OPEN
This is open, and cannot be resolved with a finite computation.
- $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$).
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]).
This is discussed in problem C11 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 30 September 2025.
Additional thanks to: Cedric Pilatte
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #241, https://www.erdosproblems.com/241, accessed 2026-02-13
