Let $S$ be the set of limit points of $(p_{n+1}-p_n)/\log n$. This problem asks whether $S=[0,\infty]$. Although this conjecture remains unproven, a lot is known about $S$. Some highlights:

• $\infty\in S$ by Westzynthius' result [We31] on large prime gaps,
• $0\in S$ by the work of Goldston, Pintz, and Yildirim [GPY09] on small prime gaps,
• Erdős [Er55] and Ricci [Ri56] independently showed that $S$ has positive Lebesgue measure,
• Hildebrand and Maier [HiMa88] showed that $S$ contains arbitrarily large (finite) numbers,
• Pintz [Pi16] showed that there exists some small constant $c>0$ such that $[0,c]\subset S$,
• Banks, Freiberg, and Maynard [BFM16] showed that at least $12.5\%$ of $[0,\infty)$ belongs to $S$,
• Merikoski [Me20] showed that at least $1/3$ of $[0,\infty)$ belongs to $S$, and that $S$ has bounded gaps.

Asked by Erdős and Selfridge (sometimes also with Schinzel). They also ask can there be such that no two of the moduli divide each other, or where all the moduli are odd and square-free?

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$.

Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST21] have proved that if the moduli are all squarefree then at least one must be even.

Conjectured by Erdős and Graham, who also ask about a density-type version: for example, is \[\sum_{\substack{a\in A\\ a>N}}\frac{1}{a}\gg \log N\] a sufficient condition for $A$ to contain the moduli of a covering system? The answer (to both colouring and density versions) is no, due to the result of Hough [Ho15] on the minimum size of a modulus in a covering system - in particular one could colour all integers $<10^{18}$ different colours and all other integers a new colour.

Crocker [Cr71] has proved there are are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Erdős believes this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$.

Odlyzko has checked this up to $10^7$. Granville and Soundararajan [GrSo98] have proved that this is very related to the problem of finding primes $p$ for which $2^p\equiv 2\pmod{p^2}$ (for example this conjecture implies there are infinitely many such $p$).

Erdős thinks that proving this with two powers of 2 is perhaps easy.

Asked by Erdős and Sárközy, who proved that $A$ must have density $0$. The set of $p^2$, where $p\equiv 3\pmod{4}$ is prime, has this property. Note that such a set cannot contain a three-term arithmetic progression, and hence by the bound of Kelley and Meka [KeMe23] we have \[\lvert A\cap\{1,\ldots,N\}\rvert\ll \exp(-O((\log N)^{1/12}))N\] for all large $N$.

Asked by Erdős, Sárközy, and Szemerédi, who constructed a set which shows this would be the best possible.

Erdős suggested that a computer could be used to explore this, and did not see any other method to attack this.

Tao [Ta23] has proved that this series does converge assuming a strong form of the Hardy-Littlewood prime tuples conjecture.

Erdős called this conjecture 'rather silly'. Using covering congruences Erdős [Er50] proved that the set of such odd integers contains an infinite arithmetic progression.

The first prime without this property is $97$.

It is easy to see that almost all numbers are not practical. This may be true with $m=n!$. Erdős originally showed that $h(n!) <n$. Vose [Vo85] has shown that $h(n!)\ll n^{1/2}$.

Related to [304].

Conjectured by Erdős and Lovász [ErLo75], who proved that this holds if $\mathcal{F}\leq \frac{8}{3}n-4$. Disproved by Kahn [Ka94] who constructed an infinite sequence of $\mathcal{F}$, each a family of sets of size $n\to\infty$, such that any set $S$ of size $n-1$ is disjoint from at least one set in $\mathcal{F}$. The Erdős and Lovász constant of $8/3$ has not been improved.

Conjectured by Bollobás and Erdős [BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao [FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most \[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]

The blow-up of $C_5$ shows that this would be the best possible. The best known bound is due to Balogh, Clemen, and Lidicky [BCL21], who proved that deleting at most $1.064n^2$ edges suffices.

Győri proved this with $1.03n^5$, which has been improved by Füredi. The answer is yes, as proved independently by Grzesik [Gr12] and Hatami, Hladky, Král, Norine, and Razborov [HHKNR13].

Asked by Erdős and Tenenbaum. Ruzsa has found a counterexample. Tenenbaum asked the weaker variant (still open) where for every $\epsilon>0$ there is some $k=k(\epsilon)$ such that at least $1-\epsilon$ density of all integers have a divisor of the form $a+k$ for some $a\in A$.

Proved by Lorentz [Lo54].

Erdős [Er54] proved by the probabilistic method that such a set $A$ exists with $\lvert A\cap\{1,\ldots,N\}\rvert\ll (\log N)^2$.

Erdős observed that this value is finite and $>1$.

Erdős proved this is true with $k$ replaced by $2k$ in the denominator.

The minimum overlap problem. The example (with $N$ even) $A=\{N/2+1,\ldots,3N/2\}$ shows that $c\leq 1/2$ (indeed, Erdős initially conjectured that $c=1/2$). The lower bound of $c\geq 1/4$ is trivial, and Scherk improved this to $1-1/\sqrt{2}=0.29\cdots$. The current records are \[0.379005 < c < 0.380926\cdots,\] the lower bound due to White [Wh22] and the upper bound due to Haugland [Ha16].

The answer is no by Ruzsa [Ru87], who proved that if $A$ is an essential component then there exists some constant $c>0$ such that $\lvert A\cap \{1,\ldots,N\}\rvert \geq (\log N)^{1+c}$ for all large $N$.

The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. Erdős proved that for every infinite Sidon set $A$ we have \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\] and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

This follows from the colouring result of Croot [Cr03]. Obtaining better quantitative aspects seems interesting still -- note that Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$. Is there a better bound?

The answer is yes, as proved by Croot [Cr03].

This would follow immediately from the twin prime conjecture. The answer is yes, proved by Ford, Luca, and Pomerance [FLP10].

Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.

Solved by Tao [Ta23b], who proved that \[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]

Carmichael has asked whether there is an integer $t$ for which $\phi(n)=t$ has exactly one solution. Erdős has proved that if such a $t$ exists then there must be infinitely many such $t$.

Asked by Erdős and Szemerédi [ErSz83]. Solved by Chang [Ch03].

This was disproved for $k\geq 8$ by Khachatrian [AhKh94]. Erdős asks if the conjecture remains true provided $n\geq (1+o(1))p_k^2$.

Conjectured by Hajnal and Erdős and solved by Liu and Montgomery [LiMo20]. The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

Conjectured by Bollobás and Erdős. Bollobás and Shelah have confirmed this for $k=1$. Proved by Gyárfás [Gy92], who proved the stronger result that, if $G$ is 2-connected, then $G$ is either $K_{2k+2}$ or contains a vertex of degree at most $2k$.

A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.

If $G$ is not bipartite the answer is yes, proved by Erdős, Frankl, and Rödl [ErFrRo86]. The answer is no for $G=C_6$, the cycle on 6 vertices. Morris and Saxton [MoSa16] have proved there are at least \[2^{(1+c)\mathrm{ex}(n;C_6)}\] such graphs for infinitely many $n$, for some constant $c>0$. It is still possible (and conjectured by Morris and Saxton) that the weaker bound of \[2^{O(\mathrm{ex}(n;G))}\] holds for all $G$.

Conjectured by Erdős and Simonovits, who could not even prove that at least $2$ copies of $C_4$ are guaranteed.

He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.

Conjectured by Erdős and Hajnal [ErHa89], who proved that a complete graph or independent set must exist on \[\geq \exp(c_H\sqrt{\log n})\] many vertices, where $c_H>0$ is some constant. This was improved by Bucić, Nguyen, Scott, and Seymour [BNSS23] to \[\geq \exp(c_H\sqrt{\log n\log\log n}).\]

Erdős, Hajnal, and Shelah have shown that $G_1$ and $G_2$ must both contain all sufficiently large cycles.

Conjectured by Mihók and Erdős. It is likely that $2^n$ can be replaced by any sufficiently quickly growing sequence (e.g. the squares).

Gyárfás, Komlós, and Szemerédi [GyKoSz84] have proved that this sum is $\gg \log k$. Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$.

Erdős [Er48] proved that $\sum_n \frac{d(n)}{2^n}$ is irrational, where $d(n)$ is the divisor function.

Erdős could prove this is true for almost all $n\equiv 0\pmod{4}$.

This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(a,b)$ is unknown.

Proved by Reed [Re99]. (Thanks also to Reed for pointing out that the case $k=0$ is trivial, since if $G$ is not bipartite then $G$ contains an odd cycle.)

Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82].

Conjectured by Erdős, Faudreee, and Ordman. This would be best possible, as witnessed by dividing the vertices of $K_n$ into two equal parts and colouring all edges between the parts red and all edges inside the parts blue.

The answer is yes, proved by Gruslys and Letzter [GrLe20].

Asked by Erdős, Faudree, Rousseau, and Schelp [ErFaRoSc93]. $K_4$ is the only known example of such a graph.

In other words, is $K_{3,3}$ Ramsey size linear? Asked by Erdős, Faudree, Rousseau, and Schelp [ErFaRoSc93].

Asked by Erdős, Ordman, and Zalcstein [ErOrZa93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$).

Conjectured by Erdős, Fajtlowicz, and Staton. It is known that $F(5)=3$ and $F(7)=4$. Ramsey's theorem implies that $F(n)\gg \log n$. Bollobás observed that $F(n)\ll n^{1/2+o(1)}$. Alon, Krivelevich, and Sudakov [AKS07] have improved this to $n^{1/2}(\log n)^{O(1)}$.

Conjectured by Erdős and Faudree, who showed that $f(n) > 2^{n/2}$, and further speculate that $f(n)/2^{n/2}\to \infty$. This conjecture was proved by Verstraëte [Ve04], who proved the number of such sets is \[\ll 2^{n-n^c}\] for some constant $c>0$.

A weaker version of the conjecture asks for some constant $c$ such that $f(m)>f(n)-c$ for all $m>n$. This question can be asked for other graphs than $C_4$.

Erdős originally conjectured that $R(G)\geq R(k)$, which is trivial for $k=3$, but fails already for $k=4$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 1/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.

For $n=5$ the regular pentagon is the unique such set (Erdős mysteriously remarks this was proved by 'a colleague').

Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor n/2\rfloor$ distinct distances is still open.

Solved by Fishburn [Al63]. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$. The stronger conjecture that $\sum f(u_i)^2$ is maximal for the regular $n$-gon (for large enough $n$) is still open.

Conjectured by Erdős and Moser. Füredi has proved an upper bound of $O(n\log n)$. Edelsbrunner and Hajnal have constructed $n$ such points with $2n-7$ pairs distance $1$ apart.

Open even for convex polygons.

Danzer has found a convex polygon on 9 points such that every vertex has three vertices equidistant from it (but this distance depends on the vertex), and Fishburn and Reeds have found a convex polygon on 20 points such that every vertex has three vertices equidistant from it (and this distance is the same for all vertices).

If this fails for $4$, perhaps there is some constant for which it holds?

Erdős could not even prove $h(n)\geq n$. Pach has shown $h(n)<n^{\log_23}$.

Perhaps the diameter is $\geq n-1$ for all large $n$ (Piepmeyer has an example of $9$ such points with diameter $<5$).

Even replacing $n^{1/2}$ with any function $\to\infty$, this conjecture is open.

Perhaps the diameter is even $\geq n-1$ for sufficiently large $n$. Kanold proved the diameter is $\geq n^{3/4}$. The bounds on the distinct distance problem [89] proved by Guth and Katz [GuKa15] imply a lower bound of $\gg n/\log n$.

Elekes [El84] has a simple construction of a set with $\gg n^{3/2}$ such circles. This may be the correct order of magnitude.

It is trivial from the Cauchy-Schwarz inequality that $f(k^2)=4k$. Erdős also asks for which $n$ is it true that $f(n+1)=f(n)$.

Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $k=3$ case. The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.

The Erdős sumset conjecture. Proved by Moreira, Richter, and Robertson [MRR19].

Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82]. This fails if the graph has chromatic number $\aleph_0$.

Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82].

Conjectured by Erdős and Simonovits. Disproved by Janzer [Ja21].

The lower bound is easy: this is $\geq n$ and equality holds if and only if $p(z)=z^n$. The Chebyshev polynomial shows that the constant $1/2$ in this conjecture is best possible. Erdős originally conjectured this without the $o(1)$ term but Szabados observed that was too strng. Pommeranke has proved an upper bound of $O(n^2)$.

Conjectured by Erdős, Herzog, and Piranian [ErHePi58]. The lower bound $\mu(A) \gg n^{-4}$ follows from a result of Pommerenke [Po61]. The stronger lower bound $\gg (\log n)^{-O(1)}$ is still open.

Wagner [Wa88] proves, for $n\geq 3$, the existence of such polynomials with \[\mu(A) \ll_\epsilon (\log\log n)^{-1/2+\epsilon}\] for all $\epsilon>0$.

Pyber [Py87] has proved there exist constants $c_2>c_1>1$ such that $c_1^n<h(n)<c_2^n$.

Conjectured by Erdős and Hajnal.

Conjectured by Erdős, Sós, and Sárkzözy [ErSaSo95], who proved this for $F_3(N)$. Erdős [Er35] earlier proved that $F_4(N)=o(N)$. Erdős also asks about $F(N)$, the size of the largest such set such that the product of no odd number of $a\in A$ is a square. Ruzsa proved that $\lim F(N)/N <1$. The value of $\lim F(N)/N$ is unknown, but it is $>1/2$.

Conjectured by Erdős, Pomerance, and Sárközy [ErPoSa97] prove this when $f$ is the divisor function or the number of distinct prime divisors of $n$, but Erdős believes it is false when $f(n)=\phi(n)$ or $\sigma(n)$.

Conjectured by Burr, Erdős, Graham, and Li [BuErGrLi96]. Pomerance observed that the condition $\sum 1/(d_i-1)\geq 1$ is necessary. In [BuErGrLi96] they prove the property holds for $\{3,4,7\}$.

Conjectured by Burr, Erdős, Graham, and Li [BuErGrLi96].

Conjectured by Erdős, Kohayakava, and Gyárfás. Edwards [Ed73] proved that $f(m)\geq 0$ always. Note that $f(\binom{n}{2})= 0$, taking $K_n$. Solved by Alon [Al96], who showed $f(n^2/2)\gg n^{1/2}$, and also showed that $f(m)\ll m^{1/4}$ for all $m$. The best possible constant in $f(m)\leq Cm^{1/4}$ is unknown.

Conjectured by Erdős and Gyárfás, who proved the existence of some $C>1$ such that $R(n;3,r)>C^{\sqrt{n}}$. Note that when $r=k=2$ we recover the classic Ramsey numbers. It is likely that for all $r,k\geq 2$ there exists some $C_1,C_2>1$ (depending only on $r$) such that \[ C_1^{n^{1/k-1}}< R(n;k,r) < C_2^{n^{1/k-1}}.\] Antonio Girao has pointed out that this problem as written is easily disproved: the obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), as soon as $N \geq C^n$ for some absolute constant $C>1$. This implies $R(n;3,2) \geq C^{n}$, contradicting the conjecture. Perhaps Erdős had a different problem in mind, but it is not clear what that might be. It would presumably be one where the natural probabilistic argument would deliver a bound like $C^{\sqrt{n}}$ as Erdős and Gyárfás claim to have achieved via the probabilistic method.

Conjectured by Andrásfai and Erdős. It is possible that such a graph could contain an infinite complete graph.

It is easy to see that we must have $\lvert A\rvert \ll N^{1/2}$. Csaba has constructed such an $A$ with $\lvert A\rvert \gg N^{1/5}$.

Asked by Erdős and Pach. Pannowitz proved that this is true for the largest distance between points of $A$, but it is unknown whether a second such distance must occur.

Asked by Erdős and Pach. Simonovits observed that the subsets of $[3m-1]$ of size $m$, two sets joined by edge if and only if they are disjoint, forms a triangle-free graph of diameter $2$ which is regular of degree $\binom{2m-1}{m}$, showing that $f(n)=o(n)$ infinitely often. This graph may have the minimal possible $f$, but Erdős encourages the reader to try and find a better graph.

Asked by Erdős and Gyárfás, who proved that this is the case when $G$ has maximum degree $\ll \log n/\log\log n$. A construction of Simonovits shows that this conjecture is false if we just have maximum degree $\leq Cn^{1/2}$, for some large enough $C$.

Asked by Erdős and Gyárfás, who proved that \[\frac{5}{6}(n-1) < f(n)<n,\] and that $f(9)=8$. Erdős believed the upper bound is closer to the truth. In fact the lower bound is: Bennett, Cushman, Dudek,and Pralat [BCDP22] have shown that \[f(n) \sim \frac{5}{6}n.\] Joos and Mubayi [JoMu22] have found a shorter proof of this.

Erdős and Selfridge proved that $N$ can never be a perfect power. Erdős remarked that this 'seems hopeless at present'.

When $p$ is prime Berlekamp [Be68] has proved $W(p+1)\geq p2^p$. Gowers [Go01] has proved \[W(k) \leq 2^{2^{2^{2^{2^{k+9}}}}}.\]

Green and Tao [GrTa08] have proved that there must always exist some $k$ primes in arithmetic progression, but these need not be consecutive. Erdős called this conjecture 'completely hopeless at present'.

Erdős says it would also be of interest to determine the dependence of $n$ on $\epsilon$ - perhaps $\epsilon>1/(\log n)^c$ for some $c>0$ is necessary.

The current best bounds known are \[2^{c^{\frac{k}{\log k}}}\leq F(k) \leq c_0^{(\frac{1}{5}+o(1))2^k},\] where $c>0$ is some absolute constant and $c_0=1.26408\cdots$ is the 'Vardi constant'. The lower bound is due to Konyagin [Ko14] and the upper bound to Elsholtz and Planitzer [ElPl21].

Asked by Erdős and Nešetřil. They also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved independently by Chung-Trotter and Gyárfás-Tuza.

Asked by Erdős and Nešetřil. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

It is easy to see that $h(n)\leq n-\sqrt{n}$ and that $h(n)\leq n-H(n)$. Conjectured by Erdős and Gallai, who were unable to make progress even assuming $G$ is $K_4$-free. Erdős remarked that this conjecture is 'perhaps completely wrongheaded'.

There may even be $\gg \lvert A\rvert^2$ many such $a$. A similar question can be asked for truncations of finite Sidon sets.

A similar problem can be asked for infinite Sidon sets.

Lindström [Li98] has shown this is true for $A$ itself, subsequently strengthened by Kolountzakis [Ko99].

This may even hold with $k\approx \epsilon N^{1/2}$.

Yes, as shown by Pilatte [Pi23].

If we replace $2$ by $1$ then $A$ is a Sidon set, for which Erdős proved this is true.

The current bounds are \[ \frac{n^{3/2}}{(\log n)^{3/2}}\ll R(C_4,K_n)\ll \frac{n^2}{(\log n)^2}.\] The upper bound is due to Szemerédi (mentioned in [ErFaRoSc78]), and the lower bound is due to Spencer [Sp77].

Investigated by Erdős and Freud. This has been discussed on MathOverflow, where LeechLattice shows \[h(N) \ll N^{2/3}.\] The observation of Zachary Hunter in that question coupled with the bounds of Kelley-Meka [KeMe23] imply that \[h(N) \gg \exp(c(\log N)^{1/12})\] for some $c>0$.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that \[c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.\]

The Burr-Erdős conjecture. Solved by Lee [Le16], who proved that \[ R(H) \leq 2^{2^{O(d)}}n.\]

Erdős [Er35] proved that this sum always converges for a primitive set. Solved by Lichtman [Li23].

Erdős, Hajnal, and Rado proved that $R_r(k)$ grows like a tower of exponentials of height at least $r-2$ and at most $r-1$. Hajnal has proved that $r-1$ is the correct height if we consider the corresponding hypergraph Ramsey number for $4$ colours.

This limit was proved to exist by Graham, Spencer, and Witsenhausen [GrSpWi77]. Similar questions can be asked for the density or upper density of infinite sets without such configurations.

Gerver [Ge77] has proved \[f(k) \geq (1+o(1))k\log k.\] It is trivial that \[\frac{f(k)}{\log W(k)}\geq \frac{1}{2},\] but improving the right-hand side to any constant $>1/2$ is open.

The Sparse Ruler problem. Rédei asked whether this limit exists, which was proved by Erdős and Gál [ErGa48]. Bounds on the limit were improved by Leech [Le56]. The limit is known to be in the interval $[1.56,\sqrt{3}]$. The lower bound is due to Leech [Le56], the upper bound is due to Wichmann [Wi63]. Computational evidence by Pegg [Pe20] suggests that the upper bound is the truth. A similar question can be asked without the restriction $A\subset \{0,1,\ldots,N\}$.

The 'density Hales-Jewett' problem. This was proved by Furstenberg and Katznelson [FuKa91]. A new elementary proof, which gives quantitative bounds, was proved by the Polymath project [Po09].

First asked by Hindman. Hindman [Hi80] has proved this is false (with 7 colours) if we ask for an infinite $A$.

Moreira [Mo17] has proved that in any finite colouring of $\mathbb{N}$ there exist $x,y$ such that $\{x,x+y,xy\}$ are all the same colour.

Alweiss [Al23] has proved that, in any finite colouring of $\mathbb{Q}\backslash \{0\}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour. Bowen and Sabok [BoSa22] had proved this earlier for the first non-trivial case of $\lvert A\rvert=2$.

For some colourings a single equilateral triangle has to be excluded, considering the colouring by alternating strips. Shader [Sh76] has proved this is true if we just consider a single right-angled triangle.

Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS73] proved that every Ramsey set is 'spherical': it lies on the surface of some sphere. Graham has conjectured that every spherical set is Ramsey. Leader, Russell, and Walters [LRW12] have alternatively conjectured that a set is Ramsey if and only if it is 'subtransitive': it can be embedded in some higher-dimensional set on which rotations act transitively.

Sets known to be Ramsey include vertices of $k$-dimensional rectangles [EGMRSS73], non-degenerate simplices [FrRo90], trapezoids [Kr92], and regular polygons/polyhedra [Kr91].

Proved by Sárkzözy [Sa85] for all sufficiently large $n$, and by Granville and Ramaré [GrRa96] for all $n\geq 5$.

More generally, if $f(n)$ is the largest integer such that, for some prime $p$, we have $p^{f(n)}$ dividing $\binom{2n}{n}$, then $f(n)$ should tend to infinity with $n$. Can one even disprove that $f(n)\gg \log n$?

No decent bound is known even for $N(k,1)$. Probabilistic methods imply that, for every fixed constant $c>0$, we have $N(k,ck)>C_c^k$ for some $C_c>1$.

Cantor, Erdős, Schreiber, and Straus [Er66] proved that $h(d)\ll d!$ is possible. Van der Waerden's theorem implies that $h(d)\to \infty$. Beck [Be17] has shown that $h(d) \leq d^{8+\epsilon}$ is possible for every $\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$.

Erdős remarks 'it seems certain that the answer is affirmative'. This was solved by Beck [Be81]. Recently Beck [Be17] proved that one can replace $\ll_d 1$ with $\ll d^{4+\epsilon}$ for any $\epsilon>0$.

Erdős remarks the upper bound $o(N^2)$ is certainly false for $\ell >\epsilon \log N$. The answer is yes: Fox and Pohoata [FoPo20] have shown that, for all fixed $1\leq k<\ell$, \[F_k(N,\ell)=N^{2-o(1)}\] and in fact \[F_{k}(N,\ell) \leq \frac{N^2}{(\log\log N)^{C_\ell}}\] where $C_\ell>0$ is some constant.

This is trivially true if $\mathcal{F}$ does not contain any bipartite graphs, since by the Erdős-Stone theorem if $H\in\mathcal{F}$ has minimal chromatic number $r\geq 2$ then \[\mathrm{ex}(n;H)=\mathrm{ex}(n;\mathcal{F})=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}.\] Erdős and Simonovits observe that this is false for infinite families $\mathcal{F}$, e.g. the family of all cycles.

Conjectured by Burr and Erdős. The trivial bound is \[R(Q_n) \leq R(K_{2^n})\leq C^{2^n}\] for some constant $C>1$. This was improved a number of times; the current best bound due to Tikhomirov [Ti22] is \[R(Q_n)\ll 2^{(2-c)n}\] for some small constant $c>0$. (In fact $c\approx 0.03656$ is permissible.)

Asked by Erdős and Sauer. Resolved by Janzer and Sudakov [JaSu22], who proved that there exists some $C=C(k)>0$ such that any graph on $n$ vertices with at least $Cn\log\log n$ edges contains a $k$-regular subgraph.

A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.

Conjectured by Erdős and Gallai. The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.

Originally considered by Moser. It is trivial that $f_3(n)\geq R_3(3^n)$, the maximal size of a subset of $\{1,\ldots,3^n\}$ without a three-term arithmetic progression. Moser showed that \[f_3(n) \gg \frac{3^n}{\sqrt{n}}.\]

The answer is yes, which is a corollary of the density Hales-Jewett theorem, proved by Furstenberg and Katznelson [FuKa91].

Originally due to Straus. It is known that \[N^{1/4}\ll F(N) \ll (N\log N)^{1/2}\] The lower bound is due to Bosznay [Bo89] and the upper bound to Erdős and Sárközy [ErSa90].

Originally asked by Cohen. Erdős observed that colouring according to whether $\{ \sqrt{2}n\}<1/2$ or not implies $f(d) \ll d$. Beck [Be80] has improved this using the probabilistic method, constructing a colouring that shows $f(d)\leq (1+o(1))\log_2 d$. Van der Waerden's theorem implies $f(d)\to \infty$ is necessary.

Juhász [Ju79] has shown that $k\geq 5$. It is also known that $k\leq 10000000$ (as Erdős writes, 'more or less').

Graham [Gr80] has shown that this is true if we replace rectangle by right-angled triangle. The same question can be asked for parallelograms. It is not true for rhombuses.

This is false; Kovač [Ko23] provides an explicit (and elegantly simple) colouring using 25 colours such that no colour class contains the vertices of a rectangle of area $1$. The question for parallelograms remains open.

This type of problem belongs to 'canonical' Ramsey theory. The existence of $H(k)$ follows from Szemerédi's theorem, and it is easy to show that $H(k)^{1/k}\to\infty$.

The answer is yes, which was proved by Rödl [Ro03].

In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then \[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]

This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]

It is known that it must contain a 4-term arithmetic progression if $d=2$, and need not contain a 3-term arithmetic progression if $d=5$. The cases $d=3$ and $d=4$ are unknown.

Originally conjectured by Gerver and Ramsey [GeRa79], who showed that the answer is yes for $\mathbb{Z}^3$, and for $\mathbb{Z}^2$ that the number of collinear points can be bounded.

The answer is no, even for $k=3$, as shown by Ardal, Brown, and Jungić [ABJ11].

Geneson [Ge19] has shown that $k\leq 5$.

Davis, Entringer, Graham, and Simmons [DEGS77] have shown that there must exist a monotone 3-term arithmetic progression and need not contain a 5-term arithmetic progression.

If three sets are allowed then this is possible.

The answer is yes, as shown by Baumgartner [Ba75].

The answer is no, as shown by Baumgartner [Ba75] (whose construction uses the axiom of choice).

It follows from the prime number theorem that such a progression has length $\leq(1+o(1))\log N$.

It is trivial that $G_k(N)\leq R_k(N)$, and it is possible that $G_k(N) <R_k(N)$ (for example with $k=3$ and $N=14$). Komlós, Sulyok, and Szemerédi [KSS75] have shown that $R_k(N) \ll G_k(N)$.

Let $f(N)$ be the maximum possible $r$. Erdős and Stein conjectured that $f(N)=o(N)$, which was proved by Erdős and Szemerédi [ErSz68], who showed that, for every $\epsilon>0$, \[\frac{N}{\exp((\log N)^{1/2+\epsilon})} \ll_\epsilon f(N) < \frac{N}{(\log N)^c}\] for some $c>0$. Erdős believed the lower bound is closer to the truth.

There are odd integers $m$ such that none of $2^km+1$ are prime, which arise from covering systems (i.e. one shows that there exists some $n$ such that $(2^km+1,n)>1$ for all $k\geq 1$). Erdős and Graham also ask whether there is such an $m$ where a covering system is not 'responsible'. The answer is probably no since otherwise this would imply there are infinitely many Fermat primes of the form $2^{2^t}+1$.

The density of such $n$ is zero. Erdős and Graham believed that no such $n$ exist.

It is easy to see by probabilistic methods that this holds for almost all integers. Romanoff [Ro34] showed that a positive density set of integers are representable as the sum of $2^k+p$ for prime $p$, and Erdős used covering systems to show that there is a positive density set of integers which cannot be so represented.

If $x$ is irrational then this can be false, but it may be true for almost all $x\in\mathbb{R}$. Curtiss [Cu22] showed that this is true for $x=1$ and Erdős [Er50b] showed it is true for all $x\in\mathbb{Q}$.

Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].

Erdős [Er51] showed that there are infinitely many $n$ such that \[s_{n+1}-s_n > (1+o(1))\frac{\pi^2}{6}\frac{\log s_n}{\log\log s_n},\] so this bound would be the best possible. The current best bound is due to Chan [Ch21], who proved an upper bound of $s_n^{\frac{5}{26}+o(1)}$. More precisely, they proved that there exists some $C>0$ such that, for all large $x$, the interval \[(x,x+Cx^{5/26}]\] contains a squarefree number.

See also [489].

The Sylvester-Gallai theorem implies that there must exist a point where only two lines from $A$ meet. This problem asks whether there must exist three such points which form a triangle (with sides induced by lines from $A$). Füredi and Palásti [FuPa84] showed this is false when $d\geq 4$ is not divisible by $9$. Escudero [Es16] showed this is false for all $d\geq 4$.

Conjectured by Erdős and de Bruijn. The Sylvester-Gallai theorem states that $f(n)\geq 1$. That $f(n)\to \infty$ was proved by Motzkin [Mo51]. Kelly and Moser [KeMo58] proved that $f(n)\geq\tfrac{3}{7}n$ for all $n$. This is best possible for $n=7$. Motzkin conjectured that for $n\geq 13$ there are at least $n/2$ such lines. Csima and Sawyer [CsSa93] proved a lower bound of $f(n)\geq \tfrac{6}{13}n$ when $n\geq 8$. Green and Tao [GrTa13] proved that $f(n)\geq n/2$ for sufficiently large $n$.

Conjectured by Ulam. Erdős believed there cannot be such a set. This problem is discussed in a blogpost by Terence Tao, in which he shows that there cannot be such a set, assuming the Bombieri-Lang conjecture.

Harborth constructed such a set when $n=5$.

The answer is yes, proved by Juhász [Ju79], who proved more generally that the complement of $S$ must contain a congruent copy of any set of four points. This is not true for arbitrarily large sets of points, but perhaps is still true for any set of five points.

An old question of Steinhaus. Erdős was 'almost certain that such a set does not exist'.

In fact, such a set does exist, as proved by Jackson and Mauldin [JaMa02]. Their construction depends on the axiom of choice.

A variant of the 'happy ending' problem, which asks for the same without the 'no point in the interior' restriction. Erdős observed $g(4)=5$ (as with the happy ending problem) but Harborth [Ha78] showed $g(5)=10$. Nicolás [Ni07] and Gerken [Ge08] independently showed that $g(6)$ exists. Horton [Ho83] showed that $g(n)$ does not exist for $n\geq 7$.

An example with $n=4$ is an isosceles triangle with the point in the centre. Erdős originally believed this was impossible for $n\geq 5$, but Pomerance constructed a set with $n=5$ (see [Er83c] for a description), and 'a Hungarian high school student' gave an unspecified construction for $n=6$. Is this possible for $n=7$?

The answer is yes, proved by Green and Tao [GrTa08]. The stronger claim that there are arbitrarily long arithmetic progressions of consecutive primes is still open.

The answer is yes, as proved by Montgomery and Vaughan [MoVa86], who in fact found the correct order of magnitude with the power $2$ replaced by any $\gamma\geq 1$.

Lorentz [Lo54] showed there is such a set with, for all large $N$, \[\lvert A\cap\{1,\ldots,N\}\rvert \ll \frac{\log\log N}{\log N}N\]

Erdős [Er51] proved that, for infinitely many $k$, \[ n_{k+1}-n_k \gg \frac{\log n_k}{\sqrt{\log\log n_k}}.\] Richards [Ri82] improved this to \[\limsup_{k\to \infty} \frac{n_{k+1}-n_k}{\log n_k} \geq 1/4.\] The constant $1/4$ here has been improved, most lately to $0.868\cdots$ by Dietmann, Elsholtz, Kalmynin, Konyagin, and Maynard [DEKKM22]. The best known upper bound is due to Bambah and Chowla [BaCh47], who proved that \[n_{k+1}-n_k \ll n_k^{1/4}.\]

Hopf and Pannwitz [HoPa34] proved $f_2(n)=n$. Heppes [He56] and Grünbaum-Strasziewicz independently showed that $f_3(n)=2n-2$.

For $d=2$ this is trivial. For $d=3$ there is an unpublished proof by Kuiper and Boerdijk. The general case was proved by Danzer and Grünbaum [DaGr62].

More generally, if $A,B\subseteq \mathbb{R}$ are two countable dense sets then is there an entire function such that $f(A)=B$?

Originally a conjecture of Littlewood. The answer is yes (for all $n\geq 2$), proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST19].

The lower bound of $\sqrt{n}$ is trivial from Parseval's theorem. The answer is no (contrary to Erdős' initial guess). Kahane [Ka80] constructed 'ultraflat' polynomials $P(z)=\sum a_kz^k$ with $\lvert a_k\rvert=1$ such that \[P(z)=(1+o(1))\sqrt{n}\] uniformly forall $z\in\mathbb{C}$ with $\lvert z\rvert=1$, where the $o(1)$ term $\to 0$ as $n\to \infty$.

For more details see the paper [BoBo09] of Bombieri and Bourgain and, where Kahane's construction is improved to yield such a polynomial with \[P(z)=\sqrt{n}+O(n^{\frac{7}{18}}(\log n)^{O(1)})\] for all $z\in\mathbb{C}$ with $\lvert z\rvert=1$.

Erdős originally conjectured that $N(k)=2^k-1$, but this was disproved by Erdős and Bruijn. It is not even known whether $N(4)$ is finite.

Cramer proved an upper bound of $O(N(\log N)^4)$ conditional on the Riemann hypothesis. The prime number theorem immediately implies a lower bound of $\gg N(\log N)^2$.

Erdős [Er50] proved that there are infinitely many $n$ such that $f(n)\gg \log\log n$. Erdős could not even prove that there do not exist infinitely many integers $n$ such that for all $2^k<n$ the number $n-2^k$ is prime (probably $n=105$ is the largest such integer).

Erdős [Er50] proved this when $A=\{2^k : k\geq 0\}$. Solved by Chen and Ding [ChDi22].

This is well-known if $c_1$ is sufficiently small.

Wintner observed that if $f$ can take complex values on the unit circle then the limit need not exist. The answer is yes, as proved by Halász [Ha68].

Originally asked to Erdős by Wintner. The limit is infinite for a finite set of primes, which follows from a theorem of Pólya.

Originally asked to Erdős by Bose.

The Erdős-Straus conjecture. The existence of a representation of $4/n$ as the sum of at most four distinct unit fractions follows trivially from a greedy algorithm.

Schinzel conjectured the generalisation that, for any fixed $a$, if $n$ is sufficiently large in terms of $a$ then there exist distinct integers $1\leq x<y<z$ such that \[\frac{a}{n} = \frac{1}{x}+\frac{1}{y}+\frac{1}{z}.\]

A sequence defined in such a fashion is known as Sylvester's sequence.

Originally asked to Erdős by Kalmár. Erdős believed the answer is yes. Romanoff [Ro34] proved that the answer is yes if $C$ is an integer.

Erdős writes it is 'easy to see' that this holds with $3$ replaced by $2$, and that $3$ would be best possible here. We do not see an easy argument that this holds with $2$, but this follows e.g. from the main result of Mann [Ma60].

The answer is yes, proved by Freiman [Fr73].

Proved by Birch [Bi59].

Erdős [Er75c] proved the answer is yes under the stronger condition that $\limsup n_k/k^t=\infty$ for all $t\geq 1$.

Related to [69]. Erdős and Graham [ErGr80] write 'we just know too little about sieves to be able to handle such a question ("we" here means not just us but the collective wisdom (?) of our poor struggling human race).'

The answer is yes, as shown by Nesterenko [Ne96].

This is known now for $1\leq k\leq 4$. The cases $k=1,2$ are reasonably straightforward, as observed by Erdős [Er52]. The case $k=3$ was proved independently by Schlage-Puchta [ScPu06] and Friedlander, Luca, and Stoiciu [FLC07]. The case $k=4$ was proved by Pratt [Pr22].

This was disproved by Cassels [Ca60].

Cassels [Ca60] proved this under the alternative hypotheses \[\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert\gg \log\log x\] and \[\sum_{n\in A} \{ \theta n\}^2=\infty\] for every $\theta\in (0,1)$.

Erdős and Szekeres [ErSz59] proved that $\lim f(n)^{1/n}=1$ and $f(n)>\sqrt{2n}$. Erdős proved an upper bound of $f(n) < \exp(n^{1-c})$ for some constant $c>0$ with probabilistic methods. Atkinson [At61] showed that $f(n) <\exp(cn^{1/2}\log n)$ for some constant $c>0$.

If $A=\mathbb{N}$ then this series is $\sum_{n}\frac{d(n)}{2^n}$, where $d(n)$ is the number of divisors of $n$, which is known to be irrational.

Erdős and Straus [ErSt71] have proved this is true if $a_n$ is monotone, i.e. $a_{n-1}\leq a_n$ for all $n$.

This is true under either of the stronger assumptions that

• $a_{n+1}-a_n\to \infty$ or
• $a_n \gg n\sqrt{\log n\log\log n}$.

Erdős and Graham speculate that the condition $\limsup a_{n+1}-a_n=\infty$ is not sufficient, but know of no example.

Related to [260].

One possible definition of an 'irrationality sequence' (see also [263] and [264]). An example of such a sequence is $a_n=2^{2^n}$, while a non-example is $a_n=n!$. It is known that if $a_n$ is such a sequence then $a_n^{1/n}\to\infty$.

One possible definition of an 'irrationality sequence' (see also [262] and [264]).

A possible definition of an 'irrationality sequence' (see also [262] and [263]). One example is $a_n=2^{2^n}$.

Cantor observed that $a_n=\binom{n}{2}$ is such a sequence. If we replace $+1$ by a larger constant then higher degree polynomials can be used - for example if we consider $\sum\frac{1}{a_n}$ and $\sum\frac{1}{a_n+8}$ then $a_n=n^3+6n^2+5n$ is an example.

This conjecture is due to Stolarsky.

It may be sufficient to have $n_k/k\to \infty$. Good [Go74] and Bicknell and Hoggatt [BiHo76] have shown that $\sum \frac{1}{F_{2^n}}$ is irrational. The nature of $\sum \frac{1}{F_n}$ itself is unknown.

Erdős and Straus proved the answer is yes for the 2-dimensional version, where $X\subseteq \mathbb{R}^2$ is the set of \[\left( \sum_{n\in A} \frac{1}{n},\sum_{n\in A}\frac{1}{n+1}\right) \] as $A\subseteq\mathbb{N}$ ranges over all infinite sets with $\sum_{n\in A}\frac{1}{n}<\infty$.

If $P$ is infinite this sum is always irrational.

Erdős and Graham write 'the answer is almost surely in the affirmative if $f(n)$ is assumed to be nondecreasing'. Even the case $f(n)=n$ is unknown, although Hansen [Ha75] has shown that \[\sum_n \frac{1}{\binom{2n}{n}}=\sum_n \frac{n!}{(n+1)\cdots (n+n)}=\frac{1}{3}+\frac{2\pi}{3^{5/2}}\] is transcendental.

It is easy to see that $A(1)$ is the set of integers which have no 2 in their base 3 expansion. Odlyzko and Stanley have found similar characterisations are known for $A(3^k)$ and $A(2\cdot 3^k)$ for any $k\geq 0$, see [OdSt78]. There are no conjectures for the general case.

Simonovits and Sós [SiSo81] have shown that $t\ll N^2$. It is possible that the maximal $t$ is achieved when we take the $A_i$ to be all arithmetic progressions in $\{1,\ldots,N\}$ containing some fixed element.

If we drop the non-empty requirement then Simonovits, Sós, and Graham [SiSoGr80] have shown that \[t\leq \binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1\] and this is best possible.

Selfridge has found an example using divisors of $360$ if $p=3$ is allowed.

A problem of Herzog and Schönheim.

This is best possible as the system $2^{i-1}\pmod{2^i}$ shows. This was proved indepedently by Selfridge and Crittenden and Vanden Eynden [CrVE70].

Whether such a composite Lucas sequence even exists was open for a while, but using covering systems Graham [Gr64] showed that \[a_0 = 1786772701928802632268715130455793\] \[a_1 = 1059683225053915111058165141686995\] generate such a sequence. This problem asks whether one can have a composite Lucas sequence without 'an underlying system of covering congruences responsible'.

The density of such $n$ is zero.

Even the case $k=3$ seems difficult. This may be true with the primes replaced by any set $A\subseteq \mathbb{N}$ such that \[\lvert A\cap [1,N]\rvert \gg N/\log N\] and \[\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n} -\log\log N\to \infty\] as $N\to \infty$.

For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.

Erdős and Graham [ErGr80] suggest this 'may have to await improvements in current sieve methods' (of which there have been several since 1980).

The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$.

In 1202 Fibonacci observed that this process terminates for any $x$ when $A=\mathbb{N}$. The problem when $A$ is the set of odd numbers is due to Stein.

Graham [Gr64b] has shown that $\frac{m}{n}$ is the sum of distinct unit fractions with denominators $\equiv a\pmod{d}$ if and only if \[\left(\frac{n}{(n,(a,d))},\frac{d}{(a,d)}\right)=1.\] Does the greedy algorithm always terminate in such cases?

Graham [Gr64c] has also shown that $x$ is the sum of distinct unit fractions with square denominators if and only if $x\in [0,\pi^2/6-1)\cup [1,\pi^2/6)$. Does the greedy algorithm for this always terminate? Erdős and Graham believe not - indeed, perhaps it fails to terminate almost always.

Graham [Gr63] has proved this when $p(x)=x$. Cassels [Ca60] has proved that these conditions on the polynomial imply every sufficiently large integer is the sum of $p(n_i)$ with distinct $n_i$. Burr has proved this if $p(x)=x^k$ with $k\geq 1$ and if we allow $n_i=n_j$.

The upper bound $f(k) \leq (1+o(1))\frac{k}{e-1}$ is trivial since for any $u\geq 1$ we have \[\sum_{u\leq n\leq eu}\frac{1}{n}=1+o(1),\] and hence if $f(k)=u$ then we must have $k\geq (e-1-o(1))u$. Essentially solved by Croot [Cr01], who showed that for any $N>1$ there exists some $k\geq 1$ and \[N<n_1<\cdots <n_k \leq (e+o(1))N\] with $1=\sum \frac{1}{n_i}$.

It is trivial that $f(k)\geq (1+o(1))\frac{e}{e-1}k$, since for any $u\geq 1$ \[\sum_{e\leq n\leq eu}\frac{1}{n}= 1+o(1),\] and so if $eu\approx f(k)$ then $k\leq \frac{e-1}{e}f(k)$. Proved by Martin [Ma00].

The answer is yes, proved by Croot [Cr01].

The example $1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$ shows that $3$ would be best possible here. The lower bound of $\geq 2$ is equivalent to saying that $1$ is not the sum of reciprocals of consecutive integers, proved by Erdős [Er32].

This conjecture would follow for all but at most finitely many exceptions if it were known that, for all large $N$, there exists a prime $p\in [N,2N]$ such that $\frac{p+1}{2}$ is also prime.

This is still open even if $\lvert I_2\rvert=1$. It is perhaps true with two intervals replaced by any $k$ intervals.

For example, \[\sum_{3\leq n\leq 5}\frac{1}{n} = \frac{47}{60}\textrm{ and }\sum_{3\leq n\leq 6}\frac{1}{n}=\frac{19}{20}.\]

Straus observed that $A$ is closed under multiplication. Furthermore, it is easy to see that $A$ does not contain any prime power.

Results of Bleicher and Erdős [BlEr75] imply $v(k) \gg k!$. It may be that $v(k)$ grows doubly exponentially in $\sqrt{k}$ or even $k$.

An elementary inductive argument shows that $n_k\leq ku_k$ where $u_1=1$ and $u_{i+1}=u_i(u_i+1)$, and hence \[v(k) \leq kc_0^{2^k},\] where \[c_0=\lim_n u_n^{1/2^n}=1.26408\cdots\] is the 'Vardi constant'.

Erdős and Graham [ErGr80] claim a bound of \[t(N)\ll\frac{N}{\log N},\] but have no idea of the true value of $t(N)$.

Erdős and Straus [ErSt71b] have proved the existence of some constant $c>0$ such that \[-c < k(N)-(e-1)N \ll \frac{N}{\log N}.\]

More generally, how many disjoint $A_i$ can be found in $\{1,\ldots,N\}$ such that the sums $\sum_{n\in A_i}\frac{1}{n}$ are all equal? Using sunflowers it can be shown that there are at least $N\exp(-O(\sqrt{\log N}))$ such sets.

Hunter and Sawhney have observed that Theorem 3 of Bloom [Bl23] (coupled with the trivial greedy approach) implies that $k(N)=(1-o(1))\log N$.

It is not even known whether this is $2^{cN}$ for some $c<1$ or $2^{(1+o(1))N}$.

The answer is yes, proved by Bloom [Bl21].

There does not exist such a sequence, which follows from the positive solution to [298] by Bloom [Bl21].

Erdős and Graham believe the answer is $A(N)=(1+o(1))N$. Croot [Cr03] disproved this, showing the existence of some constant $c<1$ such that $A(N)<cN$ for all large $N$. It is trivial that $A(N)\geq (1-\frac{1}{e}+o(1))N$.

The example $A=(N/2,N]\cap \mathbb{N}$ shows that $\lvert A\rvert\geq N/2$.

The colouring version of this is [303], which was solved by Brown and Rödl [BrRo91].

The possible alternative question, that if $A\subseteq \mathbb{N}$ is a set of positive lower density then must there exist $a,b,c\in A$ such that \[\frac{1}{a}=\frac{1}{b}+\frac{1}{c},\] has a negative answer, taking for example $A$ to be the union of $[5^k,(1+\epsilon)5^k]$ for large $k$ and sufficiently small $\epsilon>0$. This was observed by Hunter and Sawhney.

The density version of this is [302]. This colouring version is true, as proved by Brown and Rödl [BrRo91].

Erdős [Er50c] proved that \[\log\log b \ll N(b) \ll \frac{\log b}{\log\log b}.\] The upper bound was improved by Vose [Vo85] to \[N(b) \ll \sqrt{\log b}.\] One can also investigate the average of $N(a,b)$ for fixed $b$, and it is known that \[\frac{1}{b}\sum_{1\leq a<b}N(a,b) \gg \log\log b.\]

Related to [18].

Bleicher and Erdős [BlEr76] have shown that \[D(b)\ll b(\log b)^2.\] If $b=p$ is a prime then \[D(p) \gg p\log p.\]

For $n_i$ the product of three distinct primes, this is true when $b=1$, as proved by Butler, Erdős and Graham [BuErGr15] (this paper is perhaps Erdős' last paper, appearing 19 years after his death).

Asked by Barbeau [Ba76]. Can this be done if we drop the requirement that all $p\in P$ are prime and just ask for them to be relatively coprime, and similarly for $Q$?

Hunter and Sawhney have observed that Theorem 3 of Bloom [Bl23] implies the answer to the second question is no: in fact all integers $m\leq (1-o(1))\log N$ can be written as the sum of distinct unit fractions with denominators from $\{1,\ldots,N\}$.

It is trivially at least $1/[1,\ldots,N]$.

Erdős and Graham knew this with $e^{-cK}$ replaced by $c/K^2$.

For example, \[\frac{1}{2}+\frac{1}{3}=1-\frac{1}{6}.\]

$c_0$ is called the Vardi constant.

This is not true if $A$ is a multiset, for example $2,3,3,5,5,5,5$.

This is not true in general, as shown by Sándor [Sa97], who observed that the proper divisors of $120$ form a counterexample. More generally, Sándor shows that for any $n\geq 2$ there exists a finite set $A\subseteq \mathbb{N}\backslash\{1\}$ with $\sum_{k\in A}\frac{1}{k}<n$ and no partition into $n$ parts each of which has $\sum_{k\in A_i}\frac{1}{k}<1$.

The minimal counterexample is $\{2,3,4,5,6,7,10,11,13,14,15\}$, found by Tom Stobart.

Inequality is obvious for the second claim, the problem is strict inequality. This fails for small $n$, for example \[\frac{1}{2}-\frac{1}{3}-\frac{1}{4}=-\frac{1}{12}.\]

Erdős and Straus [ErSt75] proved this when $A=\mathbb{N}$. Sattler [Sat75] proved this when $A$ is the set of odd numbers. For the squares $1$ must be excluded or the result is trivially false, since \[\sum_{k\geq 2}\frac{1}{k^2}<2.\]

Bleicher and Erdős [BlEr75] proved the lower bound \[\frac{N}{\log N}\prod_{i=3}^k\log_iN\leq \frac{\log S(N)}{\log 2},\] valid for $k\geq 4$ and $\log_kN\geq k$, and also [BlEr76b] proved the upper bound \[\log S(N)\leq \log_r N\left(\frac{N}{\log N} \prod_{i=3}^r \log_iN\right),\] valid for $r\geq 1$ and $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

See also [321].

Let $R(N)$ be the maximal such size. Results of Bleicher and Erdős from [BlEr75] and [BlEr76b] imply that \[\frac{N}{\log N}\prod_{i=3}^k\log_iN\leq R(N)\leq \frac{1}{\log 2}\log_r N\left(\frac{N}{\log N} \prod_{i=3}^r \log_iN\right),\] valid for any $k\geq 4$ with $\log_kN\geq k$ and any $r\geq 1$ with $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

See also [320].

Connected to Waring's problem. The famous Hypothesis $K$ of Hardy and Littlewood was that $1_A^{(k)}(n)\leq n^{o(1)}$, but this was disproved by Mahler [Ma36] for $k=3$, who constructed infinitely many $n$ such that \[1_A^{(3)}(n)\gg n^{1/12}\] (where $A$ is the set of cubes). Erdős believed Hypothesis $K$ fails for all $k\geq 4$, but this is unknown. Hardy and Littlewood made the weaker Hypothesis $K^*$ that for all $N$ and $\epsilon>0$ \[\sum_{n\leq N}1_A^{(k)}(n)^2 \ll_\epsilon N^{1+\epsilon}.\] Erdős and Graham remark: 'This is probably true but no doubt very deep. However, it would suffice for most applications.'

Independently Erdős [Er36] and Chowla proved that for all $k\geq 3$ and infinitely many $n$ \[1_A^{(k)}(n) \gg n^{c/\log\log n}\] for some constant $c>0$ (depending on $k$).

This would have significant applications to Waring's problem. Erdős and Graham describe this as 'unattackable by the methods at our disposal'. The case $k=2$ was resolved by Landau, who showed \[f_{2,2}(x) \sim \frac{cx}{\sqrt{\log x}}\] for some constant $c>0$.

For $k>2$ it is not known if $f_{k,k}(x)=o(x)$.

Erdős and Graham describe this problem as 'very annoying'. Probably $f(x)=x^5$ should work.

Mahler and Erdős [ErMa38] proved that $f_{k,2}(x) \gg x^{2/k}$. For $k=3$ the best known is due to Wooley [Wo15], \[f_{3,3}(x) \gg x^{0.917\cdots}.\]

Erdős originally asked whether this was true with $A=B$, but this was disproved by Cassels [Ca57].

The connection to unit fractions comes from the observation that $\frac{1}{a}+\frac{1}{b}$ is a unit fraction if and only if $a+b\mid ab$.

Asked by Erdős and Newman. Nešetřil and Rödl have shown the answer is no for all $C$ (source is cited as 'personal communication' in [ErGr80]). Erdős had previously shown the answer is no for $C=3,4$ and infinitely many other values of $C$.

Erdős proved that $1/2$ is possible and Krückeberg [Kr61] proved $1/\sqrt{2}$ is possible. Erdős and Turán [ErTu41] have proved this $\limsup$ is always $\leq 1$.

The fact that $1$ is possible would follow if any finite Sidon set is a subset of a perfect difference set.

Asked by Erdős and Nathanson.

Prikry, Tijdeman, Stewart, and others (see the survey articles [St78] and [Ti79]) have shown that a sufficient condition is that $A$ has positive density.

One can also ask what conditions are sufficient for $D(A)$ to have positive density, or for $\sum_{d\in D(A)}\frac{1}{d}=\infty$, or even just $D(A)\neq\emptyset$.

Erdős and Newman [ErNe77] have proved this is true when $A$ is the set of squares.

Erdős originally asked if even $f(n)\leq n^{1/3}$ is true. This is known, and the best bound is due to Balog [Ba89] who proved that \[f(n) \ll_\epsilon n^{\frac{4}{9\sqrt{e}}+\epsilon}\] for all $\epsilon>0$. (Note $\frac{4}{9\sqrt{e}}=0.2695\ldots$.)

It is likely that $f(n)\leq n^{o(1)}$, or even $f(n)\leq e^{O(\sqrt{\log n})}$.

One way this can happen is if there exists $\theta>0$ such that \[A=\{ n>0 : \{ n\theta\} \in X_A\}\textrm{ and }B=\{ n>0 : \{n\theta\} \in X_B\}\] where $\{x\}$ denotes the fractional part of $x$ and $X_A,X_B\subseteq \mathbb{R}/\mathbb{Z}$ are such that $\mu(X_A+X_B)=\mu(X_A)+\mu(X_B)$. Are all possible $A$ and $B$ generated in a similar way (using other groups)?

Erdős and Graham [ErGr80b] have shown that a basis $A$ has an exact order if and only if $a_2-a_1,a_3-a_2,a_4-a_3,\ldots$ are coprime. They also prove that \[\frac{1}{4}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{5}{4}.\] It is known that $h(2)=4$, but even $h(3)$ is unknown (it is $\geq 7$).

Bateman has observed that for $h\geq 3$ there is a basis of order $h$ with no restricted order, taking \[A=\{1\}\cup \{x>0 : h\mid x\}.\] Kelly [Ke57] has shown that any basis of order $2$ has restricted order at most $4$ and conjectures it always has restricted order at most $3$.

The set of squares has order $4$ and restricted order $5$ (see [Pa33]) and the set of triangular numbers has order $3$ and restricted order $3$ (see [Sc54]).

Is it true that if $A\backslash F$ is a basis for all finite sets $F$ then $A$ must have a restricted order? What if they are all bases of the same order?

Erdős and Graham [ErGr80] also ask about the difference set $A-A$, whether this has positive density, and whether this contains $22$.

This sequence is at OEIS A005282.

An old problem of Dickson. Even a starting set as small as $\{1,4,9,16,25\}$ requires thousands of terms before periodicity occurs.

A problem of Ulam. The sequence is \[1,2,3,4,6,8,11,13,16,18,26,28,\ldots\] at OEIS A002858.

A problem of Folkman. Folkman [Fo66] showed that this is true if \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1+\epsilon}\] for some $\epsilon>0$ and all $N$.

The original question was answered by Szemerédi and Vu [SzVu06] (who proved that the answer is yes).

This is best possible, since Folkman [Fo66] showed that for all $\epsilon>0$ there exists a multiset $A$ with \[\lvert A\cap \{1,\ldots,N\}\rvert\ll N^{1+\epsilon}\] for all $N$, such that $A$ is not subcomplete.

Folkman proved this under the stronger assumption that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2+\epsilon}\] for some $\epsilon>0$.

This is true, and was proved by Szemerédi and Vu [SzVu06]. The stronger conjecture that this is true under \[\lvert A\cap \{1,\ldots,N\}\rvert\geq (2N)^{1/2}\] seems to be still open (this would be best possible as shown by [Er61b].

Erdős and Graham [ErGr80] remark that very little is known about $T(A)$ in general. It is known that \[T(n)=1, T(n^2)=128, T(n^3)=12758,\] \[T(n^4)=5134240,\textrm{ and }T(n^5)=67898771.\] Erdős and Graham remark that a good candidate for the $n$ in the question are $k=2^t$ for large $t$, perhaps even $t=3$, because of the highly restricted values of $n^{2^t}$ modulo $2^{t+1}$.

Graham [Gr64d] has shown that the sequence $a_n=F_n-(-1)^{n}$, where $F_n$ is the $n$th Fibonacci number, has these properties. Erdős and Graham [ErGr80] remark that it is easy to see that if $a_{n+1}/a_n>\frac{1+\sqrt{5}}{2}$ then the second property is automatically satisfied, and that it is not hard to construct very irregular sequences satisfying both properties.

The Fibonacci sequence $1,1,2,3,5,\ldots$ shows that $m=1$ and $n=2$ is possible. The sequence of powers of $2$ shows that $m=0$ and $n=1$ is possible. The case $m=2$ and $n=3$ is not known.

Even in the range $t\in (0,1)$ and $\alpha\in (1,2)$ the behaviour is surprisingly complex. For example, Graham [Gr64e] has shown that for any $k$ there exists some $t_k\in (0,1)$ such that the set of $\alpha$ such that the sequence is complete consists of at least $k$ disjoint line segments. It seems likely that the sequence is complete for all $t>0$ and all $1<\alpha < \frac{1+\sqrt{5}}{2}$. Proving this seems very difficult, since we do not even known whether $\lfloor (3/2)^n\rfloor$ is odd or even infinitely often.

This was proved by Ryavec. The stronger statement that, for all $s\geq 0$, \[\sum_{n\in A}\frac{1}{n^s} <\frac{1}{1-2^{-s}},\] was proved by Hanson, Steele, and Stenger [HSS77].

Graham [Gr64f] proved this is true when $p(n)=n$. Erdős and Graham also ask which rational functions $r(x)\in\mathbb{Z}[x]$ force $\{ r(n) : n\in\mathbb{N}\}$ to be complete?

Erdős (unpublished) proved that this is true if $A$ has infinite measure, or if $A$ is an unbounded set of positive measure.

Erdős and Mauldin (unpublished) claim that this is true for trapezoids in general, but fails for parallelograms.

Bleicher and Erdős conjecture the answer is no.

This fails for $a_i=i$ for example. Erdős and Graham also ask what happens if we drop the monotonicity restriction and just ask that the $a_i$ are distinct. Perhaps some permutation of $\{1,\ldots,n\}$ has at least $cn^2$ such distinct sums. This latter problem has been solved by Konieczny [Ko15], who showed that a random permutation of $\{1,\ldots,n\}$ has, with high probability, at least \[\left(\frac{1+e^{-2}}{4}+o(1)\right) n^2\] many such consecutive sums.

The original problem was solved (in the affirmative) by Beker [Be23b].

They also ask how many consecutive integers $>n$ can be represented as such a sum? Is it true that, for any $c>0$ at least $cn$ such integers are possible (for sufficiently large $n$)?

Asked by Erdős and Harzheim. What if we remove the monotonicity and/or the distinctness constraint? Also what is the least $m$ which is not a sum of the given form? Can it be much larger than $n$? Erdős and Harzheim can show that $\sum_{x<a_i<x^2}\frac{1}{a_i}\ll 1$. Is it true that $\sum_i \frac{1}{a_i}\ll 1$?

Erdős and Moser [Mo63] considered the case when $A$ is the set of primes, and conjectured that the $\limsup$ of the number of such representations in this case is infinite. They could not even prove that the upper density of the set of integers representable in this form is positive.

A problem of MacMahon, studied by Andrews [An75].

Erdős and Graham state it 'can be shown' that $f(n)\to \infty$.

Erdős and Moser proved this bound with an additional factor of $(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65]. Stanley [St80] has shown that this quantity is maximised when $A$ is an arithmetic progression and $t=\tfrac{1}{2}\sum_{n\in A}n$.

Erdős and Selfridge have proved that the product of consecutive integers is never a power. The condition $\lvert I_i\rvert \geq 4$ is necessary here, since Pomerance has observed that the product of \[(2^{n-1}-1)2^{n-1}(2^{n-1}+1),\] \[(2^n-1)2^n(2^n+1),\] \[(2^{2n-1}-2)(2^{2n-1}-1)2^{2n-1},\] and \[(2^{2n-2}-2)(2^{2n}-1)2^{2n}\] is a always a square.

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

Note that $8$ is 3-full and $9$ is 2-full. Is the the only pair of such consecutive integers?

It would also be interesting to find upper and lower bounds for the analogous product with $B_r$ for $r\geq 3$, where $B_r(n)$ is the $r$-full part of $n$ (that is, the product of prime powers $p^a \mid n$ such that $p^{a+1}\nmid n$ and $a\geq r$). Is it true that, for every fixed $r,k\geq 2$ and $\epsilon>0$, \[\limsup \frac{\prod_{n\leq m<n+k}B_r(m) }{n^{1+\epsilon}}\to\infty?\]

Mahler [Ma35] showed that this is $\gg \log\log n$. Schinzel [Sc67b] observed that for infinitely many $n$ it is $\leq n^{O(1/\log\log\log n)}$. The truth is probably $\gg (\log n)^2$ for all $n$.

Open even for $k=2$. Erdős and Graham remark 'the answer should be affirmative but the problem seems very hard'.

Pomerance has observed that if we replace $1/2$ in the exponent by $1/\sqrt{e}-\epsilon$ for any $\epsilon>0$ then this is true for density reasons.

Conjectured by Erdős and Pomerance [ErPo78], who proved that this set and its complement both have positive upper density.

Conjectured by Erdős and Pomerance [ErPo78], who proved the analogous result for $P(n)<P(n+1)<P(n+2)$. Proved by Balog [Ba01], who proved that this is true for $\gg \sqrt{x}$ many $n\leq x$ (for all large $x$).

This would follow if $P(n(n+1))/\log n\to \infty$, where $P(m)$ denotes the largest prime factor of $m$ (see Problem [368]). Hickerson conjectured the largest solution is \[16! = 14! 5!2!.\] The condition $a_1<n-1$ is necessary to rule out the trivial solutions when $n=a_2!\cdots a_k!$.

Studied by Erdős and Graham [ErGr76] (see also [LSS14]). It is known, for example, that:

• no $D_k$ contains a prime,
• $D_2=\{ n^2 : n>1\}$,
• $\lvert D_3\cap \{1,\ldots,n\}\rvert = o(\lvert D_4\cap \{1,\ldots,n\}\rvert)$,
• the least element of $D_6$ is $527$, and
• $D_k=\emptyset$ for $k>6$.

Very deep if true, since it would imply there is a prime between any two consecutive squares.

Originally conjectured by Grimm [Gr69], who proved it when $k \ll \log n/\log\log n$. Ramachandra, Shorey, and Tijdeman [RST75] have improved this to \[k \ll \left(\frac{\log n}{\log\log n}\right)^3.\]

Erdős, Graham, Ruzsa, and Straus [EGRS75] have shown that, for any two primes $p$ and $q$, there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $pq$.

If the sum is denoted by $f(n)$ then Erdős, Graham, Ruzsa, and Straus [EGRS75] have shown \[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n) = \sum_{k=2}^\infty \frac{\log k}{2^k}=\gamma_0\] and \[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n)^2 = \gamma_0^2,\] so that for almost all integers $f(m)=\gamma_0+o(1)$.

Erdős and Graham state they can prove that, for $k$ fixed and large, the density of $n$ such that $\binom{n}{k}$ is squarefree is $o_k(1)$. They can also prove that there are infinitely many $n$ such that $\binom{n}{k}$ is not squarefree for $1\leq k<n$, and expect that the density of such $n$ is positive.

If $s(n)$ denotes the largest integer such that $\binom{n}{k}$ is divisible by $p^{s(n)}$ for some prime $p$ for at least one $1\leq k<n$ then it is easy to see that $s(n)\to \infty$ as $n\to \infty$ (and in fact that $s(n) \asymp \log n$).

Erdős and Graham only knew that $B(x) > x^{1-o(1)}$. Similarly, we call an interval $[u,v]$ 'very bad' if $\prod_{u\leq m\leq v}m$ is powerful. The number of integers $n\leq x$ contained in at least one very bad interval should be $\ll x^{1/2}$. In fact, it should be asymptotic to the number of powerful numbers $\leq x$.

See also [382].

Conjectured by Erdős and Selfridge. There are infinitely many $n$ such that $n(n+1)$ is powerful (see [364]).

Erdős and Graham report it follows from results of Ramachandra that $v-u\leq v^{1/2+o(1)}$.

See also [380].

A conjecture of Erdős and Selfridge. Proved by Ecklund [Ec69], who made the stronger conjecture that whenever $n>k^2$ the binomial coefficient $\binom{n}{k}$ is divisible by a prime $p<n/k$. They have proved the weaker inequality $p\ll n/k^c$ for some constant $c>0$.

Erdős and Graham write that 'a proof that this cannot happen infinitely often for $\binom{n}{2}$ seems hopeless; probably this can never happen for $\binom{n}{k}$ if $3\leq k\leq n-3$.'

Erdős once conjectured that $\binom{n}{k}$ must always have a divisor in $(n-k,n]$, but this was disproved by Schinzel and Erdős [Sc58].

Asked by Erdős and Straus. For example when $n=2$ we have $k=4$: \[3\cdot 4\cdot 5\cdot 6 \mid 7\cdot 8\cdot 9\cdot 10.\] No example was known for $n\geq 10$.

Erdős, Guy, and Selfridge [EGS82] have shown that \[f(n)-2n \asymp \frac{n}{\log n}.\]

Erdős, Selfridge, and Straus have shown that \[\lim \frac{t(n)}{n}=\frac{1}{e}.\] Alladi and Grinstead [AlGr77] have obtained similar results when the $a_i$ are restricted to prime powers.

If we change the condition to $a_t\leq n$ it can be shown that \[A(n)=n-\frac{n}{\log n}+o\left(\frac{n}{\log n}\right)\] via a greedy decomposition (use $n$ as often as possible, then $n-1$, and so on). Other questions can be asked for other restrictions on the sizes of the $a_t$.

Erdős and Graham write that they do not even know whether $f(n)=1$ infinitely often (i.e. whether a factorial is the product of two consecutive integers infinitely often).

The answer is yes, proved by Hall. It is probably true that the sum is $o(N/(\log N)^c)$ for some constant $c>0$.

It follows from the Thue-Siegel theorem that, for $n$ fixed, there are only finitely many potential such $x$ and $y$.

Erdős and Graham write that $n+1$ always divides $\binom{2n}{n}$, but it is quite rare that $n$ divides $\binom{2n}{n}$.

The Brocard-Ramanujan conjecture. Erdős and Graham describe this as an old conjecture, and write it 'is almost certainly true but it is intractable at present'.

Overholt [Ov93] has shown that this has only finitely many solutions assuming a weak form of the abc conjecture.

Erdős and Obláth [ErOb37] proved this is true when $(x,y)=1$ and $k\neq 4$. Pollack and Shapiro [PoSh73] proved this is true when $(x,y)=1$ and $k=4$. The known methods break down without the condition $(x,y)=1$.

Erdős and Graham write that it is easy to show that $g_k(n) \ll_k \log n$ always, but the best possible constant is unknown.

See also [401].

See also [400].

A conjecture of Graham [Gr70], who also conjectured that (assuming $A$ itself has no common divisor) then the only cases where equality achieved are when $A=\{1,\ldots,n\}$ or $\{L/1,\ldots,L/n\}$ (where $L=\mathrm{lcm}(1,\ldots,n)$) or $\{2,3,4,6\}$.

Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87].

Proved for all sets by Balasubramanian and Soundararajan [BaSo96].

Asked by Burr and Erdős. Frankl and Lin [Li76] independently showed that the answer is yes, and the largest solution is \[2^7=2!+3!+5!.\] In fact Lin showed that the largest power of $2$ which can divide a sum of distinct factorials containing $2$ is $2^{254}$, and that there are only 5 solutions to $3^m=a_1!+\cdots+a_k!$ (when $m=0,1,2,3,6$).

See also [404].

See also [403]. Lin [Li76] has shown that $f(2,2) \leq 254$.

Erdős and Graham remark that it is probably true that in general $(p-1)!+a^{p-1}$ is rarely a power at all (although this can happen, for example $6!+2^6=28^2$).

The only examples seem to be $4=1+3$ and $256=1+3+3^2+3^5$. If we only allow the digits $1$ and $2$ then $2^{15}$ seems to be the largest such power of $2$.

A conjecture originally due to Newman.

Pillai [Pi29] was the first to investigate this function, and proved \[\log_3 n < f(n) < \log_2 n\] for all large $n$. Shapiro [Sh50] proved that $f(n)$ is essentially multiplicative.

Erdős, Granville, Pomerance, and Spiro [EGPS90] have proved that the answer to the first two questions is yes, conditional on a form of the Elliott-Halberstam conjecture.

It is likely true that, if $k\to \infty$ however slowly with $n$, then for almost $n$ the largest prime factor of $n$ is $\leq n^{o(1)}$.

A problem of Finucane. One can also ask about $n\mapsto \sigma(n)-1$.

The known solutions to $g_{k+2}(n)=2g_k(n)$ are $n=10$ and $n=94$. Selfridge and Weintraub found solutions to $g_{k+9}(n)=9g_k(n)$ and Weintraub found \[g_{k+25}(3114)=729g_k(3114)\] for all $k\geq 6$.

That is, there is (eventually) only one possible sequence that the iterated sum of divisors function can settle on. Selfridge reports numerical evidence suggests the answer is no, but Erdős and Graham write 'it seems unlikely that anything can be proved about this in the near future'.

See also [413] and [414].

Erdős suggested this problem as a way of showing that the iterated behaviour of $n\mapsto n+\nu(n)$ eventually settles into a single sequence, regardless of the starting value of $n$ (see also [412] and [414]).

Erdős and Graham report it could be attacked by sieve methods, but 'at present these methods are not strong enough'. Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \nu(m)\leq n$ for all $m<n$?

Asked by Spiro. That is, there is (eventually) only one possible sequence that the iterations of $n\mapsto h(n)$ can settle on. Erdős and Graham believed the answer is yes. Similar questions can be asked by the iterates of many other functions. See also [412] and [413].

Erdős [Er36b] proved that \[F(n)\asymp \log\log\log n,\] and similarly if we replace $\phi$ with $\sigma$ or $\tau$ or $\nu$ or any 'decent' additive or multiplicative function.

Pillai [Pi29] proved $V(x)=o(x)$. The behaviour of $V(x)$ is almost completely understood. Maier and Pomerance [MaPo88] proved \[V(x)=\frac{x}{\log x}e^{(C+o(1))\log\log\log x},\] for some explicit constant $C>0$. Ford [Fo98] improved this to \[V(x)\asymp\frac{x}{\log x}e^{C_1(\log\log\log x-\log\log\log\log x)^2+C_2\log\log\log x-C_3\log\log\log\log x}\] for some explicit constants $C_1,C_2,C_3>0$. Unfortunately this falls just short of an asymptotic formula for $V(x)$ and determining whether $V(2x)/V(x)\to 2$.

See also [417].

It is trivial that $V'(x) \leq V(x)$. See also [416].

Asked by Erdős and Sierpiński. It follows from the Goldbach conjecture that every odd number can be written as $n-\phi(n)$. What happens for even numbers?

Erdős [Er73b] has shown that a positive density set of integers cannot be written as $\sigma(n)-n$.

It can be shown that any number of the shape $1+1/k$ for $k\geq 1$ is a limit point, but no others are known.

Erdős and Graham write that it is easy to show that $\lim F(n^{1/2},n)=\infty$, and in fact the $n^{1/2}$ can be replaced by $n^{1/2-c}$ for some small constant $c>0$.

Asked by Hofstadter. The sequence begins $1,1,2,3,3,4,\ldots$ and is A005185 in the OEIS. It is not even known whether $f(n)$ is well-defined for all $n$.

Asked by Hofstadter. The sequence begins $1,2,3,5,6,8,10,11,\ldots$ and is A005243 in the OEIS.

Asked by Hofstadter. The sequence begins $2,3,5,9,14,17,26,\ldots$ and is A005244 in the OEIS.

Erdős [Er68] proved that \[F(n)-\pi(n)\asymp n^{3/4}(\log n)^{-3/2}.\] Surprisingly, if we consider the corresponding problem in the reals (so the largest $m$ such that there are reals $1\leq a_1<\cdots <a_m\leq x$ such that for any distinct indices $i,j,r,s$ we have $\lvert a_ia_j-a_ra_s\rvert \geq 1$) then Alexander proved that $m> x/8e$ is possible.

See also [490].

The answer is yes, proved by Ruzsa [Ru72].

Erdős and Graham could show this is true (assuming the prime $k$-tuple conjecture) if we replace $\liminf$ by $\limsup$.

Erdős and Graham write 'preliminary calculations made by Selfridge indicate that this is the case but no proof is in sight'. For example if $n=8$ we have $a_1=7$ and $a_2=5$ and then must stop.

A problem of Ostmann, sometimes known as the 'inverse Goldbach problem'. The answer is surely no. The best result in this direction is due to Elsholtz and Harper [ElHa15], who showed that if $A,B$ are such sets then for all large $x$ we must have \[\frac{x^{1/2}}{\log x\log\log x} \ll \lvert A \cap [1,x]\rvert \ll x^{1/2}\log\log x\] and similarly for $B$.

Elsholtz [El01] has proved there are no infinite sets $A,B,C$ such that $A+B+C$ agrees with the set of prime numbers up to finitely many exceptions.

See also [432].

Asked by Straus, inspired by a problem of Ostmann (see [431]).

This type of problem is associated with Frobenius. Erdős and Graham [ErGr72] proved $g(n,t)<2t^2/n$, and there are examples which show that \[g(n,t) \geq \frac{t^2}{n-1}-5t\] for $n\geq 2$.

Associated with problems of Frobenius.

Asked by Lehmer and Lehmer [LeLe62]. For example $\Lambda(2,2)=9$ and $\Lambda(3,2)=77$. It is known that $\Lambda(k,3)=\infty$ for all even $k$ and $\Lambda(k,4)=\infty$ for all $k$.

This has been partially resolved: Hildebrand [Hi91] has shown that $\Lambda(k,2)$ is finite for all $k$.

There are trivially $o(x)$ many squares.

Taking all integers $\equiv 1\pmod{3}$ shows that $\lvert A\rvert\geq N/3$ is possible. This can be improved to $\tfrac{11}{32}N$ by taking all integers $\equiv 1,5,9,13,14,17,21,25,26,29,30\pmod{32}$, as observed by Massias.

Lagarias, Odlyzko, and Shearer [LOS83] proved this is sharp for the modular version of the problem; that is, if $A\subseteq \mathbb{Z}/N\mathbb{Z}$ is such that $A+A$ contains no squares then $\lvert A\rvert\leq \tfrac{11}{32}N$. They also prove the general upper bound of $\lvert A\rvert\leq 0.475N$ for the integer problem.

In fact $\frac{11}{32}$ is sharp in general, as shown by Khalfalah, Lodha, and Szemerédi [KLS02], who proved that the maximal such $A$ satisfies $\lvert A\rvert\leq (\tfrac{11}{32}+o(1))N$.

It is easy to give a sequence with \[\limsup\frac{A(x)}{x^{1/2}}=c>0.\] There are related results (particularly for what happens if we consider $\mathrm{lcm}(a_i,a_{i+1},\ldots,a_{i+k})$ in a paper of Erdős and Szemerédi [ErSz80].

The answer is yes, proved by Erdős and Sárkőzy [ErSa80].

An unpublished result of Heilbronn guarantees this for $c$ sufficiently close to $1$.

Erdős [Er35] proved that $\delta(n)<(\log n)^{-c}$ for some $c>0$. Tenenbaum [Te75] showed that $\delta(n)=(\log n)^{(-1+o(1))\alpha}$ where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]

This has been resolved by Ford [Fo08]. Among many other results, Ford proves \[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}},\] and that the second conjecture is false (i.e. $\delta'(n) \geq \delta(n)$ for some constant $c>0$)

The estimate $\lvert \mathcal{F}\rvert=o(2^n)$ implies that if $A\subset \mathbb{N}$ is a set of positive density then there are infinitely many distinct $a,b,c\in A$ such that $[a,b]=c$ (i.e. [487]).

Solved by Kleitman [Kl71], who proved \[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.\]

Erdős and Graham also ask whether there is a good inequality known for $\sum_{n\leq x}\tau^*(n)$.

See also [447].

Erdős and Graham write 'we can prove $n_k>k^{1+c}$ but no doubt much more is true'.

Erdős [Er37] proved that the density of integers $n$ with $\omega(n)>\log\log n$ is $1/2$. The Chinese remainder theorem implies that there is such an interval with \[\lvert I\rvert \geq (1+o(1))\frac{\log x}{(\log\log x)^2}.\] It could be true that there is such an interval of length $(\log x)^{k}$ for arbitrarily large $k$.

Asked by Erdős and Straus. The answer is no, as shown by Pomerance [Po79].

Pomerance [Po79] has proved the $\limsup$ is at least $2$.

Richter [Ri76] proved that \[\liminf_n \frac{q_n}{n^2}>2.84\cdots.\]

Erdős and Graham write this is 'almost certainly' true, but the proof is beyond our ability, for two reasons (at least):

• Firstly, one has to rule out the possibility of many primes $q$ such that $p_k<q^2<p_{k+1}$. There should be at most one such $q$, which would follow from $p_{k+1}-p_k<p_k^{1/2}$, which is essentially the notorious Legendre's conjecture.
• The small primes also cause trouble.

This question arose in work of Eggleton, Erdős, and Selfridge.

Erdős and Graham report they can show \[f(n,t) \gg \frac{t}{\log t}.\]

Erdős and Graham write the existence of such an $\alpha$ has 'very recently been shown', but frustratingly give neither a name nor a reference. I will try to track down this solution soon.

The first conjecture was proved by Sárközy [Sa76], who in fact proved \[N(X,\delta) \ll \delta^{-3}\frac{X}{\log\log X}.\] It is not even known whether $N(X,\delta)<X^{1-\epsilon}$ for some $\epsilon>0$. See also [466].

Graham proved this is true, and in fact \[N(X,1/10)> \frac{\log X}{10}.\] This was substantially improved by Sárközy [Sa76], who proved that for, all sufficiently small $\delta>0$, \[N(X,\delta)>X^{1/2-\delta^{1/7}}.\] See also [465].

This is what I assume the intended problem is, although the presentation in [ErGr80] is missing some crucial quantifiers, so I may have misinterpreted it.

The same question can be asked for those $n$ which do not have distinct sums of sets of divisors, but any proper divisor of $n$ does.

Weird numbers were investigated by Benkoski and Erdős [BeEr74], who proved that the set of weird numbers has positive density.

Melfi [Me15] has proved that there are infinitely many primitive weird numbers, conditional on various well-known conjectures on the distribution of prime gaps. For example, it would suffice to show that $p_{n+1}-p_n <\frac{1}{10}p_n^{1/2}$ for sufficiently large $n$.

A problem of Ulam. In particular, what about $Q=\{3,5,7,11\}$?

A problem due to Ulam. For example if we begin with $3,5$ then the sequence continues $3,5,7,11,13,17,\ldots$. It is possible that this sequence is infinite.

Asked by Segal. The answer is yes, as shown by Odlyzko.

Watts has suggested that perhaps the obvious greedy algorithm defines such a permutation - that is, let $a_1=1$ and let \[a_{n+1}=\min \{ x : a_n+x\textrm{ is prime and }x\neq a_i\textrm{ for }i\leq n\}.\] In other words, do all positive integers occur as some such $a_n$? Do all primes occur as a sum?

The sequence is OEIS A002048 and begins \[1,2,4,5,8,10,14,15,16,21,22,23,25,\ldots.\] In general, if $a_1<a_2<\cdots$ is a sequence so that no $a_n$ is a sum of consecutive $a_i$s, then must the density of the $a_i$ be zero? What about the lower density?

A problem of Graham.

A question of Erdős and Heilbronn. Solved in the affirmative by da Silva and Hamidoune [dSHa94].

Probably there is no such $A$ for any polynomial $f$.

A conjecture of Graham. It is easy to see that $2^n\not\equiv 1\mod{n}$ for all $n>1$, so the restriction $k\neq 1$ is necessary. Erdős and Graham report that Graham, Lehmer, and Lehmer have proved this for $k=2^i$ for $i\geq 1$, or if $k=-1$, but I cannot find such a paper.

As an indication of the difficulty, when $k=3$ the smallest $n$ such that $2^n\equiv 3\pmod{n}$ is $n=4700063497$.

A conjecture of Newman. This was proved Chung and Graham, who in fact show that for any $\epsilon>0$ there must exist some $n$ such that there are infinitely many $m$ for which \[\lvert x_{m+n}-x_m\rvert < \frac{1}{(c-\epsilon)n}\] where \[c=1+\sum_{k\geq 1}\frac{1}{F_{2k}}=2.535\cdots\] and $F_m$ is the $m$th Fibonacci number. This constant is best possible.

Erdős and Graham write that 'it is surprising that [this problem] offers difficulty'.

The result for $\sqrt{2}$ was obtained by Graham and Pollak [GrPo70]. The problem statement is open-ended, but presumably Erdős and Graham would have been satisfied with the wide-ranging generalisations of Stoll ([St05] and [St06]).

Schur proved that $f(k)<ek!$. See also [183].

A conjecture of Roth.

First investigated by Rényi and Rédei [Re47]. Erdős [Er49b] proved that $f(k)<k^{1-c}$ for some $c>0$. The conjecture that $f(k)\to \infty$ is due to Erdős and Rényi.

Davenport and Erdős [DaEr37] proved that the answer is yes when $X_n=\{0\}$ for all $n\in A$. The problem considers logarithmic density since Besicovitch [Be34] showed examples exist without a natural density, even when $X_n=\{0\}$ for all $n\in A$.

Davenport and Erdős [DaEr37] showed that there must exist an infinite sequence $a_1<a_2\cdots$ in $A$ such that $a_i\mid a_j$ for all $i\leq j$.

This is true, a consequence of the positive solution to [447] by Kleitman [Kl71].

The example $A=\{a\}$ and $n=2a-1$ and $m=2a$ shows that $2$ would be best possible.

For example, when $A=\{p^2: p\textrm{ prime}\}$ then $B$ is the set of squarefree numbers, and the existence of this limit was proved by Erdős.

See also [208].

This would be best possible, for example letting $A=[1,N/2]\cap \mathbb{N}$ and $B=\{ N/2<p\leq N: p\textrm{ prime}\}$.

See also [425].

Erdős [Er46] proved that if $f(n+1)-f(n)=o(1)$ or $f(n+1)\geq f(n)$ then $f(n)=c\log n$ for some constant $c$.

This is true, and was proved by Wirsing [Wi70].

For example if $A=\mathbb{N}$ then $f(x)=\{x\}$ is the usual fractional part operator.

A problem due to Le Veque [LV53], who proved it in some special cases.

This is false is general, as shown by Schmidt [Sc69].

A conjecture of Schinzel.

A problem of Selfridge and Straus [SeSt58], who prove that this is true if $k=2$ and $\lvert A\rvert \neq 2^l$ (for $k\geq 0$).

The infamous Littlewood conjecture.

Originally a conjecture due to Oppenheim. Davenport and Heilbronn [DaHe46] solve the analogous problem for quadratic forms in 5 variables.

This is true, and was proved by Margulis [Ma89].

Sperner's theorem states that $\lvert \mathcal{F}\rvert \leq \binom{n}{\lfloor n/2\rfloor}$. This is also known as Dedekind's problem.

Resolved by Kleitman [Kl69], who proved that the number of such families is \[2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}}.\]