Cyclotomic polynomials in combinatorics

Question

I am searching for a combinatorial significance of cyclotomic polynomials. The only examples I got are a paper by Neville Robbins http://www.emis.de/journals/INTEGERS/papers/a6/a6.pdf and two recent papers by Gregg Musiker and Victor Reiner http://arxiv.org/PS_cache/arxiv/pdf/1012/1012.1844v2.pdf and http://combinatorics.cis.strath.ac.uk/fpsac2011/proceedings/dmAO0161.pdf but these do not essentially give a clear picture. I am interested in examples that relate cyclotomic polynomials to foundations of combinatorics (if these exist) or if someone can give a direct combinatorial interpretation of coefficients of cylotomic polynomials that'll be quite helpful.

Answer 1

For $p$ prime, the cyclotomic polynomials are $\Phi_p(x)=\frac{1-x^p}{1-x}=1+x+x^2+ ... +x^{p-1}$. I've seen connections to combinatorics of these polynomials other than the ones noted in the other answers:

A) When evaluated at negative integers, the polynomials give $W(m,p)$ the number of walks of length $p$ between any two distinct vertices of the complete graph $K_m$ for $m>2$:

$$W(m,p)=(-1)^{p-1}\Phi_p(1-m)=(-1)^{p-1} \frac{1-(1-m)^p}{1-(1-m)}=\frac{(m-1)^{p}-(-1)^p}{m}.$$

For $K_3$, see the Jacobsthal sequence OEIS A001045; for $K_4$, A015518; for $K_5$, A015521; for $K_6$, A015531; for $K_7$, A015540; ... .

The $W(m,p)$, ignoring primality, are the signed rows of A135278, alluded to in C below:

$$W(m,1)=1$$ $$W(m,2)=-2+m$$ $$W(m,3)=3-3m+m^2$$ $$W(m,4)=-4+6m-4m^2+m^3$$ $$W(m,5)=5-10m+10m^2-5m^3+m^4,$$

so these numbers can also be related to colored or weighted $n$-simplexes.

Relation to K-theory: The unsigned matrix $W$ above acting on the column vector $(-0,d,-d^2,d^3,...)$ generates the Euler classes for a hypersurface of degree $d$ in $CP^n$. (Cf. Dugger, A Geometric Introduction to K-Theory, p. 168, also A104712, A111492, and A238363).

B) When the polynomials are expanded as sums of the sequence $(1+x)^k$ rather than $x^k$, many of the coefficients ($T(n,k)$ below) have combinatoric interpretations as presented for the first few columns of A239473 (signed A059260). Take your pick, but I don't see an overarching interpretation across columns (however, see the update in the comment section below).

Hidden in the simple expression of the polynomials is an underlying relation between the partial sums of a sequence of polynomials and their binomial transforms, that is independent of any interpretation of the cyclotomic polynomials:

$$\displaystyle \sum_{k=0}^{n} x^k = \sum_{k=0}^{n} T(n,k) (1+x)^k = \frac{1-x^{n+1}}{1-x}=\Phi_{n+1}(x),$$

for $n+1$ an odd prime, is a specific example of

$$\displaystyle \sum_{k=0}^{n} p_k(x) = \sum_{k=0}^{n} T(n,k) (1+p.(x))^k = \frac{1-p.(x)^{n+1}}{1-p.(x)},$$

umbrally, i.e., $\displaystyle (1+p.(x))^k=\sum_{j=0}^{k} \binom{k}{j}p_j(x)$.

Furthermore (within this extended umbral presentation), the Wiki article simplex relates the inequality $\sum_{k=0}^{n} t_k<1$ to an $n$-simplex as the corner of the $n$-cube and the equality $\sum_{k=0}^{n+1} x_k=1$ to the algebraic standard $n$-simplex in algebraic geometry.

C) Simply expand the polynomials in terms of $(x-1)^k$ to obtain the binomial coefficients (A135278) $T(n,k)=\binom{n+1}{k+1}$ that counts the k-faces of a regular n-simplex, or reversed A074909 related to Martin Gardener's "bulgarian solitaire":

$$\displaystyle \frac{1-x^{n+1}}{1-x} = \sum_{k=0}^{n} \binom{n+1}{k+1} (x-1)^k=\Phi_{n+1}(x),$$ or,

$$\displaystyle \Phi_{n+1}(x+1)=\sum_{k=0}^{n} \binom{n+1}{k+1} x^k=\frac{(1+x)^{n+1}-1}{x}$$

for $n+1$ an odd prime. These are also the Whitney numbers (except for the first) for any trees with n+1 vertices, making another contact with Rota's papers.

D) For connections to weights of specific types of weighted Motzkin paths, see The Matrix Ansatz, Orthogonal Polynomials, and Permutations (pg. 4), or Matrix Ansatz Lattice Paths, and Rook Polynomials (pg. 40), by Sylvie Corteel et al.

Edit (Jul, 2020):

E) Again for $p$ prime,

$$\int_0^1\Phi_p(x) \; dx= \int_0^1\frac{x^p-1}{x-1} \; dx = H_p$$

where $H_n = St1_{n,2}/n!$ are the harmonic numbers and $St1_{n,k}$ are the Stirling numbers of the first kind. The harmonic numbers and their generalization are intimately related to the digamma function, the Riemann zeta function, and fractional calculus (MSE-Q&A and MO-Q) over the basis functions $H(x)\frac{x^n}{n!}$ (with $H(x)$, the Heaviside step function) and Dirac delta distributions $\delta^{(n)}(x)$.

Added Apr. 14, 2023:

F) For both $p$ and $n$ prime with $[n]_p = \frac{p^{n}-1}{p-1}$ and $[n]_p! = \prod_{i=1}^n [i]_p$, the cardinality of the finite Grassmannian $G(k,n)(\mathbb{F}_p)$ is

$$G_{k,n} = \frac{[n]_p!}{[k]_p![n-k]_p!}.$$

See eqn. 10 on p. 8 of "Lattice polytopes, Hecke operators, and the Ehrhart polynomial" by Gunnells and Villegas. See also the more general discussion in "The different tongues of q-calculus" by Ernst.

G) Closely related are the quantum numbers defined by

$$[n]_q = \frac{q^{n}-q^{-n}}{q-q^{-1}} $$

$$= q^{-n+1} \frac{(q^2)^n-1}{(q^2)-1} $$

$$ = q^{-n+1} + q^{-n+3} + q^{-n+5} + \cdots + q^{n-5} + q^{n-3} + q^{n-1} .$$

See "Knot polynomial identities and quantum group coincidences" by Morrison, Peters, and Snyder.

Search on 'quantum integer' first in A239473 then in A001045 for the Jacobsthal numbers, A000225 for the 'Mersenne' numbers, and A010892 for the inverse of the 6-th cyclotomic polynomial.

Added Oct 2014:

A tangential note:

The relation between products of $\Phi_m(x)$ and the Coxeter polynomial for $A_n$, $f_n(x)=\frac{1-x^{n+1}}{1-x}$, for $n$ not prime, are given on page 19 of "On the characteristic polynomials of Cartan matrices and the Chebyshev polynomials" by Pantelis Damianou. E.g., $$f_7(x)=\Phi_2(x)\Phi_4(x)\Phi_8(x).$$

More generally, Damianou reveals a relationship between products of $\Phi_m(x)$ and the characteristic polynomials of the Cartan matrix of the simple Lie algebras expressed in terms of the Chebyshev polynomials $U$ and $T$, which lead to interesting combinatorics in many entries of the OEIS, e.g., A119900 whose columns are the unsigned rows of A053122. For $A_n$, he presents the associated polynomial $Q_n(x)=f_n(x^2)=e^{i n \theta}U_n(cos(\theta))$ with $x=e^{i \theta}$.

Added Feb. 29, 2024:

In a similar extension, the Binet formula for generalized FIbonacci polynomials, including the Chebyshev polynomials of the second kind,

$$F_n(x) = \frac{a(x)^n-b(x)^n}{a(x)-b(x)}$$

is discussed in "Irreducibility of generalized FIbonacci polynomials" by Florez and Saunders. This gives the bivariate complete homogeneous symmetric polynomials $h_n(a(x),b(x))$, which as coefficients of different series can be related via compositional inversion to the Eulerian polynomials, the Narayana polynomials, and soliton solutions of the KdV equation. All the polynomials mentioned in the paper and more such polynomials can be found in the OEIS.

Answer 2

I don't know that this is foundational, but see

http://en.wikipedia.org/wiki/Sicherman_dice

Answer 3

The following may be helpful to you:

Coefficients of Cyclotomic Polynomials - Jordan Bell

Memoirs of the AMS - Number 510 - On the Coefficients of Cyclotomic Polynomials - Gennady Bachman

Combinatorial Aspects of Elliptic Curves

Answer 4

A recent paper of mine on permutation enumeration that uses cyclotomic polynomials is I. M. Gessel, Reciprocals of exponential polynomials and permutation enumeration, Australasian J. Combin. 74 (2) (2019), 364–370.

Answer 5

Ethan Coven and Aaron Meyerowitz have a paper "Tiling the integers with translates of one finite set" (cited recently on Terry Tao's blog) about tiling the integers with a single prototile.

That is, they are looking for conditions under which subsets of the integers, $A$ say, such that there are $n_1,n_2,n_3,...$ such that $n_1+A$, $n_2+A$, $\ldots$ disjointly cover all of the integers.

In Coven and Meyerowitz's paper, two conditions are given directly in terms of cyclotomic polynomials for $A$ to have this property. If both conditions are satisfied, then $A$ tiles the integers. On the other hand, if $A$ tiles the integers, then one of the conditions is shown to be satisfied. They conjecture that the second condition must also be satisfied.

Answer 6

http://math.ecnu.edu.cn/~jwguo/maths/congruence.pdf

Here, the cyclotomic polynomials appear in an identity involving q-binomial coefficients.

Answer 7

My first thought was the pair of papers by Musiker and Reiner that you mention. Another paper involving combinatorics and cyclotomic polynomials is the following.

Cyclotomic factors of the descent set polynomial

Denis Chebikin, Richard Ehrenborg, Pavlo Pylyavskyy, Margaret Readdy

Journal of Combinatorial Theory, Series A Volume 116, Issue 2, February 2009, Pages 247-264

Answer 8

I remember seeing in my student days in constructions of Block Designs, or more specifically, mutually orthogonal latin squares, finite fields play a crucial role and cyclotomic polynomials enter there. Sorry I cannot be any more specific.