## Can nonabelian groups be detected “locally”?

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.

-
Dihedral groups look like an interesting special case. – David Cohen Oct 12 2011 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.

-
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 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.

-
+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. springerlink.com/content/3040n1420586v676 – Gjergji Zaimi Oct 13 2011 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.

-