of these operations are available in standard sources (e.g. [63] [64]). A key
step in the formula is the sum over $k_{i}$. This complexity question suggests
two interesting mathematical problems about partitions.
Problem 1: Given the sequence of positive integers $n$, consider the
partitions $p$ of $n$ in the presentation as distinct positive parts with
their positive multiplicities $p=[c_{1}^{m_{1}},c_{2}^{m_{2}}\cdots
c_{S}^{m_{S}}]$, where $\sum_{i=1}^{S}c_{i}m_{i}=n$, the function
$f(p,n)=\prod_{i=1}^{S}m_{i}$, and the function $\tilde{f}(n)={\rm
Max}_{p\vdash n}(f(p,n))$. Describe the asymptotic growth of $\tilde{f}(n)$ at
large $n$.

Problem 2: Given the sequence of positive integers $n$, consider the
partitions $p$ of $n$ in the presentation as distinct positive parts with
their positive multiplicities $p=[c_{1}^{m_{1}},c_{2}^{m_{2}}\cdots
c_{S}^{m_{S}}]$, where $\sum_{i=1}^{S}c_{i}m_{i}=n$, the function
$g(p,n)=\prod_{i=1}^{S}\lfloor{m_{i}/2}\rfloor$, and the function
$\tilde{g}(n)={\rm Max}_{p\vdash n}(g(p,n))$. Describe the asymptotic growth
of $\tilde{g}(n)$ at large $n$.

The second problem is more directly relevant to the calculation of the
complexity desired, but the the first is closely related and plausibly has a
similar asymptotic behaviour at large $n$. These sequences are easily explored
using Mathematica for values of $n$ up to $60$. Generating functions for the
sums over partitions of the products of multiplicities have been considered by
MacMahon [65] and may perhaps be adapted to give the Max functions involved in
the above problems.

###  6.4 Counting $C_{\mu\lambda}^{\;\;\;\mu}$

The previous developments demonstrates that we can access
$C_{\mu\lambda}^{\;\;\;\mu}$ for general $\lambda$ and some $\mu$,
independently of knowing their sum over $\mu$. It is, indeed, a problem on its
own to evaluate $C_{\mu\lambda}^{\;\;\;\mu}$. This problem has applications
such as counting ribbon graphs with certain properties.

For an integer $n$, a generic partition
$\lambda=[c^{m_{1}}_{1},c^{m_{2}}_{2},\dots,c^{m_{L+N}}_{L+N}]\vdash n$, and
$\mu_{\ell}\vdash n$ such that

$\displaystyle\displaystyle\mu_{\ell}=[2^{\frac{1}{2}(n-({\cal P}+{\cal
Q}))+\ell},1^{{\cal P}+{\cal Q}-2\ell}]$ (6.183)

using previous notation, we have given in (6.182) an expression for
$C_{\mu_{\ell}\lambda}^{\;\;\;\mu_{\ell}}$ for $\ell\in[\\![0,\widetilde{\cal
P}+\widetilde{\cal Q}]\\!]$. We can thus provide a table of the values of
$C_{\mu_{\ell}\lambda}^{\;\;\;\mu_{\ell}}$. For a few values of
$n\in\\{1,2,\dots,6\\}$, this is recorded in Table 3. One checks that the sum
of $C_{\mu_{\ell}\lambda}^{\;\;\;\mu_{\ell}}$ over the $\ell$’s within a
sector corresponding to the same $\lambda$ returns the right output. This has
to be compared with the corresponding row labeled by $\lambda$ in Table 4.

$n$ | $\lambda$ | $\mu$ | $C_{\mu\lambda}^{\;\;\;\mu}$
---|---|---|---
1 | $[1]$ | $[1]$ | 1
2 | $[1^{2}]$ | $[1^{2}]$ | 1
|  | $[2]$ | 1
3 | $[3]$ | $[2,1]$ | 2
| $[1^{3}]$ | $[1^{3}]$ | 1
| $[1^{3}]$ | $[2,1]$ | 1
4 | $[3,1]$ | $[2,1^{2}]$ | 4
| $[2^{2}]$ | $[2,1^{2}]$ | 1
| $[2^{2}]$ | $[2^{2}]$ | 2
| $[1^{4}]$ | $[1^{4}]$ | 1
| $[1^{4}]$ | $[2,1^{2}]$ | 1
| $[1^{4}]$ | $[2^{2}]$ | 1
5 | $[3,1^{2}]$ | $[2,1^{3}]$ | 6
| $[3,1^{2}]$ | $[2^{2},1]$ | 4
| $[2^{2},1]$ | $[2,1^{3}]$ | 3
| $[2^{2},1]$ | $[2^{2},1]$ | 2
| $[1^{5}]$ | $[1^{5}]$ | 1
| $[1^{5}]$ | $[2,1^{3}]$ | 1
| $[1^{5}]$ | $[2^{2},1]$ | 1
6 | $[3^{2}]$ | $[2^{2},1^{2}]$ | 8
| $[3^{2}]$ | $[2^{3}]$ | 8
| $[3,1^{3}]$ | $[2,1^{4}]$ | 8
| $[3,1^{3}]$ | $[2^{2},1^{2}]$ | 8
| $[2^{2},1^{2}]$ | $[2,1^{4}]$ | 6
| $[2^{2},1^{2}]$ | $[2^{2},1^{2}]$ | 4
| $[2^{2},1^{2}]$ | $[2^{3}]$ | 6
| $[1^{6}]$ | $[1^{6}]$ | 1
| $[1^{6}]$ | $[2,1^{4}]$ | 1
| $[1^{6}]$ | $[2^{2},1^{2}]$ | 1
| $[1^{6}]$ | $[2^{3}]$ | 1
Table 3: Evaluation of $C_{\mu\lambda}^{\;\;\;\mu}$ for
$\lambda=[3^{*},2^{*},1^{*}]\vdash n$, $n\in\\{1,2,\dots,6\\}$.

##  7 Bounds for disjoint unions of partitions

Consider a partition $\lambda$ of $n$, which takes the form
$\lambda^{(1)}\sqcup\lambda^{(2)}$ where $\lambda^{(1)}\vdash
n_{1},\lambda^{(2)}\vdash n_{2}$ and $n_{1}+n_{2}=n$. For example if
$\lambda=[4,3,2,2]\vdash n=11$ we can write

$\displaystyle\lambda=[4]\circ[3,2,2]\;,\;\;\qquad{[4]\vdash
n_{1}=4;\;\;[3,2,2]\vdash n_{2}=7}$ (7.1)
$\displaystyle\lambda=[4,3]\circ[2,2]\;,\;\;\qquad{[4,3]\vdash
n^{\prime}_{1}=7;\;\;[2,2]\vdash n^{\prime}_{2}=4}$ (7.2)
$\displaystyle{\lambda=[4,2]\circ[3,2]\;,\;\;\qquad[4,2]\vdash
n^{\prime\prime}_{1}=6;\;\;[3,2]\vdash n^{\prime\prime}_{2}=5}$ (7.3)

These are just three of several possibilities.

The sum of normalised characters is

$\displaystyle\displaystyle
G_{\lambda}\equiv\sum_{R}{\chi^{R}(T_{\lambda})\over d_{R}}=\sum_{\mu\vdash
n}{\;{|{\cal C}_{\lambda}|\over|{\cal
C}_{\mu}|}}\delta(T_{\mu}T_{\mu}\sigma_{3}^{*})$ (7.4)

where $\sigma_{3}^{*}$ is any chosen permutation in the class $\lambda$.
Picking a decomposition $\lambda=\lambda^{(1)}\sqcup\lambda^{(2)}$, with
$\lambda^{(1)}\vdash n_{1},\lambda^{(2)}\vdash n_{2}$, we also pick a
homomorphism $S_{n_{1}}\times S_{n_{2}}\rightarrow S_{n_{1}+n_{2}}$ by letting
$S_{n_{1}}$ act on $\\{1,\cdots,n_{1}\\}$ while $S_{n_{2}}$ acts on
$\\{n_{1}+1,\cdots,n_{1}+n_{2}\\}$. We then pick a permutation in the
conjugacy class $\lambda$ of the form
$\sigma_{3}^{*}=\sigma_{3}^{*(1)}\circ\sigma_{3}^{*(2)}$, where
$\sigma_{3}^{*(1)}$ belongs to conjugacy class ${\cal C}_{\lambda^{(1)}}$ and
$\sigma_{3}^{*(2)}$ belongs to ${\cal C}_{\lambda^{(2)}}$.

The quantity $\delta(T_{\mu}T_{\mu}\sigma_{3}^{*})$ will contain contributions
where $\mu$ splits into the form $\mu=\mu^{(1)}\sqcup\mu^{(2)}$ with
$\mu^{(1)}\vdash n_{1},\mu^{(2)}\vdash n_{2}$. Hence,

$\displaystyle\displaystyle G_{\lambda}\geq\sum_{\mu^{(1)}\vdash
n_{1}}\sum_{\mu^{(2)}\vdash n_{2}}{{|{\cal
C}_{\lambda^{(1)}\circ\lambda^{(2)}}|\over|{\cal
C}_{\mu^{(1)}\circ\mu^{(2)}}|}}\delta(T_{\mu^{(1)}\circ\mu^{(2)}}T_{\mu^{(1)}\circ\mu^{(2)}}\sigma_{3}^{*})\equiv
G_{{\rm{factored}}}$ (7.5)

In fact, as ${\cal C}_{\mu^{(1)}\circ\mu^{(2)}}\neq{\cal
C}_{\mu^{(1)}}\circ{\cal C}_{\mu^{(2)}}\subset S_{n_{1}}\times S_{n_{2}}$, we
have $T_{\mu^{(1)}\circ\mu^{(2)}}\neq T_{\mu^{(1)}}\circ T_{\mu^{(2)}}$, where
we extend $\circ$ to the group algebra. We have instead the following
equality:

$\displaystyle\displaystyle\delta(T_{\mu^{(1)}\circ\mu^{(2)}}T_{\mu^{(1)}\circ\mu^{(2)}}\sigma_{3}^{*})=\delta(T_{\mu^{(1)}}T_{\mu^{(1)}}\sigma_{3}^{*(1)})\delta(T_{\mu^{(2)}}T_{\mu^{(2)}}\sigma_{3}^{*(2)})$
(7.6)

Let us assume that some $\sigma_{1},\sigma_{2}\in{\cal
C}_{\mu^{(1)}\circ\mu^{(2)}}$ obeys $\sigma_{1}\sigma_{2}\sigma_{3}^{*}=\rm
id$. Then, we have $\sigma_{1}\sigma_{2}\sigma_{3}^{*}$
$=\sigma_{1}\sigma_{2}(\sigma_{3}^{*(1)}\circ\sigma_{3}^{*(2)})=\rm id$, and
moreover there exist some
$\sigma_{i}^{*(1)}\circ\sigma_{i}^{*(2)}=\sigma_{i}$, $i=1,2$, where
$\sigma_{i}^{*(1)}\in{\cal C}_{\mu^{(1)}}$ and $\sigma_{i}^{*(2)}\in{\cal
C}_{\mu^{(2)}}$. Thus

$\displaystyle\displaystyle(\sigma_{1}^{*(1)}\circ\sigma_{1}^{*(2)})(\sigma_{2}^{*(1)}\circ\sigma_{2}^{*(2)})(\sigma_{3}^{*(1)}\circ\sigma_{3}^{*(2)})=(\sigma_{1}^{*(1)}\sigma_{2}^{*(1)}\sigma_{3}^{*(1)})\circ(\sigma_{1}^{*(2)}\sigma_{2}^{*(2)}\sigma_{3}^{*(2)})=\rm
id$ (7.7)

which requires each factor to be the identity on each subgroup $S_{n_{1}}$ or
$S_{n_{2}}$.

The converse is clearly true: if the product
$\delta(T_{\mu^{(1)}}T_{\mu^{(1)}}\sigma_{3}^{*(1)})\delta(T_{\mu^{(2)}}T_{\mu^{(2)}}\sigma_{3}^{*(2)})=1$,
then we can easily construct two $\sigma_{1},\sigma_{2}\in{\cal
C}_{\mu^{(1)}\circ\mu^{(2)}}$ which obeys
$\sigma_{1}\sigma_{2}\sigma_{3}^{*}=\rm id$, by collecting two permutations in
the class ${\cal C}_{\mu^{(1)}}$ and two permutations in ${\cal
C}_{\mu^{(2)}}$ and pair them to produce $\sigma_{1}$ and $\sigma_{2}$.

Now note that

$\displaystyle G_{{\rm{factored}}}=\sum_{\mu^{(1)}\vdash
n_{1}}\sum_{\mu^{(2)}\vdash n_{2}}{{|{\cal
C}_{\lambda^{(1)}\circ\lambda^{(2)}}|\over|{\cal
C}_{\mu^{(1)}\circ\mu^{(2)}}|}}\delta(T_{\mu^{(1)}}T_{\mu^{(1)}}\sigma_{3}^{*(1)})\delta(T_{\mu^{(2)}}T_{\mu^{(2)}}\sigma_{3}^{*(2)})$
(7.8) (7.9) $\displaystyle=\sum_{\mu^{(1)}\vdash n_{1}}\sum_{\mu^{(2)}\vdash
n_{2}}{{|{\cal C}_{\lambda^{(1)}\circ\lambda^{(2)}}|\over|{\cal
C}_{\mu^{(1)}\circ\mu^{(2)}}|}{|{\cal C}_{\mu^{(1)}}||{\cal
C}_{\mu^{(2)}}|\over|{\cal C}_{\lambda^{(1)}}||{\cal C}_{\lambda^{(2)}}|}}$
(7.10) (7.11) $\displaystyle\qquad\qquad\times{|{\cal
C}_{\lambda^{(1)}}|\over|{\cal
C}_{\mu^{(1)}}|}\delta(T_{\mu^{(1)}}T_{\mu^{(1)}}\sigma_{3}^{*(1)}){|{\cal
C}_{\lambda^{(2)}}|\over|{\cal
C}_{\mu^{(2)}}|}\delta(T_{\mu^{(2)}}T_{\mu^{(2)}}\sigma_{3}^{*(2)})$ (7.12)
$\displaystyle={|{\rm Aut}^{(n_{1})}(\lambda^{(1)})||{\rm
Aut}^{(n_{2})}(\lambda^{(2)})|\over|{\rm
Aut}^{(n)}(\lambda^{(1)}\circ\lambda^{(2)})|}\sum_{\mu^{(1)}\vdash
n_{1}}\sum_{\mu^{(2)}\vdash n_{2}}{|{\rm
Aut}^{(n)}(\mu^{(1)}\circ\mu^{(2)})|\over|{\rm Aut}^{(n_{1})}(\mu^{(1)})||{\rm
Aut}^{(n_{2})}(\mu^{(2)})|}$ (7.13) (7.14)
$\displaystyle\qquad\qquad\times{|{\cal C}_{\lambda^{(1)}}|\over|{\cal
C}_{\mu^{(1)}}|}\delta(T_{\mu^{(1)}}T_{\mu^{(1)}}\sigma_{3}^{*(1)}){|{\cal
C}_{\lambda^{(2)}}|\over|{\cal
C}_{\mu^{(2)}}|}\delta(T_{\mu^{(2)}}T_{\mu^{(2)}}\sigma_{3}^{*(2)})$ (7.15)

where we used the orbit stabilizer theorem to express the sizes of the
conjugacy classes in terms of the order of the automorphism groups. In
particular, we introduce the notation:

$\displaystyle|{\cal C}_{\rho^{(i)}}|=n!/|{\rm
Aut}^{(n_{i})}(\rho^{(i)})|\;,\qquad\rho=\lambda,\mu\;,i=1,2$ (7.16)
$\displaystyle|{\cal C}_{\rho^{(1)}\circ\rho^{(2)}}|=n!/|{\rm
Aut}^{(n)}(\rho^{(1)}\circ\rho^{(2)})|\;,\quad\rho=\lambda,\mu$ (7.17)

Now observe that

$\displaystyle\displaystyle{|{\rm
Aut}^{(n)}(\mu^{(1)}\circ\mu^{(2)})|\over|{\rm Aut}^{(n_{1})}(\mu^{(1)})||{\rm
Aut}^{(n_{2})}(\mu^{(2)})|}\geq 1$ (7.18)

This means

$\displaystyle\displaystyle G_{{\rm{factored}}}$ $\displaystyle\geq$
$\displaystyle{|{\rm Aut}^{(n_{1})}(\lambda^{(1)})||{\rm
Aut}^{(n_{2})}(\lambda^{(2)})|\over|{\rm
Aut}^{(n)}(\lambda^{(1)}\circ\lambda^{(2)})|}$ (7.19) $\displaystyle\times$
$\displaystyle\sum_{\mu^{(1)}\vdash n_{1}}\sum_{\mu^{(2)}\vdash n_{2}}{|{\cal
C}_{\lambda^{(1)}}|\over|{\cal
C}_{\mu^{(1)}}|}\delta(T_{\mu^{(1)}}T_{\mu^{(1)}}\sigma_{3}^{*(1)}){|{\cal
C}_{\lambda^{(2)}}|\over|{\cal
C}_{\mu^{(2)}}|}\delta(T_{\mu^{(2)}}T_{\mu^{(2)}}\sigma_{3}^{*(2)})$ (7.21)

Equivalently

$\displaystyle\displaystyle G_{{\rm{factored}}}\geq{|{\rm
Aut}^{(n_{1})}(\lambda^{(1)})||{\rm Aut}^{(n_{2})}(\lambda^{(2)})|\over|{\rm
Aut}^{(n)}(\lambda^{(1)}\circ\lambda^{(2)})|}G_{\lambda^{(1)}}G_{\lambda^{(2)}}$
(7.22)

and we conclude

$\displaystyle\displaystyle G_{\lambda}\geq{|{\rm
Aut}^{(n_{1})}(\lambda^{(1)})||{\rm Aut}^{(n_{2})}(\lambda^{(2)})|\over|{\rm
Aut}^{(n)}(\lambda^{(1)}\circ\lambda^{(2)})|}G_{\lambda^{(1)}}G_{\lambda^{(2)}}$
(7.23)

So we have a lower bound on the column sum of normalised characters for any
conjugacy class $\lambda$ associated with any disjoint decomposition of
$\lambda=\lambda^{(1)}\sqcup\lambda^{(2)}$.

We define

$\displaystyle\displaystyle F_{\lambda}=|{\rm Aut}(\lambda)|G_{\lambda}$
(7.24)

and express the disjoint union as a sum of partitions,
$\lambda^{(1)}\sqcup\lambda^{(2)}\equiv\lambda^{(1)}+\lambda^{(2)}$.Note that

$\displaystyle\displaystyle F_{\lambda}=|{\rm Aut}(\lambda)||{\cal
C}_{\lambda}|\sum_{R}{\chi^{R}_{\lambda}\over
d_{R}}=n!\sum_{R}{\chi^{R}_{\lambda}\over d_{R}}$ (7.25)

We will refer to $F_{\lambda}$ the column sum of normalised characters.

The inequality (7.23) thus proves:

######  Theorem 11.

$\displaystyle\displaystyle F_{\lambda^{(1)}+\lambda^{(2)}}\geq
F_{\lambda^{(1)}}F_{\lambda^{(2)}}$ (7.26)

As a direct corollary, we also obtain:

$\displaystyle\displaystyle\log(F_{\lambda^{(1)}+\lambda^{(2)}})\geq\log(F_{\lambda^{(1)}})+\log(F_{\lambda^{(2)}})$
(7.27)

In other words, the logarithm of the sum of normalised characters is super-
additive. We are using the disjoint union to define an addition on partitions.
Super-additivity and associated theorems are discussed, for example in [66].

##  8  Discussion and outlook

In this paper, we have studied properties of the column sum of normalized
central characters, $\sum_{R\vdash n}\chi^{R}(T_{\lambda})/d_{R}$, where
$T_{\lambda}$ denotes the sum of elements in the conjugacy class ${\cal
C}_{\lambda}$ of the symmetric group, and the sum is over irreducible
representations $R$. A summary of our main results is included in the
introduction. We will here make general remarks and discuss some future
directions following from this work.

The starting point of our investigations has been the expression of the column
sum of normalised central characters in terms of a sum over structure
constants of multiplication in the centre of the group algebra of $S_{n}$
(Proposition 1). This lends itself to efficient computational algorithms and
combinatorial interpretations. A combinatorial interpretation of geometrical
nature involves the expression of the column sum as a sum over bi-partite
ribbon graphs with face structure determined by $\lambda$. These graphs appear
with a weight equal to an integer ratio of orders of automorphism groups, one
group for the symmetry of some vertices and another group for the symmetry of
the graph (Theorem 4). It is interesting to note that bi-partite ribbon graphs
appear summed, with slightly different weights, in other physical
applications. In the computation of matrix model correlators, they appear
weighted by the inverse of the automorphism group of the graph. In tensor
models, they appear with weight one in the enumeration of tensor model
observables. In the context of matrix model correlators, interesting
generating functions for correlators can sometimes be written explicitly, form
special functions of interest in string theory, and relate to the phenomenon
of super-integrability [67][68][69]. It will be interesting to consider
generating functions for bi-partite graph counting, with weights of the kind
that have appeared here.

In deriving the lower bounds for the column sums (6.182), we have obtained the
counting of bi-partite ribbon graphs with face structure $\lambda$, and vertex
structures for black vertices and white vertices given by partition $\mu$,
where $\mu=[2^{*},1^{*}]$. The techniques we used should also allow results
for the case where the black and white vertex types are given by partitions
$\mu,\nu$, not necessarily equal but both of type $[2^{*},1^{*}]$. Further
generalisation to $\mu,\nu$ belonging to conjugacy classes of type
$[s^{k_{s}},\cdots,3^{k_{3}},2^{*},1^{*}]$ for small $s$ and small
$k_{3},\cdots,k_{s}$ should be possible, using perturbative techniques from
matrix models. These bi-partite graph counting problems are special cases of
Hurwitz counting of branched covers [48], which are of broad and current
interest, e.g. [50, 51], in combinatorics.

Having established that the function computing the column sum of central
normalized characters belongs to #P (as well as the stronger result that the
decision problem is in class P), the ensuing natural question is whether it is
#P -hard (and so #P -complete). Given that we have expressed this function
in terms of the enumeration of bi-partite ribbon graphs possessing a specific
structure, it seems logical to continue within the realm of graph theory,
which abounds with #P -hard and #P -complete problems. The primary
distinction between ribbon graphs and ordinary graphs lies in the symmetry:
the cyclic symmetry $\mathbb{Z}_{k}$ at a $k$-valent vertex in ribbon graphs
is substituted by a local $S_{k}$ symmetry in ordinary graphs. Nevertheless,
permutations and their associated double cosets offer a unified description
for both graph types [70]. This could be instrumental as part of the strategy
to prove the #P -hardness of problems related to both ordinary and ribbon
graphs. The crucial step involves devising a polynomial reduction of a
recognized #P -hard problem in ordinary graph theory to the enumeration of
bi-partite ribbon graphs arising in the column sum problem.

Acknowledgements. JBG thanks Christophe Tollu for insightful discussions on
complexity theory. We also thank Anirban Chowdhury, Robert de Mello Koch,
Charles Nash, Denjoe O’ Connor, Yang-Hui He for useful discussions. SR is
supported by the Science and Technology Facilities Council (STFC) Consolidated
Grants ST/P000754/1 “String theory, gauge theory and duality” and ST/T000686/1
“Amplitudes, strings and duality” and a Visiting Professorship at the Dublin
Institute for Advanced Studies.

## Appendix

##  Appendix A Proof of Proposition 1

Our goal is to show that, for any $\lambda\vdash n$,

$\displaystyle\displaystyle\sum_{\mu\vdash
n}C_{\mu\lambda}^{\;\;\;\mu}=\sum_{R\vdash n}{\chi^{R}(T_{\lambda})\over
d_{R}}$ (A.1)

Start by (2.8) and multiply it by $T_{\lambda}$:

$\displaystyle\displaystyle T_{\mu}T_{\nu}T_{\lambda}=\sum_{\rho\vdash
n}C_{\mu\nu}^{\;\;\;\rho}T_{\rho}T_{\lambda}$ (A.2)

We define the Kronecker delta function on the symmetric group as
$\delta:S_{n}\to\mathbb{R}$, $\delta(\sigma)=1$, if $\sigma=\rm id$ and 0
otherwise, and extend $\delta$ by linearity over the group algebra
${\mathbb{C}}(S_{n})$ of $S_{n}$. We evaluate the previous equation:

$\displaystyle\displaystyle\delta(T_{\mu}T_{\nu}T_{\lambda})=\sum_{\rho\vdash
n}C_{\mu\nu}^{\;\;\;\rho}\delta(T_{\rho}T_{\lambda})=\sum_{\rho\vdash
n}C_{\mu\nu}^{\;\;\;\rho}\sum_{\sigma\in{\cal C}_{\rho},\tau\in{\cal
C}_{\lambda}}\delta(\sigma\tau)$ (A.3)

Using the fact that a permutation and its inverse belong to the same conjugacy
class, we infer $[\sigma]=\rho=[\tau^{-1}]=\lambda$ and deduce:

$\displaystyle\displaystyle\delta(T_{\mu}T_{\nu}T_{\lambda})=\sum_{\rho\vdash
n}C_{\mu\nu}^{\;\;\;\rho}|{\cal C}_{\lambda}|\delta_{\rho\lambda}=|{\cal
C}_{\lambda}|C_{\mu\nu}^{\;\;\;\lambda}$ (A.4)

where in the last expression, $\delta_{\rho\lambda}$ is a Kronecker delta on
partitions. It gives 1 if two partitions are equal i.e. they have the same
parts (each part in same number), and gives 0 otherwise. Thus, we have an
expression of the structure constant

$\displaystyle\displaystyle
C_{\mu\nu}^{\;\;\;\lambda}=\delta(T_{\mu}T_{\nu}T_{\lambda})/|{\cal
C}_{\lambda}|.$ (A.5)

Defining $C_{\mu\nu\lambda}:=\delta(T_{\mu}T_{\nu}T_{\lambda})$, we have the
following identities

$\displaystyle C_{\mu\nu\lambda}=C_{\mu\nu}^{\;\;\;\lambda}|{\cal
C}_{\lambda}|\,,\qquad\qquad
C_{\mu\nu\lambda}=C_{\nu\lambda\mu}=C_{\lambda\mu\nu}$ (A.6) (A.7)
$\displaystyle C_{\nu\lambda\mu}=C_{\nu\lambda}^{\;\;\;\mu}|{\cal
C}_{\mu}|=C_{\mu\nu\lambda}=C_{\mu\nu}^{\;\;\;\lambda}|{\cal C}_{\lambda}|$
(A.8) (A.9) $\displaystyle
C_{\nu\lambda}^{\;\;\;\mu}=C_{\mu\nu}^{\;\;\;\lambda}\frac{|{\cal
C}_{\lambda}|}{|{\cal C}_{\nu}|}$ (A.10)

This shows that $C_{\nu\lambda}^{\;\;\;\mu}$ is proportional to
$C_{\mu\nu}^{\;\;\;\lambda}$.

Using the expansion in representation of the Kronecker delta function in terms
of characters:

$\delta(\sigma)=\sum_{R\vdash n}\frac{d_{R}}{n!}\,\chi^{R}(\sigma)$ (A.11)

we expand the left-hand side of (A.1):

$\displaystyle\displaystyle\sum_{\mu\vdash
n}C_{\mu\lambda}^{\;\;\;\mu}=\sum_{\mu\vdash n}{1\over|{\cal
C}_{\mu}|}\delta(T_{\mu}T_{\lambda}T_{\mu})=\sum_{\mu\vdash n}{1\over|{\cal
C}_{\mu}|}\sum_{R\vdash
n}\frac{d_{R}}{n!}\,\chi^{R}(T_{\mu}T_{\lambda}T_{\mu})$ (A.12)

There is a crucial property of the characters: If $B$ is a central element,
then for any $A$

$\chi^{R}(AB)={1\over d_{R}}\chi^{R}(A)\chi^{R}(B)$ (A.13)

Then, another expression of (A.12) is

$\displaystyle\sum_{\mu\vdash n}C_{\mu\lambda}^{\;\;\;\mu}=\sum_{\mu\vdash
n}{1\over|{\cal C}_{\mu}|}\sum_{R\vdash n}\frac{d_{R}}{n!}\,{1\over
d_{R}}\chi^{R}(T_{\mu}T_{\mu})\chi^{R}(T_{\lambda})$ (A.14)
$\displaystyle=\sum_{R\vdash n}\left[\frac{d_{R}}{n!}\,\sum_{\mu\vdash
n}{1\over|{\cal
C}_{\mu}|}\chi^{R}(T_{\mu}T_{\mu})\right]\widehat{\chi}^{R}(T_{\lambda})$
(A.15)

The following lemma ends the proof:

######  Lemma 5.

$\displaystyle\displaystyle\frac{d_{R}}{n!}\sum_{\mu\vdash n}{1\over|{\cal
C}_{\mu}|}\chi^{R}(T_{\mu}T_{\mu})=1$ (A.16)

###### Proof.

We use again the relation (A.13) for writing:

$\displaystyle\displaystyle\frac{d_{R}}{n!}\sum_{\mu\vdash n}{1\over|{\cal
C}_{\mu}|}\chi^{R}(T_{\mu}T_{\mu})=\frac{1}{n!}\sum_{\mu\vdash n}{1\over|{\cal
C}_{\mu}|}\chi^{R}(T_{\mu})\chi^{R}(T_{\mu})=\frac{1}{n!}\sum_{\mu\vdash
n}{|{\cal C}_{\mu}||{\cal C}_{\mu}|\over|{\cal
C}_{\mu}|}\chi^{R}(g_{\mu})\chi^{R}(g_{\mu})$ (A.17)

where $g_{\mu}$ is a representative of ${\cal C}_{\mu}$, which implies
$\chi^{R}(T_{\mu})=|{\cal C}_{\mu}|\chi^{R}(g_{\mu})$ . We then obtain

$\frac{d_{R}}{n!}\sum_{\mu\vdash n}{1\over|{\cal
C}_{\mu}|}\chi^{R}(T_{\mu}T_{\mu})=\frac{1}{n!}\sum_{\mu\vdash
n}\sum_{g_{\mu}\in{\cal
C}_{\mu}}\chi^{R}(g_{\mu})\chi^{R}(g_{\mu})=\frac{1}{n!}\sum_{g\in
S_{n}}\chi^{R}(g)\chi^{R}(g)=1$ (A.18)

where we use the orthogonality relation $\sum_{g\in
S_{n}}\chi^{S}(g)\chi^{R}(g)=n!\delta_{RS}$.

∎

##  Appendix B Codes

This appendix contains GAP and Sage codes for different countings discussed in
the manuscript. We use a SageMath interface to run GAP, so all codes start
with `%%gap`.

###  B.1 Counting using conjugacy classes

We deliver a code computing the integer $C_{\mu\mu\lambda}/|{\cal C}_{\mu}|$
(3.5). Comments accompany each function and explain its calculation purpose.

    %%gap
    ##  Produces the list of all terms in T_{ mu } T_{ mu }/|C_{ mu }|
    # n a positive integer
    # mu a number between 1 and the number of partitions of n
    # mu labels a conjugacy class

    partsq := function (mu , n)

        local LL, cc, Listmu, l , Grp ;

        Grp := SymmetricGroup(n) ;
        cc := ConjugacyClasses (Grp) ;
        Listmu := AsList(cc[mu]) ;   # conjugacy classes as lists
        l := Length(Listmu);        # length of Listmu
        LL := [];

        for k in [ 1 .. l ] do
            Add ( LL , Listmu[1]*Listmu[k] ) ;
            # register the product of  Listmu[1] and Listmu[k]
            # Listmu[1] is the 1st representative of T_{mu}
            # Listmu[1]* Listmu[k] computes the k-th element Listmu[1]*T_{mu}
        od;
        return LL ;
    end;

    %%gap
    # Enumerates the number of elements of the conjugacy class
    # labeled by lam in the product of T_{ mu } T_{ mu } / |C_{ mu }|
    # uses partsq ( mu , n )
    # Applies a filter to target the terms that are in the conjugacy class lam
    # n a positive integer
    # lam, mu integers labeling some conjugacy classes
    # lam, mu integers between 1 and the number of partitions of n

    Countmumulam := function ( mu , lam , n  )
        local cc , Grp ;
        Grp  := SymmetricGroup (n) ;
        cc := ConjugacyClasses (Grp) ;
        return Length ( Filtered ( partsq (mu,n) , x -> x in  AsList (cc[lam ]) ) ) ;
    end ;

Finally the following function achieves the enumeration of the number of
elements $T_{\mu}*T_{\mu}/|{\cal C}_{\mu}|$ that belong to ${\cal
C}_{\lambda}$:

    %%gap
    # n a positive integer
    # lam integer labeling a conjugacy class

    Tablam := function ( lam , n )

        local i, L, s , l ;
        L := [ ] ;
        s := 0;
        l := NrPartitions ( n );

        Print("nb part = ", l, "\n" );
        for i in [1 ..l] do
            Add ( L , [ cc [i]  , Countmumulam ( i , lam , n )] )   ;
            if Countmumulam ( i , lam , n ) > 0 then
                s := s + Countmumulam ( i , lam , n );
            fi;
        od ;

        Print("total s = ", s, "\n");
        return L ;
    end ;

    %%gap
    cc[1] ;
    Tablam ( 1 , 3);

    [out]
    ()^G
    nb part = 3
    total s = 3
    [ [ ()^G, 1 ], [ (1,2)^G, 1 ], [ (1,2,3)^G, 1 ] ]

###  B.2 Basic functions on symmetric group computations and their complexity

Computing the orbits of a permutation: This is a simple Python code for
computing the list of orbits of a given permutation.

    # Function to find a single orbit
    # visited is an array recording the visited indices
    # permut is a permutation
    # start is an index from which we start the construction of the orbit
    # Assuming: start <= degree of permut

    def find_orbit(visited, permut, start):
        orbit = []
        while not visited[start]:
            visited[start] = True
            orbit.append(start)
            start = permut[start-1]
        return orbit

    # Function which computes the set of orbits
    # of a permutation permut of n objects
    def compute_orbits(n, permut):

        # Initialize all elements as not visited
        visited = [False] * (n + 1)
        orbits = []

        # Find all orbits
        for i in range(1, n + 1):
            if not visited[i]:
                orbits.append(find_orbit(visited,permut, i))

        return orbits

    # Example:
    # Permutation must be provided as a list, e.g., [2, 3, 1, 5, 4] for n=5
    n = 5
    perm = [2, 3, 1, 5, 4]
    orbits = compute_orbits(n, perm)
    print "The orbits are:", orbits

    (out)
    The orbits are: [[1, 2, 3], [4, 5]]

Our task is to evaluate the complexity of the function `compute_orbits(n,
permut)`.

First, the complexity of `find_orbit(visited, permut, i)` is evaluated as
follows: we read, append, assign new values to $start$ until $visited[start]$
becomes $True$. To become $True$, we must reach the size $c_{i}$ of the cycle
containing $start=i$. Thus running `find_orbit` costs ${\cal
O}(|c_{i}|)\subset{\cal O}(n)$, for a given orbit of size $c_{i}$ and ignoring
the size of each input key $k_{i_{j}}$ (adding them in the end, will simply
cost another factor of $n$).

The permutation $permut$ is stored as a list of the $n$ first integers.

\- Creating the list $visited$ is an allocation followed by an append of $n$
strings $False$: this costs ${\cal O}(n)$.

\- In the loop, we append $orbits$ only if $visited[i]$ is $False$; this
occurs at most $n$ times and when a new cycle of $permut$ starts; the test “
if $visited[i]$ is $False$” cost as much as reading $i$ which is ${\cal O}(1)$
(ignoring the size of $i$). Then follows the call of `find_orbit(visited,
permut, i)` that we have already computed the complexity.

In `compute_orbits(n, permut)`, we append to the list $orbits$, the orbit
returned by `find_orbit(visited, permut, i)`. This costs the length of the
orbit appended. We finally obtain, after summing over all orbit sizes, exactly
$n$. Thus the cost of the algorithm is polynomial in $n$, taking into account
the size of each key $i$.

Computing the cycle structure of a permutation: This is a simple modification
of the previous functions.

    # Function to find the size of an orbit
    # visited is an array recording the visited indices
    # permut is a permutation
    # start an index from which we start constructing the orbit
    # Assuming: start <= degree of permut

    def find_orbit_size(visited, permut, start):
        s = 0
        while not visited[start]:
            visited[start] = True
            s=s+1
            start = permut[start-1]
        return s

This new function should be inserted in the remaining program. Then the list
obtained in `orbits.append` is the cycle structure of $permut$. The complexity
remains unchanged.

###  B.3 Sage code for lower bounds on the column sum

In this appendix, we provide a Sage implementation of the bounds on the column
sum as elaborated in the text. We start from formulas (6.111) and (6.119), for
a given partition $\lambda$. Then, we extend the code to the most generic
situation delivered in formula (6.172). By restriction, we can recover (6.131)
and (LABEL:eq:GenBoundEven) when the partition $\lambda$ consists solely of
odd or even cycles.

To obtain the sum of normalized central characters in Sage, we use symmetric
functions provided by the command `SymmetricFunctions(QQ)`.

Sage code for the column sum of normalized central characters -

    # For extra comments consult:
    # https://doc.sagemath.org/html/en/reference/combinat/sage/
    combinat/sf/sfa.html
    #
    s = SymmetricFunctions(QQ).s()
    # Schur symmetric function
    pp = SymmetricFunctions(QQ).power()
    # power symmetric function

    # Ccomputes the sum of normalized central characters
    # for conjugacy class labeled by Lam in the permutation group Sn
    # n a positive integer
    # Lam a partition of n

    def NormCharSum (n , Lam) :
      l = len ( Partitions(n).list() )
      s = 0
      P = Partitions(n).list()
      for i in range( l ):
           s = s +
        s(P[i]).scalar(pp(Lam))*factorial(n)/Lam.centralizer_size()/dimension(P[i])
           # P[i] determines the irrep
           # s(P[i]).scalar(pp(Lam)) gives the caracter chi^(P[i])_Lam
           # Lam.centralizer_size() gives the size of the centralizer
           # dimension (P[i]) is the dimension of the irrep P[i]
      return s

We test the function as:

    NormCharSum (2, Partition([1,1]))
    (out)  2
    NormCharSum (5, Partition([2,2,1]))
    (out) 31

Sage code for data in Table 1 - The following code delivers the data of Table
1 which lists the column sum and its lower bound in the simplest case when
$\lambda=[n]$. We implement directly the formula (6.111) as:

    # Return the lower bound for the column sum of the character table
    # when lambda is the cycle [n] of odd length n
    # n an positive odd integer

    def func (n):
        return 2^((n-1)/2)* factorial((n-1)/2)

    # Returns a list L of 4-tuples
    # n a odd positive integer
    # for q = 3,5, ...., 2k+1 < n
    # L[q] =
    # [ q the number which is partitioned,
    # the column sum for lambda = [q],
    # the lower bound computed by func(q),
    # relative error between the two results ]
    # N is for getting a numerical evaluation

    def Bound_SingleOddCycle (n):
        L = []
        for q in range (3,n+1,2):
            No = NormCharSum (q, Partition([q]))
            f = func(q)
            L.append( [q, No, f, N((No - f)/No)])
        return L

We run this code by calling:

    Bound_SingleOddCycle (21):

    (out)
    [[3, 3, 2, 0.333333333333333],
     [5, 40, 8, 0.800000000000000],
     [7, 1260, 48, 0.961904761904762],
     [9, 72576, 384, 0.994708994708995],
     [11, 6652800, 3840, 0.999422799422799],
     [13, 889574400, 46080, 0.999948199948200],
     [15, 163459296000, 645120, 0.999996053329387],
     [17, 39520825344000, 10321920, 0.999999738823268],
     [19, 12164510040883200, 185794560, 0.999999984726507],
     [21, 4644631106519040000, 3715891200, 0.999999999199960]]

Sage code for the Table 2 - We deal with the data of Table 2 that records the
column sum and its lower bound when $\lambda=[a^{p}]$, with $a$ an odd
positive integer.

We implement directly the formula (6.119) as:

    # Returns the lower bound for the column sum of the character table
    # when lambda = [a^p]
    # a an odd positive integer
    # p is an integer

    def funcSingleOdd ( a, p ):
        s = 0
        for k in range (0,floor(p/2)+1):
            s = s + factorial( p*(a-1)/2+ k )/ ( a^k *factorial(k))
        return 2^((a-1)*p/2)*s

We tabulate this function and the column sum to collect the data of Table 2:

    #  Return a list L of 4-tuples
    # A a positive integer
    # n  a positive integer
    # for a = 3,5, ...., 2k+1 < A
    # for q = 1,2,..., n
    # the (a,q)-th element of the list L
    # L[a,q] = [a*q  , the column sum for lambda = [a^q],
    # the lower bound (a,q), relative error between the two results]
    # N is for getting a numerical evaluation

    def NCS_SingleOdd (A, n):
        L = []
        for a in range (3,A+1,2):
            for q in range (2,n+1):
                l =[]
                for m in range (1,q+1):
                    l.append(a)
                No = NormCharSum (a*q, Partition(l))
                f = funcSingleOdd(a,q)
                L.append( [a*q, No, f, N((No-f)/No)])
        return L

We run this code as:

     NCS_SingleOdd (7, 4)
     (out)
     [[6, 99, 16, 0.838383838383838],
     [9, 4520, 112, 0.975221238938053],
     [12, 504012, 1664, 0.996698491305763],
     [10, 139535, 768, 0.994496004586663],
     [15, 3276085815, 110592, 0.999966242642518],
     [20, 309182846345600, 47480832, 0.999999846431222],
     [14, 1669223276, 92160, 0.999944788692247],
     [21, 47396002215287089, 451215360, 0.999999990479886],
     [28, 10217174199249113268200217, 9249384038400, 0.999999999999095]]

Sage code for Table 4 - The following gives the code for the data found in
Table 4. Based on (6.172), we compute the general lower bound of the column
sum.

    # Returns a list [Cmumulam, su]
    # L = [p_1,p_2,p_3] takes only the number of occurrences
    # of a partition of n of the form 3* p_1 + 2*p_2 + p_3
    # where p_1, p_2, p_3  are fixed and never vanishing

    # Cmumulam is a list of pairs [mu, C]
    # where the partitions mu contribute
    # to the factorization of L in two permutations of type mu
    # mu = [(n- P-Q)/2 + ell, P+Q-2*ell]
    # where P = p_1 + p_3 is the number of odd parts in L
    # Q = p_2  the number of even parts in L
    # p_2 is an even positive integer
    # and C is the structure constant C^mu_{mu L} of the centre

    # su is the bound on the column sum

    def BoundMK321 (L):
      if (L[1]%2) != 0 :
         print "Err: Q must be even"
         return 0
      else:
         n = 3*L[0] + 2*L[1] + L[2]
         P = L[0]+ L[2]
         Q = L[1]

         tQ = L[1]/2
         tP = floor(L[0]/2) + floor(L[2]/2)

         su = 0
         su2 = 0
         Cmumulam = []
         for ell in range(tP+tQ+1):
           for M in range(tP+1):
             for K in range (tQ+1):
                if (K+M== ell):
                  su1 = 0
                  for k0 in range( floor(L[0]/2)+1 ):
                     for k2 in range( floor(L[2]/2)+1 ):
                        if (k0+k2 == M):
                           for k1 in range( floor(L[1]/2) +1 ):
                              if k1 == K :
                                 su1 += 1/((3^(k0)*factorial(k0)*
                                  factorial(L[0]-2*k0)) )*
                                  1/((2^(k1)*factorial(k1)* factorial(L[1]-2*k1)))*
                                  1/((1^(k2)*factorial(k2)* factorial(L[2]-2*k2)))
                   su1 *=  binomial(Q-2*K,(Q-2*K)/2) /(2^(2*M))

                   su += 2^((1/2)*(n - P - 3*Q)+2*ell)
                   * factorial((1/2)*(n - P - Q) + ell)
                   *factorial(P + Q- 2*ell) *su1
           Cmumulam.append( [[ 1/2*(n - (P+Q)) + ell, P+Q-2*ell ],su-su2])
           su2 = su

        return [Cmumulam,su]

To test this function, we call

     BoundMK321 ([0,2,2])
     (out) [[[[1, 4], 6], [[2, 2], 4], [[3, 0], 6]], 16]

Now, we define a function that tabulates the bounds on the column sum for
various values of $n$. This gives the data of Table 4.

    # Computes a list tot_List of 4-tuples [L[i], no, nu[1], N((no-nu[1])/no)]
    # where
    # given a positive integer M, for all 1 <= n <= M
    # L the list of partitions of n with maximal part 3,
    # thus all partitions of the form [3^*,2^*,1^*]
    #
    # For all partitions L[i] elements of L
    # no is the sum of central normalized characters in conjugacy class L[i]
    # (uses function NormCharSum (n, L[i]))
    # nu[1] is the lower bound obtained for L[i]
    # (uses BoundMK321 on the multiplicity list of L[i])
    # and the relative error N((no-nu[1])/no)

    def funBound321 (M):

        for n in range(1,M+1):
            L = Partitions(n, max_part=3).list()
            l = len(L)
            tot_List =[]

            for i in range(l):

                li = list(L[i])
                if li.count(2)%2 ==0 :

                    no = NormCharSum (n, L[i])
                    Lcount = [li.count(3), li.count(2), li.count(1)]
                    nu = BoundMK321(Lcount)
                    #nu[1] contains the bound, nu[0] is a list of the Cmumulam

                    tot_List.append( [L[i],  no, nu[1], N((no-nu[1])/no)  ] )

            print n, tot_List
            print "\n"
        return 0

We run the following code to produce a table extending Table 4.

    funBound321 (10)

    (out)
    1 [[[1], 1, 1, 0.000000000000000]]
    2 [[[1, 1], 2, 2, 0.000000000000000]]
    3 [[[3], 3, 2, 0.333333333333333],
    [[1, 1, 1], 3, 2, 0.333333333333333]]

    4 [[[3, 1], 12, 4, 0.666666666666667],
    [[2, 2], 7, 3, 0.571428571428571],
     [[1, 1, 1, 1], 5, 3, 0.400000000000000]]

    5 [[[3, 1, 1], 42, 10, 0.761904761904762],
     [[2, 2, 1], 31, 5, 0.838709677419355],
     [[1, 1, 1, 1, 1], 7, 3, 0.571428571428571]]

    6 [[[3, 3], 99, 16, 0.838383838383838],
     [[3, 1, 1, 1], 99, 16, 0.838383838383838],
    [[2, 2, 1, 1], 118, 16, 0.864406779661017],
     [[1, 1, 1, 1, 1, 1], 11, 4, 0.636363636363636]]

    7 [[[3, 3, 1], 612, 32, 0.947712418300654],
    [[3, 2, 2], 381, 24, 0.937007874015748],
    [[3, 1, 1, 1, 1], 231, 28, 0.878787878787879],
    [[2, 2, 1, 1, 1], 309, 24, 0.922330097087379],
    [[1, 1, 1, 1, 1, 1, 1], 15, 4, 0.733333333333333]]

    8 [[[3, 3, 1, 1], 2898, 112, 0.961352657004831],
    [[3, 2, 2, 1], 3216, 72, 0.977611940298508],
    [[3, 1, 1, 1, 1, 1], 462, 40, 0.913419913419913],
    [[2, 2, 2, 2], 272, 21, 0.922794117647059],
    [[2, 2, 1, 1, 1, 1], 772, 50, 0.935233160621762],
    [[1, 1, 1, 1, 1, 1, 1, 1], 22, 5, 0.772727272727273]]

    9 [[[3, 3, 3], 4520, 112, 0.975221238938053],
    [[3, 3, 1, 1, 1], 9432, 192, 0.979643765903308],
    [[3, 2, 2, 1, 1], 17022, 240, 0.985900599224533],
    [[3, 1, 1, 1, 1, 1, 1], 882, 60, 0.931972789115646],
    [[2, 2, 2, 2, 1], 2000, 45, 0.977500000000000],
    [[2, 2, 1, 1, 1, 1, 1], 1642, 70, 0.957369062119367],
    [[1, 1, 1, 1, 1, 1, 1, 1, 1], 30, 5, 0.833333333333333]]

    10 [[[3, 3, 3, 1], 44093, 320, 0.992742612206019],
    [[3, 3, 2, 2], 50157, 432, 0.991387044679706],
    [[3, 3, 1, 1, 1, 1], 27639, 432, 0.984369912080755],
    [[3, 2, 2, 1, 1, 1], 63981, 528, 0.991747550053922],
    [[3, 1, 1, 1, 1, 1, 1, 1], 1596, 80, 0.949874686716792],
    [[2, 2, 2, 2, 1, 1], 11460, 186, 0.983769633507853],
    [[2, 2, 1, 1, 1, 1, 1, 1], 3391, 120, 0.964612208787968],
    [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 42, 6, 0.857142857142857]]

    0

$n$ | $\lambda$ | $\sum_{R\vdash n}{\chi^{R}(T_{\lambda})\over d_{R}}$ | Lower bound | Relative error
---|---|---|---|---
1 | $[1]$ | 1 | 1 | 0
2 | $[1^{2}]$ | 2 | 2 | 0
3 | $[3]$ | 3 | 2 | 0.33
| $[1^{3}]$ | 3 | 2 | 0.33
4 | $[3,1]$ | 12 | 4 | 0.66
| $[2^{2}]$ | 7 | 3 | 0.57
| $[1^{4}]$ | 5 | 3 | 0.40
5 | $[3,1^{2}]$ | 42 | 10 | 0.76
| $[2^{2},1]$ | 31 | 5 | 0.83
| $[1^{5}]$ | 7 | 3 | 0.57
6 | $[3^{2}]$ | 99 | 16 | 0.83
| $[3,1^{3}]$ | 99 | 16 | 0.83
| $[2^{2},1^{2}]$ | 118 | 16 | 0.88
| $[1^{6}]$ | 11 | 4 | 0.63
7 | $[3^{2},1]$ | 612 | 32 | 0.94
| $[3,2^{2}]$ | 381 | 24 | 0.93
| $[3,1^{4}]$ | 231 | 28 | 0.87
| $[2^{2},1^{3}]$ | 309 | 24 | 0.92
| $[1^{7}]$ | 15 | 4 | 0.73
8 | $[3^{2},1^{2}]$ | 2898 | 112 | 0.96
| $[3,2^{2},1]$ | 3216 | 72 | 0.97
| $[3,1^{5}]$ | 462 | 40 | 0.91
| $[2^{4}]$ | 272 | 21 | 0.92
| $[2^{2},1^{4}]$ | 772 | 50 | 0.94
| $[1^{8}]$ | 22 | 5 | 0.77
9 | $[3^{3}]$ | 4520 | 112 | 0.97
| $[3^{2},1^{3}]$ | 9432 | 192 | 0.97
| $[3,2^{2},1^{2}]$ | 17022 | 240 | 0.98
| $[3,1^{6}]$ | 882 | 60 | 0.93
| $[2^{4},1]$ | 2000 | 45 | 0.97
| $[2^{2},1^{5}]$ | 1642 | 70 | 0.96
| $[1^{9}]$ | 30 | 5 | 0.83
Table 4: The column sum evaluation and its lower bound for
$\lambda=[3^{*},2^{*},1^{*}]\vdash n$, $n\in\\{1,2,\dots,9\\}$. Only non
vanishing values are shown.

###  B.4 GAP code for lower bounds on column sum

We provide below a GAP code that produces the lower bounds on the column sum
problem. Some functions have been introduced in Appendix B.1, we recall them
for pedagogical purpose.

    %%gap
    partsq := function (mu , m )
            local LL, cc, Listmu , Grp ;
            LL := []  ;
            Grp := SymmetricGroup(m) ;
            cc := ConjugacyClasses (Grp) ;
            Listmu := AsList(cc[mu]) ;
            for k in [ 1 .. Length(Listmu) ] do
               Add ( LL , Listmu[1]*Listmu[k] ) ;
            od;
    return LL ;
    end;

    # Returns the structure constant C_{mu lam}^{mu}
    # Takes as input indices mu, lam of partitions of m

    Countmumulam := function ( mu , lam , m  )
        local cc , Grp ;
        Grp  := SymmetricGroup (m ) ;
        cc := ConjugacyClasses ( Grp ) ;
        return
        Length ( Filtered ( partsq ( mu , m  ) , x -> x in  AsList (cc[lam ]) ) ) ;
    end ;

    ## Produces for lambda, a list of mu’s ,
    ## along with the C_{ mu , mu , lambda }

    Tablam := function ( lam , m )
        local L , cc  ;
        cc := ConjugacyClasses ( SymmetricGroup (m )) ;
        L := [ ] ;
        for i in [ 1 .. NrPartitions ( m ) ] do
           Add ( L , [ cc [i]  , Countmumulam ( i , lam , m )] )   ;
        od ;
    return L ;
    end ;

    ## Computes  the indices of [2*,1*] partitions
    # mm1 a positive integer

    Partitions2st1stind := function ( mm1)
            local pp , Countones, Counttwos  , LL1 ;
            LL1 := [] ;
            pp := Partitions(mm1) ;
            for i in [1 .. NrPartitions (mm1 )]  do
                Countones := Length( Positions (  pp[i] , 1 ) ) ;
                Counttwos := Length( Positions (  pp[i] , 2 ) ) ;
                if
                   2*Counttwos + Countones  = mm1  then Add ( LL1 ,   i  ) ;
                fi;
            od ;
    return LL1;
    end;

    partmunu := function (mu , nu ,  m )
            local LL, cc, Listmu , Listnu,  Grp ;
            LL := []  ;
            Grp := SymmetricGroup(m) ;
            cc := ConjugacyClasses (Grp) ;
            Listmu := AsList(cc[mu]) ;
            Listnu := AsList(cc[nu]) ;
            for k in [ 1 .. Length(Listmu) ] do
               for l in [ 1 .. Length(Listnu) ] do
                 Add ( LL , Listmu[k]*Listnu[l] ) ;
                od;
            od;
    return LL ;
    end;

    ## We can do the same selection of 2st1st at the level of partitions ;
    ## this function lists the partitions
    Partitions2st1st := function ( mm1)
            local pp , Countones, Counttwos  , LL1 ;
            LL1 := [] ;
            pp := Partitions(mm1) ;
            for i in [1 .. NrPartitions (mm1 )]  do
                Countones := Length( Positions (  pp[i] , 1 ) ) ;
                Counttwos := Length( Positions (  pp[i] , 2 ) ) ;
                if
                   2*Counttwos + Countones  = mm1  then Add ( LL1 ,   pp[i]  ) ;
                fi;
            od ;
    return LL1;
    end;

    ## This is a variation that produces the indices
    Partitions2st1stind := function ( mm1)
            local pp , Countones, Counttwos  , LL1 ;
            LL1 := [] ;
            pp := Partitions(mm1) ;
            for i in [1 .. NrPartitions (mm1 )]  do
                Countones := Length( Positions (  pp[i] , 1 ) ) ;
                Counttwos := Length( Positions (  pp[i] , 2 ) ) ;
                if
                   2*Counttwos + Countones  = mm1  then Add ( LL1 ,   i  ) ;
                fi;
            od ;
    return LL1;
    end;

    ## This computes  the bound of the colum sum
    ## Lam is the partition
    ## m is the integer which is partitioned

    Sumlam2st1stPartInp  := function ( Lam , m )
        local  S , i, lam  ;
        #pp2s1s := Partitions2st1st (m) ;
        S := 0 ;
        lam := Position ( Partitions (m) , Lam );
        for i in Partitions2st1stind(m)  do
            S := S + Countmumulam ( i , lam , m ) ;
        od ;
    return  S  ;
    end ;

We run it as

    %%gap
    # For all lam at fixed n, compute the lower bound coming from
    # partition of the type [2*,1*]
    for  p in Partitions (5) do
     Print (   Sumlam2st1stPartInp ( p  , 5 ) , " " ,p ,  " \n " )  ;
    od ;

    (out)
    3 [ 1, 1, 1, 1, 1 ]
    0 [ 2, 1, 1, 1 ]
    5 [ 2, 2, 1 ]
    10 [ 3, 1, 1 ]
    0 [ 3, 2 ]
    0 [ 4, 1 ]
    8 [ 5 ]

    %%gap
    for  p in Partitions (8) do
     Print (   Sumlam2st1stPartInp ( p  , 8 ) , " " ,p ,  " \n " )  ;
    od ;

    (out)
    5 [ 1, 1, 1, 1, 1, 1, 1, 1 ]
    0 [ 2, 1, 1, 1, 1, 1, 1 ]
    50 [ 2, 2, 1, 1, 1, 1 ]
    0 [ 2, 2, 2, 1, 1 ]
    21 [ 2, 2, 2, 2 ]
    40 [ 3, 1, 1, 1, 1, 1 ]
    0 [ 3, 2, 1, 1, 1 ]
    72 [ 3, 2, 2, 1 ]
    112 [ 3, 3, 1, 1 ]
    0 [ 3, 3, 2 ]
    0 [ 4, 1, 1, 1, 1 ]
    72 [ 4, 2, 1, 1 ]
    0 [ 4, 2, 2 ]
    0 [ 4, 3, 1 ]
    72 [ 4, 4 ]
    80 [ 5, 1, 1, 1 ]
    0 [ 5, 2, 1 ]
    96 [ 5, 3 ]
    0 [ 6, 1, 1 ]
    48 [ 6, 2 ]
    96 [ 7, 1 ]
    0 [ 8 ]

## References

  * [1] David J. Gross and Washington Taylor.  Two-dimensional QCD is a string theory.  Nucl. Phys. B, 400:181–208, 1993.
  * [2] David J. Gross and Washington Taylor.  Twists and Wilson loops in the string theory of two-dimensional QCD.  Nucl. Phys. B, 403:395–452, 1993.
  * [3] Stefan Cordes, Gregory W. Moore, and Sanjaye Ramgoolam.  Lectures on 2-d Yang-Mills theory, equivariant cohomology and topological field theories.  Nucl. Phys. B Proc. Suppl., 41:184–244, 1995.
  * [4] Ofer Aharony, Suman Kundu, and Tal Sheaffer.  A String Theory for Two Dimensional Yang-Mills Theory I.  arxiv:2312.12266[hep-th] 12 2023.
  * [5] Lior Benizri and Jan Troost.  Symmetric Group Gauge Theories and Simple Gauge/String Dualities.  arXiv:2404.12543[hep-th] 4 2024.
  * [6] Robbert Dijkgraaf and Edward Witten.  Topological gauge theories and group cohomology.  Commun. Math. Phys., 129(2):393–429, 1990.
  * [7] Edward Witten.  On quantum gauge theories in two dimensions.  Commun. Math. Phys., 141(1):153 – 209, 1991.
  * [8] Daniel S. Freed and Frank Quinn.  Chern-Simons theory with finite gauge group.  Commun. Math. Phys., 156:435–472, 1993.
  * [9] M. Fukuma, S. Hosono, and H. Kawai.  Lattice topological field theory in two-dimensions.  Commun. Math. Phys., 161:157–176, 1994.
  * [10] Robert de Mello Koch, Yang-Hui He, Garreth Kemp, and Sanjaye Ramgoolam.  Integrality, duality and finiteness in combinatoric topological strings.  JHEP, 01:071, 2022.
  * [11] Donald Marolf and Henry Maxfield.  Transcending the ensemble: baby universes, spacetime wormholes, and the order and disorder of black hole information.  JHEP, 08:044, 2020.
  * [12] John G. Gardiner and Stathis Megas.  2d TQFTs and baby universes.  JHEP, 10:052, 2021.
  * [13] Anindya Banerjee and Gregory W. Moore.  Comments on summing over bordisms in TQFT.  JHEP, 09:171, 2022.
  * [14] Ibrahima Bah, Daniel S. Freed, Gregory W. Moore, Nikita Nekrasov, Shlomo S. Razamat, and Sakura Schafer-Nameki.  A Panorama Of Physical Mathematics c. 2022.  arxiv:2211.04467[hep-th] 11 2022.
  * [15] E. Sharpe.  Dilaton shifts, probability measures, and decomposition.  arxiv:2312.08438[hep-th] 12 2023.
  * [16] Sanjaye Ramgoolam and Eric Sharpe.  Combinatoric topological string theories and group theory algorithms.  JHEP, 10:147, 2022.
  * [17] Adrian Padellaro, Rajath Radhakrishnan, and Sanjaye Ramgoolam.  Row–column duality and combinatorial topological strings.  J. Phys. A, 57(6):065202, 2024.
  * [18] Hélène Barcelo and Arun Ram.  Combinatorial representation theory.  Oberwolfach Reports, 7:799–882, 1997.
  * [19] Richard P. Stanley.  Positivity problems and conjectures.  Mathematics: frontiers and perspectives, American Mathematical Society, Providence, RI, page 295–319, 2000.
  * [20] Leonard Susskind.  Computational Complexity and Black Hole Horizons.  Fortsch. Phys., 64:24–43, 2016.  [Addendum: Fortsch.Phys. 64, 44–48 (2016)].
  * [21] Adam Bouland, Bill Fefferman, and Umesh Vazirani.  Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality.  arxiv:1910.14646[quant-ph] 10 2019.
  * [22] James Halverson and Fabian Ruehle.  Computational Complexity of Vacua and Near-Vacua in Field and String Theory.  Phys. Rev. D, 99(4):046015, 2019.
  * [23] Thomas W. Grimm and Jeroen Monnee.  Finiteness Theorems and Counting Conjectures for the Flux Landscape.  arxiv:2311.09295[hep-th] 11 2023.
  * [24] Joseph Ben Geloun and Sanjaye Ramgoolam.  Quantum mechanics of bipartite ribbon graphs: Integrality, Lattices and Kronecker coefficients.  Algebraic Combinatorics, to appear, 10 2020.
  * [25] Francis D. Murnaghan.  The analysis of the kronecker product of irreducible representations of the symmetric group.  American Journal of Mathematics, 60:761, 1938.
  * [26] Joseph Ben Geloun and Sanjaye Ramgoolam.  Counting tensor model observables and branched covers of the 2-sphere.  Ann. Inst. H. Poincare D Comb. Phys. Interact., 1(1):77–138, 2014\.
  * [27] Paolo Mattioli and Sanjaye Ramgoolam.  Permutation Centralizer Algebras and Multi-Matrix Invariants.  Phys. Rev. D, 93(6):065040, 2016.
  * [28] Joseph Ben Geloun and Sanjaye Ramgoolam.  Tensor Models, Kronecker coefficients and Permutation Centralizer Algebras.  JHEP, 11:092, 2017.
  * [29] Remi C. Avohou, Joseph Ben Geloun, and Nicolas Dub.  On the counting of $O(N)$ tensor invariants.  Adv. Theor. Math. Phys., 24(4):821–878, 2020.
  * [30] Joseph Ben Geloun.  On the counting tensor model observables as $U(N)$ and $O(N)$ classical invariants.  PoS, CORFU2019:175, 2020.
  * [31] Thomas William Brown, P. J. Heslop, and S. Ramgoolam.  Diagonal multi-matrix correlators and BPS operators in N=4 SYM.  JHEP, 02:030, 2008.
  * [32] Yusuke Kimura and Sanjaye Ramgoolam.  Branes, anti-branes and Brauer algebras in gauge-gravity duality.  JHEP, 11:078, 2007.
  * [33] Rajsekhar Bhattacharyya, Storm Collins, and Robert de Mello Koch.  Exact Multi-matrix Correlators.  JHEP, 03:044, 2008.
  * [34] Rajsekhar Bhattacharyya, Robert de Mello Koch, and Michael Stephanou.  Exact Multi-Restricted Schur Polynomial Correlators.  JHEP, 06:101, 2008.
  * [35] Yusuke Kimura and Sanjaye Ramgoolam.  Enhanced symmetries of gauge theory and resolving the spectrum of local operators.  Phys. Rev. D, 78:126003, 2008.
  * [36] Paolo Mattioli and Sanjaye Ramgoolam.  Permutation Centralizer Algebras and Multi-Matrix Invariants.  Phys. Rev. D, 93(6):065040, 2016.
  * [37] Joseph Ben Geloun and Sanjaye Ramgoolam.  The quantum detection of projectors in finite-dimensional algebras and holography.  JHEP, 05:191, 2023.
  * [38] Juan Martin Maldacena.  The Large N limit of superconformal field theories and supergravity.  Adv. Theor. Math. Phys., 2:231–252, 1998.
  * [39] S. S. Gubser, Igor R. Klebanov, and Alexander M. Polyakov.  Gauge theory correlators from noncritical string theory.  Phys. Lett. B, 428:105–114, 1998.
  * [40] Edward Witten.  Anti-de Sitter space and holography.  Adv. Theor. Math. Phys., 2:253–291, 1998.
  * [41] H. Narayanan.  On the complexity of computing kostka numbers and littlewood-richardson coefficients.  J Algebr Comb, 24:347–354, 2006.
  * [42] K. D. Mulmuley, H. Narayanan, and M. Sohoni.  Geometric complexity theory iii: on deciding nonvanishing of a littlewood–richardson coefficient.  J Algebr Comb, 36:103–110, 2015.
  * [43] Christian Ikenmeyer, Ketan Mulmuley, and Michael Walter.  On vanishing of kronecker coefficients.  Computational Complexity, 26:949–992, 2017.
  * [44] Christian Ikenmeyer, Igor Pak, and Greta Panova.  Positivity of the symmetric group characters is as hard as the polynomial time hierarchy.  arxiv: 2207.05423[math-CO] 7 2022.
  * [45] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach.  Cambridge University Press, 1st edition, 2009.
  * [46] Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojt ěch Havlíček, and Guanyu Zhu.  Quantum complexity of the kronecker coefficients.  PRX Quantum, 5:010329, Feb 2024.
  * [47] Christian Ikenmeyer and Sathyawageeswar Subramanian.  A remark on the quantum complexity of the kronecker coefficients.  arxiv:2307.02389[quant-ph] 07 2023.
  * [48] A. Hurwitz.  Ueber riemann’sche flächen mit gegebenen verzweigungspunkten.  Mathematische Annalen, 39(1):1–60, 1891.
  * [49] Mireille Bousquet-Mélou and Gilles Schaeffer.  Enumeration of planar constellations.  Adv. Appl. Math., 24:337–368, 2000.
  * [50] John Irving.  Combinatorial constructions for transitive factorizations in the symmetric group.  Waterloo’s Institutional Repository, 2004.
  * [51] John Irving.  Minimal transitive factorizations of permutations into cycles.  Canadian Journal of Mathematics, 61:1092 – 1117, 2006.
  * [52] Morton Hamermesh.  Group theory and its application to Physical Problems.  Dover Books on Physics. Dover, 2003.
  * [53] R. Goodman and N.R. Wallach.  Symmetry, Representations, and Invariants.  Graduate Texts in Mathematics. Springer New York, 2009.
  * [54] I.G. Macdonald.  Symmetric Functions and Hall Polynomials.  Oxford classic texts in the physical sciences. Clarendon Press, 1998.
  * [55] William Fulton.  Young Tableaux, volume 35 of London Mathematical Society Student Texts.  Cambridge University Press, 1997.
  * [56] Jurgis Pasukonis and Sanjaye Ramgoolam.  Quivers as Calculators: Counting, Correlators and Riemann Surfaces.  JHEP, 04:094, 2013.
  * [57] Arvind Ayyer, Hiranya Kishore Dey, and Digjoy Paul.  How large is the character degree sum compared to the character table sum for a finite group?  arixv:2406.06036[math.RT] 6 2024.
  * [58] Garreth Kemp and Sanjaye Ramgoolam.  BPS states, conserved charges and centres of symmetric group algebras.  JHEP, 01:146, 2020.
  * [59] S.K. Lando, R.V. Gamkrelidze, V.A. Vassiliev, and A.K. Zvonkin.  Graphs on Surfaces and Their Applications.  Encyclopaedia of Mathematical Sciences, Low dimensional topology II. Springer Berlin Heidelberg, 2013.
  * [60] M Bauer and C Itzykson.  Triangulations.  Discrete Mathematics, 156(1-3):29–81, 1996.
  * [61] Robert de Mello Koch and Sanjaye Ramgoolam.  From Matrix Models and Quantum Fields to Hurwitz Space and the absolute Galois Group.  arxiv:1002.1634[hep-th] 2 2010.
  * [62] T. W. Brown.  Complex matrix model duality.  Phys. Rev. D, 83:085002, 2011.
  * [63] Wikipedia contributors.  Computational complexity of mathematical operations Wikipedia, the free encyclopedia, 2024.  [Online; accessed 23-Jun3-2024].
  * [64] J. M. Borwein and P. B. Borwein.  Pi and the AGM: a study in analytic number theory and computational complexity.  Wiley, 1987.
  * [65] P. A. MacMahon.  Divisors of numbers and their continuations in the theory of partitions.  Proc. London Math. Soc., 19:75–113.
  * [66] Horst Alzer.  A superadditive property of hadamard’s gamma function.  Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 79(1):11–23, 2009.
  * [67] A. Morozov and Sh. Shakirov.  Exact 2-point function in Hermitian matrix model.  JHEP, 12:003, 2009.
  * [68] A. S. Alexandrov, A. Mironov, and A. Morozov.  Partition functions of matrix models as the first special functions of string theory. 1. Finite size Hermitean one matrix model.  Int. J. Mod. Phys. A, 19:4127–4165, 2004.
  * [69] A. Mironov and A. Morozov.  Superintegrability summary.  Phys. Lett. B, 835:137573, 2022.
  * [70] Robert de Mello Koch and Sanjaye Ramgoolam.  Strings from Feynman Graph counting : without large N.  Phys. Rev. D, 85:026007, 2012.