# Counting total number of monic irreducible polynomials of all degrees $k$ that divide $m$.

Why is the following relation counting monic irreducible polynomials of all degrees $d$ that divide $m$ true?

$$\sum_{d\ |\ m}\left(\frac{1}{d} \sum_{c\ |\ d} \mu(d/c)\ p^{c}\right) = \frac{1}{m} \sum_{d\ |\ m} \phi\!\left(\frac{m}{d}\right)\ p^{d},$$

where $\mu(n)$ is the Möbius function and $\phi(n)$ is Euler's totient function.

Background: one can express the degree of the polynomial $x^{p^m}-x$ over $\mathbb{F}_{p}$ ($p$ = prime) as the sum of the degrees of the monic irreducible factors of $x^{p^m}-x$ as $$$$p^m = \sum_{d\ |\ m} d\ I_d,$$$$ where the sum runs over all divisors $d$ of $m$, and $I_d$ is the number of minimal polynomials of degree $d$ which are factors of $x^{p^m}-x$.

By Möbius inversion on gets the number of monic irreducible polynomials of degree $m$ as, $$I_m =\frac{1}{m} \sum_{d\ |\ m} \mu(d)\ p^{m/d}= \frac{1}{m} \sum_{d\ |\ m} \mu\!\left(\frac{m}{d}\right)\ p^{d}.$$

Now, if I sums up the monic irreducible polynomials of all degrees $d$ that divide $m$ one has, $$\sum_{d\ |\ m} I_d =\sum_{d\ |\ m}\left(\frac{1}{d} \sum_{c\ |\ d} \mu(d/c)\ p^{c}\right) = \frac{1}{m} \sum_{d\ |\ m} \phi\!\left(\frac{m}{d}\right)\ p^{d},$$ where $\phi(n)$ is Euler's totient function counting the number of integers less than $n$ that are relatively prime to $n$ given by, $$\phi(n) = |{\{0 \leq i < n\ | \gcd(i, n) = 1\}}|.$$

I verified the above relation in Matlab. I initially thought that $\sum_{d\ |\ n} \phi(d) = n$ would be of help, but could not come up with a decent proof. Any suggestions are greatly appreciated. Thanks.

Let's start from :

$$\sum_{d\ |\ m} I_d =\sum_{d\ |\ m}\left(\frac{1}{d} \sum_{c\ |\ d} \mu(d/c)\ p^{c}\right)=\sum_{d\ |\ m} \sum_{c\ |\ d} \left(\frac{1}{d}\mu(d/c)\ p^{c}\right)$$

Then invert the double sum (change of variable $(d,c)\mapsto(c,\frac{d}{c})=(c,e)$), you get

$$\sum_{d\ |\ m} \sum_{c\ |\ d} \left(\frac{1}{d}\mu(d/c)\ p^{c}\right)=\sum_{c\ |\ m} \sum_{e\ |\ \frac{m}{c}} \left(\frac{1}{ce}\mu(e)\ p^{c}\right)$$

$$\sum_{d\ |\ m} I_d =\sum_{c\ |\ m}\frac{p^c}{c} \sum_{e\ |\ \frac{m}{c}} \left(\frac{\mu(e)}{e}\right)$$

Now this is a well known result that :

$$\phi(n)=\sum_{d\ |\ n}\mu(d)\frac{n}{d}$$

It is just the Moebius formula applied to the identity (you gave us) :

$$\sum_{d\ |\ n}\phi(d)=n$$

So we see in particular that :

$$\sum_{e\ |\ \frac{m}{c}} \left(\frac{\mu(e)}{e}\right)=\frac{c}{m}\sum_{e\ |\ \frac{m}{c}} \left(\mu(e)\frac{m}{ce}\right)=\frac{c}{m}\phi(\frac{m}{c})$$

Finally :

$$\sum_{d\ |\ m} I_d =\sum_{c\ |\ m}\frac{p^c}{c}\frac{c}{m}\phi(\frac{m}{c})=\frac{1}{m}\sum_{c\ |\ m}p^c\phi(\frac{m}{c})$$

• That's great. Didn't think of switching the summation order around. Thanks a lot. – user1657446 Mar 25 '15 at 15:22