Erdos–Graham conjecture
Encyclopedia
In combinatorial number theory, the Erdős–Graham problem is the problem of proving that, if the set {2, 3, 4, ...} of integer
s greater than one is partition
ed into finitely many subsets, then one of the subsets can be used to form an Egyptian fraction representation of unity. That is, for every r > 0, and every r-coloring of the integers greater than one, there is a finite monochromatic subset S of these integers such that
In more detail, Paul Erdős
and Ronald Graham
conjectured that, for sufficiently large r, the largest member of S could be bounded by br for some constant b independent of r. It was known that, for this to be true, b must be at least e
.
Ernie Croot proved the conjecture as part of his Ph.D thesis, and later (while a post-doctoral student at UC Berkeley) published the proof in the Annals of Mathematics
. The value Croot gives for b is very large: it is at most e167000. Croot's result follows as a corollary of a more general theorem stating the existence of Egyptian fraction representations of unity for sets C of smooth number
s in intervals of the form [X, X1+δ], where C contains sufficiently many numbers so that the sum of their reciprocals is at least six. The Erdős–Graham conjecture follows from this result by showing that one can find an interval of this form in which the sum of the reciprocals of all smooth numbers is at least 6r; therefore, if the integers are r-colored there must be a monochromatic subset C satisfying the conditions of Croot's theorem.
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s greater than one is partition
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
ed into finitely many subsets, then one of the subsets can be used to form an Egyptian fraction representation of unity. That is, for every r > 0, and every r-coloring of the integers greater than one, there is a finite monochromatic subset S of these integers such that
In more detail, Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Ronald Graham
Ronald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
conjectured that, for sufficiently large r, the largest member of S could be bounded by br for some constant b independent of r. It was known that, for this to be true, b must be at least e
E (mathematical constant)
The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...
.
Ernie Croot proved the conjecture as part of his Ph.D thesis, and later (while a post-doctoral student at UC Berkeley) published the proof in the Annals of Mathematics
Annals of Mathematics
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study. It ranks amongst the most prestigious mathematics journals in the world by criteria such as impact factor.-History:The journal began as The Analyst in 1874 and was...
. The value Croot gives for b is very large: it is at most e167000. Croot's result follows as a corollary of a more general theorem stating the existence of Egyptian fraction representations of unity for sets C of smooth number
Smooth number
In number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...
s in intervals of the form [X, X1+δ], where C contains sufficiently many numbers so that the sum of their reciprocals is at least six. The Erdős–Graham conjecture follows from this result by showing that one can find an interval of this form in which the sum of the reciprocals of all smooth numbers is at least 6r; therefore, if the integers are r-colored there must be a monochromatic subset C satisfying the conditions of Croot's theorem.