Lack of unique factorization of ideals

In the ring ${\mathbf Z}[\sqrt{-3}]$, the ideal $P = (2,1+\sqrt{-3})$ is prime since it has index 2 in the ring. Note $P^2 = (4,2+2\sqrt{-3},-2 + 2\sqrt{-3}) = (4,2+2\sqrt{-3}) = (2)(2,1+\sqrt{-3}) = (2)P$, where $(2)$ is the principal ideal generated by 2 in ${\mathbf Z}[\sqrt{-3}]$. If there were unique factorization of ideals into products of prime ideals in ${\mathbf Z}[\sqrt{-3}]$ then the equation $P^2 = (2)P$ would imply $P = (2)$, which is false since $1+\sqrt{-3}$ is in $P$ but it is not in $(2)$.

In fact we have $P^2 \subset (2) \subset P$ and this can be used to prove the ideal (2) does not even admit a factorization into prime ideals, as follows. If $Q$ is a prime ideal factor of (2) then $(2) \subset Q$, so $PP = P^2 \subset Q$, which implies $P \subset Q$ (from $Q$ being prime), so $Q = P$ since $P$ is a maximal ideal in ${\mathbf Z}[\sqrt{-3}]$. If (2) is a product of prime ideals then it must be a power of $P$, and $P^n \subset P^2$ for $n \geq 2$, so the strict inclusions $P^2 \subset (2) \subset P$ imply (2) is not $P^n$ for any $n \geq 0$.

The "intuition" that the ideal $P = (2,1+\sqrt{-3})$ is the key ideal to look at here is that $P$ is the conductor ideal of the order ${\mathbf Z}[\sqrt{-3}]$. The problems with unique factorization of ideals in an order are in some sense encoded in the conductor ideal of the order. So you want to learn what a conductor ideal is and look at it in several examples. For example, the ideals $I$ in ${\mathbf Z}[\sqrt{-3}]$ which are relatively prime to $P$ (meaning $I + P$ is the unit ideal (1)) do admit unique factorization into products of prime ideals relatively prime to $P$. That illustrates why problems with unique factorization of ideals in ${\mathbf Z}[\sqrt{-3}]$ are closely tied to the ideal $P$.

If you look at the ideal notation $P' = (2,1+\sqrt{-3})$ in the larger ring ${\mathbf Z}[(1+\sqrt{-3})/2]$, which we know has unique factorization of ideals, then we don't run into any problem like above because $P' = 2(1,(1+\sqrt{-3})/2) = (2)$ in ${\mathbf Z}[(1+\sqrt{-3})/2]$, so $P'$ is actually a principal ideal and the "paradoxical" equation $PP = (2)P$ in ${\mathbf Z}[\sqrt{-3}]$ corresponds in ${\mathbf Z}[(1+\sqrt{-3})/2]$ to the dumb equation $P'P' = P'P'$. (The ideal $P'$ in ${\mathbf Z}[(1+\sqrt{-3})/2]$ is prime since the quotient ring mod $P'$ is a field of size 4: ${\mathbf Z}[(1+\sqrt{-3})/2]$ is isom. as a ring to ${\mathbf Z}[x]/(x^2+x+1)$, so ${\mathbf Z}[(1+\sqrt{-3})/2]/P' = {\mathbf Z}[(1+\sqrt{-3})/2]/(2)$ is isom. to $({\mathbf Z}/2{\mathbf Z})[x]/(x^2+x+1)$, which is a field of size 4.)

The arithmetic of nonmaximal quadratic orders comes up naturally when studying binary quadratic forms, so in particular Cox's book contains some discussion of this.

As it happens, when I taught a course based (sometimes closely, sometimes not) on Cox's book, I included a "case study" of factorization in the ring $\mathbb{Z}[\sqrt{-3}]$: see Section 3 of these notes.

Hint $\ $ Given any fraction $\rm\,w\,$ witnessing that the nonmaximal order $\rm\,D\,$ is not integrally closed, i.e. a proper fraction over $\rm\,D\,$ that's a root of a monic $\rm\,f(x)\in D[x],\,$ the proof below shows, for the fractional ideal $\rm\ I = (w,1),\ \ I^{\:\!n} =\, I^{\:\!n-1},\,$ but $\rm\ I\ne 1\,$ (by $\rm\,w\not\in D$), $\,$ contra unique factorization. Here $\rm\, n=2,\ w = (-1 + \sqrt{-3})/2\ $ is integral over $\rm\,D = \mathbb Z[\sqrt{-3}],\,$ being a root of $\rm\,x^2+x+1\,.$

Alternatively, clearing denominators from the fractional ideals to obtain integral ideals, we obtain $\rm\ J^2 =\, 2\:\!J,\,$ but $\rm\ J \ne (2),\,$ for $\rm\, J = 2\,(w,1) = (-1+\sqrt{-3},\,2),\, $ also contra unique factorization. For further remarks, including relations with Dedekind's conductor ideal and irrationality proofs, see my discussion with Gerry Myerson here and here in a sci.math thread circa May 20, 2009. Below is an excerpt from the first linked post, followed by an excerpt of the second (first we use fractional ideals, which we then eliminate, for readers knowing only integral ideals).

Theorem $\ $ Dedekind domains $\rm\,D\,$ (so PIDs) are integrally closed.

Proof $\ $ Suppose a fraction $\rm\,w\,$ over $\rm\,D\,$ is integral over $\rm\,D,$ i.e. in terms of $\rm D$-fractional ideals

$$\begin{align} \rm suppose \,\ \ \color{#c00}{w^n}\,\ &\rm\in\qquad (w^{n-1},\ldots,w,1)\,.\quad\quad\ \ \color{#0a0}{[*]}\\[.4em] {\rm Since}\ \rm\, (w,1)^n\ &\rm =\ (\color{#c00}{w^n},w^{n-1},\ldots,w,1) \\[.4em] &\rm =\qquad (w^{n-1},...,w,1)\ \ \ \rm by\,\ \ \color{#0a0}{[*]}\\[.4em] {\rm i.e.}\, \ \ \ \rm\ (w,1)^n\, &\rm =\ (w,1)^{n-1}\\[.4em] \rm thus\ \ \ \,(w,1)\ \ &\rm =\ (1)\ \text{ by cancelling invertible ideal }\ (w,1)^{n-1}\\[.4em] \rm therefore\,\ \ \ w\ &\rm \in\ \:\!(1) = D,\ thus \ D\ is\ integrally\ closed. \quad \small \bf QED \end{align}\qquad\quad $$

Remark $\ $ A common similar proof cancels $\,\rm I\,$ from $\rm\ I^2 =\, I,\ \ I = (w^n,...,w,1)\,.$

Note $ $ If fractional ideals are unfamiliar then we can clear denominators from the prior proof by scaling it by $\rm\, b^n,\,$ where $\rm\ w = a/b,\,$ i.e.

$$\begin{align}\rm (w,1)^n\ &\rm =\ (w,1)^{n-1}\ \text{ which, upon scaling through by }\ b^n\\[.4em] \rm \Rightarrow\ \ \ (a,b)^n\, &\rm =\ b\ (a,b)^{n-1}\\[.4em] \rm \Rightarrow\ \ \ (a,b)\ \ \, &=\rm\ (b)\ \ \text{by cancelling the invertible ideal }\ (a,b)^{n-1}\ \ from\ above\\[.4em] \Rightarrow \rm \quad b\mid a\ \ \ &\rm in\ \ D,\ \ i.e.\ \ a/b\in D \end{align}\quad$$

See here for a more detailed proof in the cubic case.

Gerry Myerson [email protected] wrote on May 19, 2009, 7:56:35 PM:

Bill Dubuque [email protected] wrote:

The (monic) Rational Root Test is essentially equivalent to the fact that the domain of integers is integrally-closed. If you examine the elementary direct proofs from this more general standpoint they're essentially all equivalent. This is evident and trivial to anyone familiar with notion of conductor ideals (dating back to Dedekind). Alas, apparently not all number-theorists are familiar with this basic notion, e.g. see Gerry Myerson's post [1] where he rediscovers the well-known elementary inductive proof that obtains from unwinding the elegant one-line conductor-based proof. Further, in the same thread, he seems to lend support to the absurd claim by Estermann (and Niven?) that this proof is new. Nothing could be further from the truth. Such methods are merely elementary manifestations of the raison d'etre for the abstraction incorporated in the conductor ideal. This fundamental object is introduced very early in any study of algebraic number theory and the perceptive student should easily recognize the fundamental role it plays in more concrete instances.

[1] Gerry Myerson, sci.math post on 2006/7/12 Thread: Irrationality and the Fundamental Theorem of Arithmetic

Readers may be interested in my paper, Irrationality via well-ordering, Australian Math. Soc. Gazette 35 (2008) 121-125, available on the web at http://www.austms.org.au/Publ/Gazette/2008/May08/Myerson.pdf

A better title would be "Irrationality via the Division Algorithm" (or "via the Euclidean Algorithm") since your proofs there are simply well-known proofs of PID results that've been pulled-back to Euclidean domains by eliminating ideal-theoretic notions. More on this below.

It is misleading to say the the proofs are "via well-ordering". Rather, the proofs depend crucially on a domain $D$ being Euclidean. This requires not only a "size" map from $D$ into a well-ordered set, but also, crucially, a Division Algorithm with respect to the map. Euclideaness is used implicitly in your proofs when you take the integer or fractional part of a fraction to help achieve a descent on possible denominators for $\,w = \sqrt m\,$ (or $w$ an algebraic integer).

In that paper, you'll find,

THEOREM $2$. If $m$ is an integer, and $\sqrt m$ is not an integer, then $\sqrt m$ is irrational.

Proof. Assuming $\,w = \sqrt m\,$ is rational but not an integer, let $k$ be the integer such that $k < w < k+1,$ and let $n$ be the smallest positive integer such that nw is an integer; then $n(w-k)$ is a smaller positive integer whose product with $\sqrt m$ is an integer, contradiction.

That's very well-known and very widely published.

You'll also find the theorem stating that the integers are integrally closed in the rationals;

THEOREM $5$. Let $f$ be a monic polynomial with integer coefficients. Let $w$ be a solution of $f(w) = 0.$ Then if $w$ is not an integer, it is irrational.

Proof. Assume the hypotheses, assume $w$ is rational, and let $n$ be the smallest positive integer whose product with $w^j$ is an integer for all $j$ less than the degree of $f$. Then $n$ times the fractional part of $w$ is a smaller positive integer with the same property, contradiction.

Again that's very-well known and I do recall seeing it published at least a handful of times if not more. Notice that your $\,n\,$ is simply a least common denominator for the fractions $w^j.\,$ More structurally consider instead the universal denominator set $\,C\subset \Bbb Z\,$ for the whole ring $\,\Bbb Z[w],\,$ i.e. $\,C\, \Bbb Z[w] \subseteq \Bbb Z,\,$ i.e. $\,C = \{n \in \Bbb Z\ :\ n f(w) \in \Bbb Z,\, \forall\ f(w) \in \Bbb Z[w]\}$. This yields an ideal $\,C\,$ known as the conductor of $\,\Bbb Z[w]\,$ into $\Bbb Z.$

$C\,$ satisfies the crucial property that $\,n \in C \Rightarrow nw \in C,\,$ simply because $\,w\,$ is integral over $\,\Bbb Z\,$ (i.e. $\,w^k\,$ is a $\,\Bbb Z$-linear combination of $\,w^j,\,$ for $\,j < k = \deg w).\,$ This then implies that $\,C\,$ is not only an ideal of $\,\Bbb Z,\,$ but also of $\,\Bbb Z[w]\,$ (in fact the largest such ideal). But since $\,\Bbb Z\,$ is a PID, the conductor ideal is principal $\,C = n\Bbb Z\,$ so $\,nw \in C = n\Bbb Z \Rightarrow\, w \in \Bbb Z.\,$ So we've proved any fraction integral over a PID actually lies in it, i.e. PIDs are integrally closed.

Your proofs essentially proceed the same way except you have eliminated the lemma that $\,\Bbb Z\,$ is a PID by repeating the proof of the Lemma ("inlining" it) in your descent-based proof on denominators, i.e. $\,n \in C \Rightarrow nw \in C \Rightarrow n(w-k) \in C,\,$ for $\,k = {\rm integer\_part}(w).\,$ But $\,0 < n(w-k) < n,\,$ via $\,0 < w-k < 1,\,$ so $\,n(w-k)\,$ is a smaller denominator than $\,n.\,$ This is equivalent to descent-based proof that the denominator ideal $\,C\,$ is principal. It's essentially a special case of the the standard Euclidean descent proof that Euclidean $\Rightarrow$ PID, i.e. if $\,n\,$ is the smallest elt of $\,C\,$ then $\,n\,$ must divide every other elt $\,m\,$ of $\,C,\,$ else Euclidean division yields a smaller elt $\,m \bmod n \in C,\,$ contra minimality of $\,n.\,$ Above is just the special case $\,m = nw,\,$ which yields $\,n\mid nw\,$ in $\,\Bbb Z,\,$ i.e. $\,w\in\Bbb Z.$

Here is how I like to present this proof in structural form:

The conductor ideal of a domain extension $\,D \subset E\,$ is $\,C = \{d \in D\ :\ dE \subseteq D\}$.

One easily sees $\,C = CD = CE,\,$ i.e. $\,C\,$ is an ideal of both $\,D\,$ and $\,E$.

$C\neq \{0\}\,$ & $\,D\,$ PID $\Rightarrow C = cD = cE \Rightarrow D = E\,$ via cancel $\,c \neq 0.\ \ $ [*]

Said proof is just the special case $\,C,D,E = n,\,\Bbb Z,\,\Bbb Z[w].\,$ Here $\,C\neq \{0\}\,$ since $\,w = a/b,\,$ $ \deg f = k \Rightarrow b^{k-1} \in C,\,$ i.e. $\,b^{k-1}\,$ is a denominator for all elts of $\,\Bbb Z[w] = \Bbb Z\langle 1,w,w^2,..,w^{k-1}\rangle$.

Notice how simple the proof has become when expressed in the appropriate abstractions: it is a trivial one-line proof [*] based on the conductor ideal, being principal, is cancellable. More generally, cancellable/invertible ideals (esp. Dedekind domains) play a fundamental role in algebraic number theory.

I ask in the paper for the earliest publications of these (and other) proofs in the form in which I relate them. This form may well be merely an elementary manifestation of the conductor ideal, but I reckon there's a lot to be said for elementary manifestations. In particular, students who are still years away from learning about conductor ideals can still understand, maybe with a little help, the proofs above.

The same might be argued for analogous "elementary" proofs that've had their higher-order structure removed, e.g the famous proof (better here) of unique factorization by Klappauf, Lindemann, Zermelo that I cited earlier in this thread. It isn't published too frequently (except as a curiosity) because it obfuscates the underlying algebraic structure and hence has little pedagogical value. Someone ignorant of the relevant algebraic theory might stumble upon such proofs with great effort. But someone familiar with the theory can mechanically churn out these monstrosities by simply rewriting the higher-order proofs to use only the most primitive notions - eliminating structure (rings, ideals, etc.) Indeed, the process is so mechanical that one could easily program a computer to perform such proof transformations.

The earliest publication I've seen of the proof given above for Theorem 2 is the 1975 paper of Estermann. I haven't seen any print publication of the proof of Theorem 5 given above, but it was posted to this newsgroup in July 2000, and I've seen it on the web. There may well have been earlier appearances of these proofs in the form given here, and I'd like to see them.

There's little point in doing such for the reasons enumerated above. The conductor-based ideas are over a century old - dating back to the ground-breaking work of Dedekind. It's highly likely that the proof is already in Dedekind's work (perhaps implicitly since there are various ideal-theoretic forms of such proofs).

Alas, no one has yet tackled the enormous task of writing the definitive history of unique factorization - where many of these topics would be discussed. I once thought I might do such and had many files of papers of historical significance to aid in this endeavor. However I no longer have these available since they were among items that were stolen while in storage. But nowadays such a task should be easier since many older papers are now much more easily accessible in electronic archives.

Let me take an example with no fractions, Z[2i]=Z[x]/(x^2+4). Now (2+2i)*(2-2i) = 8, but 2+2i is irreducible. So that is a little crazy.

What about the ideal (2)? In the quotient ring we have Z[x]/(2,x^2+4) = Z[x]/(2,x^2) is not a domain, so (2) is not prime. How does it factor into prime ideals?

I claim it doesn't. It ought to factor into (1+i)*(1-i), but there are no such elements in Z[2i]. How to prove it? Well if J = P*Q, then at least J ≤ P, so let's look for primes above (2).

Z[x]/(2,x^2) is a nice local ring with a unique maximal ideal (2,x)/(2,x^2), which pulls back to (2,2i). Since there is only one prime above J=(2), we must have J is some power of P=(2,2i), or else J has no such prime factorization.

Well P*P = (4,4i,-4) = (4,4i) does not contain 2, so that is done. J has no prime factorization.

In case you want to stick with the evil Dr. √−3 and his house of lies, Z[√−3] = Z[x]/(x^2+3), here is an example there:

(1+√−3)(1-√−3) = 4, but 2, 1+√−3, and 1-√−3 are all irreducible. Evil.

What about the ideal (2)? In the quotient ring we have Z[x]/(2,x^2+3) = Z[x]/(2,(x+1)^2) is again not a domain, so (2) is not prime. How does it factor into prime ideals?

I claim it doesn't. (I am little unclear on what it should factor into, since (1+√−3)/2 is a unit, rather than a prime). At any rate, we look for prime ideals above it.

Since Z[x]/(2,(x+1)^2) is a nice local ring with unique maximal ideal (2,x+1)/(2,(x+1)^2) that pulls back to (2,1+√−3), we see that if J=(2) has a factorization into prime ideals, it must be a power of P=(2,1+√−3). However, P*P = (4,2+2√−3,−2+2√−3) = (4,2+2√−3) does not contain 2. Hence J has no such factorization into prime ideals.