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].
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].
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 [687].
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]).
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$.
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.
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].
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.
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].
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.
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$.
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 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.
See also [3].
This problem is #9 in Ramsey Theory in the graphs problem collection. See also [800].
In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then \[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]
This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]
This problem is #2 in Ramsey Theory in the graphs problem collection.
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$.
The answer is yes, proved by Freiman [Fr73].
See also [899] for the difference set analogue.
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$.
This problem has consequences for [894].
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)}?\]
Konyagin [Ko01] proved the strong upper bound \[N(X,\delta) \ll_\delta N^{1/2}.\]
See also [466] for lower bounds.
Is there some $\delta>0$ such that \[\lim_{x\to \infty}N(X,\delta)=\infty?\]
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$)?
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]).
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].
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.
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)?\]
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.
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?\]
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].
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)?\]
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$.
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}.\]
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).\]
Is it true that if $t>n$ then $t\geq n+p$?
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$.
If $n\geq 2$ does every connected set in $\mathbb{R}^n$ contain more than $2^{\aleph_0}$ many connected subsets?
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?\]