
\documentclass[finalversion]{FPSAC2020}
\articlenumber{79}
\bibliography{fpsac}



\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage[all]{xy}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}[section]
\newtheorem{prop}[thm]{\protect\propositionname}
\newtheorem{conjecture}[thm]{\protect\conjecturename}
\newtheorem{cor}[thm]{\protect\corollaryname}

\theoremstyle{definition}
\newtheorem{defn}[thm]{\protect\definitionname}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
%\usepackage{cmap}
\usepackage{fontenc}
\usepackage[leftcaption]{sidecap}

\sidecaptionvpos{figure}{c}


\usepackage{footmisc}

%\newcommand{\FigBesBeg}[1][1.0]{%
% \let\MyFigure\figure
% \let\MyEndfigure\endfigure
% \renewenvironment{figure}[1]{\begin{SCfigure}[#1]##1}{\end{SCfigure}}}

%\newcommand{\FigBesEnd}{%
% \let\figure\MyFigure
% \let\endfigure\MyEndfigure}

\makeatother

\providecommand{\conjecturename}{Conjecture}
\providecommand{\corollaryname}{Corollary}
\providecommand{\definitionname}{Definition}
\providecommand{\propositionname}{Proposition}
\providecommand{\theoremname}{Theorem}


%% define your title in the usual way
\title{Word Measures on Symmetric Groups}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Liam Hanany\thanks{\href{mailto:liamhanany@mail.tau.ac.il}{liamhanany@mail.tau.ac.il}. Supported by Israel Science Foundation (ISF) via grant 1071/16}\addressmark{0} \and Doron Puder\thanks{\href{mailto:doronpuder@gmail.com}{doronpuder@gmail.com}. Supported by Israel Science Foundation (ISF) via grant 1071/16}\addressmark{0}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{0}School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Fix a word $w$ in a free group $F_r$ on $r$ generators. A $w$-random
permutation in the symmetric group $S_n$ is obtained by sampling $r$ independent uniformly
random permutations $\sigma_1,\ldots,\sigma_r\in S_n$ and evaluating
$w\left(\sigma_1,\ldots,\sigma_r\right)$. In (Puder 2014, Puder--Parzanchevski 2015)
it was shown that the average number of fixed points in a $w$-random
permutation is $1+\theta\left(n^{1-\pi\left(w\right)}\right)$, where
$\pi\left(w\right)$ is the smallest rank of a subgroup $H\le F_r$
containing $w$ as a non-primitive element. We show that $\pi\left(w\right)$ plays a role in estimates
of other natural families of characters. In particular, we show that
for all $s\ge2$, the average number of $s$-cycles is $\frac{1}{s}+O\left(n^{-\pi\left(w\right)}\right)$.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{symmetric groups, free groups, random permutations}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\bibliography{sample}
%\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\global\long\def\F{\mathbb{\mathbb{\mathbf{F}}}}%
 
\global\long\def\rk{\mathbb{\mathrm{rank}}}%
 
\global\long\def\crit{\mathbb{\mathrm{Crit}}}%
 
\global\long\def\Hom{\mathrm{Hom}}%
 
\global\long\def\defi{\stackrel{\mathrm{def}}{=}}%
 
\global\long\def\ks{k_{1},\ldots,k_{\ell}}%
 
\global\long\def\tr{{\cal T}r }%
 
\global\long\def\id{\mathrm{id}}%
 
\global\long\def\Aut{\mathrm{Aut}}%
 
\global\long\def\wl{w_{1},\ldots,w_{\ell}}%
 
\global\long\def\alg{\le_{\mathrm{alg}}}%
 
\global\long\def\ff{\stackrel{*}{\le}}%

\global\long\def\pmulti{\pi_{1}^{\mathrm{multi}}}%
 
\global\long\def\mocc{{\cal MOCC}}%
 
\global\long\def\mcg{{\cal M}\mathrm{u}{\cal C}{\cal G}}%
 
\global\long\def\decomp{{\cal D}\mathrm{ecomp}}%
 
\global\long\def\algdecomp{{\cal A}\mathrm{lg}{\cal D}\mathrm{ecomp}}%


\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Let $\F_{r}$ denote the free group on $r$ generators. A word $w\in\F_{r}$
induces a mapping on any finite group, $w:G^{r}\to G$, by substituting
the letters of $w$ with elements of $G$. This map defines a distribution
on the group $G$: the push forward of the uniform distribution on
$G^{r}$. Equivalently, this distribution is the normalized number
of times each element in $G$ is obtained by a substitution in $w$.
We call this distribution the $w$-measure on $G$. For example, if
$w=xyxy^{-2}$, a $w$-random element in $G$ is $ghgh^{-2}$ where
$g,h$ are independent, uniformly random elements of $G$. In this
paper, we restrict our attention to word measures on the symmetric
groups $S_{n}$. 

More concretely, we study these measures using non-abelian Fourier
theory: given a character\footnote{A character $\chi$ of the group $G$ is given by $\mathrm{tr}\circ\rho$,
where $\rho\colon G\to\mathrm{GL}_{d}\left(\mathbb{C}\right)$ is
some homomorphism.} $\chi$ of $G$, we compute $\mathbb{E}_{w}\left[\chi\right]$, the
average value of this character under the $w$-measure on $G$. Word
measures are constant on conjugacy classes of $G$, i.e.~are class
functions on the group $G$, and every class function is a linear
combination of irreducible characters. Therefore, the expressions
$\mathbb{E}_{w}\left[\chi\right]$, running over all characters $\chi$,
uniquely determine the resulting word measure.

Our focus is on the following class functions of $S_{n}$. Given $\ks\in\mathbb{Z}_{\ge1}$,
denote 
\begin{equation}
\chi_{\ks}\left(\sigma\right)\defi\#\mathrm{fix}\left(\sigma^{k_{1}}\right)\cdot\ldots\cdot\#\mathrm{fix}\left(\sigma^{k_{\ell}}\right),\label{eq:chi k1 ... ks}
\end{equation}
where $\#\mathrm{fix}\left(\tau\right)$ is the number of fixed points
of the permutation $\tau$. When we write $\mathbb{E}_{w}\left[\chi_{\ks}\right]$
there is also a suppressed parameter $n$. In fact, $\mathbb{E}_{w}\left[\chi_{\ks}\right]$
is a map $\mathbb{N}\to\mathbb{Q}$, where $n$ is mapped to the average
value of this character under the $w$-measure on $S_{n}$.

For every word $w\in\F_{r}$ and $\ks\in\mathbb{Z}_{\ge1}$, the expectation
$\mathbb{E}_{w}\left[\chi_{\ks}\right]$ is a rational function of
$n$, for large enough $n$: this is essentially a result of Nica
\cite{nica1994number}, and see also Section 4 and especially Remark
31 in \cite{Linial2010}. For example, $\mathbb{E}_{xyx^{-1}y^{-1}}\left[\chi_{1,2}\right]=3+\frac{4\left(n^{4}-9n^{3}+23n^{2}-13n-1\right)}{n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-5\right)}$
for all $n\ge6$. In particular, for large enough $n$, $\mathbb{E}_{w}\left[\chi_{\ks}\right]$
can be written as a Laurent series in $n$. Our main goal in this
paper is to estimate the leading terms of this Laurent series expansion.
The special case of $\chi_{1}=\#\mathrm{fix}(\sigma)$, the average
number of fixed points, was studied in \cite{Puder2014,PP15}. These
papers show a connection between $\mathbb{E}_{w}\left[\chi_{1}\right]$
and invariants of $w$ as an element of the free group.

In order to explain these invariants, we need a few notions from combinatorial
group theory and the study of free groups. A generating set of minimal
size of a finitely generated free group is called a \emph{basis}.
An element $w\in\F$ is called \emph{primitive} if it belongs to a
basis of $\F$. The rank of the free group $\F$, denoted $\mathrm{rk}\F,$
is the size of a basis of $\F$. The classical Nielsen-Schreier theorem
states that subgroups of free groups are free. The primitivity rank
of a word, which plays an important role in this paper, was first
introduced in \cite{Puder2014}:
\begin{defn}
The primitivity rank $\pi(w)$ of a word $w\in\F_{r}$ is the minimal
rank of a subgroup $H\leq\F_{r}$ containing $w$ as a non-primitive
element. If there are no such subgroups, set $\pi\left(w\right)=\infty$.
We also consider the set of critical subgroups of $w$ defined as
\[
\crit\left(w\right)=\left\{ H\le\F\,\middle|\,\mathrm{rk}H=\pi\left(w\right),H\ni w~\mathrm{and}~w~\mathrm{non-primitive~in}~H\right\} .
\]
\end{defn}

For example, $\pi\left(w\right)=0\iff w=1$ as the trivial word is
contained in the trivial subgroup but not as a primitive element.
Words with $\pi\left(w\right)=1$ are precisely proper powers and
if $u\in\F_{r}$ is not a proper power and $m\ge2$, then $\crit\left(u^{m}\right)=\left\{ \left\langle u^{d}\right\rangle \,\middle|\,d\mid m,~d<m\right\} $.
Finally, $\pi\left(w\right)=\infty$ if and only if $w$ is primitive
in $\F_{r}$, and in any other case $\pi\left(w\right)\le r$ \cite[Lemma 4.1]{Puder2014}.
The set $\crit\left(w\right)$ is always finite \cite[Section 4]{PP15}.
We can now state the aforementioned result from \cite{PP15}.
\begin{thm}[{\cite[Theorem 1.8]{PP15}}] \label{thm:pp15}For every $w\in\F_{r}$

\[
\mathbb{E}_{w}\left[\#\mathrm{fix}(\sigma)\right]=1+\frac{\left|\crit(w)\right|}{n^{\pi(w)-1}}+O\left(\frac{1}{n^{\pi(w)}}\right).
\]
\end{thm}

Since the expected number of fixed points in a uniformly random permutation
is $1$, the theorem can be restated as

\[
\mathbb{E}_{w}\left[\chi_{1}\right]=\mathbb{E}_{\mathrm{unif}}\left[\chi_{1}\right]+\frac{\left|\crit\left(w\right)\right|}{n^{\pi(w)-1}}+O\left(\frac{1}{n^{\pi(w)}}\right),
\]
where $\mathbb{E}_{\mathrm{unif}}\left[f\right]$ is the expectation
of a function $f\colon S_{n}\to\mathbb{R}$ with respect to the uniform
distribution on $S_{n}$. In this paper we prove the following generalization
of \cref{thm:pp15}:
\begin{thm}
\label{thm:Word-Measure-Character-Bound}For every non-power $w\in\F_{r}$
and every $\ks\in\mathbb{Z}_{\ge1}$, there exists a positive integer
$C_{\ks}\in\mathbb{N}$ such that
\[
\mathbb{E}_{w}\left[\chi_{\ks}\right]=\mathbb{E}_{\mathrm{unif}}\left[\chi_{\ks}\right]+\frac{C_{\ks}\cdot\left|\crit\left(w\right)\right|}{n^{\pi(w)-1}}+O\left(\frac{1}{n^{\pi(w)}}\right).
\]
Moreover, the constant $C_{\ks}$ is equal to the scalar product 
\[
\left\langle \chi_{\ks},\chi_{1}-1\right\rangle =\frac{1}{n!}\sum_{\sigma\in S_{n}}\chi_{\ks}\left(\sigma\right)\cdot\left(\chi_{1}\left(\sigma\right)-1\right),
\]
which is independent of $n$ for all large enough $n$.
\end{thm}

Note that the exclusion of powers in the statement of the theorem
is necessary, but these expected values can still be understood. Indeed,
$\chi_{\ks}\left(\sigma^{t}\right)=\chi_{tk_{1},\ldots,tk_{\ell}}\left(\sigma\right)$.
Hence, we can still obtain an approximation for the expected value
of a power using the theorem.

An interesting corollary of \cref{thm:Word-Measure-Character-Bound}
deals with the expected number of cycles of a given size. Fix $s\in\mathbb{N}$.
Let $\mathrm{Cyc}_{s}(\sigma)$ denote the number of cycles of
length $s$ in the permutation $\sigma$. The expected number of
such cycles in a uniformly random permutation is $\frac{1}{s}$.
For every large enough $n$, $\mathrm{Cyc}_{s}$ is a fixed linear
combination of the characters from \eqref{eq:chi k1 ... ks}. For
example, $\mathrm{Cyc}_{2}=\frac{\chi_{2}-\chi_{1}}{2}$. If $s\ge2$,
then for every large enough $n$, $\left\langle \mathrm{Cyc}_{s},\chi_{1}-1\right\rangle =0$.
Therefore, \cref{thm:Word-Measure-Character-Bound} yields,
\begin{cor}
Let $s\ge2$. For every non-power $w\in\F_{r}$,

\[
\mathbb{E}_{w}\left[\mathrm{Cyc}_{s}\right]=\frac{1}{s}+O\left(\frac{1}{n^{\pi(w)}}\right).
\]
\end{cor}

It is a well-known fact, c.f.~\cite{macdonald1998symmetric}, that
there are families of irreducible characters $\xi=\left\{ \xi_{n}\right\} _{n\ge n_{0}}$
($\xi_{n}$ being an irreducible character of $S_{n}$), with dimension
polynomial in $n$ and which are finite linear combinations of the
functions $\chi_{\ks}$. Such a family of irreducible
characters corresponds to a family of Young diagrams, given by a Young
diagram $\mathcal{D}$ of size $n_{0}$, so that $\xi_{n}$ corresponds
to the Young diagram obtained from ${\cal D}$ by adding $n-n_{0}$
boxes to the first row. The first few examples of such characters
are $1,\chi_{1}-1,\frac{\chi_{2}+\chi_{1,1}}{2}-2\chi_{1},\frac{\chi_{1,1}-\chi_{2}}{2}-\chi_{1}+1$,
corresponding to the young diagrams $\left(n\right),\left(n-1,1\right),\left(n-2,2\right)$
and $\left(n-2,1,1\right)$, respectively.

In fact, by orthogonality of irreducible characters, \cref{thm:Word-Measure-Character-Bound}
is equivalent to that for such a family of irreducible characters $\xi$,
if $\xi\ne1,\chi_{1}-1$ then\vspace{-10bp}

\begin{equation}
\mathbb{E}_{w}\left[\xi\right]=O\left(\frac{1}{n^{\pi(w)}}\right).\label{eq:bound for irreps}
\end{equation}
We conjecture the following much stronger bound:
\begin{conjecture}
Let $\xi$ be a family of irreducible characters of $S_{n}$ as above.
Then, 
\begin{equation}
\mathbb{\mathbb{E}}_{w}\left[\xi\right]=O\left(\frac{1}{\left(\dim\xi\right)^{\pi(w)-1}}\right).\label{eq:conj-bound}
\end{equation}
\end{conjecture}

Whenever $\xi\neq1,\chi_{1}-1$, the dimension $\dim\xi$ is a polynomial
function of $n$, of degree greater than $1$. Thus, the conjectural
bound \eqref{eq:conj-bound} is stronger (for non-powers) than \eqref{eq:bound for irreps}.
The conjecture holds for words of primitivity rank $1$, namely, for
proper powers (this follows from \cite{nica1994number} and from \cite[Section 4]{Linial2010}).
Another known special case of this conjecture is the commutator $\left[x,y\right]=xyx^{-1}y^{-1}$:
indeed, $\pi\left(\left[x,y]\right]\right)=2$ and already in 1896
Frobenius \cite{frobenius1896gruppencharaktere} showed that $\mathbb{E}_{\left[x,y\right]}\left[\chi\right]=\frac{1}{\dim\chi}$
for every finite group $G$ and every irreducible character $\chi$
of $G$. Moreover, given two class functions $f_{1},f_{2}\colon G\to\mathbb{R}$
and an irreducible character $\chi$ of $G$, a simple application
of Schur's Lemma gives $\left\langle f_{1}\ast f_{2},\chi\right\rangle =\frac{\langle f_{1},\chi\rangle\langle f_{2},\chi\rangle}{\dim\chi}$.
If $w_{1}\in\F(x_{1},\ldots,x_{k}),w_{2}\in\F(x_{k+1},\ldots,x_{r})$
are two words generated by disjoint sets of letters, then the $w_{1}w_{2}$-measure
on $G$ is the convolution of the $w_{1}$- and the $w_{2}$-measures,
and by the corollary of Schur's Lemma, $\mathbb{E}_{w_{1}w_{2}}\left[\chi\right]=\frac{\mathbb{E}_{w_{1}}\left[\chi\right]\cdot\mathbb{E}_{w_{2}}\left[\chi\right]}{\dim\chi}$.
On the other hand, $\pi(w_{1}w_{2})=\pi(w_{1})+\pi(w_{2})$ \cite[Lemma 6.8]{Puder2014}.
Hence, knowing the conjecture for two such words implies the claim
for their product. In particular, this implies the conjecture for
every product of disjoint commutators and powers, that is, for every
word of the form 
\[
w=[x_{1},y_{1}]\cdot[x_{2},y_{2}]\cdot\ldots\cdot[x_{r},y_{r}]\cdot z_{1}^{k_{1}}\cdot\ldots\cdot z_{m}^{k_{m}}\in\F\left(x_{1},\ldots,x_{r},y_{1},\ldots,y_{r},z_{1},\ldots,z_{m}\right),
\]
with $r,m\in\mathbb{N}_{\ge0}$ and $k_{1},\ldots,k_{m}\in\mathbb{Z}$.

\section{The main ideas in the proofs\label{sec:Outline-of-the-proofs}}

In this section we give an overview of the main ideas of our work,
which together lead to our main result: \cref{thm:Word-Measure-Character-Bound}.
Full proofs and further details are given in the full version of this
paper.

\subsection{Generalizations of the object of study\label{subsec:generalizations}}

The quantities we wish to study are of the form 
\[
\mathbb{E}_{w}\left[\chi_{\ks}\right]=\mathbb{E}_{\sigma_{1},\ldots,\sigma_{r}\in S_{n}}\left[\#\mathrm{fix}\left(w^{k_{1}}\left(\sigma_{1},\ldots,\sigma_{r}\right)\right)\cdot\ldots\cdot\#\mathrm{fix}\left(w^{k_{\ell}}\left(\sigma_{1},\ldots,\sigma_{r}\right)\right)\right].
\]
Assume that $w$ is written in the ordered basis $B=\left\{ b_{1},\ldots,b_{r}\right\} $
of $\F_{r}$. Choosing a uniformly random $r$-tuple of permutations
from $S_{n}$ is the same as choosing at random an homomorphism $\varphi\colon\F_{r}\to S_{n}$,
as $\varphi\left(b_{1}\right),\ldots,\varphi\left(b_{r}\right)$ is
a uniformly random $r$-tuple of permutations. Replacing the letters
of $w$ by the permutations $\varphi\left(b_{1}\right),\ldots,\varphi\left(b_{r}\right)$,
we obtain the permutation $\varphi\left(w\right)$. Hence,
\begin{equation}
\mathbb{E}_{w}\left[\chi_{\ks}\right]=\mathbb{E}_{\varphi\in\mathrm{Hom}\left(\F_{r},S_{n}\right)}\left[\#\mathrm{fix}\left(\varphi\left(w^{k_{1}}\right)\right)\cdot\ldots\cdot\#\mathrm{fix}\left(\varphi\left(w^{k_{\ell}}\right)\right)\right].\label{eq:original object}
\end{equation}
Following \cite{PP15}, the first step in our analysis is to generalize
the function we study. This generalization is crucial for the next
steps. The most straightforward generalization is to consider quantities
of the form

\begin{equation}
\mathbb{E}_{\varphi\in\mathrm{Hom}\left(\F_{r},S_{n}\right)}\left[\#\mathrm{fix}\left(\varphi\left(w_{1}\right)\right)\cdot\ldots\cdot\#\mathrm{fix}\left(\varphi\left(w_{\ell}\right)\right)\right],\label{eq:arbitrary words}
\end{equation}
for arbitrary words $w_{1},\ldots,w_{\ell}\in\F_{r}$. Next, we generalize
from fixed points of a word to \emph{common }fixed points of several
words, or, equivalently, to common fixed points of subgroups: note
that given a finite set of words $w_{1},\ldots,w_{t}\in\F_{r}$, an
element $i\in[n]$ is a \emph{common} fixed point of all the permutations
$\varphi\left(w_{1}\right),\ldots,\varphi\left(w_{t}\right)$ if and
only if it is a common fixed point of all the permutations in the
subgroup $\varphi\left(H\right)\le S_{n}$ where $H=\langle w_{1},\ldots,w_{t}\rangle\leq\F_{r}$.
For (a finitely generated) $H\le\F_{r}$ we denote by $\#\mathrm{fix}\left(\varphi\left(H\right)\right)$
the number of common fixed points of $\varphi\left(H\right)$. We
extend the function we wish to study to quantities of the form

\begin{equation}
\mathbb{E}_{\varphi\in\mathrm{Hom}\left(\F_{r},S_{n}\right)}\left[\#\mathrm{fix}\left(\varphi\left(H_{1}\right)\right)\cdot\ldots\cdot\#\mathrm{fix}\left(\varphi\left(H_{\ell}\right)\right)\right],\label{eq:studying common fixed points of subgroups}
\end{equation}
where $H_{1},\ldots,H_{\ell}\leq\F_{r}$ are f.g.~(finitely generated)
subgroups of $\F_{r}$.

If $H,H'\le\F_{r}$ are conjugate subgroups then $\#\mathrm{fix}\left(\varphi\left(H\right)\right)=\#\mathrm{fix}\left(\varphi\left(H'\right)\right)$.
Therefore, \eqref{eq:studying common fixed points of subgroups} depends,
in fact, on a \emph{multiset of conjugacy classes of f.g.~subgroups}
of $\F_{r}$. We shall work in the category of these objects, which
we denote $\mocc\left(\F_{r}\right)$.

Finally, assume that there are two multisets of f.g.~subgroups $H_{1},\ldots,H_{\ell}\le\F_{r}$
and $J_{1},\ldots,J_{m}\le\F_{r}$, and that there is a map $f\colon\left[\ell\right]\to\left[m\right]$,
such that $H_{i}\le J_{f\left(i\right)}$ for all $1\le i\le\ell$.
Let $\left\{ \varphi_{j}\colon J_{j}\to S_{n}\right\} _{j=1}^{m}$
be independent, uniformly random homomorphisms. Our final generalization
of the object of study is to
\begin{equation}
\mathbb{E}_{\left\{ \varphi_{j}\in\Hom\left(J_{j},S_{n}\right)\right\} _{j=1}^{m}}\left[\#\mathrm{fix}\left(\varphi_{f\left(1\right)}\left(H_{1}\right)\right)\cdot\ldots\cdot\#\mathrm{fix}\left(\varphi_{f\left(\ell\right)}\left(H_{\ell}\right)\right)\right].\label{eq:final generalization of object of study}
\end{equation}
As described in the sequel, much of the technique in our proofs relies
on this generalization of \eqref{eq:original object} to \eqref{eq:arbitrary words},
\eqref{eq:studying common fixed points of subgroups} and \eqref{eq:final generalization of object of study}.
Next, we give a geometric description of the category of $\mocc\left(\F_{r}\right)$
which makes many of our definitions more straightforward and many
of our lemmas more intuitive.

\subsection{Multi core graphs}

Let $B=\left\{ b_{1},\ldots,b_{r}\right\} $ be a basis of $\F_{r}$,
and consider the bouquet $X_{B}$ of $r$ circles with distinct labels
from $B$ and arbitrary orientations and with wedge point $o$. Then
$\pi_{1}\left(X_{B},o\right)$ is naturally identified with $\F_{r}$.
The notion of ($B$-labeled) core graphs, introduced in \cite{stallings1983topology},
refers to (usually) finite, connected graphs with no leaves, that
come with a graph morphism to $X_{B}$ which is an \emph{immersion},
namely, locally injective. In other words, this is a finite connected
graph with no leaves, with edges that are directed and labeled by
the elements of $B$, such that for every vertex $v$ and every $b\in B$,
there is at most one incoming $b$-edge and at most one outgoing $b$-edge
at $v$. We stress that multiple edges between two vertices and loops
at vertices are allowed.

There is a natural one-to-one correspondence between finite $B$-labeled
core graphs and conjugacy classes of f.g.~subgroups of $\F_{r}$
-- see \cite{stallings1983topology,kapovich2002stallings,Puder2014,PP15}
for more details. Here, we consider core graphs which are not necessarily
connected:
\begin{defn}
\label{def:not-necessarily-connected-core-graphs}Let $B$ be a basis
of $\F_{r}$. A $B$-labeled \emph{multi core graph }is a disjoint
union of finitely many finite core graphs. In other words, this is
a finite graph, not necessarily connected, with no leaves, and which
comes with an immersion to $X_{B}$. We denote the set of $B$-labeled
multi core graphs by $\mcg_{B}\left(\F_{r}\right)$.
\end{defn}

Because a connected core graph corresponds to a conjugacy class of
f.g.~subgroups of $\F_{r}$, a multi core graph corresponds to a
multiset of such objects. Therefore, every basis $B$ of $\F_{r}$
gives a one-to-one correspondence
\begin{equation}
\begin{gathered}\mcg_{B}\left(\F_{r}\right)=\\
\left\{ \begin{gathered}B\mathrm{-labeled~}\\
\mathrm{multi~core~graphs}
\end{gathered}
\right\} 
\end{gathered}
~~~\longleftrightarrow~~~\begin{gathered}\mocc\left(\F_{r}\right)=\\
\left\{ \begin{gathered}\mathrm{finite~multisets~of~conjugacy~classes}\\
\mathrm{of~f.g.~subgroups~of}~\F_{r}
\end{gathered}
\right\} 
\end{gathered}
.\label{eq:1-to-1 correspondence of categories}
\end{equation}

\begin{defn}
A morphism $\eta\colon\Gamma\to\Delta$ between $B$-labeled multi
core graphs is a graph-morphism which  commutes with the immersions
$p,q$ to $X_{B}$.
\[
\xymatrix{\Gamma\ar[rd]^{p}\ar[rr]^{\eta} &  & \Delta\ar[ld]_{q}\\
 & X_{B}
}
\]
\end{defn}

In particular, the morphism $\eta$ is itself an immersion, and it
preserves the orientations and labels of the edges. To get a description
of $\eta$ in terms of subgroups, assume that $\Gamma$ consists of
$\ell$ components $\Gamma_{1},\ldots,\Gamma_{\ell}$   and that
$\Delta$ consists of $m$ components $\Delta_{1},\ldots,\Delta_{m}$.
Let $f\colon\left[\ell\right]\to\left[m\right]$ be the induced map
on connected components, so $\eta\left(\Gamma_{i}\right)\subseteq\Delta_{f\left(i\right)}$.
For every $i\in\left[\ell\right]$, pick an arbitrary vertex $v_{i}\in\Gamma_{i}$
and let $H_{i}=\pi_{1}\left(\Gamma_{i},v_{i}\right)$. As $\eta$
is an immersion, it induces \emph{injective} maps in the level of
the fundamental groups: indeed, any non-backtracking cycle in $\Gamma$
is mapped to a non-backtracking cycle in $\Delta$. Therefore, $\eta$
can be thought of as the injection, for all $i\in\left[\ell\right]$
\begin{equation}
H_{i}\hookrightarrow\pi_{1}\left(\Delta_{f\left(i\right)},\eta\left(v_{i}\right)\right).\label{eq:injection of pi1}
\end{equation}

Now we are very close to the situation that led to \eqref{eq:final generalization of object of study},
but in order to define a \eqref{eq:final generalization of object of study}-like
quantity that depends on $\eta$, we still need to conjugate the images
in \eqref{eq:injection of pi1} so that they all sit in the same subgroups
in the conjugacy class of subgroups of $\Delta_{j}$. Formally, pick
an arbitrary vertex $v_{j}\in\Delta_{j}$ for all $j\in\left[m\right]$
and let $J_{j}=\pi_{1}\left(\Delta_{j},v_{j}\right)$. For every $i\in\left[\ell\right]$,
let $x_{i}\in\F_{r}$ satisfy $x_{i}\left[\pi_{1}\left(\Delta_{f\left(i\right)},\eta\left(v_{i}\right)\right)\right]x_{i}^{-1}=J_{f\left(i\right)}$.
So now $x_{i}H_{i}x_{i}^{-1}\le J_{f\left(i\right)}$, and we are
now able to define another form of \eqref{eq:final generalization of object of study}
which comes from the morphism $\eta$:
\begin{defn}
\label{def:Phi}In the above notation, let $\left\{ \varphi_{j}\colon J_{j}\to S_{n}\right\} _{j=1}^{m}$
be independent, uniformly random homomorphisms. Define\vspace{-20bp}
\end{defn}

\[
\Phi_{\eta}\left(n\right)\defi\mathbb{E}_{\left\{ \varphi_{j}\in\Hom\left(J_{j},S_{n}\right)\right\} _{j=1}^{m}}\left[\#\mathrm{fix}\left(\varphi_{f\left(1\right)}\left(x_{1}H_{1}x_{1}^{-1}\right)\right)\cdot\ldots\cdot\#\mathrm{fix}\left(\varphi_{f\left(\ell\right)}\left(x_{\ell}H_{\ell}x_{\ell}^{-1}\right)\right)\right].
\]

Note that the values of $\Phi_{\eta}$ do not depend on our choice
of basepoints in the components of $\Gamma$ and $\Delta$. As explained
in \cite[Section 6]{PP15} for the simpler case analyzed there, $\Phi_{\eta}\left(n\right)$
can also be given the following topological interpretation. Let $\widehat{\Delta_{n}}$
be a random $n$-sheeted covering space of $\Delta$. Then $\Phi_{\eta}\left(n\right)$
is equal to the average number of lifts of $\eta$ to $\widehat{\Delta_{n}}$.
\[
\xymatrix{ & \widehat{\Delta_{n}}\ar@{->>}[d]^{p}\\
\Gamma\ar[r]^{\eta}\ar@{-->}[ur] & \Delta
}
\]

We end this subsection with three important invariants of multi core
graphs.
\begin{defn}
Let $\Gamma\in\mcg_{B}\left(\F_{r}\right)$ be a multi core graph
and $\mathcal{H}=\left\{ H_{1}^{\F_{r}},\ldots,H_{\ell}^{\F_{r}}\right\} $
the corresponding multiset in $\mocc\left(\F_{r}\right)$. We denote
by $rk\mathcal{H}=\mathrm{rk}\Gamma$ the sum of ranks of $H_{1},\ldots,H_{\ell}$,
by $\chi\left(\Gamma\right)=\chi\left({\cal H}\right)$ the Euler
characteristic of $\Gamma$, and by $c\left(\Gamma\right)=c\left({\cal H}\right)$
the number of connected components of $\Gamma$ (which is $\ell$
in the current notation). These three quantities are related by $\mathrm{rk}\Gamma+\chi\left(\Gamma\right)=c\left(\Gamma\right)$.
\end{defn}


\subsection{Free and algebraic morphisms}

A subgroup $H$ of a free group $\F$ is called a \emph{free factor}
of $\F$, and $\F$ a \emph{free extension} of $H$, denoted $H\ff\F$,
if it is generated by some subset of a basis of $\F$. Equivalently,
this means that there is another subgroup $K\leq\F_{r}$, such that
$\F=H\ast K$. The useful notion of an algebraic extensions of free
groups is defined as follows (see \cite{miasnikov2007algebraic} for
a survey):
\begin{defn}
Let $H$ be a subgroup of the free group $\F$. Then $\F$ is an \emph{algebraic
extension }of $H$, denoted $H\alg\F$, if there is no intermediate
proper free factor of $\F$. Namely, if whenever $H\leq J\ff F$,
we have $J=\F$.
\end{defn}

Given a morphism of \emph{connected }core graphs, we may say it is
free (algebraic) if the induced map in the level of fundamental groups
gives a free (algebraic, respectively) extension of groups. A crucial
ingredient of our argument is to find the right generalizations of
these notions to morphisms of multi core graphs. We start with free
extensions.
\begin{defn}
\label{def:free extension of a multiset of subgroups}If $H_{1},\ldots,H_{\ell}$
are subgroups of the free group $J$, we say that $J$ is a \emph{free
extension} of the multiset $\left\{ H_{1},\ldots,H_{\ell}\right\} $,
denoted $\left\{ H_{1},\ldots,H_{\ell}\right\} \ff J$, if $J$ decomposes
as a free product 
\[
J=\left(\ast_{i=1}^{\ell}j_{i}H_{i}j_{i}^{-1}\right)*K
\]
for some conjugate subgroup $j_{i}H_{i}j_{i}^{-1}$ of $H_{i}$ (so
$j_{i}\in J$) and some subgroup $K\le J$.
\end{defn}

The definition of a free morphism $\eta:\Gamma\to\Delta$ of multi
core graphs is very similar, except that one needs first to choose
arbitrarily some subgroup from the conjugacy class of every component
of $\Delta$, and then find a suitable subgroup for every component
of $\Gamma$ mapping to it. This can be done similarly to the manner
by which we defined $\Phi_{\eta}$ in \cref{def:Phi}, and
we give the precise definition in the full version of the paper.
The following theorem states some properties of free morphisms.
\begin{prop}
\label{prop:properties of free morphisms}
\begin{enumerate}
\item \label{enu:Every-injective-morphism is free}Every \emph{injective}
morphism of multi core graphs is free. In particular, the identity
morphism if free.
\item \label{enu:free is transitive}The composition of two free morphisms
is free.
\item \label{enu:Phi can ignore free extensions} If $\xymatrix{\bullet\ar[r]_{\varphi}\ar@/^{0.5pc}/[rr]^{\eta} & \bullet\ar[r]_{\psi} & \bullet}
$ is a composition of morphisms with $\psi$ free, then $\Phi_{\varphi}=\Phi_{\eta}$.
\end{enumerate}
\end{prop}

We move to defining our generalization of the notion of algebraic
extensions.
\begin{defn}
Let $\eta\colon\Gamma\to\Delta$ be a morphism of multi core graphs
$\Gamma,\Delta\in\mcg_{B}\left(\F_{r}\right)$. We say that $\eta$
is \emph{algebraic} if whenever $\Gamma\stackrel{_{\eta_{1}}}{\longrightarrow}\Sigma\stackrel{_{\eta_{2}}}{\longrightarrow}\Delta$
is a decomposition of $\eta$ with $\eta_{2}$ free, we have that
$\eta_{2}$ is an isomorphism.
\end{defn}

This notion can also be described in algebraic terms, namely, when
a free group $\F$ is considered to be an algebraic extension of a
multiset of its subgroups $\left\{ H_{1},\ldots,H_{\ell}\right\} $
-- we elaborate in the full paper. The following theorem lists some
important properties of algebraic morphisms.
\begin{thm}
\label{thm:properties of algebraic morphisms}\ 

\begin{enumerate}
\item \label{enu:alg is surjective}Every algebraic morphism of multi core
graphs is surjective.
\item \label{enu:transitivity of algebraic morphisms}The composition of
two algebraic morphisms is algebraic.
\item The identity morphism is algebraic.
\item \label{enu:algebraic-free-decomposition}Let $\eta:\Gamma\to\Delta$
be a morphism of multi core graphs. Then there is a unique decomposition
\[
\xymatrix{\Gamma\ar[rr]_{\mathrm{algebraic}}^{\varphi}\ar@/^{2pc}/[rrrr]^{\eta} &  & \Sigma\ar[rr]_{\text{free}}^{\mathrm{\psi}} &  & \Delta}
\]
$\eta=\psi\circ\varphi$ such that $\varphi$ is algebraic and $\psi$
is a free\footnote{To be precise, this decomposition is unique up to an isomorphism of
the intermediate multi core graph which preserves the two decompositions.}. 
\end{enumerate}
\end{thm}


\subsection{The length of a morphism}

In view of \cref{prop:properties of free morphisms}, for
every morphism $\eta\colon\Gamma\to\Delta$ of multi core graphs,
if $\overline{\eta}$ marks the induced morphism from $\Gamma$ to
the image of $\eta$ in $\Delta$, then $\Phi_{\eta}\equiv\Phi_{\overline{\eta}}$.
Therefore, in order to analyze the values of the function $\Phi$,
it is enough to consider \emph{surjective} morphisms. 

Every surjective morphism $\eta\colon\Gamma\to\Delta$ can be thought
of as a partition of the vertices of $\Gamma$ given by the fibers
of $\eta$: the vertices of $\Delta$ correspond to the blocks of
this partition, and there is a $b$-edge from the block $V$ to the
block $U$ if and only if there a $b$-edge from some vertex $v\in V$
to some vertex $u\in U$. Note that not every partition of the vertices
of $\Gamma$ corresponds to a moprhism, as the resulting graph might
not be a core graph (and have, say, two distinct $b$-edges emanating
from the same vertex). However, every partition of the vertices of
$\Gamma$ can ``generate'' a legitimate morphism using ``Stallings
foldings'', as we now explain.

Given a $B$-labeled directed finite graph, which may not be a multi
core graph, we can ``fold'' it until it becomes a multi core graph.
Every folding step consists of identifying two edges $e_{1}$ and
$e_{2}$ with the same label, either emanating from the same vertex
or entering the same vertex, and then gluing them to a single edge
and identifying their other ends to a single vertex. We continue folding
until no such coincidences exist, in which case we have a multi core
graph\footnote{In some sources, the folding process also includes leaf-pruning. In
our situation we never introduce leaves in the process, so it does
not matter.}. The resulting multi core graph does not depend on the order of folding
steps (see \cite{stallings1983topology}).
\begin{defn}
\label{def:combinatorial distance}A merging-step of a multi core
graph is a gluing together of two vertices of this graph followed
by folding. Let $\eta\colon\Gamma\to\Delta$ be a surjective morphism
of $B$-labeled multi core graphs. The \emph{length of $\eta$}, denoted
$\rho_{B}\left(\eta\right)$, is the smallest number of merging-steps
which lead from $\Gamma$ to $\Delta$ to create $\eta$.
\end{defn}

There is also a natural ``algebraic'', basis-independent version
of a distance between multisets of conjugacy classes of subgroups.
This algebraic distance gives rise to an algebraic distance of morphisms of $\mcg_B(\F_r)$, denoted $\rho\left(\eta\right)$, we define in the full paper. The following theorem sums
up the main properties of these two distances.

\begin{thm}
\label{thm:alg distance  =00003D comb distance}Let $\eta\colon\Gamma\to\Delta$
be a morphism of multi core graphs. Let $\Sigma=\mathrm{Image}\left(\eta\right)$
denote the image of $\eta$ in $\Delta$, and let $\eta=\iota\circ\overline{\eta}$
be the decomposition of $\eta$ to a surjective and an injective morphisms
$\xymatrix{\Gamma\ar@{->>}[r]^{\overline{\eta}} & \Sigma\ar@{^{(}->}[r]^{\iota} & \Delta}
$. Then 
\[
\rho\left(\eta\right)=\rho_{B}\left(\overline{\eta}\right)+\left[\mathrm{rk}(\Delta)-\mathrm{rk}(\Sigma)\right].
\]
In particular, 
\[
\rho\left(\eta\right)=\mathrm{rk}(\Delta) - \mathrm{rk}(\Gamma)~\iff~\rho_{B}\left(\overline{\eta}\right)= \mathrm{rk}(\Sigma)-\mathrm{rk}(\Gamma)~\iff~\eta~\mathrm{is~free}~\iff~\overline{\eta}~\mathrm{is~free}.
\]
\end{thm}


\subsection{M\"{o}bius inversions of $\Phi$}

Recall that our goal is to estimate $\Phi_{\eta}\left(n\right)$ for
some morphism $\eta\colon\Gamma\to\Delta$ of multi core graphs, and
that we may assume that $\eta$ is surjective. The next component
is to analyze several M\"{o}bius inversions of this function inside
a finite poset which we now define.
\begin{defn}
\label{def:poset of decompositions}Let $\eta\colon\Gamma\twoheadrightarrow\Delta$
be a surjective morphism of multi core graphs. Let $\decomp\left(\eta\right)$
denote the poset of decompositions of $\eta$ into two surjective
morphisms $\xymatrix{\Gamma\ar@{->>}[r]^{\eta_{1}} & \Sigma\ar@{->>}[r]^{\eta_{2}} & \Delta}
$, where the latter decomposition is considered identical to the morphism $\xymatrix{\Gamma\ar@{->>}[r]^{\eta'_{1}} & \Sigma'\ar@{->>}[r]^{\eta'_{2}} & \Delta}
$ if there is an isomorphism $\Sigma\cong\Sigma'$ which commutes with
both decompositions. In the same notation, $\left(\eta_{1},\eta_{2}\right)\le\left(\eta'_{1},\eta'_{2}\right)$
whenever there is a morhism $\theta\colon\Sigma\to\Sigma'$ which
makes the following diagram commute. 
\[
\xymatrix{\Gamma\ar@{->>}[r]^{\eta{}_{1}}\ar@{->>}[rd]^{\eta'{}_{1}} & \Sigma\ar@{->>}[d]^{\theta}\ar@{->>}[rd]^{\eta_{2}}\\
 & \Sigma'\ar@{->>}[r]^{\eta'_{2}} & \Delta
}
\]
\end{defn}

Clearly, $\decomp\left(\eta\right)$ is a finite poset. In the same
spirit as in \cite{PP15}, we can now define three different M\"{o}bius
inversions of the function $\Phi$ which are defined on the elements
of the poset. First, there is a unique ``left inversion'' of $\Phi$,
denoted $L^{B}$, which can be defined by setting that for every surjective
morphism $\eta$,
\[
\Phi_{\eta}=\sum_{\left(\eta_{1},\eta_{2}\right)\in\decomp\left(\eta\right)}L_{\eta_{2}}^{B}.
\]
Note that this well defines a map $L_{\eta}^{B}\colon\mathbb{N}\to\mathbb{Q}$
for every surjective morphism $\eta$ by induction on the size of
$\decomp\left(\eta\right)$. Indeed, $L_{\eta}^{B}=\Phi_{\eta}-\sum_{\left(\eta_{1},\eta_{2}\right)\in\decomp\left(\eta\right)\setminus\left\{ \left(\mathrm{id},\eta\right)\right\} }L_{\eta_{2}}^{B}$,
and the summation on the right hand side is on morphisms with a smaller
poset of decompositions. (The base case is $L_{\mathrm{id}}^{B}=\Phi_{\mathrm{id}}$.)
Similarly, we define the right M\"{o}bius inversion $R^{B}$ and
the two-sided inversion $C^{B}$ by
\begin{equation}
\Phi_{\eta}=\sum_{\left(\eta_{1},\eta_{2}\right)\in\decomp\left(\eta\right)}R_{\eta_{1}}^{B}=\sum_{\left(\eta_{1},\eta_{2},\eta_{3}\right)}C_{\eta_{2}}^{B},\label{eq:def of R and C}
\end{equation}
where the rightmost summation is over decompositions $\eta=\eta_{3}\circ\eta_{2}\circ\eta_{1}$
defined up to an equivalence parallel to the one in \cref{def:poset of decompositions}.

It follows from \cref{thm:properties of algebraic morphisms}
that if $\eta$ is \emph{algebraic}, then we can obtain a subposet
of $\decomp\left(\eta\right)$ which consists only of decompositions
to \emph{algebraic }morphisms. We can then define in the same way
the M\"{o}bius inversions of $\Phi$ with respect to this subposet.
We denote these inversions by $L^{\mathrm{alg}},R^{\mathrm{alg}}$
and $\mathrm{C^{\mathrm{alg}}}$. We prove the following results:
\begin{thm}
\label{thm:C-upper-bound}If $\eta\colon\Gamma\to\Delta$ is a surjective
morphism, then 
\[
C_{\eta}^{B}(n)=O\left(n^{\chi\left(\Gamma\right)-\rho\left(\eta\right)}\right).
\]
Similarly, if $\eta\colon\Gamma\to\Delta$ is an algebraic morphism,
then
\[
C_{\eta}^{\mathrm{alg}}(n)=O\left(n^{\chi\left(\Gamma\right)-\rho\left(\eta\right)}\right).
\]
In particular, following \cref{thm:alg distance  =00003D comb distance},
if $\eta$ is algebraic but not the identity, then 
\[
C_{\eta}^{\mathrm{alg}}(n)=O\left(n^{\chi\left(\Delta\right)-1}\right).
\]
\end{thm}

\begin{defn}
Let $\eta\colon\Gamma\to\Delta$ be a surjective morphism. Denote
by $\chi_{\max}(\eta)$ the maximal Euler characteristic of a multi
core graph $\Sigma$ such that there is a decomposition $\xymatrix{\Gamma\ar@{->>}[r]^{\eta_{1}} & \Sigma\ar@{->>}[r]^{\eta_{2}} & \Delta}
$ of $\eta$ with $\eta_{1}$ \emph{non-identity algebraic. }Every
such decomposition of $\eta$ with $\eta_{1}$ \emph{non-identity}
algebraic and $\chi\left(\Sigma\right)=\chi_{\max}\left(\eta\right)$
is called \emph{critical} (for $\eta$). Let $Crit(\eta)$ denote
the subset of critical decompositions in $\decomp\left(\eta\right)$.
\end{defn}

In particular, if $\Gamma_{w}$ is the core graph corresponding to
$\left\langle w\right\rangle ^{\F_{r}}$, and the unique morphism
$\Gamma_{w}\to X_{B}$ is surjective, then $\chi_{\max}\left(\Gamma_{w}\to X_{B}\right)=1-\pi\left(w\right)$.
The following theorem is now a simple corollary of \cref{thm:C-upper-bound}
together with the connection between $C^{\mathrm{alg}}$ and $\Phi$
as described in \eqref{eq:def of R and C}, and the fact that for
identity morphisms $\mathrm{id}\colon\Gamma\to\Gamma$ we have $\Phi_{\mathrm{id}}=L_{\mathrm{id}}^{alg}=R_{\mathrm{id}}^{alg}=C_{\mathrm{id}}^{alg}=n^{\chi\left(\Gamma\right)}$.
\begin{thm}
\label{thm:Phi-approximation}Let $\eta\colon\Gamma\to\Delta$ be
a surjective morphism. Then

\[
\Phi_{\eta}(n)=n^{\chi\left(\Gamma\right)}+|Crit(\eta)|\cdot n^{\chi_{max}\left(\eta\right)}+O\left(n^{\chi_{\max}\left(\eta\right)-1}\right).
\]
\end{thm}


\subsection{Back to $\chi_{\protect\ks}$}

We now return to the initial quantity we aimed to study in \cref{thm:Word-Measure-Character-Bound}. For $w_{1},\ldots,w_{\ell}\in\F_{r}\setminus\left\{ 1\right\} $
denote by $\Gamma_{w_{1},\ldots,w_{\ell}}$ the multi core graph which
is a disjoint union of $\ell$ cycles, depicting the conjugacy classes
$\left\langle w_{1}\right\rangle ^{\F_{r}},\ldots,\left\langle w_{\ell}\right\rangle ^{\F_{r}}$.
Fix $\ks\in\mathbb{Z}_{\ge1}$ and a non-power $1\ne w\in\F_{r}$.
In the language of multi core graphs and their morphisms, $\mathbb{E}_{w}\left[\chi_{\ks}\right]$
is equal to $\Phi_{\eta}$, where $\eta$ is the sole core graph morphism
$\Gamma_{w^{k_{1}},\ldots,w^{k_{\ell}}}\to X_{B}$. There are many
decompositions $\xymatrix{\Gamma_{w^{k_{1}},\ldots,w^{k_{\ell}}}\ar@{->>}[r]^{~~~~\eta_{1}} & \Sigma\ar@{->>}[r]^{\eta_{2}} & X_{B}}
$ of $\eta$ with $\chi\left(\Sigma\right)=0$ and $\eta_{1}$ algebraic
which are, in a sense, independent of $w$, and their number independent
of $w$. We carefully analyze the \emph{next} layer of decompositions
with $\eta_{1}$ algebraic, show that they are all of Euler characteristic
$1-\pi\left(w\right)$, and that their number is exactly $C_{\ks}\cdot\left|\crit\left(w\right)\right|$,
for an absolute constant $C_{\ks}$ independent of $w$. (In this
proof we rely on algebraic results of Baumslag and Steinberg \cite[Theorem 1]{baumslag1964residual}
and of Louder \cite[Theorem 1.5]{louder2013scott}.) This then leads
to the statement of \cref{thm:Word-Measure-Character-Bound}.

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}

