The vertex ideal of a lattice

../

corollary_4_7: States that the radicals of the product ideal and the vertex ideal of a lattice coincide and that the top-dimensional part of the product ideal is contained in that of the vertex ideal.

corollary_4_8: States that for every lattice of dimension two the top-dimensional parts of the product ideal and the vertex ideal are equal, and records that this fails in dimension three.

definition_4_1: Defines the product ideal of a lattice as the monomial ideal generated by the products x^u x^v over the Graver basis elements u - v, and records that it is contained in the vertex ideal, sometimes strictly.

proposition_2_1: States that lowering a positive coordinate of a vertex of a lattice fiber gives a vertex of its own fiber, so the non-vertices of all fibers are the exponents of a monomial ideal, the vertex ideal of the lattice.

proposition_4_2: States that if L = ker(A) intersected with Z^n for a unimodular matrix A, the product ideal equals the vertex ideal and both equal the Stanley–Reisner ideal of the matroid complex of the lattice.

proposition_4_3: States that the product ideal equals the vertex ideal for every two-dimensional lattice in Z^2, and records the paper's examples showing that this fails for a two-dimensional lattice in Z^3 and in dimension three.

theorem_2_10: States that the radical of the vertex ideal of a rank m lattice is the intersection of the primes generated by the variables indexed by the linearly independent m-subsets of rows of a lattice-basis matrix, that is the Stanley–Reisner ideal of a matroid complex.

theorem_2_3: States that the vertex ideal of a lattice equals the intersection of the initial ideals of its lattice ideal over all generic weight vectors, which gives a first, finite algorithm for computing it.

theorem_2_8: States that the vertex ideal of a lattice is generated by the monomials lcm of x^alpha_j over the supports of the positive circuits of its ordered Graver basis, so it can be computed from the Graver basis alone.

theorem_3_11: States that for a codimension two lattice ideal with L = ker(A) meeting the nonnegative orthant only at 0, an embedded prime P_tau of the vertex ideal has cone{a_i : i in tau} not a face of the cone of all columns, so the irrelevant maximal ideal is not associated.

theorem_3_14: States that some toric ideal of codimension three has a Gröbner cone with five facets, refuting a conjecture of Sturmfels and Thomas that such cones have at most four facets; the witness is A = [15, 247, 248, 345].

theorem_3_8: States that the vertex ideal is the intersection of the irreducible ideals generated by the powers x_i^(u_i+1), i outside tau, over all critical polyhedra Q_u^tau-bar, after characterizing its standard monomials and standard pairs through vertices at the origin of lattice-point hulls.

---

Serkan Hoşten, Diane Maclagan, "The vertex ideal of a lattice," arXiv:math/0012197 (2000); Adv. in Appl. Math. 29 (2002), no. 4, 521-538, DOI 10.1016/S0196-8858(02)00030-1.

The copy read for this card is arXiv:math/0012197v1 (20 December 2000), 19 pages, the only arXiv version; the journal version (Crossref record read) was not compared, and the labels cited here are v1's. The arXiv record carries no license field, so arXiv's assumed license applies (arXiv:math/0012197), every other right reserved.

Overview

Question and construction. Hoşten and Maclagan associate to an arbitrary rank-$m$ sublattice $\mathcal L\subseteq\mathbf Z^n$ a monomial ideal encoding all vertices of all lattice fibers. For $u\in\mathbf N^n$, Definition 1.1 sets

$$P_u=\operatorname{conv}\{v\in\mathbf N^n:u-v\in\mathcal L\}.$$

Proposition 2.1 proves that the union of the sets $\operatorname{Vert}(P_u)$ is an order ideal in $\mathbf N^n$; consequently there is a monomial ideal $V_{\mathcal L}\subseteq k[x_1,\ldots,x_n]$ such that $x^v\notin V_{\mathcal L}$ exactly when $v$ is a vertex of its fiber. The rational-polyhedral finiteness of the vertex sets is cited background from Theorem 16.1 of reference [9], not a result proved here.

Descriptions and computation of the vertex ideal. After defining the lattice ideal

$$I_{\mathcal L}=\langle x^u-x^v:u-v\in\mathcal L\rangle$$

in Definition 2.2, Theorem 2.3 identifies

$$V_{\mathcal L}=\bigcap_{\omega\ \mathrm{generic}}\operatorname{in}_{\omega}(I_{\mathcal L}).$$

The proof uses the fact that standard monomials of a generic initial ideal are the unique minimizers of the corresponding weight functional on their fibers. This gives a finite but potentially very inefficient algorithm; Example 2.4 exhibits a family with at least $n!$ initial ideals, while Remark 2.13 obtains the required intersection from only $n2^{n-1}$ of them.

Definition 2.5 introduces the Graver basis $\operatorname{Gr}_{\mathcal L}$ as the union of the Hilbert bases in all orthants. Lemma 2.6 converts a positive dependence $\sum_i c_i(\alpha_i-\beta_i)=0$ among Graver elements into a monomial $\operatorname{lcm}_i(x^{\alpha_i})\in V_{\mathcal L}$. Corollary 2.7 proves that every minimal generator arises this way. Theorem 2.8 sharpens this to the generating formula

$$V_{\mathcal L}=\left\langle\operatorname{lcm}_{j\in\tau}x^{\alpha_j}:\tau\text{ supports a positive circuit of }\operatorname{Gr}_{\mathcal L}\right\rangle.$$

Thus the main constructive method is to compute the Graver basis and its positive circuits, rather than the entire Gröbner fan.

Radical, matroid, and enumeration. For a lattice-basis matrix $B\in\mathbf Z^{n\times m}$ with rows $b_i$, Proposition 2.9 records the cited Gröbner-theoretic fact that the radical of a generic initial ideal is the Stanley–Reisner ideal of the corresponding simplicial complex $\Delta_\omega$. Theorem 2.10 then proves

$$\sqrt{V_{\mathcal L}}=\bigcap_{\substack{\sigma\subseteq[n],\ |\sigma|=m\\\{b_i:i\in\sigma\}\text{ linearly independent}}} \langle x_i:i\in\sigma\rangle.$$

Corollary 2.12 reformulates this as the Stanley–Reisner ideal of the matroid complex $\Delta(\mathcal M(\mathcal L))$. Proposition 2.14 identifies the multigraded Hilbert series of $S/V_{\mathcal L}$ with the generating series for vertices of all fibers. For $\mathcal L=\ker(A)\cap\mathbf Z^n$ with $A=[a_1,\ldots,a_n]$ a single row of natural numbers, Proposition 2.15 deduces that the number of vertices in the fiber of degree $b$ is eventually periodic, with period dividing $\operatorname{lcm}(a_1,\ldots,a_n)$.

Associated primes and standard pairs. Lemma 3.1 shows that every associated prime of $V_{\mathcal L}$ occurs among the associated primes of some generic initial ideal, and that the minimal primes are exactly the union of the minimal primes of those initial ideals; Example 3.2 shows strictness for associated primes in general. Proposition 3.3 gives codimension at most $\min(n,2^m-1)$. Proposition 3.5 characterizes standard pairs directly through persistence of the vertex property. With

$$Q_u=\{z\in\mathbf R^m:Bz\leq u\},\qquad R_u=\operatorname{conv}(Q_u\cap\mathbf Z^m),$$

Theorem 3.6 says that $x^u$ is standard precisely when the origin is a vertex of $R_u$, and characterizes a standard pair $(x^u,\tau)$ by retaining this property after the inequalities indexed by $\tau$ are removed, but losing it when any further inequality is removed. Definition 3.7 calls $Q_u$ critical when the origin is a vertex of $R_u$ but of no $R_{u+e_i}$ (the print writes the range as $i=1,\ldots,k$), and Theorem 3.8 indexes the irreducible primary decomposition, called irredundant in the text before Definition 3.7, by the critical polyhedra $Q_u^{\bar\tau}$:

$$V_{\mathcal L}=\bigcap_{Q_u^{\bar\tau}\ \mathrm{critical}} \langle x_i^{u_i+1}:i\in\bar\tau\rangle.$$

For a codimension two lattice ideal $I_{\mathcal L}$ with $\mathcal L=\ker(A)\cap\mathbf Z^n$ and $\mathcal L\cap\mathbf N^n=\{0\}$, the planar polygon argument of Lemma 3.9 yields Theorem 3.11: if $\mathcal P_\tau=\langle x_i:i\notin\tau\rangle$ is an embedded prime of $V_{\mathcal L}$, then the cone generated by the columns $a_i$, $i\in\tau$, of $A$ is not a face of the cone generated by all the columns; so $\langle x_1,\ldots,x_n\rangle$ is not an associated prime of $V_{\mathcal L}$. Remark 3.12 and Example 3.13 show that this fails in higher codimension. The explicit lattice in Example 3.13 is then used in Theorem 3.14 to prove the existence of a codimension-three toric ideal having a Gröbner cone with five facets, refuting a conjecture of Sturmfels and Thomas that every such cone has at most four (numbered 6.1 on p. 2 and 6.2 on p. 14). Example 3.15 is a separate computer-produced example with six facets; it is presented as computation, not as a general theorem.

The product ideal. Definition 4.1 introduces the more readily computed ideal

$$P_{\mathcal L}=\langle x^ux^v:u-v\in\operatorname{Gr}_{\mathcal L}\rangle,$$

and immediately gives $P_{\mathcal L}\subseteq V_{\mathcal L}$; the example following the definition shows that containment can be strict. Proposition 4.2 proves equality, with both ideals equal to the relevant matroid ideal, when $\mathcal L=\ker(A)\cap\mathbf Z^n$ and $A$ is unimodular. Proposition 4.3 proves equality for a rank-two lattice in the ambient lattice $\mathbf Z^2$, while Example 4.4 shows failure in rank three. Lemma 4.5 and Proposition 4.6 establish compatibility of Graver bases, vertex ideals, and product ideals with coordinate projection/localization when lattice rank is preserved. Corollary 4.7 proves $\sqrt{P_{\mathcal L}}=\sqrt{V_{\mathcal L}}$ and $\operatorname{Top}(P_{\mathcal L})\subseteq\operatorname{Top}(V_{\mathcal L})$; Corollary 4.8 upgrades the latter to equality for rank-two lattices. These statements concern radicals or top-dimensional components and do not assert $P_{\mathcal L}=V_{\mathcal L}$ in general.

Relation to E963

Let $X=\{a_1,\ldots,a_n\}\subset\mathbf R$ be the set in E963, with a fixed ordering, and put

$$\mathcal L_X=\left\{z\in\mathbf Z^n:\sum_{i=1}^n z_i a_i=0\right\}.$$

This is a saturated sublattice of $\mathbf Z^n$. A subset indexed by $S\subseteq[n]$ is dissociated exactly when

$$\mathcal L_X\cap\{z\in\{-1,0,1\}^n:\operatorname{supp}(z)\subseteq S\}=\{0\};$$

indeed, a nonzero such vector is precisely an equality between two distinct subset sums supported on $S$.

The radical results discard precisely the bounded-coefficient information central to E963. Corollary 4.7 and Theorem 2.10 identify $\sqrt{P_{\mathcal L_X}}=\sqrt{V_{\mathcal L_X}}$ with a matroid Stanley–Reisner ideal. Its faces avoid arbitrary integer relations, whereas dissociation only forbids relations with coefficients in $\{-1,0,1\}$. Thus the matroid complex yields only subsets of $X$ that are linearly independent over $\mathbf Q$; for a set of integers these have at most one element, so it cannot by itself imply a logarithmic bound. Likewise, Proposition 2.14 counts all fiber vertices but supplies no estimate for squarefree vertices of a prescribed degree. The paper's ideals therefore give computational machinery for finite examples, but the paper proves neither $f(n)\geq\lfloor\log_2 n\rfloor$ nor a construction violating it.

Results

Labels and page numbers are those of the arXiv print (pp. 1--19).

• Proposition 2.1 (p. 3), with Definition 1.1 (p. 1): the vertices of all fibers form an order ideal, so the vertex ideal $V_{\mathcal L}$ exists.
• Theorem 2.3 (p. 3): $V_{\mathcal L}$ is the intersection of the generic initial ideals of the lattice ideal.
• Theorem 2.8 (p. 5), with Definition 2.5, Lemma 2.6 and Corollary 2.7 (pp. 4--5): generators of $V_{\mathcal L}$ from the positive circuits of the Graver basis.
• Theorem 2.10 (p. 6), with Corollary 2.12 (p. 7): the radical of $V_{\mathcal L}$ is the Stanley–Reisner ideal of a matroid complex.
• Theorem 3.8 (p. 11), with Theorem 3.6 (p. 10): standard pairs and the irreducible primary decomposition through critical polyhedra.
• Theorem 3.11 (p. 13), with Lemma 3.9 (p. 11): in codimension two the irrelevant ideal is not associated to $V_{\mathcal L}$; Example 3.13 (p. 14) shows failure in codimension three.
• Theorem 3.14 (pp. 14--15): a codimension three toric ideal with a Gröbner cone with five facets.
• Definition 4.1 (p. 15): the product ideal $P_{\mathcal L}\subseteq V_{\mathcal L}$.
• Proposition 4.2 (p. 16): $P_{\mathcal L}=V_{\mathcal L}$ for a unimodular matrix.
• Proposition 4.3 (p. 16): $P_{\mathcal L}=V_{\mathcal L}$ for a two-dimensional lattice in $\mathbf Z^2$.
• Corollary 4.7 (p. 18), with Lemma 4.5 and Proposition 4.6 (pp. 17--18): equal radicals of $P_{\mathcal L}$ and $V_{\mathcal L}$.
• Corollary 4.8 (p. 18): equal top-dimensional parts for a two-dimensional lattice.

Read status. Claims checked for the results above, read clause by clause on the print, with their proofs read; the computer calculations of Examples 3.13, 3.15 and 4.4 and of Theorem 3.14 were not redone.

Bears on

• Problem 963: background only. The paper does not mention dissociated sets, subset sums or the problem. The section above derives from Definition 4.1 that a subset $S$ of $X$ is dissociated exactly when $x_S$ is not in the product ideal of the lattice of integer relations among the elements of $X$, and from Proposition 2.1 and Theorem 2.8 a sufficient vertex test; the paper bounds the degree of no such standard monomial, so it neither proves nor refutes the problem's lower bound.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.