Failure Of Unique Factorization
A simple example of the failure of the fundamental theorem of arithmetic
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
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 
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 
Clearly 
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 
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 
Every Hilbert number greater than 
The key observation is that some Hilbert numbers can be factored in more than one way:
Thus FTA fails for Hilbert numbers.
Another popular example of the failure of FTA uses square roots.
Note the numbers then are all those of the form:
where 
satisfy the FTA.
Even Simpler
Let us consider an extremely complex subset of the natural numbers:
Okay 
-
The primes in
-
Every number in
-
The factorization in
Let’s look at each of these in turn. A prime in 
Note, this process now stops, since 
Note, the factorizations are different. For example,
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]
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/
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.
I love this newsletter.
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.
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.
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
(claiming that “the counting numbers and the odd counting numbers are the only such sets with unique factorization”), but proofs are not included.
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!
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.
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.