21 solved out of 61 shown (show only solved or open)
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]. Additional thanks to: Zachary Hunter 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
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]).

OPEN
Let $A$ be an infinite set such that there are no distinct $a,b,c\in A$ such that $a\mid (b+c)$ and $b,c>a$. Is there such an $A$ with $\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?$ Does there exist some absolute constant $c>0$ such that there are always infinitely many $N$ with $\lvert A\cap\{1,\ldots,N\}\rvert<N^{1-c}?$

Is it true that $\sum_{n\in A}\frac{1}{n}<\infty?$

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

An example of an $A$ with this property where $\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0$ is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.

For the finite version see [13].

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]. For the infinite version see [12]. Additional thanks to: Zachary Chase OPEN -$1000
Let $f(n,k)$ be minimal such that every $\mathcal{F}$ family of $n$-uniform sets with $\lvert F\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that $f(n,k) < c_k^n$ for some constant $c_k>0$?
Erdős and Rado [ErRa60] originally proved $f(n,k)\leq (k-1)^nn!$. Kostochka [Ko97] improved this slightly (in particular establishing an upper bound of $o(n!)$, for which Erdős awarded him the consolation prize of \$100), but the bound stood at$n^{(1+o(1))n}$for a long time until Alweiss, Lovett, Wu, and Zhang [ALWZ20] proved $f(n,k) < (Ck\log n\log\log n)^n$ for some constant$C>1$. This was refined slightly, independently by Rao [Ra20], Frankston, Kahn, Narayanan, and Park [FKNP19], and Bell, Chueluecha, and Warnke [BCW21], leading to the current record of $f(n,k) < (Ck\log n)^n$ for some constant$C>1$. In [Er81] offered \$1000 for a proof or disproof even just in the special case when $k=3$, which he expected 'contains the whole difficulty'. He also wrote 'I really do not see why this question is so difficult'.

The usual focus is on the regime where $k=O(1)$ is fixed (say $k=3$) and $n$ is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KoRoTa99] have shown $f(n,k)=(1+O_n(k^{-1/2^n}))k^n.$

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

SOLVED
Given any infinite set $A\subset \mathbb{N}$ there is a set $B$ of density $0$ such that $A+B$ contains all except finitely many integers.
Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].
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? Must such an $A$ satisfy $\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?$

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

Erdős [Er54] proved that such a set $A$ exists with $\lvert A\cap\{1,\ldots,N\}\rvert\ll (\log N)^2$ (improving a previous result of Lorentz [Lo54] who achieved $\ll (\log N)^3$). Wolke [Wo96] has shown that such a bound is almost true, in that we can achieve $\ll (\log N)^{1+o(1)}$ if we only ask for almost all integers to be representable.

The answer to the third question is yes: Ruzsa [Ru98c] has shown that we must have $\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}\geq e^\gamma\approx 1.781.$

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

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

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

SOLVED - $500 If$f:\mathbb{N}\to \{-1,+1\}$then is it true that for every$C>0$there exist$d,m\geq 1$such that $\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?$ The Erdős discrepancy problem. This is true, and was proved by Tao [Ta16], who also proved the more general case when$f$takes values on the unit sphere. In [Er81] it is further conjectured that $\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.$ OPEN Let the van der Waerden number$W(k)$be such that whenever$N\geq W(k)$and$\{1,\ldots,N\}$is$2$-coloured there must exist a monochromatic$k$-term arithmetic progression. Improve the bounds for$W(k)$- for example, prove that$W(k)^{1/k}\to \infty$. When$p$is prime Berlekamp [Be68] has proved$W(p+1)\geq p2^p$. Gowers [Go01] has proved $W(k) \leq 2^{2^{2^{2^{2^{k+9}}}}}.$ In [Er81] Erdős further asks whether$W(k+1)/W(k)\to \infty$, or$W(k+1)-W(k)\to \infty$. SOLVED -$1000
Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.
Proved by Szemerédi [Sz74]. The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$ (with further slight improvements in [BlSi23]), Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$.

OPEN - $500 Let$A\subset (1,\infty)$be a countably infinite set such that for all$x\neq y\in A$and integers$k\geq 1$we have $\lvert kx -y\rvert \geq 1.$ Does this imply that $\liminf \frac{\lvert A\cap [1,x]\rvert}{x}=0?$ Or $\sum_{x\in A}\frac{1}{x\log x}<\infty,$ or $\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n)?$ Perhaps even $\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}\ll \frac{\log x}{\sqrt{\log\log x}}?$ Note that if$A$is a set of integers then the condition implies that$A$is a primitive set (that is, no element of$A$is divisible by any other), for which the convergence of$\sum_{n\in A}\frac{1}{n\log n}$was proved by Erdős [Er35], and that$\sum_{n<x}\frac{1}{n}=o(\log x)$was proved by Behrend [Be35]. In [Er73] mentions an unpublished proof of Haight that $\lim \frac{\lvert A\cap [1,x]\rvert}{x}=0$ holds if the elements of$A$are independent over$\mathbb{Q}$. Additional thanks to: Zachary Chase OPEN Let$N(k,\ell)$be the minimal$N$such that for any$f:\{1,\ldots,N\}\to\{-1,1\}$there must exist a$k$-term arithmetic progression$P$such that $\left\lvert \sum_{n\in P}f(n)\right\rvert> \ell.$ Find good upper bounds for$N(k,\ell)$. Is it true that for any$c>0$there exists some$C>1$such that $N(k,ck)\leq C^k?$ What about $N(k,1)\leq C^k$ or $N(k,\sqrt{k})\leq C^k?$ No decent bound is known even for$N(k,1)$. Probabilistic methods imply that, for every fixed constant$c>0$, we have$N(k,ck)>C_c^k$for some$C_c>1$. OPEN Find the smallest$h(d)$such that the following holds. There exists a function$f:\mathbb{N}\to\{-1,1\}$such that, for every$d\geq 1$, $\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),$ where$P_d$ranges over all finite arithmetic progressions with common difference$d$. Cantor, Erdős, Schreiber, and Straus [Er66] proved that$h(d)\ll d!$is possible. Van der Waerden's theorem implies that$h(d)\to \infty$. Beck [Be17] has shown that$h(d) \leq d^{8+\epsilon}$is possible for every$\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that$h(d)\gg d^{1/2}$. SOLVED Let$1\leq k<\ell$be integers and define$F_k(N,\ell)$to be minimal such that every set$A\subset \mathbb{N}$of size$N$which contains at least$F_k(N,\ell)$many$k$-term arithmetic progressions must contain an$\ell$-term arithmetic progression. Find good upper bounds for$F_k(N,\ell)$. Is it true that $F_3(N,4)=o(N^2)?$ Is it true that for every$\ell>3$$\lim_{N\to \infty}\frac{\log F_3(N,\ell)}{\log N}=2?$ Erdős remarks the upper bound$o(N^2)$is certainly false for$\ell >\epsilon \log N$. The answer is yes: Fox and Pohoata [FoPo20] have shown that, for all fixed$1\leq k<\ell$, $F_k(N,\ell)=N^{2-o(1)}$ and in fact $F_{k}(N,\ell) \leq \frac{N^2}{(\log\log N)^{C_\ell}}$ where$C_\ell>0$is some constant. SOLVED Let$f_3(n)$be the maximal size of a subset of$\{0,1,2\}^n$which contains no three points on a line. Is it true that$f_3(n)=o(3^n)$? Originally considered by Moser. It is trivial that$f_3(n)\geq R_3(3^n)$, the maximal size of a subset of$\{1,\ldots,3^n\}$without a three-term arithmetic progression. Moser showed that $f_3(n) \gg \frac{3^n}{\sqrt{n}}.$ The answer is yes, which is a corollary of the density Hales-Jewett theorem, proved by Furstenberg and Katznelson [FuKa91]. OPEN Let$F(N)$be the maximal size of$A\subseteq \{1,\ldots,N\}$which is 'non-averaging', so that no$n\in A$is the arithmetic mean of at least two elements in$A$. What is the order of growth of$F(N)$? Originally due to Straus. It is known that $N^{1/4}\ll F(N) \ll N^{\sqrt{2}-1+o(1)}.$ The lower bound is due to Bosznay [Bo89] and the upper bound to Conlon, Fox, and Pham [CFP23] (improving on earlier bound due to Erdős and Sárközy [ErSa90] of$\ll (N\log N)^{1/2}$). See also [789]. Additional thanks to: Zachary Chase OPEN Find the best function$f(d)$such that, in any 2-colouring of the integers, at least one colour class contains an arithmetic progression with common difference$d$of length$f(d)$for infinitely many$d$. Originally asked by Cohen. Erdős observed that colouring according to whether$\{ \sqrt{2}n\}<1/2$or not implies$f(d) \ll d$(using the fact that$\|\sqrt{2}q\| \gg 1/q$for all$q$, where$\|x\|$is the distance to the nearest integer). Beck [Be80] has improved this using the probabilistic method, constructing a colouring that shows$f(d)\leq (1+o(1))\log_2 d$. Van der Waerden's theorem implies$f(d)\to \infty$is necessary. OPEN Let$G_k(N)$be such that any set of$N$integers contains a subset of size at least$G_k(N)$which does not contain a$k$-term arithmetic progression. Determine the size of$G_k(N)$. How does it relate to$R_k(N)$, the size of the largest subset of$\{1,\ldots,N\}$without a$k$-term arithmetic progression? Is it true that $\lim_{N\to \infty}\frac{R_3(N)}{G_3(N)}=1?$ First asked and investigated by Riddell [Ri69]. It is trivial that$G_k(N)\leq R_k(N)$, and it is possible that$G_k(N) <R_k(N)$(for example with$k=3$and$N=14$). Komlós, Sulyok, and Szemerédi [KSS75] have shown that$R_k(N) \ll_k G_k(N)$. Additional thanks to: Zachary Chase OPEN Let$n_1<\cdots < n_r\leq N$with associated$a_i\pmod{n_i}$such that the congruence classes are disjoint (that is, every integer is$\equiv a_i\pmod{n_i}$for at most one$1\leq i\leq r$). How large can$r$be in terms of$N$? Let$f(N)$be the maximum possible$r$. Erdős and Stein conjectured that$f(N)=o(N)$, which was proved by Erdős and Szemerédi [ErSz68], who showed that, for every$\epsilon>0$, $\frac{N}{\exp((\log N)^{1/2+\epsilon})} \ll_\epsilon f(N) < \frac{N}{(\log N)^c}$ for some$c>0$. Erdős believed the lower bound is closer to the truth. SOLVED -$250
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$ (which was also asked by Erdős in [Er73]).
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$.

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

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$?
Erdős [Er50] proved this when $A=\{2^k : k\geq 0\}$. Solved by Chen and Ding [ChDi22].

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?
Wintner observed that if $f$ can take complex values on the unit circle then the limit need not exist. The answer is yes, as proved by Wirsing [Wi67], and generalised by Halász [Ha68].
OPEN - $100 Let$f(N)$be the maximum size of$A\subseteq \{1,\ldots,N\}$such that the sums$a+b+c$with$a,b,c\in A$are all distinct (aside from the trivial coincidences). Is it true that $f(N)\sim N^{1/3}?$ Originally asked to Erdős by Bose. Bose and Chowla [BoCh62] provided a construction proving one half of this, namely $(1+o(1))N^{1/3}\leq f(N).$ The best upper bound known to date is due to Green [Gr01], $f(N) \leq ((7/2)^{1/3}+o(1))N^{1/3}$ (note that$(7/2)^{1/3}\approx 1.519\cdots$). More generally, Bose and Chowla conjectured that the maximum size of$A\subseteq \{1,\ldots,N\}$with all$r$-fold sums distinct (aside from the trivial coincidences) then $\lvert A\rvert \sim N^{1/r}.$ This is known only for$r=2$(see [30]). Additional thanks to: Cedric Pilatte OPEN 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$? If we further ask that$\lvert S\rvert=l$(for any fixed$l$) then is the number of solutions $\ll \frac{2^N}{N^2},$ with the implied constant independent of$l$and$t$? Erdős and Moser proved the first bound with an additional factor of$(\log n)^{3/2}$. This was removed by Sárközy and Szemerédi [SaSz65], thereby answering the first question in the affirmative. Stanley [St80] has shown that this quantity is maximised when$A$is an arithmetic progression and$t=\tfrac{1}{2}\sum_{n\in A}n$. Additional thanks to: Zachary Chase OPEN Is it true that for any$n,k\geq 1$, if$n+1,\ldots,n+k$are all composite then there are distinct primes$p_1,\ldots,p_k$such that$p_i\mid n+i$for$1\leq i\leq k$? Note this is trivial when$k\leq 2$. Originally conjectured by Grimm. This is a very difficult problem, since it in particular implies$p_{n+1}-p_n <p_n^{1/2-c}$for some constant$c>0$, in particular resolving Legendre's conjecture. Grimm proved that this is true if$k\ll \log n/\log\log n$. Erdős and Selfridge improved this to$k\leq (1+o(1))\log n$. Ramachandra, Shorey, and Tijdeman [RST75] have improved this to $k\ll\left(\frac{\log n}{\log\log n}\right)^3.$ 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) the only cases where equality is achieved are when$A=\{1,\ldots,n\}$or$\{L/1,\ldots,L/n\}$(where$L=\mathrm{lcm}(1,\ldots,n)$) or$\{2,3,4,6\}$. Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87]. Proved for all sets by Balasubramanian and Soundararajan [BaSo96]. 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}?$ If$A\subseteq \{1,\ldots,n\}$is such that all products$a_1\cdots a_r$are distinct for$a_1<\cdots <a_r$then is it true that $\lvert A\rvert \leq \pi(n)+O(n^{\frac{r+1}{2r}})?$ Erdős [Er68] proved that there exist some constants$0<c_1\leq c_2$such that $\pi(n)+c_1 n^{3/4}(\log n)^{-3/2}\leq F(n)\leq \pi(n)+c_2 n^{3/4}(\log n)^{-3/2}.$ Surprisingly, if we consider the corresponding problem in the reals (so consider the largest$A\subset [1,x]$such that for any distinct$a,b,c,d\in A$we have$\lvert ab-cd\rvert \geq 1$) then Alexander proved that$\lvert A\rvert> x/8e$is possible (disproving an earlier conjecture of Erdős [Er73] that$m=o(x)$). Alexander's construction seems to be unpublished, and I have no idea what it is. See also [490], [793], and [796]. Additional thanks to: Rishika Agrawal SOLVED Let$N\geq 1$. What is the size of the largest$A\subset \{1,\ldots,N\}$such that$\mathrm{lcm}(a,b)\leq N$for all$a,b\in A$? Is it attained by choosing all integers in$[1,(N/2)^{1/2}]$together with all even integers in$[(N/2)^{1/2},(2N)^{1/2}]$? Let$g(N)$denote the size of the largest such$A$. The construction mentioned proves that $g(N) \geq \left(\tfrac{9}{8}n\right)^{1/2}+O(1).$ Erdős [Er51b] proved$g(N) \leq (4n)^{1/2}+O(1)$. Chen [Ch98] established the asymptotic $g(N) \sim \left(\tfrac{9}{8}n\right)^{1/2}.$ Chen and Dai [DaCh06] proved that $g(N)\leq \left(\tfrac{9}{8}n\right)^{1/2}+O\left(\left(\frac{N}{\log N}\right)^{1/2}\log\log N\right).$ In [ChDa07] the same authors prove that, infinitely often, Erdős' construction is not optimal: if$B$is that construction and$A$is such that$\lvert A\rvert=g(N)$then, for infinitely many$N$, $\lvert A\rvert\geq \lvert B\rvert+t,$ where$t\geq 0$is defined such that the$t$-fold iterated logarithm of$N$is in$[0,1)$. Additional thanks to: Terence Tao 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, who proved it when$t=p-1$. A similar conjecture was made for arbitrary abelian groups by Alspach. Such an ordering is often called a valid ordering. This has been proved for$t\leq 12$(see Costa and Pellegrini [CoPe20] and the references therein) and for$p-3\leq t\leq p-1$(see Hicks, Ollis, and Schmitt [HOS19] and the references therein). Kravitz [Kr24] has proved this for $t \leq \frac{\log p}{\log\log p}.$ Additional thanks to: Zachary Chase 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]. Additional thanks to: Mehtaab Sawhney OPEN 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)$. In particular, is it true that$\ell(N)\sim N^{1/2}$? Originally asked by Riddell [Ri69]. Erdős noted the bounds $N^{1/3} \ll \ell(N) \leq (1+o(1))N^{1/2}$ (the upper bound following from the case$A=\{1,\ldots,N\}$). The lower bound was improved to$N^{1/2}\ll \ell(N)$by Komlós, Sulyok, and Szemerédi [KSS75]. The correct constant is unknown, but it is likely that the upper bound is true, so that$\ell(N)\sim N^{1/2}$. In [AlEr85] Alon and Erdős make the stronger conjecture that perhaps$A$can always be written as the union of at most$(1+o(1))N^{1/2}$many Sidon sets. (This is easily verified for$A=\{1,\ldots,N\}$using standard constructions of Sidon sets.) 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? In other words, must some colour class be an IP set. Asked by Graham and Rothschild. See also [531]. Proved by Hindman [Hi74] (for any number of colours). 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$\omega(n)=k$for all$n\in A$and there does not exist$a_1,\ldots,a_r\in A$and an integer$d$such that$(a_i,a_j)=d$for all$i\neq j$and$(a_i/d,d)=1$for all$i$. The conjectured upper bound for$f_r(N)$would follow if the size of such an$A$must be at most$c_r^k$. The original sunflower proof of Erdős and Rado gives the upper bound$c_r^kk!$. 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. Additional thanks to: Zach Hunter 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}.$ Erdős observed that $\sum_{n\in A}\frac{1}{n}\sum_{p\leq N}\frac{1}{p}\leq r\sum_{m\leq N^2}\frac{1}{m}\ll r\log N,$ and hence $\sum_{n\in A}\frac{1}{n} \ll r\frac{\log N}{\log\log N}.$ See also [536] and [537]. OPEN Let$h(n)$be such that, for any set$A\subseteq \mathbb{N}$of size$n$, the set $\left\{ \frac{a}{(a,b)}: a,b\in A\right\}$ has size at least$h(n)$. Estimate$h(n)$. Erdős and Szemerédi proved that $n^{1/2} \ll h(n) \ll n^{1-c}$ for some constant$c>0$. 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}$? A conjecture of Erdős and Heilbronn. The answer is yes, proved by Szemerédi [Sz70] (in fact for arbitrary finite abelian groups). Erdős speculated that perhaps the correct threshold is$(2N)^{1/2}$; this is also a conjecture of Selfridge, and has been proved when$N$is prime by Balandraud [Ba12]. 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. SOLVED Is it true that if$A\subseteq\{1,\ldots,n\}$is a set such that$[a,b]>n$for all$a\neq b$, where$[a,b]$is the least common multiple, then $\sum_{a\in A}\frac{1}{a}\leq \frac{31}{30}.$ Is it true that there must be$\gg n$many$m\leq n$which do not divide any$a\in A$? The first bound is best possible as$A=\{2,3,5\}$demonstrates. Resolved by Schinzel and Szekeres [ScSz59] who proved the answer to the first question is yes and the answer to the second is no, and in fact there are examples with at most$n/(\log n)^c$many such$m$, for some constant$c>0$. In [Er73] Erdős further speculates that in fact $\sum_{a\in A}\frac{1}{a}\leq 1+o(1),$ where the$o(1)$term$\to 0$as$n\to \infty$. See also [784]. 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. OPEN Is it true that if$A\subset \mathbb{R}^2$is a set of$n$points such that every subset of$3$points determines$3$distinct distances (i.e.$A$has no isosceles triangles) then$A$must determine at least$f(n)n$distinct distances, for some$f(n)\to \infty$? In [Er73] Erdős attributes this problem (more generally in$\mathbb{R}^k$) to himself and Davies. In [Er97e] he does not mention Davis, but says this problem was investigated by himself, Füredi, Ruzsa, and Pach. In [Er73] Erdős says it is not even known in$\mathbb{R}$whether$f(n)\to \infty$. Straus has observed that if$2^k\geq n$then there exist$n$points in$\mathbb{R}^k$which contain no isosceles triangle and determine at most$n-1$distances. See also [656]. OPEN Fix some constant$C>0$and let$n$be large. Let$A\subseteq \{2,\ldots,n\}$be such that$(a,b)=1$for all$a\neq b\in A$and$\sum_{n\in A}\frac{1}{n}\leq C$. What choice of such an$A$minimises the number of integers$m\leq n$not divisible by any$a\in A$? Is this minimised by letting$n\geq q_1>q_2>\cdots$be the consecutive primes in decreasing order and choosing$A=\{q_1,\ldots,q_k\}$where$k$is maximal such that $\sum_{i=1}^k\frac{1}{q_i}\leq C?$ OPEN Let$C>0$be some constant and$n$be large. If$A\subseteq\{1,\ldots,n\}$has$\sum_{n\in A}\frac{1}{n}\leq C$then is there some$c$(which may depend on$C$) such that $\{ m\leq n : a\nmid m\textrm{ for all }a\in A\}$ has size$\geq n/(\log n)^{c}$? An example of Schinzel and Szekeres [ScSz59] shows that this would be best possible (up to the value of$c$). See also [542]. SOLVED Let$A,B\subseteq \mathbb{N}$be infinite sets such that$A+B$contains all large integers. Let$A(x)=\lvert A\cap [1,x]\rvert$and similarly for$B(x)$. Is it true that if$A(x)B(x)\sim x$then $A(x)B(x)-x\to \infty$ as$x\to \infty$? A conjecture of Erdős and Danzer. Such sets$A$and$B$(with all large integers in$A+B$and$A(x)B(x)\sim x$) are called exact additive complements. Danzer [Da64] proved that exact additive complements exist. The answer is yes, proved by Sárközy and Szemerédi [SaSz94]. Ruzsa [Ru17] has constructed, for any function$w(x)\to \infty$, such a pair of sets with $A(x)B(x)-x<w(x)$ for infinitely many$x$. OPEN Let$\epsilon>0$. Is there some set$A\subset \mathbb{N}$of density$>1-\epsilon$such that$a_1\cdots a_r=b_1\cdots b_s$with$a_i,b_j\in A$can only hold when$r=s$? Similarly, can one always find a set$A\subset\{1,\ldots,N\}$with this property of size$\geq (1-o(1))N$? An example of such a set with density$1/4$is given by the integers$\equiv 2\pmod{4}$. Selfridge constructed such a set with density$1/e-\epsilon$for any$\epsilon>0$: let$p_1<\cdots<p_k$be a sequence of large consecutive primes such that $\sum_{i=1}^k\frac{1}{p_i}<1<\sum_{i=1}^{k+1}\frac{1}{p_i},$ and let$A$be those integers divisible by exactly one of$p_1,\ldots,p_k$. For the second question the set of integers with a prime factor$>N^{1/2}$give an example of a set with size$\geq (\log 2)N$. Erdős could improve this constant slightly. Additional thanks to: Rishika Agrawal OPEN Let$g(n)$be maximal such that given any set$A\subset \mathbb{R}$with$\lvert A\rvert=n$there exists some$B\subseteq A$of size$\lvert B\rvert\geq g(n)$such that$b_1+b_2\not\in A$for all$b_1\neq b_2\in B$. Estimate$g(n)$. A conjecture of Erdős and Moser. Klarner proved$g(n) \gg \log n$(indeed, a greedy construction suffices). Choi [Ch71] proved$g(n) \ll n^{2/5+o(1)}$. The current best bounds known are $(\log n)^{1+c} \ll g(n) \ll \exp(\sqrt{\log n})$ for some constant$c>0$, the lower bound due to Sanders [Sa21] and the upper bound due to Ruzsa [Ru05]. OPEN Let$f(n)$be maximal such that if$B\subset (2n,4n)\cap \mathbb{N}$there exists some$C\subset (n,2n)\cap \mathbb{N}$such that$c_1+c_2\not\in B$for all$c_1\neq c_2\in C$and$\lvert C\rvert+\lvert B\rvert \geq f(n)$. Estimate$f(n)$. In particular is it true that$f(n)\leq n^{1/2+o(1)}$? A conjecture of Choi [Ch71], who proved$f(n) \ll n^{3/4}$. OPEN Let$h(n)$be maximal such that if$A\subseteq \mathbb{Z}$with$\lvert A\rvert=n$then there is$B\subseteq A$with$\lvert B\rvert \geq h(n)$such that if$a_1+\cdots+a_r=b_1+\cdots+b_s$with$a_i,b_i\in B$then$r=s$. Estimate$h(n)$. Straus [St66] proved$h(n) \ll n^{1/2}$. Erdős noted the bound$h(n)\gg n^{1/3}$and claimed that Choi had proved$h(n) \gg (n\log n)^{1/3}$, although I cannot find such a paper. See also [186]. OPEN Let$l(n)$be maximal such that if$A\subset\mathbb{Z}$with$\lvert A\rvert=n$then there exists some$B\subseteq A$with$\lvert B\rvert \geq l(n)$such that there are no solutions to $a_1=a_2+\cdots+a_r$ with$a_i\in B$all distinct. Estimate$l(n)$. In particular, is it true that$l(n)n^{-1/2}\to \infty$? Is it true that$l(n)< n^{1-c}$for some$c>0$? Erdős observed that$l(n)\geq (n/2)^{1/2}$, which Choi improved to$l(n)>(1+c)n^{1/2}$for some$c>0$. Erdős thought he could prove$l(n)=o(n)$but had 'difficulties in reconstructing [his] proof'. OPEN Let$g(n)$be minimal such that there exists$A\subseteq \{0,\ldots,n\}$of size$g(n)$with$\{0,\ldots,n\}\subseteq A+A$. Estimate$g(n)$. In particular is it true that$g(n)\sim 2n^{1/2}$? A problem of Rohrbach, who proved $(2^{1/2}+c)n^{1/2} \leq g(n) \leq 2n^{1/2}$ for some small constant$c>0$. OPEN Let$f(n)$be maximal such that in any$A\subset \mathbb{Z}$with$\lvert A\rvert=n$there exists some sum-free subset$B\subseteq A$with$\lvert B\rvert \geq f(n)$, so that there are no solutions to $a+b=c$ with$a,b,c\in B$. Estimate$f(n)$. Erdős gave a simple proof that shows$f(n) \geq n/3\$. The best known bounds are $\frac{n}{3}+2\leq f(n) \leq \frac{n}{3}+o(n).$ The lower bound is due to Bourgain [Bo97] and the upper bound is due to Eberhard, Green, and Manners [EGM14].