% AMSLaTeX File
\documentstyle[12pt]{amsart}
%------ GENERAL MACROS -----
%
% Standard rings and fields, affine and projective space
%
\def\NZQ{\Bbb} % the font for N,Z,Q,R,C
\def\NN{{\NZQ N}}
\def\QQ{{\NZQ Q}}
\def\ZZ{{\NZQ Z}}
\def\RR{{\NZQ R}}
\def\CC{{\NZQ C}}
\def\AA{{\NZQ A}}
\def\PP{{\NZQ P}}
%
%------------------------------------------------
% Symbols in "Fraktur"
%
\def\frk{\frak} % font for "Fraktur"
\def\aa{{\frk a}}
\def\pp{{\frk p}}
\def\Pp{{\frk P}}
\def\qq{{\frk q}}
\def\Qq{{\frk Q}}
\def\mm{{\frk m}}
\def\Mm{{\frk M}}
\def\nn{{\frk n}}
\def\Nn{{\frk N}}
%
%------------------------------------------------
% Small letters in bold
%
\def\ab{{\bold a}}
\def\bb{{\bold b}}
\def\xb{{\bold x}}
\def\yb{{\bold y}}
\def\zb{{\bold z}}
%
\def\opn#1#2{\def#1{\operatorname{#2}}} % to make operators
%------------------------------------------------
% Numerical invariants of rings, ideals, and modules
%
\opn\chara{char}
\opn\length{\ell}
%\opn\pd{pd}
%\opn\rk{rk}
\opn\projdim{proj\,dim}
\opn\injdim{inj\,dim}
\opn\rank{rank}
\opn\depth{depth}
\opn\grade{grade}
\opn\height{height}
\opn\embdim{emb\,dim}
\opn\codim{codim}
\def\OO{{\cal O}}
\opn\Tr{Tr}
\opn\bigrank{big\,rank}
\opn\superheight{superheight}\opn\lcm{lcm}
\opn\trdeg{tr\,deg}%
\opn\reg{reg}
\opn\hdeg{hdeg}
\opn\gcd{gcd}
\opn\bigin{bigin}
\opn\lm{lm}
\opn\min{min}
\opn\revlex{revlex}
%------------------------------------------------
% Divisors
%
\opn\div{div}
\opn\Div{Div}
\opn\cl{cl}
\opn\Cl{Cl}
%
%------------------------------------------------
% Subsets of the spectrum of a ring
%
\opn\Spec{Spec}
\opn\Supp{Supp}
\opn\supp{supp}
\opn\Sing{Sing}
\opn\Ass{Ass}
%
%------------------------------------------------
% Standard operations on ideals and modules
%
\opn\Ann{Ann}
\opn\Rad{Rad}
\opn\Soc{Soc}
\opn\Shad{Shad}
%
%------------------------------------------------
% Linear algebra and homology, endo- and automorphisms
%
\opn\Ker{Ker}
\opn\Coker{Coker}
\opn\Im{Im}
\opn\Hom{Hom}
\opn\Tor{Tor}
\opn\Ext{Ext}
\opn\End{End}
\opn\Aut{Aut}
\opn\id{id}
\def\Frob{{\cal F}}
\opn\nat{nat}
\opn\pff{pf}% \pf exists already
\opn\Pf{Pf}
\opn\GL{GL}
\opn\SL{SL}
\opn\mod{mod}
\opn\ord{ord}
%
%------------------------------------------------
% Convexity
%
\opn\aff{aff}
\opn\con{conv}
\opn\relint{relint}
\opn\st{st}
\opn\lk{lk}
\opn\cn{cn}
\opn\core{core}
\opn\vol{vol}
%------------------------------------------------
% Graded rings and Rees algebras
\opn\gr{gr}
\def\Rees{{\cal R}}
%
%------------------------------------------------
% Polynomials and power series
%
\def\poly#1#2#3{#1[#2_1,\dots,#2_{#3}]}
\def\pot#1#2{#1[\kern-0.28ex[#2]\kern-0.28ex]}
\def\Pot#1#2#3{\pot{#1}{#2_1,\dots,#2_{#3}}}
\def\konv#1#2{#1\langle #2\rangle}
\def\Konv#1#2#3{\konv{#1}{#2_1,\dots,#2_{#3}}}
%
%------------------------------------------------
% Direct and inverse limits
%
\opn\dirlim{\underrightarrow{\lim}}
\opn\invlim{\underleftarrow{\lim}}
%
%
% Names with a meaning
%
\let\union=\cup
\let\sect=\cap
\let\dirsum=\oplus
\let\tensor=\otimes
\let\iso=\cong
\let\Union=\bigcup
\let\Sect=\bigcap
\let\Dirsum=\bigoplus
\let\Tensor=\bigotimes
%
%------------------------------------------------
%
\let\to=\rightarrow
\let\To=\longrightarrow
\def\Implies{\ifmmode\Longrightarrow \else
\unskip${}\Longrightarrow{}$\ignorespaces\fi}
\def\implies{\ifmmode\Rightarrow \else
\unskip${}\Rightarrow{}$\ignorespaces\fi}
\def\iff{\ifmmode\Longleftrightarrow \else
\unskip${}\Longleftrightarrow{}$\ignorespaces\fi}
\let\gets=\leftarrow
\let\Gets=\longleftarrow
\let\followsfrom=\Leftarrow
\let\Followsfrom=\Longleftarrow
\let\:=\colon
%
%
%
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Remarks}[Theorem]{Remarks}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Examples}[Theorem]{Examples}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Problem}[Theorem]{}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\newtheorem{Notation}[Theorem]{Notation}
\newtheorem{Construction}[Theorem]{Construction}
%
% We like the var forms of some greek letters (as taught in German
%schools)
%
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\kappa=\varkappa
%
% We print on A4 paper
%
\textwidth=15cm
\textheight=22cm
\topmargin=0.5cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\pagestyle{plain}
%
% The pf environment of AMSART needs a little help
%
\def\qed{\ifhmode\textqed\fi
\ifmmode\ifinner\quad\qedsymbol\else\dispqed\fi\fi}
\def\textqed{\unskip\nobreak\penalty50
\hskip2em\hbox{}\nobreak\hfil\qedsymbol
\parfillskip=0pt \finalhyphendemerits=0}
\def\dispqed{\rlap{\qquad\qedsymbol}}
\def\noqed{\def\qed{\relax}}
%
% ------ END OF GENERAL MACROS -------
%
% ------ MACROS FOR THIS ARTICLE -------
%
\def\p{^\prime}
\def\pp{^{\prime\prime}}
\def\CT{{\tilde{\cal C}}}
\def\HT{{\tilde H}}
\def\KK{{\cal K}}
\def\FF{{\cal F}}
\def\MM{{\cal M}}
\def\LL{{\cal L}}
\def\rr{{\frak r}}
\opn\ini{in}
\opn\inm{inm}
\def\lle{ <_1}
\def\gge{ >_1}
\def\cocoa
{\mbox{\rm C\kern-.13em o\kern-.07
em C\kern-.13em o\kern-.15em A}}
\def\cocoal
{\mbox{\rm C\kern-.13em o\kern-.07
em C\kern-.13em o\kern-.15em A\kern-.1em L}}
%
%
\begin{document}
\title{ Bigeneric initial ideals, diagonal subalgebras and
bigraded Hilbert functions}
\author{Annetta Aramova, Kristina Crona and Emanuela De Negri}
\date{}
\footnotetext[1]{AMS-classification: 13A02, 13D40, 13P10}
\maketitle
\begin{abstract}
In this paper we study some problems concerning bigraded ideals. By
introducing the concept of bigeneric initial ideal, we answer an open
question about diagonal subalgebras and we give a necessary condition for a
function to be the bigraded Hilbert function of a bigraded
algebra. Moreover we give an upper bound for the regularity of a
bistable ideal in terms of the degrees of its generators.
\end{abstract}
\section*{Introduction}
In this work we introduce {\it{bigeneric initial ideals}}
and apply them to different problems concerning
bigraded algebras. More precisely, let $k$
be an infinite field, let
$R=k[x_1,\dots, x_n, y_1, \dots, y_{m}]$ be the polynomial
ring in $n+m$ variables. We consider the grading defined by
$\deg x_{i}=(1,0)$, $\deg y_{j}=(0,1)$.
Let $I$ be a bigraded ideal, i.e., an ideal which is
homogeneous with respect to this
grading.
Suppose that a monomial order is given on
$R$. As in the graded case we make coordinate changes
in order to obtain good properties for the initial ideal
$\ini (I)$ of $I$. However, in the bigraded situation
the coordinate
changes can only be made in the $x$'s separately and
in the $y$'s separately. Roughly, the bigeneric initial ideal
$\bigin(I)$ of an ideal $I$ is defined to be the
initial ideal of $g(I)$ where $g$ is
a general coordinate change in this restricted sense.
The proof of the existence of bigeneric initial ideals
is similar to the corresponding result for
generic initial ideals. Furthermore, bigeneric
initial ideals have some properties analogous
to generic initial ideals. They are bi-Borel fixed. If
$k$ has characteristic zero, they are strongly bistable. In the first
section we show these useful results and some other basic
properties of bigeneric initial ideals.
We next study the Castelnuovo-Mumford regularity of bigeneric
initial ideals. In the classical theory, the Bayer-Stillman Theorem
\cite{BaS} says that the regularity of a graded ideal
equals the regularity of its generic initial ideal (with respect
to a reverse lexicographical order). Example
\ref{terai} shows that this is not true in general for a bigraded ideal $I$
and $\bigin(I)$. We give an upper bound for the regularity of a
bistable ideal
in terms of the degrees of its generators (Theorem \ref{reg}).
In Section 3 we apply bigeneric initial ideals
to the study of diagonal subalgebras of a bigraded
algebra. Recall that for a pair of positive integers $a,b$ the
$(a,b)$-diagonal $\Delta$ is the set $\Delta=\{(as,bs) | s \in \ZZ \}$.
The diagonal subalgebra $(R/I)_\Delta$ of $R/I$ is
defined as $(R/I)_\Delta= \oplus_{s\in \ZZ} (R/I)_{(as,bs)}$.
We show that there
exist integers $a',b'$ such
that if $a\geq a', b\geq b'$, then
for the $(a,b)$-diagonal $\Delta$
we have that
$(R/I)_{\Delta}$
has a quadratic Gr\"obner basis.
This answers an open question in \cite{CHTV}.
It is known that for any graded ideal there exists a unique
lexsegment ideal with the same Hilbert function. In Section 4, introducing
bilex ideals, we prove a similar result for
bigraded ideals (Theorem \ref{hilb}). In contrast to the graded
case, for a given
bigraded ideal, a bilex ideal with the same bigraded Hilbert function is
not unique (cf. Example \ref{notu}). This suggests
that it is hard to find a complete characterization of the
bigraded Hilbert function as it is known in the graded case by
Macaulay Theorem \cite{M}. However, we give an upper bound for the growth
of the bigraded Hilbert function of bigraded ideals (Theorem \ref{bound}).
Bigraded algebras occur naturally in the
context of Rees algebras (see \cite{CHTV}), which is
one of the motivations for studying bigraded
structures.
However, notice that for all our results
about bigraded objects, the corresponding
multigraded results do hold as well
with similar proofs.
Work on this paper started while the authors visited the
University of Essen. We thank J\"urgen Herzog for several useful
discussions.
\section{Bigeneric initial ideals}
Throughout the paper, let $k$
be an infinite field, let
$R=k[x_1,\dots, x_n, y_1, \dots, y_{m}]$ be the polynomial
ring in $n+m$ variables. We consider the grading defined by
$\deg x_{i}=(1,0)$, $\deg y_{j}=(0,1)$. An ideal $I\subset R$
is {\it{bigraded}} if it is
homogeneous with respect to this
grading.
In this section we define bigeneric initial ideals
and show some basic properties.
First we need some
notation.
Let $a,b \geq 0$ be integers.
For a graded ideal $J \subset k[x_1,\dots, x_{n}]$,
the $k$-vector space generated by all elements
of degree $a$ is denoted by $J_{a}$.
The ideal generated by $J_{a}$ is
denoted by $(J_a)$.
For a bigraded ideal $I \subset R$, we
define $I_{(a,b)}$ and $(I_{(a,b)})$ analogously.
For a monomial
$u\in R$, set
\[
m_x (u) = \max\{i\: x_i | u\}, \quad m_y(u) = \max\{i\: y_i | u\}.
\]
Recall that a monomial ideal
$J\subset k[x_1,\dots, x_{n}]$ is {\it stable} if for
every monomial $u\in J$ one has $x_iu/x_{m_x(u)}\in J$
for every $i \dots >x_{n}, \,\,\, y_{1}> \dots >y_{m}$.
From standard topological arguments and following
the proof of \cite[Theorem 15.18]{Eis}, one has:
\begin{Theorem}
\label{existence}
Let $I \subset R$ be a bigraded ideal.
There is a Zariski open set $U$ in $G$
and an ideal $J$
such that for all $g\in U$ we have
$\ini (g(I))=J$.
\end {Theorem}
The ideal $J$ in the theorem is defined to be
the {\it {bigeneric initial ideal}}
of $I$, denoted by $\bigin(I)$.
The proofs of the following two propositions are similar to
the proofs of \cite[Theorem 15.20]{Eis} and
\cite[Theorem 15.23 b]{Eis}, respectively.
\begin {Proposition}
\label{Borel}
The ideal $\bigin(I)$ is bi-Borel fixed
for any bigraded ideal $I\subset R$.
\end{Proposition}
\begin{Proposition}
\label{stable}
If $k$ is a field of characteristic zero, then
$\bigin(I)$ is strongly bistable
for any bigraded ideal $I\subset R$.
\end{Proposition}
In Section 3 we shall use the following
result.
\begin{Lemma}
\label{BS}
Let $I \subset R$ be a bigraded ideal such that
$\ini (I) $ is bi-Borel fixed.
Then there exist integers $ c', d'$ such that
$(\ini (I)_{(c,d)})$ is a bistable ideal for
$c\geq c', d\geq d'$.
\end {Lemma}
\begin{pf}
Put $J= \ini (I)$.
Let $(a_{1},b_{1}), \dots, (a_{s},b_{s})$
be the bidegrees of the monomials in the minimal
set of generators of $J$.
Set $a= \max_{1 \leq i \leq s} \{ a_{i} \}$ and
$b=\max_{1 \leq i \leq s} \{ b_{i} \} $.
Let
$$
T=\{ x^{\alpha_{ij}}y^{\beta_i}: 1\leq i \leq r, 1\leq j\leq s_i \}
$$
be the minimal generating set
for $(J_{(a, b)})$.
Let $I_{(\beta_i)}$ be the ideal in $k[x_1,\dots, x_n]$
generated by $\{ x^{\alpha_{ij}}: 1\leq j\leq s_i \}$.
Let $g$ be a direct product of an
$n \times n$ upper triangular invertible matrix and the $m \times m$
identity matrix. If a monomial $u\in T$, then $g(u) \in T$,
as well. Consequently, $I_{(\beta_i)}$ is Borel-fixed.
Hence by
\cite [Proposition 10]{E R T},
there does exist an integer
${c_i}'\geq a$ such that $((I_{(\beta_i)})_{r})$ is stable for
all integers $r\geq {c_i}'$.
Put $c'= \text {max} \{ {c_i}'\}$, and
let $d'$ be the corresponding integer for the $y$-part.
If $x^\alpha y^\beta \in (J_{(c',d')})$,
then
$x^\alpha y^\beta=x^{\alpha'}y^{\beta'} \cdot x^{\alpha_{ij}}y^{\beta_i}$
for some $i,j$. Thus $x^\alpha \in ((I_{(\beta_i)})_{{c_i}'})$.
It follows that
$x_t x^\alpha / x_{m_{x}(x^\alpha)}
\in ((I_{(\beta_i)})_{{c_i}'}) $, if
$ti=\min_x(w')$. Then
$v=(x_iu'/x_{m_x(u')}) (x_{m_x(u')}w'/x_i)$ where, by condition
\ref{bistabil}.1, $x_iu'/x_{m_x(u')}\in I$. Therefore $x_iu'/x_{m_x(u')}=u''z$
for some $u''\in G(I)$, so that $v$ can be written as
$v=u''w''$ and $m_x(u'')\leq m_x(u')$. Now, if $m_x(u'')\leq
\min_x(w'')$ we are done, otherwise we repeat the process.
After finitely many steps, we get $v=uw$ with
$u\in G(I)$ and $m_x(u)\leq \min_x(w)$.
If $m_y(u)>j=\min_y(w)$,
then writing $v=(y_ju/y_{m_y(u)}) (y_{m_y(u)}w/y_j)$, we have
that $\tilde{u}=y_ju/y_{m_y(u)}\in I$. As we have just shown, we
can decompose
$\tilde{u}=u_1w_1$ with $u_1\in G(I)$ and $m_x(u_1)\leq
\min_x(w_1)$. Then $v=u_1(w_1\tilde{w})$ where
$\tilde{w}=(y_{m_y(u)}w/y_j)$, and $m_x(u_1)\leq \min_x(w_1)\leq
m_x(\tilde{u})= m_x(u)\leq \min_x(w)=\min_x(\tilde{w})$.
Therefore $m_x(u_1)\leq
\min_x(w_1\tilde{w})$. Moreover, $m_y(u_1)\leq m_y(\tilde{u})\leq
m_y(u)$.
After finitely many such steps, we obtain
the desired decomposition of $v$.
\end{pf}
\begin{Theorem}
\label{reg}
Let $I$ be a bistable ideal, $G(I)=\{u_1,\ldots,u_s\}$, and
$\deg u_i=(a_i,b_i)$ for $1\leq i\leq s$. Let
$m_x(I)=\max_{1\leq i\leq s}\{a_i\}$ and $m_y(I)=\max_{1\leq
i\leq s}\{b_i\}$. Then
\begin{enumerate}
\item[(a)] $\reg_x(I)= m_x(I)$ and $\reg_y(I)=m_y(I)$.
\item[(b)] $\reg(I)\leq m_x(I)+m_y(I)$.
\end{enumerate}
\end{Theorem}
First we show the theorem in a particular case.
\begin{Lemma}
\label{Lemma2}
Let $I\subset R$ be a bistable ideal such that $G(I)=G_x\Union
G_y$ where $G_x\subset k[x_1,\ldots,x_n]$ and $G_y\subset
k[y_1,\ldots,y_m]$. Then $I$ satisfies $(a)$ and $(b)$ of
$\ref{reg}$.
\end{Lemma}
\begin{pf}
Let $F(G_x)$ and $F(G_y)$ be the minimal free resolutions of the
ideals $(G_x)\subset R$ and $(G_y)\subset R$ respectively. Then
it is known that $F(G_x)\tensor_R F(G_y)$ is the minimal free
resolution of $I$. Since the ideals $(G_x)$ and $(G_y)$ are
stable, by \cite{EK} (cf. also \cite[Corollary 2.2]{AH}),
$\reg(G_x)=m_x(G_x)$ and
$\reg(G_y)=m_y(G_y)$. From here we conclude that \ref{reg} holds
for $I$.
\end{pf}
\begin{pf}[Proof of \ref {reg}]
For a monomial $u=x^{\alpha}y^{\beta}\in M_{(a,b)}$, set:
\[
|u|=a+b; \qquad u_x=x^{\alpha}, \quad u_y=y^{\beta}.
\]
Here, we consider the degree lexicographical order on the
monomials of $R$ that satisfies $x_1>>I_t @>>> I_{t+1}@>>> R/(I_t : v)(-|v|)@>>>0
\end{eqnarray}
where $v=u_{t+1}$.
We will show
\begin{enumerate}
\item[$(*)$] $(I_t : v)$ is bistable with $G(I_t
:v)=G_x\Union G_y$ where $G_x\subset k[x_1,\ldots,x_n]$ and
$G_y\subset k[y_1,\ldots,y_m]$. Moreover, one has
$m_x(I_t:v)\leq \max\{1,m_x(I_t)-|v_x|\}$ and $m_y(I_t:v)\leq
\max\{1,m_y(I_t)-|v_y|\}$.
\end{enumerate}
First we claim that for all $i>>I_t @>>> I_{t+1}@>>> R/(I_t : v)(-|v_x|)@>>>0.
\end{eqnarray}
From this sequence, we obtain
\[
\reg_x(I_{t+1})\leq \max\{\reg_x(I_t), \reg_x(R/(I_t : v)(-|v_x|))\}.
\]
By the inductive hypothesis $\reg_x(I_t)=m_x(I_t)$. Since the
ideal $(I_t:v)$ satisfies $(*)$, by \ref{Lemma2} we get
$\reg_x(I_t:v)=m_x(I_t:v)$, so that
\[
\reg_x(R/(I_t : v)(-|v_x|))\leq \max\{|v_x|, m_x(I_t)-1\}.
\]
As $|v_x|\leq m_x(I_{t+1})$ and $m_x(I_t)\leq m_x(I_{t+1})$, we get
$\reg_x(I_{t+1})\leq m_x(I_{t+1})$. On the other hand, by
definition, one has $m_x(I_{t+1})\leq \reg_x(I_{t+1})$. This
concludes the proof of (a).
\end{pf}
It is known that a graded ideal and its generic initial ideal
with respect to the reverse lexicographical order have
the same regularity \cite{BaS}. The corresponding result in the
bigraded case does not hold:
\begin{Example}
\label{terai}
{\em
The following example was communicated to us by N. Terai. Let $I$ be the
ideal in $k[x_1,x_2,x_3,y_1,y_2,y_3]$ generated by:
\[
x_1x_2x_3,x_1x_2y_2,x_1x_3y_3,x_1y_1y_2,x_1y_1y_3,
\]
\[
x_2x_3y_1,x_2y_1y_3,x_2y_2y_3,x_3y_1y_2,x_3y_2y_3.
\]
Then $\reg(I)=3$. We consider the reverse lexicographical order
with $x_1>x_2>x_3>y_1>y_2>y_3$. Computing $\bigin(I)$ with
Macaulay program, we obtain that $\reg(\bigin(I))=4$.
}
\end{Example}
\section{Gr\"obner bases for diagonal subalgebras}
For a pair of positive integers $a,b$ the
$(a,b)$-diagonal $\Delta$ is the set
$\Delta=\{(as,bs) | s \in \ZZ \}$.
The {\it {diagonal subalgebra}} $(R/I)_\Delta$ of $R/I$ is
defined as $(R/I)_\Delta= \oplus_{s\in \ZZ} (R/I)_{(as,bs)}$.
We consider $(R/I)_\Delta$ as a standard graded ring by
assigning the degree one to the elements $x^\alpha y^\beta$ such that
$|\alpha|=a$, $|\beta|=b$.
In this section we shall show that for any bigraded ideal $I$ in
$R$, there exist
$a', b'$ such that whenever
$a \geq a'$, $b \geq b'$, we have
that the $(a, b)$-diagonal subalgebra $(R/I)_\Delta$ of $R/I$
has a quadratic Gr\"obner basis. This result is
a bigraded correspondence to the well known result
that high enough Veronese subrings of any graded algebra
have quadratic Gr\"obner bases (see \cite{E R T}).
Throughout the section, let
$<_{R}$ be a monomial order on $R$
satisfying
$x_1>\dots > x_n$ and $y_1>\dots > y_m$. For some
general results and terminology
from the
theory of Gr\"obner bases, see e.g.\cite {F}.
First recall some notation.
Let $<$ be an order on a
polynomial ring $k[x_1,\dots,x_n]$ and
let $A$ be a set of elements in $k[x_1,\ldots,x_n]$.
The monomial $x^\alpha$
can be {\it {reduced}} with respect to $A$ and $<$,
if there exist a polynomial
$f\in A$ and a monomial $x^\beta \in k[x_1,\ldots,x_n]$,
such that $x^{\alpha}-f x^\beta=h$, where for the leading
monomial $\text {lm} (h) $ of $h$, we
have $\text{lm}(h) < x^\alpha$, or $h=0$. By abuse
of notation we will write only
$\text{lm}(h) < x^\alpha$ for this.
The monomial $x^\alpha$
is said to be
{\it{normal}} with respect to $A$ and $<$, if $x^\alpha$
can not be reduced with respect to $A$ and $<$. Notice
that $x^\alpha$ is normal exactly if it can not be written
as $x^\alpha=x^{\alpha'} \text {lm}(f)$, where
$f\in A$, and $x^{\alpha'}$ is a monomial.
We shall use the following criteria for a set
in an ideal to be a Gr\"obner basis.
\begin{Lemma}
\label{grocrit}
Let $k|x_1,\ldots, x_n]$ be the polynomial ring, with an order
$<$, and let $I \subset k[x_1,\ldots, x_n]$ be an ideal.
Let $\cal I$ be a set of elements in the
the ideal $I$.
Let $N_I$ be the set of monomials which are normal with
respect to $I$,
and let
$N_{\cal I}$ be the set of monomials which are normal
with respect to $\cal I$.
Then $N_I \subset N_{\cal I} $, and $\cal I$ is a Gr\"obner basis
if and only if equality holds.
\end{Lemma}
\begin{pf}
If ${\cal I}$ is a Gr\"obner basis
then clearly $N_I = N_{\cal I}$.
Conversely, if
$N_I = N_{\cal I}$
then for every monomial
$x^\alpha \in \ini (I)$, we have
$x^\alpha \notin N_{\cal I}$.
It follows that there exists $g \in \cal I$
such that $x^\alpha$ is divisible by $\text{lm}(g)$,
which implies that
${\cal I}$ is a Gr\"obner basis for $I$.
\end{pf}
For the $(a,b)$-diagonal $\Delta$,
we shall describe $(R/I)_\Delta$ as a quotient of
a polynomial ring.
Let $T_{(a,b)}$ be the polynomial ring
$T_{(a,b)}=K[\{ z_u \}]$, where $u$ is a monomial in $R$ of
bidegree $(a,b)$. Let $\phi=\phi_{(a,b)}$ : $T_{(a,b)} \to R$
be the homomorphism sending $z_u$ to $u$.
For a bigraded ideal $I \subset R$, let $V_{a,b}(I)$ denote
the preimage of $I$ in $T_{(a,b)}$ with respect to $\phi$.
Then we have $(R/I)_\Delta=T_{(a,b)}/ V_{a,b}(I)$.
Given the order $<_{R}$ on $R$, we consider an
{\it{extended order}} $<$ on $T_{(a,b)}$. More precisely,
let $<_{\revlex}$ be the reverse lexicographical order
on $T_{(a,b)}=K[\{ z_u \}]$ where the variables are ordered by
$z_u < z_{u'}$ if $u <_{R} u'$.
The extended order $<$ on $T_{(a,b)}$
is defined by
$z^\alpha > z^\beta $
if $\phi (z^\alpha) >_{R} \phi (z^\beta)$ or if
$\phi (z^\alpha) = \phi (z^\beta)$ and
$z^\alpha >_{\revlex} z^\beta$.
Let $\sigma$ be the $k$-linear map: $\Im \phi \to T_{(a,b)} $
sending $x^\alpha y^\beta$ to the least monomial $z^\gamma$, with
respect to the extended order,
such that $\phi (z^\gamma)=x^\alpha y^\beta$.
For $f \in R$, let $S(f)$ be the set $\{ uf \}$,
where $u$ is a monomial of minimal bidegree such that $u f \in \Im \phi$.
\begin{Remark}
\label{Ema}
{\em
Note that if $f \in R$ is of bidegree $(c,d)$, and
if $u $ is a minimal monomial such that $u f \in \Im \phi$
in the above sense, then
$ \sigma (u f)$ is of degree
$\max \{ \lceil c/a \rceil , \lceil d/b \rceil \}$.}
\end{Remark}
Essentially the same result as below is
stated in \cite[Theorem 18]{E R T}.
However, for the convenience of
the reader we give a proof which is rather similar
to the proof given in \cite{E R T} for the
graded case.
\begin{Theorem}
\label {E. R. T.}
Let $I$ be a bigraded ideal with Gr\"obner basis
$g_1, \dots, g_r$ with respect to $<_{R}$. Assume that
$\ini (I)$ is bistable and that
$\deg (g_i) \leq (c,d)$ for $1\leq i\leq r$
If $\Delta$ is the $(a,b)$-diagonal, then
the defining ideal
$V_{(a,b)}(I)$ of
$(R/I)_\Delta$ has a Gr\"obner basis with
respect to the extended order
consisting of the sets
$$
\{ z_{v}z_{v'}- \sigma(\phi(z_v z_{v'})) \} \mbox{ and }
\{ \sigma (g) : g \in \bigcup_{i=1}^r S(g_i) \}.
$$
In particular, the Gr\"obner basis consists of elements
of de\-gree $\leq$ $ \max \{ 2, \lceil c/a \rceil , \lceil d/b \rceil \}$.
\end{Theorem}
First we need some preliminary results.
Notice that $\Ker \phi$ is simply the defining ideal
of the Segre product of two Veronese subrings of
polynomial rings.
\begin{Lemma}
\label{gro1}
The set
$\{ z_v z_{v'}-\sigma(\phi(z_v z_{v'})) \}$
is a Gr\"obner basis for $\Ker \phi$
with respect to the extended order on
$T_{(a,b)}$.
\end{Lemma}
\begin{pf}
Since $ T_{(a,b)}/ \Ker \phi$ is a
subring of $R$ generated by monomials,
it is well known that
$\Ker \phi$ is generated by the set
$ \{ z^\alpha-z^\beta : \phi(z^\alpha)=\phi(z^\beta) \}$.
Hence for any monomial $z^\gamma$, the
normal form of $z^\gamma$ with
respect to $\Ker \phi$ equals
$\sigma (\phi(z^\gamma))$.
Write
$\sigma (\phi(z^\gamma))$ as
$\sigma (\phi(z^\gamma))=z_{v_{1}}\cdots z_{v_{q}}$,
where $z_{v_{1}}\geq\cdots \geq z_{v_{q}}$.
One verifies that
$\sigma (\phi(z^\gamma))$ is
the unique monomial with the same image as
$z^\gamma$ satisfying the following condition:
If $x_{i}$, $y_{j}$ are variables in $v_{l}$,
and $x_{i'}$, $y_{j'}$ are variables in $v_{l+1}$,
then $i \leq i', j\leq j'$.
Set $z^\gamma= z_{w_{1}}\cdots z_{w_{q}}$, where
$z_{w_{1}}\geq\cdots \geq z_{w_{q}}$.
If $z^\gamma$ is not normal with respect to
$\Ker \phi$, then there exist $1 \leq is$,
or similarly for two $y$-variables. Then
$z_{w_i} z_{w_j} \neq \sigma (\phi (z_{w_i} z_{w_j}))$,
and hence $z^\gamma$ is not normal with respect to
the claimed Gr\"obner basis.
We are done by Lemma \ref{grocrit}.
\end{pf}
The following properties of the extended order $<$
are obvious:
\begin{Remark}
\label{order}
{\em (1) If $z^\alpha$, $z^\beta$ are monomials such that
$z^\alpha=\sigma(\phi(z^\alpha))$ and
$z^\alpha > z^\beta$,
then $\phi(z^\alpha) > \phi(z^\beta)$;
\noindent
(2) For every polynomial $f\in \Im\phi$ we have
$\lm (\sigma(f)) = \sigma (\lm(f))$.}
\end{Remark}
\begin{Lemma}
\label{gro2}
The set consisting of
$
\{ z_v z_{v'}-\sigma(\phi(z_v z_{v'})) \}
$
and of all elements of the form $\sigma (u g_i)$, $1\leq i\leq r$,
where $u$ is a monomial such that $ug_i\in \Im\phi$, is a
Gr\"obner basis for $V_{a,b}(I)$ with
respect to the extended order .
\end{Lemma}
\begin{pf}
Let $z^\gamma$ be a monomial which is not normal with respect
to the ideal $V_{a,b}(I)$. By Lemma \ref{grocrit} it is
enough to show that $z^\gamma$ is also not normal
with respect to the claimed Gr\"obner basis.
By assumption, there exists some
polynomial $f\in V_{a,b}(I)$
such that
$z^\gamma> \text{lm} (z^\gamma-f) $. If $z^\gamma$ can
be reduced by elements of the form
$z_v z_{v'}-\sigma(\phi(z_v z_{v'})) $, we are done.
Otherwise $z^{\gamma}$ is normal with
respect to $\Ker \phi$ by Lemma \ref {gro1}, which
gives
$z^{\gamma}= \sigma (\phi( z^\gamma))$. By \ref{order}.1,
it follows that
$\phi(z ^\gamma) >
\phi ( \lm( z^{\gamma}-f) ) \geq
\lm(\phi ( z^{\gamma})- \phi (f) )
$.
This means that $\phi (z^{\gamma})$ is not normal with
respect to $I$, and consequently
$\phi (z^{\gamma})=u \text{lm}(g_i)$ for some
monomial $u$ and some $g_i$.
Thus
$z^\gamma=\sigma(\phi(z^\gamma))=
\sigma ( \text{lm}(u g_{i}))=
\text{lm} (\sigma (u g_{i}))$.
Consequently $z^\gamma$ is not normal with respect
to the claimed Gr\"obner basis, which
completes the proof.
\end{pf}
\noindent
{\it{Proof of Theorem \ref {E. R. T.} }}
\newline
By Lemma \ref{gro2} we are done if for any
element of the form $\sigma(w g_i)$,
where $w$
is a monomial such that $wg_i\in \Im\phi$,
we have that $\lm(\sigma (w g_i))$ is divided by
$\lm(\sigma (w' g_j))$, where $w' g_j \in S(g_j)$.
Thus if
$\tilde u \in \ini (I) \cap \Im \phi$, we need that
$\sigma (\tilde u)$ is divided by some $\sigma (u)$
where $u$ is a minimal generator for
$\ini (I)\cap \Im \phi$.
Let $u'$ be an element in $\ini (I)\cap \Im \phi$
of minimal bidegree among those
dividing $\tilde u$. Say $\deg (u')= t(a,b)$.
Let $\tilde u=x_{i_1} \cdots x_{i_{d_1}} \cdot y_{j_1} \cdots y_{j_{d_2}}$
where $i_1 \leq \cdots \leq i_{d_1}$ and
$j_1 \leq \cdots \leq j_{d_2}$.
Since $\ini (I)$ is bistable we have
that $u=x_{i_1} \cdots x_{i_{ta}} \cdot y_{j_1} \cdots y_{j_{tb}} \in
\ini(I) $. Furthermore, $u$ is a minimal generator for
$\ini (I)\cap \Im \phi$ since it has bidegree $t(a,b)$.
As $\sigma (u)$ divides $\sigma (\tilde u) $ we are done.
\begin{Lemma}
\label{lemmainitial}
Let $I \subset R$ be a bigraded ideal with Gr\"obner basis of
bidegree $\leq (c,d)$, and let $a\geq c, b\geq d$. Then
\begin{enumerate}
\item
$(I_{(a,b)})=((I_{(c,d)})_{(a,b)})=\{ g\in I : \deg g \geq (a,b) \}$;
\item
$( (\ini (I))_{(a,b)})= \ini ( (I_{(a,b)}))$;
\item
$(I_{(a,b)})$ has a Gr\"obner basis consisting of
elements which are all of bidegree $(a,b)$.
\end{enumerate}
\end {Lemma}
\begin{pf}
The first claim is true since $I$ is generated
in bidegree $\leq (c,d)$.
Next, if the set $\{ f_i \}$ is a Gr\"obner basis for $I$,
then $\ini (I)$ is generated by the set $\{ \text{lm} (f_i) \}$. Thus
$\ini ((I_{(a,b)}))$ is generated by all elements of the form
$u \text{lm} (f_i)$ where $u$
is a monomial such that $\deg u \text{lm} (f_i) =(a,b)$.
Clearly $( (\ini (I))_{(a,b)})$ is generated by the same set
and thus
$( (\ini (I))_{(a,b)})= \ini ((I_{(a,b)}))$.
It follows that the set of elements of the form
$u f_{i}$ where $u$
is a monomial such that $\deg u \text{lm} (f_i) =(a,b)$
is a Gr\"obner basis for $(I_{(a,b)})$.
\end{pf}
\begin{Corollary}
\label {corinitial}
Let $I \subset R$ be a bigraded ideal such that $\ini ((I_{(c,d)}))$ is
bistable
for some $c,d$, where $\ini (I)$ is generated in bidegree $\leq (c,d)$.
Let $\{ g_{i} \}$ be a Gr\"obner basis for $I_{(c,d)}$,
where $ \deg (g_i) = (c,d)$ for all $i$
(see Lemma \ref {lemmainitial}).
Assume that $a\geq c, b\geq d$.
If $\Delta$ is the $(a,b)$-diagonal, then
the defining ideal
$V_{(a,b)}(I)$ of
$(R/I)_\Delta$ has a Gr\"obner basis
consisting of the sets
$\{ z_u z_{u'}-\sigma(\phi(z_u z_{u'})) \}$
and $\{ \sigma (g) \}$ where $g$ is an element
the form $v g_i$, where $v$ is a monomial of
bidegree $(a-c,b-d)$.
In particular,
the Gr\"obner basis for $V_{(a,b)}(I)$
consists of quadratic elements.
\end{Corollary}
\begin{pf}
Put $J=(I_{(c,d)})$. By Lemma \ref{lemmainitial}
$\ini (J)=\ini (I_{(c,d)})=( (\ini I)_{(c,d)})$.
Thus $\ini (J)$ is bistable.
By the same Lemma we
have $(I_{(a,b)})=(J_{(a,b)})$. Since $\Im \phi$
consists of elements of bidegree $\geq (a,b)$, it follows that
$$
V_{(a,b)}(I)=
V_{(a,b)}( (I_{(a,b)}))=
V_{(a,b)}( (J_{(a,b)}))=
V_{(a,b)}(J) \,.
$$
We are done since Theorem \ref {E. R. T.} applies to $J$.
\end{pf}
\begin{Theorem}
\label{quadgro}
For any bigraded ideal $I \subset R$, there exist
$a', b'$ such that for
all $(a,b)$-diagonals, where
$a \geq a'$, $b \geq b'$,
the diagonal subalgebra $(R/I)_\Delta$ of $R/I$
has a quadratic Gr\"obner basis.
If $k$ has characteristic zero, and if
$\bigin(I)$ is generated in bidegree $\leq (c,d)$,
then one may choose $a'= \lceil c/2 \rceil, b'=\lceil d/2 \rceil$.
\end{Theorem}
\begin{pf}
By Proposition \ref{Borel}, for any bigraded ideal $I \subset R$, we have
that $\text{bigin}(I)$
is bi-Borel fixed. After a coordinate change we may thus assume
that $\ini (I) $ is bi-Borel fixed.
In the case when $k$ has characteristic zero,
$\ini (I) $ is bistable by Proposition \ref {stable}, and the result
follows from Theorem \ref {E. R. T.}.
In the general case,
there exist integers
$c', d'$ such that $\ini (I)$ is generated in bidegree
$\leq (c',d')$, and such that
$(\ini (I)_{(c,d)})$ is bistable whenever
$c \geq c', d\geq d'$ by Lemma \ref{BS}. Now
the previous corollary applies.
\end{pf}
\section{The bigraded Hilbert function}
In this section we apply bigeneric initial ideals to study the
bigraded Hilbert function of bigraded algebras. We take as a
model the proof of Macaulay Theorem \cite{M} as it is given
in \cite{Bi}. Our main results here are Theorem \ref{hilb} and
Theorem \ref{bound} below. Example \ref{notu} shows that the situation is
different from the graded case where a lexsegment ideal
$I^{lex}$ with the same Hilbert function as $I$ is unique.
Let $I\subset R$ be a bigraded ideal.
Set $h(b,d)=\dim_kR_{(b,d)}/I_{(b,d)}$ where $R_{(b,d)}$ denotes the
vector space of all bihomogeneous elements
in $R$ of bidegree
$(b,d)$, and $I_{(b,d)}=I\sect R_{(b,d)}$. We consider the bigraded
Hilbert function of $R/I$:
\[
H(R/I)=\sum_{b,d\geq 0}h(b,d)t^bs^d.
\]
In addition to the notation introduced at the beginning of
Section 2, we set
\[
X=\{x_1,\ldots,x_n\}, \qquad Y=\{y_1,\ldots,y_n\},
\]
and for a subset $S\subset M_{(b,d)}$, denote
\[
m_{x,i}(S)=|\{u\in S \: m_x(u)=i\}|, \quad m_{y,i}(S)=|\{u\in S \:
m_y(u)=i\}|,
\]
\[
m_{x,\leq i}(S)=\sum_{j=1}^{i}m_{x,j}(S), \quad m_{y,\leq
i}(S)=\sum_{j=1}^{i}m_{y,j}(S).
\]
Throughout this section we will work with the degree
lexicographical order on $R$ induced by
$x_1>x_2>\ldots >x_n>y_1>y_2>\ldots>y_m$. However, all results
hold if we consider any term order which is the degree
lexicographical order on $k[x_1,\ldots,x_n]$ with
$x_1>x_2>\ldots >x_n$ and the degree
lexicographical order on $k[y_1,\ldots,y_m]$ with
$y_1>y_2>\ldots>y_m$ (see also \ref{remshad} below).
\begin{Definition}
\label{lex}
{\em For a monomial $u\in M_{(b,d)}$, the set $L(u)=\{w\in M_{(b,d)}
\:w\geq u\}$ is
called a {\it lexsegment}.}
\end{Definition}
\begin{Remarks}
\label{rem1}
{\em First note that for a given integer $\ell\leq |M_{(b,d)}|$, there exists a
unique lexsegment $L\subset M_{(b,d)}$ with $|L|=\ell$.
If $u\in M_{(b,0)}$, then $L(u)$ is the usual lexsegment in $M_{(b,0)}$, as
defined in the homogeneous case. In this case, it is clear that
the shadow of $L(u)$, defined by $XL(u)=\{x_iw, 1\leq i\leq n,
w\in L(u)\}$, is again a lexsegment, namely $XL(u)=L(ux_n)$.
Let $S\subset M_{(b,0)}$ be a strongly stable set,
and let $S^{lex}$ be the lexsegment in $M_{(b,0)}$ with
$|S^{lex}|=|S|$. Then Bigatti \cite{Bi} proved:
\begin{enumerate}
\item[(a)] $m_{x,\leq i}(S^{lex})\leq m_{x,\leq i} (S)$ for all
$i$.
\smallskip
\item[(b)] $|XS^{lex}|\leq |XS|$.
\end{enumerate}
}
\end{Remarks}
\begin{Lemma}
\label{first}
Let $S$ be a strongly bistable set of monomials in $M_{(b,d)}$,
and let $I$ be the ideal generated by $S$. Then
\begin{enumerate}
\item[(a)] $XS=\Union_{u\in S}\{ux_{m_x(u)},ux_{m_x(u)+1}\ldots,
ux_n\}$,
\[
YS=\Union_{u\in S}\{uy_{m_y(u)},uy_{m_y(u)+1}\ldots,
uy_m\},
\]
and these unions are disjoint.
\item[(b)] $m_{x,i}(XS)= m_{x,\leq i}(S)$, and $m_{y,i}(YS)=
m_{y,\leq i}(S)$.
\smallskip
\item[(c)] $|XS|=\sum_{i=1}^{n}m_{x,\leq i}(S)$, and $|YS|=\sum_{i=1}^{m}m_{y,\leq
i}(S)$.
\smallskip
\item[(d)] $\dim_k I_{(b+1,d)}=\sum_{i=1}^{n}m_{x,\leq i}(S)$,
and $\dim_k I_{(b,d+1)}=\sum_{i=1}^{m}m_{y,\leq i}(S)$.
\end{enumerate}
\end{Lemma}
\begin{pf}
(a) Let $v\in XS$. Then $v=ux_i$ with $u\in S$ and some $1\leq i\leq
n$. If $ix^{\alpha}$, then $uy^{\beta}\in L$;
\item[(ylex)] if $v\in M_{(0,d)}$ and
$v>y^{\beta}$, then $x^{\alpha}v\in L$.
\end{enumerate}
A monomial ideal $J\subset R$ is called a
{\it bilex ideal} if $J_{(b,d)}$ is generated, as a $k$-vector
space, by a bilex set of monomials for every $b,d\geq 0$.}
\end{Definition}
Note that bilex ideals are strongly bistable.
\begin{Lemma}
\label{shad}
If $L\subset M_{(b,d)}$ is a bilex set, then $XL$ and $YL$ are bilex too.
\end{Lemma}
\begin{pf}
Take a monomial $uv\in L$ with $u\in M_{(b,0)}$, $v\in
M_{(0,d)}$, and let $w>x_iu$.
Then $w>x_nu$, so that $w\in
L(x_nu)=XL(u)$. Therefore $w=x_jz$ for some $z\in L(u)$. Since $L$ is
bilex, one has $zv\in L$, hence $wv\in
XL$. Similarly one shows that $XL$ satisfies (ylex). By
symmetry, $YL$ is bilex too.
\end{pf}
\begin{Lemma}
\label{shadlex}
Let $L$ be a lexsegment in $M_{(b,d)}$. Then
\begin{enumerate}
\item[(a)] $L$ is bilex.
\item[(b)] $YL$ is a lexsegment.
\end{enumerate}
\end{Lemma}
\begin{pf}
One checks immediately (a). To prove (b), say $L=L(u)$ where
$u\in M_{(b,d)}$. We will show that $YL(u)=L(uy_m)$. We may assume
$d>0$. If $v\in
L(u)$, then for every $1\leq j\leq m$, one has $y_jv\geq
y_ju\geq y_mu$, therefore $YL(u)\subset L(uy_m)$.
Let now $w\in L(uy_m)$.
Write $u=u_xu_y$ and $w=w_xw_y$ with $u_x,w_x\in M_{(b,0)}$ and
$u_y\in M_{(0,d)}$, $w_y\in Y^{d+1}$. Since $w\geq uy_m$, one has
$w_x\geq u_x$. If $w_x> u_x$, then for any $y_i$ dividing $w_y$,
one has $w_xw_y/y_i$ $>u_xu_y$, therefore $w/y_i\in L(u)$ which
implies that $w\in YL(u)$. It remains to consider the case $w_x=
u_x$. Then $w_y\geq u_yy_m$, so that $w_y\in L(u_yy_m)=YL(u_y)$.
Therefore $w_y=y_jv$ for some $v\in L(u_y)$ and some $j$. Then
$u_xv\geq u_xu_y$, and since $w=y_ju_xv$ we obtain that $w\in YL(u)$.
\end{pf}
\begin{Remark}
\label{remshad}
{\em (a) Notice that in general $XL$ is not a
lexsegment.
Consider the following simple example:
$R=k[x_1,x_2,x_3,y_1,y_2]$, $u=x_2y_1$, and $L=L(u)=
\{x_1y_1,x_1y_2,x_2y_1\}$. Then $x_2^2y_2>x_2x_3y_1$, so that
$x_2^2y_2\in L(ux_3)$, but $x_2^2y_2\notin XL(u)$.
(b) If we consider the degree lexicographical order with
$y_1>\ldots> y_m>x_1>\ldots>x_n$, we obtain that $XL$ is a lexsegment.}
\end{Remark}
Let $S$ be a strongly bistable set of monomials in
$M_{(b,d)}$. Set $T=\{v\in
M_{(0,d)} \: uv\in S \mbox{ for some } u\in M_{(b,0)}\}$ and let
$T=\{v_1,\ldots,v_k\}$ where $v_1>v_2>\ldots>v_k$. Then $S$ can
be decomposed uniquely as a disjoint union
\begin{eqnarray}
\label{dec1}
S=\Union_{j=1}^k S_jv_j \mbox{ with } S_j\subset M_{(b,0)}
\mbox{ for } 1\leq j\leq k.
\end{eqnarray}
For each $j$, $1\leq j\leq k$, let $S_j^{lex}$ be the lexsegment
in $M_{(b,0)}$ with $|S_j^{lex}|=|S_j|$. Set
\[
S^{xlex}=\Union_{j=1}^k S_j^{lex}v_j.
\]
By symmetry, one can decompose $S$ as a disjoint union
\begin{eqnarray}
\label{dec2}
S=\Union_{j=1}^l u_jT_j \mbox{ with } T_j\subset M_{(0,d)}
\mbox{ for } 1\leq j\leq l,
\end{eqnarray}
where $\{u_1,\ldots,u_l\}=\{u\in
M_{(b,0)} \: uv\in S \mbox{ for some } v\in M_{(0,d)}\}$ and
$u_1>u_2>\ldots>u_l$. For each $j$, $1\leq j\leq l$, let
$T_j^{lex}$ be the lexsegment
in $M_{(0,d)}$ with $|T_j^{lex}|=|T_j|$. Set
\[
S^{ylex}=\Union_{j=1}^l u_jT_j^{lex}.
\]
\begin{Theorem}
\label{bilex}
Let $S$ be a strongly bistable set of monomials in $M_{(b,d)}$. Then there
exists a bilex
set $S^{bilex}\subset M_{(b,d)}$ such that
\begin{enumerate}
\item[(a)] $|S^{bilex}|=|S|$;
\smallskip
\item[(b)] $m_{x,\leq i}(S^{bilex})\leq m_{x,\leq i}(S)$;
\smallskip
\item[(c)] $m_{y,\leq i}(S^{bilex})\leq m_{y,\leq i}(S)$.
\end{enumerate}
\end{Theorem}
\begin{pf}
Let $S=\Union_{j=1}^k S_jv_j$ be the decomposition (\ref{dec1})
of $S$. Since $S$ is strongly bistable, we have that
$T=\{v_1,\ldots,v_k\}$ is a strongly
stable subset of $M_{(0,d)}$, and for every $j$ the set $S_j$ is
strongly stable in $M_{(b,0)}$. We will show
that the set $S^{xlex}$ defined above has the
following properties:
\begin{enumerate}
\item[$(*)$] if $w=uv_j\in S^{xlex}$ where $u\in S_j^{lex}$, then
$L(u)v_j\subset S^{xlex}$;
\item[$(**)$] if $w=uv_j\in S^{xlex}$ and $y_s$
divides $v_j$, then for every $l~~\ldots>u_l$. Then $S^{xlex}=\Union_{i=1}^l
u_iT_i$ with
$T_1=\{v_1,\ldots,v_k\}$, and $S^{bilex}=\Union_{i=1}^l
u_iT_i^{lex}$. Let
$(XS_1)^{lex}=\{w_1,\ldots,w_s\}$. Then we get
the decomposition $(XS)^{xlex}=\Union_{i=1}^sw_iW_i$ with
$W_i\subset M_{(0,d)}$,
so that
$(XS)^{bilex}=\Union_{i=1}^sw_iW_i^{lex}$. Fix an
$i$ and take a $v\in T_i$. Since $XS_1^{lex}\subset (XS_1)^{lex}$, for
every $j$ one has
$x_ju_i=w_{p(i,j)}$ for some $1\leq p(i,j)\leq s$. On the other hand,
$x_ju_iv\in
XS^{xlex}\subset (XS)^{xlex}$, therefore $w_{p(i,j)}v\in w_{p(i,j)}W_{p(i,j)}$,
which implies that
$v\in W_{p(i,j)}$. Hence $T_i\subset W_{p(i,j)}$, so that
$T_i^{lex}\subset
W_{p(i,j)}^{lex}$ for every $i$. This shows the inclusion
$XS^{bilex}\subset
(XS)^{bilex}$.
As at the beginning of the proof, one has $YT_i^{lex}\subset
(YT_i)^{lex}$.
Thus $YS^{bilex}=\Union_{i=1}^lu_i(YT_i^{lex})\subset
\Union_{i=1}^lu_i(YT_i)^{lex}$.
On the other hand, since $YS^{xlex}=\Union_{i=1}^lu_i(YT_i)$, one obtains that
$(YS^{xlex})^{ylex}=\Union_{i=1}^lu_i(YT_i)^{lex}$. Thus $YS^{bilex}\subset
(YS^{xlex})^{ylex}$.
Now we show that $YS^{xlex}\subset (YS)^{xlex}$, and this will
conclude the proof since by \ref{incl} (b) one has that
$(YS^{xlex})^{ylex}\subset
((YS)^{xlex})^{ylex}=(YS)^{bilex}$. Let
$Y\{v_1,\ldots,v_k\}=\{z_1,\ldots,z_q\}$. Then
we have the decomposition $YS=\Union_{i=1}^qU_iz_i$ with
$U_i\subset
M_{(b,0)}$. It is clear that for each $j$ there is a $p(j)$, $1\leq p(j)\leq q$, such
that
$S_j\subset U_{p(j)}$. Therefore $S_j^{lex}\subset U_{p(j)}^{lex}$. Since
$(YS)^{xlex}=\Union_{i=1}^qU_i^{lex}z_i$, one obtains that
$YS^{xlex}\subset (YS)^{xlex}$.
\end{pf}
\begin{Lemma}
\label{cor4}
Let $I\subset R$ be a strongly bistable ideal. Then there exists a bilex
ideal
$I^{bilex}$ with the same bigraded Hilbert function.
\end{Lemma}
\begin{pf}
We have $I=\dirsum I_{(b,d)}$ and each bigraded component
$I_{(b,d)}$ is spanned by a strongly bistable set $S_{(b,d)}$ in
$M_{(b,d)}$. For each $(b,d)$, let
$I_{(b,d)}^{bilex}$ be the vector space spanned by the
bilex set $(S_{(b,d)})^{bilex}$ defined in \ref{bilex}. Set
$I^{bilex}=\dirsum I_{(b,d)}^{bilex}$. It remains to show that $I^{bilex}$
is an ideal.
By \ref{main} for every $(b,d)$ one has $XI_{(b,d)}^{bilex}\subset
(XI_{(b,d)})^{bilex}$. Since $XI_{(b,d)}\subset I_{(b+1,d)}$, by
\ref{incl} one obtains
that $(XI_{(b,d)})^{bilex}\subset I_{(b+1,d)}^{bilex}$. Therefore
$XI_{(b,d)}^{bilex}\subset I_{(b+1,d)}^{bilex}$. Similarly one has
$YI_{(b,d)}^{bilex}\subset I_{(b,d+1)}^{bilex}$. This proves that
$I^{bilex}$ is an
ideal.
\end{pf}
Now we are able to prove:
\begin{Theorem}
\label{hilb}
Let $I\subset R$ be a bigraded ideal. Then there exists a bilex ideal
$I^{bilex}$ with
the same bigraded Hilbert function.
\end{Theorem}
\begin{pf}
Since any initial ideal $\ini(I)$ has the same bigraded Hilbert function as
$I$, we can
assume that $I$ is a monomial ideal. Since the Hilbert function
of a monomial ideal does not depend on the ground field, we can
assume $\chara k=0$. Then $\bigin(I)$
is strongly
bistable (\ref{stable}). Now the claim of the theorem follows from \ref{cor4}.
\end{pf}
The following example shows that a bilex ideal with the same bigraded Hilbert
function as $I$ is not unique.
\begin{Example}
\label{notu}
{\em Let $S$ be the set defined in Example \ref{ex}
and let $I$ be the ideal generated by $S$. Using same notation
as in the proof of \ref{cor4}, let $I_{(b,d)}^{bilex_2}$ be the
vector space spanned by the bilex set
$((S_{(b,d)})^{ylex})^{xlex}$, and set $I^{bilex_2}=\dirsum
I_{(b,d)}^{bilex_2}$. Then $I^{bilex_2}$ and $I^{bilex}$ are two
different bilex ideals with
the same bigraded Hilbert function as $I$. Moreover
\[
I^{bilex}=(S^{bilex}, x_2^3y_1y_3) ; \quad
I^{bilex_2}=(S^{bilex_2}, x_1x_3y_2^3)
\]
so that they are generated in different bidegrees.
}
\end{Example}
We recall the definition of the Macaulay expansion. Let
$a$ and $i$ be two positive
integers. Then $a$ can be written uniquely in the form
\[
a={a_i\choose i}+{a_{i-1}\choose i-1}+\cdots +{a_j\choose j}
\]
where $a_i>a_{i-1}>\ldots>a_j\geq j\geq 1$, see e.g.
\cite[Chapter 4]{BH}. Set
\[
a^{~~*}=
{a_i+1\choose i+1}+{a_{i-1}+1\choose i}+\cdots +{a_j+1\choose j+1}.
\]
\ \\
\begin{Proposition}
\label{lexbou}
Let $L\subset M_{(b,d)}$ be a
lexsegment. Denote by $\langle L \rangle$ the $k$-vector space spanned by $L$.
Let
\[
\dim_k R_{(b,d)}/\langle L \rangle = {m+d-1\choose d} q+r
\]
be the Euclidean division of $\dim_k R_{(b,d)}/\langle L \rangle$ by
${m+d-1\choose d}$. Then
\[
\dim_k R_{(b,d+1)}/R_{(0,1)}\langle L \rangle = {m+d\choose d+1} q+r^{}.
\]
\end{Proposition}
\begin{pf}
Let $L=L(u)$ and write $u=u_xu_y$ with $u_x\in M_{(b,0)}$, $u_y\in
M_{(0,d)}$. First we show
\begin{eqnarray}
\label{decom}
L(u)=(\Union_{\tilde{u}\in L(u_x)\setminus
\{u_x\}}\tilde{u}M_{(0,d)})\union u_xL(u_y).
\end{eqnarray}
By definition of a lexsegment and in view of the considered
monomial order, it follows that $u_xL(u_y)\subset L(u)$ and $(L(u_x)\setminus
\{u_x\})M_{(0,d)}\subset L(u)$. On the other hand, for every $w\in
L(u)$, decomposing $w=w_xw_y$, one has $w_x\geq u_x$. If $w_x>
u_x$, then $w\in (L(u_x)\setminus
\{u_x\})M_{(0,d)}$, and if $w_x=u_x$, then $w_y\geq u_y$, so that
$w\in u_xL(u_y)$. This shows the desired decomposition (\ref{decom}).
For a monomial $w\in M_{(b,d)}$, set $E(w)=\{z\in M_{(b,d)} \: z}$ (see e.g.
\cite[Proposition 4.2.8]{BH}), and this concludes the proof.
\end{pf}
The proof of the following inequality uses exactly the same
arguments as those of Bigatti's Theorem \cite{Bi} (c.f. \ref{rem1}(a)) . For
convenience of the reader, we give the main steps.
\begin{Lemma}
\label{Bigatti}
Let $S\subset M_{(b,d)}$ be a strongly bistable set, and let
$L\subset M_{(b,d)}$ be a lexsegment with $|L|\leq |S|$. Then
\[
m_{y,\leq i}(L)\leq m_{y,\leq i}(S) \mbox{ for all } i.
\]
\end{Lemma}
\begin{pf}
We proceed by induction on $m$. The case $m=1$ being clear,
assume $m>1$. The subsets $S$ and $L$ may be uniquely
decomposed:
\[
S=\Union_{j=0}^d S_jy_m^j, \quad L=\Union_{j=0}^d L_jy_m^j
\]
with $S_j,L_j\subset M_{(b,d-j)}\sect
k[x_1,\ldots,x_n,y_1,\ldots,y_{m-1}]$. It is easy to check that
for every $j$, $S_j$ is a strongly bistable subset of
$k[x_1,\ldots,x_n,y_1,\ldots,y_{m-1}]$. One has
\[
m_{y,\leq m}(L)=|L|\leq |S|= m_{y,\leq m}(S)
\]
and
\[
m_{y,\leq m-1}(L)\leq m_{y,\leq m-1}(S) \Longleftrightarrow
|L_0|\leq |S_0|.
\]
Define
\[
S^*=\Union_{j=0}^d S_j^{lex}y_m^j
\]
where $S_j^{lex}$ is the lexsegment in $M_{(b,d-j)}\sect
k[x_1,\ldots,x_n,y_1,\ldots,y_{m-1}]$ with $|S_j^{lex}|=|S_j|$
for all $j$.
We claim that $S^*$ is strongly bistable. In fact, since all
$S_j^{lex}$ are lexsegments and in particular strongly
bistable, it remains to show that for all
$j$, denoting $Y_{m-1}=\{y_1,\ldots,y_{m-1}\}$, one has
$Y_{m-1}S_j^{lex}\subset S_{j-1}^{lex}$. The set $S$ being strongly
bistable, it follows that $Y_{m-1}S_j\subset
S_{j-1}$. By induction we have
\[
m_{y,\leq i}(S_j^{lex})\leq m_{y,\leq i}(S_j) \mbox{ for all }
1\leq i\leq m-1.
\]
Thus, applying \ref{first}(c), we get
\begin{eqnarray*}
|Y_{m-1}S_j^{lex}| \leq |Y_{m-1}S_j| \leq |S_{j-1}|=|S_{j-1}^{lex}|.
\end{eqnarray*}
Since by \ref{rem1}(b) $Y_{m-1}S_j^{lex}$ is a lexsegment, this
implies that $Y_{m-1}S_j^{lex}\subset S_{j-1}^{lex}$.
Replacing $S$ by $S^*$, we may assume that all $S_j$ are
lexsegments.
For a subset $T\subset M_{(b,d)}$ set $\min(T)=$the least
monomial in $T$. For a monomial $u=x^{\alpha}y_1^{a_1}\ldots
y_m^{a_m}$, define $\widehat{u}=u$ if $a_m=0$, and
$\widehat{u}=u(y_{m-1}/y_m)^{a_m}$ if $a_m>0$. Then, as in
\cite{Bi}, one shows:
\begin{enumerate}
\item[(a)] $u,v\in M_{(b,d)}$, $u\leq v \Longrightarrow \widehat{u}\leq
\widehat{v}$;
\item[(b)] for every strongly bistable set $S$,
one has $\widehat{\min(S)}=\min(S_0)$.
\end{enumerate}
We claim that $\min(L)\geq \min(S)$. Indeed, assuming $\min(L)<
\min(S)$, since $L=L(\min(L))$, we get $S\subset L$ and $S\neq
L$ and from here the contradiction $|S|<|L|$.
Now, by (a) and (b), we obtain
\[
\min(L_0)=\widehat{\min(L)}\geq \widehat{\min(S)}=\min(S_0).
\]
Since $L_0$ and $S_0$ are both lexsegments in $M_{(b,d)}$, the
last inequality implies that $L_0\subset S_0$. Thus $|L_0|\leq
|S_0|$. Moreover, we have by induction
\[
m_{y,\leq i}(L_0)\leq m_{y,\leq i}(S_0) \mbox{ for } 1\leq i\leq
m-1.
\]
Since for $i}$;
\smallskip
\item[(b)] $h(b+1,d)\leq {n+b\choose b+1} q_1+r_1^{***}$.
\end{enumerate}
\end{Theorem}
\begin{pf}
Arguing as in the proof of \ref{hilb} we can assume that $I$ is
a strongly bistable ideal.
Fix an integer $b\geq 0$ and consider
$I_b=\dirsum_{d\geq 0} I_{(b,d)}\subset R_b=\dirsum_{d\geq 0}
R_{(b,d)}$ as graded modules over $A= k[y_1,\ldots,y_m]$. For
every $d$, let $(I_{(b,d)})^{lex}$ be the vector space spanned
by the lexsegment consisting of the first $\dim_kI_{(b,d)}$ monomials in
$M_{(b,d)}$. Set $I_b^{lex}=\dirsum_{d\geq 0} (I_{(b,d)})^{lex}$.
Applying \ref{first}(c) and \ref{Bigatti} we obtain the
in\-equal\-ity
\[
\dim_kR_{(0,1)}(I_{(b,d)})^{lex}\leq \dim_kR_{(0,1)}I_{(b,d)}.
\]
Since $R_{(0,1)}I_{(b,d)}\subset I_{(b,d+1)}$, we
get
\[
\dim_kR_{(0,1)}(I_{(b,d)})^{lex}\leq
\dim_kI_{(b,d+1)}=\dim_k(I_{(b,d+1)})^{lex}.
\]
According to \ref{shadlex}(b), $R_{(0,1)}(I_{(b,d)})^{lex}$ is a vector space
spanned by a lexsegment.
Thus $R_{(0,1)}(I_{(b,d)})^{lex}\subset
(I_{(b,d+1)})^{lex}$. This shows that $I_b^{lex}$ is a graded module
over $A$. Moreover, it has the same Hilbert function as $I_b$,
i.e. $ \dim_kR_{(b,d)}/(I_b^{lex})_d=
h(b,d)$ for every $d$. Then one
obtains
\begin{eqnarray*}
h(b,d+1)&=&\dim_kR_{(b,d+1)}/(I_b^{lex})_{d+1}\leq
\dim_kR_{(b,d+1)}/R_{(0,1)}(I_{(b,d)})^{lex} \\
& =& {m+d\choose d+1}q+r^{}.
\end{eqnarray*}
The last equality follows from \ref{lexbou}. This shows (a).
Similarly, one proves (b) by considering the degree lexicographical
order defined by $y_1>\ldots> y_m>x_1>\ldots>x_n$ (cf. \ref{remshad}(b)).
\end{pf}
The following simple example shows that conditions (a) and (b)
of \ref{bound} are not sufficient for a function to be the
bigraded Hilbert function of a bigraded algebra.
\begin{Example}
\label{lastex}
{\em Let $h(1,0)=n=3$, $h(0,1)=m=2$, $h(1,1)=2$, $h(2,0)= 6$,
$h(0,2)=3$, $h(2,1)=3$, $h(1,2)=3$ and $h(b,d)=0$
if both $b>1$ and $d>1$. Then the only bilex sets $S$ in
$M_{(1,1)}\subset k[x_1,x_2,x_3,y_1,y_2]$ such that
$|S|=|M_{(1,1)}|-h(1,1)= 4$ are:
\[
S_1=\{x_1y_1,x_1y_2,x_2y_1,x_3y_1\},
S_2=\{x_1y_1,x_1y_2,x_2y_1,x_2y_2\}.
\]
However $|XS_1|=9$, $|YS_1|=7>|M_{(1,2)}|-h(1,2)$, and
$|XS_2|=10>|M_{(2,1)}|-h(2,1)$, $|YS_2|=6$, so that there is no
bilex ideal, and hence by \ref{hilb} no bigraded ideal whose
bigraded Hilbert function coincides with the given function.
}
\end{Example}
\vspace{.15in}
\begin{thebibliography}{99}
\bibitem{AH} A. Aramova and J. Herzog, Koszul cycles and
Eliahou--Kervaire type resolutions, J. of Algebra
181 (1996) 347 -- 370.
\bibitem{BaS} D. Bayer and M. Stillman, A theorem on refining
division orders by the reverse lexicographic orders, Duke J.
Math. 55 (1987) 321 -- 328.
\bibitem{Bl} C. Blancafort, Hilbert functions of graded algebras
over Artinian rings, J. of Pure and Appl. Algebra 125
(1998) 55 -- 78.
\bibitem{Bi} A. M. Bigatti, Upper bounds for the Betti numbers
of a given Hilbert function, Comm. in Algebra 21
(1993) 2317 -- 2334.
\bibitem{BH} W. Bruns and J. Herzog, Cohen-Macaulay Rings
(Cambridge University Press, Cambridge, revised edition 1998).
\bibitem{CHTV} A. Conca, J. Herzog, N. V. Trung, G. Valla,
Diagonal subalgebras of bigraded algebras and
embeddings of Blow-ups of projective spaces,
Amer. J. Math. 119 (1997) 859--901.
\bibitem{Eis} D. Eisenbud, Commutative Algebra with a view toward
Algebraic Geometry (Springer-Verlag, Berlin Heidelberg New York,
1995).
\bibitem{E R T} D. Eisenbud, A. Reeves, B. Totaro,
Initial ideals, Veronese subrings, and rates of algebras,
Adv. Math. 109 (1994) 168--187.
\bibitem{EK} S. Eliahou and M. Kervaire, Minimal resolutions
of some monomial ideals, J. of Algebra 129 (1990)
1-- 25.
\bibitem{F} R. Fr\"oberg, An introduction to Gr\"obner Bases
(Chichester: John Wiley \& Sons, 1997).
\bibitem{M} F. S. Macaulay, Some properties of enumeration in
the theory of modular systems, Proc. London Math. Soc. 26
(1927) 531--555.
\end{thebibliography}
\ \\ \\
\noindent
Annetta Aramova, FB 6 Mathematik und Informatik, Universit\"at-GHS-Essen,\\
Postfach 103764, Essen 45117, Germany\\
a.aramova@@uni-essen.de\\
\ \\
Kristina Crona, Department of Mathematics, Stockholm University,\\
S-106 91 Stockholm, Sweden\\
crona@@matematik.su.se\\
\ \\
Emanuela De Negri, Dipartimento di Matematica, Universit\`a di
Genova,\\
Via Dodecaneso 35, I-16146 Genova, Italia\\
denegri@@dima.unige.it
\end{document}
**