Invariants of Finite Groups

Invariants of Finite Groups

In this section, with notation as in the introduction to this chapter, $G$ will be a finite group.

Note

The ssumption that $G$ is finite implies:

By a result of Emmy Noether, $K[V]$ is integral over $K[V]^G$. In particular,
$\; \; \; \; \; \dim K[V]^G = \dim K[V] = n.$
Moreover, $K[V]^G$ is finitely generated as a $K$-algebra.

If the group order $|G|$ is invertible in $K$, then we have the explicit Reynolds operator
$\; \; \; \; \; \mathcal R: K[V] \to K[V], f\mapsto \frac{1}{|G|}\sum_{\pi\in G}(f \;\! . \;\! \pi).$

Note

We speak of non-modular invariant theory if $|G|$ is invertible in $K$, and of modular invariant theory otherwise.

Note

In the non-modular case, using Emmy Noether's result and the Reynolds operator, it is not too difficult to show that $K[V]^G$ is a free module over any of its graded Noether normalizations. That is, $K[V]^G$ is Cohen-Macaulay. In the modular case, $K[V]^G$ may not be Cohen-Macaulay.

Note

In the non-modular case, the Hilbert series of $K[V]^G$ can be precomputed as its Molien series. See Harm Derksen, Gregor Kemper (2015) and Wolfram Decker, Theo de Jong (1998) for explicit formulas.

Knowing the Hilbert series means to know the dimension of each graded piece $K[V]^G_d$. This information can often be used to speed up algorithms for finding invariants. The most basic task here is to compute the invariants of some given degree $d$, that is, to find an explicit $K$-basis of $K[V]^G_d$. There are two different approaches:

The Reynolds Operator Method, available in the non-modular case, applies the Reynolds operator to sufficiently many monomials in $K[x_1, \dots, x_n]_d\cong K[V]_d$, and extracts a $K$-basis from the resulting generating set.
The Linear Algebra Method, available in the non-modular and the modular case, finds the elements of a $K$-basis all at once by setting up and solving an appropriate $K$-linear system of equations.

These methods are, in particular, crucial to the computation of primary and secondary invariants. Primary invariants and irreducible secondary invariants together generate $K[V]^G$ as a $K$-algebra. Omitting redundant generators yields a system of fundamental invariants. In the non-modular case, an alternative and typically more effective way to compute generators of $K[V]^G$ is King's algorithm which finds a system of fundamental invariants directly, without computing primary and secondary invariants. See Simon King (2013).

We discuss the relevant OSCAR functionality below.

Creating Invariant Rings

How Groups are Given

The invariant theory part of OSCAR distinguishes two ways of how finite groups and their actions on $K[x_1, \dots, x_n]\cong K[V]$ are specified:

Matrix Groups

Here, $G$ will be explicitly given as a matrix group $G\subset \text{GL}_n(K)\cong \text{GL}(V) $ by (finitely many) generating matrices, acting on $K[x_1, \dots, x_n]\cong K[V]$ by linear substitution:

\[(f \;\! . \;\! \pi) (x_1, \dots, x_n) = f((x_1, \dots, x_n) \cdot \rho(\pi)) \text{ for all } \pi\in G.\]

Permutation Groups

Here, $G$ will be given as a permutation group, acting on $K[x_1, \dots, x_n]\cong K[V]$ by permuting the variables.

Constructors for Invariant Rings

invariant_ring — Method

invariant_ring(G::MatrixGroup)
invariant_ring(K::Field = QQ, G::PermGroup)

Return the invariant ring of the finite matrix group or permutation group G.

In the latter case, use the specified field K as the coefficient field. The default value for K is QQ.

Note

The creation of invariant rings is lazy in the sense that no explicit computations are done until specifically invoked (for example, by the primary_invariants function).

Examples

julia> K, a = CyclotomicField(3, "a");

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0]);

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1]);

julia> G = MatrixGroup(3, K, [M1, M2]);

julia> IRm = invariant_ring(G)
Invariant ring of
Matrix group of degree 3 over Cyclotomic field of order 3
with generators
AbstractAlgebra.Generic.MatSpaceElem{nf_elem}[[0 0 1; 1 0 0; 0 1 0], [1 0 0; 0 a 0; 0 0 -a-1]]

julia> IRp = invariant_ring(symmetric_group(3))
Invariant ring of
Sym( [ 1 .. 3 ] )
with generators
PermGroupElem[(1,2,3), (1,2)]

julia> coefficient_ring(IRp)
Rational Field

source

Basic Data Associated to Invariant Rings

If IR is the invariant ring $K[x_1,..., x_n]^G$ of a finite matrix group $G$, then

group(IR) refers to $G$,
coefficient_ring(IR) to $K$, and
polynomial_ring(IR) to $K[x_1,..., x_n]$.

Moreover, is_modular(IR) returns true in the modular case, and false otherwise.

Examples

julia> K, a = CyclotomicField(3, "a")(Cyclotomic field of order 3, a)
julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0])[0   0   1]
[1   0   0]
[0   1   0]
julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1])[1   0        0]
[0   a        0]
[0   0   -a - 1]
julia> G = MatrixGroup(3, K, [ M1, M2 ])Matrix group of degree 3 over Cyclotomic field of order 3
julia> IR = invariant_ring(G)Invariant ring of
Matrix group of degree 3 over Cyclotomic field of order 3
with generators
AbstractAlgebra.Generic.MatSpaceElem{nf_elem}[[0 0 1; 1 0 0; 0 1 0], [1 0 0; 0 a 0; 0 0 -a-1]]
julia> group(IR)Matrix group of degree 3 over Cyclotomic field of order 3
julia> coefficient_ring(IR)Cyclotomic field of order 3
julia> R = polynomial_ring(IR)Multivariate Polynomial Ring in x[1], x[2], x[3] over Cyclotomic field of order 3 graded by
  x[1] -> [1]
  x[2] -> [1]
  x[3] -> [1]
julia> x = gens(R)3-element Vector{MPolyElem_dec{nf_elem, AbstractAlgebra.Generic.MPoly{nf_elem}}}:
 x[1]
 x[2]
 x[3]
julia> is_modular(IR)false

The Reynolds Operator

reynolds_operator — Method

 reynolds_operator(IR::InvRing{FldT, GrpT, T}, f::T) where {FldT, GrpT, T <: MPolyElem}

In the non-modular case, return the image of f under the Reynolds operator projecting onto IR.

Examples

julia> K, a = CyclotomicField(3, "a")
(Cyclotomic field of order 3, a)

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0])
[0   0   1]
[1   0   0]
[0   1   0]

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1])
[1   0        0]
[0   a        0]
[0   0   -a - 1]

julia> G = MatrixGroup(3, K, [ M1, M2 ])
Matrix group of degree 3 over Cyclotomic field of order 3

julia> IR = invariant_ring(G)
Invariant ring of
Matrix group of degree 3 over Cyclotomic field of order 3
with generators
AbstractAlgebra.Generic.MatSpaceElem{nf_elem}[[0 0 1; 1 0 0; 0 1 0], [1 0 0; 0 a 0; 0 0 -a-1]]

julia> R = polynomial_ring(IR)
Multivariate Polynomial Ring in x[1], x[2], x[3] over Cyclotomic field of order 3 graded by
  x[1] -> [1]
  x[2] -> [1]
  x[3] -> [1]

julia> x = gens(R)
3-element Vector{MPolyElem_dec{nf_elem, AbstractAlgebra.Generic.MPoly{nf_elem}}}:
 x[1]
 x[2]
 x[3]

julia> f = x[1]^3
x[1]^3

julia> reynolds_operator(IR, f)
1//3*x[1]^3 + 1//3*x[2]^3 + 1//3*x[3]^3

julia> M = matrix(GF(3), [0 1 0; -1 0 0; 0 0 -1])
[0   1   0]
[2   0   0]
[0   0   2]

julia> G = MatrixGroup(3, GF(3), [M])
Matrix group of degree 3 over Galois field with characteristic 3

julia> IR = invariant_ring(G)
Invariant ring of
Matrix group of degree 3 over Galois field with characteristic 3
with generators
gfp_mat[[0 1 0; 2 0 0; 0 0 2]]

julia> R = polynomial_ring(IR)
Multivariate Polynomial Ring in x[1], x[2], x[3] over Galois field with characteristic 3 graded by
  x[1] -> [1]
  x[2] -> [1]
  x[3] -> [1]

julia> x = gens(R)
3-element Vector{MPolyElem_dec{gfp_elem, gfp_mpoly}}:
 x[1]
 x[2]
 x[3]

julia> f = x[1]^2
x[1]^2

julia> reynolds_operator(IR, f)
2*x[1]^2 + 2*x[2]^2

julia> f = x[1]^3
x[1]^3

julia> reynolds_operator(IR, f)
0

source

Invariants of a Given Degree

basis — Function

 basis(IR::InvRing, d::Int, algo::Symbol = :default)

Given an invariant ring IR and an integer d, return a basis for the invariants in degree d.

The optional argument algo specifies the algorithm to be used. If algo = :reynolds, the Reynolds operator is utilized (this method is only available in the non-modular case). Setting algo = :linear_algebra means that plain linear algebra is used. The default option algo = :default asks to select the heuristically best algorithm.

The Molien Series

molien_series — Method

molien_series([S::PolyRing], I::InvRing)

In the non-modular case, return the Molien series of I as a rational function.

If a univariate polynomial ring with rational coefficients is specified by the optional argument S::PolyRing, then return the Molien series as an element of the fraction field of that ring.

Examples

julia> K, a = CyclotomicField(3, "a");

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0]);

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1]);

julia> G = MatrixGroup(3, K, [M1, M2]);

julia> IR = invariant_ring(G);

julia> MS = molien_series(IR)
(-t^6 + t^3 - 1)//(t^9 - 3*t^6 + 3*t^3 - 1)

julia> parent(MS)
Fraction field of Univariate Polynomial Ring in t over Rational Field

source

Primary Invariants

primary_invariants — Method

primary_invariants(IR::InvRing;
  ensure_minimality::Int = 0, degree_bound::Int = 1,
  primary_degrees::Vector{Int} = Int[])

Return a system of primary invariants for IR as a Vector sorted by increasing degree. The result is cached, so calling this function again with argument IR will be fast and give the same result.

The primary invariants are computed using the algorithm in Gregor Kemper (1999).

The product of the degrees $d_1,\dots, d_n$ of the returned primary invariants is guaranteed to be minimal among all possible sets of primary invariants.

Expert users (or users happy to experiment) may enter the following keyword arguments to speed up the computation. Note that all of these options are ignored if there are already primary invariants cached. If admissible degrees $d_1,\dots, d_n$ for a system of primary invariants are known a priori, these degrees can be specified by primary_degrees = [d_1, ..., d_n]. Note that an error is raised if in fact no primary invariants of the given degrees exist. An a priori known number $k \geq 1$ with $d_1\cdots d_n \geq k \cdot |G|$, where $G$ is the underlying group, can be specified by degree_bound = k. The default value is degree_bound = 1. In some situations, the runtime of the algorithm might be improved by assigning a positive integer to ensure_minimality. This leads to an early cancellation of loops in the algorithm and the described minimality of the degrees is not guaranteed anymore. A smaller (positive) value of ensure_minimality corresponds to an earlier cancellation. However, the default value ensure_minimality = 0 corresponds to no cancellation.

Examples

julia> K, a = CyclotomicField(3, "a");

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0]);

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1]);

julia> G = MatrixGroup(3, K, [M1, M2]);

julia> IR = invariant_ring(G);

julia> primary_invariants(IR)
3-element Vector{MPolyElem_dec{nf_elem, AbstractAlgebra.Generic.MPoly{nf_elem}}}:
 x[1]*x[2]*x[3]
 x[1]^3 + x[2]^3 + x[3]^3
 x[1]^3*x[2]^3 + x[1]^3*x[3]^3 + x[2]^3*x[3]^3

julia> IR = invariant_ring(G); # "New" ring to avoid caching

julia> primary_invariants(IR, primary_degrees = [ 3, 6, 6 ])
3-element Vector{MPolyElem_dec{nf_elem, AbstractAlgebra.Generic.MPoly{nf_elem}}}:
 x[1]*x[2]*x[3]
 x[1]^3*x[2]^3 + x[1]^3*x[3]^3 + x[2]^3*x[3]^3
 x[1]^6 + x[2]^6 + x[3]^6

source

Secondary Invariants

secondary_invariants — Method

secondary_invariants(IR::InvRing)

Return a system of secondary invariants for IR as a Vector sorted by increasing degree. The result is cached, so calling this function again with argument IR will be fast and give the same result. Note that the secondary invariants are defined with respect to the currently cached system of primary invariants for IR (if no system of primary invariants for IR is cached, such a system is computed and cached first).

Implemented Algorithms

For the non-modular case, the function relies on Algorithm 3.7.2 in Harm Derksen, Gregor Kemper (2015), enhanced by ideas from Simon King (2007). In the modular case, Algorithm 3.7.5 in Harm Derksen, Gregor Kemper (2015) is used.

Examples

julia> K, a = CyclotomicField(3, "a");

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0]);

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1]);

julia> G = MatrixGroup(3, K, [M1, M2]);

julia> IR = invariant_ring(G);

julia> secondary_invariants(IR)
2-element Vector{MPolyElem_dec{nf_elem, AbstractAlgebra.Generic.MPoly{nf_elem}}}:
 1
 x[1]^3*x[2]^6 + x[1]^6*x[3]^3 + x[2]^3*x[3]^6

source

irreducible_secondary_invariants — Method

irreducible_secondary_invariants(IR::InvRing)

Return a system of irreducible secondary invariants for IR as a Vector sorted by increasing degree. The result is cached, so calling this function again will be fast and give the same result. Here, a secondary invariant is called irreducible, if it cannot be written as a polynomial expression in the primary invariants and the other secondary invariants.

Note that the secondary invariants and hence the irreducible secondary invariants are defined with respect to the currently cached system of primary invariants for IR (if no system of primary invariants for IR is cached, such a system is computed and cached first).

Examples

julia> M = matrix(QQ, [0 -1 0 0 0; 1 -1 0 0 0; 0 0 0 0 1; 0 0 1 0 0; 0 0 0 1 0]);

julia> G = MatrixGroup(5, QQ, [M]);

julia> IR = invariant_ring(G);

julia> secondary_invariants(IR)
12-element Vector{MPolyElem_dec{fmpq, fmpq_mpoly}}:
 1
 x[1]*x[3] - x[2]*x[3] + x[2]*x[4] - x[1]*x[5]
 x[3]^2 + x[4]^2 + x[5]^2
 x[1]^3 - 3*x[1]*x[2]^2 + x[2]^3
 x[1]^2*x[3] - x[1]*x[2]*x[3] - x[1]*x[2]*x[4] + x[2]^2*x[4] + x[1]*x[2]*x[5]
 x[1]*x[3]^2 - x[2]*x[3]^2 + x[2]*x[4]^2 - x[1]*x[5]^2
 x[1]^2*x[3] + x[1]^2*x[4] - 2*x[1]*x[2]*x[4] + x[2]^2*x[4] + x[2]^2*x[5]
 x[1]*x[3]*x[4] - x[2]*x[3]*x[4] - x[1]*x[3]*x[5] + x[2]*x[4]*x[5]
 x[3]*x[4]^2 + x[3]^2*x[5] + x[4]*x[5]^2
 x[1]*x[3]^3 - x[2]*x[3]^3 + x[2]*x[3]^2*x[4] + x[1]*x[3]*x[4]^2 - x[2]*x[3]*x[4]^2 + x[2]*x[4]^3 - x[1]*x[3]^2*x[5] - x[1]*x[4]^2*x[5] + x[1]*x[3]*x[5]^2 - x[2]*x[3]*x[5]^2 + x[2]*x[4]*x[5]^2 - x[1]*x[5]^3
 x[3]^4 + 2*x[3]^2*x[4]^2 + x[4]^4 + 2*x[3]^2*x[5]^2 + 2*x[4]^2*x[5]^2 + x[5]^4
 x[1]*x[3]^5 - x[2]*x[3]^5 + x[2]*x[3]^4*x[4] + 2*x[1]*x[3]^3*x[4]^2 - 2*x[2]*x[3]^3*x[4]^2 + 2*x[2]*x[3]^2*x[4]^3 + x[1]*x[3]*x[4]^4 - x[2]*x[3]*x[4]^4 + x[2]*x[4]^5 - x[1]*x[3]^4*x[5] - 2*x[1]*x[3]^2*x[4]^2*x[5] - x[1]*x[4]^4*x[5] + 2*x[1]*x[3]^3*x[5]^2 - 2*x[2]*x[3]^3*x[5]^2 + 2*x[2]*x[3]^2*x[4]*x[5]^2 + 2*x[1]*x[3]*x[4]^2*x[5]^2 - 2*x[2]*x[3]*x[4]^2*x[5]^2 + 2*x[2]*x[4]^3*x[5]^2 - 2*x[1]*x[3]^2*x[5]^3 - 2*x[1]*x[4]^2*x[5]^3 + x[1]*x[3]*x[5]^4 - x[2]*x[3]*x[5]^4 + x[2]*x[4]*x[5]^4 - x[1]*x[5]^5

julia> irreducible_secondary_invariants(IR)
8-element Vector{MPolyElem_dec{fmpq, fmpq_mpoly}}:
 x[1]*x[3] - x[2]*x[3] + x[2]*x[4] - x[1]*x[5]
 x[3]^2 + x[4]^2 + x[5]^2
 x[1]^3 - 3*x[1]*x[2]^2 + x[2]^3
 x[1]^2*x[3] - x[1]*x[2]*x[3] - x[1]*x[2]*x[4] + x[2]^2*x[4] + x[1]*x[2]*x[5]
 x[1]*x[3]^2 - x[2]*x[3]^2 + x[2]*x[4]^2 - x[1]*x[5]^2
 x[1]^2*x[3] + x[1]^2*x[4] - 2*x[1]*x[2]*x[4] + x[2]^2*x[4] + x[2]^2*x[5]
 x[1]*x[3]*x[4] - x[2]*x[3]*x[4] - x[1]*x[3]*x[5] + x[2]*x[4]*x[5]
 x[3]*x[4]^2 + x[3]^2*x[5] + x[4]*x[5]^2

source

Fundamental Systems of Invariants

fundamental_invariants — Function

fundamental_invariants(IR::InvRing, algo::Symbol = :default; beta::Int = 0)

Return a system of fundamental invariants for IR.

The result is cached, so calling this function again with argument IR will be fast and give the same result.

Implemented Algorithms

In the non-modular case the function relies on King's algorithm Simon King (2013) which finds a system of fundamental invariants directly, without computing primary and secondary invariants. If an upper bound for the degrees of fundamental invariants is known, this can be supplied by the keyword argument beta and might result in an earlier termination of the algorithm. By default, the algorithm uses the bounds from Mátyás Domokos, Pál Hegedűs (2000) and Müfit Sezer (2002).

Alternatively, if specified by algo = :primary_and_secondary, the function computes fundamental invariants from a collection of primary and irreducible secondary invariants. The optional keyword argument beta is ignored for this algorithm.

In the modular case, only the second method is available for theoretical reasons.

Examples

julia> K, a = CyclotomicField(3, "a")
(Cyclotomic field of order 3, a)

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0])
[0   0   1]
[1   0   0]
[0   1   0]

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1])
[1   0        0]
[0   a        0]
[0   0   -a - 1]

julia> G = MatrixGroup(3, K, [ M1, M2 ])
Matrix group of degree 3 over Cyclotomic field of order 3

julia> IR = invariant_ring(G)
Invariant ring of
Matrix group of degree 3 over Cyclotomic field of order 3
with generators
AbstractAlgebra.Generic.MatSpaceElem{nf_elem}[[0 0 1; 1 0 0; 0 1 0], [1 0 0; 0 a 0; 0 0 -a-1]]

julia> fundamental_invariants(IR)
4-element Vector{MPolyElem_dec{nf_elem, AbstractAlgebra.Generic.MPoly{nf_elem}}}:
 x[1]^3 + x[2]^3 + x[3]^3
 x[1]*x[2]*x[3]
 x[1]^6 + x[2]^6 + x[3]^6
 x[1]^3*x[2]^6 + x[1]^6*x[3]^3 + x[2]^3*x[3]^6

source

Invariant Rings as Affine Algebras

affine_algebra — Method

affine_algebra(IR::InvRing)

Given an invariant ring IR with underlying graded polynomial ring, say R, return a graded affine algebra, say A, together with a graded algebra homomomorphism A $\rightarrow$ R which maps A isomorphically onto IR.

Note

If a system of fundamental invariants for IR is already cached, the function makes use of that system. Otherwise, such a system is computed and cached first. The algebra A is graded according to the degrees of the fundamental invariants, the modulus of A is generated by the algebra relations on these invariants, and the algebra homomomorphism A $\rightarrow$ R is defined by sending the i-th generator of A to the i-th fundamental invariant.

Examples

julia> K, a = CyclotomicField(3, "a")
(Cyclotomic field of order 3, a)

julia> M1 = matrix(K, [0 0 1; 1 0 0; 0 1 0])
[0   0   1]
[1   0   0]
[0   1   0]

julia> M2 = matrix(K, [1 0 0; 0 a 0; 0 0 -a-1])
[1   0        0]
[0   a        0]
[0   0   -a - 1]

julia> G = MatrixGroup(3, K, [ M1, M2 ])
Matrix group of degree 3 over Cyclotomic field of order 3

julia> IR = invariant_ring(G)
Invariant ring of
Matrix group of degree 3 over Cyclotomic field of order 3
with generators
AbstractAlgebra.Generic.MatSpaceElem{nf_elem}[[0 0 1; 1 0 0; 0 1 0], [1 0 0; 0 a 0; 0 0 -a-1]]

julia> affine_algebra(IR)
(Quotient of Multivariate Polynomial Ring in y[1], y[2], y[3], y[4] over Cyclotomic field of order 3 graded by
  y[1] -> [3]
  y[2] -> [3]
  y[3] -> [6]
  y[4] -> [9] by ideal(y[1]^6 - 3*y[1]^4*y[3] - 16*y[1]^3*y[2]^3 - 4*y[1]^3*y[4] + 3*y[1]^2*y[3]^2 + 24*y[1]*y[2]^3*y[3] + 4*y[1]*y[3]*y[4] + 72*y[2]^6 + 24*y[2]^3*y[4] - y[3]^3 + 8*y[4]^2), Map with following data
Domain:
=======
Quotient of Multivariate Polynomial Ring in y[1], y[2], y[3], y[4] over Cyclotomic field of order 3 graded by
  y[1] -> [3]
  y[2] -> [3]
  y[3] -> [6]
  y[4] -> [9] by ideal(y[1]^6 - 3*y[1]^4*y[3] - 16*y[1]^3*y[2]^3 - 4*y[1]^3*y[4] + 3*y[1]^2*y[3]^2 + 24*y[1]*y[2]^3*y[3] + 4*y[1]*y[3]*y[4] + 72*y[2]^6 + 24*y[2]^3*y[4] - y[3]^3 + 8*y[4]^2)
Codomain:
=========
Multivariate Polynomial Ring in x[1], x[2], x[3] over Cyclotomic field of order 3 graded by
  x[1] -> [1]
  x[2] -> [1]
  x[3] -> [1])

source