MHB Ideals and GCDs in k[x] .... .... Cox Et al: "Ideals, Varieties and Algorithms"

[Math Amateur]

I am reading the undergraduate introduction to algebraic geometry entitled "Ideals, Varieties and Algorithms: An introduction to Computational Algebraic Geometry and Commutative Algebra (Third Edition) by David Cox, John Little and Donal O'Shea ... ...

I am currently focused on Chapter 1, Section 5: Polynomials of One Variable ... ... and need help with the proof of Proposition 8, part 3 ...

Proposition 8 of Chapter 1 (including Definition 7 which is relevant) reads as follows:View attachment 5680In the above text from Cox et al we read the following:

" ... ... To prove part (iii), let $$h \ = \ GCD(f_2, \ ... \ ... \ , f_s)$$. We leave it as an exercise to show that

$$<f_1, h> \ = \ <f_1, \ ... \ ... \ , f_s>$$

... ... "I need help to show that $$<f_1, h> \ = \ <f_1, \ ... \ ... \ , f_s>$$ ... ...Work so far ...

We need to show that $$<f_1, h> \ \subset \ <f_1, \ ... \ ... \ , f_s>$$ ... and also that

$$<f_1, \ ... \ ... \ , f_s> \ \subset \ <f_1, h>$$So to show $$<f_1, h> \ \subset \ <f_1, \ ... \ ... \ , f_s>$$ we start with

Let $$l \in <f_1, h>$$ ...

Then, by definition of $$<f_1, h>$$, we have that $$l = f_1 t_1 + h t_2$$ where $$t_1, t_2 \in k[x]$$ ...Now we have that $$h = GCD(f_2, \ ... \ ... \ , f_s)$$ ... BUT ... how do we use this in the proof?Note that we also have

(1) $$h = GCD(f_2, \ ... \ ... \ , f_s) \Longrightarrow h \text{ divides } f_2, \ ... \ ... \ , f_s$$

$$\Longrightarrow h \ = \ f_2 u_2, h \ = \ f_3 u_3, \ ... \ ... \ , h \ = \ f_s U_s
$$

for some $$u_2, \ ... \ ... \ , u_s \in k[x]$$ ...(2) $$k[x]$$ is a PID so that:

$$<f_1, h > \ = \ <v>$$ for some polynomial $$v \in k[x]$$ ... ...... but, how do we use (1) and (2) in the required proof ...
Can someone please help me to complete the proof of $$<f_1, h> \ = \ <f_1, \ ... \ ... \ , f_s>$$ ...Help will be appreciated ...

Peter

 

[Deveno]

The reason why we use generating sets is to simplify proving things about the things they generate.

So, in order to prove:

$\langle f_1,h\rangle = \langle f_1,f_2,\dots,f_s\rangle$, it suffices to prove that:

(1) $f_1,h \in \langle f_1,f_2,\dots,f_s\rangle$ (this shows that $\langle f_1,h\rangle \subseteq \langle f_1,f_2,\dots,f_s\rangle$).

(2) $f_1,f_2,\dots,f_s \in \langle f_1,h\rangle$ (this shows the other inclusion).

(2) is the "easy" part here. Since $h = \gcd(f_2,\dots,f_s)$ we have $f_j = p_jh$ for some $p_j \in k[x]$ for each $j = 2,\dots,s$ (since $h$ divides each $f_j$).

Since $\langle f_1,h\rangle$ is an ideal, and $h \in \langle f_1,h\rangle$, it is thus immediate that:

$f_2,\dots,f_s \in \langle f_1h\rangle$.

It is of course trivial that $f_1$ lies in both ideals. So the "tough" part is showing that $h \in \langle f_2,\dots,f_s\rangle$ (which will then show it is in the larger ideal).

In other words we must show $h$ is in the $k[x]$-linear span of $f_2,\dots,f_s$.

So consider the set $M = [\text{span}_{k[x]}(\{f_2,\dots,f_s\})] - \{0\}$. The degrees of the elements of $M$ forms a set of natural numbers, which thus has a minimal element. Thus $M$ has an element of minimal degree, say, $m$.

By our definition of $M$, we have:

$m = c_2f_2 + \cdots + c_sf_s$, for some $c_2,\dots,c_s \in k[x]$, not all 0. Thus for any particular $f_j$ (for $j \in \{2,\dots,s\})$, we have:

$f_j = qm + r$, where $\text{deg}(r) < \text{deg}(m)$, or $r = 0$. Suppose $r \neq 0$. We then have:

$r = (-qc_2)f_2 + \cdots + (1 - qc_j)f_j + \cdots + (-qc_s)f_s \in M$.

This contradicts the minimal degree of $m$, hence $r = 0$, and thus $m|f_j$, for each $j$.

Now suppose further that we have $p \in k[x]$, such that $p|f_j$ for all $j = 2,\dots,s$. Since $m \in M$, we have $p|m$, and thus $m$ is a gcd of $f_2,\dots,f_s$.

Thus $m = ah$ for some $a\neq 0 \in k$ (by (i) of Proposition 8), and since by construction $m \in \langle f_1,f_2,\dots,f_s\rangle$ and this is an ideal, and $a \neq 0$, we have:

$h = \dfrac{1}{a}m \in \langle f_1,f_2,\dots,f_s\rangle$.

The important thing to take away from all this, is that $k[x]$ is a Euclidean domain, which makes explicit computations of gcd's possible by leveraging the Euclidean division algorithm.

Most of this can be applied, more or less unchanged, to any Euclidean domain, which then gives us the following important fact: Euclidean domains are principal ideal domains, and thus this proposition gives us a specific way to compute a generator.

Since principal ideal domains are always unique factorization domains, we thus also know we can use this to factor polynomials over a field $k$ into prime (irreducible) polynomials, which makes ideals generated by prime polynomials objects of great interest, and these, in turn, can reveal facts about the field $k$.

 

[Math Amateur]

The reason why we use generating sets is to simplify proving things about the things they generate.

So, in order to prove:

$\langle f_1,h\rangle = \langle f_1,f_2,\dots,f_s\rangle$, it suffices to prove that:

(1) $f_1,h \in \langle f_1,f_2,\dots,f_s\rangle$ (this shows that $\langle f_1,h\rangle \subseteq \langle f_1,f_2,\dots,f_s\rangle$).

(2) $f_1,f_2,\dots,f_s \in \langle f_1,h\rangle$ (this shows the other inclusion).

(2) is the "easy" part here. Since $h = \gcd(f_2,\dots,f_s)$ we have $f_j = p_jh$ for some $p_j \in k[x]$ for each $j = 2,\dots,s$ (since $h$ divides each $f_j$).

Since $\langle f_1,h\rangle$ is an ideal, and $h \in \langle f_1,h\rangle$, it is thus immediate that:

$f_2,\dots,f_s \in \langle f_1h\rangle$.

It is of course trivial that $f_1$ lies in both ideals. So the "tough" part is showing that $h \in \langle f_2,\dots,f_s\rangle$ (which will then show it is in the larger ideal).

In other words we must show $h$ is in the $k[x]$-linear span of $f_2,\dots,f_s$.

So consider the set $M = [\text{span}_{k[x]}(\{f_2,\dots,f_s\})] - \{0\}$. The degrees of the elements of $M$ forms a set of natural numbers, which thus has a minimal element. Thus $M$ has an element of minimal degree, say, $m$.

By our definition of $M$, we have:

$m = c_2f_2 + \cdots + c_sf_s$, for some $c_2,\dots,c_s \in k[x]$, not all 0. Thus for any particular $f_j$ (for $j \in \{2,\dots,s\})$, we have:

$f_j = qm + r$, where $\text{deg}(r) < \text{deg}(m)$, or $r = 0$. Suppose $r \neq 0$. We then have:

$r = (-qc_2)f_2 + \cdots + (1 - qc_j)f_j + \cdots + (-qc_s)f_s \in M$.

This contradicts the minimal degree of $m$, hence $r = 0$, and thus $m|f_j$, for each $j$.

Now suppose further that we have $p \in k[x]$, such that $p|f_j$ for all $j = 2,\dots,s$. Since $m \in M$, we have $p|m$, and thus $m$ is a gcd of $f_2,\dots,f_s$.

Thus $m = ah$ for some $a\neq 0 \in k$ (by (i) of Proposition 8), and since by construction $m \in \langle f_1,f_2,\dots,f_s\rangle$ and this is an ideal, and $a \neq 0$, we have:

$h = \dfrac{1}{a}m \in \langle f_1,f_2,\dots,f_s\rangle$.

The important thing to take away from all this, is that $k[x]$ is a Euclidean domain, which makes explicit computations of gcd's possible by leveraging the Euclidean division algorithm.

Most of this can be applied, more or less unchanged, to any Euclidean domain, which then gives us the following important fact: Euclidean domains are principal ideal domains, and thus this proposition gives us a specific way to compute a generator.

Since principal ideal domains are always unique factorization domains, we thus also know we can use this to factor polynomials over a field $k$ into prime (irreducible) polynomials, which makes ideals generated by prime polynomials objects of great interest, and these, in turn, can reveal facts about the field $k$.

Thanks for the help Deveno ...

A key point was obviously to realize that, as you wrote:
" ... ... in order to prove:

$\langle f_1,h\rangle = \langle f_1,f_2,\dots,f_s\rangle$, it suffices to prove that:

(1) $f_1,h \in \langle f_1,f_2,\dots,f_s\rangle$ (this shows that $\langle f_1,h\rangle \subseteq \langle f_1,f_2,\dots,f_s\rangle$).

(2) $f_1,f_2,\dots,f_s \in \langle f_1,h\rangle$ (this shows the other inclusion). ... ...

... ... ... ... "

Key point that I missed ...Further, not sure how you knew to involve a polynomial of minimum degree ...

But anyway ... followed your proof ... thanks again for the help ...

Peter

 

[Deveno]

Well, to be honest, it's how some texts *define* the gcd (which would clearly make this proof a lot easier). Then one has to go on and show then it *is* indeed a "common divisor", and that it is maximal in some sense.

This way of looking at gcd's was first shown by Étienne Bézout for polynomials in: Théorie générale des équations algébriques (1779), although in 1629 Claude Gaspard Bache had used a similar formulation of what we now call a Bézout identity to solve problems of the form:

$ax - by = 1$.

In fact, the "$d$" function $\deg(p)$, for $p \in k[x]$, turns out to be a semi-group homomorphism:

$(k[x]^{\ast},\cdot) \to (\Bbb N,+)$

which allows us to use the total order of the natural numbers to define a *pre-order* or *quasi-order* on polynomials (it's not total, because two polynomials of the same degree are typically held to be "incomparable" which also means we lose the anti-symmetric property, so it's not a partial order, either).

Nevertheless, we can still use this quasi-order to define a partitioning of polynomials in $k$ by degree, which is an equivalence relation which comes in handy.

The net result of this, is that polynomial rings over a field are very "integer-like" in their behavior (if you are good at number theory, chances are you can use many elements of your "number theory bag of tricks" and apply them straight-across to polynomials-look at some of anemone's posts for examples of this).

Something even deeper underlying all this, is the exponential rule in the indeterminate $x$:

$x^m\cdot x^n = x^{m+n}$

so the degree function can be thought of as a kind of "logarithm" of $x$ (this becomes even more clear if we include Laurent polynomials, which have negative degrees of $x$, this ring is usually denoted $k[x,x^{-1}]$, and is the localization of the ring $k[x]$ at the multiplicatively closed set $S = \{x^n: n \in \Bbb N\}$, a sort of "generalization" of the field of quotients construction-it's not a field, but it is a sub-ring of the field of rational functions in $x$, and every power of $x$ is a unit in this ring).

Another way to look at polynomials $k[x]$ is as the monoid-ring $k[\Bbb N]$, and the Laurent polynomials are the group-ring $k[\Bbb Z]$, so the character of the natural numbers/integers are "deeply embedded" in polynomials. These are examples of "universal constructions" (that is, they possesses appropriate universal mapping properties), of ways to create "a general $k$-algebra" from $\Bbb N$ and $\Bbb Z$, respectively.