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].
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}.\]
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]).
The sequence of such numbers is A006286 in the OEIS.
Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).
Granville and Soundararajan [GrSo98] have proved that this is very related to the problem of finding primes $p$ for which $2^p\equiv 2\pmod{p^2}$ (for example this conjecture implies there are infinitely many such $p$).
Erdős often asked this under the weaker assumption that $n$ is not divisible by $4$. Erdős thought that proving this with two powers of 2 is perhaps easy, and could prove that it is true (with a single power of two) for almost all $n$.
Is it true that \[\sum_{n\in A}\frac{1}{n}<\infty?\]
An example of an $A$ with this property where \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0\] is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.
Elsholtz and Planitzer [ElPl17] have constructed such an $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert\gg \frac{N^{1/2}}{(\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2}.\]
Schoen [Sc01] proved that if all elements in $A$ are pairwise coprime then \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N^{2/3}\] for infinitely many $N$. Baier [Ba04] has improved this to $\ll N^{2/3}/\log N$.
For the finite version see [13].
For the infinite version see [12].
In [Er92c] Erdős asks about the general version where $a\nmid (b_1+\cdots+b_r)$ for $a<\min(b_1,\ldots,b_r)$, and whether $\lvert A\rvert \leq N/(r+1)+O(1)$.
Is it true that for all $\epsilon>0$ and large $N$ \[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/2-\epsilon}.\] Is it true that \[\lvert \{1,\ldots,N\}\backslash B\rvert =o(N^{1/2})?\]
Erdös and Freud investigated the finite analogue in 'a recent Hungarian paper', proving that there exists $A\subseteq \{1,\ldots,N\}$ such that the number of integers not representable in exactly one way as the sum of two elements from $A$ is $<2^{3/2}N^{1/2}$, and suggest the constant $2^{3/2}$ is perhaps best possible.
Tao [Ta23] has proved that this series does converge assuming a strong form of the Hardy-Littlewood prime tuples conjecture.
In [Er98] Erdős further conjectures that \[\sum_{n=1}^\infty (-1)^n \frac{1}{n(p_{n+1}-p_n)}\] converges and \[\sum_{n=1}^\infty (-1)^n \frac{1}{p_{n+1}-p_n}\] diverges. He further conjectures that \[\sum_{n=1}^\infty (-1)^n \frac{1}{n(p_{n+1}-p_n)(\log\log n)^c}\] converges for every $c>0$, and reports that he and Nathanson can prove this for $c>2$ (and conditionally for $c=2$).
Blecksmith, Erdős, and Selfridge [BES99] proved that the number of such primes is \[\ll_A \frac{x}{(\log x)^A}\] for every $A>0$, and Elsholtz [El03] improved this to \[\ll x\exp(-c(\log\log x)^2)\] for every $c<1/8$.
Are there infinitely many practical $m$ such that \[h(m) < (\log\log m)^{O(1)}?\] Is it true that $h(n!)<n^{o(1)}$? Or perhaps even $h(n!)<(\log n)^{O(1)}$?
The sequence of practical numbers is A005153 in the OEIS.
Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). Hindman has proved the conjecture for $n<10$. Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large $n$.
In [Er97d] Erdős asks how large $\chi(G)$ can be if instead of asking for the copies of $K_n$ to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge.
In [Er81] offered \$1000 for a proof or disproof even just in the special case when $k=3$, which he expected 'contains the whole difficulty'. He also wrote 'I really do not see why this question is so difficult'.
The usual focus is on the regime where $k=O(1)$ is fixed (say $k=3$) and $n$ is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KRT99] have shown \[f(n,k)=(1+O_n(k^{-1/2^n}))k^n.\]
Is it true that \[f(n) \ll n?\]
This problem was solved by Kahn [Ka94] who proved the upper bound $f(n) \ll n$. The Erdős-Lovász lower bound of $\frac{8}{3}n-O(1)$ has not been improved, and it has been speculated (see e.g. [Ka94]) that the correct answer is $3n+O(1)$.
Conjectured by Bollobás and Erdős [BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao [FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most \[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]
See also [615].
In [Er92b] Erdős asks, more generally, if a graph on $(2k+1)n$ vertices in which every odd cycle has size $\geq 2k+1$ can be made bipartite by deleting at most $n^2$ edges.
In [Er92b] and [Er97f] Erdős asks more generally: if $r\geq 5$ is odd and a graph has $rn$ vertices and the smallest odd cycle has size $r$ then is the number of cycles of size $r$ at most $n^{r}$?
Tenenbaum asked the weaker variant (still open) where for every $\epsilon>0$ there is some $k=k(\epsilon)$ such that at least $1-\epsilon$ density of all integers have a divisor of the form $a+k$ for some $a\in A$.
The answer is no, as proved by Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], who (among other results) prove that if \[1< C \leq N^{\frac{\log\log\log N}{4\log\log N}}\] then, for any $N\leq n_1<\cdots< n_k\leq CN$, the density of integers not covered for any fixed choice of residue classes is at least \[\prod_{i}(1-1/n_i)\] (and this density is achieved for some choice of residue classes as above).
Another stronger conjecture would be that the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.
Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.
See also [40].
An explicit construction was given by Jain, Pham, Sawhney, and Zakharov [JPSZ24].
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?\]
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.\]
This is extremely false, as shown by Konieczny [Ko15], who both constructs an explicit permutation with $S(\pi) \geq n^2/4$, and also shows that for a random permutation we have \[S(\pi)\sim \frac{1+e^{-2}}{4}n^2.\]
Ruzsa has observed that this follows immediately from the stronger fact proved by Plünnecke [Pl70] that (under the same assumptions) \[d_S(A+B)\geq \alpha^{1-1/k}.\]
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$.
Can a lacunary set $A\subset\mathbb{N}$ be an essential component?
The Schnirelmann density is defined by \[d_s(A) = \inf_{N\geq 1}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N}.\]
This is a stronger propery than $B$ being an essential component (see [37]). Linnik [Li42] gave the first construction of an essential component which is not an additive basis.
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$.
Indeed, we must trivially have $\sum_{d|n_k}1/d \geq k$, or else there is a greedy colouring as a counterexample. Since $\prod_{p}(1+1/p^2)$ is finite we must have $\prod_{p|n_k}(1+1/p)\gg k$. To achieve the minimal $\prod_{p|n_k}p$ we take the product of primes up to $T$ where $\prod_{p\leq T}(1+1/p)\gg k$; by Mertens theorems this implies $T\geq C^{k}$ for some constant $C>1$, and hence $n_k\geq \prod_{p\mid n_k}p\geq \exp(cC^k)$ for some $c>0$.
Solved by Tao [Ta23b], who proved that \[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]
In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.
See also [694].
There is likely nothing special about the integers in this question, and indeed Erdős and Szemerédi also ask a similar question about finite sets of real or complex numbers. The current best bound for sets of reals is the same bound of Rudnev and Stevens above. The best bound for complex numbers is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}},\] due to Solymosi [So05].
One can in general ask this question in any setting where addition and multiplication are defined (once one avoids any trivial obstructions such as zero divisors or finite subfields). For example, it makes sense for subsets of finite fields. The current record is that there exists $c>0$ such that if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{c}$ then \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}+o(1)},\] due to Mohammadi and Stevens [MoSt23].
There is also a natural generalisation to higher-fold sum and product sets. For example, in [ErSz83] (and in [Er91]) Erdős and Szemerédi also conjecture that for any $m\geq 2$ and finite set of integers $A$ \[\max( \lvert mA\rvert,\lvert A^m\rvert)\gg \lvert A\rvert^{m-o(1)}.\] See [53] for more on this generalisation and [808] for a stronger form of the original conjecture. See also [818] for a special case.
Erdős and Szemerédi proved that there exist arbitrarily large sets $A$ such that the integers which are the sum or product of distinct elements of $A$ is at most \[\exp\left(c (\log \lvert A\rvert)^2\log\log\lvert A\rvert\right)\] for some constant $c>0$.
See also [52].
Burr and Erdős [BuEr85] showed that there exists a constant $c>0$ such that it cannot be true that \[\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2\] for all large $N$ and that there exists a Ramsey $2$-complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert < (2\log_2N)^3.\] Improve either of these bounds.
Solved by Conlon, Fox, and Pham [CFP21], who constructed for every $r\geq 2$ an $r$-Ramsey complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll r(\log N)^2,\] and showed that this is best possible, in that there exists some constant $c>0$ such that if $A\subset \mathbb{N}$ satisfies \[\lvert A\cap \{1,\ldots,N\}\rvert \leq cr(\log N)^2\] for all large $N$ then $A$ cannot be $r$-Ramsey complete.
Erdős later asked ([Er92b] and [Er95]) if the conjecture remains true provided $N\geq (1+o(1))p_k^2$ (or, in a weaker form, whether it is true for $N$ sufficiently large depending on $k$).
See also [534].
The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.
See also [65].
A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.
He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.
Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős wrote [Er87] that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.
David Penman has observed that this is certainly true if the graph has uncountable chromatic number, since by a result of Erdős and Hajnal [ErHa66] such a graph must contain arbitrarily large finite complete bipartite graphs (see also Theorem 3.17 of Reiher [Re24]).
Zach Hunter has observed that this follows from the work of Liu and Montgomery [LiMo20]: if $G$ has infinite chromatic number then, for infinitely many $r$, it must contain some finite connected subgraph $G_r$ with chromatic number $r$ (via the de Bruijn-Erdős theorem [dBEr51]). Each $G_r$ contains some subgraph $H_r$ with minimum degree at least $r-1$, and hence via Theorem 1.1 of [LiMo20] there exists some $\ell_r\geq r^{1-o(1)}$ such that $H_r$ contains a cycle of every even length in $[(\log \ell)^8,\ell]$.
See also [64].
This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove a much stronger result: if the average degree of $G$ is sufficiently large then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.
An infinite tree with minimum degree $3$ shows that the answer is trivially false for infinite graphs.
See also the entry in the graphs problem collection.
See also [57].
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.
Pratt [Pr24] has proved this is irrational, conditional on a uniform version of the prime $k$-tuples conjecture.
Tao has observed that this is a special case of [257], since \[\sum_{n\geq 2}\frac{\omega(n)}{2^n}=\sum_p \frac{1}{2^p-1}.\]
Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although he conjectured that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.
Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.
Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.
See also [922] and the entry in the graphs problem collection.
Rödl [Ro82] has proved this for hypergraphs, and also proved there is such a graph (with chromatic number $\aleph_0$) if $f(n)=\epsilon n$ for any fixed constant $\epsilon>0$.
It is open even for $f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$ (see [111]).
The answer is yes, proved by Gruslys and Letzter [GrLe20].
In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c>1/24$.
A shorter and simpler proof of an upper bound of the strength $4-c$ for some constant $c>0$ (and a generalisation to the case of more than two colours) was given by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba [BBCGHMST24].
This problem is #3 in Ramsey Theory in the graphs problem collection.
In [Er69b] Erdős asks for even a construction whose largest clique or independent set has size $o(n^{1/2})$, which is now known.
Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size \[\geq 2^{(\log\log n)^{C}}\] for some constant $C>0$. Li [Li23b] has recently improved this to \[\geq (\log n)^{C}\] for some constant $C>0$.
This problem is #4 in Ramsey Theory in the graphs problem collection.
Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?
Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or $f_c(n)\gg \log n$?
Edwards (unpublished) and Khadziivanov and Nikiforov [KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see [905]).
Fox and Loh [FoLo12] proved that \[f_c(n) \leq n^{O(1/\log\log n)}\] for all $c<1/4$, disproving the first conjecture of Erdős.
The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.
See also [600] and the entry in the graphs problem collection.
A split graph is one where the vertices can be split into a clique and an independent set. Every split graph is chordal. Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.
Proved by Ahlswede and Khachatrian [AhKh97], who more generally showed the following. Let $2\leq t\leq k\leq m$ and let $r\geq 0$ be such that \[\frac{1}{r+1}\leq \frac{m-2k+2t-2}{(t-1)(k-t+1)}< \frac{1}{r}.\] The largest possible family of subsets of $[m]$ of size $k$, such that the pairwise intersections have size at least $t$, is the family of all subsets of $[m]$ of size $k$ which contain at least $t+r$ elements from $\{1,\ldots,t+2r\}$.
Prove that $f(n)=o(2^n)$.
Prove that $f(n)/2^{n/2}\to \infty$.
One can also ask about the existence and value of $\lim f(n)^{1/n}$.
A similar question can be asked for other even cycles.
See also [666] and the entry in the graphs problem collection.
Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$?
Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.
This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.
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.
Is it true that $f(n)\leq n^{o(1)}$? Or even $f(n) < n^{c/\log\log n}$ for some constant $c>0$?
The set of lattice points imply $f(n) > n^{c/\log\log n}$ for some constant $c>0$. Erdős offered \$500 for a proof that $f(n) \leq n^{o(1)}$ but only \$100 for a counterexample.
It is trivial that $f(n) \ll n^{1/2}$. A result of Pach and Sharir implies $f(n) \ll n^{2/5}$.
Fishburn (personal communication to Erdős) proved that $6$ is the smallest $n$ such that $f(n)=3$ and $8$ is the smallest $n$ such that $f(n)=4$, and suggested that the lattice points may not be best example.
See also [754].
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].
Edelsbrunner and Hajnal [EdHa91] have constructed $n$ such points with $2n-7$ pairs distance $1$ apart. (This disproved an early stronger conjecture of Erdős and Moser, that the true answer was $\frac{5}{3}n+O(1)$.)
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.
Erdős [Er94b] wrote 'I could not prove it but felt that it should not be hard. To my great surprise both B. H. Sendov and M. Simonovits doubted the truth of this conjecture.' In [Er94b] he offers \$100 for a counterexample but only \$50 for a proof.
The stated problem is false for $n=4$, for example taking the points to be vertices of a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor [BeFo99].
See also [103].
Grünbaum [Gr76] constructed an example with $\gg n^{3/2}$ such lines. Erdős speculated this may be the correct order of magnitude. This is false: Solymosi and Stojaković [SoSt13] have constructed a set with no five on a line and at least \[n^{2-O(1/\sqrt{\log n})}\] many lines containing exactly four points.
See also [102]. A generalisation of this problem is asked in [588].
It is easy to see that $h_c(n) \ll_c n^{1/2}$, and Erdős originally suggested that perhaps a similar lower bound $h_c(n)\gg_c n^{1/2}$ holds. Zach Hunter has pointed out that this is false, even replacing $>3$ points on each line with $>k$ points: consider the set of points in $\{1,\ldots,m\}^d$ where $n\approx m^d$. These intersect any line in $\ll_d n^{1/d}$ points, and have $\gg_d n^2$ many pairs of points each of which determine a line with at least $k$ points. This is a construction in $\mathbb{R}^d$, but a random projection into $\mathbb{R}^2$ preserves the relevant properties.
This construction shows that $h_c(n) \ll n^{1/\log(1/c)}$.
See also [99].
In [Er75h] Erdős also asks how many such unit circles there must be if the points are in general position.
It is trivial from the Cauchy-Schwarz inequality that $f(k^2)=k$. Erdős also asks for which $n$ is it true that $f(n+1)=f(n)$.
It is easy to see that $f(k^2+1)\geq k$, by first dividing the unit square into $k^2$ smaller squares of side-length $1/k$, and then replacing one square by two smaller squares of side-length $1/2k$. Halász [Ha84] gives a construction that shows $f(k^2+2)\geq k+\frac{1}{k+1}$, and in general, for any $c\geq 1$, \[f(k^2+2c+1)\geq k+\frac{c}{k}\] and \[f(k^2+2c)\geq k+\frac{c}{k+1}.\] Halász also considers the variants where we replace a square by a parallelogram or triangle.
Erdős and Soifer [ErSo95] and Campbell and Staton [CaSt05] have conjectured that, in general, for any integer $-k<c<k$, $f(k^2+2c+1)=k+\frac{c}{k}$, and proved the corresponding lower bound. Praton [Pr08] has proved that this general conjecture is equivalent to $f(k^2+1)=k$.
Baek, Koizumi, and Ueoro [BKU24] have proved $g(k^2+1)=k$, where $g(\cdot)$ is defined identically to $f(\cdot)$ with the additional assumption that all squares have sides parallel to the sides of the unit square. More generally, they prove that $g(k^2+2c+1)=k+c/k$ for any $-k<c<k$, which determines all values of $g(\cdot)$.
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.
In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]
See also the entry in the graphs problem collection and [740] for the infinitary version.
A theorem of de Bruijn and Erdős [dBEr51] implies that, if $G$ has infinite chromatic number, then $G$ has a finite subgraph of chromatic number $n$ for every $n\geq 1$.
In [Er95d] Erdős suggests this is true, although such an $F$ must grow faster than the $k$-fold iterated exponential function for any $k$.
What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$?
On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In [Er81] Erdős conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.
See also [74].
See also the entry in the graphs problem collection - on this site the problem replaces transitive tournament with directed path, but Zach Hunter and Raphael Steiner have a simple argument that proves, for this alternative definition, that $k(n,m)=(n-1)(m-1)$.
Disproved by Janzer [Ja21] who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]
See also [146] and [147] and the entry in the graphs problem collection.
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.
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$.
Estimate $h(n)$ as well as possible.
The answer is no, as independently shown by Schipperus [Sc99] (published in [Sc10]) and Darby [Da99].
For example, Larson [La00] has shown that this is false when $\alpha=\omega^{\omega^2}$ and $n=5$. There is more background and proof sketches in Chapter 2.9 of [HST10], by Hajnal and Larson.
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.
This is true if $A$ is unbounded or dense in some interval. It therefore suffices to prove this when $A=\{a_1>a_2>\cdots\}$ is a countable strictly monotone sequence which converges to $0$.
Steinhaus [St20] has proved this is false whenever $A$ is a finite set.
This conjecture is known in many special cases (but, for example, it is is open when $A=\{1,1/2,1/4,\ldots\}$. For an overview of progress we recommend a nice survey by Svetic [Sv00] on this problem. A survey of more recent progress was written by Jung, Lai, and Mooroogen [JLM24].
Erdős (and independently Hall [Ha96] and Montgomery) also asked about $F(N)$, the size of the largest $A\subseteq\{1,\ldots,N\}$ such that the product of no odd number of $a\in A$ is a square. Ruzsa [Ru77] observed that $1/2<\lim F(N)/N <1$. Granville and Soundararajan [GrSo01] proved an asymptotic \[F(N)=(1-c+o(1))N\] where $c=0.1715\ldots$ is an explicit constant.
This problem was answered in the negative by Tao [Ta24], who proved that for any $k\geq 4$ there is some constant $c_k>0$ such that $F_k(N) \leq (1-c_k+o(1))N$.
See also [888].
In [Er92b] Erdős wrote 'last year I made the following silly conjecture': every integer $n$ can be written as the sum of distinct integers of the form $2^k3^l$, none of which divide any other. 'I mistakenly thought that this was a nice and difficult conjecture but Jansen and several others found a simple proof by induction.' This simple proof is as follows: one proves the stronger fact that such a representation always exists, and moreover if $n$ is even then all the summands can be taken to be even: if $n=2m$ we are done applying the inductive hypothesis to $m$. Otherwise if $n$ is odd then let $3^k$ be the largest power of $3$ which is $\leq n$ and apply the inductive hypothesis to $n-3^k$ (which is even).
In [Er92b] Erdős makes the stronger conjecture (for $a=2$, $b=3$, and $c=5$) that, for any $\epsilon>0$, all large integers $n$ can be written as the sum of distinct integers $b_1<\cdots <b_t$ of the form $2^k3^l5^m$ where $b_t<(1+\epsilon)b_1$.
See also [845].
See also [125].
Does $A+B$ have positive density?
Keevash and Sudakov [KeSu06] have proved this under the additional assumption that $G$ has at most $n^2/12$ edges.
The obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), provided $N \leq C^n$ for some absolute constant $C>1$. This implies $R(n;3,2) \geq C^{n}$, contradicting the conjecture.
Perhaps Erdős had a different problem in mind, but it is not clear what that might be. It would presumably be one where the natural probabilistic argument would deliver a bound like $C^{\sqrt{n}}$ as Erdős and Gyárfás claim to have achieved via the probabilistic method.
How large can the chromatic number and clique number of this graph be? In particular, can the chromatic number be infinite?
See also [213].
It may be true that there are at least $n^{1-o(1)}$ many such distances. In [Er97e] Erdős offers \$100 for 'any nontrivial result'.
What is the order of growth of $f(n)$? Does $f(n)/\sqrt{n}\to \infty$?
Simonovits observed that the subsets of $[3m-1]$ of size $m$, two sets joined by edge if and only if they are disjoint, forms a triangle-free graph of diameter $2$ which is regular of degree $\binom{2m-1}{m}$. This construction proves that \[f(n) \leq n^{(1+o(1))\frac{2}{3H(1/3)}}=n^{0.7182\cdots},\] where $H(x)$ is the binary entropy function. In [Er97b] Erdős encouraged the reader to try and find a better construction.
In this note Alon provides a simple construction that proves $f(n) \ll \sqrt{n\log n}$: take a triangle-free graph with independence number $\ll \sqrt{n\log n}$ (the existence of which is the lower bound in [165]) and add edges until it has diameter $2$; the neighbourhood of any set is an independent set and hence the maximum degree is still $\ll \sqrt{n\log n}$.
Hanson and Seyffarth [HaSe84] proved that $f(n)\leq (\sqrt{2}+o(1))\sqrt{n}$ using a Cayley graph on $\mathbb{Z}/n\mathbb{Z}$, with the generating set given by some symmetric complete sum-free set of size $\sim \sqrt{n}$. An alternative construction of such a complete sum-free set was given by Haviv and Levy [HaLe18].
Füredi and Seress [FuSe94] proved that $f(n)\leq (\frac{2}{\sqrt{3}}+o(1))\sqrt{n}$.
The precise asymptotics of $f(n)$ are unknown; Alon believes that the truth is $f(n)\sim \sqrt{n}$.
Can $G$ be made into a triangle-free graph with diameter $2$ by adding at most $\delta n^2$ edges?
In this note Alon solves this problem in a strong form, in particular proving that a triangle-free graph on $n$ vertices with maximum degree $<n^{1/2-\epsilon}$ can be made into a triangle-free graph with diameter $2$ by adding at most $O(n^{2-\epsilon})$ edges.
See also [618].
Answered in the negative by Tao [Ta24c], who proved that for any large $n$ there exists a set of $n$ points in $\mathbb{R}^2$ such that any four points determine at least give distinct distances, yet there are $\ll n^2/\sqrt{\log n}$ distinct distances in total. Tao discusses his solution in a blog post.
In [Er82c] he further conjectures that, if $m,k$ are fixed and $n$ is sufficiently large, then there must be at least $k$ distinct primes $p$ such that \[p\mid m(m+1)\cdots (m+n)\] and yet $p^2$ does not divide the right-hand side.
See also [364].
See also [3].
The existence of such progressions for small $k$ has been verified for $k\leq 10$, see the Wikipedia page. It is open, even for $k=3$, whether there are infinitely many such progressions.
See also [219].
The best known upper bounds for $r_k(N)$ are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$. An asymptotic formula is still far out of reach, even for $k=3$.
In [Er73] mentions an unpublished proof of Haight that \[\lim \frac{\lvert A\cap [1,x]\rvert}{x}=0\] holds if the elements of $A$ are independent over $\mathbb{Q}$.
See also [858].
The weaker conjecture that there exists some $c>0$ such that $(2-c)\Delta^2$ sets suffice was proved by Molloy and Reed [MoRe97], who proved that $1.998\Delta^2$ sets suffice (for $\Delta$ sufficiently large). This was improved to $1.93\Delta^2$ by Bruhn and Joos [BrJo18] and to $1.835\Delta^2$ by Bonamy, Perrett, and Postle [BPP22]. The best bound currently available is \[1.772\Delta^2,\] proved by Hurley, de Joannis de Verclos, and Kang [HJK22].
Erdős and Nešetřil also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved independently by Chung-Trotter and Gyárfás-Tuza.
Does $c(n)^{1/n}\to \alpha$ for some $\alpha <2$?
Solved by Bradač [Br24], who proved that $\alpha=\lim c(n)^{1/n}$ exists and \[\alpha \leq 2^{H(1/3)}=1.8899\cdots,\] where $H(\cdot)$ is the binary entropy function. Seymour's construction proves that $\alpha\geq 3^{1/3}=1.442\cdots$. Bradač conjectures that this lower bound is the true value of $\alpha$.
This problem is #17 in Ramsey Theory in the graphs problem collection.
For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?
Erdős believed there might be just one jump, occcurring at $\alpha=0$.
Conlon, Fox, and Sudakov [CFS11] have proved that, for any fixed $\alpha>0$, \[F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.\] Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.
For all $\alpha>0$ it is known that \[F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.\] See also [563].
Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, \[F(n,\alpha)\sim c_\alpha \log n\] for some constant $c_\alpha$.
This problem is #9 in Ramsey Theory in the graphs problem collection. See also [800].
See also [544].
This problem is #5 in Ramsey Theory in the graphs problem collection.
Is \[\lim_{k\to \infty}\frac{f(k)}{\log W(k)}=\infty\] where $W(k)$ is the van der Waerden number?
Moreira [Mo17] has proved that in any finite colouring of $\mathbb{N}$ there exist $x,y$ such that $\{x,x+y,xy\}$ are all the same colour.
Alweiss [Al23] has proved that, in any finite colouring of $\mathbb{Q}\backslash \{0\}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour. Bowen and Sabok [BoSa22] had proved this earlier for the first non-trivial case of $\lvert A\rvert=2$.
Sets known to be Ramsey include vertices of $k$-dimensional rectangles [EGMRSS73], non-degenerate simplices [FrRo90], trapezoids [Kr92], and regular polygons/polyhedra [Kr91].
Proved by Sárkzözy [Sa85] for all sufficiently large $n$, and by Granville and Ramaré [GrRa96] for all $n\geq 5$.
More generally, if $f(n)$ is the largest integer such that, for some prime $p$, we have $p^{f(n)}$ dividing $\binom{2n}{n}$, then $f(n)$ should tend to infinity with $n$. Can one even disprove that $f(n)\gg \log n$?
Is it true that, for every $\mathcal{F}$, there exists $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]
This is trivially true if $\mathcal{F}$ does not contain any bipartite graphs, since by the Erdős-Stone theorem if $H\in\mathcal{F}$ has minimal chromatic number $r\geq 2$ then \[\mathrm{ex}(n;H)=\mathrm{ex}(n;\mathcal{F})=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}.\] Erdős and Simonovits observe that this is false for infinite families $\mathcal{F}$, e.g. the family of all cycles.
See also [575] and the entry in the graphs problem collection.
A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.
See also [483].
The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.
Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.
See also [583].
The answer is yes, which is a corollary of the density Hales-Jewett theorem, proved by Furstenberg and Katznelson [FuKa91].
See also [789].
Erdős and Graham asked this with just any $k$-term arithmetic progression in blue (not necessarily with distance $1$), but Alon has pointed out that in fact no such $k$ exists: in any red/blue colouring of the integer points on a line either there are two red points distance $1$ apart, or else the set of blue points and the same set shifted by $1$ cover all integers, and hence by van der Waerden's theorem there are arbitrarily long blue arithmetic progressions.
It seems most likely, from context, that Erdős and Graham intended to restrict the blue arithmetic progression to have distance $1$ (although they do not write this restriction in their papers).
This is false; Kovač [Ko23] provides an explicit (and elegantly simple) colouring using 25 colours such that no colour class contains the vertices of a rectangle of area $1$. The question for parallelograms remains open.
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 equivalent to one on 'abelian squares' (see [231]). In particular $A$ can be interpreted as an infinite string over an alphabet with $d$ letters (each letter describining which of the $d$ possible steps is taken at each point). An abelian square in a string $s$ is a pair of consecutive blocks $x$ and $y$ appearing in $s$ such that $y$ is a permutation of $x$. The connection comes from the observation that $p,q,r\in A\subset \mathbb{R}^d$ form a three-term arithmetic progression if and only if the string corresponding to the steps from $p$ to $q$ is a permutation of the string corresponding to the steps from $q$ to $r$.
This problem is therefore equivalent to asking for which $d$ there exists an infinite string over $\{1,\ldots,d\}$ with no abelian squares. It is easy to check that in fact any finite string of length $7$ over $\{1,2,3\}$ contains an abelian square.
An infinite string without abelian squares was constructed when $d=4$ by Keränen [Ke92]. We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results, and a blog post by Renan for an entertaining and educational discussion.
These bounds were improved by Croot [Cr03b] who proved \[\frac{N}{L(N)^{\sqrt{2}+o(1)}}< f(N)<\frac{N}{L(N)^{1/6-o(1)}},\] where $f(N)=\exp(\sqrt{\log N\log\log N})$. These bounds were further improved by Chen [Ch05] and then by de la Bretéche, Ford, and Vandehey [BFV13] to \[\frac{N}{L(N)^{1+o(1)}}<f(N) < \frac{N}{L(N)^{\sqrt{3}/2+o(1)}}.\] The latter authors conjecture that the lower bound here is the truth.
That is, for all $d\mid n$ with $d>1$ there is an associated $a_d$ such that every integer is congruent to some $a_d\pmod{d}$, and if there is some integer $x$ with \[x\equiv a_d\pmod{d}\textrm{ and }x\equiv a_{d'}\pmod{d'}\] then $(d,d')=1$.
Adenwalla [Ad25] has proved there are no such $n$.
In general, for any $n$ one can try to choose such $a_d$ to maximise the density of integers so covered, and ask what this density is. This was also investigated by Adenwalla [Ad25].
See also [851].
Is it true that, for almost all $x$, for sufficiently large $n$, we have \[R_{n+1}(x)=R_n(x)+\frac{1}{m},\] where $m$ is minimal such that $m$ does not appear in $R_n(x)$ and the right-hand side is $<x$? (That is, are the best underapproximations eventually always constructed in a 'greedy' fashion?)
Without the 'eventually' condition this can fail for some rational $x$ (although Erdős [Er50b] showed it holds without the eventually for rationals of the form $1/m$). For example \[R_1(\tfrac{11}{24})=\frac{1}{3}\] but \[R_2(\tfrac{11}{24})=\frac{1}{4}+\frac{1}{5}.\]
Kovač [Ko24b] has proved that this is false - in fact as false as possible: the set of $x\in (0,\infty)$ for which the best underapproximations are eventually 'greedy' has Lebesgue measure zero. (It remains an open problem to give any explicit example of a number which is not eventually greedy, despite the fact that almost all numbers have this property.)
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$.
The Sylvester-Gallai theorem implies that there must exist a point where only two lines from $A$ meet. This problem asks whether there must exist three such points which form a triangle (with sides induced by lines from $A$). Füredi and Palásti [FuPa84] showed this is false when $d\geq 4$ is not divisible by $9$. Escudero [Es16] showed this is false for all $d\geq 4$.
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$.
In [Er84] Erdős speculates that perhaps there are $\geq (1+o(1))kn/6$ many such lines, but says 'perhaps [this] is too optimistic and one should first look for a counterexample'. The constant $1/6$ would be best possible here, since there are arrangements of $n$ points with no four points on a line and $\sim n^2/6$ many lines containing three points (see Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84]).
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).
Ascher, Braune, and Turchet [ABT20] have shown that there is a uniform upper bound on the size of such a set, conditional on the Bombieri-Lang conjecture. Greenfeld, Iliopoulou, and Peluse [GIP24] have shown (unconditionally) that any such set must be very sparse, in that if $S\subseteq [-N,N]^2$ has no three on a line and no four on a circle, and all pairwise distances integers, then \[\lvert S\rvert \ll (\log N)^{O(1)}.\]
See also [130].
In fact, such a set does exist, as proved by Jackson and Mauldin [JaMa02]. Their construction depends on the axiom of choice.
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 differences are listed at A256435 on the OEIS.
Solved by Barth and Schneider [BaSc70], who proved that if $A,B\subset\mathbb{R}$ are countable dense sets then there exists a transcendental entire function $f$ such that $f(z)\in B$ if and only if $z\in A$. In [BaSc71] they proved the same result for countable dense subsets of $\mathbb{C}$.
See also [230].
For more details see the paper [BoBo09] of Bombieri and Bourgain and where Kahane's construction is improved to yield such a polynomial with \[P(z)=\sqrt{n}+O(n^{\frac{7}{18}}(\log n)^{O(1)})\] for all $z\in\mathbb{C}$ with $\lvert z\rvert=1$.
See also [228].
Erdős 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.
Estimate \[m_1=\sup \overline{\delta}(A),\] where $A$ ranges over all measurable subsets of $\mathbb{R}^2$ without two points distance $1$ apart. In particular, is $m_1\leq 1/4$?
The trivial upper bound is $m_1\leq 1/2$, since for any unit vector $u$ the sets $A$ and $A+u$ must be disjoint. Erdős' question was solved by Ambrus, Csiszárik, Matolcsi, Varga, and Zsámboki [ACMVZ23] who proved that $m_1\leq 0.247$.
The values of the sum are listed at A074741 on the OEIS.
The sequence of values of $f(n)$ is A109925 on the OEIS.
See also [237].
The limit is infinite for a finite set of primes, which follows from a theorem of Pólya [Po18], that if $P(n)$ is a quadratic integer polynomial without repeated roots then as $n\to \infty$ the largest prime factor of $f(n)$ also approaches infinity. Indeed, if $P$ is a finite set of primes and $(a_i)$ is the set of integers divisible only by primes in $P$, and $a_{i+1}-a_i$ is bounded, then there exists some $k$ such that $a_{i+1}=a_i+k$ infinitely often, which contradicts Pólya's theorem with $f(n)=n(n+k)$.
Tijdeman [Ti73] proved that, if $P$ is a finite set of primes, then \[a_{i+1}-a_i \gg \frac{a_i}{(\log a_i)^C}\] for some constant $C>0$ depending on $P$.
Tijdeman [Ti73] resolved this question, proving that, for any $\epsilon>0$, there exists an infinite set of primes $P$ such that, with $a_i$ defined as above, \[a_{i+1}-a_i \gg a_i^{1-\epsilon}.\]
See also [368].
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]).
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}.\]
The answer is yes, proved by Freiman [Fr73].
See also [899] for the difference set analogue.
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.\]
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).\]
In [Er88c] Erdős notes that Cusick had a simple proof that there do exist infinitely many such $n$. Erdődoes not record what this was, but Kovač has provided the following proof: for every positive integer $m$ and $n=2^{m+1}-m-2$ we have \[\frac{n}{2^n}=\sum_{n<k\leq n+m}\frac{k}{2^k}.\]
This was essentially solved by Hančl [Ha91], who proved that such a sequence needs to satisfy \[\limsup_{n\to \infty} \frac{\log_2\log_2 a_n}{n} \geq 1.\] More generally, if $a_n\ll 2^{2^{n-F(n)}}$ with $F(n)<n$ and $\sum 2^{-F(n)}<\infty$ then $a_n$ cannot be an irrationality sequence.
Kovač and Tao [KoTa24] have proved that any strictly increasing sequence such that $\sum \frac{1}{a_n}$ converges and $\lim a_{n+1}/a_n^2=0$ is not such an irrationality sequence. On the other hand, if \[\liminf \frac{a_{n+1}}{a_n^{2+\epsilon}}>0\] for some $\epsilon>0$ then the above folklore result implies that $a_n$ is such an irrationality sequence.
Kovač and Tao [KoTa24c] have proved that $2^n$ is not such an irrationality sequence. More generally, they prove that any strictly increasing sequence of positive integers such that $\sum\frac{1}{a_n}$ converges and \[\liminf \left(a_n^2\sum_{k>n}\frac{1}{a_k^2}\right) >0 \] is not such an irrationality sequence. In particular, any strictly increasing sequence with $\limsup a_{n+1}/a_n <\infty$ is not such an irrationality sequence.
On the other hand, Kovač and Tao do prove that for any function $F$ with $\lim F(n+1)/F(n)=\infty$ there exists such an irrationality sequence with $a_n\sim F(n)$.
Erdős believed that $a_n^{1/n}\to \infty$ is possible, but $a_n^{1/2^n}\to 1$ is necessary.
This has been almost completely solved by Kovač and Tao [KoTa24], who prove that such a sequence can grow doubly exponentially. More precisely, there exists such a sequence such that $a_n^{1/\beta^n}\to \infty$ for some $\beta >1$.
It remains open whether one can achieve \[\limsup a_n^{1/2^n}>1.\] A folklore result states that $\sum \frac{1}{a_n}$ is irrational whenever $\lim a_n^{1/2^n}=\infty$, and hence such a sequence cannot grow faster than doubly exponentially - the remaining question is the precise exponent possible.
A negative answer was proved by Kovač and Tao [KoTa24], who proved even more: there exists a strictly increasing sequence of positive integers $a_n$ such that \[\sum \frac{1}{a_n+t}\] converges to a rational number for every $t\in \mathbb{Q}$ (with $t\neq -a_n$ for all $n$).
The answer is yes, proved by Kovač [Ko24], who constructs an explicit open ball inside the set. Kovač and Tao [KoTa24] have proved an analogous result for all higher dimensions.
Can the $a_k$ be explicitly determined? How fast do they grow?
Moy [Mo11] has proved that, for all such sequences, for all $\epsilon>0$, $a_k\leq (\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$.
In general, sequences which begin with some initial segment and thereafter are continued in a greedy fashion to avoid three-term arithmetic progressions are known as Stanley sequences.
If we drop the non-empty requirement then Simonovits, Sós, and Graham [SiSoGr80] have shown that \[t\leq \binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1\] and this is best possible.
Is the minimum density achieved when all the $a_i$ are equal?
For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.
Note that since the $k$th prime is $\sim k\log k$ the lower bound $n_k>(1+\epsilon)k\log k$ is best possible here.
Is it true that for every $\epsilon>0$ there exists some $k$ such that, for every choice of congruence classes $a_i$, the density of integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is less than $\epsilon$?
Does this process always terminate if $x$ has odd denominator and $A$ is the set of odd numbers? More generally, for which pairs $x$ and $A$ does this process terminate?
Graham [Gr64b] has shown that $\frac{m}{n}$ is the sum of distinct unit fractions with denominators $\equiv a\pmod{d}$ if and only if \[\left(\frac{n}{(n,(a,d))},\frac{d}{(a,d)}\right)=1.\] Does the greedy algorithm always terminate in such cases?
Graham [Gr64c] has also shown that $x$ is the sum of distinct unit fractions with square denominators if and only if $x\in [0,\pi^2/6-1)\cup [1,\pi^2/6)$. Does the greedy algorithm for this always terminate? Erdős and Graham believe not - indeed, perhaps it fails to terminate almost always.
Alekseyev [Al19] has proved this when $p(x)=x^2$, for all $m>8542$. For example, \[1=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}\] and \[200 = 2^2+4^2+6^2+12^2.\]
This conjecture would follow for all but at most finitely many exceptions if it were known that, for all large $N$, there exists a prime $p\in [N,2N]$ such that $\frac{p+1}{2}$ is also prime.
The smallest $b$ for each $a$ are listed at A375081 at the OEIS.
This was resolved in the affirmative by van Doorn [vD24], who proved $b=b(a)$ always exists, and in fact $b(a) \ll a$. Indeed, if $a\in (3^k,3^{k+1}]$ then one can take $b=2\cdot 3^{k+1}-1$. van Doorn also proves that $b(a)>a+(1/2-o(1))\log a$, and considers various generalisations of the original problem.
It seems likely that $b(a)\leq (1+o(1))a$, and perhaps even $b(a)\leq a+(\log a)^{O(1)}$.
More generally, if the leading digit of $n$ in base $p$ is $p-1$ then $p\mid (a_n,L_n)$. There is in fact a necessary and sufficient condition: a prime $p\leq n$ divides $(a_n,L_n)$ if and only if $p$ divides the numerator of $1+\cdots+\frac{1}{k}$, where $k$ is the leading digit of $n$ in base $p$. This can be seen by writing \[a_n = \frac{L_n}{1}+\cdots+\frac{L_n}{n}\] and observing that the right-hand side is congruent to $1+\cdots+1/k$ modulo $p$. (The previous claim about $p-1$ follows immediately from Wolstenholme's theorem.)
This leads to a heuristic prediction (see for example a preprint of Shiu [Sh16]) of $\asymp\frac{x}{\log x}$ for the number of $n\in [1,x]$ such that $(a_n,L_n)=1$. In particular, there should be infinitely many $n$, but the set of such $n$ should have density zero. Unfortunately this heuristic is difficult to turn into a proof.
The answer is yes, as proved by Martin [Ma00], who in fact proved that if $B=\mathbb{N}\backslash A$ then, for all large $x$, \[\frac{\lvert B\cap [1,x]\rvert}{x}\asymp \frac{\log\log x}{\log x},\] and also gave an essentially complete description of $B$ as those integers which are small multiples of prime powers.
van Doorn has observed that if $n\in A$ (with $n>1$) then $2n\in A$ also, since if $\sum \frac{1}{m_i}=1$ then $\frac{1}{2}+\sum\frac{1}{2m_i}=1$ also.
An elementary inductive argument shows that $n_k\leq ku_k$ where $u_1=1$ and $u_{i+1}=u_i(u_i+1)$, and hence \[v(k) \leq kc_0^{2^k},\] where \[c_0=\lim_n u_n^{1/2^n}=1.26408\cdots\] is the 'Vardi constant'.
Hunter and Sawhney have observed that Theorem 3 of Bloom [Bl21] (coupled with the trivial greedy approach) implies that $k(N)=(1-o(1))\log N$.
Liu and Sawhney [LiSa24] have proved that $A(N)=(1-1/e+o(1))N$.
Estimate $f(N)$. In particular, is $f(N)=(\tfrac{1}{2}+o(1))N$?
Wouter van Doorn has given an elementary argument that proves \[f(N)\leq (25/28+o(1))N.\] Indeed, consider the sets $S_a=\{2a,3a,4a,6a,12a\}\cap [1,N]$ as $a$ ranges over all integers of the form $8^b9^cd$ with $(d,6)=1$. All such $S_a$ are disjoint and, if $A$ has no solutions to the given equation, then $A$ must omit at least two elements of $S_a$ when $a\leq N/12$ and at least one element of $S_a$ when $N/12<a\leq N/6$, and an elementary calculation concludes the proof.
Stijn Cambie and Wouter van Doorn have proved that, if we allow solutions to this equation with non-distinct $b_i$, then the size of the maximal set is at most $N/2$. Indeed, this is the classical threshold for the existence of some distinct $a,b\in A$ such that $a\mid b$.
Estimate $f(N)$. In particular, is $f(N)=(\tfrac{1}{2}+o(1))N$?
Wouter van Doorn has proved, in an unpublished note, that \[f(N) \leq (9/10+o(1))N.\] Stijn Cambie has observed that \[f(N)\geq (5/8+o(1))N,\] taking $A$ to be all odd integers $\leq N/4$ and all integers in $[N/2,N]$.
Stijn Cambie has also observed that, if we allow $b=c$, then there is a solution to this equation when $\lvert A\rvert \geq (\tfrac{2}{3}+o(1))N$, since then there must exist some $n,2n\in A$.
Related to [18].
This was solved by Yokota [Yo88], who proved that \[D(b)\ll b(\log b)(\log\log b)^4(\log\log\log b)^2.\] This was improved by Liu and Sawhney [LiSa24] to \[D(b)\ll b(\log b)(\log\log b)^3(\log\log\log b)^{O(1)}.\]
In [ErGr80] this problem is stated with the sequence $u_1=1$ and $u_{n+1}=u_n(u_n+1)$, but Quanyu Tang has pointed out this is probably an error (since with that choice we do not have $\sum \frac{1}{u_n}=1$). This question with Sylvester's sequence is the most natural interpretation of what they meant to ask.
This is not true in general, as shown by Sándor [Sa97], who observed that the proper divisors of $120$ form a counterexample. More generally, Sándor shows that for any $n\geq 2$ there exists a finite set $A\subseteq \mathbb{N}\backslash\{1\}$ with $\sum_{k\in A}\frac{1}{k}<n$ and no partition into $n$ parts each of which has $\sum_{k\in A_i}\frac{1}{k}<1$.
The minimal counterexample is $\{2,3,4,5,6,7,10,11,13,14,15\}$, found by Tom Stobart.
See also [321].
See also [320].
Independently Erdős [Er36] and Chowla proved that for all $k\geq 3$ and infinitely many $n$ \[1_A^{(k)}(n) \gg n^{c/\log\log n}\] for some constant $c>0$ (depending on $k$).
For $k>2$ it is not known if $f_{k,k}(x)=o(x)$.
What if $a,b\in A$ with $a\neq b$ implies $a+b\nmid 2ab$? Must $\lvert A\rvert=o(N)$?
Wouter van Doorn has given an elementary argument that proves that if $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert \geq (25/28+o(1))N$ then $A$ must contain $a\neq b$ with $a+b\mid ab$ (see the discussion in [301]).
See also [302].
Ruzsa suggests that a non-trivial variant of this problem arises if one imposes the stronger condition that \[\lvert A\cap \{1,\ldots,N\}\rvert \sim c_AN^{1/2}\] for some constant $c_A>0$ as $N\to \infty$, and similarly for $B$.
One can also ask what conditions are sufficient for $D(A)$ to have positive density, or for $\sum_{d\in D(A)}\frac{1}{d}=\infty$, or even just $D(A)\neq\emptyset$.
It is likely that $f(n)\leq n^{o(1)}$, or even $f(n)\leq e^{O(\sqrt{\log n})}$.
The set of squares has order $4$ and restricted order $5$ (see [Pa33]) and the set of triangular numbers has order $3$ and restricted order $3$ (see [Sc54]).
Is it true that if $A\backslash F$ is a basis for all finite sets $F$ then $A$ must have a restricted order? What if they are all bases of the same order?
Hegyvári, Hennecart, and Plagne [HHP07] have shown that for all $k\geq2$ there exists a basis of order $k$ which has restricted order at least \[2^{k-2}+k-1.\]
This sequence is at OEIS A005282.
What can be said about this sequence? Do infinitely many pairs $a,a+2$ occur? Does this sequence eventually have periodic differences? Is the density $0$?
The original question was answered by Szemerédi and Vu [SzVu06] (who proved that the answer is yes).
This is best possible, since Folkman [Fo66] showed that for all $\epsilon>0$ there exists a multiset $A$ with \[\lvert A\cap \{1,\ldots,N\}\rvert\ll N^{1+\epsilon}\] for all $N$, such that $A$ is not subcomplete.
This is true, and was proved by Szemerédi and Vu [SzVu06]. The stronger conjecture that this is true under \[\lvert A\cap \{1,\ldots,N\}\rvert\geq (2N)^{1/2}\] seems to be still open (this would be best possible as shown by [Er61b].
Is it true that there are infinitely many $k$ such that $T(n^k)>T(n^{k+1})$?
Kovač and Predojević [KoPr24] have proved that this is true for cyclic quadrilaterals - that is, every set with infinite measure contains four distinct points on a circle such that the quadrilateral determined by these four points has area $1$. They also prove that there exists a set of infinite measure such that every convex polygon with congruent sides and all vertices in the set has area $<1$.
Koizumi [Ko25] has resolved this question, proving that any set with infinite measure must contain the vertices of an isosceles trapezoid, an isosceles triangle, and a right-angled triangle, all of area $1$.
The original problem was solved (in the affirmative) by Beker [Be23b].
They also ask how many consecutive integers $>n$ can be represented as such a sum? Is it true that, for any $c>0$ at least $cn$ such integers are possible (for sufficiently large $n$)?
How does $f(n)$ grow? Is $f(n)=o(n)$?
If $g(n)$ is the maximal $k$ such that there are $1\leq a_1,\ldots,a_k\leq n$ with all consecutive sums distinct (i.e. we drop the monotonicity assumption in the definition of $f$) then Hegyvári [He86] has proved that \[\left(\frac{1}{3}+o(1)\right) n\leq g(n)\leq \left(\frac{2}{3}+o(1)\right)n.\]
A similar question can be asked if we replace strict monotonicity with weak monotonicity (i.e. we allow $a_i=a_j$).
Erdős and Harzheim also ask what is the least $m$ which is not a sum of the given form? Can it be much larger than $n$? Erdős and Harzheim can show that $\sum_{x<a_i<x^2}\frac{1}{a_i}\ll 1$. Is it true that $\sum_i \frac{1}{a_i}\ll 1$?
Hayato Egami has observed that the answer for the first question is trivially yes as written, since one can take $a_n=n$. Presumably Erdős and Graham meant to impose some condition to rule out this sequence, but it is not clear what was intended.
In particular, in the case $n=1$, can one prove that $a_k/k\to \infty$ and $a_k/k^{1+c}\to 0$ for any $c>0$?
See also [839].
If we further ask that $\lvert S\rvert=l$ (for any fixed $l$) then is the number of solutions \[\ll \frac{2^N}{N^2},\] with the implied constant independent of $l$ and $t$?
The second question was answered in the affirmative by Halász [Ha77], as a consequence of a more general multi-dimensional result.
This is false: Ulas [Ul05] has proved there are infinitely many solutions when $n=4$ or $n\geq 6$ and $\lvert I_i\rvert=4$ for $1\leq i\leq n$. Bauer and Bennett [BaBe07] proved there are infinitely many solutions when $n=3$ or $n=5$ and $\lvert I_i\rvert=4$ for $1\leq i\leq n$. Furthermore, Bennett and Van Luijk [BeVL12] have found infinitely many solutions when $n\geq 5$ and $\lvert I_i\rvert=5$ for $1\leq i\leq n$.
In general, Ulas conjectures there are infinitely many solutions for any fixed size of $\lvert I_i\rvert$, provided $n$ is sufficiently large.
See also [930] for a more general question.
Erdős [Er76d] believed the answer to this question is no, and in fact if $n_k$ is the $k$th powerful number then \[n_{k+2}-n_k > n_k^c\] for some constant $c>0$.
It is trivial that there are no quadruples of consecutive powerful numbers since one must be $2\pmod{4}$.
Is the number of such $n\leq x$ bounded by $(\log x)^{O(1)}$?
The list of $n$ such that $n$ and $n+1$ are both powerful is A060355 in the OEIS.
The answer to the first question is no: Golomb [Go70] observed that both $12167=23^3$ and $12168=2^33^213^2$ are powerful. Walker [Wa76] proved that the equation \[7^3x^2=3^3y^2+1\] has infinitely many solutions, giving infinitely many counterexamples.
See also [364].
Stephan has found no such $n$ below $10^8$.
Note that $8$ is 3-full and $9$ is 2-full. Erdős and Graham asked if this is the only pair of such consecutive integers. Stephan has observed that $12167=23^3$ and $12168=2^33^213^2$ (a pair already known to Golomb [Go70]) is another example, but there are no other examples below $10^8$.
In [Er76d] Erdős asks the weaker question of whether there are any consecutive pairs of $3$-full integers.
The truth is probably $F(n)\gg (\log n)^2$ for all $n$. Erdős [Er76d] conjectured that, for every $\epsilon>0$, there are infinitely many $n$ such that $F(n) <(\log n)^{2+\epsilon}$.
Pasten [Pa24b] has proved that \[F(n) \gg \frac{(\log\log n)^2}{\log\log\log n}.\] The largest prime factors of $n(n+1)$ are listed as A074399 in the OEIS.
Unfortunately the problem is trivially true as written (simply taking $\{1,\ldots,k\}$ and $n>k^{1/\epsilon}$). There are (at least) two possible variants which are non-trivial, and it is not clear which Erdős and Graham meant. Let $P$ be the sequence of $k$ consecutive integers sought for. The potential strengthenings which make this non-trivial are:
See also [370].
Steinerberger has pointed out this problem has a trivial solution: take $n=m^2-1$, and then it is obvious that the largest prime factor of $n$ is $\leq m+1\ll n^{1/2}$ and the largest prime factor of $n+1$ is $\leq m\ll (n+1)^{1/2}$ (these $\ll$ can be replaced by $<$ if we choose $m$ such that $m,m+1$ are both composite).
Given that Erdős and Graham describe the above observation of Pomerance and explicitly say about this problem that 'we know very little about this', it is strange that such a trivial obstruction was overlooked. Perhaps the problem they intended was subtly different, and the problem in this form was the result of a typographical error, but I have no good guess what was intended here.
See also [369].
Hickerson conjectured the largest solution is \[16! = 14! 5!2!.\] The condition $a_1<n-1$ is necessary to rule out the trivial solutions when $n=a_2!\cdots a_k!$.
Surányi was the first to conjecture that the only non-trivial solution to $a!b!=n!$ is $6!7!=10!$.
Grimm proved that this is true if $k\ll \log n/\log\log n$. Erdős and Selfridge improved this to $k\leq (1+o(1))\log n$. Ramachandra, Shorey, and Tijdeman [RST75] have improved this to \[k\ll\left(\frac{\log n}{\log\log n}\right)^3.\]
A positive answer would imply that \[\sum_{p\leq n}1_{p\mid \binom{2n}{n}}\frac{1}{p}=(1-o(1))\log\log n,\] and Erdős, Graham, Ruzsa, and Straus say there is 'no doubt' this latter claim is true.
See also [382].
Is it true that \[Q(x)\gg_k (\log x)^k\] for every $k\geq 1$?
The answer to this problem is no: Nicolas [Ni71] proved that \[Q(x) \ll (\log x)^{O(1)}.\]
See also [380].
Tao has discussed this problem in a blog post.
Sarosh Adenwalla has observed that the first question is equivalent to [430]. Indeed, if $n$ is large and $a_i$ is the sequence defined in the latter problem, then [430] implies tha there is a composite $a_j$ such that $a_j-p(a_j)>n$ and hence $F(n)>n$.
Weisenberg has provided four easy examples that show Erdős and Graham were too optimistic here: \[\binom{7}{3}=5\cdot 7,\] \[\binom{10}{4}= 2\cdot 3\cdot 5\cdot 7,\] \[\binom{14}{4} = 7\cdot 11\cdot 13,\] and \[\binom{15}{6}=5\cdot 7\cdot 11\cdot 13.\]
Alladi and Grinstead [AlGr77] have obtained similar results when the $a_i$ are restricted to prime powers.
Solved in the affirmative by He, Juškevičius, Narayanan, and Spiro [HJNS24]. The bound of $1/n$ is the best possible, as shown by taking $z_k=1$ for $1\leq k\leq n/2$ and $z_k=i$ otherwise.
See also [498].
Pomerance [Po14] has shown that for any $k\geq 0$ there are infinitely many $n$ such that $n-k\mid\binom{2n}{n}$, although the set of such $n$ has upper density $<1/3$. Pomerance also shows that the set of $n$ such that \[\prod_{1\leq i\leq k}(n+i)\mid \binom{2n}{n}\] has density $1$.
The smallest $n$ for each $k$ are listed as A375077 on the OEIS.
Overholt [Ov93] has shown that this has only finitely many solutions assuming a weak form of the abc conjecture.
There are no other solutions below $10^9$ (see the OEIS page).
Jonas Barfield has found the solution \[10! = 48^4 - 36^4=12^4\cdot 175.\]
See also [401].
Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87].
Proved for all sets by Balasubramanian and Soundararajan [BaSo96].
See also [404].
Is there a prime $p$ and an infinite sequence $a_1<a_2<\cdots$ such that if $p^{m_k}$ is the highest power of $p$ dividing $\sum_{i\leq k}a_i!$ then $m_k\to \infty$?
Erdős and Graham ask this allowing the case $p=2$, but this is presumably an oversight, since clearly there are infinitely many solutions to this equation when $p=2$.
Brindza and Erdős [BrEr91] proved that are finitely many such solutions. Yu and Liu [YuLi96] showed that the only solutions are \[2!+1^4=3\] \[2!+5^4=3^3\] and \[4!+1^5=5^2.\]
This would imply via Kummer's theorem that \[3\mid \binom{2^{k+1}}{2^k}\] for all large $k$.
Erdős, Granville, Pomerance, and Spiro [EGPS90] have proved that the answer to the first two questions is yes, conditional on a form of the Elliott-Halberstam conjecture.
It is likely true that, if $k\to \infty$ however slowly with $n$, then for almost $n$ the largest prime factor of $\phi_k(n)$ is $\leq n^{o(1)}$.
The number of iterations required is A039651 in the OEIS.
Is it true that, for every $m,n\geq 2$, there exist some $i,j$ such that $\sigma_i(m)=\sigma_j(n)$?
That is, there is (eventually) only one possible sequence that the iterated sum of divisors function can settle on. Selfridge reports numerical evidence which suggests the answer is no, but Erdős and Graham write 'it seems unlikely that anything can be proved about this in the near future'.
Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \omega(m)\leq n$ for all $m<n$?
Erdős also believed that $\Omega$, the count of the number of prime factors with multiplicity), should have infinitely many barriers. Selfridge found the largest barrier for $\Omega$ which is $<10^5$ is $99840$.
In [ErGr80] this problem is suggested as a way of showing that the iterated behaviour of $n\mapsto n+\omega(n)$ eventually settles into a single sequence, regardless of the starting value of $n$ (see also [412] and [414]).
Erdős and Graham report it could be attacked by sieve methods, but 'at present these methods are not strong enough'.
The behaviour of $V(x)$ is now almost completely understood. Maier and Pomerance [MaPo88] proved \[V(x)=\frac{x}{\log x}e^{(C+o(1))(\log\log\log x)^2},\] for some explicit constant $C>0$. Ford [Fo98] improved this to \[V(x)\asymp\frac{x}{\log x}e^{C_1(\log\log\log x-\log\log\log\log x)^2+C_2\log\log\log x-C_3\log\log\log\log x}\] for some explicit constants $C_1,C_2,C_3>0$. Unfortunately this falls just short of an asymptotic formula for $V(x)$ and determining whether $V(2x)/V(x)\to 2$.
In [Er79e] Erdős asks further to estimate the number of $n\leq x$ such that the smallest solution to $\phi(m)=n$ satisfies $kx<m\leq (k+1)x$.
Erdős [Er73b] has shown that a positive density set of integers cannot be written as $\sigma(n)-n$.
This is true, as shown by Browkin and Schinzel [BrSc95], who show that any integer of the shape $2^{k}\cdot 509203$ is not of this form. It seems to be open whether there is a positive density set of integers not of this form.
Mehtaab Sawhney has shared the following simple argument that proves that the above limit points are in fact the only ones.
If $v_p(m)$ is the largest $k$ such that $p^k\mid m$ then $\tau(m)=\prod_p (v_p(m)+1)$ and so \[\frac{\tau((n+1)!)}{\tau(n!)} = \prod_{p|n+1}\left(1+\frac{v_p(n+1)}{v_p(n!)+1}\right).\] Note that $v_p(n!)\geq n/p$, and furthermore $n+1$ has $<\log n$ prime divisors, each of which satisfy $v_p(n+1)<\log n$. It follows that the contribution from $p\leq n^{2/3}$ is at most \[\left(1+\frac{\log n}{n^{1/3}}\right)^{\log n}\leq 1+o(1).\]
There is at most one $p\mid n+1$ with $p\geq n^{2/3}$ which (if present) contributes exactly \[\left(1+\frac{1}{\frac{n+1}{p}}\right).\] We have proved the claim, since these two facts combined show that the ratio in question is either $1+o(1)$ or $1+1/k+o(1)$, the latter occurring if $n+1=pk$ for some $p>n^{2/3}$.
After receiving Sawhney's argument I found that this had already been proved, with essentially the same argument, by Erdős, Graham, Ivić, and Pomerance [EGIP].
In [ErGr80] (and in Guy's book) this problem as written is asking for whether almost all integers appear in this sequence, but the answer to this is trivially no (as pointed out to me by Steinerberger): no integer $\equiv 1\pmod{3}$ is ever in the sequence, so the set of integers which appear has density at most $2/3$. This is easily seen by induction, and the fact that if $a,b\in \{0,2\}\pmod{3}$ then $ab-1\in \{0,2\}\pmod{3}$.
Presumably it is the weaker question of whether a positive density of integers appear (as correctly asked in [Er77c]) that was also intended in [ErGr80].
If $A\subseteq \{1,\ldots,n\}$ is such that all products $a_1\cdots a_r$ are distinct for $a_1<\cdots <a_r$ then is it true that \[\lvert A\rvert \leq \pi(n)+O(n^{\frac{r+1}{2r}})?\]
Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.
Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for such a construction and \$25 for a proof that no such construction is possible.
Bradač and Christoph [BrCh24] have proved the answer is no: if $f(n)$ is the maximum number of unique subgraphs in a graph on $n$ vertices then \[f(n) = o\left(\frac{2^{\binom{n}{2}}}{n!}\right).\] (Quantitatively the $o(1)$ in their argument can be taken to be $O(\frac{\log\log\log n}{\log\log n})$.)
Indeed, we apply this with $k=q=d$ and $a=1$ and let $p_m,\ldots,p_{m+{d-1}}$ be consecutive primes all congruent to $1$ modulo $d$, with $m>n+1$. If $p_{n+1}+\cdots+p_{m-1}\equiv r\pmod{d}$ with $1\leq r\leq d$ then \[d \mid p_{n+1}+\cdots +p_m+\cdots+p_{m+d+r-1}.\]
Is it true that, for sufficiently large $n$, not all of this sequence can be prime?
Sarosh Adenwalla has observed that this problem is equivalent to (the first part of) [385]. Indeed, assuming a positive answer to that, for all large $n$, there exists a composite $m<n$ such that all primes dividing $m$ are $>n-m$. It follows that such an $m$ is equal to some $a_i$ in the sequence defined for $[1,n)$, and $m$ is composite by assumption.
Elsholtz [El01] has proved there are no infinite sets $A,B,C$ such that $A+B+C$ agrees with the set of prime numbers up to finitely many exceptions.
See also [432].
The problem is written as Erdős and Graham describe it, but presumably they had in mind the regime where $n$ is fixed and $t\to \infty$.
A positive answer follows from work of Bui, Pratt, and Zaharescu [BPZ24], as noted by Tao in this blog post. In particular Tao shows that, if $L(x)$ is the maximal number of such squares possible, and $u(x)=(\log x\log\log x)^{1/2}$, then \[x\exp(-(2^{1/2}+o(1))u(x)) \leq L(x) \leq x\exp(-(2^{-1/2}+o(1))u(x)).\]
See also [841].
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$.
In other words, if $G$ is the infinite graph on $\mathbb{N}$ where we connect $m,n$ by an edge if and only if $n+m$ is a square, then is the chromatic number of $G$ equal to $\aleph_0$?
This is true, as proved by Khalfalah and Szemerédi [KhSz06], who in fact prove the general result with $x+y=z^2$ replaced by $x+y=f(z)$ for any non-constant $f(z)\in \mathbb{Z}[z]$ such that $2\mid f(z)$ for some $z\in \mathbb{Z}$.
See also [438].
Is it attained by choosing all integers in $[1,(N/2)^{1/2}]$ together with all even integers in $[(N/2)^{1/2},(2N)^{1/2}]$?
If $\delta'(n)$ is the density of integers which have exactly one divisor in $(n,2n)$ then is it true that $\delta'(n)=o(\delta(n))$?
Among many other results in [Fo08], Ford also proves that the second conjecture is false, and more generally that if $\delta_r(n)$ is the density of integers with exactly $r$ divisors in $(n,2n)$ then $\delta_r(n)\gg_r\delta(n)$.
Solved by Kleitman [Kl71], who proved \[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.\]
A more precise result was proved by Hall and Tenenbaum [HaTe88] (see Section 4.6), who showed that the upper density is $\ll\epsilon \log(2/\epsilon)$. Hall and Tenenbaum further prove that $\tau^+(n)/\tau(n)$ has a distribution function.
Erdős and Graham also asked whether there is a good inequality known for $\sum_{n\leq x}\tau^+(n)$. This was provided by Ford [Fo08] who proved \[\sum_{n\leq x}\tau^+(n)\asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}}\] where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]
See also [448].
In [Er79d] Erdős writes that probably $n_k<e^{o(k)}$ but $n_k>k^d$ for all constant $d$.
More generally, let $q(n,k)$ denote the least prime which does not divide $\prod_{1\leq i\leq k}(n+i)$. This problem asks whether $q(n,\log n)\geq (2+\epsilon)\log n$ infinitely often. Taking $n$ to be the product of primes between $\log n$ and $(2+o(1))\log n$ gives an example where \[q(n,\log n)\geq (2+o(1))\log n.\]
Can one prove that $q(n,\log n)<(1-\epsilon)(\log n)^2$ for all large $n$ and some $\epsilon>0$?
See also [663].
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?\]
What is the size of $D_n\backslash \cup_{m<n}D_m$?
If $f(N)$ is the minimal $n$ such that $N\in D_n$ then is it true that $f(N)=o(N)$? Perhaps just for almost all $N$?
Melfi [Me15] has proved that there are infinitely many primitive weird numbers, conditional on various well-known conjectures on the distribution of prime gaps. For example, it would suffice to show that $p_{n+1}-p_n <\frac{1}{10}p_n^{1/2}$ for sufficiently large $n$.
The sequence of weird numbers is A006037 in the OEIS. There are no odd weird numbers below $10^{17}$.
Mrazović and Kovač, and independently Alon, have observed that the existence of some valid choice of $Q$ follows easily from Vinogradov's theorem that every large odd integer is the sum of three distinct primes. In particular, there exists some $N$ such that every prime $>N$ is the sum of three distinct (smaller) primes. We may then take $Q_0$ to be the set of all primes $\leq N$ (in which case all primes are eventually in some $Q_i$).
Watts has suggested that perhaps the obvious greedy algorithm defines such a permutation - that is, let $a_1=1$ and let \[a_{n+1}=\min \{ x : a_n+x\textrm{ is prime and }x\neq a_i\textrm{ for }i\leq n\}.\] In other words, do all positive integers occur as some such $a_n$? Do all primes occur as a sum?
Shelah proved that it is consistent that the answer is negative, although with a very large value of $\mathfrak{c}$. It remains open whether it is consistent to have a negative answer assuming $\mathfrak{c}=\aleph_2$.
This has been proved for $t\leq 12$ (see Costa and Pellegrini [CoPe20] and the references therein) and for $p-3\leq t\leq p-1$ (see Hicks, Ollis, and Schmitt [HOS19] and the references therein). Kravitz [Kr24] has proved this for \[t \leq \frac{\log p}{\log\log p}.\] (This was independently earlier observed by Will Sawin in a MathOverflow post.)
Bedert and Kravitz [BeKr24] have now proved this conjecture for \[t \leq e^{(\log p)^{1/4}}.\]
As an indication of the difficulty, when $k=3$ the smallest $n$ such that $2^n\equiv 3\pmod{n}$ is $n=4700063497$.
The minimal such $n$ for each $k$ is A036236 in the OEIS.
The original formulation of this problem had an extra condition on the minimal element of the sequence $A_k$ being large, but Ryan Alweiss has pointed out that is trivially always satisfied since the minimal element of the sequence must grow by at least $1$ at each stage.
Find similar results for $\theta=\sqrt{m}$, and other algebraic numbers.
Solved by Erdős, Sárközy, and Sós [ESS89], who in fact prove that there are at least \[\frac{N}{2}-O(N^{1-1/2^{k+1}})\] many even numbers which are of this form. They also prove that if $k=2$ then there are at least \[\frac{N}{2}-O(\log N)\] many even numbers which are of this form, and that $O(\log N)$ is best possible, since there is a $2$-colouring such that no power of $2$ is representable as a monochromatic sum.
A refinement of this problem appears as Problem 25 on the open problems list of Ben Green.
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.\]
See also [208].
This is true, and was proved by Szemerédi [Sz76].
In [Er72] Erdős goes on to ask whether \[\lim \frac{\lvert A\rvert\lvert B\rvert\log N}{N^2}\] exists, and to determine its value.
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.)
This is true, and was proved by Margulis [Ma89].
Resolved by Kleitman [Kl69], who proved that the number of such families is \[2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}}.\]
See also [395].
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].
See also [712] for the general case.
If the sets $A_x$ are closed and have measure $<1$, then must there exist an independent set of size $3$?
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.
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$.
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.
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}$.
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}.\]
This was resolved by Elliott [El67], who proved that (assuming not all points are on a circle or a line) that, provided $n>393$, the points determine at least $\binom{n-1}{2}$ distinct circles.
The problem appears to remain open for small $n$. Segre observed that projecting a cube onto a plane shows that the lower bound $\binom{n-1}{2}$ is false for $n=8$.
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$)?
Solved in the affirmative by Pokrovskiy, Versteegen, and Williams [PVW24].