Sumset small-doubling covering structure

Conjecture 15 · arXiv:2509.02561

arXiv Conjecture medium confidence— first stated 2025-09-02

Authors: Noga Alon, Huy Tuan Pham

Status open high confidence

Conjecture 15 of arXiv:2509.02561 proposes an optimal covering lemma: collections \mathcal{F}_{\ell} of complexity \log|\mathcal{F}_{\ell}|=\tilde{O}(2^{\ell}) and minimum member size \tilde{\Omega}(2^{\ell}s) such that every set A with |A|=s and |A+A|\leq K|A| has its sumset containing some F\in\mathcal{F}_{\ell} for \ell\leq\log_2 K. The paper establishes a weaker version (Theorem 6) with complexity exponential in 2^{2\ell} rather than 2^{\ell}, and the conjecture asks to close this gap. No follow-up resolving the conjecture was found; the paper was posted in September 2025 and the conjecture appears to remain open.

Reviewer notes. No follow-up found in indexed literature. The conjecture is an optimal strengthening of Theorem 6 of the same paper, reducing the complexity bound from \exp(O(2^{2\ell})) to \exp(\tilde{O}(2^{\ell})). It is motivated by Lovett's question (from Green's open problems list) on whether sumsets A+A of dense sets contain large subsets of the form B+B+B+B. The paper is very recent (September 2025), so the open status is expected.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. There exist collections of sets $\mathcal{F}_{\ell}$ such that [size/complexity conditions] and such that for every $|A|=s$ with $|A+A|\leq K|A|$, there exists $\ell\leq\log_{2}K$ and $F\in\mathcal{F}_{\ell}$ such that $A+A\supseteq F$.

Context

The authors believe the main covering lemma — showing sumsets of sets with small doubling contain dense subsets of low complexity — will have further applications beyond those discussed in the paper. This conjecture proposes an optimal or strengthened form of that covering lemma, and is motivated in part by a version of Lovett's question (from Green's list of open problems [14]) asking whether sumsets $A+A$ of dense sets contain large subsets that are iterated sumsets $B+B+B+B$.

Notes. The statement text as extracted appears truncated: the clause 'such that and such that' suggests that the size or complexity conditions on the collections $\mathcal{F}_{\ell}$ were lost in the source extraction. The mathematical content may be incomplete or garbled.

Source paper

Random Cayley graphs and random sumsets
Noga Alon, Huy Tuan Pham · 2025-09-02
https://arxiv.org/abs/2509.02561