A factorisation that hides its primes

The proof that every whole number factors into primes in only one way leans on a lemma, and the lemma leans on Euclid’s algorithm, which subtracts. That dependency is easy to state and hard to feel, because the whole numbers never give any reason to doubt the result. The way to feel it is to take the subtraction away and keep everything else.

So keep only the numbers that leave a remainder of one on division by four: $1, 5, 9, 13, 17, 21, 25, \ldots$ The product of two of them is another, since

$$(4a+1)(4b+1) = 4(4ab + a + b) + 1,$$

so this set is closed under multiplication, has a one, and is as good a place to factor in as any. What it lacks is closure under addition: the sum of two of its members leaves remainder two, and their difference leaves remainder zero. Nothing else about ordinary arithmetic has been touched.

Call a member irreducible if it is not $1$ and cannot be written as a product of two smaller members. Then $9$ is irreducible, because its only proper divisor is $3$, which leaves remainder three. So is $21$, whose divisors $3$ and $7$ both leave remainder three. So is $49$. And $441 = 9 \times 49 = 21 \times 21$ is a single number with two factorisations into irreducibles, neither a rearrangement of the other.

These are usually called the Hilbert numbers, after David Hilbert, who is said to have used them in lectures for exactly this purpose: to make an audience that believed unique factorisation was obvious see that it had been proved, and that the proof had used something.

Existence survives the loss of addition #

Half of the fundamental theorem goes through untouched, and it is worth seeing which half before looking at the half that breaks.

Every Hilbert number above one is a product of irreducibles. The proof is word for word the one for ordinary primes: either the number is irreducible, or it is a product of two smaller Hilbert numbers, and the same applies to each. The factors are whole numbers that shrink at every step and stay above one, so the splitting stops. It uses the ordering of the whole numbers and closure under multiplication, and nothing else. The Hilbert numbers have both.

The second half is where the whole numbers use more than they admit. The theorem as the whole numbers have it comes with two proofs of uniqueness, and each spends a resource the Hilbert numbers do not have.

Euclid’s route runs the algorithm on a prime and a number it does not divide, gets $px + ay = 1$, and multiplies through. Here that identity has nowhere to live. The smallest positive number of the form $21x + 9y$ is $3$ — take $x = 1$, $y = -2$ — and $3$ is not a Hilbert number. Inside the set, $9$ and $21$ have no common divisor except $1$, and still no combination of them reaches $1$. The algorithm that pares a rectangle down to its largest square needs to subtract, and subtraction has left.

Zermelo’s route is subtler and breaks more visibly. It takes the smallest number with two factorisations, subtracts the product of the smallest factor from each, and factors what is left. For $441$ the smallest factors are $9$ and $21$, and $441 - 9 \times 21 = 252$. That leaves remainder zero on division by four. The proof’s whole move is to hand a smaller member of the set back to the induction, and the number it produces is not a member.

The primes the set leaves out #

The failure has a cause that can be exhibited, and exhibiting it removes most of the mystery. Every Hilbert number is an ordinary whole number, and ordinary whole numbers do factor uniquely. So look at $441$ in the arithmetic that contains it.

In the whole numbers, $441 = 3 \times 3 \times 7 \times 7$, and there is nothing further to say. The Hilbert numbers cannot see $3$ or $7$, because both leave remainder three. What they can see is any product of two such primes, since $3 \times 3 = 9$ and $3 \times 7 = 21$ and $7 \times 7 = 49$ all leave remainder one. So the set sees the four primes only in pairs, and four things can be paired in three ways. Two of the three pairings give distinct products here; the third, $3$ with the second $7$ and the second $3$ with the first, is the same as the second.

That is the whole of it. The two rival factorisations are one factorisation, grouped two ways, by divisors the set does not contain. The irreducibles $9$, $21$ and $49$ look like atoms from inside, and each is secretly a pair. When two of them share a hidden prime, their products can be regrouped, and regrouping is what the set calls a second factorisation.

This is the same shape that the ring where six factors twice turned out to have, stripped of everything that made it look algebraic. There, $2 \times 3$ and $(1 + \sqrt{-5})(1 - \sqrt{-5})$ were four ideals grouped two ways. Here the missing pieces are not ideals at all but perfectly ordinary numbers that happen to have been excluded — which is why the Hilbert numbers are the cleanest place to see what goes wrong.

Two kinds of irreducible #

The hidden-prime picture predicts exactly which Hilbert numbers are irreducible, and the prediction can be checked number by number.

Take a Hilbert number and factor it in the whole numbers. Every odd prime leaves remainder one or three on division by four. A product of primes leaves remainder one exactly when an even number of its factors leave remainder three, since each such factor flips the remainder between one and three. So the prime factorisation of a Hilbert number contains some primes of the form $4k + 1$ and an even number of primes of the form $4k + 3$, counted with repetition.

Now the question is when such a number can be split into two Hilbert numbers. A prime of the form $4k + 1$ can be split off on its own, since it is itself a member. Two primes of the form $4k + 3$ can be split off together. So the only numbers that admit no split are a single prime of the form $4k + 1$, or exactly two primes of the form $4k + 3$ and nothing else. Those are the irreducibles, and there are two kinds of them.

Of the $110$ Hilbert numbers up to $441$, $41$ are irreducibles of the first kind and $32$ of the second. The second kind is not a curiosity at the margin; among small numbers it is nearly as common as the first.

And it is the second kind that causes every failure. A product of irreducibles of the first kind is a product of distinct-looking ordinary primes that the set does contain, and it factors uniquely because the whole numbers do. The trouble starts only when at least two irreducibles of the second kind appear and between them they carry at least two different hidden primes: then there is more than one way to pair them. The smallest number carrying two copies of $3$ and two of $7$ is $441$, which is why $441$ is where the grid’s first failure sits.

Irreducible is not prime here #

In the whole numbers two words mean the same thing. An irreducible cannot be split into smaller factors; a prime, in the sense Euclid’s lemma uses, divides one of the factors whenever it divides a product. The lemma is the statement that every irreducible is prime, and it is exactly the statement uniqueness needs.

The Hilbert numbers separate the two words, and they do it at a precise, checkable place.

Take $9$. It divides $21 \times 21 = 441$, with cofactor $49$, and it does not divide $21$. So $9$ is irreducible and is not prime. The same happens to every irreducible of the second kind, and the table shows why each witness works: $9 = 3 \times 3$ divides a product that contains $3$ twice, but the two copies of $3$ are in different factors. The divisor needs both of its hidden primes, and the product supplies them from two directions.

The irreducibles of the first kind never fail. A Hilbert number that is an ordinary prime $p$ and divides a product of two Hilbert numbers divides it in the whole numbers too, and there Euclid’s lemma holds, so $p$ divides one of the factors. The cofactor is automatically a Hilbert number, since a quotient of two numbers of the form $4k+1$ that is whole leaves remainder one as well.

So in this set the lemma is true for exactly the irreducibles that the whole numbers would also call prime, and false for exactly the others. That is the most precise sense in which the failure of unique factorisation is the failure of Euclid’s lemma: not a general malaise, but a list of the atoms for which one sentence is false.

Every modulus from three up #

The choice of four was arbitrary, and the failure does not depend on it.

In the numbers of the form $3k + 1$, the first failure is $100 = 4 \times 25 = 10 \times 10$, because $2$ and $5$ both leave remainder two on division by three and any two such primes multiply to a member. In the numbers of the form $6k + 1$ it is $3025 = 25 \times 121 = 55 \times 55$, built the same way from $5$ and $11$. And in the even numbers, with $1$ thrown in to make multiplication have a unit, it is $36 = 2 \times 18 = 6 \times 6$ — here the hidden prime is $2$ itself, which every member carries at least once, and the odd parts are what get regrouped.

The general statement is that the numbers congruent to one modulo $m$ factor uniquely for $m = 1$ and $m = 2$, where they are all the whole numbers or all the odd ones, and fail for every $m$ from three up. The argument is the Hilbert argument with one more ingredient. For $m \ge 3$ there is some remainder $a$, coprime to $m$ and not equal to one, whose powers return to one after $r$ steps. Dirichlet’s theorem supplies two different primes $p$ and $q$ that both leave remainder $a$. Then $p^r$, $q^r$, $p^{r-1}q$ and $pq^{r-1}$ are all members and all irreducible, since no shorter product of copies of $p$ and $q$ reaches remainder one, and

$$p^r \times q^r = p^{r-1}q \times pq^{r-1}$$

is a failure. For $m = 4$ and $a = 3$ the order is $r = 2$, and taking $p = 3$ and $q = 7$ returns $9 \times 49 = 21 \times 21$ exactly.

What the modulus decides is only how large the first failure is. Whether there is one is decided by the existence of a remainder other than one, and every modulus above two has that.

The count survives when the order does not #

Something is preserved through all of this, and it is preserved exactly.

Every factorisation of $441$ has two factors. That is not a coincidence of one example. The hidden-prime description says how many irreducibles any factorisation must use: each prime of the form $4k + 1$ is one irreducible, and each pair of primes of the form $4k + 3$ is one irreducible, so the number of factors is

$$(\text{primes } 4k+1) + \tfrac{1}{2}(\text{primes } 4k+3),$$

counted with repetition. Both quantities are read off the ordinary factorisation, which is unique. So however a Hilbert number is factored, the number of factors is always the same.

The figure checks the claim on five thousand numbers and finds it true for each. It also shows how slowly failure spreads. Only $3.5\%$ of the Hilbert numbers below twenty thousand factor more than one way, and the curve is still rising. It keeps rising: a typical large number has more and more prime factors, so it tends to carry several primes of the form $4k + 3$, and as soon as it carries two different ones among four or more it can be paired more than one way. The share tends to one, but on the scale of the figure it is creeping.

The number of factorisations is a pairing count. With $2k$ distinct primes of the form $4k + 3$ and nothing repeated, there are $1 \cdot 3 \cdot 5 \cdots (2k - 1)$ ways to pair them. For $4{,}389$, whose hidden primes are $3, 7, 11, 19$, that is three, and those are its three factorisations: $21 \times 209$, $33 \times 133$ and $57 \times 77$.

A set where every factorisation of a number has the same length is called half-factorial, and the Hilbert numbers are one. That property turns out to be the right measure of how badly unique factorisation can fail, and it is a real invariant: the next time factorisation breaks in a ring of algebraic integers, whether lengths survive is a question with a definite answer, decided by the size of the missing piece.

Putting the primes back #

The repair is to let the hidden primes in.

Enlarge the Hilbert numbers to all the odd numbers. The new members $3, 7, 11, \ldots$ are exactly the primes the set was missing, and once they are present every irreducible of the second kind stops being irreducible: $9$ becomes $3 \times 3$, $21$ becomes $3 \times 7$. The two factorisations of $441$ refine to the same four primes, and the ambiguity disappears — not because the arithmetic changed, but because the factorisations were incomplete and can now be finished.

This is Kummer’s move, run on the smallest possible example. The ring where six factors twice had irreducibles that were secretly products of ideals, and the repair was to adjoin the ideals. Here the irreducibles are secretly products of ordinary primes, and the repair is to adjoin the ordinary primes. The difference is only that in the Hilbert numbers the missing divisors are already available elsewhere, as honest integers, so nobody has to invent anything; in the rings of algebraic integers the missing divisors exist nowhere until they are defined, and defining them is what created ideal theory.

The same move also explains the shape of the failure. A set of numbers factors uniquely when its irreducibles are exactly the primes of some larger arithmetic, and fails when an irreducible corresponds to more than one prime of that arithmetic. The Hilbert numbers sit inside the odd numbers with each irreducible of the second kind covering two primes; the Gaussian integers sit over the whole numbers with some primes splitting in two — the primes of the form $4k + 1$ — and some not. Both are the same remainder-four distinction, seen from opposite sides.

What a table of failures cannot establish #

The general theorem about moduli. The monoid table finds the first failure for four moduli by search. The argument that every modulus from three up fails uses Dirichlet’s theorem on primes in a residue class, which is a deep result, and no search could replace it — a search can only confirm that failures exist for the moduli it tries.

That the share tends to one. The curve of failures reaches $3.5\%$ at twenty thousand and is plainly rising. The claim that it approaches one in the limit is a statement about the typical number of prime factors of large numbers, which grows like the logarithm of the logarithm; at a range where that is still small, no drawing can show where the curve is heading.

Why subtraction is the resource. The figures show the failure and its cause in hidden primes. They do not show that closure under addition is what the proof of uniqueness needs — that is the content of the two broken proofs above, and a picture of a monoid shows only multiplication.

Still open: irreducibles one more than a square #

Some questions about the Hilbert numbers are old questions about primes wearing different clothes, and one of them is a famous open problem.

If $n$ is even, then $n^2 + 1$ leaves remainder one on division by four, so it is a Hilbert number. Every prime factor of $n^2 + 1$ has the form $4k + 1$, because $-1$ is a square modulo a prime only when the prime leaves remainder one on division by four. So $n^2 + 1$ carries no hidden primes at all, it factors uniquely in the Hilbert numbers, and it is irreducible there exactly when it is an ordinary prime.

Whether infinitely many Hilbert numbers of the form $n^2 + 1$ are irreducible is therefore Landau’s question of whether there are infinitely many primes one more than a square, posed in 1912 and still open. The nearest result is Henryk Iwaniec’s of 1978: infinitely many numbers $n^2 + 1$ are products of at most two primes. Read in the Hilbert numbers, infinitely often $n^2 + 1$ has at most two irreducible factors. Why the step from two factors to one is so hard is the subject of the sieve’s ceiling.

Not a property of multiplication #

Unique factorisation is usually presented as a fact about how numbers multiply. The Hilbert numbers multiply exactly as the whole numbers do, contain every product they should, and still factor $441$ in two ways. So the theorem is not a fact about multiplication; it is a fact about which numbers are present to be factored into.

The whole numbers contain every prime, so no irreducible can hide one. The Hilbert numbers exclude the primes of the form $4k + 3$, and their irreducibles hide them in pairs. The next question is whether a set can have all its primes and still fail to factor uniquely for a different reason — and whether a ring can factor uniquely while missing the tool that proves it. That second possibility is real, and it is the subject of the ring that factors with no way to divide.