4
$\begingroup$

Do you know if there exist algebraic studies of the ring of the power series which emerge when using the theory of Polya for enumeration of sets with certain symmetries? For instance if some ideals have nice properties, and similar.

I have seen a brief account in the chapter "Algebraic Enumeration" by Gessel and Stanley in the "Handbook of Combinatorics," but not much more.

$\endgroup$
4
  • 2
    $\begingroup$ Could you be a little more specific? $\endgroup$
    – J.C. Ottem
    Commented May 26, 2011 at 17:37
  • 1
    $\begingroup$ I don't think this question is well posed. Polya theory is a tool for counting orbits of structures under a group action. What group do you have in mind? (And note that we need a permutation group - the action must be specified.) $\endgroup$ Commented May 26, 2011 at 22:57
  • $\begingroup$ Might the question be related to the relation of the Burnside ring en.wikipedia.org/wiki/Burnside_ring and combinatorial species? $\endgroup$ Commented May 27, 2011 at 5:52
  • $\begingroup$ What I had in mind was, for instance, having found a generating function for some enumeration problem, i.e. the number of nonisomorphic simple graphs with given number of nodes and edges, whether this has been considered as the Hilbert function of some graded algebra, and whether this graded algebra could be obtained from a simpler algebra (like a polynomial algebra) through e.g. quotients. An example in a similar spirit is the Stanley-Reisner ring of a simplicial complex. $\endgroup$ Commented Jul 22, 2011 at 15:32

3 Answers 3

3
$\begingroup$

Pólya's theorem arises in the theory of invariants of finite groups. See Section 10 of http://math.mit.edu/~rstan/pubs/pubfiles/38.pdf.

$\endgroup$
1
  • $\begingroup$ thanks, this is exactly what i was looking for four years ago $\endgroup$ Commented Aug 4, 2015 at 8:24
3
$\begingroup$

I must admit that I don't understand what the posted question is asking, but since the OP seemed to be satisfied with Professor Stanley's answer, I would like to add an algebro-geometric analogue of this situation that may be relevant to this, at least in spirit. (Thanks for asking this question and the answers, which gave me more things to think about, especially from Stanley's article.)

When $X$ is a finite set, studying the enumeration in the set-theoretic quotient $X^{n}/G$ is the main purpose of the Pólya enumeration theorem, and studying the quotient space $X^{n}/G$, when $X$ is a finite CW complex, can be thought as a topological analogue. What can we count about this quotient space? Among various options, we can count "holes", or more precisely, the singular Betti numbers $h^{i}(X^{n}/G)$. Writing

$$\chi_{u}(Y) := \sum_{i=0}^{\infty}(-u)^{i}h^{i}(Y),$$

Macdonald showed that

$$\chi_{u}(X^{n}/G) = Z_{G}(\chi_{u}(X), \chi_{u^{2}}(X), \dots, \chi_{u^{n}}(X)),$$

where

$$Z_{G}(x_{1}, \dots, x_{n}) := \frac{1}{|G|}\sum_{g \in G}x_{1}^{m_{1}(g)} \cdots x_{n}^{m_{n}(g)},$$

writing $m_{i}(g)$ to mean the number of length $i$ cycles in the cycle decomposition of $g$ in $S_{n}$, which is the cycle index of $G$ in $S_{n}$ appearing in the original Pólya enumeration theorem.

My favorite analogue is to consider this over a finite field $\mathbb{F}_{q}$. Namely, if $X$ is a quasi-projective variety over $\mathbb{F}_{q}$, then it turns out that

$$|(X^{n}/G)(\mathbb{F}_{q})| = Z_{G}(|X(\mathbb{F}_{q})|, |X(\mathbb{F}_{q^{2}})|, \dots, |X(\mathbb{F}_{q^{n}})|),$$

where $G$ acts on $X^{n}$ by permuting coordinates (as in the set-theoretic setting). When $X = \mathbb{A}^{1}_{\mathbb{F}_{q}} = \mathrm{Spec}(\mathbb{F}_{q}[t])$, this statement says that there are precisely $q^{n}$ algebra maps

$$\mathbb{F}_{q}[x_{1}, \dots, x_{n}]^{G} \rightarrow \mathbb{F}_{q}$$

over $\mathbb{F}_{q}$, where $G$ acts on the polynomial algebra by permuting variables.

One place you can find these sorts of analogues is my recent preprint: Pólya enumeration theorems in algebraic geometry.

$\endgroup$
1
$\begingroup$

The article Formal Power Series by Ivan Niven The American Mathematical Monthly Vol. 76, No. 8 (Oct., 1969), pp. 871-889 is well written. I'm not sure if that is what you are looking for though.

The book Analytic Combinatorics is available online and worth looking at.

$\endgroup$

You must log in to answer this question.