Namespaces
Variants
Actions

Difference between revisions of "Hermann algorithms"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 63 formulas out of 63 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
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.
+
<!--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:
 
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 (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 <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 (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<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.
+
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).
 
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).
Line 13: Line 21:
 
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]]).
 
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.
+
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 <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
+
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
  
<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>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007018.png" /> satisfying the recursion
+
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
  
<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>
+
\begin{equation*} B ( m , D , n ) &lt; m D + B ( m D + m D ^ { 2 } , D , n - 1 ), \end{equation*}
  
<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>
+
\begin{equation*} B ( m , D , 1 ) \leq m D. \end{equation*}
  
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.
+
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 <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
+
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
  
<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>
+
\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 <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:
+
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:
  
<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>
+
\begin{equation*} \Delta f _ { i } = A _ { i , r + 1 } f _ { r + 1 } + \ldots + A _ {i , l } f _ { l }, \end{equation*}
  
<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>
+
\begin{equation*} A _{i, \,j} \in k ,\; i = 1 , \dots , r. \end{equation*}
  
 
Subtracting as necessary multiples of the obvious solutions
 
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>
+
\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 <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
+
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
  
<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>
+
\begin{equation*} \operatorname { deg } f _ { j + r} , \dots , \operatorname { deg }  f _ { l } &lt; \operatorname { deg } \Delta = r D. \end{equation*}
  
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" />.
+
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 &lt; 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007057.png" />,
+
Tracing through the argument verifies the recurrence. It is easy to verify that when $n \geq 2$,
  
<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>
+
\begin{equation*} B ( m , D , n ) &lt; ( 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130070/h13007059.png" />-linear inhomogeneous equations
+
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
  
<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>
+
\begin{equation*} a _ { i 1 } f _ { 1 } + \ldots + a _ { i l } f _ { l } = b _ { i } , i = 1 , \ldots , m, \end{equation*}
  
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" />.
+
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]]).
 
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====
 
====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>
+
<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>

Revision as of 16:56, 1 July 2020

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
How to Cite This Entry:
Hermann algorithms. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hermann_algorithms&oldid=17667
This article was adapted from an original article by W. Dale Brownawell (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article