Gauss's lemma (polynomials)

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a theorem about polynomials over the integers, or, more generally, over a unique factorization domain (that is, a ring that has a unique factorization property similar to the fundamental theorem of arithmetic). Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

Gauss's lemma first appeared as Article 42 in his Disquisitiones Arithmeticae as the statement that if P and Q are monic polynomials with rational coefficients, not all of them integers, then the coefficients of their product PQ also cannot all be integers.

In modern form, Gauss's lemma asserts that the product of two primitive polynomials is primitive. (A polynomial with integer coefficients is primitive if it has 1 as a greatest common divisor of its coefficients.)

A corollary of Gauss's lemma, sometimes also called Gauss's lemma, is that a primitive polynomial is irreducible over the integers if and only if it is irreducible over the rational numbers. More generally, a primitive polynomial has the same complete factorization over the integers and over the rational numbers. In the case of coefficients in a unique factorization domain , "rational numbers" must be replaced by "field of fractions of ". This implies that, if is either a field, the ring of integers, or a unique factorization domain, then every polynomial ring (in one or several indeterminates) over is a unique factorization domain. Another consequence is that factorization and greatest common divisor computation of polynomials with integers or rational coefficients may be reduced to similar computations on integers and primitive polynomials. This is systematically used (explicitly or implicitly) in all implemented algorithms (see Polynomial greatest common divisor and Factorization of polynomials).

Gauss's lemma, as well as its consequences that do not involve the existence of a complete factorization, remain true over any GCD domain (an integral domain over which greatest common divisors exist). In particular, a polynomial ring over a GCD domain is also a GCD domain. If one calls primitive a polynomial such that the coefficients generate the unit ideal, Gauss's lemma is true over every commutative ring. However, some care must be taken when using this definition of primitive, as, over a unique factorization domain that is not a principal ideal domain, there are polynomials that are primitive in the above sense and not primitive in this new sense.

The lemma over the integers

If <math>F(X) = a_0 + a_1 X + \dots + a_n X^n</math> is a polynomial with integer coefficients, then <math>F</math> is called primitive if the greatest common divisor of all the coefficients <math>a_0, a_1, \dots, a_n</math> is 1; in other words, no prime number divides all the coefficients.

Proof: Clearly the product f(x)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 cannot divide all the coefficients of either f(x) or g(x) (otherwise they would not be primitive). Let arxr be the first term of f(x) not divisible by p and let bsxs be the first term of g(x) not divisible by p. Now consider the term xr+s in the product, whose coefficient is

:<math>\cdots + a_{r+2} b_{s-2} + a_{r+1} b_{s-1} + a_r b_s + a_{r-1} b_{s+1} + a_{r-2} b_{s+2} + \cdots .</math>

The term arbs is not divisible by p (because p is prime), yet all the remaining ones are, so the entire sum cannot be divisible by p. By assumption all coefficients in the product are divisible by p, leading to a contradiction. Therefore, the coefficients of the product can have no common divisor and are thus primitive. <math>\square</math>

The proof is given below for the more general case. Note that an irreducible element of Z (a prime number) is still irreducible when viewed as constant polynomial in Z[X]; this explains the need for "non-constant" in the statement.

Statements for unique factorization domains

Gauss's lemma holds more generally over arbitrary unique factorization domains. There the content of a polynomial can be defined as the greatest common divisor of the coefficients of (like the gcd, the content is actually a set of associate elements). A polynomial with coefficients in a UFD is then said to be primitive if the only elements of that divide all coefficients of at once are the invertible elements of ; i.e., the gcd of the coefficients is one.

Primitivity statement: If is a UFD, then the set of primitive polynomials in is closed under multiplication. More generally, the content of a product <math>fg</math> of polynomials is the product <math>c(f)c(g)</math> of their individual contents.

Irreducibility statement: Let be a unique factorization domain and its field of fractions. A non-constant polynomial <math>f</math> in <math>R[x]</math> is irreducible in <math>R[x]</math> if and only if it is both irreducible in <math>F[x]</math> and primitive in <math>R[x]</math>.

(For the proofs, see #General version below.)

Let <math>R</math> be a unique factorization domain with field of fractions <math>F</math>. If <math>f \in F[x]</math> is a polynomial over <math>F</math> then for some <math>d</math> in <math>R</math>, <math>df</math> has coefficients in <math>R</math>, and so – factoring out the gcd <math>q</math> of the coefficients – we can write <math>df = qf'</math> for some primitive polynomial <math>f' \in R[x]</math>. As one can check, this polynomial <math>f'</math> is unique up to the multiplication by a unit and is called the primitive part (or primitive representative) of <math>f</math> and is denoted by <math>\operatorname{pp}(f)</math>. The procedure is compatible with product: <math>\operatorname{pp}(fg) = \operatorname{pp}(f)\operatorname{pp}(g)</math>.

The construct can be used to show the statement:

A polynomial ring over a UFD is a UFD.

Indeed, by induction, it is enough to show <math>R[x]</math> is a UFD when <math>R</math> is a UFD. Let <math>f \in R[x]</math> be a non-zero polynomial. Now, <math>F[x]</math> is a unique factorization domain (since it is a principal ideal domain) and so, as a polynomial in <math>F[x]</math>, <math>f</math> can be factorized as:

:<math>f = g_1 g_2 \dots g_r</math>

where <math>g_i</math> are irreducible polynomials of <math>F[x]</math>. Now, we write <math>f = c f'</math> for the gcd <math>c</math> of the coefficients of <math>f</math> (and <math>f'</math> is the primitive part) and then:

:<math>f = c f' = c \operatorname{pp}(g_1) \operatorname{pp}(g_2) \cdots \operatorname{pp}(g_r).</math>

Now, <math>c</math> is a product of prime elements of <math>R</math> (since <math>R</math> is a UFD) and a prime element of <math>R</math> is a prime element of <math>R[x]</math>, as <math>R[x]/(p) \cong R/(p)[x]</math> is an integral domain. Hence, <math>c</math> admits a prime factorization (or a unique factorization into irreducibles). Next, observe that <math>f' = \operatorname{pp}(g_1) \cdots \operatorname{pp}(g_r)</math> is a unique factorization into irreducible elements of <math>R[x]</math>, as (1) each <math>\operatorname{pp}(g_i)</math> is irreducible by the irreducibility statement and (2) it is unique since the factorization of <math>f'</math> can also be viewed as a factorization in <math>F[x]</math> and factorization there is unique. Since <math>c</math> and <math>f'</math> are uniquely determined by <math>f</math> up to unit elements, the above factorization of <math>f</math> is a unique factorization into irreducible elements. <math>\square</math>

The condition that "R is a unique factorization domain" is not superfluous because it implies that every irreducible element of this ring is also a prime element, which in turn implies that every non-zero element of R has at most one factorization into a product of irreducible elements and a unit up to order and associate relationship. In a ring where factorization is not unique, say with p and q irreducible elements that do not divide any of the factors on the other side, the product shows the failure of the primitivity statement. For a concrete example one can take , , , , . In this example the polynomial (obtained by dividing the right hand side by ) provides an example of the failure of the irreducibility statement (it is irreducible over R, but reducible over its field of fractions ). Another well-known example is the polynomial , whose roots are the golden ratio and its conjugate showing that it is reducible over the field , although it is irreducible over the non-UFD which has as field of fractions. In the latter example the ring can be made into an UFD by taking its integral closure in (the ring of Dirichlet integers), over which becomes reducible, but in the former example R is already integrally closed.

General version

Let <math>R</math> be a commutative ring. If <math>f</math> is a polynomial in <math>R[x_1, \dots, x_n]</math>, then we write <math>\operatorname{cont}(f)</math> for the ideal of <math>R</math> generated by all the coefficients of <math>f</math>; it is called the content of <math>f</math>. Note that <math>\operatorname{cont}(af) = a\operatorname{cont}(f)</math> for each <math>a</math> in <math>R</math>. The next proposition states a more substantial property.

A polynomial <math>f</math> is said to be primitive if <math>\operatorname{cont}(f)</math> is the unit ideal <math>(1)</math>. When <math>R = \mathbb{Z}</math> (or more generally when <math>R</math> is a Bézout domain), this agrees with the usual definition of a primitive polynomial. (But if <math>R</math> is only a UFD, this definition is inconsistent with the definition of primitivity in #Statements for unique factorization domains.)