\section{Introduction}
\vspace{-3mm}

Efficient exploration in the absence of dense reward signals is a long-standing problem in reinforcement learning~\citep{vecerik2017leveraging}. Without dense extrinsic signals, a promising alternative is to define suitable auxiliary \textit{intrinsic} signals that can help the agent in exploring its environment~\citep{laud2004theory}. Recently, \textit{curiosity} has emerged as a promising computational framework for modeling intrinsic reward and has brought major advances in many sparse-reward domains~\citep{pathak2017curiosity,burda2018large,burda2018exploration,pathak2019self,dean2020see}. While the algorithmic details of different methods vary, the core idea is to use changes in the observed state as the intrinsic reward to encourage agents to explore their environment. Despite their strong performance on many sparse-reward tasks, these existing approaches tend to rely on a holistic view of state transitions and do not allow for a targeted understanding of specific aspects of the environment. However, not all states are equally interesting but such information is not available to the agent a priori. On the contrary, humans rely on extensive knowledge about the world when exploring the environment. Language serves as a powerful medium for encoding this knowledge. A particular type of language that humans use is \textit{question} -- in an unfamiliar environment, humans often start the exploration by asking what can be done in the environment.
Based on this observation, we hypothesize that \textit{language-based question answering} may provide a grounded and targeted medium to probe specific knowledge about the current state in order to solve the task at hand.

As a step towards more structured and flexible curiosity-driven learning, we develop a novel form of curiosity, \textsc{Ask \& Explore}\ (\textsc{AnE}), that leverages \textit{grounded question answering} to encourage the agent to ask questions about the environment and be curious when the answers to these questions change. These questions can capture physical properties of the objects (e.g., \textit{Is the large sphere green in color?}) as well as their spatial relationships with other objects (e.g., \textit{Are there any blue spheres behind the cyan ball?}). By using language as a compositional medium to uncover specific knowledge about the environment, we are able to train an agent that explores and solves challenging long-horizon sparse-reward tasks. In addition to our qualitative results, we perform an in-depth study of what type of questions are useful under what scenarios to provide empirical guidelines for applying our method.

\vspace{-3mm}
\section{Background}
\vspace{-3mm}

\textbf{Exploration bonuses and curiosity-driven exploration}. Exploration bonuses motivate agents to explore their environment even when extrinsic reward $r_t^e$ is sparse (or zero) by training the policy to maximize a new reward $r_t = r_t^e + r_t^i$, where $r_t^i$ is the exploration bonus or the intrinsic reward at time $t$~\citep{krebs2009novelty,dayan1996exploration,sutton1990integrated}. The intrinsic reward $r_t^i$ is designed to be higher in novel states in order to encourage the agents to explore less frequently visited states. In recent years, several promising algorithms in this family include: 1) Curiosity-driven exploration by self-supervised prediction~\citep{pathak2017curiosity,burda2018large,pathak2019self}, which formulates an intrinsic reward that encourages the agent to favor transitions with high prediction error using dynamics-based learning, and 2) Random Network Distillation (RND)~\citep{burda2018exploration}, which encourages novelty by training the policy to minimize the prediction error of a predictor neural network as it tries to mimic a randomly initialized target neural network. Several other approaches have used count-based exploration~\citep{bellemare2016unifying, tang2017exploration} and multimodal signals~\citep{dean2020see} to encourage exploration.

\textbf{CLEVR-Robot Environment:} We perform experiments using the CLEVR-Robot Environment~\citep{jiang2019language}, an open-source object interaction environment built using the MuJoCo physics engine~\citep{todorov2012mujoco} and CLEVR language engine~\citep{johnson2017clevr}. The environment is designed to serve as a testbed for studying grounded language understanding and object manipulation. To succeed in this environment, the agent must be able to handle a varying number of objects with diverse visual and physical properties (see details in Appendix~\ref{app_dataset}).

\begin{figure}[tbp]
\centering
\vspace{-6mm}
\includegraphics[width=\linewidth]{images/approach.pdf}
\caption{\textbf{\textsc{Ask \& Explore}}: Our approach proposes a curiosity formulation that leverages grounded question answering to query specific knowledge about the environment. The agent is encouraged to ask questions and be curious about transitions when the answer to a question changes (details in Section~\ref{sec: approach}).\vspace{-6mm}}
\label{fig:approach}
\end{figure}

\vspace{-3mm}
\section{\textsc{Ask \& Explore}}
\label{sec: approach}
\vspace{-3mm}

Our goal is to develop an intrinsic reward that leverages the knowledge about the physical properties of objects and how objects in the environment relate to each other. Such intrinsic reward may bridge the gap between passive pattern recognition and active decision making. To design the intrinsic reward, we chose grounded language as a flexible medium for encoding this knowledge. The CLEVR-Robot environment provides an ideal testbed for using grounded language as a source of intrinsic reward as it provides functionalities to generate scenes and language (in the form of questions) that can be evaluated as the agent interacts with the environment. Note that access to the true state and language is not required. Indeed, for an agent in the real world, such assumptions do not hold. Nonetheless, just like humans can describe a scene with language, the agent can also be equipped with a parameterized visuolinguistic model such as a visual question answering model (VQA) or image captioning model. We plan to explore these directions in future works.

We formulate an intrinsic reward that aims to generate the agent's curiosity about transitions when the answers to the agent's questions grounded in the environment change. At every step, the agent has access to $n$ questions, $q_1, q_2, ... q_n$. For question $q_k$, the difference in the answer before the transition $A(s_t, q_k)$, and after the transition $A(s_{t+1}, q_k)$ contributes to the curiosity signal corresponding to that action (Figure \ref{fig:approach}). To evaluate $A(s_t, q_k)$, we experiment with two types of intrinsic rewards that leverage language. One of them uses the labeling function of the CLEVR-Robot environment and the other utilizes a parameterized VQA model (experiments with the latter can be found in Appendix \ref{app_vqa}). The intrinsic reward at time $t$, $r^i_t$, expressed as
\begin{equation}
     r_t^i = \sum_{k=1}^n \mathbbm{1}[A(s_t, q_k) \neq A(s_{t+1}, q_k)]
\end{equation}

Further algorithmic details such as how the questions are selected can be found in Appendix \ref{imp_details}.

\begin{figure}[tbp]
\centering
\begin{subfigure}[t]{0.24\columnwidth}
\centering
\includegraphics[width=0.99\linewidth, height=0.8\linewidth]{images/simplegoal_init.png}
\vspace{-0.5cm}
\caption{\scriptsize \centering Goal is: ``{\it There is a \textbf{\textcolor{green}{green}} sphere; are there any rubber \textbf{\textcolor{cyan}{cyan}} balls \textbf{in front of} it?}".}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\columnwidth}
\centering
\includegraphics[width=0.99\linewidth, height=0.8\linewidth]{images/simplegoal_transition.png}
\vspace{-0.5cm}
\caption{\scriptsize \centering Agent performs actions and interacts with the environment and tries to satisfy goal.}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\columnwidth}
\centering
\includegraphics[width=0.99\linewidth, height=0.8\linewidth]{images/simplegoal_end.png}
\vspace{-0.5cm}
\caption{\scriptsize \centering Resulting state: Agent receives \textbf{+1} reward.}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\columnwidth}
\centering
\includegraphics[width=0.99\linewidth, height=0.8\linewidth]{images/order.png}
\vspace{-0.5cm}
\caption{\scriptsize \centering Object ordering}
\end{subfigure}
\caption{We use the CLEVR-Robot environment and consider both dense (a-c) and sparse (d) reward settings. The global location of the objects vary across episodes (images from~\citet{jiang2019language}).\vspace{-4mm}}
\label{fig:clevr_env}
\end{figure}

\vspace{-3mm}
\section{Experiments}
\vspace{-3mm}

We design our experiments to understand the following overarching question: \textit{Does an agent with grounded language understanding explore the environment in a more structured and efficient manner?} To answer different aspects of this question, we first evaluate our approach in tasks with different reward sparsity (Section \ref{sec: varying_sparsity}). Then, we evaluate the impact of different types of grounded language understanding on the performance and how the impact differs in settings with varying reward sparsity (Section \ref{sec: varying_complexity}). Finally, we study the effect of the linguistic feedback's density on the efficacy of exploration (due to space limit, we defer the details to Appendix \ref{app_multiple_ques}).

We compare our approach to three baselines:

1. Proximal Policy Optimization (PPO)~\citep{schulman2017proximal} (no exploration bonus)

2. Intrinsic Curiosity Module (ICM)~\citep{pathak2017curiosity}

3. Random Network Distillation (RND)~\citep{burda2018exploration}.

We use the same optimized hyperparameters from the original papers~\citep{pathak2017curiosity, burda2018exploration}. The agent is trained using PPO in all experiments with the same hyperparameters\footnote{The original ICM uses A3C but we used PPO similar to~\cite{burda2018large}.}. We perform three independent runs of each algorithm without any tuning of random seeds, and plot the mean and standard deviation across the three runs (see details in Appendix~\ref{app_details}).

\vspace{-2mm}
\subsection{Varying Degree of Reward Sparsity}
\label{sec: varying_sparsity}
\vspace{-2mm}

To study in what scenarios grounded language understanding can help exploration, we test our approach in two tasks with drastically different reward sparsity.

\textbf{Dense reward setting.} \quad In this setting, the agent needs to complete an object alignment goal where the spatial relationship between two objects in the environment is specified, for example, \textit{"There is a green sphere; are there any rubber cyan balls in front of it?"} (Figure \ref{fig:clevr_env} (a-c)). Goal descriptions take the form of questions which can be evaluated on the state to assess if the goal has been met successfully. The agent receives a reward of $+1$ if it manipulates the objects to achieve the desired spatial arrangement. When the environment is reset before every episode, it is ensured that the goal state is not satisfied initially.

\textbf{Sparse reward setting.} \quad In the \textbf{object ordering} task (Figure \ref{fig:clevr_env} (d)), the agent needs to order the objects by color in a single line, for example, \textit{“arrange the objects so that their
colors range from blue to green in the horizontal direction, and keep the objects close vertically"}. The ordering of colors we specify is: \textit{cyan, purple, green, blue, red} from left to right. The agent is given a $+10$ reward if it is able to successfully order the objects in this arrangement, and $0$ otherwise. The rationale behind opting for a $+10$ reward instead of $+1$ is to compensate for the extreme reward sparsity which led to the agent not making any significant progress.

The results for the two settings are shown in Figure \ref{fig:sparsity_plots}. We observe in the dense reward setting, PPO with no exploration bonus outperforms all curiosity-driven methods, which highlights that curiosity does not provide a significant advantage when the reward is dense. In the sparse reward task, we find that while all existing baseline methods struggle to make meaningful progress, \textsc{AnE}\ significantly outperforms the baselines in this setting using a single question ($n = 1$) at each step. This confirms our hypothesis -- an intrinsic reward that leverages grounded language understanding is better at exploring the environment. The exploration results in a wider coverage of relevant states and helps the agent learn to solve the task more efficiently
compared to existing novelty-based exploration methods.
In addition, we study the impact of scaling to multiple questions in both dense and sparse reward environments in Appendix \ref{app_multiple_ques}, and the performance of different approaches in the absence of any extrinsic reward in Appendix \ref{app_intrinsic_only}.

\begin{figure}[tbp]
\begin{minipage}{.49\textwidth}
\centering
\vspace{-2mm}
\includegraphics[width=\linewidth]{images/regular_setting_1.png}
(a) Dense reward setting
\end{minipage}%
\hspace{.02\textwidth}
\begin{minipage}{.49\textwidth}
\centering
\vspace{-2mm}
\includegraphics[width=\linewidth]{images/sparse_setting_1.png}
(b) Sparse reward setting
\end{minipage}%
\caption{\textsc{AnE}\ significantly outperforms the baselines (PPO, ICM and RND) in the sparse reward setting which demonstrates the effectiveness of an intrinsic reward based on grounded question answering.\vspace{-6mm}}
\label{fig:sparsity_plots}
\end{figure}

\vspace{-2mm}
\subsection{Varying complexity of questions}
\label{sec: varying_complexity}
\vspace{-2mm}

To better understand which questions are most useful for the task, we test the performance of \textsc{AnE}\ using three types of questions querying varying complexity of spatial relationships between objects in the environment - \textbf{one}, \textbf{two} and \textbf{three} ``hop'' questions:

\vspace{-1mm}
\textbf{One-hop}: \textit{``There is a red metallic sphere; are there any green matte balls left of it?''}

\vspace{-1mm}
\textbf{Two-hop}: \textit{``Are there any purple rubber balls that are on the left side of the red sphere that is behind the blue matte ball?''}

\vspace{-1mm}
\textbf{Three-hop}: \textit{``There is a green rubber ball behind the red metallic sphere; are there any blue balls in front of the purple matte sphere?''}

\begin{figure}[!ht]
\begin{minipage}{.49\textwidth}
\centering
\vspace{-2mm}
\includegraphics[width=\linewidth]{images/regular_setting_hops_1.png}
(a) Dense reward setting
\end{minipage}%
\hspace{.02\textwidth}
\begin{minipage}{.49\textwidth}
\centering
\vspace{-2mm}
\includegraphics[width=\linewidth]{images/sparse_setting_hops_1.png}
(b) Sparse reward setting
\end{minipage}%
\caption{Comparing the performance of \textsc{AnE}\ for questions of varying complexity. \vspace{-4mm}}
\label{fig:complexity_plots}
\end{figure}

We observe in Figure \ref{fig:complexity_plots} how the performance of the agent varies with increasing complexity of questions (in terms of a greater number of pair-wise relationships between objects). It is interesting to note that the relationship between language and agent performance is not the same across different task settings. The extrinsic reward increases in the dense reward setting as we move from one-hop to two-hop questions in the environment and then decreases as we progress to three-hop questions. While in the sparse task, the success rate is highest using one-hop questions and decreases as we increase the number of object relationships, although all improve over the baselines. Therefore, even simple probes of spatial relationships are sufficient as a curiosity signal.

\vspace{-3mm}
\section{Conclusion}
\vspace{-3mm}

In this paper, we proposed a novel form of curiosity by encouraging the agent to ask questions about the environment and be curious when the answers to their questions change. We show that this formulation of intrinsic reward probes targeted knowledge about the physical properties of the objects as well as their spatial relationships with other objects, achieving significantly better performance than existing curiosity methods on highly sparse reward tasks.

{\small


\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}