Theorem 3.1.1.
The Noether Degree Bound claims a ring of invariants is generated in degrees \(\leq |G|\) giving,
\begin{equation*}
R^G = \mathbb{K} [ R_G(\bar x^{\bar \beta}) | \; |\bar \beta| \leq |G|].
\end{equation*}
Chapter 3 Degree Bounds and Algorithms
Section 3.1
Our goal is to find algorithms that provide us with a description of all possible invariants in an efficient way. Formally, we look for minimal generators for the ring of invariants \(R^G\) and more precisely for minimal algebra generators for \(R^G\) as an algebra over the coefficient field \(\mathbb{K}\text{.}\)
For our search to be successful, we need to hope that there are finitely many generators. In our setup (finite groups and characteristic zero) a consequence of Hilbert’s Basis Theorem is that our invariant rings are finitely generated. However, we will run in computational troubles if we do not have a stopping point for our search. The most effective way is to provide a bound the degrees of these generators.
Subsection 3.1.1 Noether Degree Bound
A beautiful theorem of Noether establishes that we have a bound on the degree of a minimal generator independent from the action itself, but just in terms of the order of the group. Moreover, we only need to look at images of monomials under the Reynolds operator.
Noether’s result is a constructive tool that provides us with a computational strategy! We can apply \(R_G\) to all the finitely many monomials in degrees \(\leq |G|\) to get generators for \(R^G\text{.}\) As the number of monomials grows exponentially with the number of variables and the degree, this is more of a theoretical algorithm, but it does tell us that our goal is at least possible!
Subsection 3.1.2 Hilbert Ideal
To describe a more sophisticated approach to the search for minimal algebra generators for an invariant ring, we can actually consider an ideal instead! Note: for any \(\{ f_1,..., f_s\} \subseteq R\text{,}\) the ideal generatd by \(\{f_1,...f_s\}\) and the subalgebra generated by \(\{f_1,...f_s\}\) over \(\mathbb{K}\) are very different objects.
Definition 3.1.2.
Let \(J_G := R(R^G)_+\) be the ideal in \(R\) generated by all positive degree invariants. We call \(J_G\) the Hilbert Ideal for this action of \(G\text{.}\)
Theorem 3.1.3.
Let \(J_G \) be the Hilbert ideal in \(R\) for the action of \(G\text{.}\) If \(J_G = (f_1,...,f_s)\) and every \(f_i\) is invariant so \(f_i\in R^G, \,\, \forall i\text{,}\) then \(R^G = \mathbb{K}[f_1,...f_s]\)
Note that the condition that every generator is invariant is not hard to satisfy as if you have a generator that is not invariant, then you can apply the Reynolds operator \(R^G\) to obtain a new generator that is. You can now replace the old generator with this new one and still get the same ideal. What is special here is that a set of ideal generators work as algebra generators! Computationally, algebra generators are much harder to find as there is no guarantee to have finitely many of them. However, the Hilbert Basis Theorem tells us that every ideal is finitely generated.
Subsection 3.1.3 Presentations
When we say that \(\{f_1,...f_s\} \subseteq R\) are minimal generators for a subring \(S\text{,}\) we do not exclude the possibility that there is some relation, some polynomial identity, that they satisfy as elements in the bigger ring \(R\text{.}\) We can describe the relations between the generators via a presentation of the subring.
Definition 3.1.4.
Let \(S = \mathbb{K}[f_1,...f_s] \subset R\text{.}\) A presentation of \(S\) is a map,
\begin{equation*}
T=: \mathbb{K}[u_1,...u_s] \xrightarrow{\phi}S
\end{equation*}
such that \(\frac{T}{\text{ker}(\phi)} \cong S\text{.}\) We call the elements of the presentation ideal \(\text{ker}(\phi)\) the syzygies of \(f_i\)’s.
Algorithms for finding generators for ideals have been intensely studied and especially in relation with the theory of Groebener bases. We cannot go in the details of these tools, but what is of notice is that they are implemented in Macaulay2 and so we can rely on them in our implementation. In particular, these methods are particularly effective in solving problems in Elimnination Theory. Often the goal is to compute an ideal of relations hoping that this is less complicated than the original structure, possibly elimnating some variables.
Proposition 3.1.5.
(Elimination Theory): In \(S \otimes \mathbb{K}[u_1,...,u_s] = \mathbb{K}[x_1,...,x_n,u_1,...u_s]\) consider the ideal,
\begin{equation*}
I = (u_i - f_x(\bar x) | \, \left\langle f_i\right\rangle = S
\end{equation*}
Then,
\begin{equation*}
\text{ker} (\phi)= I \cap \mathbb{K}[u_1,...,u_s]
\end{equation*}
Algorithm 3.1.6.
Compute a Groebner Basis \(G\) for \(I\) with elimination order for the \(x\)’s. Then, \(G \cap \mathbb{K}[y_1,...y_s]\) is the Groebner Basis for \(ker \phi\)
Subsection 3.1.4 Graph of Linear Actions
We can use Elimination Theory to solve our original problem of finding minimal generators for the ring of invariants. We first need to construct a geometric description of the action of a group \(G\text{.}\)
Definition 3.1.7.
Let \(G\) be a finite matrix group in \(GL_n(\mathbb{K})\text{.}\) For \(A\in G\) consider,
\begin{equation*}
V_A = \left\{ ( \bar v, A \bar v) \mid ,v \in V \right \} \subseteq V \oplus V
\end{equation*}
Then \(A_G = \cup_{A\in G}V_A\) is the subspace arrangement associated to the action of G.
Note that \(V_A\) is a linear subspace. So \(\mathbb{I}(V_A)\text{,}\) the set of polynomials vanishing on \(V_A\text{,}\) is an ideal generated by linear polynomials, we call this a linear ideal.
Example 3.1.8.
Consider
\begin{equation*}
V_{\begin{pmatrix}
1 \amp 0 \\
0 \amp -1 \\
\end{pmatrix}} = \{(x_1,x_2,x_1,-x_2) \mid x_1, x_2 \in V\} = \mathbb{V}(y_1-x_1, y_2+x_2)
\end{equation*}
Subsection 3.1.5 Subspace Arrangement Approach
The finite union of the subspaces \(V_A\text{,}\) denoted \(\mathcal{A}\) is a subspace arrangement, called the group action arrangement. Via Elimination Theory, we can use the vanishing ideal of \(\mathcal{A}\) to recover the Hilbert Ideal.
Theorem 3.1.9.
(Derksen): Let \(I_G = \mathbb{I}(A_G) = \cap_{A\in G}\mathbb{I}(V_A) \subseteq \mathbb{K}[x_1,...x_n,y_1,...y_n].\) Then
\begin{equation*}
(I_G +(y_1,...,y_n)) \cap \R = J_G.
\end{equation*}
Recent work has shown that the same approach works in the exterior algebra.
Theorem 3.1.10.
(Gandini) Let \(I_G^{'} = \cap_{A\in G} \mathbb{I}(V_A) \subseteq \Lambda(\bar x, \bar y)\text{.}\) Then
\begin{equation*}
(I_G^{'} +(y_1,...y_n)) \cap \Lambda(x_1,...,x_n) = J_G^{'} : = \Lambda(\bar x)(\Lambda(\bar x)^G)_+
\end{equation*}
The exterior algebra approach has computational potential. Whilst Derken’s approach leads to an algorithm with a long run time, first experiments suggest that a fast algorithm could be implemented for skew polynomials. We aim to pursue this line of inquiry in the near future.
Section 3.2 Specialized algorithms
For some specific types of actions we have faster and simpler algorithms to find invariants.
Subsection 3.2.1 Abelian Groups and Weight Matrices
Every abelian group \(G\) can be written in its invariant factors decomposition as
\begin{equation*}
G \cong \mathbb{Z}_{d_1} \oplus....\oplus \mathbb{Z}_{d_r},
\end{equation*}
for some unique \(d_i\) such that \(d_i \mid d_{1+1}\) where \(i=1, \ldots , r-1\text{.}\) In multiplicative notation,
\begin{equation*}
G \cong \left\langle g_1\right\rangle \oplus...\oplus\left\langle g_r \right\rangle, \,\,\,\,\, |g_i| =d_i.
\end{equation*}
A diagonal action of \(G\) on \(R= \mathbb{K}[\bar x]\) is given by
\begin{equation*}
g_i \cdot x_j = \mu_i^{w_ij}x_j
\end{equation*}
for \(\mu_i \) a primitive \(d_i^{th}\) root of unity. We can encod the action in the weight matrix
\begin{equation*}
W = (w_{ij})_{ij} =
\begin{pmatrix}
\mu_{11} \amp \cdots \amp \mu_{1n} \\
\vdots \amp \ddots \amp \\
\mu_{r1} \amp \cdots \amp \mu_{rn}
\end{pmatrix}
\end{equation*}
where the rows are indexed by the generators \(g_i\) of \(G\) and the columns are indexed by the variables \(x_j\) of \(R\text{.}\)
Theorem 3.2.1.
A monomial is invariant under the action of \(G\) if an only if its exponent vector is in the kernel of the weigtht matrix \(W \text{.}\) In symbols,
\begin{equation*}
\bar x^{\bar \beta} \in R^G \iff W \bar \beta \cong (0,...,0),
\end{equation*}
where the entry in position \(i\) is computed modulo \(d_i\text{.}\)
Interpreting each row has the weight of the action of the generator \(g_i\text{,}\) we have that \(g_i\) acts trivially on the monomial \(\bar x^{\bar \beta}\) precisely when
\begin{equation*}
\mu_i^{\sum_j w_{ij} \beta_j} = 1
\end{equation*}
so \((W \bar \beta)_i =0\) modulo \(d_i\) as \(\mu_i\) is a primitve \(d_i^{th}\) root of unity.
We can use this result computationally. As the action is diagonal, the invariant ring is generated by monomials. By Noether Degree Bound we only need to examine all monomials of degree less than the order of the group \(G\text{.}\) Then, by the theorem above, if we can sort the monomials in terms of their weigtht \(W\bar \beta\text{,}\) then the monomials with weight \(\bar 0\) will be invariant.
