4
$\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$
  • 9
    $\begingroup$ "Invariant theory" is one keyword (well, key-phrase) for getting into the large literature on this kind of question. $\endgroup$ – Noam D. Elkies Aug 15 '19 at 2:48
  • 3
    $\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 '19 at 3:11
  • 5
    $\begingroup$ See the following MO question from 2010: mathoverflow.net/questions/14613/…. $\endgroup$ – KConrad Aug 15 '19 at 3:47
  • 4
    $\begingroup$ For some work in this area see sciencedirect.com/science/article/pii/0001870884900057. $\endgroup$ – Richard Stanley Aug 15 '19 at 14:39
  • 1
    $\begingroup$ See also Richard Stanley's paper Invariants of finite groups and their applications to combinatorics, projecteuclid.org/euclid.bams/1183544328. $\endgroup$ – Ira Gessel Aug 18 '19 at 5:28
6
$\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, Grundzuge einer arithmetischen theorie der algebraischen grossen, Crelle, Journal fur die reine und angewandte Mathematik 92:1-122, 1881 (reprinted in Werke, vol. 2, 237–387) as an important early contribution.

The paper by Garsia and Stanton linked in Richard Stanley's comment is an important contribution to this literature, dating to 1984.

The MO question 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,\dots,t_n]$ as a shorthand.

General results:

(a) The invariant ring $A[\mathbf{t}]^G$ is generated by the invariants of degree at most $\operatorname{max}(n,n(n-1)/2)$, a result usually attributed to Manfred Gobel (see here), although it was actually anticipated by Leopold Kronecker (see section 12 of his paper Grundzuge einer arithmetischen theorie der algebraischen grossen, Crelle, Journal fur 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 $|G|$, 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 Grobner bases to compute primary and secondary invariants, again not specific to permutation groups; see the book 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 here).

(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 here). When this shelling exists, the assumption that $A$ be a field of characteristic not dividing $|G|$ 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, work of Vic Reiner handles $A_n\subset S_n$ and the diagonally embedded $S_n\hookrightarrow S_n\times S_n\subset S_{2n}$, and work of 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, sections 2.5 and 2.8, along with a discussion of its connection to Gobel'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 $|G|$). 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 this MSE question 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 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.]

| cite | improve this answer | |
$\endgroup$
4
$\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: https://arxiv.org/abs/1811.05440. 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.

| cite | improve this answer | |
$\endgroup$

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.