The Krull dimension of the semiring of natural numbers is equal to 2

Let $R$ be a ring. Its Krull dimension is the supremum of the lengths $n$ of chains $P_0\subsetneq P_1 \subsetneq\dots\subsetneq P_n$ of prime ideals of $R$. When $R$ is a field, the null ideal is the only prime ideal, and it is a maximal ideal so that its Krull dimension is zero. When $R$ is a principal ideal domain which is not a field, there are two kinds of prime ideals: the null ideal is prime (as in any domain), and the other prime ideals are the maximal ideals of $R$, generated by a prime element $p$. In particular, the Krull dimension of the ring of integers is equal to $1$.

It is classic that these concepts can be defined for semirings as well.

A semiring $R$ is a set endowed with a commutative and associative addition with a neutral element $0$, an associative multiplication with a neutral element $1$, such that addition distributes over multiplication: $(a+b)c=ac+bc$ and $c(a+b)=ca+cb$. When its multiplication is commutative, the semiring is said to be commutative.

Semirings $R$ have ideals: these are nonempty subsets $I$ which are stable under addition ($a+b\in I$ for $a,b\in I$), and stable under multiplication by any element of $R$: for general semirings, one has to distinguish between left, right, and two-sided ideals; for commutative semirings, the notions coincide.

An ideal $P$ of a semiring $R$ is said to be prime if $R\setminus P$ is a multiplicative subset; explicitely, $P\neq R$, and if $ab\in P$, then $a\in P$ or $b\in P$.

An ideal $P$ of a semiring $R$ is said to be maximal if $P\neq R$ and if there is no ideal $I$ such that $P\subsetneq I\subsetneq R$. A semiring $R$ is said to be local if it admits exactly one maximal ideal; this means that the set of non-invertible elements of $R$ is an ideal.

The amusing part comes from the classification of prime and maximal ideals of the semiring $\mathbf N$ of natural numbers, which I learned of via a Lean formalization project led by Junyan Xu.

Theorem.

1. The semiring $\mathbf N$ is local; its maximal ideal is the set $\mathbf N\setminus\{1\}$.
2. The null ideal is a prime ideal.
3. The other prime ideals are the sets $p\mathbf N$, for all prime numbers $p$.

In particular, we have chains $\langle 0\rangle \subsetneq \langle p\rangle \subsetneq \mathbf N\setminus\{1\}$ of prime ideals, hence the result stated in the title of this post:

Corollary. — The Krull dimension of the semiring of natural numbers is equal to $2$.

Proof.

1. The element $1$ is the only unit of $\mathbf N$, and $\mathbf N\setminus\{1\}$ is obviously an ideal, necessarily its unique maximal ideal.
2. The null ideal is a prime ideal, as in any semiring which is a domain.
3. Let now $P$ be a nonzero prime ideal of $\mathbf N$ and let $p$ be the smallest nonzero element of $P$. Then $p\neq 1$ (otherwise, $P=\mathbf N$, which is not prime). The hypothesis that $P$ is prime implies that one of the prime factors of $p$ belongs to $p$; by the choice of $p$, this must be $p$ itself, so that $p$ is a prime number. Then $P$ contains the set $p\mathbf N $ of multiples of $p$, which is a prime ideal of $\mathbf N$. Let us assume that $p\mathbf N\subsetneq P$ and let $n\in P\setminus p\mathbf N$. By assumption, $p$ does not divide $n$, so that these two integers are coprime. By the following proposition, $P$ contains every integer at least equal to $(p-1)(n-1)$; in particular, it contains both a power of $2$ and a power of $3$; since $P$ is prime, it contains $2$ and $3$, and it contains any integer at least $(2-1)(3-1)=2$, hence $P=\mathbf N\setminus\{1\}$. This concludes the proof.

Proposition. — Let $a$ and $b$ be nonzero coprime natural numbers. For any integer $n\geq (a-1)(b-1)$, there are natural numbers $u$ and $v$ such that $n=au+bv$.

Proof. — Since $a$ and $b$ are coprime, there are integers $u$ and $v$ such that $n=au+bv$. Replacing $u$ by $u+b$ and $v$ by $v-a$, we may assume that $0\leq u$. Replacing $u$ by $u-b$ and $v$ by $v+a$, we may assume that $u < b$. Then \[ bv = n - au \geq (a-1)(b-1)-a(b-1)= -(b-1). \] This implies $v\geq0$, so that $u$ and $v$ are natural numbers.

On the other hand, not all natural numbers $< (a-1)(b-1)$ can be written as such as sum. For example, $ab-a-b$ can't. Indeed, if $ab-a-b=au+bv$, hence $ab=a(u+1)+b(v+1)$, then $b$ divides $a(u+1)$, hence $b$ divides $u+1$, and similarly $a$ divides $v+1$. Then $ab$ is the sum of two nonzero multiples of $ab$, a contradiction. The precise distribution of the natural numbers $< (a-1)(b-1)$ which can be written as $au+bv$, for some natural numbers $u$ and $v$ is complicated, but at least one result is known : such an integer $n$ can be written in this form if and only if $ab-a-b-n$ cannot! One direction is clear, if $n$ and $ab-a-b-n$ can both be written in this form, then so can their sum, which is $ab-a-b$, a contradiction. On the other hand, let $n$ be an integer that cannot be written in this form, and write it as $n=au+bv$, for some integers $u$ and $v$, with $0\leq u< b$. By assumption, $v<0$, hence $v\leq -1$. Then \[ ab-a-b-n=ab-a-b-au-bv=a(b-1-u)+b(-v-1).\] We see that $b-1-u\geq 0$ and $-v-1\geq 0$, which shows that $ab-a-b-n$ can be written in the desired form.

Another open question of the style of the proposition had been raised by Frobenius: consider mutually coprime integers $a_1,\dots,a_r$; then any large enough integer $n$ can be written as $n=a_1u_1+\dots+a_ru_r$, for some natural numbers $u_1,\dots,u_r$, but when $r\geq 3$, there is no known formula for largest natural number that cannot be written in this form. The case $r=2$ that we discussed here was due to Sylvester (1884).