# On the average number of cycles in conjugacy class products

Jesse Campion Loth  Simon Fraser University, Burnaby, Canada
<EMAIL_ADDRESS>and  Amarpreet Rattan  Simon Fraser University,
Burnaby, Canada<EMAIL_ADDRESS>
###### Abstract.

We show that for the product of two fixed point free conjugacy classes, the
average number of cycles is always very similar. Specifically, our main result
is that for a randomly chosen pair of fixed point free permutations of cycle
types $\alpha$ and $\beta$, the average number of cycles in their product is
between $H_{n}-3$ and $H_{n}+1$, where $H_{n}$ is the harmonic number.

##  1\. Introduction

Let $n$ be a positive integer. For any finite set $A$, let $\mathfrak{S}_{A}$
be the symmetric group on $A$. We also use the notation
$[n]:=\\{1,\ldots,n\\}$, and $\mathfrak{S}_{n}:=\mathfrak{S}_{[n]}$. A
_partition of $n$_ is a list $\alpha=(\alpha_{1},\ldots,\alpha_{k})$ of
positive integers such that $\alpha_{i}\geq\alpha_{i+1}$ and
$\sum_{i}\alpha_{i}=n$. Each $\alpha_{i}$ is called a _part_ , and the
_length_ of $\alpha$, denoted $\ell(\alpha)$, is the number of parts (thus
$\ell(\alpha)=k$ above). For each $0\leq j\leq\ell(\alpha)$, we define
$\alpha^{\prime}_{j}=\sum_{i=1}^{j}\alpha_{i}$, with $\alpha^{\prime}_{0}=0$.
We let $C_{\alpha}$ be the conjugacy of $\mathfrak{S}_{n}$ indexed by
$\alpha$. We call the permutation
$(1\;\cdots\;\alpha_{1}^{\prime})\cdots(\alpha_{\ell(\alpha)-1}^{\prime}+1\;\cdots\;n)$
the _canonical permutation of type_ $\alpha$. We further let
$H_{n}:=\sum_{i=1}\tfrac{1}{i}$ be the _$n^{\textnormal{th}}$ harmonic
number_.

We start by defining the main statistic of study. For two partitions
$\alpha,\beta\vdash n$, let $C_{\alpha,\beta}$ be the random variable for the
number of cycles in $\sigma\cdot\omega$, where $\sigma$ and $\omega$ are
chosen uniformly at random from the conjugacy classes $C_{\alpha}$ and
$C_{\beta}$, respectively. The goal of this manuscript is to estimate the
expected value of $C_{\alpha,\beta}$ when $\alpha$ and $\beta$ are partitions
without parts equal to 1. We study this statistic through maps.

Let $\alpha$ and $\beta$ be partitions without parts of size 1 of the same
positive integer $n$, and let $\sigma_{0}$ and $\omega_{0}$ be the canonical
permutations of type $\alpha$ and $\beta$, respectively. For a permutation
$\pi\in\mathfrak{S}_{n}$, we define a _map_ $m_{\pi}=(D,R,E(\pi))$, where $D$
is a set and $R$ and $E(\pi)$ are permutations given as follows. The set
$D=S\cup T$ are the _darts_ , where $S=\\{s_{1},\dots,s_{n}\\}$ and
$T=\\{t_{1},\dots,t_{n}\\}$. The set of darts can be thought of as a set of
half-edges in a bipartite graph whose left side (right side) has
$\ell(\alpha)$ ($\ell(\beta)$) vertices, and the $i^{\textnormal{th}}$ vertex
on the left side (right side) has the darts
$s_{\alpha^{\prime}_{i}+1},\ldots,s_{\alpha^{\prime}_{i+1}}$
($t_{\beta^{\prime}_{i}+1},\ldots,t_{\beta^{\prime}_{i+1}})$ at it. The
permutation $E(\pi)$ is a fixed point free involution on the set $D$ given by

$E(\pi):=(s_{1}\,t_{\pi(1)})(s_{2}\,t_{\pi(2)})\dots(s_{n}\,t_{\pi(n)}).$

Thus $E(\pi)$ is in $\mathfrak{S}_{D}$ and gives a perfect matching between
the sets $S$ and $T$; the set $E(\pi)$ indicates that an edge is placed
between the darts $s_{i}$ and $t_{\pi(i)}$ for each $i$, giving a bipartite
graph $G$. The permutation $R$ is also in $\mathfrak{S}_{D}$ and sends

$s_{i}\rightarrow s_{\sigma_{0}(i)}\textnormal{ and }t_{i}\rightarrow
t_{\omega_{0}(i)};$ (1)

that is,

$R:=(s_{1}\,s_{2}\dots
s_{\alpha_{1}^{\prime}})(s_{\alpha_{1}^{\prime}+1},\dots
s_{\alpha_{2}^{\prime}})\dots(s_{\alpha_{\ell(\alpha)-1}^{\prime}+1},\dots,s_{n})\cdot\\\
(t_{1}\,t_{2}\dots t_{\beta_{1}^{\prime}})(t_{\beta_{1}^{\prime}+1},\dots
t_{\beta_{2}^{\prime}})\dots(t_{\beta_{\ell(\beta)-1}^{\prime}+1},\dots,t_{n}),$

and its cycle type is $\alpha\cup\beta$, where $\alpha\cup\beta$ is the
partition of $2n$ with parts in $\alpha$ or $\beta$. The permutation $R$, also
called the _rotation scheme_ , encodes an embedding of the bipartite graph
$G$; when drawn on an orientable surface, the cycles of $R$ give the local
clockwise order in which the darts appear at each vertex. Together
$m_{\pi}=(D,R,E(\pi))$ can be visualized as a 2-cell embedding of a graph on
an orientable surface111A _2-cell embedding_ of a graph on an orientable
surface is an embedding of a graph on a surface such that edges do not cross,
and the removal of the graph from the surface leaves connected components each
homeomorphic to a disc. ; see Figure 1.

Figure 1. Pictured is the map $m_{\pi}$ from Example 1. Here we have
$\alpha=(4,3)$, $\beta=(3,2,2)$ and $\pi=(1)(2\,3\,5)(4\,7\,6)$.

It is well known (see §4.2 [GS98] and references therein) that these maps are
in correspondence with products of permutations of type $\alpha$ and $\beta$.
Faces in the map $m_{\pi}$ are given by the cycles of $R\cdot E(\pi)$, and
they naturally correspond to the cycles in $\sigma_{0}\pi\omega_{0}\pi^{-1}$:
if $\sigma_{0}\pi\omega_{0}\pi^{-1}$ has cycle type $\lambda$, then $R\cdot
E(\pi)$ has cycle type $2\lambda:=(2\lambda_{1},2\lambda_{2},\ldots)$, where
the $\lambda_{i}$ are the parts of $\lambda$. The permutation
$\sigma_{0}\pi\omega_{0}\pi^{-1}$ can be recovered from $R\cdot E(\pi)$ by
simply ignoring the symbols that correspond to darts in $T$ and interpreting
the resulting permutation on $S$ as acting on the symbols on $[n]$.222The
claim about the connection between the cycles of
$\sigma_{0}\pi\omega_{0}\pi^{-1}$ and $R\cdot E(\pi)$ remains true for any
other fixed permutations $\sigma$ and $\omega$ in $C_{\alpha}$ and
$C_{\beta}$, respectively, as long as the permutation $R$ has cycles
compatible with $\sigma$ and $\omega$ in the sense of (1). Example 1
illustrates this correspondence.

######  Example 1 (Permutation/map correspondence).

Let $\alpha=(4,3)$ and $\beta=(3,2,2)$. A map $m_{\pi}=(D,R,E(\pi))$ is
pictured in Figure 1 with $\pi=(1)(2\,3\,5)(4\,7\,6)\in\mathfrak{S}_{7}$. Here
$D=S\cup T$ and

$\displaystyle R$
$\displaystyle=(s_{1}\,s_{2}\,s_{3}\,s_{4})(s_{5}\,s_{6}\,s_{7})\cdot(t_{1}\,t_{2}\,t_{3})(t_{4}\,t_{5})(t_{6}\,t_{7}),$
$\displaystyle E(\pi)$
$\displaystyle=(s_{1}\,t_{1})(s_{2}\,t_{3})(s_{3}\,t_{5})(s_{4}\,t_{7})(s_{5}\,t_{2})(s_{6}\,t_{4})(s_{7}\,t_{6}).$

Whence

$R\cdot
E(\pi)=(s_{1}\,t_{3})(s_{2}\,t_{5}\,s_{6}\,t_{6}\,s_{4}\,t_{1}\,s_{5}\,t_{4}\,s_{3}\,t_{7}\,s_{7}\,t_{2}).$

Each cycle of $R\cdot E(\pi)$ traces a face of $m_{\pi}$ in Figure 1 via a
walk in the following way. Pick a symbol, say $t_{5}$, and begin a walk around
the map while keeping the map to the right; begin at the vertex containing the
dart $t_{5}$ to get to $t_{4}$; then walk along the edge connecting $t_{4}$ to
$s_{6}$. The walk then, by definition, goes from $t_{5}$ to $s_{6}$. Continue
by walking along the vertex containing the dart $s_{6}$ to $s_{7}$, and then
walk along the edge connecting $s_{7}$ to $t_{6}$. The walk then goes from
$s_{6}$ is $t_{6}$. Hence the walk traces $\cdots t_{5}\rightarrow
s_{6}\rightarrow t_{6}\cdots$. Note the permutation $R\cdot E(\pi)$ acts on
those symbols in the same way. The canonical permutations $\sigma_{0}$ and
$\omega_{0}$ of type $\alpha$ and $\beta$, respectively, are given by

$\displaystyle\sigma_{0}$ $\displaystyle=(1\,2\,3\,4)(5\,6\,7)\in C_{\alpha},$
$\displaystyle\omega_{0}$ $\displaystyle=(1\,2\,3)(4\,5)(6\,7)\in C_{\beta}$

We compute

$\displaystyle\sigma_{0}\pi\omega_{0}\pi^{-1}$
$\displaystyle=(1\,2\,3\,4)(5\,6\,7)\cdot(1)(2\,3\,5)(4\,7\,6)\cdot(1\,2\,3)(4\,5)(6\,7)\cdot[(1)(2\,3\,5)(4\,7\,6)]^{-1}$
$\displaystyle=(1)(2\,6\,4\,5\,3\,7)$

Note that $\sigma_{0}\pi\omega_{0}\pi^{-1}$ can be obtained from $R\cdot
E(\pi)$ by removing the symbols in $T$.

Thus studying the number of faces of bipartite maps is equivalent to studying
$C_{\alpha,\beta}$. We use this correspondence to estimate
$E[C_{\alpha,\beta}]$ because it is easier to define our structures and
substructures in maps. We formalise this now.

We denote by $M_{\alpha,\beta}$ the set of all such maps:

$M_{\alpha,\beta}:=\\{m_{\pi}:\pi\in S_{n}\\}$

Let $U$ be the uniform probability distribution on this set. Then
$(M_{\alpha,\beta},U)$ is a probability space. We use $F(\cdot)$ to denote the
number of faces of a map. From above, we see that $F(m_{\pi})=c(R\cdot
E(\pi))$; that is, the number of faces in $m_{\pi}$ is the number of cycles in
the product of $R\cdot E(\pi)$. Define $F_{\alpha,\beta}:=F$ as the random
variable on $(M_{\alpha,\beta},U)$ for the number of faces in a map in
$M_{\alpha,\beta}$.

######  Lemma 2.

For any positive integer $n$ and partitions $\alpha$ and $\beta$ of $n$,

$\mathbb{E}[F_{\alpha,\beta}]=\mathbb{E}[C_{\alpha,\beta}].$

###### Proof.

Note that

$\mathbb{E}[F_{\alpha,\beta}]=\frac{d}{dq}\Bigr{|}_{q=1}\,\frac{1}{n!}\sum_{\pi\in
S_{n}}q^{c(R\cdot E(\pi))},$

while

$\mathbb{E}[C_{\alpha,\beta}]=\frac{d}{dq}\Bigr{|}_{q=1}\,\frac{1}{|C_{\alpha}||C_{\beta}|}\sum_{\begin{subarray}{c}\sigma\in
C_{\alpha}\\\ \omega\in C_{\beta}\end{subarray}}q^{c(\sigma\omega)}.$

With $\sigma_{0}$ and $\omega_{0}$ as the canonical permutations of type
$\alpha$ and $\beta$, respectively, we have

$\displaystyle\frac{1}{n!}\sum_{m_{\pi}\in M_{\alpha,\beta}}q^{F(m_{\pi})}$
$\displaystyle=\frac{1}{n!}\sum_{\pi\in S_{n}}q^{c(R\cdot E(\pi))}$
$\displaystyle=\frac{1}{n!}\sum_{\pi\in
S_{n}}q^{c(\sigma_{0}\pi\omega_{0}\pi^{-1})}$
$\displaystyle=\frac{z_{\beta}}{n!}\sum_{\omega\in
C_{\beta}}q^{c(\sigma_{0}\omega)}$
$\displaystyle=\frac{1}{|C_{\alpha}||C_{\beta}|}\sum_{\begin{subarray}{c}\sigma\in
C_{\alpha}\\\ \omega\in C_{\beta}\end{subarray}}q^{c(\sigma\omega)},$

and the result follows. ∎

The statistic $C_{\alpha,\beta}$ has been studied previously in some special
cases. The case when $\alpha=2^{n/2}$, the partition with all parts equal to
2, models a random surface obtained by gluing together polygonal disks and has
been studied with motivation from physics. Pippenger and Schleich [PS06] show
that $\mathbb{E}[C_{2^{n/2},3^{n/3}}]=H_{n}+O(1)$, and also obtain bounds for
the variance. Their results use a combinatorial analysis of a random process.
More recently, their result was generalised by Chmutov and Pittel [CP16] to
any $\beta$ with parts all of size at least $3$. They show that the whole
distribution of permutations obtained is asymptotically uniform up to parity.
As a corollary to this, it follows that
$\mathbb{E}[C_{2^{n/2},\beta}]=H_{n}+O(1)$. Their proof follows a method of
Gamburd [Gam06] that uses the Fourier transform on representations of the
symmetric group and recent bounds on characters given by Larsen and Shalev
[LS08].

Although it is not explicitly mentioned in their paper, these methods
trivially extend to the case when $\alpha$ has all parts of size at least $3$
and $\beta$ has all parts of size at least $2$. The same result holds in this
case, giving that $\mathbb{E}[C_{\alpha,\beta}]=H_{n}+O(1)$. The size of the
$O(1)$ term is unclear, as it relies on a very general, powerful character
bound. However in some special cases more precise bounds are known. The case
when $\alpha=(n)$ has been studied by various authors, using representation
theory [Sta11], matrix integrals [Jac94], and more combinatorial methods
Goulden and Jackson [GJ92], Cori _et al._ [CMS12], and Boccara [Boc80]. These
results are more refined, and give the exact number of products with a given
number of cycles. From this, we can obtain the average number of cycles. The
case $\alpha=\beta=(n)$ is especially nice; we have that
$\mathbb{E}[C_{(n),(n)}]=H_{n-1}+\lceil\frac{n}{2}\rceil^{-1}$. In the more
general case when $\beta$ has all parts of size at least $2$, it follows from
Stanley’s generating function [Sta11, Theorem 3.1] that
$H_{n-1}-\frac{4}{n}\leq\mathbb{E}[C_{(n),\beta}]\leq H_{n-1}+\frac{4}{n}$
(see [CLHM+22]).

In all these known cases, we see that the average number of cycles is close to
$H_{n}$. We shall here be determining an estimate in the more general case
when $\alpha$ and $\beta$ can be any partitions with no parts of size one. We
state our main theorem.

######  Theorem 3.

For any partitions $\alpha$ and $\beta$ with no part of size 1, we have
$H_{n}-3<\mathbb{E}[C_{\alpha,\beta}]\leq H_{n}+1$.

Our theorem eliminates the asymptotic notation present in the more general
results previously mentioned. The method of proof will also be more
combinatorial, using random processes on maps.

##  2\. Basic terminology and random processes

We give some definitions and terminology that we shall make extensive use of
throughout the paper.

Fix $\alpha$ and $\beta$ to be partitions of $n$ with no parts of size 1. A
partial map is a triple $m=(D,R,E)$, where $D$ and $R$ are defined as they
were for maps, but where $E\in\mathfrak{S}_{D}$ is an involution (not
necessarily fixed point free). The involution can be represented by an
injection $\pi:X\rightarrow[n]$, where $X\subseteq[n]$. Then we can set

$E(\pi):=\prod_{i\in X}(s_{i}\,t_{\pi(i)})$

and define the partial map $m_{\pi}=(D,R,E(\pi))$. Notice that a map is itself
a partial map. In this case $E$ will be a fixed point free involution, and the
associated function $\pi$ will be a permutation on $\\{1,2,\ldots,n\\}$. Also
when $E$ is the identity (the associated function $\pi$ has the empty set as
its domain) the partial map is just a set of darts at vertices with no faces
or edges. These are the two extreme cases.

Fix an injection $\pi:X\rightarrow[n]$ for some subset $X\subseteq[n]$, and
let $m=m_{\pi}=(D,R,E(\pi))$ be a partial map, and write $E=E(\pi)$. Figure 2
contains some examples of the definitions given below.

  * •

_Paired/unpaired darts_ : Each dart in $m$ is one of the symbols in $S$ or
$T$. We have two types of dart:

    * –

Paired dart: A dart in a partial map that is part of an edge, _i.e_ a dart
that is in a $2$-cycle in $E$.

    * –

Unpaired dart: A dart in a partial map that is not part of an edge, _i.e_ a
dart that is a fixed point in $E$. Let $S^{u},T^{u}$ be the set of unpaired
darts in $S,T$ respectively.

  * •

_Completed face_ : A cycle in $R\cdot E$ only containing paired darts. Let
$F(m)$ denote the number of completed faces in the partial map.

  * •

_Unpaired permutation/partial face/length_ : For $m$, the induced permutation
of $R\cdot E$ on $S^{u}\cup T^{u}$ is called the _unpaired permutation_ ,
which we denote $u_{m}$. That is, we remove all paired darts, and any
resulting empty cycles, from $R\cdot E$ to obtain $u_{m}$. We write $u=u_{m}$
when $m$ is clear from the context. A _partial face_ is a cycle in $u_{m}$.
The _length_ of a partial face is its length as a cycle.

  * •

_Bad dart_ : An unpaired dart contained in a cycle of length one in $u_{m}$.

  * •

_Mixed partial face/bad partial map_ : A partial face in $m$ is _mixed_ if it
contains darts in both $S^{u}$ and $T^{u}$. The partial map $m$ is called
_bad_ if it does not contain any mixed partial faces.

Figure 2.  In the partial map $m$ on the left, the paired darts are
$\\{s_{1},s_{2},s_{3},s_{4},s_{7},t_{2},t_{3},t_{4},t_{5},t_{7}\\}$. The
unpaired darts are all of the remaining darts, so $S^{u}=\\{s_{5},s_{6}\\}$
and $T^{u}=\\{t_{1},t_{6}\\}$. It has two completed faces, given by the cycles
$(s_{2}\,t_{2})$ and $(s_{4}\,t_{5})$. The unpaired permutation is
$u_{m}=(t_{1})(s_{5}\,s_{6}\,t_{6})$. It has one bad dart, $t_{1}$, and it has
one mixed partial face, so it is not a bad map. The partial map $m^{\prime}$
on the right has $S^{u}=\\{s_{5},s_{6},s_{7}\\}$ and
$T^{u}=\\{t_{1},t_{6},t_{7}\\}$, and it has the same bad dart, $t_{1}$, as
$m$. Furthermore, we observe
$u_{m^{\prime}}=(t_{1})(s_{5}\,s_{6}\,s_{7}\,s_{8})(t_{6}\,t_{7})$. There are
no mixed partial faces, so $m^{\prime}$ is a bad map.

We shall use a different random process to prove the upper and lower bounds
for $\mathbb{E}[F_{\alpha,\beta}]$.

Random Process A (RPA)

  1. (1)

Initialize $S^{u}=S$, $T^{u}=T$, $X=\emptyset$, $\pi_{0}:X\rightarrow[n]$.

  2. (2)

Call $m_{\pi_{k-1}}$ the partial map at the start of the $k^{\textnormal{th}}$
step. Pick the _active dart_ $d$ from $S^{u}\cup T^{u}$ with respect to the
following order of preference.

     * •

The bad dart in $S^{u}$ with smallest index.

     * •

The bad dart in $T^{u}$ with smallest index.

     * •

The dart with the smallest index in $S^{u}$.

  3. (3)

If $d=s_{i}\in S^{u}$, then pick $t_{j}\in T^{u}$ uniformly at random and call
$t_{j}$ the _pairing dart_ at this step. If $d=t_{j}\in T^{u}$, then pick
$s_{i}\in S^{u}$ uniformly at random and call $s_{i}$ the _pairing dart_. Set
$X=X\cup\\{i\\}$, and define $\pi_{k}:X\rightarrow[n]$ as $\pi_{k-1}$ from the
previous step, but also with $\pi_{k}(i)=j$.

  4. (4)

Then $S^{u}=S^{u}-\\{s_{i}\\}$ and $T^{u}=T^{u}-\\{t_{j}\\}$. If
$S^{u}\neq\emptyset$ then return to step $2$.

  5. (5)

Output the map $m_{\pi_{n}}$.

Random Process B (RPB)

  1. (1)

Initialize $S^{u}=S$ and $T^{u}=T$, $X=\emptyset$, $\pi_{0}:X\rightarrow[n]$.

  2. (2)

Call $m_{\pi_{k-1}}$ the partial map at the start of the $k^{\textnormal{th}}$
step. Pick the _active dart_ as $s_{k}$.

  3. (3)

Pick $t_{j}\in T^{u}$ uniformly at random and call $t_{j}$ the _pairing dart_
at this step. Set $X=X\cup\\{i\\}$, and define $\pi_{k}:X\rightarrow[n]$ as
$\pi_{k-1}$ from the previous step also with $\pi_{k}(i)=j$.

  4. (4)

Then $S^{u}=S^{u}-\\{s_{k}\\}$ and $T^{u}=T^{u}-\\{t_{j}\\}$. If
$S^{u}\neq\emptyset$ then return to step $2$.

  5. (5)

Output the map $m_{\pi_{n}}$.

After $n$ steps of either process, the output is a map in $M_{\alpha,\beta}$.

######  Lemma 4.

RPA and RPB both output a uniform at random map from $M_{\alpha,\beta}$.

###### Proof.

At the $k^{\textnormal{th}}$ iteration of step $2$, there are $n-k+1$ choices
of pairing dart. There are therefore $n!$ possible outcomes of this random
process, each with equal probability. There are $n!$ elements in
$M_{\alpha,\beta}$, and every map is clearly output by each of the random
processes. The result follows. ∎

We give some basic observations, which are illustrated in Figures 3 and 4.

######  Observation 5.

Suppose that we are at some step 2 of RPA or RPB. Let $m$ be the partial map
at the beginning of this step, and suppose that it has active dart $d$. Step 3
then pairs $d$ with another dart. Let $u=u_{m}$. Observe the following.

  1. 1.

Suppose that $d$ is a bad dart. A completed face is added at this step if and
only if the pairing dart is also bad (_i.e._ in the unpaired permutation $u$,
both $d$ and its pairing dart are fixed points). When a completed face is
added the resulting map has two fewer bad darts. A new bad dart is added if
and only if the pairing dart is in a partial face of length $2$.

  2. 2.

Suppose that $d$ is not a bad dart. A completed face is added if and only if
the pairing dart is $u(d)$ or $u^{-1}(d)$. If the pairing dart is $u(d)$ and
$u(d)=u^{-1}(d)$ then two completed faces are added at this step. Similarly, a
bad dart is added if and only if the pairing dart is $u^{2}(d)$ or
$u^{-2}(d)$. If $u^{2}(d)=u^{-2}(d)$, then two bad darts are added.

Figure 3.  Illustrating Observation 5.1, we have four maps: the left contains
two partial maps $m_{1}$ and $m_{2}$ and the right contains possible outputs
$m_{1}^{\prime}$ and $m_{2}^{\prime}$, respectively, of an application of one
of the random processes. On the left the active dart is in green. The map
$m_{1}$ has two bad darts $s_{4}$ (the active dart) and $t_{4}$. The map
$m_{1}^{\prime}$ was obtained by pairing $s_{4}$ with $t_{4}$, completing a
face (given by the cycle $(s_{1}\,t_{3}\,s_{4}\,t_{1}\,s_{3}\,t_{4})$), as
claimed in Observation 5.1.
The map $m_{2}$ has $s_{3}$ as the active dart, and has a face of length 2. If
$s_{3}$ is paired with $t_{5}$, a bad dart, $t_{8}$, is created in
$m_{2}^{\prime}$.  Figure 4. Illustrating Observation 5.2, we have four maps
whose relationship with each other is the same as in Figure 3. The green dart
is again the active dart. We find
$u_{m_{1}}=(s_{5}\,s_{6}\,s_{7}\,s_{8})(t_{5}\,t_{6})(t_{7}\,t_{8})(s_{4}\,t_{4})$.
The partial map $m_{1}^{\prime}$ is obtained by pairing $s_{4}$ with $t_{4}$;
by Observation 5.2 this creates two completed cycles, one is given by
$(s_{1}\,t_{1}\,s_{3}\,t_{4}\,s_{2}\,t_{2})$ and the other by
$(t_{3}\,s_{4})$.
The map $m_{2}$ has $u_{m_{2}}=(s_{5}\,s_{6}\,t_{2}\,t_{5})$. The partial map
$m_{2}^{\prime}$ is obtained from $m_{2}$ by pairing the active dart $s_{5}$
with $t_{2}$. Since $u^{2}_{m_{2}}(s_{5})=u^{-2}_{m_{2}}(s_{5})=t_{2}$, this
creates two bad darts in $m_{2}^{\prime}$, the darts $s_{6}$ and $t_{5}$.

###  2.1. Proving the upper bound with RPA

Again, throughout this section $\alpha$ and $\beta$ are partitions of some
positive integer $n$ with no parts of size 1. Suppose some partial map $m$
appears at the start of some step of RPA. Then the random process will pair
the active dart with a randomly chosen pairing dart. This will add some number
(possibly zero) of completed faces to the partial map. Let $F_{m}$ be the
random variable for the number of completed faces that are added when the
random process adds a new edge to $m$.

######  Lemma 6.

Suppose the random process outputs the map $m_{\pi}$. Let $m_{\pi}^{(k)}$
denote the partial map at the $k^{\textnormal{th}}$ step of the process that
outputted $m_{\pi}$. Then we have

$\mathbb{E}[F_{\alpha,\beta}]\leq\max_{m_{\pi}\in
M_{\alpha,\beta}}\left\\{\sum_{k=1}^{n}\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\right\\}.$

###### Proof.

Each face in $m_{\pi}$ is added as a completed face at some step of RPA. Once
it is added, it cannot be removed at a later step. At the
$k^{\textnormal{th}}$ iteration of step 3, let $m_{k}$ be the random variable
for the partial map at the start of this step, and let $A_{k}$ be the random
variable for the number of completed faces added at the $k^{\textnormal{th}}$
step.

Using total probability, we have

$\mathbb{E}[A_{k}]=\sum_{m}Pr[m_{k}=m]\mathbb{E}[F_{m}],$

where the sum is over all possible partial maps. Using linearity of
expectation gives:

$\displaystyle\mathbb{E}[F_{\alpha,\beta}]$
$\displaystyle=\sum_{k=1}^{n}\mathbb{E}[A_{k}]$
$\displaystyle=\sum_{k=1}^{n}\sum_{m}Pr[m_{k}=m]\mathbb{E}[F_{m}]$
$\displaystyle=\frac{1}{n!}\sum_{m_{\pi}\in
M_{\alpha,\beta}}\sum_{k=1}^{n}\mathbb{E}[F_{m_{\pi}^{(k-1)}}]$
$\displaystyle\leq\max_{m_{\pi}\in
M_{\alpha,\beta}}\left\\{\sum_{k=1}^{n}\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\right\\}\qed$

######  Lemma 7.

Any partial map $m$ appearing at the start of some step of RPA has at most two
bad darts, and at most one mixed partial face. This mixed partial face is
always of the form
$(s_{i_{1}}\,\dots\,s_{i_{a}}\,t_{j_{1}}\,\dots\,t_{j_{b}})$, and if the
active dart $d$ is in this partial face it must equal $s_{i_{1}}$.

###### Proof.

Suppose the partial map $m$ has no bad darts, and suppose $d$ is the active
dart at this step. If the pairing dart is $u^{2}(d)$ then $u(d)$ will become a
bad dart at the next step. If the pairing dart is $u^{-2}(d)$ then $u^{-1}(d)$
will become a bad dart at the next step. If $u^{2}(d)=u^{-2}(d)$ then these
choices coincide and we add two bad darts. The above are merely Observation 5
restated. In either case, we add at most two bad darts.

Now suppose $m$ has one or two bad darts. Then $d$ is one of these bad darts,
since step 2 of RPA prioritises choosing bad darts for the active dart. See
Figure 3 for an example of RPA processing a bad dart. We make a new bad dart
if and only if the pairing dart $d^{\prime}$ is in partial face of length 2.
In the new map $d$ will no longer be a bad dart. Since we removed a bad dart,
and added at most one bad dart, at the next step we will have at most two bad
darts.

This covers both cases, so the number of bad darts is always at most two. We
now prove the claims about the mixed partial faces.

The partial map at the start of an application of RPA has no paired darts, so
it has no mixed partial faces. We therefore proceed by induction. Let $m$ be
the partial map at the beginning of some iteration of RPA. Suppose the partial
map $m$ at the start of a step of the process has at most one mixed partial
face. If the map is bad then it has no mixed partial faces, and we can add at
most one mixed partial face at this step.

Otherwise assume that the map has one mixed partial face. We have two cases:
the active dart $d$ is bad or not. If $d$ is bad, then processing it cannot
add any more mixed partial faces. If $d$ is not bad, then it is in $S^{u}$ by
our choice of active dart in step 2. Let $v$ be the vertex incident with $d$.
We first aim to show that $u_{m}^{-1}(d)\in T^{u}$; for that purpose, we
assume the opposite: that $u_{m}^{-1}(d)\in S^{u}$. First, all the darts in
$S^{u}$ with smaller index than $d$ are processed. Second, observe that all
the darts in $S^{u}$ not incident with $v$ with larger index must be in
partial faces only containing darts in $S^{u}$. This is because any paired
dart with larger index than $d$ in $S^{u}$ (at $v$ or a later vertex) must
have been paired with an active bad dart in $T$ (by the choice of active dart
at step 2), and pairing an active bad dart cannot create a new mixed partial
face. This has two consequences. First, all the darts in $S^{u}$ that are
contained in the mixed partial face must be incident with $v$. Moreover, they
appear contiguously in the mixed partial face from the dart with lowest index
to the dart with highest index. Since $d$ is the dart with lowest index among
the unpaired darts at $v$, if $u_{m}^{-1}(d)\in S^{u}$, then $u_{m}^{-1}(d)$
has the highest index amongst unpaired darts at $v$. Therefore the mixed
partial face equals $(d\cdots u_{m}^{-1}(d))$, so only contains darts incident
with $v$. Thus this partial face is not mixed, giving a contradiction.

Therefore $u_{m}^{-1}(d)\in T^{u}$, so the mixed partial face is of the form
$(d\,s_{i_{1}}\,\cdots\,s_{i_{a}}\,t_{j_{1}}\,\cdots\,t_{j_{b}})$ with $a\geq
0$ and $b\geq 1$. Pairing $d$ with any dart in this mixed partial face, or
outside of this mixed partial face, still preserves there being at most one
mixed partial face of this form. ∎

We now estimate when completed faces are added to a partial map.

###### Proof of the upper bound in Theorem 3.

Fix some map $m_{\pi}\in M_{\alpha,\beta}$. Using Lemma 6 it will be
sufficient to estimate $\sum_{k=1}^{n}\mathbb{E}[F_{m_{\pi}^{(k-1)}}]$. Fix
some value of $k$ and let $d$ be the active dart chosen in the
$k^{\textnormal{th}}$ iteration of step 2.

Case 1: The dart $d$ is bad. By Observation 5, a face will be added if and
only if the pairing dart is also bad. By Lemma 7, there is at most one other
bad dart, so there is at most one other choice that adds a face. This gives
$\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\leq\frac{1}{n-k+1}$.

Case 2: The dart $d$ is not bad and $u(d)\in S^{u}$. Then the pairing dart
cannot be chosen to be $u(d)$, so $u^{-1}(d)$ is the only possible choice of
pairing dart that adds a completed face. In this case
$\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\leq\frac{1}{n-k+1}$.

Case 3: The dart $d$ is not a bad dart and $u(d)\in T^{u}$. Then choosing the
pairing dart to be $u(d)$ or $u^{-1}(d)$ adds a completed face, and both of
these choices are possible. If $u(d)=u^{-1}(d)$ then choosing the pairing dart
to be $u(d)$ adds $2$ completed faces. We therefore have
$\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\leq\frac{2}{n-k+1}$. Since $u(d)\in T^{u}$,
we see that $d$ is in a mixed partial face at the start of this step. By Lemma
7 we have that $u^{-1}(d)\in T^{u}$, so the mixed partial face is of the form
$(d\,t_{i_{1}}\,\dots\,t_{i_{a}})$. Therefore once $d$ is paired, this face is
no longer mixed. By Lemma 7 this was the only mixed partial face at the start
of this step, so the map at the start of the next step is bad.

Let $d^{\prime}$ be the active dart at the next step, which is step $k+1$. If
the active dart $d^{\prime}$ is bad, then we are in case 1 and we may add more
faces. In this case, the partial map at the start of step $k+2$ will also be
bad. This will continue until we eventually arrive at some step $j$, with
$j>k$, where the partial map at the start of this step is bad and the active
dart is not bad, or the whole map will be completed before we reach such a
step $j$. If this step $j$ exists, and $\hat{d}$ is the active dart, then
because the map is bad, we have $u_{m_{\pi}^{(j-1)}}(\hat{d})\in S^{u}$ and
$u^{-1}_{m_{\pi}^{(j-1)}}(\hat{d})\in S^{u}$, so there will be no choice of
pairing dart that adds a face. Therefore $\mathbb{E}[F_{m_{\pi}^{(j-1)}}]=0$.
Grouping together these terms we obtain
$\mathbb{E}[F_{m_{\pi}^{(k-1)}}]+\mathbb{E}[F_{m_{\pi}^{(j-1)}}]\leq\tfrac{2}{n-k+1}<\tfrac{1}{n-k+1}+\tfrac{1}{n-j+1}$,
with the intermediate terms
$\mathbb{E}[F_{m_{\pi}^{(i-1)}}]\leq\tfrac{1}{n-i+1}$. Thus

$\sum_{i=k}^{j}\mathbb{E}[F_{m_{\pi}^{(i-1)}}]\leq\sum_{i=k}^{j}\frac{1}{n-i+1}.$
(2)

If the index $j$ exists, we call the above described run between $k$ and $j$
of the algorithm a _closed run_ , and a _open run_ otherwise. The algorithm
may have several closed runs, and potentially one open run. The expectations
for added faces for closed runs all satisfy (2). Then, by definition, all
remaining iterations of the algorithm satisfy Cases 1 or 2, in which case

$\sum_{k=1}^{n}\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\leq\sum_{k=1}^{n}\frac{1}{n-k+1}=H_{n}<H_{n}+1.$

If there is an open run beginning at the $k^{\textnormal{th}}$ iteration, then

$\sum_{i=k}^{n}\mathbb{E}[F_{m_{\pi}^{(i-1)}}]\leq\frac{2}{n-k+1}+\sum_{i=k+1}^{n}\frac{1}{n-i+1}\leq\left(\sum_{i=k}^{n}\frac{1}{n-i+1}\right)+1,$

in which case we also obtain

$\sum_{k=1}^{n}\mathbb{E}[F_{m_{\pi}^{(k-1)}}]\leq\left(\sum_{k=1}^{n}\frac{1}{n-k+1}\right)+1\leq
H_{n}+1.$

In either case, the result is proved. ∎

###  2.2. Proving the lower bound with RPB

Again, throughout this section $\alpha=(\alpha_{1},\ldots)$ and
$\beta=(\beta_{1},\ldots)$ are partitions of some positive integer $n$ with no
parts of size 1. Recall that for each $0\leq j\leq\ell(\alpha)$ that
$\alpha^{\prime}_{j}=\sum_{i=1}^{j}\alpha_{i}$, with $\alpha^{\prime}_{0}=0$.

We prove the lower bound by analysing RPB. In this case the active dart at the
beginning of step $k$ is always $s_{k}$. Let $B_{k}$ be the random variable
for the number of completed faces added to the partial map at step $k$. Thus
$B_{k}$ is similar to $A_{k}$ except it applies to RPB. As for $A_{k}$, we
clearly have

$\mathbb{E}[F_{\alpha,\beta}]=\sum_{k=1}^{n}\mathbb{E}[B_{k}].$ (3)

We will need some additional variables on RPB. Let $m$ be the partial map at
the start of step $k$ of RPB. Note that $m$ has $k-1$ edges and $2(n-k+1)$
unpaired darts.

  * •

Let $O_{k}$ be the random variable for the number of bad darts in $T^{u}$ in
$m$.

  * •

Let $b_{k}$ be the event that $m$ is bad.

Thus each variable $O_{k}$ and $b_{k}$ count their relevant quantities at the
beginning of step $k$ of the algorithm. Before we find estimates on these new
definitions, we make an observation about RPB. These observations are based on
the simple choice of active dart in step 2.

######  Observation 8.

Let $m$ be a map at the beginning of step $k$. Suppose the active dart $s_{k}$
is at the $j^{\textnormal{th}}$ vertex, so $k=\alpha_{j}^{\prime}+r$ for some
$0\leq r\leq\alpha_{j+1}-1$. Then all the darts at the $j^{\textnormal{th}}$
vertex after $s_{k}$ are unpaired, while all the darts before are paired.
Furthermore, all the darts at the $i^{\textnormal{th}}$ vertex on the left
hand side are paired if $i<j$ and unpaired if $i>j$. It follows that a cycle
of $u_{m}$ is $(s_{k}\cdots s_{\alpha^{\prime}_{j+1}}\,t_{i_{1}}\cdots
t_{i_{p}})$ for some set of darts $M=\\{t_{i_{1}},\ldots,t_{i_{p}}\\}\subseteq
T$. This is the only potentially mixed partial face of $m$, and $m$ is bad if
and only if $M$ is empty. In the special case where $r=1$, the set $M$ is
necessarily empty, and the above cycle of $u_{m}$ has the form
$(s_{\alpha^{\prime}_{j}+1}\cdots s_{\alpha^{\prime}_{j+1}})$.

We now give estimates on $O_{k}$ and $b_{k}$.

######  Lemma 9.

If $k\neq\alpha^{\prime}_{j}+1$ for all $j$, then $\mathbb{E}[O_{k}]\leq 3$
and $Pr[b_{k}]\leq\frac{4}{n-k+2}$. If $k=\alpha^{\prime}_{j}+1$ for some $j$
or $k=1$, then $\mathbb{E}[O_{k}]\leq 3+\frac{3}{n-k+2}$ and $Pr[b_{k}]=1$.

###### Proof.

Our proof is by induction on $k$, the steps of the algorithm. Since $\alpha$
and $\beta$ have no parts of size one, we have
$\mathbb{E}[O_{1}]=\mathbb{E}[O_{2}]=0$, $P[b_{1}]=1$ and $Pr[b_{2}]=0$. Now
suppose the conditions of the lemma hold for $O_{j}$ and $b_{j}$ for all
$j\leq k$. We prove the result holds after the $k^{\textnormal{th}}$ step is
completed (the beginning of the $(k+1)^{\textnormal{st}}$ step). Denote the
map at the beginning of the $k^{\textnormal{th}}$ step $m$; the active dart in
$m$ is $s_{k}$ and there are $n-k+1$ unpaired darts in $T^{u}$ that $s_{k}$
could be paired with at this step. We set $u=u_{m}$ to be the unpaired
permutation.

Case 1: $k\neq\alpha^{\prime}_{j}$ and $k\neq\alpha^{\prime}_{j}+1$ for all
$j$. From Observation 5, we add a bad dart at this step if and only if the
pairing dart is $u^{2}(s_{k})$ or $u^{-2}(s_{k})$. However, by our choice of
$k$, we have $u(s_{k})\in S^{u}$, so pairing $s_{k}$ with $u^{2}(s_{k})$ would
add a bad dart in $S^{u}$ in the resulting map. Therefore there is only one
choice of pairing dart for $s_{k}$ that could add a bad dart in $T^{u}$.
Separately, if the pairing dart is a bad dart, then the pairing dart is no
longer bad in the resulting partial map. Since $k\neq\alpha^{\prime}_{j}+1$,
we have $\mathbb{E}[O_{k}]\leq 3$, so

$\displaystyle\mathbb{E}[O_{k+1}]$
$\displaystyle\leq\mathbb{E}[O_{k}]-\frac{\mathbb{E}[O_{k}]}{n-k+1}+\frac{1}{n-k+1}$
$\displaystyle\leq 3\left(1-\frac{1}{n-k+1}\right)+\frac{1}{n-k+1}<3.$

If the partial map $m$ at the beginning of the $k^{\textnormal{th}}$ step is
bad, then the partial map at the $(k+1)^{\textnormal{st}}$ step will be bad if
and only if the pairing dart is bad. If $m$ is not bad, then by Observation 8
the only mixed partial face is the one containing the active dart $s_{k}$, and
the only pairing dart that results in a bad map is $t_{i_{1}}$ (in the
notation of Observation 8). Both cases of $m$ being bad and not bad are
illustrated in Figure 5.

Figure 5. On the left are possible maps at the beginning of the
$6^{\textnormal{th}}$ iteration of the RPB, while the primed maps on the right
are their output after the $6^{\textnormal{th}}$ step is executed. In both
cases $s_{6}$ (green) is the active dart. At top left, we have
$u_{m_{1}}=(s_{6}\,s_{7}\,s_{8})(t_{1})(t_{7}\,t_{8})$, so the map is bad. The
dart $s_{6}$ is paired with the bad dart $t_{1}$ to obtain $m_{1}^{\prime}$,
which is bad. The reader can confirm that pairing $s_{6}$ with either dart
$t_{7}$ or $t_{8}$ (neither dart is bad) instead of $t_{1}$ does not produce a
bad map.
At bottom left, we have
$u_{m_{2}}=(s_{6}\,s_{7}\,s_{8}\,t_{3}\,t_{8})(t_{1})$, so $m_{2}$ has a mixed
partial face and is not bad. Note the mixed partial face contains the active
dart. Furthermore, the dart $t_{3}$ plays the role of $t_{i_{1}}$ in
Observation 8, and if $s_{6}$ is paired with $t_{3}$, we get the bad map
$m_{2}^{\prime}$. The reader can check that pairing $s_{6}$ with $t_{1}$ or
$t_{8}$ instead of $t_{3}$ does not give a bad map.

Since $k\neq\alpha^{\prime}_{j}+1$, we can use the inductive assumption and
total probability to obtain

$\displaystyle Pr[b_{k+1}]$ $\displaystyle=Pr[b_{k+1}\mid
b_{k}]Pr[b_{k}]+Pr[b_{k+1}\mid b_{k}^{c}]Pr[b_{k}^{c}]$ $\displaystyle\leq
Pr[b_{k}]\frac{\mathbb{E}[O_{k}\mid
b_{k}]}{n-k+1}+Pr[b_{k}^{c}]\frac{1}{n-k+1}$ $\displaystyle\leq
Pr[b_{k}]\frac{\mathbb{E}[O_{k}\mid
b_{k}]}{n-k+1}+Pr[b_{k}^{c}]\frac{1+\mathbb{E}[O_{k}\mid b_{k}^{c}]}{n-k+1}$
$\displaystyle\leq\frac{1+\mathbb{E}[O_{k}]}{n-k+1}\leq\frac{4}{n-k+1}.$

Case 2: $k=\alpha^{\prime}_{j}$ for some $j$. In this case the active dart
$s_{k}$ is the last unpaired dart at its vertex. If the partial map at this
step is not bad, then by Observation 5 both $u^{2}(s_{k})$ and $u^{-2}(s_{k})$
are valid choices of pairing dart that add a bad dart to the resulting map.
Therefore we expect to add $\frac{2}{n-k+1}$ bad darts in this case. If the
partial map at this step is bad, then $s_{k}$ itself is a bad dart. In this
case we add one new bad dart if and only if the pairing dart is in a partial
face containing two unpaired darts. If we are at an early step and
$\beta=2^{n/2}$, then almost every dart could satisfy this. Therefore we use a
rough estimate and assume any choice of pairing dart will add a bad dart.
Regardless of if the partial map at this step is bad or not, pairing $s_{k}$
with any bad dart will result in a map with one fewer bad dart (the pairing
dart will no longer be bad). This gives

$\displaystyle\mathbb{E}[O_{k+1}]$ $\displaystyle\leq\mathbb{E}[O_{k+1}\mid
b_{k}]Pr[b_{k}]+\mathbb{E}[O_{k+1}\mid b_{k}^{c}]Pr[b_{k}^{c}]$
$\displaystyle\leq(\mathbb{E}[O_{k}\mid
b_{k}]+1)Pr[b_{k}]+\left(\mathbb{E}[O_{k}\mid
b_{k}^{c}]+\frac{2}{n-k+1}\right)Pr[b_{k}^{c}]-\frac{\mathbb{E}[O_{k}]}{n-k+1}$
$\displaystyle=\mathbb{E}[O_{k}]\left(1-\frac{1}{n-k+1}\right)+Pr[b_{k}]\left(1-\frac{2}{n-k+1}\right)+\frac{2}{n-k+1}$
$\displaystyle\leq
3\left(1-\frac{1}{n-k+1}\right)+\frac{4}{n-k+2}\left(1-\frac{2}{n-k+1}\right)+\frac{2}{n-k+1}$
$\displaystyle=3\left(1-\frac{1}{n-k+1}\right)+\frac{6}{n-k+1}-\frac{12}{(n-k+1)(n-k+2)}$
$\displaystyle\leq 3+\frac{3}{n-k+1}.$

At the next step, the active dart is $s_{k+1}$, and
$k+1=\alpha^{\prime}_{j}+1$. Then by Observation 8 all of the darts at the
vertex incident with $s_{k+1}$ are unpaired. Therefore the partial map is
necessarily bad. This means $Pr[b_{k+1}]=1$.

Case 3: We have $k=\alpha^{\prime}_{j}+1$ for some $j$. In this case, again,
the active dart $s_{k}$ is at a vertex with all unpaired darts by Observation
8 and the map is bad. Therefore there are no choices of pairing dart that add
a bad dart in $T^{u}$. However, choosing a pairing dart that is bad will
remove this bad dart from the resulting map. Therefore using induction we have

$\displaystyle\mathbb{E}[O_{k+1}]$
$\displaystyle\leq\left(1-\frac{1}{n-k+1}\right)\mathbb{E}[O_{k}]$
$\displaystyle\leq\left(1-\frac{1}{n-k+1}\right)\left(3+\frac{3}{n-k+2}\right)$
$\displaystyle<3\left(\frac{n-k}{n-k+1}\right)\left(\frac{n-k+1}{n-k}\right)=3.$

Since the partial map at the start of this step is bad, the partial map at the
next step will be bad if and only if the pairing dart is bad. Therefore we
obtain

$\displaystyle
Pr[b_{k+1}]\leq\frac{\mathbb{E}[O_{k}]}{n-k+1}\leq\frac{3+\frac{3}{n-k+2}}{n-k+1}\leq\frac{4}{n-k+1}.$

Note that when $n-3\leq k\leq n$, the right hand side of the previous equation
is greater than or equal to 1, so it provides no interesting bound for
$Pr[b_{k+1}]$.

This covers all the cases and hence completes the induction. ∎

We are now ready to give the lower bound.

###### Proof of the lower bound in Theorem 3.

We estimate $\mathbb{E}[B_{k}]$ for each $k$ and then use (3). First observe
that $\mathbb{E}[B_{n}]\geq 1$ and $\mathbb{E}[B_{1}]=0$. Second, for the
special cases when $k=\alpha_{j}^{\prime}+1$ for some $j$, we find by
Observations 5 and 8 that the map at the beginning of the
$k^{\textnormal{th}}$ iteration is bad and that $\mathbb{E}[B_{k}]=0$.

Next, using total probability, we have

$\mathbb{E}[B_{k}]=\mathbb{E}[B_{k}|b_{k}]Pr[b_{k}]+\mathbb{E}[B_{k}|b_{k}^{c}]Pr[b_{k}^{c}]\geq\mathbb{E}[B_{k}|b_{k}^{c}](1-Pr[b_{k}]).$
(4)

To estimate the right hand side of (4), we use the estimate on $Pr[b_{k}]$
from Lemma 9, but note that estimate is only useful when $k\leq n-3$
(otherwise the stated estimate on $Pr[b_{k}]$ is greater than or equal to 1).
Thus when $k=n-2$ or $n-1$, we use the coarse lower bound of 0 for
$\mathbb{E}[B_{k}]$. Thus we have so far

$\displaystyle\mathbb{E}[B_{1}],\mathbb{E}[B_{n-2}]\textnormal{ and
}\mathbb{E}[B_{n-1}]\geq 0,$ $\displaystyle\mathbb{E}[B_{n}]\geq 1,$ (5) and
$\displaystyle\mathbb{E}[B_{k}]=0\textnormal{ when
}k=\alpha^{\prime}_{j}+1\textnormal{ for some }j.$

For the remaining values of $k$, we estimate (4) in two cases: when
$k\neq\alpha_{j}^{\prime}$ for all $j$ and when $k=\alpha^{\prime}_{j}$ for
some $j$. At the beginning of the $k^{\textnormal{th}}$ step, we let $m$ be
the partial map and $v$ the vertex with the active dart $s_{k}$. Since we are
estimating $\mathbb{E}[B_{k}|b_{k}^{c}]$, we assume $m$ is not bad.

Case 1: $k\neq\alpha^{\prime}_{j}$ for any $j$. Then since $m$ is not bad, by
Observation 8 we have that the active dart $s_{k}$ is in the lone mixed
partial face, so $u^{-1}(s_{k})\in T^{u}$, while $u(s_{k})\in S^{u}$, from
which it follows that $s_{k}$ is not bad. But then from Observation 5 it
follows that the lone choice of pairing dart that adds a face is
$u^{-1}(s_{k})$. So

$\displaystyle\mathbb{E}[B_{k}|b_{k}^{c}]$ $\displaystyle\geq\frac{1}{n-k+1},$

whence

$\displaystyle\mathbb{E}[B_{k}|b_{k}^{c}](1-Pr[b_{k}])$
$\displaystyle\geq\frac{1}{n-k+1}\left(1-\frac{4}{n-k+2}\right)$
$\displaystyle=\frac{1}{n-k+1}-\frac{4}{(n-k+1)(n-k+2)}.$

Case 2: $k=\alpha^{\prime}_{j}$ for some $j$. Since $m$ is not bad, by
Observation 8 the active dart $s_{k}$ is in a mixed face, so $s_{k}$ is not
bad. By Observation 5 there are two choices of pairing dart that add a
completed face: $u(s_{k})$ and $u^{-1}(s_{k})$. Both of these may be possible
as choices of pairing dart, since $s_{k}$ being the last unpaired dart at $v$
implies $u(s_{k}),u^{-1}(s_{k})\in T^{u}$. As noted in Observation 5, if
$u(s_{k})=u^{-1}(s_{k})$, then two faces are added. Hence

$\displaystyle\mathbb{E}[B_{k}|b_{k}^{c}]$
$\displaystyle\geq\frac{2}{n-k+1}=\frac{1}{n-k}+\frac{1}{n-k+1}-\frac{1}{(n-k)(n-k+1)}.$

This gives

$\displaystyle\mathbb{E}[B_{k}|b_{k}^{c}](1-Pr[b_{k}])$
$\displaystyle\geq\left(\frac{1}{n-k}+\frac{1}{n-k+1}-\frac{1}{(n-k)(n-k+1)}\right)\left(1-\frac{4}{n-k+2}\right)$
$\displaystyle>\frac{1}{n-k+1}+\frac{1}{n-k}-\frac{4}{(n-k+1)(n-k+2)}$
$\displaystyle\;\;\;\;\;-\frac{4}{(n-k)(n-k+2)}-\frac{1}{(n-k)(n-k+1)}$
$\displaystyle>\frac{1}{n-k+1}-\frac{4}{(n-k+1)(n-k+2)}$
$\displaystyle\;\;\;\;\;+\frac{1}{n-k}-\frac{5}{(n-k)(n-k+1)}.$

Let

$\displaystyle C$
$\displaystyle=\\{\alpha^{\prime}_{j}:j=1,\ldots,\ell(\alpha)-1\textnormal{
and }\alpha^{\prime}_{j}\leq n-3\\}$ $\displaystyle\textnormal{ and }D$
$\displaystyle=\\{\alpha^{\prime}_{j}+1:j=1,\ldots,\ell(\alpha)-1\textnormal{
and }\alpha^{\prime}_{j}\leq n-4\\},$

and recall the identity

$\sum_{k=i}^{m}\frac{1}{k(k+1)}=\frac{1}{i}-\frac{1}{m+1}.$

Then, using (3), (4) and (5) and summing over $k$ gives:

$\displaystyle\mathbb{E}[F_{\alpha,\beta}]$
$\displaystyle=\sum_{k=1}^{n}\mathbb{E}[B_{k}]=1+\sum_{k=2}^{n-3}\mathbb{E}[B_{k}|b_{k}^{c}](1-Pr[b_{k}])$
$\displaystyle\geq 1+\sum_{k=2\atop k\notin
C,D}^{n-3}\left(\frac{1}{n-k+1}-\frac{4}{(n-k+1)(n-k+2)}\right)$
$\displaystyle\;\;\;\;\;\;+\sum_{k\in
C}\left(\frac{1}{n-k+1}-\frac{4}{(n-k+1)(n-k+2)}+\frac{1}{n-k}-\frac{5}{(n-k)(n-k+1)}\right)$
$\displaystyle=1+\sum_{k=2\atop k\notin
C,D}^{n-3}\left(\frac{1}{n-k+1}-\frac{4}{(n-k+1)(n-k+2)}\right)$
$\displaystyle\;\;\;\;\;\;+\sum_{k\in
C,D}\left(\frac{1}{n-k+1}-\frac{5}{(n-k+1)(n-k+2)}\right)$
$\displaystyle>1+\sum_{k=2}^{n-3}\frac{1}{n-k+1}-5\sum_{k=2}^{n-3}\frac{1}{(n-k+1)(n-k+2)}$
$\displaystyle=H_{n}-\frac{1}{2}-\frac{1}{3}-\frac{1}{n}-5\left(\frac{1}{4}-\frac{1}{n}\right)=H_{n}-\frac{25}{12}+\frac{4}{n}>H_{n}-3.\qed$

## References

  * [Boc80] G. Boccara.  Nombre de representations d’une permutation comme produit de deux cycles de longueurs donnees.  Discrete Mathematics, 29(2):105–134, 1980.
  * [CLHM+22] J. Campion Loth, K. Halasz, T. Masařík, B. Mohar, and R. Šámal.  Random 2-cell embeddings of multistars.  Proc. Amer. Math. Soc., 2022.
  * [CMS12] R. Cori, M. Marcus, and G. Schaeffer.  Odd permutations are nicer than even ones.  European Journal of Combinatorics, 33(7):1467–1478, 2012.
  * [CP16] S. Chmutov and B. Pittel.  On a surface formed by randomly gluing together polygonal discs.  Adv. in Appl. Math., 73:23–42, 2016.
  * [Gam06] A. Gamburd.  Poisson–dirichlet distribution for random belyi surfaces.  The Annals of Probability, 34(5):1827–1848, 2006.
  * [GJ92] I. P. Goulden and D. M. Jackson.  The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group.  European J. Combin., 13(5):357–365, 1992.
  * [GS98] A. Goupil and G. Schaeffer.  Factoring n-cycles and counting maps of given genus.  European J. Combin., 19(7):819–834, 1998.
  * [Jac94] D. M. Jackson.  On an integral representation for the genus series for $2$-cell embeddings.  Trans. Amer. Math. Soc., 344(2):755–772, 1994.
  * [LS08] M. Larsen and A. Shalev.  Characters of symmetric groups: sharp bounds and applications.  Invent. Math., 174(3):645–687, 2008.
  * [PS06] N. Pippenger and K. Schleich.  Topological characteristics of random triangulated surfaces.  Random Structures Algorithms, 28(3):247–288, 2006.
  * [Sta11] R. P. Stanley.  Two enumerative results on cycles of permutations.  European J. Combin., 32(6):937–943, 2011.


# This is the title

C*-ALGEBRAIC CASAS-ALVERO CONJECTURE
K. MAHESH KRISHNA

Post Doctoral Fellow

Statistics and Mathematics Unit

Indian Statistical Institute, Bangalore Centre

Karnataka 560 059 India

Email<EMAIL_ADDRESS>
Date:

Abstract: Based on Casas-Alvero conjecture [J. Algebra, 2001] we formulate the
following conjecture.
C*-algebraic Casas-Alvero Conjecture : Let $\mathcal{A}$ be a commutative
C*-algebra, $n\in\mathbb{N}$ and let
$P(z)\coloneqq(z-a_{1})(z-a_{2})\cdots(z-a_{n})$ be a polynomial over
$\mathcal{A}$ with $a_{1},a_{2},\dots,a_{n}\in\mathcal{A}$. If there exists an
element $b\in\mathcal{A}$ such that
$P(b)=P^{\prime}(b)=P^{{}^{\prime\prime}}(b)=\cdots=P^{(n-1)}(b)=0$, then
$P(z)=(z-c)^{n}$ on $\mathcal{A}$ for some $c\in\mathcal{A}$.
We show that C*-algebraic Casas-Alvero Conjecture holds for C*-algebraic
polynomials of degree 2.
Keywords: C*-algebra, Casas-Alvero Conjecture.
Mathematics Subject Classification (2020): 46L05, 30C10.

###### Contents

  1. 1 Introduction
  2. 2 C*-algebraic Casas-Alvero conjecture

##  1\. Introduction

In 2001, Prof. Eduardo Casas-Alvero made the following conjecture [1].

######  Conjecture 1.1.

[1, 5, 11] (Casas-Alvero Conjecture) If a complex monic polynomial of degree
$n$ shares a common zero with each of its (first) $n-1$ derivatives, then it
is $n^{\text{th}}$ power of a linear monic polynomial.

Conjecture 1.1 also appears as Problem 30 in the list of 33 problems Some open
problems in low dimensional dynamical systems by Gasull [6].

In 2011, using Gauss-Lucas theorem, Draisma and Jong proved that Conjecture
1.1 holds for polynomials of degree upto 4 [5]. In 2006, using MAPLE,
Diaz–Toca and Gonzalez–Vega verified Conjecture 1.1 for all polynomials of
degree upto 7 [4]. In 2007, Graf von Bothmer, Labs, Schicho and van de
Woestijne proved that Conjecture 1.1 holds for polynomials of degree of the
form $p^{k}$ or $2p^{k}$, where $p$ is a prime and $k$ is a natural number
[7]. In 2014, Yakubovich proved that Conjecture 1.1 holds for polynomial with
only real roots satisfying some conditions [13, 12]. In 2014, Castryck,
Laterveer and Ounaies proved that Conjecture 1.1 holds for polynomials of
degree 12 [2]. In 2020, Cima, Gasull and Manosas showed that two conjectures
similar to Conjecture 1.1 for smooth functions fail [3]. In this paper we
formulate Conjecture 1.1 for polynomials over C*-algebras. We show that
conjecture holds for second degree polynomials over C*-algebras.

##  2\. C*-algebraic Casas-Alvero conjecture

Let $\mathcal{A}$ be a C*-algebra. For
$P(z)\coloneqq(z-a_{1})(z-a_{2})\cdots(z-a_{n})$ for all $z\in\mathcal{A}$
with $a_{1},a_{2},\dots,a_{n}\in\mathcal{A}$, we define

$\displaystyle
P^{\prime}(z)\coloneqq\sum_{j=1}^{n}(z-a_{1})\cdots\widehat{(z-a_{j})}\cdots(z-a_{n}),\quad\forall
z\in\mathcal{A}$

where the term with cap is missing. We can merely formulate the C*-algebraic
version of Casas-Alvero conjecture as follows.

######  Conjecture 2.1.

(C*-algebraic Casas-Alvero Conjecture) Let $\mathcal{A}$ be a commutative
C*-algebra, $n\in\mathbb{N}$ and let
$P(z)\coloneqq(z-a_{1})(z-a_{2})\cdots(z-a_{n})$ be a polynomial over
$\mathcal{A}$ with $a_{1},a_{2},\dots,a_{n}\in\mathcal{A}$. If there exists an
element $b\in\mathcal{A}$ such that
$P(b)=P^{\prime}(b)=P^{{}^{\prime\prime}}(b)=\cdots=P^{(n-1)}(b)=0$, then
$P(z)=(z-c)^{n}$ on $\mathcal{A}$ for some $c\in\mathcal{A}$.

######  Theorem 2.2.

Conjecture 2.1 holds for C*-algebraic polynomials of degree 2.

###### Proof.

Let $\mathcal{A}$ be a commutative C*-algebra and let
$P(z)\coloneqq(z-a)(z-b)$, $a,b\in\mathcal{A}$. Assume that there is an
element $c\in\mathcal{A}$ such that $P(c)=P^{\prime}(c)=0$. Then

$\displaystyle(c-a)(c-b)=0=2c-a-b\implies c=\frac{a+b}{2}$
$\displaystyle\implies\left(\frac{a+b}{2}-a\right)\left(\frac{a+b}{2}-b\right)=0\implies(b-a)^{2}=0.$

By Gelfand-Naimark theorem $a$ and $b$ can be regarded as a complex valued
functions. Therefore $a-b=0$ which gives $a=b$. ∎

######  Remark 2.3.

  1. (i)

C*-algebraic Sendov conjecture has been formulated in [8].

  2. (ii)

C*-algebraic Schoenberg conjecture has been formulated in [9].

  3. (iii)

C*-algebraic Smale mean value conjecture and Dubinin-Sugawa dual mean value
conjecture have been formulated in [10].

## References

  * [1] Eduardo Casas-Alvero.  Higher order polar germs.  J. Algebra, 240(1):326–337, 2001.
  * [2] Wouter Castryck, Robert Laterveer, and Myriam Ounaies.  Constraints on counterexamples to the Casas-Alvero conjecture and a verification in degree 12.  Math. Comp., 83(290):3017–3037, 2014.
  * [3] A. Cima, A. Gasull, and F. Manosas.  Around some extensions of Casas-Alvero conjecture for non-polynomial functions.  Extracta Math., 35(2):221–228, 2020.
  * [4] Gema M. Diaz–Toca and Laureano Gonzalez–Vega.  On analyzing a conjecture about univariate polynomials and their roots by using Maple.  Proceedings of the Maple Conference 2006, Waterloo (Canada), July 23–26, pages 81–98, 2006.
  * [5] Jan Draisma and Johan P. de Jong.  On the Casas-Alvero conjecture.  Eur. Math. Soc. Newsl., (80):29–33, 2011.
  * [6] A Gasull.  Some open problems in low dimensional dynamical systems.  SeMA Journal, 78(3):233–269, 2021.
  * [7] Hans-Christian Graf von Bothmer, Oliver Labs, Josef Schicho, and Christiaan van de Woestijne.  The Casas-Alvero conjecture for infinitely many degrees.  J. Algebra, 316(1):224–230, 2007.
  * [8] K. Mahesh Krishna.  C*-algebraic Gauss-Lucas theorem and C*-algebraic Sendov’s conjecture.  arXiv:2203.06916v1 [math.OA] 14 March, 2022.
  * [9] K. Mahesh Krishna.  C*-algebraic Schoenberg conjecture.  arXiv:2206.06653v1 [math.OA] 14 June, 2022.
  * [10] K. Mahesh Krishna.  C*-algebraic Smale mean value conjecture and Dubinin-Sugawa dual mean value conjecture.  arXiv:2206.08154v1 [math.FA] 16 June, 2022.
  * [11] Thomas Polstra.  Convex hulls and the Casas-Alvero conjecture for the complex plane.  Rose-Hulman Undergrad. Math. J., 13(1):33–42, 2012.
  * [12] S. Yakubovich.  Polynomial problems of the Casas-Alvero type.  J. Class. Anal., 4(2):97–120, 2014.
  * [13] S. Yakubovich.  On some properties of the Abel-Goncharov polynomials and the Casas-Alvero problem.  Integral Transforms Spec. Funct., 27(8):599–610, 2016.