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 bound on the smallest modulus to $616000$.
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$).
This is equivalent to asking whether every $n$ not divisible by $4$ is the sum of a squarefree number and a power of two. 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.
For the finite version see [13].
For the infinite version see [12].
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.
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 [KoRoTa99] 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 if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{5/8}$ then \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{11}{9}+o(1)},\] due to Rudnev, Shakan, and Shkredov [RSS20].
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].
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$.
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.
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.
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$.
This problem is #3 in Ramsey Theory in the graphs problem collection.
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$.
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)=4k$. Erdős also asks for which $n$ is it true that $f(n+1)=f(n)$.
In [Er97e] Erdős clarifies that the \$500 is for a proof, and only offers \$100 for a disproof.
This problem is #1 in Ramsey Theory in the graphs problem collection.
In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]
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 [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.
This was solved by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\]
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.
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$.
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.'
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.
See also [364].
See also [3].
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].
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.
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].
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].
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).\]
Kovač [Ko24c] has proved that $2^n$ is not such an irrationality sequence. More generally, he proves that any strictly increasing sequence of positive integers such that $\sum\frac{1}{a_n}$ converges and for which there exists $C>1$ such that $\frac{1}{a_n^2}\leq C\sum_{k>n}\frac{1}{a_k^2}$ is not such an irrationality sequence.
Kovač [Ko24c] constructs a sequence $a_n$ with this property which grows exponentially with $n$: \[a_n > 1.01^n.\]
The answer is yes, proved by Kovač [Ko24], who constructs an explicit open ball inside the set. The analogous question for higher dimensions remains open.
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.
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 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.
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.
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.
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 [Bl23] (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$.
The possible alternative question, that if $A\subseteq \mathbb{N}$ is a set of positive lower density then must there exist $a,b,c\in A$ such that \[\frac{1}{a}=\frac{1}{b}+\frac{1}{c},\] has a negative answer, taking for example $A$ to be the union of $[5^k,(1+\epsilon)5^k]$ for large $k$ and sufficiently small $\epsilon>0$. This was observed by Hunter and Sawhney.
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)$?
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?
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})$?
Steinerberger has pointed out that as written this problem is trivial: simply take some lacunary $A$ whose prime factors are restricted (e.g. $A=\{1,2,4,8,\ldots,\}$) - clearly any finite sum of the shape $\sum_{a\in A'}\frac{1}{a}$ can only form a rational with denominator divisible by one of these restricted set of primes.
This is puzzling, since Erdős and Graham were very aware of this kind of obstruction, so it's a strange thing to miss. I assume that there was some unwritten extra assumption intended (e.g. $A$ contains a multiple of every integer).
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$)?
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$?
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.
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$.
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].
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.
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).
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$.
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.
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 a construction and \$25 for a proof that no such construction is possible.
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+r-1}.\]
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].
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)}?\]
Even a stronger statement is true, as shown by Konyagin [Ko01], who proved that \[N(X,\delta) \ll_\delta N^{1/2}.\]
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}$.
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?
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}.\]
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].
See also [425].
This is true, and was proved by Szemerédi [Sz76].
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}.\]
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].
Wintner [Wi44] proved that, almost surely, \[\sum_{m\leq N}f(m)\ll N^{1/2+o(1)},\] and Erdős improved the right-hand side to $N^{1/2}(\log N)^{O(1)}$. Lau, Tenenbaum, and Wu [LTW13] have shown that, almost surely, \[\sum_{m\leq N}f(m)\ll N^{1/2}(\log\log N)^{2+o(1)}.\] Harper [Ha13] has shown that the sum is almost surely not $O(N^{1/2}/(\log\log N)^{5/2+o(1)})$, and conjectured that in fact Erdős' conjecture is false, and almost surely \[\sum_{m\leq N}f(m) \ll N^{1/2}(\log\log N)^{1/4+o(1)}.\] This was proved by Caich [Ca23].
Solved by Yakir [Ya21], who proved that almost all such polynomials have \[\frac{n}{2}+O(n^{9/10})\] many roots in $\{ z\in \mathbb{C} : \lvert z\rvert \leq 1\}$.
The answer to both questions is yes: Littlewood's conjecture was solved by Kashin [Ka87], and Konyagin [Ko94] improved this to show that $m(f)\leq n^{-1/2+o(1)}$ almost surely. This is essentially best possible, since Konyagin and Schlag [KoSc99] proved that for any $\epsilon>0$ \[\limsup_{n\to \infty} \mathbb{P}(m(f) \leq \epsilon n^{-1/2})\ll \epsilon.\] Cook and Nguyen [CoNg21] have identified the limiting distribution, proving that for any $\epsilon>0$ \[\lim_{n\to \infty} \mathbb{P}(m(f) > \epsilon n^{-1/2}) = e^{-\epsilon \lambda}\] where $\lambda$ is an explicit constant.
Kahane [Ka59] showed that $a_n=\frac{1+c}{n}$ with $c>0$ has this property, which Erd\H{s} (unpublished) improved to $a_n=\frac{1}{n}$. Erd\{o}s also showed that $a_n=\frac{1-c}{n}$ with $c>0$ does not have this property.
Solved by Shepp [Sh72], who showed that a necessary and sufficient condition is that \[\sum_n \frac{e^{a_1+\cdots+a_n}}{n^2}=\infty.\]
It is 'well known' that, for almost all $\epsilon_n=\pm 1$, the series diverges for almost all $\lvert z\rvert=1$ (assuming only $\sum \lvert a_n\rvert^2=\infty$).
Dvoretzky and Erdős [DE59] showed that if $\lvert a_n\rvert >c/\sqrt{n}$ then, for almost all $\epsilon_n=\pm 1$, the series diverges for all $\lvert z\rvert=1$.
Kesten [Ke63] proved that $C_k=2k-1-1/2k+O(1/k^2)$, and more precise asymptotics are given by Clisby, Liang, and Slade [CLS07].
Conway and Guttmann [CG93] showed that $C_2\geq 2.62$ and Alm [Al93] showed that $C_2\leq 2.696$. Jacobsen, Scullard, and Guttmann [JSG16] have computed the first few decimal places of $C_2$, showing that \[C_2 = 2.6381585303279\cdots.\]
In particular, is it true that $\ell(N)\sim N^{1/2}$?
In [AlEr85] Alon and Erdős make the stronger conjecture that perhaps $A$ can always be written as the union of at most $(1+o(1))N^{1/2}$ many Sidon sets. (This is easily verified for $A=\{1,\ldots,N\}$ using standard constructions of Sidon sets.)
Erdős and Spencer [ErSp89] proved that \[F(k) \geq 2^{ck^2/\log k}\] for some constant $c>0$. Balogh, Eberhrad, Narayanan, Treglown, and Wagner [BENTW17] have improved this to \[F(k) \geq 2^{2^{k-1}/k}.\]
They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620]) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle.
See also [579] and the entry in the graphs problem collection.
See also [56].
Erdős writes this is 'intimately connected' with the sunflower problem [20]. Indeed, the conjectured upper bound would follow from the following stronger version of the sunflower problem: estimate the size of the largest set of integers $A$ such that $\omega(n)=k$ for all $n\in A$ and there does not exist $a_1,\ldots,a_r\in A$ and an integer $d$ such that $(a_i,a_j)=d$ for all $i\neq j$ and $(a_i/d,d)=1$ for all $i$. The conjectured upper bound for $f_r(N)$ would follow if the size of such an $A$ must be at most $c_r^k$. The original sunflower proof of Erdős and Rado gives the upper bound $c_r^kk!$.
See also [536].
Erdős describes a construction of Ruzsa which disproves this: consider the set of all squarefree numbers of the shape $p_1\cdots p_r$ where $p_{i+1}>2p_i$ for $1\leq i<r$. This set has positive density, and hence if $A$ is its intersection with $(N/2,N)$ then $\lvert A\rvert \gg N$ for all large $N$. Suppose now that $p_1a_1=p_2a_2=p_3a_3$ where $a_i\in A$ and $p_1,p_2,p_3$ are distinct primes. Without loss of generality we may assume that $a_2>a_3$ and hence $p_2<p_3$, and so since $p_2p_3\mid a_1\in A$ we must have $2<p_3/p_2$. On the other hand $p_3/p_2=a_2/a_3\in (1,2)$, a contradiction.
