John D. Cook

Fermat’s little theorem says that if p is a prime and a is not a multiple of p, then ap-1 = 1 (mod p). Euler’s generalization of Fermat’s little theorem says that if a is relatively prime to m, then aφ(m) = 1 (mod m) where φ(m) is Euler’s so-called totient function. This function counts the number of positive […]

There have been a couple news stories regarding proofs of major theorems. First, an update on Shinichi Mochizuki’s proof of the abc conjecture, then an announcement that Sir Michael Atiyah claims to have proven the Riemann hypothesis. Shinichi Mochizuki’s proof of the abc conjecture Quanta Magazine has a story today saying that two mathematicians have […]

Numberphile has a nice video on the fifth root trick: someone raises a two-digit number to the 5th power, reads the number aloud, and you tell them immediately what the number was. Here’s the trick in a nutshell. For any number n, n5 ends in the same last digit as n. You could prove that […]

The Goldbach conjecture says that every even number bigger than 2 is the sum of two primes. I imagine he tried out his idea on numbers up to a certain point and guessed that he could keep going. He lived in the 18th century, so he would have done all his calculation by hand. What […]

John Baez left a comment on my post on group statistics saying It’s known that the number of groups of order p^n for prime p is p^{2n^3/27+O(n^(8/3))}. It might be fun to compare this to what Mathematica says. Here goes. First let’s let p = 2. Mathematica’s FiniteGroupCount function tops out at n = 10. And […]

How do you keep things you don’t want out of your Twitter stream? You might say just don’t follow people who post things you don’t want to read, but it’s not that simple. Some people post worthwhile original material, but they retweet things that are offensive or just not interesting. You can fix that by […]

I just ran across FiniteGroupData and related functions in Mathematica. That would have made some of my earlier posts easier to write had I used this instead of writing my own code. Here’s something I find interesting. For each n, look at the groups of order at most n and count how many are Abelian […]

Sometimes simple notation can make a big difference. One example of this is the Kronecker delta function δij which is defined to be 1 if i = j and zero otherwise. Because branching logic is built into the symbol, it can keep branching logic outside of your calculation. That is, you don’t have to write “if … […]

Let u be a real-valued function of n variables, and let v be a vector-valued function of n variables, a function from n variables to a vector of size n. Then we have the following product rule: D(uv) = v Du + u Dv. It looks strange that the first term on the right isn’t Du v. The function uv is a function […]

The p-norm of a vector is defined to be the pth root of the sum of its pth powers. Such norms occur frequently in application [1]. Yoshio Koide discovered in 1981 that if you take the masses of the electron, muon, and tau particles, the ratio of the 1 norm to the 1/2 norm is very nearly 2/3. […]

The Great Pacific Garbage Patch (GPGP) is a huge region of ocean trash twice the area of Texas. I’m trying to understand how dense it is, and running into contradictory information. This article describes a project, Ocean Cleanup, that aims to clean up half the GPGP in five years. How could you possibly clean up […]

I’ve written three blog posts lately about the classification of finite simple groups. I’m done with that topic for now. I may come back and revisit it in the future. So if group theory isn’t your favorite topic, don’t worry. I don’t know what I’ll blog about next, but it’ll probably be one of the […]

The previous post defined the groups PSL(n, q) where n is a positive integer and q is a prime power. These are finite simple groups for n ≥ 2 except for PSL(2, 2) and PSL(2, 3). Overlap among PSL(n, q) There are a couple instances where different values of n and q lead to isomorphic groups: PSL(2, 4) and PSL(2, 5) are […]

A few days ago I wrote about finite simple groups and said that I might write more about them. This post is a follow-on to that one. In my earlier post I said that finite simple groups fell into five broad categories, and that three of these were easy to describe. This post will chip […]

I posted the definitions of accuracy, precision, and recall on @BasicStatistics this afternoon. I think the tweet was popular because people find these terms hard to remember and they liked a succinct cheat sheet. Accuracy = (TP+TN)/(TP+FP+FN+TN) Precision = TP/(TP+FP) Recall = TP/(TP+FN) where T = true F = false P = positive N = […]

Today‘s exponential sum curve is simply a triangle. But yesterday‘s curve was more complex and tomorrow‘s curve will be more complex as well. Why is today’s curve so simple? The vertices of the curves are the partial sums of the series where m is the month, d is the day, and y is the last two digits of […]

There’s no direct way to define the sum of an infinite number of terms. Addition takes two arguments, and you can apply the definition repeatedly to define the sum of any finite number of terms. But an infinite sum depends on a theory of convergence. Without a definition of convergence, you have no way to […]

Once in a while you’ll hear of someone doing a digital detox, which implies there’s something toxic about being digital. And there can be, but “digital” misdiagnoses the problem. The problem mostly isn’t digital technology per se but how we use it. I think the important distinction isn’t digital vs. analog, but rather push vs. […]

Mark Dominus wrote a blog post yesterday entitled Why I never finish my Haskell programs (part 1 of ∞). In a nutshell, there’s always another layer of abstraction. “Instead of just adding lists of numbers, I can do addition-like operations on list-like containers of number-like things!” Is this a waste of time? It depends entirely […]

I was reading a recent blog post by Evelyn Lamb where she mentioned in passing that 314159 is a prime number and that made me curious how many such primes there are. Let’s look at numbers formed from the digits of π to see which ones are prime. Obviously 3 and 31 are prime. 314 […]

The prime number theorem says that π(x), the number of primes less than or equal to x, is asymptotically x / log x. So it’s easy to estimate the number of primes below some number N. But what if we want to estimate the number of prime powers less than N? This is a question […]

Simple groups are to groups as prime numbers are to numbers.A simple group has no non-trivial normal subgroups, just as a prime number has no non-trivial factors. Classification Finite simple groups have been classified into five broad categories: Cyclic groups of prime order Alternating groups Classical groups Exceptional groups of Lie type Sporadic groups. Three […]

Suppose you want to multiply two 2 × 2 matrices together. How many multiplication operations does it take? Apparently 8, and yet in 1969 Volker Strassen discovered that he could do it with 7 multiplications. Upper and lower bounds The obvious way to multiply two n × n matrices takes n³ operations: each entry in […]

I was looking back over an old blog post and noticed some code in the comments that I had overlooked. Tom Pollard gives the following code for drawing Spirograph-like curves. import matplotlib.pyplot as plt from numpy import pi, exp, real, imag, linspace def spiro(t, r1, r2, r3): """ Create Spirograph curves made by one circle of […]

I use Windows, Mac, and Linux, each for different reasons. When I run Windows, I like to have a shell that works sorta like bash, but doesn’t run in a subsystem. That is, I like to have the utility programs and command editing features that I’m used to from bash on Mac or Linux, but […]

If you don’t get any outside input into your life, you’re literally an idiot, someone in your own little world. But if you get too much outside input, you become a bland cliche. I’ve written about this a couple times, and ran across a new post this morning from someone expressing a similar idea. I […]

Pareto’s 80-20 rule says that 80% of your results often come from 20% of your effort. Maybe 80% of your profit comes from 20% of your customers, or maybe 80% of the bugs in your software are removed in the first 20% of the time you spend debugging. The rule is named after Italian economist […]

Archaic measurement systems were much more complicated than the systems we use today. Even modern imperial units, while more complicated than metric (SI) units, are simple compared to say medieval English units. Why didn’t someone think of something like the metric system a thousand years ago? I imagine they did. I don’t think they were […]

My first math classes used the terms one to one and onto to describe functions. These Germanic names have largely been replaced with their French equivalents injective and surjective. Monic and epic are the category theory analogs of injective and surjective respectively. This post will define these terms and show how they play out in several contexts. In […]

A recent video by Quanta Magazine says that the eigenvalues of random matrices and the zeros of the Riemann zeta function appear to have the same distribution. I assume by “random matrices” the video is referring specifically to Gaussian orthogonal ensembles. [Update: See the first comment below for more details. You need some assumptions on […]

It’s much easier to multiply numbers together than to factor them apart. That’s the basis of RSA encryption. In particular, the RSA encryption scheme rests on the assumption that given two large primes p and q, one can quickly find the product pq but it is much harder to recover the factors p and q. For the size numbers you’ll […]

I was playing around with some geographic features of Mathematica this morning and ran across an interesting example in the documentation for the PolyhedronProjection function given here. Here’s what you get when you project a map of the earth onto each of the five regular (Platonic) solids. How the images were made At first I right-clicked […]

A few days ago I blogged about the elliptic curve secp256k1 and its use in Bitcoin. This curve has a sibling, secp256r1. Note the “r” in the penultimate position rather than a “k”. Both are defined in SEC 2: Recommended Elliptic Curve Domain Parameters. Both are elliptic curves over a field zp where p is a […]

I wrote a new blog post this morning, but for some reason it posted with an earlier date and so it doesn’t show up at the top of the blog. Here it is: Addition carries and Markov chains

Many consider Ada Lovelace to be the first programmer. An article from a couple days ago asks what did her program do? In a sense, nothing. It was written for a computer that did not exist, so it was never executed. But it was written to compute the 8th Bernoulli number. The article’s author created […]

It’s been known for some time that carbon can form structures with positive curvature (fullerenes) and structures with zero curvature (graphene). Recently researches discovered a form of carbon with negative curvature (schwartzites). News story here. More curvature posts: Squircles Curvature of an egg Curvature and automatic differentiation

Descriptions of cryptography algorithms often start with something like “Let p be a large prime” or maybe more specifically “Let p be a 256 bit prime.” How hard is it to find large prime numbers? Let’s look at the question in base b, so we can address binary and base 10 at the same time. The prime number […]

Schnorr groups, named after Claus Schnorr, are multiplicative subgroups of a finite field. They are designed for cryptographic application, namely as a setting for hard discrete logarithm problems. The application of Schnorr groups to Schnorr signatures was patented, but the patent ran out in 2008. There has been a proposal to include Schnorr signatures in Bitcoin, […]

Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) based on elliptic curve cryptography. The particular elliptic curve is known as secp256k1, which is the curve y² = x³ + 7 over a finite field to be described shortly. Addition on elliptic curves in the plane is defined geometrically in terms of where lines intercept […]

Currying is a simple but useful idea. (It’s named after logician Haskell Curry [1] and has nothing to do with spicy cuisine.) If you have a function of two variables, you can think of it as a function of one variable that returns a function of one variable. So starting with a function f(x, y), […]

There’s no perfectly satisfying way to map the globe on to a flat surface. Every projection has its advantages and disadvantages. The Mercator projection, for example, is much maligned for the way it distorts area, but it has the property that lines of constant bearing correspond to straight lines on the map. Obviously this is […]

The original butterfly effect The butterfly effect is the semi-serious claim that a butterfly flapping its wings can cause a tornado half way around the world. It’s a poetic way of saying that some systems show sensitive dependence on initial conditions, that the slightest change now can make an enormous difference later. Often this comes up […]

In The Big Bang Theory, Sheldon Cooper explains an extension of the game Rock, Paper, Scissors by introducing two more possibilities, Lizard, and Spock. Sam Kass and Karen Bryla invented the game before it became widely known via the television show. The diagram below summarizes the rules: Alternative rules Imagine yourself in the position of Sam […]

Given two objects A and B, Hom(A, B) is simply the set of functions between A and B. From this humble start, things get more interesting quickly. Hom sets To make the above definition precise, we need to say what kinds of objects and what kinds of functions we’re talking about. That is, we specify […]

How do you operate a data-driven application before you have any data? This is known as the cold start problem. We faced this problem all the time when I designed clinical trials at MD Anderson Cancer Center. We uses Bayesian methods to design adaptive clinical trial designs, such as clinical trials for determining chemotherapy dose […]

Today’s exponential sum looks like three octagons, slightly rotated with respect to each other. I thought that the graph was tracing out one octagon, then another, then another. But that’s not what it’s doing at all. You can see for yourself by going to the exponential sum page and clicking the animate link. The curve […]

Today’s the first day of a new month, which means the exponential sum of the day will be simpler than usual. The exponential sum of the day plots the partial sums of where m, d, and y are the month, day, and (two-digit) year. The n/d term is simply n, and integer, when d = 1 and so it has no effect […]

Here’s how to construct what John Horton Conway calls his “subprime fib” sequence. Seed the sequence with any two positive integers. Then at each step, sum the last two elements of the sequence. If the result is prime, append it to the sequence. Otherwise divide it by its smallest prime factor and append that. If […]

Symmetric Gaussian matrices The previous post looked at the distribution of eigenvalues for very general random matrices. In this post we will look at the eigenvalues of matrices with more structure. Fill an n by n matrix A with values drawn from a standard normal distribution and let M be the average of A and its transpose, i.e. M = ½(A […]

Suppose you create a large matrix M by filling its components with random values. If M has size n by n, then we require the probability distribution for each entry to have mean 0 and variance 1/n. Then the Girko-Ginibri circular law says that the eigenvalues of M are approximately uniformly distributed in the unit disk in the complex plane. […]