## Tag Archives: mobius function

### 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 $n$th 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.