# 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.

• google suggests looking at: combinatorial group theory Dec 3, 2011 at 18:11
• What are the foundations of combinatorics? Dec 4, 2011 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." Dec 5, 2011 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 (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)$$.

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.

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. Oct 18, 2014 at 1:48
• See Eqn. 3 of "Polygons and Chaos" by Kappraff amd Adamson archive.bridgesmathart.org/2001/bridges2001-67.pdf, and Eqn, 2.33 page 14 of "Transfer matrices ... Potts model. VI. ..." by Salas and Sokal arxiv.org/abs/1002.3761. Oct 4, 2016 at 13:31
• See Egn. 5.3 on p. 22 of "Feynman motives and deletion-contraction relations" by Aluffi and Marcolli arxiv.org/abs/0907.3225 Dec 23, 2016 at 21:34
• See Eqn. 2.1.1 on p. 5 of "The discriminant and the determinant of a hypersurface of even dimension" by Saito (arxiv.org/abs/1110.1717). Dec 24, 2016 at 8:29
• See also the bivariate complete homogeneous symmetric polynomials, the h-polynomials of the (n-1)-simplices, discussed in oeis.org/A135278 and on pg. 43 of "An inversion theorem for labelled trees ..." by Drake (people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf). Jan 11, 2017 at 22:44

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

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

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.

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! Dec 5, 2011 at 22:16
• No it was great. And I was delighted to hear about the blog post. Dec 7, 2011 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.