Abstract Vergleichsstellensätze
for preordered semifields and semirings II

This paper is part of an emerging research program on real algebra with commutative preordered semirings and semifields. Here, semirings and semifields are like rings and fields, but without the assumption of additive inverses. In Part I [3], detailed motivation for this project was given. It comes in the form of two main points:

• $\triangleright$

  Our Vergleichsstellensätze have entirely new applications which are not covered by the classical Positivstellensätze. For example, take any class of mathematical structures—such as representations of a Lie group—for which notions of direct sum and tensor product exist, and the tensor products distribute over direct sums. Then the isomorphism classes form a semiring. In many cases, this semiring carries a canonical preorder with respect to one structure being included (up to isomorphism) in another. One then obtains a preordered semiring, and results such as our Vergleichsstellensätze are useful tools in understanding its structure.

  The results of the present paper have found their first applications in probability and information theory. This comprises new formulas for the asymptotics of random walks on topological abelian groups [4] as well on the asymptotics of matrix majorization [2].

• $\triangleright$

  From the perspective of real algebra itself, semifields have a number of advantages over fields that make them of intrinsic interest. One such advantage is that if $\mathbb{R}_{+}(X)$ is the semifield of rational functions with nonnegative coefficients, then the evaluation maps are well-defined homomorphisms $\mathbb{R}_{+}(X)\to\mathbb{R}_{+}$, in stark contrast to the lack of evaluation homomorphisms on fields of rational functions. Another advantage is that semifields can combine the convenience of multiplicative inverses with the presence of nilpotency. For example, there is a semifield $F\coloneqq\mathbb{R}_{(+)}[X]/(X^{2})$ whose nonzero elements are the linear polynomials $r+sX$ with $r>0$. Since its enveloping ring is the ring of dual numbers, $F\otimes\mathbb{Z}\cong\mathbb{R}[X]/(X^{2})$, it is clear that $F$ cannot be embedded into a field.

As in real algebra generally, to understand the structure of a particular preordered semiring, it is useful to probe this structure through homomorphisms to test objects such as the real numbers. These homomorphisms can be thought of in geometrical terms as points of a spectrum. By analogy with Positivstellensätze, Part I has introduced the term Vergleichsstellensatz for a type of result which relates the given algebraic preorder to a spectral preorder. It provides sufficient conditions for the existence of an algebraic certificate witnessing a spectral preorder relation.

More concretely, in Part I we first proved a separation theorem for preordered semifields, which states that every semifield preorder is the intersection of its total semifield preorder extensions. From this, we derived a Vergleichsstellensatz for a certain class of preordered semirings $S$ in which $1>0$. In this result, the role of the spectrum is played by the monotone homomorphisms $\phi:S\to\mathbb{R}_{+}$ and $\phi:S\to\mathbb{TR}_{+}$, where $\mathbb{TR}_{+}\coloneqq([0,\infty),\max,\cdot)$ is the semifield of tropical reals. Roughly speaking, for nonzero $x,y\in S$ our Vergleichsstellensatz considers two kinds of algebraic certificates:

• $\triangleright$

  A catalytic certificate, stating that there is nonzero $a\in S$ with

  $$ax\leq ay.$$

  (1.1)

• $\triangleright$

  An asymptotic certificate, which states that

  $$x^{n}\leq y^{n}\qquad\forall n\gg 1.$$

  (1.2)

These are certificates for the spectral preorder relation in the sense that if either of them holds, then $\phi(x)\leq\phi(y)$ for all $\phi$ is easily implied. Our Vergleichsstellensatz now provides an almost converse: if we have strict inequality $\phi(x)<\phi(y)$ for all such $\phi$, then both algebraic certificates hold. The fully formal statement with precise assumptions will be recalled as Theorem 2.4.

The goal of the present paper is to dig deeper and develop abstract Vergleichsstellensätze that apply even if $1\not\geq 0$. This may seem like an artificial problem on first look, because why would one want to do this? However, there actually are many applications, for example to probability and information theory, where preordered semirings with $1\not\geq 0$ appear. To see why, it is enough to note that probability measures are by definition normalized to $1$, which indicates that one only wants measures of the same normalization to be comparable at all. In particular, the zero measure will not be comparable to any normalized measure, resulting in $1\not\geq 0$ and $1\not\leq 0$. Two such applications of the results of this paper have been worked out in companion papers [4, 2], and we now give a brief sketch of what the relevant preordered semiring is¹¹1We do so in a watered-down version where only finitely supported measures are considered; the preordered semiring actually considered in [4] has arbitrary measures (of compact support) on a topological abelian group as elements. and why one has $1\not\geq 0$. The elements of the polynomial semiring $\mathbb{R}_{+}[X_{1},\ldots,X_{d}]$ can be identified with finitely supported measures on $\mathbb{N}^{d}$, where addition of polynomials corresponds to addition of measures and multiplication of polynomials corresponds to convolution of measures. The semiring preorder generated by

then matches exactly the so-called first-order stochastic dominance at the level of measures. In algebraic terms, for $p,q\in\mathbb{R}_{+}[X_{1},\ldots,X_{d}]$ we have $p\leq q$ if and only if one can increase the exponents in some of the terms of $p$ so as to obtain $q$. Then in order for $p,q\in\mathbb{R}_{+}[X_{1},\ldots,X_{d}]$ to be comparable at all, it is necessary for the sum of the coefficients to be the same, i.e. we must have $p(1,\ldots,1)=q(1,\ldots,1)$. In particular, we indeed have $1\not\geq 0$ and $1\not\leq 0$ in this preordered semiring.

Nevertheless, it is of interest to know when a catalytic preordering certificate (1.1) and/or an asymptotic preordering certificate (1.2) exist. Since $\mathbb{R}_{+}[X_{1},\ldots,X_{d}]$ is isomorphic to the semiring of finitely supported measures on $\mathbb{N}^{d}$ with convolution as multiplication, these are equivalently questions about random walks on $\mathbb{N}^{d}$. In particular, the asymptotic preordering detects when one random walk will dominate another one at late times, in the sense of its distribution being further “upwards” componentwise in $\mathbb{N}^{d}$. Our Vergleichsstellensätze are exactly the right tool to detect when this dominance occurs by relating it to the spectral preorder, which can be calculated very concretely. Of course, among the relevant spectral preorder relations are the point evaluations like

But something special happens at the point $(1,\ldots,1)$: due to $p(1,\ldots,1)=q(1,\ldots,1)$, which is the normalization of probability, it turns out that infinitesimal information around the evaluation homomorphism $f\mapsto f(1,\ldots,1)$ must be taken into account. This comes in the form of the inequalities

In terms of our formalism, these arise because the map

is a monotone derivation with respect to the evaluation homomorphism at $(1,\ldots,1)$. For more detail, we refer to Examples 7.3 and 8.7 and the companion paper [4], where this is done more generally for random walks with compactly supported steps on topological abelian groups in general.

As this example may already indicate, the technical challenges that arise in dealing with preordered semirings with $1\not\geq 0$ are substantially greater than in the earlier case with $1\geq 0$ that was considered in Part I. A cleaner example illustrating some of the difficulty is the semifield $F\coloneqq\mathbb{R}_{(+)}[X]/(X^{2})$ mentioned above, when equipped with the semiring preorder defined as

Note that this is exactly the semiring preorder generated by $X\geq 1$. Now the only homomorphism $F\to\mathbb{R}_{+}$ is the projection $r+sX\mapsto r$, and the only homomorphism $F\to\mathbb{TR}_{+}$ to the tropical reals $\mathbb{TR}_{+}$ is the degenerate one mapping every nonzero element to $1$. Therefore if we were to use the same definition of the spectral preordering as in Part I, where this involved only monotone homomorphisms with values in $\mathbb{R}_{+}$ and $\mathbb{TR}_{+}$, then this spectral preordering would degenerate completely and could not display any interesting relation to the algebraic preordering on $F$.

As indicated already by (1.3), our solution to this problem is to enlarge the spectrum by infinitesimal information in the form of monotone derivations. In fact, we will consider the preordered semifield $\mathbb{R}_{(+)}[X]/(X^{2})$ semifield itself as another test object, so that the structure of other preordered semirings can also be probed through monotone homomorphisms with values in $\mathbb{R}_{(+)}[X]/(X^{2})$. The two components of such a homomorphism form a pair $(\phi,D)$, where $\phi:S\to\mathbb{R}_{+}$ is a homomorphism that is degenerate in the sense that

and a monotone $\phi$-derivation $D:S\to\mathbb{R}$, which is an additive monotone map satisfying the Leibniz rule with respect to $\phi$,

Furthermore, we will also have to consider the opposite semifields $\mathbb{R}_{+}^{\mathrm{op}}$ and $\mathbb{TR}_{+}^{\mathrm{op}}$ as test objects. This is not so surprising in light of the fact that reversing the preorder on a preordered semiring $S$ results in another preordered semiring $S^{\mathrm{op}}$.

In full technical detail, and using notions that will be introduced in the main text, our Vergleichsstellensatz for catalytic certificates is then the following.

Conversely, if $ax\leq ay$ holds for some nonzero $a$, then the same spectral conditions (1.4, 1.5) are trivially implied with non-strict inequalities $\leq$ in place of $<$. The first two itemized assumptions on $S$ can be thought of as saying that although we do not require $1\geq 0$ to be the case, this should nevertheless not fail too badly, in the sense that the preorder relation $\leq$ must still be suitably large. In the final part of the theorem statement, the term semialgebra refers to the case in which $S$ comes equipped with a scalar multiplication by $\mathbb{R}_{+}$.

We do not currently have a Vergleichsstellensatz for asymptotic certificates that would apply at the same level of generality, but we do have one that applies under somewhat stronger assumptions on $S$ (which still fall short of assuming $1\geq 0$). This takes the following form, which in its conclusions precisely matches our main result of Part I.

We again refer to [4] for the application to random walks, which gives much stronger results than what has been achieved with purely probabilistic methods so far, and to [2] for another application to information theory.

Here, we recall the basic definitions around semirings together with the main new definitions and results developed in Part I [3] as far as they are relevant to this paper. In the following, all unreferenced definitions and results are standard. Those of Part I are referenced with their theorem number prefixed by “I”.

A commutative semiring is a set $S$ together with two commutative monoid structures $(S,+,0)$ and $(S,\cdot,1)$ such that the multiplication $\cdot$ distributes over the addition $+$ and $1\cdot 0=0$. Since we will not consider the noncommutative case at all, we simply use the term semiring as short for “commutative semiring”. The set of multiplicatively invertible elements in a semiring $S$ is denoted $S^{\times}$. There is a unique semiring homomorphism $\mathbb{N}\to S$, given by $n\mapsto n1$, and we often abuse notation by writing $n$ instead of $n1$. A semiring $S$ is zerosumfree if $x+y=0$ in $S$ implies $x=y=0$. It has quasi-complements if for every $x\in S$ there are $y\in S$ and $n\in\mathbb{N}$ such that $x+y=n$ (I.2.19).

A semifield $F$ is a semiring such that $F^{\times}=F\setminus\{0\}$. A semifield is strict if $1$ has no additive inverse, or equivalently if $F^{\times}$ is closed under addition, or yet equivalently if $F$ is zerosumfree. Every semifield that is not a field is strict. A semidomain is a semiring without zero divisors and such that $1\neq 0$. A semidomain $S$ has a semifield of fractions $\operatorname{\mathsf{Frac}}(S)$ together with a homomorphism $S\to\operatorname{\mathsf{Frac}}(S)$ that is the initial semiring homomorphism from $S$ into a semifield. $\operatorname{\mathsf{Frac}}(S)$ is a strict semifield if and only if $S$ is zerosumfree.

A preorder is a binary relation that is reflexive and transitive. We typically denote a preorder by $\leq$, where the symbols $\geq$, $<$ and $>$ have their standard induced meaning. We write $\preceq$ when another preorder symbol is needed. We also use the following two derived relations:

• $\triangleright$

  $\approx$ is the smallest equivalence relation contained in $\leq$. In other words, $x\approx y$ is shorthand for $(x\leq y)\>\land\>(y\leq x)$.

• $\triangleright$

  $\sim$ is the equivalence relation generated by $\leq$.

A preorder is total if $x\leq y$ or $y\leq x$ for all $x$ and $y$. A map $f$ between preordered sets is monotone if $x\leq y$ implies $f(x)\leq f(y)$. A monotone map $f$ is an order embedding if the converse holds as well. If $X$ is a preordered set, then $X^{\mathrm{op}}$ denotes the preordered set with the opposite preorder in which $x\leq y$ holds if and only if $y\leq x$ in $X$.

A preordered semiring is a semiring together with a preorder relation such that for every $a\in S$, both addition by $a$ and multiplication by $a$ are monotone maps $S\to S$ (I.3.7). Note that $1\geq 0$ is not required. If $S$ is a preordered semiring, then so is $S^{\mathrm{op}}$. Preordered semifields and preordered semidomains (I.3.16/21) are preordered semirings that are semifields, respectively semidomains, with the additional condition that $x\approx 0$ implies $x=0$; for a preordered semifield, this means equivalently that $1\not\leq 0$ or $1\not\geq 0$.

The following is a central result in the theory of preordered semifields.

In other words, if $x\not\leq y$ in $F$, then the preorder on $F$ can be extended to a total semifield preorder $\preceq$ such that still $x\not\preceq y$, which by totality in particular implies $x\succ y$.

A preordered semifield $F$ is multiplicatively Archimedean if for all nonzero $x,y>1$ in $F$ there is $k\in\mathbb{N}$ with $y\leq x^{k}$ (Definition I.4.1). The paradigmatic examples of multiplicatively Archimedean semifields are $\mathbb{R}_{+}$ with its usual algebraic structure as well as the tropical reals $\mathbb{TR}_{+}$, defined as

where the first equation is the multiplicative picture of $\mathbb{TR}_{+}$ and the second the additive picture. The isomorphism between them is given by the natural logarithm³³3While the logarithm with respect to any base will work, we have found it convenient to fix a particular choice.. As far as it matters, we always specify explicitly which picture of $\mathbb{TR}_{+}$ we use, with the multiplicative picture often being preferred. The tropical reals also contain the Boolean semifield $\mathbb{B}=\{0,1\}$, in which $1+1=1$. It is the terminal object in the category of strict semifields and semiring homomorphisms. All the strict semifields mentioned in this paragraph are preordered semifields with respect to the standard preorder relation.

A surprising construction on preordered semifields is the categorical product (I.3.19). If $F_{1}$ and $F_{2}$ are preordered semifields, then their categorical product has underlying set

and carries the componentwise algebraic operations and the componentwise preorder, and it is straightforward to see that it is a preordered semifield again (having the universal property of a categorical product).

Next, we recall the relevant definitions around polynomial growth (I.3.27). If $S$ is a preordered semiring, then a pair of nonzero elements $u_{-},u_{+}\in S$ is a power universal pair if $u_{-}\leq u_{+}$ and for every nonzero $x,y\in S$ with $x\leq y$, there is $k\in\mathbb{N}$ such that

It follows that the same property holds already if merely $x\sim y$ (I.3.28). We say that $S$ is of polynomial growth if it has a power universal pair. A power universal element is $u\in S$ such that $(1,u)$ is a power universal pair. A preordered semifield of polynomial growth has a power universal element given by $u\coloneqq u_{+}u_{-}^{-1}$. Therefore when working with preordered semifields of polynomial growth, we will always work with a power universal element. On the other hand, there are preordered semirings of polynomial growth that do not have a power universal element but merely a power universal pair, such as the polynomial semiring $\mathbb{N}[X_{1},\ldots,X_{d}]$ equipped with the coefficientwise preorder (I.3.37).

Theorem 2.2 implies the following:

Based on all of these results, we had also developed an abstract Vergleichsstellensatz for preordered semirings $S$ with $1>0$ and having a power universal element $u$. This uses the test spectrum (I.7.1), which under these assumptions⁴⁴4In Section 7, we will introduce a different definition of test spectrum applying to a different class of preordered semirings. A suitable general definition of spectrum of a preordered semiring remains to be found. is the disjoint union of the monotone homomorphisms to $\mathbb{R}_{+}$ and $\mathbb{TR}_{+}$, where the latter are suitably normalized,

and equipped with a certain topology that turns this set into a compact Hausdorff space (I.7.9). The resulting Vergleichsstellensatz reads as follows.

This theorem specializes to a version of Strassen’s Vergleichsstellensatz [7, Corollary 2.6] for $u=2$. In Part I, we also showed how the classical Positivstellensatz of Krivine–Kadison–Dubois can be derived from the latter, and therefore also from our Vergleichsstellensatz, in an elementary way (I.8.4).

Later in the paper, and in particular in the statements of our main results, we will use a few additional concepts that we introduce now.

As for some basic examples, every semifield trivially has quasi-inverses. $\mathbb{N}$ also has quasi-inverses. So does every semidomain of the form $\mathbb{N}_{>0}^{n}\cup\{(0,\ldots,0)\}$, where the semiring structure is given by the componentwise operations.

The relevance of quasi-inverses is explained by the following observation.

The next definition refers to unordered structures only, but will later be used in the context of preordered semirings $S$ with monotone $D$ and degenerate $\phi$.

Note that the set of $\phi$-derivations is a vector space over $\mathbb{R}$. And if $S$ is a preordered semiring, then the set of monotone $\phi$-derivations is a convex cone inside this vector space. In either case, the $\phi$-derivations can be thought of geometrically as tangent vectors to the spectral point $\phi$.

Our results will take a slightly stronger form for semirings which have a scalar multiplication by $\mathbb{R}_{+}$.

In other words, a semialgebra is a semiring which at the same time is a semimodule over $\mathbb{R}_{+}$ [5, Chapter 14] in such a way that the multiplication of $S$ is bilinear.⁶⁶6The definition of semimodule includes the additional law $r(sx)=(rs)x$, but this is implied by the ones we have assumed. As with algebras over commutative rings, a semialgebra is equivalently a semiring $S$ equipped with a semiring homomorphism $\mathbb{R}_{+}\to S$.

As is well-known, one obtains $S\otimes\mathbb{Z}$ by applying the Grothendieck construction to $S$, which means taking the elements of $S\otimes\mathbb{Z}$ to be formal differences of elements of $S$. If $S$ is a semialgebra, then $S\otimes\mathbb{Z}$ is an $\mathbb{R}$-algebra in the obvious way.

Changing topic, we will also need a piece of terminology for preorders that are not necessarily total, but merely total on connected components.

Here is an equivalent characterization.

Clearly every total preorder is full, but not conversely. For example, the trivial preorder on any set is full.

In this section, we prove some elementary but nontrivial results on implications between inequalities in preordered semirings and semifields (with the focus on the latter). These will form an important building block for the deeper results that we develop in the subsequent sections.