OP-01133 Open

Partitions of [N] whose parts have few restricted sums

Note: A Lean proof on GitHub (K. Kitamura, 2026, no paper) shows that the inequality fails for k = ⌈N^{23/40}⌉ and all large N.

Submit a result

For a set $A$ of integers write $A \hat{+} A = \{a + a' : a, a' \in A, a \ne a'\}$. Erdős, Sárközy and Sós showed that if $k \ll \log \log N$, then every partition $\{1, \dots, N\} = A_1 \cup \dots \cup A_k$ satisfies $\bigl|\bigcup_{i=1}^k (A_i \hat{+} A_i)\bigr| \ge \frac{1}{10} N$, and that this can fail when $k \gg N / \log N$.

Problem. For which functions $k = k(N)$ does every partition of $\{1, \dots, N\}$ into $k$ parts satisfy this inequality?

Source: K. F. Roth's question for constant k, answered in P. Erdős, A. Sárközy and V. T. Sós, On a conjecture of Roth and some related problems I (1989); see Erdős problem #484. Listed in this form as Problem 25 in B. Green, 100 open problems (version of January 2026).

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: CO — Combinatorics
Secondary: NT
Keywords: additive combinatorics, Erdős problems, partitions, restricted sumsets
Literature checked: Nov. 3, 2026 by clemens-admin

References

@incollection{erdossarkozysos1989roth,
  author = {Erd{\H o}s, P. and S{\'a}rk{\"o}zy, A. and S{\'o}s, V. T.},
  title = {On a conjecture of {R}oth and some related problems {I}},
  booktitle = {Irregularities of Partitions (Fert{\H o}d, 1986)},
  series = {Algorithms Combin. Study Res. Texts},
  volume = {8},
  pages = {47--59},
  publisher = {Springer},
  year = {1989},
  doi = {10.1007/978-3-642-61324-1_4}
}

@incollection{ruzsa2004restricted,
  author = {Ruzsa, Imre Z.},
  title = {A problem on restricted sumsets},
  booktitle = {Towards a Theory of Geometric Graphs},
  series = {Contemp. Math.},
  volume = {342},
  pages = {245--248},
  publisher = {Amer. Math. Soc.},
  year = {2004},
  doi = {10.1090/conm/342/06144}
}

@misc{kitamura2026green25,
  author = {Kitamura, Kenta},
  title = {A {L}ean proof of an improved upper bound for {G}reen's Open Problem 25},
  howpublished = {\url{https://github.com/KitaKen1/green-25-upper-bound/tree/3a54a688dfc4d7b9c8990bbaeb1a124c075454e4}},
  note = {Lean 4; its mathematical explanation is marked AI-generated; not a paper},
  year = {2026}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 25; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01133, "Partitions of [N] whose parts have few restricted sums", clopen.solutions.