# On virtual resolutions of points in a product of projective spaces

Isidora Bailly-Hall  Grinnell College<EMAIL_ADDRESS>,  Christine
Berkesch  University of Minnesota<EMAIL_ADDRESS>,  Karina Dovgodko
Columbia University<EMAIL_ADDRESS>,  Sean Guan  University of
California, Berkeley<EMAIL_ADDRESS>,  Saisudharshan Sivakumar
University of Florida<EMAIL_ADDRESS>and  Jishi Sun  University of
Michigan<EMAIL_ADDRESS>
###### Abstract.

For finite sets of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$, we produce
short virtual resolutions, as introduced by Berkesch, Erman, and Smith
[virtual-original]. We first intersect with a sufficiently high power of one
set of variables for points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$ to produce
a virtual resolution of length $n+m$. Then, we describe an explicit virtual
resolution of length $3$ for a set of points in sufficiently general position
in $\mathbb{P}^{1}\times\mathbb{P}^{2}$, via a subcomplex of a free
resolution. This first result generalizes to
$\mathbb{P}^{n}\times\mathbb{P}^{m}$ work of Harada, Nowroozi, and Van Tuyl
[HNV-points] and the second partially generalizes work of [HNV-points] and
Booms-Peot [booms-peot], which were both for
$\mathbb{P}^{1}\times\mathbb{P}^{1}$. Along the way, we also note an explicit
relationship between Betti numbers and higher difference matrices of bigraded
Hilbert functions for $\mathbb{P}^{n}\times\mathbb{P}^{m}$.

###### Key words and phrases:

Syzygies, resolutions, toric varieties, virtual resolution

###### 2020 Mathematics Subject Classification:

Primary: 13D02. Secondary: 14M25, 14F06

##  1\. Introduction

Minimal free resolutions of the vanishing ideal of an embedded projective
variety $Y$ contain important geometric information; for example, the length
of such a complex is bounded below by the codimension of $Y$ and above by the
dimension of the ambient projective space. When working over the Cox ring of a
smooth projective toric variety, the virtual resolutions introduced by
Berkesch, Erman, and Smith in [virtual-original], can be shorter than minimal
free resolutions and encode more geometry; for one, it is possible to find
such complexes with length at most the dimension of the ambient space, see
[virtual-original, FH, HHL, short-HST, reggie-thesis]. There is growing
interest in producing families of short virtual resolutions, see [virtualJSAG,
duarte-seceleanu, virtualCM, reu2018, loper, yang-monomial, booms-cobb, HNV-
points, reu2019, mahrud-resDiag, booms-peot, virtual-cellular]. Most relevant
to this article are [HNV-points, booms-peot], which study virtual resolutions
of points in $\mathbb{P}^{1}\times\mathbb{P}^{1}$, as we will consider finite
sets of points $X\subseteq\mathbb{P}^{n}\times\mathbb{P}^{m}$.

Let $S=\Bbbk[x_{0},x_{1},\ldots,x_{n},y_{0},y_{1},\ldots,y_{m}]$ denote the
_Cox ring_ of $\mathbb{P}^{n}\times\mathbb{P}^{m}$, where $\Bbbk$ is an
algebraically closed field, and $S$ carries the multigrading
$\deg(x_{i})=(1,0)\in\mathbb{Z}^{2}$ and $\deg(y_{j})=(0,1)\in\mathbb{Z}^{2}$
for all $i,j$. Let $\mathbf{x}=x_{0},x_{1},\ldots,x_{n}$ and
$\mathbf{y}=y_{0},y_{1},\ldots,y_{m}$. The _irrelevant ideal_ of
$\mathbb{P}^{n}\times\mathbb{P}^{m}$ in $S$ is

$B:=\langle x_{0},x_{1},\ldots,x_{n}\rangle\cap\langle
y_{0},y_{1},\ldots,y_{m}\rangle=\langle\mathbf{x}\rangle\cap\langle\mathbf{y}\rangle.$

Let $X$ denote a finite set of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$,
and let $I_{X}$ denote the homogeneous vanishing ideal of $X$ in $S$. A graded
free complex of $S$-modules

$F_{\bullet}\ \coloneqq\ F_{0}\leftarrow F_{1}\leftarrow
F_{2}\leftarrow\cdots$

is a _virtual resolution_ of a finitely generated $\mathbb{Z}^{2}$-graded
$S$-module $M$ if it satisfies:

  1. (1)

For each $i>0$, there is some $t$ such that $B^{t}H_{i}(F_{\bullet})=0$, and

  2. (2)

$H_{0}(F_{\bullet})/\Gamma_{B}(H_{0}(F_{\bullet}))\cong M/\Gamma_{B}(M)$,

where $\Gamma_{B}(M)\coloneqq\\{m\in M\mid B^{t}m=0\text{ for some
}t\in\mathbb{N}\\}$. Equivalently, $F_{\bullet}$ is a virtual resolution of
$M$ if $\widetilde{F_{\bullet}}$ is a locally free resolution of
$\widetilde{M}$ over $\mathbb{P}^{n}\times\mathbb{P}^{m}$.

For a finite set $X$ of points in $\mathbb{P}^{1}\times\mathbb{P}^{1}$, [HNV-
points]*Theorem 4.2 made explicit the construction of a virtual resolution for
$S/I_{X}$ in [virtual-original]*Theorem 4.1. Our first main result generalizes
this to $\mathbb{P}^{n}\times\mathbb{P}^{m}$.

######  Theorem 1.1.

Let $X$ be a finite set of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$ with
natural first projection
$\pi_{1}\colon\mathbb{P}^{n}\times\mathbb{P}^{m}\to\mathbb{P}^{n}$. Let
$\ell=|\pi_{1}(X)|$ denote the number of unique first coordinates among the
points in $X$. For all $t\geq\ell-1$, the minimal free resolution of
$S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$ is a virtual resolution of
$S/I_{X}$ of length $n+m$.

A second method for finding virtual resolutions, called _virtual of a pair_ in
[virtual-original] obtains virtual resolutions by taking certain subcomplexes
of the minimal free resolution, see 5.3. [HNV-points]*Theorem 3.1 used the
virtual of a pair construction to give an explicit description of certain
virtual resolutions for finite sets of points
$X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{1}$. In the same setting [booms-
peot]*Theorems 3.3, 1.4 built on this result and gave a sufficient condition
for when virtual resolutions of a pair have length $2$.

Our second main result generalizes part of this work to
$\mathbb{P}^{1}\times\mathbb{P}^{2}$, while relying on a weakened form of the
Minimal Resolution Conjecture (see 4.4), which is open for multiprojective
spaces.

######  Definition 1.2.

For a finite set of points $X\subseteq\mathbb{P}^{n}\times\mathbb{P}^{m}$, the
_Hilbert matrix_ $H_{X}$ has entries

$(H_{X})_{i,j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=H_{S/I_{X}}(i,j)\quad\text{for
all }(i,j)\in\mathbb{Z}^{2}$

tabulating the bigraded Hilbert function of $S/I_{X}$. If

$H_{X}(i,j)=\min\\{|X|,T_{i,n}T_{j,m}\\}\quad\text{for all}\quad i,j\geq 0,$

with

$T_{a,b}:=\binom{a+b}{b},$

then we say that $X$ has a _generic Hilbert matrix_. 4.1 shows that this is an
open condition on the Hilbert scheme of points in
$\mathbb{P}^{n}\times\mathbb{P}^{m}$. We will further say that $X$ is a set of
points in _sufficiently general position_ if it has a generic Hilbert function
and satisfies an additional condition on its first Betti numbers, as given in
4.4.

######  Theorem 1.3 (See 5.4 and Appendix A).

Let $X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$ be a finite set of points
in sufficiently general position. If a weakened form of the Minimal Resolution
Conjecture holds (see 4.4), then $S/I_{X}$ has a virtual resolution of length
$3$ obtained from the virtual of a pair construction at
$\mathbf{d}=(|X|-1,0)$.

It is well-known that Hilbert functions can be computed as alternating sums of
graded Betti numbers. For $\mathbb{P}^{1}\times\mathbb{P}^{1}$,
[giuffrida-92]*Proposition 3.3 show that Betti numbers can be expressed via a
certain “second difference matrix” of $H_{X}$, and the authors of [HNV-points]
and [booms-peot] exploited this in their study of virtual resolutions for sets
of points in $\mathbb{P}^{1}\times\mathbb{P}^{1}$. In our proof of 1.3, we
similarly use an analogous observation that for
$\mathbb{P}^{n}\times\mathbb{P}^{m}$.

######  Definition 1.4.

Define a partial order on $\mathbb{Z}^{2}$ by letting
$(i,j)\geq(i^{\prime},j^{\prime})$ if $i\geq i^{\prime}$ and $j\geq
j^{\prime}$. For any infinite matrix $H=(H_{i,j})$ indexed by
$(i,j)\in\mathbb{Z}^{2}$, the _column difference operator_ $\Delta^{C}$ and
_row difference operator_ $\Delta^{R}$ are

$\displaystyle\Delta^{C}(H)_{i,j}:=H_{i,j}-H_{i-1,j}\qquad\text{and}\qquad\Delta^{R}(H)_{i,j}:=H_{i,j}-H_{i,j-1}.$

Note that the operators $\Delta^{C}$ and $\Delta^{R}$ commute.

######  Proposition 1.5.

If $M$ is a finitely generated bigraded $S$-module with minimal free
resolution

$F_{\bullet}:\quad\bigoplus_{i,j\geq
0}S(-i,-j)^{\beta_{0,(i,j)}}\leftarrow\bigoplus_{i,j\geq
0}S(-i,-j)^{\beta_{1,(i,j)}}\leftarrow\cdots\leftarrow\bigoplus_{i,j\geq
0}S(-i,-j)^{\beta_{k,(i,j)}}\leftarrow\cdots,$

then the Hilbert matrix $H_{M}$ satisfies

$\big{(}(\Delta^{C})^{n+1}(\Delta^{R})^{m+1}H_{M}\big{)}_{i,j}=B_{i,j},$

where
$B_{p,q}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{k=0}^{\infty}(-1)^{k}\beta_{k,(p,q)}$
for all $(p,q)\in\mathbb{Z}^{2}$.

### Outline

We examine syzygies of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$ in
Section 2 and prove 1.1. 1.5 is proven in Section 3. We then focus our
attention on $\mathbb{P}^{1}\times\mathbb{P}^{2}$, discussing our notion of
points in sufficiently general position in Section 4, including a weakened
statement of the Minimal Resolution Conjecture. Finally, we use this to prove
1.3 in Section 5.

### Acknowledgements

This work is a result of the University of Minnesota School of Mathematics REU
in Algebra and Combinatorics during Summer 2023, funded by NSF RTG Grant
DMS-1745638. The group is grateful for TA Sasha Pevzner’s guidance during the
REU. We also thank Daniel Erman for helpful conversations related to this work
and Gregory G. Smith for supplying a sketch of 4.1. CB was partially supported
by NSF Grant DMS 2001101.

##  2\. A short virtual resolution via intersection in
$\mathbb{P}^{n}\times\mathbb{P}^{m}$

By the end of this section, we prove 1.1. We begin with several preliminary
results. First, we note that after a change of coordinates, we may assume that
$y_{0}$ is a nonzero divisor on $S/I_{X}$; see 2.1.

For a point

$\mathbf{a}\times\mathbf{b}=[1:a_{1}:a_{2}:\cdots:a_{n}]\times[1:b_{1}:b_{2}:\cdots:b_{m}]\in\mathbb{P}^{n}\times\mathbb{P}^{m},$

and for $i,j>0$, let
$L_{a_{i}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=a_{i}x_{0}-x_{i}$
and
$L_{b_{j}}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=b_{j}y_{0}-y_{j}$.
Let

$I_{\mathbf{a}}=\langle L_{a_{1}},L_{a_{2}},\ldots,L_{a_{n}}\rangle\text{ and
}I_{\mathbf{b}}=\langle L_{b_{1}},L_{b_{2}},\ldots,L_{b_{m}}\rangle,$

so that $I_{\mathbf{a}}+I_{\mathbf{b}}$ is the bihomogeneous ideal for the
point $\mathbf{a}\times\mathbf{b}$.

######  Assumption 2.1.

Throughout this paper, we will consider a finite set of points
$X\subseteq\mathbb{P}^{n}\times\mathbb{P}^{m}$. After a linear change of
coordinates, we may and will assume that every point in $X$ is of the form
$[1:a_{1}:\cdots:a_{n}]\times[1:b_{1}:\cdots:b_{m}]$.

######  Notation 2.2.

Let $\pi_{1}(X)=\\{P_{1},P_{2},\ldots,P_{\ell}\\}$ denote the set of distinct
first coordinates in $X$, so $\ell=|\pi_{1}(X)|$. Let
$X_{k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\pi_{1}^{-1}(P_{k})\cap
X$ denote the pre-image in $X$ of $P_{k}$, and write

$X_{k}=\\{P_{k}\times Q_{k,1},P_{k}\times Q_{k,2},\ldots,P_{k}\times
Q_{k,r_{k}}\\}\subseteq X,$

where $r_{k}=|\pi_{1}^{-1}(P_{k})|$. Thus, for each $k$ with $1\leq
k\leq\ell$,

$\displaystyle I_{X_{k}}=I_{P_{k}}+\bigcap_{j=1}^{r_{k}}I_{Q_{k,j}}.$ (2.1)

Note that the ideal $I_{X}$ is necessarily $B$-saturated. For each
$j\in\\{1,2,\dots,\ell\\}$, let

$J_{j}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\bigcap_{k=1}^{j}I_{X_{k}}.$

Note that $J_{j}=I_{Y_{j}}$, where $Y_{j}=\bigsqcup_{k=1}^{j}X_{k}$ for $1\leq
j\leq\ell$.

######  Lemma 2.3.

Let $X$ be a set of at least two points in
$\mathbb{P}^{n}\times\mathbb{P}^{m}$ with $\ell=|\pi_{1}(X)|$ and $J_{\ell-1}$
as in 2.2. If $t\geq\ell-1$, then $\langle\mathbf{x}\rangle^{t}\subseteq
I_{X_{\ell}}+J_{\ell-1}$.

###### Proof.

We prove this statement by induction on $\ell=|\pi_{1}(X)|$. The base case
$\ell=1$ is trivial. If $\ell=2$, then $I_{X_{1}}=\langle
L_{a_{1}},\ldots,L_{a_{n}},G_{1},G_{2},\ldots,G_{k}\rangle$, where $L_{a_{i}}$
is a linear form in $x_{0}$ and $x_{i}$, and each $G_{i}$ is a polynomial in
the $\mathbf{y}$-variables; the ideal $I_{X_{2}}=\langle
L_{a_{1}}^{\prime},\ldots,L_{a_{n}}^{\prime},G_{1}^{\prime},G_{2}^{\prime},\ldots,G_{k^{\prime}}^{\prime}\rangle$
is of the same form. Then together,

$I_{X_{1}}+I_{X_{2}}=\langle
x_{0},x_{1},\dots,x_{n},G_{1},G_{2},\ldots,G_{k},G_{1}^{\prime},G_{2}^{\prime},\ldots,G_{k^{\prime}}^{\prime}\rangle,$

which contains $\langle\mathbf{x}\rangle^{t}$ for all $t\geq 1$, as desired.

Now for any $\ell>2$, write $X=Y_{1}\sqcup Y_{2}\sqcup X_{\ell}$, where
$Y_{1}=\bigsqcup_{k=1}^{\ell-2}{X_{k}}$ and $Y_{2}={X_{\ell-1}}$, so
$|\pi_{1}(Y_{1})|=\ell-2$ and $|\pi_{1}(Y_{2})|=1$. Then by the inductive
hypothesis,

$\langle\mathbf{x}\rangle^{\ell-2}\subseteq
I_{X_{\ell}}+I_{Y_{1}}\qquad\text{and}\qquad\langle\mathbf{x}\rangle\subseteq
I_{X_{\ell}}+I_{Y_{2}}.$

Putting these together yields the desired result:

$\displaystyle\langle\mathbf{x}\rangle^{\ell-2}\cdot\langle\mathbf{x}\rangle\subseteq(I_{X_{\ell}}+I_{Y_{1}})\cdot(I_{X_{\ell}}+I_{Y_{2}})\subseteq
I_{X_{\ell}}+\left(I_{Y_{1}}\cap
I_{Y_{2}}\right)=I_{X_{\ell}}+\bigcap_{k=1}^{\ell-1}I_{X_{k}}=I_{X_{\ell}}+J_{\ell-1}.\qquad\quad\,\qed$

We now begin working towards 2.7, which provides a primary decomposition of
$\left\langle I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle$, the
final ingredient needed to prove 1.1.

######  Lemma 2.4.

If $I$ is an ideal in $S$ such that $S/I$ has a nonzero divisor $L$ of degree
$(0,1)$, then for all $(i,j)\in\mathbb{Z}^{2}$,

$H_{S/(I+\langle L\rangle)}(i,j)=H_{S/I}(i,j)-H_{S/I}(i,j-1).$

###### Proof.

There is a graded short exact sequence

$0\to\frac{S}{I:\langle L\rangle}(0,-1)\xrightarrow{\ \ \cdot\overline{L}\ \
}\frac{S}{I}\longrightarrow\frac{S}{I+\langle L\rangle}\to 0,$

and, since $L$ is a nonzero divisor on $S/I$, $I:\langle L\rangle=I$, so the
desired equality of Hilbert functions follows. ∎

######  Lemma 2.5.

Let $X$ be a finite set of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$ as
in 2.1. If $i\geq|\pi_{1}(X)|-1$, then there is an equality of bigraded pieces
for all $j\in\mathbb{Z}$:

$\left[\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\right]_{(i,j)}=\left[\langle
I_{X},y_{0}\rangle\right]_{(i,j)}.$ (2.2)

###### Proof.

Because the vector space on the right-hand side of (2.2) is contained in the
left-hand side, it suffices to show that these vector spaces have the same
dimension, which we use induction on
$\ell\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=|\pi_{1}(X)|$.
The base case $\ell=1$ is a tautology for all $i$.

By way of induction, suppose that $\ell>1$ and (2.2) holds for all sets of
points with strictly fewer distinct first coordinates than $X$. To examine the
right-hand side of (2.2), note that 2.1 and 2.4 together imply that

$H_{S/\langle I_{X},y_{0}\rangle}(i,j)=H_{S/I_{X}}(i,j)-H_{S/I_{X}}(i,j-1).$
(2.3)

Since $I_{X}=\bigcap_{k=1}^{\ell}I_{X_{k}}$, there is a graded short exact
sequence

$0\to S/I_{X}\to S/J_{\ell-1}\oplus S/I_{X_{\ell}}\to
S/(J_{\ell-1}+I_{X_{\ell}})\to 0,$

where $J_{\ell-1}$ is as in 2.2. By 2.3, the ideal $J_{\ell-1}+\langle
I_{X_{\ell}}\rangle$ contains $\langle\mathbf{x}\rangle^{\ell-1}$. Hence
$H_{S/(J_{\ell-1}+I_{X_{\ell}})}(i,j)=0$ for all $i\geq\ell-1$, so by the
additivity of Hilbert functions on graded short exact sequences, for all $j$,

$\displaystyle H_{S/I_{X}}(i,j)$
$\displaystyle=H_{S/J_{\ell-1}}(i,j)+H_{S/I_{X_{\ell}}}(i,j)$ (2.4)
$\displaystyle\text{and}\quad H_{S/I_{X}}(i,j-1)$
$\displaystyle=H_{S/J_{\ell-1}}(i,j-1)+H_{S/I_{X_{\ell}}}(i,j-1).$ (2.5)

Combining (2.3), (2.4), and (2.5) yields the following expression for the
Hilbert function of the right-hand side of (2.2):

$H_{S/\langle
I_{X},y_{0}\rangle}(i,j)=H_{S/J_{\ell-1}}(i,j)+H_{S/I_{X_{\ell}}}(i,j)-H_{S/J_{\ell-1}}(i,j-1)-H_{S/I_{X_{\ell}}}(i,j-1).$
(2.6)

Now to examine the left-hand side of (2.2), it follows from the inductive
hypothesis that

$\left[\bigcap_{k=1}^{\ell-1}\langle
I_{X_{k}},y_{0}\rangle\right]_{(i,j)}=\left[\bigcap_{k=1}^{\ell-1}I_{X_{k}}+\langle
y_{0}\rangle\right]_{(i,j)}.$

Since there is a graded short exact sequence

$0\to\frac{S}{\bigcap_{k=1}^{\ell}\langle
I_{X_{k}},y_{0}\rangle}\to\frac{S}{J_{\ell-1}+\langle
y_{0}\rangle}\oplus\frac{S}{I_{X_{\ell}}+\langle
y_{0}\rangle}\to\frac{S}{J_{\ell-1}+I_{X_{\ell}}+\langle y_{0}\rangle}\to 0,$

the following equality of Hilbert functions holds for all $j$:

$H_{S/\bigcap_{k=1}^{\ell}\langle
I_{X_{k}},y_{0}\rangle}(i,j)=H_{S/(J_{\ell-1}+\langle
y_{0}\rangle)}(i,j)+H_{S/(I_{X_{\ell}}+\langle
y_{0}\rangle)}(i,j)-H_{S/(J_{\ell-1}+I_{X_{\ell}}+\langle
y_{0}\rangle)}(i,j).$

Next, by 2.3, since $i\geq|\pi_{1}(X)|-1$, there is a containment
$\langle\mathbf{x}\rangle^{i}\subseteq J_{\ell-1}+I_{X_{\ell}}$, so

$S_{i,j}=\left[\bigcap_{k=1}^{\ell-1}I_{X_{k}}+I_{X_{\ell}}\right]_{(i,j)}\qquad\text{and}\qquad
H_{S/(J_{\ell-1}+I_{X_{\ell}}+\langle y_{0}\rangle)}(i,j)=0.$

Since $y_{0}$ is a nonzero divisor on $S/J_{\ell-1}$ and $S/I_{X_{\ell}}$, by
2.4, for all $j$,

$\displaystyle H_{S/(J_{\ell-1}+\langle y_{0}\rangle)}(i,j)$
$\displaystyle=H_{S/J_{\ell-1}}(i,j)-H_{S/J_{\ell-1}}(i,j-1)$
$\displaystyle\text{and}\qquad H_{S/(I_{X_{\ell}}+\langle y_{0}\rangle)}(i,j)$
$\displaystyle=H_{S/I_{X_{\ell}}}(i,j)-H_{S/I_{X_{\ell}}}(i,j-1).$

Comparing with (2.6), it follows that for $i\geq\ell-1$,

$H_{S/\langle I_{X},y_{0}\rangle}(i,j)=H_{S/\bigcap_{k=1}^{\ell}\langle
I_{X_{k}},y_{0}\rangle}(i,j),$

so (2.2) is an equality, as desired. ∎

When a set of points $X$ has a generic Hilbert function, equality can be
obtained sooner.

######  Corollary 2.6.

If $X$ is a finite set of points with generic Hilbert function in
$\mathbb{P}^{n}\times\mathbb{P}^{m}$ as in 2.1 and $d=\min\\{r\mid
T_{r,n}\geq|X|\\}$, then (2.2) holds for all $i\geq d$ and $j\in\mathbb{Z}$.

###### Proof.

First consider the case that $j=0$. Here,

$\left[\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\right]_{(i,0)}=[I_{X}]_{(i,0)}\qquad\text{and}\qquad\left[\langle
I_{X},y_{0}\rangle\right]_{(i,0)}=[I_{X}]_{(i,0)},$

so (2.2) holds. When $j\geq 1$, just as in 2.5, because the vector space on
the right-hand side (RHS) of (2.2) is contained in the left-hand side (LHS),
it suffices to show that for all $i\geq d$, the dimension of the RHS is is
greater than or equal to the dimension of the LHS. This is equivalent to
showing that

$\dim_{\Bbbk}\left[\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\right]_{(i,j)}\leq\dim_{\Bbbk}\left[\langle
I_{X},y_{0}\rangle\right]_{(i,j)}.$

In turn, this is equivalent to showing $H_{RHS}(i,j)\leq H_{LHS}(i,j)$. By 2.1
and 2.4, it follows that

$H_{RHS}(i,j)=H_{S/\langle
I_{X},y_{0}\rangle}(i,j)=H_{S/I_{X}}(i,j)-H_{S/I_{X}}(i,j-1).$

Since the points are in sufficiently general position and $i\geq d$,
$H_{S/I_{X}}(i,j)=H_{S/I_{X}}(i,j-1)=|X|$, so $H_{RHS}(i,j)=0$. ∎

######  Proposition 2.7.

Let $X$ be a finite set of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$ as
in 2.1 and 2.2. Then for any integer $t\geq|\pi_{1}(X)|-1$, there is a primary
decomposition of the form

$\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle=\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\cap\langle\langle\mathbf{x}\rangle^{t},y_{0}\rangle.$

######  Remark 2.8.

Note that when $m=1$, then the statement of 2.7 can be made more explicit,
since for each point $\mathbf{a}\times\mathbf{b}\in X$,
$I_{\mathbf{a}\times\mathbf{b}}=\langle L_{a_{1}},\ldots
L_{a_{n}},L_{b_{1}}\rangle$. Then by (2.1), for any $P_{k}\in\pi_{1}(X)$,

$I_{X_{k}}=\langle
L_{P_{k,1}},L_{P_{k,2}},\ldots,L_{P_{k,n}},L_{Q_{k,1}}L_{Q_{k,2}}\cdots
L_{Q_{k,r_{k}}}\rangle.$

Since each $L_{Q_{k,j}}$ is a linear form in $y_{0}$ or $y_{1}$, their product
will be a polynomial of degree $r_{k}$ in $y_{0}$ and $y_{1}$. By 2.1, each
$Q_{k,j}$ is of the form $[b_{j,0}:b_{j,1}]$, with $b_{j,0}=1$. Therefore, the
product of the $L_{Q_{k,j}}$’s will have a term $y_{1}^{r_{k}}$. Thus

$\langle I_{X_{k}},y_{0}\rangle=\langle
L_{P_{k,1}},L_{P_{k,2}},\ldots,L_{P_{k,n}},y_{0},y_{1}^{r_{k}}\rangle.$

###### Proof of 2.7.

For any $S$-ideals $I_{1},I_{2},I_{3}$, $(I_{1}\cap
I_{2})+I_{3}\subseteq(I_{1}+I_{3})\cap(I_{2}+I_{3})$; in particular, for all
$t\geq 0$,

$\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle\subseteq\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\cap\left\langle\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle.$
(2.7)

We will now show that when $t\geq|\pi_{1}(X)|-1$, the left-hand side of (2.7)
contains the right-hand side, and it suffices to do so on each bigraded piece,
i.e., show that for all $(i,j)\in\mathbb{Z}^{2}$ and $t\geq|\pi_{1}(X)|-1$,

$\left[\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\cap\left\langle\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle\right]_{(i,j)}\subseteq\left[\left\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle\right]_{(i,j)}.$
(2.8)

We consider two cases, based on a comparison between $i$ and $t$. First,
$0\leq i<t$ and suppose that $f$ is in the left-hand side of (2.8); in
particular,
$f\in\left[\langle\langle\mathbf{x}\rangle^{t},y_{0}\rangle\right]_{(i,j)}$.
Since $i<t$ by assumption, $f$ is of low degree, so it must be that
$f\in\langle y_{0}\rangle$. This clearly also places $f$ in the right-hand
side of (2.8), so the equality holds in this case.

Second, if $i\geq t$, then $[\langle\mathbf{x}\rangle^{t}]_{i,j}=S_{(i,j)}$,
so

$\left[\left\langle\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle\right]_{(i,j)}=S_{(i,j)}\qquad\text{and}\qquad\left[\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle\right]_{(i,j)}=\left[\langle
I_{X},y_{0}\rangle\right]_{(i,j)}.$

Thus it suffices to show that for $i\geq t$,

$\left[\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\right]_{(i,j)}\subseteq\left[\langle
I_{X},y_{0}\rangle\right]_{(i,j)},$

which was shown in 2.5, finishing this case. Having established both cases, we
have now shown that (2.7) is an equality for $t\geq|\pi_{1}(x)|-1$.

It now remains to show that the ideals on the right-hand side of (2.7) are
primary. By [monomial-algebras-book]*Proposition 6.1.7,
$\left\langle\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle$ is primary. To
see that $\langle I_{X_{k}},y_{0}\rangle$ is primary for each $1\leq
k\leq|\pi_{1}(X)|$, recall from 2.2 that for each $k$, $X_{k}=\\{P_{k}\times
Q_{k,1},\ldots,P_{k}\times Q_{k,r_{k}}\\}$ and

$\displaystyle\langle I_{X_{k}},y_{0}\rangle\ =\
I_{P_{k}}+\bigcap_{j=1}^{r_{k}}I_{Q_{k,j}}+\langle y_{0}\rangle\ =\
\left\langle
L_{P_{k,1}},L_{P_{k,2}},\ldots,L_{P_{k,n}},G_{1},G_{2},\ldots,G_{s},y_{0}\right\rangle,$

where $L_{P_{k,i}}=P_{k,i}x_{0}-x_{i}$ (with $P_{k,i}$ allowed to be $0$) are
the linear forms generating each $I_{P_{k}}$ and $G_{1},G_{2},\dots,G_{s}$ are
forms in the $\mathbf{y}$ such that $\langle
G_{1},G_{2},\dots,G_{s}\rangle=\bigcap_{j=1}^{r_{k}}I_{Q_{k,j}}$. Putting this
together,

$S/\langle I_{X_{k}},y_{0}\rangle=S/\left\langle
L_{P_{k,1}},L_{P_{k,2}},\ldots,L_{P_{k,n}},G_{1},G_{2},\dots,G_{s},y_{0}\right\rangle\\\
\cong\Bbbk[x_{0},y_{0},y_{1},\ldots,y_{m}]/\left\langle
G_{1},G_{2},\dots,G_{s},y_{0}\right\rangle,$

so it suffices to show that the ideal
$J\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\langle
G_{1},G_{2},\dots,G_{s},y_{0}\rangle$ is primary in
$\Bbbk[x_{0},y_{0},\dots,y_{m}]$. To this end, let $J^{\prime}$ denote the
ideal generated by the same elements, but viewed as an ideal of
$\Bbbk[y_{0},\dots,y_{m}]$. Since
$J=J^{\prime}\Bbbk[x_{0},y_{0},\dots,y_{m}]$, it suffices to show that
$J^{\prime}$ is primary in $\Bbbk[y_{0},\dots,y_{m}]$. Now by 2.1,
$Q_{k,j}=[1:Q_{k,{j_{1}}}:\ldots:Q_{k,{j_{m}}}]$, so

$I_{Q_{k,j}}=\langle
Q_{k,{j_{1}}}y_{0}-y_{1},\ldots,Q_{k,{j_{m}}}y_{0}-y_{m}\rangle.$

Combining this with

$\left\langle\prod_{j=1}^{r_{k}}I_{Q_{k,j}},y_{0}\right\rangle\subseteq\left\langle\bigcap_{j=1}^{r_{k}}I_{Q_{k,j}},y_{0}\right\rangle=J^{\prime},$

it follows that $\langle y_{0},\ldots,y_{m}\rangle^{r_{k}}\subseteq
J^{\prime}\subseteq\langle y_{0},\ldots,y_{m}\rangle$, so the radical of
$J^{\prime}$ is $\langle\mathbf{y}\rangle$, which is maximal in
$\Bbbk[y_{0},\ldots,y_{m}]$. Thus $J^{\prime}$ is primary in
$\Bbbk[y_{0},\ldots,y_{m}]$, as desired. ∎

We are now prepared to prove the main result of this section.

###### Proof of 1.1.

Since the ideal $I_{X}$ is $B$-saturated,
$I_{X}\cap\langle\mathbf{x}\rangle^{t}:B^{\infty}=I_{X}$. Thus a minimal free
resolution of $S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$ is indeed a virtual
resolution of $S/I_{X}$.

Next, note that by [virtual-original]*Proposition 2.5.a, the minimal free
resolution of $S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$ has length at least
$n+m$, the codimension of $I_{X}$. It is thus left to show that the minimal
free resolution of $S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$ is of length at
most (and thus equal to) $n+m$. To begin, by the Auslander–Buchsbaum formula,

$\operatorname{pdim}(S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})=n+m+2-\operatorname{depth}(S/(I_{X}\cap\langle\mathbf{x}\rangle^{t}),$

thus it suffices to show that the depth of
$S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$ is at least $2$. To do this, we
produce a regular sequence on $S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$ of
length two.

Without loss of generality by 2.1, $y_{0}$ is a nonzero divisor on $S/I_{X}$.
Further, we claim that $y_{0}$ is a nonzero divisor on
$S/(I_{X}\cap\langle\mathbf{x}\rangle^{t})$. Indeed, if $f\in S$ with
$y_{0}f\in I_{X}\cap\langle\mathbf{x}\rangle^{t}$, then $y_{0}f\in I_{X}$ and
$y_{0}f\in\langle\mathbf{x}\rangle^{t}$. This will only happen if $f\in
I_{X}\cap\langle\mathbf{x}\rangle^{t}$, establishing the claim. We are now
left to produce a nonzero divisor on $S/\left\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\right\rangle$.

To find such a nonzero divisor, note that since $t\geq|\pi_{1}(X)|-1$, 2.7
provides the primary decomposition

$\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle=\bigcap_{P_{k}\in\pi_{1}(X)}\langle
I_{X_{k}},y_{0}\rangle\cap\langle\langle\mathbf{x}\rangle^{t},y_{0}\rangle.$

Now from (2.1),

$\displaystyle\langle I_{X_{k}},y_{0}\rangle$
$\displaystyle=I_{P_{k}}+\bigcap_{j=1}^{r_{k}}I_{Q_{k,j}}+\langle
y_{0}\rangle,$

so the zero divisors of $S/\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle$ are the elements belonging
to the associated primes of $S/\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle$, namely

$\displaystyle\bigcup_{P_{k}\in\pi_{1}(X)}\sqrt{\langle
I_{X_{k}},y_{0}\rangle}\cup\sqrt{\langle\langle\mathbf{x}\rangle^{t},y_{0}\rangle}=\bigcup_{P_{k}\in\pi_{1}(X)}\langle
I_{P_{k}},G_{1},G_{2},\ldots,G_{s},y_{0}\rangle\cup\langle\mathbf{x},y_{0}\rangle,$
(2.9)

where each $G_{i}$ is a polynomial in only the $\mathbf{y}$-variables. Thus,
let $L$ be any element of degree $(1,0)$ in $S$ such that $L$ does not vanish
at any point in $\pi_{1}(X)$. In this way, $L+y_{1}$ does not belong to the
set in (2.9), so $L+y_{1}$ is a nonzero divisor on $S/\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t},y_{0}\rangle$. Therefore, $S/\langle
I_{X}\cap\langle\mathbf{x}\rangle^{t}\rangle$ has depth at least $2$, so its
minimal free resolution has length (at most) $n+m$, as desired. ∎

######  Remark 2.9.

Note that the bound shown in 1.1 is not necessarily a sharp one. For points
with generic Hilbert function, we can improve the bound given in 1.1. In this
case, the minimal free resolution of $I_{X}\cap\langle\mathbf{x}\rangle^{t}$
is a virtual resolution of $I_{X}$ of length $m+n$ whenever $t\geq\min\\{r\mid
T_{r,n}\geq|X|\\}$. To see this, apply 2.6 and then follow the proofs of 2.7
and 1.1.

##  3\. Difference Hilbert matrices and Betti numbers

In this section, we prove 1.5, which relates a certain difference matrix of a
Hilbert matrix to the Betti numbers of the corresponding free resolution.

Recall that $S$ is the Cox ring of $\mathbb{P}^{n}\times\mathbb{P}^{m}$ and
$M$ a finitely generated bigraded $S$-module with minimal bigraded free
resolution $F_{\bullet}$ with Betti numbers $\beta_{k,(i,j)}$ and for all
$(p,q)\in\mathbb{Z}^{2}$,
$B_{p,q}=\sum_{k=0}^{\infty}(-1)^{k}\beta_{k,(p,q)}$. Recall $\Delta^{C}$ and
$\Delta^{R}$ from 1.4, and let

$T_{i,n}:=\binom{i+n}{n}$

denote the number of monomials of degree $i$ in
$\Bbbk[x_{0},x_{1},\dots,x_{n}]$, so $T_{i,n}T_{j,m}=H_{S}(i,j)$.

######  Lemma 3.1.

There is an equality
$H_{M}(i,j)=\sum_{(p,q)\leq(i,j)}T_{i-p,n}T_{j-q,m}B_{p,q}$.

###### Proof.

For all $k\geq 0$, $H_{S}(i,j)=T_{i,n}T_{j,m}$ and $F_{k}=\bigoplus_{p,q\geq
0}S(-p,-q)^{\beta_{k,(p,q)}}$, so

$\displaystyle H_{F_{k}}(i,j)=\dim_{\Bbbk}(F_{k})_{i,j}$
$\displaystyle=\sum_{(p,q)\leq(i,j)}\dim_{\Bbbk}(S(-p,-q)_{i,j})^{\beta_{k,(p,q)}}$
$\displaystyle=\sum_{(p,q)\leq(i,j)}\dim_{\Bbbk}(S_{i-p,j-q})^{\beta_{k,(p,q)}}$
$\displaystyle=\sum_{(p,q)\leq(i,j)}T_{i-p,n}T_{j-q,m}\beta_{k,(p,q)}.$ (3.1)

By definition of $B_{p,q}$, for any $(p,q)\leq(i,j)$ and $k$ sufficiently
large, $\beta_{k,(p,q)}=0$ and thus $H_{F_{k}}(i,j)=0$. Since $0\leftarrow
M\leftarrow F_{\bullet}$ is an exact sequence in the category of graded
$S$-modules,

$H_{M}(i,j)=\sum_{k=0}^{\infty}(-1)^{k}H_{F_{k}}(i,j).$

Substituting (3) into the right hand side now yields the desired result. ∎

######  Lemma 3.2.

Two identities hold for $\Delta^{C}$ and $\Delta^{R}$ applied to the Hilbert
matrix of $M$:

$\displaystyle(\Delta^{C}H_{M})(i,j)$
$\displaystyle=\sum_{(p,q)\leq(i,j)}T_{i-p,n-1}T_{j-q,m}B_{p,q}$
$\displaystyle\text{and}\quad(\Delta^{R}H_{M})(i,j)$
$\displaystyle=\sum_{(p,q)\leq(i,j)}T_{i-p,n}T_{j-q,m-1}B_{p,q}.$

###### Proof.

We prove the identity for $\Delta^{C}$; the proof for $\Delta^{R}$ is
analogous. By 3.1,

$\displaystyle H_{M}(i,j)$
$\displaystyle=\sum_{(p,q)\leq(i,j)}T_{i-p,n}T_{j-q,m}B_{p,q}.$

Now separate the sum into two parts, noting that when $p=i$,
$T_{i-p,n}=T_{0,n}=1$, so that

$\displaystyle H_{M}(i,j)$ $\displaystyle=\sum_{q\leq
j}T_{j-q,m}B_{i,q}+\sum_{(p,q)\leq(i-1,j)}T_{i-p,n}T_{j-q,m}B_{p,q}.$

By 3.1 applied to $(i-1,j)$,

$H_{M}(i-1,j)=\sum_{(p,q)\leq(i-1,j)}T_{i-1-p,n}T_{j-q,m}B_{p,q}.$

Now by definition of $\Delta^{C}$,

$\displaystyle(\Delta^{C}H_{M})(i,j)$ $\displaystyle=H_{M}(i,j)-H_{M}(i-1,j)$
(3.2) $\displaystyle=\sum_{q\leq
j}T_{j-q,m}B_{i,q}+\sum_{(p,q)\leq(i-1,j)}(T_{i-p,n}-T_{i-1-p,n})T_{j-q,m}B_{p,q}.$

Using the binomial identities $T_{i-p,n}-T_{i-1-p,n}=T_{i-p,n-1}$, (3.2)
simplifies to

$\displaystyle(\Delta^{C}H_{M})(i,j)$ $\displaystyle=\sum_{q\leq
j}T_{j-q,m}B_{i,q}+\sum_{(p,q)\leq(i-1,j)}T_{i-p,n-1}T_{j-q,m}B_{p,q}.$

Recombining the last two sums yields

$(\Delta^{C}H_{M})(i,j)=\sum_{(p,q)\leq(i,j)}T_{i-p,n-1}T_{j-q,m}B_{p,q}.\qed$

1.5 now follows by applying each of $\Delta^{C}$ and $\Delta^{R}$ repeatedly.

###### Proof of 1.5.

Combining Lemmas 3.1 and 3.2,

$\displaystyle G_{M}(i,j)$
$\displaystyle\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\big{(}(\Delta^{C})^{n}(\Delta^{R})^{m}H_{M}\big{)}(i,j)$
$\displaystyle\;=\sum_{(p,q)\leq(i,j)}T_{i-p,0}T_{j-q,0}B_{p,q}$
$\displaystyle\;=\sum_{(p,q)\leq(i,j)}B_{p,q}.$

Now applying $\Delta^{C}$,

$\displaystyle(\Delta^{C}G_{M})(i,j)$ $\displaystyle=G_{M}(i,j)-G_{M}(i-1,j)$
$\displaystyle=\sum_{(p,q)\leq(i,j)}B_{p,q}-\sum_{(p,q)\leq(i-1,j)}B_{p,q}\,\,=\,\,\sum_{q\leq
j}B_{i,q},$ so applying $\Delta^{R}$ yields the desired result:
$\displaystyle(\Delta^{R}\Delta^{C}G_{M})(i,j)$ $\displaystyle=\sum_{q\leq
j}B_{i,q}-\sum_{q\leq j-1}B_{i,q}\,=\,B_{i,j}.\qed$

##  4\. Sufficiently general points in $\mathbb{P}^{1}\times\mathbb{P}^{2}$

We now discuss the notion of sufficiently general points, as per the setting
of 1.3. We begin with the notion of a generic Hilbert function for $S/I_{X}$,
sketched for us by Gregory G. Smith. While this result holds over any smooth
toric variety, for continuity of notation, we state the result only for
$\mathbb{P}^{n}\times\mathbb{P}^{m}$.

######  Proposition 4.1.

For every $N\geq 1$ and all $n,m\geq 1$, there exists a dense open subset
$U\subseteq(\mathbb{P}^{n}\times\mathbb{P}^{m})^{N}$, such that for any
$X=\\{P_{1},P_{2},\dots,P_{N}\\}\subseteq\mathbb{P}^{n}\times\mathbb{P}^{m}$,
if $(P_{1},P_{2},\dots,P_{N})\in U$, then

$H_{X}(i,j)=\min\\{|X|,T_{i,n}T_{j,m}\\}\quad\text{for all}\quad i,j\geq 0,$

where
$T_{i,n}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\binom{i+n}{n}$
is equal to the number of monomials of degree $i$ in
$\Bbbk[x_{0},x_{1},\dots,x_{n}]$.

###### Proof.

A natural parameter space for $N$ distinct points in
$\mathbb{P}^{n}\times\mathbb{P}^{m}$ is simply the open subset of
$(\mathbb{P}^{n}\times\mathbb{P}^{m})^{N}$, the $N$-fold product of
$\mathbb{P}^{n}\times\mathbb{P}^{m}$, obtained by removing the large
diagonals, i.e., subsets where two points are equal. Note that the Hilbert
function of the Cox ring $S$ of $\mathbb{P}^{n}\times\mathbb{P}^{m}$ at
$(i,j)\in\mathbb{N}^{2}$ is $H_{S}(i,j)=T_{i,n}T_{j,m}$.

If the Hilbert function of a set $Y$ of $N$ distinct points disagrees with
$H_{S}(i,j)$ for some $(i,j)\in\mathbb{N}^{2}$, then it must be strictly
smaller. It follows that matrix with $N$ rows and $H_{S}(i,j)$ columns,
corresponding to evaluating the $N$ points in $Y$ at the monomial basis for
the Cox ring $S$ in degree $(i,j)$ has less than maximal rank. Thus the
corresponding maximal minors of the matrix, interpreted as polynomial
equations in the Cox ring of the parameter space
$(\mathbb{P}^{n}\times\mathbb{P}^{m})^{N}$, determine a closed subset that
contains $Y$, as desired. ∎

######  Example 4.2.

If $X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$ is a finite set of
sufficiently general points with $|X|=N\geq 12$,

$N=6q+r=3q^{\prime}+r^{\prime}\quad\text{with}\quad 0\leq r\leq
5\quad\text{and}\quad 0\leq r^{\prime}\leq 2,$

$c_{j}=\max\\{c\mid cT_{j,2}<N\\}$, and $d=\min\\{j\mid T_{j,2}\geq|X|\\}$,
then the Hilbert matrix of $S/I_{X}$ is

$\small H_{X}=\bordermatrix{~{}&0&1&2&\cdots&j&\cdots&d&d+1&\cdots\cr
0&1&3&6&\cdots&T_{j,2}&\cdots&N&N&\cdots\cr
1&2&6&12&\cdots&2T_{j,2}&\cdots&N&N&\cdots\cr\vdots&\vdots&\vdots&\vdots&&\vdots&&\vdots&\vdots&\cr
c_{j}-1&c_{j}&3c_{j}&6c_{j}&\cdots&c_{j}T_{j,2}&\cdots&N&N&\cdots\cr
c_{j}&c_{j}+1&3(c_{j}+1)&6(c_{j}+1)&\cdots&N&\cdots&N&N&\cdots\cr\vdots&\vdots&\vdots&\vdots&&\vdots&&\vdots&\vdots&\cr
q-1&q&3q&6q&\cdots&N&\cdots&N&N&\cdots\cr
q&q+1&3q+3&N&\cdots&N&\cdots&N&N&\cdots\cr\vdots&\vdots&\vdots&\vdots&&\vdots&&\vdots&\vdots&\cr
q^{\prime}-1&q^{\prime}&3q^{\prime}&N&\cdots&N&\cdots&N&N&\cdots\cr
q^{\prime}&q^{\prime}+1&N&N&\cdots&N&\cdots&N&N&\cdots\cr\vdots&\vdots&\vdots&\vdots&&\vdots&&\vdots&\vdots&\cr
N-1&N&N&N&\cdots&N&\cdots&N&N&\cdots\cr
N&N&N&N&\cdots&N&\cdots&N&N&\cdots\cr\vdots&\vdots&\vdots&\vdots&&\vdots&&\vdots&\vdots&\ddots\cr}.\normalsize\qed$

Moving towards 1.3, we now turn our attention to the specific setting of
$\mathbb{P}^{1}\times\mathbb{P}^{2}$, for which we need an additional
assumption on set of points that restricts their first Betti numbers.

######  Notation 4.3.

Given a matrix $H$ with indices $(i,j)\in\mathbb{Z}^{2}$, set

$DH\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(\Delta^{C})^{2}(\Delta^{R})^{3}H.$
(4.1)

For a finite set of points $X$ in $\mathbb{P}^{1}\times\mathbb{P}^{2}$, 1.5
implies that the Betti numbers of $S/I_{X}$ satisfy

$DH_{X}(i,j)=-\beta_{1,(i,j)}+\beta_{2,(i,j)}-\beta_{3,(i,j)}+\beta_{4,(i,j)}.$
(4.2)

for all $(i,j)>(0,0)$. Ideally, we would like to say that under certain
assumptions (for example, when $X$ has generic Hilbert matrix), the matrix
$DH_{X}$ completely determines all Betti numbers of $S/I_{X}$. This amounts to
saying that a certain version of the Minimal Resolution Conjecture (MRC) holds
for sets of points in $\mathbb{P}^{1}\times\mathbb{P}^{2}$.

Originally formulated by Lorenzini in [lorenzini] for points in
$\mathbb{P}^{n}$, the MRC states that for a set of points in sufficiently
general position, Betti numbers cannot overlap, meaning that
$\beta_{i,j}\beta_{i+1,j}=0$ for all $0\leq i\leq n$ and $j\in\mathbb{Z}$.
Later, Mustaţǎ generalized the MRC to sets of points in arbitrary projective
varieties [mustata]. A more detailed discussion of the history and current
status of the MRC can be found in the introduction of [booms-peot].

In [giuffrida-96], it is shown that the MRC holds for all sufficiently general
sets of points lying on a smooth quadric in $\mathbb{P}^{3}$. The techniques
of [giuffrida-96] are highly specific to the geometry of $\mathbb{P}^{3}$ and
therefore difficult to generalize to higher dimensions or multiprojective
spaces. The recent studies [HNV-points, booms-peot] of virtual resolutions for
points in $\mathbb{P}^{1}\times\mathbb{P}^{1}$ show a weakened partial version
of the MRC, which provides enough control to obtain their results.

For the purpose of our study, we now state a weakened version of the MRC for
points in $\mathbb{P}^{1}\times\mathbb{P}^{2}$ that parallels [giuffrida-96].
Here we only require that the Betti numbers $\beta_{1,(i,j)}$ are entirely
predicted by $DH_{X}$. This assumption provides enough control over Betti
numbers to prove 1.3.

######  Conjecture 4.4 (Weakened Minimal Resolution Conjecture).

Let $N\geq 2$ be an integer. There exists an dense open subset
$U\subseteq(\mathbb{P}^{1}\times\mathbb{P}^{2})^{N}$ such that for every
$(P_{1},P_{2},\dots,P_{N})\in U$, the set of points
$X=\\{P_{1},\dots,P_{N}\\}$ satisfies:

  1. (1)

$X$ has a generic Hilbert matrix as in 1.2, and

  2. (2)

For every fixed $(i,j)>(0,0)$, the bigraded Betti numbers of $S/I_{X}$ are
such that $\beta_{1,(i,j)}>0$ if and only if

$\displaystyle DH_{X}(i,j)<0\textrm{ and }DH_{X}(i^{\prime},j^{\prime})\leq
0\textrm{ for all }(i^{\prime},j^{\prime})\leq(i,j)\textrm{ with
}(i^{\prime},j^{\prime})\neq(0,0),$

with $DH$ as in 4.3, and whenever the above condition holds,
$\beta_{1,(i,j)}=-DH_{X}(i,j)$.

######  Example 4.5.

For each $2\leq N\leq 100$, we verified in Macaulay2 that 4.4 holds for $50$
random sets of $N$ points in $\mathbb{P}^{1}\times\mathbb{P}^{2}$ with generic
Hilbert function [M2]. ∎

##  5\. A short virtual of a pair resolution in
$\mathbb{P}^{1}\times\mathbb{P}^{2}$

In this section, we prove 1.3. To begin, The virtual of a pair construction is
one of the methods given by Berkesch, Erman, and Smith to construct virtual
resolutions, and it relies on Maclagan and Smith’s notion of multigraded
regularity. We do not define this invariant in general, but instead provide a
simplified characterization for our specific setting.

######  Proposition 5.1 (See [MS]*Proposition 6.7).

Let $X$ be a finite set of points in $\mathbb{P}^{n}\times\mathbb{P}^{m}$.
Then the _multigraded regularity_ of $S/I_{X}$ is

$\operatorname{reg}(S/I_{X})=\left\\{\mathbf{d}\in\mathbb{Z}^{2}\mid
H_{X}(\mathbf{d})=|X|\right\\}.$

######  Example 5.2.

Recall that for points in sufficiently general position in
$\mathbb{P}^{1}\times\mathbb{P}^{2}$, the Hilbert matrix is given by

$H_{X}(i,j)=\min\\{|X|,T_{i,1}T_{j,2}\\}\quad\text{for all}\quad i,j\geq 0,$

Therefore if $|X|=N$, then

$H_{X}(N-1,0)=\min\\{N,T_{N-1,1}T_{0,2}\\}=\min\\{N,N\\}=N,$

so $(N-1,0)\in\operatorname{reg}(S/I_{X})$ for all finite sets of $N$ points
$X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$. ∎

######  Theorem 5.3 (See [virtual-original]*Theorem 1.3).

Let $S$ be the Cox ring of $\mathbb{P}^{n}\times\mathbb{P}^{m}$, let $M$ be a
finitely generated bigraded $B$-saturated $S$-module, and let
$\mathbf{d}\in\mathbb{Z}^{2}$ be such that
$\mathbf{d}\in\operatorname{reg}(M)$. If $G_{\bullet}$ is the free subcomplex
of a minimal free resolution $F_{\bullet}$ of $M$ consisting of all summands
of $F_{\bullet}$ generated in degree at most $\mathbf{d}+(n,m)$, then
$G_{\bullet}$ is a virtual resolution of $M$.

As in [virtual-original], we call the virtual resolution in 5.3 the _virtual
resolution of the pair_ $(M,\mathbf{d})$. With this in hand, we are now
prepared to state the main result of this section, a more explicit version of
1.3 when $|X|\geq 12$. The case for smaller sets of points is handled in
Remark 5.5.

######  Theorem 5.4 (See 1.3).

Let $X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$ be a finite set of
sufficiently general points with $N=|X|\geq 12$. If 4.4 holds, then the
virtual of a pair construction for $\mathbf{d}=(N-1,0)$ yields a virtual
resolution of $S/I_{X}$ of the form

$S\leftarrow\begin{gathered}S(-q,-2)^{6-r}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-q-1,-2)^{r}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-q^{\prime},-1)^{3-r^{\prime}}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-q^{\prime}-1,-1)^{r^{\prime}}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-N,0)\end{gathered}\leftarrow\begin{gathered}S(-q^{\prime},-2)^{9-3r^{\prime}}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-q^{\prime}-1,-2)^{3r^{\prime}}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-N,-1)^{3}\end{gathered}\leftarrow S(-N,-2)^{3}\leftarrow
0,$

where $N=6q+r=3q^{\prime}+r^{\prime}$ with $0\leq r\leq 5$ and $0\leq
r^{\prime}\leq 2$. When $r$ (respectively, $r^{\prime}$) is zero, the term
$S(-q-1,-2)^{r}$ (respectively, $S(-q^{\prime}-1,-1)^{r^{\prime}}$ and
$S(-q^{\prime}-1,-2)^{3r^{\prime}}$) do not appear in the virtual resolution.

######  Remark 5.5.

In the case that $2\leq|X|\leq 11$, if we assume 4.4, then it is still true
that $S/I_{X}$ has a virtual resolution of length $3$ obtained by taking
$\mathbf{d}=(|X|-1,0)$ in 5.3, and the proofs are analogous to 5.4, but the
resulting virtual resolution has a slightly different form. These cases are
listed in Appendix A, and with 5.4, complete the proof of 1.3.

We now state two lemmas for the proof of 5.4.

######  Lemma 5.6.

Let $X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$ be a collection of points
with generic Hilbert matrix as in 1.2 with $N=|X|\geq 12$. If

$\small N=6q+r=3q^{\prime}+r^{\prime}\quad\text{with}\quad 0\leq r\leq
5\quad\text{and}\quad 0\leq r^{\prime}\leq 2,$

then using 4.3,

$DH_{X}=\blockarray{ccccc}\block{c(cccc)}0&100\cdots\\\ 1000\cdots\\\
\vdots\vdots\vdots\vdots\\\ q-1000\cdots\\\ q00r-6\cdots\\\ q+100-r\cdots\\\
q+2000\cdots\\\ \vdots\vdots\vdots\vdots\\\ q^{\prime}-1000\cdots\\\
q^{\prime}0r^{\prime}-39-3r^{\prime}\cdots\\\
q^{\prime}+10-r^{\prime}3r^{\prime}\cdots\\\ q^{\prime}+2000\cdots\\\
\vdots\vdots\vdots\vdots\\\ N-1000\cdots\\\ N-13-3\cdots\\\ N+1000\cdots\\\
\vdots\vdots\vdots\ddots\\\ \ .$

###### Proof.

Recall from 1.4 that $\Delta^{C}$ and $\Delta^{R}$ commute, and set
$\Delta\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\Delta^{C}\Delta^{R}=\Delta^{R}\Delta^{C}$.
In light of 4.2, straightforward computation yields

$\small H_{X}=\blockarray{ccccc}\block{c(cccc)}0&136\cdots\\\ 12612\cdots\\\
\vdots\vdots\vdots\vdots\\\ q-1q3q6q\cdots\\\ qq+13q+3N\cdots\\\
q+1q+23q+6N\cdots\\\ \vdots\vdots\vdots\vdots\\\
q^{\prime}-1q^{\prime}3q^{\prime}N\cdots\\\ q^{\prime}q^{\prime}+1NN\cdots\\\
q^{\prime}+1q^{\prime}+2NN\cdots\\\ \vdots\vdots\vdots\vdots\\\
N-1NNN\cdots\\\ NNNN\cdots\\\ \vdots\vdots\vdots\ddots\\\ \quad\
\text{\normalsize and}\quad\Delta
H_{X}=\blockarray{ccccc}\block{c(cccc)}0&123\cdots\\\ 1123\cdots\\\
\vdots\vdots\vdots\vdots\\\ q-1123\cdots\\\ q12r-3\cdots\\\ q+112-3\cdots\\\
\vdots\vdots\vdots\vdots\\\ q^{\prime}-112-3\cdots\\\
q^{\prime}1r^{\prime}-1-r^{\prime}\cdots\\\ q^{\prime}+11-10\cdots\\\
\vdots\vdots\vdots\vdots\\\ N-11-10\cdots\\\ N000\cdots\\\
\vdots\vdots\vdots\ddots\\\ \ .\normalsize\vspace*{-2mm}$

The result follows from direct computation. ∎

######  Lemma 5.7.

Let $X$ be a set of $N\geq 12$ points in sufficiently general position in
$\mathbb{P}^{1}\times\mathbb{P}^{2}$, and let $F_{\bullet}$ be the minimal
free resolution of $S/I_{X}$ with Betti numbers $\beta_{k,(i,j)}$. If
$DH_{X}(i,j)$ is the first positive entry in the $i$th row of $DH_{X}$
(excluding the $0$th and $1$st row), then $\beta_{2,(i,j)}=DH_{X}(i,j)$, i.e.,
that positive entry corresponds exactly to the number of first syzygies of
$S/I_{X}$ of degree $(i,j)$. Furthermore, $\beta_{2,(i,j^{\prime})}=0$ for all
$j^{\prime}<j$, i.e., there are no first syzygies of smaller degree coming
from that row.

###### Proof.

This argument follows the approach of [booms-peot]*Lemma 3.2. Let
$F_{\bullet}$ be the minimal free resolution of $S/I_{X}$. For $i\geq 0$, let
$C^{\leq i}$ denote the subcomplex of $F_{\bullet}$ with summands generated in
degree $\mathbf{a}=(a_{1},a_{2})$ such that $a_{1}\leq i$. These complexes
provide a filtration of $F_{\bullet}$, so for $i\geq 1$, let $C^{i}$ denote
the cokernel of the natural inclusion $C^{\leq i-1}\hookrightarrow C^{\leq
i}$.

When $K\gg N$, we claim that $C^{\leq i}$ is a virtual resolution of a pair
for $\left(S/I_{X},(i-1,K-2)\right)$. To see this, note that
$(0,N-2)\in\operatorname{reg}(S/I_{X})$ by 5.1. Thus
$(i-1,K-2)\in\operatorname{reg}(S/I_{X})$ for all $i\geq 1,K\gg N$. By
choosing $K$ to be the largest degree in the second coordinate of a generator
of any summand in $C^{\leq i}$, $C^{\leq i}$ is exactly the virtual resolution
of the pair $(S/I_{X},(i-1,K-2))$. Now $0\to C^{\leq i-1}\to C^{\leq i}\to
C^{i}\to 0$ is a short exact sequence of complexes, and $C^{\leq i-1}$ and
$C^{\leq i}$ are both virtual resolutions of $S/I_{X}$ by 5.3, so $C^{i}$ must
have irrelevant homology. Further, since the first coordinates of the degrees
of all generators in $C^{i}$ are fixed at $i$, it is actually a complex over
$\Bbbk[y_{0},y_{1},y_{2}]$ with homology modules annihilated by some power of
$\langle y_{0},y_{1},y_{2}\rangle$. The Acyclicity Lemma [eisenbud]*Lemma
20.11 thus ensures that $H_{k}(C^{i})=0$ for all $k>1$.

Now if $DH_{X}(i,j)$ is the first positive entry with $i\geq 2$ in the $i$th
row of $DH_{X}$, then

$C^{i}\colon\quad 0\leftarrow C^{i}_{1}\leftarrow C^{i}_{2}\leftarrow
C^{i}_{3}\leftarrow C^{i}_{4}\leftarrow 0$

is a minimal free resolution over $\Bbbk[y_{0},y_{1},y_{2}]$, so there are no
units in its maps and the minimal generating degrees of summands must increase
with homological degree.

By 4.4, it follows that the Betti numbers $\beta_{1,(i,j^{\prime})}$ come
precisely from the first negative entries of the $i$th row of $DH_{X}$, where
$j^{\prime}<j$. By inspection from 5.6, $0>DH_{X}(i,j-1)=\beta_{1,(i,j-1)}$
and thus $\beta_{1,(i,j)}=0$. Further, since the minimal degree of generators
must increase in $C^{i}$, $\beta_{3,(i,j)}=\beta_{4,(i,j)}=0$ and
$DH_{X}(i,j)=\beta_{2,(i,j)}$, as desired. ∎

We are now prepared to prove the main theorem of this section.

###### Proof of 5.4.

Since $X$ has the generic Hilbert matrix in 1.2, $H_{X}(N-1,0)=|X|=N$, so
$(N-1,0)\in\operatorname{reg}(S/I_{X})$ by [MS]*Proposition 6.7. Thus 5.3
produces a virtual resolution of $S/I_{X}$ that is the subcomplex of the
minimal free resolution of $S/I_{X}$ consisting of all summands generated in
degrees at most $(N,2)$.

We now examine the minimal free resolution of $S/I_{X}$. By 4.4, the first
Betti numbers can be read from the first negative entries in the rows of
$DH_{X}$, and these occurs at positions
$(q,2),(q+1,2),(q^{\prime},1),(q^{\prime}+1,1)$, and $(N,0)$ by 5.6. Since
graded Betti numbers in a minimal free resolution must increase in degree due
to minimality and by 4.4, it also follows that $\beta_{k,(i,j)}=0$ for $k>1$
for the $(i,j)$ for which $\beta_{1,(i,j)}\neq 0$.

Next, by 5.7, the second Betti numbers can be read from the first positive
entries occurring after a negative entry along a row of $DH_{X}$. By 5.6,
these occur in positions $(q^{\prime},2),(q^{\prime}+1,2)$, and $(N,1)$, with
values which match the statement of the theorem. Since graded Betti numbers in
a minimal free resolution must increase in degree due to minimality, it also
follows that $\beta_{k,(i,j)}=0$ for $k>2$ for the $(i,j)$ for which
$\beta_{2,(i,j)}\neq 0$.

Third Betti numbers are now only possible in degrees
$(q^{\prime}+2,2),(q^{\prime}+3,2),\dots,(N,2)$. However, minimality of the
original complex disallows both $\beta_{3,(i,j)}$ and $\beta_{4,(i,j)}$ to be
nonzero. Thus, only $\beta_{3,(N,2)}$ can be nonzero and $\beta_{4,(N,2)}=0$,
so by 1.5, $\beta_{3,(N,2)}=3$. Having exhausted the possible degrees for
nonzero Betti numbers, the proof is now complete. ∎

It is worth noting that the virtual of a pair construction does not always
yield a short virtual resolution, even when the
$\mathbf{d}\in\operatorname{reg}(S/I_{X})$ used is as small as possible. In
[booms-peot], Booms-Peot showed that in $\mathbb{P}^{1}\times\mathbb{P}^{1}$,
under certain conditions virtual of a pair yields a virtual resolution of
length $3$. The same issue persists in $\mathbb{P}^{1}\times\mathbb{P}^{2}$,
as shown below.

######  Example 5.8.

For $X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$ with $|X|=31$ in
sufficiently general position, the minimal free resolution has total Betti
numbers

$S\leftarrow S^{34}\leftarrow S^{66}\leftarrow S^{39}\leftarrow
S^{6}\leftarrow 0.$

Performing virtual of a pair at $(2,4)\in\operatorname{reg}(S/I_{X})$ yields
the complex

$\small 0\leftarrow S/I_{X}\leftarrow
S\leftarrow\begin{gathered}S(-3,-3)^{9}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-4)^{14}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-1,-5)^{11}\end{gathered}\leftarrow\begin{gathered}S(-3,-4)^{26}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-2,-5)^{32}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-1,-6)^{8}\end{gathered}\leftarrow\begin{gathered}S(-3,-5)^{24}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-2,-6)^{15}\end{gathered}\leftarrow
S(-3,-6)^{6}\leftarrow 0.\normalsize\qed$

##  Appendix A Short virtual of a pair resolutions for small numbers of
sufficiently general points

Listed below are the virtual resolutions obtained from performing virtual of a
pair at $(|X|-1,0)$ on the minimal free resolutions of $S/I_{X}$ when
$X\subseteq\mathbb{P}^{1}\times\mathbb{P}^{2}$ is a set of sufficiently
general points with $2\leq|X|\leq 11$. The proofs here closely follow that of
5.4 and are thus omitted. The main difference is that for a smaller number of
points, the difference matrix $DH_{X}$ is considerably more crowded.

  * •

$|X|=2$:

$S\leftarrow\begin{gathered}S(0,-2)\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(0,-1)\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-1,-1)^{2}\\\\[-5.0pt]
\oplus\\\\[-5.0pt]
S(-2,0)\end{gathered}\leftarrow\begin{gathered}S(-1,-2)^{4}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-2,-1)^{3}\end{gathered}\leftarrow S(-2,-2)^{3}.$

  * •

$|X|=3$:

$S\leftarrow\begin{gathered}S(0,-2)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-1,-1)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-3,0)\end{gathered}\leftarrow\begin{gathered}S(-1,-2)^{6}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-3,-1)^{3}\end{gathered}\leftarrow S(-3,-2)^{3}.$

  * •

$|X|=4$:

$S\leftarrow\begin{gathered}S(0,-2)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-1,-1)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-2,-1)\\\\[-5.0pt]
\oplus\\\\[-5.0pt]
S(-4,0)\end{gathered}\leftarrow\begin{gathered}S(-1,-2)^{2}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-2,-2)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-4,-1)^{3}\end{gathered}\leftarrow S(-4,-2)^{3}.$

  * •

$|X|=5$:

$S\leftarrow\begin{gathered}S(0,-2)\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-1,-2)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-1,-1)\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-2,-1)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-5,0)\end{gathered}\leftarrow\begin{gathered}S(-2,-2)^{6}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-5,-1)^{3}\end{gathered}\leftarrow S(-5,-2)^{3}.$

  * •

$|X|=6$:

$S\leftarrow\begin{gathered}S(-1,-2)^{6}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-1)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-6,0)\end{gathered}\leftarrow\begin{gathered}S(-2,-2)^{9}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-6,-1)^{3}\end{gathered}\leftarrow S(-6,-2)^{3}.$

  * •

$|X|=7$:

$S\leftarrow\begin{gathered}S(-1,-2)^{5}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-1)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-3,-1)\\\\[-5.0pt]
\oplus\\\\[-5.0pt]
S(-7,0)\end{gathered}\leftarrow\begin{gathered}S(-2,-2)^{5}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-3,-2)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-7,-1)^{3}\end{gathered}\leftarrow S(-7,-2)^{3}.$

  * •

$|X|=8$:

$S\leftarrow\begin{gathered}S(-1,-2)^{4}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-1)\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-3,-1)^{2}\\\\[-5.0pt]
\oplus\\\\[-5.0pt]
S(-8,0)\end{gathered}\leftarrow\begin{gathered}S(-2,-2)\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-3,-2)^{6}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-8,-1)^{3}\end{gathered}\leftarrow S(-8,-2)^{3}.$

  * •

$|X|=9$:

$S\leftarrow\begin{gathered}S(-1,-2)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-2)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-3,-1)^{3}\\\\[-5.0pt]
\oplus\\\\[-5.0pt]
S(-9,0)\end{gathered}\leftarrow\begin{gathered}S(-3,-2)^{9}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-9,-1)^{3}\end{gathered}\leftarrow S(-9,-2)^{3}.$

  * •

$|X|=10$:

$S\leftarrow\begin{gathered}S(-1,-2)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-2)^{4}\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-3,-1)^{2}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-4,-1)\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-10,0)\end{gathered}\leftarrow\begin{gathered}S(-3,-2)^{6}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-4,-2)^{3}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-10,-1)^{3}\end{gathered}\leftarrow S(-10,-2)^{3}.$

  * •

$|X|=11$:

$S\leftarrow\begin{gathered}S(-1,-2)\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-2,-2)^{5}\\\\[-5.0pt] \oplus\\\\[-5.0pt] S(-3,-1)\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-4,-1)^{2}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-11,0)\end{gathered}\leftarrow\begin{gathered}S(-3,-2)^{3}\\\\[-5.0pt]
\oplus\\\\[-5.0pt] S(-4,-2)^{6}\\\\[-5.0pt] \oplus\\\\[-5.0pt]
S(-11,-1)^{3}\end{gathered}\leftarrow S(-11,-2)^{3}.$

## References


# MILP for the Multi-objective VM Reassignment Problem

Takfarinas Saber1, Anthony Ventresque12, Joao Marques-Silva3, James Thorburn4,
Liam Murphy1  1Lero@UCD, School of Computer Science and Informatics,
University College Dublin, Ireland
Email<EMAIL_ADDRESS>{anthony.ventresque,
<EMAIL_ADDRESS>2IBM Research, Damastown Industrial Estate, Dublin,
Ireland  3Instituto Superior Técnico, Lisboa, Portugal, Email<EMAIL_ADDRESS>4IBM Software Group, Toronto, Canada, Email<EMAIL_ADDRESS>
###### Abstract

Machine Reassignment is a challenging problem for constraint programming (CP)
and mixed integer linear programming (MILP) approaches, especially given the
size of data centres. The multi-objective version of the Machine Reassignment
Problem is even more challenging and it seems unlikely for CP or MILP to
obtain good results in this context. As a result, the first approaches to
address this problem have been based on other optimisation methods, including
metaheuristics. In this paper we study under which conditions a mixed integer
optimisation solver, such as _IBM ILOG CPLEX_ , can be used for the Multi-
objective Machine Reassignment Problem. We show that it is useful only for
small or medium scale data centres and with some relaxations, such as an
optimality tolerance gap and a limited number of directions explored in the
search space. Building on this study, we also investigate a hybrid approach,
feeding a metaheuristic with the results of CPLEX, and we show that the gains
are important in terms of quality of the set of Pareto solutions (+126.9%
against the metaheuristic alone and +17.8% against CPLEX alone) and number of
solutions (8.9 times more than CPLEX), while the processing time increases
only by 6% in comparison to CPLEX for execution times larger than 100 seconds.

###### Index Terms:

Multi-objective Optimisation; VM/Machine Reassignment; Mixed Integer Linear
Programming; Hybrid-Metaheuristics.

##  I Introduction

#### Background and Research Challenge

Optimisation of data centres, through reassignment of virtual machines (VMs),
is largely seen as one of the biggest challenges in data centre management
[1]: not only servers are underutilised [2] and the potential savings are
important, but the problem has a lot of constraints and is difficult to solve
[3]. Constraint programming (CP) and mixed111Note that while the constraints
can be expressed by binary variables, the objectives (especially the
reliability cost, see Section II) require real variables. integer programming
(MILP) are known to be inefficient for such large scale problems with a
limited execution time [4, 5], and usually researchers focus on other
optimisation techniques (e.g., local search [6, 7] or greedy algorithms [8])
or mix CP or MILP with some other optimisation solutions (e.g., local search
[5]).

In this paper, we address a slightly different and more relevant problem for
the industry: _the Multi-objective VM Reassignment Problem_. ‘Optimising a
data centre’ seems to suggest that there is something like a _best_
reassignment of VMs, but in an enterprise there is no best placement: it is
all about which objectives are favoured (by whom and when). It is not hard to
imagine that different capital allocators (CA, the managers of data centres)
may have different perspectives on the best way of making the system better.
For instance some CAs may consider that energy consumption is the most
important element, while for others it can be the cost of licensing; or some
CAs see the reliability as the key element (for instance if they run critical
applications), while other CAs have a strict policy regarding response time
and then collocation of VMs. These preferences, or policies, may evolve or be
in competition: for instance if CAs have two policies for their data centre
(e.g., “electricity has to decrease by x%” and “management cost has to be
limited to y%”) and some reassignment solutions can serve both, which one to
favour? In this context, CP and MILP do not seem promising approaches, as the
search space is large and the constraints hard and complex. As far as we know,
the only related work tackles the problem using some other optimisation
techniques. One of the challenges here is that execution time is limited: even
if the reassignment is done on a monthly or a quarterly basis, as it often
happens, the decision process is complex and CAs cannot wait more than a few
hours or days: they verify and modify the solutions to suit their needs before
making any decision. In this paper, as it is commonly accepted by
practitioners and in the literature [5, 9] we use a time limit for the Multi-
objective Reassignment Problem.

However, given that CPLEX’s solutions are generally of better quality than the
ones of other optimisation techniques, and that there are several relaxation
mechanisms in CPLEX and the multi-objective problem itself, we study in this
paper whether a MILP solver, such as CPLEX, can be used for the Multi-
objective Machine Reassignment Problem.

#### Example

Figure 1:  Possible reassignments in 2-dimensions (in red, the good ones) and
an organisation’s policies (in grey).

As a motivating example, consider Figure 1 that shows a reassignment problem
with two objectives: the electricity consumption and the reliability (the
lower the better for both). Points a to f are all the possible reassignments,
satisfying all the constraints of the data centre. The good reassignments,
i.e., those that are better than any other in a particular combination of
objectives, are in red. Solution e, for instance, is not a good reassignment
as it is worse than b on both objectives - same applies to f wrt. c. The
decision makers may define some policies, i.e., some rules that describe the
desired optimisations: here a maximal value for the electricity consumption
and the reliability, defining the area of good assignments that the decision
makers can select (grey area on Figure 1). There are still two possible
reassignments, b and c. The decision makers can then evaluate them locally and
make a relative decision among them, such as “c gives me a better electricity
cost but it is not a huge gain, while b’s reliability is higher – so we favour
b”. Any technique addressing this problem needs to explore the research space
in all directions in order to find varied and good solutions – which is
expensive given the size of the problem.

#### Contributions

In this paper we make the following contributions: (i) we give a thorough
study of how suited is a MILP solver (CPLEX) for the Multi-objective VM
Reassignment Problem (the problem definition is given in Section II). We show
that it is useful only for rather small or medium scale data centres and with
some relaxations: a certain tolerance gap and a limited number of directions
explored in the search space (Section IV); (ii) we propose an algorithm based
on the combination of a MILP solver (CPLEX) and a hybrid-metaheuristic to
improve the performance of the solver while keeping the execution time
acceptable. This is detailed in Section V.

Hybridization is not a novel idea as such (e.g., see [10]), however combining
a solver (which aim is to find ‘proper’ solutions and not only to relax the
problem) and a meta-heuristic to benefit from both worlds in a multi-objective
context is novel to our best knowledge. CP and MILP provide better solutions
(when they get any, as they are expensive/slow) so our goal here is to help
CPLEX as much as we can (i.e., increasing the optimality gap and varying the
number of vectors) to get some solutions to feed in the meta-heuristic to
cover the search space. Note that in [5] Mehta et al. use CP on a relaxed
problem, not the original VM placement one, which leads us to think that CP is
inefficient for our problem – and anyway we also tried ILOG CP Optimizer and
noticed extremely poor performances.

##  II Problem Definition

In this section, we give a Multi-objective extension of the VM Reassignment
Problem originally proposed by Mehta et al. in [5]. We first describe briefly
the different elements of data centres, followed by the constraints of the
problem, and we finish with the different objectives that we believe are the
most relevant (note that this approach is agnostic to objectives and would
work with any other linear objective function).

###  II-A Problem Description and Notation

A data centre is composed of a set $\mathcal{M}$ of physical machines (PMs or
servers). Each machine $m_{i}\in\mathcal{M}$ has a finite amount $Q_{m_{i},r}$
of resource $r\in\mathcal{R}$ (e.g., CPU, RAM, storage). Machines
$m_{i}\in\mathcal{M}$ belonging to a same rack are linked with high network
connections, and thus considered as being in the same neighbourhood
$N(m_{i})\in\mathcal{N}$. Resources are of two different types: (i) transient
resources ($r\in\mathcal{TR}\subseteq\mathcal{R}$, e.g., RAM or storage) that
are consumed at the original host and also at the destination one during a
migration process, or (ii) non-transient ($r\in\overline{\mathcal{TR}}$). The
data centre is in charge of a set of VMs $v\in\mathcal{V}$ with resource
requirements $d_{v,r}$ for every $r\in\mathcal{R}$. $M_{0}(v)$ and $M(v)$
respectively indicate the initial and the final host of the VM $v$ during the
reassignment. VMs composing a same multi-tier application are usually gathered
by services $\mathcal{S}=\\{s_{1},\dots,s_{p}\\}$, with
$s_{p}=\\{v_{p}^{1},\dots,v_{p}^{q}\\}$.

###  II-B Constraints

We present here the linear constraints of our problem. We follow the problem’s
linear constraints provided in [5].

####  II-B1 Reassignment Constraints

Consider a binary variable $x_{v,m}$ for every VM $v\in\mathcal{V}$ and for
each machine $m\in\mathcal{M}$, which is set to 1 if $M(v)=m$ and 0 otherwise.
Constraints (1) ensure that every VM is reassigned to one and only one
machine:

$\forall v\in\mathcal{V},\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \sum_{m\in\mathcal{M}}x_{v,m}=1$ (1)

####  II-B2 Capacity Constraints

There are two ways of computing resource utilisation $U_{m,r}$ of a machine
$m\in\mathcal{M}$ and a resource $r\in\mathcal{R}$: (2) for non-transient
resources and (3) for transient resources.

$\forall r\in\overline{\mathcal{TR}},\leavevmode\nobreak\ \forall
m\in\mathcal{M},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
U_{m,r}\leavevmode\nobreak\ \leavevmode\nobreak\ =\leavevmode\nobreak\
\leavevmode\nobreak\ \sum_{v\in\mathcal{V}}d_{v,r}.x_{v,m}$ (2)

$\forall r\in\mathcal{TR},\forall
m\in\mathcal{M},U_{m,r}=\sum_{v\in\mathcal{V}|M_{0}(v)=m}d_{v,r}.x_{v,m}+\sum_{v\in\mathcal{V}|M_{0}(v)\neq
m}d_{v,r}.x_{v,m}$ (3)

The total resource utilisation of a machine $m\in\mathcal{M}$ should not
exceed its capacity $Q_{m,r}$ for every $r\in\mathcal{R}$:

$\forall r\in\mathcal{R},\leavevmode\nobreak\ \forall
m\in\mathcal{M},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
U_{m,r}\leq Q_{m,r}$ (4)

####  II-B3 Conflict Constraints

VMs which belong to a same service have to be reassigned to different machines
(e.g., for replication purposes).

$\forall s\in\mathcal{S},\leavevmode\nobreak\ \forall
m\in\mathcal{M},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{v\in s\leavevmode\nobreak\ |\leavevmode\nobreak\ M(v)=m}x_{v,m}\leq 1$
(5)

####  II-B4 Dependency Constraints

Services sometimes depend on each other. VMs of these services need to be
close to each other in order to achieve high performance (e.g., in the case of
multi-tier applications). Let $\mathcal{D}$ be the set of service dependencies
such that $\mathcal{D}=\\{(s_{i},s_{j})|s_{i},s_{j}\in\mathcal{S}$ and $s_{i}$
depends on $s_{j}\\}$, then:

$\forall s_{i},s_{j}\in\mathcal{S},(s_{i},s_{j})\in\mathcal{D}\implies\forall
v_{a}\in s_{i},\exists v_{b}\in s_{j}|N(M(v_{a}))=N(M(v_{b}))$ (6)

To give a linear definition of constraints (6), we introduce the binary
variables $y_{s,n}$ for every service $s\in\mathcal{S}$ and for each
neighbourhood $n\in\mathcal{N}$. Constraints (7) and (8) ensure that each
variable $y_{s,n}$ is set to 1 if at least one VM from the service $s$ is
hosted by a machine in the neighbourhood $n\in\mathcal{N}$ and to 0 otherwise:

$\forall s\in\mathcal{S},\leavevmode\nobreak\ \forall
n\in\mathcal{N}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{v\in s}\sum_{m\in n}x_{v,m}\leq|\mathcal{N}|.|\mathcal{S}|.y_{s,n}$ (7)

$\forall s\in\mathcal{S},\leavevmode\nobreak\ \forall
n\in\mathcal{N}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{v\in s}\sum_{m\in n}x_{v,m}\geq y_{s,n}$ (8)

If a service $s_{i}$ depends on $s_{j}$, constraints (9) guarantee that there
is not any VM from $s_{i}$ reassigned to a machine in a neighbourhood
$n\in\mathcal{N}$ without having at least one VM from $s_{j}$ reassigned to
that neighbourhood:

$\forall(s_{i},s_{j})\in\mathcal{D},\leavevmode\nobreak\ \forall
n\in\mathcal{N}y_{s_{i},n}\leq y_{s_{j},n}$ (9)

####  II-B5 Spread Constraints

Data centres are often decentralised and we assume here that they are composed
of different sites $\mathcal{L}$, each machine belonging to a location
$l\in\mathcal{L}$. For reliability and security reasons, some services need to
be spread over at least _spreadNumber_ locations. Let us introduce a binary
variable $z_{s,l}$ for every service $s\in\mathcal{S}$ and for each location
$l\in\mathcal{L}$. Constraints (10) and (11) ensure that $z_{s,l}$ gets the
value 1 if the service $s$ has at least one VM running in a machine at the
location $l$:

$\forall s\in\mathcal{S},\leavevmode\nobreak\ \forall
l\in\mathcal{L}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{v\in s}\sum_{m\in l}x_{v,m}\leq|\mathcal{N}|.|\mathcal{S}|.z_{s,l}$ (10)

$\forall s\in\mathcal{S},\leavevmode\nobreak\ \forall
l\in\mathcal{L}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{v\in s}\sum_{m\in l}x_{v,m}\geq z_{s,l}$ (11)

Constraints (12) force every service $s$ to run on at least
_$spreadNumber_{s}$_ number of locations:

$\forall s\in\mathcal{S},\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \sum_{l\in L}z_{s,l}\geq spreadNumber_{s}$ (12)

######  Definition 1 (Machine Reassignment)

An assignment $A$ of VMs to machines is a mapping:
$A:\mathcal{P}\mapsto\mathcal{M}$, such that $A(v,\mathcal{M})\to m$, which
satisfies the constraints (1–5 and 7–12).
A reassignment is a function: $ReA:A\mapsto A$ which returns a new assignment
for a given initial assignment of VMs to machines.

###  II-C Objectives

We focus here on three objectives: electricity cost, VM migration cost and
reliability cost, as they are recognised in the literature [11, 12, 13] and
make sense in practice. The multi-objective variant of the Machine
Reassignment (see Definition 1) consists of minimising the cost functions
defined by the objectives, the ones we present here or any others that would
be relevant.

####  II-C1 Reliability Cost

For each machine $m\in\mathcal{M}$ and each resource $r\in\mathcal{R}$, we
define the safety capacity $SC_{m,r}$ as the amount of resource that it is
‘safe’ to allocate without overloading $m$ – this is similar to the resource
buffer that placement algorithms often assume [14]. The risk of failure
$R_{m,r}$ is then the difference between the actual utilisation of resource
$r$ and the safety capacity, and the reliability cost $R_{cost}$ represents
the ‘non reliability’ over the full data centre.

$\forall m\in\mathcal{M},\leavevmode\nobreak\ \forall
r\in\mathcal{R},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
R_{m,r}\geq U_{m,r}-SC_{m,r}\geq 0$ (13)

$R_{cost}=\sum_{r\in R}\sum_{m\in M}R_{m,r}$ (14)

####  II-C2 Electricity Cost

For each machine $m\in\mathcal{M}$, we introduce a binary variable $o_{m}$ to
be set by constraints (15) to 1 if the machine $m$ is switched on (i.e., hosts
at least one VM) and 0 otherwise.

$\forall m\in\mathcal{M},\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ o_{m}\leq\sum_{v\in V}x_{v,m}\leq|\mathcal{V}|.o_{m}$
(15)

The electricity cost $E_{cost}$ is composed of the electricity consumption of
each machine $m\in\mathcal{M}$ multiplied by its price $\gamma_{m}$. The
electricity consumption of a machine $m$ is often modelled as a linear
function of its CPU utilisation [15, 16], with $\alpha_{m}$ being its
electricity consumption at idle and $\beta_{m}$ its consumption per unit of
CPU usage.

$E_{cost}=\sum_{m\in M}\gamma_{m}\left(\alpha_{m}.o_{m}\leavevmode\nobreak\
\leavevmode\nobreak\ +\leavevmode\nobreak\ \leavevmode\nobreak\
\beta_{m}.U_{m,CPU}\right)$ (16)

####  II-C3 Migration Cost

For each VM $v\in\mathcal{VM}$, we introduce a binary variable $mig_{v}$ to be
set by constraints (17) to 1 if v is reassigned and 0 otherwise.

$\forall v\in\mathcal{V},\sum_{m\in M\backslash
M_{0}(v)}x_{v,m}\leavevmode\nobreak\ =\leavevmode\nobreak\ mig_{v}$ (17)

The migration cost $M_{cost}$ concerns all migrating VMs. For each migrating
VM $v\in\mathcal{V}$, the migration cost is the time it takes to: (i) prepare
the VM $\mu_{1}(v)$, (ii) to transfer its image from its initial placement to
its new host $m$ $\mu_{2}(v,M_{0}(v),m)$ and (iii) to deploy it in the new
host $\mu_{2}(v)$:

$M_{cost}=\sum_{v\in
V}\left(\left[\mu_{1}(v)+\mu_{3}(v)\right].mig_{v}\leavevmode\nobreak\
\leavevmode\nobreak\ +\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{m\in\mathcal{M}}\mu_{2}(v,M_{0}(v),m).x_{v,m}\right)$ (18)

##  III Experimental Setup

In the current section we present our evaluation setup, i.e., the description
of several instances of the problem (data centres to optimise) inspired from a
well-known data set [9] and the metrics used to judge the proposed systems.
All the algorithms described below have been developed in C++. Experiments are
done on a computing cluster with 24 cores 2.0GHz Intel Ivy Bridge CPU and
128GB of RAM.

###  III-A Data set

Google and the ROADEF society (i.e., the French OR society) released a few
years ago a data set, now widely used in the OR community, for the evaluation
of VM reassignment solutions [9]. This data set represents various data
centres, of different sizes and characteristics (e.g., various number of
resources), with a large number of constraints. This data set does not provide
a multi-objective formulation though and we had to adapt the instances (note
that the participants of the challenge optimised only one single weighted sum
of the costs proposed – hence there is no possible comparison between our work
and others using ROADEF). Our instances aim to model realistic scenarios as we
observe them in large companies.For our evaluation, we take the 14 first
instances, leaving out only the largest ones (see Table I). Two of the
objectives we define are present in ROADEF as cost functions:
safety/reliability and migration, and we add electricity. We randomly generate
electricity consumption constants ($\alpha$, $\beta$) for every machine
$m\in\mathcal{M}$ and also the electricity cost $\gamma$ for every location
$l\in\mathcal{L}$. The data set also comes with a time limit representing the
maximum time allowed for the resolution of the instance (300 seconds). We
changed the time limit to: 30s for $a\\_1\\_1$, 1h for $a\\_1\\_\\{2-5\\}$, 2h
for $a\\_2\\_\\{1-3\\}$, and 10h for the other instances, which is considered
realistic by large companies in the context of optimisation performed in a
regular basis, e.g., monthly or quarterly.

Instance | # Resources | # Machines | # Services | # VMs
---|---|---|---|---
a_1_1 | 2 | 4 | 79 | 100
a_1_2 | 4 | 100 | 980 | 1,000
a_1_3 | 3 | 100 | 216 | 1,000
a_1_4 | 3 | 50 | 142 | 1,000
a_1_5 | 4 | 12 | 981 | 1,000
a_2_1 | 3 | 100 | 1,000 | 1,000
a_2_2 | 12 | 100 | 170 | 1,000
a_2_3 | 12 | 100 | 129 | 1,000
a_2_4 | 12 | 50 | 180 | 1,000
a_2_5 | 12 | 50 | 153 | 1,000
b_1 | 12 | 100 | 2,512 | 5,000
b_2 | 12 | 100 | 2,462 | 5,000
b_3 | 6 | 100 | 15,025 | 20,000
b_4 | 6 | 500 | 1,732 | 20,000
Table I: Characteristics of the different instances used in our evaluation.

###  III-B Metrics

The comparison of algorithms optimising a multi-objective problem is complex
as their results can be evaluated from different perspectives, such as: the
number of solutions on the Pareto front, the variety of solutions [17], or the
spread of these solutions. The comparison is even more complex in our case as
the problem is large, the Pareto front is not known in most cases and
objectives cannot be considered separately. In this paper, we only consider
unary metrics, i.e., returning a single value based on solutions found by
every algorithm, making a comparison of several algorithms easier.

####  III-B1 Number of solutions

Figure 2: Metrics: number of Pareto solutions (red dots) and hypervolume (grey
area).

We use the number of _non-dominated (efficient) solutions_ in our experiments
as our first metric. We refer to it as the quantity of found solutions. This
metric is highly important for data centre capital allocators as it gives them
more choices. It also provides them with backup solutions if the preferred one
appears difficult or technically impossible to implement.

####  III-B2 Hypervolume

The _hypervolume_ [18] (a.k.a., $\mathcal{S}$ metric) refers to the quality of
a set of solutions. The hypervolume is used [19] in the multi-objective
optimisation community for comparing different sets of non-dominated
solutions. For every set of solutions, this metric measures the space between
the efficient solutions and a reference point far from them. The reference
point is defined as a point in the space having the worst objective values and
must be identical for all the algorithms, but may be different for every
instance. Figure 2 shows a two-dimensional reassignment, with the non-
dominated solutions in red and the other (not interesting) solutions in light
blue. The initial placement is one of the solutions, generally not on the
Pareto front. The hypervolume is the grey area in this 2D space.

##  IV CPLEX for the VM Reassignment Problem

The goal of this section is to study both performance and scalability of a
MILP solver (i.e., CPLEX) on the Multi-objective VM Reassignment Problem.
First, we explore how CPLEX performs on the (Mono-objective) VM Reassignment
Problem, i.e., the original problem from ROADEF. We show how difficult the
problem is for CPLEX, even in this simpler version. Then we explore the
performance of CPLEX for the Multi-objective VM Reassignment and show that it
can be tackled under some restrictions, such as, a limited number of
directions (_vectors_) explored in the search space and an optimality
tolerance gap.

###  IV-A CPLEX for the Mono-objective VM Reassignment Problem

Portal et al. [20] show that the VM Reassignment Problem is too difficult for
a MILP solver like CPLEX when applied on the ROADEF instances. CPLEX could
only solve 3 instances out of the 14 within the time limit (300s) fixed during
the challenge. However CPLEX allows defining an _optimality gap tolerance_ , a
trigger that stops CPLEX when the current feasible solution falls within a
certain percent of CPLEX best estimation of the lower bound (a value smaller
or equal to the actual optimal value). For instance, a 5% gap means that any
solution that is 5% away from the estimated lower bound is accepted and stops
CPLEX. In addition, we have here a larger time budget to solve the instances.

| 50% | 20% | 10% | 5% | 1% | 0.5% | 0.1% | 0.05% | 0.01% | Limit (s)
---|---|---|---|---|---|---|---|---|---|---
a_1_1 | 0.08 | 0.08 | 0.08 | 0.08 | 0.08 | 0.12 | 0.14 | 0.23 | 0.25 | 30
a_1_2 | 186 | 183 | 185 | 185 | 1,490 | – | – | – | – | 3,600
a_1_3 | 27 | 27 | 27 | 37 | 625 | 1,691 | – | – | – | 3,600
a_1_4 | 50 | 50 | 51 | 51 | 98 | 1,682 | – | – | – | 3,600
a_1_5 | 9 | 9 | 9 | 9 | 9 | 9 | 10 | 19 | 26 | 3,600
a_2_1 | 54 | 55 | 159 | 3,670 | – | – | – | – | – | 7,200
a_2_2 | 2,511 | 2,580 | 2,580 | 2,736 | – | – | – | – | – | 7,200
a_2_3 | 71 | 71 | 71 | 71 | 5,816 | – | – | – | – | 7,200
a_2_4 | 20,445 | 20,502 | 20,655 | – | – | – | – | – | – | 36,000
a_2_5 | 21,877 | 22,492 | 22,513 | – | – | – | – | – | – | 36,000
b_1 | 3,482 | 6,913 | 6,913 | 7,094 | – | – | – | – | – | 36,000
b_{2,3,4} | – | – | – | – | – | – | – | – | – | 36,000

Table II: Execution time (s) of CPLEX for the resolution of the identity
vector (all objectives have weights equal 1) depending on the optimality
tolerance gap. The symbol ‘–’ means that no solution was found in the time
limit.

Table II shows the execution time (in seconds) of CPLEX for the resolution of
one single vector (the identity vector, i.e., with weights equal 1 for the
three objectives). As a reminder, we also add the time limit (last column)
that we set for each instance. First, we notice that CPLEX only solves
instances $a\\_1\\_1$ and $a\\_1\\_5$ in the time limit (note that 0.01% is
the default tolerance gap for CPLEX). This supports the general claim that a
MILP solver is inefficient for our problem, even in this simple case with only
one vector. We then notice that CPLEX gets a solution with a gap of 0.5% for
all small instances, 10% for all medium instances (1% or 5% for some), and
solved only one of the hard instances ($b\\_1$, with a 5% gap), even with a
50% gap. We also observe that often CPLEX finds a first good solution (e.g.,
$a\\_1\\_2$, $a\\_1\\_3$ and $a\\_1\\_4$ have a solution for 5% quickly, as
evidenced by the same time for 50%, 20%, 10% and 5%) but it is then difficult
for CPLEX to improve it. As a conclusion, CPLEX does not seem able to scale to
large instances but with a proper gap CPLEX finds good solutions.

###  IV-B CPLEX for the Multi-objective VM Reassignment Problem

Once we know that CPLEX finds it difficult to solve one weight vector in the
search space, we would like to explore what needs to be relaxed in order to
help CPLEX optimise more vectors and hence address a proper multi-objective
problem. In the current section we look at three elements: (i) given that
optimising one weight vector is already difficult to CPLEX and the more
vectors we optimise the more we explore the search space, what is the most
reasonable number of weight vectors to be optimised? (ii) getting a tiny
optimality gap increases exponentially the execution time, therefore what is
the best value for this parameter? (iii) what is the best way to use CPLEX?
Would it be better to collect all intermediate (feasible) solutions found by
CPLEX instead of only keeping the best ones for each weight vector?

|
---|---
a_1_1 | a_1_2
|
a_1_3 | a_1_4
|
a_1_5 | a_2_1
|
a_2_2 | a_2_3
|
a_2_4 | a_2_5
|
b_1 | Optimality Gap
Figure 3: Execution time (s) of CPLEX on ROADEF instances, with maximally
spread objective weight vectors and using different optimality gaps.

Figures 3 show the execution time CPLEX needs to reach different optimality
gaps given several maximally spread weight vectors. These vectors are built on
the assumption that to explore a maximum of the space the solver needs to
target widely spread directions. In our 3-dimensional space (3 objectives), we
successively use these vectors: (1,1,1), (0.6, 0.3, 0.1), (0.3, 0.1, 0.6),
(0.1, 0.6, 0.3), (0.45, 0.45, 0.1), (0.45, 0.1, 0.45) and (0.1, 0.45, 0.45).
We notice that running different vectors increases the final execution time –
as it can be expected. It also confirms what we have seen earlier in Table II
that for large optimality gaps, there is no large difference in terms of
execution time (CPLEX quickly finds good solutions), however the more we
decrease the gap, the more important is the increase in execution time. We
also see that due to the time budget limitation, we cannot run all the
possible optimisations with the different vectors for some optimality gaps
(e.g., for $a\\_1\\_2$ we could only use 2 vectors out of the 7 possible ones
with an optimality gap of 1%). Therefore, a decision has to be made on which
values should be set for both variables: the optimality gap and the number of
vectors.

According to Figures 3, two patterns emerge: (i) on small instances: asking
CPLEX for an optimality gap smaller than 5% increases its execution time
drastically, and (ii) on medium instances: this gap drops to 5 – 10%.
Therefore, to keep our optimisation in a reasonable execution time, the
larger/more complex is the instance the larger the optimality gap we consider.
Unlike what we might think, CPLEX execution time is very heterogeneous and
varies a lot from a vector to another (execution time curves are not linear).
Thus, knowing CPLEX execution time on the first vector does not give any
indication/prediction on the execution time for other vectors. Because of the
lack of knowledge of the execution time, we have to restrict the number of
vectors as much as possible. We are even more constrained regarding some
instances such as $a\\_2\\_4$ and $a\\_2\\_5$ where we could only run CPLEX on
one vector.

| Best Solutions | All Feasible Solutions
---|---|---
a_1_1 |  |
a_1_2 |  |
a_1_3 |  |
Figure 4: Hypervolume obtained on instances $a\\_1\\_1$, $a\\_1\\_2$ and
$a\\_1\\_3$ using CPLEX for different numbers of weight vectors with different
optimality gaps by either only considering the best solution found or by
collecting all the feasible solutions during the optimisation.

Another element of the resolution process that might be interesting to look at
is the intermediate (feasible) solutions generated by CPLEX. The way CPLEX
works is iterative: it first finds a feasible solution that is either
discarded/improved if it is not optimal or kept if it is optimal. In our
multi-objective context, those intermediate solutions, while not optimal in a
particular combination of objectives (remember that CPLEX solves vectors of
weights for the objectives), may sometimes carry some interesting
reassignments of the VMs, for instance wrt. some single objective – and hence
improve the hypervolume. Figures 4 show the hypervolume obtained on the
instances $a\\_1\\_1$, $a\\_1\\_2$ and $a\\_1\\_3$ by CPLEX when increasing
the number of vectors for different optimality gaps going from 50% to 0.01%.
The three figures at the left side show the hypervolume obtained when only the
best solutions are kept in the solution set while the three figures at the
right side give the hypervolume for the same experiments with all solutions in
the solution set. We notice from the graphs at the left that optimising the
objectives using a vector of weights with a small gap does not imply getting a
better hypervolume for the multiple objectives (e.g., on the instance
$a\\_1\\_3$, two vectors and a gap of 5% get a better hypervolume than using a
gap of 1%). This is mainly due to the fact that optimising a compromise of
objectives using their linear combination may lead to optimising one objective
at the expense of the others. This is also caused by the fact that the
objectives are in different units and of different scales (e.g., the
electricity cost has a larger scale than the migration cost). Collecting all
the feasible solutions during the optimisation of every vector may then be a
good improvement: see the three graphs at the right of Figure 4. We notice
that using a small optimality tolerance gap gives us better results than using
a larger one. We also notice that we get an improvement in terms of
hypervolume. This is an interesting behaviour especially since we did not add
any noticeable extra computation time (CPLEX already collects the intermediary
solutions, and filtering/removing the dominated solutions requires a
negligible execution time). In the rest of our evaluations we collect all
intermediate (good, i.e., non-dominated) solutions.

|
---|---
a_1_1 | a_1_2
|
a_1_3 | a_1_4
|
a_1_5 | a_2_1
|
a_2_2 | a_2_3
|
a_2_4 | a_2_5
|
b_1 | Optimality Gap
Figure 5: Hypervolume obtained with CPLEX (all feasible solutions) on ROADEF
instances, using maximally spread weight vectors and different optimality
gaps.

Figure 5 shows the hypervolumes obtained with different number of vectors and
different tolerance gaps, and this can be read together with Figure 3 to
figure what composition of number of vectors and tolerance gap gives the best
time-hypervolume trade-off. We notice that globally the hypervolume increases
with every new vector. This improvement is more noticeable during the 5 first
vectors. It seems to stagnate between the $5^{th}$ and $7^{th}$ (whenever
CPLEX reaches them in the time constraint), especially when the optimality gap
is tiny. This leads us to think that running several CPLEX optimisations with
a large number of vectors (larger than 5) would not be as beneficial as we
might think. It would increase the execution time without improving the
hypervolume. This idea can obviously be withdrawn if the managers of the data
centre are ready to spend more time to achieve better hypervolume results.

We see from Figures 3 and 5 that using an optimality gap of 5% and 3 weight
vectors for small instances and an optimality gap of 10% and 1 weight vector
for medium instances allow us to achieve a good hypervolume while keeping the
execution time reasonable for all the instances.

##  V Combining a Solver and a Metaheuristic

We saw earlier that CPLEX gets good results on small and medium instances,
but, it becomes really hard to improve those results without increasing either
the number of vectors or the optimality gap, and thus dramatically impacting
the execution time. In this section, we want to see whether combining a solver
with a metaheuristic allows us to get better results in a reasonable time. A
comparison of different metaheuristics has already been performed [21] and a
scalable hybrid-metaheuristic (GeNePi) proposed to optimise the Multi-
objective VM Reassignment Problem. GeNePi outperforms state-of-the-art
algorithms on both quantity and quality of solutions. GeNePi successively
applies three metaheuristics: (i) a greedy algorithm (i.e., GRASP [8]) to
quickly find good solutions representing the research space, (ii) a genetic
algorithm (i.e., NSGA-II [22]) by combining the previous solutions to get
better solutions optimising different objective trade-offs, and (iii) a local
search (i.e., PLS [23]) to refine the Pareto front and find more non-dominated
solutions.

We take the previous implementation of CPLEX and we give its results to
GeNePi, non-dominated solutions found using CPLEX being the initial
population. It might happen that CPLEX does not find enough solutions to fill
out an entire population (in our case, a population of size 20). In this case
the original greedy algorithm in GeNePi is applied to fill this gap and
compensate this lack of solutions. In our implementation, GeNePi applies 10
iterations of its second phase (i.e., NSGA-II) in order to evolve the initial
population into a fitter one, by getting better and more scattered solutions
(spread over the research space). At the end, GeNePi refines the Pareto front
by applying a unique iteration of Pareto Local Search (PLS) on the 10 most
isolated solutions. Although this step does not bring a large improvement in
terms of hypervolume, it is important as it provides decision-makers with more
implementation choices. Beside these choices, we use the same parameters as in
the GeNePi paper [21].

|  | GeNePi | CPLEX | CPLEX + GeNePi
---|---|---|---|---
Instance | Initial Hyp | Hyp | #Sol | Time | Hyp | #Sol | Time | Hyp | #Sol | Time
a_1_1 | 6.16E+15 | 9.71E+15 | 225 | 1.58 | 8.82E+15 | 3 | 0.18 | 9.74E+15 | 30 | 0.38
a_1_2 | 4.75E+18 | 5.69E+18 | 160 | 518 | 5.93E+18 | 8 | 303 | 6.17E+18 | 42 | 319
a_1_3 | 6.57E+18 | 7.22E+18 | 132 | 441 | 9.01E+18 | 5 | 151 | 9.06E+18 | 21 | 167
a_1_4 | 8.10E+18 | 9.19E+18 | 136 | 309 | 1.03E+19 | 6 | 138 | 1.09E+19 | 35 | 158
a_1_5 | 2.42E+18 | 3.15E+18 | 283 | 332 | 3.94E+18 | 4 | 21 | 4.04E+18 | 54 | 34
a_2_1 | 4.57E+19 | 5.89E+19 | 231 | 284 | 7.95E+19 | 5 | 159 | 8.17E+19 | 39 | 166
a_2_2 | 3.33E+20 | 4.36E+20 | 197 | 600 | 4.76E+20 | 7 | 2,580 | 5.01E+20 | 42 | 2,694
a_2_3 | 2.55E+20 | 3.69E+20 | 202 | 695 | 4.93E+20 | 2 | 71 | 5.13E+20 | 32 | 154
a_2_4 | 3.21E+20 | 6.19E+20 | 253 | 342 | 5.84E+20 | 3 | 20,655 | 6.68E+20 | 43 | 21,173
a_2_5 | 4.96E+20 | 5.81E+20 | 220 | 347 | 5.63E+20 | 2 | 22,513 | 5.86E+20 | 23 | 22,548
b_1 | 8.20E+21 | 8.74E+21 | 244 | 14,991 | 1.07E+22 | 2 | 8,913 | 1.09E+22 | 29 | 9,452
Table III: Summary of results obtained with GeNePi, CPLEX and CPLEX combined
with GeNePi using a gap of 5% and 3 vectors for small instances, and a gap of
10% and a unique vector for medium and large instances.

Table III shows the results obtained on the modified ROADEF instances from
$a\\_1\\_1$ to $b\\_1$, in terms of hypervolume, number of non-dominated
solutions and execution time. Results are obtained using 10 runs of GeNePi
alone (the average is taken), CPLEX alone, and our new matheuristic (i.e.,
CPLEX combined with GeNePi) while respectively defining the optimality gap and
the number of weight vectors to 5% and 3 for small instances (i.e.,
$a\\_1\\_x$), and 10% and 1 for medium and large ones (i.e., $a\\_2\\_x$ and
$b\\_1$). It also shows the execution time of each algorithm for every
instance. Table III confirms that GeNePi succeeds in improving the hypervolume
and getting a large number of non-dominated solutions while keeping the
execution time relatively low. We also notice that CPLEX outperforms GeNePi in
terms of hypervolume in 8 instances out of 11 with an average improvement of
102%. However, GeNePi gets on average 63 times more non-dominated solutions
(note that the number of solutions while interesting for the decision makers,
is not as important as the hypervolume, and anyway too many solutions makes
them difficult to explore). We see that CPLEX is slightly better in terms of
execution time (given its parallel implementation and the fact that it runs on
more powerful memory intensive machines). However we see that CPLEX struggles
to scale to large instances (GeNePi gets a better hypervolume on $a\\_2\\_4$
and $a\\_2\\_5$ with an execution time of respectively 342s and 347s vs.
21,173s and 22,548s for CPLEX). Compared to CPLEX, we clearly see that adding
GeNePi to CPLEX helps to improve the hypervolume (an increase of 17.84% on
average), and also to get more non-dominated solutions (8.9 times more
solutions on average), while keeping the execution time low (an average
execution time increase of 31.10%, but of only 6% for execution times larger
than 100s). We also see that CPLEX + GeNePi outperforms the hypervolume
obtained by GeNePi alone (with an average increase of 126.96%) and that unlike
CPLEX alone, CPLEX + GeNePi gets better hypervolumes than GeNePi in all
instances. CPLEX + GeNePi also gets a fairly reasonable number of non-
dominated solutions. However, GeNePi still gets a larger number of solutions
(5 times more on average).

To summarise, we can say that CPLEX is good at getting few solutions with a
good quality but does not scale well to large instances, unlike GeNePi and
other (hybrid-) metaheuristics. Also, knowing that CPLEX execution time on one
vector is low does not provide much information on the time to run on several
other vectors. Combining CPLEX with GeNePi seems to be a good solution to
improve CPLEX’s results in both hypervolume and number of non-dominated
solutions with a relatively low increase in the execution time. Another
advantage of our approach is that it can be adapted to the size of the
problem: when the size increases, we have the option to either continue
relaxing some of the parameters used for CPLEX (i.e., less vectors or a larger
optimality gap) or to replace CPLEX with another ‘bootstrapping’ technique
(e.g., greedy algorithm) to feed in the meta-heuristic.

##  VI Conclusion

This paper assesses whether a MILP solver, such as CPLEX, can be applied to
the Multi-objective VM Reassignment Problem, a large and difficult problem
with a lot of complex constraints: given some reassignment objectives (e.g.,
electricity cost, migration cost, reliability cost), find the best set of
reassignment solutions in a limited time – the limit being quite large (10
hours for large instances). We show that CPLEX can be used with some
relaxations: allowing an optimality tolerance gap (which stops CPLEX when the
solutions found are close to the optimal) and limiting the number of
directions explored in the search space (giving CPLEX only few vectors of
weighted objectives to explore). We also propose to combine the results of
CPLEX to the execution of a metaheuristic (GeNePi) and we compare CPLEX alone,
the metaheuristic alone and the combination of both. We observe that CPLEX is
better than the metaheuristic (an improvement of the hypervolume of 102% in
comparison to GeNePi) while the combination CPLEX+GeNePi outperforms both in
terms of hypervolume (an average increase of 126.9% vs. GeNePi and 17.8% vs.
CPLEX), while the execution time remains acceptable (an increase of only 6% on
average in comparison to CPLEX for execution times larger than 100s). As
future work, we would like to study the usage of algorithms combining
metaheuristics and a mathematical resolution for very large instances as a
scalable substitution for the MILP solver.

#### _Acknowledgement_

This work was supported, in part, by Science Foundation Ireland grants
10/CE/I1855 and 13/RC/2094, and by Science Foundation Ireland Industry
Fellowship grant 13/IF/12789.

## References

  * [1] A. Beloglazov, J. Abawajy, and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing,” FGCS, pp. 755–768, 2012.
  * [2] R. W. Ahmad, A. Gani, S. H. A. Hamid, M. Shiraz, A. Yousafzai, and F. Xia, “A survey on virtual machine migration and server consolidation frameworks for cloud data centers,” JNCA, pp. 11–25, 2015.
  * [3] A. Corradi, M. Fanelli, and L. Foschini, “Vm consolidation: A real case based on openstack cloud,” FGCS, pp. 118–127, 2014.
  * [4] F. Hermenier, S. Demassey, and X. Lorca, “Bin repacking scheduling in virtualized datacenters,” in CP, pp. 27–41, 2011.
  * [5] D. Mehta, B. O’Sullivan, and H. Simonis, “Comparing solution methods for the machine reassignment problem,” in CP, pp. 782–797, 2011.
  * [6] H. Gavranović, M. Buljubašić, and E. Demirović, “Variable neighborhood search for google machine reassignment problem,” ENDM, pp. 209–216, 2012.
  * [7] F. Brandt, J. Speck, and M. Völker, “Constraint-based large neighborhood search for machine reassignment,” Ann Oper Res, pp. 1–29, 2012.
  * [8] M. Gabay and S. Zaourar, “A GRASP approach for the machine reassignment problem,” in EURO, 2012.
  * [9] “Google/roadef challenge’12.” http://challenge.roadef.org/2012/en/.
  * [10] P. Shaw, “Using constraint programming and local search methods to solve vehicle routing problems,” in CP, pp. 417–431, 1998.
  * [11] D. Filani, J. He, S. Gao, M. Rajappa, A. Kumar, P. Shah, and R. Nagappan, “Comparing vm-placement algorithms for on-demand clouds,” in Dynamic data center power management, Intel Technology Journal, 2008.
  * [12] W. Voorsluys, J. Broberg, S. Venugopal, and R. Buyya, “Cost of virtual machine live migration in clouds: A performance evaluation,” in CloudCom, pp. 254–265, 2009.
  * [13] B. Schroeder and G. A. Gibson, “A large-scale study of failures in high-performance computing systems,” TDSC, pp. 337–351, 2010.
  * [14] X. Li, A. Ventresque, J. Omana Iglesias, and J. Murphy, “Scalable correlation-aware virtual machine consolidation using two-phase clustering,” in HPCS, 2015.
  * [15] J. Xu and J. A. Fortes, “Multi-objective virtual machine placement in virtualized data center environments,” in GreenCom, pp. 179–188, 2010\.
  * [16] C.-H. Lien, Y.-W. Bai, and M.-B. Lin, “Estimation by software for the power consumption of streaming-media servers,” TIM, pp. 1859–1870, 2007.
  * [17] E. Zitzler, M. Laumanns, L. Thiele, C. M. Fonseca, and V. G. da Fonseca, “Why quality assessment of multiobjective optimizers is difficult.,” in GECCO, pp. 666–673, 2002.
  * [18] E. Zitzler and L. Thiele, “Multiobjective optimization using evolutionary algorithms. a comparative case study,” in PPSN, pp. 292–301, 1998.
  * [19] K. Bringmann and T. Friedrich, “Approximation quality of the hypervolume indicator,” Artificial Intelligence, pp. 265–290, 2013.
  * [20] G. M. Portal, M. Ritt, L. M. Borba, and L. S. Buriol, “Simulated annealing for the machine reassignment problem,” AOR, pp. 1–22, 2012.
  * [21] T. Saber, A. Ventresque, X. Gandibleux, and L. Murphy, “Genepi: A multi-objective machine reassignment algorithm for data centres,” in HM, pp. 115–129, 2014.
  * [22] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” TEVC, pp. 182–197, 2002.
  * [23] A. Alsheddy and E. E. Tsang, “Guided pareto local search based frameworks for biobjective optimization,” in CEC, 2010.