Erdős called this 'perhaps my first serious problem'. The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $[0,Nn)$. Erdős and Moser [Er56] proved \[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\] (In [Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)

A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu [DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In [Er73] and [ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound. (The second proof of [DFX21] applies also to this generalisation.)

This problem appears in Erdős' book with Spencer [ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in [Ru99] "it is a rich kitchen where such things go to the sink".

The sequence of minimal $N$ for a given $n$ is A276661 in the OEIS.

See also [350].

Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown (contrary to Erdős' expectations) that the answer is no: the smallest modulus must be at most $10^{18}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the bound on the smallest modulus to $616000$.

The peculiar quantitative form of Erdős' question was motivated by an old result of Rankin [Ra38], who proved there exists some constant $C>0$ such that the claim holds. Solved by Maynard [Ma16] and Ford, Green, Konyagin, and Tao [FGKT16]. The best bound available, due to all five authors [FGKMT18], is that there are infinitely many $n$ such that \[p_{n+1}-p_n\gg \frac{\log\log n\log\log\log\log n}{\log\log \log n}\log n.\] The likely truth is a lower bound like $\gg(\log n)^2$. In [Er97c] Erdős revised the value of this problem to \$5000 and reserved the \$10000 for a lower bound of $>(\log n)^{1+c}$ for some $c>0$.

See also [687].

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.

Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'. (In [Er85c] he goes further and offers 'all the money I can earn, beg, borrow or steal for [a disproof]'.)

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

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 Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$.

Another stronger conjecture would be that the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.

Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.

See also [40].

A problem of Erdős and Turán. It may even be true that $h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Both proofs in fact give \[h(N) \leq N^{1/2}+N^{1/4}+1.\] Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to $0.998N^{1/4}$, which has been further optimised by O'Bryant [OB22] to yield \[h(N)\leq N^{1/2}+0.99703N^{1/4}\] for sufficiently large $N$.

See also [241] and [840].

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

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

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

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

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

The Erdős discrepancy problem. This is true, and was proved by Tao [Ta16], who also proved the more general case when $f$ takes values on the unit sphere.

In [Er81] it is further conjectured that \[\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.\]

In [Er85c] Erdős also asks about the special case when $f$ is multiplicative.

Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. Erdős proved \[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\] The upper bound has been improved to $4-\tfrac{1}{128}$ by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23].

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

A $\sqrt{n}\times\sqrt{n}$ integer grid shows that this would be the best possible. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances.

A stronger form (see [604]) may be true: is there a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even $\gg n$ many such points, or even that this is true averaged over all points.

See also [661].

The unit distance problem. In [Er94b] Erdős dates this conjecture to 1946.

This would be the best possible, as is shown by a set of lattice points. It is easy to show that there are $O(n^{3/2})$ many such pairs. The best known upper bound is $O(n^{4/3})$, due to Spencer, Szemerédi, and Trotter [SST84]. In [Er83c] and [Er85] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.

Part of the difficulty of this problem is explained by a result of Valtr (see [Sz16]), who constructed a metric on $\mathbb{R}^2$ and a set of $n$ points with $\gg n^{4/3}$ unit distance pairs (with respect to this metric). The methods of the upper bound proof of Spencer, Szemerédi, and Trotter [SST84] generalise to include this metric. Therefore to prove an upper bound better than $n^{4/3}$ some special feature of the Euclidean metric must be exploited.

See a survey by Szemerédi [Sz16] for further background and related results.

See also [92], [96], and [605].

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

Erdős originally conjectured this with no $3$ vertices equidistant, but Danzer found a convex polygon on 9 points such that every vertex has three vertices equidistant from it (but this distance depends on the vertex), and Fishburn and Reeds [FiRe92] have found a convex polygon on 20 points such that every vertex has three vertices equidistant from it (and this distance is the same for all vertices).

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

Erdős suggested this as an approach to solve [96]. Indeed, if this problem holds for $k+1$ vertices then, by induction, this implies an upper bound of $kn$ for [96].

The answer is no if we omit the requirement that the polygon is convex (I thank Boris Alexeev and Dustin Mixon for pointing this out), since for any $d$ there are graphs with minimum degree $d$ which can be embedded in the plane such that each edge has length one (for example one can take the $d$-dimensional hypercube graph on $2^d$ vertices). One can then connect the vertices in a cyclic order so that there are no self-intersections and no three consecutive vertices on a line, thus forming a (non-convex) polygon.

The Erdős-Klein-Szekeres 'Happy Ending' problem. The problem originated in 1931 when Klein observed that $f(4)=5$. Turán and Makai showed $f(5)=9$. Erdős and Szekeres proved the bounds \[2^{n-2}+1\leq f(n)\leq \binom{2n-4}{n-2}+1.\] ([ErSz60] and [ErSz35] respectively). There were several improvements of the upper bound, but all of the form $4^{(1+o(1))n}$, until Suk [Su17] proved \[f(n) \leq 2^{(1+o(1))n}.\] The current best bound is due to Holmsen, Mojarrad, Pach, and Tardos [HMPT20], who prove \[f(n) \leq 2^{n+O(\sqrt{n\log n})}.\]

In [Er97e] Erdős clarifies that the \$500 is for a proof, and only offers \$100 for a disproof.

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

See also [216], [651], and [838].

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 [ErHePi58]. The lower bound $\mu(A) \gg n^{-4}$ follows from a result of Pommerenke [Po61]. The stronger lower bound $\gg (\log n)^{-O(1)}$ is still open.

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

The weaker conjecture that $\limsup M_n=\infty$ was proved by Wagner, who show that there is some $c>0$ with $M_n>(\log n)^c$ infinitely often.

This was solved by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\]

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

Proved by Szemerédi [Sz74]. The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$ (with further slight improvements in [BlSi23]), Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$.

See also [3].

Note that if $A$ is a set of integers then the condition implies that $A$ is a primitive set (that is, no element of $A$ is divisible by any other), for which the convergence of $\sum_{n\in A}\frac{1}{n\log n}$ was proved by Erdős [Er35], and the upper bound \[\sum_{n<x}\frac{1}{n}\ll \frac{\log x}{\sqrt{\log\log x}}\] was proved by Behrend [Be35].

In [Er73] mentions an unpublished proof of Haight that \[\lim \frac{\lvert A\cap [1,x]\rvert}{x}=0\] holds if the elements of $A$ are independent over $\mathbb{Q}$.

See also [858].

In [Er79] asks the stronger version with $2$ replaced by any constant $c>1$.

The answer is yes (also to this stronger version), proved by Maier and Tenenbaum [MaTe84]. (Tenenbaum has told me that they received \$650 for their solution.)

See also [449].

It is known that there exists some constant $c>0$ such that for large $k$ \[c\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log k}.\] The lower bound is due to Kim [Ki95], the upper bound is due to Shearer [Sh83], improving an earlier bound of Ajtai, Komlós, and Szemerédi [AjKoSz80]. The lower bound has been improved to \[\left(\frac{1}{4}-o(1)\right)\frac{k^2}{\log k}\] independently by Bohman and Keevash [BoKe21] and Pontiveros, Griffiths and Morris [PGM20]. The latter collection of authors conjecture that this lower bound is the true order of magnitude.

See also [544].

Erdős offers \$100 for showing that this limit is finite. An easy pigeonhole argument shows that \[R(3;k)\leq 2+k(R(3;k-1)-1),\] from which $R(3;k)\leq \lceil e k!\rceil$ immediately follows. The best-known upper bounds are all of the form $ck!+O(1)$, and arise from this type of inductive relationship and computational bounds for $R(3;k)$ for small $k$. The best-known lower bound (coming from lower bounds for Schur numbers) is due to Exoo [Ex94], \[R(3;k) \gg (321)^{k/5}.\]

See also [483].

See also the entry in the graphs problem collection.

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.

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

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

In [Er85c] Erdős also conjectures that $d_n=d_{n+1}=\cdots=d_{n+k}$ is solvable for every $k$.

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

The answer is yes, as proved by Montgomery and Vaughan [MoVa86], who in fact found the correct order of magnitude with the power $2$ replaced by any $\gamma\geq 1$ (which was also asked by Erdős in [Er73]).

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.

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

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.

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

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

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.

Originally asked to Erdős by Bose. Bose and Chowla [BoCh62] provided a construction proving one half of this, namely \[(1+o(1))N^{1/3}\leq f(N).\] The best upper bound known to date is due to Green [Gr01], \[f(N) \leq ((7/2)^{1/3}+o(1))N^{1/3}\] (note that $(7/2)^{1/3}\approx 1.519\cdots$).

More generally, Bose and Chowla conjectured that the maximum size of $A\subseteq \{1,\ldots,N\}$ with all $r$-fold sums distinct (aside from the trivial coincidences) then \[\lvert A\rvert \sim N^{1/r}.\] This is known only for $r=2$ (see [30]).

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

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

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

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

Proved by Birch [Bi59].

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

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

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

See also [521] and [522].

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

A conjecture of Roth.

Solved by Erdős, Sárközy, and Sós [ESS89], who in fact prove that there are at least \[\frac{N}{2}-O(N^{1-1/2^{k+1}})\] many even numbers which are of this form. They also prove that if $k=2$ then there are at least \[\frac{N}{2}-O(\log N)\] many even numbers which are of this form, and that $O(\log N)$ is best possible, since there is a $2$-colouring such that no power of $2$ is representable as a monochromatic sum.

A refinement of this problem appears as Problem 25 on the open problems list of Ben Green.

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

This was solved by Schinzel [Sc87], who proved that \[f(k) > \frac{\log\log k}{\log 2}.\] In fact Schinzel proves lower bounds for the corresponding problem with $P(x)^n$ for any integer $n\geq 1$, where the coefficients of the polynomial can be from any field with zero or sufficiently large positive characteristic.

Schinzel and Zannier [ScZa09] have improved this to \[f(k) \gg \log k.\]

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

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

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

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

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

See also [208].

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

See also [425].

This is true, and was proved by Szemerédi [Sz76].

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

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

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

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

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

Erdős attributes this question to Schinzel. Eli Seamans has observed that the answer is yes (with $k=2$) for a very simple reason: \[n = 2(n+2)-(2+(n+2)).\] There may well have been some additional constraint in the problem as Schinzel posed it, but [Er61] does not record what this is.

A problem of Selfridge and Straus [SeSt58], who prove that this is true if $k=2$ and $\lvert A\rvert \neq 2^l$ (for $l\geq 0$). On the other hand, there are examples with two distinct $A,B$ both of size $2^l$ such that $A_2=B_2$.

More generally, they prove that $A$ is uniquely determined by $A_k$ if $n$ is divisible by a prime greater than $k$. Selfridge and Straus sound more cautious than Erdős, and it may well be that for all $k>2$ there exist $A,B$ of the same size with identical $A_k=B_k$.

(In [Er61] Erdős states this problem incorrectly, replacing sums with products. This product formulation is easily seen to be false, as observed by Steinerberger: consider the case $k=3$ and subsets of the 6th roots of unity corresponding to $\{0,1,2,4\}$ and $\{0,2,3,4\}$ (as subsets of $\mathbb{Z}/6\mathbb{Z}$). The correct problem statement can be found in the paper of Selfridge and Straus that Erdős cites.)

The infamous Littlewood conjecture.

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

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

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

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

A strong form of the Littlewood-Offord problem. Erdős [Er45] proved this is true if $z_i\in\mathbb{R}$, and for general $z_i\in\mathbb{C}$ proved a weaker upper bound of \[\ll \frac{2^n}{\sqrt{n}}.\] This was solved in the affirmative by Kleitman [Kl65], who also later generalised this to arbitrary Hilbert spaces [Kl70].

See also [395].

A weaker form of the conjecture of van der Waerden, which states that \[\mathrm{perm}(M)=\sum_{\sigma\in S_n}\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}n!\] with equality if and only if $a_{ij}=1/n$ for all $i,j$.

This conjecture is true, and was proved by Marcus and Minc [MaMi62].

Erdős also conjectured the even weaker fact that there exists some $\sigma\in S_n$ such that $a_{i\sigma(i)}\neq 0$ for all $i$ and \[\sum_{i}a_{i\sigma(i)}\geq 1.\] This weaker statement was proved by Marcus and Ree [MaRe59].

van der Waerden's conjecture itself was proved by Gyires [Gy80], Egorychev [Eg81], and Falikman [Fa81].

A problem of Turán. Turán observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that \[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\] This is probably the truth. The current best upper bound is \[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\] due to Razborov [Ra10].

See also [712] for the general case.

Erdős and Hajnal [ErHa60] proved the existence of arbitrarily large finite independent sets (under the assumptions in the first problem).

Erdős writes in [Er61] that Gladysz has proved the existence of an independent set of size $2$ in the second question, but I cannot find a reference.

Hechler [He72] has shown the answer to the first question is no, assuming the continuum hypothesis.

Asked to Erdős by Coxeter. Erdős thought he could show that $\lvert A\rvert \leq n^{O(1)}$, but later discovered a mistake in his proof, and his proof only gave $\leq \exp(n^{1-o(1)})$.

Bannai, Bannai, and Stanton [BBS83] have proved that \[\lvert A\rvert \leq \binom{n+2}{2}.\] A simple proof of this upper bound was given by Petrov and Pohoata [PePo21].

Shengtong Zhang has observed that a simple lower bound of $\binom{n}{2}$ is given by considering all points with exactly two coordinates equal to $1$ and all others equal to $0$.

When $n=2$ the answer is $6$ (due to Kelly [ErKe47]). When $n=3$ the answer is $8$ (due to Croft [Cr62]). The best upper bound known in general is due to Blokhuis [Bl84] who showed that \[\lvert A\rvert \leq \binom{n+2}{2}.\]

Alweiss has observed a lower bound of $\binom{n+1}{2}$ follows from considering the subset of $\mathbb{R}^{n+1}$ formed of all vectors $e_i+e_j$ where $e_i,e_j$ are distinct coordinate vectors. This set can be viewed as a subset of some $\mathbb{R}^n$, and is easily checked to have the required property.

The fact that the truth for $n=3$ is $8$ suggests that neither of these bounds is the truth.

Blumenthal's problem. Szekeres [Sz41] showed that \[\alpha_{2^n+1}> \pi \left(1-\frac{1}{n}+\frac{1}{n(2^n+1)^2}\right)\] and \[\alpha_{2^n}\leq \pi\left(1-\frac{1}{n}\right).\] Erdős and Szekeres [ErSz60] showed that \[\alpha_{2^n}=\alpha_{2^n-1}= \pi\left(1-\frac{1}{n}\right),\] and suggested that perhaps $\alpha_{N}=\pi(1-1/n)$ for $2^{n-1}<N\leq 2^n$. This was disproved by Sendov [Se92].

Sendov [Se93] provided the definitive answer, proving that $\alpha_N=\pi(1-1/n)$ for $2^{n-1}+2^{n-3}<N\leq 2^n$ and $\alpha_N=\pi(1-\frac{1}{2n-1})$ for $2^{n-1}<N\leq 2^{n-1}+2^{n-3}$.

Borsuk's problem. This is trivially true for $n=1$ and easy for $n=2$. For $n=3$ it is true, which was proved by Eggleston [Eg55].

The answer is in fact no in general, as shown by Kahn and Kalai [KaKa93], who proved that it is false for $n>2014$. The current smallest $n$ where Borsuk's conjecture is known to be false is $n=64$, a result of Brouwer and Jenrich [BrJe14].

If $\alpha(n)$ is the smallest number of pieces of diameter $<1$ required (so Borsuk's original conjecture was that $\alpha(n)=n+1$) then Kahn and Kalai's construction shows that $\alpha(n)\geq (1.2)^{\sqrt{n}}$. The best upper bound, due to Schramm [Sc88], is that \[\alpha(n) \leq ((3/2)^{1/2}+o(1))^{n}.\]

There is clearly some non-degeneracy condition intended here - probably either that not all the points are on a line, or the stronger condition that no three points are on a line.

See also [104] and [831].

Heilbronn's triangle problem. It is trivial that $\alpha(n) \ll 1/n$. Erdős observed that $\alpha(n)\gg 1/n^2$. The current best bounds are \[\frac{\log n}{n^2}\ll \alpha(n) \ll \frac{1}{n^{8/7+1/2000}}.\] The lower bound is due to Komlós, Pintz, and Szemerédi [KPS82]. The upper bound is due to Cohen, Pohoata, and Zakharov [CPZ23] (improving on an exponent of $8/7$ due to Komlós, Pintz, and Szemerédi [KPS81]).

The Hadwiger-Nelson problem. Let $\chi$ be the chromatic number of the plane. An equilateral triangle trivially shows that $\chi\geq 3$. There are several small graphs that show $\chi\geq 4$ (in particular the Moser spindle and Golomb graph). The best bounds currently known are \[5 \leq \chi \leq 7.\] The lower bound is due to de Grey [dG18]. The upper bound can be seen by colouring the plane by tesselating by hexagons with diameter slightly less than $1$.

See also [704], [705], and [706].

Cartan proved this is true with $2$ replaced by $2e$, which was improved to $2.59$ by Pommerenke [Po61]. Pommerenke [Po59] proved that $2$ is achievable if the set is connected (in fact the entire set is covered by a single circle with radius $2$).

Chowla's cosine problem. The best known bound currently, due to Ruzsa [Ru04] (improving on an earlier result of Bourgain [Bo86]), replaces $N^{1/2}$ by \[\exp(O(\sqrt{\log N}).\] The example $A=B-B$, where $B$ is a Sidon set, shows that $N^{1/2}$ would be the best possible here.

Littlewood's conjecture, proved independently by Konyagin [Ko81] and McGehee, Pigno, and Smith [MPS81].

It is trivial that this value is in $[1/2,1)$. Kövári (unpublished) observed that it must be $>1/2$. Clunie and Hayman [ClHa64] showed that it is $\leq 2/\pi-c$ for some absolute constant $c>0$. Some other results on this quantity were established by Gray and Shah [GrSh63].

See also [227].

Boas (unpublished) has proved the first part, that such a path must exist.

Huber [Hu57] proved that for every $\lambda>0$ there is a path $C_\lambda$ such that this integral is finite.

A problem of Pólya. Results of Wiman [Wi14] imply that if $(n_{k+1}-n_k)^2>n_k$ then $\limsup \frac{m(r)}{M(r)}=1$. Erdős and Macintyre [ErMa54] proved this under the assumption that \[\sum_{k\geq 2}\frac{1}{n_{k+1}-n_k}<\infty.\]

A conjecture of Fejér and Pólya. Fejér [Fe08] proved that if $\sum\frac{1}{n_k}<\infty$ then $f(z)$ assumes every value at least once, and Biernacki [Bi28] showed that this holds under the assumption that $n_k/k\to \infty$.

A problem of Turán, who proved that this maximum is $\gg 1/n$. This was solved by Atkinson [At61b], who showed that $c=1/6$ suffices. This has been improved by Biró, first to $c=1/2$ [Bi94], and later to an absolute constant $c>1/2$ [Bi00]. Based on computational evidence it is likely that the optimal value of $c$ is $\approx 0.7$.

Note that if we drop the multiplicative assumption, and simply assign $f(m)=\pm 1$ at random, then this statement is true (with $c=\sqrt{2}$), the law of the iterated logarithm.

Wintner [Wi44] proved that, almost surely, \[\sum_{m\leq N}f(m)\ll N^{1/2+o(1)},\] and Erdős improved the right-hand side to $N^{1/2}(\log N)^{O(1)}$. Lau, Tenenbaum, and Wu [LTW13] have shown that, almost surely, \[\sum_{m\leq N}f(m)\ll N^{1/2}(\log\log N)^{2+o(1)}.\] Harper [Ha13] has shown that the sum is almost surely not $O(N^{1/2}/(\log\log N)^{5/2+o(1)})$, and conjectured that in fact Erdős' conjecture is false, and almost surely \[\sum_{m\leq N}f(m) \ll N^{1/2}(\log\log N)^{1/4+o(1)}.\] This was proved by Caich [Ca23].

Erdős and Offord [EO56] showed that the number of real roots of a random degree $n$ polynomial with $\pm 1$ coefficients is $(\frac{2}{\pi}+o(1))\log n$.

See also [522].

Erdős and Offord [EO56] showed that the number of real roots of a random degree $n$ polynomial with $\pm 1$ coefficients is $(\frac{2}{\pi}+o(1))\log n$.

Solved by Yakir [Ya21], who proved that almost all such polynomials have \[\frac{n}{2}+O(n^{9/10})\] many roots in $\{ z\in \mathbb{C} : \lvert z\rvert \leq 1\}$.

See also [474] and [521].

Salem and Zygmund [SZ54] proved that $\sqrt{n\log n}$ is the right order of magnitude, but not an asymptotic.

A problem of Salem and Zygmund [SZ54]. Chung showed that, for almost all $t$, there exist infinitely many $n$ such that \[M_n(t) \ll \left(\frac{n}{\log\log n}\right)^{1/2}.\] Erdős (unpublished) showed that for almost all $t$ and every $\epsilon>0$ we have $\lim_{n\to \infty}M_n(t)/n^{1/2-\epsilon}=\infty$.

Random polynomials with independently identically distributed coefficients are sometimes called Kac polynomials - this problem considers the case of Radamacher coefficients, i.e. independent uniform $\pm 1$ values. The first problem asks whether $m(f)<1$ almost surely. Littlewood [Li66] conjectured that the stronger $m(f)=o(1)$ holds almost surely.

The answer to both questions is yes: Littlewood's conjecture was solved by Kashin [Ka87], and Konyagin [Ko94] improved this to show that $m(f)\leq n^{-1/2+o(1)}$ almost surely. This is essentially best possible, since Konyagin and Schlag [KoSc99] proved that for any $\epsilon>0$ \[\limsup_{n\to \infty} \mathbb{P}(m(f) \leq \epsilon n^{-1/2})\ll \epsilon.\] Cook and Nguyen [CoNg21] have identified the limiting distribution, proving that for any $\epsilon>0$ \[\lim_{n\to \infty} \mathbb{P}(m(f) > \epsilon n^{-1/2}) = e^{-\epsilon \lambda}\] where $\lambda$ is an explicit constant.

A problem of Dvoretzky [Dv56]. It is easy to see that (under the given conditions alone) almost all the circle is covered with probability $1$.

Kahane [Ka59] showed that $a_n=\frac{1+c}{n}$ with $c>0$ has this property, which Erd\H{s} (unpublished) improved to $a_n=\frac{1}{n}$. Erd\{o}s also showed that $a_n=\frac{1-c}{n}$ with $c>0$ does not have this property.

Solved by Shepp [Sh72], who showed that a necessary and sufficient condition is that \[\sum_n \frac{e^{a_1+\cdots+a_n}}{n^2}=\infty.\]

It is unclear to me whether Erdős also intended to assume that $\lvert a_{n+1}\rvert\leq \lvert a_n\rvert$.

It is 'well known' that, for almost all $\epsilon_n=\pm 1$, the series diverges for almost all $\lvert z\rvert=1$ (assuming only $\sum \lvert a_n\rvert^2=\infty$).

Dvoretzky and Erdős [DE59] showed that if $\lvert a_n\rvert >c/\sqrt{n}$ then, for almost all $\epsilon_n=\pm 1$, the series diverges for all $\lvert z\rvert=1$.

The constant $C_k$ is sometimes known as the connective constant. Hammersley and Morton [HM54] showed that this limit exists, and it is trivial that $k\leq C_k\leq 2k-1$.

Kesten [Ke63] proved that $C_k=2k-1-1/2k+O(1/k^2)$, and more precise asymptotics are given by Clisby, Liang, and Slade [CLS07].

Conway and Guttmann [CG93] showed that $C_2\geq 2.62$ and Alm [Al93] showed that $C_2\leq 2.696$. Jacobsen, Scullard, and Guttmann [JSG16] have computed the first few decimal places of $C_2$, showing that \[C_2 = 2.6381585303279\cdots.\]

The pinned distance problem, a stronger form of [89]. The example of an integer grid show that $n/\sqrt{\log n}$ would be best possible.

It may be true that there are $\gg n$ many such points, or that this is true on average. In [Er97e] Erdős offers \$500 for a solution to this problem, but it is unclear whether he intended this for proving the existence of a single such point or for $\gg n$ many such points.

In [Er97e] Erdős wrote that he initially 'overconjectured' and thought that the answer to this problem is the same as for the number of distinct distances between all pairs (see [89]), but this was disproved by Harborth. It could be true that the answers are the same up to an additive factor of $n^{o(1)}$.

The best known bound is \[\gg n^{c-o(1)},\] due to Katz and Tardos [KaTa04], where \[c=\frac{48-14e}{55-16e}=0.864137\cdots.\]

Commonly known as the second Hardy-Littlewood conjecture. In [Er85c] Erdős describes it as 'an old conjecture of mine which was probably already stated by Hardy and Littlewood'.

This is probably false, since Hensley and Richards [HeRi73] have shown that this is false assuming the Hardy-Littlewood prime tuples conjecture.

Erdős [Er85c] reports Straus as remarking that the 'correct way' of stating this conjecture would have been \[\pi(x+y) \leq \pi(x)+2\pi(y/2).\] Clark and Jarvis [ClJa01] have shown this is also incompatible with the prime tuples conjecture.

In [Er85c] Erdős conjectures the weaker result (which in particular follows from the conjecture of Straus) that \[\pi(x+y) \leq \pi(x)+\pi(y)+O\left(\frac{y}{(\log y)^2}\right),\] which the Hensley and Richards result shows (conditionally) would be best possible. Richards conjectured that this is false.

Erdős and Richards further conjectured that the original inequality is true almost always - that is, the set of $x$ such that $\pi(x+y)\leq \pi(x)+\pi(y)$ for all $y<x$ has density $1$. They could only prove that this set has positive lower density.

They also conjectured that for every $x$ the inequality $\pi(x+y)\leq \pi(x)+\pi(y)$ is true provided $y \gg (\log x)^C$ for some large constant $C>0$.

Hardy and Littlewood proved \[\pi(x+y) \leq \pi(x)+O(\pi(y)).\] The best known in this direction is a result of Montgomery and Vaughan [MoVa73], which shows \[\pi(x+y) \leq \pi(x)+2\frac{y}{\log y}.\]