# A topological interpretation of the cyclotomic polynomial

Gregg Musiker¹†and Victor Reiner¹‡

¹University of Minnesota, School of Mathematics, Minneapolis, MN, USA

**Abstract.** We interpret the coefficients of the cyclotomic polynomial in terms of simplicial homology.

**Résumé.** Nous donnons une interprétation des coefficients du polynôme cyclotomique en utilisant l'homologie simpliciale.

**Keywords:** Cyclotomic polynomial, higher-dimensional tree, matroid duality, oriented matroid, simplicial matroid, simplicial homology

## 1 Introduction

This paper studies the cyclotomic polynomial $\Phi_n(x)$, which is defined as the minimal polynomial over $\mathbb{Q}$ for any primitive $n^{th}$ root of unity $\zeta$ in $\mathbb{C}$. It is monic, irreducible, and has degree given by the Euler phi function $\phi(n)$, with formula

$$ \Phi_n(x) = \prod_{j \in (\mathbb{Z}/n\mathbb{Z})^\times} (x - \zeta^j). $$

The equation $x^n - 1 = \prod_{d|n} \Phi_d(x)$ gives a recurrence showing that all coefficients of $\Phi_n(x)$ lie in $\mathbb{Z}$.

Although well-studied, the coefficients of $\Phi_n(x)$ are mysterious [2, 10, 11, 14, 15, 17, 29]. We offer here two interpretations for their magnitudes, as orders of cyclic groups. In the first interpretation (Corollary 5 below) this group is a quotient of the free abelian group $\mathbb{Z}[\zeta]$ by a certain full rank sublattice.

The second interpretation is topological, given by Theorem 1 below, as the torsion in the homology of a certain simplicial complex associated with a squarefree integer $n = p_1 \cdots p_d$. These simplicial complexes originally arose in the work of Bolker [6], reappeared in the work of Kalai [13] and Adin [1] on higher-dimensional matrix-tree theorems, and were shown to be connected with cyclotomic extensions in work of J. Martin and the second author [18]. We review these simplicial complexes briefly here in order to state the result; see Section 4 for more details.

Given a positive integer $p$, let $K_p$ denote a 0-dimensional abstract simplicial complex having $p$ vertices$^{(i)}$, which we will label by the residues

$$ \{0 \mod p, 1 \mod p, \dots, (p-1) \mod p\} $$

<footnote>†Supported by NSF Postdoctoral Fellowship and NSF grant DMS-1067183.</footnote>

<footnote>‡Supported by NSF grant DMS-1001933.</footnote>

<footnote>(i) Note that here $K_p$ does not refer to a complete graph on $p$ vertices; we hope that this causes no confusion.</footnote>
for reasons that will become clear in a moment. Given primes $p_1, \dots, p_d$, let

$$K_{p_1, \dots, p_d} := K_{p_1} * \dots * K_{p_d}$$

be the simplicial join, [21, §62], of $K_{p_1}, \dots, K_{p_d}$. This is a pure $(d-1)$-dimensional abstract simplicial complex, that may be thought of as the complete $d$-partite complex on vertex sets $K_{p_1}$ through $K_{p_d}$ of sizes $p_1, \dots, p_d$. The facets (maximal simplices) of $K_{p_1, \dots, p_d}$ are labelled by sequences of residues $(j_1 \text{ mod } p_1, \dots, j_d \text{ mod } p_d)$. Denoting the squarefree product $p_1 \cdots p_d$ by $n$, the Chinese Remainder Theorem isomorphism

$$\mathbb{Z}/p_1\mathbb{Z} \times \cdots \times \mathbb{Z}/p_d\mathbb{Z} \xrightarrow{\Xi} \mathbb{Z}/n\mathbb{Z} \qquad (1)$$

allows one to label such a facet by a residue $j \bmod n$; call this facet $F_j \bmod n$. Then for any subset $A \subseteq \{0, 1, \dots, \phi(n)\}$, let $K_A$ denote the subcomplex of $K_{p_1, \dots, p_d}$ which is generated by the facets $\{F_j \bmod n\}$ as $j$ runs through the following set of residues:

$$A \cup \{\phi(n) + 1, \phi(n) + 2, \dots, n - 1, n\}.$$

Our first main result interprets the magnitudes of the coefficients of $\Phi_n(x)$. Let $\tilde{H}_i(-; \mathbb{Z})$ denote reduced simplicial homology with coefficients in $\mathbb{Z}$.

**Theorem 1** For a squarefree positive integer $n = p_1 \cdots p_d$, with cyclotomic polynomial $\Phi_n(x) = \sum_{j=0}^{\phi(n)} c_j x^j$, one has

$$\tilde{H}_i(K_{\{j\}}; \mathbb{Z}) = \begin{cases} \mathbb{Z}/c_j\mathbb{Z} & \text{if } i = d-2, \\ \mathbb{Z} & \text{if both } i = d-1 \text{ and } c_j = 0, \\ 0 & \text{otherwise.} \end{cases}$$

We furthermore interpret topologically the signs of the coefficients in $\Phi_n(x)$. For this, we use oriented simplicial homology, and orient the facet $F_j \bmod n$ having $j \equiv j_i \bmod p_i$ for $i = 1, 2, \dots, d$ as

$$[F_j] = [F_{j \bmod n}] = [j_1 \bmod p_1, \dots, j_d \bmod p_d].$$

**Theorem 2** Fix a squarefree positive integer $n = p_1 \cdots p_d$ with cyclotomic polynomial $\Phi_n(x) = \sum_{j=0}^{\phi(n)} c_j x^j$. Then for any $j \neq j'$ such that $c_j, c_{j'} \neq 0$, one has $\tilde{H}_{d-1}(K_{\{j,j'\}}; \mathbb{Z}) \cong \mathbb{Z}$, and any nonzero $(d-1)$-cycle $z = \sum_{\ell} b_{\ell} [F_{\ell}]$ in this homology group will have $b_j, b_{j'} \neq 0$, with

$$\frac{c_j}{c_{j'}} = -\frac{b_{j'}}{b_j}.$$

In particular, $c_j, c_{j'}$ have the same sign if and only if $b_j, b_{j'}$ have opposite signs.

**Example 3** We illustrate these theorems for $n = 15$. Here $d = 2, p_1 = 3, p_2 = 5$, and $\phi(n) = 2 \cdot 4 = 8$. The cyclotomic polynomial is

$$\Phi_{15}(x) = 1 - x + x^3 - x^4 + x^5 - x^7 + x^8 \\ = (+1) \cdot (x^0 + x^3 + x^5 + x^8) + (-1) \cdot (x^1 + x^4 + x^7) + 0 \cdot (x^2 + x^6).$$
<figure><img src="image_1.png" /><figcaption>Fig. 1: The case of $\Phi_{15}(x)$</figcaption></figure>

The complex $K_{p_1,p_2} = K_{3,5}$ is a complete bipartite graph with vertex sets labelled as in Figure 1(a). The subcomplex $K_\emptyset$ generated by the edges $F_j \bmod 15$ with $j \in \{\phi(n) + 1, \phi(n) + 2, \dots, n - 1\} = \{9, 10, 11, 12, 13, 14\}$ is the subgraph shown in Figure 1(b).

To see why the coefficient $c_6 = 0$ in $\Phi_{15}(x)$, one adds the edge $F_6 \bmod 15$ to the graph $K_\emptyset$, obtaining the graph $K_{\{6\}}$, shown in Figure 1(c), which has

$$ \begin{aligned} \tilde{H}_0(K_{\{6\}}; \mathbb{Z}) &= \mathbb{Z} = \mathbb{Z}/0\mathbb{Z} \\ \tilde{H}_1(K_{\{6\}}; \mathbb{Z}) &= \mathbb{Z}. \end{aligned} $$

To see why the coefficients $c_5 = +1$ or $c_7 = -1$ have magnitude 1, one adds the edge $F_5 \bmod 15$ or $F_7 \bmod 15$ to the graph $K_\emptyset$, obtaining the graphs $K_{\{5\}}$ or $K_{\{7\}}$ shown in Figures 1(d) and 1(e), which have

$$ \begin{aligned} \tilde{H}_0(K_{\{5\}}; \mathbb{Z}) &= 0 = \mathbb{Z}/(+1)\mathbb{Z} \\ \tilde{H}_0(K_{\{7\}}; \mathbb{Z}) &= 0 = \mathbb{Z}/(-1)\mathbb{Z}. \end{aligned} $$

To understand the signs of the coefficients, note first that, by convention, $\Phi_{15}(x)$ is monic, so the coefficient $c_8 = c_{\phi(n)} = +1$. Therefore any other coefficient $c_j$ should have sign

$$ \operatorname{sgn}(c_j) = \frac{\operatorname{sgn}(c_j)}{\operatorname{sgn}(c_8)} = -\frac{\operatorname{sgn}(b_8)}{\operatorname{sgn}(b_j)} $$

where $z = \sum_i b_i [F_i]$ is a nontrivial cycle in $K_{\{j,8\}}$, in which the edge $[F_j]$ is directed from the vertex $(j_1 \bmod 3)$ toward the vertex $(j_2 \bmod 5)$. As shown in Figures 1(f) and 1(g), the nontrivial cycle in $K_{\{7,8\}}$ has $[F_7]$, $[F_8]$ oriented in the same direction, explaining why $c_7 = -1$, while the nontrivial cycle in $K_{\{5,8\}}$ has $[F_5]$, $[F_8]$ oriented in the opposite direction, explaining why $c_5 = +1$.
The remainder of the paper is structured as follows. Section 2 describes our first interpretation for the cyclotomic polynomial, which applies much more generally to any monic polynomial in $\mathbb{Z}[x]$. Section 3 reviews some facts, underlying the main results, about duality of matroids, Plücker coordinates, and oriented matroids. Section 4 recalls results and establishes terminology on Kalai’s higher dimensional spanning trees in a simplicial complex. Section 5 discusses further properties of the simplicial complex $K_{p_1, \dots, p_d}$ whose subcomplexes appear in Theorem 1 and 2. Section 6 proves these theorems. We end with Section 7, where we discuss known properties of $\Phi_n(x)$ that manifest themselves topologically.

## 2 Coefficients of monic polynomials in $\mathbb{Z}[x]$

Our goal here is the first interpretation for the coefficients of $\Phi_n(x)$, which applies more generally to the coefficients of any monic polynomial $f(x)$ in $\mathbb{Z}[x]$. Recall that when $f(x)$ is of degree $r$, one has an isomorphism of $\mathbb{Z}$-modules

$$ \begin{gathered} \mathbb{Z}^r \to \mathbb{Z}[x]/(f(x)) \\ (a_0, a_1, \dots, a_{r-1}) \mapsto \sum_{j=0}^{r-1} a_j \bar{x}^j. \end{gathered} $$

As notation, given a subset $A$ of some abelian group, let $\mathbb{Z}A$ denote the collection of all $\mathbb{Z}$-linear combinations of elements of $A$.

**Proposition 4** For a monic polynomial $f(x) = \sum_{j=0}^r c_j x^j$ of degree $r$ in $\mathbb{Z}[x]$, one has an isomorphism of abelian groups

$$ (\mathbb{Z}[x]/(f)) / \mathbb{Z}A \cong \mathbb{Z}/c_j\mathbb{Z} $$

where $A$ is the subset of size $r$ given as $\{\bar{1}, \bar{x}, \bar{x}^2, \dots, \bar{x}^r\} \setminus \{\bar{x}^j\}$.

**Proof:** Consider the matrix in $\mathbb{Z}^{r \times (r+1)}$

$$ \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & -c_0 \\ 0 & 1 & 0 & \cdots & 0 & -c_1 \\ 0 & 0 & 1 & \cdots & 0 & -c_2 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & -c_{r-1} \end{bmatrix} $$

whose columns express the elements of $\{\bar{1}, \bar{x}, \bar{x}^2, \dots, \bar{x}^r\}$ uniquely in the $\mathbb{Z}$-basis $\{\bar{1}, \bar{x}, \bar{x}^2, \dots, \bar{x}^{r-1}\}$ for $\mathbb{Z}[x]/(f)$. The $r \times r$ submatrix obtained by restricting this matrix to the columns indexed by $A$ is equivalent by row and column permutations to a upper triangular matrix with diagonal entries $(1, 1, \dots, 1, -c_j)$. Hence $(\mathbb{Z}[x]/(f)) / \mathbb{Z}A \cong \mathbb{Z}/c_j\mathbb{Z}$. $\square$

The special case where $f(x)$ is the cyclotomic polynomial $\Phi_n(x)$ leads to the following considerations. Fix once and for all a primitive $n^{th}$ root of unity $\zeta$.

**Corollary 5** The cyclotomic polynomial $\Phi_n(x) = \sum_{j=0}^{\phi(n)} c_j x^j$ has

$$ \mathbb{Z}[\zeta]/\mathbb{Z}A \cong \mathbb{Z}/c_j\mathbb{Z} $$

where $A = \{1, \zeta, \zeta^2, \dots, \zeta^{\phi(n)}\} \setminus \{\zeta^j\}$.
**Proof:** Apply the previous proposition with $f(x) = \Phi_n(x)$ and $r = \phi(n)$, noting that the ring map $\mathbb{Z}[x] \to \mathbb{Z}[\zeta]$ sending $x$ to $\zeta$ will also send $x^j$ to $\zeta^j$, and induce an isomorphism $\mathbb{Z}[x]/(\Phi_n(x)) \to \mathbb{Z}[\zeta]$. $\square$

For later use (see the proof of Theorem 20), we note here that the set

$$P_n := \{\zeta^m\}_{m \in (\mathbb{Z}/n\mathbb{Z})^\times}$$

of all primitive $n^{th}$ roots of unity within $\mathbb{Z}[\zeta]$ forms a $\mathbb{Z}$-basis whenever $n$ is squarefree. This is a sharpening of an observation of Johnsen [12], who noted that $P_n$ forms a $\mathbb{Q}$-basis of $\mathbb{Q}[\zeta]$ in the same situation.

**Proposition 6** When $n$ is squarefree, the collection $P_n$ of all primitive $n^{th}$ roots of unity forms a $\mathbb{Z}$-basis for $\mathbb{Z}[\zeta]$.

**Proof:** The result is easy when $n$ is prime and can be deduced from the Chinese Remainder Theorem in the general case. See [22] for details. $\square$

## 3 Duality of matroids or Plücker coordinates

We will need a version of the linear algebraic duality between Plücker coordinates for complementary Grassmannians $G(r, \mathbb{F}^n)$, $G(n - r, \mathbb{F}^n)$, or equivalently, the duality between bases and cobases in coordinated matroids.

**Proposition 7** Let $0 \le r \le n$. Let $M$ and $M^{\perp}$ be matrices in $\mathbb{F}^{r \times n}$ and $\mathbb{F}^{(n-r) \times n}$, respectively, both of maximal rank, with the following property: $\ker M$ is equal to the row space of $M^{\perp}$, or equivalently, $\ker M^{\perp}$ is the row space of $M$. Then

(i) there exists a scalar $\alpha$ in $\mathbb{F}^{\times}$ having the following property: for every $(n-r)$-subset $T$ of $[n]$, with complementary set $T^c$,

$$\det(M|_{T^c}) = \pm \alpha \cdot \det(M^{\perp}|_T)$$

where $A|_J$ denotes the restriction of a matrix $A$ to the subset of columns indexed by $J$, and the $\pm$ sign depends upon the set $T$.

(ii) if one furthermore assumes that $\mathbb{F} = \mathbb{Q}$, that $M$ and $M^{\perp}$ have entries in $\mathbb{Z}$, and that there exists at least one $(n-r)$-subset $T_0$ for which $M|_{T_0}$, $M^{\perp}|_{T_0}$ are both invertible over $\mathbb{Z}$, then the scalar $\alpha$ above equals $\pm 1$, and one has for every $(n-r)$-subset $T$,

$$\mathrm{coker}(M|_{T^c}) \cong \mathrm{coker}(M^{\perp}|_T).$$

Here, we are thinking of coker $M$ as signifying a map between powers of $\mathbb{Z}$.

**Proof:** Both assertions can be reduced via row and column operations to the case where $M$ takes the form $[I_r|A]$ for some $r$-by-$(n-r)$ matrix $A$, where they are easier to verify. See [22] for details. $\square$

The proof of Theorem 2 will ultimately rely on the following statement about duality of oriented matroids for vectors in a vector space over an ordered field $\mathbb{F}$, such as $\mathbb{F} = \mathbb{Q}$.
**Proposition 8** Let $\mathbb{F}$ be an ordered field, $M$ and let $M^{\perp}$ be matrices in $\mathbb{F}^{r \times n}$ and $\mathbb{F}^{(n-r) \times n}$ as in Proposition 7, that is, both of maximal rank, with ker $M$ perpendicular to the row space of $M^{\perp}$. Let the vectors $v_{\ell}$ in $\mathbb{F}^r$ and $v_{\ell}^{\perp}$ in $\mathbb{F}^{n-r}$ be the $\ell^{th}$ columns of $M$ and $M^{\perp}$. Let $A$ be an $(r+1)$-subset of $\{1, 2, \dots, n\}$ such that the matrix $M|_A$ in $\mathbb{F}^{r \times (r+1)}$ has full rank $r$, with

$$ \sum_{\ell \in A} c_{\ell} v_{\ell} = 0 \qquad (2) $$

the unique dependence among its columns, up to scaling. Then for any pair of nonzero coefficients $c_j, c_{j'} \neq 0$, the matrix $M^{\perp}|_{A^c \cup \{j, j'\}}$ in $\mathbb{F}^{(n-r) \times (n-r+1)}$ has full rank $n-r$, and the unique dependence among its columns, up to scaling,

$$ \sum_{\ell \in A^c \cup \{j, j'\}} b_{\ell} v_{\ell}^{\perp} = 0, \qquad (3) $$

will have both $b_j, b_{j'} \neq 0$, with

$$ \frac{c_j}{c_{j'}} = -\frac{b_{j'}}{b_j}. $$

In particular, $c_j, c_{j'}$ have the same sign if and only if $b_j, b_{j'}$ have opposite signs.

**Proof:** The main observation here is that vectors in the row space of $M^{\perp}$ are covectors for $\{v_{\ell}^{\perp}\}$. See [22] for details. $\square$

# 4 Simplicial spanning trees

For a collection of subsets $S$ of some vertex set $V$, let $\langle S \rangle$ denote the (abstract) simplicial complex $S$ on $V$ generated by $S$, that is, $\langle S \rangle \subset 2^V$ consists of all subsets of $V$ contained in at least one subset from $S$. We recall the notion of simplicial spanning tree in $S$, following Adin [1], Duval, Klivans and Martin [8], Kalai [13], and Maxwell [19].

**Definition 9** Let $S$ be the collection of facets of a pure $k$-dimensional (abstract) simplicial complex. Say that $R \subset S$ is an $S$-spanning tree if

(i) $\langle R \rangle$ contains the entire $(k-1)$-skeleton of $\langle S \rangle$,

(ii) $\tilde{H}_k(\langle R \rangle; \mathbb{Z}) = 0$, and

(iii) $\tilde{H}_{k-1}(\langle R \rangle; \mathbb{Z})$ is finite.

We point out here three well-known features of this definition.

**Proposition 10** Fix the collection of facets $S$ of a pure $k$-dimensional simplicial complex.

(i) Condition (i) in Definition 9 is equivalent to $\tilde{H}_k(\langle S \rangle, \langle R \rangle; \mathbb{Z}) = \mathbb{Z}^{|S \setminus R|}$.

(ii) Condition (ii) in Definition 9 is equivalent to $\tilde{H}_k(\langle R \rangle; \mathbb{Q}) = 0$.
(iii) All S-spanning trees R have the same cardinality, namely

$$|R| = |S| - \mathrm{rank}_{\mathbb{Z}} \tilde{H}_k(\langle S \rangle; \mathbb{Z}). \qquad (4)$$

**Proof:** See [22] for details.

<figure><img src="image_2.png" /></figure>

The following key observation essentially goes back to work of Kalai [13, Lemma 2].

**Proposition 11** Fix a vertex set V and a collection of k-dimensional simplices S. Consider a collection of (k + 1)-dimensional faces T of cardinality

$$|T| := \mathrm{rank}_{\mathbb{Z}} \tilde{H}_k(\langle S \rangle; \mathbb{Z})$$

for which $T \cup \langle S \rangle$ forms a simplicial complex K, that is, all boundaries of faces in T lie in $\langle S \rangle$.

Then the following two assertions hold for any choice of an S-spanning tree R.

(i) The $|T| \times |T|$ matrix $\partial$ that represents the relative simplicial boundary map

$$C_{k+1}(K, \langle R \rangle; \mathbb{Z}) \rightarrow C_k(K, \langle R \rangle; \mathbb{Z}) \\ \frac{\|}{\mathbb{Z}^{|T|}} \qquad \frac{\|}{\mathbb{Z}^{|S \setminus R|}}$$

is nonsingular if and only if $\tilde{H}_{k+1}(K; \mathbb{Q}) = 0$.

(ii) When the matrix $\partial$ is nonsingular, then $\mathrm{coker}(\partial) = \tilde{H}_k(K, \langle R \rangle; \mathbb{Z})$.

**Proof:** See [22] for details.

<figure><img src="image_3.png" /></figure>

**Definition 12** Given a collection of k-simplices S, and an S-spanning tree R, say<sup>(ii)</sup> that R is torsion-free if Condition (iii) in Definition 9 is strengthened to the vanishing condition

(iv) $\tilde{H}_{k-1}(\langle R \rangle; \mathbb{Z}) = 0$.

**Example 13** For example, when $\langle R \rangle$ is a contractible subcomplex of $\langle S \rangle$ then it satisfies Condition (ii) of Definition 9 as well as the vanishing condition (iv). If it furthermore satisfies Condition (i) of Definition 9, then R becomes a torsion-free S-spanning tree.

A frequent combinatorial setting where this occurs (such as in Proposition 15 below) is when S is the set of facets of a (pure) shellable [3] simplicial complex, and R is the subset of facets which are not fully attached along their entire boundaries during the shelling process.

**Proposition 14** Using the hypotheses and notation of Proposition 11, if one assumes in addition that R is torsion-free, assertion (ii) of Proposition 11 becomes the following assertion about (non-relative) homology:

(ii) When the matrix $\partial$ is nonsingular, then $\mathrm{coker}(\partial) = \tilde{H}_k(K; \mathbb{Z})$

**Proof:** When R is torsion-free, the long exact sequence for the pair $(K, \langle R \rangle)$ shows that $\tilde{H}_k(K; \mathbb{Z}) \cong \tilde{H}_k(K, \langle R \rangle; \mathbb{Z})$. □

<figure><img src="image_4.png" /></figure>

<footnote><sup>(ii)</sup> This condition on an S-spanning tree also plays an important role in [9] by Duval, Klivans and Martin.</footnote>
# 5 More on the complete d-partite complex

It is well-known and easy to see that for a positive integer $n$ having prime factorization $n = p_1^{e_1} \cdots p_d^{e_d}$ with $e_i \ge 1$, one always has $\Phi_n(x) = \Phi_{p_1 \cdots p_d}(x^{n/p_1 \cdots p_d})$. Thus it suffices to interpret the coefficients of cyclotomic polynomials for squarefree $n$.

In this section, we fix such a squarefree $n = p_1 \cdots p_d$, and discuss further properties of the simplicial complexes $K_{p_1, \dots, p_d}$, defined in Section 1, appearing in Theorems 1 and 2.

**Proposition 15** The $(d-2)$-dimensional skeleton of $K_{p_1, \dots, p_d}$ is shellable, with

$$ \tilde{H}_{d-2}(K_{p_1, \dots, p_d}; \mathbb{Z}) = \mathbb{Z}^{n-\phi(n)}. $$

**Proof:** To show that the $(d-2)$-skeleton is shellable, we note the following three facts: (i) zero-dimensional complexes are all trivially shellable, (ii) joins of shellable complexes are shellable [24, Sec. 2], and (iii) skeleta of (pure) shellable simplicial complexes are shellable [5, Corollary 10.12]. Having shown that this skeleton is shellable, it therefore has only top homology; see, for example [3, Appendix]. This homology is free abelian, with rank the absolute value of its reduced Euler characteristic, namely

$$ \begin{aligned} \left| \sum_{i \ge -1} (-1)^i \mathrm{rank}_{\mathbb{Z}}(C_i) \right| &= \left| \sum_{i \ge -1} (-1)^i \sum_{\substack{i \le \{1, 2, \dots, d\} \\ |I|=i+1}} \prod_{i \in I} p_i \right| = \left| \sum_{I \subseteq \{1, 2, \dots, d\}} (-1)^{|I|-1} \prod_{i \in I} p_i \right| \\ &= |(p_1 - 1) \cdots (p_d - 1) - p_1 \cdots p_d| = |\phi(n) - n|. \end{aligned} $$

□

As noted in the introduction, the Chinese Remainder Theorem isomorphism (1) identifies elements of $\mathbb{Z}/n\mathbb{Z}$ with the $(d-1)$-dimensional simplices of $K_{p_1, \dots, p_d}$. Lower dimensional faces of $K_{p_1, \dots, p_d}$ can also be identified as cosets of subgroups within $\mathbb{Z}/n\mathbb{Z}$, but we will use this identification sparingly in this paper. For the sake of writing down oriented simplicial boundary maps, choose the following orientation on the simplices of $K_{p_1, \dots, p_d}$, consistent with the orientation of facets preceding Theorem 2: choose the oriented $(\ell-1)$-simplex $[j_{i_1} \mod p_{i_1}, \dots, j_{i_\ell} \mod p_{i_\ell}]$ with $i_1 < \dots < i_\ell$ as a basis element of $C_{\ell-1}(K_{p_1, \dots, p_d}; \mathbb{Z})$. The following simple observation was the crux of the results in [18].

**Proposition 16** If one identifies the indexing set $\mathbb{Z}/n\mathbb{Z}$ for the columns of the boundary map

$$ C_{d-1}(K_{p_1, \dots, p_d}; \mathbb{Z}) \to C_{d-2}(K_{p_1, \dots, p_d}; \mathbb{Z}) \quad (5) $$

with the set $\mu_n := \{\zeta^j\}_{j \in \mathbb{Z}/n\mathbb{Z}}$ of all $n^{th}$ roots of unity, then every row of this boundary map represents a $Q$-linear dependence on $\mu_n$.

**Proof:** A row in this boundary map is indexed by an oriented $(d-2)$-face, which has the form

$$ [j_1 \mod p_1, \dots, j_k \mod p_k, \dots, j_d \mod p_d] $$

for some $j_k \in \{0, 1, \dots, p_k - 1\}$ and $1 \le k \le d$. This row will contain mostly zeroes. Its non-zero entries are all $(-1)^{k-1}$, and lie in the columns indexed by those $\zeta^j$ having $j \equiv j_i \mod p_i$ for $i \ne k$, and $j \mod p_k$ arbitrary. These exponents $j$ are exactly those lying in one coset of the subgroup $p_1 \cdots \hat{p}_k \cdots p_d \mathbb{Z}/n\mathbb{Z}$ within $\mathbb{Z}/n\mathbb{Z}$. Summing $\zeta^j$ over $j$ in such a coset gives zero. □
**Example 17** Let $n = 15$ as in Example 3, and consider the matrix for the simplicial boundary map $C_1(K_{3,5}; \mathbb{Z}) \to C_0(K_{3,5}; \mathbb{Z})$. One of its rows is indexed by the 0-face $[2 \mod 5]$ and this row has exactly three nonzero entries, all equal to $(-1)^0 = +1$. To see these signs, we rewrite $[2 \mod 5]$ in three ways, all of which involve deleting the first entry out of two in an oriented 1-face:

$$ [2 \mod 5] = [0 \mod 3, 2 \mod 5] = [1 \mod 3, 2 \mod 5] = [2 \mod 3, 2 \mod 5]. $$

The columns corresponding to these three 1-faces are indexed by the roots of unity $\zeta^{12}$, $\zeta^7$, and $\zeta^2$, respectively. Summing these up with coefficients of positive one, we get

$$ 1 \cdot \zeta^{12} + 1 \cdot \zeta^7 + 1 \cdot \zeta^2 = \zeta^2(\zeta^{10} + \zeta^5 + 1), $$

which is the sum of $\zeta^j$ over $j$ lying in a coset of $5\mathbb{Z}/15\mathbb{Z}$, and hence is zero.

**Definition 18** Assume that $n$ is squarefree and let $T$ denote any set of $n - \phi(n)$ columns of the boundary map (5). Identify the complementary set $T^c$ of $\phi(n)$ columns with a subset of the $n^{th}$ roots-of-unity $\mu_n$. Create a subcomplex of $K_{p_1, \dots, p_d}$ by including its entire $(d-2)$-skeleton and attaching the subset of $(d-1)$-faces indexed by $T$. We denote this subcomplex as $K[T]$.

With this definition in mind, we will make use of an interesting feature of this labelling of the boundary map and the set $P_n$ of primitive $n^{th}$ roots of unity, noted already in [18, Remark 5]. For this next result, we let $P_n^c$ denote the $(n - \phi(n))$-element subset of $\mu_n$ indexed by the $n^{th}$ roots of unity which are not primitive.

**Proposition 19** Let $n$ be a squarefree integer and $P_n^c$ be as above. Then the subcomplex $K[P_n^c]$ of $K_{p_1, \dots, p_d}$ is contractible.

**Proof:** Observe that the primitive roots in $\mathbb{Z}/n\mathbb{Z}$ are exactly those elements which do not vanish modulo $p_i$ for $i = 1, \dots, d$. Tracing through the labelling of the $(d-1)$-faces via $\Xi$, we obtain the description

$$ K[P_n^c] = \bigcup_{i=0}^{d} \mathrm{star}_{K_{p_1, \dots, p_d}} (0 \mod p_i), $$

where $\mathrm{star}_{\Delta}(v)$ denotes the simplicial star of the vertex $v$ inside a simplicial complex $\Delta$. Furthermore, each intersection of these stars is nonempty and contractible, because it is the star of another face: for $I \subset [d]$,

$$ \bigcap_{i \in I} \mathrm{star}_{K_{p_1, \dots, p_d}} (0 \mod p_i) = \mathrm{star}_{K_{p_1, \dots, p_d}} (\{0 \mod p_i\}_{i \in I}). $$

A standard nerve lemma [4, Theorem 10.6] then shows that $K[P_n^c]$ itself is contractible. $\square$

**Theorem 20** Let $n$ be a squarefree integer and $T$ be a subset of $\mu_n$ of size $n - \phi(n)$. Let $K[T]$ be the subcomplex of $K_{p_1, \dots, p_d}$ of Definition 18. Then

$$ \tilde{H}_i(K[T]; \mathbb{Z}) \cong \begin{cases} \mathbb{Z}[\zeta]/\mathbb{Z}T^c & \text{if } i = d-2, \\ \mathbb{Z} & \text{if both } i = d-1 \text{ and } \mathrm{rank}_{\mathbb{Z}}(\mathbb{Z}T^c) < \phi(n), \\ 0 & \text{otherwise.} \end{cases} $$

where $\mathbb{Z}T^c$ is the sublattice $\mathbb{Z}$-spanned by the roots-of-unity $T^c \subset \mu_n$.
**Proof:** Choose any $\mathbb{Z}$-basis for $\mathbb{Z}[\zeta]$. Let $M$ in $\mathbb{Z}^{\phi(n)\times n}$ be the matrix that expresses the $n^{th}$ roots of unity $\mu_n$ in this basis. We construct a particular matrix $M^{\perp}$ to accompany $M$ as in Proposition 7 part (ii). Consider the collection $S$ of all $(d-2)$-faces in the complete $d$-partite complex $K_{p_1, \dots, p_d}$. The complex $\langle S \rangle$ generated by $S$ is therefore the $(d-2)$-skeleton of $K_{p_1, \dots, p_d}$. Proposition 15 implies that $\langle S \rangle$ is shellable, and that it has $\mathrm{rank}_{\mathbb{Z}} \tilde{H}_{d-2}(\langle S \rangle; \mathbb{Z}) = n - \phi(n)$. Therefore, we are in the situation of Example 13, implying that there exists a torsion-free $S$-spanning tree $R$, and any such $R$ will have $|S \setminus R| = n - \phi(n)$.

Our candidate for the matrix $M^{\perp}$ in $\mathbb{Z}^{(n-\phi(n))\times n}$ is the restriction of the boundary map from (5) to its rows indexed by $S \setminus R$. Proposition 16 shows that the rows of $M^{\perp}$ are all perpendicular to the rows of $M$. Now choose $T, T^c$ so that $T^c$ indexes the set $P_n$ of primitive $n^{th}$ roots of unity. Proposition 6 implies that the maximal minor $M|_{T^c}$ of $M$ is invertible over $\mathbb{Z}$, while Proposition 19 implies that the maximal minor $M^{\perp}|_T$ of $M^{\perp}$ is invertible over $\mathbb{Z}$. Thus $M, M^{\perp}$ satisfy the hypotheses of Proposition 7 part (ii), and combining this with Proposition 14 gives the assertion of the theorem. $\square$

# 6 Proof of Theorems 1 and 2

We are now in a position to prove Theorems 1 and 2.

**Proof of Theorem 1:** Let $T^c = \{1, \zeta, \zeta^2, \dots, \zeta^{\phi(n)}\} \setminus \{\zeta^j\}$ so that we have the equality of complexes $K[T] = K[\{\zeta^{\phi(n)+1}, \zeta^{\phi(n)+2}, \dots, \zeta^{n-1}\} \cup \{j\}] = K_j$. The theorem then follows from Theorem 20 and Corollary 5. $\square$

**Proof of Theorem 2:** We prove Theorem 2 by applying Proposition 8 to the matrices $M, M^{\perp}$ in the proof of Theorem 20, with $A = \{1, \zeta, \zeta^2, \dots, \zeta^{\phi(n)}\}$. The dependence (2) among the columns of $M|_A$ has the same coefficients (up to scaling) as the cyclotomic polynomial, and the dependence (3) among the columns of $M^{\perp}|_{A^c \cup \{j, j'\}}$ has the same coefficients (up to scaling) as a nonzero cycle $z = \sum_l b_l [F_l]$ in $\tilde{H}_{d-1}(K_{\{j, j'\}}; \mathbb{Z})$. $\square$

# 7 Concordance with known properties of $\Phi_n(x)$

Here are some results about $\Phi_n(x)$ that manifest themselves topologically. See [22] for details.

1. The two maps $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ that send $\bar{j}$ to $-\bar{j}$ and send $\bar{j}$ to $\bar{j}+1$ generate a dihedral group of simplicial automorphisms of $K_{p_1, p_2, \dots, p_d}$. One such automorphism sends the subcomplex $K_{\{j\}}$ to $K_{\{\phi(n)-j\}}$, and the subcomplex $K_{\{j, \phi(n)\}}$ to $K_{\{0, \phi(n)-j\}}$, explaining the symmetry $c_j = c_{\phi(n)-j}$ in $\Phi_n(x)$.

2. The fact that $\Phi_{2n}(x) = \Phi_n(-x)$ when $n$ is odd manifests itself topologically as follows: the subcomplex $K_{\{j\}}$ whose homology interprets the coefficient of $x^j$ for $\Phi_{2n}(x)$ is homotopy-equivalent to the suspension of the corresponding complex for $\Phi_n(x)$. Furthermore, there is a similar suspension relation between the complexes that predict the coefficients' signs.
3. When $d=2$ so $n = p_1p_2$ is the product of only two primes, all the subcomplexes $K_{\{j\}}$ of $K_{p_1,p_2}$ are graphs. Hence their $(d-2)$-dimensional homology is torsion-free. It follows that the only nonzero coefficients of $\Phi_n(x)$ are $\pm 1$, agreeing with a well-known old observation of Migotti [20]. The explicit expansion of $\Phi_{p_1p_2}(x)$ is given in Elder [10], Lam and Leung [16], and Lenstra [17].

4. In contrast to above, when $d \ge 3$ and the $p_i$'s are odd primes, $\Phi_n(x)$ often has coefficients with absolute value $\ge 2$. For example, $\Phi_{105}(x)$ has coefficient $-2$ on $x^7$ and $x^{41}$. The 2-dimensional subcomplexes $K_{\{7\}}$ and $K_{\{41\}}$, whose 1-homology equals $\mathbb{Z}/2\mathbb{Z}$, turn out to be surprisingly non-trivial. For example, neither one can be collapsed down to a real projective plane.

# 8 Acknowledgements

The authors wish to credit Jeremy Martin for the original observation that the cyclotomic matroid $\mu_n$ with $n = p_1p_2$ is cographic. They also thank Sam Elder, Nathan Kaplan, and Pieter Moree for helpful references on cyclotomic polynomials. This submission is an abridged version of [22]. We thank the referees for helpful editorial suggestions.

# References

[1] R.M. Adin, Counting colorful multi-dimensional trees. *Combinatorica* **12** (1992), 247–260.

[2] G. Bachman, On the Coefficients of Cyclotomic Polynomials *Memoirs of the American Mathematical Society* **106**, 1993.

[3] A. Björner, Shellable and Cohen-Macaulay partially ordered sets. *Trans. Amer. Math. Soc.* **260** (1980), no. 1, 159–183.

[4] A. Björner, Topological methods. *Handbook of combinatorics*, Vol. II, 1819–1872. Elsevier, Amsterdam, 1995.

[5] A. Björner and M. Wachs, Shellable nonpure complexes and posets. II. *Trans. Amer. Math. Soc.* **349** (1997), no. 10, 3945–3975.

[6] E.D. Bolker, Simplicial geometry and transportation polytopes. *Trans. Amer. Math. Soc.* **217** (1976), 121–142.

[7] H.H. Crapo and G.-C. Rota, On the foundations of combinatorial theory: Combinatorial geometries. Preliminary edition. The M.I.T. Press, Cambridge, Mass.-London, 1970.

[8] A.M. Duval, C.J. Klivans, and J.L Martin, Simplicial matrix-tree theorems. *Trans. Amer. Math. Soc.* **361** (2009), no. 11, 6073–6114.

[9] A.M. Duval, C.J. Klivans, and J.L Martin, Critical groups of simplicial complexes. preprint, arXiv:1101.3981

[10] S. Elder, Flat Cyclotomic Polynomials, Colorado Math Circle Talk, January 2, 2010, http://www.coloradomath.org/handouts/flat_cyclotomic.pdf
[11] Y. Gallot and P. Moree, Neighboring ternary cyclotomic coefficients differ by at most one. *J. Ramanujan Math. Soc.* **24** (2009), no. 3, 235248.

[12] K. Johnsen, Lineare Abhängigkeiten von Einheitswurzeln. *Elem. Math.* **40** (1985), 57–59.

[13] G. Kalai, Enumeration of $\mathbb{Q}$-acyclic simplicial complexes. *Israel J. Math.* **45** (1983), 337–351.

[14] N. Kaplan, Flat cyclotomic polynomials of order three. *J. Number Theory* **127** (2007), no. 1, 118–126.

[15] G. S. Kazandzidis, On the cyclotomic polynomial: Coefficients. *Bull. Soc. Math. Gréce* (N.S.) **4** (1963), no. 1, 1–11.

[16] T.Y. Lam and K.H. Leung, On the Cyclotomic Polynomial $\Phi_{pq}(X)$. *Amer. Math. Monthly* **103** (1996), 562–564.

[17] H.W. Lenstra, Vanishing sums of roots of unity, in: *Proceedings, Bicentennial Congress Wiskundig Genootschap, Vrije Univ., Amsterdam, 1978, Part II*, 1979, pp. 249–268.

[18] J. Martin and V. Reiner, Cyclotomic and simplicial matroids. *Israel J. Math.* **150** (2005), 229–240.

[19] M. Maxwell, Enumerating bases of self-dual matroids. *J. Combin. Theory Ser. A* **116** (2009), no. 2, 351–378.

[20] A. Migotti, Zur Theorie der Kreisteilungsgleichung. *Sitzber. Math.-Naturwiss. Classe der Kaiser. Akad. der Wiss.*, Wien **87** (1883), 7–14.

[21] J.R. Munkres, Elements of algebraic topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984.

[22] G. Musiker and V. Reiner, The cyclotomic polynomial topologically. preprint, arXiv:1012.1844

[23] J.G. Oxley, Matroid theory. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.

[24] J.S. Provan and L.J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra. *Math. Oper. Res.* **5** (1980), no. 4, 576–594.

[25] D.J.A. Welsh, Matroid theory. London Math. Soc. Monographs **8**. Academic Press, London-New York, 1976.

[26] N. White, Theory of matroids. *Encyclopedia of Mathematics and its Applications* **26**. Cambridge University Press, Cambridge, 1986.

[27] N. White, Combinatorial geometries. *Encyclopedia of Mathematics and its Applications* **29**. Cambridge University Press, Cambridge, 1987.

[28] N. White, Matroid applications. *Encyclopedia of Mathematics and its Applications* **40**. Cambridge University Press, Cambridge, 1992.

[29] Zhao, Jia; Zhang, Xianke, Coefficients of ternary cyclotomic polynomials. *J. Number Theory* **130** (2010), no. 10, 2223–2237.