# Are finitely generated amenable groups positively finitely generated?

Let $G$ be a finitely generated amenable group.

Is there a positive integer $n$ such that $n$ random elements of $G$ generate it with positive probability?

Being more formal, note that $G^n$ is amenable, so it carries a translation invariant finitely additive probability measure $\mu$. I am asking whether there is a positive integer $n$ such that:

$$\mu (\{(g_1, \dots, g_n) \in G^n \ : \ \langle g_1, \dots g_n \rangle = G\}) > 0$$

Alternatively, we can take a Folner sequence $\{F_k\}_{k \in \mathbb{N}}$ in $G^n$ and ask whether

$$\liminf_{k \to \infty} \frac{|\{ \text{Generating n-tuples} \}\cap F_k|}{|F_k|} > 0$$

• Already for the group $G=\mathbb Z$, the answer is not clear to me. Also: are you asking $\exists n\in\mathbb N$ s.t. $\forall$ invariant measures on $G^n$ the measure of generating $n$-tuples is positive? Or are you asking $\exists n\in\mathbb N$, $\exists$ and invariant measure on $G^n$ s.t. the measure of generating $n$-tuples is positive? – André Henriques Feb 26 '16 at 9:46
• Stupid question: what is a finitely additive translation invariant measure on $\mathbb{Z}?$ – Igor Rivin Feb 26 '16 at 11:48
• @IgorRivin your question is very good. To construct such a measure you need the axiom of choice: Pick a nonprincipal ultrafilter on the integers, and to measure some subset, just take the ultralimit of the density of this subset in $[-n,n]$. In the question, I just want the liminf to be positive, so we can confine ourselves to Folner sequences, avoiding the construction of a measure. – Pablo Feb 26 '16 at 12:21
• So, for the original question, I assume the answer for $\mathbb{Z}$ is $n=2,$ independently of the measure? – Igor Rivin Feb 26 '16 at 13:34
• I would expect this to be wrong for $(\mathbb Z/2\mathbb Z) \wr \mathbb Z$. It seems to me that for any fixed $n$, $n$ random elements are unlikely to generate the group -- basically, since it is hard to generate $\oplus_{\mathbb Z} \mathbb Z/2\mathbb Z$ by $n$ random elements and their translations. – Andreas Thom Feb 26 '16 at 21:56

The answer is already no for $\mathbb{Z}$, assuming the question is whether this holds for every meaure. Let $n\in\mathbb{N}$, and let $$S \,=\, \{(a_1,\ldots,a_n)\in\mathbb{Z}^n \mid \gcd(a_1,\ldots,a_n)=1\}.$$ I will demonstrate a Følner sequence in $\mathbb{Z}^n$ that does not intersect $S$, which leads to a translation-invariant, finitely additive probability measure $\mu$ on $\mathbb{Z}^n$ for which $\mu(S) = 0$.

The idea is that there are large cubes in $\mathbb{Z}^n$ that do not intersect $S$. Specifically, define a $\boldsymbol{k}$-cube in $\mathbb{Z}^n$ to be any product of the form $$A_1 \times \cdots \times A_n$$ where each $A_i$ is a set of $k$ consecutive integers. I claim that for each $k\in\mathbb{N}$ there exists a $k$-cube $C_k$ in $\mathbb{Z}^n$ so that $C_k\cap S = \emptyset$. Then $\{C_k\}$ is a Følner sequence in $\mathbb{Z}^n$, and $$\liminf_{k\to\infty} \frac{|C_k\cap S|}{|C_k|} \,=\, 0.$$

To prove that the $k$-cubes $C_k$ exist, let $k\in\mathbb{N}$, let $\mathcal{I} = \{1,\ldots,k\}^n$, and choose a family $$\{p_{(i_1,\ldots,i_n)}\}_{(i_1,\ldots,i_n)\in\mathcal{I}}$$ of $k^n$ distinct primes. By the Chinese remainder theorem, there exists a tuple $(c_1,\ldots,c_n)$ of integers so that $$c_j \equiv -i_j\pmod{p_{(i_1,\ldots,i_n)}}$$ for each $(i_1,\ldots,i_n) \in\mathcal{I}$ and each $j\in\{1,\ldots,n\}$. Then $$C_k \,=\, (c_1,\ldots,c_n) + \mathcal{I}$$ is a $k$-cube in $\mathbb{Z}^n$ that does not intersect $S$, since $$p_{(i_1,\ldots,i_n)}\;\bigl|\; \gcd(c_1+i_1,\ldots,c_n+i_n)$$ for each $(i_1,\ldots,i_n) \in \mathcal{I}$.

Edit: This technique can also be used to show that there exists a Følner sequence $\{F_k\}$ in $\mathbb{Z}$ itself so that for all $n\in\mathbb{N}$ $$\liminf_{k\to\infty} \frac{|\{\text{generating n-tuples}\}\cap F_k^n|}{|F_k^n|} = 0.$$ Specifically, we can let each $F_k$ be a disjoint union $$F_k \,=\, A_{k,1} \uplus A_{k,2} \uplus \cdots \uplus A_{k,k}$$ where each $A_{j,k}$ is a set of $k$ consecutive integers, and these sets are chosen to have the property that $\gcd(a_1,\ldots,a_k)\ne 1$ for all $(a_1,\ldots,a_k)\in A_{k,1}\times\cdots\times A_{k,k}$. If we fix $n$, then the probability that a randomly chosen element of $F_k^n$ has two coordinates from the same $A_{j,k}$ goes to $0$ as $k\to\infty$, and thus a randomly chosen element of $F_k^n$ has a high probability of not generating $\mathbb{Z}^n$.

An anti-answer: for many non-amenable groups (higher rank lattices), with reasonable definition of a measure, the answer is that the probability approaches $0$ for any $n.$ (a random subgroup will be free, by the results of R. Aoun, hence of infinite index). The OP probably knows this, but it is an amusing counterpoint.

EDIT Reasonable measure: take a subgroup generated by $n$ random products of generators, of length $N.$ Then, as $N \rightarrow \infty,$ the subgroup is free with probability exponentially close to $1$ (as a function of $N.$). Another reasonable measure (this is due to E. Fuchs and I. Rivin, see on arXiv.org): pick the $n$ elements uniformly at random from the matrices in $SL(n, \mathbb{Z})$ with your favorite norm (e.g., the frobenius norm) bounded by $N.$ (same result, though now polynomial dependence on $N$).

• Actually I do not know this, and this is indeed very interesting. Could you please explain what is meant by a 'reasonable measure', or by 'approaches zero'? – Pablo Feb 26 '16 at 13:55
• @Pablo see edit... – Igor Rivin Feb 26 '16 at 14:00