Skip to content

Failure Of Unique Factorization

January 30, 2016
tags: , , ,


A simple example of the failure of the fundamental theorem of arithmetic

ernst-eduard-kummer2

Ernst Kummer was a German mathematician active in the early 1800s. He is most famous for his beautiful work on an approach designed to solve Fermat’s Last Theorem (FLT).

Today we will talk about a barrier that stopped his approach from succeeding.

I am currently teaching basic discrete mathematics at Tech. The first topic is elementary number theory, where we have covered some of the key properties of primes. Of course, we have covered the Fundamental Theorem of Arithmetic (FTA). Recall it says:

Theorem: Every natural number greater than {1} is the product of primes, and moreover this decomposition is unique up to ordering of the primes.

This is a classic theorem, a theorem that is fundamental to almost all of number theory. It was implicit in Euclid’s famous work, and was perhaps stated and proved precisely first by Carl Gauss in his famous Disquisitiones Arithmeticae.

The Barrier

Alas as Kummer discovered the FTA fails for other sets of numbers. For other types of numbers half of the theorem still holds: every number that is not a generalization of {1} can still be written as a product of “primes.” But uniqueness is no longer true.

In 1847, Gabriel Lamé claimed, in a talk to the Paris Academy, that he had solved FLT by using complex numbers—in particular numbers that were generated by the {p}th roots of unity. Recall those are complex numbers that are solutions to the equation

\displaystyle  x^{p} = 1.

Clearly {1} is a solution always, but for primes {p} there are other solutions: {p-1} in total. Lamé’s argument was perfect, rather easy, used standard arguments, and was incorrect. The great mathematican Joseph Liouville at the talk questioned whether Lame’s assumption about unique factorization was justified; and if not, it followed that the proof was not valid. See here for a fuller discussion of this.

Liouville’s intuition was right. The FTA failed for Lamé’s numbers. Weeks after Lamé’s talk, it was discovered that Kummer had three years earlier shown that FTA indeed held for some primes {p} but failed for {p=23}. One might guess that the reason Lamé, and others, thought that factorization was unique for these numbers is that the first counterexample was for {p=23}. Kummer famously showed that FTA could be replaced by a weaker and very useful statement, which allowed his methods to prove FLT in many cases. But not all.

Failure In Simpler Systems

The failure of FTA for what is now called cyclotomic integers is a well studied and important part of number theory. It is well beyond my introductory class in discrete mathematics. This failure has led to the discovery of related failures of uniqueness. One of the classic examples is the Hilbert Numbers—named after David Hilbert—of course.

Hilbert numbers are the set of natural numbers of the form {4n + 1}. Thus they start:

\displaystyle  1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, \dots

Every Hilbert number greater than {1} is the product of “Hilbert primes.” But note that a number can be prime now without being a real prime, that is a prime over all the natural numbers. Note that {9} is a Hilbert prime: it cannot be factored as {3 \cdot 3}, since {3} is not a Hilbert number.

The key observation is that some Hilbert numbers can be factored in more than one way:

\displaystyle  441 = 9 \cdot 49 = 21^{2} .

Thus FTA fails for Hilbert numbers.

Another popular example of the failure of FTA uses square roots.

\displaystyle  6 = 2 \cdot 3 = (1 + \sqrt{-5}) \cdot (1 - \sqrt{-5}).

Note the numbers then are all those of the form:

\displaystyle  a + b\sqrt{-5},

where {a,b} are integers. Many examples can be created in this way by changing {-5} to other integers. It is a major industry trying to understand which {d} yield a set of numbers so that

\displaystyle  a + b\sqrt{d},

satisfy the FTA.

Even Simpler

Let us consider an extremely complex subset of the natural numbers:

\displaystyle  E = \{ 2x \mid x \in \mathbb{N} \}.

Okay {E} is just the set of all even numbers. This set is closed under addition and multiplication, and we claim that it has the following nice properties:

  • The primes in {E} are easy to describe;

  • Every number in {E} is a product of primes;

  • The factorization in {E} is not unique.

Let’s look at each of these in turn. A prime in {E} is {2w} where {w} is an odd natural number. The usual argument shows that every number in {E} is a product of primes. For example:

\displaystyle  72 = 2 \cdot 36 = 2 \cdot 2 \cdot 18.

Note, this process now stops, since {18} is a prime. The last part showing that FTA fails in this setting is easy: Let {a,b,c,d} be distinct odd primes. Then

\displaystyle  4abcd = 2ab \cdot 2cd = 2ac \cdot 2bd.

Note, the factorizations are different. For example,

\displaystyle  2ab \neq 2ac \text{ and } 2ab \neq 2bd.

Open Problems

Does the simple example of even numbers help in understanding why FTA is special? Where was it first stated in the literature that even numbers fail to satisfy unique factorization? We cannot find it after a quick search of the web: all examples we can find are either the Hilbert numbers, some examples using square roots, or something even more complex.


[fixed some formatting issues]

11 Comments leave one →
  1. January 30, 2016 11:35 am

    My favorite question in this realm is how much of the linear ordering of the natural numbers is “purely combinatorial”, where we eliminate all the structure that isn’t purely combinatorial via the “doubly recursive factorizations” of whole numbers, ending up with graph-theoretic structures that I dubbed Riffs and Rotes. See this link for more discussion and further links:

    http://inquiryintoinquiry.com/2013/03/03/riffs-and-rotes-2/

  2. January 30, 2016 11:54 am

    nice highlights but… words/ frames matter… is there some way to talk about it other than a “failure”? that seems an anthropomorphism or even a twist/ “failure” on wishful thinking.

  3. January 30, 2016 3:11 pm

    I love this newsletter.

  4. January 30, 2016 6:12 pm

    Very interesting post as usual.

    I suspect that you will find this paper by Bas Luttik and Vincent van Oostrom interesting: http://dx.doi.org/10.1016/j.tcs.2004.11.019

    It present a rather general result guaranteeing unique decomposition into “primes” with applications, mostly in the setting of concurrency theory, where an operation for “running processes in parallel” corresponds to multiplication.

  5. January 30, 2016 7:27 pm

    This is a lovely example. I was unaware of the even numbers example or the Hilbert numbers, and both give very clear instances of the failure of unique factorization. The strength of these examples is that it is very clear what “prime”, “integer”, and “divides” mean in this context. In the examples over quadratic fields one must simultaneously introduce these other concepts and it can get a little confusing what the crux of the matter is.

  6. February 1, 2016 12:42 pm

    The example about the factorisation of even numbers is really nice, and in particular because the property involved is described solely using multiplication, while Hilbert numbers are described with the additional help of the successor function. There is an interesting paper from 1967 that mentions this example in its first paragraph. It is also discussed in the last two pages of this other paper, two years before. Finally, this paper from 1957 had announced general results for sets of natural numbers of the form Ax+B (claiming that “the counting numbers and the odd counting numbers are the only such sets with unique factorization”), but proofs are not included.

    • February 14, 2016 12:49 pm

      When I first read your comment, I thought “this example” meant the Hilbert numbers, not the even positive integers. So in fact you are giving a citation which is much older than the one I wrote about below. Thanks for this!

  7. Ruslan Kolosenko permalink
    February 2, 2016 11:43 pm

    Thank you for the interesting article.
    But looks like there is some confusion between prime elements (https://en.wikipedia.org/wiki/Prime_element) and irreducible elements (https://en.wikipedia.org/wiki/Irreducible_element).
    A prime in E is 2p where p is an odd prime natural number.
    And an irreducible element in E is 2w where w is an odd natural number.

  8. February 14, 2016 12:45 pm

    The even positive integers E as an example of non-unique factorization occurs in Joseph H. Silverman’s _A Friendly Introduction to Number Theory_, I believe already in the 1997 first edition. This is a popular text, and if one googles under the unlikely name “E-Zone”, one can find many instances of this example on the web.

    This example is reproduced on p. 15 my number theory notes (written in 2007)

    http://math.uga.edu/~pete/4400FULL.pdf

    In a footnote on that page I suggest that the example goes back at least to Harold Stark’s (significantly older) number theory text. Unfortunately I just flipped through Stark’s text and was unable to find this example there. I should probably contact Joe Silverman to get some fact checking on this.

    I don’t like the example E so much. The modern perspective on unique factorization is that it takes place in a commutative, cancellative monoid: i.e., you have a set endowed with one operation * which is commutative, associative, has an identity element, and if a*b = a*c then b = c. In the example E there is no identity element. (You could just put it in, but now it looks more contrived.) The example H = {4k + 1 | k is a positive integer} is indeed the most natural counterexample from this abstract perspective.

    Here are two examples I like better:

    (1) Let N > 2 be an integer. Then the ring Z[\sqrt{-N}] = {x + y \sqrt{-N} | x,y are integers}
    does not have unique factorization. This can be related to the representation of primes by the binary quadratic form x^2 + Ny^2. Once this correspondence is developed (it takes about a page), one observes that 2 is certainly not of the form x^2 + Ny^2 (since N > 2)
    whereas -4N certainly is a square modulo 2 (every integer is!). This is “real life”.

    (2) The ring R[sin theta, cos theta] of real trigonometric polynomials does not have unique factorization. Indeed cos theta, 1 + sin theta and 1- sin theta are all nonassociate irreducibles and

    (cos theta)(cos theta) = (1+sin theta)(1-sin theta).

    (To check the former statement does require some work: this is done in an elementary manner in a nice article of Trotter cited in my notes.) This is really a real life example.

Trackbacks

  1. Riffs and Rotes : 3 | Inquiry Into Inquiry
  2. Failure Of Unique Factorization – Is it behind the rabbit?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s