# Failure of Unique Factorization (Lec. 4, Wednesday, January 27)

## Revisiting a Counterexample to Unique Factorization

:::{.remark}
Today roughly corresponds to chapter 4: "Paradise Lost"!
Setup: $K$ is a quadratic field, a degree 2 extension of $\QQ$, which can be written as $K = \QQ(\sqrt{d})$ with $d$ squarefree.
Last time, we completely described $\ZZ_K$ (the algebraic integers in $K$):
\[
\ZZ_K = 
\begin{cases}
\ZZ[ \sqrt{d} ] &  d \equiv 2,3 \mod 4
\\
\ZZ\left[{1 + \sqrt{d} \over 2}\right] & d \equiv 1 \mod 4.
\end{cases}
\]
We saw that the second admitted a different description as $\ts{ {a + b \sqrt{d} \over 2}}$ where $a,b$ are either both even or both odd.
Note that we can do interesting arithmetic in $\ZZ_K$, but it's not necessarily well-behaved: $\ZZ_K$ is not always a UFD.
:::

:::{.example title="A counterexample to unique factorization"}
Letting $d=-5$, we have $\ZZ_K = \ZZ[ \sqrt{-5} ]$ where $6$ factors in two ways: 
\[
6 = (1 + \sqrt{5} )(1 - \sqrt{-5} ) = (2)(3) = 6
.\]

Note that this isn't quite enough to show failure of unique factorization, e.g. we can factor $16 = (4)(4) = (2)(8)$.
Here you should check that all 4 factors are irreducible, and that the factors on the right aren't unit multiples of the ones on the left.
For example, $21 = (-7)(-3) = (7)(3)$, but the factors only differ by the unit $-1\in \ZZ\units$.
The key to checking all of those: the **norm map**:
\[
N(a + b \sqrt{-5} ) = (a + b \sqrt{-5} ) (a - \sqrt{-5} ) = a^2 + 5b^2
.\]
where the second factor was the *conjugate*, i.e. the image of the element under the nontrivial element of the Galois group of $K_{/\QQ}$.
If $a + b \sqrt{-5} \in \ZZ_K$, then $N(a + b \sqrt{-5} \in \ZZ_{\geq 0})$ and is equal to zero if and only if $a + b \sqrt{-5} = 0$.
Moreover, this is a unit if and only if its norm is 1,
[^why_norm_argument]
i.e. $a^2 + 5b^2 = 1$, which forces $b=0$ and $a=\pm 1$.
So $U(\ZZ[ \sqrt{-5} ] ) = \ts{\pm 1}$.


[^why_norm_argument]: 
$\impliedby$: If the norm is 1, the conjugate is the inverse. 
For the reverse direction, the argument was more complicated, and reduced to showing norms of units are $\pm 1$, and positivity forces it to be $1$.


We'll show one of the factors is irreducible, $1 + \sqrt{-5}$.
Recall that $x\in R$ a domain is **irreducible** if and only if whenever $x = ab$, one of $a,b$ is a unit.
It itself is not a unit, since $N(1 + \sqrt{-5 }) = 6 \neq 1$.
So suppose $1 + \sqrt{-5} = \alpha \beta$.
Then
\[
6 = N(\alpha \beta ) = N( \alpha) N( \beta)
,\]
and so up to reordering, we have $N \alpha = 2, N \beta= 3$.
Writing \( \alpha= a + b \sqrt{-5} \)  and taking norms yields $2 = a^2 + 5b^2$, which has no solutions: considering the equation $\mod 5$ yields $2\equiv a^2$, but $2$ is not a square in $\ZZ/5\ZZ$.
$\contradiction$

Note that the only other way of factoring $6$ is $6=(1)(6)$, and taking norms shows that one factor is a unit.
So if we assume \( \alpha, \beta \)  aren't units, both $N \alpha, N \beta > 1$, which leads to the previous situation.
By similar arguments, all 4 factors are irreducible.

To see that the LHS factors aren't unit multiples of the RHS factors, we can use the fact that the units are $\pm 1$, and multiplying the LHS by $\pm 1$ can't yield $2$ or $3$.
So this is a genuine counterexample to unique factorization.

:::

## Factorization Theory

:::{.remark}
What went wrong in the previous example?
We'll use a big of terminology from an area of algebra called *factorization theory*.
Many concepts related to divisibility can be discussed in this language!

:::

:::{.definition title="Monoid"}
A **monoid** is a nonempty set with a commutative associative binary operation $\cdot$ with an identity $1$.
We say a monoid is **cancellative** if and only if whenever \( \alpha \beta= \beta \alpha \) or \( \beta \alpha = \gamma \alpha \) then \( \beta = \gamma \).
:::

:::{.definition title="Terminology for Cancellative Monoids"}
Let $M$ be a cancellative monoid.
Then

- \( \alpha\divides \beta \) if and only if \( \beta= \alpha \gamma \) for some \( \gamma \).

- \( \epsilon \) is a **unit** if \( \epsilon\divides 1 \).

- \( \alpha , \beta \) are **associates** if \( \alpha = \epsilon \beta \) for some unit \( \epsilon \) 

- \( \pi\in M \) is **irreducible** if and only if \( \pi \) is a unit and whenever \( \pi= \alpha \beta \) then either \( \alpha \) or \( \beta \) is a unit.

- \( \pi \in M \) is **prime** whenever \( \pi\divides \alpha \beta \) then \( \pi\divides \alpha \) or \( \pi\divides \beta \).

- \( \delta \in M \) is a greatest common divisor of \( \alpha, \beta \) if and only if \( \delta \) is a common divisor that is divisible by every other common divisor.

- $M$ is a **unique factorization monoid** if and only if every nonunit element in $M$ factors uniquely (up to order and associates) as a product of irreducibles.

:::

:::{.remark}
Given $R$ an integral domain, then $R\smz$ with multiplication is a cancellative monoid.
Moreover, $R\smz$ is a unique factorization monoid if and only if $R$ is a UFD.
:::

:::{.question}
How do you show something is a UFD?
:::

:::{.answer}
Recall how this proof went for $\ZZ$:

- Use existence of a division algorithm.
- Prove Euclid's lemma: every irreducible is prime.
- Use factorization into irreducibles and proceed by induction, writing out two factorizations and cancelling things out in a combinatorial way.

So we'd like

1. To know that irreducibles are prime, and
2. Everything to factor into irreducibles.

:::

:::{.definition title="Atomic"}
For $M$ a cancellative monoid, $M$ is **atomic** if every nonunit element of $M$ is a product of irreducibles.
:::

:::{.proposition title="Monoids have unique factorization iff atomic and irreducibles are prime"}
Let $M$ be a cancellative monoid, then $M$ is a UFM if and only if $M$ is atomic and every irreducible is prime in $M$.
:::

:::{.proof title="of proposition"}
Omitted -- no new ideas when compared to proof of unique factorization in $\ZZ$.
:::

:::{.remark}
Note that in $\ZZ$, working in $\ZZ_{\geq 0}$ is useful because the only positive unit is $1$, and so any elements differing by a unit are in fact equal.
Can we emulate this for cancellative monoids?
The answer is yes, by modding out by the equivalence relation of being equivalent up to a unit.

:::

:::{.definition title="Reduced Monoid"}
Define $M_{\red}\da M/\sim$ where $a\sim b \iff a-b\in M\units$.
The operation on $M$ descends to well-defined operation on $M_{\red}$, and irreducibles and primes are the same in $M$ and $M_{\red}$.
:::

:::{.example title="of a more familiar reduced monoid"}
This is supposed to look like $\ZZ_{\geq 0}$, where $-7\in M \mapsto 7 \in M_{\red}$. 
:::

:::{.proposition title="A monoid has unique factorizations iff its reduced monoid does"}
$M$ is a UFM if and only if $M_{\red}$ is a UFM if and only if every element of $M_{\red}$ factors uniquely as a product of irreducibles, up to order.
:::

:::{.remark}
What did this buy us? We didn't have to worry about associates in the above statement, and the only unit is 1.
:::

:::{.remark}
Why isn't $\ZZ[ \sqrt{-5} ]$ is UFD?
It doesn't have enough elements to make unique factorization work!
:::

:::{.example title="of common refinements"}
In $\ZZ^+$, write $210 = 21\cdot 10 = 14 \cdot 15$.
These two factorizations differ but admit a common refinement to $(7\cdot 3)(2\cdot 5) = (7\cdot 2)(3\cdot 5)$, where it becomes clear that these factorizations are equal up to ordering.
This is **Euler's Four Number Theorem**, which turns out to be equivalent to unique factorization.
:::

:::{.theorem title="Characterization of unique factorization monoids"}
Let $M$ be a cancellative atomic reduced monoid.
Then $M$ is a UFM if and only if whenever \( \alpha, \beta, \gamma, \delta \in M \) such that \( \alpha \beta = \gamma \delta \), there are \( \rho, \sigma, \tau, \nu \) with 
\[
\alpha &= \rho \sigma \\
\beta &= \tau \nu \\
\gamma &= \rho \tau \\
\delta &= \sigma \nu
.\]

Note that plugging these in on the LHS and RHS respectively yield the same factors, just reordered.

:::

:::{.proof title="of theorem"}
Omitted, exercise in chasing definitions.
The interesting part is that you can go backward!
:::

:::{.remark}
Let $M_{\red} \da \qty{\ZZ[ \sqrt{5} ] \smz}_{\red}$, motivated by the fact that $\ZZ[ \sqrt{-5} ]$ is not a UFD if $\ZZ[ \sqrt{-5} ] \smz$ is not a UFM, or equivalently its reduction is not a UFM.
Then $M$ is a not a UFM.
Noting that $M$ is reduced under an equivalence relation, write $\gens{ \alpha}$ for the class of \( \alpha \) in $M$ for any \( \alpha\in \ZZ[ \sqrt{-5} ] \).

Our original counterexample for unique factorization now reads
\[
\gens{ 1 + \sqrt{-5} } \gens{ 1 - \sqrt{5} } = \gens{2} \gens{3}
.\]
This is still a counterexample since these pairs admit no common refinement.

Why are there "not enough elements" in $\ZZ[ \sqrt{-5} ]$?
Recall that for integral domains (as rings), two elements differ by a unit precisely when they generate the same ideal.
So we can think of elements of $M_{\red}$ as nonzero principal ideals of $M$, which we'll write as $\Prin( \ZZ [ \sqrt{-5} ])$.
To make this set of ideals into a monoid, one define \( \gens{ \alpha } \gens{ \beta }= \gens{ \alpha \beta }    \), where it's easy to check that this is well-defined.
So the failure of unique factorization is a failure of factorization in this set of ideals.
We can embed this in a larger collection of ideals by just deleting the word "principal", which will restore unique factorization.

:::

:::{.definition title="Multiplication of Ideals"}
Let $R$ be a commutative ring (always with 1).
If $I, J \normal R$ are ideals, we define 
\[
IJ \da \gens{ \ts{ \alpha_i \beta_i \st \alpha_i \in I, \beta_i \in J }} = \ts{ \sum \alpha_i \beta_i \st \alpha_i \in I, \beta_i \in J}
.\]

If $R$ is a domain, define the monoid $\Id(R)$ the collection of nonzero ideals of $R$ with the above multiplication.
:::

:::{.remark}
Note that the naive definition $IJ \da \ts{ij\st i\in I, j\in J}$ is not necessarily an ideal, since it may not be closed under addition.
Taking the smallest ideal containing all products fixes this.
:::

:::{.proposition title="If $R$ is a domain, then $\Id(R)$ is a monoid"}
Let $R$ be a commutative ring.
Then

- Multiplication $\cdot$ for ideals is commutative,
- Multiplication $\cdot$ for ideals is associative,
- The identity is \( \gens{ 1 }= R  \),
- Multiplication distributes over addition of ideals, i.e. $I(J+K) = IJ + IK$,
- $IJ \subseteq I \intersect J$,
- If \( I = \gens{ \alpha_1, \cdots, \alpha_j }  \) and \( J = \gens{ \beta_1, \cdots, \beta_k }  \) then \( IJ = \gens{ \alpha_1 \beta_1, \cdots, \alpha_j \beta_k }  \) is generated by all of the $jk$ pairwise products,
- If $R$ is a domain and $I, J$ are nonzero then $IJ$ is nonzero,

As a consequence, $\Id(R)$ is a monoid when $R$ is a domain.
:::

:::{.remark}
So instead of working in $\Prin( \ZZ [\sqrt{-5} ])$, we'll work in $\Id(\ZZ [\sqrt{-5} ])$.
The claim is that we can refine our bad factorizations.
Define

- \( I\da \gens{ 1 + \sqrt{-5} , 2 }  \) 
- \( I'\da \gens{ 1 - \sqrt{-5} , 2 }  \) 
- \( J\da \gens{ 1 + \sqrt{-5} , 3 }  \) 
- \( J'\da \gens{ 1 - \sqrt{-5} , 3 }  \) 

Then 

- \( IJ = \gens{ 1 + \sqrt{-5} }  \)  
- \( I'J' = \gens{ 1 - \sqrt{-5} }  \)  
- \( JJ' = \gens{ 3 }  \) 
- \( II' = \gens{ 2 }  \) 


We can then write
\[
\gens{ 1 + \sqrt{-5} } \gens{ 1 - \sqrt{-5} } = \gens{ 2 } \gens{ 3 } \implies (IJ)(I'J') = (II')(JJ')    
,\]
where the same terms are occurring in a different order.
For an example of how to work these out, let's compute $IJ$.
We get 
\[
IJ 
&= \gens{ (1 + \sqrt{-5} )^2, 3(1 + \sqrt{-5} ), 2(1 + \sqrt{-5} ), 6 }  \\
&= \gens{ 1 + \sqrt{-5} } \gens{ 1 + \sqrt{-5} , 3, 2, 1 - \sqrt{-5} } \\  
&= \gens{ 1 + \sqrt{-5} } \gens{ 1 }  \\
&= \gens{ 1 + \sqrt{-5} }
,\]
using the fact that $3-2=1$ is in the ideal on the second line.

\

We'll see later that this process allows you to recover unique factorization in $\ZZ_K$ for any number field $K$.
:::