When Do Restricted Sumsets Cover a Finite Abelian Group?

Abstract

For a subset $A$ of a finite abelian group $G$, let $\Sigma_k(A)$ denote the set of sums of $k$ distinct elements of $A$, and let $\Sigma(A)=\bigcup_{k\ge1}\Sigma_k(A)$. The problem of determining when $\Sigma(A)=G$ goes back to Erd\H{o}s and Heilbronn. Nguyen and Vu later formulated the corresponding fixed-length question: for a prescribed $k$, when does $\Sigma_k(A)=G$? For groups of odd order, we prove the sharp large-order threshold $|A|>|G|/3+1$, which forces $\Sigma_k(A)=G$ throughout the entire middle range $4\le k\le |A|-4$. This determines the limiting thresholds posed by Girard, Griffiths and Hamidoune. If $p$ is the least prime divisor of $|G|$, then, for fixed odd $p$ and sufficiently large $|G|$, the exact threshold $|A|\ge |G|/p+p-1$ forces covering throughout the middle range beginning at $2p-2$. Thus, throughout this range, prescribing the number of summands does not change the sharp covering threshold. For $3\le k\le2p-3$, the restricted and ordinary $k$-fold covering problems have the same asymptotic threshold. As an application to MDS elliptic codes on an elliptic curve $E/\F_q$, we sharpen the half-scale conjecture of Li, Wan and Zhang, obtaining the sharp $1/3$-scale bound when $|E(\F_q)|$ is odd and, more generally, the exact bound determined by the least prime divisor of $|E(\F_q)|$.