# Computing Gröbner bases and free resolutions of OI-modules

Michael Morrow  Department of Mathematics, University of Kentucky, 715
Patterson Office Tower, Lexington, KY 40506 USA<EMAIL_ADDRESS>and
Uwe Nagel  Department of Mathematics, University of Kentucky, 715 Patterson
Office Tower, Lexington, KY 40506 USA<EMAIL_ADDRESS>
###### Abstract.

Given a sequence of related modules $M_{n}$ defined over a sequence of related
polynomial rings, one may ask how to simultaneously compute a finite Gröbner
basis for each $M_{n}$. Furthermore, one may ask how to simultaneously compute
the module of syzygies of each $M_{n}$. In this paper we address both
questions. Working in the setting of OI-modules over a Noetherian polynomial
OI-algebra, we provide OI-analogues of Buchberger’s Criterion, Buchberger’s
Algorithm for computing Gröbner bases, and Schreyer’s Theorem for computing
syzygies. We also establish a stabilization result for Gröbner bases.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Gröbner Bases and the OI-Buchberger’s Algorithm
  4. 4 Syzygies and the OI-Schreyer’s Theorem
  5. 5 Computing Free Resolutions

##  1\. Introduction

Computing Gröbner bases and syzygies is a classical problem in commutative and
computational algebra. Recall that if $R$ is a Noetherian polynomial ring over
a field and $F$ is a free module over $R$ of finite rank, then a finite
Gröbner basis of any finitely generated submodule $M$ of $F$ can be computed
using Buchberger’s Algorithm. Furthermore, a theorem of Schreyer shows how to
determine a finite Gröbner basis for the module of syzygies of $M$. These
results can be used to give a constructive proof of Hilbert’s Syzygy Theorem
which asserts that $M$ has a finite free resolution. We refer the reader to
[4, Chapter 15] for more on this topic. In this paper we extend these results
to a setting where we consider a sequence $(M_{n})_{n\in\mathbb{Z}_{\geq 0}}$
of related modules $M_{n}$ over related polynomial rings whose number of
variables increases with $n$. We show that there is a finite algorithm that
simultaneously computes Gröbner bases of all modules in the sequence.

Gröbner bases in contexts beyond Noethertian polynomial rings have been
considered previously, mainly for ideals (see, e.g., [1, 2, 7, 8]). Typically
they focus on ideals in polynomial rings with infinitely many variables.
However, in order to treat also modules a more abstract approach is
beneficial. In [10], Nagel and Römer introduced OI-modules over OI-algebras,
which may be viewed as a generalization of OI-modules over a fixed ring
studied in [12]. In particular, Noetherian polynomial OI-algebras are
classified in [10]. Furthermore, it is shown that any submodule $\mathbf{M}$
of a finitely generated free OI-module $\mathbf{F}$ over a Noetherian
polynomial OI-algebra $\mathbf{P}$ has a finite Gröbner basis. It follows that
$\mathbf{F}$ is Noetherian. The Gröbner basis result has also been used, for
example in [11], where it is shown that the equivariant Hilbert series of any
finitely generated graded OI-module over $\mathbf{P}$ is rational.

The argument for the existence of a finite Gröbner basis in [10] is not
constructive. We address the question of computing such a Gröbner basis in
Section 3. In particular, we give a criterion for determining when a subset of
$\mathbf{M}$ forms a Gröbner basis of $\mathbf{M}$ (see Theorem 3.16), and use
it to describe a finite algorithm for computing a finite Gröbner basis (see
Algorithm 3.17). A key ingredient for our finiteness results is a
combinatorial statement about simultaneously factoring OI-morphisms (Lemma
3.10). Any OI-module $\mathbf{M}$ may be thought of as a sequence
$(\mathbf{M}_{n})_{n\in\mathbb{Z}_{\geq 0}}$ of $\mathbf{P}_{n}$-modules
$\mathbf{M}_{n}$. It follows that our algorithm for $\mathbf{M}$ produces a
Gröbner basis for every $\mathbf{M}_{n}$. This is possible because
stabilization occurs in the sense that there is an integer $n_{0}$ such that
the Gröbner basis of $\mathbf{M}_{n}$ can be determined from the Gröbner basis
of $\mathbf{M}_{n_{0}}$ if $n\geq n_{0}$. Deciding a priori when stabilization
occurs, i.e. estimating $n_{0}$, is a very interesting and open problem. We
establish a condition that guarantees stabilization has occurred (see 3.21).

We also consider the problem of computing syzygies. Given a finite Gröbner
basis $G$ of a submodule $\mathbf{M}$ of a finitely generated free
$\mathbf{P}$-module $\mathbf{F}$, it is shown in Section 4 how to determine a
finite Gröbner basis for the module of syzygies of $\mathbf{M}$ in terms of
$G$ (see 4.6). This may be seen as an extension of Schreyer’s result that
solves this problem in the classical setting.

The finiteness results in [10] were used to establish that a finitely
generated $\mathbf{P}$-module $\mathbf{M}$ has a free resolution with finitely
generated free $\mathbf{P}$-modules. However, only a few explicit resolutions
are known, see [5, 6] for families of examples. Furthermore, if $\mathbf{M}$
is a graded OI-module it is shown in [5] that $\mathbf{M}$ has a graded
minimal free resolution $\mathbf{F}^{\bullet}$. Here minimality means that in
every homological degree $d$ the rank of $\mathbf{F}^{d}$ is at most the rank
of $\mathbf{G}^{d}$ in any other graded free resolution $\mathbf{G}^{\bullet}$
of $\mathbf{M}$. By [5], such a minimal free resolution is unique up to
isomorphism of complexes. In Section 5 we apply our results about Gröbner
bases and syzygies to give a procedure for computing free resolutions. In
particular, if $\mathbf{M}$ is graded, we show how to compute a graded minimal
free resolution of $\mathbf{M}$ up to any chosen homological degree.

##  2\. Preliminaries

In this section we recall the necessary background on OI-modules and fix
notation. Let $K$ be a Noetherian commutative ring with identity.

######  Definition 2.1.

Let OI be the category of totally ordered finite sets and order-preserving
injective maps. An OI-_algebra_ over $K$ is a (covariant) functor from OI to
the category of commutative, associative, unital $K$-algebras.

To define a functor out of OI, it is enough to define it on the corresponding
skeleton. Therefore, we regard OI as the category whose objects are intervals
of the form $[n]=\\{1,\ldots,n\\}$ for $n\in\mathbb{Z}_{\geq 0}$ (we put
$[0]=\emptyset$) and whose morphisms are order-preserving injective maps
$[m]\to[n]$.

If $\mathbf{A}$ is any functor out of OI, we typically write $\mathbf{A}_{n}$
in place of $\mathbf{A}([n])$. We refer to $\mathbf{A}_{n}$ as the _width $n$
component_ of $\mathbf{A}$. If $\varepsilon$ is an OI-morphism, we often write
$\varepsilon_{*}$ instead of $\mathbf{A}(\varepsilon)$. We abuse notation and
write $\textnormal{Hom}(m,n)$ for the set of OI-morphisms
$\textnormal{Hom}_{\textnormal{OI}}([m],[n])$ from $[m]$ to $[n]$.

Polynomial OI-algebras were introduced in [10, Definition 2.17]. This paper
also identifies the Noetherian algebras among these. Following the notation of
[10], their building block is the following algebra.

######  Definition 2.2.

Define an OI-algebra $\mathbf{X}^{\textnormal{OI},1}$ by letting

$\mathbf{X}^{\textnormal{OI},1}_{n}=\begin{cases}K&\text{ if }n=0\\\
K[x_{\pi}\;:\;\pi\in\textnormal{Hom}(1,n)]&\text{ if }n>0\end{cases}$

and, for $\varepsilon\in\textnormal{Hom}(m,n)$, defining
$\varepsilon_{*}:\mathbf{X}^{\textnormal{OI},1}_{m}\to\mathbf{X}^{\textnormal{OI},1}_{n}$
via $x_{\pi}\mapsto x_{\varepsilon\circ\pi}$.

By [10, Proposition 4.8 and Theorem 6.15]), apart from trivial direct
summands, any Noetherian polynomial OI-algebra is isomorphic to
$(\mathbf{X}^{\textnormal{OI},1})^{\otimes c}$ for some integer $c>0$.
Identifying each $\pi$ with its image in $[n]$, one may intuitively think of
$\mathbf{P}=(\mathbf{X}^{\textnormal{OI},1})^{\otimes c}$ as a sequence
$(\mathbf{P}_{n})_{n\in\mathbb{Z}_{\geq 0}}$ of polynomial rings, where

$\mathbf{P}_{n}=K\begin{bmatrix}x_{1,1}&\cdots&x_{1,n}\\\
\vdots&\ddots&\vdots\\\ x_{c,1}&\cdots&x_{c,n}\end{bmatrix}$

has $cn$ variables, together with $K$-algebra homomorphisms
$\varepsilon_{*}\colon\mathbf{P}_{m}\to\mathbf{P}_{n}$ induced by any
$\varepsilon\in\textnormal{Hom}(m,n)$ and defined by $x_{i,j}\mapsto
x_{i,\varepsilon(j)}$.

######  Remark 2.3.

Replacing the category OI by the category FI that has the same skeleton as OI,
but whose morphisms are injective maps $[m]\to[n]$, one defines FI-algebras
and polynomial FI-algebras $(\mathbf{X}^{\textnormal{FI},1})^{\otimes c}$
analogously (see [10, Definition 2.4] for details). Every FI algebra is also
an OI-algebra. In [3], FI-algebras that are finitely generated in width one
are studied. These are precisely the quotients of polynomial FI algebras
$(\mathbf{X}^{\textnormal{FI},1})^{\otimes c}$.

We say an OI-algebra $\mathbf{A}$ is _graded_ if each $\mathbf{A}_{n}$ is a
graded $K$-algebra and each
$\varepsilon_{*}\colon\mathbf{A}_{m}\to\mathbf{A}_{n}$ is a graded
homomorphism of degree 0. Any algebra
$\mathbf{P}=(\mathbf{X}^{\textnormal{OI},1})^{\otimes c}$ is an example of a
graded OI-algebra by assigning each variable degree 1. Throughout this note,
we always use this grading of $\mathbf{P}$.

We now turn to OI-modules over OI-algebras.

######  Definition 2.4 ([10]).

An OI-_module_ $\mathbf{M}$ over an OI-algebra $\mathbf{A}$ is a (covariant)
functor from OI to the category of $K$-modules such that

  1. (i)

each $\mathbf{M}_{n}$ is an $\mathbf{A}_{n}$-module, and

  2. (ii)

for each $a\in\mathbf{A}_{m}$ and $\varepsilon\in\textnormal{Hom}(m,n)$ we
have a commuting diagram

$\textstyle{\mathbf{M}_{m}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a\cdot}$$\scriptstyle{\mathbf{M}(\varepsilon)}$$\textstyle{\mathbf{M}_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbf{A}(\varepsilon)(a)\cdot}$$\textstyle{\mathbf{M}_{m}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbf{M}(\varepsilon)}$$\textstyle{\mathbf{M}_{n}}$
(2.1)

where the vertical maps are multiplication by the indicated elements.

We sometimes refer to $\mathbf{M}$ as an $\mathbf{A}$-_module_.

Intuitively, one may think of an $\mathbf{A}$-module $\mathbf{M}$ as a
sequence $(\mathbf{M}_{n})_{n\in\mathbb{Z}_{\geq 0}}$ of
$\mathbf{A}_{n}$-modules $\mathbf{M}_{n}$ together with maps
$\varepsilon_{*}\colon\mathbf{M}_{m}\to\mathbf{M}_{n}$ induced by any
$\varepsilon\in\textnormal{Hom}(m,n)$.

A _homomorphism_ of $\mathbf{A}$-modules is a natural transformation
$\varphi:\mathbf{M}\to\mathbf{N}$ such that each
$\varphi_{n}\colon\mathbf{M}_{n}\to\mathbf{N}_{n}$ is an
$\mathbf{A}_{n}$-module homomorphism. We sometimes call $\varphi$ an
$\mathbf{A}$-_linear map_. $\mathbf{A}$-modules together with
$\mathbf{A}$-linear maps form an abelian category denoted
$\textnormal{OI}\textnormal{-Mod}(\mathbf{A})$. Thus, all concepts such as
subobject, quotient object, kernel, cokernel, injection, and surjection are
defined “width-wise” from the corresponding concepts in the category of
$K$-modules (see [13, A.3.3]). For example, the _direct sum_ of OI-modules
$\mathbf{M},\mathbf{N}$ is the OI-module $\mathbf{M}\oplus\mathbf{N}$ defined
width-wise by

$(\mathbf{M}\oplus\mathbf{N})_{n}=\mathbf{M}_{n}\oplus\mathbf{N}_{n}$

for every $n\in\mathbb{Z}_{\geq 0}$. Similarly, if
$\varphi\colon\mathbf{M}\to\mathbf{N}$ is an $\mathbf{A}$-linear map then the
kernel of $\varphi$ is a submodule of $\mathbf{M}$ defined by
$(\textnormal{ker}(\varphi))_{n}=\textnormal{ker}(\varphi_{n})$ for
$n\in\mathbb{Z}_{\geq 0}$. The image of $\varphi$ is a submodule of
$\mathbf{N}$ defined analogously.

Note that any OI-algebra $\mathbf{A}$ is trivially an OI-module over itself.
An _ideal_ of $\mathbf{A}$ is a submodule of $\mathbf{A}$.

If $f\in\mathbf{M}_{n}$ for some $n\in\mathbb{Z}_{\geq 0}$ then we call $f$ an
_element_ of $\mathbf{M}$ and write $f\in\mathbf{M}$. In this case we also say
that $f$ _has width $n$_, denoted $w(f)=n$. A _subset_ $S$ of $\mathbf{M}$,
denoted $S\subseteq\mathbf{M}$, is a subset of the disjoint union
$\coprod_{n\geq 0}\mathbf{M}_{n}$. The submodule of $\mathbf{M}$ _generated
by_ a subset $S\subseteq\mathbf{M}$ is defined to be the smallest submodule of
$\mathbf{M}$ containing $S$ and is denoted $\langle S\rangle_{\mathbf{M}}$.
For any integer $m\geq 0$ we define the $m$-_orbit_ of $S$ as the set

$\textnormal{Orb}(S,m)=\\{\mathbf{M}(\varepsilon)(s)\;:\;s\in
S\cap\mathbf{M}_{\ell},\;\varepsilon\in\textnormal{Hom}(\ell,m)\\}\subseteq\mathbf{M}_{m}.$

Thus, for every $m\geq 0$ we have

$(\langle S\rangle_{\mathbf{M}})_{m}=\langle\textnormal{Orb}(S,m)\rangle,$

where the right-hand side is generated as an $\mathbf{A}_{m}$-submodule of
$\mathbf{M}_{m}$.

######  Example 2.5.

Consider $\mathbf{P}=(\mathbf{X}^{\textnormal{OI},1})^{\otimes 2}$ and
$f=x_{1,1}x_{2,2}-x_{1,2}x_{2,1}\in\mathbf{P}_{2}$. Let $\mathbf{I}$ be the
ideal of $\mathbf{P}$ generated by $f$. Then $\mathbf{I}_{n}$ is the ideal of
$\mathbf{P}_{n}$ that is generated by the 2-minors of a generic $2\times n$
matrix.

Let now $\mathbf{J}$ be the ideal of $\mathbf{P}$ that is generated by
$g=x_{1,1}x_{2,2}-x_{1,2}x_{2,1}\in\mathbf{P}_{3}$. Then $\mathbf{J}_{n}$ is
equal to $\mathbf{I}_{n-1}\mathbf{P}_{n}$, the extension ideal of
$\mathbf{I}_{n-1}$ in $\mathbf{P}_{n}$. In particular, we have
$\mathbf{J}_{2}=0$ whereas $\mathbf{I}_{2}=\langle f\rangle\neq 0$.

Finally, let $\mathbf{L}$ be the ideal of $\mathbf{P}$ that is generated by
$x_{1,1}x_{2,3}-x_{1,3}x_{2,1}\in\mathbf{P}_{3}$. Then $\mathbf{L}_{n}$ is the
ideal of $\mathbf{P}_{n}$ that is generated by the 2-minors of a generic
$2\times n$ matrix using columns $i,j$ with $j\geq i+2$.

We now define the most important class of OI-modules for our purposes.

######  Definition 2.6 ([10]).

For any integer $d\geq 0$, define an OI-module
$\mathbf{F}^{\textnormal{OI},d}$ over an OI-algebra $\mathbf{A}$ as follows:
For $n\in\mathbb{Z}_{\geq 0}$ let

$\mathbf{F}^{\textnormal{OI},d}_{n}=\bigoplus_{\pi\in\textnormal{Hom}(d,n)}\mathbf{A}_{n}e_{\pi}\cong(\mathbf{A}_{n})^{\binom{n}{d}}.$

For $\varepsilon\in\textnormal{Hom}(m,n)$, define
$\mathbf{F}^{\textnormal{OI},d}(\varepsilon)\colon\mathbf{F}^{\textnormal{OI},d}_{m}\to\mathbf{F}^{\textnormal{OI},d}_{n}$
via $e_{\pi}\mapsto e_{\varepsilon\circ\pi}$.

A _free_ OI-module over $\mathbf{A}$ is an OI-module $\mathbf{F}$ isomorphic
to a direct sum
$\bigoplus_{\lambda\in\Lambda}\mathbf{F}^{\textnormal{OI},d_{\lambda}}$ for
integers $d_{\lambda}\geq 0$. If $|\Lambda|=n<\infty$, then $\mathbf{F}$ is
said to have _rank $n$_.

To stress the dependence on $\mathbf{A}$ we also write
$\mathbf{F}^{\textnormal{OI},d}_{\mathbf{A}}$ for
$\mathbf{F}^{\textnormal{OI},d}$.

The fact that rank is well-defined is a special case of [5, Lemma 3.6]. Note
that $\mathbf{F}^{\textnormal{OI},0}_{\mathbf{A}}$ is simply the OI-algebra
$\mathbf{A}$ considered as an OI-module over itself.

######  Remark 2.7.

Let $\mathbf{F}=\bigoplus_{i=1}^{s}\mathbf{F}^{\textnormal{OI},d_{i}}$ be a
finitely generated, free OI-module.

  1. (i)

For all $n\geq 0$ we have

$\mathbf{F}_{n}=\bigoplus_{\begin{subarray}{c}\pi\in\textnormal{Hom}(d_{i},n)\\\
1\leq i\leq s\end{subarray}}\mathbf{A}_{n}e_{\pi,i}$

where the second index on $e_{\pi,i}$ is used to keep track of which summand
it lives in.

  2. (ii)

$\mathbf{F}$ is generated as an OI-module by all
$e_{\textnormal{id}_{[d_{i}]},i}$. We call these the _basis elements_ of
$\mathbf{F}$, and any $e_{\pi,i}$ is said to be a _local basis element_ of
$\mathbf{F}$.

  3. (iii)

Let $f=\sum a_{i}e_{\pi_{i},k_{i}}\in\mathbf{F}_{m}$ and let
$\varepsilon\in\textnormal{Hom}(m,n)$. By Condition (2.1), we have

$\mathbf{F}(\varepsilon)(f)=\sum\varepsilon_{*}(a_{i})e_{\varepsilon\circ\pi_{i},k_{i}}.$

  4. (iv)

Any $\mathbf{A}$-linear map out of $\mathbf{F}$ is determined by the images of
the elements $e_{\textnormal{id}_{[d_{i}]},i}$.

######  Example 2.8.

Let $\mathbf{P}=\mathbf{X}^{\textnormal{OI},1}$, so that
$\mathbf{P}_{n}=K[x_{1},\ldots,x_{n}]$ for $n\in\mathbb{Z}_{\geq 0}$. Consider
$\mathbf{F}=\mathbf{F}^{\textnormal{OI},1}_{\mathbf{P}}\oplus\mathbf{F}^{\textnormal{OI},2}_{\mathbf{P}}$.
Since $\textnormal{Hom}(1,n)$ and $\textnormal{Hom}(2,n)$ consist of
$\binom{n}{1}$ and $\binom{n}{2}$ maps, respectively, we have

$\displaystyle\mathbf{F}_{0}$ $\displaystyle=0,$ $\displaystyle\mathbf{F}_{1}$
$\displaystyle=K[x_{1}],$ $\displaystyle\mathbf{F}_{2}$
$\displaystyle=K[x_{1},x_{2}]^{2}\oplus K[x_{1},x_{2}]\cong
K[x_{1},x_{2}]^{3},$ $\displaystyle\mathbf{F}_{3}$
$\displaystyle=K[x_{1},x_{2},x_{3}]^{3}\oplus K[x_{1},x_{2},x_{3}]^{3}\cong
K[x_{1},x_{2},x_{3}]^{6},$

and in general, $\mathbf{F}_{n}\cong
K[x_{1},\ldots,x_{n}]^{\binom{n}{1}+\binom{n}{2}}$.

An OI-module $\mathbf{M}$ over a graded OI-algebra $\mathbf{A}$ is said to be
_graded_ if each $\mathbf{M}_{m}$ is a graded $\mathbf{A}_{m}$-module and each
$\mathbf{M}(\varepsilon)\colon\mathbf{M}_{m}\to\mathbf{M}_{n}$ is a graded
homomorphism of degree 0. If $\mathbf{A}$ is graded, then
$\mathbf{F}^{\textnormal{OI},d}_{\mathbf{A}}$ is a graded module by assigning
the element $e_{\textnormal{id}_{[d]}}$ degree $0$.

We can alter the grading of an OI-module as follows. Given a graded OI-module
$\mathbf{M}$, we define the $d^{th}$ _twist (or shift) of_ $\mathbf{M}$ to be
the OI-module $\mathbf{M}(d)$ that is isomorphic to $\mathbf{M}$ as an OI-
module, and whose grading is determined by

$[\mathbf{M}(d)_{n}]_{j}=[\mathbf{M}_{n}]_{d+j}.$

If $\mathbf{M}$ and $\mathbf{N}$ are graded $\mathbf{A}$-modules, a morphism
$\varphi\colon\mathbf{M}\to\mathbf{N}$ is said to be _graded_ if each
$\varphi_{n}$ is graded of degree 0.

##  3\. Gröbner Bases and the OI-Buchberger’s Algorithm

For the rest of the paper, we assume that $K$ is a field and consider OI-
modules over a polynomial OI-algebra
$\mathbf{P}=(\mathbf{X}^{\textnormal{OI},1})^{\otimes c}$ with some $c\geq 1$.
It has been shown in [10, Theorem 6.14] (see [11, Theorem 5.6]) that every
submodule of a finitely generated free $\mathbf{P}$-module has a finite
Gröbner basis. The goal of this section is to produce an algorithm that
computes such a Gröbner basis in finitely many steps.

We begin by recalling needed concepts. Let
$\mathbf{F}=\bigoplus_{i=1}^{s}\mathbf{F}^{\textnormal{OI},d_{i}}_{\mathbf{P}}$
be a free $\mathbf{P}$-module with basis
$\\{e_{\textnormal{id}_{[d_{i}]},i}\;:\;i\in[s]\\}$. A _monomial_ in
$\mathbf{F}$ is an element of the form $ae_{\pi,i}$ where $a$ is a monomial in
$\mathbf{P}$. We say the monomial $ae_{\pi,i}$ _involves the basis element_
$e_{\textnormal{id}_{[d_{i}]},i}$. The set of all monomials in $\mathbf{F}$ is
denoted $\textnormal{Mon}(\mathbf{F})$. A _monomial submodule of $\mathbf{F}$_
is a submodule of $\mathbf{F}$ generated by monomials.

We need to order the monomials in $\mathbf{F}$.

######  Definition 3.1 (cf. [10, 11]).

A _monomial order on $\mathbf{F}$_ is a total order $<$ on
$\textnormal{Mon}(\mathbf{F})$ such that if $\mu<\nu$ for any monomials
$\mu,\nu\in\mathbf{F}_{m}$, one has

  1. (i)

$\mu<a\mu<a\nu$ for any monomial $a\neq 1$ in $\mathbf{P}_{m}$, and

  2. (ii)

$\mu<\mathbf{F}(\varepsilon)(\mu)<\mathbf{F}(\varepsilon)(\nu)$ for every
$\varepsilon\in\textnormal{Hom}(m,n)$ with $m<n$.

For example, if $c=1$, i.e. $\mathbf{P}=\mathbf{X}^{\textnormal{OI},1}$ and
$\mathbf{F}=\mathbf{F}^{\textnormal{OI},0}\cong\mathbf{P}$ consider
$x_{1}e_{\pi}\in\mathbf{F}_{5}$ and $x_{1}e_{\rho}\in\mathbf{F}_{3}$. Note
that $\pi$ maps the empty set to $[5]$, whereas $\rho$ maps the empty set to
$[3]$. Choose any map $\varepsilon\in\textnormal{Hom}(3,5)$ with
$\varepsilon(1)=1$. Then Condition (ii) in 3.1 gives
$x_{1}e_{\rho}<\mathbf{F}(\varepsilon)(x_{1}e_{\rho})=x_{\varepsilon(1)}e_{\varepsilon\circ\rho}=x_{1}e_{\pi}$.

Monomial orders exist.

######  Example 3.2 (Lexicographic Order).

Order the monomials in each $\mathbf{P}_{m}$ lexicographically with
$x_{i^{\prime},j^{\prime}}<x_{i,j}$ if either $i^{\prime}<i$ or $i^{\prime}=i$
and $j^{\prime}<j$. Define $e_{\rho,j}<e_{\pi,i}$ if $i<j$. For a fixed $i$,
identify a monomial $e_{\pi,i}\in\mathbf{F}_{m}$ with a vector
$(m,\pi(1),\ldots,\pi(d_{i}))\in\mathbb{N}^{d_{i}+1}$ and order such monomials
using the lexicographic order on $\mathbb{N}^{d_{i}+1}$. Finally, for
monomials $ae_{\pi,i}$ and $be_{\rho,j}$ in $\mathbf{F}$, define
$be_{\rho,j}<ae_{\pi,i}$ if $e_{\rho,j}<e_{\pi,i}$ or $e_{\pi,i}=e_{\rho,j}$
and $b<a$ in $\mathbf{P}$. One checks that this gives indeed a monomial order
on $\mathbf{F}$.

There is a suitable generalization of Dickson’s lemma in our context.
Following [10, Definition 6.1], a monomial $be_{\sigma,j}$ is said to be OI-
_divisible_ by a monomial $ae_{\pi,i}$ if $i=j$ and there is an OI-morphism
$\varepsilon$ such that
$\mathbf{F}(\varepsilon)(ae_{\pi,i})=\varepsilon_{*}(a)e_{\varepsilon\circ\pi,i}$
divides $be_{\sigma,j}$. It was shown in [10] (see also [11, Proposition 5.3])
that OI-divisibility gives a well-partial-order on
$\textnormal{Mon}(\mathbf{F})$. Since any monomial order on $\mathbf{F}$
refines the OI-divisibility partial order on $\textnormal{Mon}(\mathbf{F})$ it
follows that any monomial order $<$ on $\mathbf{F}$ is a _well-order_ on
$\textnormal{Mon}(\mathbf{F})$, i.e. any nonempty subset of
$\textnormal{Mon}(\mathbf{F})$ has a unique minimal element with respect to
$<$.

The following concepts are defined as in the classical situation.

######  Definition 3.3.

Fix a monomial order $<$ on $\mathbf{F}$. Let $0\not=f\in\mathbf{F}$ and write
$f=\sum c_{i}\mu_{i}$ for nonzero $c_{i}\in K$ and distinct
$\mu_{i}\in\textnormal{Mon}(\mathbf{F})$. The _leading monomial_ of $f$ is
$\textnormal{lm}(f)=\max_{<}\\{\mu_{i}\\}$. If $\textnormal{lm}(f)=\mu_{i}$
then the _leading coefficient_ of $f$ is $\textnormal{lc}(f)=c_{i}$. The
_leading term_ of $f$ is
$\textnormal{lt}(f)=\textnormal{lc}(f)\cdot\textnormal{lm}(f)$. Given any
subset $E\subseteq\mathbf{F}$ we set
$\textnormal{lm}(E)=\\{\textnormal{lm}(f)\;:\;f\in E\text{ is nonzero}\\}$.

######  Example 3.4.

Consider elements $a=a_{1}+\cdots+a_{t}\in\mathbf{P}$ and
$f=f_{1}+\cdots+f_{s}\in\mathbf{F}$ with monomials $a_{i}\in\mathbf{P}$ and
$f_{j}\in\mathbf{F}$. Possibly after reindexing, assume
$f_{1}>f_{2}>\cdots>f_{s}$ and $a_{1}f_{1}>a_{2}f_{1}>\cdots>a_{t}f_{1}$. It
follows that $a_{1}f_{1}>a_{i}f_{j}$ if $(i,j)\neq(1,1)$, and so
$\textnormal{lm}(af)=a_{1}f_{1}=a_{1}\textnormal{lm}(f)$.

The properties of a monomial order on $\mathbf{F}$ imply the following useful
facts.

######  Remark 3.5.

For any nonzero $f,g\in\mathbf{F}_{m}$ and
$\varepsilon\in\textnormal{Hom}(m,n)$, one has:

  1. (i)

$\textnormal{lm}(f+g)\leq\max(\textnormal{lm}(f),\textnormal{lm}(g))$,

  2. (ii)

$\textnormal{lm}(af)=a\textnormal{lm}(f)$ for any monomial
$a\in\mathbf{P}_{m}$, and

  3. (iii)

$\mathbf{F}(\varepsilon)(\textnormal{lm}(f))=\textnormal{lm}(\mathbf{F}(\varepsilon)(f))$.

We now define our primary object of study.

######  Definition 3.6 ([10, 11]).

Fix a monomial order $<$ on $\mathbf{F}$ and let $\mathbf{M}$ be a submodule
of $\mathbf{F}$. A subset $G\subseteq\mathbf{M}$ is called a _Gröbner basis_
(with respect to $<$) of $\mathbf{M}$ if

$\langle\textnormal{lm}(\mathbf{M})\rangle_{\mathbf{F}}=\langle\textnormal{lm}(G)\rangle_{\mathbf{F}}.$

Every submodule of $\mathbf{M}$ of $\mathbf{F}$ has a Gröbner basis by taking
$G=\mathbf{M}$. We are interested in determining a finite Gröbner basis, which
is guaranteed to exist.

For the remainder of this section, we fix a monomial order $<$ on
$\mathbf{F}$. By restricting $<$ to $\mathbf{F}_{n}$ we obtain a monomial
order on the free $\mathbf{P}_{n}$-module $\mathbf{F}_{n}$ in the classical
sense (see, e.g.,[4]), which we denote by $<_{n}$. The following result
relates Gröbner bases of OI-modules with Gröbner bases of their width $n$
components.

######  Lemma 3.7.

Let $\mathbf{M}$ be a submodule of $\mathbf{F}$. For any subset
$G\subseteq\mathbf{M}$, set $G_{n}=\textnormal{Orb}(G,n)$ for
$n\in\mathbb{Z}_{\geq 0}$. Then $G$ is a Gröbner basis of $\mathbf{M}$ if and
only if each $G_{n}$ is a Gröbner basis of $\mathbf{M}_{n}$ with respect to
$<_{n}$.

###### Proof.

Suppose that $G$ is a Gröbner basis of $\mathbf{M}$ and let
$h\in\mathbf{M}_{n}$. Then
$\textnormal{lm}_{<_{n}}(h)=\textnormal{lm}(h)\in\langle\textnormal{lm}(G)\rangle_{\mathbf{F}}$
so that $\textnormal{lm}_{<_{n}}(h)$ is divisible by some
$\mathbf{F}(\varepsilon)(\textnormal{lm}(g))=\textnormal{lm}_{<_{n}}(\mathbf{F}(\varepsilon)(g))$
with $g\in G$ and $\varepsilon\in\textnormal{Hom}(w(g),n)$. As
$\mathbf{F}(\varepsilon)(g)$ is in $G_{n}$, this shows that
$\textnormal{lm}_{<_{n}}(\mathbf{M}_{n})\subseteq\langle\textnormal{lm}_{<_{n}}(G_{n})\rangle$.
Thus, $G_{n}$ is a Gröbner basis for $\mathbf{M}_{n}$.

The argument for the reverse implication is similar and left to the reader. ∎

Combined with [10, Lemma 2.3], the above observation says that, if we regard
$\mathbf{M}$ as a sequence of modules $(\mathbf{M}_{n})_{n}$, then computing a
finite Gröbner basis $G$ of $\mathbf{M}$ is the same as “simultaneously”
computing a Gröbner basis for each module $\mathbf{M}_{n}$ with the additional
property that the Gröbner basis of $\mathbf{M}_{n}$ is obtained
“combinatorially” by the OI-action from the Gröbner basis of $\mathbf{M}_{w}$
for each $n\geq w$, where $w$ is the maximum width of an element in $G$.

The basis for our computational results is a division algorithm.

######  Definition 3.8.

Let $f\in\mathbf{F}_{n}$ and $B\subseteq\mathbf{F}$. An element
$r\in\mathbf{F}_{n}$ is called a _remainder of $f$ modulo $B$_ if $f=\sum
a_{i}q_{i}+r$ for some $q_{i}\in\textnormal{Orb}(B,n)$ and
$a_{i}\in\mathbf{P}_{n}$ such that

  1. (R1)

either $r=0$ or $\textnormal{lm}(r)$ is not OI-divisible by any element of
$\textnormal{lm}(B)$,

  2. (R2)

$\textnormal{lm}(r)<\textnormal{lm}(f)$ provided $r,f\not=0$ and $r\not=f$,
and

  3. (R3)

$\textnormal{lm}(a_{i}q_{i})\leq\textnormal{lm}(f)$ whenever
$a_{i}q_{i},f\not=0$.

Every element $f\in\mathbf{F}$ has a remainder modulo $B$. If $f$ has width
$n$ such a remainder can be computed by applying the classical division
algorithm in $\mathbf{F}_{n}$ to $f$ and the set $\textnormal{Orb}(B,n)$ with
respect to the monomial order $<_{n}$ on $\mathbf{F}_{n}$ (see, e.g, [4, Ch.
15]).

######  Remark 3.9.

(i) Note that Condition (R3) implies
$\textnormal{lm}(uq_{i})\leq\textnormal{lm}(f)$ for any monomial $u$ in
$a_{i}$, see 3.4.

(ii) An important property of remainders is that if $f\in\mathbf{F}_{m}$ has a
remainder of zero modulo $B$ and $\varepsilon\in\textnormal{Hom}(m,n)$, then
$\mathbf{F}(\varepsilon)(f)$ also has a remainder of zero modulo $B$. This
follows from Remark 3.5(iii) and Definition 3.1(ii).

We now introduce an important combinatorial result about OI-morphisms that
will serve as a key ingredient for our finiteness arguments.

######  Lemma 3.10 (OI-Factorization Lemma).

Consider any maps $\sigma\in\textnormal{Hom}(k_{1},m)$ and
$\tau\in\textnormal{Hom}(k_{2},m)$ with $k_{1},k_{2},m\in\mathbb{Z}_{\geq 0}$
and $k_{1},k_{2}\leq m$. Set
$\ell=|\textnormal{im}(\sigma)\cup\textnormal{im}(\tau)|$. Then there are maps
$\bar{\sigma}\in\textnormal{Hom}(k_{1},\ell)$,
$\bar{\tau}\in\textnormal{Hom}(k_{2},\ell)$ and
$\rho\in\textnormal{Hom}(\ell,m)$ such that

$\sigma=\rho\circ\bar{\sigma}\quad\text{and}\quad\tau=\rho\circ\bar{\tau}$

as well as
$\ell=|\textnormal{im}(\bar{\sigma})\cup\textnormal{im}(\bar{\tau})|$.

###### Proof.

Let $L=\textnormal{im}(\sigma)\cup\textnormal{im}(\tau)$ so that $\ell=|L|$.
Define a map $\gamma\colon L\to[\ell]$ via $i\mapsto|L\cap[i]|$. Clearly
$\gamma$ is strictly increasing. Since $L$ and $[\ell]$ are finite sets of the
same cardinality, it follows that $\gamma$ is a bijection. Now define maps

$\displaystyle\bar{\sigma}\colon[k_{1}]\to[\ell]\quad\text{by}\quad
i\mapsto\gamma(\sigma(i)),$
$\displaystyle\bar{\tau}\colon[k_{2}]\to[\ell]\quad\text{by}\quad
i\mapsto\gamma(\tau(i)),$ and
$\displaystyle\rho\colon[\ell]\to[m]\quad\text{by}\quad
i\mapsto\gamma^{-1}(i).$

Since $\gamma$, $\sigma$ and $\tau$ are strictly increasing, so are
$\bar{\sigma}$, $\bar{\tau}$ and $\rho$. We have
$\sigma=\rho\circ\bar{\sigma}$ and $\tau=\rho\circ\bar{\tau}$ by construction.
The last claim follows from the fact that $\rho$ is injective. ∎

The classical Buchberger’s Algorithm relies on a result known as Buchberger’s
Criterion. It determines when a set forms a Gröbner basis by analyzing so-
called _S-polynomials_. We give the corresponding construction in the OI-
setting below.

######  Definition 3.11.

Let $ae_{\pi,i}$ and $be_{\rho,j}$ be monomials in $\mathbf{F}$. Define

$\textnormal{lcm}(ae_{\pi,i},be_{\rho,j})=\begin{cases}\textnormal{lcm}(a,b)e_{\pi,i}&\text{if
}e_{\pi,i}=e_{\rho,j}\\\ 0&\text{otherwise}.\end{cases}$

Here, $\textnormal{lcm}(a,b)$ is the least common multiple of the monomials
$a$ and $b$ in $\mathbf{P}$.

######  Definition 3.12.

Let $f,g\in\mathbf{F}_{m}$ be nonzero. The _S-polynomial_ of $f$ and $g$ is
the combination

$S(f,g)=\frac{\textnormal{lcm}(\textnormal{lm}(f),\textnormal{lm}(g))}{\textnormal{lt}(f)}f-\frac{\textnormal{lcm}(\textnormal{lm}(f),\textnormal{lm}(g))}{\textnormal{lt}(g)}g.$

######  Remark 3.13.

By design, S-polynomials produce cancellation of leading terms. Specifically,
one has
$\textnormal{lm}(S(f,g))<\textnormal{lcm}(\textnormal{lm}(f),\textnormal{lm}(g))$
for any nonzero $f,g\in\mathbf{F}_{m}$.

We need the following observation whose straightforward proof is left to the
reader.

######  Lemma 3.14.

For any monomials $\mu,\nu\in\mathbf{F}_{m}$, any nonzero
$f,g\in\mathbf{F}_{m}$ and any $\rho\in\textnormal{Hom}(m,n)$, one has

$\mathbf{P}(\rho)\big{(}\frac{\textnormal{lcm}(\mu,\nu)}{\mu}\big{)}=\frac{\textnormal{lcm}(\rho_{*}(\mu),\rho_{*}(\nu))}{\rho_{*}(\mu)}.$

and

$\rho_{*}(S(f,g))=S(\rho_{*}(f),\rho_{*}(g)),$

where $\rho_{*}=\mathbf{F}(\rho)$.

Central to our theory is the notion of a _critical pair_ , which we define as
follows.

######  Definition 3.15.

Let $B\subseteq\mathbf{F}$. A tuple

$(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))\in\textnormal{Orb}(B,m)\times\textnormal{Orb}(B,m)$

is called a _critical pair of $B$_ if $b_{i},b_{j}\neq 0$ and
$\textnormal{lm}(b_{i})$ and $\textnormal{lm}(b_{j})$ involve the same basis
element of $\mathbf{F}$ and
$m=|\textnormal{im}(\sigma)\cup\textnormal{im}(\tau)|$. The set of all
critical pairs of $B$ is denoted $\mathcal{C}(B)$.

An important property of critical pairs is the fact that if $B$ is finite,
then $\mathcal{C}(B)$ is finite. Indeed, using the above notation, finiteness
of $B$ implies that there are only finitely many choices for $b_{i},b_{j}\in
B$, and for each such pair there are only finitely many possible $m$ because
$m=|\textnormal{im}(\sigma)\cup\textnormal{im}(\tau)|\leq w(b_{i})+w(b_{j})$.
The sets $\textnormal{Hom}(w(b_{i}),m)$ and $\textnormal{Hom}(w(b_{j}),m)$ are
finite.

We are now ready to state and prove an OI-version of Buchberger’s Criterion.

######  Theorem 3.16 (OI-Buchberger’s Criterion).

Let $\mathbf{M}=\langle B\rangle_{\mathbf{F}}$ be the OI-module generated by a
subset $B\subseteq\mathbf{F}$. Then $B$ is a Gröbner basis of $\mathbf{M}$ if
and only if $S(f,g)$ has a remainder of zero modulo $B$ for every critical
pair $(f,g)\in\mathcal{C}(B)$.

###### Proof.

Suppose first that $B$ is a Gröbner basis of $\mathbf{M}$. Assume there is
some $(f,g)\in\mathcal{C}(B)$ such that $S(f,g)$ has a nonzero remainder $r$
modulo $B$. Then $S(f,g)=q+r$ for some $q\in\mathbf{M}$. Since
$f,g\in\mathbf{M}$ we have $S(f,g)\in\mathbf{M}$. It follows that
$r\in\mathbf{M}$, and so
$\textnormal{lm}(r)\in\langle\textnormal{lm}(\mathbf{M})\rangle_{\mathbf{F}}=\langle\textnormal{lm}(B)\rangle_{\mathbf{F}}$.
Thus, $\textnormal{lm}(r)$ is OI-divisible by an element of
$\textnormal{lm}(B)$, a contradiction to the fact that $r$ is a remainder
modulo $B$.

Conversely, suppose each $S(f,g)$ with $(f,g)\in\mathcal{C}(B)$ has a
remainder of zero modulo $B$. By Lemma 3.7 it suffices to show for each
$n\in\mathbb{Z}_{\geq 0}$ that $B_{n}=\textnormal{Orb}(B,n)$ is a Gröbner
basis of $\mathbf{M}_{n}$ with respect to $<_{n}$. Pick $f,g\in B_{n}$ and
write $f=\mathbf{F}(\sigma)(b_{1})$ and $g=\mathbf{F}(\tau)(b_{2})$ for
elements $b_{1},b_{2}\in B$ and maps $\sigma\in\textnormal{Hom}(w(b_{1}),n)$
and $\tau\in\textnormal{Hom}(w(b_{2}),n)$. Using the classical Buchberger’s
Criterion (see, e.g., [4, Theorem 15.8]), we need to show that $S(f,g)$ has a
remainder of zero modulo $B_{n}$.

Indeed, if $\textnormal{lm}(b_{1})$ and $\textnormal{lm}(b_{2})$ involve
different basis elements of $\mathbf{F}$ then $S(f,g)$ is zero, and we are
done. Assume $\textnormal{lm}(b_{1})$ and $\textnormal{lm}(b_{2})$ involve the
same basis element of $\mathbf{F}$. By Lemma 3.10, there are maps
$\bar{\sigma}\in\textnormal{Hom}(w(b_{1}),\ell)$,
$\bar{\tau}\in\textnormal{Hom}(w(b_{2}),\ell)$ and
$\rho\in\textnormal{Hom}(\ell,n)$ with
$\ell=|\textnormal{im}(\sigma)\cup\textnormal{im}(\tau)|=|\textnormal{im}(\bar{\sigma})\cup\textnormal{im}(\bar{\tau})|$
such that $\sigma=\rho\circ\bar{\sigma}$ and $\tau=\rho\circ\bar{\tau}$. Put

$\bar{f}=\mathbf{F}(\bar{\sigma})(b_{1})\quad\text{and}\quad\bar{g}=\mathbf{F}(\bar{\tau})(b_{2})$

and note that $(\bar{f},\bar{g})\in\mathcal{C}(B)$. Functoriality of
$\mathbf{F}$ gives $\mathbf{F}(\rho)(\bar{f})=f$ and
$\mathbf{F}(\rho)(\bar{g})=g$. By 3.14, we get

$\mathbf{F}(\rho)(S(\bar{f},\bar{g}))=S(\mathbf{F}(\rho)(\bar{f}),\mathbf{F}(\rho)(\bar{g}))=S(f,g).$

Since $S(\bar{f},\bar{g})$ has a remainder of zero modulo $B$ by assumption,
it follows that $S(f,g)$ also has a remainder of zero modulo $B$. So we can
write $S(f,g)=\sum a_{i}q_{i}$ for some $a_{i}\in\mathbf{P}_{n}$ and some
$q_{i}\in\textnormal{Orb}(B,n)$ such that
$\textnormal{lm}(a_{i}q_{i})\leq\textnormal{lm}(S(f,g))$ whenever
$a_{i}q_{i}\not=0$. As $<$ and $<_{n}$ agree on $\mathbf{F}_{n}$, this says
that $S(f,g)\in\mathbf{M}_{n}$ has a remainder of zero modulo $B_{n}$ with
respect to the order $<_{n}$, completing the argument. ∎

The OI-Buchberger’s Criterion leads to an algorithm for computing Gröbner
bases in finite time. The idea is analogous to the classical case: check if
any S-polynomial has nonzero remainder, and if so, append the remainder and
repeat

######  Algorithm 3.17 (OI-Buchberger’s Algorithm).

A finite subset $B\subset\mathbf{F}$A finite Gröbner basis $G$of $\langle
B\rangle_{\mathbf{F}}$

1:set $G=B$

2:set $P=\mathcal{C}(G)$ $P\not=\emptyset$

3:choose $(f,g)\in P$

4:set $P=P\;\backslash\;\\{(f,g)\\}$

5:let $r$ be a remainder of $S(f,g)$ modulo $G$ $r\not=0$

6:set $G=G\cup\\{r\\}$

7:set $P=\mathcal{C}(G)$

###### Correctness and Termination of 3.17.

Let $G_{1},G_{2},\ldots$ denote the values of $G$ each time it gets updated
(so in particular, $G_{1}=B$). Suppose the algorithm terminates and returns
$G_{t}$. Then $S(f,g)$ has a remainder of zero modulo $G_{t}$ for every
$(f,g)\in\mathcal{C}(G_{t})$, so $G_{t}$ forms a finite Gröbner basis for
$\langle G_{t}\rangle_{\mathbf{F}}$ by the OI-Buchberger’s Criterion. For any
$t$, if $(f,g)\in\mathcal{C}(G_{t})$ and $S(f,g)$ has a remainder of $r\not=0$
modulo $G_{t}$, then $r\in\langle G_{t}\rangle_{\mathbf{F}}$, and so $\langle
G_{t}\rangle_{\mathbf{F}}=\langle G_{t+1}\rangle_{\mathbf{F}}$. It follows
that $\langle G_{t}\rangle_{\mathbf{F}}=\langle B\rangle_{\mathbf{F}}$ and the
algorithm is correct.

Suppose now that the algorithm does not terminate. Since each
$\mathcal{C}(G_{n})$ is finite we obtain an infinite sequence $G_{1}\subseteq
G_{2}\subseteq\cdots$. Let $n\in\mathbb{N}$ and let $r\not=0$ be the remainder
modulo $G_{n}$ used to form $G_{n+1}$. By the definition of remainder, we have
$\textnormal{lm}(r)\not\in\langle\textnormal{lm}(G_{n})\rangle_{\mathbf{F}}$,
and hence
$\langle\textnormal{lm}(G_{n})\rangle_{\mathbf{F}}\subsetneq\langle\textnormal{lm}(G_{n+1})\rangle_{\mathbf{F}}$.
This yields a strictly increasing chain of submodules of $\mathbf{F}$,
contradicting the fact that $\mathbf{F}$ is Noetherian (see [10, Proposition
4.2 and Theorem 6.15]). Hence the algorithm terminates in finite time. ∎

The main result of this section follows easily now.

######  Theorem 3.19.

Every submodule of a finitely generated free OI-module $\mathbf{F}$ over
$\mathbf{P}\cong(\mathbf{X}^{\textnormal{OI},1})^{\otimes c}$ has a finite
Gröbner basis with respect to any monomial order on $\mathbf{F}$ that can be
computed in finitely many steps.

###### Proof.

By [10, Theorem 6.15], any submodule of $\mathbf{F}$ is finitely generated.
Thus, we conclude by applying 3.17. ∎

The first author has implemented 3.17 using Macaulay2 (see [9]).

A finite Gröbner basis $B$ of an OI-module $\mathbf{M}$ is said to be
_minimal_ if every proper subset of $B$ is no longer a Gröbner basis $B$.

######  Example 3.20.

Let
$\mathbf{F}=\mathbf{F}^{\textnormal{OI},1}\oplus\mathbf{F}^{\textnormal{OI},1}\oplus\mathbf{F}^{\textnormal{OI},2}$
have basis
$\\{e_{\textnormal{id}_{[1]},1},e_{\textnormal{id}_{[1]},2},e_{\textnormal{id}_{[2]},3}\\}$.
Suppose $c=2$ so $\mathbf{P}$ has two rows of variables, and let

$B=\\{x_{1,1}e_{\textnormal{id}_{[1]},1}+x_{2,1}e_{\textnormal{id}_{[1]},2},\;x_{1,2}x_{1,1}e_{\pi,2}+x_{2,2}x_{2,1}e_{\textnormal{id}_{[2]},3}\\}$

where $\pi:[1]\to[2]$ is given by $1\mapsto 2$. So, the elements of $B$ have
width one and two, respectively. Using the Macaulay2 code of [9], one obtains
a minimal Gröbner basis for $\langle B\rangle_{\mathbf{F}}$ with respect to
the lex order from Example 3.2:

$\displaystyle
x_{1,1}e_{\textnormal{id}_{[1]},1}+x_{2,1}e_{\textnormal{id}_{[1]},2}$
$\displaystyle\in\mathbf{F}_{1}$ $\displaystyle
x_{1,2}x_{1,1}e_{\pi,2}+x_{2,2}x_{2,1}e_{\textnormal{id}_{[2]},3}$
$\displaystyle\in\mathbf{F}_{2}$ $\displaystyle-
x_{2,3}x_{2,2}x_{1,1}e_{\sigma_{1},3}+x_{2,3}x_{2,1}x_{1,2}e_{\sigma_{2},3}$
$\displaystyle\in\mathbf{F}_{3}$

where $\sigma_{1}:[2]\to[3]$ is given by $1\mapsto 2$ and $2\mapsto 3$ and
$\sigma_{2}:[2]\to[3]$ is given by $1\mapsto 1$ and $2\mapsto 3$. In
particular, the OI-Buchberger’s Algorithm needed to append exactly one more
element of width $3$ before terminating.

Given a submodule $\mathbf{M}$ of $\mathbf{F}$, the fact that $\mathbf{M}$ has
a finite Gröbner basis $G$ combined with 3.7 shows in particular that a
Gröbner basis of $\mathbf{M}$ can be obtained as the union of Gröbner bases of
$\mathbf{M}_{n}$ with respect to the order $<_{n}$ with $n\leq w$, where $w$
is the maximum width of an element in $G$. This suggests an alternative way
for computing a Gröbner basis of $\mathbf{M}$ by determining and comparing
Gröbner bases of $\mathbf{M}_{n}$ with respect to the order $<_{n}$ for
sufficiently large $n$. The problem is that a priori one does not know when to
stop, i.e., what is large enough. The following result gives a sufficient
condition for the desired stabilization.

######  Proposition 3.21.

Let $\mathbf{M}$ be a submodule of a free $\mathbf{P}$-module $\mathbf{F}$
generated by a finite set $B\subset\mathbf{F}$. Let $<$ be any monomial order
on $\mathbf{F}$. For any integer $m\geq 0$ , denote by $<_{m}$ the restriction
of $<$ to $\mathbf{F}_{m}$. Let $W\geq 1$ denote the maximum width of an
element in $B$. Then $B$ is a Gröbner basis of $\mathbf{M}$ with respect to
$<$ if and only if $\textnormal{Orb}(B,m)$ is a Gröbner basis for
$\mathbf{M}_{m}$ with respect to $<_{m}$ for each integer $m\leq 2W$.

###### Proof.

The forward direction is immediate from Lemma 3.6. For the reverse, by the OI-
Buchberger’s Criterion, it suffices to show for any critical pair
$(f,g)\in\mathcal{C}(B)$ that $S(f,g)$ has a remainder of zero modulo $B$.
Considering such a critical pair, we can write
$(f,g)=(\mathbf{F}(\sigma)(b_{1}),\mathbf{F}(\tau)(b_{2}))$ for maps $\sigma$
and $\tau$ and elements $b_{1},b_{2}\in B$ such that $\sigma,\tau$ land in
width $m=|\textnormal{im}(\sigma)\cup\textnormal{im}(\tau)|\leq
w(b_{1})+w(b_{2})\leq 2W$. Hence our hypothesis gives that
$\textnormal{Orb}(B,m)$ is a Gröbner basis for $\mathbf{M}_{m}$, and so
$S(f,g)$ has a remainder of zero modulo $\textnormal{Orb}(B,m)$ with respect
to $<_{m}$. But since $<$ and $<_{m}$ agree on $\mathbf{M}_{m}$, this says
that $S(f,g)$ has a remainder of zero modulo $B$ with respect to $<$. ∎

##  4\. Syzygies and the OI-Schreyer’s Theorem

Recall that in the classical setting, if $M$ is a finitely generated submodule
of a free module of finite rank over a Noetherian polynomial ring, Schreyer’s
Theorem [4, Theorem 15.10] computes a finite Gröbner basis for the module of
syzygies of $M$. Using the theory developed in the previous section, we extend
Schreyer’s result to the setting of OI-modules.

We continue to use the above notation. In particular,
$\mathbf{F}=\bigoplus_{i=1}^{s}\mathbf{F}^{\textnormal{OI},d_{i}}_{\mathbf{P}}$
always denotes a finitely generated, free OI-module over
$\mathbf{P}=(\mathbf{X}^{\textnormal{OI},1})^{\otimes c}$ with some $c\geq 1$.
We fix a monomial order $<$ on $\mathbf{F}$.

Our computation of syzygies of a submodule $\mathbf{M}$ of $\mathbf{F}$
depends on a choice of a generating set of $\mathbf{M}$.

######  Definition 4.1.

Let $B=\\{b_{1},\ldots,b_{t}\\}\subset\mathbf{F}$ and let
$\mathbf{G}=\bigoplus_{i=1}^{t}\mathbf{F}^{\textnormal{OI},w(b_{i})}_{\mathbf{P}}$
be a free OI-module with basis $\\{\epsilon_{\textnormal{id}_{[w(b_{i})]},i}\
:\ i\in[t]\\}$. We define the _module of syzygies of $B$_ as
$\textnormal{Syz}(B)=\textnormal{ker}(\varphi)$, where $\varphi$ denotes the
surjective morphism

$\varphi\colon\mathbf{G}=\bigoplus_{i=1}^{t}\langle\epsilon_{\textnormal{id}_{[w(b_{i})]},i}\rangle_{\mathbf{F}}\to\langle
B\rangle_{\mathbf{F}},\text{ defined by
$\epsilon_{\textnormal{id}_{[w(b_{i})]},i}\mapsto b_{i}$}.$

Our goal in this section is to compute a finite Gröbner basis for
$\textnormal{Syz}(B)$. To begin, we will need a suitable monomial order on
$\mathbf{G}$.

######  Definition 4.2.

Let $B=\\{b_{1},\ldots,b_{t}\\}\subset\mathbf{F}$.

  1. (i)

For any $i\in[t]$, order the set $\\{\textnormal{Hom}(w(b_{i}),n)\,:\,n\geq
w(b_{i})\\}$: Given $\pi\in\textnormal{Hom}(w(b_{i}),m)$ and
$\rho\in\textnormal{Hom}(w(b_{i}),n)$, define $\pi<\rho$ if
$(m,\pi(1),\ldots,\pi(w(b_{i})))<(n,\rho(1),\ldots,\rho(w(b_{i})))$ in the
lexicographic order on $\mathbb{N}^{w(b_{i})+1}$, where $\mathbb{N}$ is
ordered by $1<2<\cdots$.

  2. (ii)

Let $\prec_{B}$ be the total order on the union of the above sets

$\\{(\pi,i)\;:\;i\in[t],\;\pi\in\textnormal{Hom}(w(b_{i}),m),\;m\geq
w(b_{i})\\}$

defined by $(\pi,i)\prec_{B}(\rho,j)$ if either $i<j$ or $i=j$ and $\pi<\rho$.

  3. (iii)

Define a total order $<_{B}$ on $\textnormal{Mon}(\mathbf{G})$ by setting
$a\epsilon_{\pi,i}<_{B}b\epsilon_{\rho,j}$ if either
$\textnormal{lm}(\varphi(a\epsilon_{\pi,i}))<\textnormal{lm}(\varphi(b\epsilon_{\rho,j}))$
or
$\textnormal{lm}(\varphi(a\epsilon_{\pi,i}))=\textnormal{lm}(\varphi(b\epsilon_{\rho,j}))$
and $(\rho,j)\prec_{B}(\pi,i)$.

######  Remark 4.3.

Note that for any monomial $a\epsilon_{\pi,i}\in\textnormal{Mon}(\mathbf{G})$,
one has

$\textnormal{lm}(\varphi(a\epsilon_{\pi,i}))=\textnormal{lm}(a\mathbf{F}(\pi)(b_{i}))=a\mathbf{F}(\pi)(\textnormal{lm}(b_{i}))=a\pi_{*}(\textnormal{lm}(b_{i})).$

Thus, Part (iii) can be more explicitly re-stated as
$a\epsilon_{\pi,i}<_{B}b\epsilon_{\rho,j}$ if either
$a\pi_{*}(\textnormal{lm}(b_{i}))<b\rho_{*}(\textnormal{lm}(b_{j}))$ or
$a\pi_{*}(\textnormal{lm}(b_{i}))=b\rho_{*}(\textnormal{lm}(b_{j}))$ and
$(\rho,j)\prec_{B}(\pi,i)$.

Together with the fact that $<$ is a monomial order on $\mathbf{F}$, the
following observation implies that $<_{B}$ is a monomial order on
$\mathbf{G}$.

######  Lemma 4.4.

Consider any maps $\pi\in\textnormal{Hom}(w(b_{i}),m)$ and
$\rho\in\textnormal{Hom}(w(b_{j}),m)$ with $i,j\in[t]$ and
$\sigma\in\textnormal{Hom}(m,n)$. Then
$(\sigma\circ\pi,i)\prec_{B}(\sigma\circ\rho,j)$ if and only if
$(\pi,i)\prec_{B}(\rho,j)$.

###### Proof.

This follows from the fact that $\sigma$ is a strictly increasing map. ∎

For the remainder of this section we assume that $B=\\{b_{1},\ldots,b_{t}\\}$
is a Gröbner basis of $\langle B\rangle_{\mathbf{F}}$ and that each $b_{i}$ is
monic, possibly after multiplying by a suitable element of $K$. We need some
further notation.

For any $i,j\in[t]$, $\sigma\in\textnormal{Hom}(w(b_{i}),m)$ and
$\tau\in\textnormal{Hom}(w(b_{j}),m)$ with $m\geq\max(w(b_{i}),w(b_{j}))$, the
remainder of $S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))$ modulo $B$
is zero since $B$ is a Gröbner basis. Hence the division algorithm gives an
expression

$S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))=\sum_{\ell}a_{i,j,\ell}^{\sigma,\tau}\mathbf{F}(\pi_{i,j,\ell}^{\sigma,\tau})(b_{k_{i,j,\ell}^{\sigma,\tau}})$

with $a_{i,j,\ell}^{\sigma,\tau}\in\mathbf{P}_{m}$ and
$\mathbf{F}(\pi_{i,j,\ell}^{\sigma,\tau})(b_{k_{i,j,\ell}^{\sigma,\tau}})\in\textnormal{Orb}(B,m)$,
where

$\textnormal{lm}(u\mathbf{F}(\pi_{i,j,\ell}^{\sigma,\tau})(b_{k_{i,j,\ell}^{\sigma,\tau}}))\leq\textnormal{lm}(S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j})))$
(4.1)

for any monomial $u$ in $a_{i,j,\ell}^{\sigma,\tau}$ (see Remark 3.9). Define

$s_{i,j}^{\sigma,\tau}=m_{i,j}^{\sigma,\tau}\epsilon_{\sigma,i}-m_{j,i}^{\tau,\sigma}\epsilon_{\tau,j}-\sum_{\ell}a_{i,j,\ell}^{\sigma,\tau}\epsilon_{\pi_{i,j,\ell}^{\sigma,\tau},k_{i,j,\ell}^{\sigma,\tau}}\in\mathbf{G}_{m}$
(4.2)

where

$m_{i,j}^{\sigma,\tau}=\frac{\textnormal{lcm}(\mathbf{F}(\sigma)(\textnormal{lm}(b_{i})),\mathbf{F}(\tau)(\textnormal{lm}(b_{j})))}{\mathbf{F}(\sigma)(\textnormal{lm}(b_{i}))}\in\mathbf{P}_{m}.$

We need one more preparatory observation.

######  Lemma 4.5.

If $(\sigma,i)\prec_{B}(\tau,j)$ then
$\textnormal{lm}_{<_{B}}(s_{i,j}^{\sigma,\tau})=m_{i,j}^{\sigma,\tau}\epsilon_{\sigma,i}$.

###### Proof.

Note that
$\varphi(m_{i,j}^{\sigma,\tau}\epsilon_{\sigma,i})=\frac{\textnormal{lcm}(\sigma_{*}(\textnormal{lm}(b_{i})),\tau_{*}(\textnormal{lm}(b_{j})))}{\sigma_{*}(\textnormal{lm}(b_{i}))}\sigma_{*}(b_{i})$,
and so its leading monomial is
$\textnormal{lcm}(\sigma_{*}(\textnormal{lm}(b_{i})),\tau_{*}(\textnormal{lm}(b_{j})))$.
Analogously, we see that $\varphi(m_{j,i}^{\tau,\sigma}\epsilon_{\tau,j})$ has
the same leading monomial. Hence $(\sigma,i)\prec_{B}(\tau,j)$ implies
$m_{j,i}^{\tau,\sigma}\epsilon_{\tau,j}<_{B}m_{i,j}^{\sigma,\tau}\epsilon_{\sigma,i}$
by the definition of $<_{B}$. Now fix some $\ell$ and let $u$ be the monomial
in $a_{i,j,\ell}^{\sigma,\tau}$ such that

$\textnormal{lm}_{<_{B}}(a_{i,j,\ell}^{\sigma,\tau}\epsilon_{\pi_{i,j,\ell}^{\sigma,\tau},k_{i,j,\ell}^{\sigma,\tau}})=u\epsilon_{\pi_{i,j,\ell}^{\sigma,\tau},k_{i,j,\ell}^{\sigma,\tau}}.$

Then we obtain

$\displaystyle\textnormal{lm}(u\mathbf{F}(\pi_{i,j,\ell}^{\sigma,\tau})(b_{k_{i,j,\ell}^{\sigma,\tau}}))$
$\displaystyle\leq\textnormal{lm}(S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j})))$
(by (4.1))
$\displaystyle<\textnormal{lcm}(\mathbf{F}(\sigma)(\textnormal{lm}(b_{i})),\mathbf{F}(\tau)(\textnormal{lm}(b_{j})))$
(by Remark 3.13)
$\displaystyle=m_{i,j}^{\sigma,\tau}\mathbf{F}(\sigma)(\textnormal{lm}(b_{i})).$

By definition of $<_{B}$, this gives
$u\epsilon_{\pi_{i,j,\ell}^{\sigma,\tau},k_{i,j,\ell}^{\sigma,\tau}}<_{B}m_{i,j}^{\sigma,\tau}\epsilon_{\sigma,i}$
, and the claim follows. ∎

We are now ready to state and prove the main result of this section.

######  Theorem 4.6 (OI-Schreyer’s Theorem).

The $s_{i,j}^{\sigma,\tau}$ with
$(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))\in\mathcal{C}(B)$ and
$(\sigma,i)\prec_{B}(\tau,j)$ form a finite Gröbner basis for
$\textnormal{Syz}(B)$ with respect to $<_{B}$.

###### Proof.

First note that each $s_{i,j}^{\sigma,\tau}$ is indeed a syzygy, for

$\varphi(s_{i,j}^{\sigma,\tau})=S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))-S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))=0.$

Now let $h\in\textnormal{Syz}(B)$ be any nonzero syzygy. We need to show that
$\textnormal{lm}(h)$ is divisible by the leading monomial of one of the
$s_{i,j}^{\sigma,\tau}$ in the claimed Gröbner basis of $\textnormal{Syz}(B)$.

To see this write
$h=\sum_{\ell=1}^{n}c_{\ell}x^{p_{\ell}}\epsilon_{\pi_{\ell},i_{\ell}}$ for
some nonzero $c_{i}\in K$ and distinct
$x^{p_{\ell}}\epsilon_{\pi_{\ell},i_{\ell}}\in\textnormal{Mon}(\mathbf{G})$.
Note that $n\geq 2$ since $h$ is a nonzero syzygy. Assume the monomials of $h$
are ordered so that
$x^{p_{\ell}}\epsilon_{\pi_{\ell},i_{\ell}}>_{B}x^{p_{\ell^{\prime}}}\epsilon_{\pi_{\ell^{\prime}},i_{\ell^{\prime}}}$
if $\ell<\ell^{\prime}$. Then
$\textnormal{lt}_{<_{B}}(h)=c_{1}x^{p_{1}}\epsilon_{\pi_{1},i_{1}}$ and, by
definition of $<_{B}$, we get

$x^{p_{1}}\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))\geq\cdots\geq
x^{p_{n}}\mathbf{F}(\pi_{n})(\textnormal{lm}(b_{i_{n}})).$ (4.3)

We claim that

$x^{p_{1}}\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))=x^{p_{2}}\mathbf{F}(\pi_{2})(\textnormal{lm}(b_{i_{2}})).$
(4.4)

Indeed, otherwise (4.3) becomes

$x^{p_{1}}\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))>x^{p_{2}}\mathbf{F}(\pi_{2})(\textnormal{lm}(b_{i_{2}}))\geq\cdots\geq
x^{p_{n}}\mathbf{F}(\pi_{n})(\textnormal{lm}(b_{i_{n}})).$ (4.5)

Since $h$ is a syzygy we have
$\sum_{\ell=1}^{n}c_{\ell}x^{p_{\ell}}\mathbf{F}(\pi_{\ell})(b_{i_{\ell}})=0$
which, using (4.5), implies that
$x^{p_{1}}\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))$ can be written as a
$K$-linear combination of strictly smaller monomials. This is impossible, and
hence we have established (4.4).

Since
$x^{p_{1}}\epsilon_{\pi_{1},i_{1}}>_{B}x^{p_{2}}\epsilon_{\pi_{2},i_{2}}$ and
these two elements are mapped by $\varphi$ onto the same element of
$\mathbf{F}$ by (4.4), the definition of $<_{B}$ implies

$(\pi_{1},i_{1})\prec_{B}(\pi_{2},i_{2}).$ (4.6)

Now set $\alpha=x^{p_{1}}\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))$. By
Equation (4.4), $\alpha$ is divisible by
$\mathbf{F}(\pi_{2})(\textnormal{lm}(b_{i_{2}}))$, and so $\alpha$ is
divisible by
$\beta=\textnormal{lcm}(\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}})),\mathbf{F}(\pi_{2})(\textnormal{lm}(b_{i_{2}})))$.
By the OI-Factorization Lemma, there are maps
$\overline{\pi_{1}}\in\textnormal{Hom}(w(b_{i_{1}}),\ell)$,
$\overline{\pi_{2}}\in\textnormal{Hom}(w(b_{i_{2}}),\ell)$ and
$\rho\in\textnormal{Hom}(\ell,m)$ with
$\ell=|\textnormal{im}(\overline{\pi_{1}})\cup\textnormal{im}(\overline{\pi_{2}})|$
such that

$\rho\circ\overline{\pi_{1}}=\pi_{1}\quad\text{and}\quad\rho\circ\overline{\pi_{2}}=\pi_{2}.$

By construction,
$(\mathbf{F}(\overline{\pi_{1}})(b_{i_{1}}),\mathbf{F}(\overline{\pi_{2}})(b_{i_{2}}))$
is in $\mathcal{C}(B)$. Moreover, Relation (4.6) and Lemma 4.4 imply
$(\overline{\pi_{1}},i_{1})\prec_{B}(\overline{\pi_{2}},i_{2})$. Hence, we get

$\displaystyle\frac{\alpha}{\beta}\mathbf{G}(\rho)(\textnormal{lm}_{<_{B}}(s_{i_{1},i_{2}}^{\overline{\pi_{1}},\overline{\pi_{2}}}))$
$\displaystyle=\frac{\alpha}{\beta}\mathbf{G}(\rho)(m_{i_{1},i_{2}}^{\overline{\pi_{1}},\overline{\pi_{2}}}\epsilon_{\overline{\pi_{1}},i_{1}})$
(by Lemma 4.5)
$\displaystyle=\frac{\alpha}{\beta}\frac{\textnormal{lcm}(\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}})),\mathbf{F}(\pi_{2})(\textnormal{lm}(b_{i_{2}})))}{\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))}\epsilon_{\pi_{1},i_{1}}$
(by 3.14)
$\displaystyle=\frac{x^{p_{1}}\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))}{\mathbf{F}(\pi_{1})(\textnormal{lm}(b_{i_{1}}))}\epsilon_{\pi_{1},i_{1}}$
$\displaystyle=x^{p_{1}}\epsilon_{\pi_{1},i_{1}}$
$\displaystyle=\textnormal{lm}_{<_{B}}(h).$

This shows that $\textnormal{lm}_{<_{B}}(h)$ is OI-divisible by
$\textnormal{lm}_{<_{B}}(s_{i_{1},i_{2}}^{\overline{\pi_{1}},\overline{\pi_{2}}})$,
which completes the proof. ∎

In the graded case, the method can be modified to give homogenous syzygies.

######  Remark 4.7.

If $\mathbf{P}$ and $\mathbf{F}$ are graded and the elements of $B$ are
homogenous, we use the morphism

$\varphi\colon\mathbf{G}=\bigoplus_{i=1}^{t}\mathbf{F}^{\textnormal{OI},w(b_{i})}(-\deg(b_{i}))\to\langle
B\rangle_{\mathbf{F}},\text{ defined by
$\epsilon_{\textnormal{id}_{[w(b_{i})]},i}\mapsto b_{i}$}.$

It is graded (of degree zero). One checks that as a consequence the syzygies
defined in (4.2) are homogeneous.

If the generating set $B$ consists of monomials, then one gets a more explicit
Gröbner basis of $\textnormal{Syz}(B)$. The result is an OI-version of the
description of the syzygy module of a monomial module in the classical
situation (see, e.g, [4, Lemma 15.1]).

######  Corollary 4.8.

For any finite set of monomials $B\subset\mathbf{F}_{n}$, the elements
$s_{i,j}^{\sigma,\tau}\in\mathbf{G}$ with
$(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))\in\mathcal{C}(B)$ and
$(\sigma,i)\prec_{B}(\tau,j)$ form a finite Gröbner basis for
$\textnormal{Syz}(B)$ with respect to $<_{B}$, where

$s_{i,j}^{\sigma,\tau}=\frac{\textnormal{lcm}(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))}{\mathbf{F}(\sigma)(b_{i})}\epsilon_{\sigma,i}-\frac{\textnormal{lcm}(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))}{\mathbf{F}(\tau)(b_{j})}\epsilon_{\tau,j}.$

###### Proof.

Since $B$ consists of monomials, it is a Gröbner basis of $\langle
B\rangle_{\mathbf{F}}$ with respect to any monomial order on $\mathbf{F}$.
Thus, 4.6 is applicable. Moreover, each S-polynomial
$S(\mathbf{F}(\sigma)(b_{i}),\mathbf{F}(\tau)(b_{j}))$ is zero, which implies
the stated form of each $s_{i,j}^{\sigma,\tau}$ (see Equation (4.2)). We
conclude by 4.6. ∎

##  5\. Computing Free Resolutions

We now apply our results to the problem of computing free resolutions. We
continue to use the above notation.

Recall that if $\mathbf{M}$ is an $\mathbf{A}$-module, then a _free
resolution_ of $\mathbf{M}$ is an exact sequence

$\mathbf{F}^{\bullet}:\quad\cdots\to\mathbf{F}^{2}\to\mathbf{F}^{1}\to\mathbf{F}^{0}\to\mathbf{M}\to
0,$

where each $\mathbf{F}^{i}$ is a free $\mathbf{A}$-module. If $\mathbf{M}$ is
a finitely generated $\mathbf{P}$-module then $\mathbf{M}$ admits a free
resolution in which every free module $\mathbf{F}^{i}$ is finitely generated
(see [10, Theorem 7.1]). The argument in [10] is based on the finiteness
results established in that paper and not constructive. Using the results of
the previous section we obtain the first algorithm to compute, for any integer
$p\geq 0$, the first $p$ steps of a free resolution of a submodule
$\mathbf{M}$ of $\mathbf{M}$. Indeed, given a finite Gröbner basis $B_{0}$ of
$\mathbf{M}$, define $\varphi_{0}\colon\mathbf{F}^{0}\to\mathbf{M}$ by mapping
the basis elements of $\mathbf{F}^{0}$ onto the corresponding generators in
$B_{0}$. Now let $B_{1}$ be a generating set of
$\textnormal{ker}(\varphi_{0})$ determined by 4.6 and repeat this process.

######  Procedure 5.1 (Method for Computing Free Resolutions).

Let $\mathbf{M}$ be a submodule of a free $\mathbf{P}$-module. Suppose
$\mathbf{M}$ is finitely generated by a subset $B$. Compute a free resolution
for $\mathbf{M}$ as follows:

  1. (i)

Determine a finite Gröbner basis $B_{0}$ for $\mathbf{M}$ using the OI-
Buchberger’s Algorithm applied to the set $B$.

  2. (ii)

Apply the OI-Schreyer’s Theorem to $B_{0}$ to obtain a finite Gröbner basis
$B_{1}$ of $\textnormal{Syz}(B_{0})$.

  3. (iii)

Repeat (ii) as many times as desired to compute a finite Gröbner basis $B_{n}$
of $\textnormal{Syz}(B_{n-1})$.

  4. (iv)

Form (the beginning of) the free resolution $\mathbf{F}^{\bullet}$ by defining
$\mathbf{F}^{i}$ such that $\varphi_{i}$ maps the basis elements of
$\mathbf{F}^{i}$ onto the corresponding generators in $B_{i}$ as in 4.1.

Using 4.7, the above procedure can be modified in the case that $\mathbf{M}$
is a graded OI-module to produce a graded free resolution of $\mathbf{M}$.

If $\mathbf{M}$ is a graded submodule of $\mathbf{F}$, then it is shown in [5,
Theorem 3.10] that $\mathbf{M}$ has a graded free resolution
$\mathbf{F}^{\bullet}$ such that for any other graded free resolution
$\mathbf{G}^{\bullet}$ and for any homological degree $d$, the rank of
$\mathbf{F}^{d}$ is at most the rank of $\mathbf{G}^{d}$. By [5, Theorem
3.10], the resolution $\mathbf{F}^{\bullet}$ is unique up to isomorphisms of
graded free resolutions and called a _minimal_ graded free resolution of
$\mathbf{M}$ in [5]. Our methods allow us to show that there is an algorithm
that produces such a minimal free resolution.

As in the classical situation, a key is to characterize the maps occurring in
a graded minimal free resolution.

######  Definition 5.2 ([5, Definition 3.1]).

Let $\mathbf{F}$ and $\mathbf{G}$ be free $\mathbf{P}$-modules with bases
$\\{f_{1},\ldots,f_{s}\\}$ and $\\{g_{1},\ldots,g_{t}\\}$ where each $f_{i}$
lives in width $u_{i}$ and each $g_{j}$ lives in width $v_{j}$. A morphism
$\varphi\colon\mathbf{F}\to\mathbf{G}$ is determined by the images of the
$f_{i}$, i.e. by $s$ expressions of the form

$\varphi(f_{i})=\sum_{\begin{subarray}{c}1\leq j\leq t\\\
\varepsilon_{i,j}\in\textnormal{Hom}(v_{j},u_{i})\end{subarray}}a_{\varepsilon_{i,j}}\mathbf{G}(\varepsilon_{i,j})(g_{j})$

where each $a_{\varepsilon_{i,j}}\in\mathbf{P}_{u_{i}}$. We say $\varphi$ is
_minimal_ if whenever any $\varepsilon_{i,j}$ is an identity map, the
coefficient $a_{\varepsilon_{i,j}}$ is not a unit.

This concept allows one to check whether a graded free resolution is minimal.
Indeed, [5, Theorem 3.10] gives the following characterization:

######  Theorem 5.3.

A graded free resolution $\mathbf{F}^{\bullet}$ of $\mathbf{M}$ is minimal if
and only if each map between free modules in $\mathbf{F}^{\bullet}$ is
minimal.

We are ready to establish that the first steps of a graded minimal free
resolution can be computed algorithmically.

######  Theorem 5.4.

If $\mathbf{M}$ is a graded submodule of $\mathbf{F}$ with a finite generating
set $B$ consisting of homogenous elements, then, for any integer $p\geq 0$,
there is a finite algorithm that determines the first $p$ steps

$\mathbf{F}^{p}\to\cdots\to\mathbf{F}^{2}\to\mathbf{F}^{1}\to\mathbf{F}^{0}\to\mathbf{M}\to
0$

in a graded minimal free resolution of $\mathbf{M}$.

###### Proof.

Using the graded version of Procedure 5.1, we compute a graded exact sequence

$\mathbf{F}^{p}\to\cdots\to\mathbf{F}^{2}\to\mathbf{F}^{1}\to\mathbf{F}^{0}\to\mathbf{M}\to
0,$

where each $\mathbf{F}^{i}$ is a finitely generated graded free
$\mathbf{P}$-module. If one of the maps in this sequence is not minimal we
prune the sequence to obtain an exact sequence such that two consecutive free
modules are replaced by free modules of strictly smaller rank. Repeating this
process as often as needed beginning with the right-most map one eventually
obtains (the beginning) of a graded minimal free resolution of $\mathbf{M}$.

The pruning is described in detail in the proof of [5, Lemma 3.5]. ∎

5.1 and the algorithm in 5.4 have been implemented in [9].

######  Example 5.5.

  1. (i)

Let
$\mathbf{F}=\mathbf{F}^{\textnormal{OI},1}\oplus\mathbf{F}^{\textnormal{OI},2}$
have basis $\\{e_{\textnormal{id}_{[1]},1},e_{\textnormal{id}_{[2]},2}\\}$.
Let $c=2$, that is, $\mathbf{P}$ has two rows of variables, and consider the
submodule $\mathbf{M}$ of $\mathbf{F}$ generated by the single element
$f=x_{1,2}x_{1,1}e_{\pi,1}+x_{2,2}x_{2,1}e_{\rho,2}\in\mathbf{F}_{3}$ where
$\pi:[1]\to[3]$ is given by $1\mapsto 2$ and $\rho:[2]\to[3]$ is given by
$1\mapsto 1$ and $2\mapsto 3$.

The first step in resolving $\mathbf{M}$ is to compute a Gröbner basis for
$\mathbf{M}$ with respect to the lex order. Unlike in the classical setting,
the one-element set $\\{f\\}$ does _not_ form a Gröbner basis for
$\mathbf{M}$. In fact a minimal Gröbner basis for $\mathbf{M}$ can be computed
using the Macaulay2 script in [9]:

$\displaystyle x_{1,2}x_{1,1}e_{\pi,1}+x_{2,2}x_{2,1}e_{\rho,2}$
$\displaystyle\in\mathbf{F}_{3}$ $\displaystyle-
x_{2,2}x_{2,1}e_{\sigma,2}+x_{2,2}x_{2,1}e_{\tau,2}$
$\displaystyle\in\mathbf{F}_{4}$ $\displaystyle-
x_{2,3}x_{2,2}x_{1,1}e_{\alpha,2}+x_{2,3}x_{2,1}x_{1,2}e_{\sigma,2}$
$\displaystyle\in\mathbf{F}_{4}$

where the maps $\sigma,\tau,\alpha$ are given as

$\displaystyle\sigma:[2]$ $\displaystyle\to[4]$ $\displaystyle 1$
$\displaystyle\mapsto 1$ $\displaystyle 2$ $\displaystyle\mapsto 4$
$\displaystyle\tau:[2]$ $\displaystyle\to[4]$ $\displaystyle 1$
$\displaystyle\mapsto 1$ $\displaystyle 2$ $\displaystyle\mapsto 3$
$\displaystyle\alpha:[2]$ $\displaystyle\to[4]$ $\displaystyle 1$
$\displaystyle\mapsto 2$ $\displaystyle 2$ $\displaystyle\mapsto 4.$

The script in [9] then implements Theorem 5.4 to obtain the beginning of the
minimal resolution of $\mathbf{M}$:

$\cdots\to\mathbf{F}^{4}\to\mathbf{F}^{3}\to\mathbf{F}^{2}\to\mathbf{F}^{1}\to\mathbf{F}^{0}\to\mathbf{M}\to
0$

where

$\displaystyle\textnormal{rank}(\mathbf{F}^{0})$ $\displaystyle=1$
$\displaystyle\textnormal{rank}(\mathbf{F}^{1})$ $\displaystyle=2$
$\displaystyle\textnormal{rank}(\mathbf{F}^{2})$ $\displaystyle=5$
$\displaystyle\textnormal{rank}(\mathbf{F}^{3})$ $\displaystyle=9$
$\displaystyle\textnormal{rank}(\mathbf{F}^{4})$ $\displaystyle=14.$

Finally, $\mathbf{F}^{0}$ is generated in width $3$, and if $1\leq k\leq 4$,
then $\mathbf{F}^{k}$ has its generators in width $k+4$.

  2. (ii)

Let
$\mathbf{F}=\mathbf{F}^{\textnormal{OI},1}\oplus\mathbf{F}^{\textnormal{OI},1}$
have basis $\\{e_{\textnormal{id}_{[1]},1},e_{\textnormal{id}_{[1]},2}\\}$ and
let $c=2$ so that $\mathbf{P}$ has two rows of variables. Consider the
submodule $\mathbf{N}$ of $\mathbf{F}$ generated by
$x_{1,2}x_{1,1}e_{\pi,1}+x_{2,2}x_{2,1}e_{\rho,2}$, where $\pi:[1]\to[2]$ is
given by $1\mapsto 2$ and $\rho:[1]\to[2]$ is given by $1\mapsto 1$. As in the
previous example, the Macaulay2 script in [9] computes the beginning of the
minimal resolution of $\mathbf{N}$:

$\cdots\to\mathbf{F}^{4}\to\mathbf{F}^{3}\to\mathbf{F}^{2}\to\mathbf{F}^{1}\to\mathbf{F}^{0}\to\mathbf{N}\to
0$

where

$\displaystyle\textnormal{rank}(\mathbf{F}^{0})$ $\displaystyle=1$
$\displaystyle\textnormal{rank}(\mathbf{F}^{1})$ $\displaystyle=1$
$\displaystyle\textnormal{rank}(\mathbf{F}^{2})$ $\displaystyle=2$
$\displaystyle\textnormal{rank}(\mathbf{F}^{3})$ $\displaystyle=3$
$\displaystyle\textnormal{rank}(\mathbf{F}^{4})$ $\displaystyle=4.$

Here, $\mathbf{F}^{0}$ is generated in width $2$, and if $1\leq k\leq 4$, then
$\mathbf{F}^{k}$ has its generators in width $k+3$.

Finally, we remark that any free resolution $\mathbf{F}^{\bullet}$ of
$\mathbf{M}$ induces, for any integer $w\geq 0$, a free resolution
$\mathbf{F}^{\bullet}_{w}$ of $\mathbf{M}_{w}$ by restricting each
differential width-wise. Thus, if we think of $\mathbf{M}$ as a sequence
$(\mathbf{M}_{n})_{n}$ of related modules, our techniques “simultaneously”
compute a free resolution for each $\mathbf{P}_{n}$-module $\mathbf{M}_{n}$ in
the sequence. Even if the resolution $\mathbf{F}^{\bullet}$ was minimal, its
width $w$ component $\mathbf{F}^{\bullet}_{w}$ is not necessarily a minimal
resolution of $\mathbf{M}_{n}$ over $\mathbf{P}_{n}$. However, if necessary,
$\mathbf{F}^{\bullet}_{w}$ can be pruned to get a minimal free resolution of
$\mathbf{M}_{n}$. Indeed, it is straightforward to adapt the pruning method of
[5] to this case. In fact, it becomes considerably simpler.

## References

  * [1] A. Brouwer and J. Draisma, _Equivariant Gröbner bases and the two-factor model_. Math. Comput. $\mathbf{80}$ (2011), 1123–1133.
  * [2] D. E. Cohen, _Closure relations, Buchberger’s algorithm, and polynomials in infinitely many variables_ , In _Computation theory and logic_ , Lecture Notes in Comput. Sci. 270 (1987), 78–87.
  * [3] J. Draisma, R. H. Eggermont and A. Farooq, _Components of symmetric wide-matrix varieties_ , J. Reine Angew. Math. $\mathbf{793}$ (2022), 143–184.
  * [4] D. Eisenbud, _Commutative algebra_ , Graduate Texts in Mathematics $\mathbf{150}$, Springer-Verlag, New York, 1995.
  * [5] N. Fieldsteel and U. Nagel, _Minimal and cellular free resolutions over polynomial OI-algebras_ , Preprint, arXiv:2105.08603, 2021.
  * [6] N. Fieldsteel and U. Nagel, _Buchsbaum-Eisenbud complexes of OI-modules_ , Preprint, arXiv:2206.12960, 2022.
  * [7] C. J. Hillar, R. Krone and A Leykin, _Equivariant Gröbner bases_ , In: The 50th Anniversary of Gröbner Bases, T. Hibi, ed. (Tokyo: Mathematical Society of Japan, 2018), Adv. Stud. Pure Math. 77, 129–154.
  * [8] C. J. Hillar and S. Sullivant, _Finite Gröbner bases in infinite dimensional polynomial rings and applications_ , Adv. Math. 229 (2012), 1–25.
  * [9] M. Morrow, _OIGroebnerBases.m2_ , Macaulay2 package; available at
https://github.com/morrowmh/OIGroebnerBases.

  * [10] U. Nagel and T. Römer, _FI- and OI-modules with varying coefficients_ , J. Algebra $\mathbf{535}$ (2019), 286-322.
  * [11] U. Nagel, _Rationality of equivariant Hilbert series and asymptotic properties_ , Trans. Amer. Math. Soc. $\mathbf{374}$ (2021), no. 10, 7313-7357.
  * [12] S. V. Sam and A. Snowden, _Gröbner methods for representations of combinatorial categories_ , J. Amer. Math. Soc. 30 (2017), 159–203.
  * [13] C. A. Weibel, _An introduction to homological algebra_ , Cambridge Studies in Advanced Mathematics 38, Cambridge University Press, Cambridge, 1994.