Cyclic Sieving of Multisets with Bounded Multiplicity and the Frobenius Coin Problem

Abstract

The two subjects in the title are related via the specialization of symmetric polynomials at roots of unity. Let $f(z_1,\dots ,z_n)\in \mathbb{Z}[z_1,\dots ,z_n]$ be a symmetric polynomial with integer coefficients and let $\omega$ be a primitive $d$th root of unity. If $d|n$ or $d|(n-1)$ then we have $f(1,\omega ,\dots ,{\omega }^{n-1})\in \mathbb{Z}$. If $d|n$ then of course we have $f(\omega ,{\omega }^2,\dots ,{\omega }^n)=f(1,\omega ,\dots ,{\omega }^{n-1})\in \mathbb{Z}$, but when $d|(n+1)$ we also have $f(\omega ,{\omega }^2,\dots ,{\omega }^n)\in \mathbb{Z}$. We investigate these three families of integers in the case $f=h_k^{(b)}$, where $h_k^{(b)}$ is the coefficient of $t^k$ in the generating function ${\prod }_{i=1}^n(1+z_{i}t+\cdots +(z_{i}t{)}^{b-1})$. These polynomials were previously considered by several authors. They interpolate between the elementary symmetric polynomials ($b=2$) and the complete homogeneous symmetric polynomials ($b\to \infty$). When $\gcd (b,d)=1$ with $d|n$ or $d|(n-1)$ we find that the integers $h_k^{(b)}(1,\omega ,\dots ,{\omega }^{n-1})$ are related to cyclic sieving of multisets with multiplicities bounded above by $b$, generalizing the well-known cyclic sieving results for sets ($b=2$) and multisets ($b\to \infty$). When $\gcd (b,d)=1$ and $d|(n+1)$ we find that the integers $h_k^{(b)}(\omega ,{\omega }^2,\dots ,{\omega }^n)$ are related to the Frobenius coin problem with two coins. The case $\gcd (b,d)\ne 1$ is more complicated. At the end of the paper we combine these results with the expansion of $h_k^{(b)}$ in various bases of the ring of symmetric polynomials.

Final version. Accepted to Electronic Journal of Combinatorics. Fixed several typos, improved some notation, improved the statement of Corollary 5.3(a)