The Erdős–Moser problem: a large subset avoiding its own restricted sums in A
Let $A \subset \mathbb{Z}$ be a set of $n$ integers, and for $S \subset A$ let $S \hat{+} S = \{s_1 + s_2 : s_1, s_2 \in S,\ s_1 \ne s_2\}$ be its restricted sumset. Sanders proved that some $S$ with $S \hat{+} S$ disjoint from $A$ has $|S| \ge (\log n)^{1 + c}$ for an absolute $c > 0$, and Beker gave another proof with any $c < \frac{1}{68}$. In the other direction, Ruzsa showed that one cannot in general take $|S|$ larger than $e^{C\sqrt{\log n}}$.
Problem. Is there a set $S \subset A$ with $|S| = (\log n)^{100}$ such that $S \hat{+} S$ is disjoint from $A$?
Source: P. Erdős and L. Moser; recorded in P. Erdős, Extremal problems in number theory, Proc. Sympos. Pure Math. 8 (1965). Listed as Problem 2 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- NT — Number Theory
- Secondary
- CO
- Keywords
- additive combinatorics, Erdős–Moser problem, restricted sumsets, sum-free sets
References
@inproceedings{erdos1965extremal,
author = {Erd{\H o}s, P.},
title = {Extremal problems in number theory},
booktitle = {Theory of Numbers},
series = {Proceedings of Symposia in Pure Mathematics},
volume = {8},
pages = {181--189},
publisher = {American Mathematical Society},
year = {1965}
}
@article{sanders2021erdosmoser,
author = {Sanders, Tom},
title = {The {E}rd{\H o}s--{M}oser sum-free set problem},
journal = {Canadian Journal of Mathematics},
volume = {73},
number = {1},
pages = {63--107},
year = {2021},
doi = {10.4153/S0008414X1900049X}
}
@article{ruzsa2005sumavoiding,
author = {Ruzsa, Imre Z.},
title = {Sum-avoiding subsets},
journal = {The Ramanujan Journal},
volume = {9},
number = {1-2},
pages = {77--82},
year = {2005},
doi = {10.1007/s11139-005-0826-4}
}
@article{beker2026erdosmoser,
author = {Beker, Adrian},
title = {The {E}rd{\H o}s--{M}oser sum-free set problem via improved bounds for $k$-configurations},
journal = {International Mathematics Research Notices},
volume = {2026},
number = {20},
pages = {rnag235},
year = {2026},
doi = {10.1093/imrn/rnag235},
eprint = {2501.10203},
archivePrefix = {arXiv}
}
@misc{zhi2026branch,
author = {Zhi, Yao},
title = {Branch-sensitive density increments for $k$-configurations},
year = {2026},
eprint = {2610.03750},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 2; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
We refine the density-increment argument for $k$-configurations developed by Beker. The point is not to introduce a new inverse theorem, but to retain information that is lost when the graph-counting output is compressed into a single uniform alternative. For the transitive $K_k$ appearing in the $k$-configuration problem we keep a fixed moment throughout the graph recursion and obtain three genuinely …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-29 | Open → Partially resolved | The registry's curators | Branch-Sensitive Density Increments for $k$-Configurations v1 recorded from arXiv:2610.03750v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01028, "The Erdős–Moser problem: a large subset avoiding its own restricted sums in A", clopen.solutions.