Subalgebra analogue of Standard bases for ideals in $K[[t_{1}, t_{2}, \ldots, t_{m}]][x_{1}, x_{2}, \ldots, x_{n}]$

1.   Introduction, notation and definition

For the study of the structure of ideals in a polynomial ring $K[x_{1}, x_{2}, ..., x_{n}]$ over a field $K$, Bruno Buchberger presented a concept of Gröbner bases with respect to global monomial orderings (Indeterminates $x_{i}$ are greater than 1, $\forall i$) ^[8]. In ^[8], Buchberger gave an algorithm called Buchberger Algorithm For the computation of Gröbner bases, based on the multivariate division algorithm (Normal form algorithm). The concept of Gröbner bases played an important role in the field of computational algebraic geometry and computational commutative algebra. Moreover, this concept was introduced for polynomial ring over a noetherian integral domain ^[10]. This concept is extended for the localization of $K[x_{1}, x_{2}, ..., x_{n}]$ in ^[1], and termed Standard bases. The idea of Standard bases is tied with local monomial orderings (where indeterminates $x_{i}$ are less than 1, $\forall i$). They modified the idea of Normal form algorithm with respect to local monomial ordering to ensure the termination. It is an ecart based algorithm (for details, see Chapter 1 of ^[1]) known as Mora's algorithm (weak normal form algorithm) ^[3]. Furthermore, the study was made for Standard bases of ideals in a formal power series ring $K[[t_{1}, t_{2}, ..., t_{n}]]$ in ^[2] with respect to local monomial orderings. Later, a theory of Standard bases for ideals in a more general mixed ordered indeterminates ring $K[[t_{1}, t_{2}, \ldots, t_{m}]] [x_{1}, x_{2}, ..., x_{n}]$ was introduced with respect to a monomial ordering local on $t$ indeterminates ^[5]. The concept of Standard bases in $K[x_{1}, x_{2}, ..., x_{n}]$ ($K[[t_{1}, t_{2}, \ldots, t_{m}]]$) is a special case of Standard bases in $K[[t_{1}, t_{2}, \ldots, t_{m}]] [x_{1}, x_{2}, ..., x_{n}]$ for $m = 0$ ($n = 0$).

Subsequent to the concept of Gröbner bases, a concept of bases for subalgebras in $K[x_{1}, x_{2},$ $...,$ $x_{n}]$ was introduced by Robianno and Sweedler termed as Sagbi bases ^[4]. Similar to Gröbner bases, this concept is also tied with global monomial orderings. The algorithm for the construction of Sagbi bases, is based on Sagbi Normal form algorithm which is the subalgebra analogue of Normal form algorithm of ideals. The idea of Sagbi bases has been generalized in polynomial ring over a noetherian integral domain ^[7]. Later, the concept of Standard bases was introduced for complete subalgebras in the formal power series ring $K[[x_{1}, x_{2}, ..., x_{n}]]$ with respect to local monomial orderings ^[2]. The theory of Sagbi bases is extended to the localization of $K[x_{1}, x_{2}, ..., x_{n}]$, called Sasbi bases ¹ in ^[6]. As with Standard bases, this idea is also tied with local monomial orderings. They also presented the subalgebra version of Mora's algorithm, termed as Sasbi Normal form, which is also an ecart based algorithm.

¹Subalgebra Analogue of Standard bases for Ideals.

Similar to the case of Standard bases for ideals ^[5], it is natural to ask for a theory of Standard bases for subalgebras in $K[[t_{1}, t_{2}, \ldots, t_{m}]][x_{1}, x_{2}, ..., x_{n}]$. In this paper, we present the subalgebra analogue of Standard bases for ideals in $K[[t_{1}, t_{2}, \ldots, t_{m}]]$- $[x_{1}, x_{2}, ..., x_{n}]$, termed as "Subalgebra Standard bases". Similar to the Standard bases, we develop the idea of these bases with respect to a monomial ordering local on $t$ indeterminates. As with Sagbi bases, these bases could be infinite for finitely generated subalgebras (see Example 3.6). The concept of Sagbi bases (assume $x_{i}\succ1$, $1\leq i \leq n$) and Sasbi bases (assume $x_{i}\prec 1$, $1\leq i \leq n$) for subalgebras in $K[x_{1}, x_{2}, ..., x_{n}]$ is a special case of Subalgebra Standard bases in $K[[t_{1}, t_{2}, \ldots, t_{m}]][x_{1}, x_{2}, ..., x_{n}]$ for $m = 0$. Moreover, for the case $n = 0$, a Subalgebra Standard basis for subalgebra $K[G]$ ($G$ is finite, see Definition 1.3) in $K[[t_{1}, t_{2}, \ldots, t_{m}]] [x_{1}, x_{2}, ..., x_{n}]$ is a Standard basis for complete subalgebra $K[[G]]$ (see Theorem 3.2 in ^[6]). The theory of Subalgebra Standard bases (tied with mixed orderings), which we have introduced in this paper, unifies the previous theories (tied with global and local orderings). This theory is more general as previous theories could be seen as its special cases. It could also be used to solve problems like sublagebra membership problem in a mixed ring $K[[t_{1}, t_{2}, \ldots, t_{m}]] [x_{1}, x_{2}, ..., x_{n}]$.

The structure of this paper is as follows. In the start, we give basic notations and terminologies and introduce the concept of Subalgebra Standard bases (Definition 1.7). The idea of normal form is very important to characterize subalgebra bases algorithmically. For this purpose, in Section 2, first we present an algorithm (Algorithm 2.3) to compute subalgebra homogenenous normal form for $x$-homogeneous ² inputs. Due to $x$-homogeneity, the sequence of terms (obtained after each reduction) would have same $x$-degree and it would be convergent with respect to $< \underline{t} >$-adic topology. Based on this algorithm, we give a weak subalgebra normal form algorithm (Algorithm 2.5), which is one of the key ingredients for the construction of Subalgebra Standard Bases. The weak subalgebra normal form can be seen as a combination of Sagbi normal form and Sasbi normal form. For the termination of this algorithm, for input $G \subset S[x_{1}, x_{2}, \ldots, x_{n}]$ we assume that an $x$-homogeneous $S$-subalgebra $S[G^{*}]$ admits a finite Sagbi basis, where $S = K[[t_{1}, t_{2}, \ldots, t_{m}]]$. Then, finally in Section 3, we provide an algorithm to compute Subalgebra Standard bases with the support of algebraic relations between leading terms of elements of the given input.

²We need homogeneity only in terms of indeterminates $x_{i}'s$.

For simplicity, let $\underline{x} = (x_{1}, x_{2}, ..., x_{n})$ and $\underline{t} = (t_{1}, t_{2}, \ldots, t_{m})$. Let $R: = K[[\underline{t}]][\underline{x}]$ denotes the polynomial ring in indeterminates $\underline{x}$ with coefficients in the formal power series ring $K[[\underline{t}]]$. Moreover, we use the notation $\underline{t}^{\alpha}$ for $t_{1}^{\alpha_{1}}t_{2}^{\alpha_{2}}...t_{m}^{\alpha_{m}}$ and $\underline{x}^{\beta}$ for $x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}...x_{n}^{\beta_{n}}$ with $\alpha = (\alpha_{1}, \alpha_{2}, \ldots, \alpha_{m}) \in \mathbb{N}^{m}$ and $\beta = (\beta_{1}, \beta_{2}, \ldots, \beta_{n}) \in \mathbb{N}^{n}$.

Definition 1.1. A monomial ordering on the set of monomials Mon of $R$ is a total ordering $\succ$ on the same set such that for all $\alpha, \alpha^{'}, \alpha^{"} \in \mathbb{N}^{m}$ and $\beta, \beta^{'}, \beta^{"} \in \mathbb{N}^{n}$

We say a monomial ordering $\succ$ $\underline{t}$-local if its restriction to the set of monomials of $K[[\underline{t}]]$ is local.

We call a $\underline{t}$-local monomial ordering a $\underline{t}$-local weighted degree ordering if there is a weight vector $w = (w_{1}, w_{2}, ..., w_{m+n}) \in \mathbb{R}^{m}_{\leq 0}\times \mathbb{R}^{n}$ such that for all $\alpha, \alpha^{'} \in \mathbb{N}^{m}$ and $\beta, \beta^{'}, \in \mathbb{N}^{n}$, the scalar product appears as:

Definition 1.2. Let $\succ$ be a $\underline{t}$-local monomial ordering. A non-zero element $f$ of $R$ can be viewed as:

with $c_{\alpha, \beta} \in K$, $|\alpha| = \alpha_{1}+\alpha_{2}+...+\alpha_{m}$ and $|\beta| = \beta_{1}+\beta_{2}+...+\beta_{n}$. We call $\mathcal{M}_{f}: = \{\underline{t}^{\alpha}\underline{x}^{\beta}| c_{\alpha, \beta}\neq 0\}$ the set of monomials of $f$ and $\mathcal{T}_{f}: = \{ c_{\alpha, \beta} \underline{t}^{\alpha}\underline{x}^{\beta}| c_{\alpha, \beta}\neq 0\}$ the set of terms of $f$. Moreover, $lm(f): = max\{\underline{t}^{\alpha}\underline{x}^{\beta}|\underline{t}^{\alpha}\underline{x}^{\beta} \in \mathcal{M}_{f}\}$, the coefficient $c_{\alpha, \beta}$ is then leading coefficient $lc(f)$, $lt(f) = lc(f)lm(f)$ its leading term and $tail(f) = f-lt(f)$ its tail.

Now, we define a $K$-subalgebra ³ of $R$ and its leading subalgebra.

³Throughout this paper, we assume subalgebras as $K$-subalgebras unless mentioned otherwise.

Definition 1.3. Let $\succ$ be a $\underline{t}$-local monomial ordering on $R$ and a subset $G\subseteq R$, then $A = K[G]$ is a subalgebra of $R$ generated by $G$. Naturally, the elements of $A$ could be viewed as polynomials in terms of elements of $G$ with coefficients in $K$. We define the leading subalgebra of $G$ generated by $LM(G) = \{lm(g)\mid g \in G \}$ as:

Remark 1.4. If $G = \{ g_{1}, g_{2}, ..., g_{k}\}\subset R$, then $A = K[G]$ is called a finitely generated subalgebra. Throughout this paper, we work with finitely generated subalgebras.

Definition 1.5. Let $G = \{g_{1}, g_{2}, ..., g_{k}\}$ be a subset of $R$. For $a = (a_{1}, a_{2}, \ldots\, a_{k}) \in \mathbb{N}^{k}$, we call a power product of $g_{i}'s$ a $G$-monomial, i.e., $G^{a} = g_{1}^{a_{1}}g_{1}^{a_{2}}\ldots g_{k}^{a_{k}}$

Remark 1.6. Any element $f$ of subalgebra $K[G]$ could be viewed as a finite sum in terms of $G$-monomial as $f = {\sum\limits_{i}} c_{i}G^{a_{i}}$ with $c_{i} \in K$.

Now, we define a Subalgebra Standard basis for a subalgebra of $R$ as given in Definition 1.7.

Definition 1.7. Let $\succ$ be a $\underline{t}$-local monomial ordering and $A$ be a subalgebra of $R$. A Standard basis of $A$ is a subset $G\subseteq A$ such that $in(G) = in(A)$ i.e. for any $f\in A$, $lm(f)\in in(G)$.

Note that $in(G)$ need not be equal to $in(A)$, i.e., not every generating set of the subalgebra is a Subalgebra Standard basis as we can see from the following example.

Example 1.8. Let $A = K[G]$ be a subalgebra of $K[[t_{1}, t_{2}]][x_{1}, x_{2}]$ where $G$ contains three elements $g_{1} = x_{1}^2+x_{1}^4$, $g_{2} = x_{1}^2+x_{1}^6t_{2}$ and $g_{3} = x_{2}+t_{1}+t_{1}^2+t_{1}^3\ldots$. We have a $\underline{t}$-local ordering $\succ$ on $Mon(K[[t_{1}, t_{2}]][x_{1}, x_{2}])$ such that $x_{2}\succ 1\succ x_{1}\succ t_{1}\succ t_{2}$.

Choose $f = -x_{1}^6t_{2}-2x_{1}^8t_{2}-x_{1}^{12}t_{2}^2$ $( = g_{1}-g_{2}-g_{2}^{2})$ $\in A$. We can see that $lm(f) = x_{1}^6t_{2}\notin in(G)$ and hence $G$ is not a Subalgebra Standard basis of $A$.

Later, for the weak subalgebra normal form algorithm, we need the concept of multiplicative set and ecart defined as follows:

Definition 1.9. Let $\succ$ be a $\underline{t}$-local monomial ordering and $A$ be a subalgebra of $R$, then we define the multiplicative set for $A$ as:

Definition 1.10. The element $f \in R$ is said to be $\underline{x}$-homogeneous of $\underline{x}$-degree $d$ if every term of $f$ has the same $\underline{x}$-degree $d$, denoted as $\deg_{\underline{x}}(f) = d$. The ecart of any element $f \in R$ is defined as

with respect to a $\underline{t}$-local monomial ordering.

Now, we present the concept of homogenization and dehomogenization of elements of $R$ in only $\underline{x}$ indeterminates with respect to another indeterminate $x_{0}$.

Definition 1.11. Let $f \in R,$ $\underline{x}^{*} = (\underline{x}, x_{0})$ and $R^{*} = R[x_{0}]$

a) We define the homogenization $f^{*}$ of $f = {\sum\limits_{\mid\beta\mid = 0}^{d}}$ ${\sum\limits_{\mid\alpha\mid = 0}^{\infty}}c_{\alpha, \beta}\underline{t}^{\alpha}\underline{x}^{\beta}$ as:

with $\mid \beta \mid+\gamma = d$ for every term of $f^{*}$ and we define dehomogenization of $F \in R^{*}$ as:

b) Let $\succ$ be a $\underline{t}$-local monomial ordering. We define its homogenization $\succ^{*}$ which is also a $\underline{t}$-local monomial ordering, as:

Now, we present some results on the relationship between elements and their homogenization and dehomogenization.

Lemma 1.12. Let $f \in R$ and $G \subset R$ and an $\underline{x}$-homogeneous element $F \in R^{*}$

(a) $f = (f^{*})_{*}.$

(b) $F = (F_{*})^{*} x_{0}^{deg_{\underline{x}^{*}}(F)-deg_{\underline{x}^{*}}((F_{*})^{*})}$.

(c) $lm(f^{*}) = x_{0}^{ecart(f)}lm(f)$.

(d) $lm(F) = x_{0}^{ecart{(F_{*})}+deg_{\underline{x}^{*}}(F)-deg_{\underline{x}}(F_{*})}lm(F_{*})$.

(e) $lm(f^{*}) = lm({\sum\limits_{i}} c_{i}(G^{a_{i}})^{*})x_{0}^{e}$ for some $e\geq 0$ $\Leftrightarrow lm(f) = lm({\sum\limits_{i}} c_{i}G^{a_{i}})\wedge ecart({\sum\limits_{i}} c_{i}G^{a_{i}})\leq ecart(f)$.

Proof. The proof of Parts (a)–(c) would be similar to the proof holds for polynomials (see ^[9]). Part (d) can be obtained by replacing $f$ by $F_{*}$ and $f^{*}$ by $F$ in Part(c). For Part(e), first assume

If $e = 0$, then the result is obvious. For $e > 0$, from Eq (1.1), we can assume $deg_{\underline{x}^{*}}(lm(f^{*})) = deg_{\underline{x}^{*}}(lm({\sum\limits_{i}} c_{i}(G^{a_{i}})^{*})x_{0}^{e}) = d$. Moreover, by dehomogenizing both sides of Eq (1.1), we get $lm(f) = lm({\sum\limits_{i}} c_{i}G^{a_{i}})$ which implies that the $\underline{x}$-degrees of both sides are the same.

Now, consider $ecart({\sum\limits_{i}} c_{i}G^{a_{i}})-ecart(f)$

= $deg_{\underline{x}}({\sum\limits_{i}} c_{i}G^{a_{i}})-deg_{\underline{x}}(lm({\sum\limits_{i}} c_{i}G^{a_{i}}))-deg_{\underline{x}}(f)+deg_{\underline{x}}(lm(f))$

= $deg_{\underline{x}^{*}}({\sum\limits_{i}} c_{i}(G^{a_{i}})^{*})-deg_{\underline{x}^{*}}(f^{*})$

= $deg_{\underline{x}^{*}}(lm({\sum\limits_{i}} c_{i}(G^{a_{i}})^{*}))-deg_{\underline{x}^{*}}(lm(f^{*}))$

= $deg_{\underline{x}^{*}}(lm({\sum\limits_{i}} c_{i}(G^{a_{i}})^{*}))-deg_{\underline{x}^{*}}(lm({\sum\limits_{i}} c_{i}(G^{a_{i}})^{*}))x_{0}^{e}$

= $(d-e)-d = -e < 0$.

For the converse, let $G$ be the set such that $e = ecart(f)-ecart({\sum\limits_{i}} c_{i}G^{a_{i}})\geq 0$. From our assumption $lm(f) = lm({\sum\limits_{i}} c_{i}G^{a_{i}})$ and Part (c) above, we get our required result.

To present the theory of Subalgebra Standard bases, we need a subalgebra reduction process (discussed in section 2). Now, we list the conditions the subalgebra reduction with its normal form may satisfy.

Definition 1.13. Let $\succ$ be a $\underline{t}$-local monomial ordering. Suppose we have $f$, $r$ $\in R$ and $G \subset R$, such that

The above representation satisfies the following conditions (with respect to $\succ$):

Indeterminate conditions:

Determinate conditions:

Homogeneous eterminate condition:

With any of the conditions above, we call $r$ a subalgebra normal form of $f$ and if this is zero, we call such representation a Subalgebra Standard representation.

Definition 1.14. Let $\succ$ be a $\underline{t}$-local monomial ordering and $u \in S_{\succ} = \{ f \in R \mid lm(f) = 1\}$. Then under any of the above conditions, we call a subalgebra normal form $r$ of $u \cdot f$ a weak subalgebra normal form of $f$ with respect to $G\subset R$.

Note that (DC2)$\Rightarrow$(IC2), (DC1)+(IC2)$\Rightarrow$(IC1) and (DC1)+(DC2)$\Rightarrow$ (IC1). The first implication is obvious. Let us illustrate some other implications through examples:

Example 1.15. Let $g_{1} = x^2+y-x$, $g_{2} = xy+yt-x-xt^{2}-xt^3-\ldots$ and $f = x^4+y^2+2x^2y-xy-2x^3+x^2-x+y^3+yt+t-xt^2-xt^3-\ldots$ be elements of $K[[t]][x, y]$. We have $t$-local lexicographical ordering $\succ_{t-lex}$ on $K[[t]][x, y]$ with $x\succ y\succ 1\succ t$.

Here $f = (g_{1}^2+g_{2})+r$ where $r = y^3+t$. We can see that this representation satisfies (DC1) ($x^4 \notin K[xy]$ and $xy \notin K[x^4]$) and (IC2) ($y^3 \notin K[x^2, xy]$) which implies there is no connection of $lm(r)( = y^3)$ with $lm(g_{1}^2)( = x^4)$ and $lm(g_{2})( = xy)$. Moreover, there is no connection of leading G-power products $x^4$ and $xy$ with each other and so $lm(f) = x^4$ satisfies (IC1). Similarly this representation satisfies (DC2) (Any term of $r$; $y^3$ and $t \notin K[x^2, xy]$) which implies (IC1) clearly when we combine (DC2) with (DC1).

2.   Subalgebra reduction process

In this section, we discuss the reduction process in subalgebras of $R$ to compute subalgebra normal form with respect to $\underline{t}$-local monomial orderings. For an $\underline{x}$-homogeneous element in $R$, first, we present a theorem that shows the existence of subalgebra homogeneous normal form with respect to set of $\underline{x}$-homogeneous elements in $R$ along with an algorithm for its computation. Second, we present an algorithm to compute weak subalgebra normal form of any element in $R$. This algorithm is a key ingredient for the computation of Subalgebra Standard bases in $R$.

Theorem 2.1. Let $f \in R$ and $G = \{g_{1}, g_{2}, \ldots, g_{k}\} \subset R$ be $\underline{x}$-homogeneous, then there exists uniquely determined $r \in R$ such that

satisfying (DC1), (DC2) and (HDC).

Proof. We set $f_{0} = f$ and for $v > 0$ we define recursively

where $r_{v} \in R$ is such that

satisfies (DC1), (DC2) and (HDC). The above representation of $f_{v-1}$ used in 2.1 exists since power products of $lt(g_{i}'s)$ are involved in this representation.

Now, we want to show that the sequences $(f_{v})_{v = 0}^{\infty}$ and $(r_{v})_{v = 1}^{\infty}$ converge to zero in the $< \underline{t} >$-adic topology. By Lemma(2.3)^[5], there exists a $\underline{t}$-local weighted degree ordering $\succ_{w}$ with weight $w \in \mathbb{Z}_{ < 0}\times \mathbb{Z}^{n}$ for which $lm(g_{i}) = lm(g_{i})_{\succ_w}$ (leading monomials with respect to $\succ_{w}$) for all $i$, so after replacing $\succ$ by $\succ_{w}$, we get the same sequences $(f_{v})_{v = 0}^{\infty}$, $(r_{v})_{v = 1}^{\infty}$ since only power products of $lm(g_{i}'s)$ are involved in their construction. In particular, (2.2) will satisfy (DC1), (DC2) and (HDC) with respect to $\succ_{w}$. Due to (HDC), $f_{v}$ is again $\underline{x}$-homogeneous of $\underline{x}$-degree equal to $f_{v-1}$. Moreover, (DC1)+(DC2)$\Rightarrow$ (IC1), so for all $i$

From Lemma 2.4^[5], $(f_{v})_{v = 0}^{\infty}$ converges to zero in the $< \underline{t} >$-adic topology and hence by construction $(r_{v})_{v = 1}^{\infty}$ also converges to zero. But then $r: = {\sum\limits_{v = 1}^{\infty}}r_{v} \in R$ and the sum of G-monomials (unless they are zero) are $\underline{x}$-homogeneous of $\underline{x}$-$degree$ equal to $deg_{\underline{x}}(f)$. Now, we have,

satisfies (DC1), (DC2) and (HDC).

Uniqueness:

Suppose we have two representations of $f$ satisfying (DC1), (DC2) and (HDC), i.e., $f = {\sum\limits_{i}} c_{i}G^{a_{i}}+r$ and $f = {\sum\limits_{j}} b_{j}G^{d_{j}}+r^{'}$. We can see that $r^{'}-r = {\sum\limits_{i}}c_{i}G^{a_{i}}-{\sum\limits_{j}}b_{j}G^{d_{j}}$ which is a representation in terms of $G$ monomials. The terms of $r^{'}-r$ cannot be further reduced since $r^{'}$ and $r$ satisfy (DC2). Therefore, the representation of $r^{'}-r$ is only possible if $r^{'}-r$ is zero, i.e, $r^{'} = r$.

Remark 2.2. Let $R = K[[t_{1}, t_{2}]][x_{1}, x_{2}]$ and $\succ$ be a $\underline{t}$-local lexicographical ordering with $x_{1}\succ x_{2}\succ1\succ t_{1}\succ t_{2}$. Furthermore, let $f = t_{1}$, $g_{1} = t_{1}-t_{2}$ and $g_{2} = t_{1}-(t_{1})^2$ be the elements of $R$. We can see that every representation of $f$ in terms of $g_{i}'s$ is not the one we require. For example, $f = g_{2}+g_{1}^2+ (2t_{1}t_{2}-t_{2}^{2})$ does not satisfy DC1. However, there is a unique representation $f = g_{1}+t_{2}$ which satisfies every condition.

On the basis of Theorem 2.1, we now present an algorithm to compute subalgebra homogeneous normal form.

Algorithm 2.3. $(HNF)$ Let $\succ$ be any $\underline{t}$-local degree ordering in $R$.

Input: $G = \{g_{1}, g_{2}, \ldots, g_{k}\} \subset R \backslash \{0\}$ and $f\in R$, where $f$ and $g_{i}'s$ are $\underline{x}$-$homogeneous$ elements.

Output: $r \in R$ such that

satisfies (DC1), (DC2) and (HDC).

Instructions:

● $f_{0}: = f$;

● $r: = 0$;

● $v: = 0$;

● $while (f_{v}\neq 0$)

  $G_{v} = {\sum\limits_{p \in \mathcal{T}_{f_{v}}}} p$ such that $p = c_{p}lt(G^{a_{p}})$ for some $a_{p}\in \mathbb{Z}_{\geq 0}^{k}$;

  $r_{v}: = f_{v}-G_{v};$

  $r: = r+r_{v};$

  $f_{v+1}: = f_{v}-{\sum\limits_{p}}c_{p}G^{a_{p}}-r_{v}$;

  $v: = v+1$;

● return $r$;

Example 2.4. Let $R = K[[t_{1}, t_{2}]][x_{1}, x_{2}]$ and $\succ$ be a $\underline{t}$-local lexicographical ordering with $x_{1}\succ x_{2}\succ1\succ t_{1}\succ t_{2}$. Also, let $g_{1} = x_{1}+x_{2}$, $g_{2} = t_{1}+(t_{1}t_{2})+(t_{1}t_{2})^{2}+(t_{1}t_{2})^{3} \ldots$ and $f = x_{1}^{2}x_{2}+x_{2}^{3}+x_{1}^{3}t_{1}+x_{1}x_{2}^{2}t_{2}^{2}+x_{1}x_{2}^{2}t_{2}^{3}+x_{1}x_{2}^{2}t_{2}^{4}\ldots$ be the elements of $R$. Here $f, g_{1}, g_{2}$ are $\underline{x}$-homogeneous. Note that $lt(g_{1}) = x_{1}$ and $lt(g_{2}) = t_{1}$. Table 1 shows the subalgebra reduction through Algorithm 2.3.

The representation given by the algorithm is:

$f = g_{1}^{3}g_{2}+r$, where $r = HNF(f, G) = (x_{1}^{3}+3x_{1}^{2}x_{2}+3x_{1}x_{2}^{2}+x_{2}^{3})(t_{1}+(t_{1}t_{2})+(t_{1}t_{2})^{2}+\ldots) + x_{1}^{2}x_{2}+x_{2}^{3}+x_{1}x_{2}^{2}t_{2}^{2}+x_{1}x_{2}^{2}t_{2}^{3}+x_{1}x_{2}^{2}t_{2}^{4}\ldots-x_{1}^{3}((t_{1}t_{2})+(t_{1}t_{2})^{2}+\ldots)-3x_{1}^{2}x_{2}(t_{1}+(t_{1}t_{2})+(t_{1}t_{2})^{2}+ \ldots)-3x_{1}x_2^{2}(t_{1}+(t_{1}t_{2})+(t_{1}t_{2})^{2}+\ldots)-x_{2}^{3}(t_1+(t_{1}t_{2})+(t_{1}t_{2})^{2}+\ldots).$

For $f \in R$ and $G = \{g_1, g_2, \ldots, g_k \}\subset R$, we now present an algorithm to compute weak subalgebra normal form of $f$ with respect to $G$, which plays an important role for the characterization of Subalgebra Standard bases. We assume that $A = S[G^{*}]$ (as an $S$-subalgebra of $S[\underline{x}^{*}]$) admits a finite Sagbi basis with respect to $\succ^{*}$, where $S = K[[\underline{t}]]$ ⁴.

⁴Note that $S$ is a noetherian integral domain and $\succ^{*}$ is a global ordering on $\underline{x}^{*}$, we can construct a finite (if exists) Sagbi basis for $A$ in $S[\underline{x}^{*}]$ (for details see ^[7]).

Algorithm 2.5. ($WNF$) Let $\succ$ be any $\underline{t}$-local monomial ordering.

Input: $f \in R$ and $G = \{g_1, g_2, \ldots, g_k\} \subset R$

Output: $r\in R$, a weak subalgebra normal form of $f$ with respect to $G$.

Instructions:

● $T: = G$;

● $D: = \{ T^{a}$ $|$ $lm(f) = lm(T^{a})\}$, where $a \in \mathbb{Z}_{\geq 0}^{k};$

● If $(f\neq 0 \wedge D\neq \emptyset)$

If $e: = (min\{ecart(p)| p \in D\}-ecart(f)) > 0$

   $R^{'}: = HNF(x_{0}^{e}\cdot f^{*}, T^{*})$;

   $T: = T \cup \{f\}$;

   $f: = (R^{'})_{*};$

   $r: = WNF(f, T)$ ⁵;

⁵Since $S[G^{*}]$ admits a finite Sagbi basis and $lm(f^{*}) \in S[LM(G^{*})]$, therefore $S[G^{*}\cup \{f^{*}\}]$ would also admits a finite Sagbi basis. Hence, this procedure will terminate

Else

   $R^{'}: = HNF(f^{*}, T^{*})$;

   $f: = (R^{'})_{*};$

   $r: = WNF(f, T);$

● Else

   $r: = f;$

● return $r$;

Remark 2.6. Algorithm 2.5 works on the assumption that we are able to produce subalgebra homogeneous normal form as we can see that it relies on $HNF$ algorithm. If $G \subset R$ and $f \in R$, then after applying Algorithm 2.5, we can write as $u \cdot f = {\sum\limits_{i}} c_{i}G^{a_{i}}+r$ for some $u \in S_{\succ, A}$ and $G$-monomials $G^{a_{i}}$; where $r = WNF(f, G)$.

For the termination part of Algorithm 2.5, we first introduce a few notations.

Definition 2.7. For $g \in T \subset S[\underline{x}]$, we have $g^{*} \in T^{*}\subset S[\underline{x}^{*}]$, for which $lt_{\underline{x}^*}(g^{*})$is a product of power series as a coefficient with greatest $\underline{x}^*$-power product with respect to $\succ^{*}$ ordering. The leading subalgebra generated by $LT_{\underline{x}^*}(T^{*}) = \{lt_{\underline{x}^{*}}(g^{*})\mid g \in T\}$ is $S[LT_{\underline{x}^*}(T^{*})]$ denoted by $in_{\underline{x}^{*}}(T^{*})$.

Example 2.8. Let $g = x_2t_1+x_1t_1+x_1^{2}t_2$ $\in S[x_1, x_2]$ with $x_2\succ x_1\succ 1\succ t_1\succ t_2$. Then we can write $g$ as $(x_2+x_1)t_1+x_1^{2}t_2$. The homogenization $g^{*}$ of $g$ is $(x_0x_2+x_0x_1)t_1+x_1^{2}t_2$ and its $\underline{x}$-leading term $lt_{\underline{x}^{*}}(g^{*})$ is $t_1(x_0x_2)$.

Remark 2.9. For $f \in R$ and $G\subset R$, note that we have a compatibility between $lm$ and $lt_{\underline{x}^*}$ in a sense that $lt_{\underline{x}^*}(f^*) = lt_{\underline{x}^*}(G^a)^*$ implies $lm(f) = lm(G^a)$.

Now we prove the termination and correctness of Algorithm 2.5.

Proof. Termination:

In order to see the termination of the algorithm, first, we need to show that

stops. We use homogenization to prove it. By assumption, a Sagbi basis for $A$ is finite implies that the ascending chain of initial sublagebras

of the chain

must terminate (see ^[4] for further details). If this chain terminates, then

so that $lt_{\underline{x}^*}(f_{N+1}^*) \in in_{\underline{x}^{*}}(T_{N+1}^{*})$ is also in $in_{\underline{x}^{*}}(T_{N}^{*})$, i.e., $lt_{\underline{x}^*}(f_{N+1}^{*}) = lt_{\underline{x}^*}(p_{N}^{*})$ with $p_{N}^{*} \in D_{N}^{*}$. It shows that $T_{v}^{*}$ itself becomes stable for $v\geq N$ and so the algorithm continues to run with the fixed $T^{*}$. Since $p_{N}^{*} \in D_{N}^{*}$, therefore by Remark 2.9, $p_{N} \in D_{N}$, so the Chain(2.3) continues with the fixed $T$, i.e., $T_{v} = T_{N}$ for all $v\geq N$, where $N \in \mathbb{Z}_{\geq 0}$. Algorithm 2.3 ensures that $lm(R_{N})_{*} \notin K [T_{N}]$ which implies that $D_{N+1}$ is empty and hence the algorithm terminates.

Correctness:

By induction, if $N = 1$, then either $f = 0$ or $D = \emptyset$ $\Rightarrow$ $1.f = 0+f$ is a subalgebra reduction with weak normal form of $f$ satisfying (IC1) and (IC2).

Assume $N > 1$ and $e = min\{ecart(p)|p \in D\}-ecart(f)$.

Case $e\leq0$,

By Theorem 2.1,

satisfies (DC1), (DC2) and (HDC). Since (DC1) and (DC2) implies (IC1), therefore

Using Lemma 1.12(c),

for some $a_{i}\geq0$, and since $f^{*}$ and $(T^{a_{i}})^{*}$ are $\underline{x}^{*}$-homogeneous of the same $\underline{x}^{*}$-degree by (HDC), therefore the definition of homogenized ordering (Definition 1.11(b)) implies, for all $i$,

Note that

Inequality (2.4) and Eq (2.5) imply

Moreover, by induction, we have

where $u \in S_{\succ, K[T]}$ ($lm(u) = 1$) and $r$ is a weak subalgebra normal form of $(R^{'})_{*}$, satisfies (IC1) and (IC2) which implies for all $j$

Combining Eqs (2.5) and (2.7), we get

Moreover, by using inequalities (2.6) and (2.8) for all $j$, we have

The above equation, inequality (2.4) and Eq (2.7) imply that the representation in Eq (2.9) satisfies (IC1) and (IC2). Therefore, $r$ is the weak subalgebra normal form.

Case $e > 0$,

By Theorem 2.1,

satisfies (DC1), (DC2) and (HDC). Since (DC1) and (DC2) implies (IC1), we have

Using Lemma 1.12 (c),

for some $a_{i}\geq0$. The definition of homogenized ordering (Definition 1.11(b)) implies that for all $i$, we have

Since both sides of the above representation of $x_{0}^ef^{*}$ are $\underline{x}^{*}$-homogeneous of the same $\underline{x}^{*}$-degree by (HDC). Note that

and so we have

Since there is some $p \in D$ such that $lm(f) = lm(p)$, so the cancellation of leading terms of $x_{0}^{e}f^{*}$ and $p^{*}$ in Eq (2.10) implies:

Moreover, by induction

where $r$ is a weak subalgebra normal form of $R^{'}_{*}$ and $u^{'}\in S_{\succ, K[T]}$ ($lm(u^{'}) = 1$), satisfies (IC1) and (IC2) with $T^{a_{j}}$ involves only $g_{i}'s$ and $T^{a_{s}}$ involves $f$ as well. It implies for all $j$ and $s$,

Using inquality (2.14), we have

Combining Eqs (2.12) and (2.15), we have

Note that we can write $T^{a_{s}} = Q_{s}(u's, g_{i}'s, f)f$ and so ${\sum\limits_{s}}c_{s}T^{a_{s}} = {\sum\limits_{s}}c_{s}Q_{s}f = Q(u's, g_{i}'s, f)f$, where $Q = {\sum\limits_{s}}c_{s}Q_{s}$. Now Eq (2.17) becomes,

The inequality (2.11), Eq (2.15) and inequality (2.16) imply that the above representation satisfies (IC1) and (IC2). It remains to show that $u = u^{'}-Q \in S_{\succ, K[T]}$, i.e., $lm(u^{'}-Q) = 1$ which is clear, since $lm(f)\succ lm(R^{'}_{*})\succeq lm(Q_{s})lm(f)\succeq lm(Q)lm(f)$, i.e., $lm(Q)\prec 1$. This implies $lm(u^{'}-Q) = 1$. Therefore, $r$ is the weak subalgebra normal form of $f$.

Example 2.10. Let $f = x_{1}^{2}+x_{1}^{4}$ and $G = \{g_{1}, g_{2}\},$ where $g_{1} = x_{1}^2+x_{1}^{6}t_{2},$ and $g_{2} = x_{2}+t_{1}+t_{1}^2+t_{1}^{3}\ldots$. The elements $f$, $g_{1}$ and $g_{2}$ $\in K[[t_{1}, t_{2}]][x_{1}, x_{2}]$ and we have $\underline{t}$-local ordering $\succ$ on $Mon(K[[t_{1}, t_{2}]][x_{1}, x_{2}])$ such that $x_{2}\succ 1\succ x_{1}\succ t_{1}\succ t_{2}$. Note that $K[[t_{1}, t_{2}]][G^{*}] = K[[t_{1}, t_{2}]][x_{0}^{4}x_{1}^2+x_{1}^{6}t_{2}, x_{2}+x_{0}(t_{1}+t_{1}^2+t_{1}^{3}\ldots)]$ and $LT(G^{*}) = \{ x_{0}^{4}x_{1}^{2}, x_{2}\}$. We can see that there are no non-trivial algebraic relations (see ^[7] for details). Hence $G^{*}$ is a Sagbi basis which certifies the termination of Algorithm $WNF$. Here $ecart(f) = 2$, $ecart(g_{1}) = 4$ and $ecart(g_{2}) = 0$. Table 2 shows the subalgebra reduction through Algorithm 2.5.

So we get a weak subalgebra representation of $f$ as:

$(1+f-2g_{1})f = g_{1}+r$ with $(1+f-2g_{1}) = 1+x_{1}^2+x_{1}^4-2x_{1}^2-2x_{1}^6t_{2} \in S_{\succ, K[T]}$, where $T = G\cup\{f\}$.

3.   Construction of Subalgebra Standard bases

For Subalgebra Standard bases criterion, we define a notion of algebraic relations for $G \subset R$. For this, we define an evaluation map $\pi$: $K[Y]\rightarrow K[LM(G)]$ via $y_{i}\mapsto lm(g_{i})$; where the cardinality of $Y = \{y_{1}, y_{2}, \cdots \}$ is same as that of $G$.

Definition 3.1. Let $G = \{ g_{1}, g_{2}, \ldots, g_{k}\}\subset R$. The set of algebraic relations of $G$ denoted by $AR(G)$ is the kernel of above map $\pi$, i.e.,

is an ideal in $K[Y]$, where $Y = \{y_1, y_2, \ldots, y_k \}$.

Definition 3.2. Let $G = \{ g_{1}, g_{2}, \ldots, g_{k}\}\subset R$ and $g = {\sum\limits_{i}}c_{i}G^{a_{i}} \in K[G]$. We define height of $g$ with respect to given representation as:

Theorem 3.3. (Subalgebra Standard Basis Criterion) Let $G = \{ g_{1}, g_{2}, \ldots, g_{k}\}$ be a subset of $R$ such that $S[G^{*}]$ admits a finite Sagbi basis. Assume that $\mathcal{S}: = \{P_{1}, P_{2}, \ldots, P_{m} \}$ is a generating set of $AR(G)$. Then $G$ is a Subalgebra Standard basis for $K[G]$ iff for each $1\leq j\leq k$, $WNF(P_{j}(G)) = 0$ with respect to $G$.

Proof. ($\Rightarrow$) On the contrary, suppose $WNF(P_{j}(G))\neq 0$ for some $j$. Then by property of weak subalgebra normal form, $lm(WNF(P_{j}(G)) \notin in(A)$. Observe that $P_{j}(G) \in K[G]$, which implies $WNF(P_{j}(G) \in K[G]$. By assumption, $G$ is a Subalgebra Standard basis for $K[G]$. Therefore, by Definition 1.7 $lm(WNF(P_{j}(G)) \in in(A)$ which is a contradiction.

($\Leftarrow$) To prove that $G$ is a Subalgebra Standard Bases of $K[G]$, we need to show that for any $g\in K[G]$, there exists $u\in S_{\succ, K[G]}$ such that

This condition is sufficient since the above representation implies that $lm(g)\in in(A)$. On the contrary suppose that this kind of representation doesn't hold, i.e., $lm(g) \prec ht(\sum_{i = 1}^{ł}c_{i}G^{a_{i}})$. Without loss of generality, we can assume that this representation has the smallest possible height of all possible representations of $u \cdot g$. We denote this height by $X: = max_{i = 1}^{l}\{lm(G^{a_{i}})\}$. Since $lm(g)\prec X$, therefore, we can assume that the first $\alpha$ summands in the above representation be the ones for which $X = lm(G^{a_{i}})$. Then cancellation of their leading terms implies $\sum_{i = 1}^{\alpha}c_{i}lm(G^{a_{i}}) = 0$, i.e., we obtain a polynomial $P(Y) = \sum_{i = 1}^{\alpha}c_{i}Y^{a_{i}}\in AR(G)$. Now, $\mathcal{S} = \{P_{1}, ..., P_{m}\}$ being a generating set of $AR(G)$, we can write

for suitable $f_j\in K[Y]$. Furthermore, note that

⁶This equality holds for any represenation of given polynomials

Moreover, by assumption we have for all $1\leq j \leq m, \, WNF(P_{j}(G)\mid G) = 0$, which means that $w_jP_{j}(G)$ has a representation, $w_jP_{j}(G) = \sum_{q = 1}^{l_{j}}c_{q_{j}}G^{a_{q_{j}}}$, for suitable $w_j\in S_{\succ, K[G]}$. Note that

The strict inequality holds since $P_{j}\in AR(G)$. We may assume that $w = w_j, \, \hbox{where}\, \, 1\leq j \leq m$, therefore for each $j$, we have

Let $X_{j} = max_{j = 1}^{l_j}\{lm(f_{j}(G)lm(G^{a_{q_{j}}})\}$ be the height of the right hand side in Eq (3.3), then using (3.2) we have

Now, the Eqs (3.1) and (3.3) imply that:

We see that $\, X_j\prec X \,; \, \hbox {for all}\, \, 1\leq j\leq m. \, \, \hbox{Therefore, }\, \, ht(sum_{1}) = max_{j = 1}^{m}X_{j}\prec X.$ By the choice of $\alpha, \ ht(sum_{2})\prec X,$ which is a contradiction to our assumption of a representation of $g$ with smallest possible height. Thus, $G$ is a Subalgebra Standard basis of $K[G]$.

We now present an algorithm to compute Subalgebra Standard basis on the basis of Theorem 3.3.

Algorithm 3.4. Let $\succ$ be a $\underline{t}$-local monomial ordering on $R$.

Input: A finite subset $G \subset R$.

Output: A Subalgebra Standard basis ${F}$ for ${K}[{G}]$.

Instructions:

● $F = G$;

● $old F = \emptyset$;

● while ($F\neq old F$)

  Compute a generating set $\mathcal{S}$ for $AR({F})$;

  $\mathcal{P} = \mathcal{S}({F})$;

  $Red = \{WNF(p\mid {F})$ $\mid p\in \mathcal{P}\setminus\{0\}\}\setminus\{0\}$;

  $old{F} = {F}$;

  ${F} = {F}\cup Red$;

● return ${F}$;

Example 3.5. Let $G = \{g_{1}, g_{2}, g_{3}\}$, where $g_{1} = x_1^2+x_1^4$, $g_{2} = x_1^2+x_1^6t_{2}$ and $g_{3} = x_2+t_{1}+t_{1}^2+t_{1}^3\ldots$ be elements of $K[[t_{1}, t_{2}]][x_1, x_2]$. We have $\underline{t}$-local ordering $\succ$ on $Mon(K[[t_{1}, t_{2}]][x_{1}, x_{2}])$ with $x_{2} \succ 1\succ x_{1}\succ t_{1}\succ t_{2}$. Note that $K[[t_{1}, t_{2}]][G^{*}] = K[[t_{1}, t_{2}]][x_{0}^{2}x_{1}^2+x_{1}^{4}, x_{0}^{4}x_{1}^2+x_{1}^{6}t_{2}, x_{2}+x_{0}(t_{1}+t_{1}^2+t_{1}^{3}\ldots)]$ and $LT(G^{*}) = \{ x_{0}^{2}x_{1}^{2}, x_{0}^{4}x_{1}^{2}, x_{2}\}$. Since there are no non-trivial algebraic relations (see ^[7] for details). Hence $G^{*}$ is a Sagbi basis. This ensures the termination of Algorithm $WNF$. The construction of Subalgebra Standard basis for $K[G]$ is shown in Table 3. This table shows that $\{x_1^2+x_1^4, x_1^2+x_1^6t_{2}, x_2+t_{1}+t_{1}^2+t_{1}^3\ldots, -x_1^8-x_1^6t_{2}-2x_1^8t_{2}-2x_1^{10}t_{2}\}$ is a Subalgebra Standard basis for $K[G]$.

Now, we present an example which shows that Subalgebra Standard bases could be infinite for even finitely generated subalgebras.

Example 3.6. Let $\succ$ be a $\underline{t}$-local ordering on $Mon(K[[t]][x_{1}, x_{2}])$ with $x_{2}\succ 1\succ x_{1}\succ t$ and $G = \{g_{1}, g_{2}, g_{3}\} \subset K[[t]][x_{1}, x_{2}]$, where $g_{1} = x_1t+x_2$, $g_{2} = x_1x_2t$ and $g_{3} = x_1x_2^{2}t$. Table 4 shows the first three steps of the Standard basis Algorithm. At each $nth$ step there is addition of an element $x_1^{n+1}x_2t^{n+1}$ in $F_n$ ($n\geq 1$) ⁷. This implies that the set $\{x_1t+x_2, x_1x_2t, x_1x_2^2t, x_1^2x_2t^2, x_1^3x_2t^3, x_1^4x_2t^4, \ldots\}$ is a Subalgebra Standard basis for $K[G]$.

⁷In this pattern, algorithm continues for infinitely many steps.

Acknowledgments

Thanks to Prof. Dr. Gerhard Pfister for his helpful comments and valuable suggestions.

Conflict of interest

The authors declare that there is no conflict of interest.