Gilbreath's conjecture is a
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...
in
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
regarding the
sequences
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
generated by applying the
forward difference operator
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
to consecutive
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
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 L. Gilbreath who, in 1958, presented it to the mathematical community after observing the pattern by chance while doing arithmetic on a napkin.
[.] In 1878, eighty years before Gilbreath's discovery,
François Proth had, however, published the same observations along with an attempted
proof
Proof most often refers to:
* Proof (truth), argument or sufficient evidence for the truth of a proposition
* Alcohol proof, a measure of an alcoholic drink's strength
Proof may also refer to:
Mathematics and formal logic
* Formal proof, a con ...
, which was later shown to be false.
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'' + 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
denote the ordered sequence of prime numbers, and define each term in the sequence
by
:
where
is positive. Also, for each
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
greater than 1, let the terms in
be given by
:
Gilbreath's conjecture states that every term in the sequence
for positive
is equal to 1.
Verification and attempted proofs
, no valid proof of the conjecture has been published. As mentioned in the introduction, François Proth released what he believed to be a proof of the statement that was later shown to be flawed.
Andrew Odlyzko
Andrew Michael Odlyzko (Andrzej Odłyżko) (born 23 July 1949) is a Polish- American mathematician and a former head of the University of Minnesota's Digital Technology Center and of the Minnesota Supercomputing Institute. He began his career in ...
verified that
is equal to 1 for
in 1993,
[.] 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
Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of L ...
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
odd numbers, and has a sufficiently low bound on the gaps between consecutive elements in the sequence. This conjecture has also been repeated by later authors. 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.
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
even, and where the gaps between consecutive elements are not too large and are sufficiently random."
[ However, he does not give a formal definition of what "sufficiently random" means.
]
See also
* Difference operator
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a paramete ...
* Prime gap
A prime gap is the difference between two successive prime numbers. The ''n''-th prime gap, denoted ''g'n'' or ''g''(''p'n'') is the difference between the (''n'' + 1)-th and the
''n''-th prime numbers, i.e.
:g_n = p_ - p_n.\
W ...
* Rule 90, a cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tess ...
that controls the behavior of the parts of the rows that contain only the values 0 and 2
References
{{Prime number conjectures
Analytic number theory
Conjectures about prime numbers
Unsolved problems in number theory
Triangles of numbers