View source for Hermann algorithms

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300701.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300702.png" />. Any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300703.png" />-module for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300704.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300705.png" />.

Condition (P): A. Seidenberg pointed out in [[#References|[a1]]] that, in characteristic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300706.png" />, it is necessary to assume roughly the decidability of whether <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300707.png" />.

Condition (F<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300708.png" />): 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h1300709.png" /> retains interest because it gives directly the correct order of magnitude of complexity of the fundamental membership problem over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007010.png" />. That algorithm is embodied in the following basic result.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007011.png" /> have degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007014.png" />. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007015.png" />-basis for the solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007016.png" /> of the related homogeneous system of equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007017.png" /></td> </tr></table>

can be determined in a finite number of steps. That basis will have entries whose degrees are bounded by a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007018.png" /> satisfying the recursion

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007019.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007020.png" /></td> </tr></table>

To see this, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007021.png" /> be a new indeterminate over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007022.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007023.png" /> is a solution of the system, one can clear out the denominators to assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007024.png" />. Then the coefficients of each fixed power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007025.png" /> give a solution. So a basis of solutions over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007026.png" /> leads to a basis of solutions over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007027.png" />, with the same bounds, and one can assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007028.png" /> is infinite.

One may re-index the equations and unknowns, if necessary, to arrange that the upper left <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007029.png" />-submatrix of coefficients has maximal rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007030.png" />. Set

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007031.png" /></td> </tr></table>

Now, since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007032.png" /> is infinite, one may arrange by a change of variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007034.png" />, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007035.png" /> occurs in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007036.png" /> with exponent equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007037.png" />. 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:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007038.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007039.png" /></td> </tr></table>

Subtracting as necessary multiples of the obvious solutions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007040.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007041.png" /> denotes the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007042.png" />th standard basis element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007043.png" />, allows one to restrict the search for possible further solutions to those with

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007044.png" /></td> </tr></table>

Thus, for these remaining solutions one may bound the degrees of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007045.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007046.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007047.png" />, and hence one may think of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007048.png" /> as linear combinations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007050.png" />, with coefficients from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007051.png" />. Setting to zero the coefficients of the resulting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007052.png" /> powers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007053.png" /> from the original system of equations gives a linear homogeneous system of at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007054.png" /> equations with coefficients from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007055.png" /> of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007056.png" />.

Tracing through the argument verifies the recurrence. It is easy to verify that when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007057.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007058.png" /></td> </tr></table>

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007059.png" />-linear inhomogeneous equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007060.png" /></td> </tr></table>

has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007061.png" />. If it does, one can be found in a finite number steps with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007062.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007063.png" /> 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>