\section{Introduction}

The theory of the cycle type of
random permutations of the symmetric group $\ensuremath{\mathcal{S}}_n$
is very active, with many applications in combinatorics, group theory
and number theory.  A selection of applications includes
\begin{itemize}
\item The distribution of orders of permutations
(the least common multiple of cycle lengths)
\cite{equalorders, BGHP, BLGNPS, CHM, ET1, ET2, ET3, ET4, ET5, ET6, ET7, GS,Landau-perm,Massias,Nicolas,NP,NP2} and \cite[Sec. 6]{granville};
\item Invariable generation of the symmetric group
\cite{EFG2, LP, PPR} and other classical 
groups \cite{McK};
\item The distribution of fixed sets (divisors)
of permutations \cite{dfg08, EFG1, EFG2, EFK, FGK, LP, weingartner};
\item Permutations contained in transitive subgroups
\cite{Jordan, camkan, EFK};
\item Irreducibility of polynomials over the rationals
\cite{BSK, BSKK};
\item permutation groups containing elements with a single
cycle that is not a fixed point (Jordan groups) \cite{Jordan, GPU}
and \cite[Ch. 10]{Seress};
\item Polynomial factorization in finite fields
\cite{ABT, BSK, Rudnick19}
\end{itemize}

The main purpose of this paper is provide a standard reference for fundamental distributional results
about cycle types, which heretofore have been scattered across many papers.
We also showcase methods which are both
\emph{general} and \emph{combinatorial}.    
While many of the results stated here are weaker than existing results
in the literature, they are far more general,
have significantly shorter proofs and are more adaptable to new situations.
This paper is an expanded version of portions of the author's lecture notes 
on permutations prepared for the course ``Anatomy of integers and random permutations'' in 2017.

Our methods are borrowed from the
theory of numbers, particularly the theory of sieves
and the theory of averages of multiplicative functions
(see \cite[Part 3, Part 4]{Koubook} for uses in number theory).
As positive integers factor uniquely into a product of prime numbers,
and permutations factor uniquely into a product of cycles,
the connection between the distributions of the two objects
(prime factors and cycles) is not surprising.
There are significant differences, however, 
which explains why there is no simple \emph{tranference principle}
between the two objects. 
 Deeper inspection, however, reveals that
the \emph{distribution} of the two factorizations have many common features,
and for much the same underlying reasons.

Let $\sigma$ denote a random permutation from
the symmetric group $\ensuremath{\mathcal{S}}_n$, each permutation being equally
likely\footnote{Random permutations sampled
from certain other distributions have been studied, e.g. \cite{ABTbook}, but we will not discuss these here.}.
We denote by $\mathbb P_n$ and ${\mathbb E}\,_n$ the probability and expectation
with respect to a uniform random $\sigma\in \ensuremath{\mathcal{S}}_n$.
Often, the subscript $n$ will be omitted if it is clear from the context.
We denote the type (or cycle type) of $\sigma$ by
\[
(C_1(\sigma), C_2(\sigma),\ldots, C_n(\sigma)),
\]
where
$C_j(\sigma)$ is the number of cycles of length $j$ in $\sigma$.
More generally, for any subset $I$ of $[n]=\{1,\ldots,n\}$, we let $C_I(\sigma)$
be the number of cycles whose lengths lie in the set $I$.
For brevity, we write $C(\sigma)$ for the total number of
cycles in $\sigma$.
The principal problems considered in this paper are
\begin{itemize}
\item[(a)] What is the distribution of $C_j(\sigma)$ for each $j$?
\item[(b)] What is the distribution of $C_I(\sigma)$ for each $I$?
\item[(c)] What is the joint distribution of $C_{I_1}(\sigma),
\ldots,C_{I_k}(\sigma)$ for disjoint sets $I_1,\ldots,I_k\subseteq [n]$?
\item[(d)] What is the distribution of $C_I(\sigma)$
conditional on $C(\sigma)=k$?
\end{itemize}

Most of the analysis of these problems in the literature utilize
recurrence relations, properties of Stirling numbers, or by
complex analytic methods
starting with the exponential generating function of Gruder
\cite[Satz 2]{Gruder} for permutations having only cycle sizes from a set $I$.

\begin{thm}[Gruder]\label{thm:genfcn}
For real $|x|<1$, real $y$ and subset $I\subseteq {\mathbb N}$ we have
\begin{equation}\label{genfcn}
\sum_k \sum_n \mathbb P_n \big(C_I(\sigma)=k,C_{[n]\setminus I}(\sigma)=0\big) x^n y^k=
\exp \bigg\{ y \sum_{m\in I} \frac{x^m}{m}
\bigg\}.
\end{equation}
Moreover, when $I$ is finite the above identity holds for every real $x$.
\end{thm}

While many existing distribution theorems are very strong,
particularly the recent results
of   Manstavi\v{c}ius and Petuchovas
 \cite{ManPet16, ManPet17, Pet16, Pet18},
the methods are highly specialized and not easily adaptable to the solution of related problems.
By contrast, 
we eschew recurrences and generating functions
(for the most part) in favor of direct arguments.
We focus on
\emph{quantitative} results, that is, with a specific rate
of convergence, as well as results which are \emph{uniform}
in $j,I$ and the sets $I_j$.  

Underlying our analysis is the
\emph{Poisson model} of permutations, which states that
$C_j(\sigma)$ is approximately Poisson with parameter $1/j$,
an that $C_1(\sigma), C_2(\sigma), \ldots$ are quasi-independent.
This is already hinted at in Cauchy's classical formula:

\begin{thm}[Cauchy]\label{thm:Cauchy}
If $m_1+2m_2+\cdots+nm_n=n$, then
\[
\mathbb P_n \big( C_1(\sigma)=m_1,\ldots,C_n(\sigma)=m_n \big) = \prod_{j=1}^n \frac{(1/j)^{m_j}}{m_j!},
\]
\end{thm}

If  $X_1, X_2, \ldots, X_k$ are independent Poisson random variables 
with parameters $\lambda_1,\ldots,\lambda_k$ ,respectively, then the sum
$X_1+\cdots +X_k$ is Poisson with parameter $\lambda_1+\cdots+\lambda_k$.
Thus, for subsets $I$ of $[n]$ we should expect that $C_I(\sigma)$ will be roughly 
Poisson with parameter 
\[
H(I) := \sum_{j\in I} \frac{1}{j}.
\]
In the important special case $I=\{1,\ldots,n\}$ we set 
\[
H_n = \sum_{i=1}^n \frac{1}{i}.
\]
The Poisson model has limitations, however,
particularly if $I$ contains many large elements.
For example the events
``$C_j(\sigma)\ge 1$'', $n/2<j\le n$, are clearly disjoint.
Also, if $I=\{2,\ldots,n\}$, then $\mathbb P (C_I(\sigma)=0) = 1/n!$
whereas the Poisson model predicts a probability
of about $\mathrm{e}^{-H(I)} \approx 1/n$.
In general, permutations lacking large cycles are much rarer than would be 
predicted by the Poisson model, these being analogous to integers
lacking large prime factors.  We will take up this subject again later,
e.g. Theorem \ref{nolargecycles}.
On the other hand, we shall see that the Poisson model is very accurate for
small $j$, and is reasonably accurate for large $j$ on average
near the center of the distribution.



\subsection{Notational conventions.}
We adopt the standard Bachman-Landau, Hardy, and Vinogradov notations:
$f=O(g)$ and $f\ll g$ mean that there is a positive constant $C$
so that $|f| \le Cg$ throughout the domain of $f$.  The constant $C$ is independent of any parameters, unless specified by subscripts, e.g.
$f(x)=O_{\ensuremath{\varepsilon}} (x^\ensuremath{\varepsilon})$.
Also, $f \sim g$ as $x\to \infty$ means $\lim_{x\to \infty} f(x)/g(x)=1$.  


\subsection{Binomial moments and local limit laws.}
A great deal of our analysis ultimately relies on
estimates for joint binomial moments of the quantities
$C_I(\sigma)$.  Recall that if $X$
is Poisson with parameter $\lambda$,
then for any non-negative integer $m$,
\[
{\mathbb E}\, \binom{X}{m} = 
\sum_{k=0}^\infty \binom{k}{m} \mathrm{e}^{-\lambda} \frac{\lambda^k}{k!}= \frac{\lambda^m}{m!}.
\]
We establish an analog for joint binomial moments of the statistics
$C_{I_j}(\sigma)$ for disjoint $I_1,\ldots,I_k$.

\begin{thm}\label{cycles_sets_expectation}
Let $I_1,I_2, \ldots, I_k$ be disjoint subsets of $[n]$, and let
$m_1,\ldots,m_k$ be non-negative integers.  Then
\[
{\mathbb E}\, \binom{C_{I_1}(\sigma)}{m_1} \cdots \binom{C_{I_k}(\sigma)}{m_k} \le \prod_{j=1}^k \frac{H(I_j)^{m_j}}{m_j!},
\]
with equality if and only if $\sum_{j=1}^k m_j \max(I_j) \le n$.
\end{thm}

One quick application of Theorem \ref{cycles_sets_expectation}
is to the Local limit laws for $C_j(\sigma)$ of
Goncharov \cite{Gon44}.

\begin{thm}[Goncharov]\label{thm:Goncharov}
For any $n\in {\mathbb N}$, $1\le j\le n$ and $0\le m\le n/j$, we have
\[
\mathbb P \( C_j(\sigma)=m \) = \frac{(1/j)^m}{m!} \sum_{h=0}^{\fl{n/j}-m}  \frac{(-1/j)^h}{h!}, \quad (1\le j\le n, 0\le m\le n/j).
\]
\end{thm}

A special case is the
very classical \emph{derangement problem}, posed in 1708 by  Pierre Raymond de Montmort.
Taking $j=1$ we have the exact formula for derangements
\[
\mathbb P(C_1(\sigma)=0 ) = \sum_{j=0}^n \frac{(-1)^j}{j!}.
\]
Observe that if $j,m$ vary with $n$ such that 
$mj\le n$ and that
either $j\to \infty$ or $\frac{n}{j}-m\to \infty$ then
\[
\lim_{n\to \infty} \frac{\mathbb P_n \( C_j(\sigma)=m \)}{e^{-1/j} (1/j)^m/{m!}} =1.
\]
This establishes the Poisson distribution of $C_j(\sigma)$ in this range.

Theorem \ref{thm:Goncharov} can be thought of as a permutation analog of Landau's \cite[p. 211]{Landau} classical theorem in number theory, which states that
number of integers $n\le x$ 
having exactly $k$ distinct prime factors is asymptotic to
\[
\frac{x}{\log x}\; \frac{(\log_2 x)^{k-1}}{(k-1)!}
\]
as $x\to\infty$.

Here we derive a very general local limit law.  In such generality,
we only obtain an upper bound for the probability
 of the expected order.  Lower bounds
are also possible, as are asymptotic formulae, when 
working with small cycle lengths; see Theorem \ref{Poisson_smallcycles} below.
The behavior of $\mathbb P(C_I(\sigma)=0)$ when $I=\{m+1,\ldots,n\}$
is very different  than Poisson model prediction
and will be dealt with separately.

\begin{thm}\label{cycles_sets}
Let $I_1,\ldots,I_r$ be arbitrary disjoint, nonempty subsets of $[n]$ and $m_1,\ldots,m_r\ge 0$.  Then
\[
\mathbb P\big( C_{I_1}(\sigma)=m_1,\ldots,C_{I_r}(\sigma)=m_r \big) \le \frac{\mathrm{e}^{H_n}}{n} \, \prod_{j=1}^r \Bigg( \frac{H(I_j)^{m_j}}{m_j!} \mathrm{e}^{-H(I_j)}\Bigg) \cdot \(\ensuremath{\varepsilon}+\frac{m_1}{H(I_1)}+\cdots+\frac{m_r}{H(I_r)}\),
\]
where $\ensuremath{\varepsilon}=0$ if $[n]=I_1\cup \cdots \cup I_r$ and $\ensuremath{\varepsilon}=1$
otherwise.
\end{thm}

The analog of Theorem \ref{cycles_sets} for prime factors of a random integer $n\le x$ was proved by the author \cite{primepoisson}.  We note that $H_n \le \log n + 1$
for all $n$, thus the factor $\mathrm{e}^{H_n}/n$ is  bounded.
Consequently, whenever $r$ is bounded and $m_j = O(H(I_j))$ for each $j$,
the right side is 
\[
O\big( \mathbb P (Y_1=m_1,\ldots,Y_r=m_r) \big),
\] 
where for each $i$, $Y_i$ is Poisson with parameter $H(I_i)$,
and $Y_1,\ldots,Y_r$ are independent.
Thus, Theorem \ref{cycles_sets} gives an upper bound for counts of 
cycle lengths in sets $I_1,\ldots,I_r$ of the expected order (up to 
a constant factor) according to the Poisson model.   As a special case of one set $I_1=I$, we
obtain:

\begin{cor}\label{cycles-single-set}
For any $I\subset [n]$ and $m\ge 0$,
\[
\mathbb P\( C_{I}(\sigma)=m \) \le \frac{\mathrm{e}^{H_n-H(I)}}{n} \cdot \frac{H(I)^m}{m!}
\Bigg( \one(I\ne [n]) + \frac{m}{H(I)} \Bigg).
\]
In particular,
\[
\mathbb P( C_I(\sigma)=0 ) \le \frac{\mathrm{e}^{H_n-H(I)}}{n} = \mathrm{e}^{\gamma-H(I)}(1+O(1/n)).
\]
\end{cor}

The first estimate is asymptotically sharp in the case $I=[n]$
and $m=o(\log n)$ as $n\to \infty$; see \eqref{lower-smallk} below 
for a corresponding lower bound.

A slight improvement of the final estimate,
$\mathbb P(C_I(\sigma)=0) \le \mathrm{e}^{\gamma-H(I)}$,
is given in \cite{GPU} using different methods.

Theorem \ref{cycles_sets} becomes less accurate
when $m_j$ is much larger than $H(I_j)$, however it still gives
roughly the right rate of decay; e.g. when $I=[n]$ and $k=n$,
$\mathbb P(C(\sigma)=n)=1/n!$ while the right side is
$O(H_n^{n-1}/n!)$.

This corollary can be interpreted as a permutation analog of 
the Hardy-Ramanujan \cite{HR17} inequality
\[
\# \{n\le x:n\text{ has exactly }k\text{ distinct prime factors} \} \le C_1 \frac{x}{\log x}\; \frac{(\log_2 x+C_2)^{k-1}}{(k-1)!},
\]
where $C_1,C_2$ are certain absolute constants.

Theorem \ref{cycles_sets} is a useful tool for showing
that cycle counts cannot vary too much from their means.  Specifically, the local statistics obey
the same tail bounds as the Poisson distribution,
cf. Lemma \ref{Poisson_tails}.

\begin{cor}\label{single-set-tails}
Let $I$ be a nonempty subset of $[n]$.  (i) Uniformly
for $0\le \lambda \le 1$ we have
\[
\mathbb P\big( C_I(\sigma) \le \lambda H(I) \big) \le 2 \mathrm{e}^{1-Q(\lambda)H(I)},
\]
where 
\[
Q(\lambda)=\lambda \log\lambda - \lambda+1 \ge 0.
\]
Uniformly for $\lambda \ge 1$ we have
\[
\mathbb P\big( C_I(\sigma) \ge \lambda H(I)+1 \big) \le 2 \mathrm{e}^{1-Q(\lambda)H(I)}.
\]
Thirdly, uniformly for $0\le \psi \le \sqrt{H(I)}$,
\[
 \mathbb P \( |C_{I}(\sigma) - H(I)| \ge  \psi \sqrt{H(I)} \)
=O\big( \mathrm{e}^{-\frac13 \psi^2} \big). 
 \]
\end{cor}

The function $Q$ is non-negative and satisfies $Q(x) \approx \frac12 (x-1)^2$
for $x$ near $1$; see also the inequality \eqref{Qx_crude} below.

When $\lambda$ is close to 1, we can be much more precise,
showing a Central Limit Theorem for $C_I(\sigma)$; see
Theorem \ref{CLT_cycles} below.

Specializing to cycle lengths in a single interval $I=(a,b]\cap {\mathbb N}$,
and using that $H(I) \approx \log(b/a)$,
we obtain the following very useful corollary:

\begin{cor}\label{cyclesinterval}
Let $1\le a<b\le n$ and set $I=[a,b]\cap {\mathbb N}$.
Uniformly for $0 \le \ensuremath{\lambda} \le 1$, we have
\[
\mathbb P \( C_{I}(\sigma) \le \ensuremath{\lambda} \log (b/a) \) = O\( (b/a)^{-Q(\ensuremath{\lambda})} \).
\] 
Let $\lambda_0>1$.  Uniformly for $1 \le \ensuremath{\lambda} \le \ensuremath{\lambda}_0$, 
\[
\mathbb P \( C_{I}(\sigma) \ge \ensuremath{\lambda} \log (b/a) \) =O_{\lambda_0} \((b/a)^{-Q(\ensuremath{\lambda})}\).
\]
In particular, uniformly for
$0\le \psi \le \sqrt{\log(b/a)}$, 
\[
 \mathbb P \( |C_{I}(\sigma) - \log (b/a)| > \psi \sqrt{\log (b/a)} \)=O\(
 \mathrm{e}^{-\frac13 \psi^2} \).
\]
\end{cor}

Next, we take a first look at the \emph{random sequence}
$C_{[m]}(\sigma)$ $(1\le m\le n)$ for 
$\sigma\in \ensuremath{\mathcal{S}}_n$.
As long as $m$ is not too small,
it is relatively easy to deduce from Corollary \ref{cyclesinterval}
 that $C_{[m]}(\sigma)$ is \textbf{uniformly}
close to $\log m$ for most $\sigma\in \ensuremath{\mathcal{S}}_n$.

\begin{thm}[Normal sequence $C_{[m]}(\sigma)$]\label{cyclesinterval_allm}
Let $2\le \xi \le n$.  With probability $1-O(1/(\log \xi)^{1/3})$, we have 
\[
|C_{[m]} - \log m| < 2\sqrt{\log m \log\log m} \quad (\xi \le m\le n).
\]
\end{thm}

Our proof is based on the analogous proof for the normal 
distribution of prime factors of integers given in
\cite[Ch. 1]{Divisors}.
When $m$ is bounded, $C_{[m]}(\sigma)$ has a discrete distribution
which is approximately Poisson with parameter $H_m$.
Slightly better bounds than those in Theorem
 \ref{cyclesinterval_allm} are attainable, based on ideas stemming from the Law of the Iterated Logarithm from probability
theory.  Essentially one can replace the factor  $\log\log m$ with $\log\log\log m$, and this is best possible by the Law of the Iterated Logarithm.  See e.g.,
\cite{Manst-LIL};
see also \cite[Theorem 11]{Divisors} for the analogous 
statement and
proof for prime factors of integers.


Theorem \ref{cyclesinterval_allm} 
also tells us about the normal behavior $D_j(\sigma)$, the length of the $j$-th smallest cycle of $\sigma$ (note that $D_j(\sigma)=D_{j+1}(\sigma)$ for some $j$ when $\sigma$ has cycles of the same length).
Since a typical permutation
$\sigma\in \ensuremath{\mathcal{S}}_n$ has about $\log m$ cycles of length $\le m$,
we expect that $D_j(n) \approx \mathrm{e}^j$.


\begin{thm}[$j$-th smallest cycle]\label{Djn}
Let $1\le \theta \le \log n$.  With probability $1-O(\theta^{-1/3})$, we have
\[
|\log D_j(\sigma) - j| < 3\sqrt{j\log j} \qquad (\theta \le j \le C(\sigma)).
\]
\end{thm}

We conclude this section by applying the methods
of proving Theorem \ref{cycles_sets} to  
quickly derive a sharp lower bound when 
 $I=[n]$. This estimate is not new, but will be needed 
in Section \ref{sec:conditional}.

\begin{thm}\label{allsets-local}
Fix $A>1$.  Then  there is a 
constant $c(A)>0$ such that for large enough $n$ (depending on $A$),
\[
\mathbb P(C(\sigma)=k) \ge c(A) \frac{H_n^{k-1}}{(k-1)!}\mathrm{e}^{-H_n}
\qquad (1\le k\le A\log n).
\]
\end{thm}


\subsection{Conditioning on the total number of cycles}
\label{sec:conditional}

If we restrict attention to permutations with $k$ total cycles,
we may also obtain analogous theorems
about the distribution of $C_I(\sigma)$.
We focus on the ``normal'' case when $k=O(\log n)$
and prove analogs of 
Corollary \ref{single-set-tails}.
We expect that $C_I(\sigma)$ will have roughly a binomial
distribution with parameter $p=H(I)/H_n$.
Without loss of generality, we may assume that $H(I)\le \frac12 H_n$, else replace $I$ by $[n] \setminus I$.

\begin{thm}\label{conditional-tails}
Fix $A>1$.
Let $I$ be a nonempty, proper subset of $[n]$ with $H(I)\le \frac12 H_n$, suppose $
2\le k\le A\log n$, and define let $p=H(I)/H_n \le \frac12$.
For any $0\le \psi \le \sqrt{pk}$ we have
\[
\mathbb P \Big( |C_I(\sigma)-p(k-1)| \ge \psi\sqrt{p(1-p)(k-1)}\; \big| \; C(\sigma)=k \Big) =O_A \(\mathrm{e}^{-\frac13 \psi^2}\),
\]
the implied constant depending only on $A$.
\end{thm}

 We also mention here work of Mez\H o and Wang \cite{MezoWang},
 who found an asymptotic for the number of permutations 
 with exactly $k$ cycles and all cycles having length $>m$,
 for fixed $k$ and $m$ with $n\to \infty$.
 


\subsection{Permutations without small cycles.}

Sharp bounds on $\mathbb P(C_{[m]}(\sigma)=0)$ are a
key to establishing the Poisson model.
The model predicts that $\mathbb P(C_{[m]}(\sigma)=0)$
should be about $\mathrm{e}^{-H_m}$,
and Corollary \ref{cycles-single-set} contains an upper bound
close to this.
 This cannot be expected to hold for large $m$, for example 
 $\mathbb P(C_{[m]}(\sigma)=0)=1/n$ if $m \ge n/2$ since a permutation lacking cycles of length at most $m$ must be a single $n$-cycle.
  In fact, when $n/m$ is small, there is an asymptotic formula
 $\mathbb P(\sigma\in \ensuremath{\mathcal{S}}_{n,m}) \sim \omega(n/m)/m$ ($n\to\infty$, $m\to\infty$) where $\omega$ is Buchstab's function
 and $\omega(u)\to \mathrm{e}^{-\gamma}$ as $u\to\infty$ \cite[Theorem 5]{granville}.  This is analogous to the problem
 of counting integers $n\le x$ with no prime factor $\le x^{1/u}$
 (see \cite[Ch. III.6]{Tenbook}).

Our focus  is to prove that
$\mathbb P(C_{[m]}(\sigma)=0$ is very close to $\mathrm{e}^{-H_m}$ when 
$n/m$ is large.

 \begin{thm}[Permutations without small cycles]\label{nosmallcycles2}
 Let $1\le m\le n$.  Then
 \[
 \mathbb P(C_{[m]}(\sigma)=0) = \mathrm{e}^{-H_{m}} \(1 + O(\mathrm{e}^{-g(n/m)}) \),
 \]
 where $g(x)=0$ for $1\le x\le 20$ and for $x > 20$,
 \[
g(x) = x\log x - x\log\log\log x + O(x).
 \]
 \end{thm}
 
 Exact asymptotics for $\mathbb P(C_{[m]}(\sigma)=0)-\mathrm{e}^{-H_m}$
 have been obtained by Petuchovas
 \cite{Pet16, Pet18}, using generating functions 
 and a lengthy argument based on countour integration.
 Our method is much simpler and is based on sieve methods in
 number theory.
 

 \subsection{Permutations without large cycles}
 
 The distribution of permutations without
 large cycles is very different than that predicted
 by the Poisson model.  If $\sigma$ has no large cycles,
 the fact that the
 cycle lengths must sum to $n$ implies that
 $\sigma$ must in fact contain a very large number of smaller cycles, and this is a much rarer event.
 
\begin{thm}[Permutations without large cycles]\label{nolargecycles}
For $1\le m\le n$ we have
\[
\mathbb P(C_{(m,n]}(\sigma)=0) \le \mathrm{e}^{-(n/m)\log (n/m) + (n/m)}.
\]
\end{thm}

 This bound is reasonably sharp throughout the
range $1\le m\le n$.  For example, when $m=1$, Stirling's formula implies
\[
\mathbb P(C_{(1,n]}(\sigma)=0) = \mathbb P(\sigma=\text{id})=\frac{1}{n!}
\sim \frac{\mathrm{e}^{-n\log n + n}}{\sqrt{2\pi n}} \qquad
(n\to \infty).
\]
When $m=2$, Chowla, Herstein and Moore \cite{CHM} showed
an asymptotic for $\mathbb P(C_{(2,n]}(\sigma)=0)$ which implies that
\[
\mathbb P(C_{(2,n]}(\sigma)=0) = e^{-(n/2)\log (n/2)+O(n)}.
\]
When $n/m=u$ is bounded, then $\mathbb P(C_{(m,n]}(\sigma)=0) \sim \rho(u)$ as $n\to\infty$ by Goncharov \cite{Gon44}, where $\rho$ is
 the Dickman function, a continuous, decreasing 
function satisfying 
\[
\rho(u)=\mathrm{e}^{-u\log u -u\log\log(u+2)+O(u)}.
\]

Using complex analytic methods, Manstavi\v{c}ius and Petuchovas \cite{ManPet16} found
more precise asymptotics throughout the range $1\le m\le n$.
Their methods are motivated by the analogous problem of
counting integers lacking large prime factors,
see \cite[Ch. III.5]{Tenbook}.

Suppose $n/2 \le m\le n$.  Then $\sigma$ has at most
one cycle of length $k\in (m,n]$, thus
\[
\mathbb P(C_{(m,n]}(\sigma)=0) = 1 - 
\sum_{m<k\le n} {\mathbb E}\, C_k(\sigma) = 1-(H_n-H_m).
\]
In particular, when $m=50, n=100$, this helps to solve the ``100 prisoners problem'' \cite{100prisoners}: There are 100 prisoners, numbered to 100.
 The numbers from 1 to 100 are placed in 100 unmarked boxes.
Each prisoner is allowed to open 50 of the boxes, and no communication between prisoners is allowed.  If every prisoner
finds his own number then they all go free.  Althought it appears hopeless, there is a strategy that will work about 30\% of the time.
If the boxes are lebeled 1,...,100 on the outside, the mapping from external label to internal number is a permutation of $[100]$.  With probability $1-H_{100}+H_{50} \approx 0.3$, the permutation contains no cycles of length more than 50. In this case, if 
 every prisoner follows the cycle starting with his own number (first opens the box labeled on the outside with his number, then opens the box number that he finds in the first box, etc), he'll find his number
 inside one of the boxes after no more than 50 openings.




\subsection{Establishing the Poisson model}


Let $1\le k\le n$ and
consider the problem of modeling 
\[
\ensuremath{\mathcal{C}}_k=(C_1(\sigma),\ldots,C_k(\sigma))\]
by the random vector 
\[
\ensuremath{\mathcal{Z}}_k=(Z_1,\ldots,Z_k), 
\]
where $Z_1,\ldots,Z_k$ are independent Poisson random variables
with parameters $1,\frac12,\ldots,\frac{1}{k}$, respectively.
We especially desire a good approximation when $k$ is large, as opposed
to bounded (ref. Theorem \ref{cycles_sets}).
We express our results in terms of the Total Variational Distance
$d_{TV}(X,Y)$ between two random variables $X$ and $Y$ taking values
in a discrete space $\Omega$,
defined by 
\begin{equation}\label{dTV}
d_{TV}(X,Y) := \sup_{U\subset \Omega}  \mathbb P(X\in U) - \mathbb P(Y\in U).
\end{equation}



\begin{thm}[Poisson distribution of small cycles]\label{Poisson_smallcycles}
Let $1\le k\le n$.  Then $$d_{TV} (\ensuremath{\mathcal{C}}_k, \ensuremath{\mathcal{Z}}_k) \le \mathrm{e}^{-f(n/k)},$$ where $f(x)=0$ for $x\le 100$ and  for $x\ge 100$ we have
\[
f(x)=x\log x - x \log\log\log x  + O(x).
\]
\end{thm}




\begin{remark}
Theorem \ref{Poisson_smallcycles} is slightly weaker than
the main theorem of Arratia and Tavar\'e \cite{AT92},
which states that $d_{TV} (\ensuremath{\mathcal{C}}_k, \ensuremath{\mathcal{Z}}_k) \le \mathrm{e}^{-(n/k)\log(n/k)+O(n/k)}$.
Sharper bounds are known, and are expressed in terms of the 
Dickman and Buchstab functions (see \cite{Pet16,ManPet16}).
Our proof is significantly shorter than either of these treatments.
\end{remark}


We immediately obtain the following corollary, by grouping together integers into sets.

\begin{thm}[Poisson distribution of cycles in sets]\label{poisson_cycles}
Let $I_1,\ldots, I_m$ be disjoint subsets of $[k]$, with $k\le n$.  Then, for any sets $J_1,\ldots,J_m$ of 
non-negative integers,
\[
\mathbb P\( C_{I_1}(\sigma)\in J_1,\ldots,C_{I_m}(\sigma)\in J_m \) = \mathbb P\( Y_1\in J_1,\ldots,Y_m\in J_m\) + O(\mathrm{e}^{-\frac{n}{2k}\log(n/k)}),
\]
where for each $i$,
$Y_i$ is Poisson with parameter $H(I_i)$,
 and $Y_1,\ldots,Y_m$
are independent.
\end{thm}






\subsection{Uniform Central Limit Theorems}


Combining Theorem \ref{poisson_cycles} with the Central
Limit Theorem for Poisson variables (Theorem \ref{Poisson_CLT} below) establishes a Central
Limit Theorem for the count of cycles whose lengths lie in an
arbitrary set $I\subset [n]$.

\begin{thm}[Cycles CLT]\label{CLT_cycles}
Let $I\subset [n]$ with $H(I)\ge 3$.  Uniformly for all 
$I$ and any real $w$,
\[
\mathbb P \( C_{I}(\sigma)\le H(I) + w \sqrt{H(I)} \) = \Phi(w) + 
O\pfrac{\log H(I)}{\sqrt{H(I)}},
\qquad \Phi(w)=\frac{1}{\sqrt{2\pi}} \int_{-\infty}^w \mathrm{e}^{-\frac12 t^2}\, dt.
\]
\end{thm}

The special case $I=[n]$ was established by
Goncharov \cite{Gon44}, without a specific rate of convergence.
Goncharov analyzed carefully the asymptotics of the
Stirling number of the first kind, $s(n,m)$, the absolute value of which counts the
number of permutations $\sigma \in \ensuremath{\mathcal{S}}_n$ with exactly $m$ total cycles.
Since $H_n=\log n + O(1)$ and $\Phi$ has bounded derivative,
we quickly arrive at the following corollary.

\begin{thm}[CLT for all cycles; Goncharov \cite{Gon44}]\label{CLT_all_cycles}
Let $n\ge 100$ and $w\in {\mathbb R}$.  Then
\[
P\( C(\sigma) \le \log n + w\sqrt{\log n} \) = \Phi(w) + O\pfrac{\log\log n}{\sqrt{\log n}}.
\]
\end{thm}


The big-$O$ term in Theorem \ref{CLT_cycles}
 cannot be made smaller than $1/\sqrt{H(I)}$
since $C_I(\sigma)$ is integer valued, and
thus the left side is constant in intervals of $w$ of length
$1/\sqrt{H(I)}$, while $\Phi(w)$ has positive derivative.
We remark that  when $H(I)$ is bounded, $C_I(\sigma)$ is expected to
have Poisson distribution with small parameter, and this cannot be approximated by a Gaussian. 


We also derive that the $j$-th smallest cycle
of $\sigma$, denoted $D_j(\sigma)$ (with ties allowed), also obeys the
Gaussian law, refining Theorem \ref{Djn}.

\begin{thm}\label{jth-smallest-cycle}
Uniformly for $j$ in the range
\[
1\le j \le \log n - (\log n)^{1/2}\log\log n
\]
and for any real $w$,
\[
\mathbb P (\log D_{j}(\sigma) \le j + w\sqrt{j}) = \Phi(w) 
+O\pfrac{\log (2j)}{\sqrt{j}}.
\]
\end{thm}


The analogous statement for the $j$-th smallest prime factor of
an integer, without a rate of convergence, was proved by Galambos \cite{Galambos76}.


\section{Preliminaries}


\subsection{Additional notation}
$\beta|\sigma$ means that $\beta$ is a \emph{divisor} of the permutation
$\sigma$, i.e. a product of some subset of the cycles of $\sigma$.
$|\beta|$ is the size (length) of $\beta$.

$\one(S)$ is the indicator function of statement $S$; $\displaystyle \one(S) = 
\begin{cases} 1 & S \text{ is true} \\ 0 & S \text{ is false}. \end{cases}$





\begin{lem}\label{harmonic}
The harmonic sums $H_n$ satisfy

(i) $\log n \le H_n \le 1 +\log n$;

(ii) $H_n = \log n + \gamma + O(1/n)$,
where
$\gamma=0.57721566\ldots$ is Euler's constant.
\end{lem}

\begin{lem}[Stirling's formula]\label{Stirling}
We have $n! \ge (n/\mathrm{e})^n$ and the asymptotic
\[
n! = \sqrt{2\pi n} (n/\mathrm{e})^n (1+O(1/n)) \qquad (n\ge 1).
\]
\end{lem} 

\begin{lem}[Inclusion-exclusion]\label{incl-excl}
Let $a$ be a non-negative integer. For $0\le m\le k$,
\begin{align*}
\one(a=m) &= \sum_{r=m}^\infty (-1)^{r-m} \binom{r}{m} \binom{a}{r}
\\ &= \sum_{r=m}^k (-1)^{r-m} \binom{r}{m} \binom{a}{r} +
(-1)^{k+1-m} \binom{a}{m} \binom{a-m-1}{k-m},
\end{align*}
where the final term is
 at most $\binom{a}{k}\binom{k}{m}$ in
absolute value.
\end{lem}


\begin{lem}[Poisson tails; see Norton \cite{Norton76}]\label{Poisson_tails}
Let $X$ be Poisson with parameter $\lambda$. Then
\begin{align*}
\mathbb P(X\le \a \ensuremath{\lambda}) &\le \min\bigg(1, \frac{1}{(1-\a)\sqrt{\a \lambda}}  \bigg)\mathrm{e}^{-Q(\a)\ensuremath{\lambda}} \quad (0\le \a\le 1), \\
\mathbb P(X\ge \a \ensuremath{\lambda}) &\le \min\bigg( 1, \frac{1}{\a-1} \sqrt{\frac{\a}{2\pi \ensuremath{\lambda}}}\bigg) \mathrm{e}^{-Q(\a)\ensuremath{\lambda}} \quad (\a\ge 1),
\end{align*}
where $Q(x) = \int_1^x \log t\, dt = x\log x - x + 1.$
Furthermore,
\begin{equation}\label{Qx_crude}
\frac{x^2}{3} \le Q(1+x) \le x^2 \quad (|x| \le 1).
\end{equation}
\end{lem}










\section{Cycle distribution: binomial means}\label{sec:binom}
\begin{lem}\label{cycles}
Let $m_1,\ldots,m_n$ be non-negative integers with $m_1+2m_2+\cdots+nm_n\le n$.  Then
 \[
{\mathbb E}\, \prod_{j=1}^n \binom{C_j(\sigma)}{m_j} = \prod_{j=1}^n \frac{1}{m_j! j^{m_j}}.
\]
If  $m_1+2m_2+\cdots+nm_n > n$, then the left side is zero.
\end{lem}
\begin{proof}
The second assertion is obvious, since the only way for the product to be positive is for the sum of the cycle lengths to exceed $n$. Now assume that
$m_1+2m_2+\cdots+nm_n\le n$. 
 The number of ways of choosing from $[n]$ a disjoint collection 
  of $m_1$ $1-$element sets, $m_2$  $2-$element sets,
$\ldots$, $m_n$ $n-$element sets is equal to
\[
 \binom{n}{\underbrace{1 \cdots 1}_{m_1} \underbrace{2 \cdots 2}_{m_2} \cdots \underbrace{n\cdots n}_{m_n} \, t} 
 \frac{1}{m_1! \cdots m_n!} = \frac{n!/t!}{\prod_{j=1}^n (j!)^{m_j} m_j!},
 \]
by the multinomial theorem, where $t=n-(m_1+2m_2+\cdots+nm_n)$.
The elements of a $k$-element set may be arranged into a cycle in $(k-1)!$ ways.
Thus, 
the number of ways to arrange the elements of these sets into cycles is $(0!)^{m_1} (1!)^{m_2} \cdots (n-1)!^{m_k}$.
Finally, the $t$ elements not used in any of these cycles may be permuted in $t!$ ways.
\end{proof}


\begin{proof}[Proof of Theorem \ref{thm:genfcn}]
Using Cauchy's formula, we have
\begin{align*}
\sum_{n,k} \mathbb P_n \big(C_I(\sigma)=k,C_{[n]\setminus I}(\sigma)=0\big) x^n y^k &=
\sum_{n,k} x^n y^k \ssum{\sum_{i\in I} a_i = k \\ \sum_{i\in I} ia_i=n}
\prod_{i\in I} \frac{(1/i)^{a_i}}{a_i!} \\
&= \sum_{a_i\ge 0 : i\in I} \frac{x^{\sum ia_i} y^{\sum a_i} (1/i)^{a_i}}{\prod a_i!}\\
&=\exp \bigg\{ y \sum_{i\in I} \frac{x^i}{i} \bigg\}.\qedhere
\end{align*}
\end{proof}


\begin{proof}[Proof of Cauchy's theorem, Theorem \ref{thm:Cauchy}] 
Apply Lemma \ref{cycles}, noting that $\binom{C_j(\sigma)}{m_j}\ne 0$
for all $j$ if and only if $C_j(\sigma)=m_j$ for every $j$.
\end{proof}



\begin{proof}[Proof of Goncharov's local limit theorem, Theorem \ref{thm:Goncharov}]
By Inclusion-Exclusion (Proposition \ref{incl-excl}) and the Lemma \ref{cycles}, we obtain
\begin{align*}
\# \{ \sigma\in \ensuremath{\mathcal{S}}_n : C_j(\sigma)=m \} &= \sum_{\sigma\in \ensuremath{\mathcal{S}}_n} 
 \sum_{r=m}^\infty (-1)^{r-m} \binom{r}{m} \binom{C_j(\sigma)}{r} \\
&= n! \sum_{r=m}^{\fl{n/j}} (-1)^{r-m} \binom{r}{m}  {\mathbb E}\, \binom{C_j(\sigma)}{r} 
= n! (-1)^m \sum_{r=m}^{\fl{n/j}} \binom{r}{m}  \frac{(-1/j)^r}{r!}. 
\end{align*}
The desired equality follows by setting $r=h+m$.
\end{proof}



\begin{cor}[Expected number of cycles]\label{numcycles}
We have ${\mathbb E}\, C(\sigma) = H_n = \log n + \gamma + O(1/n)$.
\end{cor}

\begin{proof}
By Lemma \ref{cycles}, ${\mathbb E}\, C_j(\sigma)=1/j$ for every $j$, and the
result follows by linearity of expectation and Proposition \ref{harmonic}.
\end{proof}


\begin{proof}[Proof of Theorem \ref{cycles_sets_expectation}]
Consider a set $A$ of size $C_{I_j}(\sigma)$,
and partition $A$ into subsets $A_r$, where
$|A_r|=C_r(\sigma)$ for $r\in I_j$.  Then
\[
\binom{C_{I_j}(\sigma)}{m_j} = \sum_{\eqref{cycles-sets-2}}\; \prod_{r\in I_j} \binom{C_r(\sigma)}{m_{j,r}},
\]
where the summation is over tuples $(m_{j,r})_{1\le j\le k,r\in I_j}$
satisfying the system
\begin{equation}\label{cycles-sets-2}
\sum_{r\in I_j} m_{j,r} = m_j \quad (1\le j\le k). 
\end{equation}
Thus,
\begin{equation}\label{cycles-sets-1}
{\mathbb E}\, \prod_{j=1}^k \binom{C_{I_j}(\sigma)}{m_j} = \sum_{\eqref{cycles-sets-2}} {\mathbb E}\, \prod_{j=1}^k \prod_{r\in I_j} \binom{C_r(\sigma)}{m_{j,r}}.
\end{equation}
Using Lemma \ref{cycles}, the expectation on the right side of \eqref{cycles-sets-1} equals
\[
\prod_{j=1}^k \prod_{r\in I_j} \frac{1}{r^{m_{r,j}} m_{r,j}!}
\]
provided that
\begin{equation}\label{cycles-sets-3}
\sum_{j=1}^k \sum_{r\in I_j} r m_{r,j} \le n, 
\end{equation}
and is zero otherwise.  

If $\sum_{j=1}^k m_j \max(I_j)\le n$, then \eqref{cycles-sets-3} will always be satisfied
as long as \eqref{cycles-sets-2} holds,
and therefore
\[
{\mathbb E}\, \prod_{j=1}^k \binom{C_{I_j}(\sigma)}{m_j} =
 \prod_{j=1}^k \sum_{\eqref{cycles-sets-2}} \prod_{r\in I_j} \frac{1}{r^{m_{r,j}} m_{r,j}!} = \prod_{j=1}^k \frac{H(I_j)^{m_j}}{m_j!},
\]
as claimed.  On the other hand, if
 $\sum_{j=1}^k m_j \max(I_j) > n$, then there is some choice of the parameters
$(m_{j,r})$ satisfying \eqref{cycles-sets-2} but violating \eqref{cycles-sets-3}, 
and the left side is strictly less than the right side.
Specifically, we may take $m_{j,\max I_j}=m_j$ for each $j$
and $m_{j,r}=0$ otherwise. 
\end{proof}



\section{Counting permutations with a given cycle structure}

While Theorem \ref{thm:Goncharov} provides a exact formula
for $\mathbb P(C_j(\sigma)=m)$, an analogous formula for
$\mathbb P(C_I(\sigma)=m)$ with an arbitrary set $I$ will necessarily be far more complicated.  However, borrowing ideas from the theory
of averages of multiplicative functions in number theory, we 
give a relatively sharp upper bound for this quantity, and
more generally for the joint probability of 
$C_{I_j}(\sigma)=m_j$ for $j=1,\ldots,k$.

We begin with a rather complicated identity for the joint distribution
of the quantities $C_{I_i}$.

\begin{lem}\label{lem:CIjmj}
Let $I_1,\ldots,I_r$ be disjoint subsets of $[n]$ and $m_1,\ldots,m_r$
be non-negative integers.  Denote $I_0 = [n] \setminus (I_1\cup \cdots I_r)$.
Let $\ensuremath{\mathcal{T}}$ be the set of indices $i$ with $m_i>0$, together
with the number 0 if $I_0$ is nonempty.  Then
\begin{equation}\label{cycles-sets-equality}
  \mathbb P\big( C_{I_j}(\sigma)=m_j\; (1\le j\le r) \big)
  = \frac{1}{n}\sum_{t\in \ensuremath{\mathcal{T}}} \sum_{h \in I_t} 
  \ssum{b_1,\dots, b_n \geq 0 \\ b_1 + 2b_2 + \cdots + nb_n = n - h \\ \sum_{i\in I_j} b_i =m_j-\one(t=j),\  (1\le j\le r) } 
  \frac{1}{\prod_i b_i! i^{b_i}}.
\end{equation}
\end{lem}

\begin{proof}
 Evidently
\[
  n \# \{\sigma \in \ensuremath{\mathcal{S}}_n:  C_{I_1}(\sigma)=m_1,\ldots,C_{I_r}(\sigma)=m_r\} = \ssum{\sigma \in \ensuremath{\mathcal{S}}_n \\ C_{I_j}(\sigma)=m_j \; (1\le j\le r) } \;\; \ssum{\alpha|\sigma \\ \a \text{ a cycle}} |\a|.
\]
Write $\sigma=\a \beta$ and let $h=|\a|$.   
 Thus, for some $t\in \ensuremath{\mathcal{T}}$,  we have $|\a|=h\in I_t$
 and
\[
(C_{I_1}(\beta),\ldots,C_{I_r}(\beta))=(m_1-\one(t=1),\ldots,m_r-\one(t=r)).
\]
It is permissible to think of $\beta\in \ensuremath{\mathcal{S}}_{n-h}$ and thus
\begin{align*}
  n  \# \{\sigma \in \ensuremath{\mathcal{S}}_n: C_{I_1}(\sigma)=m_1,\ldots,C_{I_r}(\sigma)=m_r\}
  &= \sum_{t\in \ensuremath{\mathcal{T}}} \sum_{h\in I_t} \; \ssum{\a\in\ensuremath{\mathcal{S}}_n, |\a|=h \\ \a\text{ a cycle}} h \ssum{\beta\in \ensuremath{\mathcal{S}}_{n-h}\\ C_{I_i}(\beta)=m_i-\one(t=i), (1\le i\le r)} 1  \\
  &=  \sum_{t\in \ensuremath{\mathcal{T}}} \sum_{h\in I_t} \frac{n!}{(n-h)!} \ssum{\beta\in \ensuremath{\mathcal{S}}_{n-h} \\ C_{I_i}(\beta)=m_i-\one(t=i), (1\le i\le r) } 1.
\end{align*}
Now subdivide the sum according the cycle type $(b_1,\ldots,b_{n})$ of
the permutation $\beta$, use Cauchy's formula (Thm. \ref{thm:Cauchy}) to 
count such permutations for each type, and divide by $n$.  The desired identity follows.
\end{proof}




\begin{proof}[Proof of Theorem \ref{cycles_sets}]
The right side in Lemma \ref{lem:CIjmj} is at most
 \[
 \frac{1}{n} \sum_{t\in \ensuremath{\mathcal{T}}}
  \ssum{b_1,\dots, b_n \geq 0 \\ \sum_{i\in I_j} b_i =m_j-\one(t=j) \; (1\le j\le r)  } \frac{1}{\prod_i b_i! i^{b_i}} := \frac{Y}{n},
\]
  say.   By the multinomial theorem,
  \[\begin{aligned}
 Y & =    \sum_{t\in \ensuremath{\mathcal{T}}} \ssum{b_i\ge 0 \; (i\in I_1\cup \cdots \cup I_r) \\ \sum_{i\in I_j} b_i = m_j-\one(t=j) \; (1\le j\le r) } 
  \frac{1}{\prod_{i\in I_1\cup \cdots \cup I_r} b_i! i^{b_i}} \sum_{b_i\ge 0 \; (i\in I_0)} \frac1{\prod_{i\in I_0} b_i! i^{b_i}}\\
  &=  \sum_{t\in \ensuremath{\mathcal{T}}} \frac{m_t}{H(I_t)}\prod_{j=1}^r \frac{H(I_j)^{m_j}}{m_j!} \mathrm{e}^{H(I_0)}.
\end{aligned}\]
 The claimed bound now follows from
$H(I_0) = H_n - H(I_1)-\cdots-H(I_r)$.
\end{proof}


Later, we will sharpen the conclusion when $r=1$, $I_1=[k]$
or $I_1=\{k+1,\ldots,n\}$, and $m_1=0$.
These two cases tell us the
probability that a random permutation has no large cycles or
no small cycles, respectively.



\begin{proof}[Proof of Corollary \ref{single-set-tails}]
For the first inequality, apply Corollary \ref{cycles-single-set}
for all $m\le \lambda H(I)$, followed by Proposition \ref{Poisson_tails}, and get
\[
\mathbb P( C_I(\sigma) \le \lambda H(I) ) \le 2 \sum_{m\le \lambda H(I)}
\mathrm{e}^{1-H(I)} \frac{H(I)^m}{m!} \le 2\mathrm{e}^{1-Q(\lambda)H(I)}.
\]
The second inequality is similar.  We have
\begin{align*}
\mathbb P( C_I(\sigma) \ge \lambda H(I)+1 ) &\le  \sum_{m\ge \lambda H(I)+1} \mathrm{e}^{1-H(I)} \bigg( \frac{H(I)^m}{m!} + \frac{H(I)^{m-1}}{(m-1)!} \bigg) \\
&= 2 \sum_{m\ge \lambda H(I)} \mathrm{e}^{1-H(I)} \frac{H(I)^m}{m!} 
\le 2\mathrm{e}^{1-Q(\lambda)H(I)}.
\end{align*}

For the third assertion, define $\lambda^{\pm}$ by
\[
\lambda^- H(I) = H(I)-\psi\sqrt{H(I)}, \qquad
\lambda^+ H(I) + 1 = H(I) + \psi\sqrt{H(I)}.
\]
In particular, $\lambda^- , \lambda^+ \le 2$.  
Then
\begin{align*}
Q(\lambda^{\pm})H(I) &= Q \Big(1\pm \psi H(I)^{-1/2}+O(1/H(I))\Big) H(I)
\\ &= Q\big( 1\pm \psi H(I)^{-1/2} \big) H(I) + O(1),
\end{align*}
and the claim follows from \eqref{Qx_crude}.
\end{proof}


\begin{proof}[Proof of Corollary \ref{cyclesinterval}]
Let $I=(a,b] \cap {\mathbb N}$.
Firstly, suppose that $0\le \lambda\le 1$.
From \eqref{harmonic} we have $H(I)=\log (b/a)+O(1/a)$.
Thus, if we define $\lambda'$ by
\[
\lambda \log(b/a) = \lambda'H(I),
\]
then $|\lambda-\lambda'| \ll \frac{1}{a\log(b/a)}$.
By Corollary \ref{single-set-tails},
\[
\mathbb P \( C_{I}(\sigma) \le \ensuremath{\lambda} \log (b/a) \) =
\mathbb P(C_I(\sigma) \le \lambda' H(I))\le 2\mathrm{e}^{1-Q(\lambda')H(I)}.
\]
Since $|Q(\lambda)-Q(\lambda')| = O(|\lambda-\lambda'|)$,
the first inequality follows.

The proof of the second bound is similar. 
Define $\lambda'$ by 
\[
\lambda \log(b/a) = \lambda'H(I)+1,
\]
Then $|\lambda-\lambda'| \ll_{\lambda_0} \frac{1}{\log(b/a)}$.
The second assertion follows from
Corollary \ref{single-set-tails} and the estimate
$|Q(\lambda)-Q(\lambda')| = O_{\lambda_0}(|\lambda-\lambda'|)$.
The final estimate follows from the bound \eqref{Qx_crude} for $Q(u)$.
\end{proof}

In particular, taking $I=[n]$, we see that
 $C(\sigma)$ usually does not vary more that a constant times $\sqrt{\log n}$ from its mean $H_n$.


Corollaries \ref{cycles-single-set} and \ref{single-set-tails}
are not very accurate when $H(T)<1$, especially in the case $m=1$.
In this case, we expect that $C_I(\sigma)$ will rarely be much more than 1.  The next lemma gives an improved upper bound in this case.

\begin{thm}\label{cycles-set-strict}
 if $I$ is a nonempty susbet of $[n]$, and $k\ge 0$,
then
\[
\mathbb P \( C_I(\sigma) \ge k \) \le \frac{H(I)^k}{k!}.
\]
\end{thm}

\begin{proof}
By Theorem \ref{cycles_sets_expectation},
\[
\mathbb P ( C_I(\sigma) \ge k ) \le {\mathbb E}\, \binom{C_I(\sigma)}{k} \le \frac{H(I)^k}{k!}.\qedhere
\]
\end{proof}


\begin{cor}\label{two-equal-large-cycles}
Let $2\le \ell \le n$.
The probability that a random
permutation $\sigma\in \ensuremath{\mathcal{S}}_n$ has two cycles of the same length $j$
for some $j\ge \ell$, is at most $\frac{1}{2(\ell-1)}$.
\end{cor}

\begin{proof}
By Lemma \ref{cycles-set-strict}, $\mathbb P( C_j(\sigma)\ge 2) \le \frac{1}{2j^2}$.  Summing over $j\ge \ell$ we find that
\[
\mathbb P (C_j(\sigma)\ge 2\text{ for some }j\ge \ell ) \le \sum_{j=\ell}^\infty
\frac{1}{2j^2} \le \frac12 \sum_{j=\ell}^\infty \frac{1}{j(j-1)} = \frac{1}{2(\ell-1)}.\qedhere
\]
\end{proof}



\begin{proof}[Proof of Theorem \ref{cyclesinterval_allm}]
Let
\[
k_1 = \fl{\log \xi}+1, \qquad k_2 = \fl{\log n},
\]
and for $k_1 \le k\le k_2$, let $t_k = \mathrm{e}^k$.  Put $t_{k_1-1}=\xi$
and $t_{k_2+1}=x$.  For each $k$, $k_1-1 \le k\le k_2+1$, let
$N_k(x)$ be the probability 
that\footnote{Here we write $[x]$ for the set $\{1,2,\ldots,\fl{x}\}$ for any real $x\ge 1$.}
\begin{equation}\label{omegantk}
|C_{[t_k]}(\sigma)-\log t_k| \ge 2\sqrt{(k-1)\log(k-1)}-1.
\end{equation}
As $\log t_k = k+O(1)$ for all $t_k$ (including the endpoints),
\[
2\sqrt{(k-1)\log(k-1)}-1 = \psi \sqrt{\log t_k}, \quad \psi=2\sqrt{\log k}+O(1/\sqrt{k}). 
\]
Hence, by Corollary \eqref{cyclesinterval},
\[
N_k(x) \ll \mathrm{e}^{-\frac13 \psi^2} \ll \frac{1}{k^{4/3}}.
\]
Summing over $k$, we see that with probability $O(1/(\log_2 \xi)^{1/3})$, \eqref{omegantk} holds for some $k$.  Now
suppose that \eqref{omegantk} fails for every $k$ with $k_1-1\le k\le k_2+1$.
Let $\xi \le t\le x$ and suppose that $t_k < t\le t_{k+1}$.  Evidently,
\[
C_{[t_k]}(\sigma) \le C_{[t]}(\sigma) \le C_{[t_{k+1}]}(\sigma)
\]
and, by the failure of \eqref{omegantk} at every $k$,
\[
 C_{[t]}(\sigma)\ge \log t_k - 2\sqrt{(k-1)\log(k-1)}+1 \ge \log t-2\sqrt{\log t\log\log t}
\]
and
\[
C_{[t]}(\sigma) \le \log t_{k+1} + 2\sqrt{k\log k} - 1 \le  \log t+2\sqrt{\log t\log\log t}.\qedhere
\]
\end{proof}


\begin{proof}[Proof of Theorem \ref{Djn}]
We may suppose that $\theta\ge \theta_0$, where $\theta_0$ is a 
sufficiently large, absolute constant, for otherwise the conclusion
of the Corollary is trivial if the implied constant is large enough.  
Let $\xi = \fl{\mathrm{e}^{(2/3)\theta}}$.  By  Theorem
\ref{cyclesinterval_allm}, with probability $1-O(1/\theta^{1/3})$,
we have
\begin{equation}\label{Djn:Cm}
|C_{[m]}(\sigma)-\log m| < 2\sqrt{\log m\log_2 m} \qquad (\xi \le m\le n).
\end{equation}
Also, by Lemma \ref{two-equal-large-cycles}, with
probability $1-O(1/\xi)$ all the cycles of $\sigma$ of length $\ge \xi$ 
have distinct lengths.
Now suppose that $\sigma$ is a permutation satisfying \eqref{Djn:Cm},
and such that the cycles of $\sigma$ with lengths $\ge \xi$ have distinct lengths.
We suppose that $\theta_0$ is so large that the right side of the inequality
in \eqref{Djn:Cm} is at most $\frac12 \log m$ for every $m\ge \xi$.  
In particular, 
\[
 C_{[\xi]}(\sigma) < \frac32 \log \xi \le \theta,
\]
that is, $D_\theta(\sigma) > \xi$.
Thus, we may apply \eqref{Djn:Cm} with $m=D_j(\sigma)$ for all $\theta\le j\le C(\sigma)$.  As the cycle lengths $\ge \xi$ are distinct,
we have $j=C_{[m]}(\sigma) > \frac12 \log D_j(\sigma)$ and hence
\[
|j - \log D_j(\sigma)| < 2\sqrt{\log D_j(\sigma)\log_2 D_j(\sigma)} <
2\sqrt{2j\log(2j)} < 3\sqrt{j\log j}
\]
provided that $\theta_0$ is large enough (and hence $j$ is large enough).
\end{proof}


\begin{proof}[Proof of Theorem \ref{allsets-local}]
If $k=1$, $\mathbb P(C(\sigma)=1)=1/n$.  Now suppose $k\ge 2$.
We begin with \eqref{cycles-sets-equality}, 
which implies that 
\begin{equation}\label{allsets-equality}
\mathbb P(C(\sigma)=k)=\frac{1}{n} \ssum{b_1,\ldots,b_n\ge 0 \\ 
b_1+2b_2+\cdots \le n \\ b_1+\cdots+b_n=k-1} 
\frac{1}{\prod_{i\le k} b_i! i^{b_i}}.
\end{equation}
This formula is classical, following e.g. from
Vi{\` e}te's formula.
We restrict the
summations to $b_i=0 (i>m)$ for
some parameter $m\in [1,n]$ to be chosen later.
 We also replace the condition 
$b_1 + 2b_2 + \cdots \le n/2$ with an extra factor
$\frac{n-b_1-2b_2-\cdots}{n}$.  Thus, by the multinomial theorem,
\begin{align*}
\mathbb P(C(\sigma)=k) &\ge \frac{1}{n} \ssum{b_1,\ldots,b_m\ge 0 \\ b_1+\cdots+b_m=k-1} \frac{n-(b_1+2b_2+\cdots+mb_m)}{\prod_{i\le m} b_i! i^{b_i}}\\
&=\frac{H_m^{k-1}}{(k-1)!} - \frac{m}{n}
\cdot \frac{H_m^{k-2}}{(k-2)!}\\
&= \frac{H_m^{k-1}}{(k-1)!}\bigg( 1 - \frac{m(k-1)}{nH_m} \bigg).
\end{align*}
When $1\le k < \log n$, we may take $m=n$ and note that
$H_m=H_n\ge \log n$.  Thus,
\begin{equation}\label{lower-smallk}
\mathbb P(C(\sigma)=k) \ge \frac{H_n^{k-1}}{n(k-1)!}\(1- \frac{k}{\log n}\) \qquad (1\le k < \log n).
\end{equation}
In particular, this gives the asymptotic
\begin{equation}\label{allsets-asym}
\mathbb P(C(\sigma)=k) \sim \frac{H_n^{k-1}}{n(k-1)!} \qquad (k=o(\log n), n\to\infty),
\end{equation}
recovering a result of Moser and Wyman \cite{MoserWyman}
(the authors utilized generating functions and contour integration).  We note that \eqref{allsets-asym}
differs from that predicted by the Poisson model by 
a factor \[
\frac{1}{n}\mathrm{e}^{H_n} \sim \mathrm{e}^{\gamma}.
\]
To obtain Theorem \ref{allsets-local}, we 
fix $A \ge 2$ and take $m=n/(2A)$.  
We have $H_m = H_n + O(\log A)$ and so for $n$ large enough,
\[
\mathbb P(C(\sigma)=k) \ge \frac{H_m^{k-1}}{3n(k-1)!} 
\ge c(A) \frac{H_n^{k-1}}{n(k-1)!} 
\]
for some positive $c(A)$.
\end{proof}

\medskip











\section{Fixed sets  and divisors of permutations}

A \emph{fixed set} $I$ of a permutation $\sigma\in \ensuremath{\mathcal{S}}_n$ is a subset of $[n]$ fixed by $\sigma$.
 A fixed set corresponds to a product of some subset of the cycles in $\sigma$
(we include both the empty set and the whole set $[n]$ as fixed sets).  These play the
same role for permutations as divisors do for integers.  The existence of fixed sets
of a particular size has applications to various questions in combinatorial group theory,
such as generation of $\ensuremath{\mathcal{S}}_n$ by random permutations and the distribution of
transitive subgroups of $\ensuremath{\mathcal{S}}_n$.
See e.g. \cite{dfg08, camkan, EFG1, EFG2, EFK, FGK, LP, PPR, weingartner}.


\begin{lem}
 ${\mathbb E}\, 2^{C(\sigma)} = n+1$.
\end{lem}

\begin{proof}
Evidently, $2^{C(\sigma)}$ equals the number of ways to write
$\sigma=\beta_1 \beta_2$, with $\beta_j|\sigma$ for each
$j$, $\beta_i=()$ being allowed.  The permutation $\beta_1$
fixes a set $I$.  Summing over $I$ we see that
\begin{align*}
{\mathbb E}\, 2^{C(\sigma)} &= \frac{1}{n!} \sum_{\sigma\in \ensuremath{\mathcal{S}}_n} \sum_{\beta|n}
1 = \frac{1}{n!} \sum_{I \subseteq [n]} \ssum{\sigma\in \ensuremath{\mathcal{S}}_n \\ \sigma\text{ fixes
  }I} 1 \\
&= \frac{1}{n!}  \sum_{I \subseteq [n]} (n-|I|)! |I|! \\
&= \frac{1}{n!} \sum_{j=0}^n (n-j)!j!  \ssum{I \subseteq [n] \\ |I|=j}
1 = \sum_{j=0}^n 1 = n+1. \qedhere
\end{align*}
\end{proof}

By contrast, we know that $C(\sigma) \sim \log n$ for most $\sigma\in
\ensuremath{\mathcal{S}}_n$, and therefore for most $\sigma\in \ensuremath{\mathcal{S}}_n$,
$2^{C(\sigma)} \approx 2^{\log n} = n^{\log 2}$, much smaller than $n$.

\bigskip


A basic problem is to estimate $i(n,k)$, the probability that $\pi$ fixes some set of size $k$.   Equivalently, what is the probability that the cycle decomposition of $\pi$ contains disjoint cycles with lengths summing to $k$?  Evidently, $i(n,k)=i(n,n-k)$, thus it
suffices to bound $i(n,k)$ for $k\le n/2$.
Sharpening earlier bounds due to Diaconis, Fulman and Guralnick \cite{dfg08}, {\L}uczak and Pyber \cite{LP} and by Pemantle, Peres, and Rivin \cite[Theorem 1.7]{PPR}, the author with Eberhard and Green
\cite{EFG1} proved that
\begin{equation}\label{ink}
 \frac{1}{k^{\ensuremath{\mathcal{E}}}(1+\log k)^{3/2}} \ll
i(n,k) \ll \frac{1}{k^{\ensuremath{\mathcal{E}}}(1+\log k)^{3/2}},
\quad \ensuremath{\mathcal{E}} = 1- \frac{1+\log\log 2}{\log 2}=0.08607\ldots,
\end{equation}
uniformly for $1\le k\le n/2.$  A full asymptotic is not known.

This is the permutation analog of counting integers with a 
divisor in a given interval, see e.g. \cite{F08,F08b},
and is related to the Erd\H os' multiplication table problem
(\cite{Erdos55,Erdos60}),
that of estimating the 
number, $A(N)$, of \emph{distinct} products of the form $ab$ with $a\le N$, $b\le N$. 
The full proof of \eqref{ink} is rather complicated.
However, using the tools we have developed in this paper, we can quickly obtain an upper bound which is close to optimal.

\begin{thm}\label{thm:fixed-set}
Uniformly for $1\le k\le n/2$ we have
\[
i(n,k) \ll \frac{1}{k^{\ensuremath{\mathcal{E}}}}.
\]
\end{thm}

\begin{proof}
The statement is trivial for $1\le k\le 100$, thus we may assume
that $k>100$.  Let $r_0 = \frac{\log k}{\log 2}$. 
If $\sigma$ has a fixed set of size $k$, then $\sigma$ factors
as $\sigma = \a \b$, where $\a$ has size $k$ and $\b$ has size $n-k$.  By Corollary \ref{cyclesinterval},
\[
\mathbb P( C_{[k]}(\sigma)>r_0 ) \ll k^{-Q(1/\log 2)}  = k^{-\ensuremath{\mathcal{E}}}.
\]
If $C_{[k]}(\sigma)=r\le r_0$, then for some
non-negative integers $j,h$ we have
\begin{equation}\label{alphabeta}
C(\alpha)=j, \qquad C_{[k]}(\b)=h.
\end{equation}
By relabeling  the indices, we may assume that
$\a\in \ensuremath{\mathcal{S}}_{k}$ and $\b \in \ensuremath{\mathcal{S}}_{n-k}$.
With $j,h$ fixed the number of pairs $\a,\b$ with
\eqref{alphabeta} is at most
\[
\binom{n}{k} k! \mathbb P(C(\alpha)=j) (n-k)! \mathbb P(C_{[k]}(\b)=h)
\ll n! \frac{H_k^{j+h} e^{-2H_k}}{j!h!},
\]
upon invoking Lemma \ref{cycles_sets}.
Summing first over all $j,h$ with $h+j=r$ using the binomial theorem, and then over $r \le r_0$ we obtain
an upper bound for the 
probability that $\sigma$ factors as $\sigma=\a\b$ with
$|\a|=k$ and $C_{[k]}(\sigma) \le r_0$ of
\[
\ll \frac{1}{k^2} \sum_{r\le r_0} \frac{(2H_k)^r}{r!}
k^{-Q(\frac{1}{2\log 2})} \ll k^{-\ensuremath{\mathcal{E}}},
\]
upon invoking Prop. \ref{Poisson_tails}.
\end{proof}





\section{Conditioning on the total number of cycles of $\sigma$}

When $k$ is fixed and $C(\sigma)=k$, for any $I\subset [k]$
the statistic $C_I(\sigma)$ has roughly a binomial distribution
with parameter $p=H(I)/H_n$.  We make this precise here.   
   
We will use an explicit Chernoff bound for tails of the binomial distribution (see, e.g. \cite[Lemma 4.7.2]{Ash} or Theorem 6.1 in \cite{ten17}).

\begin{prop}[Binomial tails]\label{binomial_tails}
Let $X$ have binomial distribution according to $n$ trials and parameter $p\in [0,1]$;
that is, $\mathbb P(X=k)=\binom{n}{k} p^k (1-p)^{n-k}$.
If $\beta\le p$ then we have
\[
\mathbb P(X\le \beta n) \le \exp \left\{ - n \( \b \log \frac{\b}{p} + (1-\b) \log \frac{1-\b}{1-p} \) \right\}
\le \exp \bigg\{-\frac{(p-\beta)^2n}{3p(1-p)} \bigg\}.
\]
Replacing $p$ with $1-p$ we also have for $\beta\ge p$,
\[
\mathbb P(X\ge \beta n) \le  \exp \bigg\{-\frac{(p-\beta)^2n}{3p(1-p)} \bigg\}.
\]
\end{prop}

\begin{proof}[Proof of Theorem \ref{conditional-tails}]
Apply
Theorem \ref{cycles_sets} with two sets: $I$ and $[n]\setminus I$.
Here $\ensuremath{\varepsilon}=0$.  Divide by $\mathbb P(C(\sigma)=k)$, where a lower bound
is given in Theorem \ref{allsets-local}.  Set $p=H(I)/H_n$. Then, for $0\le h\le k$,  
\[
\mathbb P\Big(C_I(\sigma)=h | C(\sigma)=k \Big) \ll_A
p^{h-1} (1-p)^{k-h} \binom{k-1}{h-1} +
p^h (1-p)^{k-h-1} \binom{k-1}{h},
\]
the first term vanishing if $h=0$ and the second vanishing if $h=k$.
By Lemma \ref{binomial_tails},
\[
\mathbb P\Big(C_I(\sigma)\le p(k-1) - \psi\sqrt{p(1-p)(k-1)}\;\; \big|\;\; C(\sigma)=k \big) \ll_A \mathrm{e}^{-\frac13 \psi^2}
\]
and, since $0 \le \psi \le \sqrt{pk}$,
\begin{align*}
\mathbb P\Big(C_I(\sigma)\ge p(k-1) + \psi\sqrt{p(1-p)(k-1)}\;\; \big|\;\; \sigma\in \ensuremath{\mathcal{S}}_{n,k} \Big) &\ll_A
\exp\bigg\{  - \frac{(\psi\sqrt{p(1-p)(k-1)}-1)^2}{3p(1-p)(k-1)} \bigg\}\\
&\ll_A \mathrm{e}^{-\frac13 \psi^2}.
\end{align*}
This completes the proof.
\end{proof}





\section{Permutations without small cycles}




Our proof of Theorem \ref{nosmallcycles2} is based on the Brun-Hooley sieve \cite{BrunHooley}
from number theory.

\begin{proof}[Proof of Theorem \ref{nosmallcycles2}]
Let $K$ be fixed an sufficiently large.  If $n/m \le K$, then
by Corollary \ref{cycles-single-set}, $\mathbb P(C_{[m]}(\sigma)=0)\ll 1/m$ and 
the conclusion follows.  Now assume that $n/m > K$.
Let 
\[
D = \log(n/m),
\]
so that $D\ge 2$.
Partition $[m]$ into intervals $I_j=[z_j,z_{j-1})\cap {\mathbb N}$, where $z_j=m/D^j$,
$0\le j\le \cl{\frac{\log m}{\log D}}=t$. 
Let $k_1,\ldots,k_t$ be positive, even integers, subject to
\begin{equation}\label{kj-cond}
k_j \ge 10\log D, \qquad \sum_{j=1}^t \frac{(k_j+1) m}{D^{j-1}} \le n.
\end{equation}
With $\sigma$ fixed, let
\[
x_j = \one(C_{I_j}(\sigma)=0), \quad y_j = \sum_{r=0}^{k_j} (-1)^r \binom{C_{I_j}(\sigma)}{r}.
\]
By Inclusion-Exclusion (Prop.  \ref{incl-excl}), we have
\[
0\le y_j - x_j = \binom{C_{I_j}(\sigma)-1}{k_j+1} \le \binom{C_{I_j}(\sigma)}{k_j+1}.
\]
Using the elementary inequality
 \[
x_1\cdots x_t \ge y_1\cdots y_t - \sum_{\ell=1}^t (y_\ell-x_\ell) \sprod{j=1 \\ j\ne \ell}^t y_j,  
 \]
we thus obtain
\begin{equation}\label{small-ME}
\mathbb P(C_{[m]}(\sigma)=0) =  {\mathbb E}\, x_1\cdots x_t = {\mathbb E}\, \Bigg[y_1 \cdots y_t + O\Bigg( \sum_{\ell=1}^t \binom{C_{I_\ell}(\sigma)}{k_\ell+1} \prod_{j\ne \ell} y_j \Bigg) \Bigg]=M+O(E),
\end{equation}
say, where $M={\mathbb E}\, y_1\cdots y_t$ is the ``main term'' and $E$ is the ``error term''.
The condition \eqref{kj-cond} implies that 
\begin{equation}\label{kjmaxIj-2}
\sum_j (k_j+1) \max I_j \le n.
\end{equation}
  Thus, by
Theorem \ref{cycles_sets_expectation},
\[\begin{aligned}
M &= \ssum{r_1,\ldots,r_t \\ 0\le r_j\le k_j (1\le j\le t)} 
(-1)^{r_1+\cdots+r_t} {\mathbb E}\, \binom{C_{I_1}(\sigma)}{r_1} \cdots \binom{C_{I_t}(\sigma)}{r_t} \\
&=  \ssum{r_1,\ldots,r_t \\ 0\le r_j\le k_j (1\le j\le t)} 
(-1)^{r_1+\cdots+r_t} \prod_{j=1}^t \frac{H(I_j)}{r_j!} 
= \prod_{j=1}^t \Bigg( \sum_{r_j=0}^{k_j} \frac{(-H(I_j))^{r_j}}{r_j!}    \Bigg).
\end{aligned}\]
Since $H(I_j)=\log D+O(1)$ for every $j$, 
and recalling \eqref{kj-cond}, we have 
\begin{align*}
\sum_{r_j=0}^{k_j} \frac{(-H(I_j))^{r_j}}{r_j!} &= \mathrm{e}^{-H(I_j)} + O\pfrac{(\log D+O(1))^{k_j+1}}{(k_j+1)!}\\
&=\mathrm{e}^{-H(I_j)} \bigg( 1 + O \pfrac{D(\log D+O(1))^{k_j+1}}{(k_j+1)!}  \bigg)\\
&=\mathrm{e}^{-H(I_j)} \exp\bigg[ O\bigg(\sum_{j=1}^t \frac{D(\log D+O(1))^{k_j+1}}{(k_j+1)!}\bigg) \bigg].
\end{align*}
Hence, the main term satisfies
\begin{equation}\label{small-M}
M = e^{-H_m} \exp\left[ O\(\sum_{j=1}^t \frac{D(\log D+O(1))^{k_j+1}}{(k_j+1)!}\) \right].
\end{equation}
Similarly, using \eqref{kj-cond},  the error term satisfies
\begin{align*}
E &=  \sum_{\ell=1}^t \ssum{r_j (j\ne \ell) \\ 0\le r_j\le k_j (j\ne \ell))} 
(-1)^{\sum_{j\ne \ell} r_j} {\mathbb E}\, \binom{C_{I_\ell}(\sigma)}{k_\ell+1} 
\prod_{j\ne \ell} \binom{C_{I_j}(\sigma)}{r_j} \\
&=  \sum_{\ell=1}^t
 \frac{H(I_\ell)^{k_\ell+1}}{(k_\ell+1)!} \prod_{j\ne \ell}
\Bigg( \sum_{r_j=0}^{k_j} \frac{(-H(I_j))^{r_j}}{r_j!}  \Bigg) .
\end{align*}
Hence,
\begin{equation}\label{small-E}
E=\sum_{\ell=1}^t \frac{\mathrm{e}^{H(I_\ell)}(\log D+O(1))^{k_\ell+1}}
{(k_\ell+1)!} \mathrm{e}^{-H_m} \exp\left[ O\(\sum_{j=1}^t \frac{D(\log D+O(1))^{k_j+1}}{(k_j+1)!}\) \right].
\end{equation}
We now take
\[
k_j=k_1+2(j-1) \quad (j\ge 1), \;\; k_1=2\fl{\frac{D-1}{D} \cdot \frac{n}{2m}}-6,
\]
and readily verify that the conditions \eqref{kj-cond} hold if
$K$ is large enough.
Thus, by Stirling's formula,
\begin{align*}
\sum_{j=1}^t \frac{D(\log D+O(1))^{k_j+1}}{(k_j+1)!} 
&\ll \frac{D(\log D+O(1))^{k_1+1}}{(k_1+1)!} \\
&\le \mathrm{e}^{-(n/m)\log (n/m) + (n/m)\log\log\log (n/m) + O(n/m)}
\end{align*}
and likewise
\[
\sum_{\ell=1}^t \frac{\mathrm{e}^{H(I_\ell)}(\log D+O(1))^{k_\ell+1}}
{(k_\ell+1)!} \le  \mathrm{e}^{-(n/m)\log (n/m) + (n/m)\log\log\log (n/m) + O(n/m)}.
\]
Inserting these last two bounds into 
\eqref{small-M} and \eqref{small-M}, and recalling \eqref{small-ME},
the proof is complete.
\end{proof}








\section{Permutations without large cycles}

The traditional approach to the problem of
estimating the probability that a random permutation
has no cycle of size $>m$ is via
generating functions, e.g. Theorem \ref{genfcn}.
The sharpest results depend on a lengthy complex-analytic
argument, see \cite{Pet16, ManPet16}.

Here we use a simple combinatorial device,
combining analogs of the ``$\log x$'' trick and the 
``Rankin trick'' from number theory. Not surprisingly the
generating function makes an appearance.

\begin{proof}[Proof of Theorem \ref{nolargecycles}]
Let $I=(m,n]\cap {\mathbb N}$. 
By Cauchy's formula (Theorem \ref{thm:Cauchy}), we have
\[\begin{aligned}
n \mathbb P(C_{I}(\sigma)=0) &= \ssum{b_1,\ldots,b_m\ge 0 \\
b_1+2b_2+\cdots+ma_m=n} \prod_{j=1}^m \frac{(1/j)^{b_j}}{b_j!} \sum_{b_\ell\ge 1} \ell b_\ell \qquad (a_j=b_j-\one(j=\ell)) \\ 
&=
\sum_{\ell \le m} \ssum{a_1,\ldots,a_m\ge 0 \\
a_1+2a_2+\cdots+ma_m=n-\ell} \frac{1}{\prod_{j=1}^m a_j! j^{a_j}} \\
&=\ssum{a_1,\ldots,a_m\ge 0 \\ 
a_1+2a_2+\cdots+ma_m \in [n-m,n-1]} \frac{1}{\prod_{j=1}^m a_j! j^{a_j}}. 
\end{aligned}\]
Let  $w = u^{1/m}$, where $u=n/m$.  We have
\[\begin{aligned}
n \mathbb P(C_{I}(\sigma)=0) &\le \sum_{a_1,\ldots,a_m\ge 0} \frac{w^{a_1+\cdots+ma_m -(n-m)}}{\prod_{j=1}^m a_j! j^{a_j}}\\
&=w^{m-n} \exp \Big\{ w + \frac12 w^2 + \cdots + \frac{1}{m} w^m \Big\}.
\end{aligned}\]
The mean value theorem implies that $u^x \le 1 + (u-1)x$ for $0\le x\le 1$ and hence
\begin{equation}\label{powers-w}
 w + \frac12 w^2 + \cdots + \frac{1}{m} w^m \le \sum_{j=1}^m \frac{1+(u-1)j/m}{j}=H_m+u-1.
\end{equation}
We conclude that
\[
\mathbb P(C_{I}(\sigma)=0) \le \frac{1}{n} u^{1-n/m} \mathrm{e}^{\log m+u} =
\mathrm{e}^{-u\log u + u }. \qedhere
\]
\end{proof}









\section{Poisson approximation of small cycle lengths}


In this section, we prove Theorem \ref{Poisson_smallcycles}, which
 shows that $C_j(\sigma)$ is approximately Poisson with parameter
 $1/j$, uniformyl for small $j$.

We begin by relating $d_{TV}(\ensuremath{\mathcal{C}}_k, \ensuremath{\mathcal{Z}}_k)$ to $\mathbb P(C_{[m]}(\sigma)=0)$ using a special case of 
\cite[eq. (33)]{AT94}.  For completeness, we give a short proof.

\begin{lem}\label{dTVCkZk}
We have
\[
d_{TV}(\ensuremath{\mathcal{C}}_k, \ensuremath{\mathcal{Z}}_k) = \frac12 \sum_{\ensuremath{\mathbf{h}}\in {\mathbb N}_0^k} \prod_{j=1}^k \frac{1}{j^{h_j} h_j!} \Big| \mathrm{e}^{-H_k} -  \one(n' \ge 0) \mathbb P_{n'}(C_{[k]}(\sigma)=0)\Big|, 
\]
where $n'=n'(\ensuremath{\mathbf{h}}) = n-\sum_{j=1}^k jh_j$.
\end{lem}

\begin{proof}
We begin with the easy identity
\[
d_{TV}(\ensuremath{\mathcal{C}}_k, \ensuremath{\mathcal{Z}}_k) = \frac12 \sum_{\ensuremath{\mathbf{h}}\in {\mathbb N}_0^k} \left| \mathbb P(\ensuremath{\mathcal{C}}_k = \ensuremath{\mathbf{h}}) - \mathbb P(\ensuremath{\mathcal{Z}}_k=\ensuremath{\mathbf{h}}) \right|. 
\]
Clearly,
\[
\mathbb P(\ensuremath{\mathcal{Z}}_k=\ensuremath{\mathbf{h}}) = \mathrm{e}^{-H_k} \prod_{j=1}^k  \frac{1}{j^{h_j} h_j!}.
\]
Now suppose that $\ensuremath{\mathcal{C}}_k=\ensuremath{\mathbf{h}}$ and write $g = h_1+2h_2+\cdots+kh_k$.
If $g>n$, then $\mathbb P(\ensuremath{\mathcal{C}}_k=\ensuremath{\mathbf{h}})=0$.  Now suppose that $g\le n$.
Write $\sigma= \sigma_1 \sigma_2$, where $\sigma_1$ is the product of the cycles of length
at most $k$ and permutes a subset $I_1$ of $[n]$ of size 
$g$, and $\sigma_2$ is the product of the cycles of length greater than $k$ and permutes $[n]\setminus I$ of size $n'=n-g$.  By Cauchy's formula (Theorem \ref{thm:Cauchy}), applied to $\sigma_1$, it follows that
\[
\mathbb P(\ensuremath{\mathcal{C}}_k=\ensuremath{\mathbf{h}}) = \mathbb P_{n'}(C_{[k]}(\sigma)=0) \prod_{j=1}^k  \frac{1}{j^{h_j} h_j!},
\]
and the lemma follows.
\end{proof}

\begin{proof}[Proof of Theorem \ref{Poisson_smallcycles}]
We may assume that $k\le n/100$.  We will use Lemma \ref{dTVCkZk}
and estimate the contribution to $d_{TV}(\ensuremath{\mathcal{C}}_k,\ensuremath{\mathcal{Z}}_k)$
from the tuples
 $\ensuremath{\mathbf{h}}=(h_1,\cdots,h_k)\in {\mathbb N}_0^k$.  The main idea of the proof is to separately consider those
vectors which constitute rare events (many $h_j$ large): specifically, let
\[\begin{aligned}
\mathcal{H}_1&=\{ \ensuremath{\mathbf{h}}\in {\mathbb N}_0^k: h_1+2h_2+\cdots+kh_k \le n-50k \}, \\
\mathcal{H}_2&=\{ \ensuremath{\mathbf{h}}\in {\mathbb N}_0^k: h_1+2h_2+\cdots+kh_k > n-50k \}.
\end{aligned}\]
First, consider  $\ensuremath{\mathbf{h}}\in \mathcal{H}_1$ and let $n'=n-(h_1+2h_2+\cdots+kh_k)\ge 50k$.
By Theorem \ref{nosmallcycles2},
\[
\mathbb P_{n'}(C_{[k]}(\sigma)=0) = \mathrm{e}^{-H_k} \(1 + O(e^{-g(n'/k)})\),
\]
where $g(x)=-x\log x + x\log\log\log x+O(x)$ when $x\ge 50$. It follows that
\[
\sum_{\ensuremath{\mathbf{h}}\in\mathcal{H}_1} \prod_{j=1}^k  \frac{1}{j^{h_j} h_j!} \Big| \mathrm{e}^{-H_k} - \one(n' \ge 0)\mathbb P_{n'}(C_{[k]}(\sigma)=0)\Big| \ll \mathrm{e}^{-H_k} \ssum{\ensuremath{\mathbf{h}}\in \ensuremath{\mathcal{H}}_1}  e^{-g(n'/k)} \prod_{j=1}^k \frac{1}{j^{h_j} h_j!}.
\]
For $\ensuremath{\mathbf{h}} \in \mathcal{H}_2$, 
\[
\mathrm{e}^{-H_k} - \one(n' \ge 0)\mathbb P_{n'}(C_{[k]}(\sigma)=0) =
O(e^{-H_k}) = O(1/k)
\]
by Corollary \ref{cycles-single-set} and the bound for the harmonic sum (Proposition \eqref{harmonic}); note that if $n'\le k$ then $\ensuremath{\mathcal{T}}_{n',k}=0$.
We conclude that
\begin{equation}\label{sumrhh}
\sum_{\ensuremath{\mathbf{h}}\in{\mathbb N}_0^k} \prod_{j=1}^k  \frac{1}{j^{h_j} h_j!} \Big| \mathrm{e}^{-H_k} - \one(n' \ge 0) \mathbb P_{n'}(C_{[k]}(\sigma)=0)\Big| \ll \frac{1}{k}\sum_{50\le r\le n/k+1}\mathrm{e}^{-g(r)}
\ssum{\ensuremath{\mathbf{h}}\in {\mathbb N}_0^k \\ n' < rk} 
\prod_{j=1}^k \frac{1}{j^{h_j} h_j!}.
\end{equation}
Now we invoke the method of parameters, also known as the tilting method
(this is commonly used in Chernoff inequalities; see Section 0.5 in \cite{Divisors} for number theoretic applications).
For any real number $w\ge 1$ we have
\begin{align*}
\ssum{\ensuremath{\mathbf{h}}\in {\mathbb N}_0^k \\ n'<rk} \prod_{j=1}^k \frac{1}{j^{h_j}h_j!} &\le \sum_{\ensuremath{\mathbf{h}}\in{\mathbb N}_0^k}
w^{h_1+2h_2+\cdots+kh_k-n+rk} \prod_{j=1}^k \frac{1}{j^{h_j}h_j!} 
\\ &= w^{-n+rk} \exp\left\{ w+ \frac12 w^2+ \cdots + \frac{1}{k} w^k\right\}.
\end{align*}
Take $w=(u-r+2)^{1/k}$ where $u=\frac{n}{k}$.  By the argument in \eqref{powers-w}, 
\[
 w+ \frac12 w^2+ \cdots + \frac{1}{k} w^k \le H_k+u-r+1
 \le \log k + u-r+2.
\]
It follows that
\[
\ssum{\ensuremath{\mathbf{h}}\in {\mathbb N}_0^k \\ n'<rk} \prod_{j=1}^k \frac{1}{j^{h_j}h_j!}
\ll k \exp \big\{ -(u-r)\log(u-r+2)+(u-r)\big\}.
\]
Inserting this into \eqref{sumrhh}, we find that
\begin{align*}
d_{TV}(\ensuremath{\mathcal{C}}_k,\ensuremath{\mathcal{Z}}_k) &\ll \mathrm{e}^{u\log\log\log u+O(u)} \sum_{50\le r\le u+1} \mathrm{e}^{-r\log r + (u-r)\log(u-r+2)}\\
&\ll \mathrm{e}^{-u\log u + u\log\log\log u+O(u)}.
\qedhere
\end{align*}
\end{proof}






\section{Central Limit Theorems}


A principal tool is the fact that, as $\lambda\to\infty$, 
the Poisson random variable with parameter $\lambda$ approaches a Gaussian distribution
with mean $\lambda$ and variance $\lambda$.  The following is a special case of the Central Limit Theorem with Berry-Esseen type rate of convergence.
It may also be proved in an elementary way using
 Stirling's formula and Euler summation.


\begin{lem}[Poisson CLT]\label{Poisson_CLT}
Let $\lambda \ge 1$, and let $X$ be Poisson with parameter $\lambda$.
Uniformly for real $\lambda\ge 1$ and real $z$, we have
\[
\mathbb P \( X \le \ensuremath{\lambda} + z\sqrt{\ensuremath{\lambda}} \) = \Phi(z) + O\( \lambda^{-1/2} \), \qquad \Phi(z)=\frac{1}{\sqrt{2\pi}} \int_{-\infty}^z \mathrm{e}^{-\frac12 t^2}\, dt.
\]
\end{lem}




\begin{proof}[Proof of Theorem \ref{CLT_cycles}]
Let $H=H(I)$.
If $|w|\ge \log H$ then the result follows
from Theorem \ref{cycles-single-set}, since
the left side is thus $O(1/H)$ if $w\le -\log H$ and is $1-O(1/H)$ if $w\ge \log H$.
Suppose now that $|w| < \log H$, let
 $A=H + w\sqrt{H}$ and
\[
m=\cl{\frac{n}{\log H}}, \qquad J = I \cap [m].
\]
Because 
\[
H(I\setminus J) =\ssum{m<k\le n \\ k\in I} \frac{1}{k} \le H((m,n]\cap {\mathbb N}) \le \log\log H+O(1)
\]
we have $H(J) = H + O(\log\log H)$.  Thus,
\[
A =  H(J) + w'\sqrt{H(J)}, \quad w'=w+O\pfrac{\log\log H}{\sqrt{H}}.
\]
Thus, by Theorem \ref{poisson_cycles} and Lemma \ref{Poisson_CLT},
\[\begin{aligned}
\mathbb P ( C_I(\sigma) \le A ) &\le \mathbb P ( C_J (\sigma) \le A) \\
&=\Phi(w') + O\( H(J)^{-1/2} + \mathrm{e}^{-n/m} \) \\
&=\Phi(w') + O\pfrac{1}{\sqrt{H}} \\
&= \Phi(w) +O\pfrac{\log\log H}{\sqrt{H}}.
\end{aligned}\]

 We also  have
\[
A - \log H = H(J) + w''\sqrt{H(J)}, \quad w'=w+O\pfrac{\log H}{\sqrt{H}}
\]
and it follows from the Cycles CLT (Theorem \ref{CLT_cycles})
 that
\[\begin{aligned}
\mathbb P ( C_I(\sigma) \le A ) &\ge \mathbb P \( C_{J} (\sigma) \le A - \log H  \text{ and } C_{I\setminus J}(\sigma) \le \log H  \)\\
&=\mathbb P \( C_{J} (\sigma) \le A - \log H  \)\\
&=\Phi(w'') + O(1/\sqrt{H}) \\
&=\Phi(w) + O\pfrac{\log H}{\sqrt{H}}.
\end{aligned}\]
The theorem follows by combining the upper and lower bounds
for $\mathbb P(C_I(\sigma)\le A)$.
\end{proof}


\begin{proof}[Proof of Theorem \ref{jth-smallest-cycle}]
We may assume that $j\ge 10$ and that $n$ is sufficiently large, the statement being trivial 
otherwise.
Let $k=\fl{e^{j+w\sqrt{j}}}$.  Then $D_j(\sigma)\le k$ is equivalent to $C_{[k]}(\sigma) \ge j$. 
We may assume that $|w| \le 2\sqrt{\log j}$, since the
statement for $w$ outside this range follows from the
monotonicity of $\mathbb P(C_{[k]}\ge j)$, as a function of $w$,
and the statement for $w = \pm 2\sqrt{\log j}$.

 As $H_k=\log k + O(1)$ and $\sqrt{\log k}=\sqrt{j}+O(|w|)$, we have
\[
j = H_k - u\sqrt{H_k}, \quad\text{where}\quad u = w + O\pfrac{w^2}{\sqrt{j}}.
\]
 By Theorem \ref{CLT_cycles},
\[
\mathbb P(D_j(\sigma)\le k) = \mathbb P(C_{[k]}(\sigma) \ge j) = 1-\Phi(u)+O \( \frac{\log H_k}{\sqrt{H_k}} + e^{-n/k} \).
\]
By hypothesis, 
\begin{align*}
\log k &\le \log n - (\log n)^{1/2}\log\log n + |w|(\log n)^{1/2}\\ 
&\le \log n - (\log n)^{1/2}\log\log n + 2\sqrt{\log\log n}(\log n)^{1/2} \\
&\le \log n - \frac12 (\log n)^{1/2}\log\log n
\end{align*}
for large $n$.  Thus, 
\[
e^{-n/k} \ll \frac{1}{\log n} \le \frac{1}{j}.
\]
 Also,
\[
\Phi(u) = \Phi(w)+O\pfrac{w^2}{\sqrt{j}} = \Phi(w) + 
O\pfrac{\log (2j)}{\sqrt{j}}
\]
and the proof is complete.
\end{proof}










