Logo
All Random Solved Random Open
38 solved out of 58 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' (in [Er98] he dates it to 1931). 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].

Additional thanks to: Zach Hunter and Ralf Stephan
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 (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 upper bound on the smallest modulus to $616000$.

The best known lower bound is a covering system whose minimum modulus is $42$, due to Owens [Ow14].

Additional thanks to: Desmond Weisenberg
OPEN - $5000
If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?
This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like \[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\] would be sufficient.

Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that \[r_k(N) \ll \frac{N}{\exp((\log\log N)^{c_k})}\] for some constant $c_k>0$ depending on $k$.

Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08] (see [219]).

In [Er81] Erdős makes the stronger conjecture that \[r_k(N) \ll_C\frac{N}{(\log N)^C}\] for every $C>0$ (now known for $k=3$ due to Kelley and Meka [KeMe23]) - see [140].

See also [139] and [142].

SOLVED - $10000
Is it true that, for any $C>0$, 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].

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

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

SOLVED
Is it true that for every infinite arithmetic progression $P$ which contains even numbers there is some constant $c=c(P)$ such that every graph with average degree at least $c$ contains a cycle whose length is in $P$?
In [Er82e] Erdős credits this conjecture to himself and Burr. This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(P)$ is unknown.

See also [72].

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.

See also [661].

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. In [Er82e] he offers \$300 for the upper bound $n^{1+o(1)}$.

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

See also [660].

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.

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

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

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

Additional thanks to: Boris Alexeev and Dustin Mixon
OPEN - $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$?

Is it true that there exists $c>0$ such that, for all large $n$, \[\sum_{k\leq n}M_k > n^{1+c}?\]

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

The second question was answered by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\] The third question seems to remain open.

Additional thanks to: Winston Heap
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)$.
A conjecture of Erdős and Turá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$.

See also [3].

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] and [884].

SOLVED
For any $d\geq 1$ if $H$ is a graph such that every subgraph contains a vertex of degree at most $d$ then $R(H)\ll_d n$.
The Burr-Erdős conjecture. This is equivalent to showing that if $H$ is the union of $c$ forests then $R(H)\ll_c n$, and also that if every subgraph has average degree at most $d$ then $R(H)\ll_d n$. Solved by Lee [Le16], who proved that \[ R(H) \leq 2^{2^{O(d)}}n.\]

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

SOLVED
Let $C>0$ be arbitrary. Is it true that, if $n$ is sufficiently large depending on $C$, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq C?\]
The answer is yes, which was proved by Rödl [Ro03].

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

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

Additional thanks to: Mehtaab Sawhney
SOLVED
Let $g(k)$ be the smallest integer (if any such exists) such that any $g(k)$ points in $\mathbb{R}^2$ contains an empty convex $k$-gon (i.e. with no point in the interior). Does $g(k)$ exist? If so, estimate $g(k)$.
A variant of the 'happy ending' problem [107], which asks for the same without the 'no point in the interior' restriction. Erdős observed $g(4)=5$ (as with the happy ending problem) but Harborth [Ha78] showed $g(5)=10$. Nicolás [Ni07] and Gerken [Ge08] independently showed that $g(6)$ exists. Horton [Ho83] showed that $g(n)$ does not exist for $n\geq 7$.

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

Additional thanks to: Zach Hunter
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$.

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
Let $(S_n)_{n\geq 1}$ be a sequence of sets of complex numbers, none of which have a finite limit point. Does there exist an entire function $f(z)$ such that, for all $n\geq 1$, there exists some $k_n\geq 0$ such that \[f^{(k_n)}(z) = 0\textrm{ for all }z\in S_n?\]
Solved in the affirmative by Barth and Schneider [BaSc72].
Additional thanks to: Zachary Chase and Terence Tao
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].
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].

See also [899] for the difference set analogue.

Additional thanks to: Zachary Chase
SOLVED
Is it true that, for every $c$, there exists an $n$ such that $\sigma(n)>cn$ but there is no covering system whose moduli all divide $n$?
This was answered affirmatively by Haight [Ha79].
SOLVED
How large can $A\subseteq \{1,\ldots,N\}$ be if $A+A$ contains no square numbers?
Taking all integers $\equiv 1\pmod{3}$ shows that $\lvert A\rvert\geq N/3$ is possible. This can be improved to $\tfrac{11}{32}N$ by taking all integers $\equiv 1,5,9,13,14,17,21,25,26,29,30\pmod{32}$, as observed by Massias.

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

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

See also [439] and [587].

SOLVED
Let $A=\{n_1<n_2<\cdots\}\subset \mathbb{N}$ be a lacunary sequence (so there exists some $\epsilon>0$ with $n_{k+1}\geq (1+\epsilon)n_k$ for all $k$). Must there exist an irrational $\theta$ such that \[\{ \|\theta n_k\| : k\geq 1\}\] is not dense in $[0,1]$ (where $\| x\|$ is the distance to the nearest integer)?
Solved independently by de Mathan [dM80] and Pollington [Po79b], who showed that, given any such $A$, there exists such a $\theta$, with \[\inf_{k\geq 1}\| \theta n_k\| \gg \frac{\epsilon^4}{\log(1/\epsilon)}.\] This bound was improved by Katznelson [Ka01], Akhunzhanov and Moshchevitin [AkMo04], and Dubickas [Du06], before Peres and Schlag [PeSc10] improved it to \[\inf_{k\geq 1}\| \theta n_k\| \gg \frac{\epsilon}{\log(1/\epsilon)},\] and note that the best bound possible here would be $\gg \epsilon$.

This problem has consequences for [894].

Additional thanks to: Euro Vidal Sampaio
SOLVED
Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that \[\| \lvert P_i-P_j\rvert \| \geq \delta\] for all $1\leq i<j\leq n$. (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is it true that, for any $0<\delta<1/2$, we have \[N(X,\delta)=o(X)?\] In fact, is it true that (for any fixed $\delta>0$) \[N(X,\delta)<X^{1/2+o(1)}?\]

The first conjecture was proved by Sárközy [Sa76], who in fact proved \[N(X,\delta) \ll \delta^{-3}\frac{X}{\log\log X}.\]

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

See also [466] for lower bounds.

Additional thanks to: Stefan Steinerberger
SOLVED
Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that \[\| \lvert P_i-P_j\rvert \| \geq \delta\] for all $1\leq i<j\leq n$. (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is there some $\delta>0$ such that \[\lim_{x\to \infty}N(X,\delta)=\infty?\]

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

See also [897].

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 locally rectifiable path $C$ tending to infinity 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 such a path $C_\lambda$ such that this integral is finite.
Additional thanks to: Cedric Pilatte and Desmond Weisenberg
SOLVED - $250
Let $\alpha$ be the infinite ordinal $\omega^\omega$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$?
A problem of Erdős and Rado. For comparison, Specker [Sp57] proved this property holds when $\alpha=\omega^2$ and false when $\alpha=\omega^n$ for $3\leq n<\omega$ (a question of Erdős for which he offered \$20).

This is true, and was proved by Chang [Ch72]. Milner modified Chang's proof to prove that this remains true if we replace $K_3$ by $K_m$ for all finite $m<\omega$ (a shorter proof was found by Larson [La73]).

See also [591] and [592].

OPEN - $250
Let $\alpha$ be the infinite ordinal $\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$?
For comparison, Specker [Sp57] proved this property holds when $\alpha=\omega^2$ and false when $\alpha=\omega^n$ for $3\leq n<\omega$. Chang proved this property holds when $\alpha=\omega^\omega$ (see [590]).

See [592] for the general case.

OPEN - $1000
Determine which countable ordinals $\beta$ have the property that, if $\alpha=\omega^{^\beta}$, then in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$.
This property holds for $\beta=2$ and not for $3\leq \beta <\omega$ (Specker [Sp57]) and for $\beta=\omega$ (Chang [Ch72]).

The first open case is $\beta=\omega^2$ (see [591]). Galvin and Larson [GaLa74] have shown that if $\beta\geq 3$ has this property then $\beta$ must be 'additively indecomposable', so that in particular $\beta=\omega^\gamma$ for some $\gamma<\omega_1$. Galvin and Larson conjecture that every $\beta\geq 3$ of this form has this property.

See also [590].

OPEN - $500
For which limit ordinals $\alpha$ is it true that if $G$ is a graph with vertex set $\alpha$ then $G$ must have either an infinite path or independent set on a set of vertices with order type $\alpha$?
A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.

In [Er82e] Erdős offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.

Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.

OPEN - $250
Given $a_{i}^n\in [-1,1]$ for all $1\leq i\leq n<\infty$ we define $p_{i}^n$ as the unique polynomial of degree $n-1$ such that $p_{i}^n(a_{i}^n)=1$ and $p_{i}^n(a_{i'}^n)=0$ if $1\leq i'\leq n$ with $i\neq i'$. We similarly define \[\mathcal{L}^nf(x) = \sum_{1\leq i\leq n}f(a_i^n)p_i^n(x),\] the unique polynomial of degree $n-1$ which agrees with $f$ on $a_i^n$ for $1\leq i\leq n$ (that is, the sequence of Langrange interpolation polynomials).

Is there such a sequence of $a_i^n$ such that for every continuous $f:[-1,1]\to \mathbb{R}$ there exists some $x\in [-1,1]$ where \[\limsup_{n\to \infty} \sum_{1\leq i\leq n}\lvert p_{i}^n(x)\rvert=\infty\] and yet \[\mathcal{L}^nf(x) \to f(x)?\]

Is there such a sequence such that \[\limsup_{n\to \infty} \sum_{1\leq i\leq n}\lvert p_{i}^n(x)\rvert=\infty\] for every $x\in [-1,1]$ and yet for every continuous $f:[-1,1]\to \mathbb{R}$ there exists $x\in [-1,1]$ with \[\mathcal{L}^nf(x) \to f(x)?\]

Bernstein [Be31] proved that for any choice of $a_i^n$ there exists $x_0\in [-1,1]$ such that \[\limsup_{n\to \infty} \sum_{1\leq i\leq n}\lvert p_{i}^n(x)\rvert=\infty.\] Erdős and Vértesi [ErVe80] proved that for any choice of $a_i^n$ there exists a continuous $f:[-1,1]\to \mathbb{R}$ such that \[\limsup_{n\to \infty} \lvert \mathcal{L}^nf(x)\rvert=\infty\] for almost all $x\in [-1,1]$.
SOLVED
Let $1=d_1<\cdots <d_{\tau(n)}=n$ be the divisors of $n$ and \[G(n) = \sum_{1\leq i<\tau(n)}\frac{d_i}{d_{i+1}}.\] Is it true that $G(n)\to \infty$ for almost all $n$? Can one prove an asymptotic formula for $\sum_{n\leq X}G(n)$?
Erdős writes it is 'easy' to prove $\frac{1}{X}\sum_{n\leq X}G(n)\to \infty$.

Terence Tao has observed that, for any divisor $m\mid n$, \[\frac{\tau(n/m)}{m} \leq G(n) \leq \tau(n),\] and hence for example $\tau(n)/4\leq G(n)\leq \tau(n)$ for even $n$. It is easy to then see that $G(n)$ grows on average, and in general behaves very similarly to $\tau(n)$ (and in particular the answer to the first question is yes). Tao suggests that this was a mistaken conjecture of Erdős, which he soon corrected a year later to [448].

Indeed, in [Er82e] Erdős recalls this conjecture and observes that it is indeed trivial that $G(n)\to \infty$ for almost all $n$, and notes that he and Tenenbaum proved that $G(n)/\tau(n)$ has a continuous distribution function.

Additional thanks to: Terence Tao
SOLVED
Let $k\geq 4$. If $\mathcal{F}$ is a family of subsets of $\{1,\ldots,n\}$ with $\lvert A\rvert=k$ for all $A\in \mathcal{F}$ and $\lvert \mathcal{F}\rvert >\binom{n-2}{k-2}$ then there are $A,B\in\mathcal{F}$ such that $\lvert A\cap B\rvert=1$.
A conjecture of Erdős and Sós. Katona (unpublished) proved this when $k=4$, and Frankl [Fr77] proved this for all $k\geq 4$.

See also [703].

SOLVED - $250
Let $r\geq 1$ and define $T(n,r)$ to be maximal such that there exists a family $\mathcal{F}$ of subsets of $\{1,\ldots,n\}$ of size $T(n,r)$ such that $\lvert A\cap B\rvert\neq r$ for all $A,B\in \mathcal{F}$.

Estimate $T(n,r)$ for $r\geq 2$. In particular, is it true that for every $\epsilon>0$ there exists $\delta>0$ such that for all $\epsilon n<r<(1/2-\epsilon) n$ we have \[T(n,r)<(2-\delta)^n?\]

It is trivial that $T(n,0)=2^{n-1}$. Frankl and Füredi [FrFu84] proved that, for fixed $r$ and $n$ sufficiently large in terms of $r$, the maximal $T(n,r)$ is achieved by taking \[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\rvert> \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\] when $n+r$ is odd, and \[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\backslash \{1\}\rvert\geq \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\] when $n+r$ is even. (Frankl [Fr77b] had earlier proved this for $r=1$ and all $n$.)

An affirmative answer to the second question implies that the chromatic number of the unit distance graph in $\mathbb{R}^n$ (with two points joined by an edge if the distance between them is $1$) grows exponentially in $n$, which was proved by alternative methods by Frankl and Wilson [FrWi81] - see [704].

The answer to the second question is yes, proved by Frankl and Rödl [FrRo87].

See also [702].

Additional thanks to: Mehtaab Sawhney
SOLVED - $100
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.

Is it true that, if $P_n$ is the path of length $n$, then \[\hat{R}(P_n)/n\to \infty\] and \[\hat{R}(P_n)/n^2 \to 0?\] Is it true that, if $C_n$ is the cycle with $n$ edges, then \[\hat{R}(C_n) =o(n^2)?\]

A problem of Erdős, Faudree, Rousseau, and Schelp [EFRS78b].

Answered by Beck [Be83b], who proved that in fact $\hat{R}(P_n)\ll n$ and $\hat{R}(C_n)\ll n$.

SOLVED
Is it true that, almost surely, a random graph on $n$ vertices with $\geq (\tfrac{1}{2}+\epsilon)n\log n$ edges is Hamiltonian?
A conjecture of Erdős and Rényi [ErRe66], who proved that almost surely such a graph has a perfect matching (when $n$ is even).

This is true. Pósa [Po76] proved that almost surely a random graph with $\geq Cn\log n$ edges is Hamiltonian for some large constant $C$, and Komlós and Szemerédi [KoSz83] proved that \[\geq \frac{1}{2}n\log n+\frac{1}{2}n\log\log n+w(n)n\] edges suffices, for any function $w$ which $\to \infty$ as $n\to \infty$.

OPEN
If $\pi(x)$ counts the number of primes in $[1,x]$ then is it true that (for large $x$ and $y$) \[\pi(x+y) \leq \pi(x)+\pi(y)?\]
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}.\]

SOLVED
If $A,B,C\in \mathbb{R}^2$ form a triangle and $P$ is a point in the interior then, if $X$ where the perpendicular from $P$ to $AB$ meets the triangle, and similarly for $Y$ and $Z$, then \[\overline{PA}+\overline{PB}+\overline{PC}\geq 2(\overline{PX}+\overline{PY}+\overline{PZ}).\]
Conjectured by Erdős in 1932 (according to [Er82e]) and proved by Mordell soon afterwards, now known as the Erdős-Mordell inequality.
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}=\infty?\]
The answer is yes, proved by Ruzsa [Ru78].

See also [245] for the sum set analogue.

SOLVED
There is a function $f:(1/2,\infty)\to \mathbb{R}$ such that $f(c)\to 0$ as $c\to 1/2$ and $f(c)\to 1$ as $c\to \infty$ and every random graph with $n$ vertices and $cn$ edges has (with high probability) a path of length at least $f(c)n$.
This was proved by Ajtai, Komlós, and Szemerédi [AKS81].
OPEN
Let $m(n)$ be minimal such that there is an $n$-uniform hypergraph with $m(n)$ edges which is $3$-chromatic. Estimate $m(n)$.
In other words, the hypergraph does not have Property B. Property B means that there is a set $S$ which intersects all edges and yet does not contain any edge.

It is known that $m(2)=3$, $m(3)=7$, and $m(4)=23$. Erdős proved \[2^n \ll m(n) \ll n^2 2^n\] (the lower bound in [Er63b] and the upper bound in [Er64e]). Erdős conjectured that $m(n)/2^n\to \infty$, which was proved by Beck [Be78], who proved \[n^{1/3}2^n \ll m(n).\] Radhakrishnan and Srinivasan [RaSr00] improved this to \[\sqrt{\frac{n}{\log n}}2^n \ll m(n).\]

OPEN
Let $f(n)$ be minimal such that there is a tournament (a complete directed graph) on $f(n)$ vertices such that every set of $n$ vertices is dominated by at least one other vertex. Estimate $f(n)$.
Schütte asked Erdős this in the early 1960s.

It is easy to check that $f(1)=3$ and $f(2)=7$. Erdős [Er63c] proved \[2^{n+1}-1 \leq f(n) \ll n^22^n.\] Szekeres and Szekeres [SzSz65] proved that $f(3)=19$ and \[n2^n \ll f(n).\]

OPEN
Let $n=p^2+p+1$ for some prime power $p$, and let $A_1,\ldots,A_t\subseteq \{1,\ldots,n\}$ be a block design (so that every pair $x,y\in \{1,\ldots,n\}$ is contained in exactly one $A_i$).

Is it true that if $t>n$ then $t\geq n+p$?

A conjecture of Erdős and Sós. The classic finite geometry construction shows that $t=n$ is possible. A theorem of Erdős and de Bruijn [dBEr48] states that $t\geq n$.

In [Er82e] Erdős writes that he and Sós proved some special cases of this and the full conjecture was proved by Wilson, but I cannot find either reference.

In general, one can ask what the possible values of $t$ are, for a given $n$.

SOLVED
If $G$ is a graph with $n$ vertices and $>n^2/4$ edges then it contains a triangle on $x,y,z$ such that \[d(x)+d(y)+d(z) \geq \frac{3}{2}n.\]
A conjecture of Bollobás and Erdős. This was proved by Edwards [Ed78].
SOLVED
Every graph with $n$ vertices and $>n^2/4$ edges contains an edge which is in at least $n/6$ triangles.
A conjecture of Bollobás and Erdős. This was proved independently by Edwards (unpublished) and Hadziivanov and Nikiforov [KhNi79].

For a more general problem see [80].

SOLVED
Is there an entire function $f:\mathbb{C}\to \mathbb{C}$ such that, for any infinite sequence $n_1<n_2<\cdots$, the set \[\{ z: f^{(n_k)}(z)=0 \textrm{ for some }k\geq 1\}\] is everywhere dense?
Erdős [Er82e] writes that this was solved in the affirmative 'more than ten years ago', but gives no reference or indication who solved it. From context he seems to attribute this to Barth and Schneider [BaSc72], but this paper contains no such result.
SOLVED
Let $f:\mathbb{R}\to \mathbb{R}$ be such that $f(x+h)-f(x)$ is continous for every $h>0$. Is it true that \[f=g+h\] for some continuous $g$ and additive $h$ (i.e. $h(x+y)=h(x)+h(y)$)?
A conjecture of Erdős from the early 1950s. Answered in the affirmative by de Bruijn [dB51].

See also [908].

SOLVED
Let $f:\mathbb{R}\to \mathbb{R}$ be such that $f(x+h)-f(x)$ is measurable for every $h>0$. Is it true that \[f=g+h+r\] where $g$ is continuous, $h$ is additive (so $h(x+y)=h(x)+h(y)$), and $r(x+h)-r(x)=0$ for every $h$ and almost all (depending on $h$) $x$?
A conjecture of de Bruijn and Erdős. Answered in the affirmative by Laczkovich [La80].

See also [907].

SOLVED
Let $n\geq 2$. Is there a space $S$ of dimension $n$ such that $S^2$ also has dimension $n$?
The space of rational points in Hilbert space has this property for $n=1$. This was proved for general $n$ by Anderson and Keisler [AnKe67].
SOLVED
Does every connected set in $\mathbb{R}^n$ contain a connected subset which is not a point and not homeomorphic to the original set?

If $n\geq 2$ does every connected set in $\mathbb{R}^n$ contain more than $2^{\aleph_0}$ many connected subsets?

Asked by Erdős in the 1940s, who thought the answer to both questions is yes. The answer to both is in fact no, as shown by Rudin [Ru58] (conditional on the continuum hypothesis).
OPEN
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$.

Is there a function $f$ such that $f(x)/x\to \infty$ as $x\to \infty$ such that, for all large $C$, if $G$ is a graph with $n$ vertices and $e\geq Cn$ edges then \[\hat{R}(G) > f(C) e?\]