46 solved out of 107 shown (show only solved or open)
OPEN - $500 If$A\subseteq \{1,\ldots,N\}$with$\lvert A\rvert=n$is such that the subset sums$\sum_{a\in S}a$are distinct for all$S\subseteq A$then $N \gg 2^{n}.$ 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}}.$ 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". See also [350]. Additional thanks to: Zachary Hunter SOLVED -$1000
Can the smallest modulus of a covering system be arbitrarily large?
Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown 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$.

SOLVED - $10000 For any$C>0$are there infinitely many$n$such that $p_{n+1}-p_n> C\frac{\log\log n\log\log\log\log n}{(\log\log \log n)^2}\log n?$ 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]. OPEN Let$C\geq 0$. Is there an infinite sequence of$n_i$such that $\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?$ 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 [Er97c] Erdős asks whether$S$is everywhere dense. SOLVED -$100
Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?
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'. 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}.$ Additional thanks to: Mehtaab Sawhney OPEN Is there a covering system all of whose moduli are odd? 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]). Additional thanks to: Antonio Girao OPEN -$500
If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.
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$.

OPEN - $1000 Let$h(N)$be the maximum size of a Sidon set in$\{1,\ldots,N\}$. Is it true that, for every$\epsilon>0$, $h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?$ 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]. Additional thanks to: Zachary Hunter OPEN Is there a set$A\subset\mathbb{N}$such that $\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)$ and such that every large integer can be written as$p+a$for some prime$p$and$a\in A$? Can the bound$O(\log N)$be achieved? Must such an$A$satisfy $\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?$ 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.$ OPEN Find the optimal constant$c>0$such that the following holds. For all sufficiently large$N$, if$A\sqcup B=\{1,\ldots,2N\}$is a partition into two equal parts, so that$\lvert A\rvert=\lvert B\rvert=N$, then there is some$x$such that the number of solutions to$a-b=x$with$a\in A$and$b\in B$is at least$cN$. 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]. SOLVED We say that$A\subset \mathbb{N}$is an essential component if$d_s(A+B)>d_s(B)$for every$B\subset \mathbb{N}$with$0<d_s(B)<1$where$d_s$is the Schnirelmann density. Can a lacunary set$A\subset\mathbb{N}$be an essential component? 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$. OPEN -$500
Is there an infinite Sidon set $A\subset \mathbb{N}$ such that $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon>0$?
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$. SOLVED -$500
If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist $d,m\geq 1$ such that $\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?$
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.$

OPEN - $250 Find the value of$\lim_{k\to \infty}R(k)^{1/k}$. 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. OPEN -$500
Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?
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.

OPEN - $500 Does every set of$n$distinct points in$\mathbb{R}^2$contain at most$n^{1+O(1/\log\log n)}$many pairs which are distance 1 apart? 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.

SOLVED
If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then they determine at least $\lfloor \frac{n+1}{2}\rfloor$ distinct distances.
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$.

OPEN - $100 Does every convex polygon have a vertex with no other$4$vertices equidistant from it? 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. Additional thanks to: Boris Alexeev and Dustin Mixon OPEN -$500
Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$.
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.

OPEN
If $p(z)\in\mathbb{C}[z]$ is a monic polynomial of degree $n$ then is the length of the curve $\{ z\in \mathbb{C} : \lvert p(z)\rvert=1\}$ maximised when $p(z)=z^n-1$?
A problem of Erdős, Herzog, and Piranian [EHP58].
SOLVED
If $p(z)$ is a polynomial of degree $n$ such that $\{z : \lvert p(z)\rvert\leq 1\}$ is connected then is it true that $\max_{\substack{z\in\mathbb{C}\\ \lvert p(z)\rvert\leq 1}} \lvert p'(z)\rvert \leq (\tfrac{1}{2}+o(1))n^2?$
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.

SOLVED
Let $p(z)=\prod_{i=1}^n (z-z_i)$ for $\lvert z_i\rvert \leq 1$. Then the area of the set where $A=\{ z: \lvert p(z)\rvert <1\}$ is $>n^{-O(1)}$ (or perhaps even $>(\log n)^{-O(1)}$).
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$.

Additional thanks to: Boris Alexeev and Dustin Mixon
SOLVED - $100 Let$z_i$be an infinite sequence of complex numbers such that$\lvert z_i\rvert=1$for all$i\geq 1$, and for$n\geq 1$let $p_n(z)=\prod_{i\leq n} (z-z_i).$ Let$M_n=\max_{\lvert z\rvert=1}\lvert p_n(z)\rvert$. Is it true that$\limsup M_n=\infty$? Is it true that there exists$c>0$such that for infinitely many$n$we have$M_n > n^c$, or even that for all$n$$\sum_{k\leq n}M_k > n^{1+c}?$ 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.$ Additional thanks to: Winston Heap OPEN Let the van der Waerden number$W(k)$be such that whenever$N\geq W(k)$and$\{1,\ldots,N\}$is$2$-coloured there must exist a monochromatic$k$-term arithmetic progression. Improve the bounds for$W(k)$- for example, prove that$W(k)^{1/k}\to \infty$. 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$. SOLVED -$1000
Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.
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$.

OPEN - $500 Let$A\subset (1,\infty)$be a countably infinite set such that for all$x\neq y\in A$and integers$k\geq 1$we have $\lvert kx -y\rvert \geq 1.$ Does this imply that $\liminf \frac{\lvert A\cap [1,x]\rvert}{x}=0?$ Or $\sum_{x\in A}\frac{1}{x\log x}<\infty,$ or $\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n)?$ Perhaps even $\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}\ll \frac{\log x}{\sqrt{\log\log x}}?$ 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 that$\sum_{n<x}\frac{1}{n}=o(\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}$. Additional thanks to: Zachary Chase SOLVED -$250
The density of integers which have two divisors $d_1,d_2$ such that $d_1<d_2<2d_1$ exists and is equal to $1$.
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]. OPEN -$250
Give an asymptotic formula for $R(3,k)$.
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.

OPEN - $250 Let$R(3;k)$be the minimal$n$such that if the edges of$K_n$are coloured with$k$colours then there must exist a monochromatic triangle. Determine $\lim_{k\to \infty}R(3;k)^{1/k}.$ 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}.$

Additional thanks to: Antonio Girao, David Penman
OPEN
Let $n_1<\cdots < n_r\leq N$ with associated $a_i\pmod{n_i}$ such that the congruence classes are disjoint (that is, every integer is $\equiv a_i\pmod{n_i}$ for at most one $1\leq i\leq r$). How large can $r$ be in terms of $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.
OPEN
Let $s_1<s_2<\cdots$ be the sequence of squarefree numbers. Is it true that, for any $\epsilon>0$ and large $n$, $s_{n+1}-s_n \ll_\epsilon s_n^{\epsilon}?$ Is it true that $s_{n+1}-s_n \leq (1+o(1))\frac{\pi^2}{6}\frac{\log s_n}{\log\log s_n}?$
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$.

SOLVED
Let $f(n)$ be minimal such that the following holds. For any $n$ points in $\mathbb{R}^2$, not all on a line, there must be at least $f(n)$ many lines which contain exactly 2 points (called 'ordinary lines'). Does $f(n)\to \infty$? How fast?
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$.

OPEN
Is there a dense subset of $\mathbb{R}^2$ such that all pairwise distances are rational?
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).

OPEN
Let $d_n=p_{n+1}-p_n$. The set of $n$ such that $d_{n+1}\geq d_n$ has density $1/2$, and similarly for $d_{n+1}\leq d_n$. Furthermore, there are infinitely many $n$ such that $d_{n+1}=d_n$.
SOLVED
Are there arbitrarily long arithmetic progressions of primes?
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.
SOLVED - $250 Let$n\geq 1$and $A=\{a_1<\cdots <a_{\phi(n)}\}=\{ 1\leq m<n : (m,n)=1\}.$ Is it true that $\sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^2 \ll \frac{n^2}{\phi(n)}?$ 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]). SOLVED Is there a set$A\subset\mathbb{N}$such that, for all large$N$, $\lvert A\cap\{1,\ldots,N\}\rvert \ll N/\log N$ and such that every large integer can be written as$2^k+a$for some$k\geq 0$and$a\in A$? 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$. OPEN Let$n_1<n_2<\cdots$be the sequence of integers which are the sum of two squares. Explore the behaviour of (i.e. find good upper and lower bounds for) the consecutive differences$n_{k+1}-n_k$. 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}.$ SOLVED If$A\subseteq \mathbb{R}^d$is any set of$2^d+1$points then some three points in$A$determine an obtuse angle. 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]. Additional thanks to: Boris Alexeev and Dustin Mixon SOLVED Let $f(\theta) = \sum_{k\geq 1}c_k e^{ik\theta}$ be a trigonometric polynomial (so that the$c_k\in \mathbb{C}$are finitely supported) with real roots such that$\max_{\theta\in [0,2\pi]}\lvert f(\theta)\rvert=1$. Then $\int_0^{2\pi}\lvert f(\theta)\rvert \mathrm{d}\theta \leq 4.$ 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}$). Additional thanks to: Winston Heap, Vjekoslav Kovac, Karlo Lelas SOLVED Let$f=\sum_{n=0}^\infty a_nz^n$be an entire function. Is it true that if $\lim_{r\to \infty} \frac{\max_n\lvert a_nr^n\rvert}{\max_{\lvert z\rvert=r}\lvert f(z)\rvert}$ exists then it must be$0$? 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]. SOLVED Does there exist, for all large$n$, a polynomial$P$of degree$n$, with coefficients$\pm 1$, such that $\sqrt{n} \ll \lvert P(z) \rvert \ll \sqrt{n}$ for all$\lvert z\rvert =1$, with the implied constants independent of$z$and$n$? 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]. Additional thanks to: Mehtaab Sawhney SOLVED Let$P(z)=\sum_{1\leq k\leq n}a_kz^k$for some$a_k\in \mathbb{C}$with$\lvert a_k\rvert=1$for$1\leq k\leq n$. Does there exist a constant$c>0$such that, for$n\geq 2$, we have $\max_{\lvert z\rvert=1}\lvert P(z)\rvert \geq (1+c)\sqrt{n}?$ 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]. Additional thanks to: Mehtaab Sawhney SOLVED Let$S$be a string of length$2^k-1$formed from an alphabet of$k$characters. Must$S$contain an abelian square: two consecutive blocks$x$and$y$such that$y$is a permutation of$x$? 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. OPEN For every$c\geq 0$the density$f(c)$of integers for which $\frac{p_{n+1}-p_n}{\log n}< c$ exists and is a continuous function of$c$. OPEN Let$f(n)$count the number of solutions to$n=p+2^k$for prime$p$and$k\geq 0$. Is it true that$f(n)=o(\log n)$? 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). See also [237]. SOLVED Let$A\subseteq \mathbb{N}$be a set such that$\lvert A\cap \{1,\ldots,N\}\rvert \gg \log N$for all large$N$. Let$f(n)$count the number of solutions to$n=p+a$for$p$prime and$a\in A$. Is it true that$\limsup f(n)=\infty$? Erdős [Er50] proved this when$A=\{2^k : k\geq 0\}$. Solved by Chen and Ding [ChDi22]. See also [236]. SOLVED Let$f:\mathbb{N}\to \{-1,1\}$be a multiplicative function. Is it true that $\lim_{N\to \infty}\frac{1}{N}\sum_{n\leq N}f(n)$ always exists? 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]. OPEN Is there an infinite set of primes$P$such that if$\{a_1<a_2<\cdots\}$is the set of integers divisible only by primes in$P$then$\lim a_{i+1}-a_i=\infty$? 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. Additional thanks to: Boris Alexeev and Dustin Mixon OPEN -$100
Let $f(N)$ be the maximum size of $A\subseteq \{1,\ldots,N\}$ such that the sums $a+b+c$ with $a,b,c\in A$ are all distinct (aside from the trivial coincidences). Is it true that $f(N)\sim N^{1/3}?$
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]).

OPEN
For every $n\geq 2$ there exist distinct integers $1\leq x<y<z$ such that $\frac{4}{n} = \frac{1}{x}+\frac{1}{y}+\frac{1}{z}.$
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}.$

OPEN
Let $C>1$. Does the set of integers of the form $p+\lfloor C^k\rfloor$, for some prime $p$ and $k\geq 0$, have density $>0$?
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.
SOLVED
Let $A\subseteq \mathbb{N}$ be an infinite set such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that $\limsup_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}\geq 3?$
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].

SOLVED
Let $(a,b)=1$. Every large integer is the sum of distinct integers of the form $a^kb^l$ with $k,l\geq 0$.
Proved by Birch [Bi59].
SOLVED
Let $a_1<a_2<\cdots$ be an infinite sequence of integers such that $a_{i+1}/a_i\to 1$. If every arithmetic progression contains infinitely many integers which are the sum of distinct $a_i$ then every sufficiently large integer is the sum of distinct $a_i$.
This was disproved by Cassels [Ca60].
OPEN
Let $A\subseteq \mathbb{N}$ be such that $\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert \to \infty\textrm{ as }x\to \infty$ and $\sum_{n\in A} \{ \theta n\}=\infty$ for every $\theta\in (0,1)$, where $\{x\}$ is the distance of $x$ from the nearest integer. Then every sufficiently large integer is the sum of distinct elements of $A$.
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)$.
SOLVED
Let $z_1,z_2,\ldots \in [0,1]$ be an infinite sequence, and define the discrepancy $D_N(I) = \#\{ n\leq N : z_n\in I\} - N\lvert I\rvert.$ Must there exist some interval $I\subseteq [0,1]$ such that $\limsup_{N\to \infty}\lvert D_N(I)\rvert =\infty?$
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.$

Additional thanks to: Cedric Pilatte and Stefan Steinerberger
OPEN
Let $n\geq 1$ and $f(n)$ be maximal such that, for every $a_1\leq \cdots \leq a_n\in \mathbb{N}$ we have $\max_{\lvert z\rvert=1}\left\lvert \prod_{i}(1-z^{a_i})\right\rvert\geq f(n).$ Estimate $f(n)$ - in particular, is it true that there exists some constant $c>0$ such that $f(n) \geq \exp(n^{c})?$
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).$

Additional thanks to: Zachary Chase, Stefan Steinerberger
SOLVED
How large can a union-free collection $\mathcal{F}$ of subsets of $[n]$ be? By union-free we mean there are no solutions to $A\cup B=C$ with distinct $A,B,C\in \mathcal{F}$. Must $\lvert \mathcal{F}\rvert =o(2^n)$? Perhaps even $\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}?$
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}.$

OPEN
Let $f(k)$ be the minimal $N$ such that if $\{1,\ldots,N\}$ is $k$-coloured then there is a monochromatic solution to $a+b=c$. Estimate $f(k)$. In particular, is it true that $f(k) < c^k$ for some constant $c>0$?
Schur proved that $f(k)<ek!$. See also [183].
OPEN
Prove that there exists an absolute constant $c>0$ such that, whenever $\{1,\ldots,N\}$ is $k$-coloured (and $N$ is large enough depending on $k$) then there are at least $cN$ many integers in $\{1,\ldots,N\}$ which are representable as a monochromatic sum (that is, $a+b$ where $a,b\in \{1,\ldots,N\}$ are in the same colour class).
A conjecture of Roth.
SOLVED
Let $f(k)$ be the minimum number of terms in $P(x)^2$, where $P\in \mathbb{Q}[x]$ ranges over all polynomials with exactly $k$ non-zero terms. Is it true that $f(k)\to\infty$ as $k\to \infty$?
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.$

OPEN
Let $A\subseteq \mathbb{N}$, and for each $n\in A$ choose some $X_n\subseteq \mathbb{Z}/n\mathbb{Z}$. Let $B = \{ m\in \mathbb{N} : m\not\in X_n\pmod{n}\textrm{ for all }n\in A\}.$ Must $B$ have a logarithmic density, i.e. is it true that $\lim_{x\to \infty} \frac{1}{\log x}\sum_{\substack{m\in B\\ m<x}}\frac{1}{m}$ exists?
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$.
SOLVED
Let $A\subseteq \mathbb{N}$ have positive density. Must there exist distinct $a,b,c\in A$ such that $[a,b]=c$ (where $[a,b]$ is the lowest common multiple of $a$ and $b$)?
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].

OPEN
Let $A$ be a finite set and $B=\{ n \geq 1 : a\nmid n\textrm{ for all }a\in A\}.$ Is it true that, for every $m>n$, $\frac{\lvert B\cap [1,m]\rvert }{m}< 2\frac{\lvert B\cap [1,n]\rvert}{n}?$
The example $A=\{a\}$ and $n=2a-1$ and $m=2a$ shows that $2$ would be best possible.
OPEN
Let $A\subseteq \mathbb{N}$ be a set such that $\lvert A\cap [1,x]\rvert=o(x^{1/2})$. Let $B=\{ n\geq 1 : a\nmid n\textrm{ for all }a\in A\}.$ If $B=\{b_1<b_2<\cdots\}$ then is it true that $\lim \frac{1}{x}\sum_{b_i<x}(b_{i+1}-b_i)^2$ exists (and is finite)?
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.

SOLVED
Let $A,B\subseteq \{1,\ldots,N\}$ be such that all the products $ab$ with $a\in A$ and $b\in B$ are distinct. Is it true that $\lvert A\rvert \lvert B\rvert \ll \frac{N^2}{\log N}?$
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}\}$.

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

SOLVED
Let $f:\mathbb{N}\to \mathbb{R}$ be an additive function (i.e. $f(ab)=f(a)+f(b)$ whenever $(a,b)=1$). If there is a constant $c$ such that $\lvert f(n+1)-f(n)\rvert <c$ for all $n$ then must there exist some $c'$ such that $f(n)=c'\log n+O(1)?$
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].

SOLVED
Let $A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}$ be infinite such that $a_{i+1}/a_i\to 1$. For any $x\geq a_1$ let $f(x) = \frac{x-a_i}{a_{i+1}-a_i}\in [0,1),$ where $x\in [a_i,a_{i+1})$. Is it true that, for almost all $\alpha$, the sequence $f(\alpha n)$ is uniformly distributed in $[0,1)$?
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].

SOLVED
Does there exist a $k$ such that every sufficiently large integer can be written in the form $\prod_{i=1}^k a_i - \sum_{i=1}^k a_i$ for some integers $a_i\geq 2$?
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.
OPEN
Let $A\subset \mathbb{C}$ be a finite set of fixed size, for any $k\geq 1$ let $A_k = \{ z_1+\cdots+z_k : z_i\in A\textrm{ distinct}\}.$ For $k>2$ does the set $A_k$ (together with the size of $A$) uniquely determine the set $A$?
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.)

OPEN
Let $\alpha,\beta \in \mathbb{R}$. Is it true that $\liminf_{n\to \infty} n \| n\alpha \| \| n\beta\| =0$ where $\|x\|$ is the distance from $x$ to the nearest integer?
The infamous Littlewood conjecture.
SOLVED
Let $\alpha \in \mathbb{R}$ be irrational and $\epsilon>0$. Are there positive integers $x,y,z$ such that $\lvert x^2+y^2-z^2\alpha\rvert <\epsilon?$
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].

SOLVED
How many antichains in $[n]$ are there? That is, how many families of subsets of $[n]$ are there such that, if $\mathcal{F}$ is such a family and $A,B\in \mathcal{F}$, then $A\not\subseteq B$?
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}}.$

SOLVED
Let $z_1,\ldots,z_n\in\mathbb{C}$. Let $D$ be an arbitrary disc of radius $1$. Is it true that the number of sums of the shape $\sum_{i=1}^n\epsilon_iz_i \textrm{ for }\epsilon_i\in \{-1,1\}$ which lie in $D$ is at most $\binom{n}{\lfloor n/2\rfloor}$?
A strong form of the Littlewood-Offord problem. Erdős 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].
SOLVED
Let $M=(a_{ij})$ be a real $n\times n$ doubly stochastic matrix (i.e. the entries are non-negative and each column and row sums to $1$). Does there exist some $\sigma\in S_n$ such that $\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}?$
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].

OPEN - $500 What is$\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of$3$-edges which can placed on$n$vertices so that there exists no$K_4^3$, a set of 4 vertices which is covered by all 4 possible$3$-edges. 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. OPEN For every$x\in\mathbb{R}$let$A_x\subset \mathbb{R}$be a bounded set with outer measure$<1$. Must there exist an infinite independent set, that is, some infinite$X\subseteq \mathbb{R}$such that$x\not\in A_y$for all$x\neq y\in X$? If the sets$A_x$are closed and have measure$<1$, then must there exist an independent set of size$3$? 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. SOLVED What is the size of the largest$A\subseteq \mathbb{R}^n$such that there are only two distinct distances between elements of$A$? That is, $\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.$ 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$. Additional thanks to: Ryan Alweiss, Jordan Ellenberg, Shengtong Zhang OPEN What is the size of the largest$A\subseteq \mathbb{R}^n$such that every three points from$A$determine an isosceles triangle? That is, for any three points$x,y,z$from$A$, at least two of the distances$\lvert x-y\rvert,\lvert y-z\rvert,\lvert x-z\rvert$are equal. 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. Additional thanks to: Ryan Alweiss SOLVED Let$\alpha_n$be the infimum of all$0\leq \alpha\leq \pi$such that in every set$A\subset \mathbb{R}^2$of size$n$there exist three distinct points$x,y,z\in A$such that the angle determined by$xyz$is at least$\alpha$. Determine$\alpha_n$. 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}$. SOLVED Is every set of diameter$1$in$\mathbb{R}^n$the union of at most$n+1$sets of diameter$<1$? 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}.$ OPEN What is the minimum number of circles determined by any$n$points in$\mathbb{R}^2$, not all on a circle? OPEN Let$\alpha(n)$be such that every set of$n$points in the unit circle contains three points which determine a triangle of area at most$\alpha(n)$. Estimate$\alpha(n)$. 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]). OPEN What is the chromatic number of the plane? That is, what is the smallest number of colours required to colour$\mathbb{R}^2$such that no two points of the same colour are distance$1$apart? 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]. OPEN Let$f(z)\in\mathbb{C}[z]$be a monic non-constant polynomial. Can the set $\{ z\in \mathbb{C} : \lvert f(z)\rvert \leq 1\}$ be covered by a set of circles the sum of whose radii is$\leq 2$? 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$). OPEN If$A\subset \mathbb{Z}$is a finite set of size$N$then is there some absolute constant$c>0$and$\theta$such that $\sum_{n\in A}\cos(n\theta) < -cN^{1/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. OPEN Let$f(z)\in \mathbb{C}[z]$be a monic polynomial of degree$n$and $A = \{ z\in \mathbb{C} : \lvert f(z)\rvert\leq 1\}.$ Is it true that, for every such$f$and constant$c>0$, the set$A$can have at most$O_c(1)$many components of diameter$>1+c$(where the implied constant is in particular independent of$n$)? SOLVED Is it true that, if$A\subset \mathbb{Z}$is a finite set of size$N$, then $\int_0^1 \left\lvert \sum_{n\in A}e(n\theta)\right\rvert \mathrm{d}\theta \gg \log N,$ where$e(x)=e^{2\pi ix }$? Littlewood's conjecture, proved independently by Konyagin [Ko81] and McGehee, Pigno, and Smith [MPS81]. OPEN Let$f=\sum_{n=0}^\infty a_nz^n$be an entire function. What is the greatest possible value of $\liminf_{r\to \infty} \frac{\max_n\lvert a_nr^n\rvert}{\max_{\lvert z\rvert=r}\lvert f(z)\rvert}?$ 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]. OPEN Let$f(z)$be an entire function. Does there exist a path$L$so that, for every$n$, $\lvert f(z)/z^n\rvert \to \infty$ as$z\to \infty$along$L$? Can the length of this path be estimated in terms of$M(r)=\max_{\lvert z\rvert=r}\lvert f(z)\rvert$? Does there exist a path along which$\lvert f(z)\rvert$tends to$\infty$faster than a fixed function of$M(r)$(such that$M(r)^\epsilon$)? Boas (unpublished) has proved the first part, that such a path must exist. OPEN Let$f(z)$be an entire function, not a polynomial. Does there exist a path$C$such that, for every$\lambda>0$, the integral $\int_C \lvert f(z)\rvert^{-\lambda} \mathrm{d}z$ is finite? Huber [Hu57] proved that for every$\lambda>0$there is a path$C_\lambda$such that this integral is finite. OPEN Let$f(z)=\sum_{k\geq 1}a_k z^{n_k}$be an entire function of finite order such that$\lim n_k/k=\infty$. Let$M(r)=\max_{\lvert z\rvert=r}\lvert f(z)\rvert$and$m(r)=\max_n \lvert a_nr^n\rvert$. Is it true that $\limsup\frac{\log m(r)}{\log M(r)}=1?$ 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.$ OPEN Let$f(z)=\sum_{k=1}^\infty a_kz^{n_k}$be an entire function. Is it true that if$n_k/k\to \infty$then$f(z)$assumes every value infinitely often? 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$. OPEN Let$A_1,A_2,\ldots$be sets of complex numbers, none of which has a limit point in$\mathbb{C}$. Does there exist an entire function$f(z)$and a sequence$n_1<n_2<\cdots$such that$f^{(n_k)}$vanishes on$A_k$for all$k\geq 1$? SOLVED Let$z_1,\ldots,z_n\in \mathbb{C}$with$z_1=1$. Must there exist an absolute constant$c>0$such that $\max_{1\leq k\leq n}\left\lvert \sum_{i}z_i^k\right\rvert>c?$ 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$. SOLVED Let$f$be a Rademacher multiplicative function: a random$\{-1,0,1\}$-valued multiplicative function, where for each prime$p$we independently choose$f(p)\in \{-1,1\}$uniformly at random, and for square-free integers$n$we extend$f(p_1\cdots p_r)=f(p_1)\cdots f(p_r)$(and$f(n)=0$if$n$is not squarefree). Does there exist some constant$c>0$such that, almost surely, $\limsup_{N\to \infty}\frac{\sum_{m\leq N}f(m)}{\sqrt{N\log\log N}}=c?$ 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]. Additional thanks to: Mehtaab Sawhney OPEN For any$t\in (0,1)$let$t=\sum_{k=1}^\infty \epsilon_k(t)2^{-k}$(where$\epsilon_k(t)\in \{0,1\}$). Let$R_n(t)$denote the number of real roots of$\sum_{1\leq k\leq n}\epsilon_k(t)z^k$. Is it true that, for almost all$t\in (0,1)$, we have $\lim_{n\to \infty}\frac{R_n(t)}{\log n}=\frac{\pi}{2}?$ 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]. OPEN Is it true that all except$o(2^n)$many polynomials of degree$n$with$\pm 1$-valued coefficients have$(\frac{1}{2}+o(1))n$many roots in$\{ z\in \mathbb{C} : \lvert z\rvert \leq 1\}$? For any$t\in (0,1)$let$t=\sum_{k=1}^\infty \epsilon_k(t)2^{-k}$(where$\epsilon_k(t)\in \{0,1\}$). If$S_n(t)$is the number of roots of$\sum_{1\leq k\leq n}\epsilon_k(t)z^k$in$\lvert z\rvert \leq1$then is it true that, for almost all$t\in (0,1)$, $\lim_{n\to \infty}\frac{S_n(t)}{n}=\frac{1}{2}?$ 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 [521]. Additional thanks to: Zachary Chase OPEN For any$t\in (0,1)$let$t=\sum_{k=1}^\infty \epsilon_k(t)2^{-k}$(where$\epsilon_k(t)\in \{0,1\}$). Does there exist some constant$C>0$such that, for almost all$t\in (0,1)$, $\max_{\lvert z\rvert=1}\left\lvert \sum_{k\leq n}\epsilon_k(t)z^k\right\rvert=(C+o(1))\sqrt{n\log n}?$ Salem and Zygmund [SZ54] proved that$\sqrt{n\log n}$is the right order of magnitude, but not an asymptotic. OPEN For any$t\in (0,1)$let$t=\sum_{k=1}^\infty \epsilon_k(t)2^{-k}$(where$\epsilon_k(t)\in \{0,1\}$). What is the correct order of magnitude (for almost all$t\in(0,1)$) for $M_n(t)=\max_{x\in [0,1]}\left\lvert \sum_{k\leq n}\epsilon_k(t)x^k\right\rvert?$ 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$. SOLVED Is it true that all except at most$o(2^n)$many degree$n$polynomials with$\pm 1$-valued coefficients$f(z)$have$\lvert f(z)\rvert <1$for some$\lvert z\rvert=1$? What is the behaviour of $m(f)=\min_{\lvert z\rvert=1}\lvert f(z)\rvert?$ 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. Additional thanks to: Mehtaab Sawhney SOLVED Let$a_n\geq 0$with$a_n\to 0$and$\sum a_n=\infty$. Find a necessary and sufficient condition on the$a_n$such that, if we choose (independently and uniformly) random arcs on the unit circle of length$a_n$, then all the circle is covered with probability$1$. 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.$ OPEN Let$a_n\in \mathbb{R}$be such that$\sum_n \lvert a_n\rvert^2=\infty$and$\lvert a_n\rvert=o(1/\sqrt{n})$. Is it true that, for almost all$\epsilon_n=\pm 1$, there exists some$z$with$\lvert z\rvert=1$(depending on the choice of signs) such that $\sum_n \epsilon_n a_n z^n$ converges? 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$. OPEN Let$f(n,k)$count the number of self-avoiding walks of$n$steps (beginning at the origin) in$\mathbb{Z}^k$(i.e. those walks which do not intersect themselves). Determine $C_k=\lim_{n\to\infty}f(n,k)^{1/n}.$ 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$. OPEN Let$d_k(n)$be the expected distance from the origin after taking$n$random steps from the origin in$\mathbb{Z}^k$(conditional on no self intersections). Is it true that $\lim_{n\to \infty}\frac{d_2(n)}{n^{1/2}}= \infty?$ Is it true that $d_k(n)\ll n^{1/2}$ for$k\geq 3$? OPEN -$500
Given $n$ distinct points $A\subset\mathbb{R}^2$ must there be a point $x\in A$ such that $\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?$ Or even $\gg n/\sqrt{\log n}$?
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.$