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${◻}^{\prime }$): 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_{ij}\in R$ have degree at most $D$, $1\le i\le m$, $1\le j\le l$. An $R$-basis for the solutions $\mathbf{f}=(f_1,\dots ,f_l)\in R^l$ of the related homogeneous system of equations

$$a_{i1}{f}_1+\dots +a_{il}{f}_l=0,i=1,\dots ,m,$$

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

$$B(m,D,n)<mD+B(mD+m{D}^2,D,n-1),$$

$$B(m,D,1)\le mD.$$

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

$$\mathrm{\Delta }:=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1r}\\ ⋮& ◻& ⋮\\ a_{r1}& \dots & a_m\end{array}\right).$$

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 $\mathrm{\Delta }$ with exponent equal to $\mathrm{deg}\mathrm{\Delta }$. Next one may apply Cramer's rule (cf. Cramer rule) to think of the original system of equations as being of the form:

$$\mathrm{\Delta }{f}_i=A_{i,r+1}{f}_{r+1}+\dots +A_{i,l}{f}_l,$$

$$A_{i,j}\in k,i=1,\dots ,r.$$

Subtracting as necessary multiples of the obvious solutions

$$(A_{i,r+j},A_{i+1,r+j},\dots ,A_{r,r+j};\mathrm{\Delta }{\mathbf{e}}_j),j=1,\dots ,l-r,$$

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

$$\mathrm{deg}{f}_{j+r},\dots ,\mathrm{deg}{f}_l<\mathrm{deg}\mathrm{\Delta }=rD.$$

Thus, for these remaining solutions one may bound the degrees of all $f_j$ with respect to $X_n$ by $rD$, and hence one may think of the $f_j$ as linear combinations of $X_n^h$, $h<rD$, with coefficients from $R_{n-1}:=k[X_1,\dots ,X_{n-1}]$. Setting to zero the coefficients of the resulting $D+rD$ powers of $X_n$ from the original system of equations gives a linear homogeneous system of at most $m(D+rD)$ 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\ge 2$,

$$B(m,D,n)<(2m(m+1){)}^{2^{n-2}}{D}^{2^{n-1}}.$$

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

$$a_{i1}{f}_1+\dots +a_{il}{f}_l=b_i,i=1,\dots ,m,$$

has a solution $\mathbf{f}\in R^l$. If it does, one can be found in a finite number steps with $\mathrm{maxdeg}{f}_j\le 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]