Additive Bases in Abelian Groups

Abstract

Let $G$ be a finite, non-trivial abelian group of exponent $m$, and suppose that $B_1,...,B_k$ are generating subsets of $G$. We prove that if $k>2m\ln {\log }_2|G|$, then the multiset union $B_1\cup ...\cup B_k$ forms an additive basis of $G$; that is, for every $g\in G$ there exist $A_1\subset B_1,...,A_k\subset B_k$ such that $g={\sum }_{i=1}^k{\sum }_{a\in A_i}a$. This generalizes a result of Alon, Linial, and Meshulam on the additive bases conjecture. As another step towards proving the conjecture, in the case where $B_1,...,B_k$ are finite subsets of a vector space we obtain lower-bound estimates for the number of distinct values, attained by the sums of the form ${\sum }_{i=1}^k{\sum }_{a\in A_i}a$, where $A_i$ vary over all subsets of $B_i$ for each $i=1,>...,k$. Finally, we establish a surprising relation between the additive bases conjecture and the problem of covering the vertices of a unit cube by translates of a lattice, and present a reformulation of (the strong form of) the conjecture in terms of coverings.