# Hrushovski’s Algorithm for
Computing the Galois Group of a Linear Differential Equation

Ruyong<EMAIL_ADDRESS>This work is partially supported by a
National Key Basic Research Project of China (2011CB302400) and by a grant
from NSFC (60821002).
KLMM, AMSS, Chinese Academy of Sciences,
Beijing 100190, China

###### Abstract

We present a detailed and simplified version of Hrushovski’s algorithm that
determines the Galois group of a linear differential equation. There are three
major ingredients in this algorithm. The first is to look for a degree bound
for proto-Galois groups, which enables one to compute one of them. The second
is to determine the identity component of the Galois group that is the
pullback of a torus to the proto-Galois group. The third is to recover the
Galois group from its identity component and a finite Galois group.

##  1 Introduction

In [6], Hrushovski developed an algorithm to compute the Galois groups for
general linear differential equations. To the best of my knowledge, this is
the first algorithm that works for all linear differential equations with
rational function coefficients. Before Hrushovski’s results, the known
algorithms were only valid for linear differential equations of special types,
for instance, low order or completely reducible equations. The algorithm due
to Kovacic ([7]) deals with the second order equations. In [12], the authors
determined the structural properties of the Galois groups of second and third
order linear differential equations. In many cases these properties can be
used to determine the Galois groups. In [2], the authors gave an algorithm to
compute the Galois group of linear differential equations that are completely
reducible. The reader is referred to [11, 15] for the survey of algorithmic
aspects of Galois groups and the references given there for more results. In
particular, in [11], the author gave a clear explanation of the method based
on Tannakian philosophy and introduced the various techniques that were used
in the known algorithms.

Throughout the paper, $C$ denotes an algebraically closed field of
characteristic zero and $k=C(t)$ is the differential field with the usual
derivation $\delta=\frac{d}{dt}$. The algebraic closure of $k$ is denoted by
$\bar{k}$. Linear differential equations we consider here will be of the
matrix form:

$\delta(Y)=AY,$ (1)

where $Y$ is a vector with $n$ unknowns and $A$ is an $n\times n$ matrix with
entries in $k$. Denote the Picard-Vessiot extension field of $k$ for (1) by
$K$ and the solution space of (1) by $V$. Then the Galois group of (1) over
$k$, denoted by ${\mbox{\rm Gal}}(K/k)$, are defined as the group of
differential automorphisms of $K$ that keep all elements of $k$ fixed. For
brevity, we usually use ${\mathcal{G}}$ to denote this group. ${\mathcal{G}}$
is a subgroup of ${\rm GL}(V)$. A matrix in ${\rm GL}_{n}(K)$ whose columns
form a basis of $V$ is called a fundamental matrix of (1).

Elements of $V^{n}$ are vectors with $n^{2}$ coordinates. For the sake of
convenience, elements of $V^{n}$ are also written in the matrix form. In such
a case, $V^{n}=\\{Fh|h\in{\rm Mat}_{n}(C)\\}$, where $F$ is a fundamental
matrix of (1). Set

$V^{n}_{inv}=\\{Fh|h\in{\rm GL}_{n}(C)\\}.$

Then $V_{inv}^{n}$ is an open subset of $V^{n}$. Note that if $F=I_{n}$, then
$V^{n}_{inv}={\rm GL}_{n}(C)$. In this paper, we will always use $X$ to denote
the $n\times n$ matrix whose entries are indeterminates $x_{i,j}$. Without any
possible ambiguity, we will also use $X$ to denote the set of indeterminates.
Let $Z$ be a subset of $V^{n}_{inv}$. $Z$ is said to be a Zariski closed
subset of $V_{inv}^{n}$ if there are polynomials $P_{1}(X),\cdots,P_{m}(X)$
such that $Z={\mbox{\rm Zero}}(P_{1}(X),\cdots,P_{m}(X))\cap V_{inv}^{n}$. In
this case, we also say that $Z$ is defined by $P_{1}(X),\cdots,P_{m}(X)$. We
will use $N_{d}(V_{inv}^{n})$ to denote the set of all subsets of
$V_{inv}^{n}$, which are defined by finitely many polynomials with degree not
greater than $d$. Note that here we have no requirement for the coefficients
of these polynomials. Suppose that $\tilde{k}$ is an extension field of $k$
and $Z\subseteq V_{inv}^{n}$. If $Z$ can be defined by polynomials with
coefficients in $\tilde{k}$, then $Z$ is said to be $\tilde{k}$-definable. The
stabilizer of $Z$, denoted by ${\rm stab}(Z)$, is defined as the subgroup of
${\rm GL}(V)$ whose elements keep $Z$ unchange. Let $Z\in N_{d}(V_{inv}^{n})$.
In case that we emphasize the degree $d$ of defining polynomials, we will also
say “$Z$ is bounded by $d$”.

Let $F$ be a fundamental matrix. For any $\sigma\in{\rm GL}(V)$, there exists
$[\sigma]\in{\rm GL}_{n}(C)$ such that $\sigma(F)=F[\sigma]$. The map
$\phi_{F}:{\rm GL}(V)\rightarrow{\rm GL}_{n}(C)$, given by
$\phi_{F}(\sigma)=[\sigma]$, is a group isomorphism and
$\phi_{F}({\mathcal{G}})$ is an algebraic subgroup of ${\rm GL}_{n}(C)$. Let
${\mathcal{H}}$ be a subgroup of ${\rm GL}_{n}(V)$. For ease of notations, we
use ${\mathcal{H}}_{F}$ to denote $\phi_{F}({\mathcal{H}})$. ${\mathcal{H}}$
is said to be an algebraic subgroup if so is ${\mathcal{H}}_{F}$. Assume that
${\mathcal{H}}$ is an algebraic subgroup. Then
${\mathcal{H}}^{\circ},{\mathcal{H}}^{t}$ are used to denote the pre-images of
${\mathcal{H}}_{F}^{\circ}$ and ${\mathcal{H}}_{F}^{t}$, where
${\mathcal{H}}_{F}^{\circ}$ denotes the identity component of
${\mathcal{H}}_{F}$ and ${\mathcal{H}}_{F}^{t}$ is the intersection of kernels
of all characters of ${\mathcal{H}}_{F}$. ${\mathcal{H}}$ is said to be
bounded by $d$ if so is ${\mathcal{H}}_{F}$.

The key point of Hrushovski’s algorithm is that one can compute an integer
$\tilde{d}$ such that there is an algebraic subgroup ${\mathcal{H}}$ (or
${\mathcal{H}}_{F}$) of ${\rm GL}(V)$ bounded by $\tilde{d}$ satisfying

$(*):({\mathcal{H}}^{\circ})^{t}\unlhd{\mathcal{G}}^{\circ}\leq{\mathcal{G}}\leq{\mathcal{H}},\,\,\mbox{or}\,\,\,\,({\mathcal{H}}_{F}^{\circ})^{t}\unlhd{\mathcal{G}}_{F}^{\circ}\leq{\mathcal{G}}_{F}\leq{\mathcal{H}}_{F}.$

For simplicity of presentation, we introduce the following notion.

###### Definition 1.1

The algebraic group ${\mathcal{H}}$ $($or ${\mathcal{H}}_{F}$$)$ in $(*)$ is
called a proto-Galois group of (1).

Roughly speaking, Hrushovski’s approach includes the following steps.

  * $(S1)$

(proto-Galois groups). One can compute an integer $\tilde{d}$ only depending
on $n$ such that there is a proto-Galois group of (1), which is bounded by
$\tilde{d}$. Let ${\mathcal{H}}$ be the intersection of the stabilizers of
$k$-definable elements of $N_{\tilde{d}}(V^{n}_{inv})$. Then ${\mathcal{H}}$
is a desired proto-Galois group of (1).

  * $(S2)$

(The toric part). Compute ${\mathcal{H}}_{F}^{\circ}$ and let
$\chi_{1},\cdots,\chi_{l}$ be generators of the character group of
${\mathcal{H}}_{F}^{\circ}$. Then the map $\varphi=(\chi_{1},\cdots,\chi_{l})$
is a morphism from ${\mathcal{H}}_{F}^{\circ}$ to $(C^{*})^{l}$.
$\varphi({\mathcal{G}}_{F}^{\circ})$ is the Galois group of some exponential
extension $E$ of $\tilde{k}$ over $\tilde{k}$, where $\tilde{k}$ is an
algebraic extension of $k$. One can find $E$ by computing the hyperexponential
solutions of some symmetric power system of (1). Pulling
$\varphi({\mathcal{G}}_{F}^{\circ})$ back to ${\mathcal{H}}_{F}^{\circ}$, one
gets ${\mathcal{G}}_{F}^{\circ}$.

  * $(S3)$

(The finite part). Find a finite Galois extension $k_{G}$ of $k$ and a
$k_{G}$-definable subset $Z$ of $V^{n}_{inv}$ such that
${\mathcal{G}}^{\circ}={\rm stab}(Z)$. Let $Z_{1}=Z,Z_{2},\cdots,Z_{m}$ be the
orbit of $Z$ under the action of ${\mbox{\rm Gal}}(k_{G}/k)$. Then
${\mathcal{G}}=\cup_{i=1}^{m}\\{\sigma\in{\rm GL}(V)|\sigma(Z)=Z_{i}\\}$.

We follow Hrushovski’s approach, but take out the logical language and
elaborate the details of the proofs that were only sketched in his paper. We
hope this will be helpful for the reader to understand Hrushovski’s approach.
Meanwhile, we simplify the first step of his approach. In spite of calculating
all $k$-definable elements, we only need compute one $k$-definable element to
obtain a proto-Galois group. Hrushovski showed in the part iii@ of [6] how to
compute the integer $\tilde{d}$ as claimed in (S1). As well as providing the
detailed explanations of his proofs, we present an explicit estimate of the
integer $\tilde{d}$.

The paper is organized as follows. In Appendix A, we describe a method to find
a bound for $k$-definable elements of $N_{d}(V^{n}_{inv})$. In Appendix B, an
explicit estimate of the integer $\tilde{d}$ that bounds the proto-Galois
groups is presented. These bounds will guarantee the termination of the
algorithm. In Sections 2 and 3, we show how to compute a proto-Galois group
and then the Galois group. Some computation details are omitted in these
sections and will be completed in Section 4.

Acknowledgements. Special thanks go to Michael F. Singer for his numerous
significant suggestions that improve the paper a lot. In preparing the paper,
the author was invited by Michael F. Singer to visit North Carolina State
University for two weeks. The author thanks him for the invitation and
financial support. Many thanks also go to Shaoshi Chen, Ziming Li and Daniel
Rettstadt for their valuable discussions.

##  2 proto-Galois groups

This section will be devoted to finding a proto-Galois group of (1). Let
$d\in{\mathbb{Z}}_{\geq 0}\cup\\{\infty\\}$ and $I\subseteq
k[x_{1,1},\cdots,x_{n,n}]$. $I_{\leq d}$ denotes the set of polynomials in $I$
with degree not greater than $d$. Set

$I_{F,d}=\left\\{P(X)\in k[x_{1,1},\cdots,x_{n,n}]_{\leq
d}\,\,\left|\,\,P(F)=0\right.\right\\}\,\,\mbox{and}\,\,Z_{F,d}={\rm
Zero}(I_{F,d})\bigcap V_{inv}^{n}$ (2)

When $d=\infty$, we use $I_{F}$ and $Z_{F}$ for short. $I_{F}$ consists of
algebraic relations among entries of the fundamental matrix $F$. The Galois
group of (1) is considered as the subgroup of ${\rm GL}(V)$ that preserves
$I_{F}$. Precisely,

${\mathcal{G}}=\\{\sigma\in{\rm GL}(V)\,\,|\,\,\sigma(Z_{F})=Z_{F}\\}.$

Hence once $I_{F}$ is computed, ${\mathcal{G}}$ will be determined. In
general, it is hard to calculate $I_{F}$. While given a nonnegative integer
$d$, the results in Appendix A enable us to compute $I_{F,d}$ (see Section
4.1). Moreover, we shall show that if $d$ is large enough, then ${\rm
stab}(Z_{F,d})$ will be a proto-Galois group of (1). Corollary B.15 in
Appendix B tells us how large the integer $d$ is enough. Let us start with two
lemmas.

###### Lemma 2.1

Assume that $U$ is a $C$-definable Zariski closed subset of ${\rm GL}_{n}(C)$
such that ${\mathcal{G}}\subseteq{\rm stab}(FU)$. Then $FU$ is a $k$-definable
Zariski closed subset of $V^{n}_{inv}$. Moreover if $U$ is bounded by $d$ then
so is $FU$.

  * Proof.

Assume that $U$ is bounded by $d$. Let

$J=\left\\{P(X)\in C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq
d}\,\,|\,\,\forall\,\,u\in U,P(u)=0\right\\}.$

Since $U$ is bounded by $d$, $U={\rm Zero}(J)\cap{\rm GL}_{n}(C)$. Let
$\tilde{I}$ be the ideal in $K[x_{1,1},x_{1,2},\cdots,x_{n,n}]$ generated by
$\\{P(F^{-1}X)|P(X)\in J\\}$. Set

$\tilde{I}_{\leq d}=\tilde{I}\cap K[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq d}.$

Then $\\{P(F^{-1}X)|P(X)\in J\\}\subseteq\tilde{I}_{\leq d}$ and $FU={\rm
Zero}(\tilde{I}_{\leq d})\cap V^{n}_{inv}$. Moreover, assume that $P(X)$ is a
polynomial in $K[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq d}$ satisfying that
$P(Fu)=0$ for any $u\in U$. Then one can easily see that $P(FX)$ is a
$K$-linear combination of finitely many elements in $J$. Therefore
$P(X)\in\tilde{I}_{\leq d}$. Now let

$I_{\leq d}=\tilde{I}_{\leq d}\cap k[x_{1,1},x_{1,2},\cdots,x_{n,n}].$

We will show that $I_{\leq d}$ generates $\tilde{I}$. For this, it suffices to
prove that $I_{\leq d}$ generates $\tilde{I}_{\leq d}$, since $\tilde{I}_{\leq
d}$ generates $\tilde{I}$. We will use the similar argument as in (p.23, [16])
to prove this. Use $\langle I_{\leq d}\rangle$ to denote the ideal of
$K[x_{1,1},x_{1,2},\cdots,x_{n,n}]$ generated by $I_{\leq d}$. Assume that
$\tilde{I}_{\leq d}$ is not a subset of $\langle I_{\leq d}\rangle$. Pick
$Q(X)\in\tilde{I}_{\leq d}\setminus\langle I_{\leq d}\rangle$ such that ${\rm
num}(Q(X))$, the number of the monomials of $Q(X)$, is minimal. If ${\rm
num}(f)=1$, it is clear that $Q(X)\in\langle I_{\leq d}\rangle$. Hence ${\rm
num}(Q(X))>1$. Without loss of generality, we may assume that one of the
coefficients of $Q(X)$ equals one and one of them, say $c$, is not in $k$. Let
$\sigma\in{\mathcal{G}}$. We use $Q_{\sigma}(X)$ to denote the image of $Q(X)$
by applying $\sigma$ to the coefficients of $Q(X)$. For every $u\in U$, since
$Q(\sigma^{-1}(Fu))=0$,

$\sigma(Q(\sigma^{-1}(Fu))=Q_{\sigma}(\sigma(\sigma^{-1}(Fu)))=Q_{\sigma}(Fu)=0.$

It implies that $Q_{\sigma}(X)\in\tilde{I}_{\leq d}$ for all
$\sigma\in{\mathcal{G}}$. Then the minimality of ${\rm num}(Q(X))$ implies
that both $Q(X)-Q_{\sigma}(X)$ and $c^{-1}Q(X)-\sigma(c)^{-1}Q_{\sigma}(X)$
are in $\langle I_{\leq d}\rangle$. Therefore

$\forall\,\,\sigma\in{\mathcal{G}},\,\,(\sigma(c)^{-1}-c^{-1})Q(X)\in\langle
I_{\leq d}\rangle.$

Since $c\notin k$, there is $\sigma\in{\mathcal{G}}$ such that $\sigma(c)\neq
c$. So $Q(X)\in\langle I_{\leq d}\rangle$, a contradiction. Hence $I_{\leq d}$
generates $\tilde{I}_{\leq d}$. $\Box$

The correctness of the statement below is almost obvious. However, since it
will be used frequently, we state it as a lemma.

###### Lemma 2.2

Let $H$ be a subgroup of ${\rm GL}_{n}(C)$ and ${\mathcal{N}}={\rm stab}(FH)$.
Then ${\mathcal{N}}_{F}=H$.

  * Proof.

One can easily see that ${\mathcal{N}}_{F}\subseteq H$. Assume that $h\in H$.
Then there is an element $\sigma_{h}$ in ${\rm GL}(V)$ satisfying that
$\sigma_{h}(F)=Fh$. Now for any $h^{\prime}\in H$,

$\sigma_{h}(Fh^{\prime})=Fhh^{\prime}\in
FH\,\,\mbox{and}\,\,\sigma_{h}(Fh^{-1}h^{\prime})=Fh^{\prime}.$

They imply that $\sigma_{h}\in{\mathcal{N}}$ and then $h\in{\mathcal{N}}_{F}$.
This concludes the lemma. $\Box$

###### Proposition 2.3

Let $\tilde{d}$ be as in Corollary B.15 of Appendix B and ${\mathcal{H}}={\rm
stab}(Z_{F,\tilde{d}})$. Then ${\mathcal{H}}$ is a proto-Galois group of (1)
and moreover, $Z_{F,\tilde{d}}=F{\mathcal{H}}_{F}$.

  * Proof.

We first show that $Z_{F,\tilde{d}}=F{\mathcal{H}}_{F}$. Assume that
$Z_{F,\tilde{d}}=FH$. If $H$ is a group, then one has that
${\mathcal{H}}_{F}=H$ by Lemma 2.2. That is to say,
$Z_{F,\tilde{d}}=FH=F{\mathcal{H}}_{F}$. Hence it suffices to show that $H$ is
a group. As $F\in Z_{F,\tilde{d}}$, we have that $I_{n}\in H$. Suppose that
$h_{1},h_{2}\in H$. For any $P(X)\in I_{F,\tilde{d}}$, the equality
$P(Fh_{2})=0$ implies that $P(Xh_{2})$ is an element of $I_{F,\tilde{d}}$.
Hence $P(Fh_{1}h_{2})=0$ and then $h_{1}h_{2}\in H$. It remains to prove that
for any $h\in H$, $h^{-1}\in H$. As $H$ is closed under the multiplication,
$Hh\subseteq H$. Multiplying both sides of $Hh\subseteq H$ by $h$ repeatedly,
we have that

$\cdots\subseteq Hh^{3}\subseteq Hh^{2}\subseteq Hh\subseteq H.$

It is easy to verify that $H$ is a Zariski closed subset of ${\rm GL}_{n}(C)$
and so is $Hh^{i}$ for all positive integer $i$. The stability of the above
sequence indicates that $Hh^{i_{0}+1}=Hh^{i_{0}}$ for some $i_{0}\geq 0$ and
therefore $Hh=H$. So $h^{-1}\in H$.

Now we prove that ${\mathcal{H}}$ is a proto-Galois group of (1). First of
all, as $Z_{F,\tilde{d}}$ is $k$-definable, ${\mathcal{G}}\subseteq{\rm
stab}(Z_{F,\tilde{d}})={\mathcal{H}}$. By Corollary B.15, there is a proto-
Galois group $\tilde{H}$ of (1) bounded by $\tilde{d}$. Since
${\mathcal{G}}_{F}\subseteq\tilde{H}$, ${\mathcal{G}}\subseteq{\rm
stab}(F\tilde{H})$ and then by Lemma 2.1, $F\tilde{H}$ is a $k$-definable
element of $N_{\tilde{d}}(V_{inv}^{n})$. Then there are polynomials
$Q_{1}(X),\cdots,Q_{s}(X)$ in
$k[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq\tilde{d}}$ such that $F\tilde{H}={\rm
Zero}(Q_{1}(X),\cdots,Q_{s}(X))\cap V_{inv}^{n}$. It follows from $Q_{i}(F)=0$
that $Q_{i}\in I_{F,\tilde{d}}$ for all $i$ with $1\leq i\leq s$. Hence
$F{\mathcal{H}}_{F}=Z_{F,\tilde{d}}\subseteq F\tilde{H}$. This implies that
${\mathcal{H}}_{F}\subseteq\tilde{H}$. Note that
$({\mathcal{H}}_{F}^{\circ})^{t}$ is generated by all unipotent elements of
${\mathcal{H}}_{F}^{\circ}$ that are in $\tilde{H}^{\circ}$. Hence

$({\mathcal{H}}_{F}^{\circ})^{t}\subseteq(\tilde{H}^{\circ})^{t}\subseteq{\mathcal{G}}_{F}^{\circ}\subseteq{\mathcal{H}}_{F}^{\circ}.$

Then the conclusion follows from the fact that
$({\mathcal{H}}_{F}^{\circ})^{t}$ is a normal subgroup of
${\mathcal{H}}_{F}^{\circ}$. $\Box$

##  3 Recovering Galois groups

Throughout this section, $I_{F,\tilde{d}},Z_{F,\tilde{d}}$ and ${\mathcal{H}}$
are as in Proposition 2.3. We will first compute a Zariski closed subset of
$Z_{F,\tilde{d}}$ whose stabilizer is ${\mathcal{G}}^{\circ}$. Then using the
Galois group of finite extension, we construct $I_{\tilde{F}}$ and then the
Galois group ${\mathcal{G}}$, where $I_{\tilde{F}}$ is defined in (2) with
some fundamental matrix $\tilde{F}$ and $d=\infty$. Note that
${\mathcal{G}}^{\circ}$ is defined as the pre-image of
${\mathcal{G}}_{F}^{\circ}$ under the map $\phi_{F}$ in Section 1. It is well-
known that ${\mathcal{G}}^{\circ}$ is equal to ${\mbox{\rm
Gal}}(\bar{k}K/\bar{k})$ where $\bar{k}K$ is the Picard-Vessiot extension
field of $\bar{k}$ for (1).

###  3.1 Identity component ${\mathcal{G}}^{\circ}$

Decomposing ${\mathcal{H}}_{F}$ into irreducible components, we obtain its
identity component ${\mathcal{H}}_{F}^{\circ}$. The defining equations of
${\mathcal{H}}_{F}^{\circ}$ will lead to a Zariski closed subset
$Z_{{\mathcal{H}}^{\circ}}$ of $Z_{F,\tilde{d}}$ such that the stabilizer of
$Z_{{\mathcal{H}}^{\circ}}$ is ${\mathcal{H}}^{\circ}$. Let
$\chi_{1},\cdots,\chi_{l}$ be generators of $X({\mathcal{H}}_{F}^{\circ})$,
where $X({\mathcal{H}}_{F}^{\circ})$ is the group of characters of
${\mathcal{H}}_{F}^{\circ}$. We will show that each character corresponds to a
hyperexponential element over $\bar{k}$. Assuming we can find
$\chi_{1},\cdots,\chi_{l}$ (and we will show how this can be done), the
results in [2] allow us to find algebraic relations among hyperexponential
elements associated with $\chi_{1},\cdots,\chi_{l}$. These relations together
with $Z_{{\mathcal{H}}^{\circ}}$ produce a Zariski closed subset $Z$ of
$Z_{{\mathcal{H}}^{\circ}}$ such that the identity component of ${\rm
stab}(Z)$ is ${\mathcal{G}}^{\circ}$. Using the similar argument as
constructing $Z_{{\mathcal{H}}^{\circ}}$, we are able to find a Zariski closed
subset whose stabilizer is ${{\mathcal{G}}^{\circ}}$.

Let $\bar{k}K$ be the Picard-Vessiot extension field of $\bar{k}$ for (1) and
$H$ a subgroup of ${\rm GL}_{n}(C)$. For brevity, we will use $H(\bar{k}K)$ to
denote ${\rm Zero}(I(H))\cap{\rm GL}_{n}(\bar{k}K)$ where $I(H)$ is the
vanishing ideal of $H$ in $C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$. Let
${\mathcal{N}}$ be a subgroup of ${\rm GL}_{n}(V)$. Suppose that
$F{\mathcal{N}}_{F}$ is $\bar{k}$-definable and $\Phi$ is the vanishing ideal
of $F{\mathcal{N}}_{F}$ in $\bar{k}[x_{1,1},x_{1,2},\cdots,x_{n,n}]$. Let
$\gamma$ be an element in ${\rm Zero}(\Phi)\cap{\rm GL}_{n}(\bar{k})$. Then we
have the following porposition.

###### Proposition 3.1

  * $(a)$

For every $\bar{F}\in F{\mathcal{N}}_{F}$, there is
$g_{\bar{F}}\in{\mathcal{N}}_{F}$ such that

$\left(\gamma
g_{\bar{F}}\right)^{-1}\bar{F}\in{\mathcal{N}}_{F}^{\circ}(\bar{k}K);$

  * $(b)$

Let $g_{\bar{F}}$ be an element in ${\mathcal{N}}_{F}$ such that $(a)$ holds
for $\bar{F}$ and let $\alpha=\gamma g_{\bar{F}}$. Set

$Z_{\alpha}={\rm Zero}\left(\left\\{P(\alpha^{-1}X)\,\,|\,\,P(X)\in
I({\mathcal{N}}_{F}^{\circ})\right\\}\right)\bigcap V_{inv}^{n}.$

Then ${\rm stab}(Z_{\alpha})={\mathcal{N}}^{\circ}$ and
$Z_{\alpha}=\bar{F}{\mathcal{N}}_{F}^{\circ}$, which is a Zariski closed
subset of $F{\mathcal{N}}_{F}$.

  * Proof.

$(a)$. One can easily verify that ${\rm Zero}(\Phi)\cap{\rm
GL}_{n}(\bar{k}K)=F{\mathcal{N}}_{F}(\bar{k}K)$. Then we have that
$\bar{F}{\mathcal{N}}_{F}(\bar{k}K)=F{\mathcal{N}}_{F}(\bar{k}K)$ because
$\bar{F}\in F{\mathcal{N}}_{F}$. Therefore $\gamma$ is an element of
$\bar{F}{\mathcal{N}}_{F}(\bar{k}K)$. Equivalently, $\gamma^{-1}\bar{F}$ is in
${\mathcal{N}}_{F}(\bar{k}K)$. Since ${\mathcal{N}}_{F}$ is $C$-definable,
there is $g_{\bar{F}}\in{\mathcal{N}}_{F}$ such that

$g_{\bar{F}}^{-1}\gamma^{-1}\bar{F}=\left(\gamma
g_{\bar{F}}\right)^{-1}\bar{F}\in{\mathcal{N}}_{F}^{\circ}(\bar{k}K).$

$(b)$. Note that $V_{inv}^{n}=\\{\bar{F}h\,\,|\,\,h\in{\rm GL}_{n}(C)\\}$.
From the definition of $Z_{\alpha}$, for any $\bar{F}h\in Z_{\alpha}$, we have
that $\alpha^{-1}\bar{F}h$ belongs to ${\mathcal{N}}_{F}^{\circ}(\bar{k}K)$.
It means that $h\in{\mathcal{N}}_{F}^{\circ}$, because
$\alpha^{-1}\bar{F}\in{\mathcal{N}}_{F}^{\circ}(\bar{k}K)$ and $h\in{\rm
GL}_{n}(C)$. Therefore $Z_{\alpha}\subseteq\bar{F}{\mathcal{N}}_{F}^{\circ}$.
It is obvious that $\bar{F}{\mathcal{N}}_{F}^{\circ}$ is a subset of
$Z_{\alpha}$. Hence

$Z_{\alpha}=\bar{F}{\mathcal{N}}_{F}^{\circ}\subseteq\bar{F}{\mathcal{N}}_{F}=F{\mathcal{N}}_{F}$

that is a Zariski closed subset of $F{\mathcal{N}}_{F}$.

Finally, we show that ${\rm stab}(Z_{\alpha})={\mathcal{N}}^{\circ}$. Denote
${\rm stab}(Z_{\alpha})$ by ${\mathcal{W}}$. As
$Z_{\alpha}=\bar{F}{\mathcal{N}}_{F}^{\circ}$, Lemma 2.2 implies that
${\mathcal{W}}_{\bar{F}}={\mathcal{N}}_{F}^{\circ}$. From the assumption,
$\bar{F}=F\bar{h}$ for some $\bar{h}\in{\mathcal{N}}_{F}$. Hence
${\mathcal{W}}_{F}=\bar{h}{\mathcal{W}}_{\bar{F}}\bar{h}^{-1}=\bar{h}{\mathcal{N}}_{F}^{\circ}\bar{h}^{-1}$.
Owing to the normality of ${\mathcal{N}}_{F}^{\circ}$ in ${\mathcal{N}}_{F}$,
we have that ${\mathcal{W}}_{F}={\mathcal{N}}_{F}^{\circ}$. Therefore
${\mathcal{W}}={\mathcal{N}}^{\circ}$. $\Box$

###### Remark 3.2

Propositions 2.3 and 3.1 enable us to compute a Zariski closed subset
$Z_{{\mathcal{H}}^{\circ}}$ of $Z_{F,\tilde{d}}$ such that ${\rm
stab}(Z_{{\mathcal{H}}^{\circ}})={\mathcal{H}}^{\circ}$. It suffices to
compute an element $\alpha$ in ${\rm Zero}(I_{F,\tilde{d}})\cap{\rm
GL}_{n}(\bar{k})$ and $\bar{F}\in F{\mathcal{H}}_{F}$ satisfying that
$\alpha^{-1}\bar{F}\in{\mathcal{H}}_{F}^{\circ}(\bar{k}K)$.

Let $\alpha$ be an element of ${\rm Zero}(I_{F,\tilde{d}})\cap{\rm
GL}_{n}(\bar{k})$ and $\bar{F}$ in $F{\mathcal{H}}_{F}$ satisfying that
$\alpha^{-1}\bar{F}\in{\mathcal{H}}_{F}^{\circ}(\bar{k}K)$. From the above
proposition, we know that such $\alpha$ and $\bar{F}$ exist.

###### Proposition 3.3

Let $\chi:{\mathcal{H}}_{F}^{\circ}\rightarrow C^{*}$ be a character of
${\mathcal{H}}_{F}^{\circ}$, which is represented by a polynomial in
$C[x_{1,1},x_{1,2},\cdots,x_{n,n},1/\det(X)]$. Then $\chi(\alpha^{-1}\bar{F})$
is a hyperexponential element over $\bar{k}$. Moreover for any
$h\in{\mathcal{H}}_{F}^{\circ}$,

$\chi(\alpha^{-1}\bar{F}h)=\chi(\alpha^{-1}\bar{F})\chi(h).$

  * Proof.

Since $\chi$ is a character of ${\mathcal{H}}_{F}^{\circ}$, for any
$h_{1},h_{2}\in{\mathcal{H}}_{F}^{\circ}(\bar{k}K)$,
$\chi(h_{1}h_{2})=\chi(h_{1})\chi(h_{2})$. Note that
$\alpha^{-1}\bar{F}\in{\mathcal{H}}_{F}^{\circ}(\bar{k}K)$. For any
$h\in{\mathcal{H}}_{F}^{\circ}$,

$\chi(\alpha^{-1}\bar{F}h)=\chi(\alpha^{-1}\bar{F})\chi(h)=\chi(\alpha^{-1}\bar{F})\chi(h).$

Suppose that $\sigma\in{\mathcal{G}}^{\circ}$. Then
$\sigma(\alpha^{-1}\bar{F})=\alpha^{-1}\bar{F}[\sigma]$ for some
$[\sigma]\in{\rm GL}_{n}(C)$. As $\alpha^{-1}\bar{F}$ belongs to
${\mathcal{H}}_{F}^{\circ}(\bar{k}K)$ that is $C$-definable, we have that
$\sigma(\alpha^{-1}\bar{F})\in{\mathcal{H}}_{F}^{\circ}(\bar{k}K)$. It follows
that $[\sigma]\in{\mathcal{H}}_{F}^{\circ}$. Hence for any
$\sigma\in{\mathcal{G}}^{\circ}$,

$\sigma\left(\frac{\chi(\alpha^{-1}\bar{F})^{\prime}}{\chi(\alpha^{-1}\bar{F})}\right)=\frac{\chi(\alpha^{-1}\bar{F}[\sigma])^{\prime}}{\chi(\alpha^{-1}\bar{F}[\sigma])}=\frac{\chi(\alpha^{-1}\bar{F})^{\prime}\chi([\sigma])}{\chi(\alpha^{-1}\bar{F})\chi([\sigma])}=\frac{\chi(\alpha^{-1}\bar{F})^{\prime}}{\chi(\alpha^{-1}\bar{F})}.$

Thus
$\frac{\chi(\alpha^{-1}\bar{F})^{\prime}}{\chi(\alpha^{-1}\bar{F})}\in\bar{k}$.
$\Box$

Suppose that $\chi_{1},\cdots,\chi_{l}$ are the generators of
$X({\mathcal{H}}_{F}^{\circ})$, all of which are nontrivial and represented by
polynomials in $C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$. Then each character
$\chi_{i}$ corresponds to a hyperexponential element
$\chi_{i}(\alpha^{-1}\bar{F})$, denoted by $h_{i}$. Let
$v_{i}=h_{i}^{\prime}/h_{i}$ for all $i$ with $1\leq i\leq l$, and
$E=\bar{k}(h_{1},\cdots,h_{l})$ that is the Picard-Vessiot extension of
$\bar{k}$ for the equations

$\delta(Y)=\hbox{\rm diag}(v_{1},\cdots,v_{l})Y.$

Note that $E$ is a subfield of $\bar{k}K$. Let
${\mathbf{h}}=(h_{1},\cdots,h_{l})$. Then ${\mathbf{h}}$ is a fundamental
matrix of the above equations and ${\mbox{\rm Gal}}(E/\bar{k})$ can naturally
be embedded into $(C^{*})^{l}$. Denote the image of ${\mbox{\rm
Gal}}(E/\bar{k})$ by $T$ under this embedding. That is to say,

$T=\left\\{\left.(c_{1},\cdots,c_{l})^{T}\in(C^{*})^{l}\,\,\right|\,\,\exists\,\,\sigma\in{\mbox{\rm
Gal}}(E/\bar{k})\,\,s.t.\,\,\sigma(h_{i})=c_{i}h_{i},i=1,\cdots,l\right\\}.$

In [2], the authors show that when $C$ is an algebraically closed computable
field, given $v_{1},\cdots,v_{l}$, one can compute a set of elements
$S=\\{h_{\eta_{1}},\cdots,h_{\eta_{r}}\\}\subseteq\\{h_{1},\cdots,h_{l}\\}$
such that

  * $(i)$

$h_{\eta_{1}},\cdots,h_{\eta_{r}}$ are algebraically independent over $C$;

  * $(ii)$

for each $j\in\\{1,\cdots,l\\}$, there are an element $f_{j}\in\bar{k}$ and
integers $m_{j},m_{i,j},m_{j}\neq 0$ satisfying

$h_{j}^{m_{j}}=f_{j}\prod_{i=1}^{r}h_{\eta_{i}}^{m_{i,j}}$

if $S$ is nonempty, or $h_{j}^{m_{j}}=f_{j}$ if $S$ is empty.

The equalities in $(ii)$ generate almost all algebraic relations among
$h_{1},\cdots,h_{l}$. Due to the proof of Proposition 2.5 in [2], the set
$\\{y_{j}^{m_{j}}-\prod_{i=1}^{r}y_{\eta_{i}}^{m_{i,j}},j=1,2,\cdots,l\\}$
defines an algebraic subgroup of $(C^{*})^{l}$, whose identity component is
equal to $T$. Let $\varphi=(\chi_{1},\cdots,\chi_{l})$. Then $\varphi$ is a
surjective morphism from ${\mathcal{H}}_{F}^{\circ}$ to $(C^{*})^{l}$, for all
$\chi_{i}$ are nontrivial. As $\bar{F}\in F{\mathcal{H}}_{F}$, it follows from
the normality of ${\mathcal{H}}_{F}^{\circ}$ in ${\mathcal{H}}_{F}$ that
${\mathcal{H}}_{\bar{F}}^{\circ}={\mathcal{H}}_{F}^{\circ}$. Thus
${\mathcal{G}}_{\bar{F}}^{\circ}\subseteq{\mathcal{H}}_{\bar{F}}^{\circ}={\mathcal{H}}_{F}^{\circ}$.
Moreover, we have

###### Lemma 3.4

$\varphi({\mathcal{G}}_{\bar{F}}^{\circ})=T.$

  * Proof.

Note that ${\mathcal{G}}^{\circ}={\mbox{\rm Gal}}(\bar{k}K/\bar{k})$ and
$E\subseteq\bar{k}K$ that is a Picard-Vessiot extension field. By the Galois
theory, the map $\psi:{\mathcal{G}}^{\circ}\rightarrow{\mbox{\rm
Gal}}(E/\bar{k})$ given by $\psi(\sigma)=\sigma|_{E}$ for any
$\sigma\in{\mathcal{G}}^{\circ}$ is surjective. For any
$[\sigma]\in{\mathcal{G}}_{\bar{F}}^{\circ}$, there is
$\sigma\in{\mathcal{G}}^{\circ}$ such that $\sigma(\bar{F})=\bar{F}[\sigma]$
and then

$\displaystyle\psi(\sigma)({\mathbf{h}})$
$\displaystyle=\sigma({\mathbf{h}})=(\sigma(h_{1}),\cdots,\sigma(h_{l}))=(\chi_{1}(\alpha^{-1}\bar{F}[\sigma]),\cdots,\chi_{l}(\alpha^{-1}\bar{F}[\sigma]))$
$\displaystyle=(\chi_{1}(\alpha^{-1}\bar{F})\chi_{1}([\sigma]),\cdots,\chi_{l}(\alpha^{-1}\bar{F})\chi_{l}([\sigma]))=(\chi_{1}([\sigma])h_{1},\cdots,\chi_{l}([\sigma])h_{l}).$

By the definition of $T$, we have that
$\varphi([\sigma])=(\chi_{1}([\sigma]),\cdots,\chi_{l}([\sigma]))\in T$. Now
assume that $(c_{1},\cdots,c_{l})^{T}\in T$. Then there is
$\sigma\in{\mbox{\rm Gal}}(E/\bar{k})$ such that $\sigma(h_{j})=c_{j}h_{j}$
for all $j$ with $1\leq j\leq l$. Due to the surjectivity of $\psi$, there is
$\hat{\sigma}\in{\mathcal{G}}^{\circ}$ such that $\psi(\hat{\sigma})=\sigma$.
Assume that $\hat{\sigma}(\bar{F})=\bar{F}[\hat{\sigma}]$ for some
$[\hat{\sigma}]\in{\mathcal{G}}_{\bar{F}}^{\circ}$. It follows that

$c_{j}=\frac{\sigma(h_{j})}{h_{j}}=\frac{\hat{\sigma}(h_{j})}{h_{j}}=\frac{\chi_{j}(\alpha^{-1}\bar{F}[\hat{\sigma}])}{\chi_{j}(\alpha^{-1}\bar{F})}=\frac{\chi_{j}(\alpha^{-1}\bar{F})\chi_{j}([\hat{\sigma}])}{\chi_{j}(\alpha^{-1}\bar{F})}=\chi_{j}([\hat{\sigma}]),\,\,j=1,\cdots,l.$

In other words, $(c_{1},\cdots,c_{l})^{T}$ is the image of $[\hat{\sigma}]$
under the morphism $\varphi$. So $\varphi({\mathcal{G}}_{\bar{F}}^{\circ})=T$.
$\Box$

Set

$J=\\{P(\alpha^{-1}X)\,\,|\,\,P(X)\in
I({\mathcal{H}}_{F}^{\circ})\\}\bigcup\left\\{\chi_{j}(\alpha^{-1}X)^{m_{j}}-f_{j}\prod_{i=1}^{r}\chi_{\eta_{i}}(\alpha^{-1}X)^{m_{i,j}},j=1,\cdots,l\right\\}.$

Let $Z_{J}={\mbox{\rm Zero}}(J)\cap V^{n}_{inv}$ and $\bar{{\mathcal{H}}}={\rm
stab}(Z_{J})$.

###### Proposition 3.5

$\bar{{\mathcal{H}}}^{\circ}={\mathcal{G}}^{\circ}$.

  * Proof.

Assume that $Z_{J}=\bar{F}\bar{H}$ where $\bar{H}\subseteq{\rm GL}_{n}(C)$.
Recall that $\alpha^{-1}\bar{F}\in{\mathcal{H}}_{F}^{\circ}(\bar{k}K)$. It is
easy to verify that

$\bar{H}={\mathcal{H}}_{F}^{\circ}\bigcap{\mbox{\rm
Zero}}\left(\left\\{\chi_{j}^{m_{j}}-\prod_{i=1}^{r}\chi_{\eta_{i}}^{m_{i,j}},\,\,j=1,2,\cdots,l\right\\}\right).$

Therefore $\bar{H}$ is a group and then by Lemma 2.2,
$\bar{{\mathcal{H}}}_{\bar{F}}=\bar{H}$. To prove
$\bar{{\mathcal{H}}}^{\circ}={\mathcal{G}}^{\circ}$, it suffices to show that
$\bar{H}^{\circ}={\mathcal{G}}_{\bar{F}}^{\circ}$. Since
$\varphi=(\chi_{1},\cdots,\chi_{l})$ is surjective,

$\varphi(\bar{H})=(C^{*})^{l}\bigcap{\mbox{\rm
Zero}}\left(\left\\{y_{j}^{m_{j}}-\prod_{i=1}^{r}y_{\eta_{i}}^{m_{i,j}},j=1,2,\cdots,l\right\\}\right).$

The discussion before Lemma 3.4 indicates that the identity component of
$\varphi(\bar{H})$ is equal to $T$. Note that
$\ker(\varphi)=({\mathcal{H}}^{\circ}_{F})^{t}=({\mathcal{H}}_{\bar{F}}^{\circ})^{t}$.
Then we have $\ker(\varphi)\subseteq{\mathcal{G}}_{\bar{F}}^{\circ}$, since
${\mathcal{H}}$ is a proto-Galois group. As $Z_{J}$ is $\bar{k}$-definable,
${\mathcal{G}}^{\circ}\subseteq\bar{{\mathcal{H}}}$ and then
${\mathcal{G}}_{\bar{F}}^{\circ}\subseteq\bar{{\mathcal{H}}}_{\bar{F}}=\bar{H}$.
Now we have

$[\bar{H}:{\mathcal{G}}_{\bar{F}}^{\circ}]=\left[\bar{H}/\ker(\varphi):{\mathcal{G}}_{\bar{F}}^{\circ}/\ker(\varphi)\right]=[\varphi(\bar{H}):\varphi({\mathcal{G}}_{\bar{F}}^{\circ})].$

Owing to Lemma 3.4, $\varphi({\mathcal{G}}_{\bar{F}}^{\circ})$ is equal to $T$
that is the identity component of $\varphi(\bar{H})$. Hence
$[\bar{H}:{\mathcal{G}}_{\bar{F}}^{\circ}]$ is finite. Thus
$\bar{H}^{\circ}={\mathcal{G}}_{\bar{F}}^{\circ}$, which completes the proof.
$\Box$

Due to Proposition 3.1, there are

$\beta\in{\rm Zero}(J)\cap{\rm
GL}_{n}(\bar{k})\,\,\mbox{and}\,\,\tilde{F}\in\bar{F}\bar{{\mathcal{H}}}_{\bar{F}}$
(3)

such that $\beta^{-1}\tilde{F}\in{\mathcal{G}}_{\bar{F}}^{\circ}(\bar{k}K)$.
Let

$Z_{\beta}={\rm Zero}\left(\left\\{P(\beta^{-1}X)\,\,|\,\,P(X)\in
I({\mathcal{G}}_{\bar{F}}^{\circ})\right\\}\right)\cap V_{inv}^{n}.$

By Proposition 3.1 again, we have that
$Z_{\beta}=\tilde{F}{\mathcal{G}}_{\bar{F}}^{\circ}$ that is a Zariski closed
subset of $\bar{F}\bar{{\mathcal{H}}}_{\bar{F}}$ and ${\rm
stab}(Z_{\beta})={\mathcal{G}}^{\circ}$. Furthermore, by Lemma 2.2,
${\mathcal{G}}_{\tilde{F}}^{\circ}={\mathcal{G}}_{\bar{F}}^{\circ}$.

###  3.2 Galois group ${\mathcal{G}}$

Let $\beta$ and $\tilde{F}$ be as in (3). Let $k_{G}$ be the Galois closure of
$k(\beta^{-1})$, where $k(\beta^{-1})$ denotes the extension field of $k$ by
joining the entries of $\beta^{-1}$. For any $\tau\in{\mbox{\rm
Gal}}(k_{G}/k)$, set

$J_{\tau(\beta)}=\left\langle\left\\{P(\tau(\beta)^{-1}X)\,\,|\,\,P(X)\in
I({\mathcal{G}}_{\tilde{F}}^{\circ})\right\\}\right\rangle$

where $\langle*\rangle$ denotes the ideal in
$k_{G}[x_{1,1},x_{1,2},\cdots,x_{n,n}]$ generated by $*$.

###### Proposition 3.6

Let $I_{\tilde{F}}$ be defined in (2) with $F=\tilde{F}$ and $d=\infty$ . Then

$I_{\tilde{F}}=\left(\bigcap_{\tau\in{\mbox{\rm
Gal}}(k_{G}/k)}J_{\tau(\beta)}\right)\bigcap
k[x_{1,1},x_{1,2},\cdots,x_{n,n}].$

  * Proof.

Denote the ideal in the righthand side of the above equality by $\Phi$.
Suppose that $P(X)\in\Phi$. Then $P(X)\in J_{\beta}$. From the previous
subsection, $\tilde{F}\in Z_{\beta}$. So $P(\tilde{F})=0$. That is to say,
$P(X)\in I_{\tilde{F}}$. Thus $\Phi\subseteq I_{\tilde{F}}$. Conversely,
suppose that $P(X)\in I_{\tilde{F}}$. Then $P(\tilde{F})=0$. Applying
${\mathcal{G}}^{\circ}$ to it, we obtain that $P(\tilde{F}g)=0$ for every
$g\in{\mathcal{G}}_{\tilde{F}}^{\circ}$ and furthermore the polynomial
$P(\tilde{F}X)$ vanishes on ${\mathcal{G}}_{\tilde{F}}^{\circ}(\bar{k}K)$.
Since $\beta^{-1}\tilde{F}\in{\mathcal{G}}_{\tilde{F}}^{\circ}(\bar{k}K)$,
$\tilde{F}{\mathcal{G}}_{\tilde{F}}^{\circ}(\bar{k}K)=\beta{\mathcal{G}}_{\tilde{F}}^{\circ}(\bar{k}K)$.
It implies that $P(\beta X)$ vanishes on
${\mathcal{G}}_{\tilde{F}}^{\circ}(\bar{k}K)$. Consequently, $P(\beta X)$
belongs to $\langle I({\mathcal{G}}_{\tilde{F}}^{\circ})\rangle$ and then
$P(X)\in J_{\beta}$. Because all coefficients of $P(X)$ are in $k$, $P(X)\in
J_{\tau(\beta)}$ for all $\tau\in{\mbox{\rm Gal}}(k_{G}/k)$. Hence
$P(X)\in\Phi$. $\Box$

If $I_{\tilde{F}}$ is computed, then it is easy to verify that

${\mathcal{G}}_{\tilde{F}}=\\{g\in{\rm GL}_{n}(C)\,\,|\,\,\forall\,\,P(X)\in
I_{\tilde{F}},\,\,P(Xg)\in I_{\tilde{F}}\\}.$

In the following, we present another method to compute
${\mathcal{G}}_{\tilde{F}}$ that avoids computing $I_{\tilde{F}}$. From
Proposition 3.20 and Theorem 3.11 of [8], there is a Picard-Vessiot extension
field, say $\tilde{K}$, of $k$ that contains $k_{G}$ and $K$ as subfields.
Then Galois theory implies that if $\tau$ is an element of ${\mbox{\rm
Gal}}(k_{G}/k)$ (or ${\mathcal{G}}$), then there is $\rho\in{\mbox{\rm
Gal}}(\tilde{K}/k)$ such that the restriction of $\rho$ on $k_{G}$ (or $K$) is
equal to $\tau$. Let $\\{Q_{1}(X),\cdots,Q_{\nu}(X)\\}$ be a set of generators
of $I({\mathcal{G}}_{\bar{F}}^{\circ})$. Set

$\tilde{G}=\bigcup_{\tau\in{\mbox{\rm Gal}}(k_{G}/k)}\left\\{\,\,g\in{\rm
GL}_{n}(C)\left|\,\,Q_{i}(\tau(\beta)^{-1}\tilde{F}g)=0,\,\,\mbox{for all
$i=1,\cdots,\nu$}\right.\right\\}.$

Then we have

###### Proposition 3.7

${\mathcal{G}}_{\tilde{F}}=\tilde{G}$.

  * Proof.

We first prove that ${\mathcal{G}}_{\tilde{F}}\subseteq\tilde{G}$. Assume that
$[\sigma]\in{\mathcal{G}}_{\tilde{F}}$. Then there is $\sigma\in{\mathcal{G}}$
such that $\sigma({\tilde{F}})={\tilde{F}}[\sigma]$ and furthermore there is
$\rho\in{\mbox{\rm Gal}}(\tilde{K}/k)$ such that $\rho|_{K}=\sigma$. Let
$\tau=\rho|_{k_{G}}$. Note that $\tau\in{\mbox{\rm Gal}}(k_{G}/k)$. Then for
all $i$ with $1\leq i\leq\nu$,

$\rho(Q_{i}(\beta^{-1}{\tilde{F}}))=Q_{i}(\tau(\beta)^{-1}\sigma({\tilde{F}}))=Q_{i}({\tau(\beta)^{-1}\tilde{F}}[\sigma])=0.$

This implies that $[\sigma]\in\tilde{G}$. Conversely, assume that
$g\in\tilde{G}$. Then there is $\tau\in{\mbox{\rm Gal}}(k_{G}/k)$ such that
$Q_{i}(\tau(\beta)^{-1}{\tilde{F}}g)=0$ for all $i$ with $1\leq i\leq\nu$.
There is $\rho\in{\mbox{\rm Gal}}(\tilde{K}/k)$ such that
$\rho|_{k_{G}}=\tau^{-1}$. Since $\rho|_{K}\in{\mathcal{G}}$, there is
$h\in{\mathcal{G}}_{\tilde{F}}$ such that
$\rho|_{K}({\tilde{F}})={\tilde{F}}h$. Now we have that

$\forall\,\,i=1,\cdots,\nu,\,\,\rho(Q_{i}(\tau(\beta)^{-1}{\tilde{F}}g))=Q_{i}(\beta^{-1}{\tilde{F}}hg)=0.$

Hence
$\beta^{-1}{\tilde{F}}hg\in{\mathcal{G}}_{\tilde{F}}^{\circ}(\tilde{K})$,
which implies that $hg\in{\mathcal{G}}_{\tilde{F}}^{\circ}$ and thus
$g\in{\mathcal{G}}_{\tilde{F}}$. $\Box$

##  4 Simplified Hrushovski’s Algorithm

Now we are ready to present the algorithm. Instead of ${\mathcal{G}}$, we
shall compute ${\mathcal{G}}_{\tilde{F}}$ for some fundamental matrix
$\tilde{F}$. Throughout this section, $C$ will denote the algebraic closure of
a computable field of characteristic zero.

###### Algorithm 4.1

Input: A linear differential equation (1) with coefficients in $C(t)$.
Output: the Galois group ${\mathcal{G}}_{\tilde{F}}$.

  * $(a)$

By Corollary B.15, determine an integer $\tilde{d}$ such that there is a
proto-Galois group of (1) bounded by $\tilde{d}$.

  * $(b)$

Compute a fundamental matrix $F$ (the first finitely many terms of its formal
power series expansion at some point). Compute $I_{F,\tilde{d}}$ and then
${\mathcal{H}}_{F}$, where $I_{F,\tilde{d}}$ is defined in (2) and
${\mathcal{H}}$ is the stabilizer of ${\rm Zero}(I_{F,\tilde{d}})\cap
V_{inv}^{n}$.

  * $(c)$

Compute ${\mathcal{H}}_{F}^{\circ}$ and find a zero $\alpha$ of
$I_{F,\tilde{d}}$ in ${\rm GL}_{n}(\overline{C(t)})$ and $\bar{F}\in
F{\mathcal{H}}_{F}$ such that $\alpha^{-1}\bar{F}$ is an element of
${\mathcal{H}}_{F}^{\circ}(\bar{k}K)$.

  * $(d)$

Compute generators of $X({\mathcal{H}}_{F}^{\circ})$, say
$\chi_{1},\cdots,\chi_{l}$, which are represented by polynomials in
$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$. Denote $\chi_{i}(\alpha^{-1}\bar{F})$ by
$h_{i}$ for $i=1,2,\cdots,l$. By Proposition 3.1, $h_{i}$ is hyperexponential
over $\overline{C(t)}$. Compute these $h_{i}$.

  * $(e)$

Using the method in [2], compute algebraic relations for $h_{1},\cdots,h_{l}$,
say

$\left\\{h_{j}^{m_{j}}-f_{j}\prod_{i=1}^{r}h_{\eta_{i}}^{m_{i,j}},j=1,2,\cdots,l\right\\}$

where $f_{j}\in\overline{C(t)}$ and $h_{\eta_{1}},\cdots,h_{\eta_{r}}$ are
algebraically independent over $C(t)$.

  * $(f)$

Denote a set of generators of $I({\mathcal{H}}_{F}^{\circ})$ by
$\\{P_{1}(X),\cdots,P_{\mu}(X)\\}$ and set

$J=\\{P_{i}(\alpha^{-1}X),i=1,\cdots,\mu\\}\bigcup\left\\{\chi_{j}^{m_{j}}(\alpha^{-1}X)-f_{j}\prod_{i=1}^{r}\chi_{\eta_{i}}^{m_{i,j}}(\alpha^{-1}X),j=1,\cdots,l\right\\}.$

Compute $\bar{{\mathcal{H}}}={\rm stab}({\rm Zero}(J)\cap V_{inv}^{n})$ and
then $\bar{{\mathcal{H}}}^{\circ}$ that is equal to ${\mathcal{G}}^{\circ}$.

  * $(g)$

As in the step $(c)$, compute ${\mathcal{G}}_{\bar{F}}^{\circ}$ and find
$\beta$ in ${\rm Zero}(J)\cap{\rm GL}_{n}(\overline{C(t)})$ and
$\tilde{F}\in\bar{F}\bar{{\mathcal{H}}}_{\bar{F}}$ such that
$\beta^{-1}\tilde{F}\in{\mathcal{G}}_{\bar{F}}^{\circ}(\bar{k}K)$.

  * $(h)$

Denote a set of generators of $I({\mathcal{G}}_{\bar{F}}^{\circ})$ by
$\\{Q_{1}(X),\cdots,Q_{\nu}(X)\\}$. Let $k_{G}$ be the Galois closure of
$C(t)(\beta^{-1})$, where $C(t)(\beta^{-1})$ is the extension field of $C(t)$
by joining the entries of $\beta^{-1}$. Compute ${\mbox{\rm Gal}}(k_{G}/C(t))$
and

${\mathcal{G}}_{\tilde{F}}=\bigcup_{\tau\in{\mbox{\rm
Gal}}(k_{G}/C(t))}\left\\{g\in{\rm
GL}_{n}(C)\,\,|\,\,\forall\,\,i=1,\cdots,\nu,\,\,Q_{i}(\tau(\beta)^{-1}\tilde{F}g)=0\right\\}.$

  * $(i)$

Return ${\mathcal{G}}_{\tilde{F}}$.

The correctness of the algorithm follows from the results in Sections 2 and 3.
In the following, we will present several computation details omitted in the
previous sections. Generally, it is difficult to find a fundamental matrix of
(1). What we can compute is the first finitely many terms of formal power
series solutions of (1) at some point of $C$. Let $z$ be a generic point of
$C$. Expanding $A$ at $t=z$, we have

$A=A_{0}+A_{1}(t-z)+A_{2}(t-z)^{2}+\cdots,\,\,A_{i}\in{\rm
Mat}_{n}\left(C\left[z,\frac{1}{q(z)}\right]\right)$ (4)

where $q(z)$ is a polynomial in $C[z]$ such that $q(t)$ is the least common
multiple of the denominators of the entries of $A$. Using the above expansion,
we can compute a formal power series solutions of (1) that has the following
form

$\Gamma_{z}=I_{n}+D_{1}(t-z)+D_{2}(t-z)^{2}+\cdots,\,\,D_{i}\in{\rm
Mat}_{n}\left(C\left[z,\frac{1}{q(z)}\right]\right).$

If $a$ is an element of $C$ that does not vanish $q(z)$, then $\Gamma_{z}$ can
be specialized to $\Gamma_{a}$ that is the formal power series expansion of
some fundamental matrix of (1) at $t=a$. In this section, we will use $F_{a}$
to denote the fundamental matrix of (1) in ${\rm GL}_{n}(K)$ whose formal
power series expansion at $t=a$ is of the form $\Gamma_{a}$. We will begin
with a fundamental matrix $F_{a}$ and then may replace it by other fundamental
matrix if necessary during the computation process.

###  4.1 Computing $I_{{F_{a}},\tilde{d}}$ and ${\mathcal{H}}_{F_{a}}$

Corollary A.7 says that the coefficients of defining polynomials in
$C(t)[x_{1,1},\cdots,x_{n,n}]_{\leq\tilde{d}}$ of $Z_{F,\tilde{d}}$ can be
chosen to be rational functions bounded by an integer $\ell$. Without loss of
generality, we may assume that all these coefficients are polynomial in $t$
which are bounded by $2\ell$. Let

$P_{{\mathbf{c}}}(X)=\sum_{|\vec{m}|\leq\tilde{d}}\left(\sum_{0\leq i\leq
2\ell}c_{i,\vec{m}}(t-a)^{i}\right)X^{\vec{m}},\,\,{\mathbf{c}}=(\cdots,c_{i,\vec{m}},\cdots).$

where the $c_{i,\vec{m}}$ are indeterminates. A small modification of Theorem
1 in [1] yields the following theorem that bounds the order of
$P_{{\mathbf{c}}}(F_{a})$.

###### Theorem 4.2

One can compute an integer $N$ depending on $A,n,\ell$ such that

$P_{\mathbf{c}}(F_{a})=0\,\,\mbox{or}\,\,ord_{t=a}(P_{\mathbf{c}}(F_{a}))\leq
N.$

  * Proof.

Consider $F_{a}$ as a vector with $n^{2}$ entries. Then $F_{a}$ is a solution
of the system (${A^{\oplus n}}$). The system (${A^{\oplus n}}$) is defined in
Appendix A. Then the theorem follows from Theorem 1 in [1]. $\Box$

The above theorem can be generalized into the case that the coefficients of
$P_{{\mathbf{c}}}(X)$ involve algebraic functions. More precisely, let
$\gamma$ be an algebraic function with minimal polynomial $Q(x)$ and let
$l=\deg(Q(x))$. Assume that
${\mathbf{w}}=(1,\gamma,\gamma^{2},\cdots,\gamma^{l-1})^{T}$. Then it is easy
to see that ${\mathbf{w}}$ is a solution of linear differential equations
$\delta(Y)=BY$ where $B\in{\rm Mat}_{l}(C(t))$ can be constructed from $Q(x)$.
Let

$\tilde{P}_{{\mathbf{c}}}(X)=\sum_{|\vec{m}|\leq\tilde{d}}\left(\sum_{j=1}^{l}\left(\sum_{0\leq
i\leq
2\ell}c_{i,j,\vec{m}}(t-a)^{i}\right)\gamma^{j}\right)X^{\vec{m}},\,\,{\mathbf{c}}=(\cdots,c_{i,j,\vec{m}},\cdots).$

Assume that $t=a$ is a regular point of $\gamma$. Then

###### Corollary 4.3

There is an integer $\tilde{N}$ depending on $A,Q(x),n,\ell$ such that

$\tilde{P}_{\mathbf{c}}(F_{a})=0\,\,\mbox{or}\,\,\mbox{\rm
ord}_{t=a}\tilde{P}_{{\mathbf{c}}}(F_{a})\leq\tilde{N}.$

  * Proof.

We only need to consider the system

$\delta(Y)=\hbox{\rm diag}(\underbrace{A,\cdots,A}_{n},B)Y.$

Then the corollary follows from the above theorem. $\Box$

Let ${\cal S}$ be the set of the coefficients of the first $N+2$ terms of
$P_{{\mathbf{c}}}(F_{a})$. ${\cal S}$ is a linear system in ${\mathbf{c}}$ and

$P_{\bar{{\mathbf{c}}}}(F_{a})=0\Leftrightarrow\,\,\mbox{$\bar{{\mathbf{c}}}$
is a solution of ${\cal S}$}.$

So computing $I_{{F_{a}},\tilde{d}}$ is reduced into solving the linear system
${\cal S}$.

Assume that $I_{{F_{a}},\tilde{d}}$ is computed. Then we can compute
${\mathcal{H}}_{F_{a}}$ as follows. For any $h\in{\mathcal{H}}_{F_{a}}$,
${F_{a}}h\in Z_{{F_{a}},\tilde{d}}$. It implies that for any $P(X)\in
I_{{F_{a}},\tilde{d}}$, $P(F_{a}h)=0$ and so that $P(Xh)\in
I_{F_{a},\tilde{d}}$. This induces the defining equations for
${\mathcal{H}}_{F_{a}}$. More precisely, let $P_{1}(X),\cdots,P_{\mu}(X)$ be a
$C(t)$-basis of $I_{F_{a},\tilde{d}}$. Let
${\mathbf{x}}=(\cdots,X^{\vec{m}},\cdots)$ be a vector consisting of all
monomials in $x_{1,1},\cdots,x_{n,n}$ with degree not greater than
$\tilde{d}$, where $X^{\vec{m}}=x_{1,1}^{m_{1,1}}x_{1,2}^{m_{1,2}}\cdots
x_{n,n}^{m_{n,n}}$. For any $h\in{\rm GL}_{n}(C)$, there is $[h]\in{\rm
GL}_{n^{2}+\tilde{d}\choose\tilde{d}}(C)$ such that

$h\cdot{\mathbf{x}}=(\cdots,(Xh)^{\vec{m}},\cdots)={\mathbf{x}}[h].$

For any $i=1,\cdots,\mu$, there is ${\mathbf{p}}_{i}\in
C(t)^{n^{2}+\tilde{d}\choose\tilde{d}}$ such that
$P_{i}(X)={\mathbf{x}}{\mathbf{p}}_{i}$. Then we have

$h\in{\mathcal{H}}_{F_{a}}\Leftrightarrow\forall
i,P_{i}(Xh)={\mathbf{x}}[h]{\mathbf{p}}_{i}\in
I_{F_{a},\tilde{d}}\Leftrightarrow\forall
i,[h]{\mathbf{p}}_{i}\wedge{\mathbf{p}}_{1}\wedge{\mathbf{p}}_{2}\wedge\cdots\wedge{\mathbf{p}}_{\mu}=0.$

This induces the defining equations for ${\mathcal{H}}_{F_{a}}$.

###  4.2 Computing $\alpha$ and $\bar{F}$

Assume that we have calculated $I_{F_{a},\tilde{d}}$ and
${\mathcal{H}}_{F_{a}}$. Decomposing ${\mathcal{H}}_{F_{a}}$ into irreducible
components, we obtain ${\mathcal{H}}_{F_{a}}^{\circ}$. Compute a zero
$\bar{\alpha}$ of $I_{F_{a},\tilde{d}}$ in ${\rm GL}_{n}(\overline{C(t)})$.
Assume that $b\in C$ is a regular point of $\bar{\alpha}^{-1}$ and $q(b)\neq
0$, where $q(z)$ is as in (4). It is well-known that there is $g\in{\rm
GL}_{n}(C)$ such that $F_{a}=F_{b}g$. In general, it is difficult to find such
$g$, because we can only compute the first finitely many terms of $\Gamma_{a}$
and $\Gamma_{b}$. Note that $\Gamma_{a}$ (resp. $\Gamma_{b}$) is the formal
power sereis expansion of $F_{a}$ (resp. $F_{b}$) at $t=a$ (resp. $t=b$).
Fortunately, it is easy to find $h\in{\rm GL}_{n}(C)$ such that $F_{b}h$
belongs to $F_{a}{\mathcal{H}}_{F_{a}}$. Such $h$ can be calculated as below.
$F_{b}h\in F_{a}{\mathcal{H}}_{F_{a}}$ if and only if for any $P(X)\in
I_{F_{a},\tilde{d}}$, $P(F_{b}h)=0$. Using the bound given in Theorem 4.2, the
latter conditions derive the defining equations for $h$. Assume that we have
found such $h$. Let $\bar{F}=F_{b}h$. Proposition 3.1 tells us that there is
$\bar{g}\in{\mathcal{H}}_{F_{a}}$ such that
$(\bar{\alpha}\bar{g})^{-1}\bar{F}\in{\mathcal{H}}_{F_{a}}^{\circ}(\bar{k}K)$.
Since both $\bar{\alpha}^{-1}$ and $\bar{F}$ can be expanded as formal power
series at the point $t=b$, the bound given in Theorem 4.2 allows us to derive
the defining equations for $\bar{g}$ from the condition
$(\bar{\alpha}\bar{g})^{-1}\bar{F}\in{\mathcal{H}}_{F_{a}}^{\circ}(\bar{k}K)$.
Compute such $\bar{g}$ and let $\alpha=\bar{\alpha}\bar{g}$.

###  4.3 Computing $h_{i}$

By Remark B.18 in Appendix B, we can find a set of generators of
$X({\mathcal{H}}_{F_{a}}^{\circ})$, say $\chi_{1},\cdots,\chi_{l}$. Assume
that $\chi_{1},\cdots,\chi_{l}$ are defined by polynomials of degree not
greater than an integer $\kappa$. Denote the monomials in entries of
$\alpha^{-1}\bar{F}$ with degree not greater than $\kappa$ by
${\mathbf{m}}_{1},\cdots,{\mathbf{m}}_{m}$. Then each ${\mathbf{m}}_{i}$
satisfies a linear differential operator $L_{i}$ with coefficients in
$C(t)(\alpha^{-1})$. Let $L=LCLM(L_{1},\cdots,L_{m})$. For each
$i=1,\cdots,l$, $h_{i}=\chi_{i}(\alpha^{-1}\bar{F})$ is a hyperexponential
solution of $L$. To compute $h_{i}$, it means to calculate
$v_{i}=h_{i}^{\prime}/h_{i}$ where $i=1,\cdots,l$. From [3], one can compute
all hyperexponential solutions of $L$ and then the bounds for minimal
polynomials of $\bar{h}^{\prime}/\bar{h}$ where $\bar{h}$ is any
hyperexponential solution. Using these bounds and Hermite-Padé approximation,
one can recover $v_{i}$ from the series expansion of
$\chi_{i}(\alpha^{-1}\bar{F})^{\prime}/\chi_{i}(\alpha^{-1}\bar{F})$.

###  4.4 Computing ${\mathcal{G}}_{\tilde{F}}$

The method described in Section 4.2 can be adapted to find $\beta$ and
$\tilde{F}$ in Step (g). So far, in Step (g), we obtain $\beta$ and
$\tilde{F}$ satisfying that
$\beta^{-1}\tilde{F}\in{\mathcal{G}}_{\bar{F}}^{\circ}(\bar{k}K)$, and a set
of generators of $I({\mathcal{G}}_{\bar{F}}^{\circ})$, denoted by
$\\{Q_{1}(X),\cdots,Q_{\nu}(X)\\}$. Assume that $t=c$ is the point we pick to
find $\beta$ and $\tilde{F}$ in Step (g). That is to say, both $\beta^{-1}$
and $\tilde{F}$ can be expanded as formal power series at the point $t=c$. By
Corollary 4.3, there is an integer $\tilde{N}$ such that for all $i$ with
$1\leq i\leq\nu$ and $\tau\in{\mbox{\rm Gal}}(k_{G}/C(t))$,

$Q_{i}(\tau(\beta)^{-1}\tilde{F}{\mathbf{c}})=0\quad\mbox{or}\quad\mbox{\rm
ord}_{t=c}(Q_{i}(\tau(\beta)^{-1}\tilde{F}{\mathbf{c}}))\leq\tilde{N}.$

For each $\tau\in{\mbox{\rm Gal}}(k_{G}/C(t))$, let ${\cal S}_{\tau}$ be the
set of coefficients of the first $\tilde{N}+2$ terms of formal power series
$Q_{1}(\tau(\beta)^{-1}\tilde{F}{\mathbf{c}}),\cdots,Q_{\nu}(\tau(\beta)^{-1}\tilde{F}{\mathbf{c}})$.
Then for each $\tau\in{\mbox{\rm Gal}}(k_{G}/k)$, ${\cal S}_{\tau}$ is the set
of polynomials in ${\mathbf{c}}$ and for any $g\in{\rm GL}_{n}(C)$,
$Q_{i}(\tau(\beta)^{-1}\tilde{F}g)=0$ for all $i$ with $1\leq i\leq\nu$ if and
only if $g\in{\rm Zero}({\cal S}_{\tau}).$ Let

${\mathcal{G}}_{\tilde{F}}=\left(\bigcup_{\tau\in{\mbox{\rm
Gal}}(k_{G}/k)}{\rm Zero}({\cal S}_{\tau})\right)\bigcap{\rm GL}_{n}(C).$

We then obtain the desired Galois group.

##  Appendix A Bounds for $k$-definable elements of $N_{d}(V^{n}_{inv})$

In this appendix, the symbols in the previous sections are used. Let $W$ be a
$C$-vector subspace of $V$ of dimension not greater than $n$. Assume that
${\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m}$ is a basis of $W$.

###### Definition A.1

$W$ is said to be $k$-definable if there is $M\in GL_{n}(k)$ such that

$M({\mathbf{w}}_{1},{\mathbf{w}}_{2},\cdots,{\mathbf{w}}_{m})=\begin{pmatrix}\tilde{W}\\\
0\end{pmatrix}$ (5)

where $\tilde{W}$ is an invertible $m\times m$ matrix. We call $M$ the
defining matrix of $W$.

###### Remark A.2

There is some $B\in{\mbox{\rm Mat}}_{m}(k)$ such that $\tilde{W}$ is a
fundamental matrix of linear differential equations $\delta(Y)=BY$.

Clearly, $V$ is a ${\mathcal{G}}$-module. Moreover, we have

###### Proposition A.3

Let $W$ be a $C$-vector subspace of $V$. Then the following are equivalent:

  1. $(a)$

$W$ is $k$-definable;

  2. $(b)$

$W$ is a ${\mathcal{G}}$-submodule of $V$.

  * Proof.

$(a)\Rightarrow(b)$. Assume that $W$ is $k$-definable and
${\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m}$ is a $C$-basis of $W$. Then there
is an $M\in{\rm GL}_{n}(k)$ such that (5) holds. For any
$\sigma\in{\mathcal{G}}$, it follows from Remark A.2 that there is
$[\sigma]\in{\rm GL}_{m}(C)$ such that $\sigma(\tilde{W})=\tilde{W}[\sigma]$.
Applying $\sigma$ to (5), we have

$M(\sigma({\mathbf{w}}_{1}),\sigma({\mathbf{w}}_{2}),\cdots,\sigma({\mathbf{w}}_{m}))=\begin{pmatrix}\tilde{W}\\\
0\end{pmatrix}[\sigma].$

Then the above equality and (5) deduce that

$(\sigma({\mathbf{w}}_{1}),\sigma({\mathbf{w}}_{2}),\cdots,\sigma({\mathbf{w}}_{m}))=({\mathbf{w}}_{1},{\mathbf{w}}_{2},\cdots,{\mathbf{w}}_{m})[\sigma].$

Hence $W$ is a ${\mathcal{G}}$-submodule.

$(b)\Rightarrow(a)$. Assume that $W$ is a ${\mathcal{G}}$-submodule and
${\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m}$ is a $C$-basis of $W$. Then there
is an $m\times m$ submatrix of $({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m})$
which is invertible. Without loss of generality, assume that the submatrix
consisting of the first $m$ rows of the matrix
$({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m})$ is invertible. Denote this
submatrix by $\tilde{W}$ and the left $(n-m)\times m$ submatrix by $\bar{W}$.
Let $\bar{M}=\bar{W}\tilde{W}^{-1}$. Assume that $\sigma\in{\mathcal{G}}$. We
then have that
$\sigma(({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m})[\sigma]$
for some $[\sigma]\in{\rm GL}_{m}(C)$. Applying $\sigma$ to $\bar{M}$ yields
that

$\sigma(\bar{M})=\sigma(\bar{W}\tilde{W}^{-1})=\sigma(\bar{W})\sigma(\tilde{W}^{-1})=\bar{W}[\sigma](\tilde{W}[\sigma])^{-1}=\bar{W}\tilde{W}^{-1}=\bar{M},$

which implies that $\sigma(\bar{M})=\bar{M}$ for all $\sigma\in{\mathcal{G}}$.
Hence all entries of $\bar{M}$ belong to $k$. Let

$M=\begin{pmatrix}I_{m}&0\\\ -\bar{M}&I_{n-m}\end{pmatrix},$ (6)

Then $M$ is a matrix such that (5) holds. $\Box$

###### Definition A.4

Let $W$ be a $k$-definable subspace of $V$ and $m$ an integer. We call $W$
bounded by $m$ if there is $M$ with $\deg(M)\leq m$ such that (5) holds, where
$\deg(M)$ is defined as the maximum of the degrees of entries of $M$.

###### Proposition A.5

There is an integer $\ell$ such that all $k$-definable subspaces of $V$ are
bounded by $\ell$.

  * Proof.

Evidently, it is enough to prove Proposition A.5 for the fixed dimension
$k$-definable subspaces. Let $W$ be a $k$-definable subspace of $V$ with a
basis ${\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{m}$. From the proof of
Proposition A.3, $M$ can be chosen to satisfy that there is a permutation
matrix $P$ such that $MP$ is of the form (6). In other words,

$({\mathbf{w}}_{1},{\mathbf{w}}_{2},\cdots,{\mathbf{w}}_{m})=P\begin{pmatrix}I_{m}&0\\\
\bar{M}&I_{n-m}\end{pmatrix}\begin{pmatrix}\tilde{W}\\\ 0\end{pmatrix},$

where $\bar{M}$ is an $(n-m)\times m$ matrix with entries in $k$. If
$\deg(\bar{M})$ is not greater than $\ell$, neither is $\deg(M)$. One can
easily see that the coordinates of $P{\mathbf{w}}_{1}\wedge
P{\mathbf{w}}_{2}\wedge\cdots\wedge P{\mathbf{w}}_{m}$ are the permutation of
those of
${\mathbf{w}}_{1}\wedge{\mathbf{w}}_{2}\wedge\cdots\wedge{\mathbf{w}}_{m}$.
This implies that we only need to consider the case $P=I_{n}$. An easy
calculation yields that

$\displaystyle{\mathbf{w}}_{1}\wedge{\mathbf{w}}_{2}\wedge\cdots\wedge{\mathbf{w}}_{m}$
$\displaystyle=\sum_{1\leq i_{1}<i_{2}<\cdots<i_{m}\leq
n}c_{i_{1},i_{2},\cdots,i_{m}}{\mathbf{e}}_{i_{1}}\wedge{\mathbf{e}}_{i_{2}}\wedge\cdots\wedge{\mathbf{e}}_{i_{m}}$
$\displaystyle=\sum_{1\leq i_{1}<i_{2}<\cdots<i_{m}\leq
n}a_{i_{1},i_{2},\cdots,i_{m}}\det(\tilde{W}){\mathbf{e}}_{i_{1}}\wedge{\mathbf{e}}_{i_{2}}\wedge\cdots\wedge{\mathbf{e}}_{i_{m}},$

where $c_{i_{1},i_{2},\cdots,i_{m}}\in K,a_{i_{1},i_{2},\cdots,i_{m}}\in k$.
Note that $\delta(\tilde{W})=B\tilde{W}$ for some $B\in{\rm Mat}_{m}(k)$.
Therefore $\delta(\det(\tilde{W}))=\mbox{\rm{Tr}}(B)\det(\tilde{W})$. It
implies that the vector $(\cdots,c_{i_{1},i_{2},\cdots,i_{m}},\cdots)$ is a
hyperexponential solution over $k$ of the exterior system
$\delta(Y)=\left(\wedge^{m}A\right)Y$. The matrix $\wedge^{m}A$ can be
constructed from $A$. Assume that $\bar{M}=(\lambda_{i,j}),1\leq i\leq
n-m,1\leq j\leq m$. We further have that

$a_{12\cdots m}=1,\,\,a_{12\cdots\hat{j}\cdots mi}=\lambda_{i-m,j},\,\,m+1\leq
i\leq n,1\leq j\leq m.$

Assume that ${\mathbf{v}}h$ is a hyperexponential solution of
$\delta(Y)=\left(\wedge^{m}A\right)Y$ where $h$ is a hyperexponential element
over $k$ and ${\mathbf{v}}\in k^{n\choose m}$. Note that if we fix
hyperexponential elements $h$, then from [14, 16], there is an integer $\ell$
such that $\deg({\mathbf{v}})\leq\ell/2$. To obtain the entries of $\bar{M}$
from those of ${\mathbf{v}}$, we need to normalize ${\mathbf{v}}$ at some
coordinate, for instance when $P=I_{n}$, $a_{12\cdots m}$ is normalized to 1.
Hence $\deg(\bar{M})\leq\ell$. $\Box$

Since we restrict ourselves to Zariski closed subsets of $V^{n}_{inv}$, we
need to consider the following two new systems. One is the $n$-direct sum of
(1):

$\delta(Y)=\hbox{\rm diag}(\underbrace{A,A,\cdots,A}_{n})Y=A^{\oplus n}Y.$
(${A^{\oplus n}}$)

Then $V^{n}$ is the solution space of (${A^{\oplus n}}$) and $\hbox{\rm
diag}(\underbrace{F,F\cdots,F}_{n})$, denoted by $F^{\oplus n}$, is a
fundamental matrix. The other is the symmetric power system of (${A^{\oplus
n}}$). Define a map

$\displaystyle S^{\leq d}:V^{n}$ $\displaystyle\longrightarrow
K^{n^{2}+d\choose d}$
$\displaystyle{\mathbf{v}}=(v_{1,1},v_{2,1},\cdots,v_{n,n})$
$\displaystyle\longrightarrow(\cdots,v_{1,1}^{\mu_{1,1}}v_{1,2}^{\mu_{1,2}}\cdots
v_{n,n}^{\mu_{n,n}},\cdots,),\,\,\sum_{1\leq i,j\leq n}\mu_{i,j}\leq d.$

Then $S^{\leq d}({\mathbf{v}})$ is a solution of the symmetric power system of
(1), denoted by

$\delta(Y)=\left({S^{\leq d}A^{\oplus n}}\right)Y.$ (${S^{\leq d}A^{\oplus
n}}$)

The matrix ${S^{\leq d}A^{\oplus n}}$ can be constructed from $A$ and its
entries are in $k$. Denote the solution space of (${S^{\leq d}A^{\oplus n}}$)
by ${(V^{n})^{\circledS\leq d}}$. More details about the symmetric power
system could be found in (p. 39, [16]) and [14].

Let $Z$ be an element of $N_{d}(V^{n}_{inv})$. Set

$W_{Z}={\rm span}_{C}\\{S^{\leq d}({\mathbf{z}}),{\mathbf{z}}\in Z\\}.$

Then $W_{Z}$ is a subspace of ${(V^{n})^{\circledS\leq d}}$.

###### Proposition A.6

Given an element $Z$ of $N_{d}(V^{n}_{inv})$, $Z$ is $k$-definable if and only
if $W_{Z}$ is $k$-definable.

  * Proof.

Suppose that $S^{\leq d}({\mathbf{v}}_{1}),\cdots,S^{\leq
d}({\mathbf{v}}_{m})$ is a basis of $W_{Z}$.

$(\Rightarrow)$ Assume that $\sigma\in{\mathcal{G}}$. Since $Z$ is
$k$-definable, $\sigma({\mathbf{v}})\in Z$ for all ${\mathbf{v}}\in Z$. It
implies that for each $i=1,\cdots,m$, $\sigma(S^{\leq
d}({\mathbf{v}}_{i}))=S^{\leq d}(\sigma({\mathbf{v}}_{i}))\in W_{Z}$.
Consequently, $W_{Z}$ is a ${\mathcal{G}}$-module. By Proposition A.3, $W_{Z}$
is $k$-definable.

$(\Leftarrow)$ Assume that $W_{Z}$ is $k$-definable. By Proposition A.3, there
is $M\in{\rm GL}_{m}(k)$ such that

$M(S^{\leq d}({\mathbf{v}}_{1}),\cdots,S^{\leq
d}({\mathbf{v}}_{m}))=\begin{pmatrix}\tilde{W}\\\ 0\end{pmatrix}$

where $\tilde{W}$ is an $m\times m$ matrix. Denote the $i$th-row of $M$ by
${\mathbf{m}}_{i}$ for $i=m+1,\cdots,{n^{2}+d\choose d}$. Let
${\mathbf{x}}=(1,x_{1,1},\cdots,x_{1,1}^{\mu_{1,1}}\cdots
x_{n,n}^{\mu_{n,n}},\cdots)$ where $\mu_{1,1}+\mu_{1,2}+\cdots+\mu_{n,n}\leq
d$. Then $P_{i}(X)={\mathbf{m}}_{i}\cdot{\mathbf{x}}$ is a polynomial of
degree at most $d$ with the coefficients in $k$, where
$i=m+1,\cdots,{n^{2}+d\choose d}$. One can easily verify that

$Z\subseteq{\rm Zero}\left(P_{m}(X),\cdots,P_{n^{2}+d\choose
d}(X)\right)\bigcap V_{inv}^{n}.$

Since $Z\in N_{d}(V^{n}_{inv})$, there are $Q_{1}(X),\cdots,Q_{l}(X)$ with
degree at most $d$, which define $Z$. By the dimension argument, for each
$i=1,\cdots,l$, $Q_{i}(X)$ is a $\bar{k}$-linear combinations of
$P_{m}(X),\cdots,P_{n^{2}+d\choose d}(X)$. Therefore the above inclusion
relation is actually an equality. $\Box$

The above two propositions indicate the following corollary.

###### Corollary A.7

There is an integer $\ell$ such that for every $k$-definable element $Z$ of
$N_{d}(V^{n}_{inv})$, the coefficients of the defining equations of $Z$ can be
chosen to be rational functions whose degrees are not greater than $\ell$.

  * Proof.

Let $Z$ be a $k$-definable element of $N_{d}(V^{n}_{inv})$. Then $W_{Z}$ is a
$k$-definable subspace of ${(V^{n})^{\circledS\leq d}}$ by Proposition A.6.
Moreover, from the proof of Proposition A.6, the coefficients of the defining
equations of $Z$ can be chosen to be the entries of the defining matrix of
$W_{Z}$. Hence to prove the corollary, it suffices to show that all
$k$-definable subspaces of ${(V^{n})^{\circledS\leq d}}$ are bounded by an
integer $\ell$. This can be done by applying Proposition A.5 to
${(V^{n})^{\circledS\leq d}}$. $\Box$

##  Appendix B Bounds for proto-Galois groups

In this appendix, we shall find an integer $\tilde{d}$ depending on $n$ with
the following property. For any algebraic subgroup $G$ of ${\rm GL}_{n}(C)$,
there is an algebraic subgroup $H$ of ${\rm GL}_{n}(C)$, which is bounded by
$\tilde{d}$, satisfying

$(*):(H^{\circ})^{t}\unlhd G^{\circ}\leq G\leq H.$

Most of results in this section appeared in the part iii@ of [6], where more
families of algebraic subgroups of ${\rm GL}_{n}(C)$ that can be uniformly
definable are given. Here we only present those we need. At the same tine, we
will use the term “bounded by $d$” instead of “uniformly definable”. As
mentioned in Introduction, we elaborate the details of the proofs in [6] and
present the explicit estimates of the bounds. Meanwhile, we will show how to
compute a set of generators of the character group of a given connected
algebraic subgroup. The following notation will be used frequently.

###### Notation B.1

Let $H$ be an algebraic subgroup of ${\rm GL}_{n}(C)$ and $S$ an arbitrary
subset of $H$.

${\mathcal{F}}$: a family of algebraic subgroups of ${\rm GL}_{n}(C)$;
$H_{\mathcal{F}}$: the intersection of all $H^{\prime}\in{\mathcal{F}}$ with
$H\subseteq H^{\prime}$; $N_{H}(H^{\prime})$: the normalizer of $H^{\prime}$
in $H$ where $H^{\prime}$ is an algebraic subgroup of $H$;
${\mathcal{F}}_{mt}(H)$: the family of maximal tori of $H$;
${\mathcal{F}}_{imt}(H)$: the family of intersections of maximal tori of $H$;
${\mathcal{F}}_{up}$: the family of subgroups of ${\rm GL}_{n}(C)$ generated
by unipotent elements; $X(H)$: the group of characters of $H$; $H^{t}$: the
intersection of kernals of all characters of $H$.

An algebraic subgroup $H$ of ${\rm GL}_{n}(C)$ is said to be bounded by $d$ if
there are polynomials $Q_{1}(X),\cdots,Q_{m}(X)$ in
$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$ with degree not greater than $d$ such that

$H={\rm Zero}(Q_{1}(X),\cdots,Q_{m}(X))\bigcap{\rm GL}_{n}(C).$

For a family of algebraic subgroups of ${\rm GL}_{n}(C)$, say ${\mathcal{F}}$,
we say ${\mathcal{F}}$ is bounded by $d$, if every element of ${\mathcal{F}}$
is bounded by $d$. For an ideal $I$ in $C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$,
$I$ is said to be bounded by $d$ if there exist generators of $I$ whose
degrees are not greater than $d$. Throughout this appendix, unless otherwise
specified, subgroups always mean algebraic subgroups.

###  B.1 Preparation lemmas

To achieve the integer $\tilde{d}$, we need the following degree bounds from
computational algebraic geometry. More details on these degree bounds can be
found in [4, 9, 13]. For the moment, we assume that $I$ is an ideal in
$C[x_{1},\cdots,x_{n}]$. Then we have

###### Proposition B.2

Suppose that $I$ is bounded by $d$. Then there is $\gamma(n,d)$ in
${\mathbb{N}}$ such that $I\cap C[x_{1},\cdots,x_{i}]$ is bounded by
$\gamma(n,d)$.

###### Remark B.3

By Groebner bases computation, $\gamma(n,d)$ can be chosen as
$2\left(\frac{d^{2}}{2}+d\right)^{2^{n-1}}$, which is less than
$(d+1)^{2^{n}}$. The reader is referred to [4] for more details.

The following several lemmas play the key role in this appendix.

###### Lemma B.4

Let $H$ be a subgroup of ${\rm GL}_{n}(C)$ bounded by $d$. Then there exists a
family ${\mathcal{F}}_{ad}(H)$ of subgroups of $H$ bounded by $\max\\{d,n\\}$
such that for any connected subgroup $H^{\prime}$ of $H$,
$N_{H}(H^{\prime})\in{\mathcal{F}}_{ad}(H)$. Particularly,
${\mathcal{F}}_{ad}({\rm GL}_{n}(C))$ is bounded by $n$.

  * Proof.

Let ${\mathfrak{g}l}(H)$ be the Lie algebra of $H$. Consider the adjoint
action of $H$ on ${\mathfrak{g}l}(H)$. Then ${\mathfrak{g}l}(H^{\prime})$ is a
subspace of ${\mathfrak{g}l}(H)$ and $N_{H}(H^{\prime})$ is the stabilizer of
${\mathfrak{g}l}(H^{\prime})$ under the adjoint action. Let
$B_{1},\cdots,B_{l}$ be a basis of ${\mathfrak{g}l}(H^{\prime})$ and the
${\mathbf{e}}_{i,j}$ a basis of ${\rm Mat}_{n}(C)$. Then for any $h\in
N_{H}(H^{\prime})$, there is $g_{h}\in{\rm GL}_{n^{2}}(C)$ such that
$h({\mathbf{e}}_{1,1},\cdots,{\mathbf{e}}_{n,n})h^{-1}=({\mathbf{e}}_{1,1},\cdots,{\mathbf{e}}_{n,n})g_{h}$.
It is easy to see that the entries of $g_{h}$ are of the form
$P_{l,m}(h)/\det(h)$ where the $P_{l,m}(X)$ are polynomials with degree at
most $n$. Assume that
$B_{s}=({\mathbf{e}}_{1,1},\cdots,{\mathbf{e}}_{n,n}){\mathbf{b}}_{s}$ for
$s=1,\cdots,l$ where ${\mathbf{b}}_{s}=(b_{s,i,j})\in C^{n^{2}}$. Then since
$hB_{s}h^{-1}\in{\mathfrak{g}l}(H^{\prime})$, there are
$a_{s,1},\cdots,a_{s,l}\in C$ such that
$hB_{s}h^{-1}=\sum_{\xi}a_{s,\xi}B_{\xi}$. In other words,

$hB_{s}h^{-1}=\sum_{i,j}b_{s,i,j}h{\mathbf{e}}_{i,j}h^{-1}=({\mathbf{e}}_{1,1},\cdots,{\mathbf{e}}_{n,n})g_{h}{\mathbf{b}}_{s}=({\mathbf{e}}_{1,1},\cdots,{\mathbf{e}}_{n,n})\sum_{\xi=1}^{l}a_{s,\xi}{\mathbf{b}}_{\xi}.$

That is

$g_{h}{\mathbf{b}}_{s}=\sum_{\xi=1}^{l}a_{s,\xi}{\mathbf{b}}_{\xi}.$

The above nonhomogeneous linear equations has solutions if and only if

$\mbox{\rm{rank}}({\mathbf{b}}_{1},\cdots,{\mathbf{b}}_{l})=\mbox{\rm{rank}}({\mathbf{b}}_{1},\cdots,{\mathbf{b}}_{l},g_{h}{\mathbf{b}}_{s}).$

This leads to the equations that together with the defining equations of $H$
define $N_{H}(H^{\prime})$. Since the entries of $g_{h}$ are of the form
$P_{l,m}(h)/\det(h)$ where the $P_{l,m}(X)$ are polynomials with degree at
most $n$, the defining ideal of $N_{H}(H^{\prime})$ is generated by those of
$H$ and the polynomials with degrees $\leq n$. Hence ${\mathcal{F}}_{ad}(H)$
is bounded by $\max\\{d,n\\}$. In particular, when $H={\rm GL}_{n}(C)$,
${\mathcal{F}}_{ad}({\rm GL}_{n}(C))$ is bounded by $n$. $\Box$

Let $\\{\tau_{H,\lambda}:H\rightarrow{\rm
GL}_{\mu}(C)|H\in{\mathcal{F}},\lambda\in\Lambda\\}$ be a family of morphisms
from elements of ${\mathcal{F}}$ to ${\rm GL}_{\mu}(C)$ where $\mu$ is a
positive integer and $\Lambda$ is a set. Assume that
$\tau_{H,\lambda}=(P_{i,j}^{H,\lambda}(X)/Q^{H,\lambda}(X))$. We will say that
the $\\{\tau_{H,\lambda}\\}$ are bounded by $m$ if
$\deg(P^{H,\lambda}_{i,j}(X))\leq m$ and $\deg(Q^{H,\lambda}(X))\leq m$.

###### Lemma B.5

Let $\\{\tau_{H,\lambda}\,\,|\,\,H\in{\mathcal{F}},\lambda\in\Lambda\\}$ be as
above. Assume that ${\mathcal{F}}$ is bounded by $d$ and
$\\{\tau_{H,\lambda}\,\,|\,\,H\in{\mathcal{F}},\lambda\in\Lambda\\}$ is
bounded by $m$. Then

  * $(a)$

$\\{\tau_{H,\lambda}(H)\\}$ is bounded by $(\bar{d}+1)^{2^{\mu^{2}+n^{2}}}$
where $\bar{d}=\max\\{m+1,d\\}$.

  * $(b)$

if ${\mathcal{F}}^{\prime}$ is a family of subgroups of ${\rm GL}_{\mu}(C)$
bounded by $d^{\prime}$, then

$\\{\tau^{-1}_{H,\lambda}\left(H^{\prime}\cap\tau_{H,\lambda}(H)\right)|H^{\prime}\in{\mathcal{F}}^{\prime},H\in{\mathcal{F}},\lambda\in\Lambda\\}$

is bounded by $\max\\{d,md^{\prime}\\}.$

  * Proof.

Assume that $H$ is defined by $S_{H}$, a set of polynomials with degree $\leq
d$.

$(a)$ $\tau_{H,\lambda}(H)$ is defined by

$\left\langle
Q^{H,\lambda}(X)y_{1,1}-P^{H,\lambda}_{1,1}(X),\cdots,Q^{H,\lambda}(X)y_{\mu,\mu}-P^{H,\lambda}_{\mu,\mu}(X),S_{H}\right\rangle\bigcap
C[y_{1,1},y_{1,2},\cdots,y_{\mu,\mu}].$

By Proposition B.2, $\tau_{H,\lambda}(H)$ is bounded by
$(\bar{d}+1)^{2^{\mu^{2}+n^{2}}}$ where $\bar{d}=\max\\{m+1,d\\}$.

$(b)$ Assume that $H^{\prime}$ is defined by $g_{1}(Y),\cdots,g_{s}(Y)$ where
$\deg(g_{i}(Y))\leq d^{\prime}$. Then one can see that
$\tau^{-1}_{H,\lambda}\left(H^{\prime}\cap\tau_{H,\lambda}(H)\right)$ is
defined by

$S_{H},\,\,g_{1}\left(\left(\frac{P^{H,\lambda}_{i,j}(X)}{Q^{H,\lambda}(X)}\right)\right),\cdots,g_{s}\left(\left(\frac{P^{H,\lambda}_{i,j}(X)}{Q^{H,\lambda}(X)}\right)\right).$

Clearing the denominators, we obtain the defining polynomials of
$\tau^{-1}_{H,\lambda}\left(H^{\prime}\cap\tau_{H,\lambda}(H)\right)$ in
$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$, whose degrees are not greater than
$\max\\{d,md^{\prime}\\}$. $\Box$

Given a non-negative integer $d$, set

$d^{*}=\max_{i}\left\\{{{n^{2}+d\choose d}\choose
i}^{2}\right\\},\,\,n^{*}=d^{*}d{n^{2}+d\choose d}.$

###### Proposition B.6

Assume that ${\mathcal{F}}$ is bounded by $d$. Then for any subgroup
$H^{\prime}\subseteq{\rm GL}_{n}(C)$ and $H\in{\mathcal{F}}$ with $H\unlhd
H^{\prime}$, there is a family of morphisms
$\tau_{H^{\prime},H}:H^{\prime}\rightarrow{\rm GL}_{d^{*}}(C)$ with
$\ker(\tau_{H^{\prime},H})=H$, which are bounded by $n^{*}$. Furthermore, if
$H^{\prime}$ varies among a family of subgroups of ${\rm GL}_{n}(C)$ bounded
by $d^{\prime}$, then
$\\{\tau_{H^{\prime},H}(H^{\prime})|H^{\prime}\in{\mathcal{F}}^{\prime},H\in{\mathcal{F}}\,\,\mbox{with}\,\,H\unlhd
H^{\prime}\\}$ is bounded by

$(\bar{d}+1)^{2^{(d^{*})^{2}+n^{2}}},\,\,\mbox{where}\,\,\bar{d}=\max\\{n^{*}+1,d^{\prime}\\}.$

  * Proof.

$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq d}$ is a $C$-vector space with
dimension $n^{2}+d\choose d$. The group ${\rm GL}_{n}(C)$ acts naturally on
$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq d}$, which is defined as follows

$\forall\,\,g\in{\rm GL}_{n}(C),\,\,P(x)\in
C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq d},\,\,g\cdot P(X)=P(Xg).$

Suppose that $H\in{\mathcal{F}}$. Let

$I_{\leq d}(H)=\\{P(X)\in C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq
d}\,\,|\,\,P(H)=0\\}.$

It is also a $C$-vector space of finite dimension. Since $I_{\leq d}(H)$
defines $H$, $H={\rm stab}(I_{\leq d}(H))$. Let $\nu=\dim_{C}(I_{\leq d}(H))$
and

$E=\bigwedge^{\nu}C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq d}.$

Then

$\dim_{C}(E)={{n^{2}+d\choose
d}\choose\nu}\,\,\mbox{and}\,\,\bigwedge^{\nu}I_{\leq
d}(H)=C{\mathbf{v}}\,\,\mbox{for some ${\mathbf{v}}\in E$}.$

The action of ${\rm GL}_{n}(C)$ on $C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq
d}$ induces an action of ${\rm GL}_{n}(C)$ on $E$. We will still use $\cdot$
to denote this action. It is easy to see that $H={\rm stab}(C{\mathbf{v}})$.
Let $U=\oplus U_{\chi}$ where the $\chi$ are characters of $H$ and

$U_{\chi}=\\{{\mathbf{u}}\in
E\,\,|\,\,h\cdot{\mathbf{u}}=\chi(h){\mathbf{u}}\\}.$

Note that the above direct sum runs over a finite set. Assume that
$U=\oplus_{i=1}^{s}U_{\chi_{i}}$. It is clear that ${\mathbf{v}}\in
U_{\chi_{i}}$ for some $i$. Let $H^{\prime}$ be a subgroup of ${\rm
GL}_{n}(C)$ satisfying that $H\unlhd H^{\prime}$. Then $U$ is invariant under
the action of $H^{\prime}$. Let ${\mathcal{L}}$ be the set of $C$-linear maps
from $U$ to $U$ which leave all $U_{\chi_{i}}$ unchanged. Then since
$\dim_{C}(U)\leq\dim_{C}(E)$,

$\dim_{C}({\mathcal{L}})\leq(\dim_{C}(U))^{2}\leq(\dim_{C}(E))^{2}={{n^{2}+d\choose
d}\choose\nu}^{2}.$

Let ${\mathbf{u}}_{1},\cdots,{\mathbf{u}}_{l}$ be a suitable basis of $U$ such
that under this basis, each element of ${\mathcal{L}}$ is represented as the
matrix $\hbox{\rm diag}(M_{1},\cdots,M_{s})$ where $M_{i}\in{\rm
Mat}_{\dim(U_{\chi_{i}})}(C)$. Furthermore every matrix of the form $\hbox{\rm
diag}(M_{1},\cdots,M_{s})$ where $M_{i}\in{\rm Mat}_{\dim(U_{\chi_{i}})}(C)$
represents an element of ${\mathcal{L}}$. For any $h^{\prime}\in H^{\prime}$,
there is $[h^{\prime}]\in{\rm GL}_{l}(C)$ such that

$(h^{\prime}\cdot{\mathbf{u}}_{1},\cdots,h^{\prime}\cdot{\mathbf{u}}_{l})=({\mathbf{u}}_{1},\cdots,{\mathbf{u}}_{l})[h^{\prime}].$

By an easy calculation, the entries of $[h^{\prime}]$ are polynomials in those
of $h^{\prime}$ with degree $\leq d\nu$. For any $L\in{\mathcal{L}}$, we will
use $L^{{\mathbf{u}}}$ to denote the matrix in ${\rm GL}_{l}(C)$ satisfies
that

$L(({\mathbf{u}}_{1},{\mathbf{u}}_{2},\cdots,{\mathbf{u}}_{l}))=({\mathbf{u}}_{1},{\mathbf{u}}_{2},\cdots,{\mathbf{u}}_{l})L^{\mathbf{u}}.$

The action of $H^{\prime}$ on $U$ derives an adjoint action of $H^{\prime}$ on
${\mathcal{L}}$ as follows: for any $L\in{\mathcal{L}},h^{\prime}\in
H^{\prime}$,

$\displaystyle(h^{\prime}\cdot L)(({\mathbf{u}}_{1},\cdots,{\mathbf{u}}_{l}))$
$\displaystyle=h^{\prime}\cdot
L(h^{\prime-1}\cdot{\mathbf{u}}_{1},\cdots,h^{\prime-1}\cdot{\mathbf{u}}_{l})=h^{\prime}\cdot
L(({\mathbf{u}}_{1},\cdots,{\mathbf{u}}_{l})[h^{\prime}]^{-1})$
$\displaystyle=h^{\prime}\cdot(({\mathbf{u}}_{1},\cdots,{\mathbf{u}}_{l})L^{\mathbf{u}}[h^{\prime}]^{-1})=({\mathbf{u}}_{1},\cdots,{\mathbf{u}}_{l})[h^{\prime}]L^{\mathbf{u}}[h^{\prime}]^{-1}.$

Fix a basis of ${\mathcal{L}}$, say $L_{1},\cdots,L_{m}$, where
$m\leq{{n^{2}+d\choose d}\choose\nu}^{2}$. Then the adjoint action induces a
morphism from $H^{\prime}$ to ${\rm GL}_{m}(C)$

$\tau_{H^{\prime},H}:H^{\prime}\longrightarrow{\rm
GL}_{m}(C),\,\,\tau_{H^{\prime},H}(h^{\prime})=\eta_{h^{\prime}}$ (7)

where $\eta_{h^{\prime}}\in{\rm GL}_{m}(C)$ satisfies that

$([h^{\prime}]L_{1}^{\mathbf{u}}[h^{\prime}]^{-1},\cdots,[h^{\prime}]L_{m}^{\mathbf{u}}[h^{\prime}]^{-1})=(L_{1}^{\mathbf{u}},\cdots,L_{m}^{\mathbf{u}})\eta_{h^{\prime}}.$

We will show that $\ker(\tau_{H^{\prime},H})=H$. Suppose that
$h^{\prime}\in\ker(\tau_{H^{\prime},H})$. Then $\eta_{h^{\prime}}=I_{m}$. In
other words, $[h^{\prime}]L^{\mathbf{u}}=L^{\mathbf{u}}[h^{\prime}]$ for all
$L\in{\mathcal{L}}$. It implies that $[h^{\prime}]$ is of the following form:

$[h^{\prime}]=\hbox{\rm
diag}(\underbrace{c_{1},\cdots,c_{1}}_{\dim(V_{\chi_{1}})},\cdots,\underbrace{c_{s},\cdots,c_{s}}_{\dim(V_{\chi_{s}})}).$

Particularly, $h^{\prime}\cdot{\mathbf{v}}=c_{i}{\mathbf{v}}$ for some $i$.
Hence $h^{\prime}\in H={\rm stab}(C{\mathbf{v}})$. One can easily see that
$H\subseteq\ker(\tau_{H^{\prime},H})$. Hence $H=\ker(\tau_{H^{\prime},H})$.
Since $m\leq d^{*}$, ${\rm GL}_{m}(C)$ can be naturally embedded into ${\rm
GL}_{d^{*}}(C)$. Composing this embedding map with $\tau_{H^{\prime},H}$
induces a morphism from $H^{\prime}$ to ${\rm GL}_{d^{*}}(C)$ with kernel $H$.
We will still denote this morphism by $\tau_{H^{\prime},H}$. An easy
calculation yields that

$\tau_{H^{\prime},H}(X)=\left(\frac{P_{i,j}^{H^{\prime},H}(X)}{Q^{H^{\prime},H}(X)}\right)$

where $P_{i,j}^{H^{\prime},H}(X),Q^{H^{\prime},H}(X)$ are polynomials in
$x_{i,j}$ and $Q^{H^{\prime},H}(h^{\prime})=\det([h^{\prime}])$. Furthermore,
the $P_{i,j}^{H^{\prime},H}(h^{\prime})$ are polynomials in the entries of
$[h^{\prime}]$ with degree $\leq l$. Since the entries of $[h^{\prime}]$ are
polynomials in those of $h^{\prime}$ with degree $\leq d\nu$, the
$P_{i,j}^{H^{\prime},H}(h^{\prime})$ and $Q^{H^{\prime},H}(h^{\prime})$ are
polynomials in the entries of $h^{\prime}$ with degree $\leq ld\nu$, which is
not greater than $n^{*}$. This proves that
$\\{\tau_{H,\lambda}\,\,|\,\,H\in{\mathcal{F}},\lambda\in\Lambda\\}$ is
bounded by $n^{*}$.

Finally, by Lemma B.5,
$\\{\tau_{H^{\prime},H}(H^{\prime})|H^{\prime}\in{\mathcal{F}}^{\prime},H\in{\mathcal{F}}\,\,\mbox{with}\,\,H\unlhd
H^{\prime}\\}$ is bounded by
$(\bar{d}+1)^{2^{(d^{*})^{2}+n^{2}}},\,\,\mbox{where}\,\,\bar{d}=\max\\{n^{*}+1,d^{\prime}\\}$.
$\Box$

###### Remark B.7

As linear algebraic groups, $\tau_{H^{\prime},H}(H^{\prime})$ is isomorphic to
$H^{\prime}/H$. Therefore Proposition B.6 says that $H^{\prime}/H$ can be
uniformly embedded into ${\rm GL}_{d^{*}}(C)$ and $H^{\prime}/H$ varies among
a bounded family if $H^{\prime}$ does.

###### Lemma B.8

${\mathcal{F}}_{up}$ is bounded by $(2n^{3}+1)^{8^{n^{2}}}$.

  * Proof.

Assume that $H$ is a subgroup generated by unipotent elements. Then by (p.55,
Proposition, [5] ), it is the product of at most $2\dim(H)$ one-dimensional
unipotent subgroups. From (p. 96, Lemma C, [5]), we know that one-dimension
unipotent subgroup is of the form:

$I_{n}+{\mathbf{m}}x+\frac{{\mathbf{m}}^{2}}{2}x^{2}+\cdots+\frac{{\mathbf{m}}^{n-1}}{(n-1)!}x^{n-1},\,\,{\mathbf{m}}^{n}=0,\,\,x\in
C,$

where ${\mathbf{m}}\in{\rm Mat}_{n}(C)$ and ${\mathbf{m}}^{n}=0$. Hence $H$
has a polynomial parametrized representation

$(Y)=\prod_{i=1}^{2\dim(H)}\left(I_{n}+{\mathbf{m}}_{i}x_{i}+\frac{{\mathbf{m}}_{i}^{2}}{2}x_{i}^{2}+\cdots+\frac{{\mathbf{m}}_{i}^{n-1}}{(n-1)!}x_{i}^{n-1}\right).$

Note that $\dim(H)\leq n^{2}$. Then the polynomials in the above system
contains at most $3n^{2}$ variables and are of degree not greater than
$2n^{3}$. Eliminating all $x_{i}$ in the above system, we obtain the defining
ideal of $H$. Then Proposition B.2 yields the desired bound. $\Box$

###### Lemma B.9

Both ${\mathcal{F}}_{mt}({\rm GL}_{n}(C))$ and ${\mathcal{F}}_{imt}({\rm
GL}_{n}(C))$ are bounded by 1.

  * Proof.

Every maximal torus of ${\rm GL}_{n}(C)$ is conjugate to $(C^{*})^{n}$. Hence
it is equal to the intersection of ${\rm GL}_{n}(C)$ and a linear subspace of
${\rm Mat}_{n}(C)$. Consequently, ${\mathcal{F}}_{mt}({\rm GL}_{n}(C))$ is
bounded by 1. As the intersection of linear subspaces of ${\rm Mat}_{n}(C)$ is
still linear, any element of ${\mathcal{F}}_{imt}({\rm GL}_{n}(C))$ is the
intersection of ${\rm GL}_{n}(C)$ and a linear subspace of ${\rm Mat}_{n}(C)$.
So ${\mathcal{F}}_{imt}({\rm GL}_{n}(C))$ is also bounded by 1. $\Box$

###### Lemma B.10

Assume that $H$ is a connected subgroup of ${\rm GL}_{n}(C)$. Then $H^{t}$ is
generated by all unipotent elements of $H$.

  * Proof.

Since $H/H^{t}$ is a torus, there are no nontrivial unipotent elements in
$H/H^{t}$. Hence all unipotent elements of $H$ are in $H^{t}$. From Lemma 2.1
in [10], $H^{t}$ is generated by $(P,P)$ and $R_{u}(H)$ where $P$ is a Levi
factor of $H$ and $R_{u}(H)$ is the unipotent radical of $H$. Moreover $(P,P)$
is semi-simple, so it is generated by unipotent elements. Therefore $H^{t}$ is
generated by all unipotent elements of $H$. $\Box$

###  B.2 Main results

Let $J(n)$ be a Jordan bound, so that every finite subgroup of ${\rm
GL}_{n}(C)$ contains a normal abelian subgroup of index at most $J(n)$. In the
following, we will show the main results in this appdendix. Denote

$\kappa_{1}=\max_{i}\left\\{{{n^{2}+(2n^{3}+1)^{8^{n^{2}}}\choose
n^{2}}\choose
i}^{2}\right\\}\quad\mbox{and}\quad\kappa_{2}=\kappa_{1}(2n^{3}+1)^{8^{n^{2}}}{n^{2}+(2n^{3}+1)^{8^{n^{2}}}\choose
n^{2}}.$ (8)

###### Proposition B.11

There exists an integer $I(n)$ that is not greater than
$J\left(\max_{i}\left\\{{\kappa_{1}^{2}+1\choose i}\right\\}\right)$ and a
family ${\mathcal{F}}$ of subgroups of ${\rm GL}_{n}(C)$ bounded by

$\kappa_{3}\triangleq\kappa_{2}(\kappa_{1}^{2}+1)\max_{i}\left\\{{\kappa_{1}^{2}+1\choose
i}\right\\}$ (9)

with the following property. For every subgroup $H$ of ${\rm GL}_{n}(C)$,
there is $H^{\prime}\in{\mathcal{F}}$ such that

  * $(a)$

$H^{\circ}\leq H^{\prime}$.

  * $(b)$

$H$ normalizes $H^{\prime}$; so $H^{\prime}\unlhd HH^{\prime}\leq{\rm
GL}_{n}(C)$.

  * $(c)$

$[H:H\cap H^{\prime}]=[HH^{\prime}:H^{\prime}]\leq I(n)$.

  * $(d)$

Every unipotent element of $H^{\prime}$ lies in $H^{\circ}$.

We will show the proposition by separating three cases.

###### Lemma B.12

Proposition B.11 is true for finite groups with $I(n)=J(n)$ and
${\mathcal{F}}$ is bounded by 1.

  * Proof.

Assume that $H\subset{\rm GL}_{n}(C)$ is a finite group. Let $\bar{H}$ be a
normal abelian subgroup of $H$ with $[H:\bar{H}]\leq J(n)$. As a finite
abelian subgroup of ${\rm GL}_{n}(C)$ is diagonalizable, $\bar{H}$ is
contained in some maximal tori of ${\rm GL}_{n}(C)$. Let $H^{\prime}$ be the
intersection of maximal tori containing $\bar{H}$. Then
$H^{\prime}\in{\mathcal{F}}_{imt}({\rm GL}_{n}(C))$. Clearly, $H$ normalizes
$H^{\prime}$. Since $\bar{H}\subseteq H\cap H^{\prime}$, $[H:H^{\prime}\cap
H]\leq[H:\bar{H}]\leq J(n)$. The only unipotent element of $H^{\prime}$ is the
identity. So $(a)-(d)$ hold for $H,H^{\prime}$. The lemma follows from the
fact that ${\mathcal{F}}_{imt}({\rm GL}_{n}(C))$ is bounded by $1$. $\Box$

###### Lemma B.13

Assume that $H$ is a subgroup whose identity component is a torus. Then
Proposition B.11 is true for $H$ with
$I(n)=J\left(\max_{i}\left\\{{n^{2}+1\choose i}^{2}\right\\}\right)$ and
${\mathcal{F}}$ is bounded by

$(n^{2}+1)\max_{i}\left\\{{n^{2}+1\choose i}^{2}\right\\}.$

  * Proof.

Let $M=(H^{\circ})_{{\mathcal{F}}_{imt}({\rm GL}_{n}(C))}$ and $N=N_{{\rm
GL}_{n}(C)}(M)$. It is easy to verify that $H$ normalizes $M$ and thus
$H\subseteq N$. Since $M$ lies in the family ${\mathcal{F}}_{imt}({\rm
GL}_{n}(C))$ bounded by $1$, Lemma B.4 implies that $N$ lies in a family
${\mathcal{F}}_{ad}({\rm GL}_{n}(C))$ bounded by $n$. Let
$\tilde{n}=\max_{i}\\{{n^{2}+1\choose i}^{2}\\}$. By Proposition B.6, there is
a morphism

$\tau_{N,M}:N\longrightarrow{\rm GL}_{\tilde{n}}(C)$

satisfies that $\ker(\tau_{N,M})=M$ and $\tau_{N,M}$ is bounded by
$\tilde{n}(n^{2}+1)$. As $H^{\circ}\subseteq M$, $\tau_{N,M}(H)$ is a finite
subgroup of ${\rm GL}_{\tilde{n}}(C)$. From Lemma B.12, there is
$\tilde{M}\in{\mathcal{F}}_{imt}({\rm GL}_{\tilde{n}}(C))$ such that
$(a)$-$(c)$ hold for $\tau_{N,M}(H),\tilde{M}$ (with
$I(\tilde{n})=J(\tilde{n})$). Let
$H^{\prime}=\tau_{N,M}^{-1}(\tilde{M}\cap\tau_{N,M}(N))$. Note that
${\mathcal{F}}_{imt}({\rm GL}_{\tilde{n}}(C))$ is bounded by 1. By Lemma B.5,
$H^{\prime}$ is bounded by $\tilde{n}(n^{2}+1)$. We will show that the
$H^{\prime}$ satisfy $(a)$-$(d)$ with $I(n)=J(\tilde{n})$. It is clear that
$H^{\circ}\leq H^{\prime}$. For any $h\in H$, since $T_{M,N}(H)$ normalizes
$\tilde{M}$ and $\tau_{N,M}(N)$,

$\tau_{N,M}(hH^{\prime}h^{-1})=\tau_{N,M}(h)(\tilde{M}\cap\tau_{N,M}(N))\tau_{N,M}(h)^{-1}=\tilde{M}\cap\tau_{N,M}(N)=\tau_{N,M}(H^{\prime}).$

Therefore $hH^{\prime}h^{-1}\subseteq H^{\prime}$. This indicate that
$hH^{\prime}h^{-1}=H^{\prime}$ for any $h\in H$. In other words, $H$
normalizes $H^{\prime}$. This proves $(b)$. Since both $HH^{\prime}$ and
$H^{\prime}$ contain $M$,

$\displaystyle[HH^{\prime}:H^{\prime}]$
$\displaystyle=[\tau_{N,M}(HH^{\prime}):\tau_{N,M}(H^{\prime})]=[\tau_{N,M}(H)\tau_{N,M}(H^{\prime}):\tau_{N,M}(H^{\prime})]$
$\displaystyle=[\tau_{N,M}(H):\tau_{N,M}(H)\cap\tau_{N,M}(H^{\prime})]=[\tau_{N,M}(H):\tilde{M}\cap\tau_{N,M}(H)]\leq
J(\tilde{n}).$

This proves $(c)$. Suppose that $h^{\prime}$ is an unipotent element of
$H^{\prime}$. Then $\tau_{N,M}(h^{\prime})$ is an unipotent element of
$\tilde{M}$. However $\tilde{M}$ consists of semi-simple elements. Hence
$\tau_{N,M}(h^{\prime})=1$. Then $h^{\prime}\in M$. But $M$ is contained in a
torus, so $h^{\prime}=1$. This proves $(d)$. $\Box$

Now we are ready to prove Proposition B.11 for the general case.

  * Proof.

Let $U=(H^{\circ})^{t}$. By Lemma B.10, $U$ is generated by unipotent
elements. Then it follows from Lemma B.8 that $U$ is bounded by
$(2n^{3}+1)^{8^{n^{2}}}$. Let $N=N_{{\rm GL}_{n}(C)}(U)$. Lemma B.4 indicates
that $N$ lies in ${\mathcal{F}}_{ad}({\rm GL}_{n}(C))$ that is bounded by $n$.
Let $\kappa_{1}$ and $\kappa_{2}$ be as in (8). Using Proposition B.6 again,
there is a morphism

$\phi_{N,U}:N\longrightarrow{\rm GL}_{\kappa_{1}}(C)$

such that $\ker(\phi_{N,U})=U$ and $\phi_{N,U}$ is bounded by $\kappa_{2}$. We
first prove that $H\leq N$. For any $h\in H$ and any character $\chi$ of
$H^{\circ}$, $\chi(hXh^{-1})$ is a character of $H^{\circ}$. Hence for any
$u\in U$, $\chi(huh^{-1})=1$. So $huh^{-1}\in U$ for any $u\in U$. In other
words, $H$ normalizes $U$. So $H\leq N$. As $H^{\circ}/U$ is a torus,
$\phi_{N,U}(H)^{\circ}$ is a torus in ${\rm GL}_{\kappa_{1}}(C)$. Lemma B.13
implies that there is $M^{\prime}\leq{\rm GL}_{\kappa_{1}}(C)$ bounded by
$(\kappa_{1}^{2}+1)\max_{i}\left\\{{\kappa_{1}^{2}+1\choose i}^{2}\right\\}$
such that $(a)$-$(d)$ hold for $\phi_{N,U}(H),M^{\prime}$ with
$I(n)=J\left(\max_{i}\left\\{{\kappa_{1}^{2}+1\choose i}\right\\}\right)$. Let
$H^{\prime}=\phi^{-1}_{U}(M^{\prime}\cap\phi_{N,U}(N))$. Then by Lemma B.5,
$H^{\prime}$ is bounded by $\kappa_{3}$, where $\kappa_{3}$ is defined in (9).
The similar arguments as in the proof of Lemma B.13 implies $(a)$-$(c)$ hold
for $H,H^{\prime}$ with $I(n)=J\left(\max_{i}\left\\{{\kappa_{1}^{2}+1\choose
i}\right\\}\right)$. Now let us show that $(d)$ holds. Assume that $u$ is an
unipotent element of $H^{\prime}$. Then $\phi_{N,U}(u)$ is an unipotent
element of $M^{\prime}$. Since $M^{\prime}$ and $\phi_{N,U}(H)^{\circ}$
satisfy $(d)$, $\phi_{N,U}(u)\in\phi_{N,U}(H)^{\circ}$. Whereas
$\phi_{N,U}(H)^{\circ}$ is a torus, $\phi_{N,U}(u)=1$. Thus $u\in U\subseteq
H^{\circ}$. $\Box$

###### Proposition B.14

Let $I(n)$ and $\kappa_{3}$ be as in Proposition B.11. Then there exists a
family $\tilde{{\mathcal{F}}}$ of subgroups of ${\rm GL}_{n}(C)$ bounded by

$\tilde{d}\triangleq(\kappa_{3})^{I(n)-1}$

with the following property. For any subgroup $H$ of ${\rm GL}_{n}(C)$, there
exists $\tilde{H}\in\tilde{{\mathcal{F}}}$ such that $H\leq\tilde{H}$, and
every unipotent element of $\tilde{H}$ lies in $H^{\circ}$.

  * Proof.

Let ${\mathcal{F}}$ be as in Proposition B.11 and

$\tilde{{\mathcal{F}}}=\\{\bar{H}\,\,|\,\,\exists\,\,M\in{\mathcal{F}},M\unlhd\bar{H},[\bar{H}:M]\leq
I(n)\\}.$

Every element of $\tilde{{\mathcal{F}}}$ is the union of at most $I(n)$ cosets
of some element in ${\mathcal{F}}$. It is well-known that the union of two
varieties is defined by the product of their corresponding defining
polynomials. Hence $\tilde{{\mathcal{F}}}$ is bounded by $\tilde{d}$. Assume
that $H$ is a subgroup of ${\rm GL}_{n}(C)$. Let $H^{\prime}$ be an element in
${\mathcal{F}}$ such that $(a)$-$(d)$ in Proposition B.11 hold for
$H,H^{\prime}$. Let $\tilde{H}=HH^{\prime}$. Then
$\tilde{H}\in\tilde{{\mathcal{F}}}$ by Proposition B.11 (c). The unipotent
elements of $\tilde{H}$ lie in $\tilde{H}^{\circ}$ and then in
$(H^{\prime})^{\circ}$. As the unipotent elements of $H^{\prime}$ lie in
$H^{\circ}$, so do the unipotent elements of $\tilde{H}$. $\Box$

###### Corollary B.15

Let $\tilde{{\mathcal{F}}}$ be the family as in Proposition B.14. Then for any
subgroup $H$ of ${\rm GL}_{n}(k)$, there is
$\tilde{H}\in\tilde{{\mathcal{F}}}$ such that

$(\tilde{H}^{\circ})^{t}\unlhd H^{\circ}\leq H\leq\tilde{H}.$

  * Proof.

By Proposition B.14, there is $\tilde{H}\in\tilde{{\mathcal{F}}}$ such that
$H\leq\tilde{H}$ and the unipotent elements of $\tilde{H}$ lie in $H^{\circ}$.
Then the corollary follows from Lemma B.10 and the fact that
$(\tilde{H}^{\circ})^{t}$ is normal in $\tilde{H}^{\circ}$. $\Box$

In the following, $H$ is assumed to be connected. Proposition B.6 allows us to
bound the degrees of generators of $X(H)$. $X(H)$ can be viewed as a subset of
$C[H]$, the coordinate ring of $H$. The morphism $\varphi:H\rightarrow
H^{\prime}$ induces a group homomorphism
$\varphi^{\circ}:X(H^{\prime})\rightarrow X(H)$.

###### Proposition B.16

Let $\kappa_{2}$ be as in (8). Then there are generators of $X(H)$, which are
represented by polynomials bounded by $\kappa_{2}$.

  * Proof.

From Lemmas B.10 and B.8, $H^{t}$ is bounded by $(2n^{3}+1)^{8^{n^{2}}}$. By
Proposition B.6, there is a morphism $\tau_{H,H^{t}}:H\rightarrow{\rm
GL}_{\kappa_{1}}(C)$ satisfying that $\ker(\tau_{H,H^{t}})=H^{t}$ and
$\tau_{H,H^{t}}$ is bounded by $\kappa_{2}$, where $\kappa_{1}$ is as in (8).
$\tau_{H,H^{t}}$ is of the from

$\left(\frac{P^{H,H^{t}}_{i,j}(X)}{Q^{H,H^{t}}(X)}\right)\quad\mbox{where}\,\,\deg(P^{H,H^{t}}_{i,j}(X))\leq\kappa_{2},\,\,\deg(Q^{H,H^{t}}(X))\leq\kappa_{2}.$

From the proof of Proposition B.6, $Q^{H,H^{t}}(I_{n})=1$ and for any
$h,h^{\prime}\in H$,

$Q^{H,H^{t}}(hh^{\prime})=\det([hh^{\prime}])=\det([h][h^{\prime}])=\det([h])\det([h^{\prime}])=Q^{H,H^{t}}(h)Q^{H,H^{t}}(h^{\prime}).$

It implies that $Q^{H,H^{t}}(X)\in X(H)$. Notice that
$X((C^{*})^{\kappa_{1}})$ is generated by the characters
$y_{1},\cdots,y_{\kappa_{1}}$ and so is the group of characters of any its
subgroup. Since $\tau_{H,H^{t}}(H)$ is a torus in ${\rm GL}_{\kappa_{1}}(C)$,
it is conjugate to a subgroup of $(C^{*})^{\kappa_{1}}$. So
$X(\tau_{H,H^{t}}(H))$ is generated by some linear polynomials.
$\tau_{H,H^{t}}$ induces a group homomorphism:

$\displaystyle\tau_{H,H^{t}}^{\circ}:X(\tau_{H,H^{t}}(H))$
$\displaystyle\rightarrow X(H)$ $\displaystyle\chi^{\prime}$
$\displaystyle\rightarrow\chi^{\prime}\circ\tau_{H,H^{t}}$

For any $\chi\in X(H)$ and $h\in H$, since $\chi(hh^{\prime})=\chi(h)$ for all
$h^{\prime}\in H^{t}$, there is $g\in C[\tau_{H,H^{t}}(H)]$ such that
$g\circ\tau_{H,H^{t}}=\chi$. One can verify that $g$ is actually a character
of $\tau_{H,H^{t}}(H)$. Therefore $\tau_{H,H^{t}}^{\circ}$ is surjective. Let
$L_{1},\cdots,L_{s}$ be linear polynomials, which generate
$X(\tau_{H,H^{t}}(H))$. Then
$L_{1}\circ\tau_{H,H^{t}},\cdots,L_{s}\circ\tau_{H,H^{t}}$ generate $X(H)$.
Since $Q^{H,H^{t}}(X)\in X(H)$,

$Q^{H,H^{t}}(X),(L_{1}\circ\tau_{H,H^{t}})Q^{H,H^{t}}(X),\cdots,(L_{s}\circ\tau_{H,H^{t}})Q^{H,H^{t}}(X)$

still generate $X(H)$ and are polynomials bounded by $\kappa_{2}$. $\Box$

Let $P_{1}(X),\cdots,P_{l}(X)$ be in
$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq\kappa_{2}}$ such that their images
constitute a $C$-basis of
$C[x_{1,1},x_{1,2},\cdots,x_{n,n}]_{\leq\kappa_{2}}/(I(H))_{\leq\kappa_{2}}$,
where $I(H)$ is the set of polynomials in $C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$
that vanishes on $H$. Let $c_{1},\cdots,c_{l}$ be indeterminates and
$P_{\mathbf{c}}(X)=\sum_{i=1}^{l}c_{i}P_{i}(X)$, where
${\mathbf{c}}=(c_{1},\cdots,c_{l})$. Then the conditions

$P_{\mathbf{c}}(I_{n})=1\,\,\mbox{and}\,\,\forall\,\,h,h^{\prime}\in
H,\,\,P_{\mathbf{c}}(h)P_{\mathbf{c}}(h^{\prime})-P_{\mathbf{c}}(hh^{\prime})=0$

induce a system of algebraic equations $J$ for ${\mathbf{c}}$. Moreover, we
have the following proposition.

###### Proposition B.17

$\dim(J)=0$ and for each zero $\bar{{\mathbf{c}}}$ of $J$ in $C^{l}$,
$P_{\bar{{\mathbf{c}}}}(X)$ is a character of $H$.

  * Proof.

Evidently, for each $\bar{{\mathbf{c}}}\in{\rm Zero}(J)\cap C^{l}$,
$P_{\bar{{\mathbf{c}}}}(X)$ is a morphism from $H$ to $C^{*}$ and thus a
character of $H$. Suppose that
$\bar{{\mathbf{c}}},\bar{{\mathbf{c}}}^{\prime}\in{\rm Zero}(J)\cap C^{l}$ and
$P_{\bar{{\mathbf{c}}}}(h)=P_{\bar{{\mathbf{c}}}^{\prime}}(h)$ for all $h\in
H$. Then it implies that
$P_{\bar{{\mathbf{c}}}}(X)-P_{\bar{{\mathbf{c}}}^{\prime}}(X)\in(I(H))_{\leq\kappa_{2}}$.
Hence

$\sum_{i=1}^{l}(\bar{c}_{i}-\bar{c}_{i}^{\prime})P_{i}(X)\equiv
0\mod(I(H))_{\kappa_{2}}$

where $\bar{{\mathbf{c}}}=(\bar{c_{1}},\cdots,\bar{c}_{l})$ and
$\bar{{\mathbf{c}}}^{\prime}=(\bar{c_{1}}^{\prime},\cdots,\bar{c}_{l}^{\prime})$.
Since $P_{1}(X),\cdots,P_{l}(X)$ modulo $(I(H))_{\kappa_{2}}$ are linearly
independent over $C$. So $\bar{{\mathbf{c}}}=\bar{{\mathbf{c}}}^{\prime}$.
That is to say, the map $\varphi:{\rm Zero}(J)\cap C^{l}\rightarrow X(H)$
defined by $\varphi(\bar{{\mathbf{c}}})=P_{\bar{{\mathbf{c}}}}(X)$ is
injective. Now assume that $\dim(J)>0$. Then ${\rm Zero}(J)\cap C^{l}$ is an
uncountable set and so is $X(H)$. However, it is known that $X(H)$ is a
countable set. This contradiction concludes the proposition. $\Box$

###### Remark B.18

Given a connect subgroup $H$ of ${\rm GL}_{n}(C)$, Propositions B.16 and B.17
allow us to compute a set of generators of $X(H)$ that are represented by
polynomials in $C[x_{1,1},x_{1,2},\cdots,x_{n,n}]$.

## References

  * [1] P.D. Bertrand and F. Beukers, Équations Différentielles Linéaires et Majorations de Multiplicités, Ann.Scient. éc. Norm. Sup., 4(18), 181-192, 1985.
  * [2] Elie Compoint and Michael F. Singer, Computing Galois groups of completely reducible differential equations, J. Symbolic Comput., 11,1-22,1998.
  * [3] J.H. Davenport and Michael F. Singer, Elementary and Liouvillian solutions of linear differential equations, J. Symbolic Comput., 2, 237-260, 1986.
  * [4] Thomas W. Dube, The Structure of polynomial ideals and Gröbner bases, SIAM J. Comput., 19(4), 750 C773, 1990.
  * [5] James E. Humphreys, Linear Algebraic Groups, Springer-Verlag New York, 1981.
  * [6] Ehud Hrushovski, Computing the Galois group of a linear differential equation, Banach Center Publications, 58, 97-138, 2002.
  * [7] Jerald J. Kovacic, An algorithm for solving second order linear homogeneous differential equations. J. Symbolic Comput. 2(1), 3 C43, 1986.
  * [8] Andy R. Magid, Lectures on Differential Galois Theory, University Lecture Series v.7, American Mathematical Society, 1994.
  * [9] A. Seidenberg, Constructions in algebra, Trans. AMS, 197, 273-313, 1974.
  * [10] Micael F. Singer, Moduli of linear differential equations on the Riemann sphere with fixed Galois groups, Pacific Journal of Mathematics, 160(2), 343-395, 1993.
  * [11] Michael F. Singer, Introduction to the Galois theory of linear differential equations, Algebraic Theory of Differential Equations, M.A.H. MacCallum and A.V. Mikhalov, eds., London Mathematical Society Lecture Note Series (no. 357), Cambridge University Press, 1-82, 2009.
  * [12] Michael F. Singer and F. Ulmer, Galois groups of second and third order linear differential equations, J. Symbolic Comput., 16, 9 - 36, 1993.
  * [13] L. van den Dries and K. Schmidt, Bounds in the theory of polynomial rings over fields. A nonstandard approach, Inventiones Mathematicae, 76, 77-91, 1984.
  * [14] Mark van Hoeij and Jacques-Arthur Weil, An algoirthm for computing invariants of differential Galois groups, J. Pure Appl. Algebra, 117/118, 353-379,1997.
  * [15] Marius van der Put, Galois theory and algorithms for linear differential equations, J. Symbolic Comput., 39, 451 C463, 2005.
  * [16] Marius van der Put and Michael F. Singer, Galois Theory of Linear Differential Equations, Springer-Verlag, Berlin Heidelberg, 2003.