10
$\begingroup$

As is well-known (see, for example, a nice exposition by our own Qiaochu: https://qchu.wordpress.com/2012/11/07/fixed-points-of-random-permutations/) that the distribution of the number of fixed points of random permutations (so, uniformly chosen elements of $S_n$) is Poisson, for largish $n.$ The question is: what is known for proper subgroups of $S_n?$

$\endgroup$
16
  • 4
    $\begingroup$ What sort of answer are you looking for? Then mean and variance are easy to calculate, of course, but even sticking to transitive subgroups, at one extreme, you have the regular representation of a group of order $n$. $\endgroup$ Sep 20, 2015 at 12:53
  • $\begingroup$ The question is: what kind of distributions do you get? There is obviously the trivial case of an $n$-cycle (limiting distribution is the delta function), but maybe the limiting distribution is always Poisson? Or maybe there often is NOT a limiting distribution? (clearly, we are talking about families of groups here) $\endgroup$
    – Igor Rivin
    Sep 20, 2015 at 13:16
  • 3
    $\begingroup$ The OP's question is a mathematically well-defined question: what distributional limits can one get for the numbers of fixed points in a sequence $G_n$ of groups where each $G_n$ is a subgroup of $S_n$? So I don't understand the claim that the question is too broad. $\endgroup$
    – Dan Romik
    Sep 20, 2015 at 19:29
  • 3
    $\begingroup$ @DanRomik I didn't vote on the question, but I didn't see reference to a sequence of subgroups $G_n$ of $S_n$. The appearance of broadness may be due to the fact that any finite group is a proper subgroup of some $S_n$. $\endgroup$
    – Todd Trimble
    Sep 20, 2015 at 19:48
  • 4
    $\begingroup$ Regarding the sequence of subgroups $G_n$ formulation of the question, the problem arises that in most such sequences the $G_n$ need not have anything to do with each other. To fix that I suggest the following extra condition: the image of $G_n \times G_m$ in $S_{n+m}$ (via the standard embedding $S_n \times S_m \to S_{n+m}$) should lie in $G_{n+m}$. (That is, the $G_n$ should form a monoidal subcategory of the monoidal category of finite sets and bijections.) For example, the alternating groups $A_n$ have this property. $\endgroup$ Sep 20, 2015 at 22:49

5 Answers 5

12
$\begingroup$

The Boston-Shalev Conjecture asserts that there is a constant $\delta$ such that for any transitive simple group $G$, the proportion of derangments in $G$ is at most $\delta$. After a long sequence of papers this has recently been proved by Guralnick and Fulman.

It is known that this conjecture does not extend to transitive actions of almost simple groups. Moreover, Boston et. al. proved that if $\delta(G)$ is the proportion of derangements in $G$ then the set $\{ \delta(G)\mid G \textrm{ a finite primitive group}\}$ is dense in $(0,1)$.

$\endgroup$
0
9
$\begingroup$

Primitive actions of $S_n$ other than the natural one were examined by Diaconis, Fulman and Guralnick in ``On fixed points of permutations." J. Algebraic Combin. 28 (2008), no. 1, 189–218. The interesting case is the embedding in $S_{{n} \choose {k}}$ by action on $k$-sets (with $k$ fixed and $n$ growing). The authors show that the limiting distribution is a polynomial in some independent Poisson distributions.

$\endgroup$
8
$\begingroup$

I generally agree with Geoff that the question is too broad, and that you should tell us what types of families of subgroups you are most interested in.

I don't know of any proven results in this direction, but in case it is of any use in formulating conjectures, here are a few Sunday afternoon experimental results (done in Magma) on maximal subgroups of $S_n$ for $n$ about $10000$. For each example I took a sample of $10000$ random elements. For $S_{10000}$ itself, I got

{* 0^^3649, 1^^3681, 2^^1845, 3^^642, 4^^147, 5^^29, 6^^5, 7^^2 *}

For almost all examples I was finding that there were more fixed-point-free elements than in the symmetric group. The intransitive maximals are of the form $S_m \times S_n$ of degree $m+n$. I expect you could calculate the distributions theoretically. For $S_{5000} \times S_{5000}$, I got

{* 0^^1352, 1^^2654, 2^^2753, 3^^1816, 4^^902, 5^^363, 6^^121, 7^^29, 8^^9, 9 *}

and it was similar for $S_{50} \times S_{9950}$.

For transitive maximals, the large imprimitive groups have the form $S_n \wr S_m$ of degree $mn$. For $S_{100} \wr S_{100}$ I got

{* 0^^5301, 1^^2000, 2^^1293, 3^^733, 4^^368, 5^^167, 6^^70, 7^^40, 8^^19, 9^^5,
   10^^2, 11^^2 *}.

Turning to primitive groups, we have examples like $S_{140}$ acting on the $9730$ unordered pairs. For this, I got:

 {* 0^^4440, 1^^3394, 2^^1143, 3^^574, 4^^204, 5^^48, 6^^105, 7^^42, 8^^8, 
    10^^17, 11^^13, 12^^4, 14, 15^^4, 16, 21, 28 *}

and similarly for other large primitives like primitive wreath product actions.

Classical groups look more intersting, and I wasn't detecting much pattern. Here are a few examples. ${\rm PSL}(13,2)$, degree $8191$:

{* 0^^2867, 1^^5803, 3^^1271, 7^^58, 15 *}

${\rm PSL}(5,11)$, degree $16105$:

{* 0^^3478, 1^^3915, 2^^1916, 3^^575, 4^^77, 5^^32, 12, 13^^2, 14, 15^^3 *}

${\rm PSp}(14,2)$, degree $16383$:

 {* 0^^4152, 1^^4244, 3^^1393, 7^^197, 15^^13, 31 *}

${\rm PSp}(6,7)$, degree $19608$ ($2$ more popular than $1$ fixed point):

 {* 0^^5092, 1^^1762, 2^^2137, 3^^650, 4^^221, 5^^81, 8^^29, 9^^4, 10^^14, 11^^3,
    12, 16^^4, 17, 18 *}

${\rm P \Omega}^+(6,9)$, degree $7462$ (even stronger preference for 2, and even numbers):

{* 0^^5711, 1^^171, 2^^3467, 3^^91, 4^^350, 6^^202, 12^^3, 22^^5 *}

You asked for $p$-groups. First a Sylow $2$-subgroup of $S_{8192}$ of order $2^{8191}$:

  {* 0^^8916, 2^^165, 4^^196, 6^^165, 8^^126, 10^^113, 12^^87, 14^^56, 16^^42, 
     18^^32, 20^^27, 22^^19, 24^^14, 26^^15, 28^^9, 30^^6, 32, 34^^4, 36, 38, 40^^3, 
     50^^2 *}

It's hard to see what is going on there.

And a Sylow $5$-subgroup of $S_{15625}$ of order $5^{3906}$.

{* 0^^8724, 100^^2, 250^^3, 340^^3, 345, 350^^4, 370^^2, 375^^15, 420, 435, 445,
   450, 470^^3, 475^^10, 490^^2, 495^^7, 500^^52, 540, 545, 550, 565^^2, 570, 
   575^^5, 595^^4, 600^^19, 615^^2, 620^^12, 625^^53,...*} 
$\endgroup$
6
  • $\begingroup$ That is very interesting! Did you try any $p$-groups, per chance? $\endgroup$
    – Igor Rivin
    Sep 20, 2015 at 15:04
  • $\begingroup$ I'm confused by your examples. Could you explain the $S_n\times S_m$ example a bit more? I took it to mean the subgroup of $S_{m+n}$ obtained by permutations that leave the set of first $m$ elements fixed. But in that case, wouldn't you expect that the proportion of elements with no fixed points is approximately $1/e$ times $1/e$ which is patently not the case in your numerics. I'm sure I've not understood what you mean. $\endgroup$
    – Lucia
    Sep 20, 2015 at 17:43
  • $\begingroup$ I'm also confused by the numerics for $S_{140}$ acting on the unordered pairs. The probability of an element of $S_{140}$ having no two cycles is approximately $1/\sqrt{e}$, and the probability of having at most one one cycle is approximately $2/e$. So shouldn't the proportion here with no fixed points be approximately $2/e^{3/2}$, which is only about $40\%$. $\endgroup$
    – Lucia
    Sep 20, 2015 at 17:58
  • $\begingroup$ @Lucia Yes you are right on both counts! Thanks for pointing this out. I think the fault lies with the default Magma random element generator. I will investigate further and try and come up with some more accurate figures. $\endgroup$
    – Derek Holt
    Sep 20, 2015 at 18:01
  • $\begingroup$ @Lucia I have revised the figures using a better random eleemnt generator (the Product Replacement Algorithm). $\endgroup$
    – Derek Holt
    Sep 20, 2015 at 18:18
6
$\begingroup$

A Gaussian limiting distribution is possible (if you allow a scaling operation to bring the mean and variance down to $O(1)$; this was not specified in the question but seems like a fair assumption). Let $k_1,\ldots,k_m$ be numbers such that $k_1+\ldots+k_m=n$. Then the number $Y$ of fixed points in the subgroup $$ S_{k_1}\times\ldots\times S_{k_m} $$ of $S_n$ has the distribution of a sum $X_1+\ldots+X_m$ of independent random variables such that $X_j$ is distributed like the number of fixed points in a uniformly random permutation in $S_{k_j}$. If we choose the $k_j$'s so that they are all large and so that $m\to\infty$ (for example taking $m\approx \sqrt{n}$ and $k_j\approx \sqrt{n}$), by the central limit theorem $Y$ will converge in distribution to a Gaussian.

$\endgroup$
2
$\begingroup$

Given $G\leq S_n$ let $X_G$ be the random variable on $\mathbf{N} = \{0,1,\dots,\}$ defined by the number of fixed points of a random $g \in G$.

Claim: For every random variable $X$ on $\overline{\mathbf{N}} = \mathbf{N} \cup \{\infty\}$ there is a sequence of groups $G_n$ such that $X_{G_n} \to X$ in distribution.

In other words, the set $\{\mu_{X_G}: G\leq S_n\}$ is dense in the space of all probability measures on $\overline{\mathbf{N}}$. As established in the comments, there are multiple ways of interpretting the question. This answers one particularly concrete interpretation.

Lemma 1: If both $X$ and $Y$ can be obtained, then so can their (independent) sum $X+Y$ and product $XY$.

(In the event of $0\cdot\infty$, our convention is $0\cdot\infty = 0$.)

Proof: Suppose $X_G \approx X$ and $X_H \approx Y$, where $G \leq \text{Sym}(\Omega_1)$ and $H \leq \text{Sym}(\Omega_2)$. Then $G\times H$ acts on $\Omega_1 \sqcup \Omega_2$ via $$(g,h) \omega = \begin{cases} g \omega : \omega \in \Omega_1, \\ h \omega : \omega\in \Omega_2.\end{cases}$$ For this action we have $$\text{fix}_{\Omega_1 \sqcup \Omega_2}((g,h)) = \text{fix}_{\Omega_1}(g) \cup \text{fix}_{\Omega_2}(h),$$ so the random variable for this action is $X_G + X_H \approx X + Y$.

Alternatively, $G \times H$ acts on $\Omega_1 \times \Omega_2$ via $$(g,h)(\omega_1,\omega_2) = (g\omega_1, h \omega_2).$$ For this action we have $$\text{fix}_{\Omega_1 \times \Omega_2}((g,h)) = \text{fix}_{\Omega_1}(g) \times \text{fix}_{\Omega_2}(h),$$ so the random variable for this action is $X_G X_H \approx X Y$.

Lemma 2: For each $t\in[0,1]$ we can obtain a random variable $X_t$ such that $X_t = 0$ with probability $t$ and $X_t = 1$ with probability $1-t$.

Proof: For prime $p$ consider the "$ax+b$ group" $\mathbf{F}_p^\times \ltimes \mathbf{F}_p$ acting on $\mathbf{F}_p$ via $(a,b) x = ax+b$. Evidently $$|\text{fix}_{\mathbf{F}_p}(a,b))| = \begin{cases} 1 & \text{if}~a\neq 1,\\ 0&\text{if}~a=1, b \neq 0,\\ p & \text{if}~a=1,b=0.\end{cases}$$ So we can obtain a random variable $Y$ such that $Y = 1$ with probability $1-1/(p-1)$, $Y=0$ with probability $1/(p-1) - 1/p(p-1)$, and $Y=p$ with probability $1/p(p-1)$. By Lemma 1 then we can obtain $Y^* = \prod_{i=1}^k Y_i$, where each $Y_i$ is an independent copy of $Y_i$. Note that $Y^*=1$ with probability $(1-1/(p-1))^k$ and $Y^*\geq 2$ with probability $\leq k/p(p-1)$. Put $k = \lfloor \log(1/(1-t)) p \rfloor$ and send $p\to\infty$.

Proof of main claim: It suffices to show that we can obtain any random variable supported on $\{0,\dots,N-1\}\cup\{\infty\}$ for each $N$. We will prove this by induction on $N$. For the case $N=0$ (i.e., $X=\infty$ with probability $1$), consider $X_{S_n}$ as $n\to\infty$. Now let $N\geq 1$ and let $X$ be an arbitrary random variable supported on $\{0,\dots,N-1\}\cup\{\infty\}$. Let $p_i = \mathbf{P}(X = i)$. Let $Y$ be the random variable supported on $\{0,\dots,N-2\}\cup\{\infty\}$ defined by $$\mathbf{P}(Y = i) = p_{i+1} / (1 - p_0).$$ By induction we can obtain $Y$. Thus by the lemmas we can obtain $$(X_0 + Y) X_{p_0} \sim X.$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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