Cosets in A + A for sets with a small additive complement
Let $A \subset \mathbb{F}_2^n$ have an additive complement of size $K$: a set $S \subset \mathbb{F}_2^n$ with $|S| = K$ and $A + S = \mathbb{F}_2^n$. Write $2A = A + A$. Green also asked whether $2A$ must contain a coset of codimension $O(\log K)$, which would imply the polynomial Bogolyubov conjecture; Hosseini and Alweiss pointed out that it need not: for $A$ the Hamming ball of radius $n/2 - \sqrt{n}$ some $S$ of size $O(n)$ has $A + S = \mathbb{F}_2^n$, while every subspace contained in $A - A$ has codimension $\gg \sqrt{n}$.
Problem. Does $2A$ contain a coset of a subspace of codimension $O_K(1)$?
Source: B. Green, 100 open problems (version of January 2026), Problem 52.
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NT
- Keywords
- additive combinatorics, additive complements, Bogolyubov's lemma, finite field model, sumsets
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@article{katznelson2001,
author = {Katznelson, Y.},
title = {Chromatic numbers of {C}ayley graphs on $\mathbb{Z}$ and recurrence},
journal = {Combinatorica},
volume = {21},
number = {2},
pages = {211--219},
year = {2001},
doi = {10.1007/s004930100019}
}
@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}
}
@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}
}
@misc{kitaken2026green52,
author = {{KitaKen1}},
title = {green-52-log-counterexample: a {L}ean formalization of the counterexample to the codimension $O(\log K)$ version},
howpublished = {\url{https://github.com/KitaKen1/green-52-log-counterexample}},
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 52; 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-00943, "Cosets in A + A for sets with a small additive complement", clopen.solutions.