A partition of the Boolean cube with no structured sumset
Let $\mathbb{F}_2^n$ be partitioned into sets $A_1, \dots, A_K$, and write $2A_i = A_i + A_i$. The question is open even for $K = 3$. For the Hamming ball $B = \{x : x_1 + \dots + x_n \le \frac{n}{2} - \sqrt{n}\}$ (the sum taken in the integers), $2B$ contains no coset of codimension $O(1)$, so one special case is to show that three such Hamming balls, relative to different bases, cannot cover $\mathbb{F}_2^n$. A positive answer would give a positive answer to the analogous question for a set with an additive complement of size $K$.
Problem. Must $2A_i$ contain a coset of a subspace of codimension $O_K(1)$ for some $i$?
Source: B. Green, 100 open problems (version of January 2026), Problem 53.
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NT
- Keywords
- additive combinatorics, finite field model, Hamming balls, partitions, sumsets
References
@incollection{green2005ffm,
author = {Green, Ben},
title = {Finite field models in additive combinatorics},
booktitle = {Surveys in Combinatorics 2005},
series = {London Mathematical Society Lecture Note Series},
volume = {327},
pages = {1--28},
publisher = {Cambridge University Press},
year = {2005},
doi = {10.1017/CBO9780511734885.002}
}
@article{glasscock2022,
author = {Glasscock, Daniel and Koutsogiannis, Andreas and Richter, Florian K.},
title = {On {K}atznelson's question for skew-product systems},
journal = {Bulletin of the American Mathematical Society (N.S.)},
volume = {59},
number = {4},
pages = {569--606},
year = {2022},
doi = {10.1090/bull/1764},
eprint = {2106.11393},
archivePrefix = {arXiv}
}
@misc{jaber2026hamming,
author = {Jaber, Michael and Kumar, Vinayak M.},
title = {Covering $\mathbb{F}_2^n$ with {H}amming balls},
year = {2026},
eprint = {2606.07918},
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 53; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
Green asked the following question concerning structures in sumsets: Suppose that $\mathbb{F}_2^n$ is partitioned into sets $A_1, \dots, A_K$. Does $A_i+A_i$ contain a coset of codimension $O_K(1)$ for some $i$? An answer is not known even in the case of $K = 3$. We resolve this question in the affirmative in two special cases: (1) when $A_1, A_2$ are Hamming …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-29 | Open → Partially resolved | The registry's curators | Covering $\mathbb{F}_2^n$ with Hamming Balls v1 recorded from arXiv:2606.07918v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01037, "A partition of the Boolean cube with no structured sumset", clopen.solutions.