A More Intuitive Variant of a UFD

In this post, we consider a variation of a unique factorization domain (UFD) that can more closely align with our intuition for prime factorization of integers — specifically, rather than the factorization being required to be up to invertible elements, here we require the factorization to be up to multiplicative identity. This is a seemingly stronger definition, and one that doesn’t seem to encompass fields trivially or obviously (in line with our intuition for integer prime factorization.)

We clarify what we mean by this. The standard definition of a UFD is:

Definition. A UFD is an integral domain $D$ in which every nonzero element $x$ can be written as a factorization

$\displaystyle x = up_{1}\ldots p_{n}$

where the $p_{i}$ are irreducible (a different notion than prime) and $u$ is an invertible element, and where this factorization is unique up to order of the $p_{i}$ .

As a prototypical example, take the ring of integers $\mathbb{Z}$ . Prime factorization is a well-known property of this domain. But we don’t typically think of a field like $\mathbb{Q}$ or $\mathbb{R}$ as satisfying an analogous prime factorization, at least when we first learn about them before abstract algebra — intuitively, we can “keep dividing in further.” But by our definition above, fields are actually UFDs — since all elements are invertible, we can just trivially say that $x = u$ with $n = 0$ and $u = x$ is the unique factorization of $x$ . This definition does make certain things cleaner from an abstract algebra perspective; for example, it allows us to have a “class inclusion chain” in which fields are UFDs, which are then integral domains. However, it then doesn’t necessarily always align with our intuition for what unique factorization really “means.” Thus, we consider a different but analogously defined concept here:

Definition. A strong UFD is an integral domain $D$ in which every nonzero element $x$ can be written as a factorization

$\displaystyle x = ( \pm 1)p_{1}\ldots p_{n}$

where the $p_{i}$ are irreducible, and where this factorization is unique up to order of the $p_{i}$ .

(Note on terminology: I originally considered the term “pseudo-UFD,” but this suggests a weaker definition while ours is stronger. From a cursory Google search, it doesn’t seem like there are other uses of the term “strong UFD” yet.)

Actually, this definition doesn’t encompass the prototype of $\mathbb{Z}$ , since we can always write $p = (1)(p) = ( - 1)( - p)$ for $p$ irreducible, yielding non-uniqueness. (If $p$ is irreducible, then $- p$ is too.) It does encompass $\mathbb{Z}_{+}$ , but that’s not even a ring. What algebraic structure would $\mathbb{Z}_{+}$ be? Well, if we add 0 (which doesn’t change anything because our definition specifies “nonzero”) and look at $\mathbb{Z}_{0}$ , then this is a commutative semiring — in fact, it is a commutative cancellative semiring. But in that case, the sign is irrelevant.

Or alternatively, we can remedy this definition in a way to rescue its application to $\mathbb{Z}$ . So we can talk about multiple possible definitions here. We can name these concepts by “type I,” “type II,” etc.

For the first definition, let’s work backwards (in a “reverse mathematics” style) to see how generally we can write this definition. Let’s use the prototype of $\mathbb{Z}_{+}$ or $\mathbb{Z}_{0}$ . Actually, for these prototypes, sign can be removed from the definition, and actually then we wouldn’t even need to require addition! (We can then use $\mathbb{Z}_{+}$ as our prototype to avoid dealing with 0.) So let’s do this for a group-like structure. We assume multiplication, and then we need associativity … but do we need anything else? Commutativity, for uniqueness up to order. Do we need multiplicative identity? It doesn’t look like we do, just to write down the definition. Also, terminology note: this wouldn’t be a domain, so instead of UFD we can call it a unique factorization algebra, or UFA. So we define:

Definition. A type I unique factorization algebra (UFA) is a commutative semigroup $S$ in which every element $x$ can be written as a factorization

$\displaystyle x = p_{1}\ldots p_{n}$

where the $p_{i}$ are irreducible, and where this factorization is unique up to order of the $p_{i}$ .

We now need to figure out what “irreducible” would mean. To avoid conflict with “irreducible” in standard commutative algebra, we call our concept “type I irreducible,” also to align it with our definition of “type I UFA.” (In general, we’ll name concepts based on alignment of definitions.) We’ll define this by formalizing the intuitive idea of “can’t be divided into further,” which matches our intuition closely for defining prime numbers in $\mathbb{Z}_{+}$ when first learning about them before abstract algebra:

Definition. An element $x \in S$ is type I irreducible if we cannot write $x = ab$ for some $a,b \in S$ .

Actually, this doesn’t work for the prototype of $\mathbb{Z}_{+}$ because of the multiplicative identity. So instead, we’ll amend our definitions to require multiplicative identity and exclude it from irreducibility:

Definition. Let $M$ be a commutative monoid. An element $x \in M$ is type I irreducible if we cannot write $x = ab$ for $a,b \neq 1$ . We say $M$ is a type I UFA if every element $x\neq 1$ can be written as a factorization

$\displaystyle x = p_{1}\ldots p_{n}$

where each $p_{i}$ is not equal to 1, is type I irreducible, and where the factorization is unique up to the order of the $p_{i}$ .

By this definition, $\mathbb{Z}_{+}$ is a type I UFA. This matches our intuition closely for defining prime numbers in $\mathbb{Z}_{+}$ when first learning about them before abstract algebra. Since factorizations express elements as products, irreducibility in this context intuitively makes sense to be defined in terms of whether it can be expressed further as a product (in a nontrivial way.)

Another approach to defining UFAs comes from modifying our previous construction to encompass $\mathbb{Z}$ . (Thus, for this, $\mathbb{Z}$ is our prototype.) We could this by introducing an order and then requiring the $p_{i}$ to be positive, but that seems like a lot of extra structure that we should be able to avoid requiring. Instead, we can amend our definition by defining the uniqueness “modulo sign,” to exclude $(1)(x) = ( - 1)( - x)$ .

Let’s try the reverse math approach here too. To do this, we need to know about sign, so we should have addition (in conjunction of course with the already-present multiplication.) For sign, we need additive inverses and additive identity, and we also need associativity, commutativity, and identity of multiplication. We also need compatibility between addition and multiplication, and for the uniqueness modulo sign we should have $( - 1)( - x) = (1)(x)$ , which comes from distributivity. Actually, I’m not sure if things like $( - 1)( - x) = (1)(x)$ require commutativity and/or associativity of addition, but those seem like reasonable requirements in general so we can include them. Together, this yields a commutative ring. Thus, we can define (keeping track of sign in the irreducibility definition too, and keeping track now of avoiding 0):

Definition. Let $R$ be a commutative ring. A nonzero element $x \in R$ is type II irreducible if we cannot write $x = ab$ for $\left\{ a,b \right\} \neq \left\{ 1,x \right\}$ and $\left\{ a,b \right\} \neq \left\{ - 1, - x \right\}$ . We say $R$ is a type II UFA if every nonzero element $x$ can be written as a factorization

$\displaystyle x = ( \pm 1)p_{1}\ldots p_{n}$

where each $p_{i}$ is not equal to 1 or -1, is type II irreducible, and where the factorization is unique up to order of the $p_{i}$ and sign, in the following sense: two factorizations

$\displaystyle x = ( \pm 1)p_{1}\ldots p_{n} = ( \pm 1)q_{1}\ldots q_{m}$

are considered equivalent if $n = m$ , there exists a bijection $b:\left\{ 1,\ldots,n \right\} \rightarrow \left\{ 1,\ldots,n \right\}$ such that $q_{i} = \pm p_{b(i)}$ , and the number of sign changes in going from $p_{i}$ to $q_{i}$ (and including the sign of $\pm 1$ ) is even.

There’s a lot to unpack here with these concepts; let’s go about it methodically.

—

First, is it necessary to state that the number of sign changes must be even for a type II UFA? Since if we have a number of sign changes that are odd then that would imply $x = - x$ , but $x$ is nonzero. Oh, but that is possible in a ring of characteristic 2. In fact, for a ring of characteristic 2 that is true for all $x$ .

So we have two cases: $R$ has characteristic 2 or not 2. If it has characteristic 2, then it doesn’t matter what we say about sign; if I have a factorization and then put as many signs as I want in front of the factors, it doesn’t change the value. In fact, each factor doesn’t change upon placing a sign in front of it, so once I’ve found a factorization in a ring of characteristic 2, uniqueness modulo sign is trivially satisfied. So in characteristic 2, we can equivalently remove the whole “modulo sign condition.” But if $R$ doesn’t have characteristic 2, then the sign changes being even (given $x \neq 0$ ) is a consequence of $q_{i} = \pm p_{b(i)}$ , so we wouldn’t need to state it as an extra condition. Thus, in general, we can equivalently remove the condition that the number of sign changes must be even.

(We are implicitly excluding the zero ring here, or equivalently a ring of characteristic 1.)

—

Next, I suspect that the uniqueness of factorization (for type II) allows us to conclude cancellativity, and therefore show that $R$ must in fact be an integral domain. Can we do this? (Actually, can we do this to show cancellativity in type I UFAs too?)

Let’s try this out.

Lemma. A type I UFA must be cancellative — in other words, $ab = ac \rightarrow b = c$ .

Proof. Let $x = ab = ac$ . We know that we have factorizations for $a,b,c$ :

$\displaystyle a = p_{1}\ldots p_{n},$

$\displaystyle b = q_{1}\ldots q_{m},$

$\displaystyle c = r_{1}\ldots r_{l},$

where the $p_{i},q_{i},r_{i}$ are irreducible and not equal to 1. Thus,

$\displaystyle p_{1}\ldots p_{n}q_{1}\ldots q_{m} = p_{1}\ldots p_{n}r_{1}\ldots r_{l}.$

These are two different factorizations into non-identity irreducibles, hence by uniqueness they must be the same up to order. So this implies that $n + m = n + l \rightarrow m = l$ , and the factors in the RHS are a permutation of those in the LHS. Say that the permutation fixes the $p_{i}$ ; then, the permutation must only permute the $q_{i}$ into the $r_{i}$ , but by commutativity this yields $b = c$ , as desired. Otherwise, say that the permutation doesn’t fix the $p_{i}$ , so calling the permutation $b$ , for some $i \in \lbrack 1,n\rbrack$ we have $p_{i} = r_{b(i)}$ . In fact, let’s single out all the indices for which the $p_{i}$ get mapped to non- $p_{i}$ : this permutation must have a set of indices $i_{1},\ldots,i_{s},j_{1},\ldots,j_{t}$ for which

$\displaystyle p_{i_{i}} = r_{b\left( i_{i} \right)},$

$\displaystyle q_{j_{i}} = p_{b\left( j_{i} \right)}.$

Basically, everything that $b$ “ignored” when mapping the $p_{i}$ (we assume $b$ goes from LHS to RHS), $q_{i}$ must map to.

So $b$ does a couple things: it maps some of $p$ to some of $p$ , it maps rest of $p$ to some of $r$ , it maps some of $q$ to rest of $p$ , and it maps rest of $q$ to rest of $r$ . The elements $b$ and $c$ are made up of all the $q$ and $r$ respectively, and we’re trying to show they’re equal.

So what is the product of all the $q$ ? Well, some of $q$ goes to some of $p$ , and the rest goes to some of $r$ , so this is equal to some of $p$ and some of $r$ . But where does that “some of $p$ ” go? If we ignore the factors in both factorizations where $b$ sends $p$ to $p$ , then from the rest of the factors, the “some of $p$ ” can’t map back to $p$ , thus it must map to $r$ . But since this is a bijection, all of $r$ must be accounted for, thus the product of all the $q$ is the product of all the $r$ . This shows $b = c$ , as desired. $\blacksquare$

(Another proof that could be easier to input to a formal proof system could be to use induction: first, if $ab = ac$ , where $a,b,c$ are irreducible, then we can yield $b = c$ pretty easily: by uniqueness of factorization, we’d need to have $(a,b),(a,c)$ be equal up to re-ordering, so either $a = a$ and $b = c$ , as desired, or $a = c$ and $b = a$ , so $b = c$ , as desired. Then, we use induction on $n$ to show that if

$\displaystyle ap_{1}\ldots p_{n} = aq_{1}\ldots q_{n}$

with the $a,p_{i},q_{i}$ all irreducible, then we can cancel $a$ . Once we show that, then the lemma immediately follows from considering $p_{1}\ldots p_{n}q_{1}\ldots q_{m} = p_{1}\ldots p_{n}r_{1}\ldots r_{l}$ , knowing that uniqueness of factorization implies $n + m = n + l \rightarrow m = l$ , and then cancelling each $p_{i}$ until $q_{1}\ldots q_{m} = r_{1}\ldots r_{l} \rightarrow b = c$ remains.)

We could probably have a similar cancellativity implication for type II UFAs too:

Conjecture. A type II UFA must be cancellative — in other words, for a *nonzero* $a$ , $ab = ac \rightarrow b = c$ .

Attempt. Actually, the whole sign part of the definition of uniqueness may make this more complicated, even though we highly suspect it to be true. So a better way of writing out the proof could be to see if we can take the “nonzero subset” of the type II UFA $R$ and see if this is a type I UFA, in the same way that we can take the subset $\mathbb{Z}_{+}$ from $\mathbb{Z}$ , and then apply our lemma on type I UFAs.

We should be careful though, since “nonzero” isn’t enough — we want the “positive” elements. Only we don’t have order, so instead what we’re thinking is to pick one of $x$ or $- x$ for each $x$ .

Let’s do this as follows. Let $R$ be a type II UFA. We can form

$\displaystyle \left\{ \left\{ x, - x \right\}:x \in R,x \neq 0 \right\}.$

(We’ll have multiple $x$ for which the set $\left\{ x, - x \right\}$ coincide, but that’s totally fine in this construction.) Then, we can form a subset of $R$ , which we call $R_{+}$ , by picking an element from each set in this set of sets. (This picking would probably require the Axiom of Choice; absent an order, I’m not sure how to define this picking function from the other ZF axioms.) Thus, we define $R_{+}$ such that

$\displaystyle x \in R_{+} \rightarrow x \in R,$

$\displaystyle x \in R_{+} \rightarrow - x \notin R_{+}\ (unless\ x = - x.)$

So actually, let’s separate characteristic 2 versus not 2. If the characteristic is 2, then $\left\{ \left\{ x, - x \right\}:x \in R,x \neq 0 \right\}$ is literally just the set of nonzero elements of $R$ (in “natural” bijection with that.) Then, the whole sign condition disappears, and it follows that $R_{+}$ is a type I UFA. So we cite cancellativity of $R_{+}$ : if $a,b,c \in R_{+}$ , then $ab = ac \rightarrow b = c$ . Now, this shows our desired type II cancellativity in the case that $b,c \neq 0$ . If $b = 0$ , then $ac = 0$ , and $a \neq 0$ . Is it still possible for $c \neq 0$ ? This connects to the “no divisors of zero” equivalently stated condition for integral domains. We know for example that there exist nonzero matrices whose product is zero. The problem is, cancellativity on $R_{+}$ on its own can’t really say much about $c = 0$ , since $R_{+}$ excludes 0. Furthermore, the whole type II UFA condition explicitly excludes 0 from the condition.

It remains to figure this out. $\blacksquare$

Briefly, though, let’s continue the train of thought, interesting in its own right, on $R_{+}$ being a type I UFA. Would this be true for $R$ of characteristic not 2?

Well, we would still have that $R_{+}$ consists of nonzero elements of $R$ , thus unique factorization applies to all elements of $R_{+}$ . This means that if $x \in R_{+}$ , then we can write

$\displaystyle x = ( \pm 1)p_{1}\ldots p_{n}$

where the $p_{i} \in R$ are type II irreducible. If $y \in R$ is type II irreducible, then it can’t be written in the form $y = ab$ for $\left\{ a,b \right\} \neq \left\{ 1,y \right\}$ and $\left\{ a,b \right\} \neq \left\{ - 1, - y \right\}$ . In particular, that implies that we can’t have $y = ab$ with $a,b \neq 1$ , so $y$ is type I irreducible. Thus, type II irreducibility implies type I irreducibility for elements in $R$ .

Thus, for arbitrary $x \in R_{+}$ , we can write

$\displaystyle x = ( \pm 1)p_{1}\ldots p_{n}$

where the $p_{i}$ are type I irreducible. Furthermore, since the characteristic is not 2, $R_{+}$ must contain exactly one of $p_{i}$ or $- p_{i}$ for each $i$ . Actually, though, it’s possible that the “wrong sign” for $x$ was chosen when $x$ was picked over $- x$ to be in $R_{+}$ , so that the requisite signed $p_{i}$ may not have been chosen for $R_{+}$ . So it seems we might need to be more methodical about constructing $R_{+}$ to conclude type I unique factorization within $R_{+}$ .

—

The idea of “unique factorization” is very much in the league of the general concept of a free object. In particular, the type I UFA definition seems especially simple. Can we show something like the following?

Lemma. A commutative monoid $M$ is a type I UFA if and only if it is free.

Proof. What is a free commutative monoid? Well, it is basically the set of all words in a set of variables $V$ , subject to equalities that are guaranteed by the axioms of commutative monoids. But in commutative monoids we must have that words that are the same with different orderings of characters must actually be equal, and similarly words involving the identity are equal to words with the identity characters removed. Conversely, these (assuming that words automatically incorporate associativity) are the only conditions on equality of words. But this is exactly the definition of a type I UFA. $\blacksquare$

Conjecture. A commutative ring $R$ is a type II UFA if and only if it is free.

Disproof. Similarly to the type I case, what we want to see is whether the uniqueness condition is exactly the condition of equality that would be guaranteed by the axioms of a commutative ring. Clearly, the axioms show that the factorizations in the uniqueness condition are equivalent (re-ordering of multiplicative factors, even number of sign changes.) Given no other relations imposed on the set of variables, are those the only possible factorizations that could be equivalent? No, they aren’t, since we can have words involving addition: for example, with variables $\left\{ a,b,c \right\}$ , a free commutative ring would include $ab + c$ . So these are different. $\blacksquare$

Thus, we won’t use the terminology of “type I UFA” anymore; instead, “UFA” will mean “type II UFA.” For example, what we have above is just that if $R$ is a UFA of characteristic 2, then $R_{+}$ is a free commutative monoid. Do we still want a term to replace “type I irreducible” or “type II irreducible?” Let’s skip that question for now.

—

It seems very intuitive to me that type II irreducibility implies (standard) irreducibility (since it bans a whole swath of decompositions that would presumably include those banned by irreducibility.) Let’s try to show this, and in general investigate the relationship between the three concepts of irreducibility. We recall the definition of an irreducible element from standard commutative algebra: $x$ is irreducible if it is nonzero, not invertible, and not the product of two non-invertible elements. Clearly, type I irreducibility doesn’t make sense for commutative rings (which is why we have the type II concept), but we can define type II irreducibility in commutative rings. Then, can we show that a (nonzero) type II irreducible element must be irreducible?

We can try to show the converse. Say that a nonzero element $x$ is reducible. Then, it is either invertible or it can be written as $x = ab$ where $a,b$ are non-invertible.

Say that $x = ab$ where $a,b$ are non-invertible. Since 1 and -1 are invertible, we must have $\left\{ a,b \right\} \neq \left\{ 1,x \right\}$ and $\left\{ a,b \right\} \neq \left\{ - 1, - x \right\}$ . But then $x$ is type II reducible. So in this case, we have the desired.

Otherwise, $x$ is invertible. (Here, I don’t have as much intuition for whether $x$ would be type II reducible. But let’s give it a shot.) Hence, $x$ is cancellable: for any $b,c$ , $xb = xc \rightarrow b = c$ . We split into cases depending on multiplicative order of $x$ (call it $n$ .)

If $n > 2$ (or $n$ doesn’t exist), then write $x = \left( x^{- 1} \right)\left( x^{2} \right)$ . If $\left\{ x^{- 1},x^{2} \right\} = \left\{ 1,x \right\}$ , then there are two cases: $x^{- 1} = 1 \rightarrow x = 1$ , contradicting $n > 2$ , or $x^{2} = 1$ , which is impossible. Thus, this set equality can’t hold. Otherwise, if $\left\{ x^{- 1},x^{2} \right\} = \left\{ - 1, - x \right\}$ , then there are two cases: $x^{- 1} = - 1 \rightarrow x = - 1$ , contradicting $n > 2$ , or $x^{2} = - 1$ . If $x^{2} = - 1$ , then $x^{4} = 1$ . Furthermore, $x^{1} = x \neq 1$ (since $n > 2$ ), $x^{2} = - 1 \neq 1$ (since $n > 2$ ), and $x^{3} = - x \neq 1$ (since $x \neq - 1$ since $n > 2$ .) Thus, $n = 4$ , and $- 1 = 1$ implies that the ring has characteristic not 2. So if $x$ has order greater than 2, but if the order is not 4 or the characteristic is 2, then we’ve shown $x$ to be type II reducible.

If $x$ has order 4 and the characteristic is not 2, then write $x = \left( x^{- 2} \right)\left( x^{3} \right)$ . If $\left\{ x^{- 2},x^{3} \right\} = \left\{ 1,x \right\}$ , then there are two cases: $x^{- 2} = 1 \rightarrow x^{2} = 1$ , impossible, or $x^{3} = 1$ , also impossible. Thus, this set equality can’t hold. Otherwise, if $\left\{ x^{- 2},x^{3} \right\} = \left\{ - 1, - x \right\}$ , then there are two cases: $x^{- 2} = - 1 \rightarrow x^{2} = - 1 \neq 1$ , or $x^{3} = - 1$ . The second case yields $x^{6} = 1$ , which contradicts $n = 4$ since 4 doesn’t divide 6. But we can still have $x^{2} = - 1$ — this works at least in a ring like $\mathbb{C}$ . So this doesn’t show type II reducibility.

If $n = 2$ , then $x^{2} = 1$ but $x \neq 1$ ; in that case, $x^{3} = x \neq 1$ . If we try a decomposition of the form $x = \left( x^{r} \right)\left( x^{s} \right)$ , we need $r + s = 1$ mod 2, and that always yields 1 and $x$ . So this doesn’t show type II reducibility.

If $n = 1$ , then $x = 1$ ; is 1 type II reducible? If there exists some invertible $x \notin \left\{ 1, - 1 \right\}$ , then we could write $1 = xx^{- 1}$ , showing that 1 is type II reducible. In particular, this can’t happen say for $\mathbb{Z}_{2}$ , since there exist no elements beside $1, - 1$ . It also can’t happen say for the ring $\mathbb{Z}$ , so we probably can’t show something like “any ring greater than X cardinality must have 1 as type II reducible.”

Thus, to summarize, we can say the following:

Theorem. If $x$ is type II irreducible in a commutative ring $R$ , then either:

$x$ is irreducible; or
$x = 1$ and the only invertible elements are $1$ and $-1$ ; or
$x$ has order 2; or
$x^{2} = - 1$ and the characteristic of $R$ is not 2.

Theorem. If $x$ is type II irreducible and not invertible in a commutative ring $R$ , then $x$ is irreducible.

—

Can we mimic the relationship between $\mathbb{Z}_{+}$ and $\mathbb{Z}$ to show a similar relationship between free commutative monoids and UFAs? Maybe by taking a commutative monoid and “adding the negatives of elements” in a “closure-style” operation? Or can we form a subset of a UFA (maybe a more deliberate construction of $R_{+}$ above) that must be a free commutative monoid, in the same way that $\mathbb{Z}_{+}$ is a subset of $\mathbb{Z}$ ?

Let’s start with a UFA $R$ . In a similar way that $\mathbb{Z}_{+}$ is a subset of $\mathbb{Z}$ , we want to construct a subset $M \subseteq R$ that must be a free commutative monoid.

It remains to try this.

Conversely, let’s start with a free commutative monoid $M$ , and let’s see if we can “add the negatives of elements” to $M$ , forming a ring $R$ that would then be a UFA.

It remains to try this as well.

—

We continue this discussion in a follow-up post.

Share and like (need WordPress account to like):