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].
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$.
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.
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].
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.\]
Can a lacunary set $A\subset\mathbb{N}$ be an essential component?
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$.
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].
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}.\]
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].
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$?
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.)
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.
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})$?
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].
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.
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}})?\]
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)$.
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?
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.
Is it true that for all $m\geq n+k$ \[M(n,k) \neq M(m,k)?\]
In general, how many solutions does $M(n,k)=M(m,l)$ have when $m\geq n+k$ and $l>1$? Erdős expects very few (and none when $l\geq k$).
The only solutions Erdős knew were $M(4,3)=M(13,2)$ and $M(3,4)=M(19,2)$.
In [Er79d] Erdős conjectures the stronger fact that (aside from a finite number of exceptions) if $k>2$ and $m\geq n+k$ then $\prod_{i\leq k}(n+i)$ and $\prod_{i\leq k}(m+i)$ cannot have the same set of prime factors.