# A non-trivial property of all groups

This question appeared in my answer to this question, but it seems to be interesting in itself. Let $G$ be an infinite finitely generated group, $\epsilon\gt 0$. Is there a finite subset $S\subset G$ such that every subset of $S$ with at least $\epsilon|S|$ elements generates $G$? If the answer is "yes", it should have a trivial proof by Gromov's thesis (every property of all finitely generated groups is either false or trivial).

Update. In view of Stephen's answer and Kevin's comment below, perhaps a more correct question is this:

• Is it true that if we represent an infinite group $G$ as a union of a finite number of subsets, then one of these subsets generates a finite index subgroup of $G$?

• Just to clarify that I am reading this correctly, we are fixing $G$ and $\epsilon$ and trying to determine if such an $S$ exists for the pair $(G,\epsilon)$? – ARupinski Feb 9 '11 at 17:47
• $S$ depends on $\epsilon$ and $G$, so $|S|\gg 1/\epsilon$. – Mark Sapir Feb 9 '11 at 17:59
• Example: if $G$ is the additive group of integers, then $S$ may consist of the first $2/\epsilon$ prime numbers (since every two primes generate $G$). – Mark Sapir Feb 9 '11 at 18:04
• To generate $G$ seems to be too much. I asked a modified form of this question as mathoverflow.net/questions/54921/… – Andreas Thom Feb 9 '11 at 20:01
• @Andreas: You are correct, one need to generate up to finite index. – Mark Sapir Feb 9 '11 at 20:35

This is false for the infinite dihedral group $\langle a,b\mid b^2=1, ba=a^{-1}b\rangle$. No set $S$ works for $\epsilon\le1/3$, because there is always a subset with $\lceil{\epsilon|S|}\rceil$ elements that lies entirely in $\{a^n\mid n\in\mathbb{Z}\}$, $\{a^{2n}b\mid n\in\mathbb{Z}\}$ or $\{a^{2n+1}b\mid n\in\mathbb{Z}\}$, and none of these three sets generates the whole group.

• I think that the same idea works for $Z \times Z_n$ and $\epsilon < \frac{1}{n}$. Any set $S$ will have a subset with $\epsilon |S|$ elements which lies entirely in some $\Z \times {k}$. Then if $k=0$ clearly the set cannot generate, while if $k \neq 0$, the set cannot generate elements of the form $(Z \backslash \frac{n}{gcd (n,k)} Z )\times \{ 0 \}$. – Nick S Feb 9 '11 at 19:43
• Perhaps what is really going on is that if you allow $G$ to be finite, but let $S$ be a multi-set, then the criterion fails for $G=(Z/2Z)^2$ and $\epsilon=1/4$ say, because at least $1/4$ of the elements in $S$ will just be one element of $G$, and $G$ is not generated by one element. Now $G$ is finite so this isn't allowed---but now replace $(Z/2Z)^2$ with any infinite finitely-generated group which admits a surjection onto $(Z/2Z)^2$ and now you have a real counterexample via the same argument. – Kevin Buzzard Feb 9 '11 at 20:17
• Good! I guess, the question mathoverflow.net/questions/54921/… by Andreas Thom is what I really had to ask. – Mark Sapir Feb 9 '11 at 20:37

This concerns the updated question. The answer is yes.

If $G$ is represented as the union of a finite number of subsets $A_1, \dots,A_n$, then one of the subsets generates a finite index subgroup of $G$. Indeed, let $G_i$ be the subgroup which is generated by $A_i$. Then, $G$ is the union of the $G_i$.

B.H. Neumann proved that if $G$ is the union of a finite number of left cosets of subgroups, then one of the subgroups is of finite index (see this post). In particular, there exists some $i$ such that $G_i$ is of finite index.

• Good. Then one can view this question as a motivation for your question. – Mark Sapir Feb 10 '11 at 1:36