initial_results.tex

\section{Definitions and initial results}

\subsection{Parametric Gröbner bases and their motivation}
Gröbner bases are a central tool when doing almost any computations on ideals in multivariate polynomial rings. Gröbner bases helps us to decide ideal membership, and when using a suitable term order it helps us to intersect ideals, eliminate variables, decide radical membership etc. Sometimes, we wish to study a family of ideals, parameterized by some variables. We could for instance ask for which values of $a$ and $b$ we have $ax - 1 \in \langle bx - 1 \rangle$. While this example is admittedly simple, answering such questions in general would require us to be able to describe a Gröbner basis for a parameterized ideal, no matter what value the parameters take. In this simple example, $ax - 1 \in \langle bx - 1 \rangle$ if and only if $a = b$ unless $b = 0$ in which case the inclusion hold for any value of $a$. This corresponds to the observation that $bx - 1$ is a Gröbner basis for the ideal and when $b=0$, 1 is a Gröbner basis.

We will gradually look at more structured ways of describing the Gröbner basis of a parameterized ideal. The first definition was introduced by Volker Weispfenning in~\cite{Weispfenning}.

\begin{definition}[Comprehensive parametric Gröbner basis]\label{def:par_grb}
  Let $A$ be a commutative, Noetherian ring, $k_{1}$ be a field, $X$ be a set of variables and let $F \subset A[X]$ be a finite set of polynomials. A \textit{comprehensive parametric Gröbner basis} of $\langle F \rangle$ is a finite set of polynomials $G \subset \langle F \rangle$ such that $\sigma(G)$ is a Gröbner basis of $\langle \sigma(\langle F \rangle) \rangle$ for any ring homomorphism $\sigma : A \to k_{1}$. Here $\sigma(f)$ for an $f \in A[X]$ denotes the coefficient-wise application of $\sigma$ on $f$.
\end{definition}
\textit{Remark. }Most of this text will focus on the special case when $k$ is a field contained in $k_{1}$, $U$ is another set of variables with $U \cap X = \emptyset$ and $A = k[U]$. Then $\sigma : k[U] \to k_{1}$ corresponds to a choice of value for each variable in $U$. Since $k[U][X]$ is isomorphic to $k[X, U]$, we will often refer to parametric Gröbner bases of an ideal $I \subset k[X, U]$. It is also important to see, that $\langle \sigma(F) \rangle = \langle \sigma(\langle F \rangle) \rangle$ for any finite $F \subset A[X]$ and any specialization $\sigma$.

For example, consider the ideal $I = \langle ux + y, y^{2} + 1 \rangle \subset \C[u][x, y]$. The given generators form a Gröbner basis of $I$ w.r.t.\ the lexicographic monomial order, and also for every choice of $u$, except $u = 0$. In this case, the generators become $\{y, y^{2} + 1\}$, which is not a Gröbner basis. Indeed, $\langle y, y^{2} + 1 \rangle = \C[x, y]$, so $1 \in \langle \LM(\langle y, y^{2} + 1 \rangle) \rangle$. But $\langle \LM(\{y, y^{2} + 1\}) \rangle = \langle y \rangle$, which does not contain 1.

We call a ring homomorphism $\sigma : k[U] \to k_{1}$ a \textit{specialization}. Since $\sigma|k : k \to k_{1}$ is always injective, we can assume without loss of generality that $k \subset k_{1}$ and that $\sigma$ restricted to $k$ is the identity, i.e. $\sigma|k = id$. By the linearity of $\sigma$, we can characterize $\sigma$ uniquely by its image of $\,U$. Thus, we can identify $\{\sigma : k[U] \to k_{1} \mid \sigma \text{ is a ring hom.}\}$ with the affine space $k_{1}^{|U|}$. For $\alpha \in k_{1}^{|U|}$ we'll denote the corresponding map
\[\sigma_{\alpha}(u_{i}) = \alpha_{i} \quad \text{for $u_{i} \in U$}\] extended linearly.

It should be noted, that for computing Gröbner bases of ideals in the ring $k[U][X]$, it suffices to compute a Gröbner basis of the ideal, just viewing it as an ideal in $k[X, U]$ with respect to a monomial order where $X^{v_{1}} > U^{v_{2}}$ for all vectors of natural numbers $v_{1}, v_{2}$. This is proven in lemma~\ref{lem:block_order}.

\begin{example}\upshape
  The behavior of the ideal of leading monomials is highly erratic under specializations. If $F$ is a generating set for some ideal $I \subset A[X]$ and $\sigma : A \to k_{1}$ is a specialization, then we can have all the following scenarios:
  \begin{itemize}
    \item $\langle \LM(\sigma(I)) \rangle = \langle \LM(I) \rangle$ \\ If $F = \{x^{2} + u\} \subset \C[u][x]$ and $\sigma : \C[u] \to \C$ sets $\sigma(u) = 0$, then $\sigma(F) = \{x^{2}\}$, hence $\langle x^{2} \rangle = \langle \LM(\sigma(I)) \rangle = \langle \LM(I) \rangle = \langle x^{2} \rangle$.

    \item $\langle \LM(\sigma(I)) \rangle \subsetneq \langle \LM(I) \rangle$ \\ If $F = \{ux, y\} \subset \C[u][x]$ and $\sigma : \C[u] \to \C$ sets $\sigma(u) = 0$, then $\sigma(F) = \{y\}$, hence $\langle y \rangle = \langle \LM(\sigma(I)) \rangle \subsetneq \langle \LM(I) \rangle = \langle x, y \rangle$.

    \item $\langle \LM(I) \rangle \subsetneq \langle \LM(\sigma(I)) \rangle$ \\ If $F = \{ux^{2} + x\} \subset \C[u][x]$ and $\sigma : \C[u] \to \C$ sets $\sigma(u) = 0$, then $\sigma(F) = \{x\}$, hence $\langle x^{2} \rangle = \langle \LM(I) \rangle \subsetneq \langle \LM(\sigma(I)) \rangle = \langle x \rangle$.

    \item $\langle \LM(I) \rangle \nsubset \langle \LM(\sigma(I)) \rangle$ and $\langle \LM(\sigma(I)) \rangle \nsubset \langle \LM(I) \rangle$ \\ If $F = \{ux^{2} + x, uy\} \subset \C[u][x]$ and $\sigma : \C[u] \to \C$ sets $\sigma(u) = 0$, then $\sigma(F) = \{x\}$, hence $\langle \LM(I) \rangle = \langle x^{2}, y \rangle$ which is neither a subset nor a superset of $\langle \LM(\sigma(I)) \rangle = \langle x \rangle$.
  \end{itemize}
\end{example}

% \begin{example}\upshape
%   Consider the ideal $I = \langle ux - 1, vx - 1 \rangle \subset \C[u, v][x, y]$ and a specialization $\sigma : \C[u, v] \to \C$. To analyze the behaviour of $I$ under different specializations, let's split into cases.

%   \begin{enumerate}
%     \item If either $\sigma(u) = 0$ or $\sigma(v) = 0$, then $\langle \sigma(I) \rangle = \langle 1 \rangle \subset \C[x, y]$. If $\sigma(u) = 0$, then $\sigma(ux - 1) = -1$, hence the generators above form a Gröbner basis of $\langle I \rangle$. The other polynomial becomes redundant, so we don't have a reduced Gröbner basis.

%     \item If $\sigma(u) = \sigma(v)$, then $\langle \sigma(I) \rangle = \langle \sigma(u)x - 1 \rangle$. In this case the generators also form a Gröbner basis.

%     \item If $\sigma(u) \neq \sigma(v)$ and neither of them are 0, then $\sigma(v)(\sigma(u)x - 1) - \sigma(u)(\sigma(v)x - 1) = \sigma(v) - \sigma(u) \in \langle \sigma(I) \rangle$, hence $\langle \sigma(I) \rangle = \langle 1 \rangle$. In this case the generators do not form a Gröbner basis of $\langle \sigma(I) \rangle$.
%   \end{enumerate}

%   The reduced Gröbner basis of $I$ is $\{u - v, ux - 1\}$, which always specializes to a Gröbner basis, as can be seen above. However, it is not always enough to compute a reduced Gröbner basis.

%   Consider the ideal $J = \langle ux^{2} + y, y^{2} + 1 \rangle$, where the generators form the reduced Gröbner basis of $J$. And indeed, whenever $\sigma(u) \neq 0$, it specializes to the reduced Gröbner basis of $\langle \sigma(J) \rangle$. However, when $\sigma(u) = 0$, we get $\langle \sigma(J) \rangle = \langle 1 \rangle$, but $\sigma(\{ux^{2} + y, y^{2} + 1\}) = \{y, y^{2} + 1\}$, which is not a Gröbner basis.

%   $G = \{ax^{2} + y + 1, bx^{2} + y + 1, y-1\}$
% \end{example}

As can be seen from the example of $\{ux + y, y^2 + 1\}$, a set of generators can form a parametric Gröbner basis for a restricted set of specializations. Sometimes we are only interested in a subset of specializations. Since a specialization is uniquely determined by its image of the parameters, we use subsets of $k_{1}^{|U|}$ to describe these restrictions. Since the end goal of this is to compute parametric Gröbner bases, we want to work with subsets that can be described in a computationally feasible way. We use the Zariski topology, where closed sets (and hence open sets) can be described by a finite set of polynomials.

\begin{definition}[Vanishing sets \& locally closed sets]
  Let $k \supset k_{1}$ be fields and $E \subset k[X]$. Then the \textit{vanishing set} of $E$ is $\V(E) := \{v \in k_{1}^{n} \mid e(v) = 0 \;\; \forall e \in E\}$.  If $f \in k[X]$ we write $\V(f)$ to mean $\V(\{f\})$.

  A \textit{locally closed set}\footnote{Called such because if $\,Y = C \setminus D$ is a locally closed set, then $Y$ is a closed set in the subspace topology on $D^{\complement}$} is a set of the form $\V(E) \setminus \V(N)$ for two closed sets $\V(E)$ and $\V(N)$.
\end{definition}

For example, when working over $k = \R$, we have $\V(0) = \R^{n}$, $\V(1) = \emptyset$, and $\V(x^{2} + y^{2} - 1)$ is the unit circle in $\R^{2}$. $\V(x^{2} + y^{2} - 1) \setminus \V(x)$ is the unit circle in $\R^{2}$ with the  $x$-axis removed. In the Zariski topology a subset $C \subset k_{1}^{n}$ is closed if and only if $C = \V(E)$ for some $E \subset k[X]$. It should be noted, that $\V(E) = \V(\langle E \rangle)$ for all $E \subset k[X]$.

\begin{definition}[Parametric Gröbner basis]
  Let $k \supset k_{1}$ be fields, let $X$ be a set of variables, let $F \subset k[U][X]$ be a finite set of polynomials and let $Y \subset k_{1}^{|U|}$ be a locally closed set. A \textit{parametric Gröbner basis} of $\langle F \rangle$ on $Y$ is a finite set of polynomials $G \subset \langle F \rangle$ such that $\sigma(G)$ is a Gröbner basis of $\langle \sigma(\langle F \rangle) \rangle$ for any ring homomorphism $\sigma_{\alpha} : k[U] \to k_{1}$ with $\alpha \in Y$.
\end{definition}
\begin{definition}[Gröbner system]
  Let $Y$ be a locally closed set and $F, G \subset k[U][X]$ be finite sets. Then $(Y, G)$ is called a \textit{segment of a Gröbner system for $F$} if $\sigma_{\alpha}(G)$ is a Gröbner basis of $\langle \sigma_{\alpha}(F) \rangle$ for all $\alpha \in Y$. A set $\{(Y_{1}, G_{1}), \dots, (Y_{t}, G_{t})\}$ is called a \textit{Gröbner system} if each $(Y_{i}, G_{i})$ is a segment of a Gröbner system.

  We call the locally closed sets $Y_{i}$ for the $\textit{conditions}$ on a segment.

  A Gröbner system $\{(Y_{1}, G_{1}), \dots, (Y_{t}, G_{t}))\}$ is called \textit{comprehensive}, if $\bigcup_{i=1}^{\,t}Y_{i} = k_{1}^{|U|}$. We also say a Gröbner system is \textit{comprehensive on $L \subset k_{1}^{|U|}$} if $\bigcup_{i=1}^{t}Y_{i} = L$.
\end{definition}

We will sometimes call a triple $(E, N, G)$ for a segment of a Gröbner system. By this we mean that $(V(E) \setminus V(N), G)$ is a segment of a Gröbner system. Do also note, that for segments of a Gröbner system, we relax the restriction that $G \subset \langle F \rangle$ to just $G \subset A[X]$.

Gröbner systems and parametric Gröbner bases are restricted to ideals in $k[U][X]$ instead of over a more general ring $A[X]$. Section~\ref{sec:grb_covers} will cover the more general case.

\begin{example}\upshape
  Consider again the ideal $J = \langle ux^{2} + y, y^{2} + 1 \rangle \subset \C[u][x, y]$. It shouldn't be hard to convince yourself that the given generators form a Gröbner basis under any specialization where $\sigma(u) \neq 0$. For the specialization setting $\sigma(u) = 0$, we have $\langle \sigma(J) \rangle = \langle 1 \rangle$. Hence, we have the following comprehensive Gröbner system:
  \[\{(\V(0) \setminus \V(u), \{ux^{2} + y, y^{2} + 1\}), \quad (\V(u) \setminus \V(1), \{1\})\}\]

  The first segment gives a parametric Gröbner basis of $J$ on $\V(0) \setminus \V(u)$. But since $1 \notin \J$, the second segment does not give a parametric Gröbner basis of $J$ on $\V(u) \setminus \V(1)$. However, $-y(ux^{2} + y) + (y^{2} + 1) = -ux^{2}y + 1 \in J$ specializes to $1$ when $\sigma(u) = 0$. Hence, we also have the following Gröbner system, which also gives a comprehensive parametric Gröbner basis:
  \[\{(\V(0) \setminus \V(1), \{ux^{2} + y, y^{2} + 1, -ux^{2}y + 1\})\}\]
\end{example}

\begin{definition}[Leading coefficient w.r.t.\ variables]
  Let $f \in k[X, U]$. Then $\LT_{U}(f)$ denotes the leading term of $f$, when we see $f$ as an element of $k[U][X]$. Similarly, the leading coefficient of $f \in k[U][X]$ is $\LC_{U}(f)$ and the leading monomial is $\LM_{U}(f)$.
\end{definition}

Note that $\LC_{U}(f) \in k[U]$, i.e.\ the leading term is a polynomial in $k[U]$ times a monomial in $X$. For example, the polynomial $f = ux + vx + 1 \in C[x, u, v]$ has $\LC_{\{u, v\}}(f) = u + v$, $\LM_{\{u, v\}}(f) = x$ and $\LT_{\{u, v\}}(f) = (u+v)x$.

From this point, we assume that the monomial order on $k[X, U]$ satisfies $X^{v_{1}} > U^{v_{2}}$ for all $v_{1} \in \N^{|X|}$ and $v_{2} \in \N^{|U|}$. We will write this property as $X \gg U$. This monomial order restricts to a monomial order on $k[X]$, denoted by $<_{X}$. Note that this assumption is not too restrictive, as we're usually only interested in a certain monomial order on the variables, since the parameters will be specialized away anyway. Thus, for a given monomial order $<_{X}$, we can construct a suitable monomial order on $k[X, U]$, by using $<_{X}$ and breaking ties with any monomial order on $k[U]$. The lexicographic order with $X > U$ satisfies $X \gg U$. The reason for this assumption is the following lemma:

\begin{lemma}\label{lem:block_order}
  Let $<$ be a monomial order on $k[X, U]$ such that $X \gg U$, let $I \subset k[X, U]$ be an ideal and let $G = \{g_{1}, \dots, g_{n}\}$ be a Gröbner basis of $I$ w.r.t.\ $<$. Then $G$ can be seen as a Gröbner basis of $\,I \subset k[U][X]$ w.r.t.\ the restricted monomial order $<_{X}$.
\end{lemma}
\begin{proof}
  Let $f \in I \subset k[X, U]$., then we need to prove that $\LT_{U}(f) \in \langle \LT_{U}(G) \rangle$. As $G$ is a Gröbner basis of $I$ in $k[X, U]$, we can write
  \[ f = \sum_{i=1}^{n} h_{i} g_{i} \]
  where $\LM(f) \geq \LM(g_{i}, h_{i})$ for each $i$. Since $X \gg U$ this implies $\LM_{U}(f) \geq \LM_{U}(g_{i}, h_{i})$ for each i. Because of the inequality $\LM_{U}(f) \geq \LM_{U}(g_{i} h_{i})$, the leading term of $f$ can only be produced by leading terms of $g_{i}h_{i}$. Now, the equation above still holds when we see $f, g_{1}, \dots, g_{n}, h_{1}, \dots, h_{n}$ as elements of $k[U][X]$. Let $J = \{i \in \{1, \dots, n\} \mid \LM_{U}(h_{i} g_{i}) = \LM_{U}(f)\}$. Since $\LT_{U}(g_{i} h_{i}) = \LT_{U}(g_{i})\LT_{U}(h_{i})$, we have
  \[\LT_{U}(f) = \sum_{i \in J} \LT_{U}(h_{i}) \LT_{U}(g_{i})\]
  so $\LT_{U}(f) \in \langle \LT_{U}(G) \rangle$, and so $G$ is a Gröbner basis of $I \subset k[U][X]$.
\end{proof}











\subsection{Pseudo-division}\label{sec:ps_div}
The division algorithm for polynomial rings over fields form the basis of most of the applications of Gröbner bases. One could even say that having a well-behaved remainder under the division algorithm is one of the primary motivations behind Gröbner bases. Pseudo-division will turn out to be equally important in the parametric setting. The idea is straight-forward. Suppose you want to divide $ax$ by $bx$ in $k[a, b][x]$. Since $b$ does not divide $a$, it seems we are stuck. But that is only due to the nature of the ring we work over (specifically that it's not a field) rather than the structure of the polynomials. Had $a$ and $b$ been any non-zero field elements, the division would be easy.

Pseudo-division is a way to overcome the fact, that our ground ring may not be a field. The idea is to allow ourselves to scale the polynomial by an appropriate scalar from the ground ring. In the case above, we can't divide $ax$ by $bx$, but we can divide $bax$ by $bx$ and get a remainder of zero. Pseudo-division in a restricted setting over $k[U][X]$ can be found in~\cite{IVA}. I am not aware that the rest of the results in this subsection appear in literature, but they have been extracted from proofs of other theorems in~\cite{grb_covers},~\cite{MONTES20101391}.

\begin{definition}[Pseudo-division]
  Let $f, f_{1}, f_{2}, \dots, f_{n}, g_{1}, g_{2}, \dots, g_{n}, r \in A[X]$ be polynomials and let $c \in A$. A \textit{pseudo-division of $f$ modulo $g_{1}, \dots, g_{n}$} is a relation
  \[cf = r + \sum_{i=1}^{n} f_{i}g_{i}\]
  where the following is satisfied:
  \begin{enumerate}
    \item $c = \prod_{j\in J} \LC(g_{j})^{p_{j}}$ for some subset $J \subset \{1, 2, \dots, n\}$ and powers $p_{j} \in \N$.
    \item $\LM(f_{i})\LM(g_{i}) \leq \LM(f)$ for all $i \in \{1, 2, \dots, n\}$.
    \item No term of $r$ is divisible by $\LM(g_{i})$ for any $i$.
    \item $\coef(f_{i}, m) \in \langle \coef(f, m') \mid m' \geq \LM(g_{i}m) \rangle$ for all $i \in \{1, 2, \dots, n\}$ and monomials $m$.
  \end{enumerate}
  We call $r$ a \textit{pseudo-remainder} and the $f_{i}$'s are called \textit{pseudo-quotients}.
\end{definition}


\begin{theorem}\label{thm:exi_pseudo}
  Let $f, g_{1}, g_{2}, \dots, g_{n} \in A[X]$ be polynomials. Then there exists a pseudo-division of $f$ modulo $g_{1}, \dots, g_{n}$.
\end{theorem}
\begin{proof}
  See the appendix, section \ref{app:pseudo}
\end{proof}

Pseudo-division allows us to overcome the problem, that our ground ring isn't a field, but we still have to be careful. If $b$ happened to be zero, then we cannot divide $ax$ by $bx$. Hence, we need some assumptions on the leading terms we divide with. The reason is that, after specialization, a pseudo-division turns into a regular multivariate division. Hence, parametric Gröbner bases and pseudo-division inherit all the nice properties Gröbner bases has under regular division.

\begin{lemma}\label{lem:ps_div_to_div}
  Let $f \in A[X]$, let $\{g_{1}, \dots, g_{n}\} \subset A[X]$, let $\sigma : A \to k_{1}$ be a ring homomorphism and let
  \[cf = r + \sum_{i=1}^{n}f_{i}g_{i}\]
  be a pseudo-division. Then
  \[\sigma(cf) = \sigma(r) + \sum_{i=1}^{n} \sigma(f_{i})\sigma(g_{i})\]
  satisfies $\LM(\sigma(f_{i} g_{i})) \leq \LM(\sigma(f))$. Furthermore, if $\sigma(\LC(g_{i})) \neq 0$ for all $i$, then either $\sigma(r) = 0$ or none of the terms of $\sigma(r)$ is divisible by any leading term of the $\sigma(g_{i})$'s.
\end{lemma}
\begin{proof}
  The first equality follows directly since $\sigma$ is a ring homomorphism. For the inequality $\LM(\sigma(f_{i} g_{i})) \leq \LM(\sigma(f))$, we have the fourth condition from pseudo-divisions: $\coef(f_{i}, m) \in \langle \coef(f, m') \mid m' \geq m \LM(g_{i}) \rangle$. Hence for any monomial $m$ with $m\LM(g_{i}) \geq \LM(\sigma(f))$, we have $\sigma(\coef(f_{i}, m \LM(g_{i}))) = 0$, since $\langle \coef(f, m) \mid m \geq \LM(\sigma(f)) \rangle = \langle 0 \rangle$.

  For the remainder, we have from pseudo-division that no term of $r$ is divisible by any $\LT(g_{i})$. Assuming $\sigma(\LC(g_{i})) \neq 0$ for all $i$, we have $\LM(g_{i}) = \LM(\sigma(g_{i}))$ for all $i$. Hence, no term of $\sigma(r)$ is divisible by any $\LM(\sigma(g_{i}))$, and since we work over a field, no term of $\sigma(r)$ is divisible by any $\LT(\sigma(g_{i}))$.
\end{proof}


Since remainders modulo a Gröbner basis $G$ are unique, we have that $f \in \langle G \rangle$ if and only if $f$ leaves a remainder of $0$ under division modulo $G$. We have the following analogous statement for parametric Gröbner bases and pseudo-division.

\begin{lemma}\label{lem:ps_rem_unique}
  Let $(Y, G)$ be a segment of a parametric Gröbner basis with $G = \{g_{1}, \dots, g_{n}\} \subset A[X]$, and assume that $\sigma_{\alpha}(\LC(g)) \neq 0$ for all $\alpha \in Y$ and $g \in G$. Let $f \in A[X]$ and let
  \[cf = r + \sum_{i=1}^{n} f_{i} g_{i}, \quad c'f = r' + \sum_{i=1}^{n} f'_{i} g_{i}\]
  be pseudo-divisions. Then
  \[\sigma_{\alpha}(r'c) = \sigma_{\alpha}(rc')\]
  for all specializations $\sigma_{\alpha}$ with $\alpha \in Y$. Furthermore, $\sigma_{\alpha}(f) \in \langle \sigma_{\alpha}(G) \rangle$ if and only if $\sigma_{\alpha}(r) = 0$.
\end{lemma}
\begin{proof}
  Consider
  \begin{align*}
    0 &= \sigma_{\alpha}(c' c f) - \sigma_{\alpha}(c' c f) \\
      &= \sigma_{\alpha}(cr') - \sigma_{\alpha}(c'r) + \sum_{i=1}^{n}\left(\sigma_{\alpha}(c f_{i}') - \sigma_{\alpha}(c' f_{i})\right)\sigma_{\alpha}(g_{i}).
  \end{align*}
  Since $\sum_{i=1}^{n}(\sigma_{\alpha}(c f_{i}') - \sigma_{\alpha}(c' f_{i}))\sigma_{\alpha}(g_{i}) \in \langle \sigma_{\alpha}(G) \rangle$, we must have $\sigma_{\alpha}(c' r) - \sigma_{\alpha}(c r') \in \langle \sigma_{\alpha}(G) \rangle$. If $\sigma_{\alpha}(c't) - \sigma_{\alpha}(cr') \neq 0$ then, since $\sigma_{\alpha}(G)$ is a Gröbner basis, that would imply that the leading term of $\sigma_{\alpha}(c' r) - \sigma_{\alpha}(c r')$ is divisible by some $\LM(\sigma_{\alpha}(g_{i}))$. But that would imply some term of either $\sigma_{\alpha}(c' r)$ or $\sigma_{\alpha}(c r')$ is divisible by that $\LM(\sigma_{\alpha}(g_{i}))$. Since $\LM(\sigma_{\alpha}(g_{i})) = \LM(g_{i})$ and no term of $r$ is divisible by any $\LM(g_{i})$ (by the properties of pseudo-division), this cannot happen. Hence, $\sigma_{\alpha}(c' r) - \sigma_{\alpha}(c r') = 0$.

  For the last assertion, if $\sigma_{\alpha}(r) = 0$, then clearly $\sigma_{\alpha}(f) \in \langle \sigma_{\alpha}(G) \rangle$ since $\sigma_{\alpha}(c)$ is invertible. On the other hand, if $\sigma_{\alpha}(f) \in \langle \sigma_{\alpha}(G) \rangle$, find a pseudo-reduction
  \[c f = r + \sum_{i=1}^{n} g_{i} f_{i}\]
  Then, since $\sigma_{\alpha}(c) \neq 0$ for any $\alpha \in Y$, by lemma~\ref{lem:ps_div_to_div} we get that
  \[\sigma_{\alpha}(c)\sigma_{\alpha}(f) = \sigma_{\alpha}(r) + \sum_{i=1}^{n} g_{i} f_{i}\]
  where no term of $\sigma_{\alpha}(r)$ is divisible by any leading term of $\sigma_{\alpha}(G)$. Since $\sigma_{\alpha}(G)$ is a Gröbner basis, and $\sigma_{\alpha}(c) \sigma_{\alpha}(f) \in \langle \sigma_{\alpha}(G) \rangle$, this implies $\sigma_{\alpha}(r) = 0$.
\end{proof}

\begin{example}\upshape
  Consider the comprehensive parametric Gröbner basis $G = \{ ax + y, bx + y, (a - b)y \} \subset \C[a, b, c][x, y]$ and the element $f = cxy + 1 \in \C[a, b, c][x, y]$. On the segment $\V(0) \setminus \V(ab(a-b))$, we can find a pseudo-reduction. First, reduce the term $cxy$ using $ax + y$:
  \[ (a)(cxy + 1) = (cy)(ax + y) - cy^{2} + a \]
  leaving a remainder of $\,-cy^{2} + a$. This remainder can be reduced using $(a - b)y$:
  \[(a-b)(a)(cxy + 1) = (a-b)(cy)(ax + y) - (cy)((a - b)y) + a^{2} - ab \]
  giving us the multiplier $c = a(a - b)$ and remainder $r = a^{2} - ab$.

  We could also have reduced the term $cxy$ using $(a - b)y$:
  \[(a-b)(cxy + 1) = (cx)((a-b)y) + a - b \]
  giving us a multiplier $c' = (a - b)$ and remainder $a - b$. We see that $c r' = (a-b)(a^{2} - ab) = (a - b)((a-b)a) = c' r$ in accordance with the theorem above.

  If the segment induces relations between leading coefficients, this might show up in the pseudo-remainders. Consider the segment $(\V(a - b), \{ax + 1, bx + 1\})$ and the polynomial $abx$. Here, we find two different pseudo-remainders:
  \begin{align*}
    abx = (b)(ax + 1) - b \\
    abx = (a)(bx + 1) - a
  \end{align*}
  In accordance with the theorem, we have that $\sigma_{\alpha}(a) = \sigma_{\alpha}(b)$ for all $\alpha \in \V(a - b)$. Do note, that for $\alpha \notin \V(a - b)$, $\sigma_{\alpha}(\{ax + 1, bx + 1\})$ is not a Gröbner basis, hence the theorem does not apply here.
\end{example}

Finally, to fully establish the correspondence between pseudo-division before specialization and division after specialization, we have the following: if we have a Gröbner basis $\sigma(G)$ after specialization, then any division modulo $G$ ``lifts'' to a pseudo-division before specialization. That is the content of this rather technical lemma.

\begin{lemma}\label{lem:div_to_ps_div}
  Let $G = \{g_{1}, \dots, g_{n}\} \subset A[X]$, let $f \in \langle G \rangle$ and let $\sigma : A \to K_{1}$ be a specialization such that $\sigma(\LC(g_{i})) \neq 0$ for all $i$. If $\,\sigma(f)$ reduces to zero mod $\sigma(g_{1}), \dots, \sigma(g_{n})$, then there is some $h \in \langle G \rangle$ and $\,b \in A \setminus \ker(\sigma)$ such that $\sigma(bf) = \sigma(h)$ and $\,\LM(h) = \LM(\sigma(f))$.
\end{lemma}
\begin{proof}
  The proof is by induction on the monomial order $<$ in $\LM(\sigma(f))$. The base case is $\sigma(f) = 0$, in which case we can choose $h = 0 \in \langle G \rangle$ and $b = 1$.

  Now, let $\sigma(f) \neq 0$ reduce to zero mod $\sigma(g_{1}), \dots, \sigma(g_{n})$, and suppose for every $f' \in \langle G \rangle$ with $\LM(\sigma(f')) < \LM(\sigma(f))$, there is some $h' \in \langle G \rangle$ and $b \in A \setminus \ker(\sigma)$ such that $\sigma(b'f') = \sigma(h')$ and $\LM(h') = \LM(\sigma(f'))$. Let
  \[\sigma(f) = \frac{\LC(\sigma(f))}{\LC(\sigma(g_{i}))} \sigma(g_{i}) + r\]
  with $\LM(r) < \LM(\sigma(g))$ be the first step of the reduction to zero. Since $\sigma(\LC(g_{i})) \neq 0$, we have that $\LC(\sigma(g_{i})) = \sigma(\LC(g_{i}))$. Then we have
  \begin{align*}
    \sigma(f) &= \frac{\LC(\sigma(f))}{\sigma(\LC(g_{i}))} \sigma(g_{i}) + r \iff \sigma(\LC(g_{i}) f) = \LC(\sigma(f)) \sigma(g_{i}) + \LC(g_{i})r
  \end{align*}
  Thus, $\LC(\sigma(f)) = \sigma(\coef(f, \LM(\sigma(f))))$, and so
  \[f' = \LC(g_{i})f - \coef(f, \LM(\sigma(f))) g_{i} \in \langle G \rangle\]
  satisfies either $\sigma(f') = 0$ or $\LM(\sigma(f')) < \LM(\sigma(f))$. In the first case, we've reached the base case, so we are done. Otherwise, $\sigma(f')$ is reducible to zero mod $\sigma(g_{1}), \dots, \sigma(g_{n})$ via the rest of the reduction of $\sigma(f)$, so we can find $b' \in A \setminus \ker(\sigma)$ and $h' \in \langle G \rangle$ such that $\LM(h') = \LM(\sigma(f'))$ and $\sigma(b' f') = \sigma(h)$. Then let $b = b' \LC(g_{i})$ and $h = h' + b' \coef(f, \LM(\sigma(f))) g_{i}$, so
  \begin{align*}
    \sigma(b f) &= \sigma(\LC(g_{i}) b' f) \\
           &= \sigma(b' (f' + \coef(f, \LM(\sigma(f))) g_{i})) \\
           &= \sigma(h' + b' \coef(f, \LM(\sigma(f))) g_{i}) \\
           &= \sigma(h)
  \end{align*}
  and $\LM(h) = \LM(g_{i}) = \LM(\sigma(g_{i})) = \LM(\sigma(f))$. Finally, since $b', \LC(g_{i}) \notin \ker(\sigma)$, we have $b \notin \ker(\sigma)$. This uses that $\ker(\sigma)$ is a prime ideal, which is true since its codomain is a field.
\end{proof}














\subsection{A criterion on stability}
In this section we will prove a criterion to decide when a Gröbner basis $G$ of an ideal $\langle F \rangle$ maps to a Gröbner basis $\sigma(G)$ of the ideal $\langle \sigma(F) \rangle$. This is theorem 3.1 in \cite{Kalkbrener}.

\begin{lemma}\label{lem:grb_iff_reduc_to_z}
  Let $G$ be a Gröbner basis of an ideal $\langle F \rangle \subset A[X]$ w.r.t. $<$, let $\sigma : A \to K$ be a ring homomorphism to a field $K$ and set $\,G_{\sigma} = \{g \in G \mid \sigma(\LC(g)) \neq 0\} = \{g_{1}, g_{2}, \dots, g_{l}\} \subset A[X]$. Then $\sigma(G_{\sigma})$ is a Gröbner basis of the ideal $\langle \sigma(F) \rangle$ w.r.t. $<_{X}$ if and only if $\sigma(g)$ is reducible to 0 modulo $\sigma(G_{\sigma})$ for every $g \in G$.
\end{lemma}
\begin{proof}
  First, we prove ``$\Longrightarrow$'': Suppose $\sigma(G_{\sigma})$ is a Gröbner basis of $\langle \sigma(F) \rangle$. Since $\sigma(g) \in \langle \sigma(F) \rangle$, we get that $\sigma(g)$ reduces to zero modulo any Gröbner basis of $\langle \sigma(F) \rangle$ by theorem~\ref{thm:grb}, in particular $\sigma(G_{\sigma})$.

  Next, we prove ``$\Longleftarrow$'': Assume that $\sigma(g)$ is reducible to 0 modulo $G_{\sigma}$ for every $g \in G$ and let $f \in \langle F \rangle$ such that $\sigma(f) \neq 0$. It's enough to show that
  \[\exists\, h \in \langle F \rangle : \sigma(\LC(h)) \neq 0 \land \LM(h) \mid \LM(\sigma(f)).\]
  Indeed, since $G$ is a Gröbner basis of $\langle F \rangle$, that implies there is some $g \in G$ such that $\LM(g) \mid \LM(h)$ and $\LM(h) = \LM(\sigma(h)) \mid \LM(\sigma(f))$. Furthermore, since $\LC(g) \mid \LC(h)$ and $\sigma(\LC(h)) \neq 0$, we have that $\sigma(\LC(g)) \neq 0$, hence $\LT(\sigma(g)) \mid \LT(\sigma(f))$. Thus, if the above holds for any $f$, then $\sigma(G)$ is a Gröbner basis of $\langle \sigma(F) \rangle$. We prove this claim by induction on $<_{X}$.

  The base case is when $\LM(f) = 1$, which means $f \in A$. Since we assumed $\sigma(f) \neq 0$, we have $\LM(\sigma(f)) = \LM(f)$ and $\sigma(\LC(f)) \neq 0$.

  Now, the induction step. Let $f \in \langle F \rangle$ with $\sigma(\LC(f)) \neq 0$ and assume that every $f' \in \langle F \rangle$ with $\LM(f') < \LM(f)$ we have $\exists\, h \in \langle F \rangle : \sigma(\LC(h)) \neq 0 \land \LM(h) \mid \LM(\sigma(f'))$. If $\sigma(\LC(f)) \neq 0$, we can simply use $h = f$, so consider the case when $\sigma(\LC(f)) = 0$. If there is some $\sigma(g) \in G_{\sigma}$ such that $\LM(g) \mid \LM(f)$, then we can reduce $f$ by $g$ to get $f' = \LC(g) \cdot f - \LC(f) \cdot \frac{\LM(f)}{\LM(g)}g$. Then $\LM(\sigma(f')) = \LM(\sigma(f))$ since $\sigma(\LC(f)) = 0$ and $\LM(f') < \LM(f)$, so the assertion holds by the induction hypothesis.

  On the other hand, if there is no such $\sigma(g) \in G_{\sigma}$, then we must have some $g \in G \setminus G_{\sigma}$ such that $\LM(g) \mid \LM(f)$. However, we can't simply reduce by $g$, since the factor $\LC(g)$ is zero under $\sigma$. Instead, we can find a subset with $\{g_{j_{1}}, \dots, g_{j_{r}}\} \subset G \setminus G_{\alpha}$ such that
  \[\LT(f) = \sum_{i = 1}^{r} c_{i} \frac{\LM(f)}{\LM(g_{j_{i}})} \LT(g_{j_{i}}).\]
  Since each of the $\sigma(g_{j_{i}})$ are reducible to 0 modulo $G_{\sigma}$, by lemma~\ref{lem:div_to_ps_div} we can find some $h_{i} \in \langle F \rangle$ and $b_{i} \in A \setminus \ker(\sigma)$ such that $\sigma(b_{i} g_{j_{i}}) = \sigma(h_{i})$ and $\LM(\sigma(h_{i})) = \LM(\sigma(g_{j_{i}})) > \LM(g_{j_{i}})$ for each $i \in \{1, \dots, r\}$. Let $b = \prod_{i = 1}^{r} b_{i}$, which is non-zero, then
  \[f' = b f - \sum_{i = 1}^{r} c_{i} \frac{b}{b_{i}} \frac{\LM(f)}{\LM(g_{j_{i}})}(b_{i}g_{j_{i}} - h_{i})\]
  is a new polynomial with
  \[\sigma(f') = \sigma(b f) - \sum_{i = 1}^{r} \sigma\left(c_{i} \frac{b}{b_{i}} \frac{\LM(f)}{\LM(g_{j_{i}})}\right) (\sigma(b_{i} g_{j_{i}}) - \sigma(h_{i})) = \sigma(b f)\]
  hence $\LM(\sigma(f')) = \LM(\sigma(f))$ but also $\LM(f') < \LM(f)$ since $\LM(g_{j_{i}}) > \LM(h_{i})$. Thus the conclusion follows from the induction hypothesis.
\end{proof}

\begin{corollary}\label{cor:grb_if_nmap_to_z}
  Let $G$ be a Gröbner basis of an ideal $\langle F \rangle \subset A[X]$ w.r.t.\ $<$ and let $\sigma : A \to K$ be a ring homomorphism to a field $K$. If $\,\sigma(\LC(g)) \neq 0$ for all $g \in G$, then $\sigma(G)$ is a Gröbner basis of $\,\langle \sigma(F) \rangle$.
\end{corollary}
\begin{proof}
  Let $G_{\sigma} = \{g \in G \mid \sigma(\LC(g)) \neq 0\}$. By assumption, $G_{\sigma} = G$, so lemma~\ref{lem:grb_iff_reduc_to_z} applies immediately.
\end{proof}


We will use a consequence of this lemma, which uses a test that is much easier to check. We use the above lemma with $A = k[U]$.

\begin{lemma}\label{lem:grb_if_nmap_to_z}
  Let $G = \{g_{1}, g_{2}, \dots, g_{k}\}$ be a Gröbner basis of an ideal $\langle F \rangle$ in $k[X, U]$ w.r.t $<$ and let $\alpha \in k_{1}^{|U|}$. If $\sigma_{\alpha}(\LC_{U}(g)) \neq 0$ for each $g \in G \setminus k[U]$, then $\sigma_{\alpha}(G)$ is a Gröbner basis of $\langle \sigma_{\alpha}(F) \rangle$.
\end{lemma}
\begin{proof}
  First note that since $X^{v_{1}} > U^{v_{2}}$, any Gröbner basis of $\langle F \rangle \subset k[X, U]$ is also a Gröbner basis of $\langle F \rangle \subset k[U][X]$ by lemma~\ref{lem:block_order}. Let $G_{\alpha} = \{\sigma_{\alpha}(g) \mid \sigma_{\alpha}(\LC_{U}(g)) \neq 0\}$. If there is any $g \in G$, such that $\sigma_{\alpha}(g) \in k_{1} \setminus \{0\}$, then $g \in G \cap k[U]$ since $\sigma_{\alpha}(\LC_{U}(g)) \neq 0$ for all $g \in G \setminus K[U]$. Furthermore, since $g \in \langle F \rangle$, we get that $\langle \sigma_{\alpha}(F) \rangle = k_{1}[X]$ and $\sigma_{\alpha}(G)$ is a Gröbner basis as it contains a unit.

  If there is no such $g$, then $\alpha \in \V(G \cap k[U])$. Take any $g \in G$. If $\sigma_{\alpha}(g) \in G_{\alpha}$, then $\sigma_{\alpha}(g)$ is reducible to $0$ modulo $G_{\alpha}$, since it's leading term is divisible by its own leading term.

  On the other hand, if $\sigma_{\alpha}(g) \notin G_{\alpha}$, then we must have $g \in G \cap k[U]$. Since $\alpha \in \V(G \cap k[U])$ then $\sigma_{\alpha}(g) = 0$, so is immediately reducible to zero. Thus $\sigma_{\alpha}(G)$ is a Gröbner basis of $\langle \sigma_{\alpha}(F) \rangle$ by lemma~\ref{lem:grb_iff_reduc_to_z}.
\end{proof}

With lemma~\ref{lem:grb_if_nmap_to_z} in mind, we can start constructing Gröbner systems. Let $G$ be the reduced Gröbner basis of an ideal $\langle F \rangle \subset k[X, U]$, and let $H = \{\LC_{U}(g) \mid g \in G \}$. Then $\left(\V(0) \setminus \bigcup_{h \in H} \V(h), G\right)$ is a segment of a Gröbner system. Thus, to make a Gröbner system, we need to find segments covering $\bigcup_{h \in H} \V(h) = \V(\lcm(H))$. Here, $\lcm(H)$ is the least common multiple of the elements in $H$. As we will see later, we can find a Gröbner basis under the condition $\V(S)$ for some $S \subset k[U]$, by computing a Gröbner basis of $\langle F \cup S \rangle$ and remove everything in $\langle S \rangle$.

\begin{example}\upshape
  Consider the ideal $I = \langle ax + cy, bx + dy \rangle \subset \C[a, b, c, d][x, y]$. The reduced Gröbner basis for $I$ w.r.t.\ the lexicographic order with $x > y$ is $G = \{ax + cy, bx + dy, (ad - bc)y\}$. The leading coefficients are $\{a, b, ad - bc\}$, so for any specialization with $\sigma(a), \sigma(b), \sigma(ad - bc) \neq 0$, this specializes to a Gröbner basis. This is equivalent to requiring that $\sigma(ab(ad-bc)) \neq 0$.

  Now, we need to produce Gröbner systems covering the rest. If $\sigma(a) = 0$, then the ideal becomes $\langle cy, bx + dy, bcy \rangle$ with leading coefficients $\{c, b, bc\}$. Since $\sigma(bc) \neq 0 \iff \sigma(b) \neq 0 \land \sigma(c) \neq 0$ and we can reduce $bcy$ using $cy$, we have that $\{cy, bx + dy\}$ is a Gröbner basis of the segment $\V(a) \setminus \V(bc)$.

  Moving on to the segment where $\sigma(a) = \sigma(b) = 0$, we're left with the generating set $\{cy, dy\}$, which is a Gröbner basis as long as $\sigma(c), \sigma(d) \neq 0$. It remains unchanged if only one of them vanishes, but when we add $\sigma(c) = \sigma(d) = 0$, we're left with the zero ideal.

  Backtracking, we consider the case when $\sigma(a) = \sigma(c) = 0$. In this case the generating set is $\{bx + dy\}$ with leading coefficient $b$. Hence $\{bx + dy\}$ is a Gröbner basis when $\sigma(b) \neq 0$. Setting $\sigma(a) = \sigma(b) = \sigma(c) = 0$, we get a segment we have already computed. Hence, we have found the following partial Gröbner system. The indentations are meant to represent the recursive nature of the computation.

  \begin{align*}
    \{&(\V(0) \setminus \V(ab(ad-bc)),& &\{ax + cy, bx + dy, (ad-bc)y\}) \\
      &\;\; (\V(a) \setminus \V(bc),& &\{cy, bx + dy\}) \\
      &\;\; \;\;(\V(a, b) \setminus \V(cd),& &\{cy, dy\}) \\
      &\;\; \;\; \;\;(\V(a, b, c) \setminus \V(d),& &\{dy\}) \\
      &\;\; \;\; \;\; \;\;(\V(a, b, c, d) \setminus \V(1),& &\{0\}) \\
      &\;\; \;\; \;\;(\V(a, b, d) \setminus \V(c),& &\{cy\})\\
      &\;\; \;\;(\V(a, c) \setminus \V(b), &&\{bc + dy\})\}
  \end{align*}

  A similar pattern emerges when we start by setting $\sigma(b) = 0$, which the reader is invited to work out themselves. When we set $\sigma(ad - bc) = 0$, we're left with the leading coefficients $\{a, b\}$, and when they do not vanish, we get the Gröbner basis $\{ax + cy, bx + dy\}$.

  Setting $\sigma(ad - bc) = \sigma(a) = 0$, we get the generating set $\{cy, bx + dy\}$ with leading coefficients $\{b, c\}$. Hence $\{cy, bx + dy\}$ is a Gröbner basis of the segment $\V(ad - bc, a) \setminus \V(bc)$. However, since $\V(ad - bc, a) = \V(a, bc)$, we see that this segment is actually empty.

  Similarly, when we set $\sigma(ad - bc) = \sigma(b) = 0$, we get the leading coefficients $\{a, d\}$, hence the segment $\V(ad - bc, b) \setminus \V(ad)$. However, since $\V(ad - bc, b) = \V(ad, b)$, this segment is also empty. Thus, we have found a comprehensive Gröbner system for $I$.

  It should be noted, that in this example we did not have to recompute the Gröbner basis because the Gröbner basis remained a Gröbner basis after specialization. If we take the example of $J = \langle ux + y, y^{2} + 1 \rangle \subset \C[u][x, y]$, the situation is different. The generators form a Gröbner basis, with leading coefficients $\{u, 1\}$. Hence, $\{ux + y, y^{2} + 1\}$ is a Gröbner basis on the segment $\V(0) \setminus \V(u)$. However, when we set $\sigma(u) = 0$, the remaining generating set is $\{y, y^{2} + 1\}$, which is not a Gröbner basis. Instead, we compute the Gröbner basis of this segment to be $\{1\}$. Since $\sigma(1) = 0$ is never satisfied, we have the following Gröbner system for $J$:
  \[\{\V(0) \setminus \V(u), \{ux + y, y^{2} + 1\}, \quad (\V(u) \setminus \V(1), \{1\})\}\]
\end{example}