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[edit]