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.

In [Er85c] and [Er97c] Erdős asks whether $S$ is everywhere dense.

Asked by Erdős and Selfridge (sometimes also with Schinzel). They also asked whether there can be a covering system such that all the moduli are odd and squarefree. The answer to this stronger question is no, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

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$ (but the latter has been shown not to exist, see [586]).

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\}$. Pan [Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

The sequence of such numbers is A006286 in the OEIS.

See also [10], [11], and [16].

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$.

Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).

See also [9], [11], and [16].

Odlyzko has checked this up to $10^7$. Hercher [He24b] has verified this is true for all odd integers up to $2^{50}\approx 1.12\times 10^{15}$.

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 often asked this under the weaker assumption that $n$ is not divisible by $4$. Erdős thought that proving this with two powers of 2 is perhaps easy, and could prove that it is true (with a single power of two) for almost all $n$.

See also [9], [10], and [16].

Asked by Erdős and Sárközy [ErSa70], who proved that $A$ must have density $0$. They also prove that this is essentially best possible, in that given any function $f(x)\to \infty$ as $x\to \infty$ there exists a set $A$ with this property and infinitely many $N$ such that \[\lvert A\cap\{1,\ldots,N\}\rvert>\frac{N}{f(N)}.\] (Their example is given by all integers in $(y_i,\frac{3}{2}y_i)$ congruent to $1$ modulo $(2y_{i-1})!$, where $y_i$ is some sufficiently quickly growing sequence.)

An example of an $A$ with this property where \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0\] is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.

Elsholtz and Planitzer [ElPl17] have constructed such an $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert\gg \frac{N^{1/2}}{(\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2}.\]

Schoen [Sc01] proved that if all elements in $A$ are pairwise coprime then \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N^{2/3}\] for infinitely many $N$. Baier [Ba04] has improved this to $\ll N^{2/3}/\log N$.

For the finite version see [13].

Apparently originally considered by Erdős and Nathanson, although later Erdős attributes this to Erdős, Sárközy, and Szemerédi (but gives no reference), and claims a construction of an $A$ such that for all $\epsilon>0$ and all large $N$ \[\lvert \{1,\ldots,N\}\backslash B\rvert \ll_\epsilon N^{1/2+\epsilon},\] and yet there for all $\epsilon>0$ there exist infinitely many $N$ where \[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/3-\epsilon}.\]

Erdös and Freud investigated the finite analogue in 'a recent Hungarian paper', proving that there exists $A\subseteq \{1,\ldots,N\}$ such that the number of integers not representable in exactly one way as the sum of two elements from $A$ is $<2^{3/2}N^{1/2}$, and suggest the constant $2^{3/2}$ is perhaps 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.

In [Er98] Erdős further conjectures that \[\sum_{n=1}^\infty (-1)^n \frac{1}{n(p_{n+1}-p_n)}\] converges and \[\sum_{n=1}^\infty (-1)^n \frac{1}{p_{n+1}-p_n}\] diverges. He further conjectures that \[\sum_{n=1}^\infty (-1)^n \frac{1}{n(p_{n+1}-p_n)(\log\log n)^c}\] converges for every $c>0$, and reports that he and Nathanson can prove this for $c>2$ (and conditionally for $c=2$).

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.

Chen [Ch23] has proved the answer is no.

See also [9], [10], and [11].

The first prime without this property is $97$. The sequence of such primes is A038133 in the OEIS. These are called cluster primes.

Blecksmith, Erdős, and Selfridge [BES99] proved that the number of such primes is \[\ll_A \frac{x}{(\log x)^A}\] for every $A>0$, and Elsholtz [El03] improved this to \[\ll x\exp(-c(\log\log x)^2)\] for every $c<1/8$.

It is easy to see that almost all numbers are not practical. Erdős originally showed that $h(n!) <n$. Vose [Vo85] proved the existence of infinitely many practical $m$ such that $h(m)\ll (\log m)^{1/2}$.

The sequence of practical numbers is A005153 in the OEIS.

See also [304] and [825].

In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that (for sufficiently large $n$) \[\mathrm{rt}(n; 4,\epsilon n)\geq n^2/8?\]

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.\]

See also [615].

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.

In [Er92b] Erdős asks, more generally, if a graph on $(2k+1)n$ vertices in which every odd cycle has size $\geq 2k+1$ can be made bipartite by deleting at most $n^2$ edges.

See also the entry in the graphs problem collection.

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].

In [Er92b] and [Er97f] Erdős asks more generally: if $r\geq 5$ is odd and a graph has $rn$ vertices and the smallest odd cycle has size $r$ then is the number of cycles of size $r$ at most $n^{r}$?

This is very similar to [486].

Asked by Erdős and Tenenbaum. Ruzsa gave the following simple counterexample: let $A=\{n_1<n_2<\cdots \}$ where $n_l \equiv -(k-1)\pmod{p_k}$ for all $k\leq l$, where $p_k$ denotes the $k$th prime.

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$.

Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].

Such a set is called an additive complement to the primes.

Erdős [Er54] proved that such a set $A$ exists with $\lvert A\cap\{1,\ldots,N\}\rvert\ll (\log N)^2$ (improving a previous result of Lorentz [Lo54] who achieved $\ll (\log N)^3$). Wolke [Wo96] has shown that such a bound is almost true, in that we can achieve $\ll (\log N)^{1+o(1)}$ if we only ask for almost all integers to be representable.

The answer to the third question is yes: Ruzsa [Ru98c] has shown that we must have \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}\geq e^\gamma\approx 1.781.\]

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

It is easy to see that $S(\iota)=o(n^2)$ if $\iota$ denotes the identity permutation, as studied by Erdős and Harzheim [Er77]. Motivated by this, Erdős asked if this remains true for all permutations.

This is extremely false, as shown by Konieczny [Ko15], who both constructs an explicit permutation with $S(\pi) \geq n^2/4$, and also shows that for a random permutation we have \[S(\pi)\sim \frac{1+e^{-2}}{4}n^2.\]

See also [356] and [357].

Erdős [Er36c] proved this is true with $k$ replaced by $2k$ in the denominator (in a stronger form that only considers $A\cup (A+b)$ for some $b\in B$, see [38]).

Ruzsa has observed that this follows immediately from the stronger fact proved by Plünnecke [Pl70] that (under the same assumptions) \[d_S(A+B)\geq \alpha^{1-1/k}.\]

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$.

Erdős [Er36c] proved that if $B$ is an additive basis of order $k$ then, for any set $A$ of Schnirelmann density $\alpha$, for every $N$ there exists some integer $b\in B$ such that \[\lvert (A\cup (A+b))\cap \{1,\ldots,N\}\rvert\geq \left(\alpha+\frac{\alpha(1-\alpha)}{2k}\right)N.\] It seems an interesting question (not one that Erdős appears to have asked directly, although see [35]) to improve the lower bound here, even in the case $B=\mathbb{N}$. Erdős observed that a random set of density $\alpha$ shows that the factor of $\frac{\alpha(1-\alpha)}{2}$ in this case cannot be improved past $\alpha(1-\alpha)$.

This is a stronger propery than $B$ being an essential component (see [37]). Linnik [Li42] gave the first construction of an essential component which is not an additive basis.

See also [707].

This follows from the colouring result of Croot [Cr03]. Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$ (simply taking $n_k$ to be the lowest common multiple of some interval $[1,C^k]$). Sawhney has observed that there is also a doubly exponential lower bound, and hence this bound is essentially sharp.

Indeed, we must trivially have $\sum_{d|n_k}1/d \geq k$, or else there is a greedy colouring as a counterexample. Since $\prod_{p}(1+1/p^2)$ is finite we must have $\prod_{p|n_k}(1+1/p)\gg k$. To achieve the minimal $\prod_{p|n_k}p$ we take the product of primes up to $T$ where $\prod_{p\leq T}(1+1/p)\gg k$; by Mertens theorems this implies $T\geq C^{k}$ for some constant $C>1$, and hence $n_k\geq \prod_{p\mid n_k}p\geq \exp(cC^k)$ for some $c>0$.

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

See also [298].

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).\]

In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.

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$.

See also [694].

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

Erdős and Szemerédi proved that there exist arbitrarily large sets $A$ such that the integers which are the sum or product of distinct elements of $A$ is at most \[\exp\left(c (\log \lvert A\rvert)^2\log\log\lvert A\rvert\right)\] for some constant $c>0$.

See also [52].

This was disproved for $k=212$ by Ahlswede and Khachatrian [AhKh94], who suggest that their methods can disprove this for arbitrarily large $k$.

Erdős later asked ([Er92b] and [Er95]) if the conjecture remains true provided $N\geq (1+o(1))p_k^2$ (or, in a weaker form, whether it is true for $N$ sufficiently large depending on $k$).

See also [534].

Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density, and in [Er95d] he speculates the upper density (or even upper logarithmic density) must be $\geq 1/2$.

The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

See also [65].

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}).\]

See also the entry in the graphs problem collection.

Erdős also asked [Er87] about finding a common subgraph $H$ (with chromatic number either $4$ or $\aleph_0$) in any finite collection of graphs with chromatic number $\aleph_1$.

Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős wrote [Er87] that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.

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).

David Penman has observed that this is certainly true if the graph has uncountable chromatic number, since by a result of Erdős and Hajnal [ErHa66] such a graph must contain arbitrarily large finite complete bipartite graphs (see also Theorem 3.17 of Reiher [Re24]).

Zach Hunter has observed that this follows from the work of Liu and Montgomery [LiMo20]: if $G$ has infinite chromatic number then, for infinitely many $r$, it must contain some finite connected subgraph $G_r$ with chromatic number $r$ (via the de Bruijn-Erdős theorem [dBEr51]). Each $G_r$ contains some subgraph $H_r$ with minimum degree at least $r-1$, and hence via Theorem 1.1 of [LiMo20] there exists some $\ell_r\geq r^{1-o(1)}$ such that $H_r$ contains a cycle of every even length in $[(\log \ell)^8,\ell]$.

See also [64].

A problem of Erdős and Hajnal. 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$.

See also the entry in the graphs problem collection.

See also [57].

The decimal expansion is A331373 in the OEIS.

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

Pratt [Pr24] has proved this is irrational, conditional on a uniform version of the prime $k$-tuples conjecture.

Tao has observed that this is a special case of [257], since \[\sum_{n\geq 2}\frac{\omega(n)}{2^n}=\sum_p \frac{1}{2^p-1}.\]

Erdős and Rado proved that $\mathfrak{c}\to (\omega+n,4)_2^3$ for any $2\leq n<\omega$.

In [Er82e] Erdős credits this conjecture to himself and Burr. This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(P)$ is unknown.

See also [72].

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.)

See also [922] and the entry in the graphs problem collection.

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. In [Er95d] Erdős suggests this may even be true with an independent set of size $\gg n$.

See also [750].

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].

In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c>1/24$.

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

Wigderson [Wi24] has proved that there are infinitely many such graphs (although his proof is not explicit, and an explicit example of such a graph apart from $K_4$ is still unknown.)

A problem of Erdős and Rothschild. Alon and Trotter showed that, provided $c<1/4$, $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.

Edwards (unpublished) and Khadziivanov and Nikiforov [KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see [905]).

Fox and Loh [FoLo12] proved that \[f_c(n) \leq n^{O(1/\log\log n)}\] for all $c<1/4$, disproving the first conjecture of Erdős.

The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.

See also [600] and the entry in the graphs problem collection.

Asked by Erdős, Ordman, and Zalcstein [EOZ93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$). The example of all edges between a complete graph on $n/3$ vertices and an empty graph on $2n/3$ vertices show that $n^2/6+O(n)$ is sometimes necessary.

A split graph is one where the vertices can be split into a clique and an independent set. Every split graph is chordal. Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.

Conjectured by Erdős, Fajtlowicz, and Stanton. 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 $2^{n/2}<f(n) \leq 2^{n-2}$. The first problem was solved by Verstraëte [Ve04], who proved \[f(n)\ll 2^{n-n^{1/10}}.\] This was improved by Nenadov [Ne25] to \[f(n) \ll 2^{n-n^{1/2-o(1)}}.\]

One can also ask about the existence and value of $\lim f(n)^{1/n}$.

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$, as Faudree and McKay [FaMc93] showed that $R(W)=17$ for the pentagonal wheel $W$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/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)$.

This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.

For $n=5$ the regular pentagon is the unique such set (which has two distinct distances). Erdős mysteriously remarks in [Er90] this was proved by 'a colleague'. A published proof of this fact is provided by Kovács [Ko24c].

Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor \frac{n+1}{2}\rfloor$ distinct distances is still open. Fishburn in fact conjectures that if $R(x)$ counts the number of distinct distances from $x$ then \[\sum_{x\in A}R(x) \geq \binom{n}{2}.\]

Szemerédi conjectured (see [Er97e]) that this stronger variant remains true if we only assume that no three points are on a line, and proved this with the weaker bound of $n/3$.

See also [660].

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.

See also [95].

Conjectured by Erdős and Moser. Füredi [Fu90] proved an upper bound of $O(n\log n)$. A short proof of this bound was given by Brass and Pach [BrPa01]. The best known upper bound is \[\leq n\log_2n+4n,\] due to Aggarwal [Ag15].

Edelsbrunner and Hajnal [EdHa91] have constructed $n$ such points with $2n-7$ pairs distance $1$ apart. (This disproved an early stronger conjecture of Erdős and Moser, that the true answer was $\frac{5}{3}n+O(1)$.)

A positive answer would follow from [97]. See also [90].

Erdős could not even prove $h(n)\geq n$. Pach has shown $h(n)<n^{\log_23}$. Erdős, Füredi, and Pach [EFPR93] have improved this to \[h(n) < n\exp(c\sqrt{\log n})\] for some constant $c>0$.

Perhaps the diameter is even $\geq n-1$ for sufficiently large $n$. Piepmeyer has an example of $9$ such points with diameter $<5$. 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$.

A problem of Erdős and Purdy. It is not even known if $h_c(n)\geq 5$ (see [101]).

It is easy to see that $h_c(n) \ll_c n^{1/2}$, and Erdős originally suggested that perhaps a similar lower bound $h_c(n)\gg_c n^{1/2}$ holds. Zach Hunter has pointed out that this is false, even replacing $>3$ points on each line with $>k$ points: consider the set of points in $\{1,\ldots,m\}^d$ where $n\approx m^d$. These intersect any line in $\ll_d n^{1/d}$ points, and have $\gg_d n^2$ many pairs of points each of which determine a line with at least $k$ points. This is a construction in $\mathbb{R}^d$, but a random projection into $\mathbb{R}^2$ preserves the relevant properties.

This construction shows that $h_c(n) \ll n^{1/\log(1/c)}$.

It is not even known whether $h(n)\geq 2$ for all large $n$.

See also [99].

In [Er81d] Erdős proved that $\gg n$ many circles is possible, and that there cannot be more than $n(n-1)$ many circles. Elekes [El84] has a simple construction of a set with $\gg n^{3/2}$ such circles. This may be the correct order of magnitude.

In [Er75h] Erdős also asks how many such unit circles there must be if the points are in general position.

See also [506] and [831].

In [Er94b] Erdős dates this conjecture to 'more than 60 years ago'. Erdős proved that $f(2)=1$ in an early mathematical paper for high school students in Hungary. Newman proved (in personal communication to Erdős) that $f(5)=2$.

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

It is easy to see that $f(k^2+1)\geq k$, by first dividing the unit square into $k^2$ smaller squares of side-length $1/k$, and then replacing one square by two smaller squares of side-length $1/2k$. Halász [Ha84] gives a construction that shows $f(k^2+2)\geq k+\frac{1}{k+1}$, and in general, for any $c\geq 1$, \[f(k^2+2c+1)\geq k+\frac{c}{k}\] and \[f(k^2+2c)\geq k+\frac{c}{k+1}.\] Halász also considers the variants where we replace a square by a parallelogram or triangle.

Erdős and Soifer [ErSo95] and Campbell and Staton [CaSt05] have conjectured that, in general, for any integer $-k<c<k$, $f(k^2+2c+1)=k+\frac{c}{k}$, and proved the corresponding lower bound. Praton [Pr08] has proved that this general conjecture is equivalent to $f(k^2+1)=k$.

Baek, Koizumi, and Ueoro [BKU24] have proved $g(k^2+1)=k$, where $g(\cdot)$ is defined identically to $f(\cdot)$ with the additional assumption that all squares have sides parallel to the sides of the unit square. More generally, they prove that $g(k^2+2c+1)=k+c/k$ for any $-k<c<k$, which determines all values of $g(\cdot)$.

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

In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]

See also the entry in the graphs problem collection and [740] for the infinitary version.

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

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

A theorem of de Bruijn and Erdős [dBEr51] implies that, if $G$ has infinite chromatic number, then $G$ has a finite subgraph of chromatic number $n$ for every $n\geq 1$.

In [Er95d] Erdős suggests this is true, although such an $F$ must grow faster than the $k$-fold iterated exponential function for any $k$.

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Every $G$ with chromatic number $\aleph_1$ must have $h_G(n)\gg n$ since $G$ must contain, for some $r$, $\aleph_1$ many vertex disjoint odd cycles of length $2r+1$.

On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In [Er81] Erdős conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.

See also [74].

A problem of Erdős and Rado [ErRa67], who showed $k(n,m) \ll_m n^{m-1}$, or more precisely, \[k(n,m) \leq \frac{2^{m-1}(n-1)^m+n-2}{2n-3}.\] Larson and Mitchell [LaMi97] improved the dependence on $m$, establishing in particular that $k(n,3)\leq n^{2}$. Zach Hunter has observed that \[R(n,m) \leq k(n,m)\leq R(n,m,m),\] which in particular proves the upper bound $k(n,m)\leq 3^{n+2m}$.

See also the entry in the graphs problem collection - on this site the problem replaces transitive tournament with directed path, but Zach Hunter and Raphael Steiner have a simple argument that proves, for this alternative definition, that $k(n,m)=(n-1)(m-1)$.

A problem of Erdős, Herzog, and Piranian [EHP58].

The lower bound is easy: this is $\geq n$ and equality holds if and only if $p(z)=z^n$. The assumption that the set is connected is necessary, as witnessed for example by $p(z)=z^2+10z+1$.

The Chebyshev polynomials show that $n^2/2$ is best possible here. Erdős originally conjectured this without the $o(1)$ term but Szabados observed that was too strong. Pommerenke [Po59a] proved an upper bound of $\frac{e}{2}n^2$.

Eremenko and Lempert [ErLe94] have shown this is true, and in fact Chebyshev polynomials are the extreme examples.

Conjectured by Erdős, Herzog, and Piranian [EHP58]. 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$. Erdős [Er97f] writes that the lower bound was already known to Isaacs.

Conjectured by Erdős and Hajnal. In arrow notation, this is asking where $\alpha \to (\alpha,3)^2$ implies $\alpha \to (\alpha, n)^2$ for every finite $n$.

The answer is no, as independently shown by Schipperus [Sc99] (published in [Sc10]) and Darby [Da99].

For example, Larson [La00] has shown that this is false when $\alpha=\omega^{\omega^2}$ and $n=5$. There is more background and proof sketches in Chapter 2.9 of [HST10], by Hajnal and Larson.

Conjectured by Erdős, Sós, and Sárkzözy [ESS95], who proved \[F_2(N)=\left(\frac{6}{\pi^2}+o(1)\right)N,\] \[F_3(N) = (1-o(1))N,\] and also established asymptotics for $F_k(N)$ for all even $k\geq 4$ (in particular $F_k(N)\asymp N/\log N$ for all even $k\geq 4$). Erdős [Er38] earlier proved that $F_4(N)=o(N)$ - indeed, if $\lvert A\rvert \gg N$ and $A\subseteq \{1,\ldots,N\}$ then there is a non-trivial solution to $ab=cd$ with $a,b,c,d\in A$.

Erdős (and independently Hall [Ha96] and Montgomery) also asked about $F(N)$, the size of the largest $A\subseteq\{1,\ldots,N\}$ such that the product of no odd number of $a\in A$ is a square. Ruzsa [Ru77] observed that $1/2<\lim F(N)/N <1$. Granville and Soundararajan [GrSo01] proved an asymptotic \[F(N)=(1-c+o(1))N\] where $c=0.1715\ldots$ is an explicit constant.

This problem was answered in the negative by Tao [Ta24], who proved that for any $k\geq 4$ there is some constant $c_k>0$ such that $F_k(N) \leq (1-c_k+o(1))N$.

See also [888].

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

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

See also [125].

A problem of Burr, Erdős, Graham, and Li [BEGL96]. More generally, if $n_1<\cdots<n_k$ have \[\sum_{i=1}^k\log_{n_k}(2)>1\] and $A_i$ is the set of integers with only the digits $0,1$ in base $n_i$ then does $A_1+\cdots+A_k$ have positive density? Melfi [Me01] noted this is false as written, with a counterexample given by $\{3,9,81\}$, but suggests it is true if we further insist that the $n_k$ are pairwise coprime.

If $C=A+B$ then Melfi [Me01] showed $\lvert C\cap[1,x]\rvert \gg x^{0.965}$ and Hasler and Melfi [HaMe24] improved this to $\lvert C\cap [1,x]\rvert \gg x^{0.9777}$. Hasler and Melfi also show that the lower density of $C$ is at least \[\frac{1015}{1458}\approx 0.69616.\]

See also [124].

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. Erdős thought it 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, and indeed $R(n;3,2) \geq C^{n}$:

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), provided $N \leq 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.

Asked by Andrásfai and Erdős. Erdős [Er97b] also asked where such a graph could contain an infinite complete graph, but this is impossible by an earlier result of Anning and Erdős [AnEr45].

See also [213].

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. The lower bound $f(n)\geq (1-o(1))\sqrt{n}$ follows from the fact that a graph with maximum degree $d$ and diameter $2$ has at most $1+d+d(d-1)=d^2+1$ many vertices.

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}$. This construction proves that \[f(n) \leq n^{(1+o(1))\frac{2}{3H(1/3)}}=n^{0.7182\cdots},\] where $H(x)$ is the binary entropy function. In [Er97b] Erdős encouraged the reader to try and find a better construction.

In this note Alon provides a simple construction that proves $f(n) \ll \sqrt{n\log n}$: take a triangle-free graph with independence number $\ll \sqrt{n\log n}$ (the existence of which is the lower bound in [165]) and add edges until it has diameter $2$; the neighbourhood of any set is an independent set and hence the maximum degree is still $\ll \sqrt{n\log n}$.

Hanson and Seyffarth [HaSe84] proved that $f(n)\leq (\sqrt{2}+o(1))\sqrt{n}$ using a Cayley graph on $\mathbb{Z}/n\mathbb{Z}$, with the generating set given by some symmetric complete sum-free set of size $\sim \sqrt{n}$. An alternative construction of such a complete sum-free set was given by Haviv and Levy [HaLe18].

Füredi and Seress [FuSe94] proved that $f(n)\leq (\frac{2}{\sqrt{3}}+o(1))\sqrt{n}$.

The precise asymptotics of $f(n)$ are unknown; Alon believes that the truth is $f(n)\sim \sqrt{n}$.

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$.

In this note Alon solves this problem in a strong form, in particular proving that a triangle-free graph on $n$ vertices with maximum degree $<n^{1/2-\epsilon}$ can be made into a triangle-free graph with diameter $2$ by adding at most $O(n^{2-\epsilon})$ edges.

See also [618].

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.

Conjectured by Erdős and Selfridge. There are infinitely many $n$ such that $n(n+1)$ is powerful (see [364]). Erdős and Selfridge proved that $N$ can never be a perfect power. Erdős remarked that this 'seems hopeless at present'.

In [Er82c] he further conjectures that, if $m,k$ are fixed and $n$ is sufficiently large, then there must be at least $k$ distinct primes $p$ such that \[p\mid m(m+1)\cdots (m+n)\] and yet $p^2$ does not divide the right-hand side.

See also [364].

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}}}}}.\]

In [Er81] Erdős further asks whether $W(k+1)/W(k)\to \infty$, or $W(k+1)-W(k)\to \infty$.

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'.

The existence of such progressions for small $k$ has been verified for $k\leq 10$, see the Wikipedia page. It is open, even for $k=3$, whether there are infinitely many such progressions.

See also [219].

Erdős [Er51] proved this for all $0\leq \alpha \leq 2$, and Hooley [Ho73] extended this to all $\alpha \leq 3$.

See also [208].

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 in 1985 (see [FGST89]). This bound would be the best possible, as witnessed by a blowup of $C_5$. The minimum number of such sets required is sometimes called the strong chromatic index of $G$.

The weaker conjecture that there exists some $c>0$ such that $(2-c)\Delta^2$ sets suffice was proved by Molloy and Reed [MoRe97], who proved that $1.998\Delta^2$ sets suffice (for $\Delta$ sufficiently large). This was improved to $1.93\Delta^2$ by Bruhn and Joos [BrJo18] and to $1.835\Delta^2$ by Bonamy, Perrett, and Postle [BPP22]. The best bound currently available is \[1.772\Delta^2,\] proved by Hurley, de Joannis de Verclos, and Kang [HJK22].

Erdős and Nešetřil 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, who also ask whether $c(3m+2)=3^m$. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

Solved by Bradač [Br24], who proved that $\alpha=\lim c(n)^{1/n}$ exists and \[\alpha \leq 2^{H(1/3)}=1.8899\cdots,\] where $H(\cdot)$ is the binary entropy function. Seymour's construction proves that $\alpha\geq 3^{1/3}=1.442\cdots$. Bradač conjectures that this lower bound is the true value of $\alpha$.

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 infinite 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]. It follows immediately using the Sidon property that $A+A$ is similarly well-distributed.

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

A question of Erdős, Sárközy, and Sós [ESS94]. It is easy to prove that the greedy construction of a maximal Sidon set in $\{1,\ldots,N\}$ has size $\gg N^{1/3}$. Ruzsa [Ru98b] constructed a maximal Sidon set of size $\ll (N\log N)^{1/3}$.

See also [340].

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 [EFRS78]), and the lower bound is due to Spencer [Sp77].

This problem is #17 in Ramsey Theory in the graphs problem collection.

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. This is equivalent to showing that if $H$ is the union of $c$ forests then $R(H)\ll_c n$, and also that if every subgraph has average degree at most $d$ then $R(H)\ll_d n$. Solved by Lee [Le16], who proved that \[ R(H) \leq 2^{2^{O(d)}}n.\]

This problem is #9 in Ramsey Theory in the graphs problem collection. See also [800].

Erdős [Er35] proved that this sum always converges for a primitive set. Lichtman [Li23] proved that the answer is yes.

A problem of Tuza. It is trivial that $G$ can be made triangle-free after removing at most $3k$ edges. The examples of $K_4$ and $K_5$ show that $2k$ would be best possible.

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].

It is easy to see that $4\mid \binom{2n}{n}$ except when $n=2^k$, and hence it suffices to prove this when $n$ is a power of $2$.

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$?

Spencer [Sp73] has proved that if $k=2^tm$ with $m$ odd then \[N(k,1)=2^t(k-1)+1.\] Erdős and Graham write that 'no decent bound' is known even for $N(k,2)$. 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. In fact, they show that, if $r_\ell(N)$ is the size of the largest subset of $\{1,\ldots,N\}$ without an $\ell$-term arithmetic progression then there exists some absolute constant $c>0$ such that \[\left(c \frac{r_\ell(N)}{N}\right)^{2(k-1)}N^2 < F_k(N,\ell) <\left(\frac{r_\ell(N)}{N}\right)^{O(1)}N^2.\] Any improved bounds for Szemerédi's theorem (see [139]) therefore yield improved bounds for $F_k(N,\ell)$. In particular, the bounds of Leng, Sah, and Sawhney [LSS24] imply \[F_k(N,\ell) \leq \frac{N^2}{\exp((\log\log N)^{c_\ell})}\] for some constant $c_\ell>0$.

A problem of Erdős and Simonovits.

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.

See also [575] and the entry in the graphs problem collection.

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.)

See also the entry in the graphs problem collection.

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, who proved that $O(n\log n)$ many cycles and edges suffices.

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.

Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.

See also [583].

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^{1/4+o(1)}.\] The lower bound is due to Bosznay [Bo89] and the upper bound to Pham and Zakharov [PhZa24], improving an earlier bounds of Conlon, Fox, and Pham [CFP23]. The original upper bound of Erdős and Sárközy [ErSa90] was $\ll (N\log N)^{1/2}$).

See also [789].

Originally asked by Cohen. Erdős observed that colouring according to whether $\{ \sqrt{2}n\}<1/2$ or not implies $f(d) \ll d$ (using the fact that $\|\sqrt{2}q\| \gg 1/q$ for all $q$, where $\|x\|$ is the distance to the nearest integer). 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$. Erdős and Graham claim that $k\leq 10000000$ ('more or less'), but give no proof.

Erdős and Graham asked this with just any $k$-term arithmetic progression in blue (not necessarily with distance $1$), but Alon has pointed out that in fact no such $k$ exists: in any red/blue colouring of the integer points on a line either there are two red points distance $1$ apart, or else the set of blue points and the same set shifted by $1$ cover all integers, and hence by van der Waerden's theorem there are arbitrarily long blue arithmetic progressions.

It seems most likely, from context, that Erdős and Graham intended to restrict the blue arithmetic progression to have distance $1$ (although they do not write this restriction in their papers).

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.\]

This is true for $d\leq 3$ and false for $d\geq 4$.

This problem is equivalent to one on 'abelian squares' (see [231]). In particular $A$ can be interpreted as an infinite string over an alphabet with $d$ letters (each letter describining which of the $d$ possible steps is taken at each point). An abelian square in a string $s$ is a pair of consecutive blocks $x$ and $y$ appearing in $s$ such that $y$ is a permutation of $x$. The connection comes from the observation that $p,q,r\in A\subset \mathbb{R}^d$ form a three-term arithmetic progression if and only if the string corresponding to the steps from $p$ to $q$ is a permutation of the string corresponding to the steps from $q$ to $r$.

This problem is therefore equivalent to asking for which $d$ there exists an infinite string over $\{1,\ldots,d\}$ with no abelian squares. It is easy to check that in fact any finite string of length $7$ over $\{1,2,3\}$ contains an abelian square.

An infinite string without abelian squares was constructed when $d=4$ by Keränen [Ke92]. We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results, and a blog post by Renan for an entertaining and educational discussion.

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

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

See also [195] and [196].

Geneson [Ge19] proved that $k\leq 5$. Adenwalla [Ad22] proved that $k\leq 4$.

See also [194] and [196].

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.

See also [194] and [195].

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$.

First asked and investigated by Riddell [Ri69]. 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_k 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.

These bounds were improved by Croot [Cr03b] who proved \[\frac{N}{L(N)^{\sqrt{2}+o(1)}}< f(N)<\frac{N}{L(N)^{1/6-o(1)}},\] where $f(N)=\exp(\sqrt{\log N\log\log N})$. These bounds were further improved by Chen [Ch05] and then by de la Bretéche, Ford, and Vandehey [BFV13] to \[\frac{N}{L(N)^{1+o(1)}}<f(N) < \frac{N}{L(N)^{\sqrt{3}/2+o(1)}}.\] The latter authors conjecture that the lower bound here is 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.

Adenwalla [Ad25] has proved there are no such $n$.

In general, for any $n$ one can try to choose such $a_d$ to maximise the density of integers so covered, and ask what this density is. This was also investigated by Adenwalla [Ad25].

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 odd integers which cannot be so represented.

See also [851].

Erdős and Graham write it is 'not difficult' to construct irrational $x$ such that this fails (although give no proof or reference, and it seems to still be an open problem to actually construct some such irrational $x$). Curtiss [Cu22] showed that this is true for $x=1$ and Erdős [Er50b] showed it is true for all $x=1/m$ with $m\geq 1$. Nathanson [Na23] has shown it is true for $x=a/b$ when $a\mid b+1$ and Chu [Ch23b] has shown it is true for a larger class of rationals; it is still unknown whether this is true for all rational $x>0$.

Without the 'eventually' condition this can fail for some rational $x$ (although Erdős [Er50b] showed it holds without the eventually for rationals of the form $1/m$). For example \[R_1(\tfrac{11}{24})=\frac{1}{3}\] but \[R_2(\tfrac{11}{24})=\frac{1}{4}+\frac{1}{5}.\]

Kovač [Ko24b] has proved that this is false - in fact as false as possible: the set of $x\in (0,\infty)$ for which the best underapproximations are eventually 'greedy' has Lebesgue measure zero. (It remains an open problem to give any explicit example of a number which is not eventually greedy, despite the fact that almost all numbers have this property.)

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.

In [Er79] Erdős says perhaps $s_{n+1}-s_n \ll \log s_n$, but he is 'very doubtful'.

Filaseta and Trifonov [FiTr92] proved an upper bound of $s_n^{1/5}$. Pandey [Pa24] has improved this exponent to $1/5-c$ for some constant $c>0$.

See also [489] and [145].

Equivalently, one can ask the dual problem: given $n$ points in $\mathbb{R}^2$ such that there are no lines containing at least four points then there are three points such that the lines determined by them are ordinary ones (i.e. contain exactly two points each).

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$. The fact that $f(n)\geq 1$ was conjectured by Sylvester in 1893. Erdős rediscovered this conjecture in 1933 and told it to Gallai who proved it.

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$. (A proof that $f(n)\geq n/2$ for large $n$ was earlier claimed by Hansen but this proof was flawed.)

The bound of $n/2$ is best possible for even $n$, since one could take $n/2$ points on a circle and $n/2$ points at infinity. Surprisingly, Green and Tao [GrTa13] show that if $n$ is odd then $f(n)\geq 3\lfloor n/4\rfloor$.

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. The same conclusion was independently obtained by Shaffaf [Sh18].

Indeed, Shaffaf and Tao actually proved that such a rational distance set must be contained in a finite union of real algebraic curves. Solymosi and de Zeeuw [SdZ10] then proved (unconditionally) that a rational distance set contained in a real algebraic curve must be finite, unless the curve contains a line or a circle.

Ascher, Braune, and Turchet [ABT20] observed that, combined, these facts imply that a rational distance set in general position must be finite (conditional on the Bombieri-Lang conjecture).

Anning and Erdős [AnEr45] proved there cannot exist an infinite such set. Harborth constructed such a set when $n=5$. The best construction to date, due to Kreisel and Kurz [KK08], has $n=7$.

Ascher, Braune, and Turchet [ABT20] have shown that there is a uniform upper bound on the size of such a set, conditional on the Bombieri-Lang conjecture. Greenfeld, Iliopoulou, and Peluse [GIP24] have shown (unconditionally) that any such set must be very sparse, in that if $S\subseteq [-N,N]^2$ has no three on a line and no four on a circle, and all pairwise distances integers, then \[\lvert S\rvert \ll (\log N)^{O(1)}.\]

See also [130].

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 [107], 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$.

This problem is #2 in Ramsey Theory in the graphs problem collection.

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 Palásti has proved such sets exist for all $n\leq 8$. Erdős believed this is impossible for all sufficiently large $n$.

In [Er85c] Erdős also conjectures that $d_n=d_{n+1}=\cdots=d_{n+k}$ is solvable for every $k$ (which is equivalent to $k$ consecutive primes in arithmetic progression, see [141]).

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.

See also [3] and [141].

Lorentz [Lo54] proved 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\] The answer is yes, proved by Ruzsa [Ru72]. Ruzsa's construction is ingeniously simple: \[A = \{ 5^nm : m\geq 1\textrm{ and }5^n\geq C\log m\}+\{0,1\}\] for some large absolute constant $C>0$. That every large integer is of the form $2^k+a$ for some $a\in A$ is a consequence of the fact that $2$ is a primitive root of $5^n$ for all $n\geq 1$.

In [Ru01] Ruzsa constructs an asymptotically best possible answer to this question (a so-called 'exact additive complement'); that is, there is such a set $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert \sim \frac{N}{\log_2N}\] as $N\to \infty$.

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}.\]

The differences are listed at A256435 on the OEIS.

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

See also [132].

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].

This was solved independently by Kristiansen [Kr74] (only in the case when $c_k\in\mathbb{R}$) and Saff and Sheil-Small [SSS73] (for general $c_k\in \mathbb{C}$).

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

Solved by Barth and Schneider [BaSc70], who proved that if $A,B\subset\mathbb{R}$ are countable dense sets then there exists a transcendental entire function $f$ such that $f(z)\in B$ if and only if $z\in A$. In [BaSc71] they proved the same result for countable dense subsets of $\mathbb{C}$.

Clunie (unpublished) proved this if $a_n\geq 0$ for all $n$. This was disproved in general by Clunie and Hayman [ClHa64], who showed that the limit can take any value in $[0,1/2]$.

See also [513].

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

See also [230].

Solved in the affirmative by Barth and Schneider [BaSc72].

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 for all $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$.

See also [228].

Erdős initially conjectured that the answer is yes for all $k\geq 2$, but for $k=4$ this was disproved by de Bruijn and Erdős. At least, this is what Erdős writes, but gives no construction or reference, and a simple computer search produces no such counterexamples for $k=4$. Perhaps Erdős meant $2^k$, where indeed there is an example for $k=4$: \[1213121412132124.\]

Erdős then asked if there is in fact an infinite string formed from $\{1,2,3,4\}$ which contains no abelian squares? This is equivalent to [192], and such a string was constructed by Keränen [Ke92]. The existence of this infinite string gives a negative answer to the problem for all $k\geq 4$.

Containing no abelian squares is a stronger property than being squarefree (the existence of infinitely long squarefree strings over alphabets with $k\geq 3$ characters was established by Thue).

We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results.

A question of Moser [Mo66]. A lower bound of $m_1\geq \pi/8\sqrt{3}\approx 0.2267$ is given by taking the union of open circular discus of radius $1/2$ at a regular hexagonal lattice suitably spaced aprt. Croft [Cr67] gives a small improvement of $m_1\geq 0.22936$.

The trivial upper bound is $m_1\leq 1/2$, since for any unit vector $u$ the sets $A$ and $A+u$ must be disjoint. Erdős' question was solved by Ambrus, Csiszárik, Matolcsi, Varga, and Zsámboki [ACMVZ23] who proved that $m_1\leq 0.247$.

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$.

The values of the sum are listed at A074741 on the OEIS.

Solved by Hooley [Ho65], who proved that these gaps have an exponential distribution: that is, if $f(c)$ is the function in question, then \[f(c)=(1+o(1))(1-e^{-c})\] (where the $o(1)$ goes to $0$ uniformly as $k\to \infty$).

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 $1< 2^k<n$ the number $n-2^k$ is prime (probably $n=105$ is the largest such integer).

The sequence of values of $f(n)$ is A109925 on the OEIS.

See also [237].

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

See also [236].

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 Wirsing [Wi67], and generalised 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 [Po18], that if $f(n)$ is a quadratic integer polynomial without repeated roots then as $n\to \infty$ the largest prime factor of $f(n)$ also approaches infinity. Indeed, if $P$ is a finite set of primes and $(a_i)$ is the set of integers divisible only by primes in $P$, and $a_{i+1}-a_i$ is bounded, then there exists some $k$ such that $a_{i+1}=a_i+k$ infinitely often, which contradicts Pólya's theorem with $f(n)=n(n+k)$.

Tijdeman [Ti73] proved that, if $P$ is a finite set of primes, then \[a_{i+1}-a_i \gg \frac{a_i}{(\log a_i)^C}\] for some constant $C>0$ depending on $P$.

Tijdeman [Ti73] resolved this question, proving that, for any $\epsilon>0$, there exists an infinite set of primes $P$ such that, with $a_i$ defined as above, \[a_{i+1}-a_i \gg a_i^{1-\epsilon}.\]

See also [368].

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].

See also [899] for the difference set analogue.

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).'

See also [679] and [827].

The decimal expansion of this sum is A256936 on the OEIS.

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

The decimal expansion of this sum is A098990 on the OEIS.

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)$.

The answer is yes, as proved by Schmidt [Sc68], who later showed [Sc72] that in fact this is true for all but countably many intervals of the shape $[0,x]$.

Essentially the best possible result was proved by Tijdeman and Wagner [TiWa80], who proved that, for almost all intervals of the shape $[0,x)$, we have \[\limsup_{N\to \infty}\frac{\lvert D_N([0,x))\rvert}{\log N}\gg 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$.

This was improved to \[f(n) \leq \exp( cn^{1/3}(\log n)^{4/3})\] by Odlyzko [Od82].

If we denote by $f^*(n)$ the analogous quantity with the assumption that $a_1<\cdots<a_n$ then Bourgain and Chang [BoCh18] prove that \[f^*(n)< \exp(c(n\log n)^{1/2}\log\log n).\]

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 Erdős [Er48] proved is irrational.

The case when $A$ is the set of primes is [69].

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$. Erdős [Er48] proved that $\sum_n \frac{d(n)}{t^n}$ is irrational for any integer $t\geq 2$.

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].

In [Er88c] Erdős notes that Cusick had a simple proof that there do exist infinitely many such $n$. Erdős does not record what this was, but Kovač has provided the following proof: for every positive integer $m$ and $n=2^{m+1}-m-2$ we have \[\frac{n}{2^n}=\sum_{n<k\leq n+m}\frac{k}{2^k}.\]

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$.

This was essentially solved by Hančl [Ha91], who proved that such a sequence needs to satisfy \[\limsup_{n\to \infty} \frac{\log_2\log_2 a_n}{n} \geq 1.\] More generally, if $a_n\ll 2^{2^{n-F(n)}}$ with $F(n)<n$ and $\sum 2^{-F(n)}<\infty$ then $a_n$ cannot be an irrationality sequence.

One possible definition of an 'irrationality sequence' (see also [262] and [264]). A folklore result states that $\sum \frac{1}{a_n}$ is irrational whenever $\lim a_n^{1/2^n}=\infty$.

Kovač and Tao [KoTa24] have proved that any strictly increasing sequence such that $\sum \frac{1}{a_n}$ converges and $\lim a_{n+1}/a_n^2=0$ is not such an irrationality sequence. On the other hand, if \[\liminf \frac{a_{n+1}}{a_n^{2+\epsilon}}>0\] for some $\epsilon>0$ then the above folklore result implies that $a_n$ is such an irrationality sequence.

A possible definition of an 'irrationality sequence' (see also [262] and [263]). One example is $a_n=2^{2^n}$. In [ErGr80] they also ask whether such a sequence can have polynomial growth, but Erdős later retracted this in [Er88c], claiming 'It is not hard to show that it cannot increase slower than exponentially'.

Kovač and Tao [KoTa24c] have proved that $2^n$ is not such an irrationality sequence. More generally, they prove that any strictly increasing sequence of positive integers such that $\sum\frac{1}{a_n}$ converges and \[\liminf \left(a_n^2\sum_{k>n}\frac{1}{a_k^2}\right) >0 \] is not such an irrationality sequence. In particular, any strictly increasing sequence with $\limsup a_{n+1}/a_n <\infty$ is not such an irrationality sequence.

On the other hand, Kovač and Tao do prove that for any function $F$ with $\lim F(n+1)/F(n)=\infty$ there exists such an irrationality sequence with $a_n\sim F(n)$.

Cantor observed that $a_n=\binom{n}{2}$ is such a sequence. If we replace $-1$ by a different constant then higher degree polynomials can be used - for example if we consider $\sum_{n\geq 2}\frac{1}{a_n}$ and $\sum_{n\geq 2}\frac{1}{a_n-12}$ then $a_n=n^3+6n^2+5n$ is an example of both series being rational.

Erdős believed that $a_n^{1/n}\to \infty$ is possible, but $a_n^{1/2^n}\to 1$ is necessary.

This has been almost completely solved by Kovač and Tao [KoTa24], who prove that such a sequence can grow doubly exponentially. More precisely, there exists such a sequence such that $a_n^{1/\beta^n}\to \infty$ for some $\beta >1$.

It remains open whether one can achieve \[\limsup a_n^{1/2^n}>1.\] A folklore result states that $\sum \frac{1}{a_n}$ is irrational whenever $\lim a_n^{1/2^n}=\infty$, and hence such a sequence cannot grow faster than doubly exponentially - the remaining question is the precise exponent possible.

This conjecture is due to Stolarsky.

A negative answer was proved by Kovač and Tao [KoTa24], who proved even more: there exists a strictly increasing sequence of positive integers $a_n$ such that \[\sum \frac{1}{a_n+t}\] converges to a rational number for every $t\in \mathbb{Q}$ (with $t\neq -a_n$ for all $n$).

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 sum $\sum \frac{1}{F_n}$ itself was proved to be irrational by André-Jeannin [An89].

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$.

The answer is yes, proved by Kovač [Ko24], who constructs an explicit open ball inside the set. Kovač and Tao [KoTa24] have proved an analogous result for all higher dimensions.

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], and conjectured in general that such a sequence always eventually either satisfies \[a_k\asymp k^{\log_23}\] or \[a_k \asymp \frac{k^2}{\log k}.\] There is no known sequence which satisfies the second growth rate, but Lindhurst [Li90] gives data which suggests that $A(4)$ has such growth ($A(4)$ is given as A005487 in the OEIS).

Moy [Mo11] has proved that, for all such sequences, for all $\epsilon>0$, $a_k\leq (\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$.

In general, sequences which begin with some initial segment and thereafter are continued in a greedy fashion to avoid three-term arithmetic progressions are known as Stanley sequences.

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. In [Er97c] Erdős asks this for finite (not necessarily abelian) groups.

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'.

This was answered affirmatively by Haight [Ha79].

Simpson [Si86] has observed that the density of integers covered is at least \[\sum_i \frac{1}{n_i}-\sum_{i<j}\frac{1}{[n_i,n_j]}+\sum_{i<j<k}\frac{1}{[n_i,n_j,n_k]}-\cdot\] (where $[\cdots]$ denotes the least common multiple) which is achieved when all $a_i$ are equal, settling the second question.

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).

Note that since the $k$th prime is $\sim k\log k$ the lower bound $n_k>(1+\epsilon)k\log k$ is best possible here.

The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$. If the $n_i$ are pairwise relatively prime then it is sufficient that $\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$.

Alekseyev [Al19] has proved this when $p(x)=x^2$, for all $m>8542$. For example, \[1=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}\] and \[200 = 2^2+4^2+6^2+12^2.\]

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.

For example, \[\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{20}=1.\] 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}.\]

The smallest $b$ for each $a$ are listed at A375081 at the OEIS.

This was resolved in the affirmative by van Doorn [vD24], who proved $b=b(a)$ always exists, and in fact $b(a) \ll a$. Indeed, if $a\in (3^k,3^{k+1}]$ then one can take $b=2\cdot 3^{k+1}-1$. van Doorn also proves that $b(a)>a+(1/2-o(1))\log a$, and considers various generalisations of the original problem.

It seems likely that $b(a)\leq (1+o(1))a$, and perhaps even $b(a)\leq a+(\log a)^{O(1)}$.

Steinerberger has observed that the answer to the second question is trivially yes: for example, any $n$ which begins with a $2$ in base $3$ has $3\mid (a_n,L_n)$.

More generally, if the leading digit of $n$ in base $p$ is $p-1$ then $p\mid (a_n,L_n)$. There is in fact a necessary and sufficient condition: a prime $p\leq n$ divides $(a_n,L_n)$ if and only if $p$ divides the numerator of $1+\cdots+\frac{1}{k}$, where $k$ is the leading digit of $n$ in base $p$. This can be seen by writing \[a_n = \frac{L_n}{1}+\cdots+\frac{L_n}{n}\] and observing that the right-hand side is congruent to $1+\cdots+1/k$ modulo $p$. (The previous claim about $p-1$ follows immediately from Wolstenholme's theorem.)

This leads to a heuristic prediction (see for example a preprint of Shiu [Sh16]) of $\asymp\frac{x}{\log x}$ for the number of $n\in [1,x]$ such that $(a_n,L_n)=1$. In particular, there should be infinitely many $n$, but the set of such $n$ should have density zero. Unfortunately this heuristic is difficult to turn into a proof.

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

The answer is yes, as proved by Martin [Ma00], who in fact proved that if $B=\mathbb{N}\backslash A$ then, for all large $x$, \[\frac{\lvert B\cap [1,x]\rvert}{x}\asymp \frac{\log\log x}{\log x},\] and also gave an essentially complete description of $B$ as those integers which are small multiples of prime powers.

van Doorn has observed that if $n\in A$ (with $n>1$) then $2n\in A$ also, since if $\sum \frac{1}{m_i}=1$ then $\frac{1}{2}+\sum\frac{1}{2m_i}=1$ also.

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] could show \[t(N)\ll\frac{N}{\log N},\] but had no idea of the true value of $t(N)$.

Solved by Liu and Sawhney [LiSa24] (up to $(\log\log N)^{O(1)}$), who proved that \[\frac{N}{(\log N)(\log\log N)^3(\log\log\log N)^{O(1)}}\ll t(N) \ll \frac{N}{\log 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 [Bl21] (coupled with the trivial greedy approach) implies that $k(N)=(1-o(1))\log N$.

It was not even known for a long time whether this is $2^{cN}$ for some $c<1$ or $2^{(1+o(1))N}$. In fact the former is true, and the correct value of $c$ is now known.

• Steinerberger [St24] proved the relevant count is at most $2^{0.93N}$;
• Independently, Liu and Sawhney [LiSa24] gave both upper and lower bounds, proving that the count is \[2^{(0.91\cdots+o(1))N},\] where $0.91\cdots$ is an explicit number defined as the solution to a certain integral equation;
• Again independently this same asymptotic was proved (with a different proof) by Conlon, Fox, He, Mubayi, Pham, Suk, and Verstraëte [CFHMPSV24], who prove more generally, for any $x\in \mathbb{Q}_{>0}$, a similar expression for the number of $A\subseteq \{1,\ldots,N\}$ such that $\sum_{n\in A}\frac{1}{n}=x$;
• The above papers all appeared within weeks of each other in 2024; in 2017 a similar question (with $\leq 1$ rather than $=1$) was asked on MathOverflow by Mikhail Tikhomirov and proofs of the correct asymptotic were sketched by Lucia, RaphaelB4, and js21.

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

See also [46] and [47].

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$.

Liu and Sawhney [LiSa24] have proved that $A(N)=(1-1/e+o(1))N$.

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

Wouter van Doorn has given an elementary argument that proves \[f(N)\leq (25/28+o(1))N.\] Indeed, consider the sets $S_a=\{2a,3a,4a,6a,12a\}\cap [1,N]$ as $a$ ranges over all integers of the form $8^b9^cd$ with $(d,6)=1$. All such $S_a$ are disjoint and, if $A$ has no solutions to the given equation, then $A$ must omit at least two elements of $S_a$ when $a\leq N/12$ and at least one element of $S_a$ when $N/12<a\leq N/6$, and an elementary calculation concludes the proof.

Stijn Cambie and Wouter van Doorn have noted that, if we allow solutions to this equation with non-distinct $b_i$, then the size of the maximal set is at most $N/2$. Indeed, this is the classical threshold for the existence of some distinct $a,b\in A$ such that $a\mid b$.

See also [302] and [327].

The colouring version of this is [303], which was solved by Brown and Rödl [BrRo91]. One can take either $A$ to be all odd integers in $[1,N]$ or all integers in $[N/2,N]$ to show $f(N)\geq (1/2+o(1))N$.

Wouter van Doorn has proved, in an unpublished note, that \[f(N) \leq (9/10+o(1))N.\] Stijn Cambie has observed that \[f(N)\geq (5/8+o(1))N,\] taking $A$ to be all odd integers $\leq N/4$ and all integers in $[N/2,N]$.

Stijn Cambie has also observed that, if we allow $b=c$, then there is a solution to this equation when $\lvert A\rvert \geq (\tfrac{2}{3}+o(1))N$, since then there must exist some $n,2n\in A$.

See also [301] and [327].

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.\]

This was solved by Yokota [Yo88], who proved that \[D(b)\ll b(\log b)(\log\log b)^4(\log\log\log b)^2.\] This was improved by Liu and Sawhney [LiSa24] to \[D(b)\ll b(\log b)(\log\log b)^3(\log\log\log b)^{O(1)}.\]

For $n_i$ the product of three distinct primes, this is true when $b=1$, as proved by Butler, Erdős and Graham [BEG15] (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$?

This was essentially solved by Croot [Cr99], who proved that if $f(N)$ is the smallest integer not representable then \[\left\lfloor\sum_{n\leq N}\frac{1}{n}-\frac{9}{2}(1+o(1))\frac{(\log\log N)^2}{\log N}\right\rfloor\leq f(N)\] and \[f(N)\leq \left\lfloor\sum_{n\leq N}\frac{1}{n}-\frac{1}{2}(1+o(1))\frac{(\log\log N)^2}{\log N}\right\rfloor.\] It follows that, if $m_N=\lfloor \sum_{n\leq N}\frac{1}{n}\rfloor$, then the set of integers representable is, for all $N$ sufficiently large, either $\{1,\ldots,m_N-1\}$ or $\{1,\ldots,m_N\}$.

The answer to the second question is no: there are at least $(1-o(1))\log N$ many such integers, which follows from a more precise result of Croot [Cr99], who showed that every integer at most \[\leq \sum_{n\leq N}\frac{1}{n}-(\tfrac{9}{2}+o(1))\frac{(\log\log N)^2}{\log N}\] can be so represented.

Liu and Sawhney [LiSa24] observed that the main result of Bloom [Bl21] implies a positive solution to this conjecture. They prove a more precise version, that if $(\log N)^{-1/7+o(1)}\leq \alpha \leq 1/2$ then there is some $S\subseteq A$ such that \[\frac{a}{b}=\sum_{n\in S}\frac{1}{n}\] with $a\leq b \leq \exp(O(1/\alpha))$. They also observe that the dependence $b\leq \exp(O(1/\alpha))$ is sharp.

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}\] and \[\frac{1}{2}+\frac{1}{3}+\frac{1}{7}=1-\frac{1}{42}.\] It is clear that we must have $m=p_1\cdots p_k$, and hence in particular (up to ordering) there is at most one solution for each $m$. The integers $m$ for which there is such a solution are known as primary pseudoperfect numbers, and there are $8$ known, listed in A054377 at the OEIS.

This is true, and shown by Lim and Steinerberger [LiSt24] who proved that there exist infinitely many $n$ such that \[\epsilon(n)n^2\ll \left(\frac{\log\log n}{\log n}\right)^{1/2}.\] Erdős and Graham (and also Lim and Steinerberger) believe that the exponent of $2$ is best possible here, in that $\liminf \epsilon(n) n^{2+\delta}=\infty$ for all $\delta>0$.

$c_0$ is called the Vardi constant and the sequence $u_n$ is Sylvester's sequence.

In [ErGr80] this problem is stated with the sequence $u_1=1$ and $u_{n+1}=u_n(u_n+1)$, but Quanyu Tang has pointed out this is probably an error (since with that choice we do not have $\sum \frac{1}{u_n}=1$). This question with Sylvester's sequence is the most natural interpretation of what they meant to ask.

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 [Sa75] 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}<1.\]

Adenwalla has observed that a lower bound of \[\lvert A\rvert\geq (1-\tfrac{1}{e}+o(1))N\] follows from the main result of Croot [Cr01], which states that there exists some set of integers $B\subset [(\frac{1}{e}-o(1))N,N]$ such that $\sum_{b\in B}\frac{1}{b}=1$. Since the sum of $\frac{1}{m}$ for $m\in [c_1N,c_2N]$ is asymptotic to $\log(c_2/c_1)$ we must have $\lvert B\rvert \geq (1-\tfrac{1}{e}+o(1))N$.

We may then let $A=B\cup\{1\}$ and choose $\delta(n)=-1$ for all $n\in B$ and $\delta(1)=1$.

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$.

Wouter van Doorn has given an elementary argument that proves that if $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert \geq (25/28+o(1))N$ then $A$ must contain $a\neq b$ with $a+b\mid ab$ (see the discussion in [301]).

See also [302].

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 (see [707]).

Asked by Erdős and Nathanson.

Ruzsa has observed that there is a simple counterexample: take $A$ to be the set of numbers whose binary representation has only non-zero digits in even places, and $B$ similarly but with non-zero digits only in odd places. It is easy to see $A$ and $B$ both grow like $\gg N^{1/2}$ and yet for any $n\geq 1$ there is exactly one solution to $n=a+b$ with $a\in A$ and $b\in B$.

Ruzsa suggests that a non-trivial variant of this problem arises if one imposes the stronger condition that \[\lvert A\cap \{1,\ldots,N\}\rvert \sim c_AN^{1/2}\] for some constant $c_A>0$ as $N\to \infty$, and similarly for $B$.

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.

See also [806].

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})}$.

See also Problem 59 on Green's open problems list.

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$).

The answer is no, and a counterexample was provided by Turjányi [Tu84]. This was generalised (to the replacement of $A+A$ by the $h$-fold sumset $hA$ for any $h\geq 2$) by Ruzsa and Turjányi [RT85]. Ruzsa and Turjányi do prove (under the same hypotheses) that \[\lim_{N\to \infty}\frac{\lvert (A+A+A)\cap \{1,\ldots,3N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty,\] and conjecture that the same should be true with $(A+A)\cap \{1,\ldots,2N\}$ in the numerator.

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 conjectured it always has restricted order at most $3$ (which he proved under the additional assumption that the basis has positive lower density). Kelly's conjecture was disproved by Hennecart [He05], who constructed a basis of order $2$ with restricted order $4$.

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?

Hegyvári, Hennecart, and Plagne [HHP07] have shown that for all $k\geq2$ there exists a basis of order $k$ which has restricted order at least \[2^{k-2}+k-1.\]

It is trivial that this sequence grows at least like $\gg N^{1/3}$. Erdős and Graham [ErGr80] also asked about the difference set $A-A$, whether this has positive density, and whether this contains $22$. It does contain $22$, since $a_{15}-a_{14}=204-182=22$. The smallest integer which is unknown to be in $A-A$ is $33$ (see A080200). It may be true that all or almost all integers are in $A-A$.

This sequence is at OEIS A005282.

See also [156].

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.

See also Problem 7 of Green's open problems list.

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].

See also [1].

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 (a construction showing this fails for parallelograms was provided by Kovač) [Ko23].

Kovač and Predojević [KoPr24] have proved that this is true for cyclic quadrilaterals - that is, every set with infinite measure contains four distinct points on a circle such that the quadrilateral determined by these four points has area $1$. They also prove that there exists a set of infinite measure such that every convex polygon with congruent sides and all vertices in the set has area $<1$.

Koizumi [Ko25] has resolved this question, proving that any set with infinite measure must contain the vertices of an isosceles trapezoid, an isosceles triangle, and a right-angled triangle, all of area $1$.

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 was solved by Konieczny [Ko15], see [34]).

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$)?

See also [34] and [357].

Asked by Erdős and Harzheim.

If $g(n)$ is the maximal $k$ such that there are $1\leq a_1,\ldots,a_k\leq n$ with all consecutive sums distinct (i.e. we drop the monotonicity assumption in the definition of $f$) then Hegyvári [He86] has proved that \[\left(\frac{1}{3}+o(1)\right) n\leq g(n)\leq \left(\frac{2}{3}+o(1)\right)n.\]

A similar question can be asked if we replace strict monotonicity with weak monotonicity (i.e. we allow $a_i=a_j$).

Erdős and Harzheim also ask 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$?

See also [34] and [356].

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.

In [ErGr80] this was asked without the 'at least two' restriction, but otherwise the answer is trivially yes, as observed by Egami, since one can take $a_n=n$.

A problem of MacMahon, studied by Andrews [An75]. When $n=1$ this sequence begins \[1,2,4,5,8,10,14,15,\ldots.\] This sequence is A002048 in the OEIS. Andrews conjectures \[a_k\sim \frac{k\log k}{\log\log k}.\]

See also [839].

Alon and Erdős [AlEr96] proved that $f(n) = n^{1/3+o(1)}$, and more precisely \[\frac{n^{1/3}}{(\log n)^{4/3}}\ll f(n) \ll \frac{n^{1/3}}{(\log n)^{1/3}}(\log\log n)^{1/3}.\] Vu [Vu07] improved the lower bound to \[f(n) \gg \frac{n^{1/3}}{\log n}.\] Conlon, Fox, and Pham [CFP21] determined the order of growth of $f(n)$ up to a multiplicative constant, proving \[f(n) \asymp \frac{n^{1/3}(n/\phi(n))}{(\log n)^{1/3}(\log\log n)^{2/3}}.\]

Erdős and Moser proved the first bound with an additional factor of $(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65], thereby answering the first question in the affirmative. 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$.

The second question was answered in the affirmative by Halász [Ha77], as a consequence of a more general multi-dimensional result.

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 always a square.

This is false: Ulas [Ul05] has proved there are infinitely many solutions when $n=4$ or $n\geq 6$ and $\lvert I_i\rvert=4$ for $1\leq i\leq n$. Bauer and Bennett [BaBe07] proved there are infinitely many solutions when $n=3$ or $n=5$ and $\lvert I_i\rvert=4$ for $1\leq i\leq n$. Furthermore, Bennett and Van Luijk [BeVL12] have found infinitely many solutions when $n\geq 5$ and $\lvert I_i\rvert=5$ for $1\leq i\leq n$.

In general, Ulas conjectures there are infinitely many solutions for any fixed size of $\lvert I_i\rvert$, provided $n$ is sufficiently large.

See also [930] for a more general question.

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 [Er76d] believed the answer to this question is no, and in fact if $n_k$ is the $k$th powerful number then \[n_{k+2}-n_k > n_k^c\] for some constant $c>0$.

It is trivial that there are no quadruples of consecutive powerful numbers since one must be $2\pmod{4}$.

By OEIS A060355 there are no such $n$ for $n<10^{22}$.

See also [137], [365], and [938].

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=2^3y^2+1$.

The list of $n$ such that $n$ and $n+1$ are both powerful is A060355 in the OEIS.

The answer to the first question is no: Golomb [Go70] observed that both $12167=23^3$ and $12168=2^33^213^2$ are powerful. Walker [Wa76] proved that the equation \[7^3x^2=3^3y^2+1\] has infinitely many solutions, giving infinitely many counterexamples.

See also [364].

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. Erdős and Graham asked if this is the only pair of such consecutive integers. Stephan has observed that $12167=23^3$ and $12168=2^33^213^2$ (a pair already known to Golomb [Go70]) is another example, but (by OEIS A060355) there are no other examples for $n<10^{22}$.

In [Er76d] Erdős asks the weaker question of whether there are any consecutive pairs of $3$-full 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?\]

Let $F(n)$ be the prime in question. Pólya [Po18] proved that $F(n)\to \infty$ as $n\to\infty$. Mahler [Ma35] showed that $F(n)\gg \log\log n$. Schinzel [Sc67b] observed that for infinitely many $n$ we have $F(n)\leq n^{O(1/\log\log\log n)}$.

The truth is probably $F(n)\gg (\log n)^2$ for all $n$. Erdős [Er76d] conjectured that, for every $\epsilon>0$, there are infinitely many $n$ such that $F(n) <(\log n)^{2+\epsilon}$.

Pasten [Pa24b] has proved that \[F(n) \gg \frac{(\log\log n)^2}{\log\log\log n}.\] The largest prime factors of $n(n+1)$ are listed as A074399 in the OEIS.

Erdős and Graham state that this is open even for $k=2$ and 'the answer should be affirmative but the problem seems very hard'.

Unfortunately the problem is trivially true as written (simply taking $\{1,\ldots,k\}$ and $n>k^{1/\epsilon}$). There are (at least) two possible variants which are non-trivial, and it is not clear which Erdős and Graham meant. Let $P$ be the sequence of $k$ consecutive integers sought for. The potential strengthenings which make this non-trivial are:

• Each $m\in P$ must be $m^\epsilon$-smooth. If this is the problem then the answer is yes, which follows from a result of Balog and Wooley [BaWo98]: for any $\epsilon>0$ and $k\geq 2$ there exist infinitely many $m$ such that $m+1,\ldots,m+k$ are all $m^\epsilon$-smooth.
• Each $m\in P$ must be in $[n/2,n]$ (say). In this case a positive answer also follows from the result of Balog and Wooley [BaWo98] for infinitely many $n$, but the case of all sufficiently large $n$ is open.

See also [370].

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 (since the density of integers $n$ whose greatest prime factor is $\leq n^{1/\sqrt{e}}$ is $1/2$).

Steinerberger has pointed out this problem has a trivial solution: take $n=m^2-1$, and then it is obvious that the largest prime factor of $n$ is $\leq m+1\ll n^{1/2}$ and the largest prime factor of $n+1$ is $\leq m\ll (n+1)^{1/2}$ (these $\ll$ can be replaced by $<$ if we choose $m$ such that $m,m+1$ are both composite).

Given that Erdős and Graham describe the above observation of Pomerance and explicitly say about this problem that 'we know very little about this', it is strange that such a trivial obstruction was overlooked. Perhaps the problem they intended was subtly different, and the problem in this form was the result of a typographical error, but I have no good guess what was intended here.

See also [369].

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

In [Er79e] Erdős also asks whether, for every $\alpha>0$, the density of the set of $n$ where \[P(n+1)>P(n)n^\alpha\] exists.

The sequence of such $n$ is A070089 in the OEIS.

Conjectured by Erdős and Pomerance [ErPo78], who proved the analogous result for $P(n)<P(n+1)<P(n+2)$. Solved 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]). Erdős [Er76d] proved that this problem would also follow from showing that $P(n(n-1))>4\log n$.

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!$.

Surányi was the first to conjecture that the only non-trivial solution to $a!b!=n!$ is $6!7!=10!$.

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$.

Note this is trivial when $k\leq 2$. Originally conjectured by Grimm [Gr69]. This is a very difficult problem, since it in particular implies $p_{n+1}-p_n <p_n^{1/2-c}$ for some constant $c>0$, in particular resolving Legendre's conjecture.

Grimm proved that this is true if $k\ll \log n/\log\log n$. Erdős and Selfridge improved this to $k\leq (1+o(1))\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 odd primes $p$ and $q$, there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $pq$.

The sequence of such $n$ is A030979 in the OEIS.

A question of Erdős, Graham, Ruzsa, and Straus [EGRS75], who proved that if $f(n)$ is the sum in question then \[\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)$. They also prove that, for all large $n$, \[f(n) \leq c\log\log n\] for some constant $c<1$. (It is trivial from Mertens estimates that $f(n)\leq (1+o(1))\log\log n$.)

A positive answer would imply that \[\sum_{p\leq n}1_{p\mid \binom{2n}{n}}\frac{1}{p}=(1-o(1))\log\log n,\] and Erdős, Graham, Ruzsa, and Straus say there is 'no doubt' this latter claim is true.

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].

Erdős [Er44] proved $Q(x)\gg (\log x)^{1+c}$ for some constant $c>0$.

The answer to this problem is no: Nicolas [Ni71] proved that \[Q(x) \ll (\log x)^{O(1)}.\]

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$.

A question of Erdős, Eggleton, and Selfridge, who write that 'plausible conjectures on primes' imply that $F(n)\leq n$ for only finitely many $n$, and in fact it is possible that this quantity is always at least $n+(1-o(1))\sqrt{n}$ (note that it is trivially $\leq n+\sqrt{n}$).

Tao has discussed this problem in a blog post.

Sarosh Adenwalla has observed that the first question is equivalent to [430]. Indeed, if $n$ is large and $a_i$ is the sequence defined in the latter problem, then [430] implies tha there is a composite $a_j$ such that $a_j-p(a_j)>n$ and hence $F(n)>n$.

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$.'

Weisenberg has provided four easy examples that show Erdős and Graham were too optimistic here: \[\binom{7}{3}=5\cdot 7,\] \[\binom{10}{4}= 2\cdot 3\cdot 5\cdot 7,\] \[\binom{14}{4} = 7\cdot 11\cdot 13,\] and \[\binom{15}{6}=5\cdot 7\cdot 11\cdot 13.\]

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].

More generally, if $k_1>2$ then for fixed $a$ and $b$ \[a\prod_{1\leq i\leq k_1}(m_1+i)=b\prod_{1\leq j\leq k_2}(m_2+j)\] should have only a finite number of solutions.

See also [363] and [931].

Asked by Erdős and Straus. For example when $n=2$ we have $k=5$: \[2\times 3 \times 4 \times 5\times 6 \mid 7 \times 8 \times 9\times 10\times 11.\] and when $n=3$ we have $k=4$: \[3\times 4\times 5\times 6 \mid 7\times 8\times 9\times 10.\] Bhavik Mehta has computed the minimal such $k$ for $1\leq n\leq 18$ (now available as A375071 on the OEIS).

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

It is easy to see that \[\lim \frac{t(n)}{n}\leq \frac{1}{e}.\] Erdős [Er96b] wrote he, Selfridge, and Straus had proved a corresponding lower bound, so that $\lim \frac{t(n)}{n}=\frac{1}{e}$, and 'believed that Straus had written up our proof. Unfortunately Straus suddenly died and no trace was ever found of his notes. Furthermore, we never could reconstruct our proof, so our assertion now can be called only a conjecture.'

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$. Similar questions can be asked for other $k\geq 3$.

A reverse Littlewood-Offord problem. Erdős originally asked this with $\sqrt{2}$ replaced by $1$, but Carnielli and Carolino [CaCa11] observed that this is false, choosing $z_1=1$ and $z_k=i$ for $2\leq k\leq n$, where $n$ is even, since then the sum is at least $\sqrt{2}$ always.

Solved in the affirmative by He, Juškevičius, Narayanan, and Spiro [HJNS24]. The bound of $1/n$ is the best possible, as shown by taking $z_k=1$ for $1\leq k\leq n/2$ and $z_k=i$ otherwise.

See also [498].

Erdős and Graham write that $n+1$ always divides $\binom{2n}{n}$ (indeed $\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number), but it is quite rare that $n$ divides $\binom{2n}{n}$.

Pomerance [Po14] has shown that for any $k\geq 0$ there are infinitely many $n$ such that $n-k\mid\binom{2n}{n}$, although the set of such $n$ has upper density $<1/3$. Pomerance also shows that the set of $n$ such that \[\prod_{1\leq i\leq k}(n+i)\mid \binom{2n}{n}\] has density $1$.

The smallest $n$ for each $k$ are listed as A375077 on the OEIS.

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.

There are no other solutions below $10^9$ (see the OEIS page).

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

Jonas Barfield has found the solution \[10! = 48^4 - 36^4=12^4\cdot 175.\]

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) the only cases where equality is 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$).

Erdős and Graham ask this allowing the case $p=2$, but this is presumably an oversight, since clearly there are infinitely many solutions to this equation when $p=2$.

Brindza and Erdős [BrEr91] proved that are finitely many such solutions. Yu and Liu [YuLi96] showed that the only solutions are \[2!+1^2=3\] \[2!+5^2=3^3\] and \[4!+1^4=5^2.\]

The only examples seem to be $1$, $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$.

This would imply via Kummer's theorem that \[3\mid \binom{2^{k+1}}{2^k}\] for all large $k$.

Saye [Sa22] has computed that $2^n$ contains every possible ternary digit for $16\leq n \leq 5.9\times 10^{21}$.

A conjecture originally due to Newman.

This is true, and was proved by Evertse, Györy, Stewart, and Tijdeman [EGST88].

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 $\phi_k(n)$ is $\leq n^{o(1)}$.

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

The number of iterations required is A039651 in the OEIS.

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$.

In [Er79d] Erdős attributes this conjecture to van Wijngaarden, who told it to Erdős in the 1950s.

That is, there is (eventually) only one possible sequence that the iterated sum of divisors function can settle on. Selfridge reports numerical evidence which 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].

In [Er79] Erdős calls such an $n$ a 'barrier' for $\omega$. Some other natural number theoretic functions (such as $\phi$ and $\sigma$) have no barriers because they increase too rapidly. Erdős believed that $\omega$ should have infinitely many barriers. In [Er79d] he proves that $F(n)=\prod k_i$, where $n=\prod p_i^{k_i}$, has infinitely many barriers (in fact the set of barriers has positive density in the integers).

Erdős also believed that $\Omega$, the count of the number of prime factors with multiplicity), should have infinitely many barriers. Selfridge found the largest barrier for $\Omega$ which is $<10^5$ is $99840$.

In [ErGr80] this problem is suggested as a way of showing that the iterated behaviour of $n\mapsto n+\omega(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'.

See also [647] and [679].

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.

Weisenberg has observed that the same questions could be asked for ordering patterns which allow equality (indeed, the final problem only makes sense if we allow equality).

Pillai [Pi29] proved $V(x)=o(x)$. Erdős [Er35b] proved $V(x)=x(\log x)^{-1+o(1)}$.

The behaviour of $V(x)$ is now almost completely understood. Maier and Pomerance [MaPo88] proved \[V(x)=\frac{x}{\log x}e^{(C+o(1))(\log\log\log x)^2},\] 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$.

In [Er79e] Erdős asks further to estimate the number of $n\leq x$ such that the smallest solution to $\phi(m)=n$ satisfies $kx<m\leq (k+1)x$.

See also [417] and [821].

It is trivial that $V'(x) \leq V(x)$. In [Er98] Erdős suggests the limit may be infinite. 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$.

This is true, as shown by Browkin and Schinzel [BrSc95], who show that any integer of the shape $2^{k}\cdot 509203$ is not of this form. It seems to be open whether there is a positive density set of integers not of this form.

Erdős and Graham noted that any number of the shape $1+1/k$ for $k\geq 1$ is a limit point (and thus so too is $1$), but knew of no others.

Mehtaab Sawhney has shared the following simple argument that proves that the above limit points are in fact the only ones.

If $v_p(m)$ is the largest $k$ such that $p^k\mid m$ then $\tau(m)=\prod_p (v_p(m)+1)$ and so \[\frac{\tau((n+1)!)}{\tau(n!)} = \prod_{p|n+1}\left(1+\frac{v_p(n+1)}{v_p(n!)+1}\right).\] Note that $v_p(n!)\geq n/p$, and furthermore $n+1$ has $<\log n$ prime divisors, each of which satisfy $v_p(n+1)<\log n$. It follows that the contribution from $p\leq n^{2/3}$ is at most \[\left(1+\frac{\log n}{n^{1/3}}\right)^{\log n}\leq 1+o(1).\]

There is at most one $p\mid n+1$ with $p\geq n^{2/3}$ which (if present) contributes exactly \[\left(1+\frac{1}{\frac{n+1}{p}}\right).\] We have proved the claim, since these two facts combined show that the ratio in question is either $1+o(1)$ or $1+1/k+o(1)$, the latter occurring if $n+1=pk$ for some $p>n^{2/3}$.

After receiving Sawhney's argument I found that this had already been proved, with essentially the same argument, by Erdős, Graham, Ivić, and Pomerance [EGIP].

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. This problem is also discussed in section E31 of Guy's book Unsolved Problems in Number Theory.

In [ErGr80] (and in Guy's book) this problem as written is asking for whether almost all integers appear in this sequence, but the answer to this is trivially no (as pointed out to me by Steinerberger): no integer $\equiv 1\pmod{3}$ is ever in the sequence, so the set of integers which appear has density at most $2/3$. This is easily seen by induction, and the fact that if $a,b\in \{0,2\}\pmod{3}$ then $ab-1\in \{0,2\}\pmod{3}$.

Presumably it is the weaker question of whether a positive density of integers appear (as correctly asked in [Er77c]) that was also intended in [ErGr80].

See also Problem 63 of Green's open problems list.

Erdős [Er68] proved that there exist some constants $0<c_1\leq c_2$ such that \[\pi(n)+c_1 n^{3/4}(\log n)^{-3/2}\leq F(n)\leq \pi(n)+c_2 n^{3/4}(\log n)^{-3/2}.\] Surprisingly, if we consider the corresponding problem in the reals (so consider the largest $A\subset [1,x]$ such that for any distinct $a,b,c,d\in A$ we have $\lvert ab-cd\rvert \geq 1$) then Alexander proved that $\lvert A\rvert> x/8e$ is possible (disproving an earlier conjecture of Erdős [Er73] that $m=o(x)$). Alexander's construction seems to be unpublished, and I have no idea what it is.

See also [490], [793], and [796].

Cedric Pilatte has observed that a positive solution to this follows from a result of Shiu [Sh00]: for any $k\geq 1$ and $(a,q)=1$ there exist infinitely many $k$-tuples of consecutive primes $p_m,\ldots,p_{m+{k-1}}$ all of which are congruent to $a$ modulo $q$.

Indeed, we apply this with $k=q=d$ and $a=1$ and let $p_m,\ldots,p_{m+{d-1}}$ be consecutive primes all congruent to $1$ modulo $d$, with $m>n+1$. If $p_{n+1}+\cdots+p_{m-1}\equiv r\pmod{d}$ with $1\leq r\leq d$ then \[d \mid p_{n+1}+\cdots +p_m+\cdots+p_{m+d+r-1}.\]

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

Weisenberg [We24] has shown the answer is no: $A$ can be arbitrarily sparse and missing at least one residue class modulo every prime $p$, and yet $A+n$ is not contained in the primes for any $n\in \mathbb{Z}$. (Weisenberg gives several constructions of such an $A$.)

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.

Sarosh Adenwalla has observed that this problem is equivalent to (the first part of) [385]. Indeed, assuming a positive answer to that, for all large $n$, there exists a composite $m<n$ such that all primes dividing $m$ are $>n-m$. It follows that such an $m$ is equal to some $a_i$ in the sequence defined for $[1,n)$, and $m$ is composite by assumption.

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$.

The problem is written as Erdős and Graham describe it, but presumably they had in mind the regime where $n$ is fixed and $t\to \infty$.

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$.

Erdős and Graham write it is 'trivial' that there are $o(x)$ many such squares, although this is not quite trivial, using Siegel's theorem.

A positive answer follows from work of Bui, Pratt, and Zaharescu [BPZ24], as noted by Tao in this blog post. In particular Tao shows that, if $L(x)$ is the maximal number of such squares possible, and $u(x)=(\log x\log\log x)^{1/2}$, then \[x\exp(-(2^{1/2}+o(1))u(x)) \leq L(x) \leq x\exp(-(2^{-1/2}+o(1))u(x)).\]

See also [841].

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$.

See also [439] and [587].

A question of Roth, Erdős, Sárközy, and Sós [ESS89] (according to some reports, although in [Er80c] Erdős claims this arose in a conversation with Silverman in 1977). Erdős, Sárközy, and Sós [ESS89] proved this for $2$ or $3$ colours.

In other words, if $G$ is the infinite graph on $\mathbb{N}$ where we connect $m,n$ by an edge if and only if $n+m$ is a square, then is the chromatic number of $G$ equal to $\aleph_0$?

This is true, as proved by Khalfalah and Szemerédi [KhSz06], who in fact prove the general result with $x+y=z^2$ replaced by $x+y=f(z)$ for any non-constant $f(z)\in \mathbb{Z}[z]$ such that $2\mid f(z)$ for some $z\in \mathbb{Z}$.

See also [438].

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

Let $g(N)$ denote the size of the largest such $A$. The construction mentioned proves that \[g(N) \geq \left(\tfrac{9}{8}n\right)^{1/2}+O(1).\] Erdős [Er51b] proved $g(N) \leq (4n)^{1/2}+O(1)$, which was improved by Choi [Ch72b]. Chen [Ch98] established the asymptotic \[g(N) \sim \left(\tfrac{9}{8}n\right)^{1/2}.\] Chen and Dai [DaCh06] proved that \[g(N)\leq \left(\tfrac{9}{8}n\right)^{1/2}+O\left(\left(\frac{N}{\log N}\right)^{1/2}\log\log N\right).\] In [ChDa07] the same authors prove that, infinitely often, Erdős' construction is not optimal: if $B$ is that construction and $A$ is such that $\lvert A\rvert=g(N)$ then, for infinitely many $N$, \[\lvert A\rvert\geq \lvert B\rvert+t,\] where $t\geq 0$ is defined such that the $t$-fold iterated logarithm of $N$ is in $[0,1)$.

Tao [Ta24b] has shown this is false: there exists $A\subset\mathbb{N}$ such that \[\sum_{n\in A\cap [1,x)}\frac{1}{n}\gg \exp((\tfrac{1}{2}+o(1))\sqrt{\log\log x}\log\log\log x)\] and \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\ll 1.\] Moreover, Tao shows this is the best possible result, in that if $\sum_{n\in A\cap [1,x)}\frac{1}{n}$ grows faster than $\exp(O(\sqrt{\log\log x}\log\log\log x))$ then \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\to \infty.\]

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$.

Besicovitch [Be34] proved that $\liminf \delta(n)=0$. Erdős [Er35] proved that $\delta(n)=o(1)$. Erdős [Er60] proved that $\delta(n)=(\log n)^{-\alpha+o(1)}$ where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\] This estimate was refined by Tenenbaum [Te84], and the true growth rate of $\delta(n)$ was determined by Ford [Fo08] who proved \[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}}.\]

Among many other results in [Fo08], Ford also proves that the second conjecture is false, and more generally that if $\delta_r(n)$ is the density of integers with exactly $r$ divisors in $(n,2n)$ then $\delta_r(n)\gg_r\delta(n)$.

See also [448], [692], and [693].

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}.\]

This is false, and was disproved by Erdős and Tenenbaum [ErTe81], who showed that in fact the upper density of the set of such $n$ is $\asymp \epsilon^{1-o(1)}$ (where the $o(1)$ in the exponent $\to 0$ as $\epsilon \to 0$).

A more precise result was proved by Hall and Tenenbaum [HaTe88] (see Section 4.6), who showed that the upper density is $\ll\epsilon \log(2/\epsilon)$. Hall and Tenenbaum further prove that $\tau^+(n)/\tau(n)$ has a distribution function.

Erdős and Graham also asked whether there is a good inequality known for $\sum_{n\leq x}\tau^+(n)$. This was provided by Ford [Fo08] who proved \[\sum_{n\leq x}\tau^+(n)\asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}}\] where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]

See also [446] and [449].

This is false - indeed, for any constant $K>0$ we have $r(n)>K\tau(n)$ for a positive density set of $n$. Kevin Ford has observed this follows from the negative solution to [448]: the Cauchy-Schwarz inequality implies \[r(n)+\tau(n)\geq \tau(n)^2/\tau^+(n)\] where $\tau^+(n)$ is as defined in [448], and the negative solution to [448] implies the right-hand side is at least $(K+1)\tau(n)$ for a positive density set of $n$. (This argument is given for an essentially identical problem by Hall and Tenenbaum [HaTe88], Section 4.6.)

See also [448].

It is not clear what the intended quantifier on $x$ is. Cambie has observed that if this is intended to hold for all $x$ then, provided \[\epsilon(\log n)^\delta (\log\log n)^{3/2}\to \infty\] as $n\to \infty$, where $\delta=0.086\cdots$, there is no such $y$, which follows from an averaging argument and the work of Ford [Fo08].

On the other hand, Cambie has observed that if $\epsilon\ll 1/n$ then $y(\epsilon,n)\sim 2n$: indeed, if $y<2n$ then this is impossible taking $x+n$ to be a multiple of the lowest common multiple of $\{n+1,\ldots,2n-1\}$. On the other hand, for every fixed $\delta\in (0,1)$ and $n$ large every $2(1+\delta)n$ consecutive elements contains many elements which are a multiple of an element in $(n,2n)$.

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

In [Er79d] Erdős writes that probably $n_k<e^{o(k)}$ but $n_k>k^d$ for all constant $d$.

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}>0.352\cdots.\]

Linnik's theorem implies that $p_n\leq n^{O(1)}$. Erdős [Er79e] writes it is 'easy to show' that for infinitely many $n$ we have $p_n <m_n$.

A problem of Erdős and Pomerance.

More generally, let $q(n,k)$ denote the least prime which does not divide $\prod_{1\leq i\leq k}(n+i)$. This problem asks whether $q(n,\log n)\geq (2+\epsilon)\log n$ infinitely often. Taking $n$ to be the product of primes between $\log n$ and $(2+o(1))\log n$ gives an example where \[q(n,\log n)\geq (2+o(1))\log n.\]

Can one prove that $q(n,\log n)<(1-\epsilon)(\log n)^2$ for all large $n$ and some $\epsilon>0$?

See also [663].

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}.\]

Solved independently by de Mathan [dM80] and Pollington [Po79b], who showed that, given any such $A$, there exists such a $\theta$, with \[\inf_{k\geq 1}\| \theta n_k\| \gg \frac{\epsilon^4}{\log(1/\epsilon)}.\] This bound was improved by Katznelson [Ka01], Akhunzhanov and Moshchevitin [AkMo04], and Dubickas [Du06], before Peres and Schlag [PeSc10] improved it to \[\inf_{k\geq 1}\| \theta n_k\| \gg \frac{\epsilon}{\log(1/\epsilon)},\] and note that the best bound possible here would be $\gg \epsilon$.

This problem has consequences for [894].

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}.\]

Konyagin [Ko01] proved the strong upper bound \[N(X,\delta) \ll_\delta N^{1/2}.\]

See also [466] for lower bounds.

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] for upper bounds.

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 integers in $A$ are also known as primitive pseudoperfect numbers and are listed as A006036 in the OEIS.

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 (which are listed as A119425 in the OEIS).

Benkoski and Erdős [BeEr74] ask about these two sets, and also about the set of $n$ that have a divisor expressible as a distinct sum of other divisors of $n$, but where no proper divisor of $n$ has this property.

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

Melfi [Me15] has proved that there are infinitely many primitive weird numbers, conditional on the fact that $p_{n+1}-p_n<\frac{1}{10}p_n^{1/2}$ for all large $n$, which in turn would follow from well-known conjectures concerning prime gaps.

The sequence of weird numbers is A006037 in the OEIS. Fang [Fa22] has shown there are no odd weird numbers below $10^{21}$, and Liddy and Riedl [LiRi18] have shown that an odd weird number must have at least 6 prime divisors.

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

Mrazović and Kovač, and independently Alon, have observed that the existence of some valid choice of $Q$ follows easily from Vinogradov's theorem that every large odd integer is the sum of three distinct primes. In particular, there exists some $N$ such that every prime $>N$ is the sum of three distinct (smaller) primes. We may then take $Q_0$ to be the set of all primes $\leq N$ (in which case all primes are eventually in some $Q_i$).

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?

A problem of Graham, who proved it when $t=p-1$. A similar conjecture was made for arbitrary abelian groups by Alspach. Such an ordering is often called a valid ordering.

This has been proved for $t\leq 12$ (see Costa and Pellegrini [CoPe20] and the references therein) and for $p-3\leq t\leq p-1$ (see Hicks, Ollis, and Schmitt [HOS19] and the references therein). Kravitz [Kr24] has proved this for \[t \leq \frac{\log p}{\log\log p}.\] (This was independently earlier observed by Will Sawin in a MathOverflow post.)

Bedert and Kravitz [BeKr24] have now proved this conjecture for \[t \leq e^{(\log p)^{1/4}}.\]

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$.

The minimal such $n$ for each $k$ is A036236 in the OEIS.

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 original formulation of this problem had an extra condition on the minimal element of the sequence $A_k$ being large, but Ryan Alweiss has pointed out that is trivially always satisfied since the minimal element of the sequence must grow by at least $1$ at each stage.

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].