Let $V$ be a finite dimensional vector space over a finite field $\mathbb{F}_q$ (the most interesting case to me is $q=O(1)$). Let $A$ be an arbitrary subset of $V$ that spans $V$ over $\mathbb{F}_q$. Let $\mu=|A|/|V|$ be the density of $A$. What can we say about the smallest $k$ such that every $v\in V$ can be written as a linear combination of $t\leq k$ elements $a_1,\dots, a_t\in A$ $$ v=\sum_{i=1}^t c_i a_i $$ with coefficients $c_i\in\mathbb{F}_q$?

I can prove $k\leq (1/\mu)^c$ for some constant $c>0$, basically by repeating applying the fact that $|A-A|\geq (3/2)|A|$ if $A$ is not a subgroup of $V$. This fact follows from an argument of Laba, and is stated as Lemma 2.5 in the following survey by Lovett: http://cseweb.ucsd.edu/~slovett/files/addcomb-survey.pdf

Is there a better upper bound? And any lower bounds known?


A related problem was studied in the papers by Ben Klopsch and myself How long does it take to generate a group? and Generating abelian groups by addition only. Describing precisely the connections with your question within the framework of an MO post would be tricky, but, for instance, Theorem 2.9 from the latter paper implies readily that every vector from $V$ can be written as $a_1+\dotsb+a_k$ with $k\le(2/\mu)-1$ and $a_1,\dotsc,a_k\in A$, with some easily classified exceptions.

And, BTW, the estimate $|A-A|\ge(3/2)|A|$ goes back to the early 50th of the previous century; it can be found in the papers of Freiman, Kneser, Kemperman, Mann, Olson, Scherk, ...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.