Suppose that a polynomial $p(x_1\ldots x_n, y_1\ldots y_n)$ in $2n$ variables is invariant under the following operations:

1) $p(x_1\ldots x_n, y_1\ldots y_n)=p(y_1\ldots y_n, x_1\ldots x_n)$

2) $\forall \sigma\in S_n, p(x_1\ldots x_n, y_1\ldots y_n)=p(y_{\sigma(1)}\ldots y_{\sigma(n)}, x_{\sigma(1)}\ldots x_{\sigma(n)})$

In other words, the polynomial has a symmetry group $S_n \times \mathbb{Z}_2$.

My question is: is there a simple polynomial basis for polynomials of degree $\leq d$ with this symmetry?

Clearly one can find a linear basis for such polynomials by taking monomials and applying all elements of the symmetry group. For example, a linear basis for this space is given by polynomials of the form

$\displaystyle\sum_{i_1\neq i_2 \neq \ldots i_d =1}^{n} \left(x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \ldots x_{i_d}^{\alpha_d} y_{i_1}^{\beta_1} y_{i_2}^{\beta_2} \ldots y_{i_d}^{\beta_d}+ y_{i_1}^{\alpha_1} y_{i_2}^{\alpha_2} \ldots y_{i_d}^{\alpha_d} x_{i_1}^{\beta_1} x_{i_2}^{\beta_2} \ldots x_{i_d}^{\beta_d} \right)$

where $\alpha_1,\ldots, \alpha_d, \beta_1, \ldots \beta_d$ are a string of integers summing to $\leq d$. The size of this basis scales exponentially with $d$.

I'm asking if there's a much simpler polynomial basis. (In other words, if every such polynomial $p$ can be written as a polynomial $q$ in some simple basis elements, where $q$ is a generic polynomial). Ideally the number of elements in the basis would grow only polynomially with $d$. For example, in the case of polynomials on $n$ variables with symmetry group $S_n$, the elementary symmetric polynomials of degree $\leq d$ are a simple polynomial basis for the space of $S_n$-symmetric polynomials of degree $\leq d$, with merely $d$ elements in the basis. (In contrast, a linear basis for this space has many elements, namely the number of partitions of $d$.) I'm asking if there is an analogous polynomial basis known for the case of $2n$ variables and symmetry group $S_n\times \mathbb{Z}_2$. Any suggestions are much appreciated.

  • 2
    $\begingroup$ Note that simple suggestions, like $p$ must be sums or products of $S_n$-symmetric polynomials in the $x_i$'s and $y_i$'s, or $p$ must be a $S_n$-symmetric polynomial in the variables $x_iy_i$ and $x_i+y_i$ seem not to work. So I believe this question may have a nontrivial answer. Additionally, I believe this question may be related to the representation theory of $S_n\times \mathbb{Z}_2$, so I have added a representation theory tag. $\endgroup$ May 11, 2016 at 21:18
  • $\begingroup$ what about the polynomials $s_k(x_1,x_2,\ldots,x_n) s_m(y_1,y_2,\ldots,y_n)+s_m(x_1,x_2,\ldots,x_n) s_k(y_1,y_2,\ldots,y_n)$ where $s_k$ is the elementary symmetric polynomial if the degree $k$? $\endgroup$
    – Leox
    May 13, 2016 at 19:41
  • $\begingroup$ Thanks for the suggestion. How could one use such polynomials to form the polynomials $q=\Sigma_i x_i y_i$ or $r=\Sigma_{i\neq j} x_i y_j$? It seems to me the polynomials you describe can form $\Sigma_{i,j} x_i y_j$ but not $q$ or $r$. $\endgroup$ May 13, 2016 at 20:18
  • $\begingroup$ where does the problem come from? $\endgroup$
    – Leox
    May 14, 2016 at 5:54
  • $\begingroup$ $q, r$ is not $S_n \times \mathbb{Z}_2$-invariant polynomial $\endgroup$
    – Leox
    May 14, 2016 at 6:23

2 Answers 2


Denote $G=S_n \times \mathbb{Z}_2$. Let the group $G$ acts on the polynomial ring $k[X_{i,j}], i \leq n, l =\{0,1\}$ ($k$ be a field of chracteristic $0$) by $(\sigma, l)=X_{\sigma(i),{j+l \mod 2}} $. To find a basis of the algebra $k[X_{i,j}]^G$ of $G$-invariants you should use the $G$-homomorphism $k[X_{i,j}] \to k[X_{i,j}]^G$, $f \mapsto R(f)$ where $R$ is the Reinolds average operator $$ R=\frac{1}{|G|}\sum_{g \in G}g. $$ Then algebra of invariants $k[X_{i,j}]^G$ is generated by the elements $R(f)$ where $f$ runs all polynomial of $k[X_{i,j}]$ up to degree $2 n!$. But of course, it is not a minimal generating set. I hope the upper bound for the degree of invariants is $n.$

Some calculation for $n=4.$
Degree 1. There is only one invariant ( in terms of $x,y$): $$ y_{{2}}+y_{{3}}+y_{{4}}+y_{{1}}+x_{{2}}+x_{{3}}+x_{{4}}+x_{{1}}. $$ Degree 2. There is $ 3$ linearly independed invariants $$ {x_{{1}}}^{2}+{x_{{2}}}^{2}+{x_{{3}}}^{2}+{x_{{4}}}^{2}+{y_{{1}}}^{2}+ {y_{{2}}}^{2}+{y_{{3}}}^{2}+{y_{{4}}}^{2},\\ x_{{1}}y_{{1}}+x_{{2}}y_{{2}}+x_{{3}}y_{{3}}+x_{{4}}y_{{4}},\\ x_{{1}}y_{{2}}+x_{{1}}y_{{3}}+x_{{1}}y_{{4}}+x_{{2}}y_{{1}}+x_{{2}}y_{ {3}}+x_{{2}}y_{{4}}+x_{{3}}y_{{1}}+x_{{3}}y_{{2}}+x_{{3}}y_{{4}}+y_{{1 }}x_{{4}}+x_{{4}}y_{{2}}+x_{{4}}y_{{3}} $$ Degree 3. I have found $6$ invariants $$ {x_{{1}}}^{3}+{x_{{2}}}^{3}+{x_{{3}}}^{3}+{x_{{4}}}^{3}+{y_{{1}}}^{3}+ {y_{{2}}}^{3}+{y_{{3}}}^{3}+{y_{{4}}}^{3} ,\\ {x_{{1}}}^{2}y_{{1}}+{x_{{2}}}^{2}y_{{2}}+{x_{{3}}}^{2}y_{{3}}+{x_{{4} }}^{2}y_{{4}}+{y_{{1}}}^{2}x_{{1}}+{y_{{2}}}^{2}x_{{2}}+{y_{{3}}}^{2}x _{{3}}+{y_{{4}}}^{2}x_{{4}},\\ \left( x_{{1}}x_{{3}}+x_{{1}}x_{{4}}+x_{{1}}x_{{2}} \right) y_{{1}}+ \left( x_{{2}}x_{{3}}+x_{{1}}x_{{2}}+x_{{2}}x_{{4}} \right) y_{{2}}+ \left( x_{{3}}x_{{4}}+x_{{1}}x_{{3}}+x_{{2}}x_{{3}} \right) y_{{3}}+ \left( x_{{1}}x_{{4}}+x_{{2}}x_{{4}}+x_{{3}}x_{{4}} \right) y_{{4}}+ \left( x_{{1}}+x_{{2}} \right) y_{{2}}y_{{1}}+ \left( x_{{1}}+x_{{3}} \right) y_{{3}}y_{{1}}+ \left( x_{{4}}+x_{{1}} \right) y_{{4}}y_{{1}} + \left( x_{{2}}+x_{{3}} \right) y_{{3}}y_{{2}}+ \left( x_{{2}}+x_{{4} } \right) y_{{4}}y_{{2}}+ \left( x_{{3}}+x_{{4}} \right) y_{{4}}y_{{3} },\\ \left( {x_{{4}}}^{2}+{x_{{3}}}^{2}+{x_{{2}}}^{2} \right) y_{{1}}+ \left( {x_{{1}}}^{2}+{x_{{4}}}^{2}+{x_{{3}}}^{2} \right) y_{{2}}+ \left( {x_{{2}}}^{2}+{x_{{1}}}^{2}+{x_{{4}}}^{2} \right) y_{{3}}+ \left( {x_{{3}}}^{2}+{x_{{1}}}^{2}+{x_{{2}}}^{2} \right) y_{{4}}+ \left( x_{{4}}+x_{{2}}+x_{{3}} \right) {y_{{1}}}^{2}+ \left( x_{{1}}+ x_{{3}}+x_{{4}} \right) {y_{{2}}}^{2}+ \left( x_{{1}}+x_{{2}}+x_{{4}} \right) {y_{{3}}}^{2}+ \left( x_{{3}}+x_{{1}}+x_{{2}} \right) {y_{{4} }}^{2},\\ x_{{1}}x_{{2}}x_{{3}}+x_{{1}}x_{{2}}x_{{4}}+x_{{1}}x_{{3}}x_{{4}}+x_{{ 2}}x_{{3}}x_{{4}}+y_{{1}}y_{{2}}y_{{3}}+y_{{1}}y_{{2}}y_{{4}}+y_{{1}}y _{{3}}y_{{4}}+y_{{2}}y_{{3}}y_{{4}},\\ \left( x_{{2}}x_{{4}}+x_{{2}}x_{{3}}+x_{{3}}x_{{4}} \right) y_{{1}}+ \left( x_{{3}}x_{{4}}+x_{{1}}x_{{4}}+x_{{1}}x_{{3}} \right) y_{{2}}+ \left( x_{{1}}x_{{4}}+x_{{2}}x_{{4}}+x_{{1}}x_{{2}} \right) y_{{3}}+ \left( x_{{1}}x_{{3}}+x_{{1}}x_{{2}}+x_{{2}}x_{{3}} \right) y_{{4}}+ \left( x_{{3}}+x_{{4}} \right) y_{{2}}y_{{1}}+ \left( x_{{2}}+x_{{4}} \right) y_{{3}}y_{{1}}+ \left( x_{{2}}+x_{{3}} \right) y_{{4}}y_{{1}} + \left( x_{{4}}+x_{{1}} \right) y_{{3}}y_{{2}}+ \left( x_{{1}}+x_{{3} } \right) y_{{4}}y_{{2}}+ \left( x_{{1}}+x_{{2}} \right) y_{{4}}y_{{3} }, $$

and so on..

  • $\begingroup$ Thank you for the reply! As I mentioned in the question, one can easily form a linear basis by taking monomials and applying the symmetry group (which is what you described above). I'd like to know if there's a simple polynomial basis for such polynomials of degree $\leq d$, with far fewer elements, as in the case of the symmetry group $S_n$. I'll edit the question to clarify this issue. $\endgroup$ May 16, 2016 at 20:36
  • $\begingroup$ of cource such a basis exists $\endgroup$
    – Leox
    May 17, 2016 at 5:58
  • $\begingroup$ Why must such a basis exist? Do you have a description of a polynomial basis for $S_n\times \mathbb{Z}_2$-symmetric polynomials of degree $\leq d$ which has only poly($d$) elements? $\endgroup$ May 17, 2016 at 17:08
  • $\begingroup$ Since the group $S_n \times \mathbb{Z}_2$ is finite then its algebra of invariants is finitely generated. At present I dont know a minimal generating set but I think that it is not very hard problem. I have asked you about origin of the problem. If there was any good application of the invariants beyond algebra, for instance to computer science, then somebode could calculate it. $\endgroup$
    – Leox
    May 17, 2016 at 17:33

A) If by "polynomial basis" you mean, by analogy with the $S_n$ case, that there are invariants such that any invariant is uniquely a polynomial in them, then no, there is no such basis. This is the condition that the invariant subring is isomorphic to a polynomial algebra, and this happens if and only if the (permutation) group in question is generated by transpositions, by the Chevalley-Shephard-Todd theorem. So, the invariant rings for Young subgroups of $S_n$ (i.e. of the form $S_{n_1}\times S_{n_2} \times\dots\times S_{n_r}$ for some $n_1+\dots+n_r = n$, and each $S_{n_i}$ factor acting on a distinct set of $n_i$ indices) have a basis in this sense, but for no other permutation groups is there such a basis.

B) BUT, if you just want a set of generators, i.e. invariants such that every invariant is a polynomial in these ones (but not uniquely), then, by a general result of Manfred Gobel for all permutation groups (see here), your answer is supplied by:

  • The product of all the variables $x_1\dots x_ny_1\dots y_n$, AND

  • The set of orbit sums of "special monomials." A "special monomial" is a monomial such that the sequence of exponents in descending order never drops by more than 1, and contains zero. For example $x_1^3x_2x_6^3y_3^2$ is a special monomial, but $x_1^3x_6^3y_3^2$ is not special because the sequence of exponents is $3,3,2,0,\dots$, containing a drop of size 2. The highest-degree special monomials are the ones like $x_1^{2n-1}x_2^{2n-2}\dots x_n^ny_1^{n-1}\dots y_{n-1}$, of degree $\binom{2n}{2}$, so all in all you get a generating set in maximum degree $\binom{2n}{2}$.

There is lots of redundancy in this generating set, and it is only specific to your group in the sense that the orbit sums are for orbits of your group. The same method gives generators for any permutation group, with the same degree bound.

  • $\begingroup$ Yes, exactly, Chevalley-et-al... and this is related to work of Harish-Chandra, and Helgason, about variously-invariant differential operators. $\endgroup$ Jun 27, 2017 at 23:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .