View source for Hermann algorithms

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 63 formulas, 63 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
In her famous 1926 paper [[#References|[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 [[#References|[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 [[#References|[a10]]] that it is necessary to assume that one can completely factor an arbitrary polynomial over $k$.

Condition (P): A. Seidenberg pointed out in [[#References|[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 [[#References|[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. [[#References|[a2]]], [[#References|[a3]]], (and later Seidenberg [[#References|[a1]]] and D. Lazard [[#References|[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 [[#References|[a11]]], A. Fröhlich and J.C. Sheperdson [[#References|[a5]]], Reufel [[#References|[a9]]], and Lazard [[#References|[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 [[#References|[a2]]], [[#References|[a3]]]. Nowadays (as of 2000), the main practical methods for computation in [[Commutative algebra|commutative algebra]] are implemented using Gröbner bases (cf. also [[Gröbner basis|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 } } &amp; { \dots } &amp; { a _ { 1 r } } \\ { \vdots } &amp; { \square } &amp; { \vdots } \\ { a _ { r 1 } } &amp; { \dots } &amp; { 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|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 [[#References|[a8]]], such bounds are necessarily doubly exponential. This is in contrast with the singly exponential bounds for the Hilbert Nullstellensatz (cf. [[Effective Nullstellensatz|Effective Nullstellensatz]]).

====References====
<table><tr><td valign="top">[a1]</td> <td valign="top">  A. Seidenberg,   "Constructions in algebra"  ''Trans. Amer. Math. Soc.'' , '''197'''  (1974)  pp. 273–313</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  D. Lazard,   "Algèbre linéaire sur $K [ X _ { 1 } , \dots , X _ { n } ]$ et élimination"  ''Bull. Soc. Math. France'' , '''105'''  (1977)  pp. 165–190</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  A. Fröhlich,   J.C. Sheperdson,   "Effective procedures in field theory"  ''Philos. Trans. Royal Soc. A'' , '''248'''  (1956)  pp. 407–432</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  G. Hermann,   "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale"  ''Math. Ann.'' , '''95'''  (1926)  pp. 736–788</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  K. Henzelt,   "Zur Theorie der Polynomideale und Resultanten, bearbeitet von Emmy Noether"  ''Math. Ann.'' , '''88'''  (1923)  pp. 53–79</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  E.W. Mayr,   A.R. Meyer,   "Complexity of the word problems for commutative semigroups and polynomial ideals"  ''Adv. Math.'' , '''46'''  (1982)  pp. 305–329</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  M. Reufel,   "Konstruktionsverfahren bei Moduln über Polynomringen"  ''Math. Z.'' , '''90'''  (1965)  pp. 231–250</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  B.L. van der Waerden,   "Eine Bemerkung über die Unzerlegbarkeit von Polynomen"  ''Math. Ann.'' , '''102'''  (1930)  pp. 738–739</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  W. Krull,   "Parameterspezialisierung in Polynomringen"  ''Archiv Math.'' , '''1'''  (1948/49)  pp. 57–60</td></tr>
</table>