Editing Gilbreath's conjecture

{{Short description|Conjecture in number theory}}
'''Gilbreath's conjecture''' is a [[conjecture]] in [[number theory]] regarding the [[integer sequence|sequences]] generated by applying the [[forward difference operator]] to consecutive [[prime number]]s and leaving the results unsigned, and then repeating this process on consecutive terms in the resulting sequence, and so forth. The statement is named after [[Norman Laurence Gilbreath|Norman L. Gilbreath]] who, in 1958, presented it to the mathematical community after observing the pattern by chance while doing arithmetic on a napkin.<ref name="Caldwell">{{cite web |first=Chris |last=Caldwell |url=http://primes.utm.edu/glossary/page.php?sort=GilbreathsConjecture |title=The Prime Glossary: Gilbreath's conjecture |work=The [[Prime Pages]] |access-date=2008-03-07 |archive-date=2012-03-24 |archive-url=https://web.archive.org/web/20120324082439/http://primes.utm.edu/glossary/page.php?sort=GilbreathsConjecture |url-status=live }}.</ref> In 1878, eighty years before Gilbreath's discovery, [[François Proth]] had, however, published the same observations along with an attempted [[mathematical proof|proof]], which was later shown to be incorrect.<ref name="Caldwell"/>

== Motivating arithmetic ==

Gilbreath observed a pattern while playing with the ordered sequence of prime numbers

:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Computing the [[absolute value]] of the difference between term ''n''&nbsp;+&thinsp;1 and term ''n'' in this sequence yields the sequence

:1, 2, 2, 4, 2, 4, 2, 4, 6, 2, ...

If the same calculation is done for the terms in this new sequence, and the sequence that is the outcome of this process, and again ''ad infinitum'' for each sequence that is the output of such a calculation, the following five sequences in this list are

:1, 0, 2, 2, 2, 2, 2, 2, 4, ...
:1, 2, 0, 0, 0, 0, 0, 2, ...
:1, 2, 0, 0, 0, 0, 2, ...
:1, 2, 0, 0, 0, 2, ...
:1, 2, 0, 0, 2, ...

What Gilbreath—and François Proth before him—noticed is that the first term in each series of differences appears to be 1.

== The conjecture ==

Stating Gilbreath's observation formally is significantly easier to do after devising a notation for the sequences in the previous section. Toward this end, let <math>(p_n)</math> denote the ordered sequence of prime numbers, and define each term in the sequence <math>(d^1_n)</math> by

: <math>d^1_n = p_{n+1} - p_n,</math>

where <math>n</math> is positive. Also, for each [[integer]] <math>k</math> greater than 1, let the terms in <math>(d_n^k)</math> be given by

: <math>d_n^k = |d_{n+1}^{k-1} - d_n^{k-1}|.</math>

Gilbreath's conjecture states that every term in the sequence <math>a_k = d_1^k</math> for positive <math>k</math> is equal to 1.

== Verification and attempted proofs ==
François Proth released what he believed to be a proof of the statement that was later shown to be flawed. [[Andrew Odlyzko]] verified that <math>d_1^k</math> is equal to 1 for <math>k \leq n = 3.4 \times 10^{11}</math> in 1993,<ref name=odlyzko>{{cite journal |first=A. M. |last=Odlyzko |author-link=Andrew Odlyzko |url=http://www.dtc.umn.edu/~odlyzko/doc/arch/gilbreath.conj.ps |title=Iterated absolute values of differences of consecutive primes |journal=Mathematics of Computation |volume=61 |year=1993 |issue=203 |pages=373–380 |doi=10.2307/2152962 |jstor=2152962 |zbl=0781.11037 |doi-access=free |access-date=2006-05-25 |archive-date=2011-09-27 |archive-url=https://web.archive.org/web/20110927061451/http://www.dtc.umn.edu/~odlyzko/doc/arch/gilbreath.conj.ps |url-status=live }}.</ref> but the conjecture remains an open problem. Instead of evaluating ''n'' rows, Odlyzko evaluated 635 rows and established that the 635th row started with a 1 and continued with only 0s and 2s for the next ''n'' numbers. This implies that the next ''n'' rows begin with a 1.

==Generalizations==
In 1980, [[Martin Gardner]] published a conjecture by [[Hallard Croft]] that stated that the property of Gilbreath's conjecture (having a 1 in the first term of each difference sequence) should hold more generally for every sequence that begins with 2, subsequently contains only [[parity (mathematics)|odd numbers]], and has a sufficiently low bound on the gaps between consecutive elements in the sequence.<ref>{{cite magazine|department=Mathematical Games|first=Martin|last=Gardner|author-link=Martin Gardner|date=December 1980|title=Patterns in primes are a clue to the strong law of small numbers|volume=243|issue=6|pages=18–28|magazine=[[Scientific American]]}}</ref> This conjecture has also been repeated by later authors.<ref>{{cite book|last=Guy|first=Richard K. | author-link=Richard K. Guy| title=Unsolved Problems in Number Theory | edition=3rd | publisher=[[Springer-Verlag]] | year=2004 | isbn=0-387-20860-7 | zbl=1058.11001 | series=Problem Books in Mathematics | page=42 }}</ref><ref>{{cite book|title=The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes|first=David|last=Darling|author-link=David J. Darling|publisher=John Wiley & Sons|year=2004|isbn=9780471667001|pages=133–134|url=https://books.google.com/books?id=HrOxRdtYYaMC&pg=PA133|contribution=Gilbreath's conjecture|access-date=2015-04-21|archive-date=2016-05-05|archive-url=https://web.archive.org/web/20160505235133/https://books.google.com/books?id=HrOxRdtYYaMC&pg=PA133|url-status=live}}</ref> However, it is false: for every initial subsequence of 2 and odd numbers, and every non-constant growth rate, there is a continuation of the subsequence by odd numbers whose gaps obey the growth rate but whose difference sequences fail to begin with 1 infinitely often.<ref>{{cite web |first=David |last=Eppstein |author-link=David Eppstein |url=https://11011110.github.io/blog/2011/02/20/anti-gilbreath-sequences.html |work=11011110 |title=Anti-Gilbreath sequences |date=February 20, 2011 |access-date=April 12, 2017 |archive-date=April 12, 2017 |archive-url=https://web.archive.org/web/20170412224428/https://11011110.github.io/blog/2011/02/20/anti-gilbreath-sequences.html |url-status=live }}</ref> {{harvtxt|Odlyzko|1993}} is more careful, writing of certain heuristic reasons for believing Gilbreath's conjecture that "the arguments above apply to many other sequences in which the first element is a 1, the others [[parity (mathematics)|even]], and where the gaps between consecutive elements are not too large and are sufficiently random."<ref name=odlyzko/><ref>{{cite journal|first1=Zachary|last1=Chase|title=A random analogue of Gilbreath's conjecture|journal=Math. Ann.|year=2023|volume=388 |issue=3 |pages=2611–2625 |doi=10.1007/s00208-023-02579-w|arxiv=2005.00530}}</ref> However, he does not give a formal definition of what "sufficiently random" means.

==See also==
* [[Difference operator]]
* [[Prime gap]]
* [[Rule 90]], a [[cellular automaton]] that controls the behavior of the parts of the rows that contain only the values 0 and 2

==References==
{{Reflist}}

{{Prime number conjectures}}

[[Category:Analytic number theory]]
[[Category:Conjectures about prime numbers]]
[[Category:Unsolved problems in number theory]]
[[Category:Triangles of numbers]]