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$ – Adam Bouland May 11 '16 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 '16 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$ – Adam Bouland May 13 '16 at 20:18
  • $\begingroup$ where does the problem come from? $\endgroup$ – Leox May 14 '16 at 5:54
  • $\begingroup$ $q, r$ is not $S_n \times \mathbb{Z}_2$-invariant polynomial $\endgroup$ – Leox May 14 '16 at 6:23

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$ – Adam Bouland May 16 '16 at 20:36
  • $\begingroup$ of cource such a basis exists $\endgroup$ – Leox May 17 '16 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$ – Adam Bouland May 17 '16 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 '16 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$ – paul garrett Jun 27 '17 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.