# Generation of finite index subgroups

Related to a question by Mark Sapir (see here) and a question by Kate Juschenko (see here), let me ask the following:

Question: Let $G$ be a finitely generated group and let $\varepsilon>0$. Is there a finite subset $S$ such every subgroup $H \subset G$ with $|H \cap S| \geq \varepsilon \cdot |S|$ is of finite index?

This would answer Kate's question and be in the spirit of Mark's suggestion.

EDIT: Bill Thurston's argument below gives for each $\varepsilon>0$ the existence of a compactly supported function $f_{\varepsilon} \colon G \to [0,1]$ with $\sum_{g \in G} f_{\varepsilon}(g)=1$ such that the following holds:

If $\sum_{h \in H} f_{\varepsilon}(h) \geq \varepsilon$ for some subgroup $H$, then $H$ is of finite index.

The remaining question is, whether $f_{\varepsilon}$ can be taken to be $|S|^{-1} \chi_S$ for some finite subset of $G$.

(Edited to add more detail about random walks on infinite graphs) Let $G$ be a group with generators $g_1, \dots, g_n$, and let $\epsilon > 0$ be given. Let $K$ be a cell complex with $n$ edges corresponding to the generators with fundamental group $G$ (this can be obtained by sewing on 2-disks for each of a possibly infinite set of relators).

We can visualize a subgroup $H$ in terms of the covering space $K_H$ of $K$ having fundamental group $H$. If $H$ has infinite index, then this covering space is infinite. Consider a random walks on the vertices of $K_H$ (that is, the coset space $G/H$) where at each time, there is equal probability of staying fixed or going to one of the $2n$ neighbors. The probability of being on any particular vertex at time $t$ evolves by a discrete form of the Laplacian: it is a convex combination of the probability of being at the $2n+1$ elements in the neighborhood of radius 1 (the graph might have loops or multiple edges between vertices, so it is a weighted avereage).

Claim: the sequence of probability distributions obtained by random walks of length $k$ on the 1-skeleton of $K_H$ tends toward $0$ at every node of the graph. Note that for subgroups of finite index, this is process is a positive linear transformation of a finite-dimensional vector space, some power of it is strictly positive, so it converges to the unique positive eigenvector of the Perron-Frobenius theorem: the uniform distribution. One way to understand the situation for an infinite graph is to consider the list of probabilities arranged in decreasing order. The maximum value always decreases, unless all its neighbors have the same value. Therefore, the sequence of maximum values converges. The rate of decrease is at least as great as the difference of the maximum from the next highest value, so for the maximum to converge, it is necessary that the next highest value converge to the same value. Similarly, the sum of the first two values decreases at least in proportion to the difference of the minimum from the third highest value (since at least one of the two points with the two highest values has a neighbor with value not greater than the third highest value). In general, the cumulative sum of the first $n$ highest values always decreases, and at a rate at least as great as the step to the $n+1$st highest values. It follows that all probabilities converge pointwise to a constant function. For an infinite graph, this implies they all converge to 0.

This argument is uniform over all subgroups of infinite index $H$. Therefore, for any $\epsilon$, after some time $T(\epsilon)$, the random walk will have probability less than $\epsilon$ of being at the base point of $K_H$. In other words, the probability distribution of the random walk in $G$ has sum over $H$ less than $\epsilon$. To summarize, for some time $T(n, \epsilon)$ depending only on $\epsilon$ and the number $n$ of generators for $G$, for any subgroup $H$ of infinite index (or even index less than say $2/\epsilon$) the time $T(n,\epsilon)$ probability of the random walk being in $H$ is less than $\epsilon$.

I think this already answers the question in spirit: instead of a test set, this gives a test function of compact support. I believe an extension of this argument should answer the problem as posed, but at the moment I don't have the free energy to try to work out the details.

• Thanks for your answer. Looking at the random walk on $G/H$ is certainly a very good idea. However, it seems not so clear to me that you pass from the $n$-sphere to the $n+1$-sphere with a probability which is bounded below. Even though there is always one point in the $n+1$-sphere, the random walk could have a lot of dead ends where going further in any direction does not increase the distance to the origin. – Andreas Thom Feb 10 '11 at 12:38
• @Andreas Thom: The dead ends only affect how fast random paths tend toward infinity, they don't stop them from escaping. To aid with intuition, note that on any finite graph, the random walk, allowing some probability of staying fixed to prevent oscillatory behavior, always converges toward the uniform distribution, so if there are more than $1/\epsilon$ nodes, eventually the probability of being at 1 is less than $\epsilon$. Infinite graphs can't do better. – Bill Thurston Feb 10 '11 at 14:23
• Thanks a lot. Arranging the probabilities in decreasing order makes it totally clear that the argument is uniform over all subgroups $H$. This was, what I did not see. – Andreas Thom Feb 11 '11 at 7:02
• Can you say some more about how to calculate $T(n,\epsilon)$ - perhaps give an explicit upper bound? It is not obvious to me that a uniform bound exists. – Will Sawin Mar 14 '12 at 2:17
• Will, I asked this as a separate question, see mathoverflow.net/questions/91188/… – Andreas Thom Mar 28 '12 at 7:07