Tag Archives: mobius inversion

An alternate characterization of cyclotomic polynomials

Prove that \Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}, where \Phi_n is the nth cyclotomic polynomial and \mu is the Möbius function on \mathbb{N}^+ defined by \mu(1) = 1, \mu(m) = (-1)^r if m is squarefree with r distinct prime factors, and \mu(m) = 0 if m is divisible by a square.

[I consulted this document from the Berkeley Math Circle when preparing this solution.]

Before we approach this (seemingly magical) identity, let’s build up some machinery.

Given an abelian group A, let A_0^\mathbb{N} denote the set of all functions \mathbb{N}^+ \rightarrow A. Recall that A^\mathbb{N}_0 is itself an abelian group under pointwise addition.

Now let R be a commutative ring with 1 and let M be a left R-module. Define an operator R_0^\mathbb{N} \times M_0^\mathbb{N} \rightarrow M_0^\mathbb{N} by (f \ast_{R,M} g)(n) = \sum_{st=n} f(s) g(t). Note that since n is positive, this sum is finite, and that s and t are nonzero. We will usually drop the subscripts on \ast. This operator is called the Dirichlet convolution of f and g.

Lemma 1: Let f,g \in R^\mathbb{N}_0 and h \in M^\mathbb{N}_0. Then f \ast_{R,M} (g \ast_{R,M} h) = (f \ast_{R,R} g) \ast_{R,M} h. Proof: We have

(f \ast (g \ast h))(n)  =  \sum_{st=n} f(s)(g \ast h)(t)
 =  \sum_{st=n} f(s) \sum_{uv=t} g(u)h(v)
 =  \sum_{st=n} \sum_{uv=t} f(s)g(u)h(v)
 =  \sum_{suv=n} f(s)g(u)h(v)
 =  \sum_{tv=n} \sum_{su=t} f(s)g(u)h(v)
 =  \sum_{tv=n} (\sum_{su=t} f(s)g(u)) h(v)
 =  \sum_{tv=n} (f \ast g)(t)h(v)
 =  ((f \ast g) \ast h)(n)

As desired. \square

Lemma 2: Let f,g \in R^\mathbb{N}_0 and h,k \in M^\mathbb{N}_0. Then (using pointwise addition) we have (f+g) \ast h = (f \ast h) + (g \ast h) and f \ast (h + k) = (f \ast h) + (f \ast k). Proof: We have

(f \ast (h+k))(n)  =  \sum_{st=n} f(s)(h+k)(t)
 =  \sum_{st=n} f(s)(h(t)+k(t))
 =  \sum_{st=n} f(s)h(t) + \sum_{st=n} f(s)k(t)
 =  (f \ast h)(n) + (f \ast k)(n)
 =  ((f \ast h) + (f \ast k))(n)

as desired. The other equality is analogous. \square

Corollary 1: R^\mathbb{N}_0 is a ring with pointwise addition and Dirichlet convolution, and M^\mathbb{N}_0 is a left R^\mathbb{N}_0 module via Dirichlet convolution. Proof: Follows from Lemmas 1 and 2. \square

Let \delta_{1,n} denote the Kronecker delta (whose value is 1 if n=1 and 0 otherwise) and let \mu : \mathbb{N}^+ \rightarrow R be the Möbius function.

Lemma 3: For all g \in R^\mathbb{N}+0, \delta_{1,n} \ast g = g. Proof: We have (\delta_{1,n} \ast g)(n) = \sum_{st=n} \delta_{1,s}g(t). Now the delta function is 0 unless s = 1, in which case t = n, and so this sum is precisely g(n) as desired. \square

Now let 1 denote the constant function whose value is 1.

Lemma 4: \mu \ast 1 = \delta_{1,n}. Proof: We have (\mu \ast 1)(n) = \sum_{st=n} \mu(s)1(t) = \sum_{s|n} \mu(s). If n = 1, then we have (\mu \ast 1)(1) = \delta_{1,1}. Now suppose n = p_1^{e_1} \cdots p_k^{e_k}, with the p_i prime. Now s = p_1^{d_1} \cdots p_k^{d_k}, where 0 \leq d_i \leq e_i. Note that if any d_i is greater than 1, then (by definition) \mu(s) = 0. So the only summands which contribute to (\mu \ast 1)(n) those with d_i \in \{0,1\}. Moreover, in this case, the value of \mu(s) depends only on whether the number of nonzero d_i is even or odd. There are 2^k subsets of \{1,\ldots,k\}, half of which have an even number of elements and half odd. So \sum_{s|n} \mu(s) = \sum_{S \subseteq \{1,\ldots,k\}} (-1)^{|S|} = 0. Hence \mu \ast 1 = \delta_{1,n}. \square

Now given f : \mathbb{N}^+ \rightarrow M, define F = 1 \ast f– so F(n) = \sum_{d|n} f(d). Then \mu \ast F = (\mu \ast 1) \ast f = f.

Now let M be the abelian group F(x)^\times. (The nonzero rational functions over F in one variable). This is an abelian group, hence a \mathbb{Z}-module, where we write our operator multiplicatively and our \mathbb{Z}-action by exponentiation. Let f : \mathbb{N}^+ \rightarrow M be given by f(n) = \Phi_n(x), and let F(n) = (1 \ast f)(n) = \sum_{d|n} \varphi_n(x) = x^n-1. Now \mu \ast F = f, which expanded out gives the identity \Phi_n(x) = \prod_{st=n} (x^s-1)^{\mu(t)} as desired.