%
% B. Sturmfels, S. Onn: "Cutting Corners"
% Version of May 28, 1998
% submitted to Advances in Applied Mathematics,,
% special issue in the honor of Henri Crapo, edited by Joe Kung
%

\magnification=\magstep1
\baselineskip=14pt

\def\note{\vskip.2cm\hrule\vskip.2cm\noindent}
\def \Box {\hbox{}\nobreak
\vrule width 1.6mm height 1.6mm depth 0mm  \par \goodbreak \vskip .2cm}

\def\R{{\bf R}}
\def\N{{\bf N}}

\def\Rd{\R^d}
\def\Rn{\R^n}
\def\Nd{\N^d}
\def\Nn{\N^n}

\def\P{P^d_n}
\def\Q{Q^d_n}

\def\l{\lambda}
\def\lc{{{\bf N}^d \backslash \lambda}}
\def\Ml{M_{\lambda}}
\def\twolc{{{\bf N}^2 \backslash \lambda}}


\def\all{{\Nd \choose n}}

\def\stair{{\Nd \choose n}_{\! stair}}
\def\twostair{{\N^2 \choose n}_{\! stair}}
\def\threestair{{\N^3 \choose n}_{\! stair}}

\def\cut{{\Nd \choose n}_{\! cut}}
\def\twocut{{\N^2 \choose n}_{\! cut}}
\def\threecut{{\N^3 \choose n}_{\! cut}}


\centerline{\bf CUTTING CORNERS}

\vskip .1cm

\centerline{ {\bf Shmuel Onn}
\  and  \ {\bf Bernd Sturmfels}}


\vskip .2cm

\beginsection{1. Introduction}

The object of study in this paper is the {\it corner cut polyhedron},
which we define as follows:
$$\P \quad := \quad conv \bigl\{ \, \l^1 + \cdots +  \l^n \,\, :
\,\,\l^1,\dots,\l^n \hbox{ are $n$ distinct vectors in } \Nd  \bigl\}
\quad \subset \,\,\, \Rd .$$
The following result demonstrates its significance in
computational commutative algebra.

\proclaim Theorem 5.0. The normal fan of the corner cut polyhedron $\P$
equals the Gr\"obner fan of  the vanishing ideal of
the generic configuration of $n$ points in affine $d$-space.
Therefore, the distinct reduced Gr\"obner bases
of this ideal are in bijection with the vertices of $\P$.

A nonempty finite subset $\l$ of the set $\Nd$ of nonnegative integer vectors
is a {\it staircase} if $u\in\l$ and $v\leq u$ (coordinatewise) implies
$v\in\l$. Let $\all$ be the set of $n$-element subsets of $\Nd$ and let
$\stair$ be its finite subset of staircases.
Staircases for $d=2$ are {\it partitions} (or {\it Ferrers diagrams}), and
staircases for $d=3$ are {\it plane partitions} (cf.~[Sta]).
These play an important role in algebraic combinatorics.
We also introduce the {\it staircase polytope}
$$\Q \quad := \quad conv \left\{\sum\l \, : \, \l\in\stair\right\}
\quad \subset \quad conv\left\{\sum\l\, : \, \l\in\all\right\}\quad=\quad\P.$$
A staircase $\l$ is called a {\it corner cut}
if it is linearly separable from its complement $\lc$,
i.e., for some $w\in \Rd$ we have $w\cdot v < w\cdot u$ for all $v\in\l$
and $u\in\lc$. Let $\cut$ be the set of all $n$-element corner cuts.
Planar  and $3$-dimensional corner cuts appear in various contexts, such as
combinatorial number theory [BF1] and computer vision [Bru], [Ger].
In this paper we examine the set $\cut$ of corner cuts
and the corner cut polyhedron $\P$ from four points of view:
polyhedral geometry (Section 2),
computational complexity (Section 3),
enumerative combinatorics (Section 4),
and commutative algebra (Section 5).

Section 2 concerns the facial structure and the normal fans of $\P$ and $\Q$.
We prove

\proclaim Theorem 2.0.
The corner cut polyhedron satisfies $\P=\Q+\Rd_{\geq 0}$
and is hence indeed a polyhedron.
The staircase polytope $\Q$ has the same vertex set as $\P$.
The map $\lambda \rightarrow \sum \lambda$ defines
a bijection between the corner cuts and the common
vertex set of $\P$ and $\Q$.

For  $\lambda \in \stair$ let $M_\lambda$ be
the ideal in $k[x]=k[x_1,\ldots,x_d]$
which is generated by all monomials
$x^u = x_1^{u_1} \cdots x_d^{u_d}$
with $u = (u_1, \ldots,u_d) \in \lc$.
We may represent $\lambda$ by the set
$\,min(M_\lambda)\,$ of
minimal generators of $M_\lambda$.
Dually, $\lambda$ can also be represented
by its subset $max(\lambda)$ of coordinatewise
maximal elements. They correspond
to the socle monomials of $k[x]/M_\lambda$.
For both representations the following computational
complexity result holds.


\proclaim Theorem 3.0.
There is a polynomial time algorithm for recognizing corner cuts.

Here the point is that the dimension $d$ is not fixed. A key
observation is that  if $\lambda$ is a corner cut then
$M_\lambda$ is {\it Borel-fixed } (Lemma 3.3). This ensures that
$max(\lambda)$ and $min(M_\lambda)$  have roughly the same size
(Corollary 3.6). For $d=2$ our algorithm can be specialized to
the algorithm in [BF1] for recognizing nonhomogeneous spectra of numbers.

The number of Borel-fixed ideals grows exponentially in $n$, even in
the plane $d=2$ (Proposition 4.4).
However, the number of corner cuts is polynomial in any fixed dimension.

\proclaim Theorem 4.0.
For fixed  $d$, we have
$\,  \#\cut \,\, = \,\, O\bigl(n^{2d{d-1\over d+1}}\bigr)$.

Staircases in dimension $2$ and $3$ are counted
by the classical generating functions
$$\sum_{n=0}^\infty\#\twostair \!\!\!\!\!\!\! \cdot z^n \ = \
\prod_{k=1}^\infty {1 \over (1-z^k)}\ \  \quad \quad
\hbox{and} \quad \quad
\sum_{n=0}^\infty \#\threestair \!\!\!\!\!\!\! \cdot z^n \ = \
\prod_{k=1}^\infty {1 \over (1-z^k)^k}\ \ .$$
See [Sta, Corollary 18.2]. No such formulas are known for $d\geq 4$.
We raise the related question of determining
$\sum_{n=0}^\infty\, \#\cut \!\! \cdot z^n$,  the generating functions
for corner cuts. Even in the plane $(d=2)$ we do not know the answer.
Section 4 also contains an efficient procedure for enumerating
$\cut$ and hence all vertices of the corner cut polyhedron $\P$.

In Section 5 we apply our combinatorial results
to Gr\"obner bases of point configurations,
starting with Theorem 5.0. We
explicitly determine the universal Gr\"obner basis for any $n$ points in
$d$-space, and we show that its cardinality is polynomial in $n$ for fixed $d$.

\vskip .1cm

The following example illustrates the objects of study.
Let $\,d=2, \,n=6$.  This is the first instance
when the map $\,{{\N^d \choose n}_{\! stair}} \rightarrow {\bf R}^d \,:
\, \lambda \mapsto \sum \lambda \,$ is not injective.
The set of staircases ${{\N^6 \choose 2}_{\! stair}} $
has $11$ elements, corresponding to the $11$ partitions of
the integer $6$.
We list each partition $\lambda$ together with
the monomial ideal
$M_\lambda$ and its image $\sum \lambda $ in $ Q^{2}_6$:
$$ \matrix{
1 + 1 + 1 + 1 + 1 +  1 && \langle x^6, y \rangle & & (15, 0) \cr
2 + 1 + 1 + 1 + 1   && \langle x^5, xy, y^2 \rangle & & (10,1) \cr
 2 + 2 + 1 + 1  && \langle x^4, x^2 y, y^2 \rangle & & (7, 2) \cr
2+2+2 && \langle x^3, y^2 \rangle &&  (6,3) \cr
3 + 1+1+1 && \langle x^4, x y , y^3  \rangle &&  (6,3) \cr
3+2+1  && \langle x^3, x^2y, xy^2, y^3  \rangle && (4,4)  \cr
3+3  && \langle x^2, y^3 \rangle && (3,6)  \cr
4 + 1+1 && \langle x^3, x y, y^4  \rangle && (3,6)  \cr
4+2 && \langle x^2, x y^2, y^4  \rangle && (2,7)  \cr
5+1 && \langle x^2, xy, y^5 \rangle &&  (1,10) \cr
6   && \langle x,y^6 \rangle && (0,15)  \cr
} $$
The corner cut polyhedron $P^2_6$ has six bounded edges
and seven vertices, one for each corner cut. Thus the
generic configuration of $6$ points in the plane
has seven distinct  initial monomial ideals $M_\lambda$.
The four staircases which are not
corner cuts are those mapped to $(3,6)$ or $(6,3)$.
The staircase polygon $Q^2_6$ is obtained from $P^2_6$ by
erasing the unbounded edges on the two coordinate axes and
drawing the edge between $(0,15)$ and $(15,0)$ instead.

In this paper we consider only finite staircases $\l$,
i.e., we assume that $\Ml$ is Artinian.
With suitable care, many of our results can be
extended to the infinite situation as well.


\beginsection{2. The Corner Cut Polyhedron and the Staircase Polytope}

For any subset ${\cal F}\subseteq\all$ we abbreviate
$\sum{\cal F}:=\{\sum\l \in \Nd :\ \l\in{\cal F}\}$.
In this section we describe the facial structure and
the normal fan of the
corner cut polyhedron $\P=conv\sum\all$ and the staircase polytope
$\Q=conv\sum\stair$.

We start with a lemma. We denote by $\mu^{(j)}$ the corner cut
$\, \{\,i \cdot e_j \, :\,  i=0,1,\ldots,n-1 \}$.

\proclaim Lemma 2.1.
For every staircase $\lambda \in \stair$, the sum of the coordinates
of the vector $\sum \lambda$ is at most ${n \choose 2}$.
Equality holds if and only if
$\, \lambda \, \in \, \bigl\{ \mu^{(1)}, \mu^{(2)}, \ldots, \mu^{(d)} \bigr\}$.

\noindent {\sl Proof: }
We use induction on $n$. The case $n\leq 2$ is trivial.
Choose $u=(u_1,\dots,u_d) \in \lambda$ such that
$\lambda \backslash \{u\}$ is a staircase of cardinality $n-1$. There are
$\,\prod_{i=1}^d (u_i+1) - 1 \,$ many non-negative vectors strictly below $u$.
Each of them must lie in $\lambda \backslash \{u\}$. Hence
$$ n \quad \geq \quad \prod_{i=1}^d (u_i+1)
 \quad \geq \quad u_1 + u_2 + \cdots + u_d + 1 . \eqno (2.1) $$
By induction, the coordinate sum of $\, \sum \lambda \backslash \{u\} \,$ is
at most ${ n-1 \choose 2}$, and hence the desired inequality follows
from (2.1) and $\, { n-1 \choose 2} + n -1  = { n \choose 2} $. Finally,
equality holds in $(2.1) $ if and only if all but one coordinate of $u$ is zero.
\Box


We now prove Theorem 2.0 and show that $\P$ deserves its name.

\vskip .3cm

\noindent {\sl Proof of Theorem 2.0: }
Let $w\in\Rd_{\geq 0}$ be a vector whose coordinates are ${\bf Q}$-linearly
independent. We sort the nonnegative integer vectors according
to their $w$-value, say, $\, \Nd \, = \,\{ u_1 = 0 ,u_2,u_3,u_4,\ldots \} $,
so that $\, w \cdot u_i < w \cdot u_j \,$ if and only if $i< j$.
The unique minimum of the map $\all\mapsto\R:\ \l\mapsto w \cdot \sum\l$
is attained at the corner cut $\l=\{u_1,\dots, u_n\}$.
Hence the point $\sum\lambda$ is the common vertex of $\P$
and of $\Q$ at which the linear
functional $\Rd\mapsto\R:\ u \mapsto w \cdot u \,$
attains its minimum. Every corner cut $\lambda \in \cut $ arises this way
for some $w \in \Rd_{\geq 0}$ and hence defines a
common vertex of $\P$ and $\Q$.

Next consider $w\in\Rd\backslash\Rd_{\geq 0}$.
Then $w$ is not bounded below over $\P$. This shows that
the map $\l\mapsto\sum\l$ is a bijection between $\cut$ and the vertex set
of $\P$, and proves that $\P=\Q+\Rd_{\geq 0}$.
Suppose now $\alpha:=w_j < 0$ is uniquely the smallest coordinate of $w$. Then
$$w\cdot\sum\l\quad = \quad \sum_{i=1}^d w_i\,(\sum \l)_i
\quad\geq\quad \alpha\cdot\sum_{i=1}^d(\sum \l)_i\quad\geq\quad
\alpha\cdot{n\choose2}\eqno(2.2)$$
holds for any staircase $\l$, with equality if and only if $\l=\mu^{(j)}$,
by Lemma 2.1. Hence the map $u \mapsto w \cdot u$ attains its minimum over
$\Q$ at the vertex $\sum \mu^{(j)}$ of $\P$. We conclude that every vertex of
$\Q$ is also a vertex of $\P$, and so $\Q$ and $\P$ have the same vertex set.
\Box

Next, we describe the facial structure and the normal fans of $\P$ and $\Q$.
For each $n\in\N$ and $w\in\Rd_{>0}$,
we construct a polytope $P_n^w$ as follows.
Let $w_0$ be the smallest real number such that
$\#\{v\in\Nd:\ w\cdot v\leq w_0\}\geq n$.
Let $L:=\{v\in\Nd:\ w\cdot v < w_0\}$, let $H:=\{v\in\Nd:\ w\cdot v = w_0\}$,
and let $h:=n-|L|\geq 1$. We define the polytope $P_n^w$ to be
$$P_n^w \quad := \quad \sum L \,\,+ \,\,
conv\sum{H\choose h} \quad \subset \quad \Rd.$$
The following theorem shows that every bounded face
of $\P$ equals $P_n^w$ for some $w\in\Rd_{>0}$.

\proclaim Theorem 2.2.
Let $w\in\Rd$ and let $F^w$ be the face of the corner cut polyhedron $\P$
at which the linear functional $x\mapsto w\cdot x$ is minimized. Then:
\item{(a)}
If $w$ is positive then $F^w=P_n^w$. If $h=|H|$ then $P_n^w$ is the point
$\sum(L\cup H)$ hence a vertex, and $L\cup H$ is a corner cut in $\cut$.
If $h<|H|$ then $dim(P_n^w)=dim(H)\geq 1$.
\item{(b)}
If $w$ is nonnegative and $I:=\{i\in[d]:\ w_i=0\}$ is nonempty then
$F^w$ is the unbounded $|I|$-dimensional face $\P\cap\R^I$, which
is isomorphic to the corner cut polyhedron $P_n^{|I|}$.
\item{(c)}
If $w$ has a negative coordinate then $w$ is unbounded below; hence
$F^w=\emptyset$.

\noindent {\sl Proof:}
To show that $F\subset\P$ is the face of $\P$ at which $w$ is minimized,
it suffices to show that the subset of $\sum\all$ at which $w$ is minimized
is precisely $F\cap\sum\all$.

First, suppose $w$ is positive. Let $L,H,h$ be determined by $w$
as described above. Then $w\cdot a < w\cdot b < w\cdot c$ for all
$a\in L$, $b\in H$, and $c\in\Nd\backslash(L\cup H)$,
and $w$ is constant over $H$. Therefore, $w$ is minimized at
$\sum\l$ if and only if $\l$ contains $L$ and any $h$ elements from $H$,
which holds precisely when $\sum\l\in P_n^w$.
Now, $P_n^w$ is a point if and only if $\sum{H\choose h}$ is, which holds
if and only if $h=|H|$. In this case $(L\cup H)\in\cut$ and
$P_n^w=\sum(L\cup H)$. Suppose next $h<|H|$.
Then the affine span of $H\choose h$ is a translate of
the affine span of $H$, hence $dim(P_n^w)=dim(H)$. This proves (a).

Next, suppose $w$ is nonnegative and $I:=\{i\in[d]:\ w_i=0\}\neq\emptyset$.
Consider any $\l\in\all$. Then $w\cdot\sum\l=0$ if $\sum\l\in\R^I$ whereas
$w\cdot\sum\l>0$ otherwise. This shows that $w$ is minimized over $\sum\all$
precisely at $(\P\cap\R^I)\cap\sum\all$.
Clearly, $\P\cap\R^I$ is isomorphic to the unbounded $|I|$-dimensional
corner cut polyhedron $P_n^{|I|}$. This shows (b).

Finally, (c) holds since if $w$ has a negative coordinate then it is
unbounded over $\P$.
\Box
We similarly describe the facial structure and normal fan of the
staircase polytope.

\proclaim Theorem 2.3.
Let $w\in\Rd$ and let $F^w$ be the face of the staircase polytope $\Q$
at which the linear functional $x\mapsto w\cdot x$ is minimized. Then:
\item{(a)}
If $w$ is positive then $F^w$ is the polytope $P_n^w$, as in Theorem 2.2 (a).
\item{(b)}
If $w$ is nonnegative and the set $I:=\{i\in[d]:\ w_i=0\}$ is nonempty then
$F^w$ is the $|I|$-dimensional face $\Q\cap\R^I$, which
is isomorphic to the staircase polytope $Q_n^{|I|}$.
\item{(c)}
If $\alpha:=min\{w_1,\dots,w_d\}<0$ and $I:=\{i\in[d]:\ w_i=\alpha\}$
then the face $F^w$ is the
$(|I| -  1)$-simplex $\,conv\{{n\choose 2}\cdot e_i:\ i\in I\}$.

\noindent {\sl Proof:}
Part (a) follows from the observation that $P_n^w\subseteq\Q$ for every
positive $w$. Part (b) is analogous to part (b) of Theorem 2.2.
It remains to prove part (c). Let $\alpha$ and $I$ be as above.
Then the inequality (2.2) holds for every staircase $\l\in\stair$.
By Lemma 2.1, the last inequality in (2.2) is strict unless $\l$ is some
$\mu^{(j)}$. By definition of $I$, the middle inequality in (2.2) is
strict unless $\l=\mu^{(j)}$ for some $j\in I$. This shows that $w$
attains its minimum over $\Q$ precisely at the $(|I|  -  1)$-simplex
$\,conv\{{n\choose 2}\cdot e_j:\ j\in I\}$, as claimed.
\Box

\noindent
We summarize the results of this section in the following theorem.

\proclaim Theorem 2.4.
The corner cut polyhedron $\P$ and the staircase polytope $\Q$ satisfy:
\item{(a)} $\P=\Q+\Rd_{\geq 0}$
and $\Q=\P\cap\{x\in\Rd:\ \sum_i x_i\leq{n\choose 2}\}$.
\item{(b)} The set of vertices of $\P$ and the set of vertices of $\Q$
equal $\sum\cut$.
\item{(c)} The face poset of $\Q$ is obtained from
the face poset of $\P$ as follows:
\itemitem{1.} Each bounded face of $\P$ is included.
\itemitem{2.} For $I\subset[d]$ with $1<|I|<d$, the face $\P\cap\R^I$
is replaced by the face $\Q\cap\R^I$.
\itemitem{3.} The face ${n\choose 2}\cdot e_i +\R^{\{i\}}$
is removed for each $i\in[d]$.
\itemitem{4.} The simplex
$conv\{{n\choose 2}\cdot e_1,\cdots,{n\choose 2}\cdot e_d\}$ and its faces
of dimension $\geq 1$ are added.







\beginsection{3. Recognizing Corner Cuts}

In this section a polynomial time algorithm is given for
deciding whether a staircase $\l$ is a corner cut.
Here the staircase $\lambda $ is represented either by its
subset $max(\lambda)$ of maximal elements, or by the set
$min(\lc)$ of minimal elements in its complement. We identify
$min(\lc)$ with the set $min(M_\lambda)$ of minimal generators
of the monomial ideal $M_\lambda$. For instance, in the plane
$(d=2)$ every staircase is represented by two integer sequences
$\, 0 = a_1 < a_2 < \cdots < a_m \, $ and $\, b_1 > b_2 > \cdots > b_m = 0 $,
which are interpreted as follows:
$$ \eqalign{
& min(\lc) \,  = \, \{(a_1,b_1),\ldots,(a_m,b_m)\},  \,\,\, \,\,
\quad M_\lambda \, := \, \langle y^{b_1}, x^{a_2} y^{b_2}, \ldots,
x^{a_{m-1}} y^{b_{m-1}}, x^{a_m} \rangle,
\cr
& max(\lambda) \,  = \, \{ (a_2 \!-\! 1, b_1 \!-\! 1), \ldots
(a_m \!-\! 1, b_{m-1} \!-\! 1)\}.  \cr}$$
Since a staircase is, by definition, nonempty and finite, the set
$min(\lc)$ contains a positive multiple of each unit vector.
This gives the following ``corner cut criterion''.

\proclaim Lemma 3.1. A staircase $\lambda$ is a corner cut if and only if
the system of linear inequalities
$$ {\rm (LP):}\quad\quad\quad
\forall \,\, v \in max(\l) \,\,\,\,
\forall \,\, u \in min( \lc) \,\, : \,\,
( u - v) \cdot w \, \geq \, 1 $$
has a solution $w \in {\bf Q}^d$. In other words, $\lambda$ is a corner
cut if and only if (LP) is feasible.
Moreover, any solution $w$ to (LP) is necessarily coordinatewise positive.

We call a solution $w$ to (LP) a {\it separator} for $\lambda$.
Recall that our input is either the set $max(\l)$ or the
set $min(\lc)$ but not both. Thus in order to write down
the linear program (LP) we must first compute $min(\lc)$
from $max(\l)$ or vice versa. This is a non-trivial task.
Agnarsson [Agn, Theorem~19] showed that for every $m \geq d \geq 1$,
there exists a staircase $\l$ with $\,\# min (\lc) = m \,\,$
and $\,\#max(\l)=c(d) \cdot m^{\lfloor {d \over 2} \rfloor}$.
The same example can be dualized to show that for each $m' \geq d \geq 1\,$
there exists a staircase $\l'$ with $\,\# max (\l') = m' \,\,$
and $\,\#min(\l') \geq c'(d) \cdot \# (m')^{\lfloor {d \over 2} \rfloor}$.
Hence the size of $max(\l)$ can be exponential in $d \,$
if $min(\lc)$ is given, and vice versa. This implies:

\proclaim Proposition 3.2.
For varying dimension $d$, there is no polynomial time algorithm
for computing $min(\lc)$ from $max(\l)$, or for
computing  $max(\l)$ from $min(\lc)$.

We shall overcome this obstacle by restricting to a special class
of staircases. A staircase $\lambda$ in $\Nd$ is called {\it Borel fixed}
if $v+ (e_j - e_i) \not\in \lc$ for all $i< j$ and $ v \in \l$.
This is equivalent to saying that the monomial ideal $M_\l$ is
Borel fixed. Borel fixed monomial ideals play an important
role in computational algebraic geometry (see [BaS] or [Eis]).

\proclaim Lemma 3.3. Up to a permutation of coordinates,
every corner cut is Borel fixed.

\noindent {\sl Proof: }
Let $\l \subseteq \Nd$ be a corner cut with separator
$ w = (w_1,\ldots,w_d)$.
Permuting coordinates if necessary we may assume
$w_1\geq \cdots \geq w_d$. Then, if $v\in\l$ and $i<j$, we have
that $w\cdot (v+(e_j-e_i))=w\cdot v+(w_j-w_i)\leq w\cdot v$ hence
$v+(e_j-e_i)\not\in\lc$.
\Box

The bit size of a vector $v\in\Nd$ is the number
$d+\sum_{i=1}^d \lceil log_2(v_i+1)\rceil$
of bits needed to present it.
The bit size of an input $V\subset\Nd$ is the sum
of the bit sizes of its members.

\proclaim Lemma 3.4. Let $\lambda$ be a staircase which is
represented by either $min(\lc)$ or by $max(\l)$.
There exists a polynomial time algorithm for deciding
whether $\lambda$ is Borel fixed.

\noindent {\sl Proof:}
A staircase $\l$ is Borel fixed if and only if
the following equivalent conditions hold:
$$ \forall \, v \in max(\l) \,: \,
v_i >0 \,\,\, \hbox{and}\,\,\,  i< j
\,\,\, \Longrightarrow \,\,\,
\exists \,
v' \in max(\l)\,:\,  v+ e_j - e_i \leq v' \eqno (3.1)  $$
$$ \forall \, u \in min(\lc) \,: \,
u_j >0 \,\,\, \hbox{and}\,\,\,  i< j
\,\,\, \Longrightarrow \,\,\, \exists \,
u' \in min(\lc)\,:\,  u - e_j + e_i \geq u' \eqno (3.2). $$
Either of (3.1), (3.2) can be tested in time polynomial in the
size of the input.
\Box

The two dual representations of a Borel fixed staircase $\lambda$
can be transformed into each  other by the following explicit rules.
For $i \in \{1,\ldots,d\}$ let $\,max(\lambda)^{[i]} \,$ denote the
subset of maximal elements in the set
$\, \bigl\{(v_1,\ldots,v_i,0,\ldots,0) \in \N^d \,: \,
v = (v_1,\ldots,v_d) \in max(\lambda) \bigr\}$.

\proclaim Proposition 3.5.
Let $\lambda$ be a Borel fixed staircase. Then
\item{(a)}
$ max(\l)\,\, = \,\, \left\{u-e_d:\ u\in min(\lc),\quad u_d>0\right\}$, and
\item{(b)}
$min(\lc) \,\, = \,\,\left\{
v + e_i \,: \, v \in max(\l)^{[i]}, \, i=1,\ldots,d \,\right\}$.

\noindent {\sl Proof:}
We claim that, if $v\in\l$, $u\in\lc$
and $u\leq v+e_d$, then $u=v+e_d$. For such $u,v$, clearly
$u_d=v_d+1$.  If $u_i<v_i$ for some $i$, then
$v+(e_d-e_i)\geq u$ and $v+(e_d-e_i) \in \lambda$, which is impossible.
Therefore $u_i=v_i$ for all $i<d$ hence $u=v+e_d$ as claimed.
It follows that if $v\in max(\l)$ then $u:=v+e_d\in min(\lc)$, and if
$u\in min(\lc)$ with $u_d>0$ then $v:=u-e_d\in max(\l)$ which proves part (a).
For part (b) note first that the set on the right hand side is an antichain
in $\lc$. It thus remains to show that it contains $min(\lc)$. Consider any
$u\in min(\lc)$ and assume $u_i$ is its last positive coordinate.
Let $\l^{(i)}=\{(v_1,\dots,v_i):\ v=(v_1,\dots,v_d)\in \l\}$ be the
projection of $\l$ to $\N^i$. Then $\l^{(i)}$ is Borel fixed and
$max(\l)^{[i]}=\{(v_1,\dots,v_i,0,\dots,0):
\ (v_1,\dots,v_i)\in max(\l^{(i)})\}$.
Further, $(u_1,\dots,u_i)\in min(\l^{(i)})$.
Part (a) applied to $\l^{(i)}$ in $\N^i$ shows 
$(u_1,\dots,u_i)=(v_1,\dots,v_i)+e_i$ for some
$(v_1,\dots,v_i)\in max(\l^{(i)})$ hence $u=v+e_i$
for some $v\in max(\l)^{[i]}$.
\Box

\proclaim Corollary 3.6.
Let $\lambda$ be a Borel fixed staircase. Then
$$ \# max(\l) + d - 1 \,\,\, \leq \,\,\,
 \# min(\lc)  \,\,\, \leq \,\,\,  d \cdot \#max(\l). $$

\noindent {\sl Proof:}
The second inequality is clear from part (b) of Proposition 3.5.
The first inequality follows from part (a) of Proposition 3.5
and the fact that, $\lambda$ being finite, the set $min(\lc)$
contains at least $d-1$ vectors with zero last coordinate.
\Box

Corollary 3.6 stands in contrast to Proposition 3.2
and the results in [Agn] for general staircases.
It shows that Borel fixed staircases are much nicer behaved
than general staircases.
We are now prepared to prove the complexity result stated in the introduction.

\vskip .2cm

\noindent {\sl Proof of Theorem 3.0: }
We describe an algorithm for deciding whether a
given staircase $\lambda$ is a corner cut, and, as we go along,
we shall argue that all steps can be done in
polynomial time in the bit size of the input.
We only explain how this is done for the case when $\l$ is represented
by $max(\l)$, where we make use of condition (3.1) of Lemma 3.4 and part (b)
of Proposition 3.5. The case when $\l$ is represented by $min(\lc)$ is
analogous and makes use of condition (3.2) of Lemma 3.4 and part (a)
of Proposition 3.5 instead.

The first step is to decide whether $\lambda$ is Borel fixed after some
permutation of the variables, and in the affirmative case, apply such
a permutation. We define a directed graph $G$ on the set
$[d] = \{1,2,\ldots,d\}$ as follows.
We include the arc $(i,j)$ in $G$ if and only if, for each
$v\in max(\l)$ with $v_i>0$ we have $v+e_j-e_i\leq v'$ for some
$v'\in max(\l)$. The number of operations needed to construct $G$ is
quadratic in $d$ and quadratic in  $\# max(\l)$ and hence is polynomial in
the input size. We now try to construct a permutation $\pi$ on $[d]$ by
the following procedure, which is easily carried out using quadratically
many operations. For $i=1,2,\dots,$ we define $\pi(i)$ to be any {\it source}
in the digraph $G-\{\pi(j):\ j<i\}$, where a source is defined to be a vertex 
having outgoing arcs to all other vertices. We claim that, if this procedure
fails at some $i$ to find a source, then no permutation makes $\l$
Borel fixed, whereas if this procedure successfully completes a
permutation $\pi=(\pi(1),\dots,\pi(d))$ then $\pi$ makes $\l$ Borel fixed.
If $\pi$ has been successfully found then it follows from the
construction of $G$ that condition (3.1) of Lemma 3.4 holds with the
coordinate order $(\pi(1),\dots,\pi(d))$, hence $\pi$ makes $\l$ Borel fixed.
Suppose then that $\pi(j)$ had been determined for all $j<i$ but
$G-\{\pi(j):\ j<i\}$ contains no source. Assume indirectly that $\l$ is
Borel fixed under some permutation $\tau$.
Let $r\in[d]$ be smallest with $\tau(r)\in S:=[d]\backslash \{\pi(j):\ j<i\}$.
Since $\tau(r)$ is not a source in $G[S]$, there exists $s>r$ with
$\tau(s)\in S$ and $(\tau(r),\tau(s))$ not an arc in $G$. By the construction
of $G$, this implies that there exists $v\in max(\l)$ with $v_{\tau(r)}>0$
such that $v+e_{\tau(s)}-e_{\tau(r)}\leq v'$ fails for all $v'\in max(\l)$.
This shows that condition (3.1) fails for the coordinate-order specified by
$\tau$, contradicting the choice of $\tau$.

So if a permutation was failed to be found then $\l$ is not a corner cut by
Lemma 3.3 and we are done. Assume now that a permutation had been found and 
applied to the coordinates, so that $\l$ is Borel-fixed.
We can then determine $\min(\lc)$ by Proposition 3.5 (b),
in polynomial time (cf. Corollary 3.6). Having at hand now both 
$max(\l)$ and $min(\lc)$, we can write down the linear program (LP) in 
Lemma 3.1. It is well known by the work of Khachiyan and Karmarkar 
[Sch, \S 13-15] that feasibility of a system of linear inequalities can be 
decided in polynomial time. This completes the proof.
\Box

\vskip .1cm

In any fixed dimension $d$, the feasibility of the
linear program (LP) can be checked in {\it strongly} polynomial time,
say, by Fourier-Motzkin elimination (cf. [Sch]).
In particular, in small dimensions $d=2,3$ it is possible to write down the
Fourier-Motzkin eliminated system of inequalities explicitly in terms of
$min(\lc)$ and $max(\l)$. This gives an analytical criterion for $\l$ to
be a corner cut. Let us demonstrate this for the plane $d=2$.
We may assume $w_2 = 1$ and ask for $w_1 \geq 0$. With $m:=\#min(\lc)$, we
obtain a system of $m^2-m$ inequalities $(u_1-v_1)\cdot w_1+(u_2-v_2)>0$
where $v=(v_1,v_2)$ runs through $max(\l)$ and $u=(u_1,u_2)$ runs through
$min(\twolc)$. Each such inequality can be rewritten as
$w_1>{{v_2-u_2}\over{u_1-v_1}}$ if $u_1>v_1$ and 
as $w_1<{{v_2-u_2}\over{u_1-v_1}}$ if $u_1<v_1$,
and can be omitted if $u_1=v_1$. Let
$$L_\l \,\,\,  := \,\,\, max\left\{{{v_2-u_2}\over{u_1-v_1}}:
\ v\in max(\l),\ u\in min(\twolc),\ u_1>v_1\right\},$$
$$ U_\l \,\,\,  := \,\,\, min\left\{{{v_2-u_2}\over{u_1-v_1}}:
\ v\in max(\l),\ u\in min(\twolc),\ u_1<v_1\right\}. $$
Then we obtain the following criterion for a staircase $\l\subset\N^2$
to be a corner cut, which is equivalent to the result on spectra of numbers
by Boshernitzan and Fraenkel in [BF1].

\proclaim Corollary 3.7.
A staircase $\l\subseteq\N^2$ is a corner cut if and only if $L_\l < U_\l$.

\noindent{\bf Remark 3.8.}
Based on this criterion, Boshernitzan and Fraenkel gave a quadratic algorithm
for recognizing nonhomogeneous spectra of numbers, which is basically
our algorithm for $d=2$. Later, in [BF2],
they refined it to a linear time algorithm. A natural question
is whether a linear time recognition algorithm for corner cuts
exists in any dimension.


\beginsection{4. Counting and Enumerating Corner Cuts}

In this section we discuss the number of corner cuts $\#\cut$.
This number grows polynomially with $n$ for fixed $d$, while
the number of Borel fixed staircases is exponential
even in the plane. We also show that in fixed dimension all
$n$-element corner cuts can be efficiently enumerated.
For the upper bound we shall make use of the following classical result.

\proclaim Proposition 4.1. {\rm (Andrews [And]) \ \ \ \ }
For every fixed $d$, the number of vertices of any lattice polytope $P$
in $\Rd$ satisfies $\, \# \, vert(P) \, = \,
O\bigl(vol(P)^{{d-1}\over{d+1}}\bigr)$.

See [BV] for recent developments in
discrete geometry related to Andrews' Theorem.

\vskip .2cm

\noindent
{\sl Proof of Theorem 4.0: } Fix the dimension $d$.
By Theorem 2.0, the corner cuts are in bijection with the vertices of the
corner cut polytope $\Q$. By Lemma 2.1, $\Q$ is contained in the $d$-simplex
$\,conv\bigl\{0,{n \choose 2}\cdot e_1,\ldots,{n\choose 2}\cdot e_d \bigr\}$,
hence its volume satisfies
$vol(\Q)\leq{1\over d!}{n\choose 2}^d=O\bigl(n^{2d}\bigr)$. Since $\Q$ is
a lattice polytope, Proposition 4.1 and Theorem 2.0 imply
$$\#\cut\quad =\quad \# vert(\Q) \quad =\quad
O\bigl((n^{2d})^{{d-1}\over{d+1}}\bigr). $$
This completes the proof of Theorem 4.0.
\Box
\noindent
The bound just proved, which relies on Theorem 2.0, is much better than the
bound of $O(n^{d^2})$ which one can
derive from results on separable partitions (see [AO]).

\vskip .1cm

\proclaim Remark 4.2. \rm
The number of vertices of any subpolytope of $\Q$
satisfies the same  bound.


\vskip .1cm

Next, we show that, in contrast with Theorem 4.0, the number of
Borel fixed staircases grows exponentially with $n$, even in the plane $d=2$.
We use a bijection between finite plane staircases and {\it RD-sequences}
- finite sequences over the alphabet $\{R,D\}$ starting with 'R' and
terminating with 'D'. Under this bijection, the RD-sequence
$$ R^{r_1}D^{d_1} R^{r_2}D^{d_2} \cdots R^{r_m}D^{d_m},
\quad\quad m,\ r_1,d_1,\dots,r_m,d_m\geq 1$$
corresponds to the staircase $\l$ given by
$$ min(\lc) \,\, = \,\, \left\{
\bigl(0,\sum_{i=1}^md_i\bigr),\ \bigl(r_1,\sum_{i=1}^{m-1}d_i\bigr),\
\bigl(r_1+r_2,\sum_{i=1}^{m-2}d_i\bigr),\ \dots,\ \bigl(\sum_{i=1}^mr_i,0\bigr)
\right\}.$$
The sequence describes the directions 'Right' and 'Down' while walking on
the boundary of $\lc$. The following characterization of planar
Borel fixed staircases is straightforward.

\proclaim Lemma 4.3.
The staircase corresponding to an RD-sequence as above is Borel fixed
if and only if $r_1=r_2 = \cdots=r_m=1$.

\proclaim Proposition 4.4.
The number of Borel fixed staircases in $\,\twostair\,$ is
$\,\, 2^{\Omega(\sqrt n)}$.

\noindent {\sl Proof: }
Given $n\geq 15$, let $k$ be the largest integer such that $n\geq 12k^2+3k$,
and let $m:=4k$. For each $k$-subset $I\subset[2k]=\{1,\dots,2k\}$
we define an RD-sequence $RD^{d_1}\dots RD^{d_m}$ by setting
$d_i:=d_{m+1-i}:=1$ if $i\in I$ and $d_i:=d_{m+1-i}:=2$ if $i\not\in I$.
The number of elements of the corresponding Borel fixed staircase $\l$ is
$\#\l=\sum_{i=1}^m i\cdot d_i = 3k\cdot(m+1)= 12k^2+3k$.
So the number of $n$-element planar Borel fixed staircases, which is no
smaller than the number of planar Borel fixed staircases with $12k^2+3k$ 
elements, is at least the number ${2k\choose k}\geq 2^k$ of $k$-subsets
$I\subset[2k]$. Since $k>\sqrt{n\over 13}$ for all large $n$,
this number is $2^{\Omega(\sqrt n)}$.
\Box

\noindent{\bf Remark 4.5.}
While RD-sequences of planar corner cuts have been studied
in various contexts under different names (e.g., in computer
vision under the term ``chain codes of digitized lines"), no simple
characterization of such sequences (say,
as the one in Lemma 4.3 for Borel fixed staircases) seems to be known.
See [Bru] for a recursive characterization.

\vskip 0.2cm


The set $\twostair$ of all planar staircases
(or partitions) has the generating function
$$\sum_{n=0}^\infty \, \#\twostair \!\! \!\! \!\! \cdot z^n \quad = \quad
\prod_{k=1}^\infty {1 \over (1-z^k)}  \quad = \quad
1+z+2z^2+3z^3+5z^4+7z^5+11z^6+13z^7 + \cdots.$$
Staircases in $3$-space are called {\it plane partitions}
in  combinatorics. The generating function
for counting $\threestair$ is derived  in [Sta, Theorem 18.2].
It is MacMahon's classical formula:
$$ \sum_{n=0}^\infty \, \#\threestair  \!\! \!\!\!\! \cdot z^n \quad = \quad
\prod_{k=1}^\infty {1 \over (1-z^k)^k}  \quad = \quad
1+z+3z^2+6z^3+13z^4+24z^5+48z^6 + \cdots.$$
To the best of our knowledge no such formulas are known for $d \geq 4$.

Is it possible to find an explicit formula for the  generating function
$\, \sum_{n=0}^\infty \, \#\cut \!\! \cdot z^n \,$ which enumerates
the subset of corner cuts among all staircases ?
Of special interest is the number of planar corner cuts
(cf.~Remark 4.5).  Here is a table for small values of $n$:
$$\matrix{
n & 5  \!& 6  \! & 7 \! & 8 \! & 9 \! & 10 \! &
11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \cr
\hbox{$\#\twocut$} & 6 \! & 7 \! & 8 \! & 10 \! & 12 \! & 13 \! &
16 & 16 & 18 & 20 & 23 & 24 & 26 & 26 & 30 & 32 & 35 & 34 \cr}$$

\vskip .2cm

\proclaim Question 4.6.
What is the generating function  for counting planar corner cuts:
$$ \sum_{n=0}^\infty \, \#\twocut \!\! \cdot z^n \quad = \quad ?$$

\vskip 0.3cm

We finish this section with an algorithm
for enumerating all corner cuts and all vertices of  $\P$.
It builds on results in [HOR2] and runs in
strongly polynomial time for fixed $d$.

\proclaim Proposition 4.7.
There is an algorithm that, given any $d$ and $n$, produces the set $\cut$ of
corner cuts and the set of vertices of $\P$ using
$n^{O\bigl(d^2\bigr)}$ arithmetic operations.

\noindent {\sl Proof: }
Put $N:=\{0,1,\dots,n-1\}$. Call a subset $\l\subseteq N^d\subset\Nd$
{\it separable} if $\l$ is strictly separable by a hyperplane from
$N^d\backslash\l$. Clearly, any $n$-element corner cut in $\Nd$ is a
separable subset of $N^d$. The collection $\cal S$ of all separable subsets
of $N^d$ is determined by the collection of
$ \# {N^d\choose d+1} \leq n^{d(d+1)}$
orientations of all $(d+1)$-simplices spanned by points of $N^d$, and can be
produced using $n^{O\bigl(d^2\bigr)}$ arithmetic operations. The exact details
involve symbolic perturbation of the points in $N^d$ to general position and
suitable determinant computations, and can be found in [HOR2].
Let $\cal T$ be the subcollection of $\cal S$ of all $n$-element $\l$ which
satisfy $\sum_{i=1}^d\sum\l\leq {n\choose 2}$,
and let $V:=\{\sum\l:\ \l\in{\cal T}\}$. From Theorem 2.0 and Lemma 2.1,
it follows that $\Q=conv(V)$ and $\l\in{\cal T}$ is a corner cut
if and only if $\sum\l$ is a vertex of $conv(V)$.
So $\l\in{\cal T}$ is a corner cut if and only if $\sum\l\not\in conv(U)$
for every $(d+1)$-subset $U\subseteq V\backslash\{\sum\l\}$.
Now $V$ is contained in $\{v\in\Nd:\ \sum_{i=1}^dv_i\leq {n\choose 2}\}$
hence $ \# V \leq{{{n\choose 2}+d}\choose d}\leq n^{2d}$, and there are
${{\# V }\choose{d+1}}=n^{O\bigl(d^2\bigr)}$ such subsets $U$ of $V$.
Therefore, the set of corner cuts $\cut\subseteq{\cal T}$ and the
corresponding set $\{\sum\l:\ \l\in\cut\}\subseteq V$ of vertices of $\P$
can be computed in $n^{O\bigl(d^2\bigr)}$ arithmetic operations as claimed.
\Box

The procedure described above gives, for every fixed $d$,
a  polynomial time algorithm that given $n$ and $v\in\Nd$ decides if
$v$ is a vertex of $\P$, and if it is, finds the (unique) corner cut
$\l\in\cut$  with  $\sum\l=v$.
It would be interesting to know if this task can be done
in polynomial time even in {\it varying}
dimension $d$, perhaps using the methods of [HOR1].

\vskip .1cm

In this section we have seen that, for fixed $d$ and varying $n$,  the map
$$\,\stair \!\! \longrightarrow \,\,\, \Q \, \cap \, {\bf Z}^d \,: \quad
 \lambda \, \mapsto \,  \sum \lambda  \eqno (4.1) $$
compresses a set of exponential size to a set of polynomial size.
On the boundary it restricts to the bijection
between $\,\cut \,$ and the vertices of $\Q$.
The typical fiber over an interior lattice point of
$\Q$ is expected to have exponential size.
It would be interesting to study the fibers of this
map in detail.  Is there an interesting {\it fiber
polytope}, in the sense of [BiS]~?




\beginsection{5. The Gr\"obner Bases of a Point Configuration}

Let $k$ be an infinite field and let
$\,{\cal P } \, = \, \{ p_1,\ldots,p_n \}$
be a configuration of $n$ distinct points in affine
$d$-space $k^d$. Each point $p_i = (p_{i1},\ldots,p_{id})$
corresponds to a maximal ideal
$\, M(p_i) \, = \, \langle x_1 - p_{i1}, \ldots,
 x_d - p_{id} \rangle \,$ in the
polynomial ring $k[x] = k[x_1,\ldots,x_d]$.
The configuration ${\cal P}$ is an algebraic variety whose
vanishing ideal is the intersection of these $n$ maximal ideals
$$ I_{\cal P} \quad = \quad
M(p_1) \, \cap \,
M(p_2) \, \cap \,
\cdots\, \cap \,
M(p_n) \qquad \subset \quad k[x]  .$$
Thus $I_{\cal P}$ is the radical ideal consisting
of those polynomials $f\in k[x]$ which vanish on ${\cal P}$.

For any non-negative vector $w$ in $\R_{\geq 0}^d$,
the {\it initial ideal} $\, in_w(I_{\cal P})\,$ is
the ideal of $w$-leading forms $in_w(f)$ where $f $ runs over $I_{\cal P}$.
We call two non-negative vectors $w$ and $w'$
{\it equivalent} if $\,in_w(I_{\cal P}) = in_{w'}(I_{\cal P})$.
The equivalence classes are the relatively open cones in
a subdivision of $\R_{\geq 0}^d$ which is called
the {\it Gr\"obner fan} of $I_{\cal P}$. A vector $w$ lies in
an open cell of the Gr\"obner fan if and only if
$in_w(I_{\cal P})$ is a monomial ideal;
see [BM], [MR], [Stu].

In this section we construct a convex polyhedron
$state({\cal P})$ in  $\Rn$ whose normal fan equals the
Gr\"obner fan of $I_{\cal P}$. Following [BM] we call
$state({\cal P})$ the {\it state polyhedron} of ${\cal P}$.
We thus obtain a one-to-one-to-one-to-one correspondence between the
following objects:
\item{(a)} the distinct reduced Gr\"obner bases of the ideal $I_{\cal P}$;
\item{(b)} the distinct initial monomial ideals of the ideal $I_{\cal P}$;
\item{(c)} the open cones in the Gr\"obner fan of $I_{\cal P}$;
\item{(d)} the vertices of the state polyhedron $State({\cal P})$.

\vskip .1cm

For $\lambda = \{\lambda_1,\lambda_2,\ldots,\lambda_n\}
\in {{\bf N}^d \choose n}$ and
a point configuration ${\cal P}$ as above we define
$$
[\lambda]({\cal P}) \quad := \quad
det \pmatrix{
p_1^{\lambda_1} & p_1^{\lambda_2} & \cdots & p_1^{\lambda_n} \cr
p_2^{\lambda_1} & p_2^{\lambda_2} & \cdots & p_2^{\lambda_n} \cr
\vdots & \vdots & \ddots & \vdots \cr
p_n^{\lambda_1} & p_n^{\lambda_2} & \cdots & p_n^{\lambda_n} \cr},
\qquad \hbox{where} \,\,\,\,\,
p_i^{\lambda_j} =
p_{i1}^{\lambda_{j1}} p_{i2}^{\lambda_{j2}}  \cdots p_{id}^{\lambda_{jd}} .
$$
The expression  $[\lambda]({\cal P})$ is defined
only up to sign, since $\lambda$ and ${\cal P}$ are
regarded as unordered sets. This is notationally  more convenient.
Note that all $\,n !\,$ terms in the expansion in the
determinant $[\lambda]({\cal P})$ are distinct
monomials in the $p_{ij}$. This implies:

\proclaim Lemma 5.1.
The determinant $[\lambda]({\cal P})$ is a non-zero polynomial
in the $dn$ variables $p_{ij}$.

We call a point configuration ${\cal P}$  {\it generic} if
$\,[\lambda]({\cal P}) \not= 0 \,$ for all corner cuts
$\lambda \in  {{\bf N}^d \choose n}_{cut}$.
By Lemma 5.1, the set of generic configurations
is non-empty and Zariski dense in the space $k^{dn}$ of
all point configurations. Thus the statement of Theorem 5.0
makes sense and is consistent with standard usage
of ``generic point configuration'' in algebraic geometry.

We define the {\it state polyhedron} of a point configuration ${\cal P}$
as follows:
$$ state({\cal P} ) \quad := \quad \R_{\geq 0}^d \,\, + \,\,
conv \, \bigl\{ \,\sum \lambda \,\,: \,\,
\lambda \in  \stair \,\,\, \hbox{and} \,\quad
[\lambda]({\cal P}) \not= 0 \, \bigr\}. $$
In view of Theorem 2.0 this is a subpolyhedron of the corner cut polyhedron
$\P$. The equality $\, state({\cal P}) = \P \,$ holds
if and only if ${\cal P}$ is generic.
The result stated in the introduction (Theorem 5.0)
is an immediate corollary to the following more general theorem.

\proclaim Theorem 5.2.
The normal fan of $\,state({\cal P})\,$ equals
the Gr\"obner fan of $I_{\cal P}$.



\noindent {\sl  Proof: }
Let $\lambda \in \stair$. For each $u \in \lc$
we form the  $(n+1) \times (n+1)$-determinant
$$ f_u \quad := \quad
\bigl[\lambda \cup \{u \}\bigr]
\bigl( {\cal P} \cup \{(x_1,\ldots,x_d)\} \bigr). $$
This is a polynomial in $k[x]$ which is well-defined up to sign.
By Laplace expansion,
$$ f_u \quad = \quad
\bigl[\lambda \bigr]({\cal P}) \cdot x^u  \,\, + \,\,
\sum_{i=1}^n (-1)^i \cdot
\bigl[\lambda \backslash \{\lambda_i \} \cup \{u\}\bigr]({\cal P})
\cdot x^{\lambda_i}. $$
We claim that the following seven statements are equivalent
for a vector $\,w \in \Rd_{\geq 0}$:

\vskip .1cm

\item{(1)} $[\lambda]({\cal P}) \not=0 \,$ and the
linear functional $\,v \mapsto w \cdot v \,$ is minimized
over $\,state({\cal P}) \,$ at $\sum \lambda$,
\item{(2)} $[\lambda]({\cal P}) \not=0 \,$ \ and  \
$\,\,\forall \, \mu \in \stair \,: \,\,\,
\mu \not= \lambda \,\,\,\hbox{and} \,\,\,
[\mu]({\cal P}) \not=0 \,\, \Longrightarrow \,\,
w \cdot \sum \mu > w \cdot \sum \lambda $,
\item{(3)} $[\lambda]({\cal P}) \not=0 \,$  and
$\, \forall \, u \in \lc \,\,\,
\forall \, i \in \{1,\ldots,n\} \! : \,
\bigl[\lambda \backslash \{\lambda_i \} \cup \{u\}\bigr]({\cal P}) \not= 0
 \Longrightarrow
w \cdot \lambda_i \, < \, w \cdot u $,
\item{(4)} $[\lambda]({\cal P}) \not=0 \,$ \ and  \
$\, \forall \, u \in \lc \,\,: \,\,
in_w(f_u) \, = \, x^u $,
\item{(5)}
$\, \forall \, u \in \lc \,\,\,\,: \,\,\,
f_u \not=0 \,\,\, \hbox{and} \,\,\,
in_w(f_u) \, = \, x^u $,
\item{(6)} $M_\lambda \,\subseteq \, in_w(I_{\cal P})$,
\item{(7)} $M_\lambda \,=  \, in_w(I_{\cal P})$.

\vskip .1cm

The implications
$\,(1)  \Leftrightarrow (2) \Rightarrow (3)
\Leftrightarrow (4) \Leftrightarrow (5)\,$
are straightforward. The implication
$(3) \Rightarrow (2)$ holds by the Basis
Exchange Lemma of linear algebra.
To see the implication $ (5) \Rightarrow (6)$, it
suffices to note that $\,f_u \,$ vanishes at
each point in ${\cal P}$ and hence $f_u \in I_{\cal P}$.
The statements (5) and (6) are equivalent because
both ideals $M_\lambda $ and $ in_w(I_{\cal P})$
are Artinian of colength $n$ in $k[x]$. Hence
if one of them contains the other, then they are equal.

To complete the proof of our claim, we next show $(7) \Rightarrow (4)$.
Suppose that (7) holds. Then the set
$\,\{ x^{\lambda_1}, x^{\lambda_2}, \ldots, x^{\lambda_n} \} \,$
is $k$-linearly independent modulo $I_{\cal P}$. This implies
that the $n \times n$-matrix $(p_i^{\lambda_j})$ has rank $n$,
and hence its determinant $\,[\lambda]({\cal P})\,$ is non-zero.
Therefore $x^u$ is the unique monomial appearing in the  expansion of $f_u $
which lies in $\,M_\lambda = in_w(I_{\cal P})$. Since
$f_u \in I_{\cal P}$, we conclude $in_w(f_u) = x^u$, and (4) is proved.

The equivalence of (1) and (7) shows that
two non-negative vectors $w$ and $w'$
give the same initial monomial ideal
$\,in_w(I_{\cal P}) =  in_{w'}(I_{\cal P}) \,$
if and only if they support the same vertex of $\,state({\cal P})$.
Hence $w$ and $w'$ lie in the same open cone of
the Gr\"obner fan of $I_{\cal P}$ if and only if they lie
in the same open cone of the normal fan of $state({\cal P})$. \Box

\vskip .1cm

\proclaim Corollary 5.3.
If  $\,in_w(I_{\cal P}) = M_\lambda$, then
$\,\bigl\{ \, f_u \,: \, u \in min(\lc) \bigr\}\,$ is
the reduced Gr\"obner basis of $I_{\cal P}$ with respect to $w$.

\noindent {\sl Proof: }
The initial terms of the elements $f_u \in I_{\cal P}$
minimally generate the initial monomial ideal
$\,in_w(I_{\cal P}) = M_\lambda$, and this ideal
contains none of the trailing terms of any $f_u$. \Box

\vskip .2cm

For fixed number of variables $d$, the number of
monomial ideals of colength $n$ grows exponentially in $n$.
Even the subset of Borel fixed ideals grows exponentially in $n$,
even for $d=2$ as Proposition 4.4 shows.
Thus the following result may be somewhat surprising.

\proclaim Corollary 5.4. Fix $d$ and let ${\cal P}$ be any
configuration of $n$ points in affine $d$-space $k^d$.
\item{(a)} The number of distinct reduced
Gr\"obner bases of $I_{\cal P}$ is $O(n^{2d{d-1\over d+1}})$.
\item{(b)} The ideal  $I_{\cal P}$ possesses a
universal Gr\"obner basis of cardinality  $O(n^{2d-3+{3 \over d+1}})$.

Recall that a {\it universal Gr\"obner basis} of the ideal $I_{\cal P}$
is a finite subset ${\cal U}$  which is a Gr\"obner basis
of $I_{\cal P}$
simultaneously for all weight vectors $\, w \in \Rd_{\geq 0}$;
cf.~[Stu, \S1].

\vskip .2cm

\noindent {\sl Proof of Corollary 5.4: }
Every vertex of  $state({\cal P})$ is a lattice point in $\Q$.
Hence (a) follows from  Theorem 5.2 and Remark 4.2. Next
note that the union of all reduced Gr\"obner bases
is a universal Gr\"obner basis for $I_{\cal P}$. By Corollary 5.3,
the cardinality of the reduced Gr\"obner basis corresponding to the
staircase $\l$ is $\, \# min(\lc)$. But we also have
$\, \# min(\lc) \leq c(d) \cdot n^{1 - 1/d} \,$
by a result of Berman [Ber, Theorem 3]. Hence the cardinality of any
reduced Gr\"obner basis of $I_{\cal P}$ is 
$\,O(n^{1-{1 \over d+1}})$. Multiplying 
this with the bound in  (a) we get (b).
\Box

\vskip .1cm

\proclaim Remark 5.5. \rm
Two monomial ideals $M_\lambda$ and $M_\mu$
which satisfy $\sum \lambda = \sum \mu$ cannot
both be initial ideals of some fixed non-monomial ideal $I$
in $k[x]$, even if $I$ is not radical.
This is the content of [Stu, \S2, Exercise (2)].
The example in the introduction shows that
there is no ideal $I$ of colength $6$ in $k[x,y]$
with $in_w(I) =  \,\langle x^3, y^2 \rangle\,$ and
$in_{w'}(I) =  \, \langle x^4, x y , y^3  \rangle $.
\Box


\vskip .2cm

In Section 4 we studied the cardinality
of $\cut$ as a function of $n$ and $d$. In
Corollary 5.4 (a) we gave an upper bound for the function
$\, F(n,d) \,:= \,$ the maximum number
of vertices of $\,state({\cal P})\,$ where ${\cal P}$
runs over all configurations of $n$ points in $k^d$,
and $k$ runs over all fields. Clearly,
$ \# \cut \leq F(n,d)=O(n^{2d{d-1\over d+1}})$,
but the inequality is generally strict.
Configurations in special position
may have more distinct reduced Gr\"obner bases than the generic
configuration with the same number of points.
Here is the first instance:

\proclaim Proposition 5.6.
$\, \# {{\N^2 \choose 7}_{\! cut}}\, = \,8 \,\, < \,\,
 F(7,2) \,= \, 10 $.

\noindent {\sl Proof: }
For $n=7, d=2$, the map (4.1) is injective.
The $15$ partitions of the number $7$
are mapped to the following $15$ distinct points,
the first eight of which are the vertices of $Q^2_7$:
$$ \eqalign{
\hbox{vertices: } \quad & (21, 0)    , \, (15, 1) ,\,    (11, 2)    ,\,
   \underline{ (7, 4) }, \,
   \underline{ (4, 7)},\,
(2, 11)    ,\,
(1, 15)    ,\,
(0, 21)    \cr
\hbox{not vertices: } \quad &
\underline{  (10, 3)}  ,\,\,
 (9, 3)   ,\,\,
(6, 5)        ,\,\,
\underline{   (6, 6)  },\,\,
(5, 6)        ,\,\,
(3, 9)        ,\,\,
\underline{   (3, 10)} \cr} $$
No subset of $ 11 $ points among these $15$
is in convex position. This shows $\,F(7,2) \leq 10$.

Consider the ten points which are not underlined.
They are in convex position, and each of them
is smaller than the other nine with respect to
some positive linear functional.
We shall present a configuration ${\cal P}$
of seven points  in ${\bf R}^2$ such that
$\,state({\cal P})\,$ has precisely these ten
vertices. This will imply $F(7,2) \geq 10$
and thus complete the proof. Set
$$ {\cal P} \quad = \quad
\bigl\{ \,
(0,0) \,, \,\,
(1,1) \,, \,\,
(2,2) \,, \,\,
(3,4) \,, \,\,
(5,7) \,, \,\,
(11,13) \,, \,\,
(\alpha,\beta ) \,\bigr\} ,
$$
where $\,(\alpha,\beta)\, \sim \,
(1.82997,1.82448)\,$ is the unique real solution of the two equations
$$ 1468 \alpha - 2 \beta^2+141 \beta-2937 \quad = \quad
4 \beta^3+2112 \beta^2+1578145 \beta-2886359 \quad = \quad 0 .$$
This configuration satisfies
$\,[\lambda]({\cal P}) = 0 \,$ when
$\lambda$ is either of the partitions $\,1 \! +
 \!1 \!+ \!2 \!+\!3$,  $\,1+2+4 \,$ or $\, 1 \! +\!1 \! +\!1 \!+ \! 4$.
The points $\,\sum \lambda \,$ representing
these three partitions are
 $\, (7,4), \,(4,7)\,$ and $ \,(6,6)$.
The other  $12$ partitions $\mu$ satisfy
$\,[\mu]({\cal P}) \not= 0 $.
Among the $12$ points $\,\sum \mu \,$
representing these $12$ partitions,
only the two underlined points $(10,3)$
and $(3,10)$ are not extreme.
Therefore the vertices of $state({\cal P})$
are exactly the ten non-underlined points.
\Box

\vskip .1cm

We point out that the computational results
in Sections 3 and 4 can now be translated into
algorithms for Gr\"obner bases theory. In particular,
Theorem 3.0 gives a polynomial time algorithm for deciding
whether a given monomial ideal $M_\lambda$ is the initial ideal
$in_w(I_{\cal P})$ of the generic point configuration
$\cal P$ in affine $d$-space with respect to some term order $w$.
In the affirmative case it produces a suitable
term order $w$. The point here is that $d$ varies.

If we fix the number of variables $d$, then Proposition 4.7 together with
Corallary 5.3 gives a polynomial time algorithm  for computing a
universal Gr\"obner basis of $I_{\cal P}$.

\vskip .2cm


\vskip 0.8cm

\noindent {\bf Acknowledgements: }
This project started in January 1998
when the second author gave a lecture series
at the Institute for Advanced Studies
in Mathematics at the Technion, Haifa.
We are grateful for this opportunity.
The second author was also supported
by a David and Lucile Packard Fellowship
and a visiting position at the
Research Institute for Mathematical Sciences
of Kyoto University.
The first author was partially supported by
a Technion VPR Grant and by the
Fund for the Promotion of Research at the Technion.

\vskip 1.4cm

{\baselineskip=13pt

\centerline{\bf References}

\vskip .2cm

\item{[Agn]} G.~Agnarsson:
The number of outside corners of monomial ideals,
Algorithms for algebra (Eindhoven, 1996).
{\sl J.~Pure Appl.~Algebra} {\bf 117/118} (1997) 3--21.

\item{[AO]} N.~Alon and S.~Onn:
Separable partitions, Preprint, 1998.

\item{[And]} G.~Andrews:
A lower bound for the volume of strictly convex bodies
with many boundary points, {\sl Trans.~Amer.~Math.~Soc.}
{\bf 106} (1965) 270-273.

\item{[BV]}  I.~B\'ar\'any and A.~Vershik:
On the number of convex lattice polytopes,
{\sl Geometric and Functional Analysis} {\bf 2} (1992) 381--393.

\item{[BaS]} D.~Bayer and M.~Stillman:
A criterion for detecting $m$-regularity,
{\sl Inventiones Math.} {\bf 87} (1987) 1--11.

\item{[BM]} D.~Bayer and I.~Morrison:
Standard bases and geometric invariant theory,
{\sl Journal of Symbolic Computation} {\bf 6} (1988) 209--217.

\item{[Ber]} D.~Berman: The number of generators of a colength $N$ ideal in a
power series ring, {\sl Journal of Algebra} {\bf 73} (1981) 156--166.

\item{[BiS]} L.~Billera and B.~Sturmfels:
Fiber Polytopes, {\sl Annals of Math.}  {\bf 135} (1992)  527--549.

\item{[BF1]} M.~Boshernitzan and A.S.~Fraenkel:
Nonhomogeneous spectra of numbers,
{\sl Discrete Mathematics} {\bf 34} (1981) 325--327.

\item{[BF2]} M.~Boshernitzan and A.S.~Fraenkel:
A linear algorithm for nonhomogeneous spectra of numbers,
{\sl Journal of Algorithms} {\bf 5} (1984) 187--198.

\item{[Bru]} A.M.~Bruckstein, Self-similarity properties of digitized straight
lines. {\sl Vision Geometry} (Hoboken, NJ, 1989),
{\sl Contemp.~Math.}~{\bf 119}, Amer.Math.Soc., Providence, 1991, 1--20.

\item{[Eis]} D.~Eisenbud, {\sl Commutative Algebra
with a View Toward Algebraic Geometry}, \hfill \break
Springer Verlag, New York, 1995.

\item{[Ger]} Y.~G\'erard, Analyse locale des droites discr\`etes.
G\'en\'eralisation et application  \`a la connexit\'e des plans discrets,
{\sl Comptes Rendus Acad.~Sci.~Paris, S\'er.~I Math.} {\bf 324} (1997)
1419--1424

\item{[HOR1]} F.~Hwang, S.~Onn and U.~Rothblum,
Representations and characterizations of vertices of bounded-shape
partition-polytopes, {\sl Linear Algebra and its Applications}, to appear.

\item{[HOR2]} F.~Hwang, S.~Onn and U.~Rothblum,
A polynomial time algorithm for vertex enumeration and optimization
over shaped partition polytopes,
{\sl MSRI Preprint Series} (1997), no. 41,
Mathematical Sciences Research Institute, Berkeley CA.

\item{[MR]}
T.~Mora and L.~Robbiano: The Gr\"obner fan of an ideal,
{\sl Journal of Symbolic Computation} {\bf 6} (1988) 183--208.

\item{[Sch]} A.~Schrijver:
{\sl Theory of Linear and Integer Programming}
Wiley-Interscience Series in Discrete Mathematics.
Chichester, 1986.

\item{[Sta]} R.~Stanley:
Theory and applications of plane partitions. I,II.
{\sl Studies in Applied Mathematics},
{\bf 50} (1971) 167--188 and 259--279.

\item{[Stu]} B.~Sturmfels:
{\sl Gr\"obner Bases and Convex Polytopes},
American Mathematical Society,
University Lecture Notes {\bf 8}, Providence, 1995.

\item{ }
}

\vskip 1.4cm

Shmuel Onn,  Department of Operations Research,
William Davidson Faculty of Industrial Engineering and Management,
Technion - Israel Institute of Technology,
32000 Haifa, Israel, {\tt onn@ie.technion.ac.il}

\vskip .4cm

Bernd Sturmfels, Department of Mathematics,
University of California, Berkeley, CA 94720, U.S.A.,
{\tt bernd@math.berkeley.edu}

\bye



