Mixing time of a pseudorandom number generator

Today I was due to speak at the Isaac Newton Institute’s workshop on “Interactions between group theory, number theory, combinatorics and geometry”, which has obviously been canceled. I was going to speak about my work on the Hall–Paige conjecture: see this earlier post. Meanwhile Péter Varjú was going to speak about some other joint work, which I’d like to share with you now.

Consider (if you can consider anything other than coronaviral apocalapyse right now) the random process {(X_n)} in {\mathbf{Z}/p\mathbf{Z}} defined in the following way: {X_0 = 1} (or any initial value), and for {n\geq 1}

\displaystyle   X_n = aX_{n-1} + b_n. \ \ \ \ \ (1)

Here we take {a} to be a fixed integer and {b_1, b_2, \dots} a sequence of independent draws from some finitely supported measure {\mu} on {\mathbf{Z}}. As a representative case, take {a = 2} and {\mu = u_{\{-1, 0, 1\}}} (uniform on {\{-1, 0, 1\}}).

Question 1 What is the mixing time of {(X_n \bmod p)} in {\mathbf{Z}/p\mathbf{Z}}? That is, how large must we take {n} before {X_n} is approximately uniformly distributed in {\mathbf{Z}/p\mathbf{Z}}?

This question was asked by Chung, Diaconis, and Graham (1987), who were motivated by pseudorandom number generation. The best-studied pseudorandom number generators are the linear congruential generators, which repeatedly apply an affine map {x\mapsto ax+b \bmod p}. These go back to Lehmer (1949), whose parameters {a} and {b} were also subject to some randomness (from MathSciNet, “The author’s proposal for generating a sequence of `random’ 8 decimal numbers {u_n} is to start with some number {u_0\neq 0}, multiply it by 23, and subtract the two digit overflow on the left from the two right hand digits to obtain a new number {u_1}.”) The process {(X_n)} defined above is an idealized model: we assume the increment {b} develops under some external perfect randomness, and we are concerned with the resulting randomness of the iterates.

My own interest arises differently. The distribution of {X_n} can be thought of as the image of {a} under the random polynomial

\displaystyle  P_n(X) = X^n + b_1 X^{n-1} + \cdots + b_n,.

In particular, {X_n \bmod p = 0} if and only if {a} is a root of {P_n}. Thus the distribution of {X_n \bmod p} is closely related to the roots of a random polynomial (of high degree) mod {p}. There are many basic and difficult questions about random polynomials: are they irreducible, what are their Galois groups, etc. But these are questions for another day (I hope!).

Returning to Question 1, in the representative case {a = 2} and {\mu = u_{\{-1, 0, 1\}}}, CDG proved the following results (with a lot of clever Fourier analysis):

  1. The mixing time is at least

    \displaystyle (1+o(1)) \log_2 p.

    This is obvious: {X_n} is supported on a set of size {O(2^n)}, and if {n \leq (1-\varepsilon) \log_2 p} then {2^n \leq p^{1-\varepsilon}}, so at best {X_n} is spread out over a set of size {p^{1-\varepsilon}}.

  2. The mixing time is never worse than

    \displaystyle C \log p \log \log p.

  3. Occasionally, e.g., if {p} is a Mersenne prime, or more generally if {a} has small order mod {p} (or even roughly small order, suitably defined), the mixing time really is as bad as that.
  4. For almost all odd {p} the mixing time is less than

    \displaystyle 1.02 \log_2 p.

You would be forgiven for guessing that {1.02} can be replaced with {1+o(1)} with more careful analysis, but you would be wrong! In 2009, Hildebrand proved that for all {p} the mixing time of {X_n \bmod p} is at least

\displaystyle  1.004 \log_2 p.

Therefore the mixing time of {X_n \bmod p} is typically slightly more than {\log_2 p}. What is going on here? What is the answer exactly?

In a word, the answer is entropy. Recall that entropy of a discrete random variable {X} is defined by

\displaystyle  H(X) = \sum_{x : \mu(x) > 0} \mathbf{P}(X = x) \log \mathbf{P}(X = x)^{-1}.

Here are some basic facts about entropy:

  1. If {X} is uniform on a set of size {k} then {H(X) = \log k}.
  2. Entropy is subadditive: the entropy of the joint variable {(X, Y)} is at most {H(X) + H(Y)}.
  3. Entropy cannot be increased by a (deterministic) function: {H(f(X)) \leq H(X)}.

By combining the second and third facts, we have the additive version (in the sense of adding the variables) of subadditivity:

\displaystyle  H(X + Y) \leq H(X) + H(Y).

In particular, it follows from (1) that

\displaystyle  H(X_{m+n}) \leq H(X_m) + H(X_n),

and hence by the subadditive lemma {H(X_n)/n} converges. (We are thinking now of {X_n} as a random variable in {\mathbf{Z}}, not reduced modulo anything.) Call the limit {H = H(a, \mu)}.

It is easy to see in our model case {a=2, \mu = u_{\{-1, 0, 1\}}} that {H \leq \log 2} (because {X_n} has support size {O(2^n)}). If {H < \log 2}, then it follows that the mixing time of {X_n \bmod p} is strictly greater than {\log_2 p} (as {X_n} cannot approach equidistribution mod {p} before its entropy is at least {(1+o(1))\log p}).

Indeed it turns out that {H < \log 2}. This is "just a computation": since {H = \inf_{n\geq 1} H(X_n) / n}, we just need to find some {n} such that {H(X_n) / n < \log 2}. Unfortunately, the convergence of {H(X_n) / n} is rather slow, as shown in Figure 1, but we can take advantage of another property of entropy: entropy satisfies not just subadditivity but submodularity

\displaystyle  H(X+Y+Z) + H(X) \leq H(X+Y) + H(X+Z),

and it follows by a short argument that {H(X_n) - H(X_{n-1})} is monotonically decreasing and hence also convergent to {H}; moreover, unlike the quotient {H(X_n)/n}, the difference {H(X_n) - H(X_{n-1})} appears to converge exponentially fast. The result is that

\displaystyle  H / \log 2 = 0.98876\dots,

so the mixing time of {X_n \bmod p} is not less than

\displaystyle  H^{-1} \log p = (1.01136\dots ) \log_2 p.

(We can also deduce, a posteriori, that we will have {H(X_n) / n < \log 2} for {n \geq 72}, though it is out of the question to directly compute {H(X_n)} for such large {n}.)

Figure 1: The entropy difference rapidly converges. Predicted values are dashed.

This observation was the starting point of a paper that Péter and I have just finished writing. The preprint is available at arxiv:2003.08117. What we prove in general is that the mixing time of {X_n \bmod p} is indeed just {(H^{-1} + o(1)) \log p} for almost all {p} (either almost all composite {p} coprime with {a}, or alternatively almost all prime {p}). In other words, entropy really is the whole story: as soon as the entropy of {X_n} is large enough, {X_n \bmod p} should be close to equidistributed (with a caveat: see below). The lower bound is more or less clear, as above. Most of the work of the paper is involved with the upper bound, for which we needed several nontrivial tools from probability theory and number theory, as well as a few arguments recycled from the original CDG paper.

However, just as one mystery is solved, another arises. Our argument depends on the large sieve, and it therefore comes with a square-root barrier. The result is that we have to assume {H(a, \mu) > \frac12 \log a}. This is certainly satisfied in our representative case {a = 2, \mu = u_{\{-1, 0, 1\}}} (as the entropy is very close to {\log 2}), but in general it need not be, and in that case the problem remains open. The following problem is representative.

Problem 2 Let {a \geq 2} and let {\mu = u_{\{0, 1\}}}. Then {X_n} is uniform on a (Cantor) set of size {2^n}, so {H(a, \mu) = \log 2}. Show that the mixing time of {X_n \bmod p} is {(1+o(1))\log_2 p} for almost all primes {p}.

You might call this the “2–3–4–5 problem”. The case {a=2} is trivial, as {X_n} is uniform on {\{1, \dots, 2^n\}}. The case {a=3} is covered by our main theorem, since {\log 2 > \frac12 \log 3}. The case {a=4} is exactly borderline, as {\log 2 = \frac12 \log 4}, and this case is not covered by our main theorem, but we sketch how to stretch the proof to include this case anyway. For {a \geq 5} we need a new idea.

An asymptotic for the Hall–Paige conjecture

Problem 1 Let {G} be a group of order {n}. Is there a bijection {f \colon G \to G} such that the map {x \mapsto x f(x)} is also a bijection?

For example, if {G} has odd order, you can just take {f(x) = x}. Then {x f(x) = x^2}, and because every element has odd order this defines a bijection. If {G = \mathbf{F}_2^d}, then it suffices to find a linear map without an eigenvalue. Cyclic groups of even order never have complete mappings (option 1: stop reading and try to prove this as a diverting puzzle; option 2: read on, and it will be explained and become essential).

In general, a solution to Problem 1 is called a complete mapping. The definition of complete mapping is a little strange. Here is some motivation, if you want some. The construction of finite projective planes is a problem going back to Euler. You can think of a finite projective plane as a collection of {n-1} mutually orthogonal {n \times n} Latin squares, where two Latin squares are termed orthogonal if, when superimposed, the {n^2} pairs of symbols are distinct. The most familiar Latin square is the cyclic Latin square, which has entries {i + j \bmod n} for {0 \leq i, j < n}. More generally, for any group {G} of order {n}, the multiplication table of {G} is an {n \times n} Latin square. If you write down what it means for another square to be orthogonal to the {G}-based Latin square, you will find yourself re-inventing the definition of complete mapping.

Another motivation, of possibly broader interest, is simply that counting complete mappings turns out to be interesting and difficult, and requires us to hone some counting skills that, we hope, will be applicable elsewhere.

The concerted effort to answer Problem 1 began with Hall and Paige (1955). First, there is an obstruction, beginning with cyclic groups of even order. More generally, consider the abelianization {G^\textup{ab}} of {G}, and suppose all the elements of {G} have nontrivial sum in {G^\textup{ab}}. Then if {f} is a bijection the elements {x f(x)} will sum up to zero, so {x f(x)} cannot possibly be a bijection. Therefore in order for a complete mapping to exist, we must have {\prod G \in [G, G]}. Hall and Paige proved that this condition is equivalent to the Sylow 2-subgroups of {G} being trivial or noncyclic. Henceforth this condition will be called the Hall–Paige condition. Conversely, Hall and Paige conjectured that Problem 1 has a solution as long as {G} satisfies their condition.

Conjecture 2 (Hall–Paige) Every group satisfying the Hall–Paige condition has a complete mapping.

Progress on the Hall–Paige conjecture was slow. Hall and Paige (1955) proved the conjecture for solvable groups and symmetric and alternating groups, but progress on the full conjecture didn’t really get under way until the classification was established. For a complete history, see the book by Evans. Aschbacher (1990) proved various restrictions on the form of a minimal counterexample. The real breakthrough came in 2009 when Wilcox showed that a minimal counterexample would have to be simple, and furthermore could not be any of the simple groups of Lie type, which leaves only the Tits group and the 26 sporadic groups. At this point the problem is in principle a finite check, but still a mammoth one. Combining Wilcox’s technology with extensive computer algebra, Evans ruled out all of the remaining groups, with one exception: the fourth Janko group {J_4}, a group of order {86775571046077562880 \approx 9 \times 10^{19}}, and finally {J_4} was ruled out by Bray in work that remained unpublished until last year. Thus the Hall–Paige conjecture was proved. Although many people contributed, it is customary to attribute the final result to Wilcox, Evans, and Bray.

Meanwhile, another strand of study was developing. Suppose we take just the cyclic group {G = C_n}. We know there is at least one complete mapping as long as {n} is odd. But how many are there?

Problem 3 How many complete mappings does the cyclic group {C_n} have?

This problem can be compared with the well-known {n} queens puzzle: how many ways can you place {n} queens on an {n \times n} chessboard so that no two are attacking? If you make the chessboard toroidal, so that going off one edge brings you back on the opposite one, and if you only allow the queens to use one of the two diagonals, then you get an equivalent question.

Heuristically, there are {n!} bijections {f}, and for each the function {x\mapsto x f(x)} has a roughly {n!/n^n} chance of being a bijection, so you can guess that the number of complete mappings is about {n!^2 / n^n}; this conjecture is attributed to Vardi (1991) (in a weaker form) and Wanless (2011).

Conjecture 4 (Vardi–Wanless) The number of complete mappings of {C_n} is asymptotically {(e^{-1} + o(1))^n n!}.

This is where additive combinatorics enters. A few years ago Freddie Manners, Rudi Mrazović, and I started thinking about Problem 3, motivated by the observation that it can be thought of as requesting the number of solutions to

\displaystyle  \pi_1 + \pi_2 = \pi_3

(or additive triples) with {\pi_1, \pi_2, \pi_3 \in S}, where {S \subset C_n^n} is the set of bijections. The usual tool for counting additive triples (or solutions to any linear equation) is Fourier analysis; hence the problem reduces to understanding the Fourier transform of {S}. After barking up this tree (for quite a while), we were eventually able to prove the Vardi–Wanless conjecture. In fact we proved something even more precise: the solution to Problem 3 turns out to be asymptotically

\displaystyle  (e^{-1/2} + o(1)) n!^2/n^{n-1},

which differs from the Vardi–Wanless guess (though they never made a guess so precise) in two important respects: there is an extra factor of {n}, and a factor of {e^{-1/2}} (what the hell?).

Since the key to unlocking Problem 3 is Fourier analysis, it seems like we are using the abelianness of {C_n} in an absolutely essential way, but today Freddie and Rudi and I have a new announcement: we can count complete mappings in nonabelian groups too, and the asymptotic is essentially unchanged.

Theorem 5 Let {G} be a group of order {n} satisfying the Hall–Paige condition. Then the number of complete mappings of {G} is asymptotically

\displaystyle  (e^{-1/2} + o(1)) |G^\textup{ab}| n!^2 / n^n.

Here are some other highlights from our paper:

  1. The asymptotic above is begging for a heuristic explanation. We give one! It uses something called the principle of maximum entropy, which I personally can’t wait to use again. Basically, if {f} is a random bijection, {x \mapsto x f(x)} is more prone to collisions than a random function, and, heuristically, has a Gibbs distribution with a particular partition function, and a calculation shows that its probability of being a bijection is therefore smaller by a constant factor.
  2. We evaluate the next term in the asymptotic! We actually show that the number of complete mappings is

    \displaystyle  e^{-1/2} (1 + (1/3 + \textup{inv}(G)/4)/n + O(1/n^2)) |G^\textup{ab}| n!^2/n^n,

    where {\textup{inv}(G)} is the proportion of involutions in {G}. This verifies another conjecture of Wanless: that elementary abelian {2}-groups have the most complete mappings of any group of the same order. We can keep going, in principle, but really we would rather not: there is a combinatorial explosion in the number of “collision types” (in a sense we make precise), and to give the next term in the asymptotic you need to sum over all of these.

  3. Orthogonally, we can give effective estimates instead of asymptotics. For example, we can show that as long as {|G| > 10^5} and all nontrivial complex representations of {G} have degree at least {21}, then {G} has a positive number of complete mappings (in fact, within a constant factor of {n!^2/n^n} such). By combining a few such effective statements, we can cover all the simple sporadic groups, apart from the two smallest {M_{11}} and {M_{12}}. You can view this as a second-generation proof of the Evans–Bray contribution to the Hall–Paige conjecture. In fact, our proof covers all nonabelian finite simple groups except for some alternating groups, some {\textup{PSL}_2(q)'s}, and about ten other groups that we list.

The preprint is available at https://arxiv.org/abs/2003.01798. Any comments appreciated, as always!