# Derangements in wreath products
of permutation groups

Vishnuram Arumugam Supported by the Australian Government Research Training
Program. Center for the Mathematics and Symmetry, University of Western
Australia, Perth 6009, Australia
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Heiko Dietrich
Research visit of H. Dietrich to UWA was supported by the 2022 Cheryl Praeger
Visiting Fellowship. School of Mathematics, Monash University, Clayton 3800,
Australia
<EMAIL_ADDRESS>S.P. Glasby Supported by the Australian Research
Council Discovery Grant DP190100450. This problem was posed at the CMSC 2022
Annual Research Retreat. All authors thank the CMSC for its hospitality.
Center for the Mathematics and Symmetry, University of Western Australia,
Perth 6009, Australia
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

Given a finite group $G$ acting on a set $X$ let $\delta_{k}(G,X)$ denote the
proportion of elements in $G$ that have exactly $k$ fixed points in $X$. Let
$\mathcal{S}_{n}$ denote the symmetric group acting on
$[n]=\\{1,2,\dots,n\\}$. For $A\leqslant\mathcal{S}_{m}$ and
$B\leqslant\mathcal{S}_{n}$, the permutational wreath product $A\wr B$ has two
natural actions and we give formulas for both, $\delta_{k}(A\wr
B,[m]{\times}[n])$ and $\delta_{k}(A\wr B,[m]^{[n]})$. We prove that for $k=0$
the values of these proportions are dense in the intervals
$[\delta_{0}(B,[n]),1]$ and $[\delta_{0}(A,[m]),1]$. Among further result, we
provide estimates for $\delta_{0}(G,[m]^{[n]})$ for subgroups
$G\leqslant\mathcal{S}_{m}\wr\mathcal{S}_{n}$ containing
$\mathcal{A}_{m}^{[n]}$. Keywords: permutation groups, derangements, fixed-
point-free permutations, wreath products 2020 Mathematics Subject
Classification: 20B07, 20B35, 05A05

##  1 Introduction

Let $\mathcal{S}_{n}$ and $\mathcal{A}_{n}$ denote the symmetric and
alternating group acting on $[n]=\\{1,2,\dots,n\\}$. A permutation of
$\mathcal{S}_{n}$ that fixes no element in $[n]$ is a _derangement_. The
proportion of derangements in a subset $C\subseteq\mathcal{S}_{n}$ is denoted
$\delta(C)$. Given $k\in\\{0,1,\dots,n\\}$, let ${\rm
Fix}_{k}\mathopen{}\mathclose{{}\left(C}\right)$ denote the set of all
permutations in $C$ with precisely $k$ fixed points. We write
$\delta_{k}(C)=|{\rm Fix}_{k}\mathopen{}\mathclose{{}\left(C}\right)|/|C|$ and
note that $\delta(C)=\delta_{0}(C)$. Given subgroups
$A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$, the wreath
product $A\wr B=A^{[n]}\rtimes B$ gives rise to two natural permutation
subgroups: the _imprimitive_ subgroup $A\wr_{I}B\leqslant\mathcal{S}_{mn}$ and
the subgroup $A\wr_{P}B\leqslant\mathcal{S}_{m^{n}}$ with _power_ (or
_product_) action, see (Iw) and (Pw) in Section 2.2 for details. There is a
large body of literature on derangements; we highlight the most relevant
results in Section 2.

For $B\leqslant\mathcal{S}_{n}$ and $\ell\in[n]$ denote by
$\genfrac{[}{]}{0.0pt}{}{B}{\ell}$ the number of permutations in $B$ with
precisely $\ell$ cycles in their disjoint cycle decomposition; we note that
$\genfrac{[}{]}{0.0pt}{}{\mathcal{S}_{n}}{\ell}$ is the Stirling number
$\genfrac{[}{]}{0.0pt}{}{n}{\ell}$ of the first kind, see [9, Section 6.1] for
properties of $\genfrac{[}{]}{0.0pt}{}{n}{\ell}$. Our first result concerns
$\delta_{k}(A\wr_{I}B)$ and $\delta_{k}(A\wr_{P}B)$.

######  Theorem 1.1.

If $m,n\geqslant 2$, $A\leqslant\mathcal{S}_{m}$, and
$B\leqslant\mathcal{S}_{n}$, then

$\displaystyle\delta_{k}(A\wr_{I}B)$
$\displaystyle=\sum_{\ell=0}^{n}\delta_{\ell}(B)\sum_{j_{1}+\dots+j_{\ell}=k}\prod_{r=1}^{\ell}\delta_{j_{r}}(A)\quad\text{and
so}\quad\delta(A\wr_{I}B)=\sum_{\ell=0}^{n}\delta_{\ell}(B)\delta(A)^{\ell};$
$\displaystyle\delta_{k}(A\wr_{P}B)$
$\displaystyle=\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}\sum_{j_{1}\cdots
j_{\ell}=k}\prod_{r=1}^{\ell}\delta_{j_{r}}(A)\text{\ and \
}\delta(A\wr_{P}B)=1-\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}(1-\delta(A))^{\ell}.$

The formulas for $\delta_{k}(A\wr_{I}B)$ and $\delta_{k}(A\wr_{P}B)$ are
proved in Theorems 5.1 and 6.5. Setting $k=1$ in Theorem 1.1 gives the simple
formulas for $\delta_{1}(A\wr_{I}B)$ and $\delta_{1}(A\wr_{P}B)$ stated in
Corollaries 5.2 and 6.6. Formulas for $k=0$ were known [1, Theorems 4.3,
5.4(1)] and follow easily from our results.

We now summarise our density results; as usual, for $a\leqslant b$ we write
$[a,b]=\\{x\in\mathbb{R}\mid a\leqslant x\leqslant b\\}$.

######  Theorem 1.2.

For fixed $B\leqslant\mathcal{S}_{n}$, the set $\\{\delta(A\wr_{I}B)\mid
A\leqslant\mathcal{S}_{m}\text{ primitive},\;m\in\mathbb{N}\\}$ is dense in
$[\delta(B),1]$. For fixed $A\leqslant\mathcal{S}_{m}$, the set
$\\{\delta(A\wr_{I}B)\mid B\leqslant\mathcal{S}_{n}\text{
imprimitive},\;n\in\mathbb{N}\\}$ is dense in $[\delta(A),1]$.

######  Theorem 1.3.

For fixed $B\leqslant\mathcal{S}_{n}$, the set $\\{\delta(A\wr_{P}B)\mid
A\leqslant\mathcal{S}_{m}\text{ primitive},\;m\in\mathbb{N}\\}$ is dense in
$[0,1]$. For fixed $A\leqslant\mathcal{S}_{m}$, the set
$\\{\delta(A\wr_{P}B)\mid B\leqslant\mathcal{S}_{n}\text{
regular},\;n\in\mathbb{N}\\}$ is dense in $[\delta(A),1]$.

######  Theorem 1.4.

Suppose $A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$ and let
$C\trianglelefteqslant A$. Let $\delta_{L},\delta_{U}\in[0,1]$ such
$\delta_{L}\leqslant\delta(Ca)\leqslant\delta_{U}$ for all $a\in A$. Let
$\pi\colon\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}\to\mathcal{S}_{n}$ be the
natural projection and suppose
$G\leqslant\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}$ satisfies
$C^{[n]}\trianglelefteqslant G\leqslant A\wr_{P}B$, where $B=\pi(G)$. Then

$1-\mathcal{C}_{B}(1-\delta_{L})\leqslant\delta(G)\leqslant
1-\mathcal{C}_{B}(1-\delta_{U})\quad\text{where
$\mathcal{C}_{B}(x)=\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}x^{\ell}$}.$

Theorem 1.2 is proved in Section 5. Most of the paper deals with power action
in Section 6 where Theorems 1.3 and 1.4 are proved. Setting $C=A$ in Theorem
1.4 proves [1, Theorem 5.4(2)] (see also Theorem 2.1(b) below) and is
particularly useful for ‘large’ primitive subgroups
$G\leqslant\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}$ satisfying
$\mathcal{A}_{m}^{[n]}\trianglelefteqslant
G\leqslant\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}$.

Further results of this paper include the determination of $\delta_{k}(G)$ for
sharply $t$-transitive subgroups $G\leqslant\mathcal{S}_{n}$, see Section 3,
and the determination of $\delta_{k}(C)$ for direct products
$C_{1}\times\dots\times C_{r}$ with intransitive or product actions, see
Theorems 4.1 and 4.3.

###  1.1 Motivation

The motivation that led us to Theorem 1.4 involved the study of primitive
permutation groups that are ‘large’, or are ‘diagonal’ [11]. We explain the
former. A _base_ for a permutation group $G\leqslant\mathcal{S}_{n}$ is a set
$\\{x_{1},\dots,x_{m}\\}$ of points of $[n]$ such that the elementwise
stabiliser $G_{(x_{1},\dots,x_{m})}$ is trivial. The minimal size of a base
for $G\leqslant\mathcal{S}_{n}$ is denoted $b(G,[n])$, or $b(G)$. It is clear
that $|G|\leqslant\prod_{i=0}^{b(G)-1}(n-i)$. In fact, the size of $b(G)$ is a
good proxy for the size of $G$ for reasons that are related to Pyber’s (now
solved) base size conjecture, see [6]. When considering permutation groups
computationally or theoretically, groups with small base size (and hence small
order) are treated very differently. For example, Seress describes very
different algorithms for small and large base groups in [18], and the ‘large’
primitive groups with product action are considered separately by Maróti [14].
In particular, primitive groups are frequently divided into two categories
(‘small’ and ‘large’), see [14, Theorem 1.1]. The _‘small’_ primitive
subgroups $G\leqslant\mathcal{S}_{N}$ satisfy $|G|\leqslant
N^{1+\lceil\log_{2}(N)\rceil}$ or are one for four simple groups, and the
_‘large’_ primitive groups satisfy $\mathcal{A}_{m}^{[n]}\trianglelefteqslant
G\leqslant\mathcal{S}_{m}\wr\mathcal{S}_{n}$ where $\mathcal{S}_{m}$ acts on
$k$-subsets of $[m]$ and $N=\binom{m}{k}^{n}$. (However, overlap is possible.
For example, if $k=1$, then
$\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}\leqslant\mathcal{S}_{m^{n}}$ is both
‘small’ and ‘large’ for $n=1$ and $m\leqslant 29$, or $n=2$ and $m\leqslant
11$, and only ‘large’ for greater $m$.) ‘Large’ primitive groups arise when
considering orders [14, Theorem 1.1], base sizes [10, Theorem], and minimal
degrees [12, Theorem 2] of primitive groups.

The ‘large’ primitive permutation groups are important in many computational
and theoretical contexts. Given such a group, we wondered whether knowing only
$\delta(G)$ was enough to determine the projection
$\pi(G)\leqslant\mathcal{S}_{n}$ in Theorem 1.4. In the light of Theorem 1.3
this may seem like an impossible hope. However, if $G=A\wr_{P}B$ is the full
wreath product, then $\delta(G)=1-\mathcal{C}_{B}(1-\delta(A))$ holds by [1,
Theorem 5.4(2)]. If $A=\mathcal{S}_{m}$, then $\delta(G)$ strongly influences
the polynomial $\mathcal{C}_{B}(x)$ when $n$ is small, and we can sometimes
recover the group $B$. (For example, if $n<6$, then the polynomial
$\mathcal{C}_{B}(x)$ determines the group $B$, and if $B$ is primitive, then
$\mathcal{C}_{B}(x)$ determines $B$ if $n<64$.) By taking $C=\mathcal{A}_{m}$,
Theorem 1.4 gives hope for recovering $\pi(G)$ from $\delta(G)$ even when $G$
is _not_ a wreath product. In order to estimate $\delta(G)$ when
$\mathcal{A}_{m}^{[n]}\trianglelefteqslant
G\leqslant\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}$, we consider proportions of
elements in _subsets_ of $G$.

Our interest was piqued by a recent announcement [16, Theorem 1.1] that if
$G\leqslant\mathcal{S}_{n}$ is a subgroup with
$\delta(Gc)=\delta(\mathcal{S}_{n})$ for some $c\in\mathcal{S}_{n}$, then
$Gc=\mathcal{S}_{n}$ and hence $G=\mathcal{S}_{n}$; see [16, Remark 1.2] for a
comment on subsets $C\leqslant\mathcal{S}_{n}$ with
$\delta(C)=\delta(\mathcal{S}_{n})$.

##  2 Background

If $G\leqslant\mathcal{S}_{n}$ is a transitive subgroup and $n\geqslant 2$,
then the Orbit-Counting Theorem implies that $\mathrm{Der}(G)$ is non-empty,
see [19, Theorem 4]. Given a transitive permutation group
$G\leqslant\mathcal{S}_{n}$, its _rank_ $r$ is the number of orbits of a
point-stabiliser on $[n]$. For such a $G$, the following bounds hold:

(1)
$\frac{r-1}{n}\leqslant\delta\mathopen{}\mathclose{{}\left(G}\right)\leqslant
1-\frac{1}{r}.$

The lower bound was proved by Cameron-Cohen [2], and the upper bound by
Diaconis-Fulman-Guralnick [4, Theorem 3.1].

Serre [19] describes some interesting consequences of the existence of
derangements to number theory and topology. Fulman-Guralnick [8] show that if
$G$ is a sufficiently large finite simple group acting faithfully and
transitively on $[n]$, then $\delta(G)\geqslant 0.016$. This result completes
the proof of the Boston-Shalev Conjecture, which claims that there is a
constant $\varepsilon>0$ such that $\delta(G)>\varepsilon$ for any such group
$G$.

In the course of our research, we proved three (quite natural) results that
were previously proved by Boston et al. [1, Theorems 4.3, 5.4(2), 5.11].

######  Theorem 2.1 (Boston et al. [1]).

Let $A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$. Then

  1. (a)

$\delta(A\wr_{I}B)=\mathcal{P}_{B}(\delta(A))$ where
$\mathcal{P}_{B}(x)=\sum_{\ell=0}^{n}\delta_{\ell}(B)x^{\ell}$.

  2. (b)

$\delta(A\wr_{P}B)=1-\mathcal{C}_{B}(1-\delta(A))$ where
$\mathcal{C}_{B}(x)=\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}x^{\ell}$.

  3. (c)

The set $\\{\delta(C)\mid\text{$C\leqslant\mathcal{S}_{n}$
primitive},\;n\in\mathbb{N}\\}$ is dense in $[0,1]$.

###  2.1 Cycle index polynomials and derangements

For $g\in\mathcal{S}_{n}$ and $i\in[n]$ let $m_{i}(g)$ denote the number of
$i$-cycles in the disjoint cycle decomposition of $g$, so that
$c_{n}(g)=\sum_{i=1}^{n}m_{i}(g)$ is the number of cycles of $g$. The well-
known _cycle index polynomial_ $\mathcal{Z}(G)$ of $G\leqslant\mathcal{S}_{n}$
is defined to be the multivariate polynomial

$\mathcal{Z}(G)=\mathcal{Z}(G;x_{1},\dots,x_{n})=\frac{1}{|G|}\sum_{g\in
G}x_{1}^{m_{1}(g)}\cdots x_{n}^{m_{n}(g)}.$

Specialising the variables $x_{i}$ allows one to obtain polynomials with fewer
variables which are easier to calculate. For example, the probability
generating functions $\mathcal{P}_{G}(x)$ and $\mathcal{C}_{G}(x)$ for the
number of fixed points and the number of permutations with $\ell$ cycles,
respectively, are

$\displaystyle\mathcal{P}_{G}(x)$
$\displaystyle=\mathcal{Z}(G;x,1,\dots,1)=\frac{1}{|G|}\sum_{\ell=0}^{n}|\mathrm{Fix}_{\ell}(G)|x^{\ell}=\sum_{\ell=0}^{n}\delta_{\ell}(G)x^{\ell}\qquad\textup{and}$
$\displaystyle\mathcal{C}_{G}(x)$
$\displaystyle=\mathcal{Z}(G;x,x,\dots,x)=\frac{1}{|G|}\sum_{g\in
G}x^{{c}_{n}(g)}=\frac{1}{|G|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{G}{\ell}x^{\ell},$

where, as in Section 1, we denote by $\genfrac{[}{]}{0.0pt}{}{G}{\ell}$ the
number of $g\in G$ with $c_{n}(g)=\ell$. Clearly, $g\in\mathrm{Fix}_{k}(G)$ if
and only if $m_{1}(g)=k$; in particular, $\delta(G)=\mathcal{P}_{G}(0)$. We
note that for $k=0$, the formulas in Theorems 1.1 and 1.4 can be expressed
using the cycle index polynomial.

Formulas for the cycle index polynomials $\mathcal{Z}(A\wr_{I}B)$ and
$\mathcal{Z}(A\wr_{P}B)$ date back to Pólya and Palmer-Robinson, respectively
[15, Theorems 1, 2]. Our proof of Theorem 1.1 does not use these formulas, as
they are rather complicated, especially for $\mathcal{Z}(A\wr_{P}B)$. The GAP
package WPE [17] is a useful research tool which, in particular, can compute
$\mathcal{Z}(A\wr_{P}B)$.

###  2.2 Group actions

We denote a group $G$ acting on a set $X$ by $(G,X)$. If $|X|=n$, then the
corresponding homomorphism $\varphi\colon G\to\mathrm{Sym}(X)$ allows us to
identify $G/\ker\varphi$ with the subgroup
$\varphi(G)\leqslant\mathcal{S}_{n}$. In this case we define
$\delta(G,X)=\delta(\varphi(G))$. Thus we shall henceforth consider _faithful_
actions, and view $G$ as a _subgroup_ of $\mathrm{Sym}(X)$. Moreover, if $Y\to
X$ is a surjection of $G$-sets, $\delta(G,Y)\geqslant\delta(G,X)$ holds, see
[7, p. 3], which implies that when considering lower bounds for the proportion
of derangements of a group (for any action), one can restrict to primitive
actions.

Given a group $A$ and a permutation group $B\leqslant\mathrm{Sym}(Y)$ the
permutational wreath product $A\wr_{Y}B$ is defined as the split extension
$A^{Y}\rtimes B$ where $A^{Y}$ is the group of all functions $Y\to A$ with
pointwise multiplication. The group $A^{Y}\rtimes B$ has underlying set
$A^{Y}\times B$ and multiplication

$(\alpha,b)(\beta,c)=(\alpha\beta^{b^{-1}},bc)\qquad\textup{where
$\alpha,\beta\in A^{Y}$, $b,c\in B$,}$

and $\beta^{b}\colon Y\to A$ is the map $y\mapsto\beta(yb^{-1})$. Following
Cameron-Gewurz-Merola [3], given permutation groups
$A\leqslant\mathrm{Sym}(X)$ and $B\leqslant\mathrm{Sym}(Y)$ the direct product
$A\times B$ has an _intransitive_ action (Ix) and a _product_ action (Px) and
the wreath product $A\wr_{Y}B$ has an _imprimitive_ action (Iw) and a _power_
action (Pw), defined as follows. To avoid towers of exponents, we write the
action of $g\in G$ on $x\in X$ as $xg$, and not $x^{g}$. Also
$X\,\dot{\cup}\,Y$ denotes the disjoint union of $X$ and $Y$.

  1. (Ix)

$(a,b)\in A\times B$ acts on $X\,\dot{\cup}\,Y$ via $x(a,b)=xa$ if $x\in X$,
and $y(a,b)=yb$ if $y\in Y$.

  2. (Px)

$(a,b)\in A\times B$ acts on $(x,y)\in X\times Y$ via $(x,y)(a,b)=(xa,yb)$.

  3. (Iw)

$(\alpha,b)\in A\wr_{Y}B$ acts on $(x,y)\in X\times Y$ via
$(x,y)(\alpha,b)=(x\alpha(y),yb)$.

  4. (Pw)

$(\alpha,b)\in A\wr_{Y}B$ acts on $\omega\in X^{Y}$ via
$\omega(\alpha,b)\colon Y\to X$, $y\mapsto\omega(yb^{-1})\alpha(yb^{-1})$.

In the case that $Y=[n]$, we identify $\omega\in X^{Y}$ and $\alpha\in A^{Y}$
with $n$-tuples $(\omega_{1},\dots,\omega_{n})$,
$(\alpha_{1},\dots,\alpha_{n})$ where each $\omega_{i}=\omega(i)$ and
$\alpha_{i}=\alpha(i)$, respectively. The power action (Pw) of the base group
$A^{Y}$ coincides with (iterated) product action (Px). Most authors call (Pw)
product action; although unconventional, we shall refer to (Pw) as power
action. If $A\leqslant\mathrm{Sym}(X)$ is primitive but not regular,
$B\leqslant\mathrm{Sym}(Y)$ is transitive, $|Y|$ is finite, and $1<|X|,|Y|$,
then $A\wr_{Y}B\leqslant\mathrm{Sym}(Y^{X})$ is primitive by [5, Lemma 2.7A],
so (Pw) can suggest a _primitive/product/power wreath_ product, so (Pw) is a
good abbreviation. We change the subscript in $A\wr_{Y}B$ in favour of the
notation $\wr_{I}$ or $\wr_{P}$.

######  Notation.

We abbreviate $(A\times B,X\,\dot{\cup}\,Y)$, $(A\times B,X\times Y)$,
$(A\wr_{Y}B,X\times Y)$, and $(A\wr_{Y}B,X^{Y})$ by $A\times_{I}B$,
$A\times_{P}B$, $A\wr_{I}B$, and $A\wr_{P}B$, respectively.

We emphasise that there is a permutation isomorphism $(A\wr_{I}B)\wr_{I}C\cong
A\wr_{I}(B\wr_{I}C)$, but associativity fails for $\wr_{P}$. Indeed
$|(X^{Y})^{Z}|=|X^{Y\times Z}|\neq|X^{(Y^{Z})}|$ if $|Y|\geqslant 2$,
$|Z|\geqslant 2$ and $|Y|^{|Z|}\neq 4$.

##  3 Sharply transitive groups

Let $G\leqslant\mathcal{S}_{n}$ be a subgroup that acts sharply
$t$-transitively, that is, it acts regularly on the set of $t$-tuples with
distinct entries in $[n]$. Hence $|G|$ equals the number $n!/(n-t)!$ of such
tuples.

######  Theorem 3.1.

Let $n\geqslant 2$, $t\in[n]$, and $k\in\\{0,\ldots,n\\}$. If
$G\leqslant\mathcal{S}_{n}$ is sharply $t$-transitive, then
$\delta_{n}(G)=1/|G|$, $\delta_{k}(G)=0$ if $t\leqslant k<n$, and

$\delta_{k}(G)=\frac{1}{k!}\sum_{j=0}^{t-k-1}\frac{(-1)^{j}}{j!}+\frac{(n-t)!}{k!}\sum_{j={t-k}}^{n-k}\frac{(-1)^{j}}{(n-k-j)!j!}\qquad\text{if
$0\leqslant k<t$.}$

###### Proof.

Note that $|\mathrm{Fix}_{n}(G)|=1$ and $|\mathrm{Fix}_{k}(G)|=0$ for
$t\leqslant k<n$, so the claim is true for $k\geqslant t$. Suppose now that
$k<t$. For a subset $K\subseteq[n]$ let $G_{(K)}$ be the elementwise
stabiliser of $K$ in $G$. Note that $|\mathrm{Der}(G,[n])|=|G|-|{F}|$, where
${F}=G_{(1)}\cup\dots\cup G_{(n)}$. This number can be determined using a
standard inclusion-exclusion argument (see also [1, Theorem 2.3]), and we
obtain

(2)
$\delta(G,[n])=\sum_{j=0}^{t-1}\frac{(-1)^{j}}{j!}+(n-t)!\sum_{j=t}^{n}\frac{(-1)^{j}}{j!(n-j)!}.$

The set $K$ of fixed points of $g\in\mathrm{Fix}_{k}(G)$ has size $k$, and $g$
induces a derangement on the complement $K^{\prime}=[n]\setminus K$. We view
$G_{(K)}$ as a sharply $(t-k)$-transitive permutation group of degree
$|K^{\prime}|=n-k$. Since $|G_{(K)}|=(n-k)!/(n-t)!$, we have

(3)
$|\mathrm{Fix}_{k}(G)|=\binom{n}{k}|G_{(K)}|\,\delta(G_{(K)},K^{\prime})=\frac{n!}{k!(n-t)!}\,\delta(G_{(K)},K^{\prime})=\frac{|G|}{k!}\,\delta(G_{(K)},K^{\prime}).$

Dividing by $|G|$, and using (2) with $n$ and $t$ replaced by $n-k$ and $t-k$
proves the claim. ∎

Throughout, we define $d_{0}=e_{0}=1$, and if $n\geqslant 1$ is an integer,
then

$d_{n}=\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}\quad\text{and}\quad
e_{n}=\sum_{k=n-1}^{n}\frac{(-1)^{k}}{k!}=\frac{(-1)^{n-1}(n-1)}{n!}.$

Note that $\lim_{n\to\infty}e_{n}=0$ and $\lim_{n\to\infty}d_{n}=e^{-1}$,
where $e$ denotes the Euler number. Also, if $n\geqslant 2$, then
$\mathcal{S}_{n}$ is sharply $(n-1)$-transitive, and $\mathcal{A}_{n}$ is
sharply $(n-2)$-transitive. The next result follows from Theorem 3.1 with a
little algebra.

######  Corollary 3.2.

If $n\geqslant 1$ and $k\in\\{0,\dots,n\\}$, then

  1. (a)

$\delta_{k}(\mathcal{S}_{n})=d_{n-k}/k!$,

  2. (b)

$\delta_{k}(\mathcal{A}_{n})=(d_{n-k}+e_{n-k})/k!$, and

  3. (c)

$\delta_{k}(\mathcal{S}_{n}\setminus\mathcal{A}_{n})=(d_{n-k}-e_{n-k})/k!$.

If $k$ is fixed, then
$\lim_{n\to\infty}\delta_{k}\mathopen{}\mathclose{{}\left(\mathcal{S}_{n}}\right)=\lim_{n\to\infty}\delta_{k}\mathopen{}\mathclose{{}\left(\mathcal{A}_{n}}\right)=\lim_{n\to\infty}\delta_{k}\mathopen{}\mathclose{{}\left(\mathcal{S}_{n}\setminus\mathcal{A}_{n}}\right)=e^{-1}/k!$.

######  Remark 3.3.

If $G\leqslant\mathcal{S}_{n}$ has $s$ orbits on $[n]$, then the Orbit-
Counting Lemma implies that

$\frac{1}{s}\sum_{k=0}^{n}k|\mathrm{Fix}_{k}(G)|=|G|=\sum_{k=0}^{n}|\mathrm{Fix}_{k}(G)|\quad\textup{and
hence}\quad\delta(G)=\sum_{k=1}^{n}\mathopen{}\mathclose{{}\left(\frac{k}{s}-1}\right)\delta_{k}(G).$

If $(G,[n])$ is a sharply $t$-transitive subgroup of $\mathcal{S}_{n}$, then
$s=1$ and $|G|=n!/(n-t)!$, and Equation (3) transforms the latter equation for
$\delta(G)$ into the following recurrence relation

$\delta(G,[n])=\frac{(n-t)!}{n(n-2)!}+\sum_{k=2}^{t-1}\frac{1}{k(k-2)!}\delta(G_{([k])},[n]\setminus[k]),$

where $(G_{([k])},[n]\setminus[k])$ is a $(t-k)$-transitive subgroup of
$\textup{Sym}([n]\setminus[k])\cong\mathcal{S}_{n-k}$.

##  4 Direct products

###  4.1 Product action

The following result generalises [1, Lemma 6.1].

######  Theorem 4.1.

For $r>0$ and $i\in[r]$ let $G_{i}\leqslant\mathrm{Sym}(X_{i})$. Let the
subgroup $G=G_{1}\times\dots\times G_{r}$ of
$\mathrm{Sym}(X_{1}\times\dots\times X_{r})$ act via (Px). If
$C=C_{1}\times\dots\times C_{r}\subseteq G$ with each $C_{i}\subseteq G_{i}$,
then

$\delta_{k}\mathopen{}\mathclose{{}\left(C}\right)=\sum_{i_{1}\cdots
i_{r}=k}\prod_{s=1}^{r}\delta_{i_{s}}(C_{s})\quad\text{and}\quad\delta\mathopen{}\mathclose{{}\left(C}\right)=1-\prod_{i=1}^{r}(1-\delta(C_{i}))\quad\text{if
$k=0$}.$

###### Proof.

Note that $C$ is partitioned into sets $D_{i_{1},\dots,i_{r}}={\rm
Fix}_{i_{1}}(C_{1})\times\dots\times{\rm Fix}_{i_{r}}(C_{r})$ for
$i_{1},\dots,i_{r}\geqslant 0$, and every element in $D_{i_{1},\dots,i_{r}}$
has exactly $i_{1}\cdots i_{r}$ fixed points. Thus we have

$\displaystyle|{\rm Fix}_{k}(C)|$ $\displaystyle=\sum_{i_{1}\cdots
i_{r}=k}\prod_{s=1}^{r}|{\rm Fix}_{i_{s}}(C_{s})|$

and dividing by $|C|=\prod_{s=1}^{r}|C_{i}|$ yields the first claim.

For $k=0$, note that $(x_{1},\dots,x_{r})\in X_{1}\times\cdots\times X_{r}$ is
fixed by $(c_{1},\dots,c_{r})\in C$ if and only if $x_{i}c_{i}=x_{i}$ for each
$i\in[r]$. Thus, $1-\delta(C)=\prod_{i=1}^{r}(1-\delta(C_{i}))$, as claimed. ∎

We now give examples of subgroups all having similar proportions of
derangements.

######  Corollary 4.2.

Let
$G_{m_{1},\dots,m_{r}}\leqslant\mathcal{S}_{m_{1}}\times\dots\times\mathcal{S}_{m_{r}}$
act via product action (Px) where

$\mathcal{A}_{m_{1}}\times\dots\times\mathcal{A}_{m_{r}}\trianglelefteqslant
G_{m_{1},\dots,m_{r}}\leqslant\mathcal{S}_{m_{1}}\times\dots\times\mathcal{S}_{m_{r}}.$

For the multi-indexed sequence $(G_{m_{1},\dots,m_{r}})$ of subgroups, we have

$\lim_{m_{1},\dots,m_{r}\to\infty}\delta\mathopen{}\mathclose{{}\left(G_{m_{1},\dots,m_{r}}}\right)=1-(1-e^{-1})^{r}.$

###### Proof.

Note that $G=G_{m_{1},\dots,m_{r}}$ is a union of cosets of
$A=\mathcal{A}_{m_{1}}\times\dots\times\mathcal{A}_{m_{r}}$ of the form

$C=A(c_{1},\dots,c_{r})=(\mathcal{A}_{m_{1}}c_{1})\times\dots\times(\mathcal{A}_{m_{r}}c_{r}).$

For each $i$, either $\mathcal{A}_{m_{i}}c_{i}=\mathcal{A}_{m_{i}}$ or
$\mathcal{A}_{m_{i}}c_{i}=\mathcal{S}_{m_{i}}\setminus\mathcal{A}_{m_{i}}$, so
$\delta\mathopen{}\mathclose{{}\left(\mathcal{A}_{m_{i}}c_{i}}\right)=d_{m_{i}}\pm
e_{m_{i}}$ by Corollary 3.2. Since each
$\delta\mathopen{}\mathclose{{}\left(\mathcal{A}_{m_{i}}c_{i}}\right)\to
e^{-1}$ for $m_{i}\to\infty$, Theorem 4.1 implies that
$\delta\mathopen{}\mathclose{{}\left(Ac}\right)\to 1-(1-e^{-1})^{r}$ as
$m_{1},\dots,m_{r}\to\infty$. If $G$ is a disjoint union
$G=\bigcup_{c\in\mathscr{C}}Ac$, so $|G|=|A||\mathcal{C}|$, then

$\delta\mathopen{}\mathclose{{}\left(G}\right)=\frac{1}{|G|}\sum_{c\in\mathscr{C}}|\mathrm{Der}(Ac)|=\frac{1}{|\mathscr{C}|}\sum_{c\in\mathscr{C}}\delta(Ac).$

As shown above, $\sum_{c\in\mathscr{C}}\delta(Ac)$ converges to
$|\mathscr{C}|(1-(1-e^{-1})^{r})$, which implies the claim. ∎

###  4.2 Intransitive action

Counting derangements with an intransitive action is straightforward.

######  Theorem 4.3.

For $r>0$ and $i\in[r]$ let $G_{i}\leqslant\mathrm{Sym}(X_{i})$. Let the
subgroup $G=G_{1}\times\dots\times G_{r}$ of
$\mathrm{Sym}(X_{1}\,\dot{\cup}\,\cdots\,\dot{\cup}\,X_{r})$ act via (Ix). If
$C=C_{1}\times\dots\times C_{r}\subseteq G$ with each $C_{i}\subseteq G_{i}$,
then

$\delta_{k}\mathopen{}\mathclose{{}\left(C}\right)=\sum_{k_{1}+\dots+k_{r}=k}\prod_{i=1}^{r}\delta_{k_{i}}\mathopen{}\mathclose{{}\left(C_{i}}\right)\qquad\text{and
hence}\qquad\delta(C)=\prod_{i=1}^{r}\delta(C_{i}).$

###### Proof.

We have $(c_{1},\dots,c_{r})\in{\rm Fix}_{k}(C)$ if and only if for each
$i\in[r]$, there exists a $k_{i}$ such that $c_{i}\in{\rm Fix}_{k_{i}}(C_{i})$
and $k=k_{1}+\cdots+k_{r}$. The result follows from

$|{\rm Fix}_{k}(C)|=\sum_{k_{1}+\dots+k_{r}=k}\prod_{i=1}^{r}|{\rm
Fix}_{k_{i}}(C_{i})|.\qed$

The following result gives subgroups with similar proportions of derangements.
We omit the proof as it similar to that of Corollary 4.2 but using Theorem 4.3
instead of Theorem 4.1.

######  Corollary 4.4.

Let
$G_{m_{1},\dots,m_{r}}\leqslant\mathcal{S}_{m_{1}}\times\dots\times\mathcal{S}_{m_{r}}$
act via intransitive action (Ix) where

$\mathcal{A}_{m_{1}}\times\dots\times\mathcal{A}_{m_{r}}\trianglelefteqslant
G_{m_{1},\dots,m_{r}}\leqslant\mathcal{S}_{m_{1}}\times\dots\times\mathcal{S}_{m_{r}}.$

The multi-indexed sequence $(G_{m_{1},\dots,m_{r}})$ satisfies
$\lim_{m_{1},\dots,m_{r}\to\infty}\delta\mathopen{}\mathclose{{}\left(G_{m_{1},\dots,m_{r}}}\right)=e^{-r}$.

##  5 Wreath products $A\wr_{I}B$ with imprimitive action

In this section we find a formula for $\delta_{k}(A\wr_{I}B)$, which is the
first formula in Theorem 1.1, and we prove the density result Theorem 1.2.

######  Theorem 5.1.

Let $A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$. Then

$\delta_{k}(A\wr_{I}B)=\sum_{\ell=0}^{n}\delta_{\ell}(B)\sum_{j_{1}+\dots+j_{\ell}=k}\prod_{r=1}^{\ell}\delta_{j_{r}}(A)\quad\textup{and
hence}\quad\delta(A\wr_{I}B)=\sum_{\ell=0}^{n}\delta_{\ell}(B)\delta(A)^{\ell}.$

###### Proof.

An element $(\alpha,b)\in A\wr_{I}B$ fixes $(x,y)\in[m]\times[n]$ if and only
if $x=x\alpha(y)$ and $y=yb$. If $y_{1},\dots,y_{\ell}$ are the fixed points
of $b$ (so $b\in{\rm Fix}_{\ell}(B)$) and $x_{i,1},\ldots,x_{i,j_{i}}$ are the
fixed points of $\alpha(y_{i})$ (so $\alpha(y_{i})\in{\rm Fix}_{j_{i}}(A)$),
then each $(x_{i,s},y_{i})$ is a fixed point of $(\alpha,b)$, and every fixed
point of $(\alpha,b)$ has this form. No constraints are imposed upon
$\alpha(y)$ for $y\in[n]\setminus\\{j_{1},\dots,j_{\ell}\\}$. The total number
of fixed points is $k=j_{1}+\dots+j_{\ell}$, hence $(\alpha,b)\in{\rm
Fix}_{k}(A\wr_{I}B)$. This shows the following, and dividing by
$|A\wr_{I}B|=|A|^{n}|B|$ proves the claim:

$|{\rm Fix}_{k}(A\wr_{I}B)|=\sum_{\ell=0}^{n}|{\rm
Fix}_{\ell}(B)|\sum_{j_{1}+\dots+j_{\ell}=k}|A|^{n-\ell}\prod_{r=1}^{\ell}|{\rm
Fix}_{j_{r}}(A)|.\qed$

######  Corollary 5.2.

If $A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$, then

$\delta_{1}(A\wr_{I}B)=\delta_{1}(A)\mathcal{P}_{B}^{\prime}(\delta(A))$

where
$\mathcal{P}_{B}^{\prime}(x)=\sum_{\ell=1}^{n}\ell\delta_{\ell}(B)x^{\ell-1}$
is the derivative of $\mathcal{P}_{B}(x)$.

The polynomial $\mathcal{P}_{B}(x)$ is elusive in general. However, when $B$
is transitive and $\delta(B)$ is small, then $\mathcal{P}_{B}(x)$ is convex
for $x\in[0,1]$, that is, cup shaped, and slightly larger than $x$ by the
following lemma.

######  Lemma 5.3.

If $B\leqslant\mathcal{S}_{n}$, then $\mathcal{P}_{B}(x)$ is convex. If $B$ is
transitive, then $0\leqslant\mathcal{P}_{B}(x)-x\leqslant\mathcal{P}_{B}(0)$
holds for $0\leqslant x\leqslant 1$.

###### Proof.

The claim is trivially true if $n=1$, so let $n\geqslant 2$ and write
$f(x)=\mathcal{P}_{B}(x)-x$. Since $\mathcal{P}_{B}(x)$ has non-negative
coefficients and highest term $x^{n}/|B|$, the second derivative satisfies
$f^{\prime\prime}(x)=\mathcal{P}^{\prime\prime}_{B}(x)>0$ for $0<x\leqslant
1$, so both $f(x)$ and $\mathcal{P}_{B}(x)$ are convex on $[0,1]$. By [1,
Theorem 4.6(4)], we have $\mathcal{P}^{\prime}_{B}(x)=\mathcal{P}_{H}(x)$
where $H\leqslant\mathcal{S}_{n-1}$ is the stabiliser of $n$ in $B$ acting on
$[n-1]$. This implies $\mathcal{P}^{\prime}_{B}(1)=1$ and
$\mathcal{P}^{\prime}_{B}(x)\leqslant 1$ for $x\in[0,1]$. Thus,
$f(1)=f^{\prime}(1)=0$, and convexity implies that $f(x)$ lies above the
tangent line $y=0$ at $(1,0)$, that is, $0\leqslant f(x)$ on the domain
$[0,1]$. Since $f^{\prime}(x)=\mathcal{P}_{B}^{\prime}(x)-1\leqslant 0$ on
$[0,1]$, the function $f(x)$ is decreasing on $[0,1]$. This proves the last
claim $f(x)\leqslant f(0)=\mathcal{P}_{B}(0)$. ∎

We now prove Theorem 1.2, employing a similar argument as in [1, Theorem
4.13].

###### Proof of Theorem 1.2.

Fix $B\leqslant\mathcal{S}_{n}$. The map
$\mathcal{P}_{B}\colon[0,1]\to(0,\infty)\colon
z\mapsto\sum_{k=0}^{n}\delta_{k}(B)z^{k}$ satisfies
$\delta(A\wr_{I}B)=\mathcal{P}_{B}(\delta(A))$ by Theorem 2.1(a). Note that
$\mathcal{P}_{B}$ is a continuous increasing polynomial function with
$\mathcal{P}_{B}(0)=\delta(B)$ and $\mathcal{P}_{B}(1)=1$, so
$\delta(B)\leqslant\delta(A\wr_{P}B)<1$ for all $A\leqslant\mathcal{S}_{m}$.
Letting $m\geqslant 1$ and $A$ vary over the primitive subgroups of
$\mathcal{S}_{m}$, it follows from Theorem 2.1(c) that the values of
$\delta(A\wr_{P}B)$ are dense in the interval $[\delta(B),1]$. This proves the
first claim.

For the second claim, fix $A\leqslant\mathcal{S}_{m}$. If
$B\leqslant\mathcal{S}_{n}$ is imprimitive, then $B$ is transitive and
$\delta(A\wr_{I}B)=\mathcal{P}_{B}(\delta(A))\geqslant\delta(A)$ by Lemma 5.3,
so the values of $\delta(A\wr_{I}B)$ (with $B$ imprimitive) lie in
$[\delta(A),1]$. Let $q$ be a prime power, and let
$C_{q}=\textup{AGL}_{1}(q)\leqslant\mathcal{S}_{q}$ act naturally on $q$
affine points; we also abbreviate $C=C_{q}$. An easy calculation shows that
$\mathcal{P}_{C}(x)=\frac{1}{q}+\frac{(q-2)x}{q-1}+\frac{x^{q}}{q(q-1)}$, see
[1, Example 4.4]. Let $B_{r}=B_{r,q}$ be the imprimitive wreath product
$C\wr_{I}\cdots\wr_{I}C$ of $r$ copies of $C$. We show that the closure of the
set $\\{\delta(A\wr_{I}B_{r,q})\mid\textup{$r\geqslant 0$, $q$ prime
power}\\}$ is the interval $[\delta(A),1]$.

The recurrence
$\mathcal{P}_{B_{r}}(x)=\mathcal{P}_{B_{r-1}}(\mathcal{P}_{C}(x))$ holds by
[1, Theorem 4.6(8)] since $B_{r}=C\wr_{I}B_{r-1}$. The function
$\mathcal{P}_{B_{r-1}}(x)$ is increasing, and since
$\mathcal{P}_{C}(x)>\alpha+\beta x$ for $\alpha=\frac{1}{q}$ and
$\beta=\frac{q-2}{q-1}$, we have
$\mathcal{P}_{B_{r}}(x)>\mathcal{P}_{B_{r-1}}(\alpha+\beta x)$. An induction
on $r$ now shows that
$\mathcal{P}_{B_{r}}(x)>\alpha(1+\beta+\cdots+\beta^{r-1})+\beta^{r}x$, and
therefore
$\mathcal{P}_{B_{r}}(x)>\alpha\frac{\beta^{r}-1}{\beta-1}=(1-\frac{1}{q})(1-\beta^{r})$
for all $x\in[0,1]$. Now choose $q>1/\varepsilon$, so that
$1-\frac{1}{q}>1-\varepsilon$, and then choose $r$ such that
$(1-\frac{1}{q})(1-\beta^{r})>1-\varepsilon$.

Let $c_{r}=\delta(A\wr_{I}B_{r})$. It follows from Theorem 2.1(a) that
$\delta(A\wr_{I}B_{r})=\mathcal{P}_{B_{r}}(\delta(A))$ and the previous
paragraph shows that $c_{r}>1-\varepsilon$. As $C$ is transitive,
$0\leqslant\mathcal{P}_{C}(x)-x\leqslant\mathcal{P}_{C}(0)$ for $x\in[0,1]$ by
Lemma 5.3, and so
$0\leqslant\mathcal{P}_{C}(x)-x\leqslant\frac{1}{q}<\varepsilon$. Set
$c_{0}=\delta(A)$ and $c_{i}=\mathcal{P}_{C}(c_{i-1})$. Then $0\leqslant
c_{i}-c_{i-1}<\varepsilon$ holds for $1\leqslant i\leqslant r$ and
$1-\varepsilon<c_{r}<1$. The claim now follows since each
$c_{i}=\delta(A\wr_{I}C\wr_{I}\cdots\wr_{I}C)=\delta(A\wr_{I}B_{i,q})$ with
$B_{i,q}$ imprimitive. ∎

In the special case that $B=\mathcal{S}_{m}$, we obtain the following explicit
formula.

######  Corollary 5.4.

Setting $B=\mathcal{S}_{m}$ in Theorem 5.1 gives

$\delta(A\wr_{I}\mathcal{S}_{n})=\sum_{\ell=0}^{n}\frac{\delta(A)^{\ell}}{\ell!}\sum_{i=0}^{n-\ell}\frac{(-1)^{i}}{i!}=\sum_{i=0}^{n}\frac{(-1)^{i}}{i!}\sum_{\ell=0}^{n-i}\frac{\delta(A)^{\ell}}{\ell!}.$

Hence
$\lim_{n\to\infty}\delta\mathopen{}\mathclose{{}\left(A\wr_{I}\mathcal{S}_{n}}\right)=e^{\delta(A)-1}$,
and so
$\lim_{n,m\to\infty}\delta\mathopen{}\mathclose{{}\left(\mathcal{S}_{m}\wr_{I}\mathcal{S}_{n}}\right)=e^{e^{-1}-1}$.

###### Proof.

The first displayed formula follows from Theorem 5.1 since
$|\delta_{\ell}(\mathcal{S}_{n})|=d_{n-\ell}/\ell!$ by Corollary 3.2.
Interchanging summations gives the second formula. The first limit now
follows, and the second follows from
$\lim_{m\to\infty}\delta(\mathcal{S}_{m})=e^{-1}$ by Corollary 3.2. ∎

##  6 Wreath products $A\wr_{P}B$ with power action

Given $A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$, we study
$A\wr_{P}B$ acting with power action on the set $\Omega=[m]^{[n]}$. Recall
that the elements of $A\wr_{P}B$ are $(\alpha,b)$ with $\alpha\in A^{[n]}$ and
$b\in B$, and that we sometimes write $\alpha\in A^{[n]}$ and
$\omega\in\Omega$ as $\alpha=(\alpha_{1},\dots,\alpha_{n})$ and
$\omega=(\omega_{1},\dots,\omega_{n})$, respectively. Using (Pw), the element
$(\alpha,b)\in A\wr_{P}B$ acts on $\omega\in\Omega$ via

$\omega{(\alpha,b)}\colon[n]\to[m],\quad
y\mapsto\omega(yb^{-1}){\alpha(y{b^{-1}})}.$

We start with a brief discussion of the numbers
$\genfrac{[}{]}{0.0pt}{}{G}{\ell}$ defined in Section 2.1. If
$G=\mathcal{S}_{n}$, then
$\genfrac{[}{]}{0.0pt}{}{G}{\ell}=\genfrac{[}{]}{0.0pt}{}{n}{\ell}$ is the
(unsigned) Stirling number $\genfrac{[}{]}{0.0pt}{}{n}{\ell}$ of the first
kind, see [9, Section 6.1] for details. It is easy to see that for $n\geqslant
1$ and $G\leqslant\mathcal{S}_{n}$ we have

$\genfrac{[}{]}{0.0pt}{}{n}{1}=(n-1)!,\quad\genfrac{[}{]}{0.0pt}{}{n}{n-1}=\binom{n}{2},\quad\genfrac{[}{]}{0.0pt}{}{n}{n}=1\quad\text{and}\quad\sum_{\ell=0}^{n}\genfrac{[}{]}{0.0pt}{}{G}{\ell}=|G|.$

######  Example 6.1.

If $C_{n}=\langle(1,2,\dots,n)\rangle\leqslant\mathcal{S}_{n}$, then
$\genfrac{[}{]}{0.0pt}{}{C_{n}}{d}=\phi(n/d)$ if $d\mid n$, and $0$ otherwise,
where $\phi$ denotes Euler’s $\phi$-function, see [1, Lemma 5.6]: The disjoint
cycle decomposition of $(1,2,\dots,n)^{k}$ consists of $n/d$ cycles each of
length $d=\gcd(n,k)$. Such an element has order $n/d$, and there are
$\phi(n/d)$ such elements in $B$. In particular, $\sum_{d\mid n}\phi(n/d)=n$.

For $\mathcal{A}_{n}$, we observe an alternating behaviour:
$\genfrac{[}{]}{0.0pt}{}{\mathcal{A}_{n}}{\ell}=0$ if $\ell\not\equiv n\bmod
2$, and
$\genfrac{[}{]}{0.0pt}{}{\mathcal{A}_{n}}{\ell}=\genfrac{[}{]}{0.0pt}{}{n}{\ell}$
otherwise. This follows from the next lemma.

######  Lemma 6.2.

If $G\leqslant\mathcal{S}_{n}$, then
$\genfrac{[}{]}{0.0pt}{}{G}{\ell}=\genfrac{[}{]}{0.0pt}{}{G\,\cap\,\mathcal{A}_{n}}{\ell}$
if $\ell\equiv n\bmod 2$, and
$\genfrac{[}{]}{0.0pt}{}{G}{\ell}=\genfrac{[}{]}{0.0pt}{}{G\,\cap\,(\mathcal{S}_{n}\setminus\mathcal{A}_{n})}{\ell}$
otherwise.

###### Proof.

Let $g\in G$ have cycle decomposition $g=g_{1}\cdots g_{\ell}$. Note that
$|g_{1}|+\dots+|g_{\ell}|=n$, and $g_{i}$ has sign $-1$ if and only if
$|g_{i}|$ is even. We can assume $g_{1},\dots,g_{s}$ have sign $-1$ and
$g_{s+1},\dots,g_{\ell}$ have sign $1$, so $g\in\mathcal{A}_{n}$ if and only
if $s$ is even. The cycles $g_{1},\dots,g_{s}$ involve an even number
$e=|g_{1}|+\dots+|g_{s}|$ of points, and the remaining $\ell-s$ cycles involve
$n-e$ points. Each of $g_{s+1},\dots,g_{\ell}$ has odd length, which forces
$n-e\equiv\ell-s\bmod 2$. Thus, if $n\equiv\ell\bmod 2$, then $s\equiv e\equiv
0\bmod 2$, and $g\in\mathcal{A}_{n}$. If $n\not\equiv\ell\bmod 2$, then
$s\not\equiv e\equiv 0\bmod 2$, and
$g\in\mathcal{S}_{n}\setminus\mathcal{A}_{n}$. The claim now follows. ∎

In particular, if $G\leqslant\mathcal{S}_{n}$ but
$\mathcal{A}_{n}\not\leqslant G$, then $H=G\cap\mathcal{A}_{n}$ has index $2$
in $G$, which implies that half of all elements lie in $H$ (and these elements
all have cycle number congruent to $n$ modulo $2$) and the other half of
elements lie in $G\setminus H$ (and all these elements have cycle number
congruent to $n+1$ modulo $2$). This is summarised in the following lemma.

######  Lemma 6.3.

If $G\leqslant\mathcal{S}_{n}$ and $\mathcal{A}_{n}\not\leqslant G$, then
$\displaystyle\sum_{i=1}^{\lfloor
n/2\rfloor}\genfrac{[}{]}{0.0pt}{}{G}{2i}=\frac{|G|}{2}=\sum_{i=1}^{\lceil
n/2\rceil}\genfrac{[}{]}{0.0pt}{}{G}{2i-1}$.

###  6.1 Formula for $\delta_{k}(A\wr_{P}B)$ in Theorem 1.1

We start with a definition.

######  Definition 6.4.

Let $b\in\mathcal{S}_{n}$ have disjoint cycle decomposition $b=b_{1}\cdots
b_{\ell}$ (including trivial cycles) and let
$b_{i}=(y_{i},y_{i}b,\dots,y_{i}b^{k_{i}-1})$ be a $k_{i}$-cycle whose
smallest element is $y_{i}$. If $\alpha\in A^{[n]}$, then the _$b_{i}$
-product_ of $\alpha$ is
$b_{i}(\alpha)=\alpha({y_{i}})\alpha(y_{i}b)\cdots\alpha(y_{i}b^{k_{i}-1})\in
A$.

######  Theorem 6.5.

Let $G=A\wr_{P}B\leqslant\mathcal{S}_{m^{n}}$ where
$A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$.

  1. (a)

Let $b\in B$ with disjoint cycle decomposition $b=b_{1}\cdots b_{\ell}$. Then

$\delta_{k}(A^{[n]}b)=\sum_{j_{1}\cdots
j_{\ell}=k}\prod_{r=1}^{\ell}\delta_{j_{r}}(A);$

if $k=0$, then $\delta(A^{[n]}b)=1-(1-\delta(A))^{\ell}$.

  2. (b)

We have

$\delta_{k}(A\wr_{P}B)=\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}\sum_{j_{1}\cdots
j_{\ell}=k}\prod_{r=1}^{\ell}\delta_{j_{r}}(A);$

if $k=0$, then

$\delta(A\wr_{P}B)=1-\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}(1-\delta(A))^{\ell}.$

###### Proof.

(a) Suppose each cycle $b_{i}$ is defined as
$b_{i}=(y_{i},y_{i}b,\dots,y_{i}b^{k_{i}-1})$ where $y_{i}$ is the smallest
element in the cycle. Suppose $(\alpha,b)\in G$ fixes some $\omega\in\Omega$.
Then $\omega(yb^{-1})\alpha(yb^{-1})=\omega(y)$ for all $y\in[n]$ by (Pw).
Letting $y=y_{i}b^{j+1}$ shows that for each $i$ and $j$ we have

$\omega(y_{i}b^{j})\alpha(y_{i}b^{j})=\omega(y_{i}b^{j+1});$

in particular,
$\omega(y_{i})\alpha(y_{i})\alpha(y_{i}b)\cdots\alpha(y_{i}b^{k_{i}-1})=\omega(y_{i})$,
and so $\omega(y_{i})$ is a fixed point of $b_{i}(\alpha)$. Moreover, the
converse is true, and $\omega$ is a fixed point of $(\alpha,b)$ if and only if
each $\omega(y_{i})$ is a fixed point of $b_{i}(\alpha)$, and
$\omega(y_{i}b^{j+1})$ is defined as
$\omega(y_{i})\alpha(y_{i})\alpha(y_{i}b)\cdots\alpha(y_{i}b^{j})$. If the
fixed points of $b_{i}(\alpha)$ are $x_{i,1},\ldots,x_{i,j_{i}}$ (so
$b_{i}(\alpha)\in{\rm Fix}_{j_{i}}(A)$), then $(\alpha,b)$ has exactly
$j_{1}\cdots j_{\ell}$ fixed points. Thus, for $b$ as above, the number of
$\alpha\in A^{[n]}$ for which $(\alpha,b)$ has exactly $k$ fixed points is

$|{\rm Fix}_{k}(A^{[n]}b)|=\sum_{j_{1}\cdots j_{\ell}=k}|\\{\alpha\in
A^{[n]}\mid\text{ each
}b_{i}(\alpha)=\alpha(y_{i})\alpha(y_{i}b)\cdots\alpha(y_{i}b^{k_{i}-1})\in{\rm
Fix}_{j_{i}}(A)\\}|$

For each $i$, we have $b_{i}(\alpha)\in{\rm Fix}_{j_{i}}(A)$ if and only if
$\alpha(y_{i})=c(\alpha(y_{i}b)\cdots\alpha(y_{i}b^{k_{i}-1}))^{-1}$ where
$c\in{\rm Fix}_{j_{i}}(A)$ and
$\alpha(y_{i}b),\dots,\alpha(y_{i}b^{k_{i}-1})\in A$ are arbitrary. Thus,

$|{\rm Fix}_{k}(A^{[n]}b)|=\sum_{j_{1}\cdots
j_{\ell}=k}|A|^{n-\ell}\prod_{r=1}^{\ell}|{\rm Fix}_{j_{r}}(A)|,$

and dividing by $|A^{[n]}b|=|A|^{n}$ proves the first claim.

The claim for $k=0$ follows via induction on $\ell$. Indeed, if $\ell=1$, then
the claim is true by the above display. For $\ell>1$, we split the sum into
the cases $j_{1}=0$ and $j_{1}\neq 0$, giving

$\displaystyle\delta(A^{[n]}b)$
$\displaystyle=\delta(A)\sum_{j_{2},\dots,j_{\ell}\geqslant
0}\prod_{r=2}^{\ell}\delta_{j_{r}}(A)+\sum_{j_{1}=1}^{m}\sum_{j_{2}\cdots
j_{\ell}=0}\prod_{r=1}^{\ell}\delta_{j_{r}}(A).$

The first summand simplifies as follows

$\delta(A)\sum_{j_{2},\dots,j_{\ell}\geqslant
0}\prod_{r=2}^{\ell}\delta_{j_{r}}(A)=\delta(A)\prod_{r=2}^{\ell}\sum_{j_{r}=0}^{m}\delta_{j_{r}}(A)=\delta(A)\prod_{r=2}^{\ell}1=\delta(A)$

and the second summand simplifies as

$\sum_{j_{1}=1}^{m}\sum_{j_{2}\cdots
j_{\ell}=0}\prod_{r=1}^{\ell}\delta_{j_{r}}(A)=\sum_{j_{1}=1}^{n}\delta_{j_{1}}(A)\sum_{j_{2}\cdots
j_{\ell}=0}\prod_{r=2}^{\ell}\delta_{j_{r}}(A)=(1-\delta(A))\sum_{j_{2}\cdots
j_{\ell}=0}\prod_{r=2}^{\ell}\delta_{j_{r}}(A)$

with $\sum_{j_{2}\cdots
j_{\ell}=0}\prod_{r=2}^{\ell}\delta_{j_{r}}(A)=1-(1-\delta(A))^{\ell-1}$ by
the induction hypothesis. Together,

$\delta(A^{[n]}b)=\delta(A)+(1-\delta(A))(1-(1-\delta(A))^{\ell-1})=1-(1-\delta(A))^{\ell},$

as claimed.

(b) Observe that both formulas in (a) depend only on $k$, and the number
$\ell$ of cycles in the cycle decomposition of $b\in B$. Therefore

$\displaystyle|{\rm Fix}_{k}(A\wr_{P}B)|$
$\displaystyle=\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}|A|^{n}\sum_{j_{1}\cdots
j_{\ell}=k}\prod_{r=1}^{\ell}\delta_{j_{r}}(A),$

and dividing by $|A\wr_{P}B|=|A|^{n}|B|$ yields the first formula of (b). The
formula for $k=0$ also follows from (a) together with the fact that
$\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}=|B|$. ∎

######  Corollary 6.6.

If $A\leqslant\mathcal{S}_{m}$ and $B\leqslant\mathcal{S}_{n}$, then
$\delta_{1}(A\wr_{P}B)=\mathcal{C}_{B}(\delta_{1}(A))$ where
$\mathcal{C}_{B}(x)=\tfrac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}x^{\ell}$.

###  6.2 Derangements of $A\wr_{P}\mathcal{S}_{n}$

If $c_{n}(g)$ denotes the number of cycles of $g\in\mathcal{S}_{n}$, then the
formula of Theorem 2.1(b) can be written as

(4) $\delta(A\wr_{P}B)=1-\frac{1}{|B|}\sum_{b\in B}(1-\delta(A))^{c_{n}(b)}.$

For $B=C_{n}=\langle(1,2,\dots,n)\rangle\leqslant\mathcal{S}_{n}$, we obtain
the following by Example 6.1 and Theorem 2.1(b).

######  Corollary 6.7.

Let $A\leqslant\mathcal{S}_{m}$ and let $C_{n}\leqslant\mathcal{S}_{n}$ be
generated by an $n$-cycle. Then

$\delta(A\wr_{P}C_{n})=1-\frac{1}{n}\sum_{d\mid n}\phi(d)(1-\delta(A))^{n/d},$

where $\phi$ denotes Euler’s $\phi$-function.

######  Corollary 6.8.

If $m,n\geqslant 2$ and $A\leqslant\mathcal{S}_{m}$, then

$\delta(A\wr_{P}\mathcal{S}_{n})=1-\prod_{\ell=1}^{n}\mathopen{}\mathclose{{}\left(1-\frac{\delta(A)}{\ell}}\right)\quad\text{and
hence $\lim_{n\to\infty}\delta(A\wr_{P}\mathcal{S}_{n})=1$.}$

We have $1-\frac{1}{n^{\delta(A)}}\leqslant\delta(A\wr_{P}\mathcal{S}_{n})$,
and if $A\leqslant\mathcal{S}_{m}$ is 2-transitive, then
$\delta(A\wr_{P}\mathcal{S}_{n})\leqslant 1-\frac{1}{n+1}$.

###### Proof.

Let $A\wr_{P}\mathcal{S}_{n}$ act on $[m]^{[n]}$ via (Pw). The identity
$\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{n}{\ell}x^{\ell}=\prod_{\ell=1}^{n}(x+\ell-1)$,
see [9, Table 264], and Theorem 2.1(b) yield

$\displaystyle\delta(A\wr_{P}\mathcal{S}_{n})$
$\displaystyle=1-\frac{1}{|\mathcal{S}_{n}|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{\mathcal{S}_{n}}{\ell}(1-\delta(A))^{\ell}=1-\frac{1}{n!}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{n}{\ell}(1-\delta(A))^{\ell}$
$\displaystyle=1-\prod_{\ell=1}^{n}\frac{(1-\delta(A))+\ell-1}{\ell}=1-\prod_{\ell=1}^{n}\mathopen{}\mathclose{{}\left(1-\frac{\delta(A)}{\ell}}\right).$

This proves the first claim. Moreover,
$\lim_{n\to\infty}\delta(A\wr_{P}\mathcal{S}_{n})=1$ follows from
$\prod_{\ell=1}^{\infty}\mathopen{}\mathclose{{}\left(1-\frac{\delta(A)}{\ell}}\right)=0$,
which is a consequence of $\sum_{\ell=1}^{\infty}\delta(A)/\ell=\infty$, see
[13, Theorem 2.2.2].

We now bound $\delta(A\wr_{P}\mathcal{S}_{n})$. It follows from [13, Eq.
(2.2.2)] that $1-\prod_{\ell=1}^{n}(1-\frac{\delta(A)}{\ell})\geqslant
1-e^{-\delta(A)H_{n}}$ where $H_{n}=\sum_{\ell=1}^{n}\frac{1}{\ell}$. Now
$H_{n}>\log(n)$ yields
$1-\prod_{\ell=1}^{n}(1-\frac{\delta(A)}{\ell})\geqslant
1-e^{-\delta(A)\log(n)}=1-n^{-\delta(A)}$, as desired. For the last claim, let
$A\leqslant\mathcal{S}_{m}$ be 2-transitive. By (1), it suffices to show that
$G=A\wr_{P}\mathcal{S}_{n}$ has rank $r=n+1$. We sketch a proof of this fact.
Let $C$ be the stabiliser in $A$ of the point $m$. Then $|A:C|=m$ and hence
the stabiliser of the point $[m,m,\dots,m]\in[m]^{[n]}$ is
$D=C\wr_{P}\mathcal{S}_{n}$. Since $|G:D|=m^{n}$ we see that $G$ is transitive
on $[m]^{[n]}$. Consider the orbits of $D$ on $[m]^{[n]}$. If
$\omega=(\omega_{1},\dots,\omega_{n})\in[m]^{[n]}$, then by 2-transitivity we
may choose $\gamma\in C^{[n]}$ such that $\omega_{i}\gamma_{i}=m$ if
$\omega_{i}=m$, and $\omega_{i}\gamma_{i}=1$ otherwise, for every $i\in[n]$.
If $\omega_{i}=m$ for exactly $j$ indices $i\in[n]$, then we may choose
$(\gamma,b)\in C\wr_{P}\mathcal{S}_{n}$ such that
$\omega(\gamma,b)=(1,\dots,1,m,\dots,m)$ with exactly $j$ copies of $m$ and
$n-j$ copies of $1$. Thus, there are $n+1$ orbits in $[m]^{[n]}$ under the
action of $D$, one for each $j\in\\{0,1,\dots,n\\}$, and therefore $G$ has
rank $n+1$, as claimed. ∎

######  Remark 6.9.

The proof of Corollary 6.8 can be modified to prove that
$\lim_{n\to\infty}\delta(A\wr_{P}\mathcal{A}_{n})=1$ for all
$A\leqslant\mathcal{S}_{m}$ with $m\geqslant 2$ by using
$\genfrac{[}{]}{0.0pt}{}{n}{\ell}=\genfrac{[}{]}{0.0pt}{}{\mathcal{S}_{n}}{\ell}\geqslant\genfrac{[}{]}{0.0pt}{}{\mathcal{A}_{n}}{\ell}$
in the above display.

###  6.3 Density in $[\delta(A),1]$: proof of Theorem 1.3

We now prove Theorem 1.3.

###### Proof of Theorem 1.3.

Suppose first that $B\leqslant\mathcal{S}_{n}$ is fixed. Theorem 2.1(b) yields
$\delta(A\wr_{P}B)=f(\delta(A))$ where $f(x)=1-\mathcal{C}_{B}(1-x)$. Since
$\mathcal{C}_{B}(x)$ is continuous and increasing on $[0,1]$, the same is true
for $f(x)$. The set $\\{\delta(A)\mid\textup{$A$ is primitive}\\}$ is dense in
$[0,1]$ by Theorem 2.1(c), so the same is true for the set
$\\{f(\delta(A))\mid\textup{$A$ is primitive}\\}$. This proves the first claim
as $f(0)=0$ and $f(1)=1$.

Suppose next that $A\leqslant\mathcal{S}_{m}$ is fixed. For each
$B\leqslant\mathcal{S}_{n}$ we have
$\mathcal{C}_{B}(x)\leqslant\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}x=x$
for $x\in[0,1]$. It follows from $0\leqslant\mathcal{C}_{B}(x)\leqslant
x\leqslant 1$ that $0\leqslant x\leqslant 1-\mathcal{C}_{B}(1-x)\leqslant 1$
and hence by Theorem 2.1(b) that
$\delta(A\wr_{P}B)=1-\mathcal{C}_{B}(1-\delta(A))\geqslant\delta(A)$.

Let $p_{1}<p_{2}<\cdots$ be a sequence of primes. Set $n=p_{1}\cdots p_{r}$
and let $Z_{r}$ be the cyclic and regular subgroup
$Z_{r}\leqslant\mathcal{S}_{n}$ generated by an $n$-cycle. Let
$z=1-\delta(A)$. When $r=1$, and $n=p_{1}$ we have

$\frac{1}{n}\sum_{d\mid
n}\phi(d)z^{n/d}=\mathopen{}\mathclose{{}\left(1-\frac{1}{p_{1}}}\right)z+\frac{1}{p_{1}}z^{p_{1}},$

by Example 6.1. Since $0<z\leqslant 1$, Corollary 6.7 shows that

$\lim_{p_{1}\to\infty}\delta(A\wr_{P}Z_{1})=\lim_{p_{1}\to\infty}\mathopen{}\mathclose{{}\left(1-\mathopen{}\mathclose{{}\left(1-\frac{1}{p_{1}}}\right)z-\frac{1}{p_{1}}z^{p_{1}}}\right)=1-z=\delta(A).$

Let $q=p_{r+1}$ be a prime with $p_{r}<q$. We consider
$Z_{r}\leqslant\mathcal{S}_{n}$ and $Z_{r+1}\leqslant\mathcal{S}_{nq}$ where
$n=p_{1}\cdots p_{r}$ and calculate the difference
$|\delta(A\wr_{P}Z_{r+1})-\delta(A\wr_{P}Z_{r})|$. Since
$\phi(nq)=(q-1)\phi(n)$, Corollary 6.7 shows the following

$\displaystyle\delta(A\wr_{P}Z_{r+1})$
$\displaystyle=1-\frac{1}{nq}\mathopen{}\mathclose{{}\left(\sum_{d\mid
n}\phi(d)z^{nq/d}+\sum_{d\mid n}\phi(dq)z^{nq/dq}}\right)$
$\displaystyle=1-\frac{1}{nq}\mathopen{}\mathclose{{}\left(\sum_{d\mid
n}\phi(d)z^{n/d}\mathopen{}\mathclose{{}\left((z^{n/d})^{q-1}+(q-1)}\right)}\right)=\delta(A\wr_{P}Z_{r})+D(n,q),$

where

$D(n,q)=\frac{1}{nq}\mathopen{}\mathclose{{}\left(\sum_{d\mid
n}\phi(d)z^{n/d}\mathopen{}\mathclose{{}\left(1-(z^{n/d})^{q-1}}\right)}\right).$

Since $0<1-(z^{n/d})^{q-1}<1$ we have
$0<D(n,q)<\frac{1}{q}\delta(A\wr_{P}Z_{r})$, and so $D(n,q)\to 0$ as
$q\to\infty$. In conclusion, the sequence $(\delta(A\wr_{P}Z_{r}))_{r\geqslant
1}$ is strictly increasing and can be arranged to start arbitrarily close to
$\delta(A)$ with arbitrarily small step size $D(n,q)$.

It remains to show that this sequence converges to $1$. We focus on $Z_{r}$
and for $\Delta\subseteq[r]$ define $p(\Delta)=\prod_{i\in\Delta}p_{i}$ and
$\Delta^{\prime}=[r]\setminus\Delta$. Since
$p([r])=p(\Delta)p(\Delta^{\prime})=n$, we have

$\displaystyle\delta(A\wr_{P}Z_{r})$ $\displaystyle=1-\frac{1}{n}\sum_{d\mid
n}\phi(d)z^{n/d}=1-\frac{1}{p([r])}\sum_{\Delta\subseteq[r]}\phi(p({\Delta}))z^{p({\Delta^{\prime}})}$
$\displaystyle=1-\frac{\phi(p([r]))}{p([r])}z-\sum_{\Delta\subseteq[r]\atop\Delta\neq[r]}\frac{\phi(p({\Delta}))}{p({\Delta})}\frac{z^{p({\Delta^{\prime}})}}{p({\Delta^{\prime}})}$
$\displaystyle\geqslant
1-\prod_{i=1}^{r}\mathopen{}\mathclose{{}\left(1-\frac{1}{p_{i}}}\right)z-\sum_{\Delta\subseteq[r]\atop\Delta\neq[r]}\frac{z^{p({\Delta^{\prime}})}}{p({\Delta^{\prime}})}>1-\prod_{i=1}^{r}\mathopen{}\mathclose{{}\left(1-\frac{1}{p_{i}}}\right)z-\sum_{i\geqslant
p_{1}}\frac{z^{i}}{i}.$

The Taylor series $\sum_{i=1}^{\infty}z^{i}/i$ converges to $-\log(1-z)$ since
$|z|<1$. Thus, for any given $\varepsilon>0$ we can choose $p_{1}$ large
enough so that $\sum_{i\geqslant p_{1}}z^{i}/i<\varepsilon/2$. Moreover,
$\prod_{p\text{ prime}}(1-\frac{1}{p})$ diverges to $0$ by [13, Theorem 2.2.2]
since $\sum_{p\text{ prime}}1/p$ diverges. Thus, we can choose $r$ large
enough so that
$\prod_{i=1}^{r}\mathopen{}\mathclose{{}\left(1-\frac{1}{p_{i}}}\right)<\varepsilon/2z$.
The claim now follows from

$\delta(A\wr_{P}Z_{r})>1-\frac{\varepsilon}{2z}z-\frac{\varepsilon}{2}=1-\varepsilon.\qed$

###  6.4 Proof of Theorem 1.4

###### Proof of Theorem 1.4.

Let $T$ be a transversal for $C$ in $A$, and write $\mathcal{T}=T^{[n]}$.
Every element in $G$ can be written as $(\beta\tau,b)$ where $\beta\in
C^{[n]}$, $\tau\in\mathcal{T}$, and $b\in B$. We fix $(\tau,b)$ and determine
the proportion $\delta(C^{[n]}(\tau,b))$. Write
$\tau=(\tau_{1},\dots,\tau_{n})$ and let $b=b_{1}\cdots b_{\ell}$ be the
disjoint cycle decomposition of $b$. Let

$D_{\tau}(b)=D_{\tau}(b_{1})\cup\cdots\cup
D_{\tau}(b_{\ell})\quad\textup{where}\quad D_{\tau}(b_{i})=\\{\alpha\in
C^{[n]}\mid b_{i}(\alpha\tau)\in\mathrm{Der}(\mathcal{S}_{m})\\}$

with $b_{i}(\alpha\tau)$ as in Definition 6.4. Arguing as in the proof of
Theorem 6.5(a), the number of $\alpha\in C^{[n]}$ for which $(\alpha\tau,b)$
is a derangement is $|D_{\tau}(b)|$. Before computing this number via
inclusion-exclusion, we focus on one of the cycles $b_{i}$ and count
$|D_{\tau}(b_{i})|$. To simplify notation, we conjugate by an element of
$\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}$ (which preserves derangements and non-
derangements), so we can assume that $b_{i}=(1,2,\dots,k_{i})$. The
$b_{i}$-product of $\alpha\tau$ now is

$b_{i}(\alpha\tau)=\alpha_{1}\tau_{1}\alpha_{2}\tau_{2}\cdots\alpha_{k_{i}}\tau_{k_{i}}=\alpha_{1}\mathopen{}\mathclose{{}\left(\alpha_{2}^{\tau_{1}^{-1}}\alpha_{3}^{(\tau_{1}\tau_{2})^{-1}}\cdots\alpha_{k_{i}}^{(\tau_{1}\cdots\tau_{k_{i}})^{-1}}}\right)\tau_{1}\tau_{2}\cdots\tau_{k_{i}},$

which is a derangement in $C\tau_{1}\cdots\tau_{k_{i}}$ if and only if
$\alpha_{1}=x\mathopen{}\mathclose{{}\left(\alpha_{2}^{\tau_{1}^{-1}}\alpha_{3}^{(\tau_{1}\tau_{2})^{-1}}\cdots\alpha_{k_{i}}^{(\tau_{1}\cdots\tau_{k_{i}})^{-1}}}\right)^{-1}$
with $x\in C$ such that
$x\tau_{1}\cdots\tau_{k_{i}}\in\mathrm{Der}(C\tau_{1}\cdots\tau_{k_{i}})$ and
$\alpha_{j}\in C$ for each $j\in[n]\setminus\\{1\\}$. Since
$b_{i}(\tau)=\tau_{1}\cdots\tau_{k_{i}}$, we have
$|\mathrm{Der}_{\tau}(b_{i})|=|\mathrm{Der}(C^{[n]}(\tau,b_{i}))|=|\mathrm{Der}(Cb_{i}(\tau))||C|^{n-1}$,
and our assumptions imply that

$|C|^{n}\delta_{L}\leqslant|D_{\tau}(b_{i})|\leqslant|C|^{n}\delta_{U}.$

More generally, when $i_{1},\dots,i_{j}$ are distinct elements of $[\ell]$, we
have

$|D_{\tau}(b_{i_{1}})\cap\dots\cap
D_{\tau}(b_{i_{j}})|=\mathopen{}\mathclose{{}\left(\prod_{j=1}^{j}|\mathrm{Der}(Cb_{i}(\tau))|}\right)|C|^{n-j},$

and hence $|C|^{n}\delta_{U}^{j}\leqslant|D_{\tau}(b_{i_{1}})\cap\dots\cap
D_{\tau}(b_{i_{j}})|\leqslant|C|^{n}\delta_{U}^{j}$. Inclusion-exclusion now
gives

$\displaystyle|\mathrm{Der}(C^{[n]}(\tau,b))|=\mathopen{}\mathclose{{}\left|\bigcup_{i=1}^{\ell}D_{\tau}(b_{i})}\right|$
$\displaystyle=\sum_{j=1}^{\ell}(-1)^{j-1}\sum_{1\leqslant
i_{1}<\dots<i_{j}\leqslant\ell}|D_{\tau}(b_{i_{1}})\cap\dots\cap
D_{\tau}(b_{i_{j}})|$
$\displaystyle\geqslant\sum_{j=1}^{\ell}(-1)^{j-1}\sum_{1\leqslant
i_{1}<\dots<i_{j}\leqslant\ell}|C|^{n}\delta_{L}^{j}$
$\displaystyle=1-\sum_{j=0}^{\ell}|C|^{n}\binom{\ell}{j}(-\delta_{L})^{j}=1-(1-\delta_{L})^{\ell}.$

Together with the analogous calculation for the upper bound, this yields

$1-(1-\delta_{L})^{\ell}\leqslant\frac{1}{|C|^{n}}|\mathrm{Der}(C^{[n]}(\tau,b))|\leqslant
1-(1-\delta_{U})^{\ell}.$

This is true for every coset $C^{[n]}(\tau,b)$ in $G$ where $b$ has exactly
$\ell$ cycles.

Recall that $\pi\colon\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}\to\mathcal{S}_{n}$
is the projection map, and that $\pi(G)=B\leqslant\mathcal{S}_{n}$ by
assumption. The kernel of the restriction of $\pi$ to $G$ is the normal
subgroup $U=G\cap\mathcal{S}_{m}^{[n]}=G\cap A^{[n]}$. In particular,
$G/U\cong B$ by the Isomorphism Theorem. By assumption,
$C^{[n]}\trianglelefteqslant U$. It follows that for every $b\in B$ there
exist $|U|$ elements in $G$ of the form $(\beta,b)$ with $\beta\in A^{[n]}$.
Moreover, there exist $|U|/|C|^{n}$ coset representatives of $C^{[n]}$ in $G$
of this form. Thus, together, we have the following lower bound; the upper
bound follows analogously:

$\displaystyle\delta(G)$
$\displaystyle\geqslant\frac{1}{|G|}\sum_{\ell=1}^{n}\frac{|U|}{|C|^{n}}\genfrac{[}{]}{0.0pt}{}{B}{\ell}|C|^{n}(1-(1-\delta_{L})^{\ell})=\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}(1-(1-\delta_{L})^{\ell})=1-\mathcal{C}_{B}(1-\delta_{L}).\qed$

######  Corollary 6.10.

Fix $n\geqslant 2$ and let $G_{1},G_{2},\dots$ be a sequence of subgroups
where each $G_{m}$ satisfies $\mathcal{A}_{m}^{[n]}\trianglelefteqslant
G_{m}\leqslant\mathcal{S}_{m}\wr_{P}\mathcal{S}_{n}$ and
$\pi_{n}(G_{m})=B\leqslant\mathcal{S}_{n}$ is independent of $m$. Then

$\lim_{m\to\infty}\delta(G_{m})=1-\frac{1}{|B|}\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}(1-e^{-1})^{\ell}>e^{-1}.$

###### Proof.

The first equality follows from Theorem 1.4 by choosing $C=\mathcal{A}_{m}$
and $A=\mathcal{S}_{m}$, and the observation that
$\lim_{m\to\infty}\delta(\mathcal{A}_{m})=\lim_{m\to\infty}\delta(\mathcal{S}_{m}\setminus\mathcal{A}_{m})=e^{-1}$
by Corollary 3.2. The second equality follows by estimating
$\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}(1-e^{-1})^{\ell}<\sum_{\ell=1}^{n}\genfrac{[}{]}{0.0pt}{}{B}{\ell}(1-e^{-1})=(1-e^{-1})|B|$.
∎

## References

  * [1] N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. L. Walker, D. T. Ose, and D. A. Jackson. The proportion of fixed-point-free elements of a transitive permutation group. _Comm. Algebra_ 21 (1993), 3259–3275.
  * [2] P. J. Cameron and A. M. Cohen. On the number of fixed point free elements in a permutation group. _Discrete Math._ 106/107 (1992), 135–138.
  * [3] P. J. Cameron, D. A. Gewurz, and F. Merola. Product action. _Discrete Math._ 308 (2008), 386–394.
  * [4] P. Diaconis, J. Fulman, and R. Guralnick. On fixed points of permutations. _J. Algebraic Combin._ 28 (2008), 189–218.
  * [5] J. D. Dixon and B. Mortimer. _Permutation groups._ Graduate Texts in Mathematics, 163. Springer-Verlag, New York, 1996.
  * [6] H. Duyan, Z. Halasi, and A. Maróti. A proof of Pyber’s base size conjecture. _Adv. Math._ 331 (2018), 720–747.
  * [7] J. Fulman and R. Guralnick. Derangements in simple and primitive groups. _Groups, combinatorics and geometry_ (Durham, 2001), 99–121, World Sci. Publ., River Edge, NJ, 2003.
  * [8] J. Fulman and R. Guralnick. Derangements in finite classical groups for actions related to extension field and imprimitive subgroups and the solution of the Boston-Shalev conjecture. _Trans. Amer. Math. Soc._ 370 (2018), 4601–4622.
  * [9] R. L. Graham, D. E. Knuth, and O. Patashnik. _Concrete mathematics. A foundation for computer science._ Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1989.
  * [10] M. W. Liebeck. On minimal degrees and base sizes of primitive permutation groups. _Arch. Math._ (Basel) 43 (1984) 11–15.
  * [11] Martin W. Liebeck, Cheryl E. Praeger, Jan Saxl. On the O’Nan-Scott theorem for finite primitive permutation groups. _J. Austral. Math. Soc. Ser._ A 44 (1988), no. 3, 389–396.
  * [12] M. W. Liebeck and J. Saxl. Minimal degrees of primitive permutation groups, with an application to monodromy groups of covers of Riemann surfaces. _Proc. London Math. Soc._ (3) 63 (1991) 266–314.
  * [13] C. H. C. Little, K. L. Teo and B. van Brunt. _An introduction to infinite products._ Springer Undergraduate Mathematics Series. Springer, Cham, 2022.
  * [14] A. Maróti. On the orders of primitive groups. _J. Algebra_ 258 (2002), no. 2, 631–640.
  * [15] E. M. Palmer and R. W. Robinson. Enumeration under two representations of the wreath product. _Acta Math._ 131 (1973), 123–143.
  * [16] B. Poonen and K. Slavov. The proportion of derangements characterises the symmetric and alternating groups (2021). arxiv.org/pdf/2107.02724
  * [17] Friedrich Rober. WPE, Provides efficient methods for working with wreath product elements, Version 0.5 (2022), GAP package. https://FriedrichRober.github.io/WPE/
  * [18] Á. Seress. _Permutation group algorithms_. Cambridge University Press, Cambridge, 2003.
  * [19] J.-P. Serre. On a theorem of Jordan. _Bull. Amer. Math. Soc._ 40 (2003), 429–440.