# Cyclotomic Polynomials in Combinatorics

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.

-
isn't it community wiki ? –  Denis Serre Dec 3 '11 at 17:20
google suggests looking at: combinatorial group theory –  Suvrit Dec 3 '11 at 18:11
What are the foundations of combinatorics? –  Mariano Suárez-Alvarez Dec 4 '11 at 6:52
@Mariano: UmerScientist may be alluding to the series of papers by Gian-Carlo Rota and his collaborators, entitled "On the foundations of combinatorial theory." –  Timothy Chow Dec 5 '11 at 16:05

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 (Whitney numbers for ?).

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.

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}$.

-
A059260 (A239473) now has a combinatorial interpretation.--For p prime, these are the h-polynomials for the n-simplexes.--Confer A049019 to see how substituting an e.g.f. for x can be used to generate a partition polynomial for the faces of permutahedra. –  Tom Copeland Oct 18 '14 at 1:48

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

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

-
-

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.

-
I hope I didn't misquote your paper with Ethan too badly! –  Anthony Quas Dec 5 '11 at 22:16
No it was great. And I was delighted to hear about the blog post. –  Aaron Meyerowitz Dec 7 '11 at 14:41

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

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

-

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

-

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.

-