In
combinatorial 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 ...
, the Erdős–Graham problem is the problem of proving that, if the set
of
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 ...
s greater than one is
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
ed into finitely many subsets, then one of the subsets can be used to form an
Egyptian fraction
An Egyptian fraction is a finite sum of distinct unit fractions, such as
\frac+\frac+\frac.
That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each ...
representation of unity. That is, for every
, and every
-coloring of the integers greater than one, there is a finite monochromatic subset
of these integers such that
:
In more detail,
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
and
Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
conjectured that, for sufficiently large
, the largest member of
could be bounded by
for some constant
independent of
. It was known that, for this to be true,
must be at least
Euler's constant
Euler's constant (sometimes also called the Euler–Mascheroni constant) is a mathematical constant usually denoted by the lowercase Greek letter gamma ().
It is defined as the limiting difference between the harmonic series and the natural ...
.
Ernie Croot
Ernie is a masculine given name, frequently a short form (hypocorism) of Ernest, Ernald, Ernesto, or Verner. It may refer to:
People
* Ernie Accorsi (born 1941), American football executive
* Ernie Adams (disambiguation)
* Ernie Afaganis (bo ...
proved the conjecture as part of his
Ph.D
A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common Academic degree, degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields ...
thesis, and later (while a
post-doctoral
A postdoctoral fellow, postdoctoral researcher, or simply postdoc, is a person professionally conducting research after the completion of their doctoral studies (typically a Doctor of Philosophy, PhD). The ultimate goal of a postdoctoral rese ...
researcher at
UC Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public university, public land-grant university, land-grant research university in Berkeley, California. Established in 1868 as the University of Californi ...
) published the proof in the ''
Annals of Mathematics
The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study.
History
The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as the ...
''. The value Croot gives for
is very large: it is at most
. Croot's result follows as a corollary of a more general theorem stating the existence of Egyptian fraction representations of unity for sets
of
smooth number
In number theory, an ''n''-smooth (or ''n''-friable) number is an integer whose prime factors are all less than or equal to ''n''. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × ...
s in intervals of the form