2 solved out of 15 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 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$.
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$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$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$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 Is it true that $\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?$ Kövári, Sós, and Turán [KST54] proved $\mathrm{ex}(n; K_{r,r}) \ll n^{2-1/r}.$ Brown [Br66] proved the conjectured lower bound when$r=3$. See also [147]. Additional thanks to: Rishika Agrawal SOLVED Give an asymptotic formula for$\mathrm{ex}(n;C_4)$. Erdős and Klein [Er38] proved$\mathrm{ex}(n;C_4)\asymp n^{3/2}$. Reiman [Re] proved $\frac{1}{2\sqrt{2}}\leq \lim \frac{\mathrm{ex}(n;C_4)}{n^{3/2}}\leq \frac{1}{2}.$ Erdős and Rényi, and independently Brown, gave a construction that proved if$n=q^2+q+1$, where$q$is a prime power, then $\mathrm{ex}(n;C_4)\geq\frac{1}{2}q(q+1)^2.$ Coupled with the upper bound of Reiman this implies that$\mathrm{ex}(n;C_4)\sim\frac{1}{2}n^{3/2}$for all large$n$. Füredi [Fu83] proved that if$q>13$then $\mathrm{ex}(n;C_4)=\frac{1}{2}q(q+1)^2.$ See also [572]. Additional thanks to: Rishika Agrawal 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$F(n)$be the maximum possible size of a subset$A\subseteq\{1,\ldots,N\}$such that$a\nmid bc$whenever$a,b,c\in A$with$a\neq b$and$a\neq c$. Is there a constant$c$such that $F(n)=\pi(n)+(c+o(1))n^{2/3}(\log n)^{-2}?$ Erdős [Er38] proved there exist constants$0<c_1\leq c_2$such that $\pi(n)+c_1n^{2/3}(\log n)^{-2}\leq F(n) \leq \pi(n)+c_2n^{2/3}(\log n)^{-2}.$ Erdős [Er69] gave a simple proof that$F(n) \leq \pi(n)+n^{2/3}$: we define a graph with vertex set the union of those integers in$[1,n^{2/3}]$with all primes$p\in (n^{2/3},n]$. We have an edge$u\sim v$if and only if$uv\in A$. It is easy to see that every$m\leq n$can be written as$uv$where$u\leq n^{2/3}$and$v$is either prime or$\leq n^{2/3}$, and hence there are$\geq \lvert A\rvert$many edges. This graph contains no path of length$3$and hence must be a tree and have fewer edges than vertices, and we are done. This can be improved to give the upper bound mentioned by using a subset of integers in$[1,n^{2/3}]$. More generally, one can ask for such an asymptotic for the size of sets such that no$a\in A$divides the product of$r$distinct other elements of$A$, with the exponent$2/3$replaced by$\frac{2}{r+1}$. See also [425]. Additional thanks to: Rishika Agrawal OPEN Is it true that every$3$-uniform hypergraph on$3n$vertices with at least$n^3+1$edges must contain either a subgraph on$4$vertices with$3$edges or a subgraph on$5$vertices with$7$edges? Additional thanks to: Rishika Agrawal OPEN Let$g(n)$be the maximal size of$A\subseteq \{1,\ldots,n\}$such that$\prod_{n\in S}n$are distinct for all$S\subseteq A$. Is it true that $g(n) \leq \pi(n)+\pi(n^{1/2})+o\left(\frac{x^{1/2}}{\log n}\right)?$ Erdős proved [Er66] $g(n) \leq \pi(n)+O\left(\frac{x^{1/2}}{\log n}\right).$ This upper bound would be essentially best possible, since one could take$A$to be all primes and squares of primes. Additional thanks to: Rishika Agrawal OPEN Let$k\geq 2$and let$g_k(n)$be the largest possible size of$A\subseteq \{1,\ldots,n\}$such that every$m$has$<k$solutions to$m=a_1a_2$with$a_1<a_2\in A$. Estimate$g_k(n)$. In particular, is it true that $g_k(n)=\frac{\log\log n}{\log n}n+(c+o(1))\frac{n}{(\log n)^2}$ for some constant$c$? Erdős [Er64d] proved that if$2^{r-1}<k\leq 2^r$then $g_k(n) \sim \frac{(\log\log n)^{r-1}}{(r-1)!\log n}n$ (which is the asymptotic count of those integers$\leq n$with$r$distinct prime factors). In particular the asymptotics of$g_k(n)$are known; in this problem Erdős was asking about the second order terms. For$k=3$he could prove the existence of some$0<c_1\leq c_2$such that $\frac{\log\log n}{\log n}n+c_1\frac{n}{(\log n)^2}\leq g_k(n)\leq \frac{\log\log n}{\log n}n+c_2\frac{n}{(\log n)^2}.$ The special case$k=2\$ is the subject of [425].