Random Cayley sum hypergraphs and $k$-fold sumsets

Abstract

We denote by $f_k(\Gamma)$ the largest integer with the property that every subset of a finite abelian group $\Gamma$ of size at least $|\Gamma| - f_k(\Gamma)$ is a $k$-fold sumset. Extending a recent result of Alon and Pham, we prove that $$ f_k(\Gamma) \leq \widetilde{O} \left(n^{(2k-1)/(4k-3)}\right) $$ holds for all finite abelian groups $\Gamma$ and integers $k \geq 2$, where $n = |\Gamma|$. Additionally, we also show that the lower bound $f_k(\Gamma) \geq \widetilde{\Omega} \left(n^{1/k}\right)$ holds if $\Gamma$ has no nontrivial element of order dividing $k$. Our upper bound improves a previous result of Balogh, Liu, and Sharifzadeh, and recovers the bound of Alon and Pham in the case $k = 2$. The proof relies on a new upper bound for the independence number of random Cayley sum hypergraphs, which may be of independent interest.