# Arithmetic statistics of Galois groups

David Kohel  Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille,
France<EMAIL_ADDRESS>
###### Abstract.

We develop a computational framework for the statistical characterization of
Galois characters with finite image, with application to characterizing Galois
groups and establishing equivalence of characters of finite images of
$\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$.

##  1\. Introduction

The absolute Galois group
$\mathcal{G}=\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ is a fundamental
object of study in number theory. The objective of this work is to develop an
explicit computational framework for the study of its finite quotients. We may
replace $\mathcal{G}$ with the absolute Galois group of any global field, but
restrict to that of $\mathbb{Q}$ for simplicity of exposition.

As point of departure, we consider an irreducible polynomial
$f(x)\in\mathbb{Z}[x]$ of degree $n$ as input. We set
$K=\mathbb{Q}[x]/(f(x))$, denote by $L$ its normal closure and by
$\mathcal{G}(K)$ the Galois group $\mathrm{Gal}(L/\mathbb{Q})$ equipped with a
permutation representation in ${\mathcal{S}}_{n}$ determined by the action on
the roots of $f(x)$. Let $\mathcal{P}_{S}(\mathbb{Z})$ be the set of primes,
coprime to the finite set $S$ of primes ramified in $\mathbb{Z}[x]/(f(x))$.

The statistical perspective we develop expresses the map from
$\mathcal{P}_{S}(\mathbb{Z})$ to factorization data as an equidistributed map
to a finite set $\mathcal{X}(K)$ equipped with a probability function induced
from the Haar measure on $\mathcal{G}(K)$. A Frobenius lift at $p$, defined up
to conjugacy, acts on the roots of $f(x)$. The permutation action on the roots
of $f(x)$ induces a representation in $\mathrm{O}(n)$, fixing the formal sum
of the roots. The orthogonal complement gives the standard representation in
$\mathrm{O}(n-1)$, spanned by differences of basis elements. Let $P(x)$ be the
characteristic polynomial of Frobenius in the permutation representation and

$S(x)=P(x)/(x-1)=x^{n-1}-s_{1}x^{n-2}+\cdots+(-1)^{n-1}s_{n-1}.$

the characteristic polynomial in the standard representation. This polynomial
is independent of choices of lift of Frobenius and choice of basis. As such,
the coordinates $(s_{1},\dots,s_{n-1})\in\mathbb{Z}^{n-1}$ are invariants of
the Frobenius conjugacy class $\mathrm{Frob}_{p}$ in the set
${\mathcal{C}\\!\ell}(\mathcal{G}(K))$ of conjugacy classes of
$\mathcal{G}(K)$. Denote the finite set of such class points by
$\mathcal{X}(K)$. We note that the class points are entirely determined by the
factorization data of $f(x)\bmod p$, and
$\mathcal{X}(K)\subset\mathbb{Z}^{n-1}$ is equipped with the structure of a
finite probability space, induced from the cover
${\mathcal{C}\\!\ell}(\mathcal{G}(K))\rightarrow\mathcal{X}(K)$. The
irreducible characters are known to form an orthogonal basis for the class
functions on ${\mathcal{C}\\!\ell}(\mathcal{G}(K))$, and the rational
characters are integer-valued class functions on the class space
$\mathcal{X}(K)$.

In what follows we develop this approach by describing systems of rational
characters on $\mathcal{G}(K)$ algebraically as a basis of polynomials in
$\mathbb{Z}[s_{1},\dots,s_{n-1}]$ modulo the defining ideal for
$\mathcal{X}(K)$, together with their associated inner product. As a
consequence we develop algorithms for the characterization of Galois groups,
and more generally, tools for determining equivalence of finite Galois
representations.

##  2\. Representations of orthogonal groups

Let $G$ be a compact Lie group. In practice, $G$ will be an orthogonal group

$G=\mathrm{O}(n-1)\subset\mathrm{O}(n)\mbox{ or
}G=\mathrm{SO}(n-1)\subset\mathrm{O}(n-1),$

or a finite permutation group, equipped with the standard representation in
$\mathrm{O}(n-1)$,

$G\subseteq{\mathcal{S}}_{n}\subset\mathrm{O}(n-1)\mbox{ or
}G\subseteq{\mathcal{A}}_{n}\subset\mathrm{SO}(n-1).$

The standard representation of ${\mathcal{S}}_{n}$ provides the motivation for
an algebraic presentation of the character ring of a permutation group. For
the character theory of permutation groups, we appeal to known algorithms for
its computation.

The symmetric group ${\mathcal{S}}_{n}$ acts on a set of $n$ elements, and the
linear extension to a basis of $\mathbb{Z}^{n}\subset\mathbb{R}^{n}$ gives the
permutation representation of ${\mathcal{S}}_{n}$. Denote a basis
$\\{\mathbf{e}_{1},\dots,\mathbf{e}_{n}\\}$. Since
$\mathbf{e}_{1}+\cdots+\mathbf{e}_{n}$ is fixed by ${\mathcal{S}}_{n}$, a line
is fixed, and we consider the action on the hyperplane spanned by the
orthogonal complement. In the basis
$\\{\mathbf{e}_{1}-\mathbf{e}_{2},\dots,\mathbf{e}_{n-1}-\mathbf{e}_{n}\\}$,
we obtain the standard representation of ${\mathcal{S}}_{n}$ in
$\mathrm{O}(n-1)$. The choice of basis is noncanonical, but the character
theory is independent of any such choice. The orthogonal group $\mathrm{O}(n)$
and its subgroup $\mathrm{O}(n-1)$ have two connected components, with
principal component $\mathrm{SO}(n-1)\subset\mathrm{SO}(n)$, such that
${\mathcal{A}}_{n}={\mathcal{S}}_{n}\cap\mathrm{SO}(n-1)$.

### Representation ring

For a compact Lie group $G$, we denote the set of conjugacy classes of $G$ by
${\mathcal{C}\\!\ell}(G)$. We define the representation ring of $G$,

$\mathfrak{R}(G)=\bigoplus_{\chi}\mathbb{Z}\chi,$

as the free abelian group on irreducible characters
$\chi:G\rightarrow\mathbb{C}$ of finite degree. We identify addition with
direct sum, and thereby the abelian submonoid
$\bigoplus\mathbb{N}\chi\subseteq\mathfrak{R}(G)$ with characters, and define
multiplication on $\mathfrak{R}(G)$ by the linear extension of tensor product
on $\bigoplus\mathbb{N}\chi$. We refer to elements of $\mathfrak{R}(G)$ as
virtual characters.

As class functions, $\mathfrak{R}(G)$ can be identified with a subring of
complex-valued functions on ${\mathcal{C}\\!\ell}(G)$. Indeed, when $G$ is
finite, the number $h$ of conjugacy classes (and of irreducible characters) is
finite, and the character table is defined as the evaluation vectors

$\left(\chi_{i}(\mathcal{C}_{1}),\dots,\chi_{i}(\mathcal{C}_{h})\right).$

in the ring $\mathbb{C}^{h}=\mathbb{C}\times\cdots\times\mathbb{C}$, for
$\chi_{i}$ running over the irreducible characters, forming a generator set
for the representation ring. For a subfield $F\subset\mathbb{C}$, we denote by
$\mathfrak{R}_{F}(G)$ the subring of $F$-valued virtual characters. While
$\mathfrak{R}(G)=\mathfrak{R}_{\mathbb{Q}}(G)$ for $G={\mathcal{S}}_{n}$ or
$G=\mathrm{O}(n-1)$, for a general finite group that we may consider, the
field of definition of an irreducible character may be a proper extension of
$\mathbb{Q}$.

Considering the group $\mathrm{O}(n)$ in $\mathrm{GL}_{n}(\mathbb{R})$, an
element $g$ satisfies a characteristic polynomial of the form

$x^{n}-s_{1}x^{n-1}+\cdots+(-1)^{n}s_{n}.$

The coefficient $s_{1}$ is the trace in its representation on
$\mathbb{R}^{n}$, and $s_{n}$ is its determinant character. We note that
$s_{k}$ is an invariant of the class of $g$, and we can identify $g\mapsto
s_{k}$ as characters. Specifically, $s_{k}$ is the character on the $k$-th
exterior power $\bigwedge\nolimits^{k}\mathbb{R}^{n}.$ We recall the structure
of the character ring for $\mathrm{O}(n)$ (cf. Takeuchi [20]).

######  Lemma 1.

The virtual character ring $\mathfrak{R}(O(n))$ is generated by $s_{k}$,
$1\leq k\leq n$, and

$\mathfrak{R}(\mathrm{O}(n))\cong\frac{\mathbb{Z}[s_{1},\dots,s_{n}]}{(s_{k}s_{n}-s_{n-k},s_{n}^{2}-1)}\cdot$

The restriction
$\mathrm{Res}:\mathfrak{R}(\mathrm{O}(n))\rightarrow\mathfrak{R}(\mathrm{SO}(n))$
surjects on

$\mathfrak{R}(\mathrm{SO}(n))\cong\frac{\mathbb{Z}[s_{1},\dots,s_{n}]}{(s_{k}-s_{n-k},s_{n}-1)}$

with kernel ideal $(s_{n}-1)$.

Remark. If $n=2m$ or $n=2m+1$, then
$\mathfrak{R}(\mathrm{SO}(n))=\mathbb{Z}[s_{1},\dots,s_{m}]$, and
$\mathfrak{R}(\mathrm{O}(n))$ is an extension by the quadratic character
$\xi=s_{n}$ such that $\xi|_{\mathrm{SO}(n)}=1$.

### Algebraic parametrization

If $H$ is a subgroup of $G$, there is an induced map
${\mathcal{C}\\!\ell}(H)\rightarrow{\mathcal{C}\\!\ell}(G)$ on conjugacy
classes and concomitant restriction homomorphism
$\mathrm{Res}:\mathfrak{R}(G)\rightarrow\mathfrak{R}(H)$ on representation
rings. Applied to the standard representation of ${\mathcal{S}}_{n}$ in
$\mathrm{O}(n-1)$, the restriction homomorphism equips the representation ring
of $\mathfrak{R}({\mathcal{S}}_{n})$ with a surjective restriction map from
$\mathfrak{R}(\mathrm{O}(n-1))$, giving an algebraic presentation of
$\mathfrak{R}({\mathcal{S}}_{n})$ by polynomials in
$\mathbb{Z}[s_{1},\dots,s_{n-1}]$ modulo the defining ideal
$(s_{k}s_{n-1}-s_{n-k-1},s^{2}_{n-1}-1)$. Given a permutation group
$G\subset{\mathcal{S}}_{n}$, the subsequent restriction captures a significant
subring of $\mathfrak{R}_{\mathbb{Q}}(G)\subset\mathfrak{R}(G)$.

As a tool to characterize permutation groups in ${\mathcal{S}}_{n}$, for
subgroups $G$ and $H$, with $H\subseteq G\subseteq{\mathcal{S}}_{n}$, we
develop the branching rules — explicit forms for the decomposition

$\mathrm{Res}(\chi_{i})=\sum_{j=1}^{n_{i}}a_{ij}\psi_{j}.$

of irreducible characters $\\{\chi_{1},\dots,\chi_{r}\\}$ on $G$ in terms of
the irreducible characters $\\{\psi_{1},\dots,\psi_{s}\\}$ on $H$. In light of
the algebraic parametrization by $\mathbb{Z}[s_{1},\dots,s_{n-1}]$, we deduce
the kernel ideals $I_{G}\subseteq I_{H}$ for each permutation group in the
lattice (poset) of subgroups. A basis of generators provides test functions
for membership in a given subgroup. We develop the algorithmic details later.

Using the Brauer-Klimyk formula (see Bump [4, Proposition 22.9]), it is
possible to develop recursive formulas for the character theory of orthogonal
groups, as done in Shieh [18, 19] for $\mathrm{USp}(2m)$, and using the
algebraic presentation, to deduce recursive branching rules for
$\mathrm{Res}:\mathfrak{R}(\mathrm{O}(n-1))\rightarrow\mathfrak{R}(G)$.
Instead, we content ourselves with the algebraic parametrization from
$\mathfrak{R}(\mathrm{O}(n-1))$ and exploit the well-established computational
character theory of permutation groups to develop branching rules in the
lattice of permutation subgroups of ${\mathcal{S}}_{n}$.

##  3\. Representations of permutation groups

Let $G$ be a permutation group — a finite group equipped with an embedding in
${\mathcal{S}}_{n}$. The cycle type of $g\in G$ is the multiset of
cardinalities of its orbits under the action of ${\mathcal{S}}_{n}$ on
$\\{1,\dots,n\\}$. A multiset can be denoted by a tuple $(d_{1},\dots,d_{t})$
or a formal product $m_{1}^{e_{1}}\cdots m_{s}^{e_{s}}$, where

$d_{1}\leq d_{2}\leq\cdots\leq d_{t}\mbox{ or }m_{1}<\cdots<m_{s}\mbox{ such
that }\sum_{i=1}^{t}d_{i}=\sum_{i=1}^{s}e_{i}m_{i}=n.$

The cycle type is invariant under conjugation in ${\mathcal{S}}_{n}$, thus the
cycle type is well-defined for the conjugacy class
$\mathcal{C}=\mathcal{C}(g)\in{\mathcal{C}\\!\ell}(G)$, where
$\mathcal{C}(g)=\\{xgx^{-1}\,:\,x\in G\\}$.

######  Lemma 2.

The map
${\mathcal{C}\\!\ell}({\mathcal{S}}_{n})\longrightarrow\\{(d_{1},\dots,d_{t})\,:\,\sum_{i=1}^{t}d_{i}=n\\}$
from conjugacy classes of ${\mathcal{S}}_{n}$ to cycle types is a bijection.

###### Proof.

Clearly, giving a cyclic ordering to any partition of $\\{1,\dots,n\\}$ into
orbits determines an element of ${\mathcal{S}}_{n}$, hence the map is
surjective. Moreover, by definition the symmetric group is $n$-transitive,
conjugating any cyclically ordered orbit partition to any another of the same
cycle type. Consequently the map is injective. ∎

Remark. For a permutation group $G\subset{\mathcal{S}}_{n}$ the induced map
${\mathcal{C}\\!\ell}(G)\rightarrow{\mathcal{C}\\!\ell}({\mathcal{S}}_{n})$ in
general is neither injective nor surjective. The failure of injectivity means
that the cycle type fails to distinguish the conjugacy classes. We will later
see this in the failure of $\mathfrak{R}({\mathcal{S}}_{n})$ to surject on
$\mathfrak{R}(G)$. In fact, the irreducible characters are known to form a
basis of the class functions on $G$ (cf. Serre [17, Theorem 6]), hence the
failure to separate conjugacy classes means that the restriction homomorphism
from $\mathfrak{R}({\mathcal{S}}_{n})$ does not surject on $\mathfrak{R}(G)$.

On the one hand, the cycle type of a conjugacy class characterizes the class.
On the other hand, the characteristic polynomial (hence its coefficients) is
class invariant of an orthogonal group element, and the permutation and
standard representations thus provide other class invariants. We make this
association explicit. Given $(d_{1},\dots,d_{t})$ be the cycle type of an
element $g\in{\mathcal{S}}_{n}$. It is easy to see that the characteristic
polynomial of the permutation representation of $g$ is

$P(x)=(x^{d_{1}}-1)\cdots(x^{d_{t}}-1)=(x^{m_{1}}-1)^{e_{1}}\cdots(x^{m_{s}}-1)^{e_{s}}.$

The eigenvalue on the trivial space is $1$, so the characteristic polynomial
in the standard representation is

$S(x)=\frac{P(x)}{(x-1)}=x^{n-1}-s_{1}x^{n-2}+\cdots+(-1)^{n-1}s_{n-1},$

and $(s_{1},\dots,s_{n-1})$ is the tuple of class invariants associated to the
the conjugacy class $\mathcal{C}(g)$ under the standard representation in
$\mathrm{O}(n-1)$. This gives the following lemma.

######  Lemma 3.

The map ${\mathcal{C}\\!\ell}({\mathcal{S}}_{n})\rightarrow\mathbb{Z}^{n-1}$
from conjugacy classes to the $(n-1)$-tuples $(s_{1},\dots,s_{n-1})$ of
coefficients of the characteristic polynomial under the standard embedding is
injective.

###### Proof.

By Lemma 2 the map from conjugacy classes to cycle types is a bijection.
However, by unique factorization in $\mathbb{Q}[x]$, a polynomial of the form
$(x^{d_{1}}-1)\cdots(x^{d_{t}}-1)$ is uniquely determined by the cycle type
$(d_{1},\dots,d_{t})$, hence the map to its coefficients
$(s_{1},\dots,s_{n-1})$ is injective. ∎

### Representation rings and character tables

Let $G$ be a permutation group and let
${\mathcal{C}\\!\ell}(G)=\\{\mathcal{C}_{1},\dots,\mathcal{C}_{h}\\}$, and
$\\{\chi_{1},\dots,\chi_{h}\\}$ be its irreducible characters. For a conjugacy
class $\mathcal{C}$, define the ideal

$\mathfrak{m}_{\mathcal{C}}=\\{f\in\mathfrak{R}(G)\,:\,f(\mathcal{C})=0\\}.$

such that the value $f(\mathcal{C})$ of a virtual character $f$ at
$\mathcal{C}$ is a well-defined class in the residue class ring
$\mathfrak{R}(G)/\mathfrak{m}_{\mathcal{C}}$. The character table of $G$ is
typically represented as a matrix whose $i$-th row is the evaluation vector
$(\chi_{i}(\mathcal{C}_{1}),\dots,\chi_{i}(\mathcal{C}_{h})).$ With this
notation, we interpret as the embedding of the character $\chi_{i}$ in the
product ring, under the injection

$\mathfrak{R}(G)\longrightarrow\mathfrak{R}(G)/\mathfrak{m}_{\mathcal{C}_{1}}\times\cdots\times\mathfrak{R}(G)/\mathfrak{m}_{\mathcal{C}_{h}}.$

######  Lemma 4.

The image of the homomorphism
$\mathfrak{R}(G)\rightarrow\mathfrak{R}(G)/\mathfrak{m}_{\mathcal{C}_{1}}\times\cdots\times\mathfrak{R}(G)/\mathfrak{m}_{\mathcal{C}_{h}}$
has finite index in its codomain.

###### Proof.

Clearly $\mathfrak{R}(G)$ is torsion-free, since the image of a virtual
character is a subring of $\mathbb{C}$. Thus $\mathfrak{R}(G)$ embeds in
$\mathfrak{R}(G)\otimes\mathbb{Q}$, which is an étale algebra, and
$\mathfrak{R}(G)/\mathfrak{m}_{\mathcal{C}_{i}}\otimes\mathbb{Q}$ its
component fields (see Brakenhoff [3] for details). It follows that the index
is finite. ∎

More generally in the direction of the Lemma, Brakenhoff [3] finds that the
center of the group ring $\mathbb{Q}[G]$ over $\mathbb{Q}$ and the tensor
product of the representation ring $\mathfrak{R}(G)\otimes\mathbb{Q}$ are
related by Brauer equivalence. We give two examples below. In view of the
restriction map from $\mathfrak{R}({\mathcal{S}}_{n})$ to $\mathfrak{R}(G)$,
and since all characters on ${\mathcal{S}}_{n}$ are rational, the image of
$\mathfrak{R}({\mathcal{S}}_{n})=\mathfrak{R}_{\mathbb{Q}}({\mathcal{S}}_{n})$
lies in the subring $\mathfrak{R}_{\mathbb{Q}}(G)\subset\mathfrak{R}(G)$. In
the examples below, we illustrate the role of nontrivial Galois action and of
quadratic characters in failure of surjectivity of
$\mathfrak{R}({\mathcal{S}}_{n})$ on $\mathfrak{R}(G)$ and on
$\mathfrak{R}_{\mathbb{Q}}(G)$. In the next section we exploit the embedding
by interpolating the character table values by the polynomial presentation
$\mathbb{Z}[s_{1},\dots,s_{n-1}]\rightarrow\mathfrak{R}_{\mathbb{Q}}(G)$.

#### Orthogonality relations.

The role of arithmetic statistics of $G$ comes from the orthogonality
relations for the irreducible characters. Let $\\{\chi_{1},\dots,\chi_{h}\\}$
be the irreducible characters for $G$, and $A(G)$ be the character matrix:

$A(G)=\left[\begin{array}[]{ccc}\chi_{1}(\mathcal{C}_{1})&\cdots&\chi_{1}(\mathcal{C}_{h})\\\
\vdots&&\vdots\\\
\chi_{h}(\mathcal{C}_{1})&\cdots&\chi_{h}(\mathcal{C}_{h})\end{array}\right]$

The orthogonality relations for characters (see Serre [17, Section 2.3]),
expressed in terms of group elements, reformulated in terms of conjugacy
classes, takes the form

$\delta_{ij}=\langle\chi_{i},\chi_{j}\rangle_{G}:=\frac{1}{|G|}\sum_{g\in
G}\chi_{i}(g)\overline{\chi_{j}(g)}=\sum_{k=1}^{h}\frac{|\mathcal{C}_{k}|}{|G|}\chi_{i}(\mathcal{C}_{k})\overline{\chi_{j}(\mathcal{C}_{k})}.$

Set $D(G)$ to be the diagonal matrix with diagonal entries
$(p_{1},\dots,p_{h})$, where $p_{k}=|\mathcal{C}_{k}|/|G|$ is the weight of
the conjugacy class $\mathcal{C}_{k}$. The orthogonality relations are then
expressed by the equality

$I_{h}=A(G)D(G)A(G)^{\dagger},$

where $\dagger$ denotes the conjugate transpose. The matrix $D(G)$ can be
viewed as the inner product matrix of the Haar measure induced by $G$ on
${\mathcal{C}\\!\ell}(G)$.

#### Rational character table.

Let $\chi$ be a character on $G$, let $m$ be the exponent of $G$, and let
$\mathcal{C}=\mathcal{C}(g)$ be a conjugacy class. As the trace of a
representation of $g$, the value $\chi(\mathcal{C})$ lies in
$\mathbb{Z}[\zeta_{m}]$, since each of its eigenvalues are in
$\boldsymbol{\mu}_{m}=\langle\zeta_{m}\rangle$. We thus obtain two actions of
the Galois group
$\mathrm{Gal}(\mathbb{Q}(\zeta_{m})/\mathbb{Q})\cong(\mathbb{Z}/m\mathbb{Z})^{*}$.
Denote
$\sigma:(\mathbb{Z}/m\mathbb{Z})^{*}\rightarrow\mathrm{Gal}(\mathbb{Q}(\zeta_{m})/\mathbb{Q})$
the isomorphism such that $\zeta_{m}^{\sigma(k)}=\zeta_{m}^{k}$. The first of
the actions is on conjugacy classes, by
$\mathcal{C}(g)\mapsto\mathcal{C}(g^{k})$, and the second on characters by
$\chi^{\sigma(k)}(\mathcal{C}(g))=\chi(\mathcal{C}(g))^{\sigma(k)}$.
Considering the action on eigenvalues we see immediately that

$\chi^{\sigma(k)}(\mathcal{C}(g))=\chi(\mathcal{C}(g^{k})).$

#### Restriction from $\mathfrak{R}({\mathcal{S}}_{n})$.

Only characters in the image of $\mathfrak{R}({\mathcal{S}}_{n})$ can be
parametrized by polynomials in $\mathbb{Z}[s_{1},\dots,s_{n-1}]$ from the
standard representation. We note by example, that the pre-image of
$\mathcal{C}$ in ${\mathcal{C}\\!\ell}({\mathcal{S}}_{n})$ under the induced
map
${\mathcal{C}\\!\ell}(G)\rightarrow{\mathcal{C}\\!\ell}({\mathcal{S}}_{n})$
can split into an even number of conjugacy class separated by a quadratic
character not coming from ${\mathcal{S}}_{n}$. We observe this phenomenon for
$G=D_{4}$ and $G=Q_{8}$ in the examples section below.

##  4\. Algorithms for Galois representations

In what follows we describe algorithms for testing equivalence of finite
Galois characters. As principal application, we consider input $f(x)$ of
degree $n$, determining a number field $K=\mathbb{Q}[x]/(f(x))$, and describe
how to evaluate a sample set of primes $S$ at characters on the permutation
group $\mathcal{G}(K)$. The approach is completely general, allowing one to
compare the set of characters on the absolute group $\mathcal{G}$ mapping
through permutation groups $\mathcal{G}(K_{1})$ and $\mathcal{G}(K_{2})$
determined by number fields $K_{1}$ and $K_{2}$.

### Factorization types of irreducible polynomials

Consider an irreducible polynomial $f(x)$ in $\mathbb{Z}[x]$ of degree $n$,
set $K=\mathbb{Q}[x]/(f(x))$ and let $L$ be its normal closure with maximal
order $\mathcal{O}_{L}$. For a rational prime $p$ and prime $\mathfrak{P}$
over $p$ in $\mathcal{O}_{L}$, the Frobenius lift
$\mathrm{Frob}_{\mathfrak{P}}$ is the unique element of the decomposition
subgroup $D_{\mathfrak{P}}\subset G=\mathcal{G}(K)$, such that

$\mathrm{Frob}_{\mathfrak{P}}(a)\equiv a^{p}\bmod\mathfrak{P}$

for all $a$ in $\mathcal{O}_{L}$. Denote by $\mathrm{Frob}_{p}$ the conjugacy
class of $\mathrm{Frob}_{\mathfrak{P}}$ in ${\mathcal{C}\\!\ell}(G)$.

For $p$ not dividing $\mathrm{disc}(f(x))$ we define the factorization type of
$f(x)\bmod p$ to be the multiset of degrees of the factorization of $f(x)$ in
$\mathbb{F}_{p}[x]$, which we may denote $(d_{1},\dots,d_{t})$, where
$d_{1}\leq\cdots\leq d_{t}$ and $d_{1}+\cdots+d_{t}=n$. We can now identify
the data of the factorization type with the cycle type of the Galois group
$G=\mathcal{G}(K)$ equipped with its embedding in ${\mathcal{S}}_{n}$.

######  Lemma 5.

The factorization type of $f(x)\bmod p$ is the cycle type of
$\mathrm{Frob}_{p}\subset\mathcal{G}(K)$.

###### Proof.

The factorization $p\mathcal{O}_{K}=\mathfrak{p}_{1}\cdots\mathfrak{p}_{t}$ is
determined from $f(x)\equiv f_{1}(x)\cdots f_{t}(x)\bmod p$, with
$\mathfrak{p}_{k}=(p,f_{k}(x))$ a prime of degree $d_{k}=\deg(f_{k})$. The
Galois group acts transitively on primes of $\mathcal{O}_{L}$ over $p$, and
there exist conjugates $\mathfrak{P}_{1},\dots,\mathfrak{P}_{t}$ over
$\mathfrak{p}_{1},\dots,\mathfrak{p}_{t}$, from which we see that $d_{k}$
divides $\deg(\mathfrak{P})$, and each $d_{k}$ is the cardinality of an orbit
of roots modulo $p$ under the action of $\mathrm{Frob}_{\mathfrak{P}}$. ∎

### Character inner products as expectation.

The factorization type of a polynomial gives a means of taking random samples
of character values $(s_{1},\dots,s_{n-1})$ at a set $S$ of primes mapping to
the group $G$. Other data, for particular characters, may come from weight one
modular eigenforms, character sums, or Kronecker symbols. Let $S$ be such a
sample set of primes, and $\psi$, $\chi$ two characters which can be evaluated
on $S$. We write $\psi(p)$ and $\chi(p)$ for the value of the character at a
sample point. We obtain an approximation for the orthogonal product
$\langle\psi,\chi\rangle$ as the expectation of $\psi\overline{\chi}$:

$\langle\psi,\chi\rangle=\mathrm{E}(\psi\overline{\chi})\sim\mathrm{E}_{S}(\psi\overline{\chi})=\frac{1}{|S|}\sum_{p\in
S}\psi(p)\overline{\chi}(p).$

Assuming the multiplicity of each irreducible character in the support of
$\psi$ and $\chi$ is one, then $m=\langle\psi,\chi\rangle$ is an integer
counting the number of irreducible characters in the support of both $\psi$
and $\chi$. When $\psi$ and $\chi$ are irreducible, to determine equality
$\psi=\chi$, one needs only sufficient precision to distinguish the one bit
$\langle\psi,\chi\rangle=0$ or $\langle\psi,\chi\rangle=1$.

The interest in working with irreducible characters, or nearly irreducible
characters as captured by the image of restriction from
$\mathfrak{R}({\mathcal{S}}_{n})$, is that the variance of the character
products $\psi\overline{\chi}$ is minimized, and the number of primes needed
to recognize convergence small, as observed by Shieh [18, 19] in the case of
symplectic groups $\mathrm{USp}(2m)$ (see also Fité and Guitart [8]).

One should note that in view of classifying the Galois group, nonvanishing of
an element of the kernel ideal of the restriction
$\mathfrak{R}({\mathcal{S}}_{n})\rightarrow\mathfrak{R}(G)$ can be used to
provably exclude $G$ as a Galois group. This was already observed by Pohst
[15], who proposed the use of factorization types as a lower bound for the
Galois group, and that for $n\geq 8$ the factorization types, and their
probabilities, fail to separate groups. This statement, however, concerns the
data of the induced Haar measure on ${\mathcal{C}\\!\ell}(G)$, and not that of
the character table of $G$. Precisely we have two data structures on
${\mathcal{C}\\!\ell}(G)$ at our disposal, that of a probability space and of
class functions (given by a character table):

  * •

${\mathcal{C}\\!\ell}(G)$ with Haar measure
$p:{\mathcal{C}\\!\ell}(G)\rightarrow\mathbb{R}$, and

  * •

$\mathbb{C}^{h}=\mathrm{Hom}({\mathcal{C}\\!\ell}(G),\mathbb{C})$ with
orthonormal basis $\\{\chi_{1},\dots,\chi_{h}\\}$.

Due to failure of surjectivity of the restriction homomorphism from
$\mathfrak{R}({\mathcal{S}}_{n})$, the subset of characters determined from
the cycle types are unlikely to separate groups for sufficiently large $n$.
Nevertheless, the joint data of Haar measure and character table, plus the
system of restriction maps coming from common embeddings in
${\mathcal{S}}_{n}$ gives more information than either the Haar measure or
character table alone.

### Restriction kernel ideal

To a conjugacy class $\mathcal{C}$ for ${\mathcal{S}}_{n}$ we associate an
ideal $\mathfrak{m}_{\mathcal{C}}$ in $\mathbb{Z}[s_{1},\dots,s_{n-1}]$ of the
form

$\mathfrak{m}_{\mathcal{C}}=(s_{1}-s_{1}(\mathcal{C}),\dots,s_{n-1}-s_{n-1}(\mathcal{C})),$

where $(s_{1}(\mathcal{C}),\dots,s_{n-1}(\mathcal{C}))$ are the values of
$s_{i}$ at $\mathcal{C}$. Then the kernel ideal for the restriction of
$\mathfrak{R}({\mathcal{S}}_{n})$ to $\mathfrak{R}(G)$ is the intersection
ideal

$I(G)=\bigcap_{\mathcal{C}\in\pi({\mathcal{C}\\!\ell}(G))}\mathfrak{m}_{\mathcal{C}},$

where
$\pi:{\mathcal{C}\\!\ell}(G)\rightarrow{\mathcal{C}\\!\ell}({\mathcal{S}}_{n})$.

#### Example.

Consider the restriction from $\mathfrak{R}(O(3))$ to
$\mathfrak{R}({\mathcal{S}}_{4})$. Since

$\mathfrak{R}(O(3))=\frac{\mathbb{Z}[s_{1},s_{2},s_{3}]}{(s_{1}s_{3}-s_{2},s_{3}^{2}-1)}$

and the values of $(s_{1},s_{2},s_{3})$ are in

$\\{(3,3,1),\ (-1,-1,1),\ (0,0,1),\ (-1,1,-1),\ (1,-1,-1)\\},$

we obtain a defining ideal of ${\mathcal{S}}_{4}$ given by the additional
generators:

$s_{1}(s_{1}+1)(s_{1}-s_{3}-2),\ s_{1}(s_{1}+1)(s_{1}-1)(s_{1}-3),\
(s_{1}+1)(s_{1}-1)(s_{3}-1).$

The map
${\mathcal{C}\\!\ell}(D_{4})\rightarrow{\mathcal{C}\\!\ell}({\mathcal{S}}_{4})$
fails to surject on $(0,0,1)$, hence there are only four maximal ideals in the
intersection and the kernel ideal for
$\mathfrak{R}({\mathcal{S}}_{4})\rightarrow\mathfrak{R}(D_{4})$ is generated
by:

$s_{1}^{2}-s_{1}-s_{2}-s_{3}-2,\ s_{2}-s_{1}s_{3},\ s_{3}^{2}-1.$

The first polynomial is not in the kernel ideal for
$\mathfrak{R}({\mathcal{S}}_{4})$ and its vanishing provides a test for
$D_{4}$. Geometrically, it means that the tensor square of the representation
with trace $s_{1}$ decomposes into a direct sum of representations with trace
$s_{1}+s_{2}+s_{3}+2$.

### Restriction homomorphism

Let $H\subset G$ be permutation groups, and set
$\ell=|{\mathcal{C}\\!\ell}(H)|$ and $h=|{\mathcal{C}\\!\ell}(G)|$ their
cardinalities of their conjugacy class sets. Suppose that
$\\{\psi_{1},\dots,\psi_{\ell}\\}$ and $\\{\chi_{1},\dots,\chi_{h}\\}$ are the
irreducible characters, which are given by embeddings in $\mathbb{C}^{\ell}$
and $\mathbb{C}^{h}$, respectively. We thus have isomorphisms

$\mathfrak{R}(H)=\bigoplus_{i=1}^{\ell}\mathbb{Z}\psi_{i}\longrightarrow\Lambda(H)\subset\mathbb{C}^{\ell},\mbox{
and
}\mathfrak{R}(G)=\bigoplus_{j=1}^{h}\mathbb{Z}\chi_{j}\longrightarrow\Lambda(G)\subset\mathbb{C}^{h},$

where $\Lambda(H)$ and $\Lambda(G)$ are the lattices in $\mathbb{C}^{\ell}$
and $\mathbb{C}^{h}$ spanned by the rows of the character table. The
restriction homomorphism $\mathfrak{R}(G)\mapsto\mathfrak{R}(H)$ is induced by
the map $\pi:{\mathcal{C}\\!\ell}(H)\rightarrow{\mathcal{C}\\!\ell}(G)$, by

$\chi\longmapsto(\chi(\pi(\mathcal{C}_{1})),\dots,\chi(\pi(\mathcal{C}_{\ell})))\in\Lambda(H)\subset\mathbb{C}^{\ell}.$

The linear transformation $\Lambda(G)\rightarrow\Lambda(H)$ gives the
restriction homomorphism as an integral $(h\times\ell)$-matrix with respect to
the respective bases of irreducible characters. The rows of this matrix can be
interpretted as branching rules, giving the decomposition of an irreducible
character on $G$ as a sum of irreducible characters on $H$.

Inside each $\Lambda(G)$ we have a sublattice (generally of lower rank)
$\Lambda_{\mathbb{Q}}(G)=\Lambda(G)\cap\mathbb{Q}^{h}$ of rational-valued
characters. We recall that for a conjugacy class $\mathcal{C}$ of group
elements of order $m$, the value of $\chi(\mathcal{C})$ is a sum of
eigenvalues in $\mathbb{Q}(\zeta_{m})$. We thus obtain an action by the Galois
group of a cyclotomic field on the irreducible characters. As a consequence,
the lattice $\Lambda_{\mathbb{Q}}(G)$ is generated by the sums over Galois
orbits of irreducible characters. Since these orbits are disjoint, this basis
of rational characters remains orthogonal, but not orthonormal, since
$\langle\chi,\chi\rangle$ measures the cardinality of the orbit (assuming
$\chi$ is a sum of irreducible characters of multiplicity one). On the other
hand, the restriction images
$\mathrm{Res}^{G}_{H}(\Lambda(G))\subset\Lambda(H)$ and
$\mathrm{Res}^{G}_{H}(\Lambda_{\mathbb{Q}}(G))\subset\Lambda_{\mathbb{Q}}(H)$
do not possess natural reduced orthogonal bases. In order to determine a
generating set which is small with respect to the orthogonality relations on
characters, we need to apply a constrained lattice reduction inside the
submonoid of characters:

$\bigoplus_{j=1}^{\ell}\mathbb{N}\psi_{j}\subset\bigoplus_{j=1}^{\ell}\mathbb{Z}\psi_{j}=\mathfrak{R}(H).$

Rather than a generic LLL algorithm, we need to carry out a structured lattice
reduction in the character monoid order to be able to invoke the heuristic
arguments for convergence of small characters.

### Algebraic parametrization

In order to interpret factorization types of polynomials (or splitting types
of primes) as conjugacy classes on which we can apply the class functions
$s_{1},\dots,s_{n-1}$, we need to find an explicit algebraic parametrization

$\frac{\mathbb{Z}[s_{1},\dots,s_{n-1}]}{I({\mathcal{S}}_{n})}\rightarrow\mathfrak{R}({\mathcal{S}}_{n})\rightarrow\mathrm{Res}^{{\mathcal{S}}_{n}}_{G}(\Lambda({\mathcal{S}}_{n}))\subseteq\Lambda(G)$

The presentation
$\mathbb{Z}[s_{1},\dots,s_{n-1}]/I({\mathcal{S}}_{n})\rightarrow\mathfrak{R}({\mathcal{S}}_{n})$
comes from the standard representation of ${\mathcal{S}}_{n}$, and its
composition into $\Lambda({\mathcal{S}}_{n})$ can be effectively computed. In
order to lift characters in $\Lambda({\mathcal{S}}_{n})$ back to
representative polynomials in $(s_{1},\dots,s_{n-1})$, we must invert

$\frac{\mathbb{Z}[s_{1},\dots,s_{n-1}]}{I({\mathcal{S}}_{n})}\rightarrow\Lambda({\mathcal{S}}_{n}).$

As noted above, the isomorphism
$\mathfrak{R}({\mathcal{S}}_{n})\rightarrow\Lambda({\mathcal{S}}_{n})$ is
obtained by the Chinese remainder theorem. More precisely, over $\mathbb{Q}$,
we obtain a product decomposition of the étale algebra
$\mathfrak{R}({\mathcal{S}}_{n})\otimes\mathbb{Q}$:

$\mathfrak{R}({\mathcal{S}}_{n})\otimes\mathbb{Q}\longrightarrow\frac{\mathfrak{R}({\mathcal{S}}_{n})}{\mathfrak{m}_{\mathcal{C}_{1}}}\otimes\mathbb{Q}\times\cdots\times\frac{\mathfrak{R}({\mathcal{S}}_{n})}{\mathfrak{m}_{\mathcal{C}_{h}}}\otimes\mathbb{Q}\cong\mathbb{Q}^{h}.$

under which
$\mathfrak{R}({\mathcal{S}}_{n})\cong\Lambda({\mathcal{S}}_{n})\subseteq\mathbb{Z}^{h}$.
Since the generators $s_{1},\dots,s_{n-1}$ can be evaluated at conjugacy
classes, we can evaluate a basis of monomials modulo $I({\mathcal{S}}_{n})$
and invert a matrix to determine the pre-image of a basis of irreducible
characters. The same applies to a basis of characters in
$\mathrm{Res}^{{\mathcal{S}}_{n}}_{G}(\Lambda({\mathcal{S}}_{n}))$ modulo the
restriction kernel $I(G)$.

### Database of restriction-induction

Databases of transitive permutation groups of degree up to 30 are available in
GAP [9] and Magma [2, 14], computed by Greg Butler, John McKay, Gordon Royle
and Alexander Hulpke (see [5], [6], [16], [7], [11]). The above is intended to
motivate an interest in a metastructure of the restriction relations (and
adjoint induction relations) between character rings $\mathfrak{R}(G)$, and
for the algebraic parametrizations arizing from the restriction homomorphism
from orthogonal groups.

##  5\. Explicit computations

We illustrate the approach through arithmetic statistics of character theory
by applying the methods to groups of low degree. First we analyze the dihedral
and quaternionic groups $D_{4}$ and $Q_{8}$ of order $8$, the smallest groups
sharing the same character table. Then we consider an example of a pair of
permutation groups of degree $8$ and order $16$ whose cycle types and induced
Haar measure on ${\mathcal{S}}_{8}$-conjugacy classes are equal. We show how
an auxillary (sub)field suffices to distinguish the characters using joint
Frobenius cycle data. In a final example, we treat different permutation
representations of ${\mathcal{A}}_{5}$, to show how this approach can be used
to establish the equivalence of the absolute Galois representations determined
by different fields.

### Dihedral and quaternionic groups of order $8$

The groups $D_{4}$ and $Q_{8}$, known to share the same character table, can
nevertheless be separated by the restriction data coming from a permutation
representation. We first recall that the common character table takes the form

$A(G)=\left[\begin{array}[]{@{\;}r@{\;}r@{\;}r@{\;}r@{\;}r@{\;}}1&1&1&1&1\\\
1&1&-1&1&-1\\\ 1&1&1&-1&-1\\\ 1&1&-1&-1&1\\\ 2&-2&0&0&0\end{array}\right]$

with weights $(1/8,1/8,1/4,1/4,1/4)$ on the conjugacy classes. The
semisemimple group algebras $\mathbb{Q}[D_{4}]$ and $\mathbb{Q}[Q_{8}]$ have
Wedderburn decompositions

$\mathbb{Q}[D_{4}]\cong\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}\times
M_{2}(\mathbb{Q}),\mbox{ and
}\mathbb{Q}[Q_{8}]\cong\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}\times\mathbb{H},$

where $\mathbb{H}$ is the quaternion algebra over $\mathbb{Q}$ ramified at $2$
and $\infty$. These decompositions correspond to the four linear characters
and sole degree-2 irreducible representation.

Only the former group, $D_{4}$, embeds in ${\mathcal{S}}_{4}$, which shows
that the permutation embedding contains distinguishing information not in the
character table. We make explicit the above approach through character theory
for the degree-$4$ permutation representation. Let
$\\{1,\chi_{1},\chi_{2},\chi_{3},\chi_{4}\\}$ be a basis of characters, with
$\chi_{1}$, $\chi_{2}$, and $\chi_{3}=\chi_{1}\chi_{2}$ quadratic linear
characters, and $\chi_{4}$ of degree $2$. The standard representation of
${\mathcal{S}}_{4}$ in $\mathrm{O}(3)$ provides irreducible characters

$\\{1,s_{1},s_{2},s_{3},s_{1}^{2}-s_{1}-s_{2}-1\\}$

where $s_{3}$ is the quadratic determinant character, $s_{1}$ and
$s_{2}=s_{1}s_{3}$ are degree-$3$ representations, and the last one is of
degree $2$. Computing the inner product matrices for these characters on
${\mathcal{S}}_{4}$ and $D_{4}$, we obtain

$\left[\begin{array}[]{@{\;}c@{\;\;}c@{\;\;}c@{\;\;}c@{\;\;}c@{\;}}1&0&0&0&0\\\
0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\ 0&0&0&0&1\end{array}\right]\mbox{ and
}\left[\begin{array}[]{@{\;}c@{\;\;}c@{\;\;}c@{\;\;}c@{\;\;}c@{\;}}1&0&0&0&1\\\
0&2&1&0&0\\\ 0&1&2&0&0\\\ 0&0&0&1&1\\\ 1&0&0&1&2\end{array}\right]\\!\cdot$

For example, this was the output to the nearest integer for the expectation
method on a sample size of 16 unramified primes, for the polynomials
$x^{4}+x+1$ and $x^{4}-2x^{2}+2$ with respective Galois groups
${\mathcal{S}}_{4}$ and $D_{4}$.

One identifies the polynomial expression $\chi=s_{1}^{2}-s_{1}-s_{2}-1$ for
the irreducible degree-$2$ character $\chi$ on ${\mathcal{S}}_{4}$, which
decomposes into a direct sum $1+s_{3}$ on $D_{4}$, from which we deduce that
$s_{1}^{2}-s_{1}-s_{2}-s_{3}-2$ is in the kernel ideal $I(D_{4})$. Similarly,
we read from the inner products
$\langle{s_{1},s_{1}}\rangle=\langle{s_{2},s_{2}}\rangle=2$ and
$\langle{s_{1},s_{2}}\rangle=1$ on $D_{4}$ that each of $s_{1}$ and $s_{2}$
decompose into two irreducible characters, which share a common irreducible
summand. The restriction homomorphism from $\mathfrak{R}({\mathcal{S}}_{4})$
thus captures

$1,s_{1}=\chi_{1}+\chi_{4},s_{2}=\chi_{2}+\chi_{4},s_{3}=\chi_{3}.$

The restriction fails to span all characters, because the conjugacy classes
are not separated by characters on ${\mathcal{S}}_{4}$. Indeed the cycle types
of the five conjugacy classes in ${\mathcal{C}\\!\ell}(D_{4})$ are $1^{4}$,
$1^{2}2^{1}$, $2^{2}$, $2^{2}$, and $4^{1}$, and hence the two classes of
cycle type $2^{2}$ map to the same class in
${\mathcal{C}\\!\ell}({\mathcal{S}}_{4})$.

The missing character $\chi_{1}$ is easily recovered. It arises from the
quadratic subfield (here with defining polynomial $x^{2}-2x+2$), which can be
expressed as a Legendre symbol. In terms of the basis of characters
$\\{1,s_{1},s_{2},s_{3},\chi_{1}\\}$, we now obtain an inner product matrix:

$\left[\begin{array}[]{cccc|c}1&0&0&0&0\\\ 0&1&0&0&0\\\ 0&0&2&1&1\\\
0&0&1&2&0\\\ \hline\cr 0&0&1&0&1\end{array}\right]$

which can be reduced to an orthonormal basis for $\mathfrak{R}(D_{4})$.

Since both $D_{4}$ and $Q_{8}$ admit permutation representations of degree
$8$, we carry out a similar analysis of the permutation representations of
degree $8$ for $D_{4}$ and $Q_{8}$, given by

$D_{4}\cong\left\langle\begin{array}[]{@{}l@{}}(1,8)(2,7)(3,4)(5,6),\\\
(1,2)(3,5)(4,6)(7,8),\\\ (1,6)(2,4)(3,8)(5,7)\end{array}\right\rangle\mbox{
and }Q_{8}\cong\left\langle\begin{array}[]{@{}l@{}}(1,2,4,7)(3,6,8,5),\\\
(1,3,4,8)(2,5,7,6)\end{array}\right\rangle\cdot$

The cycle types $1^{8}$, $2^{4}$, $4^{2}$ arise with probabilities
$(1/8,5/8,1/4)$ in $D_{4}$ whereas in $Q_{8}$, theses same types have
probabilities $(1/8,1/8,3/4)$. Both groups embed in
${\mathcal{A}}_{8}\subset\mathrm{SO}(7)$, hence the character rings are
parametrized by
$\mathfrak{R}(\mathrm{SO}(7))\cong\mathbb{Z}[s_{1},s_{2},s_{3}]$ ($s_{7}=1$
and $s_{4}=s_{3}$, $s_{5}=s_{2}$, $s_{6}=s_{1}$). Since the cycle types are
the same, the kernel ideals agree, but the Haar measures differentiate the
groups. However, a naive tabulation of the probabilities gives a poor
empirical invariant. In fact, computing these probabilities is tantamount to
evaluating the expectations of the idempotents $e_{1}$, $e_{2}$, $e_{3}$ under
the isomorphism

$\mathfrak{R}(G)\otimes\mathbb{Q}=\frac{\mathbb{Q}[s_{1},s_{2},s_{3}]}{I(G)\otimes\mathbb{Q}}\longrightarrow\frac{\mathfrak{R}(G)\otimes\mathbb{Q}}{\mathfrak{m}_{\mathcal{C}_{1}}\otimes\mathbb{Q}}\times\frac{\mathfrak{R}(G)\otimes\mathbb{Q}}{\mathfrak{m}_{\mathcal{C}_{2}}\otimes\mathbb{Q}}\times\frac{\mathfrak{R}(G)\otimes\mathbb{Q}}{\mathfrak{m}_{\mathcal{C}_{3}}\otimes\mathbb{Q}}\cong\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}.$

To express this computation in the character ring framework, we scale by the
group order to have integer values. As a general strategy for a group
$G\subset{\mathcal{S}}_{n}$ this amounts to asking whether the scaled
idempotents converge to

$(\langle|G|e_{1},1\rangle,\dots\langle|G|e_{s},1\rangle)=(|\mathcal{C}_{1}|,\dots,|\mathcal{C}_{s}|),$

where $\mathcal{C}_{i}$ are the ${\mathcal{S}}_{n}$-conjugacy classes for $G$.

Let $\\{1,\chi_{1},\chi_{2},\chi_{3},\psi\\}$ be a basis of irreducible
characters for $D_{4}$, and
$\\{1,\chi_{1}^{\prime},\chi_{2}^{\prime},\chi_{3}^{\prime},\psi^{\prime}\\}$
be a basis of irreducible characters for $Q_{8}$. The parametrization gives a
$\mathbb{Q}$-basis $\\{1,s_{1},s_{2}\\}$ and an idempotent basis
$\\{e_{1},e_{2},e_{3}\\}$ which are characteristic functions for the
evaluations on conjugacy classes. A reduced basis for the image of
$\mathfrak{R}({\mathcal{S}}_{8})$ in $\mathfrak{R}(D_{4})$ is
$\\{1,\sigma_{1},\sigma_{2}\\}$, described as follows in these respective
bases:

$\begin{array}[]{cccc}D_{4}&\\{1,s_{1},s_{2}\\}&\\{e_{1},e_{2},e_{3}\\}&\\{1,\chi_{1},\chi_{2},\chi_{3},\psi\\}\\\
\hline\cr 1&1&e_{1}+e_{2}+e_{3}&1\\\
\sigma_{1}&-s_{1}+s_{2}/2-1/2&2e_{1}-e_{2}+e_{3}&\chi_{1}+\psi\\\
\sigma_{2}&2s_{1}-s_{2}/2+1/2&4e_{1}-2e_{3}&\chi_{1}+\chi_{2}+\chi_{3}\end{array}$

Similarly, a reduced basis for the image of $\mathfrak{R}({\mathcal{S}}_{8})$
in $\mathfrak{R}(Q_{8})$ is $\\{1,\tau_{1},\tau_{2}\\}$, expressed in the
respective bases as follows:

$\begin{array}[]{cccc}Q_{8}&\\{1,s_{1},s_{2}\\}&\\{e_{1},e_{2},e_{3}\\}&\\{1,\chi_{1}^{\prime},\chi_{2}^{\prime},\chi_{3}^{\prime},\psi^{\prime}\\}\\\
\hline\cr 1&1&e_{1}+e_{2}+e_{3}&1\\\
\tau_{1}&-s_{1}+s_{2}/2-3/2&2e_{1}-2e_{2}&\psi^{\prime}\\\
\tau_{2}&3s_{1}-s_{2}+3&3e_{1}+3e_{2}-e_{3}&\chi_{1}^{\prime}+\chi_{2}^{\prime}+\chi_{3}^{\prime}\end{array}$

Relative to the parametrizations from $\mathfrak{R}(\mathrm{SO}(7))$, the
bases $(\sigma_{1},\sigma_{2})$ and $(\tau_{1},\tau_{2})$ are related by
$(\sigma_{1},\sigma_{2})=(\tau_{1}+1,\tau_{1}+\tau_{2}-1)$, and inversely
$(\tau_{1},\tau_{2})=(\sigma_{1}-1,\sigma_{1}+\sigma_{2}+2)$. we thus express
$(8e_{1},8e_{2},8e_{3}$ in the respective bases:

$\begin{array}[]{cccc}&\\{1,s_{1},s_{2}\\}&\\{1,\sigma_{1},\sigma_{2}\\}&\\{1,\tau_{1},\tau_{2}\\}\\\
\hline\cr 8e_{1}&s_{1}+1&1+\sigma_{1}+\sigma_{2}&1+2\tau_{1}+\tau_{2}\\\
8e_{2}&5s_{1}-2s_{2}+7&5-3\sigma_{1}+\sigma_{2}&1-2\tau_{1}+\tau_{2}\\\
8e_{3}&-6s_{1}+2s_{2}&2+2\sigma_{1}-2\sigma_{2}&6-2\tau_{2}\end{array}$

giving inclusions of submodules
$\langle{8e_{1},8e_{2},8e_{3}}\rangle\subset\langle{1,\sigma_{2},\sigma_{3}}\rangle=\langle{1,\tau_{2},\tau_{3}}\rangle\subset\langle{e_{1},e_{2},e_{3}}\rangle$.

Computing the expectations of the test functions
$\\{1,\sigma_{1},\sigma_{2}\\}$, for $D_{4}$ on polynomials with Galois groups
$G=D_{4}$ or $Q_{8}$, the Gram matrix
$M(G)=(\mathrm{E}(\sigma_{i}\sigma_{j}))$ ($\sigma_{0}=1$) takes the form

$M(G)=\left[\begin{array}[]{@{\;}c@{\;\;}c@{\;\;}c@{\;}}1&0&0\\\ 0&2&1\\\
0&1&3\end{array}\right]\mbox{ where }G=D_{4}\mbox{ and otherwise
}\left[\begin{array}[]{@{}r@{\;\;\;}r@{\,}r@{\;}}1&1&-1\\\ 1&2&0\\\
-1&0&5\end{array}\right]\\!\\!\cdot$

With respect to test functions $\\{1,\tau_{1},\tau_{2}\\}$ for $Q_{8}$, the
Gram matrices are

$M(G)=\left[\begin{array}[]{@{\;}c@{\;\;}c@{\;\;}c@{\;}}1&0&0\\\ 0&1&0\\\
0&0&3\end{array}\right]\mbox{ where }G=Q_{8}\mbox{ and otherwise
}\left[\begin{array}[]{@{}r@{\,}r@{\,}r@{\;}}1&-1&2\\\ -1&3&-3\\\
2&-3&7\end{array}\right]\\!\\!\cdot$

It should be clear that the full Gram matrix gives a more complete picture of
the orthogonality relations of charactes than the triple of inner products
$(\langle{8e_{1},1}\rangle),(\langle{8e_{2},1}\rangle),(\langle{8e_{3},1}\rangle)$,
which is just one linear combination of the rows in the above Gram matrices.

In the next section, we show that the choice of reduced basis for the target
group gives a better set of test functions, converging more rapidly to the
asymptotic Gram matrix. With respect to the polynomials $x^{8}+6x^{4}+1$ of
Galois group $D_{4}$ and $x^{8}-12x^{6}+36x^{4}-36x^{2}+9$ of Galois group
$Q_{8}$, we obtain reasonably good convergence (to within a half integer) with
the first 80 primes.

### Non distinguished representations of degree $8$

The first example of nonisomorphic permutation representations not
distinguished by their cycle types and Haar measure are the degree-8 groups of
order $16$ denoted 8T10 and 8T11 (see the LMFDB [13] Galois groups database).
Specifically we define the representative groups

$\begin{array}[]{l}G_{0}=\langle{(1,2,3,8)(4,5,6,7),(1,5)(3,7)}\rangle\mbox{
and }\\\
G_{1}=\langle{(1,3,5,7)(2,4,6,8),(1,4,5,8)(2,3,6,7),(1,5)(3,7)}\rangle\end{array}$

whose character tables are given by

$A(G_{0})=\left[\begin{array}[]{@{\;}*{10}{r@{\,}}r@{\;}}1&1&1&1&1&1&1&1&1&1\\\
1&1&1&1&-1&-1&-1&-1&1&1\\\ 1&1&1&1&-1&-1&1&1&-1&-1\\\
1&1&1&1&1&1&-1&-1&-1&-1\\\ 1&-1&-1&1&1&-1&i&-i&-i&i\\\
1&-1&-1&1&-1&1&-i&i&-i&i\\\ 1&-1&-1&1&-1&1&i&-i&i&-i\\\
1&-1&-1&1&1&-1&-i&i&i&-i\\\ 2&-2&2&-2&0&0&0&0&0&0\\\
2&2&-2&-2&0&0&0&0&0&0\end{array}\right]\mbox{ and
}A(G_{1})=\left[\begin{array}[]{@{\;}*{10}{r@{\,}}r@{\;}}1&1&1&1&1&1&1&1&1&1\\\
1&1&1&1&-1&-1&1&-1&-1&1\\\ 1&1&-1&-1&-1&-1&-1&1&1&1\\\
1&1&-1&-1&1&1&-1&-1&-1&1\\\ 1&1&1&1&1&-1&-1&1&-1&-1\\\
1&1&1&1&-1&1&-1&-1&1&-1\\\ 1&1&-1&-1&-1&1&1&1&-1&-1\\\
1&1&-1&-1&1&-1&1&-1&1&-1\\\ 2&-2&-2i&2i&0&0&0&0&0&0\\\
2&-2&2i&-2i&0&0&0&0&0&0\end{array}\right]$

with respective probabilities $(1/16,1/16,1/16,1/16,1/8,1/8,1/8,1/8,1/8,1/8)$.
We note that the first 8 characters are linear, and the latter two are of
degree $2$. The linear characters admit a group structure, isomorphic to
$C_{2}\times C_{4}$ and $C_{2}^{3}$, respectively. We denote the characters by
$\\{1,\chi_{1},\chi_{2},\chi_{3},\rho_{1},\bar{\rho}_{1},\rho_{2},\bar{\rho}_{2},\psi_{1},\psi_{2}\\}\mbox{
and
}\\{1,\xi_{1},\xi_{2},\xi_{3},\xi_{4},\xi_{5},\xi_{6},\xi_{7},\psi,\bar{\psi}\\}.$
In the groups $G_{0}$ and $G_{1}$ the character of the standard representation
(of degree 7) decomposes as

$s_{1}=\chi_{1}+\rho_{1}+\bar{\rho}_{1}+\psi_{1}+\psi_{2}\mbox{ and
}s_{1}=\xi_{1}+\xi_{2}+\xi_{2}+\psi+\bar{\psi},$

respectively, but the individual characters in $s_{1}$ are not separated.

Given the obvious Galois action (on the codomain field $\mathbb{Q}(i)$), we
see that the subrings $\mathfrak{R}_{\mathbb{Q}}(G_{0})$ and
$\mathfrak{R}_{\mathbb{Q}}(G_{1})$ have different ranks, $8$ and $9$. On the
other hand, the images of the restriction homomorphism from
$\mathfrak{R}({\mathcal{S}}_{8})$ have rank $4$ in each of
$\mathfrak{R}(G_{0})$ and $\mathfrak{R}(G_{1})$, generated for instance by
$\\{1,s_{1},s_{2},s_{3}\\}$. Moreover, since exactly the same four cycle types
occur, with the same probabilities $(1/16,5/16,1/8,1/2)$, the characters in
the image of restriction from $\mathfrak{R}({\mathcal{S}}_{8})$ to
$\mathfrak{R}(G_{0})$ and $\mathfrak{R}(G_{1})$ can not be differentiated.

Let $K_{0}$ and $K_{1}$ be number fields whose normal closures have respective
Galois groups $G_{0}$ and $G_{1}$. In order to distinguish these fields, it
suffices to construct missing characters from the linear character groups. In
fact these number fields have nontrivial automorphism groups, isomorphic to
$V_{4}$ and $C_{4}$, respectively. This induces respective subfield lattices
of the forms

${K_{0}}$${K_{1}}$${F_{0}^{\prime}}$${F_{0}}$${F_{0}^{\prime\prime}}$${F_{1}}$${G_{0}}$${G_{1}^{\prime}}$${G_{1}}$${G_{1}^{\prime\prime}}$${\mathbb{Q}}$${\mathbb{Q}}$

For each field we recover a significant subgroup of the linear character
groups from the quartic and quadratic characters. In fact there is a unique
cyclic subfield $F_{0}/\mathbb{Q}$ in $K_{0}$ which recovers the characters
$\rho_{1}$, $\bar{\rho}_{2}$, and $\chi_{1}=\rho_{1}^{2}$. (The other fields
$F_{0}^{\prime}$ and $F_{0}^{\prime\prime}$ are non-normal.) And there exists
a unique biquadratic field $F_{1}/\mathbb{Q}$ in $K_{1}$ which yields the
quadratic characters $\xi_{1}$, $\xi_{2}$, $\xi_{3}$. The pairs
$(K_{0},F_{0})$ and $(K_{1},F_{1})$ give characters on the pairs of
permutation groups of degree $8$ and $4$, $(G_{0},G_{0}/H_{0}\cong C_{4})$ and
$(G_{1},G_{1}/H_{1}\cong V_{4})$, such that the joint factorization types of
Frobenius characters separate the Galois structures.

### Representations of ${\mathcal{A}}_{5}$

We denote the irreducible characters of the alternating groups
${\mathcal{A}}_{5}$ by $\\{1,\chi_{1},\chi_{2},\chi_{3},\chi_{4}\\}$, where
$\chi_{1}$ is the character of the degree-$4$ standard representation,
$\chi_{2}$ is the character of a degree-$5$ representation, and $\chi_{3}$ and
$\chi_{4}$ are the conjugate characters of degree-$3$ icosohedral
representations over $\mathbb{Q}(\sqrt{5})$. The rational representations are
thus spanned by the orthogonal characters
$\\{1,\chi_{1},\chi_{2},\chi_{3}+\chi_{4}\\}$ of degrees $1$, $4$, $5$, and
$6$.

On the other hand, the permutation representation of ${\mathcal{A}}_{5}$ in
${\mathcal{S}}_{5}$ gives a parametrization by

$\mathfrak{R}(\mathrm{SO}(4))=\frac{\mathbb{Z}[s_{1},s_{2},s_{3},s_{4}]}{(s_{1}-s_{3},s_{4}-1)}\cong\mathbb{Z}[s_{1},s_{2}],$

and while $|{\mathcal{C}\\!\ell}({\mathcal{A}}_{5})|=5$, there are two
conjugacy classes which map to the same cycle type $5^{1}$ in
${\mathcal{C}\\!\ell}({\mathcal{S}}_{5})$. Thus the restriction from
$\mathfrak{R}({\mathcal{S}}_{5})$ gives a basis of four independent
characters, and we identify:

$(1,s_{1},s_{1}^{2}-s_{2}-s_{1}-1,s_{2})=(1,\chi_{1},\chi_{2},\chi_{3}+\chi_{4}).$

In addition to its degree-$5$ permutation representation, ${\mathcal{A}}_{5}$
admits a faithful permutation representation in ${\mathcal{S}}_{6}$. In the
restriction of $\mathbb{Z}[s_{1},s_{2}]\cong\mathfrak{R}(\mathrm{SO}(5))$ we
recognize the same characters equipped with a different parametrization

$(1,s_{1}^{2}-2s_{1}-s_{2}-1,s_{1},s_{2}-\chi_{1})=(1,\chi_{1},\chi_{2},\chi_{3}+\chi_{4}).$

Consider the number fields, each with Galois group ${\mathcal{A}}_{5}$,
defined by polynomials

$\begin{array}[]{l}f=x^{5}-5x^{4}+48x^{3}+28x^{2}+5x-1,\\\
g=x^{6}+4x^{5}+10x^{4}-10x^{3}+17x^{2}+10x+1\end{array}$

constructed as subfields of the same normal closure. Although not isomorphic,
we can construct the inner product matrix of the same characters set
$\\{1,\chi_{1},\chi_{2},\chi_{3}+\chi_{4}\\}$ on ${\mathcal{A}}_{5}$ with
respect to its different embeddings in ${\mathcal{S}}_{5}$ and
${\mathcal{S}}_{6}$. Jointly evaluating the characters on factorization types
of $f$ or $g$ with those of either $f$ or $g$, yields the same diagonal inner
product matrix ($=\mathrm{diag}(1,1,1,2)$ to nearest integer). This gives a
means of recognizing the same character of the absolute Galois group via
different presentations. The arithmetic statistic approach through character
theory gives a powerful tool to not only characterize Galois groups, but to
recognize equivalence of finite representations of the absolute Galois group
$\mathcal{G}$ which may arise in different contexts.

##  6\. Variance, covariance and convergence

The focus on irreducible characters provides, on the one hand, a theoretic
framework for understanding the arithmetic statistics of Frobenius
distributions. On the computational side, irreducible characters provide test
functions with optimal convergence properties. Naively, the orthogonality
relations for a system $\\{\chi_{1},\dots,\chi_{r}\\}$ of irreducible
characters as test functions, it suffices to recognize the integer
$\langle\chi_{i},\chi_{j}\rangle=\delta_{ij}$ to one bit of precision.
Furthermore, $\chi_{i}\neq 1$ and $\chi_{j}\neq 1$ the inner products
$\langle\chi_{i},1\rangle=\langle\chi_{j},1\rangle=0$ imply that $\chi_{i}$
and $\chi_{j}$ have mean $0$, hence we can interpret

$\mathrm{E}_{S}(\chi_{i}\overline{\chi}_{j})=\frac{1}{|S|}\sum_{p\in
S}\chi_{i}(p)\overline{\chi}_{j}(p)$

as a (sample) variance ($i=j$) or covariance ($i\neq j$) of the sample $S$, we
see that the use of irreducible characters (or of reduced characters in
$\mathfrak{R}(G)$ as the next best approximation when irreducible characters
are not in the restriction image from $\mathfrak{R}({\mathcal{S}}_{n})$)
minimizes the variance of the test functions, and orthogonality minimizes the
covariance.

We can illustrate the convergence properties with the lattice of subgroups
between the representation of $\mathrm{PSL}_{2}(\mathbb{F}_{7})$ on
$\mathbb{P}^{1}(\mathbb{F}_{7})$ and ${\mathcal{S}}_{8}$:

${\mathrm{PGL}_{2}(\mathbb{F}_{7})\cong
G_{1}}$${{\mathcal{S}}_{8}}$${\mathrm{PSL}_{2}(\mathbb{F}_{7})\cong
H_{1}}$${H_{2}}$${{\mathcal{A}}_{8}}$

with respective orders $|H_{1}|=168$, $|G_{1}|=336$, and $|H_{2}|=1344$.

Let $h(G)$ be the number of conjugacy classes of $G$, equal to the number of
irreducible characters and to the rank of $\mathfrak{R}(G)$; let $r(G)$ be the
number of characters irreducible over $\mathbb{Q}$, equal to the rank of
$\mathfrak{R}_{\mathbb{Q}}(G)$; and let $s(G)$ the rank of the image of the
restriction of $\mathfrak{R}({\mathcal{S}}_{n})$ to $\mathfrak{R}(G)$. For
each of the groups we give the respective numbers $h(G)$, $r(G)$ and $s(G)$,
as well as a representative polynomial (from the LMFDB [13]) with Galois group
$G$.

$\begin{array}[]{ccccl}G&h(G)&r(G)&s(G)&f_{G}(x)\\\
\hline\cr{\mathcal{S}}_{8}&22&22&22&x^{8}-x-1\\\
{\mathcal{A}}_{8}&14&12&12&x^{8}-2x^{7}+3x^{5}-5x^{4}+2x^{3}+2x^{2}-x+1\\\
G_{1}&9&8&8&x^{8}-x^{7}+x^{6}+4x^{5}-x^{4}-3x^{3}+5x^{2}-2x+1\\\
H_{2}&11&10&8&x^{8}-4x^{7}+8x^{6}-9x^{5}+7x^{4}-4x^{3}+2x^{2}+1\\\
H_{1}&6&5&5&x^{8}-4x^{7}+7x^{6}-7x^{5}+7x^{4}-7x^{3}+7x^{2}+5x+1\\\
\end{array}$

For the generic group ${\mathcal{S}}_{n}$ the characters
$(1,s_{1},\dots,s_{n-1})$ are irreducible on ${\mathcal{S}}_{n}$ and form a
system of test functions for ${\mathcal{S}}_{n}$. On ${\mathcal{A}}_{n}$ and
its subgroups the relations $s_{n-1-i}=s_{i}$ hold, and so the characters
$(1,s_{1},\dots,s_{m})$, where $n=2m+1$ or $2m+2$, form a system of test
functions for ${\mathcal{A}}_{n}$.

The Gram matrices $M(G)$ with respect to the test characters
$(1,s_{1},\dots,s_{7})$ for $G={\mathcal{S}}_{8}$, ${\mathcal{A}}_{8}$, and
$G_{1}$, respectively are:

$M({\mathcal{S}}_{8})=\left[\begin{array}[]{@{\,}*{7}{c@{\;\;}}c@{\,}}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&1&0\\\
0&0&0&0&0&0&0&1\end{array}\right]\\!\\!\raisebox{1.72218pt}{,}\;M({\mathcal{A}}_{8})=\left[\begin{array}[]{@{\,}*{7}{c@{\;\;}}c@{\,}}1&0&0&0&0&0&0&1\\\
0&1&0&0&0&0&1&0\\\ 0&0&1&0&0&1&0&0\\\ 0&0&0&1&1&0&0&0\\\ 0&0&0&1&1&0&0&0\\\
0&0&1&0&0&1&0&0\\\ 0&1&0&0&0&0&1&0\\\
1&0&0&0&0&0&0&1\end{array}\right]\\!\\!\raisebox{1.72218pt}{,}\;M(G_{1})=\left[\begin{array}[]{@{\,}*{7}{c@{\;\;}}c@{\,}}1&0&0&0&1&0&0&0\\\
0&1&0&1&1&1&0&0\\\ 0&0&3&2&1&1&1&0\\\ 0&1&2&6&4&1&1&1\\\ 1&1&1&4&6&2&1&0\\\
0&1&1&1&2&3&0&0\\\ 0&0&1&1&1&0&1&0\\\
0&0&0&1&0&0&0&1\end{array}\right]\\!\\!\cdot$

For the indicated representative polynomials, characters
$(\chi_{1},\dots,\chi_{r})$ and set of non-ramified primes $S$, we define the
error matrix: $Z_{S}(G)=\mathrm{E}_{S}(\chi_{i}\overline{\chi}_{j})-M(G)$ and
for an $(r\times r)$-matrix $Z=(z_{ij})$ and define the normalized
$\ell_{p}$-norms

$||Z||_{p}=\Big{(}\frac{1}{r^{2}}\sum_{i,j}|z_{ij}|^{p}\Big{)}^{1/p}\mbox{ and
}||Z||_{\infty}=\max_{i,j}\\{|z_{ij}|\\}.$

In particular we need $||Z_{S}(G)||_{\infty}<0.50$ in order for the
approximation to round to $M(G)$. We say that a sequence stably converges to
$M(G)$ after $m$ terms if $||Z_{S}(G)||_{\infty}<0.50$ for all initial
segments $S$ of the sequence with $|S|>m$.

Setting $S$ equal to the first $128k$ non-ramified primes, in the case of
${\mathcal{S}}_{8}$ and ${\mathcal{A}}_{8}$ the symmetric functions give good
convergence in the $\ell_{2}$, $\ell_{8}$ and $\ell_{\infty}$-norms to $M(G)$
on small sample sets consisting of the first $128k$ non-ramified primes.

$\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil{\mathcal{S}}_{8}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&0.104870&<&0.184799&<&0.257812\\\ 2:&0.104915&<&0.197659&<&0.269531\\\
3:&0.093747&<&0.189553&<&0.255208\\\ 4:&0.072267&<&0.138632&<&0.191406\\\
5:&0.063890&<&0.112834&<&0.151562\\\ 6:&0.063620&<&0.115167&<&0.171875\\\
7:&0.052897&<&0.083975&<&0.116071\\\ 8:&0.045921&<&0.070367&<&0.097656\\\
\end{array}\quad\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil{\mathcal{A}}_{8}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&0.080624&<&0.112569&<&0.140625\\\ 2:&0.099134&<&0.174740&<&0.226562\\\
3:&0.074997&<&0.128586&<&0.166666\\\ 4:&0.057739&<&0.092246&<&0.119140\\\
5:&0.058826&<&0.128167&<&0.181250\\\ 6:&0.053728&<&0.112338&<&0.158854\\\
7:&0.049278&<&0.098191&<&0.138392\\\ 8:&0.036335&<&0.065900&<&0.092773\\\
\end{array}$

Even with sample size 128, we obtain a close approximation to the correct Gram
matrix, and the convergence remains stable. In contrast, for the group $G_{1}$
(of index 120 in ${\mathcal{S}}_{8}$) taking increments of size $1024$ we find
that $2^{14}=1024\cdot 16$ primes gives an exact approximation of $M(G_{1})$
(in the $\ell_{\infty}$-norm) but that at least $1024\cdot 22$ primes are
needed for stable convergence:

$\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
G_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&0.876885&<&1.841975&<&2.686523\\\ 2:&0.229706&<&0.475835&<&0.701171\\\
3:&0.437539&<&0.862551&<&1.233723\\\ 4:&0.542897&<&1.080542&<&1.525878\\\
5:&0.267850&<&0.528893&<&0.756054\\\ 6:&0.365931&<&0.733534&<&1.035156\\\
7:&0.199105&<&0.407255&<&0.580217\\\ 8:&0.229675&<&0.471416&<&0.672363\\\
9:&0.111158&<&0.231270&<&0.333224\\\
\end{array}\quad\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
G_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
10:&0.187304&<&0.375945&<&0.533105\\\ 11:&0.211544&<&0.429012&<&0.613725\\\
12:&0.231261&<&0.465137&<&0.665364\\\ 13:&0.279154&<&0.560439&<&0.800030\\\
14:&0.201504&<&0.399819&<&0.572195\\\ 15:&0.189139&<&0.375454&<&0.534960\\\
16:&0.178182&<&0.348732&<&0.493652\\\ 17:&0.143345&<&0.282338&<&0.397633\\\
18:&0.136637&<&0.266879&<&0.378417\\\ \end{array}$

Extending the computation further, we find that the apparent stable
convergence fails when $||Z_{S}(G_{1})||_{\infty}>0.50$ for $|S|=1024\cdot k$
for $19\leq k\leq 21$ and again in the range $45\leq k\leq 48$.

Passing to a basis of rational irreducible characters ($r(G_{1})=s(G_{1})$),
the rational character table $A(G_{1})$ and the inner product matrix
$D(G_{1})$ of the Haar measure on conjugacy classes are respectively

$A(G_{1})=\left[\begin{array}[]{@{}c@{\;}*{6}{r@{\;}}r@{\;}}1&1&1&1&1&1&1&1\\\
1&1&-1&1&1&-1&1&-1\\\ 6&-2&0&0&2&0&-1&0\\\ 12&4&0&0&0&0&-2&0\\\
7&-1&1&1&-1&1&0&-1\\\ 7&-1&-1&1&-1&-1&0&1\\\ 8&0&-2&-1&0&1&1&0\\\
8&0&2&-1&0&-1&1&0\end{array}\right]\mbox{ and
}D(G_{1})=\frac{1}{336}\left[\begin{array}[]{@{\;}*{7}{c@{\;\;}}c@{\;}}1&0&0&0&0&0&0&0\\\
0&21&0&0&0&0&0&0\\\ 0&0&28&0&0&0&0&0\\\ 0&0&0&56&0&0&0&0\\\
0&0&0&0&42&0&0&0\\\ 0&0&0&0&0&56&0&0\\\ 0&0&0&0&0&0&48&0\\\
0&0&0&0&0&0&0&84\end{array}\right]\\!\\!\raisebox{1.72218pt}{,}$

which determine the diagonalized matrix
$M(G_{1})=A(G_{1})D(G_{1})A(G_{1})^{t}=\mathrm{diag}(1,1,1,2,1,1,1,1)$ with
respect to the rational irreducible characters. With respect to this basis, in
increments of $128k$ primes, we find stable convergence after just
$512=128\cdot 4$ primes:

$\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
G_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&0.191903&<&0.557482&<&0.937500\\\ 2:&0.107457&<&0.204107&<&0.312500\\\
3:&0.111166&<&0.316320&<&0.531250\\\ 4:&0.085609&<&0.199992&<&0.335937\\\
5:&0.087717&<&0.208395&<&0.350000\\\ 6:&0.094278&<&0.217121&<&0.364583\\\
7:&0.103194&<&0.236602&<&0.397321\\\ 8:&0.110885&<&0.249000&<&0.417968\\\
\end{array}\quad\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
G_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
9:&0.114006&<&0.234514&<&0.392361\\\ 10:&0.116967&<&0.233938&<&0.390625\\\
11:&0.120169&<&0.241507&<&0.403409\\\ 12:&0.090920&<&0.197313&<&0.330729\\\
13:&0.093108&<&0.180276&<&0.300480\\\ 14:&0.070129&<&0.145311&<&0.243303\\\
15:&0.074861&<&0.160193&<&0.268750\\\
16:&0.030534&<&0.066387&<&0.111328\end{array}$

For the subgroup chain $H_{1}\subset H_{2}\subset{\mathcal{A}}_{8}$, starting
with the characters $(1,s_{1},s_{2},s_{3})$, irreducible on
${\mathcal{A}}_{8}$, we find a similar analysis. In particular, the Gram
matrices with respect to this basis are

$M({\mathcal{A}}_{8})=\left[\begin{array}[]{@{\,}*{3}{c@{\;\;}}c@{\,}}1&0&0&0\\\
0&1&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{array}\right]\\!\\!\raisebox{1.72218pt}{,}\;\;M(H_{2})=\left[\begin{array}[]{@{\,}*{3}{c@{\;\;}}c@{\,}}1&0&0&0\\\
0&1&0&0\\\ 0&0&1&0\\\
0&0&0&3\end{array}\right]\\!\\!\raisebox{1.72218pt}{,}\;\;M(H_{1})=\left[\begin{array}[]{@{\,}*{3}{c@{\;\;}}c@{\,}}1&0&0&1\\\
0&1&1&2\\\ 0&1&4&3\\\ 1&2&3&10\end{array}\right]\\!\\!\cdot$

In the former two cases, the characters are orthogonal and irreducible or
nearly so ($s_{3}$ decomposes as a sum of three distinct irreducibles on
$H_{2}$), and convergence is relatively good. In constrast, the Gram matrix
$M(H_{1})$ has determinant $14$, and far from being orthogonal or irreducible
(except for $1$ and $s_{1}$) on $H_{1}$. In increments of $1024$, we find
stable convergence only after $2^{15}=1024\cdot 32$ primes:

$\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
H_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&1.300776&<&2.685076&<&3.787109\\\ 2:&0.457035&<&0.943691&<&1.331054\\\
3:&0.316304&<&0.671333&<&0.948242\\\ 4:&0.149549&<&0.327977&<&0.463623\\\
\lx@intercol\hfil\vdots\hfil\lx@intercol&\vdots&&\vdots&&\vdots\\\
13:&0.201940&<&0.417409&<&0.588792\\\ 14:&0.219831&<&0.449876&<&0.634137\\\
15:&0.207462&<&0.427431&<&0.602799\\\
16:&0.170705&<&0.352046&<&0.496520\end{array}\quad\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
H_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
17:&0.162082&<&0.331846&<&0.467773\\\ 18:&0.249476&<&0.507743&<&0.715332\\\
19:&0.260497&<&0.533048&<&0.751336\\\ 20:&0.250136&<&0.514311&<&0.725195\\\
\lx@intercol\hfil\vdots\hfil\lx@intercol&\vdots&&\vdots&&\vdots\\\
29:&0.183952&<&0.364100&<&0.511112\\\ 30:&0.193960&<&0.384122&<&0.539257\\\
31:&0.148770&<&0.290129&<&0.406060\\\
32:&0.132390&<&0.258615&<&0.362091\end{array}$

Going further one finds that the $\ell_{\infty}$-norm gradually decreases and
does indeed stay below $0.50$ after this point. In contrast, in terms of the
basis $(1,\chi_{1}=\varphi+\bar{\varphi},\chi_{2},\chi_{3},\chi_{4})$ of
irreducible characters over $\mathbb{Q}$, of degrees $(1,6,6,7,8)$ given by

$\begin{array}[]{ll}\chi_{1}=(4s_{2}+3s_{3}-s_{1}s_{2}-4s_{1}-2)/2,&\chi_{3}=s_{1},\\\
\chi_{2}=(2s_{2}+5s_{3}-s_{1}s_{2}-6s_{1}-4)/4,&\chi_{4}=(s_{1}s_{2}+2s_{1}+2-2s_{2}-3s_{3})/2,\end{array}$

the test characters stable converge to $M(H_{1})$ after only $128$ primes,
with results here in increments of $128$ primes:

$\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
H_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&0.227868&<&0.301886&<&0.406250\\\ 2:&0.225747&<&0.296604&<&0.398437\\\
3:&0.127307&<&0.165588&<&0.216145\\\ 4:&0.149822&<&0.191605&<&0.250000\\\
5:&0.166819&<&0.214155&<&0.271875\\\ 6:&0.085019&<&0.114926&<&0.148437\\\
7:&0.101179&<&0.132950&<&0.166294\\\
8:&0.114860&<&0.148922&<&0.193359\end{array}\quad\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
H_{1}\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
9:&0.064413&<&0.088651&<&0.114583\\\ 10:&0.079219&<&0.104501&<&0.132812\\\
11:&0.091419&<&0.119029&<&0.154829\\\ 12:&0.056475&<&0.076844&<&0.097656\\\
13:&0.047871&<&0.066901&<&0.086538\\\ 14:&0.041653&<&0.062817&<&0.083705\\\
15:&0.029993&<&0.041051&<&0.053125\\\
16:&0.041465&<&0.054989&<&0.069335\end{array}$

These convergence results give empirical support to the principle of using
irreducible characters as test functions, based on the theoretical
interpretation of inner product relations on characters as variance and
covariance. Moreover, when using irreducible characters, the number of primes
necessary to recognize the Gram matrix associated to a Galois group is
strikingly small.

##  7\. Asymptotics in the degree

In analyzing the character theory of a permutation group of large degree, one
must avoid certain bottlenecks in the complexity. First the number of
transitive permutation groups is too large to enumerate, and so clearly the
poset must be navigated in a lazy fashion. Second, the number of conjugacy
classes (hence of irreducible characters) for ${\mathcal{S}}_{n}$ is too large
to enumerate. For the generic groups ${\mathcal{S}}_{n}$ and
${\mathcal{A}}_{n}$, the characters $(1,s_{1},\dots,s_{n-1})$ and
$(1,s_{1},\dots,s_{m})$, where $n=2m+1$ or $2m+2$, give a subset of rational
irreducible test functions (when $n=2m+2$, the character $s_{m}$ is the sum of
two characters on ${\mathcal{A}}_{n}$, conjugate over a quadratic field). In
general the number of conjugacy classes is the partition number $p(n)$, whose
asymptotic growth is known by Hardy and Ramanujan [10] to be

$p(n)\sim\frac{1}{4n\sqrt{3}}\exp\left(\pi\sqrt{\frac{2n}{3}}\right)\\!\cdot$

In particular, we will treat a nontrivial example of degree $120$ (and $240$)
despite the large size $p(120)=1844349560$ (and $p(240)=105882246722733$) of
the corresponding partition numbers. Finally, computation of the kernel ideal
of the restriction $\mathfrak{R}(O(n-1))\rightarrow\mathfrak{R}(G)$ by
Groebner basis algorithms is prohibitively expensive, even if the $s(G)$
points in the kernel can be computed.

Polynomials with interesting Galois groups of large degree, outside the
generic groups ${\mathcal{S}}_{n}$ and ${\mathcal{A}}_{n}$ and cyclic and
dihedral groups $C_{n}$ and $D_{n}$ rely on specific constructions. We
consider such an example of Jouve, Kowalski and Zywina [12], a polynomial
$f(x)$ of degree $240$ with Galois group the Weyl group $W(E_{8})$ of the
lattice $E_{8}$, of order $696729600$. In contrast to the large number of
conjugacy classes of ${\mathcal{S}}_{240}$, the number of conjugacy classes of
$W(E_{8})$ is $112$, and the restriction homomorphism from
$\mathfrak{R}({\mathcal{S}}_{240})$ has full rank. We take the quotient of
order $348364800$ by its center, which is the Galois group of the degree $120$
polynomial $g(x)$ such that $f(x)=g(x^{2})$. The quotient group
$G=W(E_{8})/Z(W(E_{8}))$ has $67$ conjugacy classes, all characters are
rational, and the restriction homomorphism from
$\mathfrak{R}({\mathcal{S}}_{120})$ is a subring of rank $65$. We consider the
$18$ absolutely irreducible rational characters in the image. In increments of
$256$ primes, we compute the convergence to the Gram matrix $A(G)$ for these
$18$ characters to $2^{13}=256\cdot 32$ primes:

$\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
W(E_{8})/Z(W(E_{8}))\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
1:&0.512041&<&1.947691&<&3.843750\\\ 2:&0.256200&<&0.868283&<&1.609375\\\
3:&0.180087&<&0.525172&<&0.929687\\\ 4:&0.251753&<&0.848164&<&1.571289\\\
\lx@intercol\hfil\vdots\hfil\lx@intercol&\vdots&&\vdots&&\vdots\\\
13:&0.161766&<&0.376064&<&0.648137\\\ 14:&0.151537&<&0.350967&<&0.611049\\\
15:&0.139688&<&0.325884&<&0.550000\\\ 16:&0.128557&<&0.298173&<&0.504638\\\
\end{array}\quad\begin{array}[]{r@{\;}*{5}{c@{\,}}}&\lx@intercol\hfil
W(E_{8})/Z(W(E_{8}))\hfil\lx@intercol\\\
&||Z_{S}(G)||_{2}&&||Z_{S}(G)||_{8}&&||Z_{S}(G)||_{\infty}\\\ \hline\cr
17:&0.122505&<&0.279019&<&0.473345\\\ 18:&0.118703&<&0.265146&<&0.452473\\\
19:&0.114018&<&0.254474&<&0.432360\\\ 20:&0.110361&<&0.248728&<&0.442968\\\
\lx@intercol\hfil\vdots\hfil\lx@intercol&\vdots&&\vdots&&\vdots\\\
29:&0.110513&<&0.283699&<&0.530980\\\ 30:&0.108019&<&0.275711&<&0.514713\\\
31:&0.105191&<&0.262830&<&0.491053\\\
32:&0.102228&<&0.251891&<&0.468505\end{array}$

Extending the computation further suggests that the convergence to $M(G)$ is
stable for $m>2^{13}$.

##  8\. Conclusion

A standard tool in Galois group computation is to recognize the probable group
from an analysis of Frobenius cycle types. We use an explicit polynomial
parametrization of the character ring to identify the irreducible characters
in the restriction from orthogonal groups and subsequently from the symmetric
group. As in the thesis work of Shieh [18, 19], with the view to classifying
Sato-Tate groups, it is recognized that the irreducible characters on the
target group provide optimal test functions for recognizing (or rejecting) a
given group coming from a Galois representation. We develop this perspective
in the application to the parametrized representation rings of finite groups,
with associated lattice structure. Although we focus on Galois groups arising
from splitting fields of polynomials over $\mathbb{Q}$, the same methods apply
to Galois representations coming form $L$-series and modular forms, families
of exponential sums, and global fields of any characteristic.

At a higher level, the approach through character theory and arithmetic
statistics lets us identify when Frobenius distributions of different degrees
admit a common Galois subrepresentation. Examples arise in the form of fields
with isomorphic normal closures, as described in the above examples of
${\mathcal{A}}_{5}$ representations, but more generally one can recognize
whether two normal fields admit a common subfield. In this framework
orthogonality relations of characters are measured by correlations of
Frobenius distributions associated to different representations of the
absolute Galois group. This perspective has promising potential for the
computational investigation of Galois representations.

### Acknowledgements.

The author thanks Fernando Rodriguez–Villegas for suggesting the
specialization to finite groups of the author’s work with Yih-Dar Shieh and
Gilles Lachaud, on explicit character theory of orthogonal groups, and for
providing notes of his talk in Leiden on the analysis of Galois groups by
explicit character theory (see also the 2012 bachelor’s thesis of van Bommel
[1]). Thanks go also to Claus Fieker for discussions of his algorithm and code
in Magma for constructing subfields of the normal closure of a given number
field, used in building test examples of number fields with common Galois
closure. Finally, the author thanks an anonymous referee for suggesting the
permutation groups 8T10 and 8T11, as the first example (of lowest degree) for
which the cycle distributions fail to distinguish the groups. This work is
dedicated to the memory of Gilles Lachaud and our conversations on explicit
character theory of compact Lie groups.

## References

  * [1] Raymond van Bommel. Using the Chebatorev density theorem to compute the size of Galois groups. Bachelor’s Thesis, Mathematisch Instituut, Universiteit Leiden, 2012.
  * [2] Weib Bosma, John Cannon, Catherine Playoust. The Magma Algebra System I: The User Language. J. Symb. Comp., 24 (1997), 235–265.
  * [3] Jos Brakenhoff. The representation ring and the center of the group ring. Masters Thesis, Mathematisch Instituut, Universiteit Leiden, 2005.
  * [4] Daniel Bump. Lie groups. Springer, 2013.
  * [5] Gregory Butler and John Mckay. The transitive groups of degree up to eleven. Comm. Algebra, 11, no. 8 (1983), 863–911.
  * [6] Greg Butler. The transitive groups of degree fourteen and fifteen, J. Symb. Comp., 16, no. 5 (1993), 413–422.
  * [7] John H. Conway, Alexander Hulpke, and John McKay. On transitive permutation groups. LMS J. Comp. and Math., 1 (1998), 1–8.
  * [8] Francesc Fité and Xavier Guitart. On the rank and the convergence rate towards the Sato–Tate measure. International Mathematics Research Notices (2018), to appear, https://doi.org/10.1093/imrn/rnx234.
  * [9] The GAP Group. GAP—Groups, Algorithms, and Programming, 4.8.10 (2018), https://www.gap-system.org.
  * [10] Harold Hardy and Srinivasa Ramanujan. Asymptotic formulae in combinatory analysis. Proc. of the London Mathematical Society, 2, XVII, 1918, 75–115.
  * [11] Alexander Hulpke. Constructing transitive permutation groups. J. Symb. Comp., 39, no. 1 (2005), 1–30.
  * [12] Florent Jouve, Emmanuel Kowalski and David Zywina. An explicit integral polynomial whose splitting field has Galois group $W(E_{8})$. J. Théorie des Nombres de Bordeaux, 20 (2008), no. 3, 761–782.
  * [13] The LMFDB Collaboration. The L-functions and Modular Forms Database, http://www.lmfdb.org/, 2018.
  * [14] Magma Computational Algebra Group. The Magma Handbook (2018), https://magma.maths.usyd.edu.au/magma/handbook/.
  * [15] Michael E. Pohst. Computing invariants of algebraic number fields. In Group theory, algebra, and number theory. Colloquium in memory of Hans Zassenhaus, June 4–5, 1993, de Gruyter (1996), 53–73.
  * [16] Gordon Royle. The transitive groups of degree twelve. J. Symb. Comp., 4 no. 2 (1987), 255–268.
  * [17] Jean-Pierre Serre. Linear Representations of Finite Groups. GTM 42, Springer, 1971.
  * [18] Yih-Dar Shieh. Arithmetic Aspects of Points Counting and Frobenius Distributions. Thesis, Aix-Marseille Université, 2015
  * [19] Yih-Dar Shieh. Character theory approach to Sato-Tate groups. LMS J. Comp. and Math., 19, Issue A (2016), 301–314.
  * [20] Masaru Takeuchi. A remark on the character ring of a compact Lie group. J. Math. Soc. Japan, 23, no. 4, (1971), 662–675.
  * [21] William R. Unger. Computing the character table of a finite group. J. Symb. Comp., 41 (2006), 847–862.