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.

  • 1
    $\begingroup$ Dihedral groups look like an interesting special case. $\endgroup$ Oct 12, 2011 at 3:31

3 Answers 3


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.

  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 12, 2011 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.


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.


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.