Gauss's lemma (polynomial)

From Wikipedia, the free encyclopedia

This article is about Gauss's lemma for polynomials. See also Gauss's lemma.

In the theory of polynomials, Gauss's lemma, named after Carl Friedrich Gauss, refers to two related statements about polynomials with integral coefficients.

  • The first result states that the product of two primitive polynomials is primitive (a polynomial with integral coefficients is called primitive if the greatest common divisor of its coefficients is 1).
  • The second result states that if a polynomial with integral coefficients is irreducible over the integers, then it is also irreducible if it is considered as a polynomial over the rationals.

This second statement is a consequence of the first (see proof below).


Contents

[edit] Formal statement

These statements can be expanded to any unique factorization domain (UFD):

  • If R is a UFD, and f(x) and g(x) are both primitive polynomials in R[x], then so is f(x) · g(x). (Here a primitive polynomial is one whose coefficients have no common factor.)
  • Let R be a UFD and F its field of fractions. If a polynomial f(x) in R[x] is reducible in F[x], then it is reducible in R[x].

Both these results can be generalised to several variables.

[edit] Proofs of the primitivity property

First we give a proof using as few technical concepts as possible.

Theorem: The product of two primitive polynomials is itself primitive.

Proof: We will give two proofs, the first one being messy but concrete and the second being more conceptual but also more abstract.

Clearly the product f(x)\cdot g(x) of two primitive polynomials has integer coefficients. Therefore, if it is not primitive, there must be a prime p which is a common divisor of all its coefficients. But p can not divide all the coefficients of either f(x) or g(x) (otherwise they would not be primitive). Let arxr be the first coefficient of f(x) not divisible by p and let bsxs be the first coefficient of g(x) not divisible by p. Now consider the term xr + s in the product. Its coefficient must take the form:

a_r b_s + a_{r+1} b_{s-1} + a_{r+2} b_{s-2} + \ldots + a_{r-1} b_{s+1} + a_{r-2} b_{s+2} + \ldots

The first term is not divisible by p (because p is prime), yet all the remaining ones are, so the entire sum cannot be divisible by p. We assumed that all coefficients in the product were divisible by p, leading to a contradiction. Therefore, the coefficients of the product can have no common divisor and are thus primitive. This completes the proof.

A much cleaner version of this proof can be given using a little abstract algebra.

  1. Assume the product f(x).g(x) is not primitive, so its coefficients have a common prime factor, say p.
  2. This implies f(x).g(x)=0 in the ring (R/pR)[X].
  3. Since R/pR is an integral domain, either f(x) or g(x) is 0 in (R/pR)[X], and hence p must divide all the coefficients of f(x) or all the coefficients of g(x), and either of these contradicts their primitivity.

The tedious bookkeeping in the first proof was replaced in the second proof by the conceptual idea that reduction modulo p on coefficients gives a ring homomorphism from R[X] to (R/pR)[X] and R/pR is a domain.

Here is a version of Gauss' lemma in R[X] where R is any commutative ring. Call a polynomial f(x) in R[X] primitive if the ideal in R generated by the coefficients of the polynomial is the unit ideal (1) = R. (When R is a PID, this is equivalent to the notion of primitivity above, since the ideal generated by the coefficients will be a principal ideal generated by the greatest common divisor of the coefficients. But if R is a UFD that is not a PID, this new concept of primitivity is stronger than the one used above.) Gauss' lemma for R[X] says: the product of two primitive polynomials is primitive. To prove it, we proceed as follows.

  1. Assume f(x).g(x) is not primitive, so its coefficients generate a proper ideal in R. Every proper ideal lies in a maximal ideal, so the ideal generated by the coefficients of f(x).g(x) lies in some maximal ideal m in R.
  2. This implies f(x).g(x)=0 in the ring (R/m)[X].
  3. Since R/m is a field, either f(x) or g(x) is 0 in (R/m)[X], and hence all the coefficients of f(x) are in m or all the coefficients ofg(x) are in m. Either of these contradicts the primitivity of f(x) and g(x).

[edit] Proof of the lemma

For the second statement, we will prove the contrapositive:

  1. Without loss of generality we may assume f(x) is primitive.
  2. Assume f(x) is reducible over F[x]. Then there exists non-constant g(x), h(x) in F[x] such that f(x) = g(x).h(x).
  3. There exist a,b in R such that both a.g(x) and b.h(x) are primitive in R[x].
  4. By the first result (a.g(x)).(b.h(x)) = (ab).f(x) is also primitive, and hence ab is a unit in R, so a and b are units in R.

This implies f(x) is reducible over R[x].

[edit] Implications

The first result implies that the GCD of the coefficients of the product of two polynomials will be the product of the GCD of the coefficients of each polynomial. This is very useful, as a limit to the common divisors of the coefficients of the product.

The second result implies that if a polynomial can be factorised over the rationals, then there exists a factorisation over the integers. This property is also useful when combined with properties such as Eisenstein's criterion.