Gilbreath’s conjecture: a Cramér random model and a deterministic analysis

Zachary Chase, Zach Hunter and I have uploaded to the arXiv our preprint Gilbreath’s conjecture: a Cramér random model and a deterministic analysis. This paper is motivated by a notorious conjecture of Gilbreath (also proposed eighty years prior by Proth), which one can state as follows: if one starts with the sequence of primes and repeatedly takes absolute differences of consecutive terms, then the first term of each subsequent row is always :

Coming from a PDE background, I like to think of this conjecture as a (discrete) nonlinear “wave equation” problem, where the primes are the “initial data”, the downward direction in the above pyramid is the arrow of “time”, and the “equation of motion” is that the value of the “scalar field” at any given point in “spacetime” is the absolute difference of the values of the two points directly above it. We will informally refer to solutions to such an “equation” as “Gilbreath arrays”.

Numerically, the conjecture has been verified for the first rows by Odlyzko. Asymptotically, the conjecture can be heuristically justified as follows. Firstly, because all primes other than are odd, it is easy to see that the first term of each row is odd, while all other terms are even. Next, if one starts with the first primes for some large and takes initial differences, then the prime number theorem tells us that the average size of the next row is about , and Cramér’s conjecture predicts that the maximum size should be . With each new row, the maximum size can only decrease (since for any natural numbers ), and so one would expect it likely on each row that the maximum size should drop by at least (unless it has already reached ). Since there are rows to go before one reaches the end, it seems extremely likely that the maximum size should drop down to at most by then, at which point the result is forced from parity reasons.

However, it seems well beyond current technology to try to make these heuristics rigorous; even the first step of proving Cramér’s conjecture is far out of reach. In our paper, we consider two more feasible directions:

What is a realistic probabilistic model of the primes, and can one confirm the (asymptotic version of the) conjecture almost surely for such a model?

Can one use deterministic arguments to reduce the (asymptotic) Gilbreath conjecture to more tractable looking (and heuristically plausible) statements about iterated differences of primes?

Let us first discuss the question of analyzing probabilistic models. One can strip away the first row and initialize using prime gaps rather than primes; it is convenient to also strip away the aforementioned parity structure, by eliminating the initial gap , and dividing all remaining gaps by , so that one now works with an initial sequence with no parity bias. The conjecture is now equivalent to the first row always being -valued:

The Cramér model suggests that the first normalized prime gaps should behave like geometric random variables of mean about . My co-author, Zachary Chase, established an analogue of the Gilbreath conjecture for a more slowly growing model. Here is a special case of his main theorem:

Theorem 1 Suppose the initial row entries of a Gilbreath array are drawn independently from a uniform distribution on for some . Then almost surely, all but finitely many of the rows have a -valued first entry.

The Cramér model morally corresponds to a value of comparable to , which is too large for the above theorem to apply. However, we were able to improve the argument, basically allowing to be anything of size . Furthermore, it was not necessary that the distribution be uniform: the important hypothesis was that the distribution not be concentrated in any -separated set, such as the even numbers, the odd numbers, or the multiples of . (See the paper for the precise formulation of “non-concentrated”.) Such a hypothesis is needed since if for instance all initial entries were divisible by , then this property would propagate down the array, and it would become extremely unlikely that the initial values would remain -valued. Our hypotheses are obeyed by the Cramér random model, and so we obtain a heuristic confirmation of the original Gilbreath conjecture for the primes.

One can informally explain our proof of the above result as follows. We consider the portion of the array generated by the first values for some large . Suppose that at some point deep in this portion of the array, a value that is larger than is attained. Then the two values above must satisfy the equation . So, either one of these values is at least , or one of them is and the other is . If one iterates this observation, one sees that is the base of an upside-down triangle of values, topped off by at least one location where the value is at least . If one iterates that observation in turn, we see that forms the base of a “tower” of upside-down triangles stacked atop each other, with the number of such triangles bounded by the maximum size of the initial data (in the “backwards light cone” of ). In the regime, it turns out that the number (or “entropy”) of such towers is subexponential in . So if we can show that each tower only can be created with an exponentially small probability, we can conclude by the standard techniques of the union bound and the Borel, Cantelli lemma.

At this point we use the following elementary observation. Suppose that some finite Gilbreath array coming from say initial data has been generated, and consider the effect of adding a new value to the initial data, which then triggers iterations of the absolute value difference operation for various values of until one reaches the new bottom vertex of the array. This difference operation has the property that the preimage of any -separated set is still -separated. Iterating this, we see that the set of values that make iterate to a -valued bottom vertex is also -separated. So as long as the distribution of avoids -separated sets, one can iterate this observation in to show that it is exponentially rare that large triangles of -valued vertices can be created.

We also consider an asymptotic continuous random model, in which the initial data are not natural numbers, but instead independently random non-negative real numbers with an exponential distribution, which we can normalize to have mean ; this heuristically is an approximate model for the Gilbreath array generated by the first normalized prime gaps, after dividing by the mean . In this normalized model, each entry of the row ends up having the same mean . The first few values of can be computed explicitly

However, the asymptotic behavior of remains unclear to us. We were able to show an inequality for any , indicating that cannot decay faster than , but we do not know whether this is the true decay rate. In any case a decay rate of (which is very weakly supported by numerical evidence) is consistent with the Gilbreath conjecture, as it would indicate that the Gilbreath array from the first prime gaps should end up being almost entirely -valued by merely steps, well before the steps needed to reach the bottom of the array.

Now we turn to deterministic analysis of Gilbreath arrays. Suppose we found some initial data that did not grow too quickly (e.g., one had a Cramér-type bound ), but still iterated to a final value that was not . What features of the initial data could generate such a failure of a Gilbreath-type conjecture? One way in which the conjecture could fail is if the Gilbreath iteration somehow produced a reasonably long consecutive string of zeroes (say, longer than ), as then the next few iterations would not act to decrease the magnitude of the non-zero entries bordering this string of zeroes. Such a scenario would be heuristically rate, as the parity of each element of the array can be worked out explicitly using the parity identity , and so constant-parity sequences of length say should be almost surely non-existent asymptotically by standard probabilistic heuristics.

Another bad scenario is if the Gilbreath iteration, after some medium number of iterations, produced an extremely long consecutive block (say of length ) which was entirely -valued for some . This block would then persist as a -block for a large number of iterations (equal to the length of the block), thus potentially delaying for a significant time the drop-down of the maximal value to below . For odd , one can use the parity analysis alluded to earlier to argue that the formation of such a block is extremely unlikely; but for even , we can only use such heuristics if we make strong assumptions of joint independence, as we did in the probabilistic analysis in our paper.

In any event, we were able to use purely elementary methods to establish an “inverse theorem” that states, roughly speaking, that the above two scenarios are the only ways in which a Gilbreath array can fail to have a -valued first entry. This basically arises from a more careful analysis of the towers of triangles alluded to earlier. (A previous argument involved considering ways to pack a large triangle by smaller triangles, leading to a MathOverflow question which was nicely answered by Fedja Nazarov and Anders Martinsson, but we later managed to optimize the argument to the point where the answer to this packing question was no longer needed.) So this in principle reduces the (deterministic) Gilbreath conjecture to several more tractable-looking (though complicated to state) assertions, though proving those latter statements seems well out of reach at the moment.