1 Introduction
Tropical algebraic geometry is a piecewise linear shadow of algebraic geometry, in which varieties are replaced by polyhedral complexes. This area has grown significantly in the past decade and has had great success in numerous applications, such as Mikhalkin’s calculation of Gromov–Witten invariants of
$\mathbb{P}^{2}$
[Reference MikhalkinMik05], the work of Cools et al. [Reference Cools, Draisma, Payne and RobevaCDPR12] and Jensen and Payne [Reference Jensen and PayneJP14, Reference Jensen and PayneJP16] on Brill–Noether theory, and the Gross–Siebert program in mirror symmetry [Reference GrossGro11].
One current limitation of the theory, however, is that most techniques developed to date are focused on tropical varieties and tropical cycles, as opposed to schemes or more general spaces. Many of the standard tools of modern algebraic geometry thus do not yet have a tropical counterpart.
In [Reference Giansiracusa and GiansiracusaGG16], Jeffrey and Noah Giansiracusa described how to tropicalize a subscheme of a toric variety using congruences on the semiring of tropical polynomials. The authors of the present paper developed this further in [Reference Maclagan and RincónMR14], clarifying the connection to tropical linear spaces and valuated matroids.
Building on this work, in this paper we investigate a special class of ideals in the semiring of tropical polynomials, called tropical ideals, in which bounded-degree pieces are ‘matroidal’. This allows us to define tropical subschemes of a tropical toric variety, which include, but are not limited to, tropicalizations of classical subschemes of toric varieties. We show that, unlike for more general ideals, varieties of tropical ideals are always finite polyhedral complexes. In addition, even though the semiring of tropical polynomials is far from Noetherian, the restricted class of tropical ideals satisfies the ascending chain condition. They also satisfy a version of the Nullstellensatz that is completely analogous to the classical formulation.
We denote by
$\overline{\mathbb{R}}$
the tropical semiring
$\mathbb{R}\cup \{\infty \}$
with the operations tropical sum
$\oplus =\min$
and tropical multiplication
$\odot =+$
. The semiring of tropical polynomials
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
consists of polynomials with coefficients in
$\overline{\mathbb{R}}$
where all operations are tropical. For simplicity, in this introduction we describe our results in the case where the ambient toric variety is tropical affine space. A general treatment for any tropical toric variety is given in § 4.
Definition 1.1. An ideal
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a tropical ideal if for each degree
$d\geqslant 0$
the set
$I_{{\leqslant}d}$
of polynomials in
$I$
of degree at most
$d$
is a tropical linear space, or equivalently
$I_{{\leqslant}d}$
is the set of vectors of a valuated matroid. More concretely,
$I$
is a tropical ideal if it satisfies the following ‘monomial elimination axiom’:
Here we use the notation
$[f]_{\mathbf{x}^{\mathbf{u}}}$
to denote the coefficient of the monomial
$\mathbf{x}^{\mathbf{u}}$
in the tropical polynomial
$f$
.
If
$J\subseteq K[x_{1},\ldots ,x_{n}]$
is an ideal, then its tropicalization
$\operatorname{trop}(J)\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a tropical ideal. However, the class of tropical ideals is larger; we exhibit in Example 2.8 a tropical ideal that cannot be realized as
$\operatorname{trop}(J)$
for any ideal
$J\subseteq K[x_{1},\ldots ,x_{n}]$
over any field
$K$
.
As we describe below, the ‘monomial elimination axiom’ required for tropical ideals makes up for the lack of subtraction in the tropical semiring, and gives tropical ideals a rich algebraic structure reminiscent of ideals in a polynomial ring. In particular, tropical ideals seem to be better suited than general ideals of
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
for studying the underlying geometry; see Remark 4.12.
Given a polynomial
$f\in \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, its associated variety is
$$\begin{eqnarray}V(f):=\{\mathbf{w}\in \overline{\mathbb{R}}^{n}:f(\mathbf{w})=\infty \text{or the minimum in }f(\mathbf{w})\text{ is achieved at least twice}\}.\end{eqnarray}$$
If
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is an ideal, the variety of
$I$
is
$$\begin{eqnarray}V(I):=\mathop{\bigcap }_{f\in I}V(f).\end{eqnarray}$$
If
$I$
is an arbitrary ideal in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, then
$V(I)$
can be a fairly arbitrary subset of
$\overline{\mathbb{R}}^{n}$
; see Example 5.14. In particular,
$V(I)$
might not even be polyhedral. However, if
$I$
is a tropical ideal, our main result shows that this is not the case.
Theorem 1.2. If
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a tropical ideal, then the variety
$V(I)\subseteq \overline{\mathbb{R}}^{n}$
is a finite polyhedral complex.
Our proof of Theorem 1.2 generalizes the case where
$I=\operatorname{trop}(J)$
for a classical ideal
$J$
: we develop a Gröbner theory for tropical ideals, and show that any tropical ideal has a finite Gröbner complex, as in [Reference Maclagan and SturmfelsMS15, §2.5]. The variety of
$I$
is then a subcomplex of its Gröbner complex.
A tropical basis for a tropical ideal
$I$
is a collection of polynomials in
$I$
the intersection of whose varieties is the variety
$V(I)$
. It is well known that a tropical ideal of the form
$\operatorname{trop}(J)$
always admits a finite tropical basis; we show in Theorem 5.9 that this is in fact true for any tropical ideal.
We also investigate commutative algebraic properties of tropical ideals. The fact that tropical ideals are ‘matroidal’ allows us to naturally define the Hilbert function of any homogeneous tropical ideal. In the case where
$I=\operatorname{trop}(J)$
for a classical ideal
$J$
, the Hilbert function of
$I$
agrees with the Hilbert function of
$J$
. In Proposition 3.8 we show that, just as in the classical case, the Hilbert function of any homogeneous tropical ideal is eventually polynomial.
The semiring
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is not Noetherian, and tropical ideals are almost never finitely generated; see Example 3.10. Moreover, Example 3.12 shows an infinite family of distinct homogeneous tropical ideals
$\{I^{j}\}_{j\geqslant 1}$
, all of which have the same Hilbert function, such that for any
$d\geqslant 0$
, if
$k,l\geqslant d$
, then the tropical ideals
$I^{k}$
and
$I^{l}$
agree on all their graded pieces of degree at most
$d$
. Nonetheless, tropical ideals do satisfy the following Noetherian property.
Theorem 1.3 (Ascending chain condition).
There is no infinite ascending chain
$I_{1}\subsetneq I_{2}\subsetneq I_{3}\subsetneq \cdots \,$
of tropical ideals in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
.
There are several versions of the Nullstellensatz for tropical geometry in the literature; see for example [Reference Shustin and IzhakianSI07, Reference Bertram and EastonBE17, Reference Joó and MinchevaJM17, Reference Grigoriev and PodolskiiGP14]. Most of these concern arbitrary finitely generated ideals in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
. In our case, the rich structure we impose on tropical ideals allows us to use the results in [Reference Grigoriev and PodolskiiGP14] to get the following familiar formulation.
Theorem 1.4 (Tropical Nullstellensatz).
If
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a tropical ideal, then the variety
$V(I)\subseteq \overline{\mathbb{R}}^{n}$
is empty if and only if
$I$
is the unit ideal
$\langle 0\rangle$
.
Several of our results for tropical ideals imply the analogous versions for classical ideals, simply by considering tropical ideals of the form
$\operatorname{trop}(J)$
for
$J\subseteq K[x_{1},\ldots ,x_{n}]$
. Since our arguments for tropical ideals are all of combinatorial nature, our approach has the appealing feature of providing completely combinatorial proofs for some important well-known statements, such as the existence of Gröbner complexes for classical homogeneous ideals and the existence of finite tropical bases for classical ideals. This suggests that more of standard commutative algebra can be tropicalized and extended in this manner.
We conclude with a brief description of how the paper is organized. The basics of valuated matroids and tropical ideals are explained in § 2. Some Gröbner theory for tropical ideals is developed in § 3, together with a discussion on Hilbert functions and a proof of Theorem 1.3 (Theorem 3.11). Tropical subschemes of tropical toric varieties are introduced in § 4. Finally, in § 5 we prove Theorem 1.2 (Theorem 5.11), as well as the existence of finite tropical bases (Theorem 5.9) and Theorem 1.4 (Theorem 5.16).
2 Tropical ideals
In this section we introduce tropical ideals, together with several examples. We first recall some basics of valuated matroids.
Throughout this paper we take
$(R,\oplus ,\odot )$
to be a semifield, with the following extra properties. For compatibility with tropical notation we write
$\infty$
for the additive identity of
$R$
, and
$R^{\ast }$
for
$R\setminus \{\infty \}$
. We require that
$(R^{\ast },\odot )$
is a totally ordered group, and that the addition
$\oplus$
satisfies
$a\oplus b=\min (a,b)$
. Under these hypotheses,
$R$
is sometimes called a valuative semifield. We extend the total ordering on the multiplicative group to all of
$R$
by making
$\infty$
the largest element.
The main example for us will be the tropical semiring (or min-plus algebra)
$\overline{\mathbb{R}}$
:
$$\begin{eqnarray}\overline{\mathbb{R}}:=(\mathbb{R}\cup \{\infty \},\oplus ,\odot )\quad \text{where }\oplus :=\min \text{ and }\odot :=+.\end{eqnarray}$$
Here the ordering on the multiplicative group
$\mathbb{R}$
is the standard one. Another important example is the Boolean subsemiring
$\mathbb{B}$
of
$\overline{\mathbb{R}}$
:
$$\begin{eqnarray}\mathbb{B}:=(\{0,\infty \},\oplus ,\odot ).\end{eqnarray}$$
An ideal in a semiring
$R$
is a nonempty subset of
$R$
closed under addition and under multiplication by elements of
$R$
.
We denote by
$R[x_{0},\ldots ,x_{n}]$
the semiring of polynomials in the variables
$x_{0},\ldots ,x_{n}$
with coefficients in
$R$
. Note that in the case that
$R=\overline{\mathbb{R}}$
, elements of
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
are regarded as polynomials and not functions; for example, the polynomials
$f(x)=x^{2}\,\oplus \,0$
and
$g(x)=x^{2}\,\oplus \,1\odot x\,\oplus \,0$
are distinct, even though
$f(w)=g(w)$
for all
$w\in \mathbb{R}$
. The support of a polynomial
$f=\bigoplus a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}$
is
$$\begin{eqnarray}\operatorname{supp}(f):=\{\mathbf{u}\in \mathbb{N}^{n+1}:a_{\boldsymbol{ u}}\neq \infty \}.\end{eqnarray}$$
We call
$a_{\mathbf{u}}$
the coefficient in
$f$
of the monomial
$\mathbf{x}^{\mathbf{u}}$
.
2.1 Valuated matroids
Valuated matroids are a generalization of the notion of matroids, introduced by Dress and Wenzel in [Reference Dress and WenzelDW92]. We recall some of the necessary background on valuated matroids and tropical linear spaces; for basics of standard matroids, see, for example, [Reference OxleyOxl92].
Let
$E$
be a finite set, and let
$r\in \mathbb{N}$
. Denote by
$\binom{E}{r}$
the collection of subsets of
$E$
of size
$r$
. A valuated matroid on the ground set
$E$
with values in the semifield
$R$
is a pair
${\mathcal{M}}=(E,p)$
where
$p:\binom{E}{r}\rightarrow R$
satisfies the following properties.
-
– There exists
$B\in \binom{E}{r}$
such that
$p(B)\neq \infty$
. -
– Valuated basis exchange axiom: for every
$A,B\in \binom{E}{r}$
and every
$a\in A\setminus B$
there exists
$b\in B\setminus A$
with (2)
$$\begin{eqnarray}p(A)\odot p(B)\geqslant p(A\cup b-a)\odot p(B\cup a-b).\end{eqnarray}$$
In the case that
$R=\overline{\mathbb{R}}$
, the valuated basis exchange axiom is equivalent to the tropical Plücker relations; see, for instance, [Reference Maclagan and SturmfelsMS15, §4.4]. If
${\mathcal{M}}=(E,p)$
is a valuated matroid, its support
$\{B\in \binom{E}{r}:p(B)\neq \infty \}$
is the collection of bases of a rank-
$r$
matroid on the ground set
$E$
, called the underlying matroid
$\text{}\underline{{\mathcal{M}}}$
of
${\mathcal{M}}$
. The function
$p$
is called the basis valuation function of
${\mathcal{M}}$
. We consider the basis valuation functions
$p$
and
$\unicode[STIX]{x1D706}\odot p$
with
$\unicode[STIX]{x1D706}\in R^{\ast }$
to be the same valuated matroid.
As for ordinary matroids, valuated matroids have several different ‘cryptomorphic’ definitions, some of which we now recall. For more information, see [Reference Murota and TamuraMT01].
Let
${\mathcal{M}}$
be a valuated matroid on the ground set
$E$
with basis valuation function
$p:\binom{E}{r}\rightarrow R$
. Given a basis
$B$
of
$\text{}\underline{{\mathcal{M}}}$
and an element
$e\in E\setminus B$
, the (valuated) fundamental circuit
$H(B,e)$
of
${\mathcal{M}}$
is the element of the
$R$
-semimodule
$R^{E}$
whose coordinates are given by
$$\begin{eqnarray}H(B,e)_{e^{\prime }}:=p(B\cup e-e^{\prime })/p(B)\quad \text{for any }e^{\prime }\in E,\end{eqnarray}$$
where
$/$
denotes division in the semifield
$R$
(subtraction in the case of
$\overline{\mathbb{R}}$
),
$p(B^{\prime })=\infty$
if
$|B^{\prime }|>r$
, and
$\infty /\unicode[STIX]{x1D706}=\infty$
for any
$\unicode[STIX]{x1D706}\in R^{\ast }$
. A (valuated) circuit of
${\mathcal{M}}$
is any vector in
$R^{E}$
of the form
$\unicode[STIX]{x1D706}\odot H(B,e)$
, where
$B$
is a basis of
$\text{}\underline{{\mathcal{M}}}$
,
$e\in E\setminus B$
, and
$\unicode[STIX]{x1D706}\in R^{\ast }$
. We denote by
${\mathcal{C}}({\mathcal{M}})$
the collection of all circuits of
${\mathcal{M}}$
. For any
$H\in R^{E}$
, its support is defined as
$$\begin{eqnarray}\operatorname{supp}(H):=\{e\in E:H_{e}\neq \infty \}.\end{eqnarray}$$
The set of supports of the circuits of
${\mathcal{M}}$
is equal to the set of circuits of the underlying matroid
$\text{}\underline{{\mathcal{M}}}$
. Furthermore, if two circuits
$G$
and
$H$
of
${\mathcal{M}}$
have the same support, then there exists
$\unicode[STIX]{x1D706}\in R^{\ast }$
such that
$G=\unicode[STIX]{x1D706}\odot H$
[Reference Murota and TamuraMT01, Theorem 3.1(VC
$3_{e}$
)].
Collections of circuits of valuated matroids can be intrinsically characterized by axioms that generalize the classical circuit axioms for matroids; see [Reference Murota and TamuraMT01, Theorem 3.1]. The most important one is the following elimination property.
-
– Circuit elimination axiom: For any
$G,H\in {\mathcal{C}}({\mathcal{M}})$
and any
$e,e^{\prime }\in E$
such that
$G_{e}=H_{e}\neq \infty$
and
$G_{e^{\prime }}<H_{e^{\prime }}$
, there exists
$F\in {\mathcal{C}}({\mathcal{M}})$
satisfying
$F_{e}=\infty$
,
$F_{e^{\prime }}=G_{e^{\prime }}$
, and
$F\geqslant G\oplus H$
.
Here
$F\geqslant F^{\prime }$
if
$F_{e}\geqslant F_{e}^{\prime }$
for all
$e$
, and
$(G\oplus H)_{e}=G_{e}\oplus H_{e}$
.
We also use the vector formulation for valuated matroids, which generalizes the notion of cycles for matroids. A cycle of a matroid is a union of circuits. A vector of a valuated matroid is an element of the subsemimodule of
$R^{E}$
generated by the valuated circuits. More explicitly, the set of vectors of
${\mathcal{M}}$
is
$$\begin{eqnarray}{\mathcal{V}}({\mathcal{M}}):=\biggl\{\bigoplus _{H\in {\mathcal{C}}({\mathcal{M}})}\,\unicode[STIX]{x1D706}_{H}\odot H:\unicode[STIX]{x1D706}_{H}\in R\text{ for all }H\biggr\}.\end{eqnarray}$$
Vectors of a valuated matroid can also be characterized by axioms; see [Reference Murota and TamuraMT01, Theorem 3.4]. In fact, a subset
${\mathcal{V}}\subseteq R^{E}$
is the set of vectors of a valuated matroid if and only if it is a subsemimodule of
$R^{E}$
satisfying the following property.
-
– Vector elimination axiom: For any
$G,H\in {\mathcal{V}}$
and any
$e\in E$
such that
$G_{e}=H_{e}\neq \infty$
, there exists
$F\in {\mathcal{V}}$
satisfying
$F_{e}=\infty$
,
$F\geqslant G\oplus H$
, and
$F_{e^{\prime }}=G_{e^{\prime }}\oplus H_{e^{\prime }}$
for all
$e^{\prime }\in E$
such that
$G_{e^{\prime }}\neq H_{e^{\prime }}$
.
In the case that
$R=\mathbb{B}$
, valuated matroids are simply matroids, as there is no additional information encoded in the valuation. In this case, valuated circuits and vectors are in one-to-one correspondence with circuits and cycles, respectively, of the underlying matroid
$\text{}\underline{{\mathcal{M}}}$
.
In the case that
$R=\overline{\mathbb{R}}$
, the set of vectors of a valuated matroid is also called a tropical linear space in the tropical literature. In the terminology used in [Reference Maclagan and SturmfelsMS15, §4.4], if
$p$
is the basis valuation function of a rank-
$r$
valuated matroid
${\mathcal{M}}$
, then
${\mathcal{V}}({\mathcal{M}})$
is the tropical linear space
$L_{p^{\bot }}$
, where
$p^{\bot }$
is the dual tropical Plücker vector given by
$p^{\bot }(B):=p(E\setminus B)$
.
2.2 Tropical ideals
We now introduce the main object of study of this paper. Let
$\operatorname{Mon}_{d}$
be the set of monomials of degree
$d$
in the variables
$x_{0},\ldots ,x_{n}$
. We will identify elements of
$R^{\operatorname{Mon}_{d}}$
with homogeneous polynomials of degree
$d$
in
$R[x_{0},\ldots ,x_{n}]$
. In this way, if
${\mathcal{M}}$
is a valuated matroid on the ground set
$\operatorname{Mon}_{d}$
, circuits and vectors of
${\mathcal{M}}$
can be thought of as homogeneous polynomials in
$R[x_{0},\ldots ,x_{n}]$
of degree
$d$
.
Definition 2.1 (Homogeneous tropical ideals).
A homogeneous tropical ideal is a homogeneous ideal
$I\subseteq R[x_{0},\ldots ,x_{n}]$
such that for each
$d\geqslant 0$
the degree-
$d$
part
$I_{d}$
is the collection of vectors of a valuated matroid
${\mathcal{M}}_{d}$
on
$\operatorname{Mon}_{d}$
. If
$I\subseteq R[x_{0},\ldots ,x_{n}]$
is a homogeneous tropical ideal, we will denote by
${\mathcal{M}}_{d}(I)$
the valuated matroid such that
$I_{d}={\mathcal{V}}({\mathcal{M}}_{d}(I))$
.
This definition is consistent with Definition 1.1 in the introduction, in view of the characterization of vectors of a valuated matroid in terms of the vector elimination axiom.
Not all homogeneous ideals in
$R[x_{0},\ldots ,x_{n}]$
are tropical ideals. As an example, consider the ideal
$I$
in
$\overline{\mathbb{R}}[x,y]$
generated by
$x\oplus y$
. The degree-2 part of this ideal is the
$\overline{\mathbb{R}}$
-semimodule generated by
$x^{2}\oplus xy$
and
$xy\oplus y^{2}$
. This is not the set of vectors of a valuated matroid on
$\operatorname{Mon}_{2}=\{x^{2},xy,y^{2}\}$
, as the polynomial
$x^{2}\oplus y^{2}$
would be required to be in
$I$
by the vector elimination axiom applied to the two generators.
Homogeneous tropical ideals in the sense of Definition 2.1 will define subschemes of tropical projective space. We elaborate on this definition with some examples.
Example 2.2 (Realizable tropical ideals).
Let
$K$
be a field equipped with a valuation
$\operatorname{val}:K\,\rightarrow \,R$
. Any polynomial
$g\in K[x_{0},\ldots ,x_{n}]$
gives rise to a ‘tropical’ polynomial
$\operatorname{trop}(g)\in R[x_{0},\ldots ,x_{n}]$
by interpreting all operations tropically and replacing coefficients by their valuations: if
$g=\sum c_{\mathbf{u}}\cdot \mathbf{x}^{\mathbf{u}}$
, then
$\operatorname{trop}(g):=\bigoplus \operatorname{val}(c_{\mathbf{u}})\odot \mathbf{x}^{\mathbf{u}}$
. For any ideal
$J\subseteq K[x_{0},\ldots ,x_{n}]$
, its tropicalization is the ideal
$$\begin{eqnarray}\operatorname{trop}(J):=\langle \operatorname{trop}(g):g\in J\rangle \subseteq R[x_{0},\ldots ,x_{n}].\end{eqnarray}$$
If
$f$
is a polynomial of minimal support in
$\operatorname{trop}(J)$
, there exists
$g\in J$
and
$\unicode[STIX]{x1D706}\in R^{\ast }$
such that
$f=\unicode[STIX]{x1D706}\odot \operatorname{trop}(g)$
. Indeed, if
$f=\sum \unicode[STIX]{x1D706}_{i}\odot \mathbf{x}^{\mathbf{u}_{i}}\odot \operatorname{trop}(g_{i})$
with
$g_{i}\in J$
for all
$i$
, then
$f=\sum \unicode[STIX]{x1D706}_{i}\odot \operatorname{trop}(\mathbf{x}^{\mathbf{u}_{i}}g_{i})$
. Since there is no cancelation in
$R$
, we have
$\operatorname{supp}(\mathbf{x}^{\mathbf{u}_{i}}g_{i})\subseteq \operatorname{supp}(f)$
for all
$i$
, and thus
$\operatorname{supp}(\mathbf{x}^{\mathbf{u}_{i}}g_{i})=\operatorname{supp}(f)$
for all
$i$
. As all the
$\mathbf{x}^{\mathbf{u}_{i}}g_{i}$
are of minimal support in
$J$
, this implies that all of them are scalar multiples of each other, and thus
$f=\unicode[STIX]{x1D706}\odot \operatorname{trop}(g)$
for some
$g\in J$
.
It follows that if
$J\subseteq K[x_{0},\ldots ,x_{n}]$
is a homogeneous ideal, for any
$d\geqslant 0$
the degree-
$d$
polynomials in
$\operatorname{trop}(J)$
of minimal support satisfy the circuit elimination axiom of valuated matroids. The other circuit axioms are immediate, so
$\operatorname{trop}(J)$
is a homogeneous tropical ideal. A tropical ideal arising in this way is called realizable (over the field
$K$
).
Remark 2.3. If
$J\subseteq K[x_{0},\ldots ,x_{n}]$
is a homogeneous ideal, the degree-
$d$
part
$\operatorname{trop}(J)_{d}$
of the homogeneous tropical ideal
$\operatorname{trop}(J)$
is the
$R$
-semimodule generated by the polynomials
$\operatorname{trop}(g)$
with
$g\in J_{d}$
. Moreover, if the residue field of
$K$
is infinite, then every polynomial in
$\operatorname{trop}(J)_{d}$
is a scalar multiple of some
$\operatorname{trop}(g)$
with
$g\in J_{d}$
, as
$\operatorname{trop}(g)\oplus \operatorname{trop}(h)=\operatorname{trop}(g+\unicode[STIX]{x1D6FC}h)$
for a sufficiently general
$\unicode[STIX]{x1D6FC}\in K$
with
$\operatorname{val}(\unicode[STIX]{x1D6FC})=0$
. If, in addition, the value group
$\unicode[STIX]{x1D6E4}:=\operatorname{im}\operatorname{val}$
of
$K$
equals all of
$R$
, then every polynomial in
$\operatorname{trop}(J)_{d}$
is of the form
$\operatorname{trop}(g)$
for
$g\in J_{d}$
.
When the residue field is finite, however, it is possible for the underlying matroid
$\text{}\underline{{\mathcal{M}}_{d}(\operatorname{trop}(J))}$
to have some cycles that are not the support of any polynomial in
$J$
. For example, consider
$K=\mathbb{Z}/2\mathbb{Z}$
equipped with the trivial valuation
$\operatorname{val}:K\rightarrow \mathbb{B}$
, and the ideal
$J:=\langle x+y\rangle \subseteq K[x,y]$
. In this case there is no polynomial in
$J_{2}$
having support
$D:=\{x^{2},xy,y^{2}\}$
, even though the tropical polynomial
$x^{2}\oplus xy\oplus y^{2}$
is in
$\operatorname{trop}(J)_{2}$
and
$D$
is a cycle of
$\text{}\underline{{\mathcal{M}}_{2}(\operatorname{trop}(J))}$
.
A special class of realizable homogeneous tropical ideals consists of the tropical equivalent of the homogeneous ideal of a point in projective space.
Example 2.4 (Homogeneous tropical ideal of a point).
Fix
$\mathbf{a}=(a_{0},a_{1},\ldots ,a_{n})\in \operatorname{trop}(\mathbb{P}^{n})=(\overline{\mathbb{R}}^{n+1}\setminus \{(\infty ,\ldots ,\infty )\})/\mathbb{R}(1,\ldots ,1)$
. Let
$I_{\mathbf{a}}$
be the ideal generated by all homogeneous polynomials
$f\in \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
for which
$\mathbf{a}\in V(f)$
, so
$f(\mathbf{a})=\infty$
or the minimum in
$f(\mathbf{a})$
is achieved at least twice. We claim that
$I_{\mathbf{a}}$
is a tropical ideal. In addition, if
$K$
is a valued field with
$a_{i}$
in the image of the valuation for each
$0\leqslant i\leqslant n$
, then
$I_{\mathbf{a}}$
is the tropicalization of any ideal
$J_{\unicode[STIX]{x1D6FC}}$
of a point
$\unicode[STIX]{x1D6FC}\in \mathbb{P}_{K}^{n}$
with
$\operatorname{val}(\unicode[STIX]{x1D6FC}_{i})=a_{i}$
.
To prove the first claim, we first note that
$I_{\mathbf{a}}$
is generated as an
$\overline{\mathbb{R}}$
-semimodule by the set
${\mathcal{P}}$
of polynomials of the form
$(\mathbf{a}\cdot \mathbf{v})\odot \mathbf{x}^{\mathbf{u}}\oplus (\mathbf{a}\cdot \mathbf{u})\odot \mathbf{x}^{\mathbf{v}}$
with
$\deg (\mathbf{x}^{\mathbf{u}})=\deg (\mathbf{x}^{\mathbf{v}})$
and
$\mathbf{u}\neq \mathbf{v}$
, where by convention we take
$\infty$
times
$0$
equal to
$0$
when some of the
$a_{i}$
are equal to
$\infty$
. Indeed, all these binomials (and monomials, in the case some of the
$a_{i}$
equal
$\infty$
) are contained in
$I_{\mathbf{a}}$
. Suppose that
$f=\bigoplus c_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}\in I_{\mathbf{a}}$
is outside the ideal generated by
${\mathcal{P}}$
. We may assume that
$f$
has been chosen to have as few terms as possible. We may also assume that
$f(\mathbf{a})<\infty$
, as otherwise all terms of
$f$
lie in the ideal generated by
${\mathcal{P}}$
. Fix
$c_{\mathbf{v}}\odot \mathbf{x}^{\mathbf{v}}$
to be a term of
$f$
such that
$c_{\mathbf{v}}+\mathbf{a}\cdot \mathbf{v}>f(\mathbf{a})$
if one exists, or any term of
$f$
otherwise. Take
$\mathbf{v}^{\prime }\neq \mathbf{v}$
with
$c_{\mathbf{v}^{\prime }}+\mathbf{a}\cdot \mathbf{v}^{\prime }=f(\mathbf{a})$
, and set
$g=\bigoplus _{\mathbf{u}\neq \mathbf{v}}c_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}$
. Then
$f=g\oplus (c_{\mathbf{v}}-\mathbf{a}\cdot \mathbf{v}^{\prime })\odot ((\mathbf{a}\cdot \mathbf{v}^{\prime })\odot \mathbf{x}^{\mathbf{v}}\oplus (\mathbf{a}\cdot \mathbf{v})\odot \mathbf{x}^{\mathbf{v}^{\prime }})$
. In the case that the minimum in
$f(\mathbf{a})$
is not achieved at
$\mathbf{x}^{\mathbf{v}}$
, the minimum in
$g(\mathbf{a})$
is still achieved at least twice. If the minimum in
$f(\mathbf{a})$
is achieved at all its terms,
$f$
must have at least three terms, as otherwise it would be a scalar multiple of one of the polynomials in
${\mathcal{P}}$
. The minimum in
$g(\mathbf{a})$
is thus still achieved twice. Furthermore,
$g$
has fewer terms than
$f$
, so by assumption
$g$
lies in the
$\overline{\mathbb{R}}$
-semimodule generated by
${\mathcal{P}}$
, and thus so does
$f$
. This proves that
$I_{\mathbf{a}}$
is generated by
${\mathcal{P}}$
. In addition, the degree-
$d$
polynomials of minimal support in
${\mathcal{P}}$
satisfy the valuated circuit elimination axiom, which implies that
$(I_{\mathbf{a}})_{d}$
is the set of vectors of a valuated matroid [Reference Murota and TamuraMT01, Theorem 3.4], and thus
$I_{\mathbf{a}}$
is a tropical ideal.
Suppose now that
$\unicode[STIX]{x1D6FC}\in \mathbb{P}_{K}^{n}$
satisfies
$\operatorname{val}(\unicode[STIX]{x1D6FC})=\mathbf{a}$
. The homogeneous ideal
$J_{\unicode[STIX]{x1D6FC}}\subseteq K[x_{0},\ldots ,x_{n}]$
of the point
$\unicode[STIX]{x1D6FC}$
contains the binomials
$\unicode[STIX]{x1D6FC}^{\mathbf{v}}\mathbf{x}^{\mathbf{u}}-\unicode[STIX]{x1D6FC}^{\mathbf{u}}\mathbf{x}^{\mathbf{v}}$
for all pairs
$\mathbf{x}^{\mathbf{u}},\mathbf{x}^{\mathbf{v}}$
with
$\deg (\mathbf{x}^{\mathbf{u}})=\deg (\mathbf{x}^{\mathbf{v}})$
, so
$I_{\mathbf{a}}\subseteq \operatorname{trop}(J_{\unicode[STIX]{x1D6FC}})$
. If the inclusion were proper, there would be
$h\in \operatorname{trop}(J_{\unicode[STIX]{x1D6FC}})$
with
$h\notin I_{\mathbf{a}}$
. Write
$h=\sum h_{i}\odot \operatorname{trop}(g_{i})$
, where
$g_{i}\in J_{\unicode[STIX]{x1D6FC}}$
. Since
$\mathbf{a}=\operatorname{val}(\unicode[STIX]{x1D6FC})\in \operatorname{trop}(V(g_{i}))=V(\operatorname{trop}(g_{i}))$
, this contradicts that
$\mathbf{a}\not \in V(h)$
.
One can think of a homogeneous tropical ideal as the ‘tower’ of valuated matroids that determine its various homogeneous parts, as described in the following definition.
Definition 2.5 (Compatible valuated matroids).
Let
${\mathcal{S}}=({\mathcal{M}}_{d})_{d\geqslant 0}$
be a sequence of valuated matroids with values in the semiring
$R$
, where the ground set of
${\mathcal{M}}_{d}$
is the set of monomials
$\operatorname{Mon}_{d}$
. The sequence
${\mathcal{S}}$
is called a compatible sequence if the
$R$
-subsemimodule
$I$
of
$R[x_{0},\ldots ,x_{n}]$
generated by
$\{{\mathcal{V}}({\mathcal{M}}_{d}):d\geqslant 0\}$
is a homogeneous ideal. In other words,
${\mathcal{S}}$
is compatible if for any
$d\geqslant 0$
and any variable
$x_{i}$
we have
$$\begin{eqnarray}x_{i}\odot {\mathcal{V}}({\mathcal{M}}_{d}):=\{x_{i}\odot H:H\in {\mathcal{V}}({\mathcal{M}}_{d})\}\subseteq {\mathcal{V}}({\mathcal{M}}_{d+1}),\end{eqnarray}$$
or equivalently for any circuit
$G\in {\mathcal{C}}({\mathcal{M}}_{d})$
we have that
$x_{i}\odot G$
is a sum of circuits of
${\mathcal{M}}_{d+1}$
.
Compatibility of valuated matroids can be simply described in terms of their basis valuation functions.
Proposition 2.6 (Compatibility in terms of basis valuations).
Let
${\mathcal{S}}=({\mathcal{M}}_{d})_{d\geqslant 0}$
be a sequence of valuated matroids, where
${\mathcal{M}}_{d}=(\operatorname{Mon}_{d},p_{d})$
has rank
$r_{d}$
. The sequence
${\mathcal{S}}$
is a compatible sequence if and only if for any
$d\geqslant 0$
, any variable
$x_{i}$
, any
$U\subseteq \operatorname{Mon}_{d}$
of size
$r_{d}+1$
, and any
$V\subseteq \operatorname{Mon}_{d+1}$
of size
$r_{d+1}-1$
, we have that
$$\begin{eqnarray}\min _{\mathbf{x}^{\mathbf{u}}\in x_{i}U\setminus V}p_{d}(U-\mathbf{x}^{\mathbf{u}}/x_{i})\odot p_{d+1}(V\cup \mathbf{x}^{\mathbf{u}})\text{ is attained at least twice}.\end{eqnarray}$$
Proof. For any
$d\geqslant 0$
and any variable
$x_{i}$
, the set
$x_{i}\odot {\mathcal{V}}({\mathcal{M}}_{d})$
is the collection of vectors of a valuated matroid on the ground set
$\operatorname{Mon}_{d+1}$
. Indeed, if we let
$\operatorname{Mon}_{d}^{\hat{i} }$
be the set of monomials in
$\operatorname{Mon}_{d+1}$
not divisible by
$x_{i}$
, the collection
$x_{i}\odot {\mathcal{V}}({\mathcal{M}}_{d})$
is the set of vectors of the valuated matroid
${\mathcal{M}}_{d,i}$
on
$\operatorname{Mon}_{d+1}$
with basis valuation function
$$\begin{eqnarray}p_{d,i}(B)=\left\{\begin{array}{@{}ll@{}}p_{d}((B\setminus \operatorname{Mon}_{d}^{\hat{i} })/x_{i})\quad & \text{if }B\supseteq \operatorname{Mon}_{d}^{\hat{i} },\\ \infty \quad & \text{otherwise.}\end{array}\right.\end{eqnarray}$$
The sequence
${\mathcal{S}}$
is compatible if and only if, for every
$d\geqslant 0$
and any variable
$x_{i}$
, there is a containment of tropical linear spaces
${\mathcal{V}}({\mathcal{M}}_{d,i})\subseteq {\mathcal{V}}({\mathcal{M}}_{d+1})$
, or dually
${\mathcal{V}}({\mathcal{M}}_{d,i})^{\bot }\supseteq {\mathcal{V}}({\mathcal{M}}_{d+1})^{\bot }$
. By [Reference HaqueHaq12, Theorem 1], this is equivalent to the condition that, for any
$V,V^{\prime }\subseteq \operatorname{Mon}_{d+1}$
with
$|V|=|\!\operatorname{Mon}_{d}^{\hat{i} }|+r_{d}+1$
and
$|V^{\prime }|=r_{d+1}-1$
,
$$\begin{eqnarray}\min _{\mathbf{v}\in V\setminus V^{\prime }}p_{d,i}(V-\mathbf{v})\odot p_{d+1}(V^{\prime }\cup \mathbf{v})\text{ is attained at least twice},\end{eqnarray}$$
which reduces to the desired condition. ◻
The next example shows that tropical ideals carry strictly more information than their varieties.
Two tropical irreducible decompositions.
Example 2.7 (Two tropical ideals with the same variety).
Let
$K$
be the field
$\mathbb{C}$
equipped with the trivial valuation
$\operatorname{val}:\mathbb{C}\rightarrow \overline{\mathbb{R}}$
. Consider the principal ideals
$J=\langle (x+y+z)(xy+xz+yz)\rangle$
and
$J^{\prime }=\langle (x+y)(x+z)(y+z)\rangle$
in
$\mathbb{C}[x,y,z]$
. Their tropicalizations
$I:=\operatorname{trop}(J)$
and
$I^{\prime }:=\operatorname{trop}(J^{\prime })$
are homogeneous tropical ideals in
$\overline{\mathbb{R}}[x,y,z]$
with the same variety. This is shown in Figure 1, together with the two associated tropical irreducible decompositions corresponding to tropicalizing the factors in the generators of
$J$
and
$J^{\prime }$
. However, even though the tropical ideals
$I$
and
$I^{\prime }$
coincide up to degree 3, they are distinct. For instance, the degree-4 polynomial
$$\begin{eqnarray}f:=x^{3}y\oplus x^{3}z\oplus xy^{3}\oplus y^{3}z\oplus xz^{3}\oplus yz^{3}\oplus xy^{2}z\oplus xyz^{2}\oplus y^{2}z^{2}\end{eqnarray}$$
is equal to
$\operatorname{trop}((x+y)(x+z)(y+z)(x-y-z))\in I^{\prime }$
, but
$f$
is not in
$I$
: a simple computation shows that no polynomial of the form
$(x+y+z)(xy+xz+yz)(ax+by+cz)$
can have support equal to the support of
$f$
.
We finish this section with an example of a tropical ideal that is not realizable over any field
$K$
.
Example 2.8 (A non-realizable tropical ideal).
For any
$n\geqslant 2$
, we give an example of a homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
that is not realizable over any valued field. Its variety is, however, the standard tropical line in tropical projective space; see Example 5.15.
For
$d\geqslant 0$
, let
${\mathcal{M}}_{d}$
be the rank-(
$d+1$
) valuated matroid on the ground set
$\operatorname{Mon}_{d}$
whose basis valuation function
$p_{d}:\binom{\operatorname{Mon}_{d}}{d+1}\rightarrow \overline{\mathbb{R}}$
is given by
$$\begin{eqnarray}p_{d}(B):=\left\{\begin{array}{@{}ll@{}}0\quad & \text{if for any }k\leqslant d\text{ and any }\mathbf{x}^{\mathbf{v}}\in \operatorname{Mon}_{k}\text{ we have }\\ \quad & \quad |\{\mathbf{x}^{\mathbf{u}}\in B:\mathbf{x}^{\mathbf{v}}\text{ divides }\mathbf{x}^{\mathbf{u}}\}|\leqslant d-k+1,\\ \infty \quad & \text{otherwise}.\end{array}\right.\end{eqnarray}$$
Geometrically, if we think of
$\operatorname{Mon}_{d}$
as the set of lattice points inside a simplex of size
$d$
, the function
$p_{d}$
assigns the value
$0$
precisely to those
$(d+1)$
-subsets
$B$
of
$\operatorname{Mon}_{d}$
such that, for any
$k\leqslant d$
, the subset
$B$
contains at most
$d-k+1$
monomials from any simplex in
$\operatorname{Mon}_{d}$
of size
$d-k$
. A proof that the underlying matroids
$\text{}\underline{{\mathcal{M}}_{d}}$
are indeed matroids (and thus the
${\mathcal{M}}_{d}$
are valuated matroids) can be found in [Reference Ardila and BilleyAB07, Theorem 4.1], where these matroids are studied in connection to flag arrangements.
The circuits of
${\mathcal{M}}_{d}$
are the tropical polynomials of the form
$H=\unicode[STIX]{x1D706}\odot \bigoplus _{\mathbf{u}\in C}\mathbf{x}^{\mathbf{u}}$
with
$\unicode[STIX]{x1D706}\in \mathbb{R}$
and
$C$
an inclusion-minimal subset of
$\operatorname{Mon}_{d}$
satisfying
$|C|>d-\deg (\gcd (C))+1$
. This description shows that, if
$H$
is a circuit of
${\mathcal{M}}_{d}$
and
$x_{i}$
is any variable, then
$x_{i}\odot H$
is a circuit of
${\mathcal{M}}_{d+1}$
. Thus
$({\mathcal{M}}_{d})_{d\geqslant 0}$
is a compatible sequence of valuated matroids, and so the
$\overline{\mathbb{R}}$
-semimodule
$I$
generated by all
${\mathcal{V}}({\mathcal{M}}_{d})$
is a homogeneous tropical ideal.
To show that
$I$
is a non-realizable tropical ideal, note that the tropical polynomial
$f=x_{0}\oplus x_{1}\oplus x_{2}$
is a circuit of
${\mathcal{M}}_{1}$
, so in particular
$f\in I$
. If
$I$
is realizable, then
$I=\operatorname{trop}(J)$
for some ideal
$J\subseteq K[x_{0},\ldots ,x_{n}]$
, and so, since
$f$
is a circuit, there exists some
$g\in J$
such that
$f=\operatorname{trop}(g)$
. After a suitable scaling of the variables, we may assume that
$g=x_{0}+x_{1}+x_{2}$
. The polynomial
$$\begin{eqnarray}h:=g\cdot (x_{0}^{2}+x_{1}^{2}+x_{2}^{2}-x_{0}x_{1}-x_{0}x_{2}-x_{1}x_{2})=x_{0}^{3}+x_{1}^{3}+x_{2}^{3}-3x_{0}x_{1}x_{2}\end{eqnarray}$$
is then a polynomial in
$J$
, and thus
$\operatorname{trop}(h)$
lies in
$I$
. However, this contradicts the fact that
$\operatorname{supp}(\operatorname{trop}(h))\subseteq \{x_{0}^{3},x_{1}^{3},x_{2}^{3},x_{0}x_{1}x_{2}\}$
is an independent set in the underlying matroid
$\text{}\underline{{\mathcal{M}}_{3}}$
.
3 Gröbner theory for tropical ideals
In this section we develop a Gröbner theory for homogeneous tropical ideals in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
and
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
, and use it to prove some basic properties of tropical ideals with coefficients in a more general semiring
$R$
. These include the eventual polynomiality of their Hilbert functions, and the fact that tropical ideals satisfy the ascending chain condition.
We start by defining initial ideals of homogeneous ideals in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
with respect to a weight vector
$\mathbf{w}\in \overline{\mathbb{R}}^{n+1}$
.
Definition 3.1 (Initial ideals).
Let
$\mathbf{w}\in \overline{\mathbb{R}}^{n+1}$
with
$\mathbf{w}\neq (\infty ,\ldots ,\infty )$
. The initial term of a tropical polynomial
$f=\bigoplus a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}\in \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
with respect to
$\mathbf{w}$
is the tropical polynomial in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
given by
$$\begin{eqnarray}\operatorname{in}_{\mathbf{w}}(f):=\left\{\begin{array}{@{}ll@{}}\displaystyle \underset{a_{\mathbf{u}}+\mathbf{w}\cdot \mathbf{u}=f(\mathbf{w})}{\bigoplus }\mathbf{x}^{\mathbf{u}}\quad & \text{if }f(\mathbf{w})<\infty ,\\ \qquad \infty \quad & \text{otherwise},\end{array}\right.\quad \in \mathbb{B}[x_{0},\ldots ,x_{n}].\end{eqnarray}$$
In computing the dot product
$\mathbf{w}\cdot \mathbf{u}$
we follow the convention that
$\infty$
times
$a$
is
$\infty$
for
$a\neq 0$
, and
$\infty$
times
$0$
is
$0$
, so
$\mathbf{w}\cdot \mathbf{u}=\mathbf{w}^{\mathbf{u}}$
. The initial ideal
$\operatorname{in}_{\mathbf{w}}(I)$
of a homogeneous ideal
$I$
in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
is the homogeneous ideal
$$\begin{eqnarray}\operatorname{in}_{\mathbf{w}}(I):=\langle \operatorname{in}_{\mathbf{w}}(f):f\in I\rangle \subseteq \mathbb{B}[x_{0},\ldots ,x_{n}].\end{eqnarray}$$
If
$I$
is a homogeneous ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
, then we define its initial ideal
$\operatorname{in}_{\mathbf{w}}(I)$
as the initial ideal of
$I\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
, using the inclusion of
$\mathbb{B}$
into
$\overline{\mathbb{R}}$
.
Note that
$\operatorname{in}_{\mathbf{w}}(a\odot f\oplus b\odot g)=\operatorname{in}_{\mathbf{w}}(f)\oplus \operatorname{in}_{\mathbf{w}}(g)$
for
$f,g\in I$
and
$a,b\in \overline{\mathbb{R}}$
such that
$a\odot f(\mathbf{w})=b\odot g(\mathbf{w})<\infty$
, so the set of initial forms of a graded piece
$I_{d}$
of
$I$
is a semimodule over
$\mathbb{B}$
. As, in addition,
$\operatorname{in}_{\mathbf{w}}(x_{i}\odot f)=x_{i}\odot \operatorname{in}_{\mathbf{w}}(f)$
, we have
$\operatorname{in}_{\mathbf{w}}(I_{d})=(\operatorname{in}_{\mathbf{w}}I)_{d}$
. Also, since
$I$
is a homogeneous ideal,
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\mathbf{w}+\unicode[STIX]{x1D706}\mathbf{1}}(I)$
for
$\mathbf{1}=(1,1,\ldots ,1)$
, so we may regard
$\mathbf{w}$
as an element of
$\operatorname{trop}(\mathbb{P}^{n})$
.
Remark 3.2. Our definition of initial ideals is compatible with the usual definition of initial ideals used in tropical geometry, in the sense that for any homogeneous ideal
$J\subseteq K[x_{0},\ldots ,x_{n}]$
we have
$\operatorname{in}_{\mathbf{w}}(\operatorname{trop}(J))=\operatorname{trop}(\operatorname{in}_{\mathbf{w}}(J))$
. The initial ideal
$\operatorname{in}_{\mathbf{w}}(J)$
is an ideal in the polynomial ring with coefficients in the residue field of
$K$
, which has a trivial valuation, so
$\operatorname{trop}(\operatorname{in}_{\mathbf{w}}(J))$
is naturally an ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
.
An important result in this section is that initial ideals of tropical ideals are also tropical ideals. This will follow from the following key fact about valuated matroids.
We first extend the notion of initial term to vectors of any valuated matroid over
$\overline{\mathbb{R}}$
. If
$E$
is any finite set,
$H\in \overline{\mathbb{R}}^{E}$
, and
$\mathbf{w}\in \overline{\mathbb{R}}^{E}$
with
$\mathbf{w}\neq (\infty ,\ldots ,\infty )$
, the initial term of
$H$
with respect to
$\mathbf{w}$
is the subset of
$E$
,
$$\begin{eqnarray}\operatorname{in}_{\mathbf{w}}H:=\{e\in E:H_{e}+w_{e}\text{ is minimal among all }e\in E\}\end{eqnarray}$$
if
$\min (H_{e}+w_{e})<\infty$
, and
$\operatorname{in}_{\mathbf{w}}H:=\emptyset$
otherwise.
Lemma 3.3. Let
${\mathcal{M}}=(E,p)$
be a rank-
$r$
valuated matroid, where
$p:\binom{E}{r}\rightarrow \overline{\mathbb{R}}$
is its basis valuation function, and let
$\mathbf{w}=(w_{e})_{e\in E}\in \mathbb{R}^{E}$
. Then
$$\begin{eqnarray}\operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}}):=\biggl\{B\in \binom{E}{r}:p(B)-\mathop{\sum }_{e\in B}w_{e}\text{ is minimal among all }B\in \binom{E}{r}\biggr\}\end{eqnarray}$$
is the collection of bases of an (ordinary) matroid
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
of rank
$r$
on the ground set
$E$
. Its circuits are the elements of
$\operatorname{in}_{\mathbf{w}}{\mathcal{C}}({\mathcal{M}}):=\{\operatorname{in}_{\mathbf{w}}H:H\in {\mathcal{C}}({\mathcal{M}})\}$
that are minimal with respect to inclusion, and its set of cycles is
$$\begin{eqnarray}\operatorname{in}_{\mathbf{w}}{\mathcal{V}}({\mathcal{M}}):=\{\operatorname{in}_{\mathbf{w}}H:H\in {\mathcal{V}}({\mathcal{M}})\}.\end{eqnarray}$$
Proof. For any
$B\in \binom{E}{r}$
set
$$\begin{eqnarray}p_{\mathbf{w}}(B):=p(B)-\mathop{\sum }_{e\in B}w_{e}.\end{eqnarray}$$
To prove that
$\operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})$
satisfies the basis exchange axiom, fix
$A,B\in \binom{E}{r}$
and choose
$a\in A\setminus B$
. Since
$p$
satisfies the valuated basis exchange axiom (2) there exists
$b\in B\setminus A$
such that
$$\begin{eqnarray}p(A)+p(B)\geqslant p(A\cup b-a)+p(B\cup a-b).\end{eqnarray}$$
Subtracting
$\sum _{e\in A}w_{e}+\sum _{e\in B}w_{e}$
on both sides we get
$$\begin{eqnarray}p_{\mathbf{w}}(A)+p_{\mathbf{w}}(B)\geqslant p_{\mathbf{w}}(A\cup b-a)+p_{\mathbf{w}}(B\cup a-b).\end{eqnarray}$$
This implies that
$p_{\mathbf{w}}$
also satisfies the valuated basis exchange axiom. Moreover, if
$A,B\in \operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})$
, then both
$A\cup b-a$
and
$B\cup a-b$
are in
$\operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})$
as well.
We now prove that the circuits of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
have the desired description. The
$\mathbf{w}$
-initial term of any fundamental circuit
$H(B,e)$
of
${\mathcal{M}}$
(as in (3)) is the set of
$e^{\prime }\in E$
for which
$p(B\cup e-e^{\prime })-p(B)+w_{e^{\prime }}$
is minimal. Adding
$p(B)-\sum _{a\in B\cup e}w_{a}$
, we get
$$\begin{eqnarray}\operatorname{in}_{\mathbf{w}}H(B,e)=\{e^{\prime }\in E:p_{\boldsymbol{ w}}(B\cup e-e^{\prime })\text{ is minimal among all }e^{\prime }\in E\}.\end{eqnarray}$$
Any circuit
$C$
of the initial matroid
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
is the fundamental circuit of an element
$e\in E$
over a basis
$B\in \operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})$
, and thus has the form
$$\begin{eqnarray}\displaystyle C & = & \displaystyle \{e^{\prime }\in E:B\cup e-e^{\prime }\in \operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})\}\nonumber\\ \displaystyle & = & \displaystyle \{e^{\prime }\in E:p_{\mathbf{w}}(B\cup e-e^{\prime })=p_{\mathbf{w}}(B)\}\nonumber\\ \displaystyle & = & \displaystyle \operatorname{in}_{\mathbf{w}}H(B,e).\nonumber\end{eqnarray}$$
This shows that all circuits of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
appear in the collection
$\operatorname{in}_{\mathbf{w}}{\mathcal{C}}({\mathcal{M}})$
. To prove our claim, it then suffices to show that each set in
$\operatorname{in}_{\mathbf{w}}{\mathcal{C}}({\mathcal{M}})$
is a dependent set of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
. Assume by contradiction that
$\operatorname{in}_{\mathbf{w}}H\subseteq B$
for some
$H\in {\mathcal{C}}({\mathcal{M}})$
and some basis
$B\in \operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})$
. Fix
$e\in \operatorname{in}_{\mathbf{w}}H$
, and a basis
$B^{\prime }$
of the underlying matroid
$\text{}\underline{{\mathcal{M}}}$
such that
$H=\unicode[STIX]{x1D706}\odot H(B^{\prime },e)$
for some
$\unicode[STIX]{x1D706}\in \mathbb{R}$
. Since
$e\in B\setminus B^{\prime }$
, the valuated basis exchange axiom for
$p_{\mathbf{w}}$
implies that there exists
$e^{\prime }\in B^{\prime }\setminus B$
such that
$$\begin{eqnarray}p_{\mathbf{w}}(B)+p_{\mathbf{w}}(B^{\prime })\geqslant p_{\boldsymbol{ w}}(B\cup e^{\prime }-e)+p_{\boldsymbol{ w}}(B^{\prime }\cup e-e^{\prime }).\end{eqnarray}$$
As
$\operatorname{in}_{\mathbf{w}}H(B^{\prime },e)\subseteq B$
and
$e^{\prime }\not \in B$
, by (4) we have
$p_{\mathbf{w}}(B^{\prime })<p_{\mathbf{w}}(B^{\prime }\cup e-e^{\prime })$
. Moreover, since
$B\in \operatorname{in}_{\mathbf{w}}{\mathcal{B}}({\mathcal{M}})$
, we also have
$p_{\mathbf{w}}(B)\leqslant p_{\mathbf{w}}(B\cup e^{\prime }-e)$
. But then, adding these two inequalities gives a contradiction to (5).
We now prove that the set of cycles of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
is equal to
$\operatorname{in}_{\mathbf{w}}{\mathcal{V}}({\mathcal{M}})$
. Any
$H\in {\mathcal{V}}({\mathcal{M}})$
has the form
$H=H^{1}\oplus \cdots \oplus H^{k}$
for circuits
$H^{1},\ldots ,H^{k}$
of
${\mathcal{M}}$
. Its initial form
$\operatorname{in}_{\mathbf{w}}H$
is the union of those initial forms
$\operatorname{in}_{\mathbf{w}}H^{i}$
for which
$\min _{e\in E}(H_{e}^{i}+w_{e})=\min _{e\in E}(H_{e}+w_{e})$
. It follows that the collection
$\operatorname{in}_{\mathbf{w}}{\mathcal{V}}({\mathcal{M}})$
is closed under unions. Moreover, our previous claim implies that
$\operatorname{in}_{\mathbf{w}}{\mathcal{V}}({\mathcal{M}})$
contains all circuits of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
. To complete the proof, it is thus enough to show that, for any circuit
$G$
of
${\mathcal{M}}$
, the set
$\operatorname{in}_{\mathbf{w}}G$
is a cycle of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
.
We proceed by contradiction. Assume
$G$
is a circuit of
${\mathcal{M}}$
such that
$\operatorname{in}_{\mathbf{w}}G$
is not a cycle, and take
$G$
such that
$\operatorname{in}_{\mathbf{w}}G$
is inclusion-minimal with this property. Since
$\operatorname{in}_{\mathbf{w}}G$
is dependent in
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
, it contains a circuit
$C$
of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
, which must have the form
$C=\operatorname{in}_{\mathbf{w}}H$
for some circuit
$H$
of
${\mathcal{M}}$
. After tropically rescaling, we may assume that
$\min _{e\in E}(G_{e}+w_{e})=\min _{e\in E}(H_{e}+w_{e})$
. Let
$e\in \operatorname{in}_{\mathbf{w}}H\subseteq \operatorname{in}_{\mathbf{w}}G$
. We have
$G_{e}+w_{e}=H_{e}+w_{e}$
, and so
$G_{e}=H_{e}$
. Let
$e^{\prime }\in \operatorname{in}_{\mathbf{w}}G$
be such that
$e^{\prime }$
is in no circuit of
$\operatorname{in}_{\mathbf{w}}{\mathcal{M}}$
contained in
$\operatorname{in}_{\mathbf{w}}G$
; in particular,
$e^{\prime }\notin \operatorname{in}_{\mathbf{w}}H$
. It follows that
$G_{e^{\prime }}+w_{e^{\prime }}<H_{e^{\prime }}+w_{e^{\prime }}$
, and so
$G_{e^{\prime }}<H_{e^{\prime }}$
. We can then apply the circuit elimination axiom to get a circuit
$F$
of
${\mathcal{M}}$
such that
$F_{e}=\infty$
,
$F_{e^{\prime }}=G_{e^{\prime }}$
, and
$F\geqslant G\oplus H$
. This implies that
$e^{\prime }\in \operatorname{in}_{\mathbf{w}}F$
,
$\operatorname{in}_{\mathbf{w}}F\subseteq \operatorname{in}_{\mathbf{w}}G$
, and
$e\notin \operatorname{in}_{\mathbf{w}}F$
. We thus have that
$\operatorname{in}_{\mathbf{w}}F$
is a proper subset of
$\operatorname{in}_{\mathbf{w}}G$
, and our minimality assumption implies that
$\operatorname{in}_{\mathbf{w}}F$
is a cycle. This contradicts our choice of
$e^{\prime }$
, as
$e^{\prime }\in \operatorname{in}_{\mathbf{w}}F$
.◻
In order to use Lemma 3.3 to describe the relationship between the valuated matroids of an ideal and those of its initial ideals, we need the notion of contraction of a valuated matroid.
Let
${\mathcal{M}}$
be a valuated matroid on the ground set
$E$
, and let
$A$
be a subset of
$E$
of rank
$s$
. Fix a basis
$B_{A}$
of the restriction
$\text{}\underline{{\mathcal{M}}}|A$
. The contraction
${\mathcal{M}}/A$
with respect to
$B_{A}$
is the valuated matroid
${\mathcal{M}}/A=(E\setminus A,q)$
of rank
$r-s$
with basis valuation function
$q:\binom{E\setminus A}{r-s}\rightarrow R$
given by
$$\begin{eqnarray}q(B)=p(B\sqcup B_{A}).\end{eqnarray}$$
If we replace
$B_{A}$
by a different basis
$B_{A}^{\prime }$
of
$A$
, then
$q$
changes by global (tropical) multiplication by a nonzero constant; see, for instance, [Reference MurotaMur10, Theorem 5.2.5]. The resulting valuated matroids are thus the same, and we suppress the choice of
$B_{A}$
from the notation for contractions. The set of vectors of the contraction
${\mathcal{M}}/A$
is
$$\begin{eqnarray}{\mathcal{V}}({\mathcal{M}}/A)=\{H[E\setminus A]:H\in {\mathcal{V}}({\mathcal{M}})\},\end{eqnarray}$$
where
$H[E\setminus A]\in R^{E\setminus A}$
is given by
$(H[E\setminus A])_{e}:=H_{e}$
for any
$e\in E\setminus A$
; see, for example, [Reference BakerBak16, Theorem 4.17(2)].
If
$I$
is a homogeneous tropical ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
, we write
$M_{d}(I):=\text{}\underline{{\mathcal{M}}_{d}(I)}$
to emphasize the fact that no extra information is encoded in the valuated matroid
${\mathcal{M}}_{d}(I)$
besides its underlying matroid. Also, if
$M$
is a matroid on the ground set
$E$
, and
$F$
is a finite set, the coloop extension
$M\oplus F$
is the matroid on the ground set
$E\sqcup F$
obtained by attaching to
$M$
all the elements of
$F$
as coloops, i.e.,
${\mathcal{B}}(M\oplus F)=\{B\sqcup F:B\in {\mathcal{B}}(M)\}$
.
Theorem 3.4 (Initial ideals of tropical ideals are tropical).
Let
$I$
be a homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
, and fix
$\mathbf{w}\in \overline{\mathbb{R}}^{n+1}$
with
$\mathbf{w}\neq (\infty ,\ldots ,\infty )$
. The initial ideal
$\operatorname{in}_{\mathbf{w}}(I)$
is a homogeneous tropical ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
. If
$\unicode[STIX]{x1D70E}:=\{i:w_{i}=\infty \}$
and
$\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
is the set of monomials in
$\operatorname{Mon}_{d}$
divisible by a variable
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
, the associated matroid
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
is equal to
$\operatorname{in}_{\hat{\mathbf{w}}}({\mathcal{M}}_{d}(I)/\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}})\oplus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
, where
$\hat{\mathbf{w}}\in \overline{\mathbb{R}}^{\operatorname{Mon}_{d}\setminus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}$
is given by
$\hat{\mathbf{w}}_{\mathbf{x}^{\mathbf{u}}}:=\mathbf{w}\cdot \mathbf{u}$
.
Proof. For any
$f\in I_{d}$
, denote by
$f^{\unicode[STIX]{x1D70E}}$
the tropical polynomial obtained by deleting all terms of
$f$
involving a monomial in
$\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
. By definition, we have
$\operatorname{in}_{\mathbf{w}}(f)=\operatorname{in}_{\mathbf{w}}(f^{\unicode[STIX]{x1D70E}})$
. Moreover, the set
$I_{d}^{\unicode[STIX]{x1D70E}}=\{f^{\unicode[STIX]{x1D70E}}:f\in I_{d}\}$
is the set of vectors of the valuated matroid
${\mathcal{M}}_{d}(I)/\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
. It follows from Lemma 3.3 that
$(\operatorname{in}_{\mathbf{w}}(I))_{d}=\{\operatorname{in}_{\mathbf{w}}(f^{\unicode[STIX]{x1D70E}}):f\in I_{d}\}$
is the set of cycles of the matroid
$\operatorname{in}_{\hat{\mathbf{w}}}({\mathcal{M}}_{d}(I)/\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}})$
, which is also the set of cycles of the coloop extension
$\operatorname{in}_{\hat{\mathbf{w}}}({\mathcal{M}}_{d}(I)/\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}})\oplus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
.◻
We now apply these results to study Hilbert functions of homogeneous tropical ideals in
$R[x_{0},\ldots ,x_{n}]$
, where
$R$
is again a general valuative semifield, and to prove that they satisfy the ascending chain condition.
Definition 3.5 (Hilbert functions).
Let
$I$
be a homogeneous tropical ideal in
$R[x_{0},\ldots ,x_{n}]$
. Its Hilbert function is the function
$H_{I}:\mathbb{Z}_{{\geqslant}0}\rightarrow \mathbb{Z}_{{\geqslant}0}$
defined by
$$\begin{eqnarray}H_{I}(d):=\operatorname{rank}({\mathcal{M}}_{d}(I)).\end{eqnarray}$$
If
$J\subseteq K[x_{0},\ldots ,x_{n}]$
is a homogeneous ideal, then the matroid
$\text{}\underline{{\mathcal{M}}_{d}(\operatorname{trop}(J))}$
encodes the dependencies in
$(K[x_{0},\ldots ,x_{n}]/J)_{d}$
among the monomials in
$\operatorname{Mon}_{d}$
; a subset of
$\operatorname{Mon}_{d}$
is dependent if and only if there is a polynomial
$f\in J_{d}$
whose support is contained in this subset. This implies that the bases of
$\text{}\underline{{\mathcal{M}}_{d}(\operatorname{trop}(J))}$
correspond to monomial bases of the vector space
$(K[x_{0},\ldots ,x_{n}]/J)_{d}$
. It follows that Hilbert functions are preserved under tropicalization:
$$\begin{eqnarray}H_{\operatorname{trop}(J)}(d)=\dim _{K}((K[x_{0},\ldots ,x_{n}]/J)_{d})\end{eqnarray}$$
for any
$d\in \mathbb{Z}_{{\geqslant}0}$
. See also [Reference Giansiracusa and GiansiracusaGG16, Theorem 7.1.6].
A key fact about standard Gröbner theory is that the Hilbert function of an ideal is preserved when passing to an initial ideal. We next observe that this also holds in the tropical setting. Note that
$\mathbf{w}$
is not allowed to have infinite coordinates for this result.
Corollary 3.6. Suppose
$I$
is a homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
or in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
, and fix
$\mathbf{w}\in \mathbb{R}^{n+1}$
. For any
$d\in \mathbb{Z}_{{\geqslant}0}$
we have
$H_{I}(d)=H_{\operatorname{in}_{\mathbf{w}}(I)}(d)$
.
Proof. Suppose
$I$
is a homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
. By Theorem 3.4, the matroid
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
is equal to
$\operatorname{in}_{\hat{\mathbf{w}}}{\mathcal{M}}_{d}(I)$
. The description given in Lemma 3.3 shows that all bases of
$\operatorname{in}_{\hat{\mathbf{w}}}{\mathcal{M}}_{d}(I)$
are bases of the underlying matroid
$\text{}\underline{{\mathcal{M}}_{d}(I)}$
, and thus the rank of
${\mathcal{M}}_{d}(I)$
is equal to the rank of
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
, as desired.
If
$I$
is a homogeneous tropical ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
, let
$I^{\prime }:=I\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
be the ideal generated by
$I$
in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
using the inclusion of
$\mathbb{B}$
into
$\overline{\mathbb{R}}$
. By definition, the ideal
$I^{\prime }$
is a homogeneous tropical ideal satisfying
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\mathbf{w}}(I^{\prime })$
. Moreover,
$I^{\prime }$
has the same Hilbert function as
$I$
, as
$\text{}\underline{{\mathcal{M}}_{d}(I^{\prime })}=M_{d}(I)$
. The result then follows from the previous case.◻
The following result will be useful in our study of tropical ideals and their Hilbert functions.
Lemma 3.7. If
$I$
is a homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
or
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
, then there exists
$\mathbf{w}\in \mathbb{R}^{n+1}$
such that
$\operatorname{in}_{\mathbf{w}}(I)$
is generated by monomials. In fact, the set of
$\mathbf{w}$
for which
$\operatorname{in}_{\mathbf{w}}(I)$
is not generated by monomials is contained in a countable union of hyperplanes in
$\mathbb{R}^{n+1}$
.
Proof. Lemma 3.3 implies that
$\operatorname{in}_{\mathbf{w}}(I)$
is generated by the polynomials
$\operatorname{in}_{\mathbf{w}}(f)$
with
$f$
a circuit of one of the matroids
${\mathcal{M}}_{d}(I)$
. It thus suffices to show that there is a
$\mathbf{w}\in \mathbb{R}^{n+1}$
such that, for any
$d\geqslant 0$
and any circuit
$f$
of
${\mathcal{M}}_{d}(I)$
, the initial term
$\operatorname{in}_{\mathbf{w}}(f)$
is a monomial. For any such
$f$
, the set of
$\mathbf{w}\in \mathbb{R}^{n+1}$
for which
$\operatorname{in}_{\mathbf{w}}(f)$
is not a monomial is a finite union of codimension-1 polyhedra in
$\mathbb{R}^{n+1}$
. Moreover, for any
$d\geqslant 0$
the set of circuits of
${\mathcal{M}}_{d}(I)$
is finite (up to scaling). It follows that the set of
$\mathbf{w}\in \mathbb{R}^{n+1}$
for which there is some circuit
$f$
such that
$\operatorname{in}_{\mathbf{w}}(f)$
is not a monomial is a countable union of codimension-1 polyhedra in
$\mathbb{R}^{n+1}$
.◻
In § 5 we will see that, in fact, the set of
$\mathbf{w}\in \mathbb{R}^{n+1}$
for which
$\operatorname{in}_{\mathbf{w}}(I)$
is not generated by monomials is a finite union of polyhedra of codimension at least 1.
The following result shows that Hilbert functions of tropical ideals are eventually polynomial.
Proposition 3.8. If
$I$
is a homogeneous tropical ideal in
$R[x_{0},\ldots ,x_{n}]$
, then its Hilbert function
$H_{I}$
is eventually polynomial.
Proof. Let
$\unicode[STIX]{x1D711}:R\rightarrow \mathbb{B}$
be the function defined by
$\unicode[STIX]{x1D711}(a)=0$
if
$a\neq \infty$
, and
$\unicode[STIX]{x1D711}(\infty )=\infty$
. Note that
$\unicode[STIX]{x1D711}$
is a surjective semiring homomorphism, as the assumption on
$R$
that
$a\oplus b=\min (a,b)$
implies that
$a\oplus b\neq \infty$
if
$a,b\neq \infty$
. This induces a map of polynomial semirings
$\unicode[STIX]{x1D711}:R[x_{0},\ldots ,x_{n}]\rightarrow \mathbb{B}[x_{0},\ldots ,x_{n}]$
. The image
$\unicode[STIX]{x1D711}(I)$
of
$I$
is a homogeneous tropical ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
; in fact, we have
$M_{d}(\unicode[STIX]{x1D711}(I))=\text{}\underline{{\mathcal{M}}_{d}(I)}$
. The homogeneous tropical ideals
$I$
and
$\unicode[STIX]{x1D711}(I)$
therefore have the same Hilbert function, and thus it is enough to prove that Hilbert functions of homogeneous tropical ideals in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
are eventually polynomial.
In this case, we can use Lemma 3.7 and Corollary 3.6 to reduce to the case where
$I$
is a tropical ideal in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
generated by monomials. In this situation, the Hilbert function
$H_{I}(d)$
equals the number of monomials of degree
$d$
not in
$I$
, which in turn equals the Hilbert function of the ideal
$J\subseteq K[x_{0},\ldots ,x_{n}]$
generated by the monomials in
$I$
, where
$K$
is an arbitrary field. The result then follows from the standard fact that the Hilbert function of a homogeneous ideal in a polynomial ring with coefficients in a field is eventually polynomial.◻
Definition 3.9 (Hilbert polynomials).
Let
$I$
be a homogeneous tropical ideal. The Hilbert polynomial of
$I$
is the polynomial
$P_{I}$
that agrees with the Hilbert function
$H_{I}$
for
$d\gg 0$
. The dimension of
$I$
is the degree of
$P_{I}$
.
The following example shows that tropical ideals are typically not finitely generated. However, we prove in Theorem 3.11 that they do have some Noetherian properties, in the sense that they satisfy the ascending chain condition.
Example 3.10 (Tropical ideals need not be finitely generated).
Let
$J:=\langle x-y\rangle \subseteq K[x,y]$
, and let
$I:=\operatorname{trop}(J)\subseteq R[x,y]$
. We claim that the homogeneous tropical ideal
$I$
is not finitely generated. Note that
$x^{d}-y^{d}\in J$
for all
$d\geqslant 1$
, so
$x^{d}\oplus y^{d}\in I$
for all
$d\geqslant 1$
. Suppose that
$f_{1},\ldots ,f_{r}$
is a finite homogeneous generating set for
$I$
. Then for all
$d\geqslant 1$
we can write
$$\begin{eqnarray}x^{d}\oplus y^{d}=\bigoplus h_{id}\odot f_{i}.\end{eqnarray}$$
Since there is no cancelation in
$R[x,y]$
, if
$m$
is a monomial occurring in
$h_{id}$
for some
$d$
, and
$m^{\prime }$
is a monomial occurring in
$f_{i}$
, then
$mm^{\prime }$
occurs in
$h_{id}\odot f_{i}$
, and thus in
$x^{d}\oplus y^{d}$
. This is only possible if each
$f_{i}$
is either
$x^{d}\oplus y^{d}$
or a power of
$x$
or
$y$
. Thus for any
$d\geqslant \max (\deg (f_{i}))$
, each
$f_{i}$
occurring in (6) must be a power of
$x$
or
$y$
, and at least one of each must occur. This means that
$I_{d}=R[x,y]_{d}$
for
$d\gg 0$
, and so the Hilbert function of
$I$
equals zero for
$d\gg 0$
, which contradicts the fact that the Hilbert functions of
$I$
and
$J$
agree.
Theorem 3.11 (Ascending chain condition).
If
$I,J\subseteq R[x_{0},\ldots ,x_{n}]$
are homogeneous tropical ideals with
$I\subseteq J$
and identical Hilbert functions, then
$I=J$
. Thus there is no infinite ascending chain
$I_{1}\subsetneq I_{2}\subsetneq I_{3}\subsetneq \cdots \,$
of tropical ideals in
$R[x_{0},\ldots ,x_{n}]$
.
Proof. Let
$\unicode[STIX]{x1D711}:R[x_{0},\ldots ,x_{n}]\rightarrow \mathbb{B}[x_{0},\ldots ,x_{n}]$
be the semiring homomorphism described in the proof of Proposition 3.8. If
$I\subseteq J$
are homogeneous tropical ideals in
$R[x_{0},\ldots ,x_{n}]$
, then
$\unicode[STIX]{x1D711}(I)\subseteq \unicode[STIX]{x1D711}(J)$
are homogeneous tropical ideals in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
. Moreover, as
$\unicode[STIX]{x1D711}$
does not alter the underlying matroids, if
$I$
and
$J$
have the same Hilbert function, then so do
$\unicode[STIX]{x1D711}(I)$
and
$\unicode[STIX]{x1D711}(J)$
. In this case, for any
$d\geqslant 0$
, the matroids
$M_{d}(\unicode[STIX]{x1D711}(I))$
and
$M_{d}(\unicode[STIX]{x1D711}(J))$
have the same rank, and any circuit of
$M_{d}(\unicode[STIX]{x1D711}(I))$
is a union of circuits of
$M_{d}(\unicode[STIX]{x1D711}(J))$
, so
$M_{d}(\unicode[STIX]{x1D711}(J))$
is a quotient of
$M_{d}(\unicode[STIX]{x1D711}(I))$
; see [Reference OxleyOxl92, Proposition 7.3.6]. This implies that
$M_{d}(\unicode[STIX]{x1D711}(I))=M_{d}(\unicode[STIX]{x1D711}(J))$
[Reference OxleyOxl92, Corollary 7.3.4]. Given that
$I_{d}\subseteq J_{d}$
and that the circuits of a valuated matroid are determined (up to scaling) by their support, we conclude that
${\mathcal{M}}_{d}(I)={\mathcal{M}}_{d}(J)$
. It follows that
$I=J$
.
Now, suppose that
$I_{1}\subseteq I_{2}\subseteq I_{3}\subseteq \cdots \,$
is an infinite chain of homogeneous tropical ideals in
$R[x_{0},\ldots ,x_{n}]$
. This gives rise to the chain
$\unicode[STIX]{x1D711}(I_{1})\subseteq \unicode[STIX]{x1D711}(I_{2})\subseteq \unicode[STIX]{x1D711}(I_{3})\subseteq \cdots \,$
of homogeneous tropical ideals in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
. By Lemma 3.7, we can choose
$\mathbf{w}\in \mathbb{R}^{n+1}$
such that
$\operatorname{in}_{\mathbf{w}}(\unicode[STIX]{x1D711}(I_{j}))$
is generated by monomials for each
$j$
. The chain
$\operatorname{in}_{\mathbf{w}}(\unicode[STIX]{x1D711}(I_{1}))\subseteq \operatorname{in}_{\mathbf{w}}(\unicode[STIX]{x1D711}(I_{2}))\subseteq \operatorname{in}_{\mathbf{w}}(\unicode[STIX]{x1D711}(I_{3}))\subseteq \cdots \,$
is then an infinite chain of monomial ideals, which can then be regarded as ideals in
$K[x_{0},\ldots ,x_{n}]$
, where
$K$
is any field. As
$K[x_{0},\ldots ,x_{n}]$
is Noetherian, this chain must stabilize. Since
$\operatorname{in}_{\mathbf{w}}(\unicode[STIX]{x1D711}(I_{j}))$
and
$I_{j}$
have the same Hilbert functions, it follows that, for large enough
$j$
, the Hilbert functions of the
$I_{j}$
are all equal. Our previous claim then shows that, for large enough
$j$
, the ideals
$I_{j}$
are all the same, and so the chain stabilizes.◻
Example 3.12 (Tropical ideals are not determined in low degrees).
We present an infinite family of distinct homogeneous tropical ideals
$(I_{m}^{\prime })_{m>0}$
in
$\overline{\mathbb{R}}[x,y,z,w]$
, all having the same Hilbert function, such that, for any
$d\geqslant 0$
, if
$k,l\geqslant d$
, then the tropical ideals
$I_{k}^{\prime }$
and
$I_{l}^{\prime }$
agree on all their homogeneous parts of degree at most
$d$
, i.e.,
$(I_{k}^{\prime })_{i}=(I_{l}^{\prime })_{i}$
for all
$i\leqslant d$
. It follows that there is no bound
$D$
depending only on the Hilbert function of a tropical ideal
$J$
for which the homogeneous parts
$(J_{i})_{i\leqslant D}$
of degree at most
$D$
determine the whole tropical ideal
$J$
. This contrasts with the case of ideals in a standard polynomial ring, where the Gotzmann number [Reference Bruns and HerzogBH93, §4.3] of a Hilbert polynomial is a bound on the degrees of the generators for any saturated ideal with that Hilbert polynomial.
For
$\unicode[STIX]{x1D706}\in \mathbb{C}$
, consider the ideal
$J_{\unicode[STIX]{x1D706}}:=\langle x-z-w,\,y-z-\unicode[STIX]{x1D706}w\rangle$
in
$\mathbb{C}[x,y,z,w]$
, and let
$I_{\unicode[STIX]{x1D706}}:=\operatorname{trop}(J_{\unicode[STIX]{x1D706}})$
. The Hilbert function of
$I_{\unicode[STIX]{x1D706}}$
is the same as that of
$J_{\unicode[STIX]{x1D706}}$
, so
$H_{I_{\unicode[STIX]{x1D706}}}(d)=d+1$
. We claim that, for any degree
$d\geqslant 0$
, the degree-
$d$
parts of the homogeneous tropical ideals
$I_{\unicode[STIX]{x1D706}}$
are the same for all but finitely many values of
$\unicode[STIX]{x1D706}$
. Indeed, as we are working with the trivial valuation
$\operatorname{val}:\mathbb{C}\rightarrow \overline{\mathbb{R}}$
, the degree-
$d$
part of
$I_{\unicode[STIX]{x1D706}}$
is determined by its rank-
$(d+1)$
underlying matroid
$\text{}\underline{{\mathcal{M}}_{d}(I_{\unicode[STIX]{x1D706}})}$
, which encodes the linear dependencies in the vector space
$(\mathbb{C}[x,y,z,w]/J_{\unicode[STIX]{x1D706}})_{d}$
among the monomials of degree
$d$
. The polynomials
$x-z-w$
and
$y-z-\unicode[STIX]{x1D706}w$
form a Gröbner basis for
$J_{\unicode[STIX]{x1D706}}$
with respect to the lexicographic monomial order with
$x>y>z>w$
, and the initial ideal
$\operatorname{in}(J_{\unicode[STIX]{x1D706}})$
is
$\langle x,y\rangle$
. The corresponding standard monomials are the monomials that use only the variables
$z$
and
$w$
. These monomials form a basis for
$\mathbb{C}[x,y,z,w]/J_{\unicode[STIX]{x1D706}}$
. Consider the matrix
$A$
whose columns are indexed by all monomials of degree
$d$
and whose rows are indexed by the
$d+1$
standard monomials of degree
$d$
, where the entries of a column indexed by a monomial
$\mathbf{x}^{\mathbf{u}}$
correspond to the unique way of expressing
$\mathbf{x}^{\mathbf{u}}$
in terms of standard monomials in
$(\mathbb{C}[x,y,z,w]/J_{\unicode[STIX]{x1D706}})_{d}$
. Note that the entries of
$A$
are polynomials in
$\unicode[STIX]{x1D706}$
. The bases of the matroid
$\text{}\underline{{\mathcal{M}}_{d}(I_{\unicode[STIX]{x1D706}})}$
thus correspond to the
$(d+1)$
-subsets of the columns of
$A$
for which the associated maximal minor is nonzero. The collection of maximal minors of
$A$
is a finite set of polynomials in
$\unicode[STIX]{x1D706}$
, and so, for any
$\unicode[STIX]{x1D706}$
that is not a root of any of these polynomials (except for the minors that are identically zero), the matroid
$\text{}\underline{{\mathcal{M}}_{d}(I_{\unicode[STIX]{x1D706}})}$
is the same, proving our claim. We will call this matroid the generic matroid
$M_{d}$
.
We now show that for any positive integer
$n$
, the matroid
$\text{}\underline{{\mathcal{M}}_{n}(I_{n})}$
is not the generic matroid
$M_{n}$
. Consider the
$n+1$
monomials
$x^{n}$
,
$yz^{n-1}$
,
$z^{n-2}w^{2}$
,
$z^{n-3}w^{3},\ldots$
,
$w^{n}$
in
$\operatorname{Mon}_{d}$
. These can be expressed in terms of standard monomials as
$x^{n}=(z+w)^{n}$
,
$yz^{n-1}=z^{n}+\unicode[STIX]{x1D706}z^{n-1}w$
,
$z^{n-2}w^{2}$
,
$z^{n-3}w^{3},\ldots$
,
$w^{n}$
. But then a simple linear algebra computation shows that these elements are dependent only when
$\unicode[STIX]{x1D706}=n$
, as desired.
We define our family of tropical ideals
$(I_{m}^{\prime })_{m>0}$
inductively as follows. Let
$N_{0}=1$
, and suppose we have defined the tropical ideals
$I_{k}^{\prime }$
for all
$k<m$
. Define
$I_{m}^{\prime }:=I_{N_{m}}$
, where
$N_{m}>N_{m-1}$
is a large enough integer such that, for any degree
$d\leqslant N_{m-1}$
, the degree-
$d$
part of
$I_{N_{m}}$
is the generic matroid
$M_{d}$
. Since the matroid
$\text{}\underline{{\mathcal{M}}_{N_{m}}(I_{N_{m}})}$
is not
$M_{N_{m}}$
, all the tropical ideals
$I_{N_{m}}$
defined in this way must be distinct. Also, by induction, we must have
$N_{m-1}\geqslant m$
. We conclude that the family
$(I_{m}^{\prime })_{m>0}$
satisfies the required conditions: for any
$d\geqslant 0$
, if
$k,l\geqslant d$
, then the homogeneous parts of
$I_{k}^{\prime }=I_{N_{k}}$
and
$I_{l}^{\prime }=I_{N_{l}}$
of degree at most
$d$
are the generic matroids, as
$N_{k-1}$
and
$N_{l-1}$
are both greater than
$d$
.
4 Subschemes of tropical toric varieties
We now extend the definition of tropical ideals to cover subschemes of tropical toric varieties other than tropical projective space.
Tropical toric varieties are defined analogously to classical toric varieties. Given a rational polyhedral fan
$\unicode[STIX]{x1D6F4}$
, we associate an affine tropical toric variety to each cone, and glue these together. Explicitly, fix a lattice
$N\cong \mathbb{Z}^{n}$
with dual lattice
$M:=\operatorname{Hom}(N,\mathbb{Z})\cong \mathbb{Z}^{n}$
. Given a rational polyhedral fan
$\unicode[STIX]{x1D6F4}$
in
$N_{\mathbb{R}}:=N\otimes \mathbb{R}\cong \mathbb{R}^{n}$
, to each
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
we associate the vector space
$N(\unicode[STIX]{x1D70E}):=N_{\mathbb{R}}/\operatorname{span}(\unicode[STIX]{x1D70E})$
. The tropical toric variety associated to
$\unicode[STIX]{x1D6F4}$
is
$$\begin{eqnarray}\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}):=\coprod _{\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}}N(\unicode[STIX]{x1D70E}).\end{eqnarray}$$
To each
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
we also associate the space
$U_{\unicode[STIX]{x1D70E}}^{\operatorname{trop}}:=\operatorname{Hom}(\unicode[STIX]{x1D70E}^{\vee }\,\cap \,M,\overline{\mathbb{R}})$
of semigroup homomorphisms to the semigroup
$(\overline{\mathbb{R}},\odot )$
. We have
$U_{\unicode[STIX]{x1D70E}}^{\operatorname{trop}}=\coprod _{\unicode[STIX]{x1D70F}\preccurlyeq \unicode[STIX]{x1D70E}}N(\unicode[STIX]{x1D70F})$
, where the union is over all faces
$\unicode[STIX]{x1D70F}$
of
$\unicode[STIX]{x1D70E}$
. The topology on
$\overline{\mathbb{R}}$
has as basic open sets all open intervals in
$\mathbb{R}$
, plus intervals of the form
$(a,\infty ]=\{b\in \mathbb{R}:b>a\}\cup \{\infty \}$
. This induces the product topology on
$\overline{\mathbb{R}}^{\unicode[STIX]{x1D70E}^{\vee }\cap M}$
, and thus on
$U_{\unicode[STIX]{x1D70E}}^{\operatorname{trop}}$
. See [Reference KajiwaraKaj08, Reference PaynePay09, Reference RabinoffRab12] or [Reference Maclagan and SturmfelsMS15, ch. 6] for more details on this construction. Important special cases are the tropical versions of affine space, projective space, and the torus; see Example 4.2.
One can also tropicalize the notion of Cox ring of a toric variety. In the case that the fan
$\unicode[STIX]{x1D6F4}$
does not span all of
$N_{\mathbb{R}}$
, for ease of notation we tropicalize the version given in [Reference Cox, Little and SchenckCLS11, (5.1.10)]. The more invariant choice given in [Reference Cox, Little and SchenckCLS11, Theorem 5.1.17] can also be tropicalized.
In what follows we will only consider rational polyhedral fans, so will refer to them simply as fans.
Definition 4.1 (Cox semirings of tropical toric varieties).
Let
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
be a tropical toric variety defined by a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}\cong \mathbb{R}^{n}$
. Let
$s$
be the number of rays of
$\unicode[STIX]{x1D6F4}$
, and let
$t=n-\dim (\operatorname{span}(\unicode[STIX]{x1D6F4}))$
. Write
$m=s+t$
. The Cox semiring of
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
is the semiring
$$\begin{eqnarray}\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})):=\overline{\mathbb{R}}[x_{1},\ldots ,x_{m}].\end{eqnarray}$$
Write
$N$
as the direct sum
$N^{\prime }\oplus N^{\prime \prime }$
, where the rays of
$\unicode[STIX]{x1D6F4}$
span
$N_{\mathbb{R}}^{\prime }$
. Fix an
$m\times n$
matrix
$Q$
whose
$i$
th row is the first lattice point
$\mathbf{v}_{i}$
on the
$i$
th ray of
$\unicode[STIX]{x1D6F4}$
for
$1\leqslant i\leqslant s$
, and whose last
$t$
rows form a basis for
$N^{\prime \prime }$
. We grade
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
by the ‘combinatorial Chow group’
$A_{n-1}(\unicode[STIX]{x1D6F4}):=\operatorname{coker}(M\cong \mathbb{Z}^{n}\stackrel{\unicode[STIX]{x1D711}}{\rightarrow }\mathbb{Z}^{m}),$
where the map
$\unicode[STIX]{x1D711}$
is given by
$\unicode[STIX]{x1D711}(\mathbf{u})=Q\mathbf{u}$
. This gives the last
$t$
variables of
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
degree
$\mathbf{0}\in A_{n-1}(\unicode[STIX]{x1D6F4})$
.
We will identify the rays of
$\unicode[STIX]{x1D6F4}$
with the elements of
$\{1,\ldots ,s\}$
, and thus general cones of
$\unicode[STIX]{x1D6F4}$
with subsets of
$\{1,\ldots ,s\}$
. For a cone
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
write
$$\begin{eqnarray}\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}=\mathop{\prod }_{i\not \in \unicode[STIX]{x1D70E}}x_{i}\in \overline{\mathbb{R}}[x_{1},\ldots ,x_{m}].\end{eqnarray}$$
The localization of the semiring
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{m}]$
at a monomial is defined analogously to the ring case. The degree-0 part of the localization of the Cox semiring at
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}$
is isomorphic to the semigroup semiring
$$\begin{eqnarray}(\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}\cong \overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\vee }\cap M].\end{eqnarray}$$
Note that the last
$t$
variables are always inverted in these localizations.
Classical toric varieties can alternatively be described by the quotient construction
$X_{\unicode[STIX]{x1D6F4}}=(\mathbb{A}^{m}\setminus V(B_{\unicode[STIX]{x1D6F4}}))/H_{\unicode[STIX]{x1D6F4}}$
, where
$B_{\unicode[STIX]{x1D6F4}}$
denotes the irrelevant ideal
$\langle \mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}:\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}\rangle \subseteq K[x_{1},\ldots ,x_{m}]$
, and
$H_{\unicode[STIX]{x1D6F4}}=\operatorname{Hom}(A_{n-1}(X_{\unicode[STIX]{x1D6F4}}),K^{\ast })$
. This construction also tropicalizes [Reference Maclagan and SturmfelsMS15, Proposition 6.2.6]:
$$\begin{eqnarray}\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})=(\overline{\mathbb{R}}^{m}\setminus V(\operatorname{trop}(B_{\unicode[STIX]{x1D6F4}})))/\operatorname{trop}(H_{\unicode[STIX]{x1D6F4}}),\end{eqnarray}$$
where
$\operatorname{trop}(B_{\unicode[STIX]{x1D6F4}})$
denotes the monomial ideal in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{m}]$
given by
$$\begin{eqnarray}\operatorname{trop}(B_{\unicode[STIX]{x1D6F4}})=\langle \mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}:\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}\rangle\end{eqnarray}$$
and
$\operatorname{trop}(H_{\unicode[STIX]{x1D6F4}})$
is the
$n$
-dimensional subspace
$\ker (Q^{T})\subseteq \mathbb{R}^{m}$
. Write
$$\begin{eqnarray}\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{m}:=\{\mathbf{w}\in \overline{\mathbb{R}}^{m}:w_{i}=\infty \text{for }i\in \unicode[STIX]{x1D70E},~w_{i}\neq \infty \text{for }i\notin \unicode[STIX]{x1D70E}\}.\end{eqnarray}$$
The equality in (7) identifies
$U_{\unicode[STIX]{x1D70E}}^{\operatorname{trop}}$
with the subset
$(\overline{\mathbb{R}}^{m}\setminus V(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}))/\ker (Q^{T})$
, and
$N(\unicode[STIX]{x1D70E})$
with
$(\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{m}\setminus V(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}))/\ker (Q^{T})$
. The topology on
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
is consistent with the quotient topology coming from the topology on
$\overline{\mathbb{R}}^{m}$
.
Example 4.2 (Tropical affine space, projective space, and the torus).
The fan
$\unicode[STIX]{x1D6F4}$
consisting of the positive orthant in
$N_{\mathbb{R}}\cong \mathbb{R}^{n}$
gives rise to the toric variety
$\mathbb{A}^{n}$
. The tropical toric variety
$\operatorname{trop}(\mathbb{A}^{n})$
is
$\overline{\mathbb{R}}^{n}$
. Any face of the positive orthant has the form
$\operatorname{cone}\{\mathbf{e}_{i}:i\in \unicode[STIX]{x1D70E}\}$
for
$\unicode[STIX]{x1D70E}\subseteq \{1,\ldots ,n\}$
; the stratum
$N(\unicode[STIX]{x1D70E})$
corresponds precisely to the set
$\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n}\subseteq \overline{\mathbb{R}}^{n}$
. The Cox semiring
$\operatorname{Cox}(\operatorname{trop}(\mathbb{A}^{n}))$
is equal to
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
with the trivial grading
$\deg (x_{i})=0$
for all
$i$
.
The fan
$\unicode[STIX]{x1D6F4}$
defining
$\mathbb{P}^{n}$
has rays spanned by
$\mathbf{e}_{1},\ldots ,\mathbf{e}_{n}$
and
$\mathbf{e}_{0}=-\sum _{i=1}^{n}\mathbf{e}_{i}$
in
$N_{\mathbb{R}}\cong \mathbb{R}^{n}$
, and cones spanned by any
$j$
of these rays for
$j\leqslant n$
. The Cox semiring in this case is
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
with the standard grading
$\deg (x_{i})=1$
for all
$i$
. The tropicalization
$\operatorname{trop}(\mathbb{P}^{n})$
equals
$(\overline{\mathbb{R}}^{n+1}\setminus \{(\infty ,\ldots ,\infty )\})/\mathbb{R}\mathbf{1}$
, where
$\mathbf{1}=(1,\ldots ,1)$
. Figure 2 shows the fan
$\unicode[STIX]{x1D6F4}$
and its corresponding tropical toric variety
$\operatorname{trop}(\mathbb{P}^{2})=\coprod _{\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}}N(\unicode[STIX]{x1D70E})$
in the case where
$n=2$
.
Tropical projective space
$\operatorname{trop}(\mathbb{P}^{2})$
as a tropical toric variety.
The fan
$\unicode[STIX]{x1D6F4}$
consisting of just the origin in
$N_{\mathbb{R}}\cong \mathbb{R}^{n}$
gives rise to the tropical torus
$\mathbb{R}^{n}$
. Its Cox semiring is
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
with the trivial grading
$\deg (x_{i})=0$
for all
$i$
. The localization at the unique cone
$\unicode[STIX]{x1D70E}=\{\mathbf{0}\}$
is
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]_{x_{1}\cdots x_{n}}\cong \overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
.
Subschemes of a classical toric variety can be described by ideals in its Cox ring. We now extend this to the tropical realm.
Definition 4.3 (Tropical ideals in Cox semirings).
Let
$\unicode[STIX]{x1D6F4}$
be a fan in
$N_{\mathbb{R}}$
, and fix a cone
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
. An ideal
$I\subseteq \overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\vee }\cap M]$
is a tropical ideal if, for every finite set
$E$
of monomials in
$\overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\vee }\cap M]$
, the set of polynomials with support in
$E$
is the collection of vectors of a valuated matroid on
$E$
.
Set
$S=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
. A homogeneous ideal
$I\subseteq S$
is a locally tropical ideal if for every
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
the ideal
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}\subseteq \overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\vee }\cap M]$
is a tropical ideal.
Suppose the rays
$\unicode[STIX]{x1D6F4}(1)$
of
$\unicode[STIX]{x1D6F4}$
positively span
$N_{\mathbb{R}}$
, so the grading of
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
is positive and for any degree
$\mathbf{b}$
the homogeneous graded piece
$I_{\mathbf{b}}$
contains finitely many monomials (see [Reference Miller and SturmfelsMS05, ch. 8]). In this case, a homogeneous ideal
$I\subseteq \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
is a homogeneous tropical ideal if every graded piece
$I_{\mathbf{b}}$
is the set of vectors of a valuated matroid on the set of monomials of degree
$\mathbf{b}$
.
Proposition 4.4. Let
$\unicode[STIX]{x1D6F4}$
be a fan whose rays positively span
$N_{\mathbb{R}}$
. Any homogeneous tropical ideal in
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
is a locally tropical ideal.
Proof. Write
$S=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
, and suppose that
$I\subseteq S$
is a homogeneous tropical ideal. Fix
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
, and let
$E$
be a collection of monomials in
$(S_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
. All monomials in
$E$
have the form
$\mathbf{x}^{\mathbf{u}}/(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{l}$
for some
$\mathbf{u}\in \mathbb{N}^{s}$
and
$l\geqslant 0$
. Choosing a common denominator, we may assume that the exponent
$l$
is the same for all monomials in
$E$
. This means that for all
$f\in (IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
with support in
$E$
we have
$g:=(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{l}f\in IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}\cap S=(I:(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{\infty })$
. Note that
$g$
is homogeneous of degree
$l\deg (\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})$
. Moreover, given any homogeneous polynomial
$g$
of degree
$l\deg (\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})$
in
$(I:(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{\infty })$
, there is some
$l^{\prime }\geqslant 0$
for which
$(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{l^{\prime }}g\in I$
, so
$g/(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{l}\in (IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
. This gives a bijection between polynomials in
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
with support in
$E$
and homogeneous polynomials in
$(I:(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{\infty })$
of degree
$l\deg (\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})$
with support in
$(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{l}E$
.
Since the restriction of the set of vectors of a valuated matroid to a subset of its ground set is also a valuated matroid, it thus suffices to show that the set of polynomials in
$(I:(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{\infty })$
of degree
$l\deg (\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})$
is the set of vectors of a valuated matroid. This follows from the fact that, if
$I$
is a homogeneous tropical ideal, then
$J:=(I:(\mathbf{x}^{\mathbf{u}})^{\infty })$
is as well for any monomial
$\mathbf{x}^{\mathbf{u}}$
. Indeed, suppose that
$f,g\in J_{\mathbf{b}}$
. Then there is
$l\geqslant 0$
for which
$\mathbf{x}^{l\mathbf{u}}f,\mathbf{x}^{l\mathbf{u}}g\in I$
, and thus the vector elimination axiom for
$J_{\mathbf{b}}$
follows from the vector elimination axiom for
$I_{\mathbf{b}+l\deg (\mathbf{x}^{\mathbf{u}})}$
.◻
Example 4.5. Let
$\unicode[STIX]{x1D6F4}$
be the fan in
$N_{\mathbb{R}}$
consisting of just one cone
$\unicode[STIX]{x1D70E}=\{\mathbf{0}\}$
, so the corresponding tropical toric variety is the tropical torus
$\mathbb{R}^{n}$
. An ideal
$I\subseteq \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
is a locally tropical ideal if, for every finite set
$E$
of monomials in
$(\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}\cong \overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
, the set of polynomials in the image of
$I$
with support in
$E$
is the set of vectors of a valuated matroid on
$E$
.
If
$\unicode[STIX]{x1D6F4}$
is the positive orthant in
$N_{\mathbb{R}}$
, so the corresponding tropical toric variety is
$\overline{\mathbb{R}}^{n}$
, the condition for an ideal
$I\subseteq \operatorname{Cox}(X_{\unicode[STIX]{x1D6F4}})\cong \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
to be a tropical ideal (and a locally tropical ideal) is analogous: for every finite set
$E$
of monomials in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, the set of polynomials in
$I$
with support in
$E$
should be the set of vectors of a valuated matroid on
$E$
. Note that this agrees with Definition 1.1 in the introduction.
For a tropical polynomial
$f=\sum a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}\in \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, the homogenization of
$f$
is the polynomial
$\tilde{f}:=\sum a_{\mathbf{u}}\odot x_{0}^{d-|\mathbf{u}|}\odot \mathbf{x}^{\mathbf{u}}\in \overline{\mathbb{R}}[x_{0},x_{1},\ldots ,x_{n}]$
, where
$d=\max _{a_{\mathbf{u}}\neq \infty }|\mathbf{u}|$
. The homogenization of an ideal
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is
$\tilde{I} :=\langle \tilde{f}:f\in I\rangle$
. This has the property that every homogeneous polynomial
$g\in \tilde{I}$
has the form
$x_{0}^{m}\odot \tilde{f}$
for some
$m\geqslant 0$
and
$f\in I$
, and so the set of homogeneous polynomials of degree
$d$
in
$\tilde{I}$
is in bijection with the set of polynomials in
$I$
of degree at most
$d$
. This implies that, if
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a (locally) tropical ideal, then
$\tilde{I}$
is a homogeneous tropical ideal.
Example 4.6 (The affine ideal of a point).
For any
$\mathbf{a}\in \overline{\mathbb{R}}^{n}$
, let
$J_{\mathbf{a}}\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
be the ideal consisting of all tropical polynomials
$f$
whose variety
$V(f)$
contains
$\mathbf{a}$
. Its homogenization
$\tilde{J_{\mathbf{a}}}\subseteq \overline{\mathbb{R}}[x_{0},x_{1},\ldots ,x_{n}]$
is the homogeneous ideal
$J_{(0,\mathbf{a})}$
of the point
$(0,\mathbf{a})\in \overline{\mathbb{R}}^{n+1}$
(see Example 2.4). By Lemma 4.4,
$J_{\mathbf{a}}$
is a tropical ideal, as
$(\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]_{x_{0}})_{\mathbf{0}}\cong \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, with the isomorphism taking
$x_{0}$
to
$0$
. We will see in Example 5.19 that the ideals of the form
$J_{\mathbf{a}}$
are precisely the maximal tropical ideals of
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
.
The following example shows that the converse of Proposition 4.4 is not true.
Example 4.7 (Locally tropical ideals might not be homogeneous tropical ideals).
Let
$X_{\unicode[STIX]{x1D6F4}}=\mathbb{P}^{1}$
, so
$S:=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))=\overline{\mathbb{R}}[x,y]$
with the standard grading. Let
$I:=\langle x\!\oplus \!y,x^{3},y^{3}\rangle$
. Then
$(IS_{x})_{0}=(S_{x})_{0}=\overline{\mathbb{R}}[y/x]$
,
$(IS_{y})_{0}=(S_{y})_{0}=\overline{\mathbb{R}}[x/y]$
, and
$(IS_{xy})_{0}=(S_{xy})_{0}=\overline{\mathbb{R}}[(x/y)^{\pm 1}]$
. Since these localizations are all equal to their respective coordinate semirings, they are trivially tropical ideals. However,
$I_{2}$
is the
$\overline{\mathbb{R}}$
-semimodule spanned by
$x^{2}\oplus xy$
and
$xy\oplus y^{2}$
, which is not the set of vectors of a valuated matroid, as the polynomial
$x^{2}\oplus y^{2}$
is not in
$I_{2}$
.
Remark 4.8. The notion of being a (locally) tropical ideal is invariant under automorphisms of the coordinate semirings, as the lack of cancelation forces any automorphism to send monomials into monomials. In the case that the toric variety is the torus, for example, the coordinate semiring
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
has a natural action of
$\operatorname{GL}(n,\mathbb{Z})$
by monomial change of coordinates: for any matrix
$A\in \operatorname{GL}(n,\mathbb{Z})$
we have
$A\cdot \mathbf{x}^{\mathbf{u}}=\mathbf{x}^{A\mathbf{u}}$
. If
$I$
is a tropical ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
, then
$A\cdot I$
is as well, as the
$\operatorname{GL}(n,\mathbb{Z})$
action permutes finite sets of monomials.
Remark 4.9. The ascending chain condition (Theorem 3.11) holds for homogeneous tropical ideals in the positively-graded case, with the same proof, but does not hold verbatim for locally tropical ideals. For example, let
$I_{n}:=\langle x^{2},y^{2},x\oplus i\odot y:0\leqslant i\leqslant n\rangle \subseteq \overline{\mathbb{R}}[x,y]=\operatorname{Cox}(\operatorname{trop}(\mathbb{P}^{1}))$
. Then
$\{I_{n}\}_{n\geqslant 0}$
is an infinite ascending chain of locally tropical ideals. However, in this case, for all cones
$\unicode[STIX]{x1D70E}$
in the fan of
$\mathbb{P}^{1}$
, the ideals
$(I\overline{\mathbb{R}}[x,y]_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
are the unit ideal
$\langle 0\rangle$
. All the
$I_{n}$
thus correspond geometrically to the same (empty) subscheme of
$\operatorname{trop}(\mathbb{P}^{1})$
.
For a general tropical toric variety, one can define an equivalence relation on the set of locally tropical ideals in
$S:=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
by setting
$I\sim J$
if
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}=(JS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
for all
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
. The proof of Theorem 3.11 then shows that there is no infinite ascending chain of non-equivalent locally tropical ideals.
When working with semirings, congruences perform some of the functions of ideals in rings. A congruence on a semiring
$S$
is an equivalence relation
${\sim}$
on
$S$
that is compatible with addition and multiplication:
$f\sim g$
and
$f^{\prime }\sim g^{\prime }$
imply that
$(f\oplus f^{\prime })\sim (g\oplus g^{\prime })$
and
$(f\odot g)\sim (g\odot g^{\prime })$
. In [Reference Giansiracusa and GiansiracusaGG16], Jeffrey and Noah Giansiracusa defined a congruence associated to an ideal in the tropical setting, as we now recall.
Definition 4.10 (Bend relations [Reference Giansiracusa and GiansiracusaGG16]).
Let
$S:=\overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\vee }\cap M]$
for a cone
$\unicode[STIX]{x1D70E}\subseteq N_{\mathbb{R}}$
. For a polynomial
$f=\bigoplus a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}\in S$
, denote by
$f_{\hat{\mathbf{v}}}$
the polynomial obtained by deleting the term involving
$\mathbf{x}^{\mathbf{v}}$
from
$f$
, i.e.,
$f_{\hat{\mathbf{v}}}=\bigoplus _{\mathbf{u}\neq \mathbf{v}}a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}$
. The bend relations of
$f$
are
$$\begin{eqnarray}B(f):=\{f\sim f_{\hat{\mathbf{v}}}:\mathbf{x}^{\mathbf{v}}\in \operatorname{supp}(f)\}.\end{eqnarray}$$
The bend congruence
${\mathcal{B}}(I)$
of an ideal
$I\subseteq S$
is the congruence on
$S$
,
$$\begin{eqnarray}{\mathcal{B}}(I):=\langle B(f):f\in I\rangle .\end{eqnarray}$$
The coordinate semiring associated to
$I$
is
$S/{\mathcal{B}}(I)$
.
This construction is motivated by the fact that, for any ideal
$I\subseteq \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, there is a canonical isomorphism
$\operatorname{Hom}(S/{\mathcal{B}}(I),\overline{\mathbb{R}})\cong V(I)\,\subseteq \overline{\mathbb{R}}^{n}$
.
In [Reference Giansiracusa and GiansiracusaGG16], the tropicalization of the subscheme of
$\mathbb{A}^{n}$
defined by an ideal
$J\subseteq K[x_{1},\ldots ,x_{n}]$
is defined to be
$\operatorname{Spec}(\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]/{\mathcal{B}}(\operatorname{trop}(J)))$
. Here
$\operatorname{Spec}$
is used in the sense of
$\mathbb{F}_{1}$
-geometry, so it denotes a topological space with a sheaf of semirings. The underlying space of
$\operatorname{Spec}(R)$
for a semiring
$R$
is the set of prime ideals of
$R$
, where an ideal
$I$
is prime if
$f\odot g\in I$
implies that
$f\in I$
or
$g\in I$
. Similarly, the tropicalization of the subscheme of
$\mathbb{P}^{n}$
defined by a homogeneous ideal
$J\subseteq K[x_{0},\ldots ,x_{n}]$
is
$\operatorname{Proj}(\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]/{\mathcal{B}}(\operatorname{trop}(J)))$
, where the underlying set of
$\operatorname{Proj}$
is the set of homogeneous prime ideals not containing
$\langle x_{0},\ldots ,x_{n}\rangle$
. This is explained in [Reference LorscheidLor17, §9], where these are presented as a special case of Lorscheid’s blueprints. See also [Reference LorscheidLor12, Reference LorscheidLor15, Reference DurovDur07, Reference Toën and VaquiéTV09] for related work. The results in [Reference Giansiracusa and GiansiracusaGG16] are set in this context, so they describe the tropicalization of any subscheme of a classical toric variety. We now generalize this construction to include more general subschemes of tropical toric varieties that are not necessarily tropicalizations.
Definition 4.11 (Subschemes of tropical toric varieties).
Let
$I$
be a locally tropical ideal of the Cox semiring
$S$
of a tropical toric variety
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
. The subscheme of
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
defined by
$I$
is given locally as a subscheme of
$U_{\unicode[STIX]{x1D70E}}^{\operatorname{trop}}$
by
$$\begin{eqnarray}\operatorname{Spec}(\overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\vee }\cap M]/{\mathcal{B}}((IS_{\boldsymbol{ x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}})).\end{eqnarray}$$
Definition 4.11 makes sense without the restriction that
$I$
be a locally tropical ideal; the reason for requiring this condition is that, as shown in Example 5.14, without it the variety of the subscheme might not be a finite polyhedral complex.
Remark 4.12 (Tropical spectra).
In Definition 4.11, instead of using the whole collection
$\operatorname{Spec}(R)$
of prime ideals of a semiring
$R$
, it might be more useful to take just the set of tropical prime ideals as the underlying topological space, which could be called the tropical spectrum
$\operatorname{TSpec}(R)$
of
$R$
. For instance, consider
$R$
to be the quotient of
$\overline{\mathbb{R}}[x]$
by the congruence that identifies two polynomials if they correspond to the same function
$\overline{\mathbb{R}}\rightarrow \overline{\mathbb{R}}$
, such as
$x^{2}\oplus 1$
and
$x^{2}\oplus 7\odot x\oplus 1$
. In [Reference Giansiracusa and GiansiracusaGG16, Proposition 3.4.1], it is shown that the points of
$\operatorname{Spec}(R)$
are in bijection with intervals of
$\overline{\mathbb{R}}$
; the points of
$\operatorname{Spec}(\overline{\mathbb{R}}[x])$
are thus at least this complicated. In Example 4.13 we show that the set of tropical prime ideals of
$\overline{\mathbb{R}}[x]$
reflects better the classical situation.
Example 4.13 (Tropical prime ideals of
$\overline{\mathbb{R}}[x]$
).
We classify all tropical prime ideals in the semiring
$\overline{\mathbb{R}}[x]$
of tropical polynomials in one variable. For any
$a\in \overline{\mathbb{R}}$
, let
$J_{a}$
be the tropical ideal consisting of all tropical polynomials
$f$
whose variety
$V(f)\subseteq \overline{\mathbb{R}}$
contains
$a$
(see Example 4.6). If
$a=\infty$
, then
$J_{a}$
is the ideal of polynomials with no constant term. The fact that any two tropical polynomials
$f$
and
$g$
satisfy
$V(f\odot g)=V(f)\cup V(g)$
implies that
$J_{a}$
is a tropical prime ideal. We will prove that, in fact, these are the only proper nontrivial prime tropical ideals in
$\overline{\mathbb{R}}[x]$
.
Fix a prime tropical ideal
$P\subseteq \overline{\mathbb{R}}[x]$
, and let
$f=\bigoplus _{i=0}^{d}b_{i}\odot x^{i}\in P$
, where
$b_{d}\neq \infty$
. Let
$V(f)=\{a_{1},\ldots ,a_{s}\}$
. The multiplicity
$m_{i}$
of
$a_{i}$
is the maximum of
$j_{2}-j_{1}$
where both
$j_{1}$
and
$j_{2}$
achieve the minimum in
$\min _{j}(b_{j}+ja_{i})$
. Set
$g:=b_{d}\odot \prod _{i=1}^{s}(x\oplus a_{i})^{m_{i}}$
. The polynomial
$g$
is the tropical polynomial with smallest coefficients for which
$f(z)=g(z)$
for all
$z\in \overline{\mathbb{R}}$
; see, for example, [Reference Grigg and ManwaringGM07, §4]. Writing
$g=\bigoplus _{j=0}^{d}c_{j}\odot x^{j}$
, we have
$$\begin{eqnarray}c_{j}=\min \{b_{j}\}\cup \biggl\{\frac{b_{i}\cdot (k-j)+b_{k}\cdot (j-i)}{k-i}:0\leqslant i<j<k\leqslant d\biggr\},\end{eqnarray}$$
for any
$j$
, as stated in [Reference Grigg and ManwaringGM07, Lemma 3.3]. In particular,
$c_{0}=b_{0}$
and
$c_{d}=b_{d}$
. The two consequences of this formula that we will use are that
$c_{i}\leqslant b_{i}$
for all
$i$
, and, if
$c_{i}<b_{i}$
, then there is
$l$
with
$c_{i-1}-a_{l}=c_{i}=c_{i+1}+a_{l}$
.
We claim that
$g\odot f=g^{2}$
, and so
$g^{2}\in P$
. To show this we need to prove that for all
$0\leqslant k\leqslant 2d$
we have
$\min _{i+j=k}(b_{i}+c_{j})=\min _{i+j=k}(c_{i}+c_{j})$
. The inequality
${\geqslant}$
follows from the fact that
$b_{i}\geqslant c_{i}$
for all
$i$
. Suppose now that there is a pair
$(i,j)$
with
$c_{i}+c_{j}=\min _{i^{\prime }+j^{\prime }=i+j}(c_{i^{\prime }}+c_{j^{\prime }})<\min _{i^{\prime }+j^{\prime }=i+j}(b_{i^{\prime }}+c_{j^{\prime }})$
. This implies that
$c_{i}<b_{i}$
and
$c_{j}<b_{j}$
, so
$0<i,j<d$
and there must be
$l$
and
$l^{\prime }$
with
$c_{i-1}-a_{l}=c_{i}=c_{i+1}+a_{l}$
and
$c_{j-1}-a_{l^{\prime }}=c_{j}=c_{j+1}+a_{l^{\prime }}$
. Without loss of generality we may assume that
$a_{l}\leqslant a_{l^{\prime }}$
. We have
$c_{i}+c_{j}=c_{i-1}-a_{l}+c_{j+1}+a_{l^{\prime }}$
, so
$c_{i-1}+c_{j+1}\leqslant c_{i}+c_{j}$
. We may thus replace
$(i,j)$
by
$(i-1,j+1)$
and repeat. After a finite number of iterations we will have a pair
$(i,j)$
with
$c_{i}+c_{j}$
achieving the minimum
$\min _{i^{\prime }+j^{\prime }=i+j}(c_{i^{\prime }}+c_{j^{\prime }})$
and at least one of
$c_{i}=b_{i}$
or
$c_{j}=b_{j}$
, which is a contradiction. This proves that
$g^{2}=g\odot f$
.
Since
$P$
is prime, the fact that
$g^{2}\in P$
implies that
$x\oplus a\in P$
for some
$a=a_{i}$
. Multiplying by powers of
$x$
we see that
$P$
must contain all polynomials of the form
$x^{j}\oplus a\odot x^{j-1}$
. Furthermore, the vector elimination axiom forces
$P$
to contain all polynomials of the form
$a^{m}\odot x^{l}\oplus a^{l}\odot x^{m}$
. Since these polynomials generate the ideal
$J_{a}$
, we see that
$J_{a}\subseteq P$
. If
$P$
were strictly larger than
$J_{a}$
, it would contain a polynomial
$f^{\prime }$
with
$a\not \in V(f^{\prime })$
. The argument above then shows that
$x\oplus b\in P$
for some
$b\in V(f^{\prime })$
. But then the vector elimination axiom applied to
$x\oplus a$
and
$x\oplus b$
forces
$P$
to contain the constant
$\min (a,b)$
, which implies that
$P$
is the unit ideal.
We conclude this section by extending the notion of variety to ideals in a Cox semiring
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
. For a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}\cong \mathbb{R}^{n}$
and
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
, the coordinate ring of the corresponding stratum
$N(\unicode[STIX]{x1D70E})$
is
$$\begin{eqnarray}(S_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}\cong \overline{\mathbb{R}}[\unicode[STIX]{x1D70E}^{\bot }\cap M]\cong \overline{\mathbb{R}}[y_{1}^{\pm 1},\ldots ,y_{n-\dim (\unicode[STIX]{x1D70E})}^{\pm 1}].\end{eqnarray}$$
The variety of an ideal
$I\subseteq \overline{\mathbb{R}}[y_{1}^{\pm 1},\ldots ,y_{l}^{\pm 1}]$
is
$$\begin{eqnarray}V(I):=\{\mathbf{w}\in \mathbb{R}^{l}:\text{the min in }f(\mathbf{w})\text{ is achieved at least twice for all }f\in I\setminus \{\infty \}\}.\end{eqnarray}$$
For
$f\in \overline{\mathbb{R}}[y_{1}^{\pm 1},\ldots ,y_{l}^{\pm 1}]$
the initial term
$\operatorname{in}_{\mathbf{w}}(f)$
is defined as in Definition 3.1. Similarly, for an ideal
$I\subseteq \overline{\mathbb{R}}[y_{1}^{\pm 1},\ldots ,y_{l}^{\pm 1}]$
, its initial ideal is
$\operatorname{in}_{\mathbf{w}}(I):=\langle \operatorname{in}_{\mathbf{w}}(f):f\in I\rangle \subseteq \mathbb{B}[y_{1}^{\pm 1},\ldots ,y_{l}^{\pm 1}]$
.
Definition 4.14 (Varieties of ideals in Cox semirings).
Fix a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}\cong \mathbb{R}^{n}$
, and let
$I$
be a homogeneous ideal in
$S:=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
. We define
$$\begin{eqnarray}V_{\unicode[STIX]{x1D70E}}(I):=V((IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}})\subseteq N(\unicode[STIX]{x1D70E})\cong \mathbb{R}^{n-\dim (\unicode[STIX]{x1D70E})}\end{eqnarray}$$
and
$$\begin{eqnarray}V_{\unicode[STIX]{x1D6F4}}(I):=\coprod _{\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}}V_{\unicode[STIX]{x1D70E}}(I)\subseteq \coprod N(\unicode[STIX]{x1D70E})=\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}).\end{eqnarray}$$
When
$\unicode[STIX]{x1D6F4}$
is the positive orthant in
$\mathbb{R}^{n}$
, the tropical toric variety
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
is
$\operatorname{trop}(\mathbb{A}^{n})\cong \overline{\mathbb{R}}^{n}$
, and the Cox semiring
$S$
equals
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
with the trivial grading
$\deg (x_{i})=0$
for all
$i$
. In the next lemma we check that the new notion of variety agrees with that in (1), and also that the easy equivalences of the Fundamental Theorem [Reference Maclagan and SturmfelsMS15, Theorem 3.2.3] hold in this new setting.
Proposition 4.15. Let
$\unicode[STIX]{x1D6F4}$
be the positive orthant in
$N_{\mathbb{R}}$
, and let
$I$
be an ideal in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]=\operatorname{Cox}(\operatorname{trop}(\mathbb{A}^{n}))$
. Then
$$\begin{eqnarray}\displaystyle V_{\unicode[STIX]{x1D6F4}}(I)=V(I) & = & \displaystyle \{\!\mathbf{w}\in \overline{\mathbb{R}}^{n}\mid \text{for all }f\in I\text{ with }f(\mathbf{w})<\infty ,\text{ the minimum in }f(\mathbf{w})\nonumber\\ \displaystyle & & \displaystyle \quad \text{is achieved at least twice}\!\}\!.\nonumber\end{eqnarray}$$
Moreover, we have
$\mathbf{w}\in V(I)$
if and only if
$\operatorname{in}_{\mathbf{w}}(I)$
does not contain a monomial. Similarly, if
$I$
is an ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
and
$\mathbf{w}\in \mathbb{R}^{n}$
, then
$\mathbf{w}\in V(I)$
if and only if
$\operatorname{in}_{\mathbf{w}}(I)\neq \langle 0\rangle$
.
Proof. Let
$S=\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
. To show the containment
$V_{\unicode[STIX]{x1D6F4}}(I)\subseteq V(I)$
, fix
$\mathbf{w}\in V_{\unicode[STIX]{x1D70E}}(I)\subseteq N(\unicode[STIX]{x1D70E})\subseteq \overline{\mathbb{R}}^{n}$
for some
$\unicode[STIX]{x1D70E}\subseteq \{1,\ldots ,n\}$
. Suppose
$f\in I$
satisfies
$f(\mathbf{w})<\infty$
. Write
$f=f^{\unicode[STIX]{x1D70E}}+f^{\prime }$
, where every term in
$f^{\prime }$
is divisible by some variable
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
and no term in
$f^{\unicode[STIX]{x1D70E}}$
is. In particular,
$f^{\unicode[STIX]{x1D70E}}(\mathbf{w})<\infty$
and
$f^{\prime }(\mathbf{w})=\infty$
. We have
$f^{\unicode[STIX]{x1D70E}}\in (IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}\subseteq (S_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}\cong \overline{\mathbb{R}}[x_{i}^{\pm 1}:i\not \in \unicode[STIX]{x1D70E}]$
. Since
$\mathbf{w}\in V_{\unicode[STIX]{x1D70E}}(I)$
, the minimum in
$f^{\unicode[STIX]{x1D70E}}(\mathbf{w})$
is achieved at least twice, and so the same is true for the minimum in
$f(\mathbf{w})$
. This proves that
$V_{\unicode[STIX]{x1D70E}}(I)\subseteq V(I)$
.
Conversely, suppose that
$\mathbf{w}\in \overline{\mathbb{R}}^{n}$
has the property that the minimum in
$f(\mathbf{w})$
is achieved at least twice whenever
$f\in I$
with
$f(\mathbf{w})<\infty$
. Let
$\unicode[STIX]{x1D70E}:=\{i:w_{i}=\infty \}$
. For any
$f\in I$
with
$f(\mathbf{w})<\infty$
, write
$f=f^{\unicode[STIX]{x1D70E}}+f^{\prime }$
as above. We have
$f(\mathbf{w})=f^{\unicode[STIX]{x1D70E}}(\mathbf{w})$
, and the minimum in
$f(\mathbf{w})$
is achieved at least two terms in
$f^{\unicode[STIX]{x1D70E}}$
. As the images of
$f$
and
$f^{\unicode[STIX]{x1D70E}}$
agree in
$S_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle$
, it follows that
$\mathbf{w}\in V_{\unicode[STIX]{x1D70E}}(I)$
, and so
$\mathbf{w}\in V_{\unicode[STIX]{x1D6F4}}(I)$
. This completes the proof that
$V(I)=V_{\unicode[STIX]{x1D6F4}}(I)$
.
To prove the last assertion, note that, if
$I$
is an ideal in the semiring
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
(or
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
), since there is no cancelation in
$\mathbb{B}[x_{0},\ldots ,x_{n}]$
(or
$\mathbb{B}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
), the initial ideal
$\operatorname{in}_{\mathbf{w}}(I)$
contains a monomial if and only if there is
$f\in I$
with
$\mathbf{x}^{\mathbf{u}}=\operatorname{in}_{\mathbf{w}}(f)$
. This happens precisely when
$f(\mathbf{w})<\infty$
and the minimum in
$f(\mathbf{w})$
is achieved only once, i.e., when
$\mathbf{w}\not \in V(I)$
.◻
Subvarieties of tropical toric varieties can also be described in terms of the quotient construction (7).
Lemma 4.16. Fix a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}$
, and let
$I$
be a homogeneous ideal in
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
. The variety of
$I$
is
$$\begin{eqnarray}V_{\unicode[STIX]{x1D6F4}}(I)=(V(I)\setminus V(\operatorname{trop}(B_{\unicode[STIX]{x1D6F4}})))/\ker (Q^{T})\subseteq \operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}).\end{eqnarray}$$
In particular, if
$\unicode[STIX]{x1D6F4}$
is the fan of
$\mathbb{P}^{n}$
and
$I$
is a homogeneous ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
with respect to the standard grading, then
$V_{\unicode[STIX]{x1D6F4}}(I)\subseteq \operatorname{trop}(\mathbb{P}^{n})$
is equal to
$(V(I)\setminus \{(\infty ,\ldots ,\infty )\})/\mathbb{R}\mathbf{1}$
.
Proof. Write
$s$
for the number of rays of
$\unicode[STIX]{x1D6F4}$
,
$t=n-\dim (\operatorname{span}(\unicode[STIX]{x1D6F4}))$
, and
$m=s+t$
. Recall that the quotient construction (7) identifies the stratum
$N(\unicode[STIX]{x1D70E})$
with
$(\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{m}\setminus V(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}))/\ker (Q^{T})$
. By Proposition 4.15, a vector
$\mathbf{w}\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{m}$
has image
$\overline{\mathbf{w}}$
in
$V_{\unicode[STIX]{x1D70E}}(I)\subseteq N(\unicode[STIX]{x1D70E})$
if and only if
$0\notin \operatorname{in}_{\overline{\mathbf{w}}}((IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}})$
.
For any
$\mathbf{w}\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{m}$
, the image in
$(\mathbb{B}[x_{1},\ldots ,x_{m}]_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}\cong \mathbb{B}[y_{1}^{\pm 1},\ldots ,y_{n-\dim (\unicode[STIX]{x1D70E})}^{\pm 1}]$
of
$\operatorname{in}_{\mathbf{w}}(I)$
equals
$\operatorname{in}_{\overline{\mathbf{w}}}((IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}})$
. Thus we have
$0\in \operatorname{in}_{\overline{\mathbf{w}}}((IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}})$
if and only if some power of
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}$
lies in the ideal
$\operatorname{in}_{\mathbf{w}}(I)\mathbb{B}[x_{1},\ldots ,x_{m}]/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle$
. Since
$w_{i}=\infty$
for
$i\in \unicode[STIX]{x1D70E}$
, this happens if and only if there is
$f\in I$
with
$\operatorname{in}_{\mathbf{w}}(f)$
equal to some power of
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}$
, which is in turn equivalent to
$\mathbf{w}\not \in V(I)$
.◻
5 Gröbner complex for tropical ideals
In this section we define and study the Gröbner complex of a homogeneous tropical ideal, and use it to show that the variety of any tropical ideal is always the support of a finite polyhedral complex. We also show that tropical ideals satisfy the weak Nullstellensatz.
We start by extending the definition of a polyhedral complex to
$\overline{\mathbb{R}}^{n}$
. Recall that for
$\unicode[STIX]{x1D70E}\subseteq \{1,\ldots ,n\}$
we write
$\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n}=\{\mathbf{w}\in \overline{\mathbb{R}}^{n}:w_{i}=\infty \text{for }i\in \unicode[STIX]{x1D70E},~w_{i}\neq \infty \text{for }i\notin \unicode[STIX]{x1D70E}\}$
.
Definition 5.1 (Polyhedral complexes in
$\overline{\mathbb{R}}^{n}$
).
A polyhedral complex
$\unicode[STIX]{x1D6E5}$
in
$\overline{\mathbb{R}}^{n}$
is a collection of polyhedral complexes
$\unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70E}}\subseteq \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n}\cong \mathbb{R}^{n-|\unicode[STIX]{x1D70E}|}$
indexed by the set of all subsets
$\unicode[STIX]{x1D70E}\subseteq \{1,\ldots ,n\}$
, with the additional requirement that, if
$\unicode[STIX]{x1D70F}\subseteq \unicode[STIX]{x1D70E}$
and
$P$
is a polyhedron in
$\unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70F}}$
, then the closure of
$P$
in
$\overline{\mathbb{R}}^{n}$
intersected with
$\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n}$
is contained in a polyhedron of
$\unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70E}}$
. The support of any polyhedral complex is thus a closed subset of
$\overline{\mathbb{R}}^{n}$
. A polyhedral complex
$\unicode[STIX]{x1D6E5}$
is
$\mathbb{R}$
-rational if, for all
$\unicode[STIX]{x1D70E}\subseteq \{1,\ldots ,n\}$
, each polyhedron
$P\in \unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70E}}$
has the form
$P=\{\mathbf{x}\in \mathbb{R}^{n-|\unicode[STIX]{x1D70E}|}:A\mathbf{x}\leqslant \mathbf{b}\}$
with
$\mathbf{b}\in \mathbb{R}^{l}$
and
$A\in \mathbb{Q}^{l\times (n-|\unicode[STIX]{x1D70E}|)}$
for some
$l\geqslant 0$
.
This definition differs slightly from the one given in [Reference Itenberg, Katzarkov, Mikhalkin and ZharkovIKMZ16, §2.1], in that the closure of a polyhedron intersected with the boundary is not required to be a polyhedron in the complex, but just to be contained in one. A motivation for using this weaker condition is given in Example 5.3 below.
The following theorem guarantees the existence of the Gröbner complex for any homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
.
Theorem 5.2 (Gröbner complexes exist).
Let
$I\subseteq \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
be a homogeneous tropical ideal. There is a finite
$\mathbb{R}$
-rational polyhedral complex
$\unicode[STIX]{x1D6F4}(I)\subseteq \overline{\mathbb{R}}^{n+1}$
, whose support is all of
$\overline{\mathbb{R}}^{n+1}$
, such that, for any
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
and any
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
, the vectors
$\mathbf{w}$
and
$\mathbf{w}^{\prime }$
lie in the same cell of
$\unicode[STIX]{x1D6F4}(I)$
if and only if
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\mathbf{w}^{\prime }}(I)$
. The polyhedral complex
$\unicode[STIX]{x1D6F4}(I)$
is called the Gröbner complex of
$I$
.
Theorem 5.2 is a consequence of a slightly stronger result, stated in Theorem 5.6.
Example 5.3. Consider the ideal
$J:=\langle xy-xz\rangle \subseteq \mathbb{C}[x,y,z]$
, and let
$I:=\operatorname{trop}(J)\subseteq \overline{\mathbb{R}}[x,y,z]$
. The complex
$\unicode[STIX]{x1D6F4}(I)_{\emptyset }\subseteq \mathbb{R}^{3}$
has three cones, depending on whether
$w_{2}-w_{3}$
is positive, negative, or zero. The intersection of the closure of the cone
$\{\mathbf{w}\in \mathbb{R}^{3}:w_{2}>w_{3}\}$
with
$\overline{\mathbb{R}}_{\{1\}}^{3}$
is
$\{(\infty ,w_{2},w_{3}):w_{2}>w_{3}\}$
, even though
$\unicode[STIX]{x1D6F4}(I)_{\{1\}}$
consists of just one polyhedron, as
$\operatorname{in}_{\mathbf{w}}(f)=\infty$
for all
$f\in I$
and
$\mathbf{w}\in \overline{\mathbb{R}}_{\{1\}}^{3}$
.
We will make use of the following notation. The normal complex
${\mathcal{N}}(f)$
of a polynomial
$f\in \overline{\mathbb{R}}[x_{1},\ldots ,x_{l}]$
is the
$\mathbb{R}$
-rational polyhedral complex in
$\mathbb{R}^{l}$
whose polyhedra are the closures of the sets
$C[\mathbf{w}]=\{\mathbf{w}^{\prime }\in \mathbb{R}^{l}:\operatorname{in}_{\mathbf{w}^{\prime }}(f)=\operatorname{in}_{\mathbf{w}}(f)\}$
for
$\mathbf{w}\in \mathbb{R}^{l}$
.
Lemma 5.4. Let
$I\subseteq \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
be a homogeneous tropical ideal, and fix a degree
$d\geqslant 0$
. There is a finite
$\mathbb{R}$
-rational polyhedral complex
$\unicode[STIX]{x1D6F4}(I_{d})\subseteq \overline{\mathbb{R}}^{n+1}$
, whose support is all of
$\overline{\mathbb{R}}^{n+1}$
, such that, for any
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
and any
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
, the vectors
$\mathbf{w}$
and
$\mathbf{w}^{\prime }$
lie in the same cell of
$\unicode[STIX]{x1D6F4}(I_{d})$
if and only if
$\operatorname{in}_{\mathbf{w}}(I)_{d}=\operatorname{in}_{\mathbf{w}^{\prime }}(I)_{d}$
.
Proof. Fix
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
. As in the statement of Theorem 3.4, let
$\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
be the set of monomials in
$\operatorname{Mon}_{d}$
that are divisible by some variable
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
, and write
${\mathcal{M}}_{d}^{\unicode[STIX]{x1D70E}}$
for the valuated matroid
${\mathcal{M}}_{d}(I)/\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
. Let
$F_{d}^{\unicode[STIX]{x1D70E}}\in \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
be the tropical polynomial
$$\begin{eqnarray}F_{d}^{\unicode[STIX]{x1D70E}}:=\bigoplus _{B\text{ basis of }\text{}\underline{{\mathcal{M}}_{d}^{\unicode[STIX]{x1D70E}}}}p(B)\odot \biggl(\,\mathop{\prod }_{\mathbf{x}^{\mathbf{u}}\in \operatorname{Mon}_{d}\setminus (\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}\cup B)}\mathbf{x}^{\mathbf{u}}\biggr).\end{eqnarray}$$
We claim that, for
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
, we have
$\operatorname{in}_{\mathbf{w}}(I)_{d}=\operatorname{in}_{\mathbf{w}^{\prime }}(I)_{d}$
if and only if
$\operatorname{in}_{\mathbf{w}}(F_{d}^{\unicode[STIX]{x1D70E}})=\operatorname{in}_{\mathbf{w}^{\prime }}(F_{d}^{\unicode[STIX]{x1D70E}})$
. By replacing
$I$
by the ideal
$I^{\unicode[STIX]{x1D70E}}=\langle f^{\unicode[STIX]{x1D70E}}:f\in I\rangle \subseteq \overline{\mathbb{R}}[x_{i}:i\notin \unicode[STIX]{x1D70E}]$
introduced in the proof of Theorem 3.4, we may assume that
$\unicode[STIX]{x1D70E}=\emptyset$
. Indeed,
$F_{d}^{\unicode[STIX]{x1D70E}}(I)=F_{d}^{\emptyset }(I^{\unicode[STIX]{x1D70E}})$
up to tropical scaling, and
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\overline{\mathbf{w}}}(I^{\unicode[STIX]{x1D70E}})$
for any
$\mathbf{w}\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
, where
$\overline{\mathbf{w}}$
is the projection of
$\mathbf{w}$
to coordinates not in
$\unicode[STIX]{x1D70E}$
.
By Theorem 3.4, two vectors
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\emptyset }^{n+1}=\mathbb{R}^{n+1}$
satisfy
$\operatorname{in}_{\mathbf{w}}(I)_{d}=\operatorname{in}_{\mathbf{w}^{\prime }}(I)_{d}$
if and only if
$\operatorname{in}_{\hat{\mathbf{w}}}({\mathcal{M}}_{d})=\operatorname{in}_{\hat{\mathbf{w}}^{\prime }}({\mathcal{M}}_{d})$
, where
$\hat{\mathbf{w}}\in \mathbb{R}^{\operatorname{Mon}_{d}}$
is given by
$\hat{\mathbf{w}}_{\mathbf{x}^{\mathbf{u}}}=\mathbf{w}\cdot \mathbf{u}$
. Let
$r=\operatorname{rank}({\mathcal{M}}_{d}(I))$
. By Lemma 3.3, a set
$B\in \binom{\operatorname{Mon}_{d}}{r}$
is a basis of
$\operatorname{in}_{\hat{\mathbf{w}}}({\mathcal{M}}_{d}(I))$
if and only if
$B$
minimizes the function
$p(B)-\sum _{\mathbf{x}^{\mathbf{u}}\in B}\mathbf{w}\cdot \mathbf{u}$
, and thus if and only if
$B$
minimizes
$p(B)+\sum _{\mathbf{x}^{\mathbf{u}}\in \operatorname{Mon}_{d}\setminus B}\mathbf{w}\cdot \mathbf{u}$
. It follows that
$\operatorname{in}_{\hat{\mathbf{w}}}({\mathcal{M}}_{d}(I))=\operatorname{in}_{\hat{\mathbf{w}}^{\prime }}({\mathcal{M}}_{d}(I))$
if and only if the bases
$B$
of
$\text{}\underline{{\mathcal{M}}_{d}^{\unicode[STIX]{x1D70E}}}$
at which the minimum in
$F_{d}^{\emptyset }(\mathbf{w})$
is achieved are the same as for
$F_{d}^{\emptyset }(\mathbf{w}^{\prime })$
, which happens if and only if
$\operatorname{in}_{\mathbf{w}}(F_{d}^{\emptyset })=\operatorname{in}_{\mathbf{w}^{\prime }}(F_{d}^{\emptyset })$
.
We now set the polyhedral complex
$\unicode[STIX]{x1D6F4}(I_{d})_{\unicode[STIX]{x1D70E}}$
in
$\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
to be normal complex
${\mathcal{N}}(F_{d}^{\unicode[STIX]{x1D70E}})$
in
$\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}\cong \mathbb{R}^{n+1-|\unicode[STIX]{x1D70E}|}$
. It remains to check that the
$\unicode[STIX]{x1D6F4}(I_{d})_{\unicode[STIX]{x1D70E}}$
glue together to form an
$\mathbb{R}$
-rational polyhedral complex
$\unicode[STIX]{x1D6F4}(I_{d})$
in
$\overline{\mathbb{R}}^{n+1}$
: if
$\unicode[STIX]{x1D70F}\subseteq \unicode[STIX]{x1D70E}$
and
$P$
is a polyhedron in
$\unicode[STIX]{x1D6F4}(I_{d})_{\unicode[STIX]{x1D70F}}$
, then the closure of
$P$
in
$\overline{\mathbb{R}}^{n+1}$
intersected with
$\overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
should be contained in a polyhedron of
$\unicode[STIX]{x1D6F4}(I_{d})_{\unicode[STIX]{x1D70E}}$
. Again, it suffices to consider the case
$\unicode[STIX]{x1D70F}=\emptyset$
. Let
$C\subseteq \overline{\mathbb{R}}_{\emptyset }^{n+1}\cong \mathbb{R}^{n+1}$
be a maximal open cell of
$\unicode[STIX]{x1D6F4}(I_{d})_{\emptyset }$
, and suppose that
$(\mathbf{v}_{i})_{i\geqslant 0}$
is a sequence of vectors in
$C$
converging to
$\mathbf{w}\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
, where
$\mathbf{w}$
also lies in a maximal open cell of
$\unicode[STIX]{x1D6F4}(I_{d})_{\unicode[STIX]{x1D70E}}$
. Since
$C$
is a cell of
$\unicode[STIX]{x1D6F4}(I_{d})_{\emptyset }$
, the initial ideals
$\operatorname{in}_{\mathbf{v}_{i}}(I)$
are the same for any
$i$
. We will show that
$\operatorname{in}_{\mathbf{w}}(I)_{d}$
depends only on
$\operatorname{in}_{\mathbf{v}_{i}}(I)_{d}$
, which implies the desired containment.
By Theorem 3.4 and Lemma 3.3, the
$\overline{\mathbb{R}}$
-semimodule
$\operatorname{in}_{\mathbf{v}_{i}}(I)_{d}$
is determined by the matroid whose bases are the subsets
$B\in \binom{\operatorname{Mon}_{d}}{r}$
minimizing
$$\begin{eqnarray}p(B)-\mathop{\sum }_{\mathbf{u}\in B}\mathbf{v}_{i}\cdot \mathbf{u}.\end{eqnarray}$$
We claim that this minimum is achieved at a single basis
$B_{0}$
. Indeed, by Lemma 3.7, there is
$\mathbf{v}\in C$
with
$\operatorname{in}_{\mathbf{v}}(I)$
generated by monomials. Thus
$\operatorname{in}_{\mathbf{v}^{\prime }}(I)_{d}$
is spanned as an
$\overline{\mathbb{R}}$
-semimodule by monomials for all
$\mathbf{v}^{\prime }\in C$
, and so the corresponding initial matroid has only one basis
$B_{0}$
. Note that
$B_{0}$
does not depend on the choice of
$\mathbf{v}^{\prime }\in C$
.
The matroid of the
$\overline{\mathbb{R}}$
-semimodule
$\operatorname{in}_{\mathbf{w}}(I)_{d}$
has as bases the subsets of the form
$B^{\prime }\sqcup \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
with
$B^{\prime }\in \binom{\operatorname{Mon}_{d}\setminus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}{r^{\prime }}$
minimizing
$$\begin{eqnarray}p(B^{\prime }\sqcup B_{\operatorname{ Mon}_{d}^{\unicode[STIX]{x1D70E}}})-\mathop{\sum }_{\mathbf{u}\in B^{\prime }}\mathbf{w}\cdot \mathbf{u},\end{eqnarray}$$
where
$B_{\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}$
is any fixed basis of
$\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
, and
$r^{\prime }+|B_{\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}|$
is the rank of
${\mathcal{M}}_{d}(I)$
. Again, this minimum is achieved at only one subset
$B_{0}^{\prime }$
. We claim that
$B_{0}^{\prime }=B_{0}\setminus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
, which implies that
$\operatorname{in}_{\mathbf{w}}(I)_{d}$
depends only on
$\operatorname{in}_{\mathbf{v}_{i}}(I)_{d}$
, as desired.
To prove the claim, rewrite (9) as
$$\begin{eqnarray}p(B)-\mathop{\sum }_{\mathbf{u}\in B\setminus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}\mathbf{v}_{i}\cdot \mathbf{u}-\mathop{\sum }_{\mathbf{u}\in B\cap \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}\mathbf{v}_{i}\cdot \mathbf{u}.\end{eqnarray}$$
As
$i$
tends to
$\infty$
the coordinates of
$\mathbf{v}_{i}$
indexed by
$\unicode[STIX]{x1D70E}$
tend to
$\infty$
, and the others tend to finite values. The terms
$\mathbf{v}_{i}\cdot \mathbf{u}$
in (11) with
$\mathbf{u}\in B\cap \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
can thus be made arbitrarily large, while for
$\mathbf{u}\in B\setminus \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
they remain bounded. It follows that the basis
$B_{0}$
minimizing (11) contains as many elements of
$\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
as possible, and so
$|B_{0}\,\cap \,\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}\!|=r(\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}})$
. The intersection
$B_{0}\cap \operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
is then a basis
$B_{\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}$
of
$\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}$
. Furthermore, the set
$B_{0}\setminus B_{\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}$
must be the subset
$B_{0}^{\prime }$
minimizing (10), as otherwise
$B_{0}^{\prime }\sqcup B_{\operatorname{Mon}_{d}^{\unicode[STIX]{x1D70E}}}$
would yield a smaller value of (11) than
$B_{0}$
.◻
Lemma 5.5. Let
$I\subseteq \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
be a homogeneous tropical ideal. There is a degree
$D\geqslant 0$
such that, for any
$\mathbf{w},\mathbf{w}^{\prime }\in \mathbb{R}^{n+1}$
, if
$\operatorname{in}_{\mathbf{w}}(I)_{d}=\operatorname{in}_{\mathbf{w}^{\prime }}(I)_{d}$
for all
$d\leqslant D$
, then
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\mathbf{w}^{\prime }}(I)$
.
Proof. Let
$H_{I}$
be the Hilbert function of
$I$
. There is only a finite number of monomial ideals in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
with Hilbert function
$H_{I}$
, as the same is true in the polynomial ring
$K[x_{0},\ldots ,x_{n}]$
for any field
$K$
; see, for example, [Reference MaclaganMac01, Corollary 2.2]. Let
$D$
be the maximum degree of any generator of a monomial ideal with Hilbert function
$H_{I}$
.
Fix
$e>D$
, and let
$\unicode[STIX]{x1D6F4}(I_{e})_{\emptyset }$
be the polyhedral complex whose existence is guaranteed by Lemma 5.4. We will show that
$\unicode[STIX]{x1D6F4}(I_{e})_{\emptyset }$
is refined by the polyhedral complex
$\unicode[STIX]{x1D6F4}(I_{D})_{\emptyset }$
. For this, it suffices to show that the relative interior of any maximal face in
$\unicode[STIX]{x1D6F4}(I_{D})_{\emptyset }$
is contained in a maximal face of
$\unicode[STIX]{x1D6F4}(I_{e})_{\emptyset }$
. For generic
$\mathbf{v}$
in the relative interior of a maximal face in
$\unicode[STIX]{x1D6F4}(I_{e})_{\emptyset }$
, Lemma 3.7 implies that the initial ideal
$\operatorname{in}_{\mathbf{v}}(I)$
is a monomial ideal, which has Hilbert function
$H_{I}$
. Thus for all
$\mathbf{v}$
in this cell,
$\operatorname{in}_{\mathbf{v}}(I)_{e}$
is generated as a
$\mathbb{B}$
-semimodule by monomials. Our choice of
$D$
implies that these monomials are all divisible by some monomial in
$\operatorname{in}_{\mathbf{v}}(I)_{D}$
. This means that for generic
$\mathbf{v}$
and
$\mathbf{v}^{\prime }$
, if
$\operatorname{in}_{\mathbf{v}}(I)_{D}=\operatorname{in}_{\mathbf{v}^{\prime }}(I)_{D}$
, then
$\operatorname{in}_{\mathbf{v}}(I)_{e}=\operatorname{in}_{\mathbf{v}^{\prime }}(I)_{e}$
, which proves the desired containment.
To conclude, fix now specific
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\emptyset }^{n+1}\cong \mathbb{R}^{n+1}$
, and suppose that
$\operatorname{in}_{\mathbf{w}}(I)_{e}\neq \operatorname{in}_{\mathbf{w}^{\prime }}(I)_{e}$
for some
$e>D$
. This means that
$\mathbf{w}$
and
$\mathbf{w}^{\prime }$
live in different cells of the polyhedral complex
$\unicode[STIX]{x1D6F4}(I_{e})_{\emptyset }$
. As
$\unicode[STIX]{x1D6F4}(I_{e})_{\emptyset }$
is refined by
$\unicode[STIX]{x1D6F4}(I_{D})_{\emptyset }$
, this implies that
$\operatorname{in}_{\mathbf{w}}(I)_{D}\neq \operatorname{in}_{\mathbf{w}^{\prime }}(I)_{D}$
, and thus the proposition follows.◻
The following theorem is a strengthening of Theorem 5.2. It shows that the Gröbner complex of a homogeneous tropical ideal is, in each
$N(\unicode[STIX]{x1D70E})\cong \mathbb{R}^{n+1-|\unicode[STIX]{x1D70E}|}$
, dual to a regular subdivision of a convex polytope.
Theorem 5.6 (Gröbner complexes are normal complexes).
Let
$I\subseteq \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
be a homogeneous tropical ideal. For each
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
there is a tropical polynomial
$F^{\unicode[STIX]{x1D70E}}\in \overline{\mathbb{R}}[x_{i}:i\not \in \unicode[STIX]{x1D70E}]$
such that, for
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
, we have
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\mathbf{w}^{\prime }}(I)$
if and only if
$\operatorname{in}_{\mathbf{w}}(F^{\unicode[STIX]{x1D70E}})=\operatorname{in}_{\mathbf{w}^{\prime }}(F^{\unicode[STIX]{x1D70E}})$
. Moreover, the union of the normal complexes
${\mathcal{N}}(F^{\unicode[STIX]{x1D70E}})\subseteq \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}\cong \mathbb{R}^{n+1-|\unicode[STIX]{x1D70E}|}$
forms an
$\mathbb{R}$
-rational polyhedral complex
$\unicode[STIX]{x1D6F4}(I)$
in
$\overline{\mathbb{R}}^{n+1}$
.
Proof. For any
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
consider the ideal
$I^{\unicode[STIX]{x1D70E}}:=\langle f^{\unicode[STIX]{x1D70E}}:f\in I\rangle \subseteq \overline{\mathbb{R}}[x_{i}:i\notin \unicode[STIX]{x1D70E}]$
discussed in the proof of Theorem 3.4. Let
$D_{\unicode[STIX]{x1D70E}}\geqslant 0$
be the degree given by Lemma 5.5 for the ideal
$I^{\unicode[STIX]{x1D70E}}$
, and let
$D:=\max _{\unicode[STIX]{x1D70E}}D_{\unicode[STIX]{x1D70E}}$
. For any
$d\leqslant D$
, let
$F_{d}^{\unicode[STIX]{x1D70E}}$
be the tropical polynomial given in (8), and let
$F^{\unicode[STIX]{x1D70E}}:=\prod _{d\leqslant D}F_{d}^{\unicode[STIX]{x1D70E}}$
. Two vectors
$\mathbf{w},\mathbf{w}^{\prime }\in \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}$
satisfy
$\operatorname{in}_{\mathbf{w}}(F^{\unicode[STIX]{x1D70E}})=\operatorname{in}_{\mathbf{w}^{\prime }}(F^{\unicode[STIX]{x1D70E}})$
if and only if
$\operatorname{in}_{\mathbf{w}}(F_{d}^{\unicode[STIX]{x1D70E}})=\operatorname{in}_{\mathbf{w}^{\prime }}(F_{d}^{\unicode[STIX]{x1D70E}})$
for all
$d\leqslant D$
. The proof of Lemma 5.4 shows that this is the same as
$\operatorname{in}_{\overline{\mathbf{w}}}(I^{\unicode[STIX]{x1D70E}})_{d}=\operatorname{in}_{\overline{\mathbf{w}}^{\prime }}(I^{\unicode[STIX]{x1D70E}})_{d}$
for all
$d\leqslant D$
, where
$\overline{\mathbf{w}}$
and
$\overline{\mathbf{w}}^{\prime }$
are the projections of
$\mathbf{w}$
and
$\mathbf{w}^{\prime }$
to coordinates not in
$\unicode[STIX]{x1D70E}$
. By Lemma 5.5, this is equivalent to
$\operatorname{in}_{\overline{\mathbf{w}}}(I^{\unicode[STIX]{x1D70E}})=\operatorname{in}_{\overline{\mathbf{w}}^{\prime }}(I^{\unicode[STIX]{x1D70E}})$
, which is in turn the same as
$\operatorname{in}_{\mathbf{w}}(I)=\operatorname{in}_{\mathbf{w}^{\prime }}(I)$
.
Now, for any
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
, the normal complex
${\mathcal{N}}(F^{\unicode[STIX]{x1D70E}})\subseteq \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{n+1}\cong \mathbb{R}^{n+1-|\unicode[STIX]{x1D70E}|}$
is the
$\mathbb{R}$
-rational polyhedral complex obtained as the common refinement of the normal complexes
${\mathcal{N}}(F_{d}^{\unicode[STIX]{x1D70E}})$
with
$d\leqslant D$
. In Lemma 5.4 we showed that, for any fixed
$d$
, the complexes
${\mathcal{N}}(F_{d}^{\unicode[STIX]{x1D70E}})$
with
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,n\}$
form a polyhedral complex in
$\overline{\mathbb{R}}^{n+1}$
, and thus the same is true for their common refinements
${\mathcal{N}}(F^{\unicode[STIX]{x1D70E}})$
.◻
Example 5.7. Let
$J:=\langle x_{1}-x_{2},x_{3}-x_{4}\rangle \subseteq \mathbb{C}[x_{1},x_{2},x_{3},x_{4}]$
and
$I:=\operatorname{trop}(J)\subseteq \overline{\mathbb{R}}[x_{1},x_{2},x_{3},x_{4}]$
. In this case, since
$J$
is a linear ideal, the degree
$D$
given in the proof of Theorem 5.6 is equal to
$1$
. We have
$F^{\emptyset }=x_{1}x_{3}\oplus x_{1}x_{4}\oplus x_{2}x_{3}\oplus x_{2}x_{4}$
and
$F^{\{1,2\}}=x_{3}\oplus x_{4}$
. Note that the Gröbner complex of
$I$
in
$\overline{\mathbb{R}}_{\{1,2\}}^{4}$
is not equal to the normal complex of
$F^{\emptyset }|_{x_{1}=x_{2}=\infty }=\infty$
; the polynomial
$F^{\{1,2\}}$
is needed to get the comparison between
$w_{3}$
and
$w_{4}$
in this stratum.
We now use the existence of Gröbner complexes to show that the variety of a tropical ideal is an
$\mathbb{R}$
-rational polyhedral complex. We first prove that tropical ideals always admit finite tropical bases.
For a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}$
and a homogeneous
$f\in \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
, we set
$$\begin{eqnarray}V_{\unicode[STIX]{x1D6F4}}(f):=(V(f)\setminus V(\operatorname{trop}(B_{\unicode[STIX]{x1D6F4}})))/\ker (Q^{T})\subseteq \operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}).\end{eqnarray}$$
Definition 5.8 (Tropical bases).
Fix a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}$
, and let
$I\subseteq \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
be a homogeneous ideal. A set
$\{f_{1},f_{2},\ldots ,f_{l}\}\subseteq I$
of homogeneous polynomials forms a tropical basis for
$I$
if
$$\begin{eqnarray}V_{\unicode[STIX]{x1D6F4}}(I)=V_{\unicode[STIX]{x1D6F4}}(f_{1})\cap V_{\unicode[STIX]{x1D6F4}}(f_{2})\cap \cdots \cap V_{\unicode[STIX]{x1D6F4}}(f_{l}).\end{eqnarray}$$
Theorem 5.9. Any locally tropical ideal
$I\subseteq \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
has a finite tropical basis.
Proof. We first show this in the case where
$\unicode[STIX]{x1D6F4}$
is the fan of
$\mathbb{P}^{n}$
, so the Cox semiring is
$S=\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
, with the stronger assumption that
$I\subseteq S$
is a homogeneous tropical ideal in the sense of Definition 2.1. By Proposition 4.15, the variety
$V(I)\subseteq \overline{\mathbb{R}}^{n+1}$
is the union of those cells of
$\unicode[STIX]{x1D6F4}(I)$
corresponding to initial ideals not containing a monomial. Suppose that
$C$
is a cell of
$\unicode[STIX]{x1D6F4}(I)$
corresponding to an initial ideal
$\operatorname{in}_{\mathbf{w}}(I)$
that contains a monomial
$\mathbf{x}^{\mathbf{u}}$
of degree
$d$
. We will construct a homogeneous polynomial
$f\in I$
with
$V(f)\cap C=\emptyset$
. If
$C\subseteq \overline{\mathbb{R}}_{\unicode[STIX]{x1D70F}}^{n+1}$
for some nonempty
$\unicode[STIX]{x1D70F}\subseteq \{0,\ldots ,n\}$
, we can replace
$I$
by
$I^{\unicode[STIX]{x1D70F}}:=\langle g^{\unicode[STIX]{x1D70F}}:g\in I\rangle$
as in the proof of Theorem 3.4; if
$V(f^{\unicode[STIX]{x1D70F}})\subseteq \overline{\mathbb{R}}_{\unicode[STIX]{x1D70F}}^{n+1}$
does not intersect
$C$
, then
$V(f)\cap C=\emptyset$
. We may thus assume that
$C\subseteq \overline{\mathbb{R}}_{\emptyset }^{n+1}\cong \mathbb{R}^{n+1}$
.
By definition, the initial ideal
$\operatorname{in}_{\mathbf{w}}(I)$
is the same for any
$\mathbf{w}\in C$
. Fix a basis
$B$
of the initial matroid
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
. By Lemma 3.3 and Theorem 3.4,
$B$
is a basis of
$\text{}\underline{{\mathcal{M}}_{d}(I)}$
as well. Since
$\mathbf{x}^{\mathbf{u}}$
is a loop in
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
, we have
$\mathbf{x}^{\mathbf{u}}\not \in B$
. Let
$f\in I$
be the fundamental circuit
$H(B,\mathbf{x}^{\mathbf{u}})$
, as in (3).
We claim that, for any
$\mathbf{w}\in C$
, the initial form
$\operatorname{in}_{\mathbf{w}}(f)$
is equal to
$\mathbf{x}^{\mathbf{u}}$
. Suppose not. By Lemma 3.3 and Theorem 3.4, the support
$D$
of
$\operatorname{in}_{\mathbf{w}}(f)$
is a cycle in
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
. Note that
$\mathbf{x}^{\mathbf{u}}\in D$
, as otherwise
$D$
would be completely contained in the basis
$B$
, and
$B$
would contain a circuit of
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
. Since
$\mathbf{x}^{\mathbf{u}}$
is a loop in
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
, the vector elimination axiom in
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
implies that the subset
$D\setminus \{\mathbf{x}^{\mathbf{u}}\}$
must also be a cycle in
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
. But then
$D\setminus \{\mathbf{x}^{\mathbf{u}}\}$
is a nonempty cycle of
$M_{d}(\operatorname{in}_{\mathbf{w}}(I))$
contained in the basis
$B$
, which is a contradiction.
We have thus shown that, for any cell
$C\in \unicode[STIX]{x1D6F4}(I)$
not in the variety
$V(I)$
, there is a homogeneous polynomial
$f\in I$
such that
$V(f)\cap C=\emptyset$
. A tropical basis for
$I$
can then be obtained by taking the collection of all these polynomials corresponding to the finitely many cells
$C\in \unicode[STIX]{x1D6F4}(I)$
that are not in
$V(I)$
.
We now show that, if
$I\subseteq \overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
is a tropical ideal, then there exist
$f_{1},\ldots ,f_{l}\in I$
such that
$V(f_{1})\cap \cdots \cap V(f_{l})=V(I)\subseteq \mathbb{R}^{n}$
. We first claim that the homogenization
$\tilde{I} \subseteq \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
of
$I\cap \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a homogeneous tropical ideal. Indeed, note that, for any collection of monomials
$E$
in
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, the set of polynomials in
$I\cap \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
with support in
$E$
is the same as the set of polynomials in
$I$
with support in
$E$
, so
$I\cap \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
is a tropical ideal. Our claim follows since the homogenization of a tropical ideal is a homogeneous tropical ideal. Now, by the first part of the proof, there are homogeneous polynomials
$f_{1},\ldots ,f_{l}\in \tilde{I}$
with
$\operatorname{trop}(\tilde{I} )=V(f_{1})\cap \cdots \cap V(f_{l})\subseteq \overline{\mathbb{R}}^{n+1}$
. Moreover, for any homogeneous
$f\in \overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
, we have
$V(f|_{x_{0}=0})=V(f)\cap \{w_{0}=0\}$
. Thus, under the identification of
$\mathbb{R}^{n}$
with
$\{\mathbf{w}\in \mathbb{R}^{n+1}:w_{0}=0\}$
, we have
$V(I)\subseteq \mathbb{R}^{n}$
equal to
$V(\tilde{I} )\cap \{\mathbf{w}\in \mathbb{R}^{n+1}:w_{0}=0\}$
, and so
$V(I)=V(f_{1}|_{x_{0}=0})\cap \cdots \cap V(f_{l}|_{x_{0}=0})$
.
We finally consider the general case that
$I$
is a locally tropical ideal in a Cox semiring
$S=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))=\overline{\mathbb{R}}[x_{1},\ldots ,x_{m}]$
. Fix
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
. Then
$J:=(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}$
is a tropical ideal in
$(S_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}\cong \overline{\mathbb{R}}[y_{1}^{\pm 1},\ldots ,y_{p}^{\pm 1}]$
, where
$p=n-\dim (\unicode[STIX]{x1D70E})$
. By the previous paragraph we can find
$f_{1},\ldots ,f_{l}\in J$
such that
$V(J)\subseteq N(\unicode[STIX]{x1D70E})\cong \mathbb{R}^{p}$
is equal to the intersection of the hypersurfaces
$V(f_{1}),\ldots ,V(f_{l})$
. For each
$f_{i}$
there is
$g_{i}=f_{i}+f_{i}^{\prime }\in IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}$
with each monomial in
$f_{i}^{\prime }$
divisible by some
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
. There is
$e\geqslant 0$
such that
$h_{i}:=(\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}})^{e}\odot g_{i}\in I$
. By construction we have
$V_{\unicode[STIX]{x1D70E}}(h_{i})=V(f_{i})$
, and thus, taking the collection of all
$h_{i}$
as
$\unicode[STIX]{x1D70E}$
varies over all cones of
$\unicode[STIX]{x1D6F4}$
, we get a tropical basis for
$I$
.◻
We now prove the main result of this section. In order to state it, we extend the definition of a polyhedral complex to the case where the ambient space is any tropical toric variety.
Definition 5.10 (Polyhedral complexes in tropical toric varieties).
Fix a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}\cong \mathbb{R}^{n}$
.A polyhedral complex
$\unicode[STIX]{x1D6E5}$
in
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
consists of a polyhedral complex
$\unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70E}}$
in each orbit
$N(\unicode[STIX]{x1D70E})\cong \mathbb{R}^{n-\dim (\unicode[STIX]{x1D70E})}$
, with the additional requirement that, if
$\unicode[STIX]{x1D70F}$
is a face of
$\unicode[STIX]{x1D70E}$
and
$P$
is a polyhedron in
$\unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70F}}$
, then the closure of
$P$
in
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
intersected with
$N(\unicode[STIX]{x1D70E})$
is contained in a polyhedron of
$\unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70E}}$
. Note that, in particular, the support of any polyhedral complex is a closed subset of
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
. The polyhedral complex
$\unicode[STIX]{x1D6E5}$
is
$\mathbb{R}$
-rational if, for all
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
, any polyhedron
$P\in \unicode[STIX]{x1D6E5}_{\unicode[STIX]{x1D70E}}$
has the form
$P=\{\mathbf{x}\in \mathbb{R}^{n-\dim (\unicode[STIX]{x1D70E})}:A\mathbf{x}\leqslant \mathbf{b}\}$
with
$\mathbf{b}\in \mathbb{R}^{l}$
and
$A\in \mathbb{Q}^{l\times (n-\dim (\unicode[STIX]{x1D70E}))}$
for some
$l\geqslant 0$
.
Theorem 5.11 (Tropical varieties are polyhedral complexes).
Fix a fan
$\unicode[STIX]{x1D6F4}\subseteq N_{\mathbb{R}}$
, and let
$I\subseteq \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
be a locally tropical ideal. The variety
$V_{\unicode[STIX]{x1D6F4}}(I)\subseteq \operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
is the support of a finite
$\mathbb{R}$
-rational polyhedral complex in
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
.
Proof. By Theorem 5.9 we can find
$f_{1},\ldots ,f_{l}\in \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))=\overline{\mathbb{R}}[x_{1},\ldots ,x_{m}]$
, homogeneous with respect to the grading on
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
, such that
$V_{\unicode[STIX]{x1D6F4}}(I)=V_{\unicode[STIX]{x1D6F4}}(f_{1})\cap \cdots \cap V_{\unicode[STIX]{x1D6F4}}(f_{l})$
. Since the intersection of two finite
$\mathbb{R}$
-rational polyhedral complexes is a finite
$\mathbb{R}$
-rational polyhedral complex, it suffices to show that
$V_{\unicode[STIX]{x1D6F4}}(f_{i})$
is an
$\mathbb{R}$
-rational polyhedral complex in
$\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
for each
$i$
.
We first prove that
$V(f)\subseteq \overline{\mathbb{R}}^{m}$
is a finite
$\mathbb{R}$
-rational polyhedral complex for any polynomial
$f\in \overline{\mathbb{R}}[x_{1},\ldots ,x_{m}]$
. Note that it suffices to show this for the homogenization
$\tilde{f}$
of
$f$
, as
$V(f)\subseteq \overline{\mathbb{R}}^{m}$
equals
$V(\tilde{f})\cap \{w_{0}=0\}$
, under the identification of
$\{\mathbf{w}\in \overline{\mathbb{R}}^{m+1}:w_{0}=0\}$
with
$\overline{\mathbb{R}}^{m}$
. Let
$\hat{{\mathcal{N}}}(\tilde{f})\subseteq \overline{\mathbb{R}}^{m+1}$
be the union over all
$\unicode[STIX]{x1D70E}\subseteq \{0,\ldots ,m\}$
of the normal complexes
${\mathcal{N}}(\tilde{f}^{\unicode[STIX]{x1D70E}})\subseteq \overline{\mathbb{R}}_{\unicode[STIX]{x1D70E}}^{m+1}\cong \mathbb{R}^{m+1-|\unicode[STIX]{x1D70E}|}$
, where
$\tilde{f}^{\unicode[STIX]{x1D70E}}$
is obtained from
$\tilde{f}$
by setting
$x_{i}=\infty$
for all
$i\in \unicode[STIX]{x1D70E}$
. The variety
$V(\tilde{f})$
is a closed union of cells in
$\hat{{\mathcal{N}}}(\tilde{f})$
. The proof that
$V(\tilde{f})$
is actually a polyhedral complex proceeds as in the proof of Lemma 5.4, as this only requires
$I_{d}$
to determine a valuated matroid on
$\operatorname{Mon}_{d}$
, which is the case in degree
$d=\deg (\tilde{f})$
for the ideal generated by
$\tilde{f}$
.
Finally, since each
$f_{i}$
is homogeneous with respect to the grading on
$\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
, all
$V(f_{i})$
contain
$\ker (Q^{T})$
in their lineality spaces. As the quotient of an
$\mathbb{R}$
-rational polyhedral complex by a rational subspace of its lineality space is again an
$\mathbb{R}$
-rational polyhedral complex, the result follows from Lemma 4.16.◻
Remark 5.12. A corollary of Theorem 5.11 is that, if
$X$
is a subvariety of the torus
$T\cong (K^{\ast })^{n}$
determined by an ideal
$J\subseteq K[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
, then
$\operatorname{trop}(X)$
is the support of an
$\mathbb{R}$
-rational polyhedral complex in
$\mathbb{R}^{n}$
. The proof given here is essentially a simpler version of the one given in [Reference Maclagan and SturmfelsMS15, §2.5].
Remark 5.13. It would be desirable to have an analogue of the full Structure Theorem [Reference Maclagan and SturmfelsMS15, Theorem 3.3.5] for general tropical ideals. The Structure Theorem states that, if a variety
$X$
is irreducible, then the polyhedral complex with support
$\operatorname{trop}(X)$
is pure of dimension
$\dim (X)$
, and carries natural multiplicities that make it balanced. A version for tropical ideals will require generalizing the notion of irreducibility to this context.
The following example shows that the condition that the ideal
$I$
is a locally tropical ideal is crucial for Theorems 5.9 and 5.11.
Example 5.14 (Varieties of non-tropical ideals can be non-polyhedral).
Let
$\{f_{\unicode[STIX]{x1D6FC}}\}_{\unicode[STIX]{x1D6FC}\in A}$
be an arbitrary collection of tropical polynomials in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
, and consider the ideal
$I=\langle f_{\unicode[STIX]{x1D6FC}}\rangle _{\unicode[STIX]{x1D6FC}\in A}$
. The variety
$V(I)\subseteq \mathbb{R}^{n}$
satisfies
$V(I)=\bigcap _{\unicode[STIX]{x1D6FC}\in A}V(f_{\unicode[STIX]{x1D6FC}})$
, which shows that any intersection of tropical hypersurfaces can be the variety of an ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
. Moreover, note that any
$\mathbb{R}$
-rational half-hyperplane is equal to such an intersection. If
$H\subseteq \mathbb{R}^{n}$
is the half-hyperplane given by
$\mathbf{a}\cdot \mathbf{x}=c$
and
$\mathbf{b}\cdot \mathbf{x}\geqslant d$
with
$\mathbf{a},\mathbf{b}\in \mathbb{Z}^{n}$
and
$c,d\in \mathbb{R}$
, then
$$\begin{eqnarray}H=V(\mathbf{x}^{\mathbf{a}}\oplus c)\cap V(\mathbf{x}^{\mathbf{b}}\oplus (d-c)\odot \mathbf{x}^{\mathbf{a}}\oplus d).\end{eqnarray}$$
Since an infinite intersection of half-hyperplanes can result in a non-polyhedral set, the variety of an arbitrary ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
need not be polyhedral. For example, a closed disk contained in a plane in
$\mathbb{R}^{3}$
can be realized as the variety of an ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},x_{2}^{\pm 1},x_{3}^{\pm 3}]$
.
Example 5.15 (Non-realizable tropical ideals can have realizable varieties).
We now prove that the variety
$V(I)$
defined by the non-realizable tropical ideal
$I$
of Example 2.8 is the standard tropical line
$L$
in
$\operatorname{trop}(\mathbb{P}^{n})$
. This is the tropical linear space (or Bergman fan) of the uniform matroid
$U_{2,n+1}$
, which has a tropical basis consisting of all polynomials
$x_{i}\oplus x_{j}\oplus x_{k}$
for
$0\leqslant i<j<k\leqslant n$
. Indeed, any tropical polynomial of the form
$x_{i}\oplus x_{j}\oplus x_{k}$
is a circuit of
${\mathcal{M}}_{1}(I)$
and thus a polynomial in
$I$
, showing that
$V(I)\subseteq L$
. For the reverse inclusion, fix
$\mathbf{w}\in L$
, so
$\min (w_{0},w_{1},\ldots ,w_{n})$
is attained at least
$n$
times. We may assume that
$w_{0}\geqslant w_{1}=\cdots =w_{n}$
. The tropical ideal
$I$
is generated by the circuits of the valuated matroids
${\mathcal{M}}_{d}(I)$
, so it suffices to prove that, if
$d\geqslant 0$
and
$H$
is a circuit of
${\mathcal{M}}_{d}(I)$
, then the minimum in
$H(\mathbf{w})$
is achieved at least twice. Suppose that this minimum is achieved only once. After tropically scaling, the circuit
$H$
has the form
$H=\bigoplus _{\mathbf{u}\in C}\mathbf{x}^{\mathbf{u}}$
, with
$C$
an inclusion-minimal subset satisfying
$|C|>d-\deg (\gcd (C))+1$
. Our assumption implies that there exist
$\mathbf{x}^{\mathbf{u}_{0}}\in C$
and
$k\geqslant 0$
such that the only monomial in
$C$
not divisible by
$x_{0}^{k}$
is
$\mathbf{x}^{\mathbf{u}_{0}}$
. Let
$C^{\prime }:=C\setminus \{\mathbf{x}^{\mathbf{u}_{0}}\}$
. The monomial
$x_{0}\cdot \gcd (C)$
divides
$\gcd (C^{\prime })$
, so
$\deg (\gcd (C^{\prime }))\geqslant \deg (\gcd (C))+1$
. We then have
$|C^{\prime }|=|C|-1>d-\deg (\gcd (C))\geqslant d-\deg (\gcd (C^{\prime }))+1$
, contradicting the minimality of
$C$
.
Tropical ideals satisfy the following version of the Nullstellensatz, which is completely analogous to the classical version. This differs from the versions found in [Reference Shustin and IzhakianSI07, Reference Bertram and EastonBE17, Reference Joó and MinchevaJM17], and builds on the version in [Reference Grigoriev and PodolskiiGP14]. The special cases when the ambient tropical toric variety is affine space or projective space are presented in Corollary 5.17.
Theorem 5.16 (Tropical Nullstellensatz).
If
$I$
is a tropical ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
, then the variety
$V(I)\subseteq \mathbb{R}^{n}$
is empty if and only if
$I$
is the unit ideal
$\langle 0\rangle$
.
More generally, if
$\unicode[STIX]{x1D6F4}$
is a simplicial fan in
$N_{\mathbb{R}}$
and
$I\subseteq \operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
is a locally tropical ideal, then the variety
$V_{\unicode[STIX]{x1D6F4}}(I)\subseteq \operatorname{trop}(X_{\unicode[STIX]{x1D6F4}})$
is empty if and only if
$\operatorname{trop}(B_{\unicode[STIX]{x1D6F4}})^{d}\subseteq I$
for some
$d>0$
.
Proof. The ‘if’ direction of the first claim is immediate. For the ‘only if’ direction, suppose that
$I$
is a tropical ideal in
$\overline{\mathbb{R}}[x_{1}^{\pm 1},\ldots ,x_{n}^{\pm 1}]$
with
$V(I)\subseteq \mathbb{R}^{n}$
empty. Let
$J:=I\cap \overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, which is again a tropical ideal. The variety
$V(J)\cap \mathbb{R}^{n}$
is also empty. Indeed, for any
$\mathbf{w}\in \mathbb{R}^{n}$
there exists
$f\in I$
with the minimum in
$f(\mathbf{w})$
achieved only once, and then
$\mathbf{x}^{\mathbf{u}}f\in J$
for some monomial
$\mathbf{x}^{\mathbf{u}}$
, with the minimum in
$\mathbf{x}^{\mathbf{u}}f(\mathbf{w})$
again achieved only once. By Theorem 5.9, there exists a tropical basis
$\{f_{1},f_{2},\ldots ,f_{l}\}\subseteq J$
for
$J$
. Write
$d_{i}$
for the maximum degree of a monomial in
$f_{i}$
. For a fixed degree
$d\geqslant \max \{d_{i}\}$
, we consider the collection of tropical polynomials
$\{\mathbf{x}^{\mathbf{u}}f_{i}:|\mathbf{u}|\leqslant d-d_{i}\}$
. The coefficients of these polynomials can be considered as vectors in
$\overline{\mathbb{R}}^{\operatorname{Mon}_{{\leqslant}d}}$
, where
$\operatorname{Mon}_{{\leqslant}d}$
denotes the set of monomials of degree at most
$d$
. Let
${\mathcal{F}}_{d}\subseteq \overline{\mathbb{R}}^{\operatorname{Mon}_{{\leqslant}d}}$
be the collection of these vectors. By [Reference Grigoriev and PodolskiiGP14, Theorem 4(i)], since
$f_{1},\ldots ,f_{l}$
have no common solution in
$\mathbb{R}^{n}$
, for
$d\gg 0$
the set
$$\begin{eqnarray}\displaystyle {\mathcal{F}}_{d}^{\bot } & := & \displaystyle \{\!\mathbf{y}\in \mathbb{R}^{\operatorname{Mon}_{{\leqslant}d}}:\text{ the minimum in }\min (a_{\boldsymbol{ u}}+y_{\mathbf{u}}:\mathbf{u}\in \operatorname{Mon}_{{\leqslant}d})\text{ is achieved}\nonumber\\ \displaystyle & & \displaystyle \quad \text{at least twice for all }\mathbf{a}=(a_{\mathbf{u}})\in {\mathcal{F}}_{d}\!\}\nonumber\end{eqnarray}$$
is empty. Let
${\mathcal{J}}_{d}$
be the set of vectors in
$\overline{\mathbb{R}}^{\operatorname{Mon}_{{\leqslant}d}}$
corresponding to polynomials in
$J$
of degree at most
$d$
. As
${\mathcal{F}}_{d}\subseteq {\mathcal{J}}_{d}$
, the set
${\mathcal{J}}_{d}^{\bot }$
consisting of all
$\mathbf{y}\in \mathbb{R}^{\operatorname{Mon}_{{\leqslant}d}}$
for which the minimum in
$\min (a_{\mathbf{u}}+y_{\mathbf{u}}:\mathbf{u}\in \operatorname{Mon}_{{\leqslant}d})$
is achieved at least twice for all
$\mathbf{a}=(a_{\mathbf{u}})\in {\mathcal{J}}_{d}$
is also empty. Since
$J$
is a tropical ideal,
${\mathcal{J}}_{d}$
is the set of vectors of a valuated matroid
${\mathcal{M}}_{{\leqslant}d}(J)$
. The set
${\mathcal{J}}_{d}^{\bot }$
is the tropical linear space in
$\mathbb{R}^{\operatorname{Mon}_{{\leqslant}d}}$
defined by the linear tropical polynomials in
${\mathcal{J}}_{d}$
. It follows that
${\mathcal{J}}_{d}^{\bot }$
is empty if and only if the matroid
${\mathcal{M}}_{{\leqslant}d}(J)$
contains a loop. This means that
$J$
contains a monomial, and so
$I=\langle 0\rangle$
.
For the general case, suppose now that
$\unicode[STIX]{x1D6F4}$
is a simplicial fan, and the ideal
$I$
is a locally tropical ideal in
$S:=\operatorname{Cox}(\operatorname{trop}(X_{\unicode[STIX]{x1D6F4}}))$
with
$V_{\unicode[STIX]{x1D6F4}}(I)$
empty. For each cone
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
we then have
$V_{\unicode[STIX]{x1D70E}}(I)=\emptyset$
, and so, by the first part of the proof, the ideal
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}/\langle x_{i}\sim \infty :i\in \unicode[STIX]{x1D70E}\rangle )_{\mathbf{0}}=\langle 0\rangle$
. For all
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6F4}$
there is thus a polynomial of the form
$0\oplus f_{\unicode[STIX]{x1D70E}}\in (IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
, where every term of
$f_{\unicode[STIX]{x1D70E}}$
is divisible by a variable
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
.
We prove by induction on
$\dim (\unicode[STIX]{x1D70E})$
that
$I$
contains a power of
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}$
. When
$\unicode[STIX]{x1D70E}$
is the origin, the polynomial
$f_{\unicode[STIX]{x1D70E}}$
equals
$\infty$
, so
$0\in IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}$
, and thus some power of
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}$
lies in
$I$
. Suppose now that
$\dim (\unicode[STIX]{x1D70E})>0$
and the claim is true for all
$\unicode[STIX]{x1D70F}$
of smaller dimension. By induction, for all faces
$\unicode[STIX]{x1D70F}$
of
$\unicode[STIX]{x1D70E}$
, some power of
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70F}}}$
lies in
$I$
. Let
$l$
be the maximum such power over all
$\unicode[STIX]{x1D70F}\preccurlyeq \unicode[STIX]{x1D70E}$
. It suffices to show that
$f_{\unicode[STIX]{x1D70E}}$
can be chosen so that every monomial in its support is divisible by
$x_{i}^{l}$
for some
$i\in \unicode[STIX]{x1D70E}$
. Indeed, since
$(\mathbf{x}^{\hat{\unicode[STIX]{x1D70F}}})^{l}\in I$
for all faces
$\unicode[STIX]{x1D70F}$
of
$\unicode[STIX]{x1D70E}$
, as
$\unicode[STIX]{x1D70E}$
is a simplicial cone, we have
$x_{i}^{l}\in IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}$
for all
$i\in \unicode[STIX]{x1D70E}$
, and so every term of
$f_{\unicode[STIX]{x1D70E}}$
is in
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
. As
$0\oplus f_{\unicode[STIX]{x1D70E}}\in (IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
, we can repeatedly apply the vector elimination axiom in
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
to conclude that
$0\in (IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
, and thus some power of
$\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}$
lies in
$I$
.
To finish the proof, we now show that we may choose
$f_{\unicode[STIX]{x1D70E}}$
so that every monomial in its support is divisible by
$x_{i}^{l}$
for some
$i\in \unicode[STIX]{x1D70E}$
. Suppose that this is not possible. For any monomial
$\mathbf{x}^{\mathbf{u}}$
in
$S_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}}$
, let its
$\unicode[STIX]{x1D70E}$
-degree
$\deg _{\unicode[STIX]{x1D70E}}(\mathbf{x}^{\mathbf{u}})$
be its degree in just the variables
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
, i.e.,
$\deg _{\unicode[STIX]{x1D70E}}(\mathbf{x}^{\mathbf{u}}):=\sum _{i\in \unicode[STIX]{x1D70E}}u_{i}$
. Fix a choice of
$f_{\unicode[STIX]{x1D70E}}$
, which must then have a term not divisible by any
$x_{i}^{l}$
with
$i\in \unicode[STIX]{x1D70E}$
. We may assume that
$f_{\unicode[STIX]{x1D70E}}$
has been chosen so that the minimum
$\unicode[STIX]{x1D70E}$
-degree
$l^{\prime }$
among all its terms is as large as possible, and, furthermore, that
$f_{\unicode[STIX]{x1D70E}}$
has as few terms as possible of
$\unicode[STIX]{x1D70E}$
-degree equal to
$l^{\prime }$
. Fix a term
$a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}$
of
$f_{\unicode[STIX]{x1D70E}}$
of
$\unicode[STIX]{x1D70E}$
-degree
$l^{\prime }$
. As every term of
$f_{\unicode[STIX]{x1D70E}}$
is divisible by a variable
$x_{i}$
with
$i\in \unicode[STIX]{x1D70E}$
, all the terms of
$a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}\odot (0\oplus f_{\unicode[STIX]{x1D70E}})$
except for
$a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}$
have
$\unicode[STIX]{x1D70E}$
-degree at least
$l^{\prime }+1$
. The vector elimination axiom in
$(IS_{\mathbf{x}^{\hat{\unicode[STIX]{x1D70E}}}})_{\mathbf{0}}$
applied to the polynomials
$0\oplus f_{\unicode[STIX]{x1D70E}}$
and
$a_{\mathbf{u}}\odot \mathbf{x}^{\mathbf{u}}\odot (0\oplus f_{\unicode[STIX]{x1D70E}})$
then produces a polynomial of the form
$0\oplus f_{\unicode[STIX]{x1D70E}}^{\prime }$
where every term of
$f_{\unicode[STIX]{x1D70E}}^{\prime }$
has
$\unicode[STIX]{x1D70E}$
-degree at least
$l^{\prime }$
, and
$f_{\unicode[STIX]{x1D70E}}^{\prime }$
has fewer terms than
$f_{\unicode[STIX]{x1D70E}}$
of
$\unicode[STIX]{x1D70E}$
-degree equal to
$l^{\prime }$
. This contradicts our choice of
$f_{\unicode[STIX]{x1D70E}}$
, concluding the proof.◻
Theorem 5.16 has the following immediate corollary.
Corollary 5.17. If
$I$
is a locally tropical ideal in
$\operatorname{Cox}(\operatorname{trop}(\mathbb{A}^{n}))=\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
, then
$V(I)\subseteq \overline{\mathbb{R}}^{n}$
is empty if and only if
$I=\langle 0\rangle$
.
If
$I$
is a homogeneous tropical ideal in
$\overline{\mathbb{R}}[x_{0},\ldots ,x_{n}]$
, then
$V(I)\subseteq \operatorname{trop}(\mathbb{P}^{n})$
is empty if and only if there exists
$d>0$
such that
$\langle x_{0},\ldots ,x_{n}\rangle ^{d}\subseteq I$
.
Remark 5.18. The hypothesis that
$I$
is a locally tropical ideal is essential in Theorem 5.16. Consider, for example, the ideal
$I=\langle x\oplus 0,x\oplus 1\rangle \subseteq \overline{\mathbb{R}}[x]$
. Then
$V(I)\subseteq \overline{\mathbb{R}}$
is empty but
$I$
is not the unit ideal; any polynomial of the form
$f\odot (x\oplus 0)\oplus g\odot (x\oplus 1)$
involves a monomial divisible by
$x$
.
As a simple application of the tropical Nullstellensatz, we classify all maximal tropical ideals of the semiring
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
.
Example 5.19. We show that maximal tropical ideals of the semiring
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
are in one-to-one correspondence with points in
$\overline{\mathbb{R}}^{n}$
. Indeed, for any
$\mathbf{a}\in \overline{\mathbb{R}}^{n}$
, let
$J_{\mathbf{a}}$
be the tropical ideal consisting of all polynomials that tropically vanish on
$\mathbf{a}$
(see Example 4.6). If a tropical ideal
$I$
satisfies
$V(I)\neq \emptyset$
, then
$I$
must be contained in one of the
$J_{\mathbf{a}}$
. On the other hand, if
$V(I)=\emptyset$
, then, by the tropical Nullstellensatz,
$I$
must be the unit ideal
$\langle 0\rangle$
. It follows that the
$J_{\mathbf{a}}$
are the only maximal tropical ideals of
$\overline{\mathbb{R}}[x_{1},\ldots ,x_{n}]$
.
Acknowledgements
We thank Jeff Giansiracusa for several useful conversations, and Paolo Tripoli for insight into Example 5.14. The first author was partially supported by EPSRC grant EP/I008071/1 and a Leverhulme Trust International Academic Fellowship. The second author was supported by the Research Council of Norway grant 239968/F20.
