We have already been familiar with the fundamental
theorem of arithmetic every since our elementary
school, that for every positive integer can be
decomposed into product of postitive prime power form
,
and the decomposition is unique.
When it comes to the case of decomposing a polynomial
in over , for a reduction
of polynomial , it
might also be decomposed into
, although by the
Gauss's lemma these two decompositions are
fundamentally the same (and only the former one may
be taken over ).
When it comes to
(terms of degree higher than are absobred by
either the term or the term ), for
integer , there's both and
,
so the decomposition is seemly not unique here.
In this text, we will study when and why would a
ring element in an integral domain be factorized
uniquely, so that we will be able to make
distinguishment of integral domains capable of
unique factorization from those incapable of.
Unique factorization domains
In order to define the "factorization", let's have
a closer look at the example of decomposition in
(which is unique by fundamental theorem
of arithmetic) and the one in and
. The natural numbers
are not closed under subtraction, so we prefer to
study the whole of integers , while in
, there's
, although we
perceive
indifferently. In , there's
,
although we still perceive
to be the same. So intuitively, in an integral domain
, when talking about factorization, as we're
always able to take out and cancel the units, we
would like to make the elements such that
equivalent,
and are said to be associate.
Also, we borrow the concept of irreducibility of
polynomials here. When talking about irreducibility
of polynomials, we only care about how it can be
decomposed into non-constant polynomials of lower
degree, a constant polynomial multiplies the one
associate with it trivially. In this way, for any
non-unit non-zero element , if it can be
written as product of non-unit non-zero elements
that ,
then it is said to be reducible. Conversely,
for an non-unit non-zero element that cannot be
written as product of non-unit non-zero elements,
then it's said to be irreducible. The units
and zero are neither reducible nor irreducible.
The problem remains as, for every non-unit non-zero
element in integral domain , it's either
irreducible or can be written as product of other
non-unit non-zero elements. We decompose these
elements in the product recursively, until it all
of the elements in the product are irreducible.
And given two such factorization of :
Where
are all irreducible. If there're and exists
, such that and
are associate pairwisely for
, then these two factorization
are equivalent. And for non-unit non-zero element
, among all its factorizations, there's
just a single equivalence class, then is said
to be uniquely factorized in . And if every
non-unit non-zero elements in can be uniquely
factorized, is said to be a unique
factorization domain, or UFD abbreviatedly.
Clarification of the introductory cases
Since we have now made the definition of "unique
factorization" clear, we can revisit the examples
provided in the introduction of this text.
The factorization of
is unique: if
is reducible, it can only be decomposed
into two polynomial of degree ; it must be
divisible by both and due to its
roots in ; for any irreducible
polynomial in potentially other factorization, it has
root other than , so the other factor of the
factorization must take the root both of the root
, while the other factor of the factorization
is of degree or to take roots, which
is a contradiction. So the factorization
is unique, and can
be uniquely factorized in .
Now consider the example of
that
.
First let's show that for any complex number, the
the norm function
defined by
has a homomorphic
property that
,
since there's:
Given that is a subring
of , we can trim the domain of norm
function to without
affecting its homomorphic property, with the
codomain trimmed to simultaneously.
In short, we get the trimmed norm function
defined by , with
.
Any for any unit
such that , the only possibility is
, which can only be taken at
, yielding to be the
only units. There's also no zero divisor in
, since if there were any
, by
it's only possible that
or , which means it's either or
. And is thus
an integral domain.
For the irreducibility, assume there's some
such that ,
then there must be either or
. The other solution besides to
is , which is
associate with , and there's no solution to
. For , there must be either
or , the other
solution besides to is
, which is associate with ,
and there's no solution to . For
, there must be either
or . The only
other solution besides to
is ,
and it's associate with ,
and there's no solution to .
The can also be tested in the
same way. So none of the
is reducible.
Finally, given there're two factorization of
with no possible permutation to make their
irreducible elements in the product associate
pairwisely, cannot be uniquely factorized in
, which is indeed not a UFD.
Principal ideals of the elements
When it comes to integral domain , a good thing
is that is a commutative ring with unity, so
the principal ideals are in the form of
.
And on the other hand, we could write that
,
although such notation would include both of the
associativity and reducibility, given that we can add
constraint on the factor if necessary, it won't hurt.
For two elements such that ,
given that , there're
and thus
.
A non-zero non-unit element is said to be prime
once its principal ideal is prime ideal, that if
then there's either
or ,
which is equivalent to saying if
then or , just like the Euclid's
lemma but this is for the integral domain's case.
Every prime element must be irreducible, otherwise
given that ,
there's but
, which is a
contradiction to 's being prime. Conversely an
irreducible element is not necessarily prime,
consider the example in ,
all of the
are irreducible, but none of them is prime.
Essence of unique factorization
Given that we've talked about the prime elements,
and there's irreducible element that is not prime in
general, we would like to show it's necessary for
all irreducible elements to be prime in a UFD.
Assume there's some irreducible element that is
not prime in a UFD , so that there's some
such that but
.
In this case, there's a irreducible factorization of
that has a irreducible factor , and another
irreducible factorization . Given that
is associate with neither nor , the two
factorization are not equivalent, thus cannot be
uniquely factorized in , and is not UFD, which
is a contradiction. In this way we've shown it's
necessary for all irreducible elements to be
prime in UFD.
Let's consider an integral domain such that
all irreducible elements are prime, is it enough
for us to derive the unique factorization? Consider
the process that we take an element for
factorization, first we find some non-unit non-zero
elements such that ,
then we could like to dive into both and
and decompose them in a depth-first traversal manner,
until we've reach the level that we are required to
decompose an irreducible element. But what if the
factorization could last for forever, while in
mathematics we don't care whether there's a
factorization algorithm that will eventually
terminate, but the factorization's lasting forever
means the length of the irreducible factorization
will be of infinite length. Back to the definition
of UFD, we've made guarantee on unique factorization
on only those of finite length, and the appearance
of such decomposition of infinite length are out
of scope and break our promise on the element's
properties. So we must require the decomposition
to be of finite length.
So now we have an integral domain such that
all irreducible elements are prime, and the
factorization of any non-unit non-zero element
is of finite length. Is it enough now? Let's test
it, first assume it's not a UFD by for element
there're two non-equivalent factorizations:
Without losing generality, let's assume it's
the case that .
Since is irreducible and is prime under
such context, and there's , one of
the , , ...,
must hold, and without losing
generality, let's assume it is the case that
, so and must be
associate, and let it be .
Given that is an integral domain, there's
no zero divisor, so we can safely cancel
out from both sides, leaving that:
Let's repeat the process of cancelation
exhaustively, until there're:
Assume , by associating all terms before
into , we have
, and thus is
a unit, which is a contradiction to 's
being an irreducible element. So it's only
, and all these
and are associate
pairwisely. The two factorizations must be
equivalent and thus can be uniquely factorized.
For now, we have reached the point to claim that
if in an integral domain, all irreducible
elements are prime and all non-unit non-zero
elements have factorization series of finite
length, then the integral domain is a UFD.
Principal ideal domains
Principal ideal domain, or abbreviatedly
PID is an integral domain where all ideals
are principal ideal. We have already encountered
instances of such kind of integral domains:
and .
The thing special about PIDs is that they fulfils
both criteria for UFD. And we will prove why does
it so in this section.
Irreducibility equals maximality in PID
In a PID , consider
the principal ideal of an irreducible element
.
Assume there were an ideal
such that
,
then there's . Since
,
cannot be a unit, and since
,
and are not associate. So it's only
possible for to be a non-zero non-unit element
that factorizes , however is irreducible,
which is a contradiction. In this way, we simply
shows that the principal ideals of irreducible
elements are maximal.
Conversely, let there be a maximal ideal
,
assume there's some non-unit non-zero element
such that , then we have
,
and thus is not maximal,
which is a contradiction. So the maximal ideal
can only be generated by an irreducible element.
For every irreducible element, its principal ideal
is maximal, and is thereby prime. In this way, we've
shown that every irreducible elements in a PID
is prime, fulfiling our first criterion for UFD.
Ascending chain condition of principal ideals in PID
Let's think about the process of decomposition
again, that .
By setting as root, each time we decompose
into product of two elements, like ,
we create a binary tree, where leaf nodes are
primes. When it comes to PID, given that all
ideals are principal ideals and the
correspondence between elements and their
principal ideals: the root node is the
principal ideal of the element we want to
decompose; every branch node
has two children by , and we have
;
every leaf node is a maximal or prime ideal. A
good thing about the tree is that associate
elements generate the same principal ideal. And
in this way, when there are any two distinct
binary tree of factorization, we could gather
their leaf nodes, and they are just a permutation
of another, otherwise there'll irreducible
element that is not prime, which is a contradiction.
More generally, an ascending chain in
is a chain of principal ideals in the form of
.
If we are able to prove that every ascending
chain has finite length, then for any binary
tree of factorization, let the longest path
inside be of finite length , then there're
at most nodes and between and
leaves, and the tree is therefore
finite. In this way, will fulfil the
second criterion for UFD.
To prove, let's consider the summation of
elements in an infinite ascending chain that
.
While such kind of stuff looks intimidating
at the first glance, we would like to have
a look at its set theoretic and topological
properties first. A question we would like to
think about carefully is, given a monotonically
increasing sequence of , that
and ,
what's the union of closed intervals
?
Is it or ?
To show it's the latter case, think of any
, since ,
by expressing it in language we have
,
by replacing with we
will get the corresponding such that
. But for
the right endpoint , given that
, there's no closed
interval to include this point, so it will not
be included in the final interval. In this way,
we have
and
.
Therefore, it's
.
More radically, each set gathers the
elements that fulfils certain condition relative
to , and there're
and
.
Look back to our case, to show that
is
an ideal of , consider:
- .
- ,
assume it's , then , so
.
- ,
.
And since
is an ideal of , it must be principal, and let
it be . Of course there's
, so
.
But if the ascending chain is infinite, there must
be a successor
,
and by set inclusion there'll be
,
which is a contradiction.
In this way, we've shown there's no infinite
ascending chain in a PID. Given that a PID
fulfils both criteria for UFD, we've proved
that PIDs are UFDs.
Euclidean domains
Besides all ideal's being principal, another common
point for and is both of them
have division algorithm defined on it. For specified
dividend and divisor , the division algorithm
yields quotient and remainder such that
, and for some "metrics"
, e.g. and
, there's .
The metric some how ensures that Euclidean algorithm
based on the division will eventually terminate at
, finding some for
input and .
And we would like to define the Euclidean domain
, which is an integral domain equipped with a
function
called the Euclidean valuation, and must fulfil:
- For any , we have .
- For any , always
exists , such that
with or .
Given that we can define valuation
for , and valuation
for , both and are
Euclidean domains.
Inequality properties of Euclidean valuations
We would like to derive some basic but useful
properties of Euclidean valuations before
digging into deeper.
The first one is the valuation get its minimal
value in . Given that
,
must be minimal among all elements
in . Meantime, given that
,
all must also be the
same, and minimal by .
The second one is for any ,
and ,
there's . To show, we
divide by , and there's
,
with either or
.
If , since there's
, and no zero divisor in ,
we can safely cancel out on both sides, leaving
and to be unit then,
which is the impossible case. When
,
given that there's
while neither
nor is zero, we have
,
and thus .
The third one is the valuation get its minimal
value only in . Based on the
previous property, we set , and there's
.
By combining with the first property that
,
we finally have
.
More specially, the valuation is said to be
multiplicative whenever there's
.
Given that
,
it's only possible for to
be or . When ,
there's some non-unit non-zero such that
,
so it's only possible for to be
in this case. Both the valuation
for and valuation
for are multiplicative.
Euclidean domains are PIDs
We would like to show Euclidean domains are PIDs.
Since we've already done something similar on
and , and the proof is just some
easy abstraction for them.
The zero ring and the whole ring can be seen as
being generated by or
. For some non-trivial
ideal , take any non-zero
and let
,
we'll check whether there's ,
if so, we are done; otherwise take any
, and let
,
and check whether .
We do such kind of thing iteratively, and we
could show such process will create a finite
monotonic ascending chain of principal ideal
with ,
in which serves as a reliable
stop signal, and must be among them.
To show the existence of ascending chain of
principal ideal, we prove by mathematical
induction that starting from
, for the principal ideal
obtained at step ,
,
yielding principal ideal
on step
with .
Since
,
the Euclidean algorithm yields non-zero value
such that . And in
detail, we divide by when
, or divide by
when . Whatever case yields
. Besides
the common divisor , the Euclidean
algorithm also yield the Bezout's identity that
.
Utilizing the Bezout's identity, for any
,
, so there's
,
and thus . In this way, the result
yielded by Euclidean algorithm is divisible by
any common divisor of and , and is
thus maximal.
On the other hand, for any
,
there's
.
Conversely, for any , there's
.
And thus we have
.
In such way, by letting , we have
with .
In this way, we've shown all Euclidean domains
are PIDs, and are therefore UFDs.
Application in algebraic integers
While Euclidean domains are fundamentally PIDs,
but they provides convenient language for proving
a given integral domain is a PID.
Consider the Gaussian integers
where
. Since
is the subring of
, we can make a trimmed norm function
defined by
with .
With this map, we can simply show the units of
are
, and there's
no zero divisor since
.
We would also like to show that can be
used as candidate for a multiplicative Euclidean
valuation. In the first place, by
,
it fulfils the first criterion for a
Euclidean valuation.
To show it also fulfils the second criterion for
a Euclidean valuation, we need to define its
division first: by dividing by
, we find quotient
and remainder such that
.
The way of doing such division is described in
a geometrical way. First, given that all points of
are in , and
is a 2-dimensional vector space of
, we can choose an orthogonal basis
, ,
and represent as
.
Then, we find some integers
such that ,
and is trapped in the square
pinpointed by
, aka
, , , .
Among these four vertices, we choose the closest
vertex to , and denote it as
. Since in the
square of edges' length , the distance of any
point inside (including edges and vertices) to
its closest vertex is no more than
, we have:
In this way, we've shown is truly a
Euclidean valuation for ,
and is a Euclidean
domain and thereby a UFD.
I guess you can't be more confused than now: we've
shown not to be a UFD, but
also shown the Gaussian integers
to be a UFD. While and
look exactly the same, and
have homomorphic map defined in the same
way, what makes diverge from
the ?
Obviously, given that norm function trimmed to
also fulfil
and , there's
for non-zero , so it
fulfils the first criterion, and we need to check
whether it also fulfils the second criterion.
When dividing by ,
we adapt the same way of choosing orthogonal basis
,
and represent as
. We pinpoint the "cage" with
to trap , but this time it's in
rectangle shape rather than square, given that
. If we choose the
closest vertex to
, in the rectangle of edges' length
and , the distance of any point inside
(including edges and vertices) to its closest vertex
is no more than , which is
greater than . So can't be used as
the Euclidean valuation for .
And given that not a UFD
by counterexample
,
there's no other possible Euclidean valuation
and it's impossible to be a Euclidean domain.
The integral domain which is subring of
is said to be norm-Euclidean when
the trimmed norm function
can be used as an Euclidean valuation, which in turns
imply that is an Euclidean domain. However,
not being norm-Euclidean does not necessarily mean
it can't be Euclidean. For example, it can be proved
that is Euclidean but not
norm-Euclidean, although it's too complex and we
will not prove it here.
Another classical example of norm-Euclidean domain
is the Eisenstein integers , where
is the cubic primitive root. In this case, the
norm function is trimmed to
defined by
.
When dividing by ,
we choose the basis
,
which tessellates the complex plane with rhombus
"cages". Again, we choose the most proximate vertex among
to . In a rhombus of edge length
, the maximal distance to the nearest vertices
is , which is reached at the
mass center of the two equilateral triangles
sticking together back-to-back to form the rhombus.
So we have:
And the Eisenstein integers
form norm-Euclidean domain.
Polynomial rings over UFDs
We've discussed about properties of
polynomials with integer coefficients ,
deriving some useful conclusions like Gauss's
lemma, Eisenstein's criterion, and so on. For
a polynomial ring over a UFD , given
that divisibility are defined, and irreducible
elements are primes, it sheds light on
generalizing these conclusions in
to .
More importantly, we would like to show
polynomial ring over a UFD is also
a UFD which is generally not a PID: like
, it's over which
is not a field, and the ideal
is
not principal: the common divisors of its
elements is , however
is not inside (while it is not a problem
for since there's
and
is inside); the polynomial ring
over UFD with
multiple indeterminates, whose ideal
is known not to be principal, can also be
shown to be UFD, by recursively breaking
and descending it through
,
proving every intermediate polynomial rings
to be UFDs in a last-in-first-out manner.
Gauss's lemma for polynomial rings over UFDs
For polynomial ring over UFD ,
polynomial
is said to be primitive when there's no
prime element , so that
. And for any
polynomial that is not primitive, we can
iteratively take common prime factors
(repetition is
allowed) of coefficients out, so that there's
where is called the content of
and is primitive, called the primitive
part of . The process should halt in
finite step otherwise the coefficients of
can be written as infinite product of prime
elements, which is a contradiction to 's
being UFD.
A primitive polynomial can only be factorized
into primitive polynomial: let be reducible by
and without losing generality, is not
primitive by .
Then given that
,
is not primitive, which is a contradiction.
Conversely, the product of two
primitive polynomials is also primitive,
otherwise assume there were , so
that there's or ,
and assume at least the former case is true.
Since cannot divide every coefficient of
, let be the coefficient such that
while ,
and be the coefficient such that
while .
Consider the coefficient :
Which is a contradiction. So the product of
primitive polynomial can only be primitive.
Since is also an integral domain, we can
also extend and embed into its field of
fractions , so that we have
, but we can also draw a
conclusion that a primitive polynomial is
reducible over iff it's reducible over
. First we would like to show that
every polynomial
is convertible into
where and
is primitive: let's take all denominators
out so that there's
,
noted that there's
since is embedded into injectively
by ; then we
into its content and parts so that
there's ; finally we
have and we are done.
Then for some polynomial that
is reducible over by
with , let's do such process
for so that there's
,
let
where there's no common prime element
such that . If
both are units, we are done. Otherwise
let ,
if is unit while is not, for some
prime , by observing that
,
we have so is not primitive;
if is not unit, since
, there must be
,
for any prime element such that
, it's only possible
that , leading to 's
not being primitive. So the only possibility is
that both are units. In this way, is
reducible over by
with .
Conversely, a factorization of
with is also a factorization in
by . So the
reducibility of primitive polynomial in
is just the same as the one in .
For those who are familiar with Gauss's lemma
for polynomials with integer coefficients, these
proofs are nothing more than simple migrations
into polynomials over UFDs.
Eisenstein's criterion for polynomial rings over UFDs
Let's make a quick work of it. The Eisenstein's
criterion for over UFD states
that a primitive polynomial
is
irreducible when there's a prime
such that
.
Assume is reducible by
,
since there's
,
and while
implies it's either
or
. Assume it's
the former case, so there's a coefficient
such that while
, but there's
,
which is a contradiction. So polynomial
must be irreducible when it fulfils the
Eisenstein's criterion.
Polynomial rings over UFDs are UFDs
For any polynomial
, we will
first factorize its content and primitive part,
and then furtherly factorize content and
primitive part correspondingly. Assume there're
two distinct factorizations:
Where
are the factorization of content and must be
irreducible elements over ; and
are the factorization of primitive part and
must be irreducible polynomials over .
Such two factorizations over are also
factorizations over . We've proved that
all ideals of a polynomial ring over field are principal,
so is a PID and thus a UFD. The
elements and
are elements of
and thus units in , while
irreducible polynomials
are irreducible elements, so there must be
while exists such
that and are associate by
.
For two primitive polynomials
that are associate in , obviously there be
and ,
while it still remains unknown whether
are non-units but coprime. Assume it's currently
such case, however, since are polynomials
in , for each coefficients there's
.
For any prime , it's
the case that , and therefore
is not primitive; for any prime
, it's the case
that , and therefore is
not primitive. Both cases are impossible,
so it's only possible that are
units, and
.
In this way, it's actually the case that
.
Their products
and are also
associate in (as is said,
and
are elements of
and thus units in ), and by Gauss's
lemma they are also primitive, so there's
,
and therefore
.
Since is UFD, it's only possible that
and such
that and are associate by
.
By now, we've reached a point that in the
polynomial ring over a UFD , no
matter the decomposition of content into
irreducible elements or the decomposition
of primitive part into irreducible primitive
polynomials should be unique, and is
indeed a UFD.
And from the conclusion we know polynomial
rings like , ,
over UFD
are all UFDs, although none of them is PID.
Conclusion
In this text, we've first given exact
definition of unique factorization that a
non-unit non-zero element is said to be
uniquely factorized in the integral domain
when any pair of its decomposition into
irreducible elements have the same length
while there's a way to match every pair
of factor irreducible elements so that
they're associate pairwisely. By digging
into the essence of unique factorization,
we've concluded that an integral domain
that every non-unit non-zero can be uniquely
factorized, which is known as the unique
factorization domain (UFD), the factorization
series of all non-unit non-zero element should
have finite length, while all irreducible
elements must be prime in the domain.
These two criterion are sufficient and
necessary for a integral domain to be UFD.
In order to fulfil the criterion, from the
classical examples and
we've learned before this text so far, we
test the integral domain in which every
ideal inside is principle, which is known
as the principal ideal domain (PID). And
in this domain, all principal ideals of
irreducible elements are maximal and thus
prime, while having an infinite ascending
chain of principal ideal will surely
violate the constraint that every ideal
should be principal. So in this way, we've
proved that all PIDs are UFDs.
On the other hand, we've also generalize
the integral domain equipped with Euclidean
algorithm and Bezout's identity into
Euclidean domain. By putting constraint on
the greatest common divisor every time
we'll obtain by Euclidean algorithm, the
Euclidean valuation, which is a way to
"measure" the distance of a principal ideal
(corresponding to the current greatest
common divisor) to the whole ideal, we are
able to trap the every ideal into a finite
chain of principal ideal, and thus every
ideal in Euclidean domain is principal,
and it is indeed a UFD. Euclidean domain
comes in handy for proving integral domains
equipped with proper division and Euclidean
algorithm to be UFDs, like the Gaussian
integers and the
Eisenstein integers .
Finally, we've inspected the polynomial
rings over UFDs. In these rings, we are
able to define similar concepts and
conclusions to those in ,
like the primitive polynomial, Gauss's
lemma and Eisenstein criterion. And most
importantly, for any polynomial ring
over a UFD , by utilizing the
unique factorization property in
and , fundamental properties
of associate primitive polynomials in ,
and Gauss's lemma, we've successfully
proved that is also a UFD although
it's generally not a PID.
By now, we should be familiar with concepts
and basic examples of unique factorization
domains, which are foundations of the
upcoming theories.