Erdős called this 'perhaps my first serious problem'. The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $[0,Nn)$. Erdős and Moser [Er56] proved \[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\] (In [Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)

A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu [DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In [Er73] and [ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound. (The second proof of [DFX21] applies also to this generalisation.)

This problem appears in Erdős' book with Spencer [ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in [Ru99] "it is a rich kitchen where such things go to the sink".

The sequence of minimal $N$ for a given $n$ is A276661 in the OEIS.

See also [350].

Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown (contrary to Erdős' expectations) that the answer is no: the smallest modulus must be at most $10^{18}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the bound on the smallest modulus to $616000$.

This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like \[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\] would be sufficient.

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

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

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

See also [139] and [142].

The peculiar quantitative form of Erdős' question was motivated by an old result of Rankin [Ra38], who proved there exists some constant $C>0$ such that the claim holds. Solved by Maynard [Ma16] and Ford, Green, Konyagin, and Tao [FGKT16]. The best bound available, due to all five authors [FGKMT18], is that there are infinitely many $n$ such that \[p_{n+1}-p_n\gg \frac{\log\log n\log\log\log\log n}{\log\log \log n}\log n.\] The likely truth is a lower bound like $\gg(\log n)^2$. In [Er97c] Erdős revised the value of this problem to \$5000 and reserved the \$10000 for a lower bound of $>(\log n)^{1+c}$ for some $c>0$.

See also [687].

Let $S$ be the set of limit points of $(p_{n+1}-p_n)/\log n$. This problem asks whether $S=[0,\infty]$. Although this conjecture remains unproven, a lot is known about $S$. Some highlights:

• $\infty\in S$ by Westzynthius' result [We31] on large prime gaps,
• $0\in S$ by the work of Goldston, Pintz, and Yildirim [GPY09] on small prime gaps,
• Erdős [Er55] and Ricci [Ri56] independently showed that $S$ has positive Lebesgue measure,
• Hildebrand and Maier [HiMa88] showed that $S$ contains arbitrarily large (finite) numbers,
• Pintz [Pi16] showed that there exists some small constant $c>0$ such that $[0,c]\subset S$,
• Banks, Freiberg, and Maynard [BFM16] showed that at least $12.5\%$ of $[0,\infty)$ belongs to $S$,
• Merikoski [Me20] showed that at least $1/3$ of $[0,\infty)$ belongs to $S$, and that $S$ has bounded gaps.

In [Er85c] and [Er97c] Erdős asks whether $S$ is everywhere dense.

Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'. (In [Er85c] he goes further and offers 'all the money I can earn, beg, borrow or steal for [a disproof]'.)

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

Asked by Erdős and Selfridge (sometimes also with Schinzel). They also asked whether there can be a covering system such that all the moduli are odd and squarefree. The answer to this stronger question is no, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$ (but the latter has been shown not to exist, see [586]).

Conjectured by Erdős and Graham, who also ask about a density-type version: for example, is \[\sum_{\substack{a\in A\\ a>N}}\frac{1}{a}\gg \log N\] a sufficient condition for $A$ to contain the moduli of a covering system? The answer (to both colouring and density versions) is no, due to the result of Hough [Ho15] on the minimum size of a modulus in a covering system - in particular one could colour all integers $<10^{18}$ different colours and all other integers a new colour.

Crocker [Cr71] has proved there are are $\gg\log\log N$ such integers in $\{1,\ldots,N\}$. Pan [Pa11] improved this to $\gg_\epsilon N^{1-\epsilon}$ for any $\epsilon>0$. Erdős believed this cannot be proved by covering systems, i.e. integers of the form $p+2^k+2^l$ exist in every infinite arithmetic progression.

The sequence of such numbers is A006286 in the OEIS.

See also [10], [11], and [16].

Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$.

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

See also [9], [11], and [16].

Odlyzko has checked this up to $10^7$. 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$).

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

See also [9], [10], and [16].

Asked by Erdős and Sárközy [ErSa70], who proved that $A$ must have density $0$. They also prove that this is essentially best possible, in that given any function $f(x)\to \infty$ as $x\to \infty$ there exists a set $A$ with this property and infinitely many $N$ such that \[\lvert A\cap\{1,\ldots,N\}\rvert>\frac{N}{f(N)}.\] (Their example is given by all integers in $(y_i,\frac{3}{2}y_i)$ congruent to $1$ modulo $(2y_{i-1})!$, where $y_i$ is some sufficiently quickly growing sequence.)

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

Asked by Erdős and Sárközy, who observed that $(2N/3,N]\cap \mathbb{N}$ is such a set. The answer is yes, as proved by Bedert [Be23].

For the infinite version see [12].

Asked by Erdős, Sárközy, and Szemerédi, who constructed an $A$ such that for all $\epsilon>0$ and all large $N$ \[\lvert \{1,\ldots,N\}\backslash B\rvert \ll_\epsilon N^{1/2+\epsilon},\] and yet there for all $\epsilon>0$ there exist infinitely many $N$ where \[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/3-\epsilon}.\]

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.

Erdős suggested that a computer could be used to explore this, and did not see any other method to attack this.

Tao [Ta23] has proved that this series does converge assuming a strong form of the Hardy-Littlewood prime tuples conjecture.

Erdős called this conjecture 'rather silly'. Using covering congruences Erdős [Er50] proved that the set of such odd integers contains an infinite arithmetic progression.

Chen [Ch23] has proved the answer is no.

See also [9], [10], and [11].

The first prime without this property is $97$. The sequence of such primes is A038133 in the OEIS. These are called cluster primes.

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

It is easy to see that almost all numbers are not practical. Erdős originally showed that $h(n!) <n$. Vose [Vo85] proved the existence of infinitely many practical $m$ such that $h(m)\ll (\log m)^{1/2}$.

The sequence of practical numbers is A005153 in the OEIS.

See also [304] and [825].

Asked by Erdős and Tenenbaum. Ruzsa gave the following simple counterexample: let $A=\{n_1<n_2<\cdots \}$ where $n_l \equiv -(k-1)\pmod{p_k}$ for all $k\leq l$, where $p_k$ denotes the $k$th prime.

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

By a simple averaging argument the set of moduli $[m_1,m_2]\cap \mathbb{N}$ has a choice of residue classes which form an $\epsilon(m_1,m_2)$-almost covering system with \[\epsilon(m_1,m_2)=\prod_{m_1\leq m\leq m_2}(1-1/m).\] A $0$-covering system is just a covering system, and so by Hough [Ho15] these only exist for $n_1<10^{18}$.

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

Conjectured by Erdős and Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$.

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

The existence of such a set was asked by Sidon to Erdős in 1932. Erdős (eventually) proved the existence of such a set using probabilistic methods. This problem asks for a constructive solution.

An explicit construction was given by Jain, Pham, Sawhney, and Zakharov [JPSZ24].

A problem of Erdős and Turán. It may even be true that $h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Both proofs in fact give \[h(N) \leq N^{1/2}+N^{1/4}+1.\] Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to $0.998N^{1/4}$, which has been further optimised by O'Bryant [OB22] to yield \[h(N)\leq N^{1/2}+0.99703N^{1/4}\] for sufficiently large $N$.

See also [241] and [840].

Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].

Such a set is called an additive complement to the primes.

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

Erdős observed that this value is finite and $>1$.

It is easy to see that $S(\iota)=o(n^2)$ if $\iota$ denotes the identity permutation, as studied by Erdős and Harzheim [Er77]. Motivated by this, Erdős asked if this remains true for all permutations.

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

See also [356] and [357].

Erdős [Er36c] proved this is true with $k$ replaced by $2k$ in the denominator (in a stronger form that only considers $A\cup (A+b)$ for some $b\in B$, see [38]).

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

The minimum overlap problem. The example (with $N$ even) $A=\{N/2+1,\ldots,3N/2\}$ shows that $c\leq 1/2$ (indeed, Erdős initially conjectured that $c=1/2$). The lower bound of $c\geq 1/4$ is trivial, and Scherk improved this to $1-1/\sqrt{2}=0.29\cdots$. The current records are \[0.379005 < c < 0.380926\cdots,\] the lower bound due to White [Wh22] and the upper bound due to Haugland [Ha16].

The answer is no by Ruzsa [Ru87], who proved that if $A$ is an essential component then there exists some constant $c>0$ such that $\lvert A\cap \{1,\ldots,N\}\rvert \geq (\log N)^{1+c}$ for all large $N$.

Erdős [Er36c] proved that if $B$ is an additive basis of order $k$ then, for any set $A$ of Schnirelmann density $\alpha$, for every $N$ there exists some integer $b\in B$ such that \[\lvert (A\cup (A+b))\cap \{1,\ldots,N\}\rvert\geq \left(\alpha+\frac{\alpha(1-\alpha)}{2k}\right)N.\] It seems an interesting question (not one that Erdős appears to have asked directly, although see [35]) to improve the lower bound here, even in the case $B=\mathbb{N}$. Erdős observed that a random set of density $\alpha$ shows that the factor of $\frac{\alpha(1-\alpha)}{2}$ in this case cannot be improved past $\alpha(1-\alpha)$.

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.

The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. (Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$.) Erdős proved that for every infinite Sidon set $A$ we have \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\] and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

It is possible that this is true even with $g(N)=O(1)$, from which the Erdős-Turán conjecture [28] would follow.

Erdős proved that if the pairwise sums $a+b$ are all distinct aside from the trivial coincidences then \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0.\]

See also [707].

This follows from the colouring result of Croot [Cr03]. Croot's result allows for $n_k \leq e^{C^k}$ for some constant $C>1$ (simply taking $n_k$ to be the lowest common multiple of some interval $[1,C^k]$). Sawhney has observed that there is also a doubly exponential lower bound, and hence this bound is essentially sharp.

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

The answer is yes, as proved by Croot [Cr03].

See also [298].

Solved by Bloom [Bl21], who showed that the quantitative threshold \[\sum_{n\in A}\frac{1}{n}\gg \frac{\log\log\log N}{\log\log N}\log N\] is sufficient. This was improved by Liu and Sawhney [LiSa24] to \[\sum_{n\in A}\frac{1}{n}\gg (\log N)^{4/5+o(1)}.\] Erdős speculated that perhaps even $\gg (\log\log N)^2$ might be sufficient. (A construction of Pomerance, as discussed in the appendix of [Bl21], shows that this would be best possible.)

See also [46] and [298].

This would follow immediately from the twin prime conjecture. The answer is yes, proved by Ford, Luca, and Pomerance [FLP10].

Erdős remarks that the last conjecture is probably easy, and that similar questions can be asked about $\sigma(n)$.

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

Carmichael has asked whether there is an integer $t$ for which $\phi(n)=t$ has exactly one solution. Erdős has proved that if such a $t$ exists then there must be infinitely many such $t$.

See also [694].

The sum-product problem. Erdős and Szemerédi [ErSz83] proved a lower bound of $\lvert A\rvert^{1+c}$ for some constant $c>0$, and an upper bound of \[\lvert A\rvert^2 \exp\left(-c\frac{\log\lvert A\rvert}{\log\log \lvert A\rvert}\right)\] for some constant $c>0$. The lower bound has been improved a number of times. The current record is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{1558}{1167}-o(1)}\] due to Rudnev and Stevens [RuSt22] (note $1558/1167=1.33504\cdots$).

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.

Asked by Erdős and Szemerédi [ErSz83]. Solved in this form by Chang [Ch03].

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

The stated bounds are due to Burr and Erdős [BuEr85]. Resolved by Conlon, Fox, and Pham [CFP21], who constructed a Ramsey $2$-complete $A$ such that \[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^2\] for all large $N$.

See also [55] and [843].

A paper of Burr and Erdős [BuEr85] proves both upper and lower bounds for $r=2$, showing that there exists some $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 also constructing a Ramsey $2$-complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^3.\] Burr has shown that the sequence of $k$th powers is Ramsey $r$-complete for every $r,k\geq 1$.

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.

See also [54] and [843].

This was disproved for $k=212$ by Ahlswede and Khachatrian [AhKh94], who suggest that their methods can disprove this for arbitrarily large $k$.

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 suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárkzözy proved that \[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.

The decimal expansion is A331373 in the OEIS.

Erdős [Er48] proved that $\sum_n \frac{d(n)}{2^n}$ is irrational, where $d(n)$ is the divisor function.

Conjectured by Erdős, Sós, and Sárkzözy [ESS95], who proved \[F_2(N)=\left(\frac{6}{\pi^2}+o(1)\right)N,\] \[F_3(N) = (1-o(1))N,\] and also established asymptotics for $F_k(N)$ for all even $k\geq 4$ (in particular $F_k(N)\asymp N/\log N$ for all even $k\geq 4$). Erdős [Er38] earlier proved that $F_4(N)=o(N)$ - indeed, if $\lvert A\rvert \gg N$ and $A\subseteq \{1,\ldots,N\}$ then there is a non-trivial solution to $ab=cd$ with $a,b,c,d\in A$.

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

Conjectured by Erdős, Pomerance, and Sárközy [ErPoSa97] who prove this when $f$ is the divisor function or the number of distinct prime divisors of $n$, but Erdős believed it is false when $f(n)=\phi(n)$ or $\sigma(n)$.

Conjectured by Erdős and Lewin [ErLe96], who (among other related results) prove this when $a=3$, $b=5$, and $c=7$.

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

Conjectured by Burr, Erdős, Graham, and Li [BEGL96]. Pomerance observed that the condition $\sum 1/(d_i-1)\geq 1$ is necessary. In [BEGL96] they prove the property holds for $\{3,4,7\}$.

See also [125].

A problem of Burr, Erdős, Graham, and Li [BEGL96]. More generally, if $n_1<\cdots<n_k$ have \[\sum_{i=1}^k\log_{n_k}(2)>1\] and $A_i$ is the set of integers with only the digits $0,1$ in base $n_i$ then does $A_1+\cdots+A_k$ have positive density?

See also [124].

Investigated by Erdős and Turán [ErTu34] (prompted by a question of Lázár and Grünwald) in their first joint paper, where they proved that \[\log n \ll f(n) \ll n/\log n\] (the upper bound is trivial, taking $A=\{1,\ldots,n\}$). Erdős says that $f(n)=o(n/\log n)$ has never been proved, but perhaps never seriously attacked.

It is easy to see that we must have $\lvert A\rvert \ll N^{1/2}$. Csaba has constructed such an $A$ with $\lvert A\rvert \gg N^{1/5}$.

Conjectured by Erdős and Selfridge. There are infinitely many $n$ such that $n(n+1)$ is powerful (see [364]). Erdős and Selfridge proved that $N$ can never be a perfect power. Erdős remarked that this 'seems hopeless at present'.

See also [364].

In [Er79] asks the stronger version with $2$ replaced by any constant $c>1$.

The answer is yes (also to this stronger version), proved by Maier and Tenenbaum [MaTe84]. (Tenenbaum has told me that they received \$650 for their solution.)

See also [449].

Erdős [Er51] proved this for all $0\leq \alpha \leq 2$, and Hooley [Ho73] extended this to all $\alpha \leq 3$.

See also [208].

The current best bounds known are \[2^{c^{\frac{k}{\log k}}}\leq F(k) \leq c_0^{(\frac{1}{5}+o(1))2^k},\] where $c>0$ is some absolute constant and $c_0=1.26408\cdots$ is the 'Vardi constant'. The lower bound is due to Konyagin [Ko14] and the upper bound to Elsholtz and Planitzer [ElPl21].

Erdős [Er35] proved that this sum always converges for a primitive set. Lichtman [Li23] proved that the answer is yes.

It is easy to see that $4\mid \binom{2n}{n}$ except when $n=2^k$, and hence it suffices to prove this when $n$ is a power of $2$.

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

It is easy to see by probabilistic methods that this holds for almost all integers. Romanoff [Ro34] showed that a positive density set of integers are representable as the sum of $2^k+p$ for prime $p$, and Erdős used covering systems to show that there is a positive density set of integers which cannot be so represented.

See also [851].

Erdős and Graham write it is 'not difficult' to construct irrational $x$ such that this fails (although give no proof or reference, and it seems to still be an open problem to actually construct some such irrational $x$). Curtiss [Cu22] showed that this is true for $x=1$ and Erdős [Er50b] showed it is true for all $x=1/m$ with $m\geq 1$. Nathanson [Na23] has shown it is true for $x=a/b$ when $a\mid b+1$ and Chu [Ch23b] has shown it is true for a larger class of rationals; it is still unknown whether this is true for all rational $x>0$.

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

Erdős [Er51] showed that there are infinitely many $n$ such that \[s_{n+1}-s_n > (1+o(1))\frac{\pi^2}{6}\frac{\log s_n}{\log\log s_n},\] so this bound would be the best possible.

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

See also [489] and [145].

In [Er85c] Erdős also conjectures that $d_n=d_{n+1}=\cdots=d_{n+k}$ is solvable for every $k$.

The answer is yes, proved by Green and Tao [GrTa08]. The stronger claim that there are arbitrarily long arithmetic progressions of consecutive primes is still open.

See also [3] and [141].

The answer is yes, as proved by Montgomery and Vaughan [MoVa86], who in fact found the correct order of magnitude with the power $2$ replaced by any $\gamma\geq 1$ (which was also asked by Erdős in [Er73]).

Lorentz [Lo54] proved there is such a set with, for all large $N$, \[\lvert A\cap\{1,\ldots,N\}\rvert \ll \frac{\log\log N}{\log N}N\] The answer is yes, proved by Ruzsa [Ru72]. Ruzsa's construction is ingeniously simple: \[A = \{ 5^nm : m\geq 1\textrm{ and }5^n\geq C\log m\}+\{0,1\}\] for some large absolute constant $C>0$. That every large integer is of the form $2^k+a$ for some $a\in A$ is a consequence of the fact that $2$ is a primitive root of $5^n$ for all $n\geq 1$.

In [Ru01] Ruzsa constructs an asymptotically best possible answer to this question (a so-called 'exact additive complement'); that is, there is such a set $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert \sim \frac{N}{\log_2N}\] as $N\to \infty$.

Erdős [Er51] proved that, for infinitely many $k$, \[ n_{k+1}-n_k \gg \frac{\log n_k}{\sqrt{\log\log n_k}}.\] Richards [Ri82] improved this to \[\limsup_{k\to \infty} \frac{n_{k+1}-n_k}{\log n_k} \geq 1/4.\] The constant $1/4$ here has been improved, most lately to $0.868\cdots$ by Dietmann, Elsholtz, Kalmynin, Konyagin, and Maynard [DEKKM22]. The best known upper bound is due to Bambah and Chowla [BaCh47], who proved that \[n_{k+1}-n_k \ll n_k^{1/4}.\]

The differences are listed at A256435 on the OEIS.

Cramer proved an upper bound of $O(N(\log N)^4)$ conditional on the Riemann hypothesis. The prime number theorem immediately implies a lower bound of $\gg N(\log N)^2$.

The values of the sum are listed at A074741 on the OEIS.

Erdős [Er50] proved that there are infinitely many $n$ such that $f(n)\gg \log\log n$. Erdős could not even prove that there do not exist infinitely many integers $n$ such that for all $2^k<n$ the number $n-2^k$ is prime (probably $n=105$ is the largest such integer).

The sequence of values of $f(n)$ is A109925 on the OEIS.

See also [237].

Erdős [Er50] proved this when $A=\{2^k : k\geq 0\}$. Solved by Chen and Ding [ChDi22].

See also [236].

This is well-known if $c_1$ is sufficiently small.

Wintner observed that if $f$ can take complex values on the unit circle then the limit need not exist. The answer is yes, as proved by Wirsing [Wi67], and generalised by Halász [Ha68].

Originally asked to Erdős by Wintner. The limit is infinite for a finite set of primes, which follows from a theorem of Pólya.

The Erdős-Straus conjecture. The existence of a representation of $4/n$ as the sum of at most four distinct unit fractions follows trivially from a greedy algorithm.

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

A sequence defined in such a fashion is known as Sylvester's sequence.

Originally asked to Erdős by Kalmár. Erdős believed the answer is yes. Romanoff [Ro34] proved that the answer is yes if $C$ is an integer.

Proved by Birch [Bi59].

Erdős [Er75c] proved the answer is yes under the stronger condition that $\limsup n_k/k^t=\infty$ for all $t\geq 1$.

Related to [69]. Erdős and Graham [ErGr80] write 'we just know too little about sieves to be able to handle such a question ("we" here means not just us but the collective wisdom (?) of our poor struggling human race).'

See also [679] and [827].

The decimal expansion of this sum is A256936 on the OEIS.

The answer is yes, as shown by Nesterenko [Ne96].

The decimal expansion of this sum is A098990 on the OEIS.

This is known now for $1\leq k\leq 4$. The cases $k=1,2$ are reasonably straightforward, as observed by Erdős [Er52]. The case $k=3$ was proved independently by Schlage-Puchta [ScPu06] and Friedlander, Luca, and Stoiciu [FLC07]. The case $k=4$ was proved by Pratt [Pr22].

This was disproved by Cassels [Ca60].

Cassels [Ca60] proved this under the alternative hypotheses \[\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert\gg \log\log x\] and \[\sum_{n\in A} \{ \theta n\}^2=\infty\] for every $\theta\in (0,1)$.

Related to [260].

Erdős and Straus proved the answer is yes for the 2-dimensional version, where $X\subseteq \mathbb{R}^2$ is the set of \[\left( \sum_{n\in A} \frac{1}{n},\sum_{n\in A}\frac{1}{n+1}\right) \] as $A\subseteq\mathbb{N}$ ranges over all infinite sets with $\sum_{n\in A}\frac{1}{n}<\infty$.

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.

Selfridge has found an example using divisors of $360$ if $p=3$ is allowed.

This is best possible as the system $2^{i-1}\pmod{2^i}$ shows. This was proved indepedently by Selfridge and Crittenden and Vanden Eynden [CrVE70].

Whether such a composite Lucas sequence even exists was open for a while, but using covering systems Graham [Gr64] showed that \[a_0 = 1786772701928802632268715130455793\] \[a_1 = 1059683225053915111058165141686995\] generate such a sequence. This problem asks whether one can have a composite Lucas sequence without 'an underlying system of covering congruences responsible'.

The density of such $n$ is zero.

Even the case $k=3$ seems difficult. This may be true with the primes replaced by any set $A\subseteq \mathbb{N}$ such that \[\lvert A\cap [1,N]\rvert \gg N/\log N\] and \[\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n} -\log\log N\to \infty\] as $N\to \infty$.

For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.

Erdős and Graham [ErGr80] suggest this 'may have to await improvements in current sieve methods' (of which there have been several since 1980).

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.

The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$.

In 1202 Fibonacci observed that this process terminates for any $x$ when $A=\mathbb{N}$. The problem when $A$ is the set of odd numbers is due to Stein.

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.

Graham [Gr63] has proved this when $p(x)=x$. Cassels [Ca60] has proved that these conditions on the polynomial imply every sufficiently large integer is the sum of $p(n_i)$ with distinct $n_i$. Burr has proved this if $p(x)=x^k$ with $k\geq 1$ and if we allow $n_i=n_j$.

The upper bound $f(k) \leq (1+o(1))\frac{k}{e-1}$ is trivial since for any $u\geq 1$ we have \[\sum_{u\leq n\leq eu}\frac{1}{n}=1+o(1),\] and hence if $f(k)=u$ then we must have $k\geq (e-1-o(1))u$. Essentially solved by Croot [Cr01], who showed that for any $N>1$ there exists some $k\geq 1$ and \[N<n_1<\cdots <n_k \leq (e+o(1))N\] with $1=\sum \frac{1}{n_i}$.

It is trivial that $f(k)\geq (1+o(1))\frac{e}{e-1}k$, since for any $u\geq 1$ \[\sum_{e\leq n\leq eu}\frac{1}{n}= 1+o(1),\] and so if $eu\approx f(k)$ then $k\leq \frac{e-1}{e}f(k)$. Proved by Martin [Ma00].

The answer is yes, proved by Croot [Cr01].

The example $1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$ shows that $3$ would be best possible here. The lower bound of $\geq 2$ is equivalent to saying that $1$ is not the sum of reciprocals of consecutive integers, proved by Erdős [Er32].

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.

For example, \[\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{20}=1.\] This is still open even if $\lvert I_2\rvert=1$. It is perhaps true with two intervals replaced by any $k$ intervals.

For example, \[\sum_{3\leq n\leq 5}\frac{1}{n} = \frac{47}{60}\textrm{ and }\sum_{3\leq n\leq 6}\frac{1}{n}=\frac{19}{20}.\]

The smallest $b$ for each $a$ are listed at A375081 at the OEIS.

Steinerberger has observed that the answer to the second question is trivially yes: for example, any $n$ which begins with a $2$ in base $3$ has $3\mid (a_n,L_n)$.

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.

Straus observed that $A$ is closed under multiplication. Furthermore, it is easy to see that $A$ does not contain any prime power.

Results of Bleicher and Erdős [BlEr75] imply $v(k) \gg k!$. It may be that $v(k)$ grows doubly exponentially in $\sqrt{k}$ or even $k$.

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

Erdős and Graham [ErGr80] could show \[t(N)\ll\frac{N}{\log N},\] but had no idea of the true value of $t(N)$.

Solved by Liu and Sawhney [LiSa24] (up to $(\log\log N)^{O(1)}$), who proved that \[\frac{N}{(\log N)(\log\log N)^3(\log\log\log N)^{O(1)}}\ll t(N) \ll \frac{N}{\log N}.\]

Erdős and Straus [ErSt71b] have proved the existence of some constant $c>0$ such that \[-c < k(N)-(e-1)N \ll \frac{N}{\log N}.\]

More generally, how many disjoint $A_i$ can be found in $\{1,\ldots,N\}$ such that the sums $\sum_{n\in A_i}\frac{1}{n}$ are all equal? Using sunflowers it can be shown that there are at least $N\exp(-O(\sqrt{\log N}))$ such sets.

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

It was not even known for a long time whether this is $2^{cN}$ for some $c<1$ or $2^{(1+o(1))N}$. In fact the former is true, and the correct value of $c$ is now known.

• Steinerberger [St24] proved the relevant count is at most $2^{0.93N}$;
• Independently, Liu and Sawhney [LiSa24] gave both upper and lower bounds, proving that the count is \[2^{(0.91\cdots+o(1))N},\] where $0.91\cdots$ is an explicit number defined as the solution to a certain integral equation;
• Again independently this same asymptotic was proved (with a different proof) by Conlon, Fox, He, Mubayi, Pham, Suk, and Verstraëte [CFHMPSV24], who prove more generally, for any $x\in \mathbb{Q}_{>0}$, a similar expression for the number of $A\subseteq \{1,\ldots,N\}$ such that $\sum_{n\in A}\frac{1}{n}=x$;
• The above papers all appeared within weeks of each other in 2024; in 2017 a similar question (with $\leq 1$ rather than $=1$) was asked on MathOverflow by Mikhail Tikhomirov and proofs of the correct asymptotic were sketched by Lucia, RaphaelB4, and js21.

The answer is yes, proved by Bloom [Bl21].

See also [46] and [47].

There does not exist such a sequence, which follows from the positive solution to [298] by Bloom [Bl21].

Erdős and Graham believe the answer is $A(N)=(1+o(1))N$. Croot [Cr03] disproved this, showing the existence of some constant $c<1$ such that $A(N)<cN$ for all large $N$. It is trivial that $A(N)\geq (1-\frac{1}{e}+o(1))N$.

Liu and Sawhney [LiSa24] have proved that $A(N)=(1-1/e+o(1))N$.

The example $A=(N/2,N]\cap \mathbb{N}$ shows that $\lvert A\rvert\geq N/2$.

The colouring version of this is [303], which was solved by Brown and Rödl [BrRo91].

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.

The density version of this is [302]. This colouring version is true, as proved by Brown and Rödl [BrRo91].

Erdős [Er50c] proved that \[\log\log b \ll N(b) \ll \frac{\log b}{\log\log b}.\] The upper bound was improved by Vose [Vo85] to \[N(b) \ll \sqrt{\log b}.\] One can also investigate the average of $N(a,b)$ for fixed $b$, and it is known that \[\frac{1}{b}\sum_{1\leq a<b}N(a,b) \gg \log\log b.\]

Related to [18].

Bleicher and Erdős [BlEr76] have shown that \[D(b)\ll b(\log b)^2.\] If $b=p$ is a prime then \[D(p) \gg p\log p.\]

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

For $n_i$ the product of three distinct primes, this is true when $b=1$, as proved by Butler, Erdős and Graham [BEG15] (this paper is perhaps Erdős' last paper, appearing 19 years after his death).

Asked by Barbeau [Ba76]. Can this be done if we drop the requirement that all $p\in P$ are prime and just ask for them to be relatively coprime, and similarly for $Q$?

The answer to the second question is no: there are at least $(1-o(1))\log N$ many such integers, which follows from a more precise result of Croot [Cr99], who showed that every integer at most \[\leq \sum_{n\leq N}\frac{1}{n}-(\tfrac{9}{2}+o(1))\frac{(\log\log N)^2}{\log N}\] can be so represented.

Liu and Sawhney [LiSa24] observed that the main result of Bloom [Bl21] implies a positive solution to this conjecture. They prove a more precise version, that if $(\log N)^{-1/7+o(1)}\leq \alpha \leq 1/2$ then there is some $S\subseteq A$ such that \[\frac{a}{b}=\sum_{n\in S}\frac{1}{n}\] with $a\leq b \leq \exp(O(1/\alpha))$. They also observe that the dependence $b\leq \exp(O(1/\alpha))$ is sharp.

It is trivially at least $1/[1,\ldots,N]$.

Erdős and Graham knew this with $e^{-cK}$ replaced by $c/K^2$.

For example, \[\frac{1}{2}+\frac{1}{3}=1-\frac{1}{6}.\]

This is true, and shown by Lim and Steinerberger [LiSt24] who proved that there exist infinitely many $n$ such that \[\epsilon(n)n^2\ll \left(\frac{\log\log n}{\log n}\right)^{1/2}.\] Erdős and Graham (and also Lim and Steinerberger) believe that the exponent of $2$ is best possible here, in that $\liminf \epsilon(n) n^{2+\delta}=\infty$ for all $\delta>0$.

$c_0$ is called the Vardi constant and the sequence $u_n$ is Sylvester's sequence.

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 if $A$ is a multiset, for example $2,3,3,5,5,5,5$.

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.

Inequality is obvious for the second claim, the problem is strict inequality. This fails for small $n$, for example \[\frac{1}{2}-\frac{1}{3}-\frac{1}{4}=-\frac{1}{12}.\]

Erdős and Straus [ErSt75] proved this when $A=\mathbb{N}$. Sattler [Sat75] proved this when $A$ is the set of odd numbers. For the squares $1$ must be excluded or the result is trivially false, since \[\sum_{k\geq 2}\frac{1}{k^2}<1.\]

Bleicher and Erdős [BlEr75] proved the lower bound \[\frac{N}{\log N}\prod_{i=3}^k\log_iN\leq \frac{\log S(N)}{\log 2},\] valid for $k\geq 4$ and $\log_kN\geq k$, and also [BlEr76b] proved the upper bound \[\log S(N)\leq \log_r N\left(\frac{N}{\log N} \prod_{i=3}^r \log_iN\right),\] valid for $r\geq 1$ and $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

See also [321].

Let $R(N)$ be the maximal such size. Results of Bleicher and Erdős from [BlEr75] and [BlEr76b] imply that \[\frac{N}{\log N}\prod_{i=3}^k\log_iN\leq R(N)\leq \frac{1}{\log 2}\log_r N\left(\frac{N}{\log N} \prod_{i=3}^r \log_iN\right),\] valid for any $k\geq 4$ with $\log_kN\geq k$ and any $r\geq 1$ with $\log_{2r}N\geq 1$. (In these bounds $\log_in$ denotes the $i$-fold iterated logarithm.)

See also [320].

Connected to Waring's problem. The famous Hypothesis $K$ of Hardy and Littlewood was that $1_A^{(k)}(n)\leq n^{o(1)}$, but this was disproved by Mahler [Ma36] for $k=3$, who constructed infinitely many $n$ such that \[1_A^{(3)}(n)\gg n^{1/12}\] (where $A$ is the set of cubes). Erdős believed Hypothesis $K$ fails for all $k\geq 4$, but this is unknown. Hardy and Littlewood made the weaker Hypothesis $K^*$ that for all $N$ and $\epsilon>0$ \[\sum_{n\leq N}1_A^{(k)}(n)^2 \ll_\epsilon N^{1+\epsilon}.\] Erdős and Graham remark: 'This is probably true but no doubt very deep. However, it would suffice for most applications.'

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

This would have significant applications to Waring's problem. Erdős and Graham describe this as 'unattackable by the methods at our disposal'. The case $k=2$ was resolved by Landau, who showed \[f_{2,2}(x) \sim \frac{cx}{\sqrt{\log x}}\] for some constant $c>0$.

For $k>2$ it is not known if $f_{k,k}(x)=o(x)$.

Erdős and Graham describe this problem as 'very annoying'. Probably $f(x)=x^5$ should work.

Mahler and Erdős [ErMa38] proved that $f_{k,2}(x) \gg x^{2/k}$. For $k=3$ the best known is due to Wooley [Wo15], \[f_{3,3}(x) \gg x^{0.917\cdots}.\]

Erdős originally asked whether this was true with $A=B$, but this was disproved by Cassels [Ca57].

The connection to unit fractions comes from the observation that $\frac{1}{a}+\frac{1}{b}$ is a unit fraction if and only if $a+b\mid ab$.

Asked by Erdős and Newman. Nešetřil and Rödl have shown the answer is no for all $C$ (source is cited as 'personal communication' in [ErGr80]). Erdős had previously shown the answer is no for $C=3,4$ and infinitely many other values of $C$.

Erdős proved that $1/2$ is possible and Krückeberg [Kr61] proved $1/\sqrt{2}$ is possible. Erdős and Turán [ErTu41] have proved this $\limsup$ is always $\leq 1$.

The fact that $1$ is possible would follow if any finite Sidon set is a subset of a perfect difference set (see [707]).

Asked by Erdős and Nathanson.

Ruzsa has observed that there is a simple counterexample: take $A$ to be the set of numbers whose binary representation has only non-zero digits in even places, and $B$ similarly but with non-zero digits only in odd places. It is easy to see $A$ and $B$ both grow like $\gg N^{1/2}$ and yet for any $n\geq 1$ there is exactly one solution to $n=a+b$ with $a\in A$ and $b\in B$.

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

Prikry, Tijdeman, Stewart, and others (see the survey articles [St78] and [Ti79]) have shown that a sufficient condition is that $A$ has positive density.

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

Erdős and Newman [ErNe77] have proved this is true when $A$ is the set of squares.

See also [806].

Erdős originally asked if even $f(n)\leq n^{1/3}$ is true. This is known, and the best bound is due to Balog [Ba89] who proved that \[f(n) \ll_\epsilon n^{\frac{4}{9\sqrt{e}}+\epsilon}\] for all $\epsilon>0$. (Note $\frac{4}{9\sqrt{e}}=0.2695\ldots$.)

It is likely that $f(n)\leq n^{o(1)}$, or even $f(n)\leq e^{O(\sqrt{\log n})}$.

One way this can happen is if there exists $\theta>0$ such that \[A=\{ n>0 : \{ n\theta\} \in X_A\}\textrm{ and }B=\{ n>0 : \{n\theta\} \in X_B\}\] where $\{x\}$ denotes the fractional part of $x$ and $X_A,X_B\subseteq \mathbb{R}/\mathbb{Z}$ are such that $\mu(X_A+X_B)=\mu(X_A)+\mu(X_B)$. Are all possible $A$ and $B$ generated in a similar way (using other groups)?

Erdős and Graham [ErGr80b] have shown that a basis $A$ has an exact order if and only if $a_2-a_1,a_3-a_2,a_4-a_3,\ldots$ are coprime. They also prove that \[\frac{1}{4}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{5}{4}.\] It is known that $h(2)=4$, but even $h(3)$ is unknown (it is $\geq 7$).

The answer is no, and a counterexample was provided by Turjányi [Tu84]. This was generalised (to the replacement of $A+A$ by the $h$-fold sumset $hA$ for any $h\geq 2$) by Ruzsa and Turjányi [RT85]. Ruzsa and Turjányi do prove (under the same hypotheses) that \[\lim_{N\to \infty}\frac{\lvert (A+A+A)\cap \{1,\ldots,3N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty,\] and conjecture that the same should be true with $(A+A)\cap \{1,\ldots,2N\}$ in the numerator.

Bateman has observed that for $h\geq 3$ there is a basis of order $h$ with no restricted order, taking \[A=\{1\}\cup \{x>0 : h\mid x\}.\] Kelly [Ke57] has shown that any basis of order $2$ has restricted order at most $4$ and conjectures it always has restricted order at most $3$.

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?

Erdős and Graham [ErGr80] also ask about the difference set $A-A$, whether this has positive density, and whether this contains $22$.

This sequence is at OEIS A005282.

An old problem of Dickson. Even a starting set as small as $\{1,4,9,16,25\}$ requires thousands of terms before periodicity occurs.

A problem of Ulam. The sequence is \[1,2,3,4,6,8,11,13,16,18,26,28,\ldots\] at OEIS A002858.

A problem of Folkman. Folkman [Fo66] showed that this is true if \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1+\epsilon}\] for some $\epsilon>0$ and all $N$.

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.

Folkman proved this under the stronger assumption that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2+\epsilon}\] for some $\epsilon>0$.

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

Erdős and Graham [ErGr80] remark that very little is known about $T(A)$ in general. It is known that \[T(n)=1, T(n^2)=128, T(n^3)=12758,\] \[T(n^4)=5134240,\textrm{ and }T(n^5)=67898771.\] Erdős and Graham remark that a good candidate for the $n$ in the question are $k=2^t$ for large $t$, perhaps even $t=3$, because of the highly restricted values of $n^{2^t}$ modulo $2^{t+1}$.

Graham [Gr64d] has shown that the sequence $a_n=F_n-(-1)^{n}$, where $F_n$ is the $n$th Fibonacci number, has these properties. Erdős and Graham [ErGr80] remark that it is easy to see that if $a_{n+1}/a_n>\frac{1+\sqrt{5}}{2}$ then the second property is automatically satisfied, and that it is not hard to construct very irregular sequences satisfying both properties.

The Fibonacci sequence $1,1,2,3,5,\ldots$ shows that $m=1$ and $n=2$ is possible. The sequence of powers of $2$ shows that $m=0$ and $n=1$ is possible. The case $m=2$ and $n=3$ is not known.

Even in the range $t\in (0,1)$ and $\alpha\in (1,2)$ the behaviour is surprisingly complex. For example, Graham [Gr64e] has shown that for any $k$ there exists some $t_k\in (0,1)$ such that the set of $\alpha$ such that the sequence is complete consists of at least $k$ disjoint line segments. It seems likely that the sequence is complete for all $t>0$ and all $1<\alpha < \frac{1+\sqrt{5}}{2}$. Proving this seems very difficult, since we do not even known whether $\lfloor (3/2)^n\rfloor$ is odd or even infinitely often.

This was proved by Ryavec. The stronger statement that, for all $s\geq 0$, \[\sum_{n\in A}\frac{1}{n^s} <\frac{1}{1-2^{-s}},\] was proved by Hanson, Steele, and Stenger [HSS77].

See also [1].

Graham [Gr64f] proved this is true when $p(n)=n$. Erdős and Graham also ask which rational functions $r(x)\in\mathbb{Z}[x]$ force $\{ r(n) : n\in\mathbb{N}\}$ to be complete?

Bleicher and Erdős conjecture the answer is no.

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

This fails for $a_i=i$ for example. Erdős and Graham also ask what happens if we drop the monotonicity restriction and just ask that the $a_i$ are distinct. Perhaps some permutation of $\{1,\ldots,n\}$ has at least $cn^2$ such distinct sums (this was solved by Konieczny [Ko15], see [34]).

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$)?

See also [34] and [357].

Asked by Erdős and Harzheim. What if we remove the monotonicity and/or the distinctness constraint? Also 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$?

See also [34] and [356].

Erdős and Moser [Mo63] considered the case when $A$ is the set of primes, and conjectured that the $\limsup$ of the number of such representations in this case is infinite. They could not even prove that the upper density of the set of integers representable in this form is positive.

A problem of MacMahon, studied by Andrews [An75]. When $n=1$ this sequence begins \[1,2,4,5,8,10,15,\ldots.\] Andrews conjectures \[a_k\sim \frac{k\log k}{\log\log k}.\]

See also [839].

Alon and Erdős [AlEr96] proved that $f(n) = n^{1/3+o(1)}$, and more precisely \[\frac{n^{1/3}}{(\log n)^{4/3}}\ll f(n) \ll \frac{n^{1/3}}{(\log n)^{1/3}}(\log\log n)^{1/3}.\] Vu [Vu07] improved the lower bound to \[f(n) \gg \frac{n^{1/3}}{\log n}.\] Conlon, Fox, and Pham [CFP21] determined the order of growth of $f(n)$ up to a multiplicative constant, proving \[f(n) \asymp \frac{n^{1/3}(n/\phi(n))}{(\log n)^{1/3}(\log\log n)^{2/3}}.\]

Erdős and Moser proved the first bound with an additional factor of $(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65], thereby answering the first question in the affirmative. Stanley [St80] has shown that this quantity is maximised when $A$ is an arithmetic progression and $t=\tfrac{1}{2}\sum_{n\in A}n$.

Erdős and Selfridge have proved that the product of consecutive integers is never a power. The condition $\lvert I_i\rvert \geq 4$ is necessary here, since Pomerance has observed that the product of \[(2^{n-1}-1)2^{n-1}(2^{n-1}+1),\] \[(2^n-1)2^n(2^n+1),\] \[(2^{2n-1}-2)(2^{2n-1}-1)2^{2n-1},\] and \[(2^{2n-2}-2)(2^{2n}-1)2^{2n}\] is always a square.

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.

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

See also [137] and [365].

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=2^3y^2+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].

Erdős originally asked Mahler whether there are infinitely many pairs of consecutive powerful numbers, but Mahler immediately observed that the answer is yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

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

It would also be interesting to find upper and lower bounds for the analogous product with $B_r$ for $r\geq 3$, where $B_r(n)$ is the $r$-full part of $n$ (that is, the product of prime powers $p^a \mid n$ such that $p^{a+1}\nmid n$ and $a\geq r$). Is it true that, for every fixed $r,k\geq 2$ and $\epsilon>0$, \[\limsup \frac{\prod_{n\leq m<n+k}B_r(m) }{n^{1+\epsilon}}\to\infty?\]

Mahler [Ma35] showed that this is $\gg \log\log n$. Schinzel [Sc67b] observed that for infinitely many $n$ it is $\leq n^{O(1/\log\log\log n)}$. The truth is probably $\gg (\log n)^2$ for all $n$.

The largest prime factors of $n(n+1)$ are listed as A074399 in the OEIS.

Erdős and Graham state that this is open even for $k=2$ and 'the answer should be affirmative but the problem seems very hard'.

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:

• Each $m\in P$ must be $m^\epsilon$-smooth. If this is the problem then the answer is yes, which follows from a result of Balog and Wooley [BaWo98]: for any $\epsilon>0$ and $k\geq 2$ there exist infinitely many $m$ such that $m+1,\ldots,m+k$ are all $m^\epsilon$-smooth.
• Each $m\in P$ must be in $[n/2,n]$ (say). In this case a positive answer also follows from the result of Balog and Wooley [BaWo98] for infinitely many $n$, but the case of all sufficiently large $n$ is open.

See also [370].

Pomerance has observed that if we replace $1/2$ in the exponent by $1/\sqrt{e}-\epsilon$ for any $\epsilon>0$ then this is true for density reasons (since the density of integers $n$ whose greatest prime factor is $\leq n^{1/\sqrt{e}}$ is $1/2$).

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

Conjectured by Erdős and Pomerance [ErPo78], who proved that this set and its complement both have positive upper density.

In [Er79e] Erdős also asks whether, for every $\alpha>0$, the density of the set of $n$ where \[P(n+1)>P(n)n^\alpha\] exists.

The sequence of such $n$ is A070089 in the OEIS.

Conjectured by Erdős and Pomerance [ErPo78], who proved the analogous result for $P(n)<P(n+1)<P(n+2)$. Solved by Balog [Ba01], who proved that this is true for $\gg \sqrt{x}$ many $n\leq x$ (for all large $x$).

This would follow if $P(n(n+1))/\log n\to \infty$, where $P(m)$ denotes the largest prime factor of $m$ (see Problem [368]). 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!$.

Studied by Erdős and Graham [ErGr76] (see also [LSS14]). It is known, for example, that:

• no $D_k$ contains a prime,
• $D_2=\{ n^2 : n>1\}$,
• $\lvert D_3\cap \{1,\ldots,n\}\rvert = o(\lvert D_4\cap \{1,\ldots,n\}\rvert)$,
• the least element of $D_6$ is $527$, and
• $D_k=\emptyset$ for $k>6$.

Note this is trivial when $k\leq 2$. Originally conjectured by Grimm. This is a very difficult problem, since it in particular implies $p_{n+1}-p_n <p_n^{1/2-c}$ for some constant $c>0$, in particular resolving Legendre's conjecture.

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

Erdős, Graham, Ruzsa, and Straus [EGRS75] have shown that, for any two primes $p$ and $q$, there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $pq$.

The sequence of such $n$ is A030979 in the OEIS.

A question of Erdős, Graham, Ruzsa, and Straus [EGRS75], who proved that if $f(n)$ is the sum in question then \[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n) = \sum_{k=2}^\infty \frac{\log k}{2^k}=\gamma_0\] and \[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n)^2 = \gamma_0^2,\] so that for almost all integers $f(m)=\gamma_0+o(1)$. They also prove that, for all large $n$, \[f(n) \leq c\log\log n\] for some constant $c<1$. (It is trivial from Mertens estimates that $f(n)\leq (1+o(1))\log\log n$.)

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.

Erdős and Graham state they can prove that, for $k$ fixed and large, the density of $n$ such that $\binom{n}{k}$ is squarefree is $o_k(1)$. They can also prove that there are infinitely many $n$ such that $\binom{n}{k}$ is not squarefree for $1\leq k<n$, and expect that the density of such $n$ is positive.

If $s(n)$ denotes the largest integer such that $\binom{n}{k}$ is divisible by $p^{s(n)}$ for some prime $p$ for at least one $1\leq k<n$ then it is easy to see that $s(n)\to \infty$ as $n\to \infty$ (and in fact that $s(n) \asymp \log n$).

Erdős and Graham only knew that $B(x) > x^{1-o(1)}$. Similarly, we call an interval $[u,v]$ 'very bad' if $\prod_{u\leq m\leq v}m$ is powerful. The number of integers $n\leq x$ contained in at least one very bad interval should be $\ll x^{1/2}$. In fact, it should be asymptotic to the number of powerful numbers $\leq x$.

See also [382].

Erdős [Er44] proved $Q(x)\gg (\log x)^{1+c}$ for some constant $c>0$.

The answer to this problem is no: Nicolas [Ni71] proved that \[Q(x) \ll (\log x)^{O(1)}.\]

Erdős and Graham report it follows from results of Ramachandra that $v-u\leq v^{1/2+o(1)}$.

See also [380].

A conjecture of Erdős and Selfridge. Proved by Ecklund [Ec69], who made the stronger conjecture that whenever $n>k^2$ the binomial coefficient $\binom{n}{k}$ is divisible by a prime $p<n/k$. They have proved the weaker inequality $p\ll n/k^c$ for some constant $c>0$.

A question of Erdős, Eggleton, and Selfridge, who write that 'plausible conjectures on primes' imply that $F(n)\leq n$ for only finitely many $n$, and in fact it is possible that this quantity is always at least $n+(1-o(1))\sqrt{n}$ (note that it is trivially $\leq n+\sqrt{n}$).

Tao has discussed this problem in a blog post.

Erdős and Graham write that 'a proof that this cannot happen infinitely often for $\binom{n}{2}$ seems hopeless; probably this can never happen for $\binom{n}{k}$ if $3\leq k\leq n-3$.'

Erdős once conjectured that $\binom{n}{k}$ must always have a divisor in $(n-k,n]$, but this was disproved by Schinzel and Erdős [Sc58].

Asked by Erdős and Straus. For example when $n=2$ we have $k=5$ \[2\times 3 \times 4 \times 5\times 6 \mid 7 \times 8 \times 9\times 10\times 11.\] and when $n=3$ we have $k=4$: \[3\times 4\times 5\times 6 \mid 7\times 8\times 9\times 10.\] Bhavik Mehta has computed the minimal such $k$ for $1\leq n\leq 18$ (now available as A375071 on the OEIS).

Erdős, Guy, and Selfridge [EGS82] have shown that \[f(n)-2n \asymp \frac{n}{\log n}.\]

It is easy to see that \[\lim \frac{t(n)}{n}\leq \frac{1}{e}.\] Erdős [Er96b] wrote he, Selfridge, and Straus had proved a corresponding lower bound, so that $\lim \frac{t(n)}{n}=\frac{1}{e}$, and 'believed that Straus had written up our proof. Unfortunately Straus suddenly died and no trace was ever found of his notes. Furthermore, we never could reconstruct our proof, so our assertion now can be called only a conjecture.'

Alladi and Grinstead [AlGr77] have obtained similar results when the $a_i$ are restricted to prime powers.

If we change the condition to $a_t\leq n$ it can be shown that \[A(n)=n-\frac{n}{\log n}+o\left(\frac{n}{\log n}\right)\] via a greedy decomposition (use $n$ as often as possible, then $n-1$, and so on). Other questions can be asked for other restrictions on the sizes of the $a_t$.

Erdős and Graham write that they do not even know whether $f(n)=1$ infinitely often (i.e. whether a factorial is the product of two consecutive integers infinitely often).

The answer is yes, proved by Hall. It is probably true that the sum is $o(N/(\log N)^c)$ for some constant $c>0$. Similar questions can be asked for other $k\geq 3$.

Erdős and Graham write that $n+1$ always divides $\binom{2n}{n}$ (indeed $\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number), but it is quite rare that $n$ divides $\binom{2n}{n}$.

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.

The Brocard-Ramanujan conjecture. Erdős and Graham describe this as an old conjecture, and write it 'is almost certainly true but it is intractable at present'.

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

Erdős and Obláth [ErOb37] proved this is true when $(x,y)=1$ and $k\neq 4$. Pollack and Shapiro [PoSh73] proved this is true when $(x,y)=1$ and $k=4$. The known methods break down without the condition $(x,y)=1$.

Erdős and Graham write that it is easy to show that $g_k(n) \ll_k \log n$ always, but the best possible constant is unknown.

See also [401].

See also [400].

A conjecture of Graham [Gr70], who also conjectured that (assuming $A$ itself has no common divisor) the only cases where equality is achieved are when $A=\{1,\ldots,n\}$ or $\{L/1,\ldots,L/n\}$ (where $L=\mathrm{lcm}(1,\ldots,n)$) or $\{2,3,4,6\}$.

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

Asked by Burr and Erdős. Frankl and Lin [Li76] independently showed that the answer is yes, and the largest solution is \[2^7=2!+3!+5!.\] In fact Lin showed that the largest power of $2$ which can divide a sum of distinct factorials containing $2$ is $2^{254}$, and that there are only 5 solutions to $3^m=a_1!+\cdots+a_k!$ (when $m=0,1,2,3,6$).

See also [404].

See also [403]. Lin [Li76] has shown that $f(2,2) \leq 254$.

Erdős and Graham remark that it is probably true that in general $(p-1)!+a^{p-1}$ is rarely a power at all (although this can happen, for example $6!+2^6=28^2$).

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

The only examples seem to be $4=1+3$ and $256=1+3+3^2+3^5$. If we only allow the digits $1$ and $2$ then $2^{15}$ seems to be the largest such power of $2$.

This would imply via Kummer's theorem that \[3\mid \binom{2^{k+1}}{2^k}\] for all large $k$.

A conjecture originally due to Newman.

This is true, and was proved by Evertse, Györy, Stewart, and Tijdeman [EGST88].

Pillai [Pi29] was the first to investigate this function, and proved \[\log_3 n < f(n) < \log_2 n\] for all large $n$. Shapiro [Sh50] proved that $f(n)$ is essentially multiplicative.

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

A problem of Finucane. One can also ask about $n\mapsto \sigma(n)-1$.

The number of iterations required is A039651 in the OEIS.

The known solutions to $g_{k+2}(n)=2g_k(n)$ are $n=10$ and $n=94$. Selfridge and Weintraub found solutions to $g_{k+9}(n)=9g_k(n)$ and Weintraub found \[g_{k+25}(3114)=729g_k(3114)\] for all $k\geq 6$.

In [Er79d] Erdős attributes this conjecture to van Wijngaarden, who told it to Erdős in the 1950s.

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

See also [413] and [414].

In [Er79] Erdős calls such an $n$ a 'barrier' for $\omega$. Some other natural number theoretic functions (such as $\phi$ and $\sigma$) have no barriers because they increase too rapidly. Erdős believed that $\omega$ should have infinitely many barriers. In [Er79d] he proves that $F(n)=\prod k_i$, where $n=\prod p_i^{k_i}$, has infinitely many barriers (in fact the set of barriers has positive density in the integers).

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

See also [647] and [679].

Asked by Spiro. That is, there is (eventually) only one possible sequence that the iterations of $n\mapsto h(n)$ can settle on. Erdős and Graham believed the answer is yes. Similar questions can be asked by the iterates of many other functions. See also [412] and [413].

Erdős [Er36b] proved that \[F(n)\asymp \log\log\log n,\] and similarly if we replace $\phi$ with $\sigma$ or $\tau$ or $\nu$ or any 'decent' additive or multiplicative function.

Pillai [Pi29] proved $V(x)=o(x)$. Erdős [Er35b] proved $V(x)=x(\log x)^{-1+o(1)}$.

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

See also [417] and [821].

It is trivial that $V'(x) \leq V(x)$. See also [416].

Asked by Erdős and Sierpiński. It follows from the Goldbach conjecture that every odd number can be written as $n-\phi(n)$. What happens for even numbers?

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.

Erdős and Graham noted that any number of the shape $1+1/k$ for $k\geq 1$ is a limit point (and thus so too is $1$), but knew of no others.

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

Erdős and Graham write that it is easy to show that $\lim F(n^{1/2},n)=\infty$, and in fact the $n^{1/2}$ can be replaced by $n^{1/2-c}$ for some small constant $c>0$.

Asked by Hofstadter. The sequence begins $1,1,2,3,3,4,\ldots$ and is A005185 in the OEIS. It is not even known whether $f(n)$ is well-defined for all $n$.

Asked by Hofstadter. The sequence begins $1,2,3,5,6,8,10,11,\ldots$ and is A005243 in the OEIS.

Asked by Hofstadter. The sequence begins $2,3,5,9,14,17,26,\ldots$ and is A005244 in the OEIS. This problem is also discussed in section E31 of Guy's book Unsolved Problems in Number Theory.

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

Erdős [Er68] proved that there exist some constants $0<c_1\leq c_2$ such that \[\pi(n)+c_1 n^{3/4}(\log n)^{-3/2}\leq F(n)\leq \pi(n)+c_2 n^{3/4}(\log n)^{-3/2}.\] Surprisingly, if we consider the corresponding problem in the reals (so consider the largest $A\subset [1,x]$ such that for any distinct $a,b,c,d\in A$ we have $\lvert ab-cd\rvert \geq 1$) then Alexander proved that $\lvert A\rvert> x/8e$ is possible (disproving an earlier conjecture of Erdős [Er73] that $m=o(x)$). Alexander's construction seems to be unpublished, and I have no idea what it is.

See also [490], [793], and [796].

Cedric Pilatte has observed that a positive solution to this follows from a result of Shiu [Sh00]: for any $k\geq 1$ and $(a,q)=1$ there exist infinitely many $k$-tuples of consecutive primes $p_m,\ldots,p_{m+{k-1}}$ all of which are congruent to $a$ modulo $q$.

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

Erdős and Graham could show this is true (assuming the prime $k$-tuple conjecture) if we replace $\liminf$ by $\limsup$.

Weisenberg [We24] has shown the answer is no: $A$ can be arbitrarily sparse and missing at least one residue class modulo every prime $p$, and yet $A+n$ is not contained in the primes for any $n\in \mathbb{Z}$.

Erdős and Graham write 'preliminary calculations made by Selfridge indicate that this is the case but no proof is in sight'. For example if $n=8$ we have $a_1=7$ and $a_2=5$ and then must stop.

A problem of Ostmann, sometimes known as the 'inverse Goldbach problem'. The answer is surely no. The best result in this direction is due to Elsholtz and Harper [ElHa15], who showed that if $A,B$ are such sets then for all large $x$ we must have \[\frac{x^{1/2}}{\log x\log\log x} \ll \lvert A \cap [1,x]\rvert \ll x^{1/2}\log\log x\] and similarly for $B$.

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

Asked by Straus, inspired by a problem of Ostmann (see [431]).

This type of problem is associated with Frobenius. Erdős and Graham [ErGr72] proved $g(n,t)<2t^2/n$, and there are examples which show that \[g(n,t) \geq \frac{t^2}{n-1}-5t\] for $n\geq 2$.

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

Associated with problems of Frobenius.

Asked by Lehmer and Lehmer [LeLe62]. For example $\Lambda(2,2)=9$ and $\Lambda(3,2)=77$. It is known that $\Lambda(k,3)=\infty$ for all even $k$ and $\Lambda(k,4)=\infty$ for all $k$.

This has been partially resolved: Hildebrand [Hi91] has shown that $\Lambda(k,2)$ is finite for all $k$.

Erdős and Graham write it is 'trivial' that there are $o(x)$ many such squares, although this is not quite trivial, using Siegel's theorem.

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

Taking all integers $\equiv 1\pmod{3}$ shows that $\lvert A\rvert\geq N/3$ is possible. This can be improved to $\tfrac{11}{32}N$ by taking all integers $\equiv 1,5,9,13,14,17,21,25,26,29,30\pmod{32}$, as observed by Massias.

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

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

See also [439] and [587].

A question of Roth, Erdős, Sárközy, and Sós [ESS89] (according to some reports, although in [Er80c] Erdős claims this arose in a conversation with Silverman in 1977). Erdős, Sárközy, and Sós [ESS89] proved this for $2$ or $3$ colours.

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

It is easy to give a sequence with \[\limsup\frac{A(x)}{x^{1/2}}=c>0.\] There are related results (particularly for the more general case of $\mathrm{lcm}(a_i,a_{i+1},\ldots,a_{i+k})$) in a paper of Erdős and Szemerédi [ErSz80].

Let $g(N)$ denote the size of the largest such $A$. The construction mentioned proves that \[g(N) \geq \left(\tfrac{9}{8}n\right)^{1/2}+O(1).\] Erdős [Er51b] proved $g(N) \leq (4n)^{1/2}+O(1)$. Chen [Ch98] established the asymptotic \[g(N) \sim \left(\tfrac{9}{8}n\right)^{1/2}.\] Chen and Dai [DaCh06] proved that \[g(N)\leq \left(\tfrac{9}{8}n\right)^{1/2}+O\left(\left(\frac{N}{\log N}\right)^{1/2}\log\log N\right).\] In [ChDa07] the same authors prove that, infinitely often, Erdős' construction is not optimal: if $B$ is that construction and $A$ is such that $\lvert A\rvert=g(N)$ then, for infinitely many $N$, \[\lvert A\rvert\geq \lvert B\rvert+t,\] where $t\geq 0$ is defined such that the $t$-fold iterated logarithm of $N$ is in $[0,1)$.

Tao [Ta24b] has shown this is false: there exists $A\subset\mathbb{N}$ such that \[\sum_{n\in A\cap [1,x)}\frac{1}{n}\gg \exp((\tfrac{1}{2}+o(1))\sqrt{\log\log x}\log\log\log x)\] and \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\ll 1.\] Moreover, Tao shows this is the best possible result, in that if $\sum_{n\in A\cap [1,x)}\frac{1}{n}$ grows faster than $\exp(O(\sqrt{\log\log x}\log\log\log x))$ then \[\left(\sum_{n\in A\cap [1,x)}\frac{1}{n}\right)^{-2} \sum_{\substack{a,b\in A\cap (1,x]\\ a<b}}\frac{1}{\mathrm{lcm}(a,b)}\to \infty.\]

The answer is yes, proved by Erdős and Sárkőzy [ErSa80].

An unpublished result of Heilbronn guarantees this for $c$ sufficiently close to $1$.

Besicovitch [Be34] proved that $\liminf \delta(n)=0$. Erdős [Er35] proved that $\delta(n)=o(1)$. Erdős [Er60] proved that $\delta(n)=(\log n)^{-\alpha+o(1)}$ where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\] This estimate was refined by Tenenbaum [Te84], and the true growth rate of $\delta(n)$ was determined by Ford [Fo08] who proved \[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}}.\]

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

See also [448], [692], and [693].

This is false, and was disproved by Erdős and Tenenbaum [ErTe81], who showed that in fact the upper density of the set of such $n$ is $\asymp \epsilon^{1-o(1)}$ (where the $o(1)$ in the exponent $\to 0$ as $\epsilon \to 0$).

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

This is false - indeed, for any constant $K>0$ we have $r(n)>K\tau(n)$ for a positive density set of $n$. Kevin Ford has observed this follows from the negative solution to [448]: the Cauchy-Schwarz inequality implies \[r(n)+\tau(n)\geq \tau(n)^2/\tau^+(n)\] where $\tau^+(n)$ is as defined in [448], and the negative solution to [448] implies the right-hand side is at least $(K+1)\tau(n)$ for a positive density set of $n$. (This argument is given for an essentially identical problem by Hall and Tenenbaum [HaTe88], Section 4.6.)

See also [448].

Erdős and Graham write 'we can prove $n_k>k^{1+c}$ but no doubt much more is true'.

In [Er79d] Erdős writes that probably $n_k<e^{o(k)}$ but $n_k>k^d$ for all constant $d$.

Erdős [Er37] proved that the density of integers $n$ with $\omega(n)>\log\log n$ is $1/2$. The Chinese remainder theorem implies that there is such an interval with \[\lvert I\rvert \geq (1+o(1))\frac{\log x}{(\log\log x)^2}.\] It could be true that there is such an interval of length $(\log x)^{k}$ for arbitrarily large $k$.

Asked by Erdős and Straus. The answer is no, as shown by Pomerance [Po79].

Pomerance [Po79] has proved the $\limsup$ is at least $2$.

Richter [Ri76] proved that \[\liminf_n \frac{q_n}{n^2}>0.352\cdots.\]

Linnik's theorem implies that $p_n\leq n^{O(1)}$. Erdős [Er79e] writes it is 'easy to show' that for infinitely many $n$ we have $p_n <m_n$.

A problem of Erdős and Pomerance.

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

Erdős and Graham write this is 'almost certainly' true, but the proof is beyond our ability, for two reasons (at least):

• Firstly, one has to rule out the possibility of many primes $q$ such that $p_k<q^2<p_{k+1}$. There should be at most one such $q$, which would follow from $p_{k+1}-p_k<p_k^{1/2}$, which is essentially the notorious Legendre's conjecture.
• The small primes also cause trouble.

This question arose in work of Eggleton, Erdős, and Selfridge.

Erdős and Graham report they can show \[f(n,t) \gg \frac{t}{\log t}.\]

Erdős and Graham write the existence of such an $\alpha$ has 'very recently been shown', but frustratingly give neither a name nor a reference. I will try to track down this solution soon.

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

Even a stronger statement is true, as shown by Konyagin [Ko01], who proved that \[N(X,\delta) \ll_\delta N^{1/2}.\]

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

This is what I assume the intended problem is, although the presentation in [ErGr80] is missing some crucial quantifiers, so I may have misinterpreted it.

The same question can be asked for those $n$ which do not have distinct sums of sets of divisors, but any proper divisor of $n$ does.

Weird numbers were investigated by Benkoski and Erdős [BeEr74], who proved that the set of weird numbers has positive density.

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

A problem of Ulam. In particular, what about $Q=\{3,5,7,11\}$?

A problem due to Ulam. For example if we begin with $3,5$ then the sequence continues $3,5,7,11,13,17,\ldots$. It is possible that this sequence is infinite.

Asked by Segal. The answer is yes, as shown by Odlyzko.

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?

A problem of Graham, who proved it when $t=p-1$. A similar conjecture was made for arbitrary abelian groups by Alspach. Such an ordering is often called a valid ordering.

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

A question of Erdős and Heilbronn. Solved in the affirmative by da Silva and Hamidoune [dSHa94].

Probably there is no such $A$ for any polynomial $f$.

A conjecture of Graham. It is easy to see that $2^n\not\equiv 1\mod{n}$ for all $n>1$, so the restriction $k\neq 1$ is necessary. Erdős and Graham report that Graham, Lehmer, and Lehmer have proved this for $k=2^i$ for $i\geq 1$, or if $k=-1$, but I cannot find such a paper.

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.

A conjecture of Newman. This was proved Chung and Graham, who in fact show that for any $\epsilon>0$ there must exist some $n$ such that there are infinitely many $m$ for which \[\lvert x_{m+n}-x_m\rvert < \frac{1}{(c-\epsilon)n}\] where \[c=1+\sum_{k\geq 1}\frac{1}{F_{2k}}=2.535\cdots\] and $F_m$ is the $m$th Fibonacci number. This constant is best possible.

Erdős and Graham write that 'it is surprising that [this problem] offers difficulty'.

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.

The result for $\sqrt{2}$ was obtained by Graham and Pollak [GrPo70]. The problem statement is open-ended, but presumably Erdős and Graham would have been satisfied with the wide-ranging generalisations of Stoll ([St05] and [St06]).

Schur proved that $f(k)<ek!$. See also [183].

A conjecture of Roth.

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.

Davenport and Erdős [DaEr37] proved that the answer is yes when $X_n=\{0\}$ for all $n\in A$. The problem considers logarithmic density since Besicovitch [Be34] showed examples exist without a natural density, even when $X_n=\{0\}$ for all $n\in A$.

Davenport and Erdős [DaEr37] showed that there must exist an infinite sequence $a_1<a_2\cdots$ in $A$ such that $a_i\mid a_j$ for all $i\leq j$.

This is true, a consequence of the positive solution to [447] by Kleitman [Kl71].

The example $A=\{a\}$ and $n=2a-1$ and $m=2a$ shows that $2$ would be best possible.

For example, when $A=\{p^2: p\textrm{ prime}\}$ then $B$ is the set of squarefree numbers, and the existence of this limit was proved by Erdős.

See also [208].

This would be best possible, for example letting $A=[1,N/2]\cap \mathbb{N}$ and $B=\{ N/2<p\leq N: p\textrm{ prime}\}$.

See also [425].

This is true, and was proved by Szemerédi [Sz76].

Erdős [Er46] proved that if $f(n+1)-f(n)=o(1)$ or $f(n+1)\geq f(n)$ then $f(n)=c\log n$ for some constant $c$.

This is true, and was proved by Wirsing [Wi70].

For example if $A=\mathbb{N}$ then $f(x)=\{x\}$ is the usual fractional part operator.

A problem due to Le Veque [LV53], who proved it in some special cases.

This is false is general, as shown by Schmidt [Sc69].

Erdős attributes this question to Schinzel. Eli Seamans has observed that the answer is yes (with $k=2$) for a very simple reason: \[n = 2(n+2)-(2+(n+2)).\] There may well have been some additional constraint in the problem as Schinzel posed it, but [Er61] does not record what this is.

The infamous Littlewood conjecture.

Originally a conjecture due to Oppenheim. Davenport and Heilbronn [DaHe46] solve the analogous problem for quadratic forms in 5 variables.

This is true, and was proved by Margulis [Ma89].

Note that if we drop the multiplicative assumption, and simply assign $f(m)=\pm 1$ at random, then this statement is true (with $c=\sqrt{2}$), the law of the iterated logarithm.

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

Originally asked by Riddell [Ri69]. Erdős noted the bounds \[N^{1/3} \ll \ell(N) \leq (1+o(1))N^{1/2}\] (the upper bound following from the case $A=\{1,\ldots,N\}$). The lower bound was improved to $N^{1/2}\ll \ell(N)$ by Komlós, Sulyok, and Szemerédi [KSS75]. The correct constant is unknown, but it is likely that the upper bound is true, so 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.)

The existence of $F(k)$ was established by Sanders and Folkman, and it also follows from Rado's theorem. It is commonly known as Folkman's theorem.

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

In other words, must some colour class be an IP set. Asked by Graham and Rothschild. See also [531].

Proved by Hindman [Hi74] (for any number of colours).

A problem of Erdős and Graham (in [Er73] it was stated with $(a,b)=1$ instead but this is clearly a typo). They conjecture that this maximum is either $N/p$ (where $p$ is the smallest prime factor of $N$) or it is the number of integers $\{2t: t\leq N/2\textrm{ and }(2t,N)> 1\}$.

See also [56].

Erdős [Er64] proved that \[f_r(N) \leq N^{\frac{3}{4}+o(1)},\] and Abbott and Hanson [AbHa70] improved this exponent to $1/2$. Erdős [Er64] proved the lower bound \[f_3(N) > N^{\frac{c}{\log\log N}}\] for some constant $c>0$, and conjectured this should also be an upper bound.

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

This is false if we ask for four elements with the same pairwise least common multiple, as shown by Erdős [Er62] (with a proof given in [Er70]).

See also [535], [537], and [856]. A related combinatorial problem is asked at [857].

A positive answer would imply [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.

Erdős observed that \[\sum_{n\in A}\frac{1}{n}\sum_{p\leq N}\frac{1}{p}\leq r\sum_{m\leq N^2}\frac{1}{m}\ll r\log N,\] and hence \[\sum_{n\in A}\frac{1}{n} \ll r\frac{\log N}{\log\log N}.\] See also [536] and [537].

Erdős and Szemerédi proved that \[n^{1/2} \ll h(n) \ll n^{1-c}\] for some constant $c>0$.

A conjecture of Erdős and Heilbronn. The answer is yes, proved by Szemerédi [Sz70] (in fact for arbitrary finite abelian groups).

Erdős speculated that perhaps the correct threshold is $(2N)^{1/2}$; this is also a conjecture of Selfridge, and has been proved when $N$ is prime by Balandraud [Ba12].

A question of Graham.

The first bound is best possible as $A=\{2,3,5\}$ demonstrates.

Resolved by Schinzel and Szekeres [ScSz59] who proved the answer to the first question is yes and the answer to the second is no, and in fact there are examples with at most $n/(\log n)^c$ many such $m$, for some constant $c>0$.

In [Er73] Erdős further speculates that in fact \[\sum_{a\in A}\frac{1}{a}\leq 1+o(1),\] where the $o(1)$ term $\to 0$ as $n\to \infty$.

See also [784].

Erdős and Rényi [ErRe65] proved that \[f(N) \leq \log_2N+O(\log\log N).\] Erdős believed improving this to $o(\log\log N)$ is impossible.

Asked by Schinzel, motivated by a question of Erdős and Selfridge (see [7]). The answer is no, as proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Erdős observed that $\lvert A\rvert \gg N^{1/3}$ is possible, taking the first $\approx N^{1/3}$ multiples of some prime $p\approx N^{2/3}$.

Essentially solved by Nguyen and Vu [NgVu10], who proved that $\lvert A\rvert\ll N^{1/3}(\log N)^{O(1)}$.

See also [438].

This question was asked by Erdős to a young Terence Tao in 1985. We thank Tao for sharing this memory and a letter of Erdős describing the problem.

Asked by Erdős in a letter to Ruzsa in around 1980. Erdős observes that when $t=1$ the maximum possible is \[\lvert A\rvert=\left\lfloor\frac{N+1}{2}\right\rfloor,\] achieved by taking $A$ to be all odd numbers in $\{1,\ldots,N\}$. He also observes that when $t=2$ there exists such an $A$ with \[\lvert A\rvert \geq \frac{N}{2}+c\log N\] for some constant $c>0$: take $A$ to be the union of all odd numbers together with numbers of the shape $2^k$ with $k$ odd.

Erdös writes 'perhaps this is easy or false'. It is not true for four-term arithmetic progressions: colour the integers in $[3^{2k},3^{2k+1})$ red and all others blue.

Ryan Alweiss has provided the following simple argument showing that the answer is yes: suppose we have some red/blue colouring without this property. Without loss of generality, suppose $1$ is coloured red, and then either $3$ or $5$ must be blue.

Suppose first that $3$ is blue. If $n\geq 6$ is red then (considering $1,n,2n-1$) we deduce $2n-1$ is blue, and then (considering $3,n+1,2n-1$) we deduce that $n+1$ is red. In particular the colouring must be eventually constant, and we are done.

Now suppose that $5$ is blue. Arguing similarly (considering $1,n,2n-1$ and $5,n+2,2n-1$) we deduce that if $n\geq 8$ is red then $n+2$ is also red, and we are similarly done, since the colouring must be eventually constant on some congruence class modulo $2$.

The answer is yes, proved by Berend [Be97], who further proved that the sequence of such $n$ has bounded gaps (where the bound depends on the initial set of primes).

A problem of Erdős and Selfridge. This is true for $n=24$. The $n+2$ is best possible here since \[\max(\tau(n-1)+n-1,\tau(n-2)+n-2)\geq n+2.\]

In [Er79] Erdős says 'it is extremely doubtful' that there are infinitely many such $n$, and in fact suggets that \[\lim_{n\to \infty}\max_{m<n}(\tau(m)+m-n)=\infty.\]

In [Er79d] Erdős says it 'seems certain' that for every $k$ there are infinitely many $n$ for which \[\max_{n-k<m<n}(m+\tau(m))\leq n+2,\] but 'this is hopeless with our present methods', although it follows from Schinzel's Hypothesis H.

See also [413].

Erdős writes 'it is probably hopelessly difficult to decide about the truth of this conjecture'. The number of solutions is finite for any fixed $p,q$ since the largest prime factor of $n(n+1)$ tends to $\infty$ (Mahler [Ma35] showed that this is $\gg \log\log n$, see [368]).

Sampaio has observed that the answer to this question is no if one of the primes can be $2$ - for example this is false with $p=19$ and $q=2$, since if $n+1=2^k$ and $19\mid n$ then (since $2$ is a primitive root modulo $19$) we must have $18\mid k$, and hence $73\mid 2^{18}-1\mid n$. A similar argument works with $19$ replaced by any prime $p>13$ for which $2$ is a primitive root, using a result of Rotkiewicz [Ro64b] that for every prime $p>13$ there is a prime $q>p$ which divides $2^{p-1}-1$.

It is unclear whether Erdős was aware of this obstacle; certainly in [Er95c] he asks for any two primes, but may have intended to rule out such small prime obstacles.

More generally, one can ask about whether for any primes $p_1,\ldots,p_k$ there exists some $n$ such that the largest prime factor of $n+i$ is $p_i$. Erdős writes this is 'clearly impossible' if the $p_i$ are the first $k$ primes and $k$ is sufficiently large, but does not know what happens if all of the primes are sufficiently large compared to $k$.

Erdős and Sarányi [ErSa59] proved that $f(m)\gg m^{1/2}$.

A problem of Erdős and Pomerance.

The bound $q(n,k)<(1+o(1))k\log n$ is easy. It may be true this improved bound holds even up to $k=o(\log n)$.

See also [457].

Erdős believed not. Erdős and Selfridge [ErSe75] proved that the product of consecutive integers is never a perfect power.

The theory of Pell equations implies that there are infinitely many pairs $x,d$ with $(x,d)=1$ such that $x(x+d)(x+2d)$ is a square.

Considering the question of whether the product of an arithmetic progression of length $k$ can be equal to an $\ell$th power:

• Euler proved this is impossible when $k=4$ and $\ell=2$,
• Obláth [Ob51] proved this is impossible when $(k,l)=(5,2),(3,3),(3,4),(3,5)$.
• Marszalek [Ma85] proved that this is only possible for $k\ll_d 1$, where $d$ is the common difference of the arithmetic progression.

Erdős writes it is 'easy' to prove $\frac{1}{X}\sum_{n\leq X}G(n)\to \infty$.

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

Ko [Ko40] proved there are none if $(x,y)=1$, but there are in fact infinitely many solutions in general - for example, \[x=2^{12}3^6, y = 2^83^8,\textrm{ and } z = 2^{11}3^7.\] More generally, writing $a=2^{n+1}$ and $b=2^n-1$, \[x = 2^{a(b-n)}b^{2b}\cdot 2^{2n},\] \[y = 2^{a(b-n)}b^{2b}\cdot b^2,\] and \[z = 2^{a(b-n)}b^{2b}\cdot 2^{n+1}b.\] In [Er79] Erdős asks if the infinite families found by Ko are the only solutions.

Elementary sieve theory implies that the set of squarefree numbers has the translation property.

More generally, Brun's sieve can be used to prove that if $B\subseteq \mathbb{N}$ is a set of pairwise coprime integers with $\sum_{b<x}\frac{1}{b}=o(\log\log x)$ then $A=\{ n: b\nmid n\textrm{ for all }b\in A\}$ has the translation property. Erdős did not know what happens if the condition on $\sum_{b<x}\frac{1}{b}$ is weakened or dropped altogether.

The sieve of Eratosthenes implies that almost all integers are of this form, and the Brun-Selberg sieve implies the number of exceptions in $[1,x]$ is $\ll x/(\log x)^c$ for some constant $c>0$. Erdős [Er79] believed it is 'rather unlikely' that all large integers are of this form.

What if the condition that $p$ is prime is omitted? Selfridge and Wagstaff made a 'preliminary computer search' and suggested that there are infinitely many $n$ not of this form even without the condition that $p$ is prime. It should be true that the number of exceptions in $[1,x]$ is $<x^c$ for some constant $c<1$.

Most generally, given some infinite set $A\subseteq \mathbb{N}$ and function $f:A\to \mathbb{N}$ one can ask for sufficient conditions on $A$ and $f$ that guarantee every large number (or almost all numbers) can be written as \[am^2+b\] for some $m\in A$ and $a\geq 1$ and $0\leq b<f(m)$.

In another direction, one can ask what is the minimal $c_n$ such that $n$ can be written as $n=ap^2+b$ with $0\leq b<c_np$ for some $p\leq \sqrt{n}$. This problem asks whether $c_n\leq 1$ eventually, but in [Er79d] Erdős suggests that in fact $\limsup c_n=\infty$. Is it true that $c_n<n^{o(1)}$?

The Thue-Siegel theorem implies that, for fixed $k$, there are only finitely many $m,n$ such that $m\geq n+k$ and $M(n,k)=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.

See also [678], [686], and [850].

It is easy to see that there are infinitely many solutions to $M(n,k)>M(m,k)$. The referee of [Er79] found $M(96,7)>M(104,8)$ and $M(132,7)>M(139,8)$.

If $n_k$ is the smallest $n$ with this property (for some $m$) then are there good bounds for $n_k$? Erdős writes that he could prove $n_k/k\to \infty$, but knew of no good upper bounds.

If $u_k$ is minimal such that $M(u_k,k)>M(u_k+1,k)$ and $t<\min(u_k,T)$ then is it true that $M(t,k)\leq M(T,k)$?

See also [677].

One can ask similar questions for $\Omega$, the number of prime factors with multiplicity, where $\log k/\log\log k$ is replaced by $\log_2k$.

See also [248] and [413].

This follows from 'plausible assumptions on the distribution of primes' (as does the question with $k^2$ replaced by $k^d$ for any $d$); the challenge is to prove this unconditionally.

Erdős observed that Cramer's conjecture \[\limsup_{k\to \infty} \frac{p_{k+1}-p_k}{(\log k)^2}=1\] implies that for all $\epsilon>0$ and all sufficiently large $n$ there exists some $k$ such that \[p(n+k)>e^{(1-\epsilon)\sqrt{k}}.\] There is now evidence, however, that Cramer's conjecture is false; a more refined heuristic by Granville [Gr95] suggests this $\limsup$ is $2e^{-\gamma}\approx 1.119\cdots$, and so perhaps the $1+\epsilon$ in the second question should be replaced by $2e^{-\gamma}+\epsilon$.

See also [681] and [682].

Related to questions of Erdős, Eggleton, and Selfridge. This may be true with $k^2$ replaced by $k^d$ for any $d$.

See also [680] and [682].

Erdős first thought this should be true for all large $n$, but found a (conditional) counterexample: Dickson's conjecture says there are infinitely many $d$ such that \[2183+30030d\textrm{ and }2201+30030d\] are both prime, and then they must necessarily be consecutive primes. These give a counterexample since $30030=2\cdot 3 \cdot 5\cdot 7\cdot 11\cdot 13$ and every integer in $[2184,2200]$ is divisible by at least one of these primes.

See also [680] and [681].

A theorem of Sylvester and Schur states that this is $>k$ if $k\leq n/2$. Erdős writes it 'seems certain' that this holds for every $c>0$, with only a finite number of exceptions (depending on $c$). Standard heuristics on prime gaps suggest that the largest prime divisor of $\binom{n}{k}$ is in fact \[> \min(n-k+1, e^{c\sqrt{k}})\] for some constant $c>0$.

A classical theorem of Mahler states that for any $\epsilon>0$ and integers $k$ and $l$ then, writing \[(n+1)\cdots (n+k) = ab\] where the only primes dividing $a$ are $\leq l$ and the only primes dividing $b$ are $>l$, we have $a < n^{1+\epsilon}$ for all sufficiently large (depending on $\epsilon,k,l$) $n$.

Mahler's theorem implies $f(n)\to \infty$ as $n\to \infty$, but is ineffective, and so gives no bounds on the growth of $f(n)$.

One can similarly ask for estimates on the smallest integer $f(n,k)$ such that if $m$ is the factor of $\binom{n}{k}$ containing all primes $\leq f(n,k)$ then $m > n^2$.

It is trivial that the number of prime factors is \[>\frac{\log \binom{n}{k}}{\log n},\] and this inequality becomes (asymptotic) equality if $k>n^{1-o(1)}$.

If $n$ and $k$ are fixed then can one say anything about the set of integers so represented?

See also [677].

This function is closely related to the problem of gaps between primes (see [4]). The best known upper bound is due to Iwaniec [Iw78], \[Y(x) \ll x^2.\] The best lower bound is due to Ford, Green, Konyagin, Maynard, and Tao [FGKMT18], \[Y(x) \gg x\frac{\log x\log\log\log x}{\log\log x},\] improving on a previous bound of Rankin [Ra38].

Maier and Pomerance have conjectured that $Y(x)\ll x(\log x)^{2+o(1)}$.

See also [688] and [689].

Erdős could prove \[\epsilon_n \gg \frac{\log\log\log n}{\log\log n}.\]

See also [687] and [689].

See also [687] and [688].

Erdős believes that this is not possible, but could not disprove it. He could show that $p_k$ is about $e^{e^k}$ for almost all $n$, but the maximal value of $d_k(p)$ is assumed for much smaller values of $p$, at \[p=e^{(1+o(1))k}.\]

A similar question can be asked if we consider the density of integers whose $k$th smallest divisor is $d$. Erdős could show that this function is not unimodular.

If $A$ is a set of prime numbers then a necessary and sufficient condition is that $\sum_{p\in A}\frac{1}{p}=\infty$.

The general situation is more complicated. For example suppose $A$ is the union of $(n_k,(1+\eta_k)n_k)\cap \mathbb{Z}$ where $1\leq n_1<n_2<\cdots$ is a lacunary sequence. If $\sum \eta_k<\infty$ then the density of $M_A$ exists and is $<1$. If $\eta_k=1/k$, so $\sum \eta_k=\infty$, then the density exists and is $<1$.

Erdős writes it 'seems certain' that there is some threshold $\alpha\in (0,1)$ such that, if $\eta_k=k^{-\beta}$, then the density of $M_A$ is $1$ if $\beta <\alpha$ and the density is $<1$ if $\beta >\alpha$.

Erdős proved that \[\delta_1(n,m) \ll \frac{1}{(\log n)^c}\] for all $m$, for some constant $c>0$. Sharper bounds (for various ranges of $n$ and $m$) were given by Ford [Fo08].

See also [446].

See also [446].

Carmichael has asked whether there is an integer $n$ for which $\phi(m)=n$ has exactly one solution, that is, $\frac{f_{\max}(n)}{f_{\min}(n)}=1$. Erdős has proved that if such an $n$ exists then there must be infinitely many such $n$.

See also [51].

Linnik's theorem implies that there exists such a sequence of primes with \[q_k \leq e^{e^{O(k)}}.\]

See also [696].

Erdős writes it is 'easy to see' that $h(n)\to \infty$ for almost all $n$, and believed he could show that the normal order of $h(n)$ is $\log_*(n)$ (the iterated logarithm).

See also [695].

It is trivial that $\delta(m,\alpha)\to 0$ if $\alpha <1$, and Erdős could prove that the same is true for $\alpha=1$.

See also [696].

A problem of Erdős and Szekeres, who observed that \[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq \frac{\binom{n}{i}}{\binom{j}{i}}\geq 2^i\] (in particular the greatest common divisor is always $>1$). This inequality is sharp for $i=1$, $j=p$, and $n=2p$.

A problem of Erdős and Szekeres. A theorem of Sylvester and Schur says that for any $1\leq i\leq n/2$ there exists some prime $p>i$ which divides $\binom{n}{i}$.

Erdős and Szekeres further conjectured that $p\geq i$ can be improved to $p>i$ except in a few special cases. In particular this fails when $i=2$ and $n$ being some particular powers of $2$. They also found some counterexamples when $i=3$, but only one counterexample when $i\geq 4$: \[\textrm{gcd}\left(\binom{28}{5},\binom{28}{14}\right)=2^3\cdot 3^3\cdot 5.\]

A problem of Erdős and Szekeres. It is easy to see that $f(n)\leq n/P(n)$ for composite $n$, since if $j=p^k$ where $p^k\mid n$ and $p^{k+1}\nmid n$ then $\textrm{gcd}\left(n,\binom{n}{k}\right)=n/p^k$. This implies \[f(n) \leq (1+o(1))\frac{n}{\log n}.\]

It is known that $f(n)=n/P(n)$ when $n$ is the product of two primes. Another example is $n=30$.

For the second problem, it is easy to see that for any $n$ we have $f(n)\geq p(n)$, where $p(n)$ is the smallest prime dividing $n$, and hence there are infinitely many $n$ (those $=p^2)$ such that $f(n)\geq n^{1/2}$.

A problem of Erdős and Surányi [ErSu59], who proved that $g(n) \geq (2-o(1))n$, and that $g(3)=4$. Their upper bound construction took $A$ as the set of $p_ip_j$ for $i\neq j$, where $p_1<\cdots <p_\ell$ is some set of primes such that $2p_1^2>p_\ell^2$.

Gallai was the first to consider problems of this type, and observed that $g(2)=2$ and $g(3)\geq 4$.

In [Er92c] Erdős offers '100 dollars or 1000 rupees', whichever is more, for a proof or disproof. (In 1992 1000 rupees was worth approximately \$38.60.)

Erdős and Surányi similarly asked what is the smallest $c_n\geq 1$ such that in any interval $I\subset [0,\infty)$ of length $c_n\max(A)$ there exists some $B\subseteq I\cap \mathbb{N}$ with $\lvert B\rvert=n$ such that \[\prod_{a\in A} a \mid \prod_{b\in B}b.\] They prove $c_2=1$ and $c_3=\sqrt{2}$, but have no good upper or lower bounds in general.

See also [709].

A problem of Erdős and Surányi [ErSu59], who proved \[(\log n)^c \ll f(n) \ll n^{1/2}\] for some constant $c>0$.

See also [708].

A problem of Erdős and Pomerance [ErPo80], who proved \[n\left(\frac{\log n}{\log\log n}\right)^{1/2}\ll f(n)\leq (2+o(1))n(\log n)^{1/2}.\]

In [Er92c] Erdős offered 2000 rupees for an asymptotic formula; for uniform comparison across prizes I have converted this using the 1992 exchange rates.

See also [711].

A problem of Erdős and Pomerance [ErPo80], who proved that \[\max_m f(n,m) \ll n^{3/2}.\]

In [Er92c] Erdős offered 1000 rupees for a proof of either; for uniform comparison across prizes I have converted this using the 1992 exchange rates.

See also [710].

While we do not have a full understanding of the growth of $W(3,k)$, both of the specific challenges of Erdős have been met.

Green [Gr22] established the superpolynomial lower bound \[W(3,k) \geq \exp\left( c\frac{(\log k)^{4/3}}{(\log\log k) ^{1/3}}\right)\] for some constant $c>0$ (in particular disproving a conjecture of Graham that $W(3,k)\ll k^2$). Hunter [Hu22] improved this to \[W(3,k) \geq \exp\left( c\frac{(\log k)^{2}}{\log\log k}\right).\] The first to show that $W(3,k) < \exp(k^c)$ for some $c<1$ was Schoen [Sc21]. The best upper bound currently known is \[W(3,k) \ll \exp\left( O((\log k)^9)\right),\] which follows from the best bounds known for sets without three-term arithmetic progressions (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]).

A conjecture of Erdős, Graham, Ruzsa, and Straus [EGRS75]. For comparison the classical estimate of Mertens states that \[\sum_{p\leq n}\frac{1}{p}\sim \log\log n.\] By $n\in (p/2,p)\pmod{p}$ we mean $n\equiv r\pmod{p}$ for some integer $r$ with $p/2<r<p$.

A conjecture of Erdős, Graham, Ruzsa, and Straus [EGRS75]. It is open even for $k=2$.

Balakran [Ba29] proved this holds for $k=1$ - that is, $(n+1)^2\mid \binom{2n}{n}$ for infinitely many $n$. It is a classical fact that $(n+1)\mid \binom{2n}{n}$ for all $n$ (see Catalan numbers).

Erdős, Graham, Ruzsa, and Straus observe that the method of Balakran can be further used to prove that there are infinitely many $n$ such that \[(n+k)!(n+1)! \mid (2n)!\] (in fact this holds whenever $k<c \log n$ for some small constant $c>0$).

Erdős [Er68c] proved that if $a!b!\mid n!$ then $a+b\leq n+O(\log n)$.

A question of Erdős, Graham, Ruzsa, and Straus [EGRS75]. Erdős [Er68c] proved that if $a!b!\mid n!$ then $a+b\leq n+O(\log n)$.

By Legendre's formula $a! b! \mid n!(a+b-n)!$ is true if and only if for all primes $p$ \[s_p(n)+s_p(a+b-n) \leq s_p(a)+s_p(b),\] where $s_p(n)$ is the sum of the base $p$ digits of $n$.

See also [729].

Erdős [Er68c] proved that if $a!b!\mid n!$ then $a+b\leq n+O(\log n)$. The proof is easy, and can be done with powers of $2$ alone: Legendre's formula implies that if $2^k$ is the highest power of $2$ dividing $n!$ then $k=n+O(\log n)$, and hence if $a!b!\mid n!$ then $a+b\leq n+O(\log n)$.

This problem is asking if $a!b!\mid n!$ 'ignoring what happens on small primes' still implies $a+b+\leq n+O(\log n)$.

See also [728].

A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who believed there is 'no doubt' that the answer is yes.

For example $(87,88)$ and $(607,608)$.

Kummer's theorem implies that, for all odd primes $p$, $p\mid \binom{2n}{n}$ if and only some base $p$ digit of $n$ is $>p/2$, and hence $(n,n+1)$ has the required property if for all primes $p\leq n$ we have $n\not\in \{\frac{p-1}{2},p-1\}\pmod{p}$. Standard heuristics then predict there should be \[\gg \frac{x}{(\log x)^2}\] many such $n\leq x$.

A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who say it is 'not hard to show that', for almost all $n$, the minimal such $m$ satisfies \[m=\exp((\log n)^{1/2+o(1)}).\]

The Cameron-Erdős conjecture. It is trivial to see that $f(n) \geq 2^{\frac{n}{2}}$, considering all subsets of $[n/2,n]$.

This is true, and in fact $f(n) \ll 2^{n/2}$, which was proved independently by Green [Gr04] and Sapozhenko [Sa03]. In fact, both papers prove the stronger asymptotic $f(n) \sim c_n 2^{n/2}$, where $c_n$ takes on one of two values depending on the parity of $n$.

A conjecture of Erdős and Turán. Erdős and Fuchs [ErFu56] proved that the answer is no in a strong form: in fact even \[\sum_{n\leq N} 1_A\ast 1_A(n) = cN+o\left(\frac{N^{1/4}}{(\log N)^{1/2}}\right)\] is impossible. The error term here was improved to $N^{1/4}$ by Jurkat (unpublished) and Montgomery and Vaughan [MoVa90].

The case of $1_A\ast 1_A(n)$ is the subject of [763].

The answer is no, proved in a strong form by Vaughan [Va72], who showed that in fact \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+o\left(\frac{N^{1/4}}{(\log N)^{1/2}}\right)\] is impossible. Vaughan proves a more general result that applies to any $h$-fold convolution, with different main terms permitted.

Erdős could prove that there exists some constant $c>0$ such that for all large $N$ \[\exp(-c\sqrt{\log N}\log\log N)\leq \frac{\lvert A\cap [1,N]\rvert}{N}\] and \[\frac{\lvert A\cap [1,N]\rvert}{N}\leq \exp(-(1+o(1))\sqrt{\log N\log\log N}).\] Erdős asked about this because $\lvert A\cap [1,N]\rvert$ provides an upper bound for the number of integers $n\leq N$ for which there is a non-cyclic simple group of order $n$.

A problem first investigated by Hadwiger, who proved the lower bound \[c(n) \geq 2^n+2^{n-1}.\] It is easy to see that $c(2)=6$. Meier conjectured $c(3)=48$. Burgess and Erdős [Er74b] proved \[c(n) \ll n^{n+1}.\] Erdős wrote 'I am certain that if $n+1$ is a prime then $c(n)>n^n$.'.

It is easy to see that $h(n)=n+1$ if and only if $n+1$ is prime, and that $h(n)$ is unbounded for odd $n$.

It is probably true that $h(n)=3$ for infinitely many $n$.

A conjecture of Erdős and Graham, who proved the lower bound \[f(n)\geq \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}.\] Their proof is to note that we can assume that $m< \binom{n+1}{2}$ and then, for any $m$, take $S=\{ kp : 1\leq k<\frac{n}{p}\}$ where $p$ is the least prime that does not divide $m$ (so $p<(2+o(1))\log n$).

The complementary bound \[f(n) \leq \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}\] was proved by Alon and Freiman [AlFr88], who chose $m$ as the least common multiple of $\{1,\ldots,s\}$ where $s$ is maximal such that $m\leq \frac{n^2}{20(\log n)^2}$.

Erdős [Er84d] proved that \[H_k(n) \ll n^{2/3}\] (where the implied constant is absolute). The lower bound $H_k(n)\gg n^{1/2}$ follows from the fact that any set of size $n$ contains a Sidon set of size $\gg n^{1/2}$ (see [530]).

The answer is yes, and in fact \[H_k(n) \gg_k n^{2/3},\] proved by Alon and Erdős [AlEr85]. We sketch their proof as follows: take a random subset $A'\subset A$, including each $n\in A'$ with probability $\asymp n^{-1/3}$. The number of non-trivial additive quadruples in $A$ is $\ll n^2$ and hence only $\ll n^{2/3}$ non-trivial additive quadruples remain in $A'$. Since the size of the random subset is $\gg n^{2/3}$, all of the remaining non-trivial additive quadruples can be removed by removing at most $\lvert A'\rvert/2$ (choosing the constants suitably).

A question of Alon and Erdős [AlEr85], who proved $\lvert A\rvert \geq N^{2/3-o(1)}$ is possible (via a random subset), and observed that \[\lvert A\rvert \ll \frac{N}{(\log N)^{1/4}},\] since (as shown by Landau) the density of the sums of two squares decays like $(\log N)^{-1/2}$.

This question appears in a paper of Alon and Erdős [AlEr85], although the general topic was first considered by Pisier [Pi83], who observed that the converse holds, and proved that being proportionately dissociated is equivalent to being a 'Sidon set' in the harmonic analysis sense; that is, whenever $f:A\to \mathbb{C}$ there exists some $\theta\in [0,1]$ such that \[\| f\|_1 \ll \left\lvert\sum_{n\in A} f(n)e(n\theta)\right\rvert,\] where $e(x)=e^{2\pi ix}$.

Alon and Erdős write that it 'seems unlikely that [this] is also sufficient'. They also point out the same question can be asked replacing dissociated with Sidon (in the additive combinatorial sense).

A problem of Deaconescu. Erdős expects that the least such prime is much smaller than $P$, and in fact satisfies $p\leq n^{O(1)}$. Deaconescu has verified this conjecture for $n\leq 1000$.

A question of Brown, Erdős, and Freedman [BEF90]. It is a classical fact that the squares do not contain arithmetic progressions of length $4$.

An affirmative answer to the first question implies an affirmative answer to the second.

Solymosi [So07] conjectured the answer to the second question is no. Cilleruelo and Granville [CiGr07] have observed that the answer to the second question is no conditional on the Bombieri-Lang conjecture.

An example of Schinzel and Szekeres [ScSz59] shows that this would be best possible (up to the value of $c$).

See also [542].

An example of such a set with density $1/4$ is given by the integers $\equiv 2\pmod{4}$.

Selfridge constructed such a set with density $1/e-\epsilon$ for any $\epsilon>0$: let $p_1<\cdots<p_k$ be a sequence of large consecutive primes such that \[\sum_{i=1}^k\frac{1}{p_i}<1<\sum_{i=1}^{k+1}\frac{1}{p_i},\] and let $A$ be those integers divisible by exactly one of $p_1,\ldots,p_k$.

For the second question the set of integers with a prime factor $>N^{1/2}$ give an example of a set with size $\geq (\log 2)N$. Erdős could improve this constant slightly.

Erdős [Er38] proved there exist constants $0<c_1\leq c_2$ such that \[\pi(n)+c_1n^{2/3}(\log n)^{-2}\leq F(n) \leq \pi(n)+c_2n^{2/3}(\log n)^{-2}.\]

Erdős [Er69] gave a simple proof that $F(n) \leq \pi(n)+n^{2/3}$: we define a graph with vertex set the union of those integers in $[1,n^{2/3}]$ with all primes $p\in (n^{2/3},n]$. We have an edge $u\sim v$ if and only if $uv\in A$. It is easy to see that every $m\leq n$ can be written as $uv$ where $u\leq n^{2/3}$ and $v$ is either prime or $\leq n^{2/3}$, and hence there are $\geq \lvert A\rvert$ many edges. This graph contains no path of length $3$ and hence must be a tree and have fewer edges than vertices, and we are done. This can be improved to give the upper bound mentioned by using a subset of integers in $[1,n^{2/3}]$.

More generally, one can ask for such an asymptotic for the size of sets such that no $a\in A$ divides the product of $r$ distinct other elements of $A$, with the exponent $2/3$ replaced by $\frac{2}{r+1}$.

See also [425].

Erdős proved [Er66] \[g(n) \leq \pi(n)+O\left(\frac{x^{1/2}}{\log n}\right).\] This upper bound would be essentially best possible, since one could take $A$ to be all primes and squares of primes.

Erdős [Er64d] proved that if $2^{r-1}<k\leq 2^r$ then \[g_k(n) \sim \frac{(\log\log n)^{r-1}}{(r-1)!\log n}n\] (which is the asymptotic count of those integers $\leq n$ with $r$ distinct prime factors).

In particular the asymptotics of $g_k(n)$ are known; in this problem Erdős was asking about the second order terms. For $k=3$ he could prove the existence of some $0<c_1\leq c_2$ such that \[\frac{\log\log n}{\log n}n+c_1\frac{n}{(\log n)^2}\leq g_k(n)\leq \frac{\log\log n}{\log n}n+c_2\frac{n}{(\log n)^2}.\]

The special case $k=2$ is the subject of [425].

Erdős [Er74b] proved that there exists a constant $c>0$ such that \[H(n) > \exp(n^{c/(\log\log n)^2})\] for infinitely many $n$.

The sequence $H(n)$ for $1\leq n\leq 10$ is \[3,3,3,6,3,18,3,6,3,12.\] The sequence of $n$ for which $(2^n-1,3^n-1)=1$ is A263647 in the OEIS.

Pillai proved that $\limsup g(n)=\infty$ and Erdős [Er35b] proved that there exists some constant $c>0$ such that $g(n) >n^c$ for infinitely many $n$.

This conjecture would follow if we knew that, for every $\epsilon>0$, there are $\gg_\epsilon \frac{x}{\log x}$ many primes $p<x$ such that all prime factors of $p-1$ are $<p^\epsilon$.

See also [416].

A similar question can be asked for $n+\sigma(n)$, where $\sigma$ is the sum of divisors function.

Erdős [Er74b] writes it is 'easy to prove the analogous result for $\phi(n)$'.

The answer is yes, proved by Pollack [Po15b].

Erdős [Er74b] proved that $\limsup h(x)/x= \infty$, and claimed a similar proof for this problem. A complete proof that $h(x)/x\to \infty$ was provided by Pollack and Pomerance [PoPo16].

A similar question can be asked if we replace the condition $(a,b)=1$ with the condition that $a$ and $b$ are squarefree.

A problem of Benkoski and Erdős. This could be true with $C=3$. We must have $C>2$ since $\sigma(70)=144$ but $70$ is not the distinct sum of integers from $\{1,2,5,7,10,14,35\}$.

Erdős suggested that as $C\to \infty$ only divisors at most $\epsilon n$ need to be used, where $\epsilon \to 0$.

See also [18].

A stronger form of [248].

A conjecture of Graham. Lehmer has conjectured that $\phi(n)\mid n-1$ if and only if $n$ is prime. It is an easy exercise to show that $\phi(n) \mid n$ if and only if $n=2^a3^b$.

Mordell proved that \[\limsup_{n\to \infty} 1_A\ast 1_A(n)=\infty\] and Mahler [Ma35b] proved \[1_A\ast 1_A(n) \gg (\log n)^{1/4}\] for infinitely many $n$.

For example $220$ and $284$. Erdős [Er55b] proved that $A(x)=o(x)$, and Pomerance [Po81] improved this to \[A(x) \leq x \exp(-(\log x)^{1/3})\] and later [Po15] to \[A(x) \leq x \exp(-(\tfrac{1}{2}+o(1))(\log x\log\log x)^{1/2}).\]

It is easy to see that $\liminf a_n/n<\infty$ is possible.

See also [359].

A problem of Erdős, Graham, and Selfridge. For example, $t_n=6$ since $6\cdot 8\cdot 12=24^2$. Erdős originally asked whether the set with $t_n\geq n^{1-o(1)}$ has density zero. Selfridge then proved that $t_n=P(n)$, where $P(n)$ is the largest prime divisor of $n$, if $P(n)>\sqrt{2n}+1$, and $t_n \ll n^{1/2}$ otherwise.

Bui, Pratt, and Zaharescu [BPZ24] proved that the distribution of $t_n$ continues to follow $P(n)$, in that for any fixed $c\in (0,1]$ \[\lim_{x\to \infty}\frac{\lvert \{ n\leq x : t_n\leq n^c\}\rvert}{x} = \lim_{x\to \infty}\frac{\lvert \{ n\leq x : P(n)\leq n^c\}\rvert}{x}.\] They also prove that for at least $x^{1-o(1)}$ many $n\leq x$ we have \[t_n \leq \exp(O(\sqrt{\log n\log\log n}))\] and for all non-square $n$ \[t_n \gg (\log\log n)^{6/5}(\log\log\log n)^{-1/5}.\]

See also [437].

A problem of Burr and Erdős. A similar question can be asked for the set of $k$th powers for any $k\geq 3$.

See also [54] and [55].

A problem of Erdős and Sárközy.

See also [848].

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

Indeed, one proves (by induction) the stronger fact that such a representation always exists, and moreover if $n$ is even then all the summands can be taken to be even: if $n=2m$ we are done applying the inductive hypothesis to $m$. Otherwise if $n$ is odd then let $3^k$ be the largest power of $3$ which is $\leq n$ and apply the inductive hypothesis to $n-3^k$ (which is even).

See also [123].

A problem of Erdős and Sárközy.

See also [844].

Erdős [Er96b] credits this to himself and Gordon 'many years ago', but it is more commonly known as Singmaster's conjecture. For $t=3$ one could take $a=120$, and for $t=4$ one could take $a=3003$. There are no known examples for $t\geq 5$.

Both Erdős and Singmaster believed the answer to this question is no, and in fact that there exists an absolute upper bound on the number of solutions.

Matomäki, Radziwill, Shao, Tao, and Teräväinen [MRSTT22] have proved that there are always at most two solutions if we restrict $k$ to \[k\geq \exp((\log n)^{2/3+\epsilon}),\] assuming $a$ is sufficiently large depending on $\epsilon>0$.

For just $x,y$ and $x+1,y+1$ one can take \[x=2(2^r-1)\] and \[y = x(x+2).\] Erdős also asked whether there are any other examples. Matthew Bolan has observed that $x=75$ and $y=1215$ is another example, since \[75 = 3\cdot 5^2 \textrm{ and }1215 = 3^5\cdot 5\] while \[76 = 2^2\cdot 19\textrm{ and }1216 = 2^6\cdot 19.\] No other exampes are known. This sequence is listed as A343101 at the OEIS.

See also [677].

Romanoff [Ro34] proved that the set of integers of the form $2^k+p$ (where $p$ is prime) has positive lower density.

See also [205].

Brun's sieve implies $h(x) \to \infty$ as $x\to \infty$.

In [Er85c] Erdős omits the condition that $t$ be even, but this is clearly necessary.

Commonly known as the second Hardy-Littlewood conjecture. In [Er85c] Erdős describes it as 'an old conjecture of mine which was probably already stated by Hardy and Littlewood'.

This is probably false, since Hensley and Richards [HeRi73] have shown that this is false assuming the Hardy-Littlewood prime tuples conjecture.

Erdős [Er85c] reports Straus as remarking that the 'correct way' of stating this conjecture would have been \[\pi(x+y) \leq \pi(x)+2\pi(y/2).\] Clark and Jarvis [ClJa01] have shown this is also incompatible with the prime tuples conjecture.

In [Er85c] Erdős conjectures the weaker result (which in particular follows from the conjecture of Straus) that \[\pi(x+y) \leq \pi(x)+\pi(y)+O\left(\frac{y}{(\log y)^2}\right),\] which the Hensley and Richards result shows (conditionally) would be best possible. Richards conjectured that this is false.

Erdős and Richards further conjectured that the original inequality is true almost always - that is, the set of $x$ such that $\pi(x+y)\leq \pi(x)+\pi(y)$ for all $y<x$ has density $1$. They could only prove that this set has positive lower density.

They also conjectured that for every $x$ the inequality $\pi(x+y)\leq \pi(x)+\pi(y)$ is true provided $y \gg (\log x)^C$ for some large constant $C>0$.

Hardy and Littlewood proved \[\pi(x+y) \leq \pi(x)+O(\pi(y)).\] The best known in this direction is a result of Montgomery and Vaughan [MoVa73], which shows \[\pi(x+y) \leq \pi(x)+2\frac{y}{\log y}.\]

Erdős [Er70] notes that \[f_k(N) \ll \frac{\log N}{\log\log N}.\] Indeed, let $A$ be such a set. This in particular implies that, for every $t$, there are $<k$ solutions to $t=ap$ with $a\in A$ and $p$ prime, whence \[\sum_{n\in A}\frac{1}{n}\sum_{p<N}\frac{1}{p}< k \sum_{t<N^2}\frac{1}{t} \ll \log N,\] and the bound follows since $\sum_{p<N}\frac{1}{p}\gg \log\log N$.

The analogous question with natural density in place of logarithmic density (that is, we measure $\lvert A\rvert$ in place of $\sum_{n\in A}\frac{1}{n}$) is the subject of [536]. In particular Erdős [Er70] has constructed $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert \gg N$ where no four have the same pairwise least common multiple, and hence the interest of the natural density problem is the $k=3$ case.

A related combinatorial problem is asked at [857].

Alexander [Al66] and Erdős, Sárközi, and Szemerédi [ESS68] proved that this maximum is $o(1)$ (as $N\to \infty$). This condition on $A$ is a stronger form of the usual primitive condition. If $A$ is merely primitive then Behrend [Be35] proved \[\frac{1}{\log N}\sum_{n\in A}\frac{1}{n}\ll \frac{1}{\sqrt{\log\log N}}.\]

An example of such a set $A$ is the set of all integers in $[N^{1/2},N]$ divisible by some prime $>N^{1/2}$.

See also [143].

Erdős [Er70] proved that $d_t$ always exists, and that there exist some constants $c_3,c_4>0$ such that \[\frac{1}{(\log t)^{c_3}} < d_t < \frac{1}{(\log t)^{c_4}}.\]