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

\begin{equation} \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}, \end{equation}

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 $$ \begin{equation} p^m = \sum_{d\ |\ m} d\ I_d, \end{equation} $$ 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, \begin{equation} 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}. \end{equation}

Now, if I sums up the monic irreducible polynomials of all degrees $d$ that divide $m$ one has, \begin{equation} \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}, \end{equation} where $\phi(n)$ is Euler's totient function counting the number of integers less than $n$ that are relatively prime to $n$ given by, \begin{equation} \phi(n) = |{\{0 \leq i < n\ | \gcd(i, n) = 1\}}|. \end{equation}

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})$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.