Logo
All Random Solved Random Open
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