Gauss' Lemma, Field of Fractions, and More

We’ll cover quite a bit of material in this entry, finishing with Gauss’ Lemma, proving that a polynomial over a unique factorization domain is irreducible if and only if it is irreducible over the ring’s field of fractions. Before we get there, though, we must dig deeper into the structure of rings and polynomials. Let’s get started!

Definition: Localization

Lemma: The Localization Equivalence Relation is in fact an Equivalence Relation

Proof

Suppose

$$ \begin{align} (r_1, d_1) \equiv (r_2, d_2) \\ (r_2, d_2) \equiv (r_3, d_3) \\ \end{align} $$

This means that there exists \( c_1 \) and \( c_2 \in D \), such that

$$ \begin{align} (r_1 d_2 - r_2 d_1) c_1 &= 0 \\ (r_2 d_3 - r_3 d_2) c_2 &= 0 \\ \end{align} $$

Notice that if \( 0 \in D \), then setting \( c = 0 \), we have \( (r_1 d_2 - r_2 d_1 )c = 0 \). This happens for any pair of tuples, \( (r_1, d_1) \) and \( (r_2, d_2) \). So in that case every element of \( R \times D \) is equivalent to every other element.

On the other hand, if \( 0 \not\in D \), then by condition (2) above, we have

$$ x, y \in D \implies xy \in D $$

so there are no elements in \( D \) which divide \( 0 \). Therefore, if

$$ (r_1 d_2 - d_1 r_2) c = 0 $$

and \( c \neq 0 \) (since \( c \in D \) and \( 0 \not\in D \)), then we have

$$ r_1 d_2 - d_2 r_1 = 0 \\ $$

So we can ignore the \( c_1 \) and \( c_2 \) terms above and use

$$ \begin{align} r_1 d_2 - r_2 d_1 &= 0 \\ r_2 d_3 - r_3 d_2 &= 0 \\ \end{align} $$

Multiplying the top equation by \( d_3 \) and the bottom equation by \( d_1 \), we get

$$ \begin{align} r_1 d_2 d_3 - r_2 d_1 d_3 &= 0 \\ r_2 d_3 d_1 - r_3 d_2 d_1 &= 0 \\ \end{align} $$

Since \( R \) is commutative,

$$ r_2 d_1 d_3 = r_2 d_3 d_1 = r_3 d_2 d_1 $$

so when we add the two equations together, we get

$$ \begin{align} r_1 d_2 d_3 - r_3 d_2 d_1 &= 0 \\ (r_1 d_3 - r_3 d_1) d_2 &= 0 \\ \end{align} $$

which means that \( (r_1, d_1) \equiv (r_3, d_3) \).

QED

Lemma: The Ring of Fractions of R by D is in fact a Ring

You’ve probably also noticed that the equivalence relation (when \( 0 \not\in D \)), \( (r_1, d_1) \equiv (r_2, d_2) \) if and only if \( r_1 d_2 - r_2 d_1 = 0 \), is nothing more than what you get when you start with

$$ \frac{r_1}{d_1} = \frac{r_2}{d_2} $$

and multiply through by both of the denominators.

Proof

0. We’ll start by noticing that \( \displaystyle \frac{r \cdot n}{r \cdot d} \equiv \frac{n}{d} \), where \( n, r \in R \) and \( d \in D \). This happens because

$$ \begin{align} (rn)d - n (rd) &= \\ rnd - rnd &= 0 \\ \end{align} $$

1. Multiplication is associative. This is not difficult to see, as it is a direct consequence of the associativity of \(R\). Associativity happens for the numerators and the denominators. Also notice that \( \displaystyle \frac{1}{1} \) is a multiplicative identity element. Let \( \displaystyle \frac{r}{d} \in D^{-1} \cdot R \) be arbitrary. Then

$$ \begin{align} \frac{r}{d} \cdot \frac{1}{1} &= \\ \frac{r \cdot 1}{d \cdot 1} &= \frac{r}{d} \\ \end{align} $$

2. There is more to show for Addition.

It is associative:

$$ \begin{align} \left (\frac{r_1}{d_1} + \frac{r_2}{d_2} \right ) + \frac{r_3}{d_3} &= \\ \frac{ r_1 d_2 d_3 + r_2 d_1 d_3 + r_3 d_1 d_2 }{ d_1 d_2 d_3 } &= \\ \frac{ r_1 }{ d_1 } + \left ( \frac{r_2}{d_2} + \frac{r_3}{d_3} \right ) \\ \end{align} $$

It has an additive identity element: \( \displaystyle \frac{0}{1} \). Let \( \displaystyle \frac{r}{d} \in D^{-1} \cdot R \) be arbitrary, then

$$ \begin{align} \frac{r}{d} + \frac{0}{1} &= \\ \frac{r \cdot 1 + 0 \cdot d}{d \cdot 1} &= \frac{r}{d} \\ \end{align} $$

Every element has an additive inverse, \( \displaystyle - \left ( \frac{r}{d} \right) = \frac{-r}{d} \).

$$ \begin{align} \frac{r}{d} + \frac{-r}{d} &= \\ \frac{rd - rd}{d^{2}} &= \\ \frac{0}{d^{2}} &= \\ \frac{d^2 \cdot 0}{d^2} &\equiv \frac{0}{1} \\ \end{align} $$

3. The Distributive Law Holds:

First we show that

$$ \frac{r_1}{d} + \frac{r_2}{d} = \frac{r_1 + r_2}{d} $$

To see why this holds, notice that by the definition of localized addition above, we have

$$ \begin{align} \frac{r_1}{d} + \frac{r_2}{d} &= \frac{r_1 d + r_2 d}{d \cdot d} \\ &= \frac{d(r_1 + r_2)}{d \cdot d} \\ &= \frac{d}{d} \cdot \left ( \frac{r_1 + r_2}{d} \right ) \\ &= \frac{r_1 + r_2}{d} \\ \end{align} $$

Now we can use that to show that distributivity holds:

$$ \begin{align} &\frac{r_1}{d_1} \cdot \left ( \frac{r_2}{d_2} + \frac{r_3}{d_3} \right ) \\ = &\frac{r_1}{d_1} \cdot \left ( \frac{ r_2d_3 + r_3 d_2 }{d_2 d_3} \right ) \\ = &\frac{ r_1 r_2 d_3 + r_1 r_3 d_2 }{d_1 d_2 d_3} \\ = &\frac{r_1 r_2 d_3}{d_1 d_2 d_3} + \frac{r_1 r_3 d_2}{d_1 d_2 d_3} \\ = &\frac{r_1 r_2}{d_1 d_2} + \frac{r_1 r_3}{d_1 d_3} \\ = &\frac{r_1}{d_1} \cdot \frac{r_2}{d_2} + \frac{r_1}{d_1} \cdot \frac{r_2}{d_3} \\ \end{align} $$

QED

It’s not difficult to see that it is always possible to construct a homomorphism,

$$ \phi : R \rightarrow D^{-1} \cdot R $$

such that for all \( r \in R \), we have

$$ \phi(r) := \frac{r}{1} $$

Note: It is common to be sloppy about distinguishing between \(R\) and \( \phi(R) \subseteq D^{-1} \cdot R \). It usually doesn’t cause any real confusion. We did something similar when we dealt with factor groups “mod a normal subgroup”, and we’ll do it later on in the context of field extensions and ring ideals. We will try to take care when this could lead to any confusion.

When we do this, we think of \(R\) as being a subring of \( D^{-1} \cdot R \).

Notice that when \(R\) is an integral domain (so that \( x \cdot y = 0 \) implies at least one of \( x \) or \( y \) is equal to 0) then if we let \( D := R \setminus \{ 0 \} \), we see that \( D^{-1} \cdot R \) is a field i.e. it is a commutative integral domain where every non-zero element is a unit. This is exactly what happens when we construct \( \mathbb{Q} \) from \( \mathbb{Z} \). In this case, since we constructed a field it is referred to as a “Field of Fractions” instead of a “Ring of Fractions.”

Mini-Lemma: F a field implies F[x] is a Euclidean Domain

Proof

First we’ll show that \( \mathbb{F}[x] \) is Euclidean, and then we’ll show that the

$$ N : \mathbb{F}[x] \rightarrow \mathbb{N} $$

that we use is a norm map, where

$$ N( p(x) ) := 2^{\text{deg}(p(x))} $$

Recall the definition of deg(p(x)), from an earlier entry. We’ll define \( 2^{-\infty} := 0 \).

First, we’ll show that \( \mathbb{F}[x] \) is a Euclidean Domain.

Let \( f(x) \neq 0 \) and \( g(x) \in \mathbb{F}[x] \) be arbitrary polynomials. We want to show that there exist two polynomials \( q(x) \) and \( r(x) \in \mathbb{F}[x] \), such that

$$ \begin{align} g(x) &= f(x) \cdot q(x) + r(x) \\ N(r(x)) &< N(f(x)) \\ \end{align} $$

Notice that the function, \( 2^{n} \), where \( n \in \mathbb{Z} \cup \{ -\infty \} \) is strictly increasing, so

$$ \begin{align} N( r(x) ) &< N( f(x) ) \iff \\ \text{deg}(r(x)) &< \text{deg}(f(x)) \\ \end{align} $$

Because of that, we’ll use \( \text{deg}(f(x)) \) for most of our argument.

There are two possibilities. The first is easy.

1. Suppose that \( \deg{(g(x))} < \text{deg}(f(x)) \), then set \( q(x) = 0 \) and \( r(x) = g(x) \). This works.

2. Suppose \( \text{deg}({g(x)}) \geq \text{deg}(f(x)) \). We’ll prove this with induction on the degree of \( g(x) \). Suppose the result holds for every polynomial of smaller degree than \( \text{deg}(g(x)) \) (we’ll come back and cover the base case at the end).

Let

$$ \begin{align} f(x) &= a_{n}x^n + a_{n-1}x^{n-1} + … + a_{1}x + a_{0} \\ g(x) &= b_{m}x^m + b_{m-1}x^{m-1} + … + b_{1}x + b_{0} \\ \end{align} $$

where both \( a_n \) and \( b_m \neq 0 \), then let

$$ \begin{align} q_0(x) :=& \frac{a_n}{b_m} x^{\text{deg}(g(x)) - \text{deg(f(x))}} \\ g_0(x) :=& g(x) - f(x) \cdot q_0(x) \\ \end{align} $$

First, notice that neither \(f(x)\) nor \( g(x) \) is equal to the zero polynomial, so we don’t have to worry about \( -\infty \) in our calculation of the exponent of \(x\). Second, notice that the leading term of \( f(x) \cdot q_0(x) \) is equal to \( a_n \frac{b_m}{a_n} x^n x^{m - n} = b_m x^m \) and therefore \( \text{deg}(g_0(x)) < \text{deg}(g(x)) \). Thus, by induction, we can write

$$ g_0(x) = q_1(x)f(x) + r_1(x) $$

where \( \text{deg}(r_1(x)) < \text{deg}(f(x)) \).

We’ve now got two equations for \( g_0(x) \), when we set them equal to each other, we get

$$ \begin{align} g(x) - f(x)q_0(x) = q_1(x)f(x) + r_1(x) \\ \implies g(x) = f(x)[ q_0(x) + q_1(x) ] + r_1(x) \\ \end{align} $$

so setting \( q(x) = q_0(x) + q_1(x) \) gives us what we want.

Now let’s explain the base case. That happens when \( \text{deg}(g(x)) = \text{deg}(f(x)) \). In this situation, the above argument works nearly the same, except that \( g_0(x) \) will have degree strictly less than \( f(x) \), so we can use it directly as our remainder. There is no need to invoke induction.

Finally,

$$ N( p(x) ) := 2^{\text{deg}(p(x))} $$

is a norm map, because \( N(p(x)) = 1 \) if and only if \( \text{deg}(p(x)) = 0 \), i.e. \( p(x) = a_0 \), where \( a_0 \in \mathbb{F} \setminus \{ 0 \} \), which means that \( p(x) | 1 \), the “one polynomial”. Notice also that \( N(f(x) \cdot g(x)) = N(f(x)) \cdot N(g(x)) \), as a result of the Degree of Sum and Product Mini-Lemma (part 2, which concerned products).

QED

The following result is the type of thing you might forget even has to be proven, and the proof we provide relies heavily on “hand waving”. Nonetheless, it is still worth pointing out.

Mini-Lemma: Extending a Ring Homomorphism to Polynomials

Proof

Proving that \( \psi \) is a homomorphism isn’t difficult. It’s a direct result of how we defined arithmetic with polynomials.

Uniqueness is a consequence of

$$ \psi \left ( \sum\limits_{i = 0}^n a_i x^i \right ) = \sum\limits_{i = 0}^n \phi(a_i) x^i $$

QED

Definition and Lemma: Primitive Polynomials

Proof

Let \( r(x) = p(x)q(x) \), where \( p(x) \) and \( q(x) \) are primitive polynomials. Let

$$ \begin{align} p(x) &= \sum\limits_{i = 0}^m a_i x^i \\ q(x) &= \sum\limits_{j = 0}^n b_j x^j \\ r(x) &= \sum\limits_{k = 0}^{m+n} c_k x^k \\ \end{align} $$

where

$$ c_k = \sum\limits_{i + j = k} a_i b_j $$

Now, suppose that

$$ d | \gcd(\{ c_k \}_{k = 0}^{m+n}) $$

where \( d \) is a prime element of \( R \), so that it is not a unit. Since both \( p(x) \) and \( q(x) \) are primitive, \(d\) cannot divide every coefficient of those polynomials. Let \( i^{*} \) be the least index such that \( d \nmid a_{i^{*}} \) and let \( j^{*} \) be the least index such that \( d \nmid b_{j^{*}} \) and let \( k^{*} := i^{*} + j^{*} \).

$$ \begin{align} c_{k^{*}} &= \sum\limits_{i + j = k^{*}} a_i b_j \\ &= \sum\limits_{i < i^{*}, i + j = k^{*}} a_i b_j \\ &+ a_{i^{*}} b_{j^{*}}\\ &+ \sum\limits_{i > i^{*},i + j = k^{*}} a_i b_j \\ \end{align} $$

Even though this looks like a bit of a mess, all we have done is broken the sum on the first row into three separate parts, which we’ve split across the next three rows. In the second row, \( d | a_i \) and in the last row \( d | b_j \). However, in the middle, we know that \( d \nmid a_{i^{*}}b_{j^{*}} \), but this is impossible! Notice that the entire sum is equal to \( c_{k^{*}} \) and \( d \) must divide each \( c_k \). A contradiction. Thus, our assumption that \( r(x) \) was not primitive is impossible.

QED

Notice that if a ring, \( R \), is a unique factorization domain and \( p(x) \in R[x] \) is equal to

$$ \sum\limits_{i = 0}^m a_i x^i $$

where

$$ d = \gcd( \{ a_i \}_{i = 0}^n ) $$

then we can divide each coefficient by \(d\) to get

$$ \begin{align} p(x) &= d \cdot \sum\limits_{i = 0}^n \frac{a_i}{d} x^i \\ &= d \cdot \sum\limits_{i = 0}^n a_i’ x^i \\ &= d \cdot \dot{p}(x) \in R[x] \\ \end{align} $$

where \( \dot{p}(x) \) is a primitive polynomial.

Gauss’ Lemma

Proof

Notice that this result is equivalent to saying that “\( p(x) \in R[x] \) is reducible if and only if \( \phi(p)(x) \) is reducible in \( \mathbb{F}[x] \).” This is what we’ll actually prove.

Suppose that

$$ p(x) = d \cdot \dot{p}(x) = f(x) \cdot g(x) $$

(or, more technically, \( \phi(p)(x) = f(x) \cdot g(x) \))

where \( p(x) \in R \), \( \dot{p}(x) \) is a primitive polynomial and \( f(x), g(x) \in \mathbb{F}[x] \). Then

$$ \begin{align} f(x) &= \sum\limits_{i = 0}^m \frac{a_i}{b_i} x^i \\ g(x) &= \sum\limits_{j = 0}^n \frac{c_j}{d_j}x^j \\ \end{align} $$

and there are elements, \( s, t \in R \), such that \( b_i | s \) and \( d_j | t \) (consider the produce of all of the \( a_i \)’s, for example, as a possible \( s \)). This means that \( s \cdot f(x) \in R[x] \) and \( t \cdot g(x) \in R[x] \).

This gives us

$$ \begin{align} std \cdot \dot{p}(x) &= [s \cdot f(x)][t \cdot g(x)] \\ std \cdot \dot{p}(x) &= [s’ \cdot \dot{f}(x)] [ t’ \cdot \dot{g}(x) ] \\ \end{align} $$

where

$$ \begin{align} s \cdot f(x) = s’ \cdot \dot{f}(x) \\ t \cdot g(x) = t’ \cdot \dot{g}(x) \\ \end{align} $$

\( \dot{f}(x) \) and \( \dot{g}(x) \) are both primitive polynomials. This is possible since \( s \cdot f(x) \in R[x] \) and so is \( t \cdot g(x) \).

Regrouping, this gives us

$$ std \cdot \dot{p}(x) = s’ \cdot t’ \cdot \dot{f}(x) \cdot \dot{g}(x) \\ $$

In the previous lemma, we saw that the product of two primitive polynomials is primitive. Now, since the above equation is an equation of polynomials, the gcd of the coefficients must be the same. Notice that the gcd of the polynomial on the left side of the equation is \( std \), and the gcd of the polynomial is \( s’ \cdot t’ \). Thus \( std = s’ \cdot t’ \), so we know that \( d | s’ \cdot t’ \), and \( \displaystyle \frac{s’ \cdot t’}{s \cdot t} \in R \).

which (finally) gets us

$$ \begin{align} p(x) &= d \cdot \dot{p}(x) \\ &= \frac{s’ \cdot t’}{s \cdot t} \dot{f}(x) \cdot \dot{g}(x) \in R[x] \\ \end{align} $$

QED

That’s all for this entry. Thanks so much for reading (or at least reading the best parts)!!