Related to a question by Mark Sapir (see [here](https://mathoverflow.net/questions/54907/a-non-trivial-property-of-all-groups)) and a question by Kate Juschenko (see [here](https://mathoverflow.net/questions/54838/amenability-of-groups-ii)), 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$.



Generation of finite index subgroups
(**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.


