Goldbach's conjecture is one of the oldest and best-known unsolved problems in
number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
and all of
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
greater than 2 is the sum of two
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), 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 ...
s.
The conjecture has been shown to hold for all integers less than but remains unproven despite considerable effort.
History
Origins
On 7 June 1742, the
Prussia
Prussia (; ; Old Prussian: ''Prūsija'') was a Germans, German state centred on the North European Plain that originated from the 1525 secularization of the Prussia (region), Prussian part of the State of the Teutonic Order. For centuries, ...
Leonhard Euler
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
(letter XLIII), in which he proposed the following conjecture:
Goldbach was following the now-abandoned convention of considering 1 to be a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), 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 ...
, so that a sum of units would be a sum of primes.
He then proposed a second conjecture in the margin of his letter, which implies the first:
Euler replied in a letter dated 30 June 1742 and reminded Goldbach of an earlier conversation they had had (""), in which Goldbach had remarked that the first of those two conjectures would follow from the statement
This is in fact equivalent to his second, marginal conjecture.
In the letter dated 30 June 1742, Euler stated:
Similar conjecture by Descartes
René Descartes
René Descartes ( , ; ; 31 March 1596 – 11 February 1650) was a French philosopher, scientist, and mathematician, widely considered a seminal figure in the emergence of modern philosophy and Modern science, science. Mathematics was paramou ...
wrote that "Every even number can be expressed as the sum of at most three primes." The proposition is similar to, but weaker than, Goldbach's conjecture.
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
said that "Descartes actually discovered this before Goldbach... but it is better that the conjecture was named for Goldbach because, mathematically speaking, Descartes was infinitely rich and Goldbach was very poor."
almost all
In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
even numbers can be written as the sum of two primes (in the sense that the fraction of even numbers up to some which can be so written tends towards 1 as increases). In 1930, Lev Schnirelmann proved that any
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
greater than 1 can be written as the sum of not more than prime numbers, where is an effectively computable constant; see Schnirelmann density. Schnirelmann's constant is the lowest number with this property. Schnirelmann himself obtained . This result was subsequently enhanced by many authors, such as Olivier Ramaré, who in 1995 showed that every even number is in fact the sum of at most 6 primes. The best known result currently stems from the proof of the weak Goldbach conjecture by
Harald Helfgott
Harald Andrés Helfgott (born 25 November 1977) is a Peruvian mathematician working in number theory. Helfgott is a researcher ('' directeur de recherche'') at the CNRS at the Institut Mathématique de Jussieu, Paris. He is best known for submitt ...
, which directly implies that every even number is the sum of at most 4 primes.
In 1924, Hardy and Littlewood showed under the assumption of the
generalized Riemann hypothesis
The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, whi ...
that the number of even numbers up to violating the Goldbach conjecture is much less than for small .
In 1948, using
sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limi ...
methods,
Alfréd Rényi
Alfréd Rényi (20 March 1921 – 1 February 1970) was a Hungarian mathematician known for his work in probability theory, though he also made contributions in combinatorics, graph theory, and number theory.
Life
Rényi was born in Budapest to A ...
showed that every sufficiently large even number can be written as the sum of a prime and an
almost prime
In number theory, a natural number is called -almost prime if it has prime factors. More formally, a number is -almost prime if and only if , where is the total number of primes in the prime factorization of (can be also seen as the sum of al ...
with at most factors.Chen Jingrun showed in 1973 using sieve theory that every
sufficiently large
In the mathematical areas of number theory and analysis, an infinite sequence or a function is said to eventually have a certain property, if it does not have the said property across all its ordered instances, but will after some instances have ...
even number can be written as the sum of either two primes, or a prime and a
semiprime
In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
Because there are infinitely many prime n ...
(the product of two primes). See
Chen's theorem
In number theory, Chen's theorem states that every sufficiently large parity (mathematics), even number can be written as the sum of either two prime number, primes, or a prime and a semiprime (the product of two primes).
It is a weakened form o ...
Bob Vaughan
Robert Charles "Bob" Vaughan FRS (born 24 March 1945) is a British mathematician, working in the field of analytic number theory.
Life
Vaughan was born 24 March 1945. He read mathematics at University College London, earning a bachelor's degre ...
showed that "most" even numbers are expressible as the sum of two primes. More precisely, they showed that there exist positive constants and such that for all sufficiently large numbers , every even number less than is the sum of two primes, with at most exceptions. In particular, the set of even integers that are not the sum of two primes has
density
Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be u ...
zero.
In 1951,
Yuri Linnik
Yuri Vladimirovich Linnik (; January 8, 1915 – June 30, 1972) was a Soviet mathematician active in number theory, probability theory and mathematical statistics.
Biography
Linnik was born in Bila Tserkva, in present-day Ukraine. He went to ...
proved the existence of a constant such that every sufficiently large even number is the sum of two primes and at most powers of 2. János Pintz and Imre Ruzsa found in 2020 that works. Assuming the
generalized Riemann hypothesis
The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, whi ...
, also works, as shown by
Roger Heath-Brown
David Rodney "Roger" Heath-Brown is a British mathematician working in the field of analytic number theory.
Education
He was an undergraduate and graduate student of Trinity College, Cambridge; his research supervisor was Alan Baker.
Career ...
Harald Helfgott
Harald Andrés Helfgott (born 25 November 1977) is a Peruvian mathematician working in number theory. Helfgott is a researcher ('' directeur de recherche'') at the CNRS at the Institut Mathématique de Jussieu, Paris. He is best known for submitt ...
to '' Annals of Mathematics Studies'' series. Although the article was accepted, Helfgott decided to undertake the major modifications suggested by the referee. Despite several revisions, Helfgott's proof has not yet appeared in a peer-reviewed publication. The weak conjecture is implied by the strong conjecture, as if is a sum of two primes, then is a sum of three primes. However, the converse implication and thus the strong Goldbach conjecture would remain unproven if Helfgott's proof is correct.
Computational results
For small values of , the strong Goldbach conjecture (and hence the weak Goldbach conjecture) can be verified directly. For instance, in 1938, Nils Pipping laboriously verified the conjecture up to . With the advent of computers, many more values of have been checked; T. Oliveira e Silva ran a distributed computer search that has verified the conjecture for (and double-checked up to ) as of 2013. One record from this search is that is the smallest number that cannot be written as a sum of two primes where one is smaller than 9781.Tomás Oliveira e Silva Goldbach conjecture verification Retrieved 20 April 2024.
Isaac Asimov
Isaac Asimov ( ; – April 6, 1992) was an Russian-born American writer and professor of biochemistry at Boston University. During his lifetime, Asimov was considered one of the "Big Three" science fiction writers, along with Robert A. H ...
and also in the 2008 mystery novel ''No One You Know'' by Michelle Richmond.
Goldbach's conjecture is part of the plot of the 2007 Spanish film '' Fermat's Room''.
Goldbach's conjecture is featured as the main topic of research of the titular character Marguerite in the 2023 French-Swiss film '' Marguerite's Theorem''.
Formal statement
Each of the three conjectures has a natural analog in terms of the modern definition of a prime, under which 1 is excluded. A modern version of the first conjecture is:
A modern version of the marginal conjecture is:
And a modern version of Goldbach's older conjecture of which Euler reminded him is:
These modern versions might not be entirely equivalent to the corresponding original statements. For example, if there were an even integer larger than 4, for a prime, that could not be expressed as the sum of two primes in the modern sense, then it would be a counterexample to the modern version of the third conjecture (without being a counterexample to the original version). The modern version is thus probably stronger (but in order to confirm that, one would have to prove that the first version, freely applied to any positive even integer , could not possibly rule out the existence of such a specific counterexample ). In any case, the modern statements have the same relationships with each other as the older statements did. That is, the second and third modern statements are equivalent, and either implies the first modern statement.
The third modern statement (equivalent to the second) is the form in which the conjecture is usually expressed today. It is also known as the "
strong
Strong may refer to:
Education
* The Strong, an educational institution in Rochester, New York, United States
* Strong Hall (Lawrence, Kansas), an administrative hall of the University of Kansas
* Strong School, New Haven, Connecticut, United ...
", "even", or "binary" Goldbach conjecture. A weaker form of the second modern statement, known as "
Goldbach's weak conjecture
In number theory, Goldbach's weak conjecture, also known as the odd Goldbach conjecture, the ternary Goldbach problem, or the 3-primes problem, states that
: Every odd number greater than 5 can be expressed as the sum of three prime number, prime ...
", the "odd Goldbach conjecture", or the "ternary Goldbach conjecture", asserts that
Heuristic justification
Statistical considerations that focus on the probabilistic distribution of prime numbers present informal evidence in favour of the conjecture (in both the weak and strong forms) for
sufficiently large
In the mathematical areas of number theory and analysis, an infinite sequence or a function is said to eventually have a certain property, if it does not have the said property across all its ordered instances, but will after some instances have ...
integers: the greater the integer, the more ways there are available for that number to be represented as the sum of two or three other numbers, and the more "likely" it becomes that at least one of these representations consists entirely of primes.
A very crude version of the
heuristic
A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
probabilistic argument (for the strong form of the Goldbach conjecture) is as follows. The
prime number theorem
In mathematics, the prime number theorem (PNT) describes the asymptotic analysis, asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by p ...
asserts that an integer selected at random has roughly a chance of being prime. Thus if is a large even integer and is a number between 3 and , then one might expect the probability of and simultaneously being prime to be . If one pursues this heuristic, one might expect the total number of ways to write a large even integer as the sum of two odd primes to be roughly
:
Since , this quantity goes to infinity as increases, and one would expect that every large even integer has not just one representation as the sum of two primes, but in fact very many such representations.
This heuristic argument is actually somewhat inaccurate because it assumes that the events of and being prime are
statistically independent
Independence is a fundamental notion in probability theory, as in statistics and the theory of stochastic processes. Two event (probability theory), events are independent, statistically independent, or stochastically independent if, informally s ...
of each other. For instance, if is odd, then is also odd, and if is even, then is even, a non-trivial relation because, besides the number 2, only odd numbers can be prime. Similarly, if is divisible by 3, and was already a prime other than 3, then would also be
coprime
In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
to 3 and thus be slightly more likely to be prime than a general number. Pursuing this type of analysis more carefully,
G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...
and
John Edensor Littlewood
John Edensor Littlewood (9 June 1885 – 6 September 1977) was a British mathematician. He worked on topics relating to analysis, number theory, and differential equations and had lengthy collaborations with G. H. Hardy, Srinivasa Ramanu ...
in 1923 conjectured (as part of their '' Hardy–Littlewood prime tuple conjecture'') that for any fixed , the number of representations of a large integer as the sum of primes with should be
asymptotically
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
equal to
:
where the product is over all primes , and is the number of solutions to the equation in
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...
, subject to the constraints . This formula has been rigorously proven to be asymptotically valid for from the work of Ivan Matveevich Vinogradov, but is still only a conjecture when . In the latter case, the above formula simplifies to 0 when is odd, and to
:
when is even, where is Hardy–Littlewood's twin prime constant
:
This is sometimes known as the ''extended Goldbach conjecture''. The strong Goldbach conjecture is in fact very similar to the
twin prime
A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair or In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin prime' ...
conjecture, and the two conjectures are believed to be of roughly comparable difficulty.
Goldbach partition function
The '' function'' is the function that associates to each even integer the number of ways it can be decomposed into a sum of two primes. Its graph looks like a
comet
A comet is an icy, small Solar System body that warms and begins to release gases when passing close to the Sun, a process called outgassing. This produces an extended, gravitationally unbound atmosphere or Coma (cometary), coma surrounding ...
and is therefore called Goldbach's comet.
Goldbach's comet suggests tight upper and lower bounds on the number of representations of an even number as the sum of two primes, and also that the number of these representations depend strongly on the value modulo 3 of the number.
Related problems
Although Goldbach's conjecture implies that every positive integer greater than one can be written as a sum of at most three primes, it is not always possible to find such a sum using a
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
that uses the largest possible prime at each step. The Pillai sequence tracks the numbers requiring the largest number of primes in their greedy representations.
Similar problems to Goldbach's conjecture exist in which primes are replaced by other particular sets of numbers, such as the squares:
* It was proven by
Lagrange
Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiaevery positive integer is the sum of four squares. See
Waring's problem
In number theory, Waring's problem asks whether each natural number ''k'' has an associated positive integer ''s'' such that every natural number is the sum of at most ''s'' natural numbers raised to the power ''k''. For example, every natural num ...
and the related Waring–Goldbach problem on sums of powers of primes.
* Hardy and Littlewood listed as their Conjecture I: "Every large odd number () is the sum of a prime and the double of a prime". This conjecture is known as Lemoine's conjecture and is also called ''Levy's conjecture''.
* The Goldbach conjecture for practical numbers, a prime-like sequence of integers, was stated by Margenstern in 1984, and proved by Melfi in 1996: every even number is a sum of two practical numbers.
* Harvey Dubner proposed a strengthening of the Goldbach conjecture that states that every even integer greater than 4208 is the sum of two
twin prime
A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair or In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin prime' ...
s (not necessarily belonging to the same pair). Only 34 even integers less than 4208 are not the sum of two twin primes; Dubner has verified computationally that this list is complete up to A proof of this stronger conjecture would not only imply Goldbach's conjecture, but also the twin prime conjecture.
* According to
Bertrand's postulate
In number theory, Bertrand's postulate is the theorem that for any integer n > 3, there exists at least one prime number p with
:n < p < 2n - 2.
A less restrictive formulation is: for every , there is always at least one ...
, for every integer , there is always at least one prime such that If the postulate were false, there would exist some integer for which no prime numbers lie between and , making it impossible to express as a sum of two primes.
Goldbach's conjecture is used when studying computational complexity. The connection is made through the
Busy Beaver
In theoretical computer science, the busy beaver game aims to find a terminating Computer program, program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps. Since an ...
function, where BB(''n'') is the maximum number of steps taken by any ''n'' state
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
that halts. There is a 27-state Turing machine that halts if and only if Goldbach's conjecture is false. Hence if BB(27) was known, and the Turing machine did not stop in that number of steps, it would be known to run forever and hence no counterexamples exist (which proves the conjecture true). This is a completely impractical way to settle the conjecture; instead it is used to suggest that BB(27) will be very hard to compute, at least as difficult as settling the Goldbach conjecture.
MathWorld
''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...
Prime Pages
The PrimePages is a website about prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is ...