Restricted Sumsets in Partitions

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a set $B\subset\mathbb Z$, its restricted sumset is $B\widehat{+}B=\{b+b':b,b'\in B,\ b\ne b'\}$. For integers $N\geq2$ and $1\leq k\leq N$, define \[ R_k(N)=\min_{c:[N]\to[k]} \left|\{a+b:1\leq a<b\leq N,\ c(a)=c(b)\}\right|. \] Empty color classes are allowed. The counted set is the union of the restricted sumsets of the color classes; a sum attained in several classes is counted once.

Statement recorded in the supplied source.

Determine, as a function of $N$, the values of $k$ for which every $k$-coloring of $[N]$ satisfies $R_k(N)\geq N/10$. Equivalently, determine the growth of the threshold \[ \kappa(N)=\max\{k\in\{1,\ldots,N\}:R_k(N)\geq N/10\}. \] The number of colors may grow with $N$; this is not restricted to the already-known case of fixed $k$. [S2]

Short English statement

How many colors can an interval be partitioned into while guaranteeing that the union of all same-color sums of two distinct numbers has size at least one tenth of the interval?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 156 (GREEN-068). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Ben Green, 100 Open Problems, maintained author collection, Problem 25 and its comments, accessed 7 October 2026. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.