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

  • 1
    $\begingroup$ 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? $\endgroup$ – André Henriques Feb 26 '16 at 9:46
  • 2
    $\begingroup$ Stupid question: what is a finitely additive translation invariant measure on $\mathbb{Z}?$ $\endgroup$ – Igor Rivin Feb 26 '16 at 11:48
  • 2
    $\begingroup$ @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. $\endgroup$ – Pablo Feb 26 '16 at 12:21
  • 1
    $\begingroup$ So, for the original question, I assume the answer for $\mathbb{Z}$ is $n=2,$ independently of the measure? $\endgroup$ – Igor Rivin Feb 26 '16 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$).

  • $\begingroup$ 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'? $\endgroup$ – Pablo Feb 26 '16 at 13:55
  • $\begingroup$ @Pablo see edit... $\endgroup$ – Igor Rivin Feb 26 '16 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.