Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p[x]$

In an optional course called "Finite Geometries", we most recently constructed the fields $$K_{p,n}[x] := \{\alpha \in K_p[x]\,| \deg(\alpha) < n\},$$ where $K = \mathbb{Z}$, $p$ is prime and $n \in \mathbb{N}$. To do this, we defined the addition as usual whereas for the multiplication we let $\varphi \in K_p[x]$ be an irreducible polynomial of $n$-th degree and then defined $$\alpha \odot \beta := \alpha \cdot \beta \text{ mod } \varphi.$$ Now, as it is not obvious that for every $n \in \mathbb{N}$ there exists such an irreducible polynomial, we proved this for $n \geq 2$ (for $n=1$ the field is simply $(K_p, +, \cdot)$) using a lot of yet unknown tools.

Let $F = \{\phi_1, \phi_2, ...\}$ be a countable set and for every $i \in \mathbb{N}$ let $m_i \in \mathbb{N}$ be the so called "index" of $\phi_i$. We write $m_i = \operatorname{ind}(\phi_i)$. For all $m \in \mathbb{N}$, let $|\{i: m_i = m\}| < \infty$. Then, we call $$\varphi(z) := \sum_{\phi_i \in F} z^{m_i}$$ the counting power-series (is this the correct english term?) of $F$. Obviously, the coefficient of $z^m$ in $\varphi(z)$ is just $|\{i: m_i = m\}|$. For two such sets $F_1 = \{\phi_1, ...\}$ and $F_2 = \{\psi_1, ...\}$ with indices $m_i$ and $n_j$ and counting power-series $\varphi_1(z)$ and $\varphi_2(z)$, we find that the counting power-series for $F_1 \times F_2$ is simply $\varphi_1(z) \cdot \varphi_2(z)$ if we let the index of $(\phi_i, \psi_j)$ be $m_i + n_j$.

Now let $F^{(n)}$ be the set of normed irreducible polynomials of $n$-the degree in $K_p[x]$ and let $f_n = |F^{(n)}|$. We write $F^{(n)} = \{\phi_1^{(n)}, ..., \phi_{f_n}^{(n)}\}$ and for $\phi_j^{(n)} \in F^{(n)}$ let $$F_j^{(n)} = \{1, \phi_j^{(n)}, \phi_j^{(n)} \cdot \phi_j^{(n)}, ...\}.$$ Also, let $\operatorname{ind}(\phi_j^{(n)}) = n$. Then, the counting power-series of $F_j^{(n)}$ is $$\varphi_j^{(n)} = 1 + z^n + z^{2n} + ... = \frac{1}{1-z^n}.$$

Question 1: Why is $\operatorname{ind}(\phi_j^{(n)} \cdot \phi_j^{(n)}) = 2n$? We have only defined the index for $\phi_j^{(n)}$ and we have not defined that index-function to have any special properties, so how can one obtain indices for all the other elements of this set?

Next we define $$F := \{\phi \in F_1^{(1)} \times ... \times F_{f_1}^{(1)} \times F_1^{(2)} \times ... |\; \text{only finitely many factors of } \phi \text{ are} \neq 1\}.$$

This set is bijective to the set of all normed polynomials in $K_p[x]$.

Question 2: What does it mean if only finitely many factors are $\neq 1$ and how is this set bijective to the set of all normed polynomials in $K_p[x]$?

The counting power-series of $F$ is the product of the counting power-series of its factors, i.e. $$\varphi(z) = \prod_{n=1}^\infty \left( \frac{1}{1-z^n} \right)^{f_n}.$$ In $K_p[x]$ there are $p^n$ normed polynomials of $n$-th degree, and thus we can also write $$\varphi(z) = 1 + pz + p^2z^2 + ... = \frac{1}{1-pz}.$$

Question 3: What does this summation have to do with $F$ and its power-series?

After this, the writer logarithmically derives both expressions for $\varphi(z)$ and after a few transformations, he arrives at $$\sum_{n=1}^\infty \left( \sum_{d \mid n} d f_d\right) z^{n-1} = \sum_{n=1}^\infty p^n z^{n-1}$$ which can be solved using Möbius-inversion. Then, we eventually have $$n f_n = p^n + ... + \mu(n) p = p^m ( p^{n-m} + ... \pm 1),$$ where both factors cannot be $0$ and thus for all $n \in \mathbb{N}$ we have $f_n \neq 0$.

Question 4: I don't understand this last step. What is $m$? Why is the bracket $\neq 0$?

Thanks you in advance for helping me understand this proof.

• Start with nitpicking. The elements of $K_{p,n}[x]$ are usually not polynomials of $x$ but rather cosets of the ideal generated by $\varphi$. True, within each coset there is a unique polynomial of degree $<\deg\varphi$. Much like the elements of, say $\mathbb{Z}_5$ are not the integers $0,1,2,3,4$ but rather the cosets $k+5\mathbb{Z}, k=0,1,2,3,4$. It is standard abuse to equate such cosets with a 'small' representative, but early on it is best to be aware of the distinction. When it becomes second nature, you can ignore it. – Jyrki Lahtonen Mar 29 '12 at 9:51
• What is your definition of index? Oh, I see, that is part of your problem. Hmmm... Apropos, I'm not positive about it, but I suspect that the counting power series is often called an enumerating power series (or a generating function). – Jyrki Lahtonen Mar 29 '12 at 9:54
• @Jyrki: Regarding your first comment, I have no idea what an ideal is, so I can't really follow. Regarding your second comment, we have not anywhere defined an "index" except in this proof (if this is considered a definition). I understood if to be some integer assigned to an element of a set. – Huy Mar 29 '12 at 9:56
• Ok. I think I'm beginning to understand how your teacher does this. What you call a normed polynomial is more often called monic, i.e. a polynomial with leading coefficient equal to 1. Indeed, in this context the index of a monic polynomial is simply defined to be its degree. When describing the enumerating power series in a more general setting, you teacher leaves index undefined early on, but when s/he uses it on the problem at hand, index = degree. – Jyrki Lahtonen Mar 29 '12 at 10:05

Q1: Your teacher left the index undefined early on, but later context reveals that the index of a monic polynomial is most likely intended to be equal to its degree. S/he may be planning on using similar generating functions later on, and gave a more general definition for starters.

Q2: The context here is that in the ring $K_p[x]$ we have unique factorization. In other words, every monic polynomial $\phi(x)\in K_p[x]$ can be written as a product of powers of irreducible monic polynomials $\phi_i(x)$ in an essentially unique way in the form $$\phi(x)=\prod_i \phi_i(x)^{n_i}.$$ There are infinitely many irreducible polynomials $\phi_i(x)$ (Have you shown this in class? The usual proof about the infinitude of the set of prime numbers works for polynomials also!). But because $\phi(x)$ has a finite degree, only finitely many irreducible polynomials $\phi_i(x)$ can appear as factors here. Therefore only finitely many exponents $m_i$ are non-zero. Compare integer factorization of $n$: $$n=\pm\prod_ip_i^{m_i},$$ where $p_i$ are all primes. There also only finitely many exponents $m_i$ are non-zero. Namely those, where the corresponding prime $p_i$ is a factor of $n$.

Q3: Here we simply count the number of monic polynomials of degree $n$ in two ways. One way is the direct way: $n$ unknown coefficients, $p$ choices for each. The other is to use the factorization of Question 2. The power series keeps track of the degree of the product $\prod_i\phi_i(x)^{m_i}$. We easily see that the degree of that is $\sum_i m_i\deg \phi_i(x)$. Let us fix an irreducible polynomial $\phi_j(x)$. The series $\varphi_j(z)$ related to the set $F_j=\{\phi_j^n\mid n=0,1,\ldots\}$ is then $$\varphi_j(z)=1+z^{m_j}+z^{2m_j}+z^{3m_j}+\cdots,$$ where $m_j$ is the degree of $\phi_j(x)$. Here the term $z^{km_j}$ corresponds to having a factor $\phi_j^k$. Furthermore, $km_j$ is the degree of $\phi_j^k$, so the polynomial $\phi(x)$ with the above factorization will contribute towards the term $z^{\deg f}$ as it should. For example, if $p=3$, and $\phi(x)=(x+1)^3(x^2+1)$, then the irreducible factors $\phi_1(x)=x+1$ and $\phi_2(x)=x^2+1$ appear. From the series $$\varphi_1(z)=1+z+z^2+\cdots$$ we pick the term $z^3$, because $\phi_1$ appeared to the third power in the factorization of $\phi$. From the series $$\varphi_2(z)=1+z^2+z^4+\cdots,$$ we pick the term $z^2$, because $\phi_2$ was a simple factor. From all the other series $\varphi_j(z)$, where $j\neq1,2$ we pick the term $1$, because $\phi_j$ did not appear as a factor of $\phi(x)$. Multiplying all those power series together we get the term $z^3\cdot z^2=z^5$ to represent $\phi$, which is just what we wanted, because the degree of $\phi$ is equal to five. Do this for all the polynomials $\phi$, and you get the result.

Compare this with the Euler product of the $\zeta$-function: $$\zeta(s)=\sum_{n=1}\frac1{n^s}=\prod_{p\ \text{prime}}\frac1{1-p^{-s}}.$$ For example, when $n=72=2^3\cdot3^2$, we get the term $1/72^s$ from the right hand side as follows. $$\frac1{1-2^{-s}}=1+2^{-s}+4^{-s}+8^{-s}+\cdots$$ has the term $1/8^s$. Similarly the series $$\frac1{1-3^{-s}}=1+3^{-s}+9^{-s}+27^{-s}+\cdots$$ has the term $1/9^s$. In the product $$\prod_{p\ \text{prime}}\frac1{1-p^{-s}}=\prod_{p\ \text{prime}}(1+p^{-s}+p^{-2s}+p^{-3s}+\cdots)$$ we get the term $72^{-s}$ if and only if we select the factor $8^{-s}$, when $p=2$, the factor $9^{-s}$, when $p=3$, and the factor $1$, when $p>3$.

Here we are doing something similar: $$\sum_{\phi\in K_p[x],\ \phi\ \text{monic}}z^{\deg \phi}=\prod_{\phi_j\ \text{monic irreducible}}\frac1{1-z^{\deg\phi_j}}.$$ Unique factorization gives both of these power series identities.

Q4: Here $m$ is the smallest factor of $n$ such that $\mu(n/m)\neq1$. It may happen that $m=1$, but we don't know for sure ($n$ may not be square-free). The factor in parentheses is non-zero, because it is an alternating sum of distinct powers of $p$. The largest power cannot be cancelled by lower ones.

• I am not happy with my answer to your Q3. There is a lot going on there, and we don't have enough space here. It is mostly standard generatingfunctionology, but unless you have seen it earlier, your teacher is really pushing hard. If you were to learn about these in a course on (abstract) algebra, there would be easier routes to your destination. – Jyrki Lahtonen Mar 29 '12 at 10:30
• Thank you very much for your answer. For me, questions 1, 2 and 4 are solved now, however, I don't quite understand your answer to my question 3. Also, you seem to use a different notation, e.g. $f_i(x)$, which is very confusing to read, as we already defined $f_n$ to be the amount of monic irreducible polynomials of $n$-th degree... I'm not sure what $\varphi_{f_1}(z)$ means either, could you maybe elaborate or change the notation to ours? Maybe, then I have better chances to understand what's going on. – Huy Mar 29 '12 at 11:49
• @Huy, thanks for the comment. My mistake was that I read both $\varphi$ and $\phi$ as phi, and had problems matching my notation with yours :-). That should be fixed now. I also added more about the analogy with integers and their $\zeta$-function. Hopefully that makes it easier to follow. – Jyrki Lahtonen Mar 29 '12 at 13:05
• I have given your edited response another shot and now I do indeed understand much more. However, I still have a few or say new questions: 1) In your example, did you mean to pick the term $z^3$ because $\phi_1$ appears in the third power and thus we get the term $z^3 \cdot z^2 = z^5$ to represent $\phi$, or am I missing something? 2) I understand that $\frac{1}{1-pz}$ is the generating function belonging to the set of all monic polynomials and $F$ is bijective to that set. However, why can we "just like that" set two generating functions of two bijective sets equal? – Huy Mar 30 '12 at 12:36
• 3) This might be somewhat stupid but as I've never before seen these generating functions: Why exactly do we use the generating functions? What is the motivation? When will I have to use them? I mean, after all these questions and answers I think I might have understood how the proof works but I would never have come up with something even remotely related to these generating functions. However, as they are being used in this proof, I am sure that the teacher might want us to be able to use generating functions on our own to prove things... – Huy Mar 30 '12 at 12:40