Optimal covering conjecture for small-doubling sumsets

About 1 year old · traced to

Let AA be a set of size ss with doubling constant bounded by KK, meaning ∣A+A∣≤K∣A∣|A+A|\leq K|A|. For each ellell let Fℓ\mathcal{F}_\ell be a collection of sets, and let O~\tilde{O} and Ω~\tilde{\Omega} suppress polylogarithmic factors in the relevant parameter. Optimal covering conjecture. There exist collections of sets Fℓ\mathcal{F}_\ell such that

log⁡∣Fℓ∣=O~(2ℓ),\log |\mathcal{F}_\ell|=\tilde{O}(2^\ell),

and

min⁡F∈Fℓ∣F∣=Ω~(2ℓs),\min_{F\in\mathcal{F}_\ell}|F|=\tilde{\Omega}(2^\ell s),

such that for every AA with ∣A∣=s|A|=s and ∣A+A∣≤K∣A∣|A+A|\leq K|A|, there exists ℓ≤log⁡2K\ell\leq\log_2 K and F∈FℓF\in\mathcal{F}_\ell satisfying A+A⊇FA+A\supseteq F. An optimal dependence on the doubling parameter would provide sharp obstructions for the independence number of sparse random Cayley graphs, up to logarithmic factors. The source gives no resolution of this conjecture.

References

Primary source

Noga Alon and Huy Tuan Pham, “Random Cayley graphs and random sumsets”, arXiv:2509.02561 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.