fixed points of permutation groups

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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,...*} 

Answer 4

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.

Answer 5

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