Optimal covering conjecture for small-doubling sumsets

Let AA be a set of size ss with doubling constant bounded by KK, meaning A+AKA|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

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

and

minFFF=Ω~(2s),\min_{F\in\mathcal{F}_\ell}|F|=\tilde{\Omega}(2^\ell s),

such that for every AA with A=s|A|=s and A+AKA|A+A|\leq K|A|, there exists log2K\ell\leq\log_2 K and FFF\in\mathcal{F}_\ell satisfying A+AFA+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.

Sources & referencesView supporting material

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.