5
$\begingroup$

Let $\Omega_n \subseteq \mathrm{Sym}(n)^4$ be the set of all $4$-tuples $(\sigma_1,\sigma_2,\tau_1,\tau_2)$ of permutations of $\{1,\ldots,n\}$ such that $\sigma_j \tau_k = \tau_k \sigma_j$ for each pair $(j,k) \in \{1,2\}^2$.

Any four permutations determine a $8$-regular edge-labeled directed graph on $\{1,\ldots,n\}$. (Of course, the graph might not be simple.) I am interested in understanding the local structure of this graph when the four permutations are chosen uniformly at random from $\Omega_n$. In particular, I would like to know whether the commutativity constraint enforces any other kind of constraint on the structure of the graph, in the sense that a significant number of short cycles other than commutators need to occur.

A more precise formulation of the problem is as follows. Let $\mathbb{F}_r$ be the free group on $r$ generators and let $G = \mathbb{F}_2 \times \mathbb{F}_2$. Fixing an indexation for the generators of $G$, each element of $\Omega_n$ determines a unique homomorphism from $G$ to $\mathrm{Sym}(n)$. We identify a uniform random element of $\Omega_n$ with the associated random homomorphism, to be denoted $\phi$. Consider the following questions.

(1) Is it the case that for every nontrivial element $g \in G$ and every $\epsilon > 0$ the probability that $\frac{1}{n}|\mathrm{Fix}(\phi(g))| \leq \epsilon$ tends to $1$ as $n \to \infty$? I emphasize that $g$ and $\epsilon$ are fixed before the limit.

(2) Is it the case that for every nontrivial element $g \in G$ the expectation of the random variable $\frac{1}{n}|\mathrm{Fix}(\phi(g))|$ tends to $0$ as $n \to \infty$?

Clearly a positive answer to Question (1) implies a positive answer to Question (2). A positive answer to Question (1) is exactly the assertion that the uniform measures on $\Omega_n$ form a random sofic approximation to $G$. Intuitively, this would mean that a uniform random element of $\Omega_n$ has no 'unnecessary' structure.

Note that residual finiteness of $G$ implies that there exists a sequence $(\phi_n:G \to \mathrm{Sym}(n))_{n=1}^\infty$ of homomorphisms such that for each $g \in G$ the set $\mathrm{Fix}(\phi_n(g))$ is empty for sufficiently large $n$.

A final (vague) question is whether this model can be generated in any way other than its definition. The model given by a uniformly chosen $4$-tuple of permutations with no additional constraints is contiguous with a uniform random $8$-regular graph, and there are multiple ways of generating this. In this case the elementary theory shows that the analog of Question (1) with $G$ replaced by $\mathbb{F}_4$ has a positive answer.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ First of all, thanks a lot for your response - I was unaware of Dixon's theorem and it provides an interesting insight into the construction. However, it's not immediately clear to me why the theorem implies that $\phi$ is likely to be trivial on one of the factors. You seem to be assuming that the marginal of $\phi$ on $(\sigma_1,\sigma_2)$ is a uniform random pair of permutations. Why should this be the case? $\endgroup$ – burtonpeterj Oct 27 '18 at 23:25
  • $\begingroup$ In particular, the cardinality of the set of homomorphisms which are trivial on one factor is $2(n!)^2$. The situation you describe would mean that this is approximately the cardinality of $\Omega_n$. A priori it seems possible that the $\sigma$ marginal could concentrate on a set of size $o((n!)^2)$, so that this random pair does not behave like a uniform random pair. $\endgroup$ – burtonpeterj Oct 27 '18 at 23:29
  • $\begingroup$ For example, if the $\sigma$ marginal and $\tau$ marginals each concentrate on a set of size $(n!)^{3/2}$ then it's possible for $\Omega_n$ to have size as large as $(n!)^3$ which would mean that the homomorphisms trivial on one factor are unlikely. $\endgroup$ – burtonpeterj Oct 27 '18 at 23:29
  • $\begingroup$ the argument should also use the fact that the number of imprimitive actions of $\mathbb F_2$ with a given block decomposition is much smaller that that of primitive actions, which is part of Dixon's proof--so when you enumerate actions you see that the primitive ones are preponderent (and as a side consequence the marginal is asymptotically uniform). I probably won't have time to edit to add the detail to the answer today. $\endgroup$ – Jean Raimbault Oct 28 '18 at 6:44
  • $\begingroup$ I don't see how it's possible for most homomorphisms to be trivial on one factor. For example, consider defining $(\sigma_1,\sigma_2)$ by picking uniform random permutations of $\{1,\ldots,\frac{n}{2}\}$ and having them fix $\{\frac{n}{2}+1,\ldots,n\}$. (We may assume $n$ is even.) Similarly, let $(\tau_1,\tau_2)$ be uniform on $\{\frac{n}{2}+1,\ldots,n\}$ and fix $\{1,\ldots,\frac{n}{2}\}$. This generates $(\frac{n}{2}!)^4$ elements of $\Omega_n$, which is already much larger than the $(n!)^2$ elements which are trivial on one factor. $\endgroup$ – burtonpeterj Oct 29 '18 at 0:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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