8
$\begingroup$

Multivariate polynomial indexed by ${1, \ldots, n}$ are acted on by $S_n$: for $\sigma \in S_n$, define $\sigma(x_i) = x_{\sigma(x_i)}$, etc. Symmetric polynomials are those polynomials which are invariant under this action.

If we consider just a subgroup of $S_n$, a polynomial which is not symmetric my be invariant. An example: Let $S_5$ be the symmetric group of degree 5, $\tau = (1\ 2\ 3\ 4\ 5)$, and $C_5 = \{\tau^n : n = 1, ..., 5\}$. The polynomial $$f(x_1, x_2, x_3, x_4, x_5) = x_1x_3 + x_2x_4 + x_3x_5 + x_4x_1+x_5x_2$$ is invariant under the elements of $C_5$, but not under the elements of $S_5$.

I was wondering what sort of theory exists around these sets of polynomials? What are they called?

Also, Every symmetric polynomial can be expressed as some polynomial evaluated on the elementary symmetric polynomials. Is there some systematic way of generating some set of polynomials which will have this property?

$\endgroup$
7
  • 15
    $\begingroup$ "Invariant theory" is one keyword (well, key-phrase) for getting into the large literature on this kind of question. $\endgroup$ Aug 15, 2019 at 2:48
  • 5
    $\begingroup$ It's probably worth pointing out that the $S_n$ may act on polynomial rings in other interesting ways. For doubly indexed variables the action $\sigma \cdot x_{i\, j} = x_{\sigma (i) \, \sigma (j)}$ plays a role in the study of graph density inequalities. $\endgroup$
    – tim
    Aug 15, 2019 at 3:11
  • 5
    $\begingroup$ See the following MO question from 2010: mathoverflow.net/questions/14613/…. $\endgroup$
    – KConrad
    Aug 15, 2019 at 3:47
  • 4
    $\begingroup$ For some work in this area see sciencedirect.com/science/article/pii/0001870884900057. $\endgroup$ Aug 15, 2019 at 14:39
  • 3
    $\begingroup$ The better analogy is not when you consider a general subgroup of $S_n$ but rather a "good" action of a group $G$ which acts on the $x_i$ by linear transformations (and therefore on the ring of polynomials by multiplicativity). You get a theory very much like symmetric polynomials (generated by certain elementary polynomials) if and only if $G$ is what's called a "complex reflection group" en.wikipedia.org/wiki/Complex_reflection_group. A more direct analogy with $S_n$ is "Coxeter groups" en.wikipedia.org/wiki/Coxeter_group $\endgroup$ Feb 16, 2020 at 0:46

2 Answers 2

13
$\begingroup$

The name of the body of theory you are asking for is "invariant theory of permutation groups." You will also find relevant papers by searching for "polynomial permutation invariants."

It falls under the broader rubric of "invariant theory of finite groups", which is a developed field. See the books by Benson, Smith, Neusel and Smith, Campbell and Wehlau, and Derksen and Kemper. But there is a fair amount of work specifically on permutation groups, i.e., subgroups of $S_n$, acting in the way you describe, dating back to the 19th century. I'll mention the paper by Leopold Kronecker, Grundzüge einer arithmetischen theorie der algebraischen grossen, Crelle, Journal für die reine und angewandte Mathematik 92:1–122, 1881 (reprinted in Werke, vol. 2, 237–387) as an important early contribution.

The paper Group actions on Stanley–Reisner rings and invariants of permutation groups by Garsia and Stanton linked in Richard Stanley's comment is an important contribution to this literature, dating to 1984.

The MO question Invariant polynomials under a group action (hidden GIT) linked in KConrad's comment speaks to the cyclic action you mention in the OP.

I summarized a large amount of currently known theory (for general $G\subset S_n$) in this math.SE answer, which I thought belonged on MO to begin with, so I'm reproducing it here:


Let $G\subset S_n$ be the permutation group in question. Let $A[\mathbf{t}]:=A[t_1,\dotsc,t_n]$ as a shorthand.

General results:

(a) The invariant ring $A[\mathbf{t}]^G$ is generated by the invariants of degree at most $\max(n,n(n-1)/2)$, a result usually attributed to Manfred Göbel (see Computing Bases for Rings of Permutation-invariant Polynomials (DOI)), although it was actually anticipated by Leopold Kronecker (see section 12 of his paper Grundzüge einer arithmetischen theorie der algebraischen grossen, Crelle, Journal für die reine und angewandte Mathematik 92:1–122, 1881, reprinted in Werke, vol. 2, 237–387).

(b) If the coefficient ring $A$ is a field of characteristic not dividing the group order $\lvert G\rvert$, then $A[\mathbf{t}]^G$ is free as a module over the subring generated by any homogeneous system of parameters (equivalently, $A[\mathbf{t}]^G$ is Cohen–Macaulay). This result is not specific to permutation groups — it is a consequence of the Hochster–Eagon theorem. (Though again it happens that Kronecker proved it in the case of a permutation group and a field of characteristic 0.) Then any homogeneous system of parameters for $A[\mathbf{t}]^G$ is called a set of primary invariants, and a module basis over the subring they generate is a set of secondary invariants. There are algorithms based on Gröbner bases to compute primary and secondary invariants, again not specific to permutation groups; see the book Computational Invariant Theory by Derksen and Kemper. However, in the case of permutation groups, the elementary symmetric polynomials provide a uniform choice for the primary invariants, and there is a method due to Nicolas Borie that aims for more effective computability of the secondary invariants (see Effective Invariant Theory of Permutation Groups Using Representation Theory).

(c) There is also a method due to Garsia and Stanton that produces secondary invariants from a shelling of a certain cell complex (specifically, the quotient of the barycentric subdivision of the boundary of an $(n-1)$-simplex by the $G$ action on the simplex's vertices), when such exists (see Group actions on Stanley–Reisner rings and invariants of permutation groups). When this shelling exists, the assumption that $A$ be a field of characteristic not dividing $\lvert G\rvert$ becomes superfluous, i.e. the secondary invariants produced by the method give a module basis for $A[\mathbf{t}]^G$ over the subring generated by the elementary symmetric polynomials, entirely regardless of $A$. It is not an easy problem to find the shelling in general, but has been done in specific cases (the original paper by Garsia and Stanton handles the Young subgroups $Y\subset S_n$ [i.e., direct products of smaller symmetric groups acting on disjoint sets of indices], Quotients of Coxeter complexes and P-Partitions by Vic Reiner handles alternating subgroups $Y^+\subset S_n$ of Young subgroups $Y$, and diagonally embedded Young subgroups $Y \hookrightarrow Y\times Y \hookrightarrow S_n\times S_n\subset S_{2n}$, and Lexicographic Shellability for Balanced Complexes by Patricia Hersh handles the wreath product $S_2\wr S_n\subset S_{2n}$). There is a detailed development of Garsia and Stanton's shelling result in my thesis Two inquiries about finite groups and well-behaved quotients, sections 2.5 and 2.8, along with a discussion of its connection to Göbel's work (see last paragraph) and some speculation about generalizations.

(d) From (b) you can see that $A[\mathbf{t}]^G$ has a nice structure of free-module-over-polynomial-subring when $A$ is a field of characteristic not dividing $|G|$, but from (c) you can see that sometimes this nice structure still exists even when $A$ doesn't satisfy this (e.g. perhaps it is $\mathbb{Z}$, or else a field whose characteristic does divide $\lvert G\rvert$). There is a characterization, due to myself and Sophie Marques, of which groups $G\subset S_n$ have the property that this structure in $A[\mathbf{t}]^G$ exists regardless of $A$. It turns out to be the groups generated by transpositions, double transpositions, and 3-cycles.

(Our paper is framed in the language of Cohen–Macaulay rings and is focused on the situation that $A$ is a field. To see that my claim about "any $A$" in the previous paragraph follows, one shows that if for a given $G$, the described structure obtains for $A$ any field, then it also obtains with $A=\mathbb{Z}$ — this is supposedly well-known, but "just in case", it is written down carefully in section 2.4.1 of my thesis — and then one notes that a free module basis of $\mathbb{Z}[\mathbf{t}]^G$ over the subring generated by the elementary symmetric polynomials will also be a free module basis of $A[\mathbf{t}]^G$, just by base changing to $A$. See the MSE question Permutation groups acting on polynomial rings and base change for why the base change doesn't mess anything up.)

(e) As lisyarus stated, the special case of $G=A_n$ is well-understood: the invariant ring is generated by the elementary symmetric polynomials and the Vandermonde determinant. Actually this requires the hypothesis that $2$ is a unit in $A$, as you note in comments. If $2$ is not a unit in $A$, one can still generate the invariant ring with the elementary symmetric polynomials and the sum of the positive terms in the Vandermonde determinant (or, the sum of the negative terms). Certain other cases, e.g. $D_4$, also have explicit descriptions coming from Galois theory. The classical material usually assumes $A$ is a field, but see sections 5.4 and 5.5 in Owen Biesel's thesis Galois closures for rings for $A_n$ and $D_4$; Biesel is working over general $A$.


[The references to "lisyarus" and "you" in this final paragraph make sense in the context of the original post on math.SE.]

$\endgroup$
6
$\begingroup$

If you're interested specifically in the cyclic group you may be interested in the "cyclic quasi-symmetric functions" studied recently in this paper of Adin, Gessel, Reiner, and Roichman: Cyclic quasi-symmetric functions. These "cyclic quasi-symmetric functions" are not exactly the same as polynomials invariant under the action of the long cycle in $S_n$ (for instance, they are formal power series rather than polynomials, and also they also have to be "quasi-symmetric functions" in addition to enjoying a cyclic symmetry condition). But the theory here closely parallels the usual theory of symmetric functions (and the theory of quasi-symmetric functions) and does involve a kind of cyclic symmetry.

By the way, the cyclically symmetric polynomials (in your sense) were also discussed in this question of Jim Propp: Cyclically symmetric functions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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