# 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

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

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

-

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

-

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