9
$\begingroup$

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.

  • 0
    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.2012-03-29

1 Answers 1

7

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.

  • 0
    @Huy, I'm afraid I cannot read your teachers mind. It does sound like you will be seeing more of generating functions. Another possibility is that your teacher was specifically told not to do enough algebra to settle this question by other means, and consequently s/he had very few choices in how to convince you the students that this is always possible.2012-03-30