24
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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)$? $\endgroup$
    – ARupinski
    Commented Feb 9, 2011 at 17:47
  • $\begingroup$ $S$ depends on $\epsilon$ and $G$, so $|S|\gg 1/\epsilon$. $\endgroup$
    – user6976
    Commented Feb 9, 2011 at 17:59
  • 2
    $\begingroup$ 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$). $\endgroup$
    – user6976
    Commented Feb 9, 2011 at 18:04
  • $\begingroup$ To generate $G$ seems to be too much. I asked a modified form of this question as mathoverflow.net/questions/54921/… $\endgroup$
    – Andreas Thom
    Commented Feb 9, 2011 at 20:01
  • $\begingroup$ @Andreas: You are correct, one need to generate up to finite index. $\endgroup$
    – user6976
    Commented Feb 9, 2011 at 20:35

2 Answers 2

Reset to default
33
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 \}$. $\endgroup$
    – Nick S
    Commented Feb 9, 2011 at 19:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin Buzzard
    Commented Feb 9, 2011 at 20:17
  • $\begingroup$ Good! I guess, the question mathoverflow.net/questions/54921/… by Andreas Thom is what I really had to ask. $\endgroup$
    – user6976
    Commented Feb 9, 2011 at 20:37
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good. Then one can view this question as a motivation for your question. $\endgroup$
    – user6976
    Commented Feb 10, 2011 at 1:36

You must log in to answer this question.