# Computing toric ideals via saturation and Groebner bases of toric ideals

About a month ago I asked this question on math.stackexchange and unfortunately there was no response. Perhaps someone here knows the answer.

Let $A \in \mathbb{Z}^{m \times n}$ be a matrix of full row rank and $m < n$. Let $\ker A = \{ u \in \mathbb{Z}^n \; | \; Au = 0\}$. For any $u \in \ker A$ vectors $u_+$ and $u_-$ can be defined as follows: $$u_+ = \sum_{u_i > 0} u_i e_i,$$ $$u_- = - \sum_{u_i < 0} u_i e_i.$$ The ideal $I_A = \langle \{ x^{u_+} - x^{u_-} \; | \; u \in \ker A \} \rangle$ is no doubt toric. The well-known way to construct $I_A$ is the following one. Let $L = \{ l^1,...,l^r \}$ $(r = n - m)$ be a basis for $\ker A$ and $$I_L = \langle \{ x^{l^i_+} - x^{l^i_-} \; | \; i = \overline{1,r}\; \} \rangle$$ then $$I_A = I_L : (x_1 \cdots x_n)^\infty.$$ My questions are the following:

1) Is it right that $I_L$ is always $I_A$-primary (i.e. $I_A = \sqrt{I_L}$)? If so is there any relatively easy proof of it? If not what is the case when this statement may fail?

2) Are there any reasonable bounds on the size of a reduced Groebner basis of $I_A$ (for example for grevlex ordering)? Possible bounds in terms of matrix $A$ (or equivalently in terms of its basis $L$) would be much appreciated.

Any hint or reference would help a lot.

-

The answer to your first question is "No". I think it's almost always No. You can already see this in the well-known twisted cubic example. Here $A = \begin{pmatrix}1& 1& 1& 1\\ 0& 1& 2& 3\\ \end{pmatrix}$ and take, for example, the lattice basis {(1,-2,1,0),(0,1,-2,1)}. The corresponding binomial ideal $(-b^{2}+a c,-c^{2}+b d)$ is not primary. It has two components: $I_L$ and the ideal $(b,c)$

-

In general upper bounds on minimal generating systems of toric ideals are bad.

For example consider the famous $n_1\times n_1$ transportation problem, where the matrix $A\in \mathbb Z^{m\times n_1n_2}$ is the linear map that computes the row and column sums of a given $n_1\times n_2$-matrix, then it is well known that the toric Ideal $I_A$ is minimally generated by all $2\times 2$ minors of a generic $n_1\times n_2$ matrix. See "Groebner bases and convex polytopes" by Bernd Sturmfels Example 5.1 and continuation for a more detailed study.

For fixed dimensions $n_1$ and $n_2$ also upper bounds of the total degree of any primitive in the homogeneous toric ideal $I_A$ are know. see "Groebner bases and convex polytopes" corollary 4.15

Further Jesus A. De Loera and Shmuel Onn show in their so called "no hope"-theorem that there is no hope for a general upper bound on the total degree of an element in a minimal Markov basis, even for $3\times n_1n_2$ transportation problems with both dimensions $n_1$ and $n_1$ varying.

-
To be honest I've already seen Strumfels' book. However, thank you for a useful reference to the work of De Loera and Onn. Yet there is the first question to be answered as well (at least for the case of algebraically closed field of characteristic 0). It seems like one can derive a possible answer from Eisenbud and Sturmfels "Binomial Ideals", but I find it too difficult to read. –  Toric Donut Apr 24 '14 at 16:36