assertionAssertion conjectureConjecture definitionDefinition
hypothesisHypothesis remarkRemark noteNote observationObservation
problemProblem questionQuestion algorithmAlgorithm exampleExample
notationNotation 12K10, 16Y60, 03C05, 06F15 Supported by Swiss National
Science Foundation (SNSF) grant No. 200021_215157.

# Equational theories of idempotent semifields

G. Metcalfe and S. Santschi<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

This paper provides answers to several open problems about equational theories
of idempotent semifields. In particular, it is proved that (i) no equational
theory of a non-trivial class of idempotent semifields has a finite basis;
(ii) there are continuum-many equational theories of classes of idempotent
semifields; and (iii) the equational theory of the class of idempotent
semifields is co-NP-complete.

##  1 Introduction

An idempotent semiring is an algebraic structure $\langle{S,\vee,\cdot,{\rm
e}}\rangle$ satisfying

  1. (i)

$\langle{S,\cdot,{\rm e}}\rangle$ is a monoid;

  2. (ii)

$\langle{S,\vee}\rangle$ is a semilattice (i.e., an idempotent commutative
semigroup); and

  3. (iii)

$a(b\vee c)d=abd\vee acd$ for all $a,b,c,d\in S$.

If $\langle{S,\cdot,{\rm e}}\rangle$ is the monoid reduct of a group, then
$\langle{S,\vee,\cdot,{\rm e}}\rangle$ is called an idempotent semifield. Such
structures arise naturally in many areas of mathematics, including idempotent
analysis, tropical geometry, formal language theory, and mathematical logic
(see [6] for details and further references).111Alternative definitions of an
idempotent semiring (also known as a dioid or an ai-semiring) may be found in
the literature that differ with respect to the presence and/or role of
constant symbols in the signature. In particular, an idempotent semiring is
sometimes defined without ${\rm e}$ in the signature, and sometimes with both
${\rm e}$ and a further constant symbol $0$ in the signature, where $0$ is
interpreted as the neutral element of $\vee$. In the latter case, the
definition of an idempotent semifield is changed so that
$\langle{S{\setminus}\\{0\\},\cdot,{\rm e}}\rangle$ is required to be a group.
As explained in Section 5, however, our results extend also to these settings.

Any idempotent semifield $\langle{S,\vee,\cdot,{\rm e}}\rangle$ expanded with
the group inverse operation -1 and lattice meet operation $\wedge$ defined by
setting $a\wedge b:={({a}^{-1}\vee{b}^{-1})}^{-1}$ is a lattice-ordered group
($\ell$-group, for short): an algebraic structure
$\langle{L,\wedge,\vee,\cdot,{}^{-1},{\rm e}}\rangle$ such that $\langle
L,\cdot,{}^{-1},{\rm e}\rangle$ is a group; $\langle L,\wedge,\vee\rangle$ is
a lattice; and the multiplication is order-preserving, i.e., $a\leq
b\>\Longrightarrow\>cad\leq cbd$, for all $a,b,c,d\in L$, where $x\leq
y\>:\Longleftrightarrow\>x\vee y=y$. Indeed, idempotent semifields are
precisely the semiring reducts of $\ell$-groups.

In this paper, we provide answers to several open problems about equational
theories of idempotent semifields and related structures. Although these
problems have been solved for $\ell$-groups, restricting to fewer operations
requires the development of new proof methods and yields notably different
results.

In order to present these results, let us first recall some basic terminology.
A signature ${\mathcal{L}}$ is a set of operation symbols with finite arities,
and an ${\mathcal{L}}$-algebra $\mathbf{A}$ consists of a non-empty set $A$
equipped with an $n$-ary function on $A$ for each operation symbol of
${\mathcal{L}}$ of arity $n$. An ${\mathcal{L}}$-term is built inductively
using the operation symbols of ${\mathcal{L}}$ and a countably infinite set of
variables, and the ${\mathcal{L}}$-term algebra $\mathbf{Tm}({\mathcal{L}})$
consists of the set of ${\mathcal{L}}$-terms equipped with the term-building
operation symbols of ${\mathcal{L}}$. An ${\mathcal{L}}$-equation is an
ordered pair of ${\mathcal{L}}$-terms $s,t$, written $s\approx t$, and is
satisfied by an ${\mathcal{L}}$-algebra $\mathbf{A}$, written
$\mathbf{A}\models s\approx t$, if $\varphi(s)=\varphi(t)$, for any
homomorphism $\varphi\colon\mathbf{Tm}({\mathcal{L}})\to\mathbf{A}$. Given any
class of ${\mathcal{L}}$-algebras $\mathsf{K}$ and set of
${\mathcal{L}}$-equations $\mathrm{\Sigma}$, we denote by
$\mathsf{K}\models\mathrm{\Sigma}$ that $\mathbf{A}\models s\approx t$ for all
$\mathbf{A}\in\mathsf{K}$ and $s\approx t\in\mathrm{\Sigma}$. The equational
theory ${\rm Eq}(\mathsf{K})$ of a class of ${\mathcal{L}}$-algebras
$\mathsf{K}$ is the set of all ${\mathcal{L}}$-equations $s\approx t$ such
that $\mathsf{K}\models s\approx t$.

In Section 2, we provide a complete answer to the finite basis problem for
idempotent semifields. Let $\mathsf{K}$ be any class of
${\mathcal{L}}$-algebras, and call it non-trivial if at least one of its
members is non-trivial, i.e., has more than one element. A basis for the
equational theory of $\mathsf{K}$ is a set of equations
$\mathrm{\Sigma}\subseteq{\rm Eq}(\mathsf{K})$ such that every equation in
${\rm Eq}(\mathsf{K})$ is a logical consequence of $\mathrm{\Sigma}$, that is,
if $\mathbf{A}\models\mathrm{\Sigma}$ for some ${\mathcal{L}}$-algebra
$\mathbf{A}$, then $\mathbf{A}\models{\rm Eq}(\mathsf{K})$. If ${\rm
Eq}(\mathsf{K})$ has a finite basis, then $\mathsf{K}$ is said to be finitely
based. Notably, the equational theory of the $\ell$-group
$\langle{{\mathbb{Z}},\min,\max,+,-,0}\rangle$ is finitely based, but this is
not the case for the semifield $\langle{{\mathbb{Z}},\max,+,0}\rangle$ or any
other totally ordered semifield [1]. Indeed, although countably infinitely
many equational theories of $\ell$-groups have a finite basis (see, e.g.,
[2]), we prove here that:

There is no non-trivial class of idempotent semifields that is finitely based.

In Section 3, we determine the number of equational theories of classes of
idempotent semifields. Using a technique of ‘inverse elimination’ to translate
between equations in the different signatures, we obtain a one-to-one
correspondence between a family of equational theories of $\ell$-groups that
is known to be uncountable and equational theories of certain classes of
idempotent semifields, thereby proving:

There are continuum-many equational theories of classes of idempotent
semifields.

In Section 4, we establish the complexity of deciding equations in the class
of idempotent semifields. The equational theory of the class of $\ell$-groups
is known to be co-NP-complete [5, Theorem 8.3] and we prove here that this is
also the case for the restricted signature, that is:

The equational theory of the class of idempotent semifields is co-NP-complete.

We also use this result to show that the problem of deciding if there exists a
right order on a free group with at least two generators whose positive cone
contains a given finite set of elements is NP-complete and that the same is
true for the problem of deciding if there exists a right order on a free
monoid with countably infinitely many generators that satisfies a given finite
set of inequalities.

Finally, in Section 5, we extend the results of the paper to related
structures considered in the literature: expansions of idempotent semifields
with the meet operation (known to have the same equational theory as the class
of distributive $\ell$-monoids [3]), ${\rm e}$-free reducts of idempotent
semifields, and the class of idempotent semifields extended with a neutral
element $0$ for the join operation.

##  2 The finite basis problem

Let ${\mathcal{L}}_{m}$ and ${\mathcal{L}}_{s}$ be the signatures of monoids
and idempotent semirings, respectively. Following [9], let the flat extension
of an ${\mathcal{L}}_{m}$-algebra $\mathbf{M}=\langle{M,\cdot,{\rm e}}\rangle$
be the ${\mathcal{L}}_{s}$-algebra
$\flat(\mathbf{M})=\langle{M\cup\\{\top\\},\vee,\star,{\rm e}}\rangle$, where
for all $a,b\in M\cup\\{\top\\}$,

$a\star b:=\begin{cases}a\cdot b&\text{if }a,b\in M\\\
\top&\text{otherwise}\end{cases}\qquad\text{and}\qquad a\vee
b:=\begin{cases}a&\text{if }a=b\\\ \top&\text{otherwise.}\end{cases}$

It is easily confirmed that if $\mathbf{M}$ is a monoid, then
$\langle{M\cup\\{\top\\},\star,{\rm e}}\rangle$ is a monoid,
$\langle{M\cup\\{\top\\},\vee}\rangle$ is a semilattice of height one, and
$\top$ is an absorbing element for both the binary operations of
$\flat(\mathbf{M})$. The following result provides a necessary and sufficient
condition for $\flat(\mathbf{M})$ to be an idempotent semiring.

######  Lemma 2.1 (cf. [10, Lemma 2.2])

Let $\mathbf{M}$ be any monoid. Then $\flat(\mathbf{M})$ is an idempotent
semiring if and only if $\mathbf{M}$ is cancellative, i.e.,
$cad=cbd\>\Longrightarrow\>a=b$, for all $a,b,c,d\in M$.

######  Proof 2.2.

Suppose first that $\flat(\mathbf{M})$ is an idempotent semiring and $cad=cbd$
for some $a,b,c,d\in M$. Then $c(a\vee b)d=cad\vee cbd=cad\neq\top$, so $a\vee
b\neq\top$ and $a=b$. For the converse, suppose that $\mathbf{M}$ is
cancellative and consider any $a,b,c,d\in M$. If $b=c$, then, clearly,
$a(b\vee c)d=abd\vee acd$. Otherwise, $b\neq c$ and, by cancellativity,
$abd\neq acd$, so $a(b\vee c)d=a\top d=\top=abd\vee acd$.

Consider now, as key examples for the rest of this section, the monoid reduct
$\mathbf{Z}=\langle{{\mathbb{Z}},+,0}\rangle$ of the additive integer group,
and monoid reducts $\mathbf{Z}_{n}=\langle{Z_{n},\cdot,{\rm e}}\rangle$ of the
cyclic groups of order $n\in{\mathbb{N}}^{>0}$. Since these monoids are
cancellative, their flat extensions, $\flat(\mathbf{Z})$ and
$\flat(\mathbf{Z}_{n})$ ($n\in{\mathbb{N}}^{>0}$), are idempotent semirings
with a flat semilattice structure, as depicted in Figure 1. We will prove
first that the equational theory of a finitely based class of idempotent
semirings $\mathsf{K}$ is satisfied by $\flat(\mathbf{Z})$ if and only if it
is satisfied by $\flat(\mathbf{Z}_{p})$ for every prime $p$ greater than some
suitably large $n\in{\mathbb{N}}$ (Corollary 2.11). We will then show that the
equational theory of any non-trivial class of idempotent semifields is
satisfied by $\flat(\mathbf{Z})$, but not by $\flat(\mathbf{Z}_{n})$ for
$n\in{\mathbb{N}}^{>0}$, thereby establishing that the class is not finitely
based (Theorem A).

$\top$$-2$$-1$$0$$1$$2$$\dots$$\dots$

$\top$$\dots$${\rm e}$$a$$a^{2}$$a^{n-1}$

Figure 1: The Hasse diagrams of $\flat(\mathbf{Z})$ and
$\flat(\mathbf{Z}_{n})$.

For a signature ${\mathcal{L}}$ containing the binary operation symbol $\vee$,
we call an ${\mathcal{L}}$-equation of the form $s\vee t\approx t$, often
written $s\leq t$, an ${\mathcal{L}}$-inequation. We call an
${\mathcal{L}}_{s}$-inequation _simple_ if it is of the form $s\leq
t_{1}\vee\cdots\vee t_{n}$, where $s,t_{1},\dots,t_{n}$ are
${\mathcal{L}}_{m}$-terms, and call this simple ${\mathcal{L}}_{s}$-inequation
left-regular if each variable occurring in $s$ occurs in at least one of
$t_{1},\dots,t_{n}$.

######  Remark 2.3.

Clearly, an idempotent semiring satisfies an ${\mathcal{L}}_{s}$-equation
$s\approx t$ if and only it satisfies the ${\mathcal{L}}_{s}$-inequations
$s\leq t$ and $t\leq s$. Hence, using the distributivity of multiplication
over binary joins and the fact that $a\vee b\leq c\iff a\leq c\text{ and
}b\leq c$ for all elements $a,b,c$ of an idempotent semiring, there exists an
algorithm that produces for every ${\mathcal{L}}_{s}$-equation $\varepsilon$,
a finite set $\Sigma$ of simple ${\mathcal{L}}_{s}$-inequations such that an
arbitrary idempotent semiring satisfies $\varepsilon$ if and only if it
satisfies $\mathrm{\Sigma}$.

######  Remark 2.4.

If an idempotent semiring satisfies a simple ${\mathcal{L}}_{s}$-inequation
that is not left-regular, then — by substituting all variables except for one
that occurs on the left and not the right with ${\rm e}$ — it must also
satisfy $x^{n}\leq{\rm e}$ for some $n\in{\mathbb{N}}^{>0}$. Hence, reasoning
contrapositively, if a simple ${\mathcal{L}}_{s}$-inequation is satisfied by
an idempotent semiring containing an element greater than ${\rm e}$, it must
be left-regular.

For a signature ${\mathcal{L}}$, an ${\mathcal{L}}$-quasiequation is an
ordered pair consisting of a finite set of ${\mathcal{L}}$-equations
$\mathrm{\Sigma}$ and an ${\mathcal{L}}$-equation $s\approx t$, written
$\mathrm{\Sigma}\Rightarrow s\approx t$, and is satisfied by an
${\mathcal{L}}$-algebra $\mathbf{A}$ if for any homomorphism
$\varphi\colon\mathbf{Tm}({\mathcal{L}})\to\mathbf{A}$, whenever
$\varphi(s^{\prime})=\varphi(t^{\prime})$ for all $s^{\prime}\approx
t^{\prime}\in\mathrm{\Sigma}$, also $\varphi(s)=\varphi(t)$. Given any simple
${\mathcal{L}}_{s}$-inequation $\varepsilon=(s\leq t_{1}\vee\cdots\vee
t_{n})$, we define a corresponding ${\mathcal{L}}_{m}$-quasiequation

$Q(\varepsilon):=\\{t_{1}\approx t_{2},\dots,t_{1}\approx t_{n}\\}\Rightarrow
t_{1}\approx s.$

######  Lemma 2.5.

Let $\mathbf{M}$ be any monoid. Then for any left-regular simple
${\mathcal{L}}_{s}$-inequation $\varepsilon$,

$\flat(\mathbf{M})\models\varepsilon\iff\mathbf{M}\models Q(\varepsilon).$

######  Proof 2.6.

Let $\varepsilon=(s\leq t_{1}\vee\cdots\vee t_{n})$ be a left-regular simple
${\mathcal{L}}_{s}$-inequation. For the left-to-right direction suppose
contrapositively that $\mathbf{M}\not\models Q(\varepsilon)$, i.e., there
exists a homomorphism
$\varphi\colon\mathbf{Tm}({\mathcal{L}}_{m})\to\mathbf{M}$ such that
$\varphi(t_{1})=\varphi(t_{2})=\cdots=\varphi(t_{n})$ and
$\varphi(t_{1})\neq\varphi(s)$. Let
$\hat{\varphi}\colon\mathbf{Tm}({\mathcal{L}}_{s})\to\flat(\mathbf{M})$ be the
homomorphism defined by setting $\hat{\varphi}(x):=\varphi(x)$ for each
variable $x$. Then $\hat{\varphi}(u)=\varphi(u)$ for each
${\mathcal{L}}_{m}$-term $u$ and therefore $\hat{\varphi}(t_{1}\vee\cdots\vee
t_{n})=\hat{\varphi}(t_{1})\vee\cdots\vee\hat{\varphi}(t_{n})=\varphi(t_{1})\vee\cdots\vee\varphi(t_{n})=\varphi(t_{1})\neq\varphi(s)=\hat{\varphi}(s)$.
But $\varphi(t_{1}),\varphi(s)\in M$, so $\hat{\varphi}(t_{1}\vee\cdots\vee
t_{n})\not\leq\hat{\varphi}(s)$. Hence
$\flat(\mathbf{M})\not\models\varepsilon$.

For the right-to-left direction suppose, again contrapositively, that
$\flat(\mathbf{M})\not\models\varepsilon$, i.e., there exists a homomorphism
$\psi\colon\mathbf{Tm}({\mathcal{L}}_{s})\to\flat(\mathbf{M})$ such that
$\psi(s)\nleq\psi(t_{1}\vee\cdots\vee t_{n})$. Then it follows from the
definition of the order of $\flat(\mathbf{M})$ that $\psi(t_{1}\vee\cdots\vee
t_{n})\neq\top$ and $\psi(t_{1})=\cdots=\psi(t_{n})\neq\top$. Hence, since
$\varepsilon$ is left-regular, $\psi(x)\in M$ for every variable $x$ occurring
in $\varepsilon$, and we can define a homomorphism
$\hat{\psi}\colon\mathbf{Tm}({\mathcal{L}}_{m})\to\mathbf{M}$ satisfying
$\hat{\psi}(x):=\psi(x)$ for every variable $x$ occurring in $\varepsilon$.
But then, clearly, $\hat{\psi}(t_{1})=\cdots=\hat{\psi}(t_{n})$ and
$\hat{\psi}(t_{1})\neq\hat{\psi}(s)$, so $\mathbf{M}\not\models
Q(\varepsilon)$.

######  Remark 2.7.

The right-to-left direction of Lemma 2.5 does not hold in general for simple
${\mathcal{L}}_{s}$-inequations that are not left-regular; e.g.,
$\mathbf{Z}_{2}\models\emptyset\Rightarrow{\rm e}\approx x^{2}$, but
$\flat(\mathbf{Z}_{2})\not\models x^{2}\leq{\rm e}$.

######  Lemma 2.8.

Let $\mathrm{\Delta}$ be any finite set of ${\mathcal{L}}_{m}$-quasiequations.
Then $\mathbf{Z}\models\mathrm{\Delta}$ if and only if there exists an
$n\in{\mathbb{N}}$ such that $\mathbf{Z}_{p}\models\mathrm{\Delta}$ for each
prime $p>n$.

######  Proof 2.9.

For the right-to-left direction, suppose that there exists an
$n\in{\mathbb{N}}$ such that $\mathbf{Z}_{p}\models\mathrm{\Delta}$ for each
$p\in P:=\\{p\in{\mathbb{N}}\mid\text{$p>n$ and $p$ is prime}\\}$. Since
$\mathrm{\Delta}$ is a set of ${\mathcal{L}}_{m}$-quasiequations, $\prod_{p\in
P}\mathbf{Z}_{p}\models\mathrm{\Delta}$. But the projection maps
$\pi_{p}\colon\mathbf{Z}\to\mathbf{Z}_{p}$ $(p\in P)$ induce an embedding of
$\mathbf{Z}$ into $\prod_{p\in P}\mathbf{Z}_{p}$, so also
$\mathbf{Z}\models\mathrm{\Delta}$.

For the left-to-right direction, suppose that
$\mathbf{Z}\models\mathrm{\Delta}$, and let $T$ be a set of first-order
sentences axiomatizing the class of Abelian groups and let $\alpha$ be the
conjunction of the ${\mathcal{L}}_{m}$-quasiequations in $\mathrm{\Delta}$.
Since an ${\mathcal{L}}_{m}$-quasiequation is satisfied by all torsion-free
Abelian groups if and only if it is satisfied by $\mathbf{Z}$, it follows that
$T\cup\\{\\{x^{k}\approx{\rm e}\\}\Rightarrow x\approx{\rm e}\mid
k\in{\mathbb{N}}\\}\models\alpha$. By compactness, there exists an
$n\in{\mathbb{N}}$ such that $T\cup\\{\\{x^{k}\approx{\rm e}\\}\Rightarrow
x\approx{\rm e}\mid k\in{\mathbb{N}}\text{ and }k\leq n\\}\models\alpha$.
Hence $\mathbf{Z}_{p}\models\mathrm{\Delta}$ for each prime $p>n$.

######  Proposition 2.10.

Let $\mathrm{\Sigma}$ be any finite set of left-regular simple
${\mathcal{L}}_{s}$-inequations. Then
$\flat(\mathbf{Z})\models\mathrm{\Sigma}$ if and only if there exists an
$n\in{\mathbb{N}}$ such that $\flat(\mathbf{Z}_{p})\models\mathrm{\Sigma}$ for
each prime $p>n$.

Let $\mathrm{\Delta}:=\\{Q(\varepsilon)\mid\varepsilon\in\mathrm{\Sigma}\\}$.
Then

$\displaystyle\flat(\mathbf{Z})\models\mathrm{\Sigma}$
$\displaystyle\iff\mathbf{Z}\models\mathrm{\Delta}$ (Lemma 2.5)
$\displaystyle\iff\text{there exists an $n\in{\mathbb{N}}$ such that
$\mathbf{Z}_{p}\models\mathrm{\Delta}$ for each prime $p>n$}$ (Lemma 2.8)
$\displaystyle\iff\text{there exists an $n\in{\mathbb{N}}$ such that
$\flat(\mathbf{Z}_{p})\models\mathrm{\Sigma}$ for each prime $p>n$}$ (Lemma
2.5) . $\displaystyle\proofbox$

######  Corollary 2.11.

Let $\mathsf{K}$ be any finitely based class of idempotent semirings. Then
$\flat(\mathbf{Z})\models{\rm Eq}(\mathsf{K})$ if and only if there exists an
$n\in{\mathbb{N}}$ such that $\flat(\mathbf{Z}_{p})\models{\rm
Eq}(\mathsf{K})$ for each prime $p>n$.

######  Proof 2.12.

By assumption and Remark 2.3, there exists a finite basis $\mathrm{\Sigma}$
for ${\rm Eq}(\mathsf{K})$ consisting of simple
${\mathcal{L}}_{s}$-inequations. However, by Remark 2.4, every simple
${\mathcal{L}}_{s}$-inequation satisfied by $\flat(\mathbf{M})$ for some
monoid $\mathbf{M}$ is left-regular. Hence
$\flat(\mathbf{Z})\models\mathrm{\Sigma}$ if and only there exists an
$n\in{\mathbb{N}}$ such that $\flat(\mathbf{Z}_{p})\models\mathrm{\Sigma}$ for
each prime $p>n$, by Proposition 2.10, and the claim follows directly from the
fact that $\mathrm{\Sigma}$ is a basis for ${\rm Eq}(\mathsf{K})$.

###### Theorem A

There is no non-trivial class of idempotent semifields that is finitely based.

######  Proof 2.13.

Let $\mathsf{K}$ be any non-trivial class of idempotent semifields. Consider
first any $n\in{\mathbb{N}}^{>0}$. Since the ${\mathcal{L}}_{s}$-inequation
$x\leq{\rm e}\vee x^{n}$ is satisfied by all $\ell$-groups, it belongs to
${\rm Eq}(\mathsf{K})$. On the other hand,
$\mathbf{Z}_{n}\not\models\\{x^{n}\approx{\rm e}\\}\Rightarrow x\approx{\rm
e}$ yields $\flat(\mathbf{Z}_{n})\not\models x\leq{\rm e}\vee x^{n}$, by Lemma
2.5, so $\flat(\mathbf{Z}_{n})\not\models{\rm Eq}(\mathsf{K})$. Hence, by
Corollary 2.11, to show that $\mathsf{K}$ is not finitely based it suffices to
prove that $\flat(\mathbf{Z})\models{\rm Eq}(\mathsf{K})$. Moreover, by Remark
2.3, it suffices to show that $\flat(\mathbf{Z})$ satisfies every simple
${\mathcal{L}}_{s}$-inequation in ${\rm Eq}(\mathsf{K})$, and, by Remark 2.4,
since $\mathsf{K}$ is non-trivial, these simple
${\mathcal{L}}_{s}$-inequations are all left-regular.

Let $\varepsilon=(s\leq t_{1}\vee\cdots\vee t_{n})$ be any left-regular simple
${\mathcal{L}}_{s}$-inequation and suppose contrapositively that
$\flat(\mathbf{Z})\not\models\varepsilon$. Then $\mathbf{Z}\not\models
Q(\varepsilon)$, by Lemma 2.5, i.e., there exists a homomorphism
$\varphi\colon\mathbf{Tm}({\mathcal{L}}_{m})\to\mathbf{Z}$ such that
$\varphi(t_{1})=\cdots=\varphi(t_{n})$ and $\varphi(t_{1})\neq\varphi(s)$.
Moreover, we can assume that $\varphi(t_{1})<\varphi(s)$ in the standard order
on ${\mathbb{Z}}$. Now let
$\hat{\varphi}\colon\mathbf{Tm}({\mathcal{L}}_{s})\to\langle{{\mathbb{Z}},\max,+,0}\rangle$
be the homomorphism defined by setting $\hat{\varphi}(x):=\varphi(x)$ for each
variable $x$. Then
$\hat{\varphi}(s)=\varphi(s)>\varphi(t_{1})=\hat{\varphi}(t_{1})=\max\\{\hat{\varphi}(t_{1}),\dots,\hat{\varphi}(t_{n})\\}=\hat{\varphi}(t_{1}\vee\cdots\vee
t_{n})$. So $\langle{{\mathbb{Z}},\max,+,0}\rangle\not\models\varepsilon$. But
$\langle{{\mathbb{Z}},\max,+,0}\rangle$ embeds into every non-trivial
idempotent semifield, so also $\mathsf{K}\not\models\varepsilon$, i.e.,
$\varepsilon\not\in{\rm Eq}(\mathsf{K})$.

Let us remark finally that the approach followed in this section to establish
Theorem A extends to a broader class of idempotent semirings. More precisely,
there is no finitely based class of idempotent semirings $\mathsf{K}$ such
that $\flat(\mathbf{Z})\models{\rm Eq}(\mathsf{K})$ and $\mathsf{K}\models
x\leq{\rm e}\vee x^{n}$ for every $n\in{\mathbb{N}}^{>0}$. In particular, the
class of totally ordered idempotent semirings is not finitely based, which
follows also from results of [1].

##  3 The number of equational theories

For any countable signature ${\mathcal{L}}$ and class of
${\mathcal{L}}$-algebras $\mathsf{K}$, there can be at most continuum-many
equational theories of subclasses of $\mathsf{K}$. In particular, although
there are just two equational theories of classes of commutative idempotent
semifields — ${\rm Eq}(\langle{{\mathbb{Z}},+,0,\max}\rangle)$ and the set of
all ${\mathcal{L}}_{s}$-equations — the maximum number is attained in the
setting of commutative idempotent semirings.

######  Proposition 3.1.

There are continuum-many equational theories of classes of commutative
idempotent semirings.

######  Proof 3.2.

For any set of primes $P$, let $\mathrm{\Sigma}_{P}$ denote the equational
theory of the class of commutative idempotent semirings satisfying $x\leq{\rm
e}\vee x^{p}$ for all $p\in P$. We show that
$\mathrm{\Sigma}_{P}\neq\mathrm{\Sigma}_{Q}$ for any two distinct sets of
primes $P$ and $Q$, and hence that there are continuum-many such equational
theories. Consider, without loss of generality, $p\in P{\setminus}Q$. Then
$x\leq{\rm e}\vee x^{p}\in\mathrm{\Sigma}_{P}$. But also, since
$\mathbf{Z}_{p}\not\models\\{{\rm e}\approx x^{p}\\}\Rightarrow{\rm e}\approx
x$ and $\mathbf{Z}_{p}\models\\{{\rm e}\approx x^{q}\\}\Rightarrow{\rm
e}\approx x$ for any $q\in Q$, it follows from Lemma 2.5 that
$\flat(\mathbf{Z}_{p})\not\models x\leq{\rm e}\vee x^{p}$ and
$\flat(\mathbf{Z}_{p})\models x\leq{\rm e}\vee x^{q}$ for any $q\in Q$. So
$x\leq{\rm e}\vee x^{p}\not\in\mathrm{\Sigma}_{Q}$.

To prove that the maximum number of equational theories is attained also in
the setting of idempotent semifields (Theorem B), we make use of a
corresponding result for a certain class of $\ell$-groups. Note first that,
unlike idempotent semifields, $\ell$-groups form a variety: a class of
algebras of the same signature that is closed under taking homomorphic images,
subalgebras, and direct products — or, equivalently, by Birkhoff’s theorem, an
equational class. Equational theories of classes of $\ell$-groups are
therefore in one-to-one correspondence with varieties of $\ell$-groups. In
particular, equational theories of classes of totally ordered groups
correspond to varieties of $\ell$-groups that are representable, that is,
subalgebras of direct products of totally ordered groups. For further details
and references, we refer to [2].

Let ${\mathcal{L}}_{g}$ and ${\mathcal{L}}_{\ell}$ be the signatures of groups
and $\ell$-groups, respectively. A crucial role in our proof of Theorem B will
be played by the following result, recalling that a variety $\mathsf{V}_{1}$
is defined relative to a variety $\mathsf{V}_{2}$ by a set of equations
$\mathrm{\Sigma}$ if $\mathsf{V}_{1}$ consists of all the members of
$\mathsf{V}_{2}$ that satisfy $\mathrm{\Sigma}$:

######  Theorem 3.3 ([11, Theorem 1]).

There are continuum-many varieties defined relative to the variety of
representable $\ell$-groups by a set of ${\mathcal{L}}_{g}$-equations

To prove that there are continuum-many equational theories of classes of
idempotent semifields, it suffices, by Theorem 3.3, to show that any two
varieties defined relative to the variety of representable $\ell$-groups by
sets of ${\mathcal{L}}_{g}$-equations can be distinguished by an
${\mathcal{L}}_{s}$-equation. As we show below, such equations can be obtained
by ‘eliminating inverses’ from ${\mathcal{L}}_{\ell}$-inequations.

Let us say that a variety $\mathsf{V}$ of $\ell$-groups has the product-
splitting property if for any ${\mathcal{L}}_{\ell}$-terms $s,t,u$ and
variable $y$ that does not occur in $s,t,u$,

$\mathsf{V}\models{\rm e}\leq u\vee st\iff\mathsf{V}\models{\rm e}\leq u\vee
sy\vee{y}^{-1}t.$

######  Lemma 3.4.

Let $\mathsf{V}$ be any variety that is defined relative to the variety of
representable $\ell$-groups by a set of ${\mathcal{L}}_{g}$-equations. Then
$\mathsf{V}$ has the product-splitting property.

######  Proof 3.5.

Consider any ${\mathcal{L}}_{\ell}$-terms $s,t,u$ and variable $y$ that does
not occur in $s,t,u$. Suppose first that $\mathsf{V}\models{\rm e}\leq u\vee
st$. Every $\ell$-group satisfies the ${\mathcal{L}}_{s}$-quasiequation
$\\{{\rm e}\leq x\vee yz\\}\Rightarrow{\rm e}\leq x\vee y\vee z$ (cf. [5,
Lemma 3.3]), so also $\mathsf{V}\models{\rm e}\leq u\vee sy\vee{y}^{-1}t$. Now
suppose that $\mathsf{V}\not\models{\rm e}\leq u\vee st$. Since $\mathsf{V}$
is a variety of representable $\ell$-groups, there exists a totally ordered
group $\mathbf{L}\in\mathsf{V}$ and homomorphism
$\varphi\colon\mathbf{Tm}({\mathcal{L}}_{\ell})\to\mathbf{L}$ such that ${\rm
e}>\varphi(u\vee st)=\varphi(u)\vee\varphi(s)\varphi(t)$. So ${\rm
e}>\varphi(u)$ and ${\varphi(s)}^{-1}>\varphi(t)$. Observe next that
$\mathbf{L}$ embeds into the totally ordered group $\mathbf{M}$ consisting of
the direct product of the group reduct of $\mathbf{L}$ and
$\mathbf{Q}=\langle{{\mathbb{Q}},\min,\max,+,-,0}\rangle$ equipped with the
lexicographic order on $L\times{\mathbb{Q}}$ via
$\psi\colon\mathbf{L}\to\mathbf{M};\>a\mapsto\langle{a,0}\rangle$. Moreover,
any ${\mathcal{L}}_{g}$-equation satisfied by $\mathbf{L}$ and $\mathbf{Q}$ is
satisfied by $\mathbf{M}$ and, hence, since $\mathbf{Q}$ is a member of every
non-trivial variety of $\ell$-groups, $\mathbf{M}\in\mathsf{V}$. Define the
homomorphism
$\hat{\varphi}\colon\mathbf{Tm}({\mathcal{L}}_{\ell})\to\mathbf{M}$ by setting
$\hat{\varphi}(y):=\langle{\varphi(t),1}\rangle$ and
$\hat{\varphi}(x)=\varphi(x)$ for each variable $x\neq y$. Then ${\rm
e}>\hat{\varphi}(u)$ and
${\hat{\varphi}(s)}^{-1}>\hat{\varphi}(y)>\hat{\varphi}(t)$, yielding ${\rm
e}>\hat{\varphi}(s)\hat{\varphi}(y)=\hat{\varphi}(sy)$ and ${\rm
e}>{\hat{\varphi}(y)}^{-1}\hat{\varphi}(t)=\hat{\varphi}({y}^{-1}t)$. Hence
${\rm e}>\hat{\varphi}(u\vee sy\vee{y}^{-1}t)$, i.e.,
$\mathsf{V}\not\models{\rm e}\leq u\vee sy\vee{y}^{-1}t$.

######  Remark 3.6.

The proof of Lemma 3.4 establishes that every variety $\mathsf{V}$ defined
relative to the variety of representable $\ell$-groups by a set of
${\mathcal{L}}_{g}$-equations is densifiable, that is, every totally ordered
member of $\mathsf{V}$ embeds into a dense totally ordered member of
$\mathsf{V}$. Clearly, every densifiable variety of representable
$\ell$-groups has the product-splitting property; indeed, densifiability is
equivalent to a slightly stronger version of the product-splitting property in
the broader setting of semilinear residuated lattices (see [13] for details
and further references).

Observe next that if $\mathsf{V}$ is a variety of $\ell$-groups that has the
product-splitting property, then for any ${\mathcal{L}}_{\ell}$-terms
$r,s,t,u,v$ and variable $y$ that does not occur in $r,s,t,u,v$,

$\mathsf{V}\models u\leq v\vee s{r}^{-1}t\iff\mathsf{V}\models ryu\leq ryv\vee
rysyu\vee t.$

We can use this equivalence to ‘eliminate inverses’ from
${\mathcal{L}}_{\ell}$-inequations. Let us call an
${\mathcal{L}}_{\ell}$-inequation $\varepsilon$ basic if it is of the form
$s\leq t_{1}\vee\cdots\vee t_{n}$ for ${\mathcal{L}}_{g}$-terms
$t_{1},\dots,t_{n}$ and an ${\mathcal{L}}_{m}$-term $s$. For any basic
${\mathcal{L}}_{\ell}$-inequation $\varepsilon$, the
${\mathcal{L}}_{s}$-inequation $\varepsilon^{\star}$ is defined recursively as
follows:

  1. $\bullet$

If $\varepsilon=(s\leq t_{1}\vee\cdots\vee t_{n})$ is an
${\mathcal{L}}_{s}$-inequation, let $\varepsilon^{\star}:=\varepsilon$;
otherwise, let $i\in\\{1,\dots,n\\}$ be minimal such that $t_{i}=u{x}^{-1}v$
for some ${\mathcal{L}}_{m}$-term $u$, and let

$\varepsilon^{\star}:=(xys\leq xyt_{1}\vee\cdots\vee xyt_{i-1}\vee xyuxs\vee
v\vee xyt_{i+1}\vee\cdots\vee xyt_{n})^{\star}.$

An induction on the number of occurrences in $\varepsilon$ of the inverse
operation symbol establishes:

######  Proposition 3.7.

Let $\mathsf{V}$ be any variety of $\ell$-groups that has the product-
splitting property. Then
$\mathsf{V}\models\varepsilon\iff\mathsf{V}\models\varepsilon^{\star}$ for any
basic ${\mathcal{L}}_{\ell}$-equation $\varepsilon$.

###### Theorem B

There are continuum-many equational theories of classes of idempotent
semifields.

######  Proof 3.8.

There are continuum-many varieties defined relative to the variety of
representable $\ell$-groups by ${\mathcal{L}}_{g}$-equations, by Theorem 3.3.
Moreover, all these varieties have the product-splitting property, by Lemma
3.4. For each such variety $\mathsf{V}$, let $\mathrm{\Sigma}_{\mathsf{V}}$ be
the equational theory of the class of idempotent semiring reducts of members
of $\mathsf{V}$. Consider now any two distinct varieties $\mathsf{V}_{1}$ and
$\mathsf{V}_{2}$ defined relative to the variety of representable
$\ell$-groups by sets of ${\mathcal{L}}_{g}$-equations. Without loss of
generality, there exists a basic ${\mathcal{L}}_{\ell}$-equation $\varepsilon$
such that $\mathsf{V}_{1}\models\varepsilon$ and
$\mathsf{V}_{2}\not\models\varepsilon$. But then also
$\mathsf{V}_{1}\models\varepsilon^{\star}$ and
$\mathsf{V}_{2}\not\models\varepsilon^{\star}$, by Proposition 3.7, and since
$\varepsilon^{\star}$ is an ${\mathcal{L}}_{m}$-equation,
$\mathrm{\Sigma}_{\mathsf{V}_{1}}\neq\mathrm{\Sigma}_{\mathsf{V}_{2}}$. Hence
there are continuum-many equational theories of classes of idempotent
semifields.

##  4 The complexity of the equational theory of idempotent semifields

The equational theory of the variety of Abelian $\ell$-groups — equivalently,
the equational theory of $\langle{{\mathbb{Z}},\max,\min,+,-,0}\rangle$ — is
known to be co-NP-complete [16]. On the other hand, it follows from the fact
that the linear programming problem is solvable in polynomial time that the
equational theory of the class of commutative idempotent semifields —
equivalently, the equational theory of $\langle{{\mathbb{Z}},\max,+,0}\rangle$
— belongs to P. However, the equational theory of not only the variety
$\mathsf{LG}$ of $\ell$-groups [5, Theorem 8.3], but also, as we show here,
the class of idempotent semifields (Theorem C) are co-NP-complete. Indeed, we
establish this result by giving a polynomial reduction of the problem of
checking the satisfaction of an ${\mathcal{L}}_{\ell}$-inequation by
$\mathsf{LG}$ to the problem of checking the satisfaction of an
${\mathcal{L}}_{s}$-equation by the class of idempotent semifields.

Let us say that a variety $\mathsf{V}$ of $\ell$-groups has the meet-splitting
property if for any ${\mathcal{L}}_{\ell}$-terms $s,t,u$ and variable $y$ that
does not occur in $s,t,u$,

$\mathsf{V}\models{\rm e}\leq u\vee(s\wedge t)\iff\mathsf{V}\models{\rm e}\leq
u\vee sy\vee t{y}^{-1}.$

######  Lemma 4.1.

The variety of $\ell$-groups has the product-splitting and meet-splitting
properties.

######  Proof 4.2.

The fact that $\mathsf{LG}$ has the product-splitting property is established
in [3, Lemma 4.1].

To establish the left-to-right direction of the meet-splitting property for
$\mathsf{LG}$, it suffices to show that $\mathsf{LG}\models u\vee(s\wedge
t)\leq u\vee sy\vee t{y}^{-1}$: just note that for any
$\mathbf{L}\in\mathsf{LG}$ and $a,b,c,d\in L$, since ${\rm e}\leq
d\vee{d}^{-1}$,

$a\vee(b\wedge c)\leq a\vee(b\wedge c)(d\vee{d}^{-1})=a\vee(b\wedge
c)d\vee(b\wedge c){d}^{-1}\leq a\vee bd\vee c{d}^{-1}.$

For the converse, let $s,t,u$ be any ${\mathcal{L}}_{\ell}$-terms, let $y$ be
a variable that does not occur in $s,t,u$, and suppose that
$\mathsf{LG}\not\models{\rm e}\leq u\vee(s\wedge t)$. Using lattice-
distributivity, we may assume that $\mathsf{LG}\not\models{\rm e}\leq u\vee
s$, the case where $\mathsf{LG}\not\models{\rm e}\leq u\vee t$ being very
similar. An ${\mathcal{L}}_{\ell}$-equation is satisfied by $\mathsf{LG}$ if
and only if it is satisfied by the $\ell$-group
$\mathbf{Aut}(\langle{\mathbb{R}},\leq\rangle)$ consisting of the group of
order-preserving bijections of the totally ordered set
$\langle{\mathbb{R}},\leq\rangle$ equipped with the pointwise lattice-order
[7, Corollary to Lemma 3]. Hence
$\mathbf{Aut}(\langle{\mathbb{R}},\leq\rangle)\not\models{\rm e}\leq u\vee s$,
and there exists a homomorphism
$\varphi\colon\mathbf{Tm}({\mathcal{L}}_{\ell})\to\mathbf{Aut}(\langle{\mathbb{R}},\leq\rangle)$
and $q\in{\mathbb{R}}$ such that $(q)\varphi_{u}<q$ and $(q)\varphi_{s}<q$,
where we assume that order-preserving bijections act on
$\langle{\mathbb{R}},\leq\rangle$ from the right, and write $\varphi_{v}$ for
$\varphi(v)$.

We obtain a homomorphism
$\hat{\varphi}\colon\mathbf{Tm}({\mathcal{L}}_{\ell})\to\mathbf{Aut}(\langle{\mathbb{R}},\leq\rangle)$
by defining $\hat{\varphi}_{x}:=\varphi_{x}$ for every variable $x\neq y$ and
defining $\hat{\varphi}_{y}$ such that
$(q)\varphi_{s}\hat{\varphi}_{y}=(q)\varphi_{s}<q$ and
$(q)\varphi_{t}<(q)\hat{\varphi}_{y}$. Note that such a definition of
$\hat{\varphi}_{y}$ is possible because $(q)\hat{\varphi}_{y}$ can be chosen
to be arbitrarily large and any partial order-preserving injective map on
$\langle{\mathbb{R}},\leq\rangle$ extends linearly to a member of
$\mathbf{Aut}(\langle{\mathbb{R}},\leq\rangle)$. It follows, since $y$ does
not occur in $s,t,u$, that $(q)\hat{\varphi}_{u}=(q)\varphi_{u}<q$,
$(q)\hat{\varphi}_{s}\hat{\varphi}_{y}=(q)\varphi_{s}\hat{\varphi}_{y}=(q)\varphi_{s}<q$
and $(q)\hat{\varphi}_{t}=(q)\varphi_{t}<(q)\hat{\varphi}_{y}$. Hence
$\mathsf{LG}\not\models{\rm e}\leq u\vee sy\vee t{y}^{-1}$.

######  Remark 4.3.

No non-trivial proper subvariety of $\mathsf{LG}$ has the meet-splitting
property. It follows easily from [12, Example 13] that the
${\mathcal{L}}_{\ell}$-equation ${\rm e}\leq(x\vee{\rm
e})^{2}{z}^{-1}\vee{(x\vee{\rm e})}^{-1}z\vee{(x\vee{\rm e})}^{-1}$ is
satisfied by every proper subvariety of $\mathsf{LG}$; indeed, it axiomatizes
relative to $\mathsf{LG}$ the variety of normal-valued $\ell$-groups, the
unique co-atom in the subvariety lattice of $\ell$-groups. Hence, if a proper
subvariety of $\mathsf{LG}$ has the meet-splitting property, it satisfies also
${\rm e}\leq{(x\vee{\rm e})}^{-1}$ and is trivial.

######  Proposition 4.4.

The problem of checking if a basic ${\mathcal{L}}_{\ell}$-equation is
satisfied by the variety of $\ell$-groups is co-NP-complete.

######  Proof 4.5.

It is known that the problem of checking if an ${\mathcal{L}}_{\ell}$-equation
is satisfied by $\mathsf{LG}$ belongs to co-NP [5, Theorem 8.3]. It therefore
suffices to present a polynomial time algorithm that given input with an
${\mathcal{L}}_{\ell}$-equation $\varepsilon$ of the form

$\bigwedge_{i\in I}\bigvee_{j\in J_{i}}s_{ij}\leq\bigvee_{k\in
K}\bigwedge_{l\in L_{k}}t_{kl}\vee u_{kl},$

where each $s_{ij}$, $t_{kl}$, and $u_{kl}$ is an ${\mathcal{L}}_{g}$-term,
outputs a basic ${\mathcal{L}}_{\ell}$-equation $\delta$ that has size
polynomial in the size of $\varepsilon$ such that
$\mathsf{LG}\models\varepsilon\iff\mathsf{LG}\models\delta$. Just note that
the problem of checking validity in $\mathsf{LG}$ of
${\mathcal{L}}_{\ell}$-equations this form is co-NP-hard, since this is the
case even for distributive lattice equations of this form where each $s_{ij}$,
$t_{kl}$, and $u_{kl}$ is a variable [8, Corollary 2.7].

First, we do a little preprocessing, using the fact that $\mathsf{LG}$ has the
product-splitting property for the third equivalence:

$\displaystyle\mathsf{LG}\models\varepsilon$
$\displaystyle\iff\mathsf{LG}\models{\rm e}\leq(\bigvee_{k\in
K}\bigwedge_{l\in L_{k}}t_{kl}\vee u_{kl})(\bigwedge_{i\in I}\bigvee_{j\in
J_{i}}{s}^{-1}_{ij})$ $\displaystyle\iff\mathsf{LG}\models{\rm
e}\leq(\bigvee_{k\in K}\bigwedge_{l\in L_{k}}t_{kl}\vee u_{kl})(\bigvee_{i\in
I}\bigwedge_{j\in J_{i}}{s}^{-1}_{ij})$
$\displaystyle\iff\mathsf{LG}\models{\rm e}\leq(\bigvee_{k\in
K}\bigwedge_{l\in L_{k}}t_{kl}\vee u_{kl})y\vee{y}^{-1}(\bigvee_{i\in
I}\bigwedge_{j\in J_{i}}{s}^{-1}_{ij})$
$\displaystyle\iff\mathsf{LG}\models{\rm e}\leq(\bigvee_{k\in
K}\bigwedge_{l\in L_{k}}t_{kl}y\vee u_{kl}y)\vee(\bigvee_{i\in
I}\bigwedge_{j\in J_{i}}{y}^{-1}{s}^{-1}_{ij}).$

Hence we may assume that $\varepsilon$ is an ${\mathcal{L}}_{\ell}$-equation
of the form ${\rm e}\leq u_{1}\vee\cdots\vee u_{n}$, where each $u_{i}$ is a
meet of binary joins of ${\mathcal{L}}_{g}$-terms, and let $S$ be the size of
$\varepsilon$, so that at most $S$ ${\mathcal{L}}_{g}$-terms and at most $S$
meets occur in $\varepsilon$.

If $\varepsilon$ contains no meets, it is the required basic
${\mathcal{L}}_{\ell}$-equation. Otherwise, suppose that
$u_{1}=s_{1}\wedge\cdots\wedge s_{m}$ such that $s_{i}=s_{i1}\vee s_{i2}$ and
let $u:=u_{2}\vee\cdots\vee u_{n}$. By choosing distinct variables
$y_{1},\dots,y_{m}$ that do not occur in $\varepsilon$ and using the meet-
splitting property repeatedly,

$\displaystyle\mathsf{LG}\models\varepsilon$
$\displaystyle\iff\mathsf{LG}\models{\rm e}\leq u\vee(s_{1}\wedge\cdots\wedge
s_{m})$ $\displaystyle\iff\mathsf{LG}\models{\rm e}\leq u\vee
s_{1}y_{1}\vee(s_{2}\wedge\cdots\wedge s_{m}){y}^{-1}_{1}$
$\displaystyle\iff\mathsf{LG}\models{\rm e}\leq u\vee
s_{1}y_{1}\vee(s_{2}{y}^{-1}_{1}\wedge\cdots\wedge s_{m}{y}^{-1}_{1})$
$\displaystyle\iff\qquad\vdots$ $\displaystyle\iff\mathsf{LG}\models{\rm
e}\leq u\vee s_{1}y_{1}\vee s_{2}{y}^{-1}_{1}y_{2}\vee\cdots\vee
s_{m}{y}^{-1}_{1}\cdots{y}^{-1}_{m-1}y_{m}$
$\displaystyle\iff\mathsf{LG}\models{\rm e}\leq u\vee s_{11}y_{1}\vee
s_{12}y_{1}\vee(\bigvee_{i=2}^{m}s_{i1}{y}^{-1}_{1}\cdots{y}^{-1}_{i-1}y_{i}\vee
s_{i2}{y}^{-1}_{1}\cdots{y}^{-1}_{i-1}y_{i})$

Let $\varepsilon^{\prime}$ be the ${\mathcal{L}}_{\ell}$-equation ${\rm e}\leq
u\vee s_{11}y_{1}\vee
s_{12}y_{1}\vee(\bigvee_{i=2}^{m}s_{i1}{y}^{-1}_{1}\cdots{y}^{-1}_{i-1}y_{i}\vee
s_{i2}{y}^{-1}_{1}\cdots{y}^{-1}_{i-1}y_{i})$, observing that
$\varepsilon^{\prime}$ has the same number of ${\mathcal{L}}_{g}$-terms as
$\varepsilon$, and that each of these ${\mathcal{L}}_{g}$-terms has size at
most $2S$. Hence, repeating this procedure for $u_{2},\dots,u_{n}$, we obtain
in polynomial time a basic ${\mathcal{L}}_{\ell}$-equation $\delta$ of size at
most $2S^{2}$ such that
$\mathsf{LG}\models\varepsilon\iff\mathsf{LG}\models\delta$.

######  Proposition 4.6.

The problem of checking if a simple ${\mathcal{L}}_{s}$-equation is satisfied
by the class of semifields (or, equivalently, by the variety of $\ell$-groups)
is co-NP-complete.

######  Proof 4.7.

Recall that $\mathsf{LG}$ has the product-splitting property, by Lemma 4.1.
Hence, it suffices, by Proposition 4.4 and Proposition 3.7, to present a
polynomial time algorithm that given a basic ${\mathcal{L}}_{\ell}$-equation
$\varepsilon$ of the form $s\leq t_{1}\vee\cdots\vee t_{k}$ as input produces
the simple ${\mathcal{L}}_{s}$-equation $\varepsilon^{\star}$ as output, where
the size of $\varepsilon^{\star}$ should be polynomial in the size of
$\varepsilon$. Let $S$ be the size of $\varepsilon$ and recall that
$\varepsilon^{\star}$ is defined recursively by the following algorithm:

  1. $\bullet$

If $\varepsilon=(s\leq t_{1}\vee\cdots\vee t_{n})$ is an
${\mathcal{L}}_{s}$-inequation, let $\varepsilon^{\star}:=\varepsilon$;
otherwise, let $i\in\\{1,\dots,n\\}$ be minimal such that $t_{i}=u{x}^{-1}v$
for some ${\mathcal{L}}_{m}$-term $u$, and let

$\varepsilon^{\star}:=(xys\leq xyt_{1}\vee\cdots\vee xyt_{i-1}\vee xyuxs\vee
v\vee xyt_{i+1}\vee\cdots\vee xyt_{n})^{\star}.$

The number of inverses in $\varepsilon$ is bounded by $S$ and decreases in
every step of the recursive definition, so the algorithm stops after at most
$S$ steps and yields the ${\mathcal{L}}_{s}$-inequation $\varepsilon^{\star}$.
Moreover, each step increases the length of the ${\mathcal{L}}_{m}$-term on
the left of the basic ${\mathcal{L}}_{\ell}$-equation by $2$ and increases the
number of ${\mathcal{L}}_{g}$-terms on the right by $1$. Hence the length of
the ${\mathcal{L}}_{m}$-term on the left is at most $3S$ and the number of
${\mathcal{L}}_{g}$-terms is at most $2S$ in every step. It follows that in
every step the size of the ${\mathcal{L}}_{s}$-inequation is increased by at
most $3S+2\cdot 2S=7S$ and hence $\varepsilon^{\star}$ is of size at most
$7S^{2}+S$. It is also clear that $\varepsilon^{\star}$ can be computed from
$\varepsilon$ in polynomial time.

As an immediate consequence of Proposition 4.6 we obtain the main result of
this section.

###### Theorem C

The equational theory of the class of idempotent semifields is co-NP-complete.

We conclude this section by using Theorem C and a correspondence established
in [4] to prove complexity results also for the existence of right orders on
free groups and monoids satisfying finitely many constraints. Recall first
that a right order on a monoid (or group) $\mathbf{M}$ is a total order $\leq$
on $M$ such that $a\leq b\>\Longrightarrow\>ac\leq bc$ for any $a,b,c\in{M}$.
For a set $X$ we let $\mathbf{F}_{g}(X)$ and $\mathbf{F}_{m}(X)$ denote the
free group and free monoid with generators in $X$, respectively, assuming for
convenience that ${\rm F}_{g}(X)\subseteq{\rm Tm}({\mathcal{L}}_{g})$ and
${\rm F}_{m}(X)\subseteq{\rm Tm}({\mathcal{L}}_{m})$.

######  Theorem 4.8 ([4, Theorem 2]).

For any set $X$ and $s_{1},\ldots,s_{n}\in{\rm F}_{g}(X)$, there exists a
right order $\leq$ on $\mathbf{F}_{g}(X)$ satisfying ${\rm e}<s_{1},\dots,{\rm
e}<s_{n}$ if and only if $\mathsf{LG}\not\models{\rm e}\leq
s_{1}\vee\cdots\vee s_{n}$.

######  Corollary 4.9.

The problem of checking for a set $X$ with $\lvert X\rvert\geq 2$ and
$s_{1},\ldots,s_{n}\in{\rm F}_{g}(X)$ if there exists a right order $\leq$ on
$\mathbf{F}_{g}(X)$ satisfying ${\rm e}<s_{1},\dots,{\rm e}<s_{n}$ is NP-
complete.

######  Proof 4.10.

Observe first that for the case where $X$ is an infinite set, the claim
follows directly from Proposition 4.4 and Theorem 4.8. To establish the claim
in full generality, it suffices, by Theorem 4.8, to consider the case where
$\lvert X\rvert=2$. Let $X:=\\{x,y\\}$ and $Y:=\\{x_{n}\mid
n\in{\mathbb{N}}\\}$. It is well-known that $\mathbf{F}_{g}(Y)$ is isomorphic
to the commutator subgroup $\mathbf{G}$ of $\mathbf{F}_{g}(X)$ generated by
elements of the form $[x^{k},y^{l}]$ with
$k,l\in{\mathbb{Z}}{\setminus}\\{0\\}$ (see, e.g., [15, Theorem 11.48]). In
particular, for any bijection
$\pi\colon({\mathbb{Z}}{\setminus}\\{0\\})^{2}\to{\mathbb{N}}$, we can define
an isomorphism $\varphi\colon\mathbf{F}_{g}(Y)\to\mathbf{G}$ such that
$\varphi(x_{\pi(\langle{k,l}\rangle)}):=[x^{k},y^{l}]$ for
$k,l\in{\mathbb{Z}}{\setminus}\\{0\\}$.

Moreover, since
$\mathbf{F}_{g}(X)/\mathbf{G}\cong\langle{{\mathbb{Z}}^{2},+,-,0}\rangle$,
there exists a right order $\preceq$ on the group
$\mathbf{F}_{g}(X)/\mathbf{G}$. Hence, if $\leq$ is any right order on
$\mathbf{G}$, we can define a right order $\leq^{\ast}$ on $\mathbf{F}_{g}(X)$
that extends $\leq$ by setting

$s\leq^{\ast}t\>:\Longleftrightarrow\>Gs\prec Gt\,\text{ or }\,(Gs=Gt\,\text{
and }\,{\rm e}\leq ts^{-1}).$

It follows that given any $s_{1},\ldots,s_{n}\in{\rm F}_{g}(Y)$, there exists
a right order on $\mathbf{F}_{g}(Y)$ satisfying ${\rm e}<s_{1},\dots,{\rm
e}<s_{n}$ if and only if there exists a right order on $\mathbf{F}_{g}(X)$
satisfying ${\rm e}<\varphi(s_{1}),\dots,{\rm e}<\varphi(s_{n})$. Finally,
note that $\pi$ can be chosen such that $\varphi(s_{i})$ is computable in
polynomial time from $s_{i}$ for each $i=1,\dots,n$, and its size is
polynomial in the sum of the sizes of $s_{1},\dots,s_{n}$.

By [3, Corollary 3.4], every right order on $\mathbf{F}_{m}(X)$ extends to a
right order on $\mathbf{F}_{g}(X)$. Hence, by Theorem 4.8, for any
$s,t_{1},\dots,t_{n}\in{\rm F}_{m}(X)$ we have $\mathsf{LG}\not\models s\leq
t_{1}\vee\cdots\vee t_{n}$ if and only if there exist a right order $\leq$ on
$\mathbf{F}_{m}(X)$ with $s<t_{1},\dots,s<t_{n}$; and Proposition 4.6 yields:

######  Corollary 4.11.

The problem of checking if for finitely many elements $s,t_{1},\dots,t_{n}$ of
a free monoid $\mathbf{F}_{m}(X)$ with $\lvert X\rvert=\omega$ there exists a
right order $\leq$ on $\mathbf{F}_{m}(X)$ with $s<t_{i}$ is NP-complete.

Note that it does not follow directly from the previous results that Corollary
4.11 extends to the case where $\lvert X\rvert<\omega$, the main obstacle
being that the translation $\varphi$ in the proof of Corollary 4.9 introduces
new inverses, while the elimination of inverses in the proof of Proposition
4.6 introduces new variables. The exact complexity of this problem for
finitely generated free monoids therefore remains open.

##  5 Related structures

In this final section, we show that the results of the previous sections
extend in many cases to other classes of algebraic structures that are closely
related to semifields and $\ell$-groups.

Let us remark first that expanding any idempotent semifield with the lattice
meet operation produces a distributive $\ell$-monoid: an algebraic structure
$\langle{L,\wedge,\vee,\cdot,{\rm e}}\rangle$ such that $\langle{L,\cdot,{\rm
e}}\rangle$ is a monoid; $\langle{L,\wedge,\vee}\rangle$ is a distributive
lattice; and multiplication distributes over binary meets and joins. It
follows directly from Theorem B that there are continuum-many equational
theories of classes of distributive $\ell$-monoids with an idempotent
semifield reduct, and from Theorem C, as already observed in [3], that the
equational theory of distributive $\ell$-monoids is co-NP-complete. Although
not every distributive $\ell$-monoid is the meet-expansion of an idempotent
semifield (equivalently, the inverse-free reduct of an $\ell$-group), the
equational theories of the classes of distributive $\ell$-monoids and meet-
expansions of idempotent semifields (equivalently, the inverse-free reducts of
$\ell$-groups) coincide [3, Theorem 2.9]. Hence the equational theory of the
class of meet-expansions of idempotent semifields is finitely based and an
analogue of Theorem A does not hold in this setting. Note, however, that even
though the equational theory of Abelian $\ell$-groups is finitely based, this
is not the case for the class of their inverse-free reducts [14, Theorem 2].

Recall next that idempotent semifields are sometimes formulated in the
literature without the neutral element ${\rm e}$ in the signature, that is, as
${\rm e}$-free reducts of idempotent semifields as defined in this paper.
Observe, however, that a simple ${\mathcal{L}}_{s}$-inequation $s\leq
t_{1}\vee\cdots\vee s_{n}$ is satisfied by an idempotent semifield
$\mathbf{S}$ if and only if its ${\rm e}$-free reduct satisfies
$(xs)^{\circ}\leq(xt_{1})^{\circ}\vee\cdots\vee(xs_{n})^{\circ}$, where $x$ is
any variable not occurring in $s,t_{1},\dots,t_{n}$, and $v^{\circ}$ is
obtained by removing all occurrences of ${\rm e}$ from an
${\mathcal{L}}_{s}$-term $v$. Hence, we obtain easily the following analogues
of Theorems A, B, and C: there is no non-trivial class of ${\rm e}$-free
reducts of idempotent semifields that is finitely based, there are continuum-
many equational theories of classes of ${\rm e}$-free reducts of idempotent
semifields, and the equational theory of the class of ${\rm e}$-free reducts
of idempotent semifields is co-NP-complete.

Finally, recall that idempotent semirings are also sometimes formulated in the
literature with both ${\rm e}$ and a constant symbol $0$ interpreted as the
neutral element of $\vee$. We show here that analogues of our Theorems A, B,
and C also hold in this setting, using similar methods to [1, Section 4]. Let
us call an algebraic structure $\langle{F,\vee,\cdot,{\rm e},0}\rangle$ an
idempotent $0$-semiring if $\langle{F,\vee,\cdot,{\rm e}}\rangle$ is an
idempotent semiring with least element $0$, and an _idempotent 0-semifield_
if, additionally, $\langle{F{\setminus}\\{0\\},\cdot,{\rm e}}\rangle$ is the
monoid reduct of a group. Clearly, if $\mathbf{F}=\langle{F,\vee,\cdot,{\rm
e},0}\rangle$ is an idempotent $0$-semifield, then
$\mathbf{F}^{*}:=\langle{F{\setminus}\\{0\\},\vee,\cdot,{\rm e}}\rangle$ is an
idempotent semifield. Conversely, given any idempotent semiring
$\mathbf{S}=\langle{S,\vee,\cdot,{\rm e}}\rangle$ and element $0\not\in S$,
the algebraic structure $\mathbf{S}_{0}:=\langle{S\cup\\{0\\},\vee,\cdot,{\rm
e},0}\rangle$ satisfying $0\leq a$ and $0\cdot a=a\cdot 0=0$ for all $a\in
S\cup\\{0\\}$, is an idempotent $0$-semiring. In particular, if $\mathbf{S}$
is an idempotent semifield, then $\mathbf{S}_{0}$ is an idempotent
$0$-semifield. Moreover, $(\mathbf{F}^{*})_{0}=\mathbf{F}$ for each idempotent
$0$-semifield $\mathbf{F}$, and $(\mathbf{S}_{0})^{*}=\mathbf{S}$ for each
idempotent semifield $\mathbf{S}$. Hence there is a one-to-one correspondence
between any class $\mathsf{K}$ of idempotent $0$-semifields and the class
$\mathsf{K}^{*}:=\\{\mathbf{F}^{*}\mid\mathbf{F}\in\mathsf{K}\\}$ of
idempotent semifields, and a one-to-one correspondence between any class
$\mathsf{K}$ of idempotent semifields and the class
$\mathsf{K}_{0}:=\\{\mathbf{S}_{0}\mid\mathbf{S}\in\mathsf{K}\\}$ of
idempotent $0$-semifields.

Let us call a simple ${\mathcal{L}}_{s}$-inequation $s\leq t_{1}\vee\cdots\vee
t_{n}$ _right-regular_ if every variable occurring in $t_{1},\dots,t_{n}$
occurs in $s$.

######  Lemma 5.1.

Let $\mathbf{S}$ be an idempotent semiring. Then a right-regular simple
${\mathcal{L}}_{s}$-inequation is satisfied by $\mathbf{S}$ if and only if it
is satisfied by $\mathbf{S}_{0}$.

######  Proof 5.2.

The right-to-left direction follows from the fact that $\mathbf{S}$ is a
subreduct of $\mathbf{S}_{0}$. For the left-to-right direction, it suffices to
observe that a right-regular simple ${\mathcal{L}}_{s}$-inequation is
satisfied by $\mathbf{S}_{0}$ under any assignment that maps one of the
variables occurring in it to $0$.

######  Lemma 5.3.

Let $\mathbf{S}$ be any non-trivial idempotent semifield. Then for any simple
${\mathcal{L}}_{s}$-inequation $\varepsilon=(s\leq t_{1}\vee\cdots\vee t_{n})$
satisfied by $\mathbf{S}$, there exists a subset
$\\{t_{i_{1}},\dots,t_{i_{k}}\\}\subseteq\\{t_{1},\dots,t_{n}\\}$ such that
the simple ${\mathcal{L}}_{s}$-inequation $s\leq t_{i_{1}}\vee\cdots\vee
t_{i_{k}}$ is right-regular and $\mathbf{S}\models s\leq
t_{i_{1}}\vee\cdots\vee t_{i_{k}}$.

######  Proof 5.4.

Note first that, since $\mathbf{S}$ is non-trivial, there cannot be a variable
$x$ that occurs in each of $t_{1},\dots,t_{n}$ but not in $s$; otherwise, we
could assign $x$ to some element $a<{\rm e}$ in $S$ and all other variables to
${\rm e}$ to arrive at a contradiction. Hence it suffices to prove that
(assuming a suitable permutation of $t_{1},\dots,t_{n}$) if a variable $x$
occurs in each of $t_{k+1},\dots,t_{n}$, but not in $s,t_{1},\dots,t_{k}$ for
some $k<n$, then $\mathbf{S}$ satisfies $s\leq t_{1}\vee\cdots\vee t_{k}$. In
this way we can inductively eliminate all the terms on the right that contain
a variable that does not occur in $s$ and obtain a right-regular simple
${\mathcal{L}}_{s}$-inequation. Suppose contrapositively that
$\mathbf{S}\not\models s\leq t_{1}\vee\cdots\vee t_{k}$, that is, there exists
a homomorphism $\varphi\colon\mathbf{Tm}({\mathcal{L}}_{s})\to\mathbf{S}$ such
that $\varphi(s)\not\leq\varphi(t_{1})\vee\cdots\vee\varphi(t_{k})$. Let
$\hat{\varphi}\colon\mathbf{Tm}({\mathcal{L}}_{s})\to\mathbf{S}$ be the
homomorphism defined by setting $\hat{\varphi}(y):=\varphi(y)$ for every
variable $y\neq x$ and $\hat{\varphi}(x)$ to be the meet of all the elements
of the form ${\rm
e}\wedge{\varphi(u)}^{-1}\wedge{\varphi(u)}^{-1}\varphi(t_{1}){\varphi(v)}^{-1}$
such that $u,v$ are subterms of $t_{k+1},\dots,t_{n}$ not containing $x$. Then
it is straightforward to check that
$\hat{\varphi}(t_{k+1})\vee\cdots\vee\hat{\varphi}(t_{n})\leq\varphi(t_{1})$,
so
$\hat{\varphi}(s)=\varphi(s)\not\leq\varphi(t_{1})\vee\cdots\vee\varphi(t_{k})=\hat{\varphi}(t_{1})\vee\cdots\vee\hat{\varphi}(t_{n})$,
and $\mathbf{S}\not\models s\leq t_{1}\vee\cdots\vee t_{n}$.

The equational theory of any non-empty class of idempotent $0$-semifields
containing exactly two elements has a finite basis consisting of the defining
equations for bounded distributive lattices with meet operation $\cdot$,
greatest element ${\rm e}$, and least element $0$. For convenience, let us
call a class of idempotent $0$-semifields non-Boolean if at least one of its
members has more than two elements. Clearly, a class $\mathsf{K}$ of
idempotent $0$-semifields is non-Boolean if and only if $\mathsf{K}^{*}$ is
non-trivial.

######  Corollary 5.5.

Every non-Boolean class of idempotent $0$-semifields is finitely based.

######  Proof 5.6.

Suppose towards a contradiction that $\mathsf{K}$ is a finitely based non-
Boolean class of idempotent $0$-semifields. First note that for every term $t$
in the signature of idempotent $0$-semirings, there exists a term $t^{\prime}$
that is either $0$ or an ${\mathcal{L}}_{s}$-term such that $t\approx
t^{\prime}$ is satisfied by all idempotent $0$-semirings that satisfy the
absorption laws $x\cdot 0\approx 0$ and $0\cdot x\approx 0$. Since idempotent
$0$-semifields satisfy the absorption laws, we may assume, by Lemma 5.3, that
$\mathrm{\Sigma}\cup\\{0\leq x,x\cdot 0\approx 0,0\cdot x\approx 0\\}$ is a
basis for ${\rm Eq}(\mathsf{K})$ for some finite set of right-regular simple
${\mathcal{L}}_{s}$-inequations $\mathrm{\Sigma}$. That is,
$\mathrm{\Sigma}\cup\\{0\leq x,x\cdot 0\approx 0,0\cdot x\approx
0\\}\subseteq{\rm Eq}(\mathsf{K})$ and ${\rm Eq}(\mathsf{K})$ is a logical
consequence of $\mathrm{\Sigma}\cup\\{0\leq x,x\cdot 0\approx 0,0\cdot
x\approx 0\\}$. We claim that $\mathrm{\Sigma}$ is a basis for ${\rm
Eq}(\mathsf{K}^{*})$, contradicting Theorem A. Observe first that
$\mathsf{K}\models\varepsilon$ if and only if
$\mathsf{K}^{*}\models\varepsilon$, for any right-regular simple
${\mathcal{L}}_{s}$-inequation $\varepsilon$, by Lemma 5.1, so
$\mathrm{\Sigma}\subseteq{\rm Eq}(\mathsf{K}^{*})\subseteq{\rm
Eq}(\mathsf{K})$. Now suppose that some idempotent semiring $\mathbf{A}$
satisfies $\mathrm{\Sigma}$. Then $\mathbf{A}_{0}$ satisfies
$\mathrm{\Sigma}$, by Lemma 5.1, and $\mathbf{A}_{0}$ therefore satisfies
${\rm Eq}(\mathsf{K}^{*})\subseteq{\rm Eq}(\mathsf{K})$. So $\mathbf{A}$
satisfies ${\rm Eq}(\mathsf{K}^{*})$. Hence ${\rm Eq}(\mathsf{K}^{*})$ is a
logical consequence of $\mathrm{\Sigma}$.

If $\mathsf{K}$ and $\mathsf{K^{\prime}}$ are classes of idempotent semifields
with distinct equational theories, then there is a simple
${\mathcal{L}}_{s}$-inequation that is satisfied by one and not the other, so
$\mathsf{K}_{0}$ and $\mathsf{K^{\prime}}_{0}$ also have distinct equational
theories, by Lemma 5.1 and Lemma 5.3. Hence, by Theorem B:

######  Corollary 5.7.

There are continuum-many equational theories of classes of idempotent
$0$-semifields.

Moreover, there is a linear time algorithm that given any term $t$ in the
signature of idempotent $0$-semifields produces a smaller term $t^{\prime}$
that is either $0$ or an ${\mathcal{L}}_{s}$-term, and satisfies $t\approx
t^{\prime}$ in all idempotent $0$-semifields, noting that idempotent
$0$-semifields satisfy $x\vee 0\approx x$, $x\cdot 0\approx 0$, and $0\cdot
x\approx 0$. Hence, using Lemma 5.1, Lemma 5.3, and Theorem C:

######  Corollary 5.8.

The equational theory of the class of idempotent $0$-semifields is co-NP-
complete.

## References

  * [1] L. Aceto, Z. Ésik, and A. Ingólfsdóttir.  Equational theories of tropical semirings.  Theor. Comput. Sci., 298(3):417–469, 2003.
  * [2] M.E. Anderson and T.H. Feil.  Lattice-Ordered Groups: An Introduction.  Springer, 1988.
  * [3] A. Colacito, N. Galatos, G. Metcalfe, and S. Santschi.  From distributive $\ell$-monoids to $\ell$-groups, and back again.  J. Algebra, 601:129–148, 2022.
  * [4] A. Colacito and G. Metcalfe.  Ordering groups and validity in lattice-ordered groups.  J. Pure Appl. Algebra, 223(12):5163–5175, 2019.
  * [5] N. Galatos and G. Metcalfe.  Proof theory for lattice-ordered groups.  Ann. Pure Appl. Logic, 8(167):707–724, 2016.
  * [6] J.S. Golan.  Semirings and their Applications.  Kluwer, 1999.
  * [7] W.C. Holland.  The largest proper variety of lattice-ordered groups.  Proc. Amer. Math. Soc., 57:25–28, 1976.
  * [8] H.B. Hunt III, D.J. Rosenkrantz, and P.A. Bloniarz.  On the computational complexity of algebra on lattices.  SIAM J. Comput., 16(1):129–148, 1987.
  * [9] M. Jackson.  Flat algebras and the translation of universal horn logic to equational logic.  J. Symbolic Logic, 73(1):90–128, 2008.
  * [10] M. Jackson, M. Ren, and X. Zhao.  Nonfinitely based ai-semirings with finitely based semigroup reducts.  J. Algebra, 611:211–245, 2022.
  * [11] V.M. Kopytov and N.Y. Medvedev.  Varieties of lattice-ordered groups.  Algebra and Logic, 16:281–285, 1977.
  * [12] S. McCleary.  The word problem in free normal valued lattice-ordered groups: a solution and practical shortcuts.  Algebra Universalis, 14:317–348, 1982.
  * [13] G. Metcalfe, F. Paoli, and C. Tsinakis.  Residuated Structures in Algebra and Logic, volume 277 of Mathematical Surveys and Monographs.  American Mathematical Society, 2023.
  * [14] V. B. Repnitskiĭ.  Bases of identities of varieties of lattice-ordered semigroups.  Algebra i Logika, 22(6):649–665, 720, 1983.
  * [15] J.J. Rotman.  An Introduction to the Theory of Groups, volume 148 of Graduate Texts in Mathematics.  Springer, 4 edition, 1994.
  * [16] V. Weispfenning.  The complexity of the word problem for Abelian $l$-groups.  Theor. Comput. Sci., 48:127–132, 1986.

G. Metcalfe and S. Santschi
Mathematical Institute, University of Bern, Sidlerstrasse 5, 3012 Bern
Switzerland