Section 4.1
The symmetric group \(S_n \) acts naturally on \(\{1, ... , n\}\) by permuting its elements. This action allows us to define a representation \(V \cong \mathbb{K}^n\) where on the basis vectors \(\{e_1, ... , e_n\}\text{,}\) the permutation \(\sigma\) acts by \(\sigma \cdot e_i = e_{\sigma(i)}\text{.}\) As \(S_n \) acts on \(V\) by permuting its basis vectors, we have that \(V\) is a permutation representation induced by the permutation action of \(S_n\text{.}\)
Example 4.1.1.
Consider the group \(S_4\text{.}\) The matrix for the action of \((1 \,2\,3\,4) \) is given by
\begin{equation*}
M_{(1 \,2\,3\,4)} = \begin{pmatrix}
0 \amp 1 \amp 0 \amp 0 \\
0 \amp 0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1 \\
1 \amp 0 \amp 0 \amp 0
\end{pmatrix}
\end{equation*}
and then we have it acting on a vector by matrix multiplication,
\begin{equation*}
\begin{pmatrix}
0 \amp 1 \amp 0 \amp 0 \\
0 \amp 0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1 \\
1 \amp 0 \amp 0 \amp 0
\end{pmatrix} \begin{pmatrix}
v_1 \\
v_2 \\
v_3\\
v_4
\end{pmatrix} = \begin{pmatrix}
v_4 \\
v_1 \\
v_2\\
v_3
\end{pmatrix}
\end{equation*}
Now consider the action of the symmetric group \(S_n\) on the polynomial ring \(R=\mathbb{K}[x_1,x_2,...,x_n]\text{.}\) The symmetric polynomials are the invariant polynomials under this action..
Definition 4.1.2.
We call \(f \in R\text{,}\) a symmetric polynomial if
\begin{equation*}
f(x_1,x_2,...,x_n) = f(x_{\sigma(1)},x_{\sigma(2)},...,x_{\sigma(n)})
\end{equation*}
for all permutations of \(\sigma \in S_n\text{.}\)
An example of symmetric polynomials is given by the elementary symmetric polynomials.
Definition 4.1.3.
The elementary symmetric polynomials \(e_0,e_1,...,e_n\) in \(\mathbb{K}[x_1,...,x_n]\) are defined by
\begin{equation*}
e_{m}=\sum_{|J|=m} \bar x_J = \sum_{j_1 \lt j_2 \lt ... \lt j_m} x_{j_1}x_{j_2}...x_{j_m},
\end{equation*}
with \(e_0=1\text{.}\)
More generally, we can consider a permutation action by some subgroup \(G\) of \(S_n\text{.}\) For any monomial in \(R\text{,}\) we can consider its orbit under the action of \(G\text{.}\)
Definition 4.1.4.
The \(G-orbit\) of any element \(f \in R\) is
\begin{equation*}
\text{orb}(f) = \{g \cdot f \mid g \in G\}\text{.}
\end{equation*}
Any permutation in \(G\) acts on the orbit \(\text{orb}(f)\) by rearranging its elements. As a result, the orbit sums will give us invariant polynomials.
Definition 4.1.5.
The orbit sum of \(f\) the sum of over the elements of \(\text{orb}(f)\text{.}\)
We can find a set of minimal invariants by computing all orbit sums of all monomials of degree \(\lt |G|\text{.}\) But this is computationally expensive and will lead to a lot of redundant computations. Instead, we will use a result that tells us that we only need to compute the orbit sums of some special monomials. Consider the exponent sequence \(\beta\) of a monomial \(\bar x^{\bar \beta}\) and rearrange it to obtain an integer partition \(\lambda\text{,}\) where \(\lambda_1 \gt \lambda_2 \gt ... \gt \lambda_m\)
Definition 4.1.6.
We call a monomial special if the entries in its associated partition decrease by at most one at each step and the last entry is 0.
The definition of special depends on the number of variables or the number of parts in the integer partition. So \(x_1^n x_2^{n-1}....x_{n-1}^1 x_n^0\) would not be special within \(\mathbb{K}[x_1, ... , x_{n-1}]\text{,}\) but it is special in \(\mathbb{K}[x_1, ... , x_{n}]\text{.}\)
Theorem 4.1.7.
(Göbel) Let \(\phi:G \mapsto \text{GL}(n,\mathbb{K})\) be a permutation representation of a finite group acting on \(R = \mathbb{K}[x_1,...,x_n]\text{.}\) Then the ring of invariants \(R^G\) is generated as an algebra by the top elementary symmetric function \(e_n = x_1...x_n\) and the orbit sum of the special monomials.
Corollary 4.1.8.
(Göbel’s Bound) In a permutation representation of dimension at least 3, the degree of a minimal generating invariant is at most \(\binom{n}{2}\text{.}\)
We have that the bound follows from the theorem as the degree of a special momial is at most \(\binom{n}{2}\) and this is larger than \(n\text{,}\) the degree of \(e_n\text{,}\) when \(n \geq 3\text{.}\)
To show that orbits of special monomial generate the ring of invariants, one needs to consider a reduction argument. If you start with a non-special monomial, the entries of its partition are not decreasing by at most 1 and we call the first place where there is a jump a \(gap\) in the partition. Starting from a non-special monomial we can obtain a reduced monomial by decreasing all the largest exponents up to the gap by one. The reduced monomial will be closer to being special as the gap itself will be reduced by 1.
Example 4.1.9.
\(\mathbb{K}[x_1,x_2,x_3,x_4]\)\(x_1^2x_2^4x_3 \text{.}\)\((4,2,1)\)
\begin{equation*}
x_1^2x_2^4x_3 \mapsto x_1^2x_2^3 x_3,
\end{equation*}
Algorithmically, we can reduce any monomial to a special one by reducing the upper degrees repeatedly until the monomial is special. So the general idea of the proof of Gobel’s theorem is to show that the orbit sum of any monomial can be rewritten as a sum of orbit sums of special monomials or special monomials times some power of \(e_n\text{.}\) In our ongoing work we are using Gobel’s theorem as a tool for reducing the complexity of computing invariants for permutation actions.
