Warning to PROMYS students: this blog post contains major spoilers regarding problems 4 and 6 of the Open Door Problem Set. Read at your own risk.
The following problem has appeared as problem P3 on the short exam #2 during PROMYS Europe 2016:
Let with prime. How many irreducible polynomials of degree are there in ?
In part upon request of one of my friends, below I am typing up, verbatim (apart from minor typos), a solution which I have written down during the exam, between the following two horizontal lines. Below I am adding further explanations and comments, for anyone interested.
Let be the number of irreducible polynomials in of degree . I’ll show , so, by Möbius inversion, .
Let be the algebraic closure of and let be the set of roots of in . Since , all the roots are distinct. Using and, by induction, , we see is closed under addition, multiplication, nonzero inverses and contains , so is a field. Indeed, this is the unique subfield of of size : if was another such field, we see all its nonzero elements satisfy , so all the elements satisfy , thus , hence, by considering size, . Last but not least, iff : indeed, any solution of also solves , for all , so , and if , then is a finite-dimensional vector space over , so for some , i.e. .
Finally, let be irreducible of degree . Any of its roots generates an extension of of degree , i.e. . In particular, all roots of lie in . As a lemma below I show has no multiple roots, so roots of are distinct roots of , so . Thus, for any , . Conversely, if , its roots generate a subfield of of size , so . Thus, since is squarefree, we get that is precisely the product of monic irreducible polynomials of degrees dividing . Comparing degrees, .
Lemma: irreducible has no multiple roots.
Proof: Otherwise, . But is irreducible, so , hence . Thus all powers of with nonzero coefficient in have exponent divisible by , say . But then , contradicting irreducibility.
First, a remark – the above solution actually establishes the number of monic irreducible polynomials of given degree. In some sense, counting the monic ones is more natural, just like in we usually count just the positive primes, even though their additive inverses “should” count as primes just as well. Anyways, to get all irreducible polynomials, we just need to multiply by the number of possible leading coefficients – .
Some of the notions I’ve used in the solution require more explanation than others (for example because they extend beyond the scope of material on PROMYS). I’ll explain them in an order deviating from the order in which they appear in the solution.
First of all, note that I have used notation in place of . Right now I remark that these mean precisely the same thing. There are at least three reasons why I prefer this notation. Firstly, has another, contradicting, meaning in number theory, namely it often denotes the ring of all -adic integers. Secondly, it emphasizes that is a field – for general “modulo” rings my prefered notation is , which I would probably use if I’ve only cared about ring structure, but I wouldn’t ever write , since there is no field with elements. This brings me to the third point – we can generalize this notation to denoting the field with elements, which it can’t be done with notation, since it already denotes . By the way, I say “the field with elements”, because it can be shown that there is precisely one such field, provided there is one. By the way, there is a neat characterization of sizes of finite fields – for any prime power there is precisely one field of size , and no such field for other . If we take existence of algebraic closure (which I discuss below) for granted, the solution gives us a construction of such field, but it’s quite instructive to try to prove this directly.
At one point I have mentioned a “finie-dimensional vector space”. A vector space over a field is, in nontechnical terms, a set of elements, called vectors, such that we can add any two vectors and we can multiply a vector by an element of in a way such that familiar properties such as commutativity, associativity and distributivity hold. A very important concept regarding a vector space is its dimension, which is, essentially, the least number of vectors needed to express all vectors in using these vectors, addition and multiplication by elements of . We call the space finite-dimensional if this dimension is finite. These notions are central to linear algebra, which is the study of these spaces, as well as transformations between them.
An important example of a vector space in algebra is any field extension, i.e. any pair of fields . can then be considered as a vector space over – we can add any two elements of , and we can multiply an element of by an element of (we are “forgetting” that we can multiply arbitrary elements of when we think of it as of a vector space). In this scenario, there is another name for the dimension – we call it the degree of the extension. In case both are finite, there is a neat formula relating degree and their sizes: if we denote by the degree of this extension, then . This is where the part “ for some ” comes from.
It is a well-known fact, and it’s moderately easy to establish, that if is a root of irreducible polynomial in of degree , then the degree of extension , constructed by adjoining to , is equal to (note that this relates the two notions of “degree” we know – degree of a polynomial and degree of an extension). We can explicitly point out a minimal generating set – just take .
Now let me say a few words about algebraic closure of a field . It is a field extension which has two defining properties: first, every nonconstant polynomial in must have a root in (this is known as an algebraically closed field); second, every element of must be a root of a nonzero polynomial from in . An example will nicely illustrate it: Consider first . The famous fundamental theorem of algebra states that every nonconstant polynomial with complex coefficients has a complex root, that is, is algebraically closed. Moreover, any complex number is a root of a polynomial with real coefficients. This means precisely that . However, isn’t the algebraic closure of, say, , because there are complex numbers (called transcendental numbers) which aren’t roots of nonzero polynomials with rational coefficients.
It can be shown that any field has a unique algebraic closure (hence we can speak of the algebraic closure). However, we don’t need exactly that. Note that in the proof we have only used the fact that any polynomial from has all its roots, i.e. factors into linear factors, in . Hence, any algebraically closed field containing would work for our purposes.
While we are speaking about polynomials, let’s take a minute to appreciate usefulness of derivatives. Their analytic definition (as a limit) wouldn’t make sense in most fields (just think about !). Nevertheless, we can still make sense of the notion of derivative by simply giving a formula for it (for this reason, it is often called formal derivative, since, in a way, it’s just manipulating symbols, and we don’t care about any “meaning” (e.g. analytic) of these operations). Derivative “detects” multiple factors of a polynomial. To be precise, if a polynomial divides , then also divides , and hence . In particular, if are relatively prime, then has no square factors, i.e. is squarefree. As a special case of this we can deduce that if , then has precisely roots in a field extension in which it has all its roots, which we have used in case of .
I also wanted to mention, even though it is within the scope of PROMYS, the Möbius inversion formula. If we take a function defined on natural numbers and then define a function , then there is, a priori, not much reason to expect that can be expressed in terms of in a simple way. But nevertheless there is – defining the Möbius function by if is a product of distinct primes and if has a square factor, we have the identity if and for , we can extract using the mentioned inversion formula: . This can be far generalized during the notion of Dirichlet convolution, but this is one wide topic by itself.
One last remark I’d like to make is to relate this topic to an earlier post I made, about Riemann hypothesis for polynomials over a finite field. Since standard Riemann hypothesis gives us tight bounds on the number of primes up to given order, we should expect something like that to work for irreducible polynomials. Indeed, from the derived formula we get . Since no appearing that new sum will be greater than , we can bound this difference in absolute value by for some constant . This is, more or less, on the same order of magnitude as the error predicted by the Riemann hypothesis in integers case. One can wonder however, why we don’t have a tighter bound – after all, polynomial zeta function has no zeros. The reason for that can be actually traced back to the inversion formula, but this is far beyond the scope of this discussion.
Further explanations already took me over twice as much as the solution itself, so I guess it’s a good time to end the post. Most of the explanations were at least in part superficial, so I don’t expect everyone to understand everything after reading it once. I will be happy to discuss any of the parts of the topic with anyone interested.
I will leave you with a question which you can try to answer yourself, to see how well you understand the topic (some food for thought, one could say): as discussed above, we also have finite fields for not necessarily a prime. Does the derived formula for the number of irreducible polynomials hold in this case? More importantly, does the proof of this formula work? Can you generalize?