Hermann algorithms

In her famous 1926 paper [a6], G. Hermann set out to show that all standard objects in the theory of polynomial ideals over fields $k$, including the prime ideals associated to a given ideal, can be determined by means of computations involving finitely many steps, i.e. field operations in $k$. Any $R$-module for $R : = k [ X _ { 1 } , \dots , X _ { n } ]$ is determined by giving a finite set of generators, called a basis. Hermann states explicitly that one can give an upper bound for the number of operations necessary for each sort of computation.

Building on previous work [a7] by K. Henzelt and E. Noether, Hermann's work set a milestone in effective algebra. While the structural approach to algebra continued to flourish, Hermann's contribution lay fallow for decades except mainly for the notice of a few gaps:

Condition (F): B.L. van der Waerden pointed out in [a10] that it is necessary to assume that one can completely factor an arbitrary polynomial over $k$.

Condition (P): A. Seidenberg pointed out in [a1] that, in characteristic $p$, it is necessary to assume roughly the decidability of whether $[ k ^ { p } ( a _ { 1 } , \dots , a _ { s } ) : k ^ { p } ] = p ^ { s }$.

Condition (F$\square '$): M. Reufel pointed out in [a9] that, in order to obtain a normal basis for a finitely-generated free module over a polynomial ring, one needs only the factorization of polynomials into prime powers. This is weaker than (F) in positive characteristic.

Numerical corrections: C. Veltzke, cf. [a2], [a3], (and later Seidenberg [a1] and D. Lazard [a4]) noted and removed numerical inaccuracies in Hermann's bounds. The conditions are vital in Hermann's manipulations of "Elementarteilerformen" (Chow forms).

Starting in mid-twentieth century, the work of W. Krull [a11], A. Fröhlich and J.C. Sheperdson [a5], Reufel [a9], and Lazard [a4] made even more explicit that Hermann's computations give an algorithm. For more detailed historical remarks and a complete bibliography up to 1980, see [a2], [a3]. Nowadays (as of 2000), the main practical methods for computation in commutative algebra are implemented using Gröbner bases (cf. also Gröbner basis).

However, even from a thoroughly modern point of view, Hermann's algorithm for linear algebra over $R$ retains interest because it gives directly the correct order of magnitude of complexity of the fundamental membership problem over $R$. That algorithm is embodied in the following basic result.

Let $a _ { i j } \in R$ have degree at most $D$, $1 \leq i \leq m$, $1 \leq j \leq l$. An $R$-basis for the solutions $\mathbf{f} = ( f _ { 1 } , \dots , f _ { l } ) \in R ^ { l }$ of the related homogeneous system of equations

\begin{equation*} a _ { i1 } f _ { 1 } + \ldots + a _ { i l } f _ { l } = 0 , i = 1 , \ldots , m, \end{equation*}

can be determined in a finite number of steps. That basis will have entries whose degrees are bounded by a function $B ( m , D , n )$ satisfying the recursion

\begin{equation*} B ( m , D , n ) < m D + B ( m D + m D ^ { 2 } , D , n - 1 ), \end{equation*}

\begin{equation*} B ( m , D , 1 ) \leq m D. \end{equation*}

To see this, let $t$ be a new indeterminate over $k$. If $\mathbf{f} \in R ( t ) ^ { l }$ is a solution of the system, one can clear out the denominators to assume that $\mathbf{a} \in R [ t ] ^ { l }$. Then the coefficients of each fixed power of $t$ give a solution. So a basis of solutions over $k ( t ) [ X _ { 1 } , \dots , X _ { n } ]$ leads to a basis of solutions over $R$, with the same bounds, and one can assume that $k$ is infinite.

One may re-index the equations and unknowns, if necessary, to arrange that the upper left $( r \times r )$-submatrix of coefficients has maximal rank $r$. Set

\begin{equation*} \Delta : = \left( \begin{array} { c c c } { a _ { 11 } } & { \dots } & { a _ { 1 r } } \\ { \vdots } & { \square } & { \vdots } \\ { a _ { r 1 } } & { \dots } & { a _ { m } } \end{array} \right). \end{equation*}

Now, since $k$ is infinite, one may arrange by a change of variables $X _ { i } \mapsto X _ { i } + \alpha _ { i } X _ { n }$, $\alpha _ { i } \in { k }$, that $X_n$ occurs in $\Delta$ with exponent equal to $\operatorname { deg } \Delta$. Next one may apply Cramer's rule (cf. Cramer rule) to think of the original system of equations as being of the form:

\begin{equation*} \Delta f _ { i } = A _ { i , r + 1 } f _ { r + 1 } + \ldots + A _ {i , l } f _ { l }, \end{equation*}

\begin{equation*} A _{i, \,j} \in k ,\; i = 1 , \dots , r. \end{equation*}

Subtracting as necessary multiples of the obvious solutions

\begin{equation*} ( A _ { i , r + j} , A _ { i + 1 , r + j} , \dots , A _ { r, r + j} ; \Delta \mathbf{e} _ { j } ) ,\; j = 1 , \dots , l - r, \end{equation*}

where $\mathbf{e}_j$ denotes the $j$th standard basis element of $k ^ { l - r }$, allows one to restrict the search for possible further solutions to those with

\begin{equation*} \operatorname { deg } f _ { j + r} , \dots , \operatorname { deg } f _ { l } < \operatorname { deg } \Delta = r D. \end{equation*}

Thus, for these remaining solutions one may bound the degrees of all $f_j$ with respect to $X_n$ by $r D$, and hence one may think of the $f_j$ as linear combinations of $X _ { n } ^ { h }$, $h < r D$, with coefficients from $R _ { n - 1} : = k [ X _ { 1 } , \dots , X _ { n-1 } ]$. Setting to zero the coefficients of the resulting $D + r D$ powers of $X_n$ from the original system of equations gives a linear homogeneous system of at most $m ( D + r D )$ equations with coefficients from $R _ { n-1 }$ of degree at most $D$.

Tracing through the argument verifies the recurrence. It is easy to verify that when $n \geq 2$,

\begin{equation*} B ( m , D , n ) < ( 2 m ( m + 1 ) ) ^ { 2 ^ { n - 2 } } D ^ { 2 ^ { n - 1 } }. \end{equation*}

For consistent systems of inhomogeneous equations, Cramer's rule gives a particular solution, and the above procedure gives a basis for the related homogeneous system: One can determine in a finite number of steps whether a given system of $R$-linear inhomogeneous equations

\begin{equation*} a _ { i 1 } f _ { 1 } + \ldots + a _ { i l } f _ { l } = b _ { i } , i = 1 , \ldots , m, \end{equation*}

has a solution $\mathbf{f} \in R ^ { l }$. If it does, one can be found in a finite number steps with $\operatorname{maxdeg} f _ { j } \leq B ( m , D , n )$.

Thus, the Hermann algorithm gives explicit bounds for the ideal membership problem. According to the examples in [a8], such bounds are necessarily doubly exponential. This is in contrast with the singly exponential bounds for the Hilbert Nullstellensatz (cf. Effective Nullstellensatz).

References

[a1]	A. Seidenberg, "Constructions in algebra" Trans. Amer. Math. Soc. , 197 (1974) pp. 273–313
[a2]	B. Renschuch, "Beiträge zur konstruktiven Theorie der Polynomideale XVII/1: Zur Henzelt/Noether/Hermannschen Theorie der endlich vielen Schritte" Wiss. Z. Pädagog. Hochsch. Karl Liebknecht, Potsdam , 24 (1980) pp. 87–99
[a3]	B. Renschuch, "Beiträge zur konstruktiven Theorie der Polynomideale XVII/2: Zur Henzelt/Noether/Hermannschen Theorie der endlich vielen Schritte" Wiss. Z. Pädagog. Hochsch. Karl Liebknecht, Potsdam , 25 (1981) pp. 125–136
[a4]	D. Lazard, "Algèbre linéaire sur $K [ X _ { 1 } , \dots , X _ { n } ]$ et élimination" Bull. Soc. Math. France , 105 (1977) pp. 165–190
[a5]	A. Fröhlich, J.C. Sheperdson, "Effective procedures in field theory" Philos. Trans. Royal Soc. A , 248 (1956) pp. 407–432
[a6]	G. Hermann, "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale" Math. Ann. , 95 (1926) pp. 736–788
[a7]	K. Henzelt, "Zur Theorie der Polynomideale und Resultanten, bearbeitet von Emmy Noether" Math. Ann. , 88 (1923) pp. 53–79
[a8]	E.W. Mayr, A.R. Meyer, "Complexity of the word problems for commutative semigroups and polynomial ideals" Adv. Math. , 46 (1982) pp. 305–329
[a9]	M. Reufel, "Konstruktionsverfahren bei Moduln über Polynomringen" Math. Z. , 90 (1965) pp. 231–250
[a10]	B.L. van der Waerden, "Eine Bemerkung über die Unzerlegbarkeit von Polynomen" Math. Ann. , 102 (1930) pp. 738–739
[a11]	W. Krull, "Parameterspezialisierung in Polynomringen" Archiv Math. , 1 (1948/49) pp. 57–60