Systems of Laurent Polynomial Equations and Gröbner Bases

Franz Pauer
Institut fuer Mathematik, Universitaet Innsbruck
A-6020 Innsbruck, Technikerstr. 25/7, Austria
Innsbruck, A-6020
Austria
E-mail:Franz.Pauer@uibk.ac.at

Abstract

Let K be a field and $R:=K\lbrack x_1,\ldots ,x_n, x_1^{-1}, \ldots , x_n^{-1}\rbrack$ the K-algebra of Laurent polynomials over K. Let $f_1,\ldots , f_k$ be elements of R and $Z:=Z(f_1,\ldots , f_k):= \{\, z\in (K\setminus\{0\})^n\, \vert\, f_1(z)=\ldots =f_k(z)= 0\, \}$ the set of their common zeros.

Clearly, there are elements $e(1),\ldots , e(k)\in {\bf Z}^n$ such that $x^{e(1)}f_1, \ldots , x^{e(k)}f_k$ are polynomials in $K\lbrack x\rbrack :=K\lbrack x_1,\ldots ,x_n\rbrack$ and $Z= \{\, z\in (K\setminus\{0\})^n\, \vert\, (x^{e(1)}f_1)(z)=\ldots =(x^{e(k)}f_k)(z)= 0\, \}$. Hence Z could be computed via a Gröbner basis (with respect to a pure lexicographic order) of the ideal generated by $x^{e(1)}f_1, \ldots , x^{e(k)}f_k$ in $K\lbrack x\rbrack$. But the degrees of these polynomials could be very high, hence in this talk I shall propose another method to solve Laurent polynomial equations. This method is based on results of the paper PU (Pauer, F., Unterkircher, A.: Gröbner Bases for Ideals in Laurent polynomial rings and their Application to Systems of Difference Equations. Preprint 1997, submitted to AAECC).

Let $T:=\{x^a\in R\, \vert\, a\in{\bf Z}^n\}$, let T₀ be the submonoid of T generated by $\{x_i\vert 1\le i\le n\}$ and T_j the submonoid generated by $\{\prod_{i=1}^n x_i^{-1}\}\cup \{ x_i\vert 1\le i\le n, i\ne j\}, \ 1\le j\le n$ .

Let $f(i_1,\ldots ,i_n):=-\min\{ 0, i_1, \ldots ,i_n\}$ and let <_lex be the lexicographic order on ${\bf Z}^n$. Then we define a total order < on T as follows:

$$x^i < x^j: \Leftrightarrow f(i)<f(j) \ \hbox {\rm or}\ (f(i)=f(j) \ \hbox {\rm and}\ i<_{lex}j)\ .$$

Then < is a generalized term order on T, i.e. a total order on T such that

1 is the smallest element in T and

r<s implies tr<ts, for all $0\le i\le n, \, r\in T,\, t,s\in T_i.$

Moreover, all elements of T₀ are smaller then any element of $T\setminus T_0$.

By lt(f) we denote the leading term (with respect to <) of a non-zero Laurent polynomial $f\in R$.

Definition: Let J be an ideal in R and let Gbe a finite subset of $J\setminus\{ 0\}$. Then G is a Gröbner basis (with respect to <) of J iff

$$\{lt(f)\vert 0\ne f\in J\}=\{lt(tg)\vert t\in T, g\in G\}.$$

(Since < is not a term order, in general $lt(tg)\ne t.lt(g)$!)

Proposition (see PU): For every ideal in R a Gröbner basis can be computed in a finite number of steps.

For the sake of simlicity let us assume that Z is finite. Let J be the ideal in R generated by the Laurent polynomials $f_1,\ldots , f_k$ and let x_n be the smallest element in $\{ x_1,\ldots , x_n\}$. Then the ideal $J\cap K\lbrack x_n\rbrack$ in $K\lbrack x_n\rbrack$ is not zero. To get an algorithm for the computation of Z it is sufficient to know how to compute a finite system of generators of this ideal. Similar to the well-known case of polynomial ideals we obtain the following

Proposition: Let G be a Gröbner basis of J with respect to <. For $g\in G\cap K\lbrack x_n\rbrack$ let a(g) be the maximal nonnegative integer such that x_n^a(g) divides g (in $K\lbrack x_n\rbrack$). Then $\{ x_n^{-a(g)}g\vert g\in G\cap K\lbrack x_n\rbrack\}$ generates the ideal $J\cap K\lbrack x_n\rbrack$.