Tuesday, January 29, 2008

Gauss: Gauss's Lemma for Polynomials

Today's proof is taken from Carl Friedrich Gauss' Disquisitiones Arithmeticae (Article 42). This is Gauss' classic work on number theory which he wrote when he was 21. It is a masterpiece that includes the first use of modular arithmetic, the first complete proof of the fundamental theorem of algebra, a proof for quadratic reciprocity, Gauss' analysis of cyclotomic equations, as well as the first systematic presentation of number theory.

Lemma 1:

if a prime p doesn't divide an integer a, then (a +bp)/cp is not an integer

Proof:

(1) There exists an integer d such that a ≡ d (mod p) where 1 ≤ d ≤ p-1.

(2) So, p divides a - d. (see here for review of modular arithmetic)

(3) And p divides (a - d) so p divides (a -d) + bp = (a + bp) -d

(4) So therefore a + bp ≡ d (mod p)

(5) So it follows that since p doesn't divide a+bp, then (a +bp)/cp is not an integer.

QED

A monic polynomial is a polynomial whose leading coefficient is 1 (see Definition 5, here)

Theorem 2: Gauss's Lemma for Polynomials

Let P,Q be two monic polynomials such that:

P = xm + a1xm-1 + a2xm-2 + a3xm-3 + ... + am

Q = xn + b1xn-1 + b2xn-2 + b3xn-3 + ... + bn

If the coefficients of P are rational but not all integers and if the product is also monic such that:

PQ = xm+n + c1xm+n-1 + c2xm+n-2 + c3xm+n-3 + ... + cm+n

Then, the coefficients c1, c2, ..., cm+n cannot all be integers.

Proof:

(1) Let us assume that all rational cofficients in a1, ..., am and b1, ..., bn are expressed in their lowest form.

(2) Let p be a prime number that divides one of the denominators of P [we can assume this since not all the coefficients of P are integers]

(3) Since Q is monic, it is clear that the at least one of the coefficients of (Q)/p will have p as a factor of its denominator (for example, bn will have (1/p) as its coefficient).

(4) In P, there will always be one term, a fraction, whose denominator involves high powers of p than all the fractional coefficients that precede it and no lower powers than the denominators of all succeeding fractional coefficients.

For example, if there is only one fraction with the rest integers, than this fraction is the coefficient. One can start with the first coefficient divisible by p and then check if there are any coefficients after it that are divisible by a greater power of p.

(5) We can identify the term in step #4 as Gxg with G divisible by 1/(pt) with t ≥ 1.

(6) Since p divides at least one of the denominators in (Q)/p, the same term in step #4 exists in (Q)/p.

(7) We can identify the term in step #6 as Hxh with H divisible by 1/(pu) with u ≥ 1.

(8) Now, it follows that t + u ≥ 2.

(9) Next, I will show that the term xg+h in the product of (P) and (Q) will have a fractional coefficient who denominator is divisible by 1/(pt+u-1). This then will complete the proof since a coefficient that is divisible by 1/(pt+u-1) where p is a prime is not an integer.

(10) Let the terms in P which precede Gxg be 'Gxg+1, ''Gxg+2 and those which follow Gxg be G'xg-1, G''xg-2

(11) Let the terms in (Q)/p which precede Hxh be 'Hxh+1, ''Hxh+2 and those which follow Hxh be H'xh-1, H''xh-2

(12) If we multiply P and (Q)/p, the coefficient of the term Gxg*Hxh is GH + 'GH' + ''GH'' + ... + 'HG' + ''HG'' + ...

(13) Because G,H have the highest power of p, there exists e0,f0 such that:

p does not divide e0
p does not divide f0

and

GH = e0/(f0pt+u)

(14) Since any of the ('G, ''G, etc.) or ('H, ''H, etc.) have a power of p less than t or u and because any of the (G', G'', etc.) or (H', H'', etc) have a power of p no greater than t or u, it follows that any product of the form ('GH', ''GH'', etc.) will have the following form:

'GH' = ei/(fipt+u-di)

where

p does not divide ei
p does not divide fi
di ≥ 1.

(15) Now if we sum all the factors in step #14 and reduce the denominator to the lowest term, then we get:

∑ ei/(fipt+u-di) =

= e'/(f'pt+u-d'i)

where

p does not divide e'
p does not divide f'
d' ≥ 1.

(16) If we add up the result of step #14 with step #15, we get:

(e0f' + e'f0pd)/(f0f'pt+u)

where:

p does not divide e0
p does not divide e'
p does not divide f0
p does not divide f'
d ≥ 1
(t + u) ≥ 2

(17) Since Q = p*(Q)/p, for this same coefficient for P*Q, we have:

(e0f' + e'f0pd)/(f0f'pt+u-1)

where:

p does not divide e0
p does not divide e'
p does not divide f0
p does not divide f'
d ≥ 1
(t + u - 1) ≥ 1

(18) Since p does not divide e0 or f', it follows that p does not divide e0f.

(19) If:

a = e0f'
b = ef0pd-1
c = f0f'pt+u-2

Then we can use Lemma 1 above to conclude that:

(e0f' + e'f0pd)/(f0f'pt+u-1)

is not an integer.

QED

Corollary 2.1:

If a monic polynomial in Q[X] divides a monic polynomial with integral coefficients, then its coefficients are all integral.

Proof:

(1) Let f be a monic polynomial with integral coefficients.

(2) Let P be a monic polynomial that divides f.

(3) Since P divides f, there exists a polynomial Q such that:

f = PQ

(4) Since P,f are monic, it follows that Q must also be monic. [See Lemma 1, here]

(5) Assume that the coefficient in P are not all integers.

(6) Then, using Theorem 2 above, it follows that the coefficients of f are not all integers.

(7) But this is not correct since by assumption, all the coefficients of f are integers.

(8) So we reject our assumption in step #5.

QED

References

No comments: