Polynomial rings

We have already been familiar with polynomials like or defined on numbers. Actually the concept of polynomials can be extended to rings, where the polynomials also forms a ring and can be studied as a topic of ring theory.

In this text we will first introduce and study the ring properties of polynomials; then we will study the factorization of irreducibility of polynomials over fields; we prove the multiplicative group of every finite field is cyclic, by exploting the factorization of polynomials over fields; finally we will study the irreducibility of polynomials with integer coefficients, dominated by the Gauss's lemma.

Polynomial rings

A polynomial ring over commutative ring ¹ with indeterminate , is defined as a commutative ring (we will verify its ring properties later) with zero , which is also the zero of , obeying the rules and , and with all elements (called polynomials) in the form of:

Each is called the -th term of the polynomial, and the is called the coefficient of the term.

For any two polynomials , let and , since in such way can be padded by , and so does . Their addition and multiplication are defined as:

Under such settings, it's easy to verify their addition and multiplication are commutative, and the additive inverse of each polynomial is , by . More atomically, each term can also be seen as polynomial with all other terms being zero, so that all polynomials are the summation of such polynomials of single term.

With three polynomials , it's easy to verify the associavitity of multiplication and distributivity by:

By now, we've verified against all ring axioms, so it's truly a commutative ring.

Also, it won't be hard to verify that if there's , will also be commutative ring with unity , by just substiting in the multiplication rule and you will derive the property.

Leading coefficient and degree

For each non-zero polynomial , we define the degree such that and . Obviously for any non-zero polynomial . And the coefficient is called the leading coefficient of . If , the polynomial is said to be monic.

Under the polynomial ring over commutative domain , for any non-zero polynomials the leading coefficient of is , which will never be evaluated to . So in the is also a commutative domain, in which there's .

More generally, in polynomial ring , there's , concerning about the possibility of the -th term's being evaluated to . Similarily there's .

Then let's consider the degree of , if we simply let , then for some , there'll be , however , which is a contradiction. To mitigate, we define , such that . A polynomial is constant if its degree is or , and non-constant if its degree is greater than .

In the polynomial ring over integral domain , it's impossible for a non-constant polynomial to be unit. Since if there were , there will be , which is a contradiction.

Ring homomorphism induced by the coefficients

For a polynomial ring over ring , assume is a ring homomorphism, then there's another ring homomorphism induced by , defined by . For some , such fact can be (trivially) verified by:

Inducing ring homomorphisms between polynomial rings can sometimes be useful in proofs, we will see how we can use it just in this text.

Polynomial rings over multiple indeterminates

For a polynomial ring over ring , since the itself is also a commutative ring, we can introduce another indeteminate and define another polynomial ring over ring .

Consider the polynomial ring , and the map defined by , pivoting the summation of s and s. By substituting in the addition and multiplication rules you can easily find a ring homomorphism. And since there's obviously , the is a ring isomorphism and there's . So we can conveniently define polynomial ring over with two indeterminates . For anologous reason we can define polynomial ring over with indeterminates.

(Ir)reducibility of polynomials

We might have been familiar with the factorization of polynomials of numbers in more "elementary" algebra, like we are able to factorize into . A polynomial is said to be reducible if it can be factorize into non-constant polynomials of lower degree, and irreducible otherwise.

Whether a polynomial of numbers is reducible related to the number field we are discussing about, like is irreducible over , but can be factorized into in . And is irreducible over , but can be factorized into in . So when discussing about (ir)reducibility, it's good to provide over what number field the polynomial is (ir)reducible.

Whether a polynomial has a root in the given number field is a good point for interception. It may be hard to find the root of a given equation, but it's quite easy to verify whether a claimed number is a root of an equation. Like one claim that is a root of , we can verify by merely substituting it into the equation. And is reducible over since by the division algorithm of polynomials, we can divide by to obtain the another polynomial such that .

And in ring theory, we will extend and formalize these techniques and concepts from "elementary" algebra, while prodiving a more algebraic view of (ir)reducibility of polynomials.

Division algorithm

We might have been familiar with the division algorithm of polynomials of numbers: if someone claims is reducible by a factor of , we first multiply it by into so that it matches the highest term with the leading coefficient, subtract and continue division on ; again we multiply it by into to match the leading coefficient and subtract it, leaving behind and the division terminates. So by now we know has truly a factor of and can be factorized by . Similarily, we can decline the statement that has a factor of by using the division algorithm.

And in ring theory, we formalize the division algorithm for polynomial rings: for polynomial ring over a field , with polynomials , as input, the division algorithm yields as output such that , through the following steps:

1. Initialize with .
2. If , the algorithm halts.
3. Let , update , and continue on step 2.

As you can see, the leading coefficient of matches up with the leading coefficient of , so each time when we go through step 3, there's , and doing such subtraction makes decrease monotonically. Since is finite, the algorithm is must halt. And each time when gets updated, it converses the constraint that , so it yields the desired answer when it halts.

In this way, we define the division of polynomials, and can verify whether a polynomial is reducible over by provided factor . We write if after going through the division algorithm there's , verifying that is truly a factor of .

Evaluation homomorphisms and roots

Intuitively, given two polynomials , and for some , since the addition and multiplication operations of polynomials in polynomial ring are compatible with the ones in , we should expect that and , where means substituting into the indeterminate . And for some , such intuition can be verified (which is pretty trivial) by:

So the result of adding or multiplying polynomials first, and then subtituting in the value , is indeed the same as substituting in the value first, and then adding or multiplying them. And there's , since can be seen as the closed subfield of constant polynomials, while there're non-constant polynomials in . So the map defined by is a ring homomorphism, which is called the evaluation homomorphism of .

Just like what we've done for polynomials of numbers, we call that is a root of if . Obviously in the kernel of lies all the polynomials that has root .

And it can be proved that : first by is not zero polynomial, we can perform division algorithm for and such that:

And since there's , must be constant polynomial so . By applying the evaluation homomorphism we have , and the only possibility is , so we've proved .

Conversely, if , there's , so there's obviously (and trivially) .

Finally, the polynomial such that has at most roots in : the constant polynomials has no root in if it's not zero; the polynomials of degree are in the form of , whose only root in is ; for the case of polynomial of degree , if there's no root of in , then we are done. Otherwise assume is a root of , and , and by is also a commutative domain, there's , so is a polynomial of degree . We can repeat such process of root excavation until there's some polynomial that has no root in , or we hit the polynomial of degree , so has at most roots in .

Greatest common divisor and Bezout's identity

Similar to the greatest common divisor and Bezout's identity of integers, we can also define the greatest common divisor for polynomials: the greatest common divisor of is monic polynomial such that and . We write for such , and there's:

Although one that are still familiar with Euclidean algorithm will soon notice the division algorithm for integers and the division algorithm for polynomials can be used interchangable: by using the degree of the remainder polynomial in place of the remainder, we create a descending chain and ensure the Euclidean algorithm for polynomial will terminate, and by tweaking the extended Euclidean algorithm to record and matrix-multiply the quotient polynomials in place of quotients we will hopefully obtain the Bezout's identity for polynomials. However, in ring theory, we care more about what does it mean beneath the surface than just evaluating concrete identity for certain polynomials, so in this text, we will show it in some theoretic and non-constructive ways.

To prove, denote the principal ideals generated by and as and , and consider their sum , whose elements are in the form of . Assume is the non-zero monic polynomial of least degree in , and we would like to show it divides every .

First, divide by , and there's:

Noted that and , if is not zero, it will be the non-zero polynomial of least degree in instead of , which is a contradiction. So it's only possible that and . Similarily we can prove , and thus it divides every .

To show is the greatest common divisor, we will show that for any common divisor , . By 's dividing , let , so there's , and thus and is the greatest.

Finally, let's show that as the monic polynomial of least degree is unique. Let's assume there's another monic polynomial of the same degree as , as both are monic, there's , and we have:

And since is non-zero, the polynomial (where is the leading coefficient of ) exists, is a monic polynomial in and with less degree than and 's, which is a contradiction. So it's only possible the case that , and thus is unique.

Since there're no non-zero polynomial with less degree than in , and all polynomials in are divisible by , it's obvious that is actually the principal ideal of . Remember we've proved that in the ring of integers , there's also an analogous property of in polynomial ring over field .

All ideals of polynomial ring over field are principal

Given such similarity in sum of principal ideals between ring of integers and polynomial ring over field , it might be not to our astonishment that all ideals are also principal. And let's show it in this section.

In the first place, the zero ring and the whole rings are principal ideals and , trivially. And for any ideals , just like what we've done before in the proof for ring of integers, pick up any polynomial , there's . Then pickup another , although there's neither guarantee on nor on , but by doing division algorithm , we obtain some such that , and since , we have , with .

So in this way, we still create a monotonically descending chain on degree of polynomials, starting at and capped at . And for the similar rationale we used to show all ideals of ring of integers are principal, all ideals must also be principal.

Please notice that polynomial rings over multiple indeterminates, does not have such property. Like the polynomial ring , consider the sum of principal ideals ideal and the elements inside, it's impossible to find a principal ideal to hold all these elements; on the other hand, given that there's while is not a field, the rationale above is not applicable.

Irreducible polynomials generate maximal ideals

Finally we would like to prove that for ideal , it's maximal iff is irreducible over .

First, assume is maximal but is reducible by , then there's , . And since by are non-constant polynomials, and that , there's , so , which is contradiction to 's being maximal, so cannot be reducible when is maximal.

Then, assume is irreducible but is not maximal by . There must be otherwise . And since (where otherwise there'll be and ), is reducible, which is a contradiction. So is maximal when is irreducible.

For now, we've proved the sufficiency and essentiality between 's being irreducible and 's being maximal.

Existence theorem of primitive roots

The existence theorem of primitive roots states that for every finite field , its multiplicative group is cyclic, whose generator is called the primitive root.

A finite group is actually very special, you see, elements of which forms the additive group, while the remaining elements of which, except for the zero, forms the multiplicative group. A real world example for such a field is , where is prime. Even more specially, Every field of order is isomorphic to . Since the additive group is of prime order, all elements inside the group must be the generator. Among these generators let's pick out specifically, and consider the map defined by : by , and , it's a ring homomorphism, with , and thus a ring isomorphism. In this way, we've proved that all finite fields of order is isomorphic to , and we assign the symbol for denoting such kind of finite fields abstractly.

But our protagonist today is the primitive root, the generator of the multiplicative group. The is the generator of the additive group, but just the identity of the multiplicative group, which fails to generate any element. The existence of the primitive root claims the structure of the multiplicative group can only be cyclic, even though is not necessarily prime; and when , is even impossible to be prime. So how could this happen?

First, by the fundamental theorem of finite abelian group, for , where repeated primes among are allowed, there must be , under group isomorphism , where repetition is allowed among primes .

The is cyclic if there's no factor cyclic -group of repeated prime factors, then the whole is generated by , where is the generator of the corresponding factor group. The solutions to the equation over are elements of , and there're of them. Meantime, all these solutions are distinct roots of . Everything is just working fine so far.

Then, assume is not cyclic, there must be factor cyclic -groups of repeated prime factors. Without losing generality, let's assume it's the case . So the solutions to the equation are the elements of the inner direct product , and there're of them. All these solutions are distinct roots of , but this is a contradiction to what we've proved about polynomial rings over fields so far, since there are at most distinct roots for polynomials of degree over . So in this way it's impossible for to have factor cyclic -group of repeated prime factors, must be cyclic with primitive root .

So all elements in are in the form of where is the primitive root. For any , by the properties of cyclic subgroups, we can easily derive that there're elements of order , where is the Euler totient function.

The proof of the existence theorem of primitive root is an apparent application of the theory of polynomial rings to study properties of the field over which it's built. Such a conclusion will be harder to obtain outside the ring theory, especially when we treat the addition of and the multiplication of as unrelated operations, rather than building a field and polynomial ring over it. So don't be afraid of annexing different properties or even domains of study while studying mathematical objects, the more properties you've excavated, the more tools are at your hands.

Polynomials with integer coefficients

Finally, let's have a look back to , which we may be familiar with but not a polynomial ring over a field. The polynomial ring is special: connected by the Gauss's lemma, the (ir)reducibility of a polynomial with integer coefficient is equivalent to its corresponding primitive polynomial's; and by studying the primitive polynomials, we find the (ir)reducibility of a primitive polynomial over is equivalent to the one over , which is a field instead; we will also develop some criterions for testing whether a primitive polynomial is (ir)reducibile over , like the Eisenstein's criterion, rational root theorem and the reduction modulo- criterion.

Gauss's lemma for primitive polynomials

A primitive polynomial in is a polynomial with coprime coefficients, or explicitly such that . The Gauss's lemma states that the product of primitive polynomials are primitive, and a primitive polynomial can only be factorized into primitive polynomials.

Let's assume that such a primitive polynomial can be factorized into . Assume are primitive but is not primitive, so there's a prime dividing each , consider the leading coefficient , there's either or . But can not divide every coefficients in or , otherwise it contradicts with the presumption that are primitive. Let's be the coefficient such that and . If then , since we pad with for and . So we do for that and . Consider the coefficient of , there's:

So the product of two primitive polynomials can only be primitive.

On the other hand, assume primitive polynomial is factorized into which are not necessarily primitive, let there be and , so there's and , which is a contradiction to 's being primitive.

In this way, we've shown that the product of two polynomials in is primitive iff the factor polynomials are primitive.

Every non-zero polynomial in is associated with a primitive polynomial: for , by picking the greatest common divisor of the coefficients out, such that , obviously is primitive. And if is irreducible over , then must also be irreducible over : otherwise let , so there's . Iteratively pick up the least prime factor , where there must be either or , and divide it from both and the one of that's divisible by (if both are divisible by , divide by ). In the end, there must be , otherwise is not primitive, or the product of two primitive polynomial is not primitive, both of which are contradictions. But will be reducible instead, which is also a contradiction. Conversely, when is reducible by , is also reducible by , and there may be many other pairs of factor polynomials. So 's reducibility in is equivalent to 's reducibility in , and by study the reducibility of primitive polynomials in , we also study the reducibility of arbitrary polynomial in ².

Gauss's lemma for reducibility in rational numbers

When extending to , it seems to give us some kind of freedom, you know, we can do division as we wish now. But for the primitive polynomials, Gauss's lemma states that a primitive polynomial is reducible in iff it's reducible in . So the factorization of primitive polynomial does not gain from the freedom of division of rational numbers.

Let's move a step closer, for a factorization of primitive polynomial in , into , there're infinitely many pairs of equivalent factorization, given by . Among these factorizations, there must be a that are all primitive. But how can this happen?

To prove, we must first show that polynomial can be fixed into the product of reduced fraction and primitive polynomial .

The procedure is actually pretty intuitive: first we extract their denominators out, by ; then we extract their greatest common divisor out, and let , there's where is primitive by ; finally we reduce the fraction into so that and now we are done.

Back to the Gauss's lemma we are to prove, let , where are reduced fractions and are primitive polynomials, are the factorization of a primitive polynomial . We can furtherly reduce into reduced fraction so that there's .

If , then and we are done; if , then by , is not a primitive polynomial, which is a contradiction; if , then by the coefficients in are integers, but is primitive, which is also a contradiction. So the only possible case is , which indicates for any factorization of primitive polynomial , we can fix into , that are reduced fractions, and are primitive polynomials, with .

Conversely, the factorization of primitive polynomial is trivially a factorization in by . So a primitive polynomial is reducible in iff it's reducible in .

So the reducibility of primitive polynomial over and are just the same problem. But since is a field while is just an integral domain, and is bigger than , we will refer to polynomials' reducibility over indefinitely.

Eisenstein's criterion

The Eisenstein's criterion is an essential condition for a primitive polynomial to be reducible. It states that a primitive polynomial is irreducible over when but .

To prove, assume is reducible over by . The crucial part is, by but , it's either or . Assume it's the former case. And by , there's both . So we must be able to find a coefficient such that but . Consider the coefficient , there's , which is a contradiction. So is irreducible in such circumstance.

To apply the Eisenstein's criterion, we usually evaluates the greatest common divisors of coefficients except the leading coefficient, and iterate through primes , if there's any fulfiling the Eisenstein's criterion, the polynomial is irreducible over then.

Recall the interesting cyclotomic polynomials we've used in the proof of Wedderburn's little theorem. We've proved that cyclotomic polynomials are polynomials with integer coefficients. And we can prove that is irreducible over , using the Eisenstein's criterion.

Although the coefficients of are all s, we can study the reducibility of instead if we notice the reducibility of and are interchangeably equivalent: for each factorization , by some simple changes-of-variables, there's and ; we can convert each factorization of into factorization of , by using the same technique.

By binomial theorem, there's:

Where there's , and . So fulfils the Eisenstein's criterion, is irreducible over , and so does .

Rational root theorem

Another direct consequence from the Gauss's lemma is the rational root theorem: for a polynomial with integer coefficients , and a reduced fraction , if , then and .

First, pick out the greatest common divisor of the coefficients of , so that and is the primitive polynomial. By , is reducible over by , and thus over . It's a good thing that is primitive, and by the proof of Gauss's lemma, we know over .

Then, assume where is also primitive, so there's and , and thus and , and so does for and .

While the proof is utterly simple and direct, this theorem serves as an efficient tool to judge whether an equation has rational roots. Since when there's any rational root for polynomial , there must be , we just need to iterate through all factors and of and , reduce them by , and see whether is divisible by of . If none of the combinations yields a or that divides , then has no root in (although it may still be reducible over , but just by polynomials of degree higher than ).

In fact, when a polynomial of degree is reducible, it must only be reduced into factor polynomials; if a polynomial of degree is reducible, it must only be reduced into or factor polynomials, where each summand corresponds to the degree of the factor polynomial. Since the factor polynomial of degree is inevitable in these cases, the rational root theorem serves as the sufficient and essential condition of polynomials of degree or 's reducibility over .

Reduction modulo prime criterion

Since there's ring homomorphism defined by natural homomorphism of where is prime, induced by we can define the ring homomorphism . For a primtive polynomial reducible by , since are primitive, there's no prime dividing all coefficients of at once, so are just non-zeroes, and there's .

The is reducible over when there're both , but although we prevent from annihilating to zeroes, we don't prevent the leading coefficient of diminishing to zero modulo-, and even from diminishing to constants, in which case is not simply reducible by . But luckily, if the leading coefficient of or would be annihilated modulo-, there's either or , both indicates that . Conversely, if , by Euclid's lemma there's either or .

So for any primitive polynomial and , if is reducible over , then it's reduced modulo- image is reducible over . Equivalently, if there's some such that the reduced modulo- image is irreducible over , then must be irreducible over .

In practise, a irreducible primitive polynomial may be rendered as reducible in many selected . Like the which is irreducible over by Eisenstein's criterion, but is reducible modulo-:

Until it's irreducible modulo-, by:

More generally, to judge whether a reduced modulo- polynomial is reducible over , a naive but direct method is by applying the sieve method: first if is divisible by , since is a field it's also divisible by , so we can safely restrict the discussion to 's divisibility by some monic polynomial in ; by the concept of sieve method, we take out an irreducible monic polynomial, label the polynomial that is reducible by this monic polynomials, leaving those irreducible, up to polynomials of degree, testing the divisibility of by the taken irreducible monic polynomial meantime. The process starts from polynomials of degree which are all irreducible, and will repeat until there's some irreducible polynomial (which is of minimal degree, under our schema) dividing , so we need to try another , or until all irreducible polynomials of degree up to are tested, at which is indeed irreducible over , and its preimage is irreducible over .

However, since the reduction modulo- criterion is rejective, just like there're liars for Fermat's little theorem, there're liars for reduction modulo- criterion, which is irreducible over but indefinitely reducible after reduction to any .

Take as an example: first all roots can be excavated by , , and is reducible over ; by none of them is rational, has no factor polynomial of degree over ; by picking two of them and multiplying them together ³, there're combinations: , , , , , , none of them is polynomial in , so has no factor polynomial of degree over ; finally since has no factor polynomial in , it's irreducible over .

On the other hand, consider the different ways for equivalently converting : , or . By the existence theorem of primitive roots, at least one of the , or must be solvable for any prime ⁴. So after the reduction to any , will be reducible in one of the form of , or .

Due to the liar problem in reduction modulo- criterion, when a specified polynomial fulfils the criterion, its irreducibility is decisive; but designing an algorithm based on the criterion will be very likely to end up with an ineffective algorithm that never halt for some polynomial input. So use this criterion wisely.

Conclusion

In this text, we first introduce the polynomial rings over commutative rings, alongside with some fundamental concepts, like the indeterminate, degree, and leading coefficient. Then by studying the factorization and irreducibility of polynomials over fields, we've revealed the similarities between the ring of integers and polynomial rings over fields, alongside with some conclusions about roots of polynomials.

Then we prove the multiplicative group of a field can only be cyclic, by building polynomial ring over it, and showing the contradiction in the number of roots of polynomials if the multiplicative group is not cyclic.

Finally we've shown the irreducibility of polynomial with integer coefficients is equivalent to its corresponding primitive polynomial, and the irreducibility of primitive polynomials over is the same as the one over , by introducing and proving the Gauss's lemma. We have also developed and proved some criterions for irreducibility of polynomials with integer coefficients, like the Eisenstein's criterions, the rational root theorem and the reduction modulo- criterion.