# Hilbert’s Irreducibility, Modular Forms, and Computation of Certain Galois
Groups

Iva Kodrnja  Faculty of Geodesy, University of Zagreb, Kačićeva 26, 10000
Zagreb, Croatia<EMAIL_ADDRESS>and  Goran Muić  Department of Mathematics,
Faculty of Sciences, University of Zagreb, Bijenička 30, 10000 Zagreb, Croatia
<EMAIL_ADDRESS>
###### Abstract.

In this paper we discuss applications of our earlier work in studying certain
Galois groups and splitting fields of rational functions in
$\mathbb{Q}\left(X_{0}(N)\right)$ using Hilbert’s irreducibility theorem and
modular forms. We also consider computational aspect of the problem using
MAGMA and SAGE.

###### Key words and phrases:

modular forms, modular curves, birational equivalence, Galois groups,
Hilbert’s irreducibility theorem

###### 1991 Mathematics Subject Classification:

11F11, 11F23

###### 2000 Mathematics Subject Classification:

11F11

The second author acknowledges Croatian Science Foundation grant
IP-2018-01-3628.

##  1\. Introduction

In this paper we consider congruence subgroups $\Gamma_{0}(N)$, $N\geq 1$, and
the corresponding compact Riemann surface $X_{0}(N)$ which we initially
consider as a complex irreducible smooth projective curve. The
$\mathbb{Q}$–structure on $X_{0}(N)$ is defined in a standard way using
$j$–function i.e., the field of rational functions over $\mathbb{Q}$ on
$X_{0}(N)$ is given by
$\mathbb{Q}\left(X_{0}(N)\right)=\mathbb{Q}(j,j(N\cdot))$. We elaborate on
equivalent ways of defining the $\mathbb{Q}$–structure in Section 3 (see Lemma
3-3 and its proof). This should be well–known but it is hard to find a
convenient reference. These are technical results used in the proof of the
main results below. In our earlier paper [18] we gave fairly general study of
complex holomorphic maps $X_{0}(N)\longrightarrow\mathbb{P}^{2}$ and developed
the test for birationality in terms of modular forms of various even weights.
The methods of that paper are further extended and combined with techniques of
explicit computations in SAGE in our paper [19]. The paper [19] constructs
various models over $\mathbb{C}$ of $X_{0}(N)$ complementing previous works
such as [1], [2], [7], [8], [10], [15], [17], [23] and [27]. In the present
paper we describe another application of [18] and [19] where we justify why it
is interesting to study plane models of $X_{0}(N)$ of various type not
necessarily of smallest possible degree or one with smallest possible
coefficients. By Eichler–Shimura theory [22, Theorem 3.5.2] and explicit
determination of certain Eisenstein series in [13, Chapter 7], we know that
$S_{m}(\Gamma_{0}(N))$, and $M_{m}(\Gamma_{0}(N))$, for $m\geq 2$ even, have
basis consisting of forms with integral $q$–expansions. So, if we take that
$f,g,h$ are linearly independent modular forms with rational $q$–expansions
for $\Gamma_{0}(N)$, we can construct an irreducible over $\mathbb{Z}$
homogeneous polynomail with integral coefficients $P_{f,g,h}$ such that
$P_{f,g,h}(f,g,h)=0$ in $\mathbb{Q}\left(X_{0}(N)\right)$. Let $Q_{f,g,h}$ be
its dehomogenization with respect to the last variable. Again, we obtain an
irreducible over $\mathbb{Z}$ polynomial with integral coefficients. By means
of Hilbert’s irreducibility theorem (see [26], summarized in Lemma 2-4), we
obtain a family of irreducible over $\mathbb{Z}$ polynomails with integral
coefficients $Q_{f,g,h}(\lambda,\cdot)$, where $\lambda$ ranges over a certain
thin set (see [26, Proposition 3.3.5 and page 26, part 3] or Lemma 2-4 here).
In this way we obtain a family of number fields determined as splitting fields
of these polynomials all of them have the same Galois group $G_{f,g,h}$ which
is the Galois group of the splitting field of $Q_{f,g,h}(g/f,\cdot)$ over
$\mathbb{Q}(g/f)$. The goal of present paper is to study these objects as an
application of the theory developed in [18] and [19]. We should observe that
the field $\mathbb{Q}(g/f)$ is just the field of rational functions one
variable over $\mathbb{Q}$, so the reader might wonder how the study of Galois
groups in the present paper differ for example from that in [26]. The reason
is that modular forms are great source of concrete irreducible polynomials
$Q_{f,g,h}(\lambda,\cdot)$ that are more restrictive than general polynomials
over the field $\mathbb{Q}(\lambda)$ ($\lambda$ is a variable here). The
reader should consult Section 5 about many results for $\Gamma_{0}(72)$ which
shows that.

We describe the content of the paper. In Section 2 we explain how to use
Hilbert’s irreducibility (see Lemma 2-4) and a technique of Frobenius on
reducing modulo various primes (see Theorem 2-5) in order to compute
$G_{f,g,h}$. In Section 3, we adapt the results of paper [19] (see Lemmas 3-3,
3-5, and 2-2) in order to study how the Galois group $G_{f,g,h}$ behaves when
we fix $f$ and $g$ and let $h$ vary under certain assumptions on $m$ and $N$.
The main result is contained in Theorems 3-13 and 3-14. They are of general
nature and they are illustrated by more concrete results in Section 5 for
$\Gamma_{0}(63)$, $\Gamma_{0}(64)$, and especially for $\Gamma_{0}(72)$. In
the Section 4, we improve on Theorem 3-14 in the case of hyperelliptic modular
curves over $\mathbb{Q}$ (see Theorem 4-1). The section ends with an
interesting example for $\Gamma_{0}(30)$. In Section 5, we discuss
non–hyperelliptic modular curves (see Theorem 5-1). We give several elegant
computations of Galois groups $G_{f,g,h}$ based on methods and results of
Section 2. The results are contained in Proposition 5-2 (the case
$\Gamma_{0}(63)$), Proposition 5-5 (the case $\Gamma_{0}(64)$), and in
Propositions 5-6, 5-8, and 5-9 (the case $\Gamma_{0}(72)$). The key result of
that section is also Remark 5-10 related to $\Gamma_{0}(72)$. The Galois
groups of polynomials $\widetilde{Q}(\lambda,\cdot)$ (a normalized version of
$Q(\lambda,\cdot)$, see Section 2) over $\mathbb{Q}(\lambda)$ can also be
computed using MAGMA system and a routine GaloisGroup. It is also interesting
to use new MAGMA routine GeometricGaloisGroup (see [6] for implementation)
which give the Galois groups of polynomials $\widetilde{Q}(\lambda,\cdot)$
over $\mathbb{C}(\lambda)$ and compare the two. (For MAGMA implementations
(and background) the reader should consult papers [4], [6], [5], and [9].)
They are not directly used in the paper. Nevertheless, we have made many
experiments in MAGMA and SAGE related to the results of the present paper. In
the final Section 6 we reprove [23, Lemma 2] (needed in the proof of Theorem
4-1) using more elegant approach based on [18] combined with certain simple
computations in SAGE.

We would like to thank Nicole Sutherland for several useful conversations
regarding the implementation in MAGMA of routines for computing Galois groups
of polynomials with coefficients in the function fields over $\mathbb{Q}$ and
$\mathbb{C}$.

##  2\. An Application of Hilbert’s Irreducibility Theorem

The goal of the present section is to set-up the notation for the rest of the
paper and to prove Theorem 2-5.

For an even integer $m\geq 2$, let $M_{m}(\Gamma_{0}(N))$ (resp.,
$S_{m}(\Gamma_{0}(N))$) be the space of (resp., cuspidal) modular forms of
weight $m$ for $\Gamma_{0}(N)$. Assume $\dim M_{m}(\Gamma_{0}(N))\geq 3$. Let
$f,g,h$ be three linearly independent modular forms in $M_{m}(\Gamma_{0}(N))$.
Then, we define a holomorphic map $X_{0}(N)\to\mathbb{P}^{2}$ uniquely
determined by

(2-1) $\mathfrak{a}_{z}\longmapsto(f(z):g(z):h(z)),\ \ z\in\mathbb{H}.$

Since $X_{0}(N)$ has a canonical structure of complex projective irreducible
algebraic curve, this map can be regarded as a regular map between projective
varieties. Consequently, the image is an irreducible projective curve which we
denote by ${\mathcal{C}}(f,g,h)$. Let $P$ be the reduced equation of
${\mathcal{C}}(f,g,h)$ i.e., an irreducible homogeneous polynomial in three
variables with complex coefficients such that $P(f(z),g(z),h(z))=0$, for all
$z\in\mathbb{H}$. It is unique up to multiplication with non–zero complex
numbers. Its dehomogenization $Q\overset{def}{=}P(1,\cdot,\cdot)$ is also an
irreducible polynomial over $\mathbb{C}$, and it satisfies
$Q\left(g/f,h/f\right)=0$ in the field of rational functions
$\mathbb{C}\left(X_{0}(N)\right)$. It is very easy to see that $P$ is
homogenization of $Q$ i.e., $P$ is uniquely determined. The polynomial $Q$
must depend on both variables or otherwise linear independence of $f$, $g$,
and $h$ is violated. We see also that $Q\left(g/f,.\right)$ is an irreducible
polynomial of $h/f\in\mathbb{C}\left(X_{0}(N)\right)$ over the subfield
$\mathbb{C}\left(g/f\right)$ generated by $g/f$. Consequently, the field
extensions satisfy $\left[\mathbb{C}\left(g/f,\
h/f\right):\mathbb{C}\left(g/f\right)\right]=\deg{\left(Q\left(g/f,\cdot\right)\right)}$.

The next lemma is important for our considerations. We recall that by
Eichler–Shimura theory [22, Theorem 3.5.2] and explicit determination of
certain Eisenstein series in [13, Chapter 7], we know that
$S_{m}(\Gamma_{0}(N))$, and $M_{m}(\Gamma_{0}(N))$, for $m\geq 2$ even, have
basis consisting of forms with integral $q$–expansions.

######  Lemma 2-2.

Let $f,g,h$ be three linearly independent modular forms in
$M_{m}(\Gamma_{0}(N))$ having rational $q$–expansions. Then, we may select
that the polynomial $P$ (and consequently $Q$) has rational coefficients.
Moreover, $Q\left(g/f,\cdot\right)$ is an irreducible polynomial of $h/f$ over
$\mathbb{Q}\left(g/f\right)$. Consequently, we have
$\left[\mathbb{Q}\left(g/f,\
h/f\right):\mathbb{Q}\left(g/f\right)\right]=\left[\mathbb{C}\left(g/f,\
h/f\right):\mathbb{C}\left(g/f\right)\right]=\deg{\left(Q\left(g/f,\cdot\right)\right)}$.

###### Proof.

The proof of the first claim of the lemma is contained in the proof of [19,
Corollary 1. 5 (ii)]. The polynomial $P$ must be irreducible over $\mathbb{Q}$
since it is irreducible over $\mathbb{C}$. The second claim follows from this.
∎

######  Definition 2-3.

Maintaining the assumptions of Lemma 2-2, we denote by $Q_{h}=Q_{f,g,h}$ an
irreducible polynomial with relatively prime coefficients in $\mathbb{Z}$ such
that $Q_{f,g,h}\left(g/f,h/f\right)=0$. Let $L_{h}=L_{f,g,h}$ be the splitting
field $Q_{h}(g/f,\cdot)$ containing $\mathbb{Q}(g/f,h/f)$, and
$G_{h}=G_{f,g,h}\overset{def}{=}Gal(L_{h}/\mathbb{Q}(g/f))$. For
$\lambda\in\mathbb{Z}$, we let $L_{h,\lambda}=L_{f,g,h,\lambda}$ be the
splitting field $Q_{h}(\lambda,\cdot)$, and
$G_{h,\lambda}=G_{f,g,h,\lambda}\overset{def}{=}Gal(L_{h,\lambda}/\mathbb{Q})$.

The polynomial $Q_{f,g,h}$ is determined up to a multiplication by $\pm 1$.
The corresponding $P$ is denoted by $P_{h}=P_{f,g,h}$. Next, we can combine
the above considerations with the celebrated Hilbert’s irreducibility theorem.
Following Serre [26], we call a subset $A\subset\mathbb{Z}$ thin if the number
of elements in the intersection of $A$ with a segment $[-n,n]$ is $O(n^{1/2})$
as $n\longrightarrow\infty$.

######  Lemma 2-4.

There exists a thin subset $A_{f,g,h}\subset\mathbb{Z}$ such that $G_{f,g,h}$
is isomorphic to $G_{f,g,h,\lambda}$, for $\lambda\in\mathbb{Z}-A_{f,g,h}$.

###### Proof.

Since $g/f$ is transcendental over $\mathbb{Q}$ in sense of field theory, the
field $\mathbb{Q}\left(\frac{g}{f}\right)$ is just a field of rational
functions in one variable over $\mathbb{Q}$. Now, the claim follows from the
Hilbert’s irreducibility (see for example [26, Proposition 3.3.5 and page 26,
part 3]). ∎

We write $Q_{f,g,h}(\lambda,\cdot)$ in the form

$Q_{f,g,h}(\lambda,T)=\sum_{i=1}^{n}a_{i}(\lambda)T^{i}\in\mathbb{Z}[\lambda,T].$

We remark that $\lambda$ and $T$ are variables here. By Definition 2-3, the
polynomial is irreducible over $\mathbb{Z}$ (not just over $\mathbb{Q}$). For
the present purpose this form of the polynomial is not good. We use standard
trick

$\widetilde{Q}_{f,g,h}(\lambda,T)\overset{def}{=}a_{n}(\lambda)^{n-1}Q(\lambda,T/a_{n}(\lambda))=T^{n}+a_{n-1}(\lambda)T^{n-1}+\sum_{i=1}^{n-2}a_{n}(\lambda)^{n-1-i}a_{i}(\lambda)T^{i}\in\mathbb{Z}[\lambda,T].$

This polynomial is also irreducible over $\mathbb{Z}$ (and over $\mathbb{Q}$)
as it is easy to check. Recall that in the present notation we have
$\sum_{i=1}^{n}a_{i}(g/f)(h/f)^{i}=Q_{f,g,h}(g/f,h/f)=0$ in
$\mathbb{Q}(g/f,h/f)$. We fix an algebraic closure
$\overline{\mathbb{Q}(g/f)}$ containing $\mathbb{Q}(g/f,h/f)$. By Definition
2-3, we may regard $G_{f,g,h}$ as the Galois group of the splitting field
$L_{f,g,h}$ inside $\overline{\mathbb{Q}(g/f)}$. It is obvious that
$L_{f,g,h}$ is the splitting field of $Q_{f,g,h}(g/f,T)$ in
$\overline{\mathbb{Q}(g/f)}$. We decompose into linear factors in $L_{f,g,h}$

$\widetilde{Q}_{f,g,h}(g/f,T)=(T-\alpha_{1})(T-\alpha_{2})\cdots(T-\alpha_{n}),\
\ \text{say,}\ \alpha_{1}=a_{n}(g/f)h/f.$

The group $G_{f,g,h}$ permutes the fixed sequence
$\alpha_{1},\cdots,\alpha_{n}$. In this way, we may regard $G_{f,g,h}$ as a
subgroup of the symmetric group $S(n)$ of $n$–letters.

Let $\Lambda_{f,g,h}$ be the integral closure of $\mathbb{Q}[\lambda]$ in
$L_{f,g,h}$. Let $\lambda\in\mathbb{Z}-A_{f,g,h}$. We select a point
$\mathfrak{a}\in X_{0}(N)$ such that $\mathfrak{a}$ gets mapped by $g/f$ onto
$\lambda$. Let $\mathfrak{m}_{\lambda}$ be the maximal ideal in
$\mathbb{Q}[g/f]$ consisting of all that map $\mathfrak{a}$ onto zero. We fix
a maximal ideal $\mathfrak{M}_{f,g,h,\lambda}$ in $\Lambda_{f,g,h}$ lying over
$\mathfrak{m}_{\lambda}$. Then, $\Lambda_{f,g,h}/\mathfrak{M}_{f,g,h,\lambda}$
is a splitting field of $\widetilde{Q}_{f,g,h}(\lambda,T)$, and we have

$\widetilde{Q}_{f,g,h}(\lambda,T)=(T-\overline{\alpha}_{1})(T-\overline{\alpha}_{2})\cdots(T-\overline{\alpha}_{n}),$

where $\overline{\alpha}_{i}=\alpha_{i}+\mathfrak{M}_{f,g,h,\lambda}$. We may
let $L_{f,g,h,\lambda}=\Lambda_{f,g,h}/\mathfrak{M}_{f,g,h,\lambda}$ since
both $\widetilde{Q}_{f,g,h}(\lambda,T)$ and $\widetilde{Q}_{f,g,h}(\lambda,T)$
have the same splitting field. Thus, $G_{f,g,h,\lambda}$ permutes the fixed
sequence $\overline{\alpha}_{1},\cdots,\overline{\alpha}_{n}$ (see Lemma 2-3).
In this way, we may regard $G_{f,g,h,\lambda}$ as a transitive subgroup of the
symmetric group $S(n)$ of $n$–letters. The isomorphism $G_{f,g,h}$ with
$G_{f,g,h,\lambda}$ (see Lemma 2-4) can be taken to be compatible with the
action on above fixed sequences of roots. After all preparations, classical
Frobenius theory (generalized later by Chebotarev) easily implies the
following theorem which we use for explicit computations.

######  Theorem 2-5.

Maintaining above assumptions, $G_{f,g,h}$ contains a permutation with a cycle
pattern $n_{1},n_{2},\ldots,n_{t}$ if and only if there exists a prime number
$p$ and and $r\in\\{0,1,\ldots,p-1\\}$ such that
$\widetilde{Q}_{f,g,h}(r,T)=T^{n}+a_{n-1}(r)T^{n-1}+\sum_{i=1}^{n-2}a_{n}(r)^{n-1-i}a_{i}(r)T^{i}\
(\text{mod}\ p)$ can be decomposed into a product of different irreducible
factors of degrees $n_{1},n_{2},\ldots,n_{t}$.

###### Proof.

First, for each $r\in\\{0,1,\ldots,p-1\\}$, the number of integers $\leq n$ of
the the form $kp+r$ is $O(n)$ is $n\longrightarrow\infty$. So, this set can
not be thin. Next, let $\lambda\in\mathbb{Z}-A_{f,g,h}$. By Frobenius theorem,
the density of all primes $p$ such that $\widetilde{Q}_{f,g,h}(\lambda,T)\
(\text{mod}\ p)$ can be decomposed into a product of different irreducible
factors of degrees $n_{1},n_{2},\ldots,n_{t}$ is equal to the number number of
elements in $G_{f,g,h,\lambda}$ with a cycle pattern
$n_{1},n_{2},\ldots,n_{t}$ divided by the number of elements in
$G_{f,g,h,\lambda}$.

After these preliminaries, we prove the theorem. First, assume that for
$r\in\\{0,1,\ldots,p-1\\}$ $\widetilde{Q}_{f,g,h}(r,T)$ can be decomposed into
a product of different irreducible factors of degrees
$n_{1},n_{2},\ldots,n_{t}$. Then, we select $\lambda\in\mathbb{Z}-A_{f,g,h}$
such that $\lambda\equiv r\ (\text{mod}\ p)$. By Frobenius theorem and Lemma
2-4, we obtain that $G_{f,g,h}$ contains a permutation with a cycle pattern
$n_{1},n_{2},\ldots,n_{t}$.

Conversely, assume that $G_{f,g,h}$ contains a permutation with a cycle
pattern $n_{1},n_{2},\ldots,n_{t}$. Then, the same is true for
$G_{f,g,h,\lambda}$ for any $\lambda\in\mathbb{Z}-A_{f,g,h}$. We fix any such
$\lambda$. By Frobenius theorem, there exists a prime number $p$ such that
$\widetilde{Q}_{f,g,h}(\lambda,T)\ (\text{mod}\ p)$ can be decomposed into a
product of different irreducible factors of degrees
$n_{1},n_{2},\ldots,n_{t}$. Finally, let $r$ be the residue of division of
$\lambda$ by $p$. We have
$\widetilde{Q}_{f,g,h}(\lambda,T)\equiv\widetilde{Q}_{f,g,h}(r,T)\
(\text{mod}\ p)$ proving the claim. ∎

##  3\. Proof of Theorems 3-14 and 3-13

The goal of the present section is to prove Theorems 3-13 and 3-14. We start
by preliminary definitions and results. Let

$E_{4}(z)=1+240\sum_{n=1}^{\infty}\sigma_{3}(n)q^{n}$

be the usual Eisenstein series, and let

$\Delta(z)=q+\sum_{n=2}^{\infty}\tau(n)q^{n}$

be the Ramanujan delta function. Then, $j=E^{3}_{4}/\Delta$. Since
$E^{3}_{4}(N\cdot),\Delta(N\cdot)\in M_{12}(\Gamma_{0}(N))$, the fact that the
function field over $\mathbb{C}$ is generated by $j$ and $j(N\cdot)$ means
that the holomorphic map

(3-1)
$\mathfrak{a}_{z}\mapsto(1:j(z):j(Nz))=(\Delta(z)\Delta(Nz):E^{3}_{4}(z)\Delta(Nz):E^{3}_{4}(Nz)\Delta(z))$

is a birational uniformization by $S_{24}(\Gamma_{0}(N))$. The
$\mathbb{Q}$–structure on the curve $X_{0}(N)$ is introduced by considering
its field of rational function defined over $\mathbb{Q}$:

(3-2)
$\mathbb{Q}\left(X_{0}(N)\right)\overset{def}{=}\mathbb{Q}(j,j(N\cdot)).$

Now, we are ready to prove the following lemma. The lemma must be well–known
but we could not find appropriate reference.

######  Lemma 3-3.

Assume that $m\geq 2$ is an even integer. Suppose that $f,g,h\in
M_{m}(\Gamma_{0}(N))$ have integral (or rational) $q$–expansions. Then, the
map (2-1) is birational over $\mathbb{C}$ if and only if it is birational over
$\mathbb{Q}$.

###### Proof.

Assume that the map (2-1) is birational over $\mathbb{C}$. Then, we have

$\mathbb{C}(g/f,\ h/f)=\mathbb{C}(j,j(N\cdot)).$

This implies that there exist homogeneous polynomials $P$ and $Q$ of the same
degree with complex coefficients such that

$j=\frac{P(f,g,h)}{Q(f,g,h)}.$

Equivalently, we have the following:

$E^{3}_{4}\cdot Q(f,g,h)-\Delta\cdot P(f,g,h)=0.$

Inserting rational $q$–expansions of $E^{3}_{4}$, $\Delta$, $f$, $g$, and $h$,
we obtain a $q$–expansion of the modular form $E^{3}_{4}\cdot
Q(f,g,h)-\Delta\cdot P(f,g,h)$. But, by the assumption, this modular form is
identically equal to zero. Therefore, all its coefficients in the
$q$–expansion are equal to zero. (Enough to choose first few depending on its
weight.) Each of these coefficients is a linear homogeneous function in
coefficients of $P$ and $Q$. Thus, we obtain the homogeneous linear system in
coefficients of $Q$ and $P$ with coefficients in $\mathbb{Q}$. This
homogeneous system has a non–zero solution over $\mathbb{C}$. Therefore, it
has a non–zero solution over $\mathbb{Q}$. Thus, we can take that the
coefficients of $P$ and $Q$ are in $\mathbb{Q}$. This proves
$j\in\mathbb{Q}(g/f,\ h/f)$. Similarly, we also prove
$j(N\cdot)\in\mathbb{Q}(g/f,\ h/f)$. This implies

(3-4)
$\mathbb{Q}\left(X_{0}(N)\right)=\mathbb{Q}(j,j(N\cdot))\subset\mathbb{Q}(g/f,\
h/f).$

Conversely, we can write

$j=\frac{E^{3}_{4}}{\Delta}=\frac{E^{3}_{4}\cdot\Delta(N\cdot)}{\Delta\cdot\Delta(N\cdot)},\
\text{and}\
j(N\cdot)=\frac{E^{3}_{4}(N\cdot)}{\Delta(N\cdot)}=\frac{E^{3}_{4}(N\cdot)\cdot\Delta}{\Delta\cdot\Delta(N\cdot)}.$

Now, we can argue as before to prove

$g/f,\
h/f\in\mathbb{Q}\left(\frac{E^{3}_{4}\cdot\Delta(N\cdot)}{\Delta\cdot\Delta(N\cdot)},\
\frac{E^{3}_{4}(N\cdot)\cdot\Delta}{\Delta\cdot\Delta(N\cdot)}\right)=\mathbb{Q}(j,j(N\cdot)).$

Hence, we obtain

$\mathbb{Q}(g/f,\ h/f)\subset\mathbb{Q}\left(X_{0}(N)\right).$

This means that the map (2-1) is birational over $\mathbb{Q}$.

Conversely, we have

$\mathbb{Q}(g/f,\ h/f)=\mathbb{Q}\left(X_{0}(N)\right).$

Taking the composite fields (with $\mathbb{C}$) we obtain

$\mathbb{C}(g/f,\ h/f)=\left(\mathbb{C}\right)\left(\mathbb{Q}(g/f,\
h/f)\right)=\left(\mathbb{C}\right)\left(\mathbb{Q}\left(X_{0}(N)\right)\right)=\mathbb{C}\left(X_{0}(N)\right).$

In the last equality we use (3-2). This means that the map (2-1) is birational
over $\mathbb{C}$. ∎

By Eichler–Shimura theory [22, Theorem 3.5.2], for each even integer $m\geq 2$
the space of cusp forms $S_{m}(\Gamma_{0}(N))$ is defined over $\mathbb{Q}$.
Let $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ be the $\mathbb{Q}$–span of all cusp
forms in $S_{m}(\Gamma_{0}(N))$ having rational $q$–expansions. Obviously,
$S_{m}(\Gamma_{0}(N))=S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}\otimes_{\mathbb{Q}}\
\mathbb{C}$.

######  Lemma 3-5.

Assume that either $m=2$ and $X_{0}(N)$ is not hyperelliptic (implies
$g(\Gamma_{0}(N))\geq 3$) or $m\geq 4$ is an even integer such that $\dim
S_{m}(\Gamma_{0}(N))\geq\max{(g(\Gamma_{0}(N))+2,3)}$. Then, we have the
following:

  * (i)

Let $f_{0},\ldots,f_{s-1}$ be a basis of $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$.
Then, $\mathbb{Q}(X_{0}(N))$ is generated over $\mathbb{Q}$ by the quotients
$f_{i}/f_{0}$, $1\leq i\leq s-1$.

  * (ii)

Assume that $f,g\in S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ are linearly
independent over $\mathbb{Q}$. Then, there exists a non-empty Zariski open set
${\mathcal{U}}_{f,g}\subset S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ 111By
definition, the intersection of a Zariski dense subset of
$S_{m}(\Gamma_{0}(N))$ defined over $\mathbb{Q}$ with
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$. such that $X_{0}(N)$ is birationally
equivalent over $\mathbb{Q}$ to ${\mathcal{C}}(f,g,h)$ via the map (2-1) i.e.,
$\mathbb{Q}\left(g/f,h/f\right)=\mathbb{Q}\left(X_{0}(N)\right)$ for any
$h\in{\mathcal{U}}_{f,g}$.

  * (iii)

Assume that $f,g\in S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ are linearly
independent over $\mathbb{Q}$. Then, the degree of the field extension
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$ is equal to the degree of the divisor
of zeores of $g/f$.

###### Proof.

The proof of (i) is analogous to that of Lemma 3-3. The detail are left to the
reader. We just note that under assumption of the lemma we have
$\mathbb{C}\left(f_{1}/f_{0},\ldots,f_{s-1}/f_{0}\right)=\mathbb{C}\left(X_{0}(N)\right)$.
This is obvious when $m=2$, and we use [16, Corollary 3.4] for the case $m\geq
4$. For the proof of the first claim in (ii), one can adjust the proofs of
[19, Theorem 1.4]. We sketch the argument. First, we select a basis of
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ such that $f=f_{0}$ and $g=f_{1}$. Then,
by (i), we have that

$\mathbb{Q}\left(X_{0}(N)\right)=\mathbb{Q}\left(g/f,f_{2}/f,\ldots,f_{s-1}/f\right)=\mathbb{Q}\left(g/f\right)\left(f_{2}/f,\ldots,f_{s-1}/f_{0}\right)\supset\mathbb{Q}\left(g/f\right)$

is a finite algebraic extension. The set of all
$(\lambda_{2},\ldots,\lambda_{s-1})\in\mathbb{Q}^{s-2}$ such that
$(\lambda_{2}f_{2}+\cdots+\lambda_{s-1}f_{s-1})/f$ generates
$\mathbb{Q}\left(X_{0}(N)\right)$ over $\mathbb{Q}\left(g/f\right)$ is not
empty (by an argument of [19, Lemma 3.2]) and it is determined by
$R(\lambda_{2},\ldots,\lambda_{s-1})\neq 0$. Here, $R$ is the discriminant of
the characteristic polynomial of the endomorphism of the vector space
$\mathbb{Q}\left(X_{0}(N)\right)$ over $\mathbb{Q}\left(g/f\right)$ determined
by the multiplication by $(\lambda_{2}f_{2}+\cdots+\lambda_{s-1}f_{s-1})/f$
(exactly as in the proof of [19, Lemma 3.4]). The discriminant $R$ is a
polynomial in variables $\lambda_{2},\ldots,\lambda_{s-1}$ with coefficients
in $\mathbb{Q}\left(g/f\right)$. By above considerations, $R$ is a non–zero
polynomial. We select $\lambda\in\mathbb{Q}$ and $\mathfrak{a}\in X_{0}(N)$
such that $g/f$ maps $\mathfrak{a}$ onto $\lambda$, and all non–zero
coefficients of $R$ when evaluated at $\mathfrak{a}$, are non–zero numbers in
$\mathbb{Q}$. Then, $R(\lambda_{2},\ldots,\lambda_{s-1})(\mathfrak{a})$ is a
non–zero polynomial with rational coefficients. Then, for the Zariski open set
${\mathcal{U}}_{f,g}\subset S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ can be taken
the set of all
$h=\lambda_{0}f+\lambda_{1}g+\lambda_{2}f_{2}+\cdots+\lambda_{s-1}f_{s-1}$,
such that $R(\lambda_{2},\ldots,\lambda_{s-1})(\mathfrak{a})\neq 0$.

Now, we prove (iii). First of all, by (ii), there exists
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ such that
$\mathbb{Q}\left(g/f,h/f\right)=\mathbb{Q}\left(X_{0}(N)\right)$. By Lemma
3-3, we have $\mathbb{C}\left(g/f,h/f\right)=\mathbb{C}\left(X_{0}(N)\right)$.
Now, Lemma 2-2, we have that $[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$ is equal
to $[\mathbb{C}(X_{0}(N)):\mathbb{C}(g/f)]$. Finally, it is a well–known that
$[\mathbb{C}(X_{0}(N)):\mathbb{C}(g/f)]$ is equal to the degree of the divisor
of zeroes of $g/f$. ∎

We generalize the last claim in (iii) in the following corollary:

######  Corollary 3-6.

Let $m\geq 2$ be an even integer such that
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}\geq 2$. Assume that $f,g\in
S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ are linearly independent over $\mathbb{Q}$.
Then, the degree of the field extension
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$ is equal to the degree of the divisor
of zeores of $g/f$. Moreover, if we let

(3-7) $l_{m,N}\overset{def}{=}\dim
S_{m}(\Gamma_{0}(N))+g(\Gamma_{0}(N))-1-\epsilon_{m},\ \
\text{$\epsilon_{2}=1$ and $\epsilon_{m}=0$ for $m\geq 4$,}$

then $[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]\leq l_{m,N}$ (a bound independent
of $f$ and $g$).

###### Proof.

Select sufficiently large $k$ such that $\dim
S_{km}(\Gamma_{0})\geq\max{(g(\Gamma_{0}(N))+2,3)}$ (which is easy to see
using explicit formula for the dimension (see for example [19, Lemma 2.2])).
For such $k$, $f^{k}$ and $f^{k-1}g$ are $\mathbb{Q}$–linearly independent
cuspidal forms in $\dim S_{km}(\Gamma_{0})$. Now, the first claim of the
corollary follows from Lemma 3-5 (iii) since $f^{k-1}g/f^{k}=g/f$.

For the bound, we estimate the degree of the divisor of zeroes of $g/f$
applying [18, Lemma 2.1]. We obtain

(3-8)
$\mathrm{div}{(g/f)}=\mathrm{div}{(g)}-\mathrm{div}{(f)}=\mathfrak{c}_{g}-\mathfrak{c}_{f},$

where for non–zero $h_{1}\in S_{m}(\Gamma_{0}(N))$ the divisor $c_{h_{1}}$ is
an effective integral divisors of the degree
$\deg{(\mathfrak{c}_{h_{1}})}=l_{m,N}$. Hence, (3-8) implies that the degree
of the divisor of zeroes of $g/f$ is $\leq l_{m,N}$. ∎

Let us fix an even integer $m\geq 2$ such that
$\dim{S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}}\geq 3$. Assume that $f,g\in
S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ are $\mathbb{Q}$–linearly independent.
Then, for each $h\in S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$,
$h\not\in\mathbb{Q}f+\mathbb{Q}g$, we may construct irreducible polynomials
$P_{h}$ and $Q_{h}$ with integral coefficients, define splitting fields
$L_{h}$, and define Galois groups $G_{h}$ (see Definition 2-3).

######  Definition 3-9.

Let $\mathcal{G}=\mathcal{G}_{f,g}$ be the set consisting of all
representatives of groups $G_{h}$, $h\in
S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}-\left(\mathbb{Q}f+\mathbb{Q}g\right)$ up to
isomorphism. For $G\in\mathcal{G}$, let $\Xi_{G}$ be the set of all $h\in
S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}-\left(\mathbb{Q}f+\mathbb{Q}g\right)$ such
that $G_{h}\simeq G$. We denote by $\Xi^{\prime}_{G}$ the set of all
$h\in\Xi_{G}$ such that the degree of $Q_{f,g,h}(g/f,\cdot)$ is
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$.

We explain Definition 3-9 in the following lemma:

######  Lemma 3-10.

Let $G\in\mathcal{G}$. Then, the order of $G$ is divisible by
$\left[\mathbb{Q}(g/f,h/f):\mathbb{Q}(g/f)\right]$ for any $h\in\Xi_{G}$.
Moreover, $G$ can be regarded as a subgroup of the symmetric group of
$\left[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)\right]$–letters (non–uniquely). In
particular, $\mathcal{G}$ is finite. Moreover, assume that
$\Xi^{\prime}_{G}\neq\emptyset$. Then, the order of $G$ is divisible by
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$,
$\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(N))$, the splitting field $L_{f,g,h}$ is
a finite extension of $\mathbb{Q}(X_{0}(N))$, and $G$ can be regarded as a
transitive subgroup of the symmetric group of
$\left[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)\right]$–letters (uniquely up to
conjugation).

###### Proof.

The first claim is obvious since we have the chain of field extensions (see
Definition 2-3)

$\mathbb{Q}(g/f)\subset\mathbb{Q}(g/f,h/f)\subset L_{h},$

and $G\simeq G_{h}=Gal(L_{h}/\mathbb{Q}(g/f))$. Basic elementary estimate for
$\left[L_{h}:\mathbb{Q}(g/f)\right]$ implies

$\\#G_{h}=\left[L_{h}:\mathbb{Q}(g/f)\right]\leq\left(\left[\mathbb{Q}(g/f,h/f):\mathbb{Q}(g/f)\right]\right)!\leq\left(\left[\mathbb{Q}(X_{0}(N):\mathbb{Q}(g/f)\right]\right)!.$

Hence, $G$ can be regarded as a subgroup of the symmetric group of
$\left[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)\right]$–letters. Thus,
$\mathcal{G}$ is finite.

Assume that $\Xi^{\prime}_{G}\neq\emptyset$. Then, by Lemma 2-2 and Definition
3-9, for $h\in\Xi^{\prime}_{g}$, we obtain

$\left[\mathbb{Q}\left(g/f,\
h/f\right):\mathbb{Q}\left(g/f\right)\right]=\deg{\left(Q_{f,g,h}\left(g/f,\cdot\right)\right)}=[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)].$

This is equivalent with $\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(N))$. Now, it is
obvious that $L_{f,g,h}$ is a finite extension of $\mathbb{Q}(X_{0}(N))$.
Other two claims in the last part of the lemma follow from Galois theory. ∎

In the next lemma we give a bound independent of choice of $f$ and $g$. The
bound might not be optimal but it is needed in the theorem below.

######  Lemma 3-11.

The order of every group $G\in\mathcal{G}$ is less than or equal to
$l_{m,N}!=1\cdot 2\cdots l_{m,N}$ where $l_{m,N}$ is defined by (3-7).

###### Proof.

We argue as in Lemma 3-10 using the estimate
$\left[\mathbb{Q}(X_{0}(N):\mathbb{Q}(g/f)\right]\leq l_{m,N}$ (see Corollary
3-6). ∎

Finally, we need the following lemma:

######  Lemma 3-12.

Assume that $f,g\in S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ are
$\mathbb{Q}$–linearly independent. Then, there exists a subgroup
$G\in\mathcal{G}$ such that $\Xi_{G}$ is Zariski dense in
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$.

###### Proof.

The Zariski open set
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}-\left(\mathbb{Q}f+\mathbb{Q}g\right)$ is a
union of finite number of sets $\Xi_{G}$ parameterized by subgroups
$G\in\mathcal{G}$. Taking the Zariski closure we find that

$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}=\cup_{G}\ \overline{\Xi}_{G}.$

But the space $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ is irreducible in sense of
algebraic geometry. So, there exists a subgroup $G\in\mathcal{G}$ such that

$\overline{\Xi}_{G}=S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}.$

This means that $\Xi_{G}$ is Zariski dense in
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$. ∎

Now, after all of these preparations, we are ready to state and prove the main
results of the present section.

######  Theorem 3-13.

Let $m\geq 2$ be an even integer such that
$\dim{S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}}\geq 3$. Then, there exists a thin
subset $A_{m,N}\subset\mathbb{Z}$, and triples of linearly independent forms
$f_{i},g_{i},h_{i}\in S_{m}(\Gamma_{0}(N))$, $1\leq i\leq k$, such that for
any $f,g,h\in S_{m}(\Gamma_{0}(N))$ which are linearly independent, there
exists $i$ such that $G_{f,g,h}\simeq G_{f_{i},g_{i},h_{i},\lambda}$,
$\lambda\in\mathbb{Z}-A_{m,N}$.

###### Proof.

By Lemma 3-11, when $f,g$ ranges over pairs of linearly independent forms in
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$, the groups in $\mathcal{G}_{f,g}$ are
isomorphic to the subgroups of the symmetric group of $l_{m,N}$–letters. Thus,
in the corresponding union $\cup_{f,g}\ \mathcal{G}_{f,g}$, there are only
finitely many groups up to isomorphism. Let us call the representatives
$G_{f_{i},g_{i},h_{i}}$, $1\leq i\leq k$. Next, we select thin subsets
$A_{f_{i},g_{i},h_{i}}$ as in Lemma 2-4. Then, the union

$A_{m,N}\overset{def}{=}\cup^{k}_{i=1}\ A_{f_{i},g_{i},h_{i}}$

is a thin subset (see the paragraph before the statement of Lemma 2-4). For
$\lambda\in\mathbb{Z}-A_{m,N}$, we have $G_{f_{i},g_{i},h_{i},}\simeq
G_{f_{i},g_{i},h_{i},\lambda}$, $1\leq i\leq k$. The theorem follows. ∎

######  Theorem 3-14.

Assume that either $m=2$ and $X_{0}(N)$ is not hyperelliptic (implies
$g(\Gamma_{0}(N))\geq 3$) or $m\geq 4$ is an even integer such that $\dim
S_{m}(\Gamma_{0}(N))\geq\max{(g(\Gamma_{0}(N))+2,3)}$. Assume that $f,g\in
S_{m}(\Gamma_{0}(N))$ are linearly independent. Then, there exists a subgroup
$G$ of the symmetric group of $l_{m,N}$–letters (see (3-7)) such that
$\Xi^{\prime}_{G}$ is Zariski dense in $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$
(see Definition 3-9).

###### Proof.

First, by Lemma 3-11, every group $G\in\mathcal{G}$ can be isomorphically
embedded into the symmetric group of $l_{m,N}$–letters. Next, there exists
$G\in\mathcal{G}$ such that $\Xi_{G}$ is Zariski dense in
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ (see Lemma 3-12). We fix such $G$.

By Lemma 3-5, there exists a non-empty Zariski open set ${\mathcal{U}}\subset
S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ such that
$\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(N))$ for $h\in{\mathcal{U}}$. Since
$\Xi_{G}$ is Zariski dense in $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$, the
intersection $\Xi_{G}\cap\mathcal{U}$ is also Zariski dense in
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$. Moreover, since for
$h\in\Xi_{G}\cap\mathcal{U}$, we have
$\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(N))$, we obtain that the degree of
$Q_{f,g,h}(g/f,\cdot)$ is $[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$ (see Lemma
2-2). Hence, $\Xi_{G}\cap\mathcal{U}\subset\Xi^{\prime}_{G}$ by Definition
3-9. ∎

##  4\. The Case of Hyperelliptic Modular Curves

The goal of the present section is to prove Theorem 4-1. The reader should
review Definitions 2-3 and 3-9, and Theorem 3-14.

Recall from [20] that $X_{0}(N)$ is a hyperelliptic curve if and only if $N$
belongs to the set
$\\{22,23,26,28,29,30,31,33,35,37,39,40,41,46,47,48,50,59,71\\}$. Select
$f,g\in S_{2}(\Gamma_{0}(N))_{\mathbb{Q}}$ such that their orders at
$\mathfrak{a}_{\infty}$ (a cusp corresponding to $\infty$) satisfy that
$\nu_{\mathfrak{a}_{\infty}}(g)$ is largest possible, and
$\nu_{\mathfrak{a}_{\infty}}(f)=\nu_{\mathfrak{a}_{\infty}}(g)-1$. The
existence of $f$ and $g$ is easy to check using SAGE system.

######  Theorem 4-1.

Assume that $X_{0}(N)$ is a hyperelliptic curve, and $f,g\in
S_{2}(\Gamma_{0}(N))_{\mathbb{Q}}$ as above. Then, we have the following:

  * (i)

The extension $\mathbb{Q}(g/f)\subset\mathbb{Q}\left(X_{0}(N)\right)$ has the
degree two, and therefore the Galois group is $\mathbb{Z}/2\mathbb{Z}$.

  * (ii)

For all even integers $m\geq 4$ there exists a non-empty Zariski open set
${\mathcal{U}}_{m}\subset S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ such that
$L_{f^{\frac{m}{2}},gf^{\frac{m}{2}-1},h}=\mathbb{Q}\left(X_{0}(N)\right)=\mathbb{Q}\left(g/f,h/f^{m/2}\right)$,
$h\in{\mathcal{U}}_{m}$. We have
${\mathcal{U}}_{m}\subset\Xi^{\prime}_{\mathbb{Z}/2\mathbb{Z}}$ (see
Definition 3-9). Moreover, $\mathcal{G}_{f^{\frac{m}{2}},gf^{\frac{m}{2}-1}}$
consists of $\mathbb{Z}/2\mathbb{Z}$ and the trivial group.

###### Proof.

First, (i) follows from Corollary 3-6 and Lemma 6-1 (see Section 6). Next, we
prove that $\mathcal{G}_{f^{\frac{m}{2}},gf^{\frac{m}{2}-1}}$ contains a
trivial group. Indeed, note that $f^{\frac{m}{2}}$, $gf^{\frac{m}{2}-1}$ and
$g^{2}f^{\frac{m}{2}-2}$ are $\mathbb{Q}$–linearly independent cuspidal
modular forms in $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$. We have

$\mathbb{Q}\left(gf^{\frac{m}{2}-1}/f^{\frac{m}{2}},\
g^{2}f^{\frac{m}{2}-2}/f^{\frac{m}{2}}\right)=\mathbb{Q}\left(g/f,\
(g/f)^{2}\right)=\mathbb{Q}\left(g/f\right)=\mathbb{Q}\left(gf^{\frac{m}{2}-1}/f^{\frac{m}{2}}\right).$

This implies that $\mathcal{G}_{f^{\frac{m}{2}},gf^{\frac{m}{2}-1}}$ contains
the trivial group. Next, by (i),

$\mathbb{Q}\left(gf^{\frac{m}{2}-1}/f^{\frac{m}{2}}\right)=\mathbb{Q}\left(g/f\right)\subset\mathbb{Q}\left(X_{0}(N)\right)$

is a degree two extension. Thus, all groups in
$\mathcal{G}_{f^{\frac{m}{2}},gf^{\frac{m}{2}-1}}$ are isomorphically
contained in $S(2)=\mathbb{Z}/2\mathbb{Z}$. Now, we prove the first claim (ii)
which also completes the proof of the last. Since $g(\Gamma_{0}(N))\geq 2$,
for $m\geq 4$, by the well–known dimension formula (see for example
preliminary [19, Lemma 2.2]) we have that

$\displaystyle\dim S_{m}(\Gamma_{0}(N))$
$\displaystyle\geq(m-1)(g(\Gamma_{0}(N))-1)+$
$\displaystyle+\left(\frac{m}{2}-1\right)\cdot\\#\left(\text{the number of non
--equivalent cusps for $\Gamma_{0}(N)$}\right)$
$\displaystyle\geq(m-1)(g(\Gamma_{0}(N))-1)+\left(\frac{m}{2}-1\right)\geq
g(\Gamma_{0}(N))+2.$

Thus, by Lemma 3-5 (ii), there exists a non-empty Zariski open set
${\mathcal{U}}_{m}$ in $S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ such that
$\mathbb{Q}\left(X_{0}(N)\right)=\mathbb{Q}\left(g/f,h/f^{m/2}\right)$, for
$h\in{\mathcal{U}}_{m}$. We obtain that the degree of
$Q_{f^{\frac{m}{2}},gf^{\frac{m}{2}-1},h}(g/f,\cdot)$ is
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$ (see Lemma 2-2). Hence,
$\mathcal{U}_{m}\subset\Xi^{\prime}_{\mathbb{Z}/2\mathbb{Z}}$ by Definition
3-9. The claim (ii) follows. ∎

We consider an example to Theorem 4-1. Let $N=30$. Then,
$g(\Gamma_{0}(30))=3$. Using SAGE we find the following base of
$S_{2}(\Gamma_{0}(30))$:

$\displaystyle f_{0}$ $\displaystyle=q-q^{4}-q^{6}-2q^{7}+q^{9}+q^{10}+\cdots$
$\displaystyle f_{1}$ $\displaystyle=q^{2}-q^{4}-q^{6}-q^{8}+q^{10}+\cdots$
$\displaystyle f_{2}$
$\displaystyle=q^{3}+q^{4}-q^{5}-q^{6}-2q^{7}-2q^{8}+q^{10}+\cdots$

We let $f=f_{1}$ and $g=f_{2}$. Now, we have that

$\displaystyle f^{2}$ $\displaystyle=q^{4}-2q^{6}-q^{8}+5q^{12}+\cdots$
$\displaystyle fg$
$\displaystyle=q^{5}+q^{6}-2q^{7}-2q^{8}-2q^{9}-2q^{10}+2q^{11}+3q^{12}\cdots$

are elements of $S_{4}(\Gamma_{0}(30))$. By listing the basis of
$S_{4}(\Gamma_{0}(30))$ using SAGE, we construct a new base as follows:
$F=F_{0}=f^{2}$, $G=F_{1}=fg$, $F_{i}=q^{i-1}+\ldots$, $2\leq i\leq 4$,
$F_{i}=q^{i+1}+\ldots$, $5\leq i\leq 14$.

Now, we use the Trial method for $(F,G,H)$ (see [19, Section 7]) where
$H=\sum_{i=2}^{13}a_{i}F_{i}$, $a_{i}\in\mathbb{Z}$, is to be determined. This
method is very simple. Given $H$, we compute the polynom $P_{F,G,H}$ using
SAGE. When

$\deg{P_{F,G,H}}>\left(\dim{S_{4}(\Gamma_{0}(30))}+g(\Gamma_{0}(30))-1\right)/2=(14+3-1)/2=8,$

combining with Lemma 3-3, we obtain
$\mathbb{Q}(X_{0}(N))=\mathbb{Q}\left(G/F,H/F\right)=\mathbb{Q}\left(g/f,H/f^{2}\right)$.
Thus, in view of notation introduced in Theorem 4-1, we may let $h=H$.

Applying the algorithm, we may obtain $h=H=F_{3}$. The corresponding
polynomial $Q_{f^{2},fg,H}(\lambda,T)$ (a dehomogenization of $P_{f^{2},fg,H}$
(see Definition 2-3)) is given by

$\displaystyle
225\lambda^{6}\left(1-\lambda-\lambda^{2}+\lambda^{3}\right)T^{2}-\lambda^{3}\big{(}237-370\lambda+319\lambda^{2}+341\lambda^{3}-310\lambda^{4}-101\lambda^{5}+400\lambda^{6}-$
$\displaystyle-10\lambda^{7}-64\lambda^{8}+32\lambda^{9}\big{)}T+12-44\lambda-85\lambda^{2}+153\lambda^{3}+1073\lambda^{4}+1375\lambda^{5}-420\lambda^{6}-660\lambda^{7}-$
$\displaystyle-30\lambda^{8}+162\lambda^{9}-26\lambda^{10}-118\lambda^{11}+84\lambda^{12}+20\lambda^{13}+12\lambda^{14}-4\lambda^{15}.$

We see that $\mathbb{Q}(f/g)\subset\mathbb{Q}(X_{0}(N))$ is a quadratic
exension as it should be by Theorem 4-1 (i). Next, we apply methods of Section
2 (see Theorem 2-5). We easily see that
$\widetilde{Q}_{f^{2},fg,H}(\lambda,T)$ is given by

$\displaystyle
T^{2}-\lambda^{3}\big{(}237-370\lambda+319\lambda^{2}+341\lambda^{3}-310\lambda^{4}-101\lambda^{5}+400\lambda^{6}-10\lambda^{7}-64\lambda^{8}+32\lambda^{9}\big{)}T$
$\displaystyle+225\lambda^{6}\left(1-\lambda-\lambda^{2}+\lambda^{3}\right)\cdot\big{(}12-44\lambda-85\lambda^{2}+153\lambda^{3}+1073\lambda^{4}+1375\lambda^{5}-420\lambda^{6}$
$\displaystyle-660\lambda^{7}-30\lambda^{8}+162\lambda^{9}-26\lambda^{10}-118\lambda^{11}+84\lambda^{12}+20\lambda^{13}+12\lambda^{14}-4\lambda^{15}\big{)}.$

We let $\lambda\in\mathbb{Z}-A_{f,g,h}$ and reduce polynomial $(\text{mod}\
5)$. We obtain
$T^{2}-\lambda^{3}\big{(}2-\lambda^{2}+\lambda^{3}-\lambda^{5}+\lambda^{8}+2\lambda^{9}\big{)}T$.
Letting $\lambda\equiv 1\ (\text{mod}\ 5)$ (possible as explained in the proof
Theorem 2-5) we obtain $T^{2}-T=T(T-1)$. Considered $G_{f^{2},fg,H,\lambda}$
as a subgroup of the symmetric group $S(2)$, we see that it contains a
transposition. Hence, $G_{f^{2},fg,H,\lambda}=S(2)$. This recovers the Galois
group of the original polynomial $G_{f^{2},fg,H}$ by using Hilbert’s
irreducibility. More interesting examples are given in Section 5.

##  5\. The Case of Non–Hyperelliptic Modular Curves

By [20], $X_{0}(N)$ is non–hyperelliptic for
$N\in\\{34,38,42,43,44,45,51-58,60-70\\}$ or $N\geq 72$. This implies
$g(\Gamma_{0}(N))\geq 3$. We assume that in this section. The main result of
the present section is the following theorem. The reader should compare to
Theorem 4-1. The bound for $[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]$ in the
theorem below is far more better than the generic bound
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]\leq 2g(\Gamma_{0}(N))-2$ given by
Corollary 3-6.

######  Theorem 5-1.

Maintaining above assumptions, we select $f$ and $g$ in
$S_{m}(\Gamma_{0}(N))_{\mathbb{Q}}$ with largest possible orders of vanishing
at $\mathfrak{a}_{\infty}$ (as in Theorem 4-1 but they are not necessarily
consecutive here), $\nu_{\infty}(f)<\nu_{\infty}(g)$. Then,
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]\leq g(\Gamma_{0}(N))$. Consequently,
for $h\in
S_{2}(\Gamma_{0}(N))_{\mathbb{Q}}-\left(\mathbb{Q}f+\mathbb{Q}g\right)$,
$G_{f,g,h}$ can be embedded as a subgroup of the symmetric group of
$g(\Gamma_{0}(N))$–letters $S_{g(\Gamma_{0}(N))}$ (non–uniquely). Moreover,
there exists a subgroup $G$ of $S_{g(\Gamma_{0}(N))}$ such that
$\Xi^{\prime}_{G}$ is Zariski dense in (see Definition 3-9).

###### Proof.

We let $W_{i}=\left\\{f\in S_{2}(\Gamma_{0}(N));\ f=0\ \text{or}\
\nu_{\mathfrak{a}_{\infty}}(f)\geq i\right\\}$. Then, by the proof of [19,
Corollary 5.6], $\dim W_{g(\Gamma_{0}(N))-2}\geq 3$. This implies $\dim
W_{g(\Gamma_{0}(N))-1}\geq 2$. Obviously, we have $f,g\in
W_{g(\Gamma_{0}(N))-1}$. Now, in (3-8) there are a lot more cancellations.
Namely, $q$–expansions satisfy

$\begin{cases}f&=a_{l}q^{l}+\cdots,\ \ a_{l}\neq 0,\ \ l=\nu_{\infty}(f),\\\
g&=b_{k}q^{k}+\cdots,\ \ b_{k}\neq 0,\ \ k=\nu_{\infty}(g),\\\ \end{cases}$

where $k>l\geq g(\Gamma_{0}(N))-1$. This implies that

$\begin{cases}\mathfrak{c}_{f}&=(l-1)\mathfrak{a}_{\infty}+\cdots,\\\
\mathfrak{c}_{g}&=(k-1)\mathfrak{a}_{\infty}+\cdots,\\\ \end{cases}$

by definition of these divisors [18, Lemma 2.1]. Thus, by (3-8), the divisor
of zeroes of $g/f$ has degree

$2(g(\Gamma_{0}(N))-1)-(l-1)\leq
2(g(\Gamma_{0}(N))-1)-(g(\Gamma_{0}(N))-2)=g(\Gamma_{0}(N)).$

By Lemma 3-5 and Corollary 3-6, we obtain
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]\leq g(\Gamma_{0}(N))$. The rest of
claims follow from Lemma 3-10 and Theorem 3-14. ∎

We continue with an example related to [19, Corollary 5.8] which shows that
the result in Theorem 5-1 is optimal. Consider three basis elements of
$5$–dimensional space $S_{2}(\Gamma_{0}(63))$ having highest order of zero at
$\mathfrak{a}_{\infty}$:

$\displaystyle f\overset{def}{=}$ $\displaystyle
q^{4}+q^{7}-4q^{10}+2q^{13}-2q^{16}-4q^{19}+5q^{22}+\cdots,$ $\displaystyle
g\overset{def}{=}$ $\displaystyle
2q^{5}-q^{8}-3q^{11}-q^{14}+2q^{17}+q^{23}+\cdots,$ $\displaystyle
h\overset{def}{=}$ $\displaystyle
q^{3}-q^{6}+q^{9}-q^{12}-2q^{15}-q^{18}-q^{21}+3q^{24}+\cdots.$

The reader should observe that $f$ and $g$ are chosen as in the hyperelliptic
case (see Theorem 4-1). We apply methods of Section 2 (see Theorem 2-5).

######  Proposition 5-2.

Maintaining above assumptions, we have $G_{f,g,h}\simeq S(5)$. Moreover,
$h\in\Xi^{\prime}_{S(5)}$, and $\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(63))$.

###### Proof.

The reduced equation of the curve ${\mathcal{C}}(f,g,h)$ is computed in SAGE.
It is given by the polynomial $P_{f,g,h}$ irreducible over $\mathbb{Q}$

$-2h^{4}f^{2}-hf^{5}+h^{5}g+2h^{2}f^{3}g+h^{3}fg^{2}-f^{4}g^{2}+3hf^{2}g^{3}-3h^{2}g^{4}=P_{f,g,h}(f,g,h)=0.$

This implies

$Q_{f,g,h}(\lambda,T)=\lambda
T^{5}-2T^{4}+\lambda^{2}T^{3}+\left(2\lambda-3\lambda^{4}\right)T^{2}+\left(3\lambda^{3}-1\right)T-\lambda^{2}.$

We have (see Section 2)

(5-3)
$\widetilde{Q}_{f,g,h}(\lambda,T)=T^{5}-2T^{4}+\lambda^{3}T^{3}+\left(2\lambda-3\lambda^{4}\right)\lambda^{2}T^{2}+\left(3\lambda^{3}-1\right)\lambda^{3}T-\lambda^{6}.$

For $\lambda\equiv-1\ (\text{mod}\ 3)$, reducing $\equiv\ (\text{mod}\ 3)$,
the polynomial (5-3) becomes $T^{5}+T^{4}-T^{3}+T^{2}+T+1$ which is
irreducible over $\mathbb{Z}/3\mathbb{Z}$. Since $5$ is a prime number, we see
that that group $G_{f,g,h}$ must contain a $5$–cycle (see Theorem 2-5).
Similarly, for $\lambda\equiv-1\ (\text{mod}\ 7)$, the polynomial (5-3)
becomes a product of two irreducible polynomials

$T^{5}-2T^{4}-T^{3}+2T^{2}+3T-1=\left(T^{2}-T+3\right)\cdot\left(T^{3}-T^{2}+4T+2\right).$

This shows that the Galois group $G_{f,g,h}$ contains a permutation which is a
product of commuting $2$–cycle and $3$–cycle. Its cube is a transposition.
Now, since $G_{f,g,h}$ is a subgroup of $S(5)$ (and $5$ is a prime number)
which contains a $5$–cycle and a transposition, by the standard argument, the
group is $S(5)$ (see [11]). Next, by Definition 3-9, to prove
$h\in\Xi^{\prime}_{S(5)}$, we need to show that
$[\mathbb{Q}(X_{0}(N)):\mathbb{Q}(g/f)]=g(\Gamma_{0}(63))=5$. Indeed, by above
considerations and Lemma 2-2, we have that

$[\mathbb{Q}(g/f,h/f):\mathbb{Q}(g/f)]=\deg{Q_{f,g,h}(g/f,\cdot)}=5.$

But, since by Theorem 5-1 we have

$[\mathbb{Q}(X_{0}(63)):\mathbb{Q}(g/f)]\leq g(\Gamma_{0}(63))=5,$

we obtain $\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(63))$. 222 This also follows
by methods of [18] from [19, Corollary 5.8] using Lemma 3-3. The claim
follows. Finally, the last claim of the proposition is also proved. ∎

######  Remark 5-4.

Keeping $f$ and $g$ fixed and letting $h$ we have computed a considerable
number of examples using MAGMA routines mentioned in the introduction. We
always obtained $G_{f,g,h}\simeq S(5)$.

Let $N=64$. Then, $g(\Gamma_{0}(64))=3$. The basis of $S_{2}(\Gamma_{0}(63))$
is

$\displaystyle f$
$\displaystyle\overset{def}{=}q^{2}-2q^{10}-3q^{18}+6q^{26}+2q^{34}+\cdots,$
$\displaystyle g$
$\displaystyle\overset{def}{=}q^{5}-3q^{13}+5q^{29}+q^{37}+\cdots,$
$\displaystyle h$
$\displaystyle\overset{def}{=}q-3q^{9}+2q^{17}-q^{25}+\cdots,$

Using SAGE we check that $-f^{4}+h^{3}g+4hg^{3}=0$. This implies that
$Q_{f,g,h}(\lambda,T)=\lambda T^{3}+4\lambda^{3}T-1$. Arguing as in
Proposition 5-2 but reducing $(\text{mod}\ 2)$ and $(\text{mod}\ 5)$ we easily
establish.

######  Proposition 5-5.

Maintaining above assumptions, we have $G_{f,g,h}\simeq S(3)$ and
$\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(64))$.

The last set of examples is for $N=72$. We have $g(\Gamma_{0}(72))=5$. Using
SAGE, the basis of $5$–dimensional space $S_{2}(\Gamma_{0}(72))$ is given by

$\displaystyle f\overset{def}{=}f_{0}$
$\displaystyle\overset{def}{=}q^{5}-2q^{11}-q^{17}+4q^{23}-3q^{29}+\cdots,$
$\displaystyle g\overset{def}{=}f_{1}$
$\displaystyle\overset{def}{=}q^{7}-q^{13}-3q^{19}+q^{25}+3q^{31}+4q^{37}+\cdots,$
$\displaystyle f_{2}$
$\displaystyle\overset{def}{=}q^{3}-q^{9}-2q^{15}+q^{27}+4q^{33}-2q^{39}+\cdots,$
$\displaystyle f_{3}$
$\displaystyle\overset{def}{=}q^{2}-4q^{14}+2q^{26}+8q^{38}+\cdots,$
$\displaystyle f_{4}$
$\displaystyle\overset{def}{=}q-2q^{13}-4q^{19}-q^{25}+8q^{31}+6q^{37}+\cdots.$

In the following proposition, among other things, we show that
$[\mathbb{Q}(X_{0}(72)):\mathbb{Q}(g/f)]=4$ (which is $<g(\Gamma_{0}(72))=5$,
see Theorem 5-1).

######  Proposition 5-6.

Let $h=f_{3}$. Then, we have that $G_{f,g,h}\simeq D(4)$ a dihedral group of
order $2\cdot 4=8$. Moreover, $\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(72))$,
$[\mathbb{Q}(X_{0}(72)):\mathbb{Q}(g/f)]=4$, and $h\in\Xi^{\prime}_{D(4)}$.
Moreover, the Galois group of the extension $\mathbb{Q}(X_{0}(72))\subset
L_{f,g,h}$ is generated by a transposition in $D(4)$.

###### Proof.

The polynomial $P_{f,g,h}$ is given by

$f^{7}+7f^{4}g^{3}-8fg^{6}-f^{5}h^{2}-8f^{2}g^{3}h^{2}+g^{3}h^{4}.$

This implies

$\widetilde{Q}_{f,g,h}(\lambda,T)=T^{4}-\lambda^{3}(1+8\lambda^{3})T^{2}+\lambda^{9}(1+7\lambda^{3}-8\lambda^{6}).$

For $\lambda\equiv-1\ (\text{mod}\ 3)$, reducing $\equiv\ (\text{mod}\ 3)$,
the polynomial $\widetilde{Q}_{f,g,h}(\lambda,T)$ becomes $T^{4}-T^{2}-1$
which is irreducible over $\mathbb{Z}/3\mathbb{Z}$. Thus, $G_{f,g,h}$ must
contain a $4$–cycle (see Theorem 2-5). Next, for $\lambda\equiv-1\
(\text{mod}\ 3)$, reducing $\equiv\ (\text{mod}\ 5)$, the polynomial
$\widetilde{Q}_{f,g,h}(\lambda,T)$ becomes $T^{4}-2T^{2}-1$ which is product
of irreducible polynomials $T^{2}-T+2$ and $T^{2}+T+2$ over
$\mathbb{Z}/5\mathbb{Z}$. This shows that the Galois group $G_{f,g,h}$
contains a permutation with a cycle pattern 2, 2. Now, we list all transitive
groups in $S(4)$ (see http://galoisdb.math.upb.de/groups?deg=4 and [3] for
notation). They are cyclic group $C(4)$, the Klein group $E(4)$ (order $4$ all
non–trivial elements have order 2), the dihedral group $D(4)$ (order $8$), the
alternating group $A(4)$, and the symmetric group $S(4)$. Clearly, $G_{f,g,h}$
cannot be $C(4)$. It is not also $E(4)$ since it contains a four cycle which
has order $4$. Also, a four cycle is a product of three transpositions, for
example $(1,2,3,4)=(1,2)(1,3)(1,4)$. Thus, $G_{f,g,h}$ cannot be $A(4)$. Thus,
$G_{f,g,h}$ is either $D(4)$ or $S(4)$. If it would be $S(4)$, the it would
contain a permutation with a cycle pattern 1, 3. Then, by Theorem 2-5, there
would exist a prime number $p>2$ and $\lambda\in\mathbb{Z}$ such that reducing
$\equiv\ (\text{mod}\ p)$ the polynomial $\widetilde{Q}_{f,g,h}(\lambda,T)$
would be a product of a normalized linear polynomial, say $P_{1}$, and a cubic
normalized irreducible polynomial, say $P_{2}$, over $\mathbb{Z}/p\mathbb{Z}$.
Clearly, $P_{1}$ is of the form $T-a$, $a\not\equiv 0\ (\text{mod}\ p)$. Then,
$a$ is a zero of $\widetilde{Q}_{f,g,h}(\lambda,T)$ modulo $p$. Clearly, $-a$
is also a zero, and since $p>2$ we have $a\not\equiv-a\ (\text{mod}\ p)$. This
is a contradiction since $P_{2}$ cannot have zeroes in
$\mathbb{Z}/p\mathbb{Z}$.

After renumeration, the group $D(4)$ is generated by a $4$–cycle $r=(1234)$
and a transposition $s=(13)$ subject to the relation $srs=r^{-1}$. The
elements of $D(4)$ are $1,r,r^{2},r^{3},r^{4}$, $sr=(23)(14)$, $sr^{2}=(24)$
and $sr^{3}=(12)(34)$. Thus, in the chain of field extensions
$\mathbb{Q}(g/f)\subset\mathbb{Q}(g/f,h/f)\subset L_{f,g,h}$, we see that
$Gal(L_{f,g,h}/Q(g/f,h/f))$ must be generated either by $s=(13)$ or
$sr^{2}=(2,4)$ since other permutations do not have fixed points and a root
$h/f$ of $Q_{f,g,h}(g/f,T)$ must be fixed by elements of
$Gal(L_{f,g,h}/Q(g/f,h/f))$.

Finally, since the $\deg{P_{f,g,h}}=7>g(\Gamma_{0}(72))-1=4$, the Trial method
[19, Section 7] and Lemma 3-3 imply
$\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(72))$. Hence,
$[\mathbb{Q}(X_{0}(72)):\mathbb{Q}(g/f)]=4$. In particular, by Definition 3-9,
$h\in\Xi^{\prime}_{D(4)}$. ∎

######  Remark 5-7.

By the method described in Section 2 (see Theorem 2-5), a transposition in
$G_{f,g,h}=D(4)$ can be seen by taking $\lambda\equiv-1\ (\text{mod}\ 79)$ and
reducing $\widetilde{Q}_{f,g,h}(\lambda,T)$ modulo $p=79$. We obtain the
polynomial $T^{4}-7T^{2}+14$ which is a product of two linear polynomials
$T\pm 4$ and an irreducible quadratic polynomial $T^{2}+9$. By Theorem 2-5,
$G_{f,g,h}$ must contain a permutation with a cyclic pattern $1,1,2$ i.e., a
transposition.

######  Proposition 5-8.

Let $h=f_{3}+f_{4}$. Then, we have $G_{f,g,h}\simeq S(4)$. Moreover,
$h\in\Xi^{\prime}_{S(4)}$, and $\mathbb{Q}(g/f,h/f)=\mathbb{Q}(X_{0}(72))$.

###### Proof.

The proof is very similar to the proof of Proposition 5-6, but easier. So, we
sketch the argument. First, using SAGE, we find that $P_{f,g,h}$ is given by

$\displaystyle
f^{8}-f^{7}g+8f^{5}g^{3}-7f^{4}g^{4}+8fg^{7}-16g^{8}-2f^{5}g^{2}h+8f^{3}g^{4}h-16f^{2}g^{5}h+$
$\displaystyle
32g^{7}h-f^{6}h^{2}+f^{5}gh^{2}-8f^{3}g^{3}h^{2}+8f^{2}g^{4}h^{2}-24g^{6}h^{2}+2f^{3}g^{2}h^{3}+8g^{5}h^{3}-g^{4}h^{4}.$

Hence, $\widetilde{Q}_{f,g,h}(\lambda,T)$ is given by

$\displaystyle-\lambda^{12}(1-\lambda+8\lambda^{3}-7\lambda^{4}+8\lambda^{7}-16\lambda^{8})+\lambda^{8}(2\lambda^{2}+8\lambda^{4}-16\lambda^{5}+32\lambda^{7})T-$
$\displaystyle-\lambda^{4}(-1+\lambda-8\lambda^{3}+8\lambda^{4}-24\lambda^{6})T^{2}+(2\lambda^{2}+8\lambda^{5})T^{3}+T^{4}$

For $\lambda\equiv 1\ (\text{mod}\ 3)$, reducing $\equiv\ (\text{mod}\ 3)$,
the polynomial $\widetilde{Q}_{f,g,h}(\lambda,T)$ becomes $1-T+T^{3}+T^{4}$.
This polynomial is irreducible over $\mathbb{Z}/3\mathbb{Z}$. Hence, by
Theorem 2-5, the group $G_{f,g,h}$ contains a four cycle. Similarly for
$\lambda\equiv 1\ (\text{mod}\ 7)$, reducing $\equiv\ (\text{mod}\ 7)$, the
polynomial $\widetilde{Q}_{f,g,h}(\lambda,T)$ becomes
$(-2+3T+3T^{2}+T^{3})\cdot T$ a product of two irreducible polynomials. Hence,
$G_{f,g,h}$ contains a permutation with a cycle patter $1,3$. Now, as in the
proof of Proposition 5-6, in view of list all transitive groups in $S(4)$, we
see that $G_{f,g,h}$ must be $S(4)$. The other claims follow by the same
arguments as the analogous claims in Proposition 5-6. ∎

######  Proposition 5-9.

Maintaining above assumptions, let $h=f_{2}$. Then, we have
$G_{f,g,h}\simeq\mathbb{Z}/2\mathbb{Z}$. Next,
$h\in\Xi_{\mathbb{Z}/2\mathbb{Z}}$ but
$\Xi^{\prime}_{\mathbb{Z}/2\mathbb{Z}}=\emptyset$.

###### Proof.

As before, using SAGE, we find that $-f^{2}h+gh^{2}-2fg^{2}=0$. Hence, we see
$Q_{f,g,h}(\lambda,T)=\lambda T^{2}-T-2\lambda^{2}$. Hence,
$\widetilde{Q}_{f,g,h}(\lambda,T)=T^{2}-T-2\lambda^{3}$. The result easily
follows. For example, for $\lambda\equiv 0\ (\text{mod}\ 2)$, reducing
$\equiv\ (\text{mod}\ 2)$, the polynomial $\widetilde{Q}_{f,g,h}(\lambda,T)$
becomes a product $T\cdot(T-1)$. Hence, $G_{f,g,h}\simeq
S(2)\simeq\mathbb{Z}/2\mathbb{Z}$. In particular,
$h\in\Xi_{\mathbb{Z}/2\mathbb{Z}}$. Finally, for
$h^{\prime}\in\Xi_{\mathbb{Z}/2\mathbb{Z}}$, the degree of the extension
$\mathbb{Q}(g/f)\subset\mathbb{Q}(g/f,h^{\prime}/f)$ is two while
$\mathbb{Q}(g/f)\subset\mathbb{Q}(X_{0}(72))$ has degree four by Proposition
5-6. Hence, $\Xi^{\prime}_{\mathbb{Z}/2\mathbb{Z}}=\emptyset$ (see Definition
3-9). ∎

######  Remark 5-10.

Using http://galoisdb.math.upb.de/groups?deg=4 (see [3] for notation), we may
conclude that $\Xi_{C(4)}=\Xi_{E(4)}=\emptyset$ (see Definition 3-9). Indeed,
let $h^{\prime}\in\Xi_{C(4)}$ or $h^{\prime}\in\Xi_{E(4)}$. Then, the degree
$[\mathbb{Q}(g/f,h^{\prime}/f):\mathbb{Q}(f/g)]$ obviously must divide
$[\mathbb{Q}(X_{0}(72)):\mathbb{Q}(f/g)]=4$ (see Proposition 5-6). Thus,
$[\mathbb{Q}(g/f,h^{\prime}/f):\mathbb{Q}(f/g)]=4$ (or otherwise
$L_{f,g,h^{\prime}}=\mathbb{Q}(g/f,h^{\prime}/f)$ contradicting that it must
be a degree four extension of $\mathbb{Q}(f/g)$). We obtain that
$\mathbb{Q}(g/f,h^{\prime}/f)=\mathbb{Q}(X_{0}(72))$ is a Galois extension of
$\mathbb{Q}(f/g)$ with the Galois group $C(4)$. On the other hand, using $h$
from Proposition 5-8 we have the Galois extension $L_{f,g,h}$ of
$\mathbb{Q}(f/g)$ with the Galois group $S(4)$ containing
$\mathbb{Q}(X_{0}(72))$. Now, by Galois theory we conclude that $S(4)$ has
normal group with a quotient of order four. But this is a contradiction since
$S(4)$ has no normal subgroup of order $4!/4=6$.

##  6\. The Proof of Lemma 6-1

In this section we prove the following lemma used in the proof of Theorem 4-1:

######  Lemma 6-1.

Maintaining the assumptions of Theorem 4-1, we have that
$\mathbb{C}\left(g/f\right)\subset\mathbb{C}\left(X_{0}(N)\right)$ is a degree
two extension.

###### Proof.

This claim is contained in [23, Lemma 2] but we give different proof using our
previous work [18] combined with certain simple computations in SAGE.

First, we assume that we have $g(\Gamma_{0}(N))=2$ i.e.,
$N=22,23,26,28,29,31,37,50$. We use results recalled in the proof of Theorem
3-14 up to the formula in (3-7). The divisor of zeroes must be
$\mathfrak{c}_{g}$ since otherwise the divisor of zeroes would have degree
one, and we would obtain $\mathbb{C}(X_{0}(N))=\mathbb{C}(g/f)$. Hence,
$X_{0}(N)$ would have a genus $0$ which is a contradiction. This proves (6-1)
when $g(\Gamma_{0}(N))=2$. Next, we assume that $g(\Gamma_{0}(N))\geq 3$ i.e.,

(6-2) $N=30,33,35,39,40,41,46,47,48,59,71.$

Then, above method does not work since the degree of divisors
$\mathfrak{c}_{f}$ and $\mathfrak{c}_{g}$ is $2(g(\Gamma_{0})N))-1)\geq 4$. We
need to dig deeper into the geometry and computations in SAGE. We write
$f_{0},\ldots,f_{g(\Gamma_{0}(N))-1}$ for the basis of $S_{2}(\Gamma_{0}(N))$.
By Eichler–Shimura theory [22, Theorem 3.5.2] we see that they have integral
$q$–expansions, and using SAGE system we can easily check that their
$q$–expansions are of the form

(6-3) $f_{i}=a_{i}q^{i+1}+\cdots,\ \ 0\leq i\leq g(\Gamma_{0}(N))-1.$

where $a_{i}\neq 0$. By definition of $f$ and $g$, we see that $g=\lambda
f_{g(\Gamma_{0}(N))-1}$ and $f=\mu f_{g(\Gamma_{0}(N))-2}+\nu
f_{g(\Gamma_{0}(N))-1}$, for some $\lambda,\mu,\nu\in\mathbb{Q}$,
$\lambda,\mu\neq 0$. So, in order to prove (6-1), we may assume
$f=f_{g(\Gamma_{0}(N))-2}$, and $g=f_{g(\Gamma_{0}(N))-1}$.

In what follows we do not need letter $g$ to denote a cupidal form, so we may
put $g=g(\Gamma_{0}(N))$. We consider the analogue of the map (2-1) given by

(6-4) $\mathfrak{a}_{z}\longmapsto(f_{g-3}(z):f_{g-2}(z):f_{g-1}(z)),\ \
z\in\mathbb{H}.$

Let $d(f_{g-3},f_{g-2},f_{g-1})$ be the degree of that map (it is explained in
detail in [18]). We recall that $d(f_{g-3},f_{g-2},f_{g-1})$ is a degree of
the field extension
$\mathbb{C}\left({\mathcal{C}}(f_{g-3},f_{g-2},f_{g-1})\right)\subset\mathbb{C}\left(X_{0}(N)\right)$.
This means that the map (6-4) is generically $d$–to–$1$ map (see [18, Lemma
3.4]). We prove

(6-5) $d(f_{g-3},f_{g-2},f_{g-1})$ is an even integer.

In order to prove (6-5), let $K$ be the canonical divisor on $X_{0}(N)$ i.e.,
a divisor attached to a non–zero meromorphic differential form on $X_{0}(N)$.
The regular map attached to $K$ is is explicitly described in [7]:

(6-6) $X_{0}(N)\longrightarrow\mathbb{P}^{g-1},\ \
\mathfrak{a}_{z}\longmapsto\left(f_{0}(z):f_{1}(z):\cdots:f_{g-1}\right),\ \
z\in\mathbb{H}.$

The image is an irreducible projective curve, say
${\mathcal{C}}(f_{0},\ldots,f_{g-1})$. It is well–known that this maps is
generically two–to–one since our curve is hyperelliptic. This means that the
degree of the field extension
$\mathbb{C}\left({\mathcal{C}}(f_{0},\ldots,f_{g-1})\right)\subset\mathbb{C}\left(X_{0}(N)\right)$
is equal to $2$.

The map (6-4) can be considered as a rational map (i.e., defined on a open
subset), and factored as a dominant rational map in a composition of the map
(6-6) followed by the restriction of the projection
$\mathbb{P}^{g-1}\longrightarrow\mathbb{P}^{2}$ given by
$(y_{0}:y_{1}:\cdots:y_{g-1})\longrightarrow(y_{g-3}:y_{g-2}:y_{g-1})$ which
is defined on a non–empty Zariski open set of the image
${\mathcal{C}}(f_{0},\ldots,f_{g-1})$. (For example, on the complement of the
(finite) set of zeroes in $\mathbb{H}$ of the cuspidal modular form
$f_{g-3}f_{g-2}f_{g-1}$ of weight $6$.) Let $d$ be the degree of the
projection restricted to the curve ${\mathcal{C}}(f_{0},\ldots,f_{g-1})$. By
definition, this is a degree of the field extension
$\mathbb{C}\left({\mathcal{C}}(f_{g-3},f_{g-2},f_{g-1})\right)\subset\mathbb{C}\left({\mathcal{C}}(f_{0},\ldots,f_{g-1})\right)$.
Thus, considering chain field extensions
$\mathbb{C}\left({\mathcal{C}}(f_{g-3},f_{g-2},f_{g-1})\right)\subset\mathbb{C}\left({\mathcal{C}}(f_{0},\ldots,f_{g-1})\right)\subset\mathbb{C}\left(X_{0}(N)\right)$,
we see that $d(f_{g-3},f_{g-2},f_{g-1})=2d$. This proves (6-5).

Next, by the main result of [18], the product
$d(f_{g-3},f_{g-2},f_{g-1})\cdot\deg{P_{f_{g-3},f_{g-2},f_{g-1}}}$ is given by

$2(g-1)-\sum_{\mathfrak{a}\in
X_{0}(N)}\min{\left(\mathfrak{c}_{f_{g-3}}(\mathfrak{a}),\mathfrak{c}_{f_{g-2}}(\mathfrak{a}),\mathfrak{c}_{f_{g-1}}(\mathfrak{a})\right)},$

where effective divisors $\mathfrak{c}_{f_{g-3}},\mathfrak{c}_{f_{g-2}}$, and
$\mathfrak{c}_{f_{g-1}}$ are defined by [18, Lemma 2.1]. By (6-3), we have

$\sum_{\mathfrak{a}\in
X_{0}(N)}\min{\left(\mathfrak{c}_{f_{g-3}}(\mathfrak{a}),\mathfrak{c}_{f_{g-2}}(\mathfrak{a}),\mathfrak{c}_{f_{g-1}}(\mathfrak{a})\right)}\geq\min{\left(\mathfrak{c}_{f_{g-3}}(\mathfrak{a}_{\infty}),\mathfrak{c}_{f_{g-2}}(\mathfrak{a}_{\infty}),\mathfrak{c}_{f_{g-1}}(\mathfrak{a}_{\infty})\right)}=g-3.$

Thus, we obtain the following:

(6-7) $d(f_{g-3},f_{g-2},f_{g-1})\cdot\deg{P_{f_{g-3},f_{g-2},f_{g-1}}}\leq
2(g-1)-(g-3)=g+1.$

Considering case by case analysis based on (6-2) (described below), we compute
equations in SAGE, and find that $\deg{P_{f_{g-3},f_{g-2},f_{g-1}}}=2$ for all
$N$ in (6-2). Using (6-5) and (6-7), we obtain $d(f_{g-3},f_{g-2},f_{g-1})=2$
in all cases. This means that $\mathbb{C}\left(X_{0}(N)\right)$ is a quadratic
extension of $\mathbb{C}\left({\mathcal{C}}(f_{g-3},f_{g-2},f_{g-1})\right)$.
Since the explicit computations below show
$\mathbb{C}\left({\mathcal{C}}(f_{g-3},f_{g-2},f_{g-1})\right)$ is equal to
$\mathbb{C}\left(f_{g-1}/f_{g-2}\right)$, the proof lemma is complete.

Now, we give case by case analysis mentioned above. Assume $N=30$. We have
$g=3$. The equation of $\mathcal{C}(f_{g-3},f_{g-2},f_{g-1})$ is given by the
irreducible polynomial $-x^{2}_{1}+x_{0}x_{2}-x_{1}x_{2}$. We have

$\mathbb{C}\left({\mathcal{C}}(f_{g-3},f_{g-2},f_{g-1})\right)=\mathbb{C}\left(f_{g-3}/f_{g-2},f_{g-1}/f_{g-2}\right)=\mathbb{C}\left(f_{g-1}/f_{g-2}\right)$

since the equation of the curve implies
$-f^{2}_{g-2}+f_{g-3}f_{g-1}-f_{g-2}f_{g-1}=0$. Analogously, we treat
remaining cases. We leave details to the reader.

Assume that $N=33,35,39,40,41$, or $48$. We have $g=3$. The equations of
curves $\mathcal{C}(f_{g-3},f_{g-2},f_{g-1})$ are given by the irreducible
polynomials $-x^{2}_{1}+x_{0}x_{2}-2x^{2}_{2}$,
$-x^{2}_{1}-x_{0}x_{2}+2x_{1}x_{2}-x^{2}_{2}$,
$-x^{2}_{1}+x_{0}x_{2}+x_{1}x_{2}$, $-x^{2}_{1}+x_{0}x_{2}+x^{2}_{2}$,
$-x_{1}^{2}+x_{0}x_{2}+2x_{1}x_{2}$, and $-x^{2}_{1}+x_{0}x_{2}$,
respectively.

Assume $N=47$. Then, $g=4$. The equation of
$\mathcal{C}(f_{g-3},f_{g-2},f_{g-1})$ is given by the irreducible polynomial
$-x^{2}_{1}+x_{0}x_{2}+2x_{1}x_{2}-3x^{2}_{2}$.

Assume that $N=46$ or $59$. Then, $g=5$. The equations of
$\mathcal{C}(f_{g-3},f_{g-2},f_{g-1})$ are given by the irreducible
polynomials $-x^{2}_{1}+x_{0}x_{2}-x_{1}x_{2}$ and
$-x^{2}_{1}+x_{0}x_{2}+2x_{1}x_{2}-3x^{2}_{2}$, respectively.

Assume $N=71$. Then, $g=6$. The equation of
$\mathcal{C}(f_{g-3},f_{g-2},f_{g-1})$ is given by the irreducible polynomial
$-x^{2}_{1}+x_{0}x_{2}+2x_{1}x_{2}-3x^{2}_{2}$. ∎

## References

  * [1] R. Bröker, K. Lauter, A. V. Sutherland,Modular polynomials via isogeny volcanoes, Mathematics of Computation 81, 1201–1231 , (2012).
  * [2] B. Cho, N. M. Kim, J. K. Koo, Affine models of the modular curves $X(p)$ and its application, Ramanujan J. 24 , no. 2, 235–-257, (2011).
  * [3] J. H. Conway, A. Hulpke, J. McKay, On transitive permutation groups, LMS J. Computation and Mathematics, 1(1998), 1–8.
  * [4] C. Fieker, Galois groups of polynomials over $\mathbb{Q}(t)$ (2008). Magma implementation.
  * [5] C. Fieker, J. Klueners, Computation of Galois groups of rational polynomials, LMS J. Comput. Math. 17 (2014), no. 1, 141–158.
  * [6] C. Fieker, N. Sutherland, Constructions using Galois Theory, https://arxiv.org/abs/2010.01281, 2020.
  * [7] S. Galbraith, Equations for modular curves, Ph.D. thesis, Oxford (1996)
  * [8] N. Ishida, Generators and equations for modular function fields of principal congruence subgroups, Acta Arithmetica, 85 no 3, 197–207, (1998).
  * [9] D. Krumm, N. Sutherland, Galois groups over rational functional fields and explicit Hilbert irreducibility, J. Symbolic Comput. 103 (2021), 108–126.
  * [10] I. Kodrnja, On a simple model of $X_{0}(N)$, Monatsh. Math. 186 (2018), no. 4, 653–661.
  * [11] S. Lang, Algebra. Second edition., Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1984.
  * [12] Magma Computational Algebra System (Version Magma V2.26), Computational Algebra Group at the University of Sydney, 2021, http://magma.maths.usyd.edu.au/magma/
  * [13] T. Miyake, Modular forms, Springer-Verlag, (2006).
  * [14] R. Miranda,Algebraic Curves and Riemann Surfaces, Graduate Studies in Mathematics 5, (1995).
  * [15] G. Muić, Modular curves and bases for the spaces of cuspidal modular forms, Ramanujan J. 27, 181–-208, (2012)
  * [16] G. Muić, On embeddings of modular curves in projective spaces, Monatsh. Math. Vol. 173, No. 2, 239–256, (2014).
  * [17] G. Muić, D. Mikoč, Birational maps of $X(1)$ into $\mathbb{P}^{2}$, Glasnik Matematicki Vol. 48, No. 2, 301–312, (2013).
  * [18] G. Muić, On degrees and birationality of the maps $X_{0}(N)\rightarrow\mathbb{P}^{2}$ constructed via modular forms,  Monatsh. Math. Vol. 180, No. 3, 607–629, (2016).
  * [19] G. Muić, I. Kodrnja On primitive elements of algebraic function fields and models of $X_{0}(N)$, The Ramanujan Journal, 55 No. 2 (2021), 393–420 doi:10.1007/s11139-021-00423-w.
  * [20] A. P. Ogg, Hyperelliptic modular curves. Bull. Soc. Math. France 102 (1974), 449–462.
  * [21] I. R. Shafarevich,Basic algebraic geometry I: Varieties in projective space 3rd edition, Springer, 2013.
  * [22] G. Shimura, Introduction to the arithmetic theory of automorphic functions. Kanô Memorial Lectures, No. 1. Publications of the Mathematical Society of Japan, No. 11. Iwanami Shoten, Publishers, Tokyo; Princeton University Press, Princeton, N.J., (1971)
  * [23] M. Shimura,Defining Equations of Modular Curves $X_{0}(N)$, Tokyo J. Math. Vol. 18, No. 2, (1995)
  * [24] K. Ono, The Web of Modularity: Aithmetic of the Coefficients of Modular Forms and $q$–Series, Conference Board of the Mathematical Sciences 102, American Mathematical Society (2004).
  * [25] Sage Mathematics Software (Version 8.8), The Sage Developers, 2019, http://www.sagemath.org.
  * [26] J. P. Serre, Topics in Galois theory. Lecture notes prepared by Henri Damon [Henri Darmon]. With a foreword by Darmon and the author. Research Notes in Mathematics, 1. Jones and Bartlett Publishers, Boston, MA, 1992.
  * [27] Y. Yifan, Defining equations of modular curves, Advances in Mathematics 204, 481-–508, (2006)


# Smoothing complex-valued signals on graphs with Monte-Carlo

###### Abstract

We introduce new smoothing estimators for complex signals on graphs, based on
a recently studied _Determinantal Point Process_ (DPP). These estimators are
built from subsets of edges and nodes drawn according to this DPP, making up
trees and _unicycles_ , _i.e._ , connected components containing exactly one
cycle. We provide a Julia implementation of these estimators and study their
performance when applied to a ranking problem.

Index Terms—  magnetic laplacian, spanning forests, determinantal point
processes, graph smoothing, angular synchronization, ranking

##  1 Introduction

_Graph signal processing_ (GSP, [1]) usually considers real data defined over
the nodes of a graph $G=(V,E)$, and classically relies on the graph Laplacian.
For instance, a typical task in GSP consists in smoothing (denoising) a signal
$g\in\mathbb{R}^{V}$ by solving the penalized (Tikhonov) problem

$\underset{f\in\mathbb{R}^{V}}{\operatornamewithlimits{argmin}}\
q\|f-g\|^{2}+f^{\top}Lf$ (1)

where $L\in\mathbb{R}^{V\times V}$ is the graph Laplacian. We will consider
throughout weighted and undirected graphs. In Eq. (1), $f^{\top}Lf$ penalises
the squared-norm of the discrete derivative on the graph, _i.e._ :

$f^{\top}Lf=\sum_{e=(v,v^{\prime})}w_{e}(f(v^{\prime})-f(v))^{2},$

where the sum runs over all edges of the graph and $w_{e}>0$ is the edge
weight. Thus, the quadratic form $f^{\top}Lf$ can be thought of as i/
computing the squared difference between signal values along neighbouring
edges, ii/ computing a weighted sum.

For multivariate signals, defining a discrete derivative becomes less obvious,
as additional geometry enters the picture. For instance, taking
$f(v^{\prime})-f(v)$ along an edge $e=(v,v^{\prime})$ assumes that
$f(v^{\prime})$ and $f(v)$ use the same coordinate system, and introducing a
local change of basis along the edge $(v,v^{\prime})$ is a way to precise the
relation between $f(v)$ and $f(v^{\prime})$ [2]. We focus on complex-valued
signals $f\in\mathbb{C}^{V}$, for which a multiplication by $e^{i\theta_{e}}$,
where $\theta_{e}\in\left[0,2\pi\right]$, can for instance represent a known
phase offset between measurements $f(v^{\prime})$ and $f(v)$. In this setting,
we can define a _magnetic Laplacian_ $L\in\mathbb{C}^{V\times V}$ [3] (see
Appendix A) which acts as follows ($f^{*}$ denotes the conjugate transpose of
$f$):

$f^{*}Lf=\sum_{e=(v,v^{\prime})}w_{e}|f(v^{\prime})-e^{i\theta_{e}}f(v)|^{2}.$
(2)

Note that this equation supposes an orientation of each edge: each
$\theta_{e}$ is thus given with an orientation of $e$. This choice of
orientation is however arbitrary: for a given edge $e$, one orientation
associated to $\theta_{e}$ is equivalent to the other orientation associated
to $-\theta_{e}$ as
$|f(v^{\prime})-e^{i\theta_{e}}f(v)|^{2}=|e^{-i\theta_{e}}f(v^{\prime})-f(v)|^{2}$.
The set $\\{e^{i\theta_{e}}\\}_{e}$ describes a _unitary connection_ between
the nodes of $G$ [3].

Such Laplacians have applications to synchronization [4] and ranking problems
[5, 6, 7], as we explain in Section 4.

GSP algorithms that use the graph Laplacian often have $\mathcal{O}(|V|^{3})$
scaling when implemented exactly, due to the matrix inversions or
factorisations that are used (_e.g._ , the solution of Eq. (1) reads
$f_{o}=q(L+qI)^{-1}g$). In large graphs approximate methods are necessary, and
[8] introduced a Monte-Carlo estimator for the Tikhonov smoothing problem of
Eq. (1), with favourable asymptotic runtime. In this work we generalise the
estimator of [8] to complex signals, using a process recently introduced in
[9].

In Section 2, we introduce a slight variation of the random process of [9],
defined over graphs with a unitary connection. Our main theoretical results
are given in Section 3, where we derive estimators for the solution of the
Tikhonov smoothing problem. We describe a practical application to ranking in
Section 4. Some technical definitions and proofs are deferred to Appendices A,
B and C.

##  2 A process over multi-type spanning forests

We are interested in a distribution generalizing both the uniform distribution
over _spanning trees_ (UST) of a graph, and the _random spanning forests_
distribution [10]. A spanning tree is a subset of edges $\phi\subseteq E$ such
that the graph with nodes $V$ and edges $\phi$ is both connected and without
cycles (cycle-free). A rooted spanning forest (RSF) $\phi\subseteq E\cup V$ is
the combination of a spanning forest and a set of distinguished nodes called
the roots (one root per tree). A variation of these distributions can be
defined over the set of spanning forests of _unicycles_ (FU) [11, 3], subsets
of edges containing _exactly one_ cycle per connected component, and spanning
all the nodes in $V$. The generalization we consider instead draws its samples
from the set of rooted _multi-type spanning forests_ (MTSF). A rooted MTSF is
a spanning subset of edges and nodes $\phi\subseteq E\cup V$ whose connected
components are made up of rooted trees and _unicycles_. These different
structures are illustrated in Fig. 1.

We will use the following distribution, introduced in [9], over rooted MTSFs
$\phi=\phi_{\bullet}\cup\rho(\phi)$ of $G$:

$\mathbb{P}(\phi)\propto\prod_{r\in\rho(\phi)}q_{r}\prod_{e\in\phi_{\bullet}}w_{e}\prod_{C}\left(2-2\cos(\theta_{C})\right),$
(3)

with $\rho(\phi)$ the set of roots of $\phi$, $\phi_{\bullet}$ its set of
edges and $q_{v}\in\mathbb{R}^{*}_{+}$ positive parameters associated to each
node $v$. The third product is over the cycles of the unicycles in $\phi$,
where $\theta_{C}=\sum_{e\in C}\theta_{e}$.

Spanning tree

Spanning forest of unicycles

Rooted spanning forest

Rooted multi-type spanning forest

Fig. 1: Different subsets of edges and nodes, in red.

One may wonder why we do not consider the _uniform_ distribution over MTSFs
and instead favor sampling unicycles for which $2-2\cos(\theta_{C})$ is large,
meaning that these cycles are _inconsistent_. Part of the answer lies in the
fact that Eq. 3 is known to describe a _Determinantal Point Process_ (DPP)
over $E\cup V$, a useful property for proving the results in Section 3. More
details are available in Appendix B.1.

Aforementioned distributions such as USTs and RSFs are conveniently sampled
using (a variant of) Wilson’s algorithm [12], based on random walks on the
graph. These sampling procedures have been generalized to FUs [13] and,
recently, to MTSFs [9], under the sampling condition:

$\cos(\theta_{\gamma})\geq 0\text{ for all cycles $\gamma$.}$ (4)

Note that this condition applies to _all cycles_ $\gamma$ in $G$, and not only
in some MTSF $\phi$. The sampling algorithm is recalled in Appendix B.2.

Bounds on the running time of the sampling algorithm are discussed in [13, 9].
Here, we only mention that the expected running time is linear in the number
of edges, and that it decreases as $\min_{v}q_{v}$ increases.

##  3 Estimators for smoothing

Monte-Carlo estimators for smoothing on graphs have been developped using RSFs
[8]. The main idea is to sample a rooted RSF $\phi$ before propagating the
value of the function at the roots to the other nodes in their associated
trees. In the following, we show how this can be generalized to graphs with a
unitary connections using the distribution in Eq. 3. Proofs are given in
Appendix C. Specifically, given $g\in\mathbb{C}^{V}$ we derive estimators of
$f_{o}=(L+Q)^{-1}Qg$. Here $Q$ is the diagonal matrix of the $q_{v}$’s and
$L=D-A_{\theta}$ is the Hermitian _magnetic Laplacian_ matrix, with $D$ the
diagonal degree matrix and $(A_{\theta})_{v^{\prime},v}=e^{i\theta_{e}}$ if
$e=(v,v^{\prime})\in E$ ($0$ if $e\notin E$). When $q_{v}=q>0$ for all $v\in
V$, $f_{o}$ is the optimal solution of the penalized Tikhonov problem:

$\underset{f\in\mathbb{C}^{V}}{\operatornamewithlimits{argmin}}\
q\|f-g\|^{2}+f^{*}Lf.$

The first estimator $\tilde{f}$ is built by propagating values through the
transport maps $z\mapsto e^{i\theta_{e}}z$ on a rooted multi-type spanning
forest $\phi$ sampled according to Eq. 3:

$\tilde{f}(v)=\left\\{\begin{array}[]{ll}\psi_{r_{\phi}(v)\rightarrow
v}g(r_{\phi}(v))&\text{if the connected component of}\\\ &\text{$v$ is a
rooted tree,}\\\ 0&\text{otherwise,}\end{array}\right.$

where $r_{\phi}:V\rightarrow V$ maps nodes to the root of the tree containing
them, $a\rightarrow b$ denotes the unique path from $a$ to $b$ in $\phi$ and
$\psi_{a\rightarrow b}=\prod_{e\in a\rightarrow b}e^{i\theta_{e}}$.

######  Proposition 1.

$\tilde{f}$ is an unbiased estimator of $f_{o}$:

$\mathbb{E}_{\phi}(\tilde{f})=f_{o}.$

As a consequence of the Central Limit Theorem, Monte-Carlo estimators converge
at a $\mathcal{O}(\frac{\sigma}{\sqrt{n}})$ rate, with $\sigma$ the standard
deviation of the estimator and $n$ the number of samples. Instead of
increasing the number of samples one may instead focus on decreasing the
variance, and in our setting this can be done at little additional cost. A
first approach is to use a Rao-Blackwell version of the estimator $\tilde{f}$
(see [14, 15]) by conditioning on the set of _unrooted_ connected components
$\pi\subseteq E$ of the MTSF. Consider the estimator:

$\overline{f}(v)=\left\\{\begin{array}[]{ll}\psi_{r_{\phi}(v)\rightarrow
v}h(r_{\phi}(v))&\text{if the connected component}\\\ &\text{of $v$ is a
rooted tree,}\\\ 0&\text{otherwise,}\end{array}\right.$

where $h(u)=\frac{\sum_{w\in T_{u}}q_{w}\psi_{w\to u}g(w)}{\sum_{w\in
T_{u}}q_{w}},$ with $T_{v}$ the tree containing $v$ in $\phi$.

######  Proposition 2.

We have $\forall v\in
V,\overline{f}(v)=\mathbb{E}_{\phi}(\tilde{f}(v)|\phi_{\bullet}=\pi)$ and, as
a consequence:
$\mathbb{E}_{\pi}(\overline{f})=\mathbb{E}_{\phi}(\tilde{f})=f_{o}$. Also, by
the law of total variance, $\overline{f}(v)$ has a lower variance than
$\tilde{f}(v)$:

$\mathrm{Var}(\overline{f}(v))=\mathrm{Var}(\tilde{f}(v))-\mathbb{E}(\mathrm{Var}(\tilde{f}(v)|\phi_{\bullet}=\pi))\leq\mathrm{Var}(\tilde{f}(v))$

Here, variance reduction is achieved solely from computing a mean over the
nodes of the rooted trees.

The method of control variates is another classical variance-reduction
technique for Monte-Carlo estimators, and consists in adding a term with zero
mean to obtain a modified estimator with the same expectation but lower
variance [16]. The following is proved in [17], when $q_{v}=q$ for all $v\in
V$ (_i.e._ $Q=qI$.)

######  Proposition 3.

Set $\alpha=\frac{2q}{q+2d_{m}}$, where $d_{m}$ is the maximum degree in the
graph. Then, the estimator

$\hat{f}=\overline{f}-\alpha(q^{-1}(L+qI)\overline{f}-g)$

is an unbiased estimator of $f_{o}$ and verifies

$\forall v\in
V\qquad\mathrm{Var}(\hat{f}(v))\leq\mathrm{Var}(\overline{f}(v))$

This choice of $\alpha$ is expected to work well on graphs with nearly-
homogeneous degree distribution, which is the case for the graphs considered
in Section 4, where we obtain substantial improvements over $\overline{f}$.

##  4 Ranking from corrupted measurements

(a) $p=0.9$

(b) $p=0.6$

(c) $p=0.6$

(d) $p=0.6$

(e) $k=5,p=0.6$

(f) $k=10,p=0.6$

(g) $k=10,p=0.9$

(h) $p=0.6$

Fig. 2: Experimental results.

In order to study the actual performance of our estimators, we describe an
application to the _ranking_ problem. We focus on the ordinal ranking problem,
which asks to linearly order a set $X$ of $n$ elements according to an
incomplete, possibly incoherent, set of pairwise ordinal comparisons
$C_{i,j}\in\\{-1,1\\}$, for $j>i$. From this data, build a graph $G$ with $n$
nodes, and a directed edge from $i$ to $j$ if $C_{i,j}=1$ (resp. from $j$ to
$i$ if $C_{i,j}=-1$). Ranking according to [6, 7] then suggests to define the
unitary connection $\theta_{i,j}=\frac{\pi\delta C_{i,j}}{n}$ with
$\delta\in(0,1)$, and to perform _angular synchronization_ [4, 18] by solving:

$\operatornamewithlimits{argmin}_{(\omega_{v})_{v\in
V}}\sum_{e=(v,v^{\prime})}|e^{i\omega_{v^{\prime}}}-e^{i\theta_{e}}e^{i\omega_{v}}|^{2}.$
(5)

The optimal arguments $\omega_{i}$ then describe an embedding of the $n$
points onto the unit circle, from which we can extract a ranking (see [7] for
more details).

In practice, solving such a non-convex optimization problem is difficult, and
a spectral relaxation is considered instead:

$\min_{f\in\mathbb{C}^{n},\|f\|^{2}=n}f^{*}\tilde{L}f,$

for $\tilde{L}=D^{-1/2}LD^{-1/2}$ the normalized graph Laplacian, with $D$ the
diagonal degree matrix. The solution of this classical problem is the
eigenvector associated to the smallest eigenvalue of $\tilde{L}$, which can
for instance be computed by iterating the map $x\mapsto Mx/\|Mx\|$ for
$M=q(\tilde{L}+qI)^{-1}$, this is the power method [19]. Computing $x\mapsto
Mx$ can either be performed directly by solving a linear system, or using the
estimators $\tilde{f}$, $\overline{f}$ and $\hat{f}$.

If we set $\delta=\frac{1}{4}$, the sampling condition in Eq. 4 is satisfied
and fast sampling can be achieved using the variation of Wilson’s algorithm
recalled in Appendix B.2.

###  4.1 Experimental results

We illustrate in Fig. 2 some results regarding the performance of this
approach obtained with our Julia implementation111https://gricad-gitlab.univ-
grenoble-alpes.fr/tremblan/mtsf_for_graph_smoothing. We work with comparisons
$C_{i,j}$ randomly obtained from a ground-truth ranking $r_{GT}$ according to
the Erdös-Rényi Outliers model [7]: a comparison is observed with probability
$s$; if a comparison is observed, it follows the ranking $r_{GT}$ with
probability $p$, or is chosen uniformly in $\\{-1,1\\}$ otherwise. We focus on
the computationally challenging dense case and set $s=0.8$. Unless otherwise
specified, we use $q=0.1$. . The performance of the estimator $\hat{f}$ in
recovering the underlying ranking, using $m=5$ MTSFs _for each_ of the $k=10$
iterations of the power method, is illustrated in Figs. 2(a) and 2(b) for two
graphs of size $n=300$ and $p\in\\{0.6,0.9\\}$. The eigenvector of $L$
computed from the power method _without_ using the estimator is also plotted.
Here, the initialization vector $y_{0}$ used for the power method is a random
embedding of the $n$ points in the unit circle, spaced out with angle
$\frac{\pi}{2n}$.

Runtime benchmarks are available in Figs. 2(c) and 2(d) for the smoothing
problem (computation of $My_{0}$) solved either using $\hat{f}$ or using a
Cholesky decomposition, and for the computation of the eigenvector of $M$ for
the power method iteration using $\hat{f}$ or a Cholesky decomposition, and
for the Lanczos method. We display the mean running time over $100$
measurements on fixed graphs of size $n\in\\{10,10^{2},10^{3},10^{4}\\}$.

We plot Kendall’s $\tau$ coefficients [20] (the larger the better) for the
rankings recovered from the power method in Figs. 2(e), 2(f) and 2(g) for
$n=3000$ and varying $q$, averaging over $20$ realisations. Note that we still
used _fixed_ $m=5$ and $k=10$.

Reconstruction errors $\|My-\mathrm{e}(f_{o})\|$ across varying $m$, averaged
over $20$ runs for each of the estimators $\mathrm{e}(f_{o})$ of $f_{o}$, are
in Fig. 2(h) with $n=3000$.

###  4.2 Discussion

The results in Figs. 2(a) and 2(b) compare the performance of the
reconstructions obtained by the power method with and without using $\hat{f}$,
on only one realization of the graph. For these noise regimes, the ground
truth ranking $\tau_{GT}$ can no longer be recovered (which would result in a
straight diagonal line). In both cases, the recovered ranking is slightly more
spread out when using the estimator instead of the exact power method.

We obtain faster runtime in the smoothing problem than a standard Cholesky
decomposition, in graphs with more than $n\sim 10^{3}$ nodes (Fig. 2(c)). For
the eigenvector computation in Fig. 2(d), cross-over occurs at $n\sim 10^{4}$
against the power method, while we do not outperform a direct Lanczos
iteration. Note that performance for the eigenvector computation may be
increased by sampling only one set of $m=5$ MTSFs, used for all iterations of
the power method. Moreover, our current implementation is far from optimal.

As $q$ decreases, the $\tau$ coefficient increases until it reaches a fixed
value in Figs. 2(e), 2(f) and 2(g). Comparing of Figs. 2(e) and 2(f) shows
that this behavior actually reflects the convergence of the power method, as
the spectral gap of $M$ is lower for larger $q$, requiring more iterations to
converge. This suggests that there is a trade-off for the best choice of $q$:
it should be as large as possible in order to reduce sampling time, and not
too large so that it allows fast convergence of the power method. Note also
that Kendall’s $\tau$ seems to reach the value of $p$ when convergence occurs.

Regarding the convergence of the estimators, all three versions of the
estimators in Fig. 2(h) have linear decay in log-log-scale, which is
characteristic of the $\mathcal{O}(1/\sqrt{n})$ convergence rate of Monte-
Carlo estimators. In our simulations, the estimator $\hat{f}$ improves on the
regular estimator by a factor of $10$.

Throughout these experiments, we sampled $m=5$ MTSFs to compute the
estimators. Here, this choice was arbitrary, but we notice nonetheless that
this is of the order of the $\mathcal{O}(\log|V|)$ uniform spanning trees
necessary to obtain spectral sparsifiers for connection-free graphs [21],
recently adapted to MTSFs in [9].

##  5 Conclusion

We define new estimators built by propagating values along edges sampled
according to a recently introduced DPP, for the smoothing problem on graphs
endowed with a unitary connection, thus generalizing previous existing
approaches on graphs. The evaluation of these estimators on the ranking
problem, using our Julia implementation, show that they can be advantageous
for smoothing starting from moderately sized graphs, as compared to a Cholesky
decomposition, while they do not improve on a Lanczos iteration for
eigenvector computation. Nonetheless, the proposed estimators exhibit a
potentially useful computational property that is uncommon among deterministic
algorithms: their computation can be carried out without any prior global
knowledge of the graph, from local neighbor queries only, which in some
scenarii may be the only practical interaction. The choice of the parameters
$q$ and $m$ is application-dependent, and requires further investigation.
Possible extensions of this work include designing new applications of the
proposed estimators, as well as generalizing this approach to higher-
dimensional signals, where current arguments do not carry over.

## References

  * [1] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst,  “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,”  IEEE signal processing magazine, vol. 30, no. 3, pp. 83–98, 2013\.
  * [2] Amit Singer and H-T Wu,  “Vector diffusion maps and the connection laplacian,”  Communications on pure and applied mathematics, vol. 65, no. 8, pp. 1067–1144, 2012.
  * [3] Richard Kenyon,  “Spanning forests and the vector bundle Laplacian,”  The Annals of Probability, vol. 39, no. 5, pp. 1983–2017, 2011\.
  * [4] Amit Singer,  “Angular synchronization by eigenvectors and semidefinite programming,”  Applied and computational harmonic analysis, vol. 30, no. 1, pp. 20–36, 2011.
  * [5] X Yu Stella,  “Angular embedding: from jarring intensity differences to perceived luminance,”  in 2009 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009, pp. 2302–2309.
  * [6] Stella Yu,  “Angular embedding: A robust quadratic criterion,”  IEEE transactions on pattern analysis and machine intelligence, vol. 34, no. 1, pp. 158–173, 2011.
  * [7] Mihai Cucuringu,  “Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and sdp synchronization,”  IEEE Transactions on Network Science and Engineering, vol. 3, no. 1, pp. 58–79, 2016.
  * [8] Yusuf Yiğit Pilavcı, Pierre-Olivier Amblard, Simon Barthelmé, and Nicolas Tremblay,  “Graph Tikhonov regularization and interpolation via random spanning forests,”  IEEE transactions on Signal and Information Processing over Networks, vol. 7, pp. 359–374, 2021.
  * [9] Michaël Fanuel and Rémi Bardenet,  “Sparsification of the regularized magnetic Laplacian with multi-type spanning forests,”  arXiv preprint arXiv:2208.14797, 2022.
  * [10] Luca Avena and Alexandre Gaudillière,  “On some random forests with determinantal roots,”  Preprint: Weierstraß-Institut für Angewandte Analysis und Stochastik, vol. 1881, 2013.
  * [11] Robin Forman,  “Determinants of Laplacians on graphs,”  Topology, vol. 32, no. 1, pp. 35–46, 1993.
  * [12] David Bruce Wilson,  “Generating random spanning trees more quickly than the cover time,”  in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 296–303.
  * [13] Adrien Kassel and Richard Kenyon,  “Random curves on surfaces induced from the Laplacian determinant,”  The Annals of Probability, vol. 45, no. 2, pp. 932–964, 2017.
  * [14] David Blackwell,  “Conditional expectation and unbiased sequential estimation,”  The Annals of Mathematical Statistics, pp. 105–110, 1947.
  * [15] C Radhakrishna Rao,  “Information and the accuracy attainable in the estimation of statistical parameters,”  in Breakthroughs in statistics, pp. 235–247. Springer, 1992.
  * [16] Zdravko Botev and Ad Ridder,  “Variance reduction,”  Wiley statsRef: Statistics reference online, pp. 1–6, 2017.
  * [17] Yusuf Pilavcı, Pierre-Olivier Amblard, Simon Barthelmé, and Nicolas Tremblay,  “Variance reduction in stochastic methods for large-scale regularised least-squares problems,”  arXiv preprint arXiv:2110.07894, 2021.
  * [18] Afonso S Bandeira,  “Ten lectures and forty-two open problems in the mathematics of data science,”  Lecture Notes, 2015.
  * [19] Yousef Saad,  Numerical methods for large eigenvalue problems: revised edition,  SIAM, 2011.
  * [20] Maurice G Kendall,  “A new measure of rank correlation,”  Biometrika, vol. 30, no. 1/2, pp. 81–93, 1938.
  * [21] Tali Kaufman, Rasmus Kyng, and Federico Soldá,  “Scalar and matrix chernoff bounds from $l_{\infty}$-independence,”  in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2022, pp. 3732–3753.
  * [22] Fan RK Chung and Fan Chung Graham,  Spectral graph theory, vol. 92,  American Mathematical Soc., 1997.
  * [23] Odile Macchi,  “The coincidence approach to stochastic point processes,”  Advances in Applied Probability, pp. 83–122, 1975.
  * [24] Alex Kulesza and Ben Taskar,  “Determinantal point processes for machine learning,”  Foundations and Trends® in Machine Learning, vol. 5, no. 2–3, pp. 123–286, 2012.
  * [25] Michał Derezinski and Michael W Mahoney,  “Determinantal point processes in randomized numerical linear algebra,”  Notices of the American Mathematical Society, vol. 68, no. 1, pp. 34–45, 2021.

new page

##  Appendix A Technical definitions

We provide some technical definitions used in Appendices B and C.

Recall the definition of the graph Laplacian $L=\nabla^{*}\nabla$ [22], with
$\nabla\in\mathbb{R}^{E\times V}$ the (weighted) $|E|\times|V|$ edge-vertex
incidence matrix. The graph Laplacian reveals many properties of functions
$f\in\mathbb{R}^{V}$ defined on $G$. For instance, if the graph is connected,
the one-dimensional kernel of $L$ is generated by the constant function.

When considering complex signals $f\in\mathbb{C}^{V}$ on $G$, one first
defines a _unitary connection_ given by a family
$\psi_{v,e}=e^{i\theta_{v,e}}$ of unitary complex numbers, extended by
$\psi_{v,e}=\psi_{e,v}^{*}$ and
$\psi_{v,v^{\prime}}=\psi_{e,v^{\prime}}\psi_{v,e}=e^{i\theta{v,v^{\prime}}}$.
This connection gives rise to a _magnetic Laplacian_ $L=\nabla^{*}\nabla$ [3],
with $\nabla$ a twisted discrete differential:

$\nabla_{e,v}=\begin{cases}-\sqrt{w_{e}}\psi_{v,e}&\text{ if $v=a$,}\\\
\sqrt{w_{e}}\psi_{v,e}&\text{ if $v=b$,}\\\ 0&\text{otherwise},\end{cases}$

for $e=(a,b)$. Unlike the usual graph Laplacian, the magnetic Laplacian has a
trivial kernel ($\ker{L}=0$), unless the connection is _trivial_ [9], which is
a key difference in the analysis of the DPP described in Appendix B.1.

##  Appendix B DPP and smoothing estimators

###  B.1 Background on DPP and the MTSF process

A (discrete) Determinantal Point Process (DPP) is a distribution over subsets
of a finite set $\mathrm{\mathcal{X}}$ parameterized by a symmetric matrix
$K\in M_{|\mathrm{\mathcal{X}}|}(\mathbb{C})$ whose eigenvalues all lie in
$\left[0,1\right]$, this matrix is the _marginal kernel_ of the process. We
say that $X\subseteq\mathrm{\mathcal{X}}$ is distributed according to this DPP
if $\mathbb{P}(A\subseteq X)=\det K_{A,A}$ for every
$A\subseteq\mathrm{\mathcal{X}}$, where $K_{S,T}$ denotes the submatrix matrix
of $K$ whose rows (resp. columns) have been restricted to $S$ (resp. $T$). If
$K$ is a projection matrix (i.e. its eigenvalues are either $0$ or $1$),
additional structural properties are ensured. For instance, a DPP based of $K$
will only give non-zero probability to samples of size $\mathrm{rk}(K)$, the
rank of $K$.

DPPs were introduced as _repulsive_ processes [23], and have been sought after
in machine learning [24] and randomized linear algebra [25].

######  Proposition 4.

The probabilities in Eq. 3 define a (projective) DPP over $E\cup V$, with
marginal kernel

$K_{m}=\begin{bmatrix}\nabla\\\
\sqrt{Q}\end{bmatrix}(L+Q)^{-1}\begin{bmatrix}\nabla^{*}\
\sqrt{Q}\end{bmatrix},$

with $Q$ the $|V|\times|V|$ diagonal matrix of the $q_{v}$’s.

###### Proof.

See [9]. This can also be proved by a straightforward extension of the
computations in [3]. ∎

This property further relates our study to that of USTs, RSFs and FUs, which
have also been showed to be DPPs [10, 3].

When working with DPPs, the Cauchy-Binet formula is an important technical
tool, and states that for an $m\times m$ matrix $M=AB$, with $A$ $m\times n$,
$B$ $n\times m$ and where $n>m$ we have:

$\det M=\sum_{T}\det A_{:,T}\det B_{T,:},$

where the sum is over $T\subseteq\\{1,...,n\\}$ of size $|T|=m$.

###  B.2 Sampling

We briefly recall the sampling algorithm from [9]. Under the condition in Eq.
4, a MTSF $\phi$ distributed according to Eq. 3 is built by iterating the
following until all nodes belong to $\phi$.

  * a)

Start a random walk from any node $v$ not in $\phi$, while keeping track of
the path $p$ built from this random walk. The transitions are as follows: with
probability proportional to $q$, set the current node as a root. Otherwise,
choose a successor $u$ in the neighborhood of the current node $w$ with
probability proportional to $w_{(w,u)}$.

  * b)

If a node $r$ is designated as a root, add it to the forest $\phi$ together
with the path $p$ and stop the random walk.

  * c)

If the path $p$ self-intersects at $w\in V$ before reaching a node in $\phi$,
and forms a loop $C$: keep this loop in $p$ with probability
$1-\cos(\theta_{C})$, add $p$ to the forest $\phi$ and stop the random walk.
Otherwise, erase this loop and continue the random walk from $w$.

  * d)

If $p$ reaches a node in $\phi$, stop the random walk and add the path $p$ to
the forest $\phi$.

Note that the $\theta_{C}$ _a priori_ depends on the orientation of the loop,
but $\cos(\theta_{C})$ is orientation-agnostic. Such random walk based
sampling algorithms are a noteworthy instance of efficient DPP sampling, which
usually require a diagonalization of the kernel $K$ and would result here in
$\mathcal{O}((|E|+|V|)^{3})$ sampling time.

##  Appendix C Proofs for Section 3

We provide straightforward proofs of the Propositions 1 and 2 in Section 3.
Unless otherwise specified, we work with rooted MTSFs sampled according to Eq.
3.

###  C.1 Proof of Proposition 1

The main part of the proof consists in rewriting $(L+Q)^{-1}$ as an
expectation (see Eq. 7). We first use Cramer’s rule to express the
coefficients of $(L+Q)^{-1}$:

$(L+Q)^{-1}_{i,j}=(-1)^{i+j}\frac{\det(L+Q)_{-j,-i}}{\det(L+Q)},$

where $-k=V\setminus\\{k\\}$.

For the denominator, we obtain the following sum over MTSFs (see e.g. [9])

$\det(L+Q)=\sum_{\phi}\prod_{r\in\rho(\phi)}q_{r}\prod_{e\in\phi_{\bullet}}w_{e}\prod_{C}(2-2\cos(\theta_{C})),$

which is the normalizing constant in Eq. 3. The Cauchy-Binet formula further
allows to express $\det(L+Q)_{-j,-i}$ as:

$\sum_{\phi\subseteq E\cup V,|\phi|=|V|-1}\det\begin{bmatrix}\nabla^{*}\
\sqrt{Q}\end{bmatrix}_{-j,\phi}\det\begin{bmatrix}\nabla\\\
\sqrt{Q}\end{bmatrix}_{\phi,-i},$

which can be re-arranged to obtain:

$\sum_{\phi\subseteq E\cup
V,|\phi|=|V|-1}(-1)^{i+j}\det\begin{bmatrix}\begin{bmatrix}\nabla^{*}\
\sqrt{Q}\end{bmatrix}_{:,\phi}\
\delta_{j}\end{bmatrix}\det\begin{bmatrix}\begin{bmatrix}\nabla\\\
\sqrt{Q}\end{bmatrix}_{\phi,:}\\\ \delta_{i}^{*}\end{bmatrix},$ (6)

with the canonical basis vector $\delta_{i}\in\mathbb{R}^{V}$.

The product of determinants in Eq. 6 can be split along the connected
components $\phi^{k}\subseteq E\cup V$ of $\phi$. Using similar computations
as [3], we find this product is non-zero if one of these connected components
$\phi^{k}$ is a tree containing $i$ and $j$ with no root for which the product
of determinants is $\psi_{j\rightarrow i}\prod_{e\in\phi^{k}_{\bullet}}w_{e}$
and, if this component does not span the entire graph, the remaining subgraph
contains disjoint connected components which have to be taken among the
following subgraphs:

  * •

a unicycle with cycle $C$ for which the product is
$(2-2\cos(\theta_{C}))\prod_{e\in\phi^{k}_{\bullet}}w_{e}$,

  * •

a rooted tree with root $r$ for which the product is
$q_{r}\prod_{e\in\phi^{k}_{\bullet}}w_{e}$.

In the end, when computing the sum, this translates to:

$\displaystyle(L+Q)_{i,j}^{-1}$ $\displaystyle=\sum_{\phi}\psi_{j\rightarrow
i}\mathbf{1}_{i\sim j}\mathbb{P}(\phi\ |\ j\in\rho(\phi))$ (7)
$\displaystyle=\mathbb{E}(\psi_{j\rightarrow i}\mathbf{1}_{i\sim j}\ |\
j\in\rho(\phi)),$

where $\mathbf{1}_{i\sim j}$ is the indicator that $i$ and $j$ belong to the
same tree.

Writing out the formula for the optimal solution $f_{o}$ finally yields:

$\displaystyle f_{o}(i)$ $\displaystyle=\delta_{i}^{*}(L+Q)^{-1}Qg$
$\displaystyle=\sum_{j}q_{j}(L+Q)^{-1}_{i,j}g(j)$
$\displaystyle=\sum_{j}\mathbb{P}(j\in\rho(\phi))\mathbb{E}(\psi_{j\rightarrow
i}g(j)\mathbf{1}_{i\sim j}\ |\ j\in\rho(\phi))$
$\displaystyle=\mathbb{E}(\tilde{f}(i)),$ (8)

where the second to last equation is obtained from Eq. 7, and the last line
follows from the law of total expectation.

###  C.2 Proof of Proposition 2

Suppose that $\phi_{\bullet}=\pi$, denote by $r_{k}$ the root of the connected
component $\phi_{\bullet}^{k}$, and by $V_{k}$ the set of vertices in
$\phi^{k}$. Then, if $v$ belongs to $\pi^{k}$ a tree:

$\displaystyle\mathbb{E}_{\phi^{k}}(\tilde{f}(v)\ |\
\phi_{\bullet}^{k}=\pi^{k})$ $\displaystyle=\sum_{r\in
V_{k}}\mathbb{P}(r_{k}=r)\tilde{f}(v)$ $\displaystyle=\sum_{r\in
V_{k}}\frac{q_{r}}{\sum_{w\in V_{k}}q_{w}}\psi_{r\rightarrow v}g(r)$
$\displaystyle=\overline{f}(v).$

If $\pi^{k}$ is a unicycle, then $\mathbb{E}(\tilde{f}(v))=0$.

The two consequences follow from the laws of total expectation and variance.