Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

Compare with Adreas Thom's question.

share|improve this question
    
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
2  
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
show 2 more comments

2 Answers

up vote 33 down vote accepted

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.

share|improve this answer
    
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
1  
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
add comment

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.

share|improve this answer
    
Good. Then one can view this question as a motivation for your question. –  Mark Sapir Feb 10 '11 at 1:36
add comment

Your Answer

 
discard

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.