Skip to main content
added actual argument
Source Link
Jean Raimbault
  • 3.4k
  • 16
  • 27

This is not the case, in fact in both cases the limit is 1/2. This is because with probability going to 1 as $n \to +\infty$ a uniformly random morphism $\mathbb F_2 \times \mathbb F_2 \to \mathrm{Sym}(n)$ is trivial on one of the factors. The latter claim follows from Dixon's theorem that a random pair of independently chosen permutations almost surely generates a primitive group, in fact the full alternating or symmetric group so it has a trivial commutant, so for large $n$ a typical representation of $\mathbb F_2 \times F_2$ to $\mathrm{Sym}(n)$ has one factor acting with primitive image and the other trivially.

In terms of graphs this means that the graphs you defined converge to the mean of the Schreier coset graphs of $1 \times \mathbb F_2$ and $\mathbb F_2 \times 1$.

EDIT As noted in the comments the above does not contain an actual proof of its statements. To provide such a proof one needs to look onto Dixon's arguments a bit. The reference for Dixon's paper, which I will use below, is : The Probability of Generating the Symmetric Group, Math. Zeitschrift 110 (1969).

The first claim is that there are at most $(n!)^2(1 + O(C^{-n}))$ representations of $\mathbb F_2\times \mathbb F_2$ such that the first factor acts transitively. To prove this note that if it acts primitively then the image of the second factor has to act trivially. On the other hand even if it acts nonprimitively (but still transitively) its centraliser in $\mathrm{Sym}(n)$ is of cardinality at most $n$ (see eg. Lemma A.2 in https://arxiv.org/pdf/1805.03893.pdf). In the proof of his Lemma 2 Dixon shows that the number of such imprimitive representations is at most $n2^{-n/4}(n!)^2$. So we get in fine that the number of representations of $\mathbb F_2 \times \mathbb F_2$ where $\mathbb F_2 \times 1$ acts transitively is at most equal to
$$ (1 + n^3 2^{-n/4})(n!)^2 $$ which is what we wanted.

The second claim is that the number of representations where $\mathbb F_2 \times \mathbb F_2$ acts transitively, but not $\mathbb F_2 \times 1$ is $O(C^{-n}(n!)^2)$. This is in fact simpler : the number of such representations where the orbits of the first factor are of size $2 \le d \le n/2$ is at most equal to $$ \frac{n!}{(n/d)!(d!)^{n/d}} \cdot (d!)^{2n/d} \cdot \left((n/d)!\right)^2 \cdot d^{n/d} = n!\cdot (d!)^{n/d} \cdot (n/d)! \cdot d^{n/d} $$ and by Stirling's approximation this is $O((n!)^{3/2}C^n)$.

It remains to check that nontransitive representations of $\mathbb F_2 \times \mathbb F_2$ are also rare. I'm going to give a formula which should be estimable by elementary means but leave the estimate for now. Using the two facts proven above we can estimate the number of such representations by: $$ \sum_\pi \frac{n!}{\prod_{1\le i \le n} \pi_i! (i!)^{\pi_i}} \prod_{1\le i\le n} \left(1 + O(C^{-i})\right) (i!)^{2\pi_i} \\= (n!)^2 \sum_\pi \prod_{1\le i \le n}\frac{1 + O(C^{-i})}{\pi_i!} \cdot\frac{\prod_{1\le i\le n} (i!)^{\pi_i}}{n!} $$ where the sum goes over all partitions of $n$ ($\pi = (\pi_1, \ldots, \pi_n$ with $\sum_i i\pi_i = n$) with $\pi_1 = \pi_n = 0$ (these correspond to actions where the first factor acts trivially or transitively). I think in the form on the second line it should be possible to evaluate the sum to prove that it is $o(1)$.

This is not the case, in fact in both cases the limit is 1/2. This is because with probability going to 1 as $n \to +\infty$ a uniformly random morphism $\mathbb F_2 \times \mathbb F_2 \to \mathrm{Sym}(n)$ is trivial on one of the factors. The latter claim follows from Dixon's theorem that a random pair of independently chosen permutations almost surely generates a primitive group, in fact the full alternating or symmetric group so it has a trivial commutant, so for large $n$ a typical representation of $\mathbb F_2 \times F_2$ to $\mathrm{Sym}(n)$ has one factor acting with primitive image and the other trivially.

In terms of graphs this means that the graphs you defined converge to the mean of the Schreier coset graphs of $1 \times \mathbb F_2$ and $\mathbb F_2 \times 1$.

This is not the case, in fact in both cases the limit is 1/2. This is because with probability going to 1 as $n \to +\infty$ a uniformly random morphism $\mathbb F_2 \times \mathbb F_2 \to \mathrm{Sym}(n)$ is trivial on one of the factors. The latter claim follows from Dixon's theorem that a random pair of independently chosen permutations almost surely generates a primitive group, in fact the full alternating or symmetric group so it has a trivial commutant, so for large $n$ a typical representation of $\mathbb F_2 \times F_2$ to $\mathrm{Sym}(n)$ has one factor acting with primitive image and the other trivially.

In terms of graphs this means that the graphs you defined converge to the mean of the Schreier coset graphs of $1 \times \mathbb F_2$ and $\mathbb F_2 \times 1$.

EDIT As noted in the comments the above does not contain an actual proof of its statements. To provide such a proof one needs to look onto Dixon's arguments a bit. The reference for Dixon's paper, which I will use below, is : The Probability of Generating the Symmetric Group, Math. Zeitschrift 110 (1969).

The first claim is that there are at most $(n!)^2(1 + O(C^{-n}))$ representations of $\mathbb F_2\times \mathbb F_2$ such that the first factor acts transitively. To prove this note that if it acts primitively then the image of the second factor has to act trivially. On the other hand even if it acts nonprimitively (but still transitively) its centraliser in $\mathrm{Sym}(n)$ is of cardinality at most $n$ (see eg. Lemma A.2 in https://arxiv.org/pdf/1805.03893.pdf). In the proof of his Lemma 2 Dixon shows that the number of such imprimitive representations is at most $n2^{-n/4}(n!)^2$. So we get in fine that the number of representations of $\mathbb F_2 \times \mathbb F_2$ where $\mathbb F_2 \times 1$ acts transitively is at most equal to
$$ (1 + n^3 2^{-n/4})(n!)^2 $$ which is what we wanted.

The second claim is that the number of representations where $\mathbb F_2 \times \mathbb F_2$ acts transitively, but not $\mathbb F_2 \times 1$ is $O(C^{-n}(n!)^2)$. This is in fact simpler : the number of such representations where the orbits of the first factor are of size $2 \le d \le n/2$ is at most equal to $$ \frac{n!}{(n/d)!(d!)^{n/d}} \cdot (d!)^{2n/d} \cdot \left((n/d)!\right)^2 \cdot d^{n/d} = n!\cdot (d!)^{n/d} \cdot (n/d)! \cdot d^{n/d} $$ and by Stirling's approximation this is $O((n!)^{3/2}C^n)$.

It remains to check that nontransitive representations of $\mathbb F_2 \times \mathbb F_2$ are also rare. I'm going to give a formula which should be estimable by elementary means but leave the estimate for now. Using the two facts proven above we can estimate the number of such representations by: $$ \sum_\pi \frac{n!}{\prod_{1\le i \le n} \pi_i! (i!)^{\pi_i}} \prod_{1\le i\le n} \left(1 + O(C^{-i})\right) (i!)^{2\pi_i} \\= (n!)^2 \sum_\pi \prod_{1\le i \le n}\frac{1 + O(C^{-i})}{\pi_i!} \cdot\frac{\prod_{1\le i\le n} (i!)^{\pi_i}}{n!} $$ where the sum goes over all partitions of $n$ ($\pi = (\pi_1, \ldots, \pi_n$ with $\sum_i i\pi_i = n$) with $\pi_1 = \pi_n = 0$ (these correspond to actions where the first factor acts trivially or transitively). I think in the form on the second line it should be possible to evaluate the sum to prove that it is $o(1)$.

Source Link
Jean Raimbault
  • 3.4k
  • 16
  • 27

This is not the case, in fact in both cases the limit is 1/2. This is because with probability going to 1 as $n \to +\infty$ a uniformly random morphism $\mathbb F_2 \times \mathbb F_2 \to \mathrm{Sym}(n)$ is trivial on one of the factors. The latter claim follows from Dixon's theorem that a random pair of independently chosen permutations almost surely generates a primitive group, in fact the full alternating or symmetric group so it has a trivial commutant, so for large $n$ a typical representation of $\mathbb F_2 \times F_2$ to $\mathrm{Sym}(n)$ has one factor acting with primitive image and the other trivially.

In terms of graphs this means that the graphs you defined converge to the mean of the Schreier coset graphs of $1 \times \mathbb F_2$ and $\mathbb F_2 \times 1$.