Misplaced Pages

Erdős–Graham problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Erdős–Graham conjecture) Theorem on the existence of finite sets of integers >1 whose reciprocals sum to 1

In combinatorial number theory, the Erdős–Graham problem is the problem of proving that, if the set { 2 , 3 , 4 , … } {\displaystyle \{2,3,4,\dots \}} of integers greater than one is partitioned 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 {\displaystyle r>0} , and every r {\displaystyle r} -coloring of the integers greater than one, there is a finite monochromatic subset S {\displaystyle S} of these integers such that

∑ n ∈ S 1 n = 1. {\displaystyle \sum _{n\in S}{\frac {1}{n}}=1.}

In more detail, Paul Erdős and Ronald Graham conjectured that, for sufficiently large r {\displaystyle r} , the largest member of S {\displaystyle S} could be bounded by b r {\displaystyle b^{r}} for some constant b {\displaystyle b} independent of r {\displaystyle r} . It was known that, for this to be true, b {\displaystyle b} must be at least Euler's constant e {\displaystyle e} .

Ernie Croot proved the conjecture as part of his Ph.D thesis, and later (while a post-doctoral researcher at UC Berkeley) published the proof in the Annals of Mathematics. The value Croot gives for b {\displaystyle b} is very large: it is at most e 167000 {\displaystyle e^{167000}} . Croot's result follows as a corollary of a more general theorem stating the existence of Egyptian fraction representations of unity for sets C {\displaystyle C} of smooth numbers in intervals of the form [ X , X 1 + δ ] {\displaystyle } , where C {\displaystyle 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 6 r {\displaystyle 6r} ; therefore, if the integers are r {\displaystyle r} -colored there must be a monochromatic subset C {\displaystyle C} satisfying the conditions of Croot's theorem.

A stronger form of the result, that any set of integers with positive upper density includes the denominators of an Egyptian fraction representation of one, was announced in 2021 by Thomas Bloom, a postdoctoral researcher at the University of Oxford.

See also

References

  1. Erdős, Paul; Graham, Ronald L. (1980). Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique . Vol. 28. Geneva: Université de Genève, L'Enseignement Mathématique. pp. 30–44. MR 0592420.
  2. Croot, Ernest S., III (2000). Unit Fractions (Ph.D. thesis). University of Georgia, Athens.{{cite thesis}}: CS1 maint: multiple names: authors list (link)
  3. Croot, Ernest S., III (2003). "On a coloring conjecture about unit fractions". Annals of Mathematics. 157 (2): 545–556. arXiv:math.NT/0311421. doi:10.4007/annals.2003.157.545. MR 1973054. S2CID 13514070.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  4. Bloom, Thomas F. (December 2021). "On a density conjecture about unit fractions". arXiv:2112.03726 .
  5. "Unit Fractions". b-mehta.github.io. Retrieved 2023-02-19.
  6. Cepelewicz, Jordana (2022-03-09). "Math's 'Oldest Problem Ever' Gets a New Answer". Quanta Magazine. Retrieved 2022-03-09.

External links

Categories: