The largest coset in A + A for a dense subset of F_2^n
Let $A \subset \mathbb{F}_2^n$ have density $\alpha$ and write $2A = A + A$. Every such $2A$ contains a coset of dimension $\gg_\alpha n$, and there are dense sets $A$ for which $2A$ contains no coset of dimension $n - \sqrt{n}$. Sanders asked whether density at least $\frac12 - K/\sqrt{n}$ already forces a coset of codimension $O_K(1)$ in $2A$. In $[N]$, with progressions in place of cosets, the longest progression guaranteed is at least of the shape $e^{c(\log N)^{1/2}}$ (Green) and at most of the shape $e^{c(\log N)^{2/3}}$ (Ruzsa).
Problem. What is the largest dimension of a coset that $2A$ is guaranteed to contain?
Source: B. Green, Finite field models in additive combinatorics (2005), Problem 9.2. Listed as Problem 51 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
- Bogolyubov's lemma, cosets, finite field model, sumsets
- Literature checked
- Oct. 26, 2026 by clemens-admin
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},
note = {Problem 9.2; Theorems 9.3 and 9.4}
}
@article{sanders2011half,
author = {Sanders, Tom},
title = {Green's sumset problem at density one half},
journal = {Acta Arithmetica},
volume = {146},
number = {1},
pages = {91--101},
year = {2011},
doi = {10.4064/aa146-1-6},
eprint = {1003.5649},
archivePrefix = {arXiv}
}
@article{green2002ap,
author = {Green, B.},
title = {Arithmetic progressions in sumsets},
journal = {Geometric and Functional Analysis},
volume = {12},
number = {3},
pages = {584--597},
year = {2002},
doi = {10.1007/s00039-002-8258-4}
}
@article{ruzsa1991ap,
author = {Ruzsa, Imre Z.},
title = {Arithmetic progressions in sumsets},
journal = {Acta Arithmetica},
volume = {60},
number = {2},
pages = {191--202},
year = {1991},
doi = {10.4064/aa-60-2-191-202}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 51; 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-00988, "The largest coset in A + A for a dense subset of F_2^n", clopen.solutions.