OPEN - $500

If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then
\[N \gg 2^{n}.\]

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

See also [350].

SOLVED - $1000

Can the smallest modulus of a covering system be arbitrarily large?

Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown 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$.

OPEN - $5000

If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?

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

SOLVED - $10000

For any $C>0$ are there infinitely many $n$ such that
\[p_{n+1}-p_n> C\frac{\log\log n\log\log\log\log n}{(\log\log \log n)^2}\log n?\]

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

OPEN

Let $C\geq 0$. Is there an infinite sequence of $n_i$ such that
\[\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?\]

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.

SOLVED - $100

Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?

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

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

OPEN

Is there a covering system all of whose moduli are odd?

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

SOLVED

For any finite colouring of the integers is there a covering system all of whose moduli are monochromatic?

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.

OPEN

Let $A$ be the set of all integers not of the form $p+2^{k}+2^l$ (where $k,l\geq 0$ and $p$ is prime). Is the upper density of $A$ positive?

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

OPEN

Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of 2?

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

OPEN

Is every odd $n$ the sum of a squarefree number and a power of 2?

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

OPEN

Let $A$ be an infinite set such that there are no distinct $a,b,c\in A$ such that $a\mid (b+c)$. Is there such an $A$ with
\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?\]

Asked by Erdős and Sárközy, who proved that $A$ must have density $0$. The set of $p^2$, where $p\equiv 3\pmod{4}$ is prime, has this property. Note that such a set cannot contain a three-term arithmetic progression, and hence by the bound of Kelley and Meka [KeMe23] we have
\[\lvert A\cap\{1,\ldots,N\}\rvert\ll \exp(-O((\log N)^{1/12}))N\]
for all large $N$.

In [Er95c] Erdős asks whether $\sum_{n\in A}\frac{1}{n}<\infty$ (this follows from the above bound of Kelley and Meka).

SOLVED - $100

Let $A\subseteq \{1,\ldots,N\}$ be such that there are no $a,b,c\in A$ such that $a\mid(b+c)$ and $a<\min(b,c)$. Is it true that $\lvert A\rvert\leq N/3+O(1)$?

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

OPEN

Let $A\subseteq \mathbb{N}$. Let $B\subseteq \mathbb{N}$ be the set of integers which are representable in exactly one way as the sum of two elements from $A$. Is it true that for all $\epsilon>0$ and large $N$
\[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/2-\epsilon}.\]

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.

OPEN

Is it true that
\[\sum_{n=1}^\infty(-1)^n\frac{n}{p_n}\]
converges, where $p_n$ is the sequence of primes?

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.

SOLVED

Is the set of odd integers not of the form $2^k+p$ the union of an infinite arithmetic progression and a set of density $0$?

OPEN

We call $m$ practical if every integer $n<m$ is the sum of distinct divisors of $m$. If $m$ is practical then let $h(m)$ be such that $h(m)$ many divisors always suffice.

Are there infinitely many practical $m$ such that \[h(m) < (\log\log m)^{O(1)}?\] Is it true that $h(n!)<n^{o(1)}$?

SOLVED

Let $A\subset\mathbb{N}$ be infinite. Must there exist some $k\geq 1$ such that almost all integers have a divisor of the form $a+k$ for some $a\in A$?

Asked by Erdős and Tenenbaum. Ruzsa has found a counterexample (according to Erdős in [Er95], although I cannot find a paper in which this appears). 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$.

SOLVED - $100

An $\epsilon$-almost covering system is a set of congruences $a_i\pmod{n_i}$ for distinct moduli $n_1<\ldots<n_k$ such that the density of those integers which satisfy none of them is $\leq \epsilon$. Is there a constant $C>1$ such that for every $\epsilon>0$ and $N\geq 1$ there is an $\epsilon$-almost covering system with $N\leq n_1<\cdots <n_k\leq CN$?

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

OPEN - $500

If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.

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

SOLVED - $100

Is there an explicit construction of a set $A\subseteq \mathbb{N}$ such that $A+A=\mathbb{N}$ but $1_A\ast 1_A(n)=o(n^\epsilon)$ for every $\epsilon>0$?

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

OPEN - $1000

Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$,
\[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\]

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

OPEN

Is there a set $A\subset\mathbb{N}$ such that
\[\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)\]
and such that every large integer can be written as $p+a$ for some prime $p$ and $a\in A$? Can the bound $O(\log N)$ be achieved?

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.

OPEN

Let $A\subset\mathbb{N}$ be such that every large integer can be written as $n^2+a$ for some $a\in A$ and $n\geq 0$. What is the smallest possible value of
\[\limsup \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}?\]

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

SOLVED

For any permutation $\pi\in S_n$ of $\{1,\ldots,n\}$ let $S(\pi)$ count the number of distinct consecutive sums, that is, sums of the shape $\sum_{u\leq i\leq v}\pi(i)$. Is it true that
\[S(\pi) = o(n^2)\]
for all $\pi\in S_n$?

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

SOLVED

Let $B\subseteq\mathbb{N}$ be an additive basis of order $k$ with $0\in B$. Is it true that for every $A\subseteq\mathbb{N}$ we have
\[d_s(A+B)\geq \alpha+\frac{\alpha(1-\alpha)}{k},\]
where $\alpha=d_s(A)$ and
\[d_s(A) = \inf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N}\]
is the Schnirelmann density?

Erdős [Er36c] proved this is true with $k$ replaced by $2k$ in the denominator.

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

OPEN

Find the optimal constant $c>0$ such that the following holds.

For all sufficiently large $N$, if $A\sqcup B=\{1,\ldots,2N\}$ is a partition into two equal parts, so that $\lvert A\rvert=\lvert B\rvert=N$, then there is some $x$ such that the number of solutions to $a-b=x$ with $a\in A$ and $b\in B$ is at least $cN$.

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

SOLVED

We say that $A\subset \mathbb{N}$ is an essential component if $d_s(A+B)>d_s(B)$ for every $B\subset \mathbb{N}$ with $0<d_s(B)<1$ where $d_s$ is the Schnirelmann density.

Can a lacunary set $A\subset\mathbb{N}$ be an essential component?

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

OPEN

Is there $A\subset\mathbb{N}$ which is not an additive basis, but is such that for every set $B\subseteq\mathbb{N}$ of density $\beta$ and every $N$ there exists $a\in A$ such that
\[\frac{\lvert B\cap (B+a)\cap \{1,\ldots,N\}\rvert}{N}\geq (\beta+f(\beta))N\]
where $f(\beta)>0$ for $0<\beta <1 $.

OPEN - $50

Is there an infinite Sidon set $A\subset \mathbb{N}$ such that
\[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\]
for all $\epsilon>0$?

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

OPEN - $500

Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct for $a,b,c\in A$ (aside from the trivial coincidences). Is it true that
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=0?\]

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

OPEN - $100

If $A,B\subset \{1,\ldots,N\}$ are two Sidon sets such that $(A-A)\cap(B-B)=\{0\}$ then is it true that
\[ \binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1),\]
where $f(N)$ is the maximum possible size of a Sidon set in $\{1,\ldots,N\}$? If $\lvert A\rvert=\lvert B\rvert$ then can this bound be improved to
\[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq (1-c)\binom{f(N)}{2}\]
for some constant $c>0$?

SOLVED

Let $k\geq 2$. Is there an integer $n_k$ such that, if $D=\{ 1<d<n_k : d\mid n_k\}$, then for any $k$-colouring of $D$ there is a monochromatic subset $D'\subseteq D$ such that $\sum_{d\in D'}\frac{1}{d}=1$?

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

SOLVED - $100

If $\delta>0$ and $N$ is sufficiently large in terms of $\delta$, and $A\subseteq\{1,\ldots,N\}$ is such that $\sum_{a\in A}\frac{1}{a}>\delta \log N$ then must there exist $S\subseteq A$ such that $\sum_{n\in S}\frac{1}{n}=1$?

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

SOLVED

Let $A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}$ be such that $\phi(a_1)<\cdots<\phi(a_t)$. The primes are such an example. Are they the largest possible? Can one show that $\lvert A\rvert<(1+o(1))\pi(N)$ or even $\lvert A\rvert=o(N)$?

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

OPEN

Is there an infinite set $A\subset \mathbb{N}$ such that for every $a\in A$ there is an integer $n$ such that $\phi(n)=a$, and yet if $n_a$ is the smallest such integer then $n_a/a\to \infty$ as $a\to\infty$?

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

OPEN - $250

Let $A$ be a finite set of integers. Is it true that for every $\epsilon>0$
\[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\]

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 $o(\lvert A\rvert^2)$. 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, it is reasonable to conjecture (although I cannot find a record of Erdős himself actually doing so) that for any $m\geq 2$ and finite set of integers (or reals, etc) $A$ that \[\max( \lvert mA\rvert,\lvert A^m\rvert)\gg \lvert A\rvert^{m-o(1)}.\] See [53] for more on this generalisation.

SOLVED

Let $A$ be a finite set of integers. Is it true that, for every $k$, if $\lvert A\rvert$ is sufficiently large depending on $k$, then there are least $\lvert A\rvert^k$ many integers which are either the sum or product of distinct elements of $A$?

SOLVED - $100

A set of integers $A$ is Ramsey $2$-complete if, whenever $A$ is $2$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$.

Burr and Erdős [BuEr85] showed that there exists a constant $c>0$ such that it cannot be true that \[\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2\] for all large $N$ and that there exists a Ramsey $2$-complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert < (2\log_2N)^3.\] Improve either of these bounds.

SOLVED - $250

A set of integers $A$ is Ramsey $r$-complete if, whenever $A$ is $r$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. Prove any non-trivial bounds about the growth rate of such an $A$ for $r>2$.

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

SOLVED

Suppose $A\subseteq \{1,\ldots,N\}$ is such that there are no $k+1$ elements of $A$ which are relatively prime. An example is the set of all multiples of the first $k$ primes. Is this the largest such set?

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

OPEN - $500

Is there $A\subseteq \mathbb{N}$ such that
\[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\]
exists and is $\neq 0$?

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.

SOLVED

Let $F_{k}(N)$ be the size of the largest $A\subseteq \{1,\ldots,N\}$ such that the product of no $k$ many distinct elements of $A$ is a square. Is $F_5(N)=(1-o(1))N$? More generally, is $F_{2k+1}(N)=(1-o(1))N$?

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$ (for which $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$.

OPEN

Let $f(n)$ be a number theoretic function which grows slowly (e.g. slower than $(\log n)^{1-c}$) and $F(n)$ be such that for almost all $n$ we have $f(n)/F(n)\to 0$. When are there infinitely many $x$ such that
\[\frac{\#\{ n\in \mathbb{N} : n+f(n)\in (x,x+F(x))\}}{F(x)}\to \infty?\]

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

OPEN - $250

Let $a,b,c$ be three integers which are pairwise coprime. Is every large integer the sum of distinct integers of the form $a^kb^lc^m$ ($k,l,m\geq 0$), none of which divide any other?

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

OPEN

Let $3\leq d_1<d_2<\cdots <d_k$ be integers such that
\[\sum_{1\leq i\leq k}\frac{1}{d_i-1}\geq 1.\]
Can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i\in \{0,1\}$ and $a_i$ has only the digits $0,1$ when written in base $d_i$?

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

OPEN

Let $A\subseteq \mathbb{N}$ be the set of integers which have only the digits $0,1$ when written base $3$, and $B\subseteq \mathbb{N}$ be the set of integers which have only the digits $0,1$ when written base $4$. Does $A+B$ have positive density?

Conjectured by Burr, Erdős, Graham, and Li [BuErGrLi96].

OPEN - $250

Let $f(n)$ be maximal such that if $A\subseteq\mathbb{N}$ has $\lvert A\rvert=n$ then $\prod_{a\neq b\in A}(a+b)$ has at least $f(n)$ distinct prime factors. Is it true that $f(n)/\log n\to\infty$?

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.

OPEN

Let $\epsilon>0$ and $N$ be sufficiently large depending on $\epsilon$. Is there $A\subseteq\{1,\ldots,N\}$ such that no $a\in A$ divides the sum of any distinct elements of $A\backslash\{a\}$ and $\lvert A\rvert\gg N^{1/2-\epsilon}$?

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

SOLVED - $250

The density of integers which have two divisors $d_1,d_2$ such that $d_1<d_2<2d_1$ exists and is equal to $1$.

OPEN

Let $F(k)$ be the number of solutions to
\[ 1= \frac{1}{n_1}+\cdots+\frac{1}{n_k},\]
where $1\leq n_1<\cdots<n_k$ are distinct integers. Find good estimates for $F(k)$.

SOLVED

A set $A\subset \mathbb{N}$ is primitive if no member of $A$ divides another. Is the sum
\[\sum_{n\in A}\frac{1}{n\log n}\]
maximised over all primitive sets when $A$ is the set of primes?

SOLVED

Show that, for any $n\geq 5$, the binomial coefficient $\binom{2n}{n}$ is not squarefree.

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

OPEN

Is it true that all sufficiently large $n$ can be written as $2^k+m$ for some $k\geq 0$, where $\Omega(m)<\log\log m$? (Here $\Omega(m)$ is the number of prime divisors of $m$ counted with multiplicity.) What about $<\epsilon \log\log m$? Or some more slowly growing function?

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.

SOLVED

Let $x>0$ be a real number. For any $n\geq 1$ let
\[R_n(x) = \sum_{i=1}^n\frac{1}{m_i}<x\]
be the maximal sum of $n$ distinct unit fractions which is $<x$.

Is it true that, for almost all $x$, for sufficiently large $n$, we have \[R_{n+1}(x)=R_n(x)+\frac{1}{m},\] where $m$ is minimal such that $m$ does not appear in $R_n(x)$ and the right-hand side is $<x$? (That is, are the best underapproximations eventually always constructed in a 'greedy' fashion?)

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 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 such a number.)

OPEN

Let $s_1<s_2<\cdots$ be the sequence of squarefree numbers. Is it true that, for any $\epsilon>0$ and large $n$,
\[s_{n+1}-s_n \ll_\epsilon s_n^{\epsilon}?\]
Is it true that
\[s_{n+1}-s_n \leq (1+o(1))\frac{\pi^2}{6}\frac{\log s_n}{\log\log s_n}?\]

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.

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

SOLVED

Let $n\geq 1$ and
\[A=\{a_1<\cdots <a_{\phi(n)}\}=\{ 1\leq m<n : (m,n)=1\}.\]
Is it true that
\[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^2 \ll \frac{n^2}{\phi(n)}?\]

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

SOLVED

Is there a set $A\subset\mathbb{N}$ such that, for all large $N$,
\[\lvert A\cap\{1,\ldots,N\}\rvert \ll N/\log N\]
and such that every large integer can be written as $2^k+a$ for some $k\geq 0$ and $a\in A$?

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

OPEN

Let $n_1<n_2<\cdots$ be the sequence of integers which are the sum of two squares. Explore the behaviour of (i.e. find good upper and lower bounds for) the consecutive differences $n_{k+1}-n_k$.

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

OPEN

Let $N_k=2\cdot 3\cdots p_k$ and $\{a_1<a_2<\cdots <a_{\phi(N_k)}\}$ be the integers $<N_k$ which are relatively prime to $N_k$. Then, for any $c\geq 0$, the limit
\[\frac{\#\{ a_i-a_{i-1}\leq c \frac{N_k}{\phi(N_k)} : 2\leq i\leq \phi(N_k)\}}{\phi(N_k)}\]
exists and is a continuous function of $c$.

OPEN

Let $f(n)$ count the number of solutions to $n=p+2^k$ for prime $p$ and $k\geq 0$. Is it true that $f(n)=o(\log n)$?

SOLVED

Let $A\subseteq \mathbb{N}$ be a set such that $\lvert A\cap \{1,\ldots,N\}\rvert \gg \log N$ for all large $N$. Let $f(n)$ count the number of solutions to $n=p+a$ for $p$ prime and $a\in A$. Is it true that $\limsup f(n)=\infty$?

SOLVED

Let $f:\mathbb{N}\to \{-1,1\}$ be a multiplicative function. Is it true that
\[ \lim_{N\to \infty}\frac{1}{N}\sum_{n\leq N}f(n)\]
always exists?

OPEN

Is there an infinite set of primes $P$ such that if $\{a_1<a_2<\cdots\}$ is the set of integers divisible only by primes in $P$ then $\lim a_{i+1}-a_i=\infty$?

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.

OPEN

For every $n\geq 2$ there exist distinct integers $1\leq x<y<z$ such that
\[\frac{4}{n} = \frac{1}{x}+\frac{1}{y}+\frac{1}{z}.\]

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

OPEN

Let $a_1<a_2<\cdots$ be a sequence of integers such that
\[\lim_{n\to \infty}\frac{a_n}{a_{n-1}^2}=1\]
and $\sum\frac{1}{a_n}\in \mathbb{Q}$. Then, for all sufficiently large $n\geq 1$,
\[ a_n = a_{n-1}^2-a_{n-1}+1.\]

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

OPEN

Are there infinitely many $n$ such that, for all $k\geq 1$,
\[ \omega(n+k) \ll k,\]
where the implied constant depends only on $n$? (Here $\omega(n)$ is the number of distinct prime divisors of $n$.)

OPEN

Is
\[\sum_n \frac{\phi(n)}{2^n}\]
irrational? Here $\phi$ is the Euler totient function.

OPEN

Let $k\geq 1$ and $\sigma_k(n)=\sum_{d\mid n}d^k$. Is
\[\sum \frac{\sigma_k(n)}{n!}\]
irrational?

SOLVED

Let $a_1<a_2<\cdots $ be an infinite sequence of integers such that $a_{i+1}/a_i\to 1$. If every arithmetic progression contains infinitely many integers which are the sum of distinct $a_i$ then every sufficiently large integer is the sum of distinct $a_i$.

This was disproved by Cassels [Ca60].

OPEN

Let $A\subseteq \mathbb{N}$ be such that
\[\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert \to \infty\textrm{ as }x\to \infty\]
and
\[\sum_{n\in A} \{ \theta n\}=\infty\]
for every $\theta\in (0,1)$, where $\{x\}$ is the distance of $x$ from the nearest integer. Then every sufficiently large integer is the sum of distinct elements of $A$.

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

OPEN

Are there infinitely many $n$ such that there exists some $t\geq 2$ and $a_1,\ldots,a_t\geq 1$ such that
\[\frac{n}{2^n}=\sum_{1\leq k\leq t}\frac{a_k}{2^{a_k}}?\]
Is this true for all $n$? Is there a rational $x$ such that
\[x = \sum_{k=1}^\infty \frac{a_k}{2^{a_k}}\]
has at least two solutions?

Related to [260].

SOLVED

Let $X\subseteq \mathbb{R}^3$ be the set of all points of the shape
\[\left( \sum_{n\in A} \frac{1}{n},\sum_{n\in A}\frac{1}{n+1},\sum_{n\in A} \frac{1}{n+2}\right) \]
as $A\subseteq\mathbb{N}$ ranges over all infinite sets with $\sum_{n\in A}\frac{1}{n}<\infty$.
Does $X$ contain an open set?

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.

SOLVED

If a finite system of $r$ congruences $\{ a_i\pmod{n_i} : 1\leq i\leq r\}$ covers $2^r$ consecutive integers then it covers all integers.

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

OPEN

Is there an infinite Lucas sequence $a_0,a_1,\ldots,$ where $(a_0,a_1)=1$ and $a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$ such that all $a_k$ are composite, and yet no integer has a common factor with every term of the sequence?

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

OPEN

Let $k\geq 3$. Is there a choice of congruence classes $a_p\pmod{p}$ for every prime $p$ such that all except finitely many integers can be written as $a_p+tp$ for some prime $p$ and integer $t\geq k$?

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.

OPEN

Let $n_1<n_2<\cdots $ be an infinite sequence of integers with associated $a_i\pmod{n_i}$, such that for some $\epsilon>0$ we have $n_k>(1+\epsilon)k\log k$ for all $k$. Then
\[\#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for }1\leq i\leq k\}\neq o(k).\]

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

OPEN

Let $n_1<n_2<\cdots$ be an infinite sequence with associated congruence classes $a_i\pmod{n_i}$ such that the set of integers not satisfying any of the congruences $a_i\pmod{n_i}$ has density $0$.

Is it true that for every $\epsilon>0$ there exists some $k$ such that the density of integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is less than $\epsilon$?

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

OPEN

Let $A\subseteq \mathbb{N}$ be an infinite set and consider the following greedy algorithm for a rational $x\in (0,1)$: choose the minimal $n\in A$ such that $n\geq 1/x$ and repeat with $x$ replaced by $x-\frac{1}{n}$. If this terminates after finitely many steps then this produces a representation of $x$ as the sum of distinct unit fractions with denominators from $A$.

Does this process always terminate if $x$ has odd denominator and $A$ is the set of odd numbers? More generally, for which pairs $x$ and $A$ does this process terminate?

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.

OPEN

Let $p:\mathbb{Z}\to \mathbb{Z}$ be a polynomial whose leading coefficient is positive and such that there exists no $d\geq 2$ with $d\mid p(n)$ for all $n\geq 1$. Is it true that, for all sufficiently large $m$, there exist integers $1\leq n_1<\cdots <n_k$ such that
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\]
and
\[m=p(n_1)+\cdots+p(n_k)?\]

SOLVED

Let $f(k)$ be the maximal value of $n_1$ such that there exist $n_1<n_2<\cdots <n_k$ with
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\]
Is it true that
\[f(k)=(1+o(1))\frac{k}{e-1}?\]

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

SOLVED

Let $f(k)$ be the minimal value of $n_k$ such that there exist $n_1<n_2<\cdots <n_k$ with
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\]
Is it true that
\[f(k)=(1+o(1))\frac{e}{e-1}k?\]

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

OPEN

Let $k\geq 2$. Is it true that, for any distinct integers $n_1<\cdots <n_k$ such that
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\]
we must have $\max(n_{i+1}-n_i)\geq 3$?

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.

OPEN

Is it true that there are only finitely many pairs of intervals $I_1,I_2$ such that
\[\sum_{n_1\in I_1}\frac{1}{n_1}+\sum_{n_2\in I_2}\frac{1}{n_2}\in \mathbb{N}?\]

This is still open even if $\lvert I_2\rvert=1$. It is perhaps true with two intervals replaced by any $k$ intervals.

OPEN

Let $a\geq 1$. Must there exist some $b>a$ such that
\[\sum_{a\leq n\leq b}\frac{1}{n}=\frac{r_1}{s_1}\textrm{ and }\sum_{a\leq n\leq b+1}\frac{1}{n}=\frac{r_2}{s_2},\]
with $(r_i,s_i)=1$ and $s_2<s_1$? If so, how does this $b(a)$ grow with $a$?

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

OPEN

Let $A$ be the set of $n\in \mathbb{N}$ such that there exist $1\leq m_1<\cdots <m_k=n$ with $\sum\tfrac{1}{m_i}=1$. Explore $A$. In particular,

- Does $A$ have density $1$?
- What are those $n\in A$ not divisible by any $d\in A$ with $1<d<n$?

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

OPEN

Let $k\geq 1$ and let $v(k)$ be the minimal integer which does not appear as some $n_i$ in a solution to
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\]
with $1\leq n_1<\cdots <n_k$. Estimate the growth of $v(k)$.

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

SOLVED

Let $N\geq 1$ and let $t(N)$ be the least integer $t$ such that there is no solution to
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\]
with $t=n_1<\cdots <n_k\leq N$. Estimate $t(N)$.

OPEN

Let $N\geq 1$ and let $k(N)$ denote the smallest $k$ such that there exist $N\leq n_1<\cdots <n_k$ with
\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\]
Is it true that
\[\lim_{N\to \infty} k(N)-(e-1)N=\infty?\]

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

SOLVED

Let $N\geq 1$ and let $k(N)$ be maximal such that there are $k$ disjoint $A_1,\ldots,A_k\subseteq \{1,\ldots,N\}$ with $\sum_{n\in A_i}\frac{1}{n}=1$ for all $i$. Estimate $k(N)$. Is it true that $k(N)=o(\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$.

SOLVED

Let $N\geq 1$. How many $A\subseteq \{1,\ldots,N\}$ are there such that $\sum_{n\in A}\frac{1}{n}=1$?

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.

SOLVED

Let $A(N)$ denote the maximal cardinality of $A\subseteq \{1,\ldots,N\}$ such that $\sum_{n\in S}\frac{1}{n}\neq 1$ for all $S\subseteq A$. Estimate $A(N)$.

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

OPEN

What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that for any $a,b_1,\ldots,b_k\in A$ with $k\geq 2$ we have
\[\frac{1}{a}\neq \frac{1}{b_1}+\cdots+\frac{1}{b_k}?\]
Is there a constant $c>1/2$ such that $\lvert A\rvert >cN$ is possible for all large $N$?

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

OPEN

Is it true that, for any $\delta>1/2$, if $N$ is sufficiently large and $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert \geq \delta N$ then there exist $a,b,c\in A$ such that
\[\frac{1}{a}=\frac{1}{b}+\frac{1}{c}.\]

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.

OPEN

For integers $1\leq a<b$ let $N(a,b)$ denote the minimal $k$ such that there exist integers $1<n_1<\cdots<n_k$ with
\[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\]
Estimate $N(b)=\max_{1\leq a<b}N(a,b)$. Is it true that $N(b) \ll \log\log b$?

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

SOLVED

For integers $1\leq a<b$ let $D(a,b)$ be the minimal value of $n_k$ such that there exist integers $1\leq n_1<\cdots <n_k$ with
\[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\]
Estimate $D(b)=\max_{1\leq a<b}D(a,b)$. Is it true that
\[D(b) \ll b(\log b)^{1+o(1)}?\]

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

OPEN

Let $a/b\in \mathbb{Q}_{>0}$ with $b$ squarefree. Are there integers $1<n_1<\cdots<n_k$, each the product of two distinct primes, such that
\[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}?\]

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

OPEN

Are there two finite sets of primes $P,Q$ such that
\[1=\left(\sum_{p\in P}\frac{1}{p}\right)\left(\sum_{q\in Q}\frac{1}{q}\right)?\]

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

SOLVED

Let $N\geq 1$. How many integers can be written as the sum of distinct unit fractions with denominators from $\{1,\ldots,N\}$? Are there $o(\log N)$ such integers?

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.

SOLVED

Let $\alpha >0$ and $N\geq 1$. Is it true that for any $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert \geq \alpha N$ there exists some $S\subseteq A$ such that
\[\frac{a}{b}=\sum_{n\in S}\frac{1}{n}\]
with $a\leq b =O_\alpha(1)$?

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.

OPEN

What is the minimal value of $\lvert 1-\sum_{n\in A}\frac{1}{n}\rvert$ as $A$ ranges over all subsets of $\{1,\ldots,N\}$ which contain no $S$ such that $\sum_{n\in S}\frac{1}{n}=1$? Is it
\[e^{-(c+o(1))N}\]
for some constant $c\in (0,1)$?

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

OPEN

Does there exist some $c>0$ such that, for any $K>1$, whenever $A$ is a sufficiently large finite multiset of integers with $\sum_{n\in A}\frac{1}{n}>K$ there exists some $S\subseteq A$ such that
\[1-e^{-cK} < \sum_{n\in S}\frac{1}{n}\leq 1?\]

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

SOLVED

Let $n\geq 1$ and let $m$ be minimal such that $\sum_{n\leq k\leq m}\frac{1}{k}\geq 1$. We define
\[\epsilon(n) = \sum_{n\leq k\leq m}\frac{1}{k}-1.\]
How small can $\epsilon(n)$ be? Is it true that
\[\liminf n^2\epsilon(n)=0?\]

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

OPEN

Let $u_1=2$ and $u_{n+1}=u_n^2-u_n+1$. Let $a_1<a_2<\cdots $ be any other sequence with $\sum \frac{1}{a_k}=1$. Is it true that
\[\liminf a_n^{1/2^n}<\lim u_n^{1/2^n}=c_0=1.264085\cdots?\]

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

SOLVED

Is it true that if $A\subset \mathbb{N}\backslash\{1\}$ is a finite set with $\sum_{n\in A}\frac{1}{n}<2$ then there is a partition $A=A_1\sqcup A_2$ such that
\[\sum_{n\in A_i}\frac{1}{n}<1\]
for $i=1,2$?

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.

OPEN

Is there some constant $c>0$ such that for every $n\geq 1$ there exists some $\delta_k\in \{-1,0,1\}$ for $1\leq k\leq n$ with
\[0< \left\lvert \sum_{1\leq k\leq n}\frac{\delta_k}{k}\right\rvert < \frac{c}{2^n}?\]
Is it true that for sufficiently large $n$, for any $\delta_k\in \{-1,0,1\}$,
\[\left\lvert \sum_{1\leq k\leq n}\frac{\delta_k}{k}\right\rvert > \frac{1}{[1,\ldots,n]}\]
whenever the left-hand side is not zero?

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

OPEN

Let $A\subseteq \mathbb{N}$ be an infinite arithmetic progression and $f:A\to \{-1,1\}$ be a non-constant function. Must there exist a finite $S\subset A$ such that
\[\sum_{n\in S}\frac{f(n)}{n}=0?\]
What about if $A$ is an arbitrary set of positive density? What if $A$ is the set of squares excluding $1$?

OPEN

Let $S(N)$ count the number of distinct sums of the form $\sum_{n\in A}\frac{1}{n}$ for $A\subseteq \{1,\ldots,N\}$. Estimate $S(N)$.

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

OPEN

What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that all sums $\sum_{n\in S}\frac{1}{n}$ are distinct for $S\subseteq A$?

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

OPEN

Let $k\geq 3$ and $A\subset \mathbb{N}$ be the set of $k$th powers. What is the order of growth of $1_A^{(k)}(n)$, i.e. the number of representations of $n$ as the sum of $k$ many $k$th powers? Does there exist some $c>0$ and infinitely many $n$ such that
\[1_A^{(k)}(n) >n^c?\]

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

OPEN

Let $1\leq m\leq k$ and $f_{k,m}(x)$ denote the number of integers $\leq x$ which are the sum of $m$ many nonnegative $k$th powers. Is it true that
\[f_{k,k}(x) \gg_\epsilon x^{1-\epsilon}\]
for all $\epsilon>0$? Is it true that if $m<k$ then
\[f_{k,m}(x) \gg x^{m/k}\]
for sufficiently large $x$?

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

OPEN

Let $k\geq 3$ and $f_{k,3}(x)$ denote the number of integers $\leq x$ which are the sum of three nonnegative $k$th powers. Is it true that
\[f_{k,3}(x) \gg x^{3/k}\]
or even $\gg_\epsilon x^{3/k-\epsilon}$?

OPEN

Let $A\subset \mathbb{N}$ be an additive basis of order $2$. Must there exist $B=\{b_1<b_2<\cdots\}\subseteq A$ which is also a basis such that
\[\lim_{k\to \infty}\frac{b_k}{k^2}\]
does not exist?

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

OPEN

Suppose $A\subseteq \{1,\ldots,N\}$ is such that if $a,b\in A$ then $a+b\nmid ab$. Can $A$ be 'substantially more' than the odd numbers?

What if $a,b\in A$ with $a\neq b$ implies $a+b\nmid 2ab$? Must $\lvert A\rvert=o(N)$?

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

SOLVED

Suppose $A\subseteq\mathbb{N}$ and $C>0$ is such that $1_A\ast 1_A(n)\leq C$ for all $n\in\mathbb{N}$. Can $A$ be partitioned into $t$ many subsets $A_1,\ldots,A_t$ (where $t=t(C)$ depends only on $C$) such that $1_{A_i}\ast 1_{A_i}(n)<C$ for all $1\leq i\leq t$ and $n\in \mathbb{N}$?

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

OPEN

Suppose $A\subseteq \mathbb{N}$ is a Sidon set. How large can
\[\limsup_{N\to \infty}\frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}\]
be?

SOLVED

Let $A,B\subseteq \mathbb{N}$ such that for all large $N$
\[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}\]
and
\[\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.\]
Is it true that there are infinitely many solutions to $a_1-a_2=b_1-b_2\neq 0$ with $a_1,a_2\in A$ and $b_1,b_2\in B$?

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

OPEN

Let $A\subseteq \mathbb{N}$ and $D(A)$ be the set of those numbers which occur infinitely often as $a_1-a_2$ with $a_1,a_2\in A$. What conditions on $A$ are sufficient to ensure $D(A)$ has bounded gaps?

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

OPEN

Find the best function $f(n)$ such that every $n$ can be written as $n=a+b$ where both $a,b$ are $f(n)$-smooth (that is, are not divisible by any prime $p>f(n)$.)

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

OPEN

Let $d(A)$ denote the density of $A\subseteq \mathbb{N}$. Characterise those $A,B\subseteq \mathbb{N}$ with positive density such that
\[d(A+B)=d(A)+d(B).\]

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

OPEN

For $r\geq 2$ let $h(r)$ be the maximal finite $k$ such that there exists a basis $A\subseteq \mathbb{N}$ of order $r$ (so every large integer is the sum of at most $r$ integers from $A$) and exact order $k$ (i.e. $k$ is minimal such that every large integer is the sum of exactly $k$ integers from $A$). Find the value of
\[\lim_r \frac{h(r)}{r^2}.\]

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

SOLVED

Let $A\subseteq \mathbb{N}$ be an additive basis (of any finite order) such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that
\[\lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty?\]

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.

OPEN

The restricted order of a basis is the least integer $t$ (if it exists) such that every large integer is the sum of at most $t$ distinct summands from $A$. What are necessary and sufficient conditions that this exists? Can it be bounded (when it exists) in terms of the order of the basis? What are necessary and sufficient conditions that this is equal to the order of the basis?

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?

OPEN

Let $A=\{1,2,4,8,13,21,31,45,66,81,97,\ldots\}$ be the greedy Sidon sequence: we begin with $1$ and iteratively include the next smallest integer that preserves the Sidon property. What is the order of growth of $A$? Is it true that
\[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2-\epsilon}\]
for all $\epsilon>0$ and large $N$?

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.

OPEN

Let $A=\{a_1<\cdots<a_k\}$ be a finite set of integers and extend it to an infinite sequence $\overline{A}=\{a_1<a_2<\cdots \}$ by defining $a_{n+1}$ for $n\geq k$ to be the least integer exceeding $a_n$ which is not of the form $a_i+a_j$ with $i,j\leq n$. Is it true that the sequence of differences $a_{m+1}-a_m$ is eventually periodic?

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

OPEN

With $a_1=1$ and $a_2=2$ let $a_{n+1}$ for $n\geq 2$ be the least integer $>a_n$ which can be expressed uniquely as $a_i+a_j$ for $i<j\leq n$. What can be said about this sequence? Do infinitely many pairs $a,a+2$ occur? Does this sequence eventually have periodic differences? Is the density $0$?

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

SOLVED

If $A\subseteq \mathbb{N}$ is a multiset of integers such that
\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N\]
for all $N$ then must $A$ be subcomplete? That is, must
\[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\]
contain an infinite arithmetic progression?

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.

SOLVED

If $A\subseteq \mathbb{N}$ is a set of integers such that
\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2}\]
for all $N$ then must $A$ be subcomplete? That is, must
\[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\]
contain an infinite arithmetic progression?

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

OPEN

Let $A\subseteq \mathbb{N}$ be a complete sequence, and define the threshold of completeness $T(A)$ to be the least integer $m$ such that all $n\geq m$ are in
\[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\]
(the existence of $T(A)$ is guaranteed by completeness).

Is it true that there are infinitely many $k$ such that $T(n^k)>T(n^{k+1})$?

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

OPEN

Let $A=\{a_1< a_2<\cdots\}$ be a set of integers such that

- $A\backslash B$ is complete for any finite subset $B$ and
- $A\backslash B$ is not complete for any infinite subset $B$.

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.

OPEN

For what values of $0\leq m<n$ is there a complete sequence $A=\{a_1\leq a_2\leq \cdots\}$ of integers such that

- $A$ remains complete after removing any $m$ elements, but
- $A$ is not complete after removing any $n$ elements?

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.

OPEN

For what values of $t,\alpha \in (0,\infty)$ is the sequence $\lfloor t\alpha^n\rfloor$ complete?

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.

SOLVED

If $A\subset\mathbb{N}$ is a finite set of integers all of whose subset sums are distinct then
\[\sum_{n\in A}\frac{1}{n}<2.\]

OPEN

Let $p(x)\in \mathbb{Q}[x]$. Is it true that
\[A=\{ p(n)+1/n : n\in \mathbb{N}\}\]
is strongly complete, in the sense that, for any finite set $B$,
\[\left\{\sum_{n\in X}n : X\subseteq A\backslash B\textrm{ finite }\right\}\]
contains all sufficiently large rational numbers?

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?

OPEN

Let $\alpha,\beta\in \mathbb{R}_{>0}$ such that $\alpha/\beta$ is irrational. Is
\[\{ \lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 4\alpha\rfloor,\ldots\}\cup \{ \lfloor \beta\rfloor,\lfloor 2\beta\rfloor,\lfloor 4\beta\rfloor,\ldots\}\]
complete? What if $2$ is replaced by some $\gamma\in(1,2)$?

SOLVED

Let $A\subseteq \mathbb{N}$ be a lacunary sequence (so that $A=\{a_1<a_2<\cdots\}$ and there exists some $\lambda>1$ such that $a_{n+1}/a_n\geq \lambda$ for all $n\geq 1$). Must
\[\left\{ \sum_{a\in A'}\frac{1}{a} : A'\subseteq A\textrm{ finite}\right\}\]
contain all rationals in some open interval?

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

SOLVED

Is there some $c>0$ such that, for all sufficiently large $n$, there exist integers $a_1<\cdots<a_k\leq n$ such that there are at least $cn^2$ distinct integers of the form $\sum_{u\leq i\leq v}a_i$?

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

OPEN

Let $1\leq a_1<\cdots <a_k\leq n$ be integers such that all sums of the shape $\sum_{u\leq i\leq v}a_i$ are distinct. How large can $k$ be? Must $k=o(n)$?

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

OPEN

Is there a sequence $A=\{1\leq a_1<a_2<\cdots\}$ such that every integer is the sum of some finite number of consecutive elements of $A$? Can the number of representations of $n$ in this form tend to infinity with $n$?

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.

SOLVED

Let $A\subseteq \mathbb{N}$ be a finite set of size $N$. Is it true that, for any fixed $t$, there are
\[\ll \frac{2^N}{N^{3/2}}\]
many $S\subseteq A$ such that $\sum_{n\in S}n=t$?

Erdős and Moser proved this bound with an additional factor of $(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65]. 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$.

OPEN

When is the product of two or more disjoint blocks of consecutive integers a power? Is it true that there are only finitely many collections of disjoint intervals $I_1,\ldots,I_n$ of size $\lvert I_i\rvert \geq 4$ for $1\leq i\leq n$ such that
\[\prod_{1\leq i\leq n}\prod_{n\in I_i}n\]
is a square?

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 a always a square.

OPEN

Are there any triples of consecutive positive integers all of which are powerful (i.e. if $p\mid n$ then $p^2\mid n$)?

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

OPEN

Do all pairs of consecutive powerful numbers come from solutions to Pell equations? Is the number of such pairs $\leq x$ bounded by $(\log x)^{O(1)}$?

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

OPEN

Are there any 2-full $n$ such that $n+1$ is 3-full? That is, if $p\mid n$ then $p^2\mid n$ and if $p\mid n+1$ then $p^3\mid n+1$.

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

Note that $8$ is 3-full and $9$ is 2-full. Is the the only pair of such consecutive integers?

OPEN

Let $B_2(n)$ be the 2-full part of $n$ (that is, $B_2(n)=n/n'$ where $n'$ is the product of all primes that divide $n$ exactly once). Is it true that, for every fixed $k\geq 1$,
\[\prod_{n\leq m<n+k}B_2(m) \ll n^{2+o(1)}?\]
Or perhaps even $\ll_k n^2$?

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

OPEN

Let $\epsilon>0$ and $k\geq 2$. Is it true that, for all sufficiently large $n$, there is a sequence of $k$ consecutive integers in $\{1,\ldots,n\}$ all of which are $n^\epsilon$-smooth?

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

SOLVED

Are there infinitely many $n$ such that the largest prime factor of $n$ is $<n^{1/2}$ and the largest prime factor of $n+1$ is $<(n+1)^{1/2}$?

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

SOLVED

Let $P(n)$ denote the largest prime factor of $n$. There are infinitely many $n$ such that $P(n)>P(n+1)>P(n+2)$.

OPEN

Show that the equation
\[n! = a_1!a_2!\cdots a_k!,\]
with $n-1>a_1\geq a_2\geq \cdots \geq a_k$, has only finitely many solutions.

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

OPEN

For any $m\in \mathbb{N}$, let $F(m)$ be the minimal $k\geq 2$ (if it exists) such that there are $a_1<\cdots <a_k=m$ with $a_1!\cdots a_k!$ a square. Let $D_k=\{ m : F(m)=k\}$. What is the order of growth of $\lvert D_k\cap\{1,\ldots,n\}\rvert$ for $3\leq k\leq 6$? For example, is it true that $\lvert D_6\cap \{1,\ldots,n\}\rvert \gg n$?

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

OPEN

Let $n+1,\ldots,n+k$ be consecutive composite integers. Are there distinct primes $p_1,\ldots,p_k$ such that $p_i\mid n+i$ for $1\leq i\leq k$?

OPEN

Are there infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $105$?

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

OPEN

Is
\[\sum_{\substack{p\nmid \binom{2n}{n}\\ p\leq n}}\frac{1}{p}\]
unbounded as a function of $n$?

If the sum is denoted by $f(n)$ then Erdős, Graham, Ruzsa, and Straus [EGRS75] have shown
\[\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)$.

OPEN

Let $r\geq 0$. Does the density of integers $n$ for which $\binom{n}{k}$ is squarefree for at least $r$ values of $1\leq k<n$ exist? Is this density $>0$?

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.

OPEN

Let $S(n)$ denote the largest integer such that, for all $1\leq k<n$, the binomial coefficient $\binom{n}{k}$ is divisible by $p^{S(n)}$ for some prime $p$ (depending on $k$). Is it true that
\[\limsup S(n)=\infty?\]

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

OPEN

We call an interval $[u,v]$ 'bad' if the greatest prime factor of $\prod_{u\leq m\leq v}m$ occurs with an exponent greater than $1$. Let $B(x)$ count the number of $n\leq x$ which are contained in at least one bad interval. Is it true that
\[B(x)\sim \#\{ n\leq x: p\mid n\rightarrow p\leq n^{1/2}\}?\]

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

OPEN

Let $u\leq v$ be such that the largest prime dividing $\prod_{u\leq m\leq v}m$ appears with exponent at least $2$. Is it true that $v-u=v^{o(1)}$? Can $v-u$ be arbitrarily large?

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

See also [380].

SOLVED

If $1<k<n-1$ then $\binom{n}{k}$ is divisible by a prime $p<n/2$ (except $\binom{7}{3}=5\cdot 7$).

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

OPEN

Can $\binom{n}{k}$ be the product of consecutive primes infinitely often? For example
\[\binom{21}{2}=2\cdot 3\cdot 5\cdot 7.\]

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

OPEN

Is there an absolute constant $c>0$ such that, for all $1\leq k< n$, the binomial coefficient $\binom{n}{k}$ has a divisor in $(cn,n]$?

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

OPEN

Can one classify all solutions of
\[\prod_{1\leq i\leq k_1}(m_1+i)=\prod_{1\leq j\leq k_2}(m_2+j)\]
where $1<k_1<k_2$ and $m_1+k_1\leq m_2$? Are there only finitely many solutions? More generally, if $k_1>2$ then for fixed $a$ and $b$
\[a\prod_{1\leq i\leq k_1}(m_1+i)=b\prod_{1\leq j\leq k_2}(m_2+j)\]
should have only a finite number of solutions. What if one just requires that the products have the same prime factors, say when $k_1=k_2$?

OPEN

Let $t(n)$ be the maximum $m$ such that
\[n!=a_1\cdots a_n\]
with $m=a_1\leq \cdots \leq a_n$. Obtain good upper bounds for $t(n)$. In particular does there exist some constant $c>0$ such that
\[t(n) \leq \frac{n}{e}-c\frac{n}{\log n}\]
for infinitely many $n$?

Erdős, Selfridge, and Straus have shown that
\[\lim \frac{t(n)}{n}=\frac{1}{e}.\]
Alladi and Grinstead [AlGr77] have obtained similar results when the $a_i$ are restricted to prime powers.

OPEN

Let $A(n)$ denote the least value of $t$ such that
\[n!=a_1\cdots a_t\]
with $a_1\leq \cdots \leq a_t\leq n^2$. Is it true that
\[A(n)=\frac{n}{2}-\frac{n}{2\log n}+o\left(\frac{n}{\log n}\right)?\]

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

OPEN

Let $f(n)$ denote the minimal $m$ such that
\[n! = a_1\cdots a_t\]
with $a_1<\cdots <a_t=a_1+m$. What is the behaviour of $f(n)$?

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

SOLVED

Let $t_k(n)$ denote the least $m$ such that
\[n\mid (m+1)(m+2)\cdots (m+k).\]
Is it true that
\[\sum_{1\leq n\leq N}t_2(n)=o(N)?\]

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

OPEN

Is it true that for every $k$ there exists $n$ such that
\[\prod_{0\leq i\leq k}(n-i) \mid \binom{2n}{n}?\]

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

OPEN

Is it true that there are no solutions to
\[n! = x^k\pm y^k\]
with $x,y,n\in \mathbb{N}$, with $xy>1$ and $k>2$?

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

OPEN

For any $k\geq 2$ let $g_k(n)$ denote the maximal value of
\[n-(a_1+\cdots+a_k)\]
where $a_1,\ldots,a_k$ are integers such that $a_1!\cdots a_k! \mid n!$. Can one show that
\[\sum_{n\leq x}g_k(n) \sim c_k x\log x\]
for some constant $c_k$? Is it true that there is a constant $c_k$ such that for almost all $n<x$ we have
\[g_k(n)=c_k\log x+o(\log x)?\]

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

SOLVED

Prove that, for any finite set $A\subset\mathbb{N}$, there exist $a,b\in A$ such that
\[\mathrm{gcd}(a,b)\leq a/\lvert A\rvert.\]

A conjecture of Graham [Gr70], who also conjectured that (assuming $A$ itself has no common divisor) then the only cases where equality 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].

SOLVED

Does the equation
\[2^m=a_1!+\cdots+a_k!\]
with $a_1<a_2<\cdots <a_k$ have only finitely many solutions?

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

OPEN

Let $f(a,p)$ be the largest $k$ such that there are $a=a_1<\cdots<a_k$ such that
\[p^k \mid (a_1!+\cdots+a_k!).\]
Is $f(a,p)$ bounded by some absolute constant? What if this constant is allowed to depend on $a$ and $p$?

Is there a prime $p$ and an infinite sequence $a_1<a_2<\cdots$ such that if $p^{m_k}$ is the highest power of $p$ dividing $\sum_{i\leq k}a_i!$ then $m_k\to \infty$?

OPEN

Is it true that there are only finitely many powers of $2$ which have only the digits $0$ and $1$ when written in base $3$?

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

OPEN

Let $\phi(n)$ be the Euler totient function and $\phi_k(n)$ be the iterated $\phi$ function, so that $\phi_1(n)=\phi(n)$ and $\phi_k(n)=\phi(\phi_{k-1}(n))$. Let
\[f(n) = \min \{ k : \phi_k(n)=1\}.\]
Does $f(n)/\log n$ have a distribution function? Is $f(n)/\log n$ almost always constant? What can be said about the largest prime factor of $\phi_k(n)$ when, say, $k=\log\log n$?

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

OPEN

Let $g_1=g(n)=n+\phi(n)$ and $g_k(n)=g(g_{k-1}(n))$. For which $n$ and $r$ is it true that $g_{k+r}(n)=2g_k(n)$ for all large $k$?

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

OPEN

Let $\sigma_1(n)=\sigma(n)$, the sum of divisors function, and $\sigma_k(n)=\sigma(\sigma_{k-1}(n))$. Is it true that, for every $m,n$, there exist some $i,j$ such that $\sigma_i(m)=\sigma_j(n)$?

That is, there is (eventually) only one possible sequence that the iterated sum of divisors function can settle on. Selfridge reports numerical evidence 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'.

OPEN

Let $\nu(n)$ count the number of distinct primes dividing $n$. Are there infinitely many $n$ such that, for all $m<n$, we have $m+\nu(m) \leq n$?

Erdős suggested this problem as a way of showing that the iterated behaviour of $n\mapsto n+\nu(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'. Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \nu(m)\leq n$ for all $m<n$?

OPEN

Let $h_1(n)=h(n)=n+\tau(n)$ (where $\tau(n)$ counts the number of divisors of $n$) and $h_k(n)=h(h_{k-1}(n))$. Is it true, for any $m,n$, there exist $i$ and $j$ such that $h_i(m)=h_j(n)$?

OPEN

For any $n$ let $F(n)$ be the largest $k$ such that any of the $k!$ possible ordering patterns appears in some sequence of $\phi(m+1),\ldots,\phi(m+k)$ with $m+k\leq n$. Is it true that
\[F(n)=(c+o(1))\log\log\log n\]
for some constant $c$? Is the first pattern which fails to appear always
\[\phi(m+1)>\phi(m+2)>\cdots \phi(m+k)?\]
Is it true that 'natural' ordering which mimics what happens to $\phi(1),\ldots,\phi(k)$ is the most likely to appear?

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.

OPEN

Let $V(x)$ count the number of $n\leq x$ such that $\phi(m)=n$ is solvable. Does $V(2x)/V(x)\to 2$? Is there an asymptotic formula for $V(x)$?

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

See also [417].

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.

SOLVED

If $\tau(n)$ counts the number of divisors of $n$, then what is the set of limit points of
\[\frac{\tau((n+1)!)}{\tau(n!)}?\]

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

OPEN

If $\tau(n)$ counts the number of divisors of $n$ then let
\[F(f,n)=\frac{\tau((n+\lfloor f(n)\rfloor)!)}{\tau(n!)}.\]
Is it true that
\[\lim_{n\to \infty}F((\log n)^C,n)=\infty\]
for large $C$? Is it true that $F(\log n,n)$ is everywhere dense in $(1,\infty)$? More generally, if $f(n)\leq \log n$ is a monotonic function then is $F(f,n)$ everywhere dense?

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

OPEN

Let $f(1)=f(2)=1$ and for $n>2$
\[f(n) = f(n-f(n-1))+f(n-f(n-2)).\]
Does $f(n)$ miss infinitely many integers? What is its behaviour?

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

OPEN

Let $a_1=1$ and $a_2=2$ and for $k\geq 3$ we choose $a_k$ to be the least integer $>a_{k-1}$ which is the sum of at least two consecutive terms of the sequence. What is the asymptotic behaviour of this sequence?

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

SOLVED

Let $a_1=2$ and $a_2=3$ and continue the sequence by appending to $a_1,\ldots,a_n$ all possible values of $a_ia_j-1$ with $i\neq j$. Is it true that almost all integers appear in this sequence?

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.

Steinerberger has observed that this problem has a trivial negative solution - in fact 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}$.

OPEN

Let $F(n)$ be the maximum possible size of a subset $A\subseteq\{1,\ldots,N\}$ such that the products $ab$ are distinct for all $a<b$. Is there a constant $c$ such that
\[F(n)=\pi(n)+(c+o(1))n^{3/4}(\log n)^{-3/2}?\]

Erdős [Er68] proved that
\[F(n)-\pi(n)\asymp n^{3/4}(\log n)^{-3/2}.\]
Surprisingly, if we consider the corresponding problem in the reals (so the largest $m$ such that there are reals $1\leq a_1<\cdots <a_m\leq x$ such that for any distinct indices $i,j,r,s$ we have $\lvert a_ia_j-a_ra_s\rvert \geq 1$) then Alexander proved that $m> x/8e$ is possible.

See also [490].

SOLVED

Is it true that, for every $n$ and $d$, there exists $k$ such that
\[d \mid p_{n+1}+\cdots+p_{n+k},\]
where $p_r$ denotes the $r$th prime?

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

OPEN

Is there a set $A\subseteq \mathbb{N}$ such that, for infinitely many $n$, all of $n-a$ are prime for all $a\in A$ with $0<a<n$ and
\[\liminf\frac{\lvert A\cap [1,x]\rvert}{\pi(x)}>0?\]

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

SOLVED

Is it true that, if $A\subseteq \mathbb{N}$ is sparse enough and does not cover all residue classes modulo $p$ for any prime $p$, then there exists some $n$ such that $n+a$ is prime for all $a\in A$?

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

OPEN

Fix some integer $n$ and define a decreasing sequence in $[1,n)$ by $a_1=n-1$ and, for $k\geq 2$, letting $a_k$ be the greatest integer in $[1,a_{k-1})$ such that all of the prime factors of $a_k$ are $>n-a_k$. Is it true that, for sufficiently large $n$, not all of this sequence can be prime?

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.

OPEN

Are there two infinite sets $A$ and $B$ such that $A+B$ agrees with the set of prime numbers up to finitely many exceptions?

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

OPEN

If $A\subset \mathbb{N}$ is a finite set then let $G(A)$ denote the greatest integer which is not expressible as a finite sum of elements from $A$ (with repetitions allowed). Let
\[g(n,t)=\max G(A)\]
where the maximum is taken over all $A\subseteq \{1,\ldots,t\}$ of size $\lvert A\rvert=n$ which has no common divisor. Is it true that
\[g(n,t)\sim \frac{t^2}{n-1}?\]

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

OPEN

Let $k\leq n$. What choice of $A\subseteq \{1,\ldots,n\}$ of size $\lvert A\rvert=k$ maximises the number of integers not representable as the sum of finitely many elements from $A$ (with repetitions allowed)? Is it $\{n,n-1,\ldots,n-k+1\}$?

Associated with problems of Frobenius.

OPEN

If $p$ is a prime and $k,m\geq 2$ then let $r(k,m,p)$ be the minimal $r$ such that $r,r+1,\ldots,r+m-1$ are all $k$th power residues modulo $p$. Let
\[\Lambda(k,m)=\limsup_{p\to \infty} r(k,m,p).\]
Is it true that $\Lambda(k,2)$ is finite for all $k$? Is $\Lambda(k,3)$ finite for all odd $k$? How large are they?

SOLVED

How large can $A\subseteq \{1,\ldots,N\}$ be if $A+A$ contains no square numbers?

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

SOLVED

Is it true that, in any finite colouring of the integers, there must be two integers $x\neq y$ of the same colour such that $x+y$ is a square? What about a $k$th power?

A question of Roth, Erdős, Sárközy, and Sós. 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}$.

OPEN

Let $A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}$ be infinite and let $A(x)$ count the numer of indices for which $\mathrm{lcm}(a_i,a_{i+1})\leq x$. Is it true that $A(x) \ll x^{1/2}$? How large can
\[\liminf \frac{A(x)}{x^{1/2}}\]
be?

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

SOLVED

Let $A\subseteq\mathbb{N}$ be infinite and $d_A(n)$ count the number of $a\in A$ which divide $n$. Is it true that, for every $k$,
\[\limsup_{x\to \infty} \frac{\max_{n<x}d_A(n)}{\left(\sum_{n\in A\cap[1,x)}\frac{1}{n}\right)^k}=\infty?\]

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

SOLVED

Let $\delta(n)$ denote the density of integers which are divisible by some integer in $(n,2n)$. What is the growth rate of $\delta(n)$?

If $\delta'(n)$ is the density of integers which have exactly one divisor in $(n,2n)$ then is it true that $\delta'(n)=o(\delta(n))$?

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

SOLVED

Let $\tau(n)$ count the divisors of $n$ and $\tau^+(n)$ count the number of $k$ such that $n$ has a divisor in $[2^k,2^{k+1})$. Is it true that, for all $\epsilon>0$,
\[\tau^+(n) < \epsilon \tau(n)\]
for almost all $n$?

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

SOLVED

Let $r(n)$ count the number of $d_1,d_2$ such that $d_1\mid n$ and $d_2\mid n$ and $d_1<d_2<2d_1$. Is it true that, for every $\epsilon>0$,
\[r(n) < \epsilon \tau(n)\]
for almost all $n$, where $\tau(n)$ is the number of divisors of $n$?

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

OPEN

How large must $y=y(\epsilon,n)$ be such that the number of integers in $(x,x+y)$ with a divisor in $(n,2n)$ is at most $\epsilon y$?

OPEN

Estimate $n_k$, the smallest integer such that $\prod_{1\leq i\leq k}(n_k-i)$ has no prime factor in $(k,2k)$.

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

OPEN

Let $\omega(n)$ count the number of distinct prime factors of $n$. What is the size of the largest interval $I\subseteq [x,2x]$ such that $\omega(n)>\log\log n$ for all $n\in I$?

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

OPEN

Let $s_n$ be the smallest prime such that $n\mid s_n-1$ and let $m_n$ be the smallest integer such that $n\mid \phi(m_n)$. Is it true that $s_n>m_n$ for almost all $n$? Does $s_n/m_n\to \infty$ for almost all $n$? Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?

OPEN

Let $[1,\ldots,n]$ denote the least common multiple of $\{1,\ldots,n\}$. Is it true that, for all $k\geq 1$,
\[[1,\ldots,p_{k+1}-1]< p_k[1,\ldots,p_k]?\]

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.

OPEN

Let $a_0=n$ and $a_1=1$, and in general $a_k$ is the least integer $>a_{k-1}$ for which $(n-a_k,n-a_i)=1$ for all $1\leq i<k$. Does
\[\sum_{i}\frac{1}{a_i}\to \infty\]
as $n\to \infty$? What about if we restrict the sum to those $i$ such that $n-a_j$ is divisible by some prime $\leq a_j$, or the complement of such $i$?

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

OPEN

Let $s_t(n)$ be the $t$-smooth component of $n$ - that is, the product of all primes $p$ (with multiplicity) dividing $n$ such that $p<t$. Let $f(n,t)$ count the number of distinct possible values for $s_t(m)$ for $m\in [n+1,n+t]$. Is there an $\epsilon>0$ such that
\[f(n,t)>\epsilon t\]
for all $t$ and $n$?

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

OPEN

Let $p(n)$ denote the least prime factor of $n$. There is a constant $c>0$ such that
\[\sum_{\substack{n<x\\ n\textrm{ not prime}}}\frac{p(n)}{n}\sim c\frac{x^{1/2}}{(\log x)^2}.\]
Is it true that there exists a constant $C>0$ such that
\[\sum_{x\leq n\leq x+Cx^{1/2}(\log x)^2}\frac{p(n)}{n} \gg 1\]
for all large $x$?

SOLVED

Let $A=\{a_1<a_2<\cdots\}\subset \mathbb{N}$ be a lacunary sequence (so there exists some $\lambda>1$ with $a_{k+1}\geq \lambda a_k$ for all $k$). Is there an irrational $\alpha$ such that
\[\{ \{\alpha a_k\} : k\geq 1\}\]
is not everywhere dense in $[0,1]$ (where $\{x\}=x-\lfloor x\rfloor$ is the fractional part).

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.

SOLVED

Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that
\[\| \lvert P_i-P_j\rvert \| \geq \delta\]
for all $1\leq i<j\leq n$. (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is it true that, for any $0<\delta<1/2$, we have \[N(X,\delta)=o(X)?\] In fact, is it true that (for any fixed $\delta>0$) \[N(X,\delta)<X^{1/2+o(1)}?\]

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

SOLVED

Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that
\[\| \lvert P_i-P_j\rvert \| \geq \delta\]
for all $1\leq i<j\leq n$. (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is there some $\delta>0$ such that \[\lim_{x\to \infty}N(X,\delta)=\infty?\]

OPEN

Prove the following for all large $x$: there is a choice of congruence classes $a_p$ for all primes $p\leq x$, and a decomposition $\{p\leq x\}=A\sqcup B$ into two non-empty sets such that, for all $n<x$, there exist some $p\in A$ and $q\in B$ such that $n\equiv a_p\pmod{p}$ and $n\equiv a_q\pmod{q}$.

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.

OPEN

For any $n$ let $D_n$ be the set of sums of the shape $d_1,d_1+d_2,d_1+d_2+d_3,\ldots$ where $1<d_1<d_2<\cdots$ are the divisors of $n$.

What is the size of $D_n\backslash \cup_{m<n}D_m$?

If $f(N)$ is the minimal $n$ such that $N\in D_n$ then is it true that $f(N)=o(N)$? Perhaps just for almost all $N$?

OPEN

Let $A$ be the set of all $n$ such that $n=d_1+\cdots+d_k$ with $d_i$ distinct proper divisors of $n$, but this is not true for any $m\mid n$ with $m<n$. Does
\[\sum_{n\in A}\frac{1}{n}\]
converge?

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.

OPEN

Call $n$ weird if $\sigma(n)\geq 2n$ and $n\neq d_1+\cdots+d_k$, where the $d_i$ are distinct proper divisors of $n$. Are there any odd weird numbers? Are there infinitely many primitive weird numbers, i.e. those such that no proper divisor of $n$ is weird?

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

OPEN

Given a finite set of primes $Q=Q_0$, define a sequence of sets $Q_i$ by letting $Q_{i+1}$ be $Q_i$ together with all primes formed by adding three distinct elements of $Q_i$. Is there some initial choice of $Q$ such that the $Q_i$ become arbitrarily large?

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

OPEN

Given some initial finite sequence of primes $q_1<\cdots<q_m$ extend it so that $q_{n+1}$ is the smallest prime of the form $q_n+q_i-1$ for $n\geq m$. Is there an initial starting sequence so that the resulting sequence is infinite?

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.

SOLVED

Is there a permutation $a_1,a_2,\ldots$ of the positive integers such that $a_k+a_{k+1}$ is always prime?

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?

OPEN

Let $b_1=1$ and in general let $b_{n+1}$ be the least integer which is not of the shape $\sum_{u\leq i\leq v}b_i$ for some $1\leq u\leq v\leq n$. How does this sequence grow?

The sequence is OEIS A002048 and begins
\[1,2,4,5,8,10,14,15,16,21,22,23,25,\ldots.\]
In general, if $a_1<a_2<\cdots$ is a sequence so that no $a_n$ is a sum of consecutive $a_i$s, then must the density of the $a_i$ be zero? What about the lower density?

OPEN

Let $p$ be a prime. Given any finite set $A\subseteq \mathbb{F}_p\backslash \{0\}$, is there always a rearrangement $A=\{a_1,\ldots,a_t\}$ such that all partial sums $\sum_{1\leq k\leq m}a_{k}$ are distinct, for all $1\leq m\leq t$?

A problem of Graham.

OPEN

Is it true that, for all $k\neq 1$, there are infinitely many $n$ such that $2^n\equiv k\pmod{n}$?

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

SOLVED

Let $x_1,x_2,\ldots\in [0,1]$ be an infinite sequence. Is it true that there are infinitely many $m,n$ such that
\[\lvert x_{m+n}-x_n\rvert \leq \frac{1}{\sqrt{5}n}?\]

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.

OPEN

Let $a_1,\ldots,a_r,b_1,\ldots,b_r\in \mathbb{N}$ such that $\sum_{i}\frac{1}{a_i}>1$. For any finite sequence of $n$ (not necessarily distinct) integers $A=(x_1,\ldots,x_n)$ let $T(A)$ denote the sequence of length $rn$ given by
\[(a_ix_j+b_i)_{1\leq j\leq n, 1\leq i\leq r}.\]
Prove that, if $A_1=(1)$ and $A_{i+1}=T(A_i)$, then there must be some $A_k$ with repeated elements.

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.

SOLVED

Define a sequence by $a_1=1$ and
\[a_{n+1}=\lfloor\sqrt{2}(a_n+1/2)\rfloor\]
for $n\geq 1$. The difference $a_{2n+1}-2a_{2n-1}$ is the $n$th digit in the binary expansion of $\sqrt{2}$.

Find similar results for $\theta=\sqrt{m}$, and other algebraic numbers.

OPEN

Prove that there exists an absolute constant $c>0$ such that, whenever $\{1,\ldots,N\}$ is $k$-coloured (and $N$ is large enough depending on $k$) then there are at least $cN$ many integers in $\{1,\ldots,N\}$ which are representable as a monochromatic sum (that is, $a+b$ where $a,b\in \{1,\ldots,N\}$ are in the same colour class).

A conjecture of Roth.

OPEN

Let $A\subseteq \mathbb{N}$, and for each $n\in A$ choose some $X_n\subseteq \mathbb{Z}/n\mathbb{Z}$. Let
\[B = \{ m\in \mathbb{N} : m\not\in X_n\pmod{n}\textrm{ for all }n\in A\}.\]
Must $B$ have a logarithmic density, i.e. is it true that
\[\lim_{x\to \infty} \frac{1}{\log x}\sum_{\substack{m\in B\\ m<x}}\frac{1}{m}\]
exists?

SOLVED

Let $A\subseteq \mathbb{N}$ have positive density. Must there exist distinct $a,b,c\in A$ such that $[a,b]=c$ (where $[a,b]$ is the lowest common multiple of $a$ and $b$)?

OPEN

Let $A\subseteq \mathbb{N}$ be a set such that $\lvert A\cap [1,x]\rvert=o(x^{1/2})$. Let
\[B=\{ n\geq 1 : a\nmid n\textrm{ for all }a\in A\}.\]
If $B=\{b_1<b_2<\cdots\}$ then is it true that
\[\lim \frac{1}{x}\sum_{b_i<x}(b_{i+1}-b_i)^2\]
exists (and is finite)?

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

SOLVED

Let $A,B\subseteq \{1,\ldots,N\}$ be such that all the products $ab$ with $a\in A$ and $b\in B$ are distinct. Is it true that
\[\lvert A\rvert \lvert B\rvert \ll \frac{N^2}{\log N}?\]

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

SOLVED

Let $f:\mathbb{N}\to \mathbb{R}$ be an additive function (i.e. $f(ab)=f(a)+f(b)$ whenever $(a,b)=1$). If there is a constant $c$ such that $\lvert f(n+1)-f(n)\rvert <c$ for all $n$ then must there exist some $c'$ such that
\[f(n)=c'\log n+O(1)?\]

SOLVED

Let $A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}$ be infinite such that $a_{i+1}/a_i\to 1$. For any $x\geq a_1$ let
\[f(x) = \frac{x-a_i}{a_{i+1}-a_i}\in [0,1),\]
where $x\in [a_i,a_{i+1})$. Is it true that, for almost all $\alpha$, the sequence $f(\alpha n)$ is uniformly distributed in $[0,1)$?

SOLVED

Does there exist a $k$ such that every sufficiently large integer can be written in the form
\[\prod_{i=1}^k a_i - \sum_{i=1}^k a_i\]
for some integers $a_i\geq 2$?

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.

OPEN

Let $\alpha,\beta \in \mathbb{R}$. Is it true that
\[\liminf_{n\to \infty} n \| n\alpha \| \| n\beta\| =0\]
where $\|x\|$ is the distance from $x$ to the nearest integer?

The infamous Littlewood conjecture.

SOLVED

Let $\alpha \in \mathbb{R}$ be irrational and $\epsilon>0$. Are there positive integers $x,y,z$ such that
\[\lvert x^2+y^2-z^2\alpha\rvert <\epsilon?\]

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

SOLVED

Let $f$ be a Rademacher multiplicative function: a random $\{-1,0,1\}$-valued multiplicative function, where for each prime $p$ we independently choose $f(p)\in \{-1,1\}$ uniformly at random, and for square-free integers $n$ we extend $f(p_1\cdots p_r)=f(p_1)\cdots f(p_r)$ (and $f(n)=0$ if $n$ is not squarefree). Does there exist some constant $c>0$ such that, almost surely,
\[\limsup_{N\to \infty}\frac{\sum_{m\leq N}f(m)}{\sqrt{N\log\log N}}=c?\]

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

SOLVED

Let $\ell(N)$ be maximal such that in any finite set $A\subset \mathbb{R}$ of size $N$ there exists a Sidon subset $S$ of size $\ell(N)$ (i.e. the only solutions to $a+b=c+d$ in $S$ are the trivial ones). Determine the order of $\ell(N)$.

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

OPEN

Let $F(k)$ be the minimal $N$ such that if we two-colour $\{1,\ldots,N\}$ there is a set $A$ of size $k$ such that all subset sums $\sum_{a\in S}a$ (for $\emptyset\neq S\subseteq A$) are monochromatic. Estimate $F(k)$.

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

SOLVED

If $\mathbb{N}$ is 2-coloured then is there some infinite set $A\subseteq \mathbb{N}$ such that all finite subset sums
\[ \sum_{n\in S}n\]
(as $S$ ranges over all non-empty finite subsets of $A$) are monochromatic?

OPEN

What is the largest possible subset $A\subseteq\{1,\ldots,N\}$ which contains $N$ such that $(a,b)=1$ for all $a\neq b\in A$?

A problem of Erdős and Graham. 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 }(t,N)=1\}$.

OPEN

Let $r\geq 3$, and let $f_r(N)$ denote the size of the largest subset of $\{1,\ldots,N\}$ such that no subset of size $r$ has the same pairwise greatest common divisor between all elements. Estimate $f_r(N)$.

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 if $\omega(n)=k$ for all $n\in A$ then there must be some $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!$.

OPEN

Let $\epsilon>0$ and $N$ be sufficiently large. Is it true that if $A\subseteq \{1,\ldots,N\}$ has size at least $\epsilon N$ then there must be $a,b,c\in A$ such that
\[[a,b]=[b,c]=[a,c],\]
where $[a,b]$ denotes the least common multiple?

This is false if we ask for four elements with the same pairwise least common multiple, as shown by Erdős [Er62].

SOLVED

Let $\epsilon>0$ and $N$ be sufficiently large. If $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert \geq \epsilon N$ then must there exist $a_1,a_2,a_3\in A$ and distinct primes $p_1,p_2,p_3$ such that
\[a_1p_1=a_2p_2=a_3p_3?\]

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.

OPEN

Let $r\geq 2$ and suppose that $A\subseteq\{1,\ldots,N\}$ is such that, for any $m$, there are at most $r$ solutions to $m=pa$ where $p$ is prime and $a\in A$. Give the best possible upper bound for
\[\sum_{n\in A}\frac{1}{n}.\]

SOLVED

Is it true that if $A\subseteq \mathbb{Z}/N\mathbb{Z}$ has size $\gg N^{1/2}$ then there exists some non-empty $S\subseteq A$ such that $\sum_{n\in S}n\equiv 0\pmod{N}$?

The answer is yes, proved by Szemerédi [Sz70] (in fact for arbitrary finite abelian groups). Erdős speculates that perhaps the correct threshold is $(2N)^{1/2}$.

OPEN

Let $a_1,\ldots,a_p$ be (not necessarily distinct) residues modulo $p$, such that there exists some $r$ so that if $S\subseteq [p]$ is non-empty and
\[\sum_{i\in S}a_i\equiv 0\pmod{p}\]
then $\lvert S\rvert=r$. Must there be at most two distinct residues amongst the $a_i$?

A question of Graham.

OPEN

Define $f(N)$ be the minimal $k$ such that the following holds: if $G$ is an abelian group of size $N$ and $A\subseteq G$ is a random set of size $k$ then, with probability $\geq 1/2$, all elements of $G$ can be written as $\sum_{x\in S}x$ for some $S\subseteq A$. Is
\[f(N) \leq \log_2 N+o(\log\log N)?\]

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.

SOLVED

What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that, for all $\emptyset\neq S\subseteq A$, $\sum_{n\in S}n$ is not a square?

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.

OPEN

Let $t\geq 1$ and $A\subseteq \{1,\ldots,N\}$ be such that whenever $a,b\in A$ with $b-a\geq t$ we have $b-a\nmid b$. How large can $\lvert A\rvert$ be? Is it true that
\[\lvert A\rvert \leq \left(\frac{1}{2}+o_t(1)\right)N?\]

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.

OPEN

Is it true that if $\mathbb{N}$ is 2-coloured then there must exist a monochromatic three-term arithmetic progression $x,x+d,x+2d$ such that $d>x$?

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.

OPEN

Is it true that, for any two primes $p,q$, there exists some integer $n$ such that the largest prime factor of $n$ is $p$ and the largest prime factor of $n+1$ is $q$?

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

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

OPEN

Let $f(m)$ be such that if $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert=m$ then every interval in $[1,\infty)$ of length $2N$ contains $\geq f(m)$ many distinct integers $b_1,\ldots,b_r$ where each $b_i$ is divisible by some $a_i\in A$, where $a_1,\ldots,a_r$ are distinct.

Estimate $f(m)$. In particular is it true that $f(m)\ll m^{1/2}$?

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