MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $m,n\geq 2$ are two integers. Is it true that for every sufficiently large nonabelian group $G$, one can find a set $A\subset G$, with $|A|=n$, so that $|A^m| >\binom{n+m-1}{m}$?

(Edit) Let's also add the condition $m\le n$ since the answer below provides a counter-example for large enough $m$. In general it would be interesting to know the range of $(m,n)$ for which the statement holds.(/Edit)

Here $A^k=\lbrace a_1a_2\cdots a_k| a_1,a_2,\dots,a_k\in A\rbrace$ is a product set. It is obvious that in every abelian group one has $|A^m| \le\binom{n+m-1}{m}$, for every $A$.

I don't have an application in mind, I was trying the case $m=2$ and I think I have a proof (still haven't checked all the steps, but it's not particularly enlightening since it splits into many cases). I'm wondering if this is true in general and if there is a slick proof, or if there is a counter-example.

share|cite|improve this question
Dihedral groups look like an interesting special case. – David Cohen Oct 12 '11 at 3:31

The answer is no. Consider the family of groups $G_k:=(\mathbf Z_2{}^k)\rtimes \mathbf Z_2$, where the group on the right acts by interchanging the first and second coordinate. Then the commutator subgroup $G_k'$ is generated by $g_k:=((1,1,0,\ldots, 0),0)$, i.e. is of order two. So $G_k$ is non-abelian (of arbitrarily large order), but as little non-abelian as possible. Note that each element in $G_k$ has order dividing 4.

Now let $A=\lbrace a_1,\ldots, a_n \rbrace \subseteq G_k$. Then any element in $A^m$ can be written as $a_1^{e_1} \cdots a_n^{e_n} g_k^{e_k}$, where $0\leq e_i \leq 3$ for $i=1,\ldots n$ and $e_k=0,1$. This follows by applying the identity $ab=[a,b]ba$ repeatedly. In particular, $|A^m|$ is bounded by a constant depending on $n$ only, not on $m$.

Edit: To be explicit, any two elements in $G_k$ will generate a subgroup of order at most 32, so $(n,m)=(2,31)$ is one counter-example.

share|cite|improve this answer
Ah, what was I thinking. This is a nice example. You've disproved the case $\binom{n+m-1}{m}\geq 2^{2n+1}$. I guess what's left is asking if the statement in the question holds for "small" $m$, for example $m\le n$. – Gjergji Zaimi Oct 12 '11 at 8:44

If I'm not mistaken, the family of groups $\left\{ Q_8 \times (\mathbb{Z}/2\mathbb{Z})^{\times k} \right\}_{k \geq 0}$ is a counterexample to the case $m=n=2$, where $Q_8$ is the quaternion group with 8 elements.

Claim: Any subset $A$ with 2 elements yields $A^2$ with at most 3 elements.

Write two elements as $(g,x)$ and $(h,y)$, with $g,h \in Q_8$ and $x,y \in (\mathbb{Z}/2\mathbb{Z})^{\times k}$. If $g$ and $h$ commute, then $(g,x)(h,y) = (h,y)(g,x)$ and we get at most 3 elements. If $g$ and $h$ don't commute, then $g^2 = h^2$ by the special property of $Q_8$, so $(g,x)^2 = (h,y)^2$ and we get exactly 3 elements.

share|cite|improve this answer
+1. I just found out that the nonabelian groups that satisfy this for $m=n=2$ are exactly $Q_8\times G$ for $G$ an elementary abelian 2-group. – Gjergji Zaimi Oct 13 '11 at 8:16

Here is a collection of what I have so far thanks to the answers by Guntram and S. Carnahan. Let's denote by $P(n,m)$ the property that $|A^m| \le\binom{n+m-1}{m}$ for all subsets $|A|=n$.

We have that the only nonabelian $P(2,2)$ groups are of the form $Q_8\times G$ where $G$ is an elementary abelian 2-group, and that $P(3,2)$ groups have to be abelian by Freiman's paper "On two- and three-element subsets of groups".

In "A characterization of abelian groups", Brailovsky proves that large enough $P(n,2)$ are abelian by showing that $P(n,2)\implies P(n',2)$ for all $n\geq n'\geq 2$, so that the result follows from the previous paragraph.

In "Small squaring and cubing properties for finite groups", Berkovich, Freiman and Praeger prove that the only nonabelian group with $P(2,3)$ is $S_3$.

On the other hand there are nonabelian groups with $P(n,m)$ whenever $\binom{n+m-1}{m}\geq 2^{2n+1}$ as in Guntram's answer.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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