Kronecker’s nice, little black–boxes

Joos Heintz^{1}

July 26, 1999

Origins, development and interaction of modern algebraic geometry and commutative algebra may be considered as one of the most illustrative examples of historical dialectics in mathematics. Still today, and more than ever before, timeless idealism (in form of modern commutative algebra) is bravely struggling which secular materialism (in form of complexity issues in computational algebraic geometry).

Kronecker was doubtless the creator of this eternal battle field and its first war lord. In a similar way as Gauss did for computational number theory, Kronecker laid intuitively the mathematical foundations of modern computer algebra. He introduced 1882 in [Kro82] his famous ”elimination method” for polynomial equation systems and his ”parametric representation” of (equidimensional) algebraic varieties. By the way, this parametric representation was until 10 years ago rediscovered again and again.

Using his elimination method in a highly skillful, but unfortunately inimitable way, Kronecker was able to state and to prove a series of fundamental results on arbitrary algebraic varieties. He was able to define in a precise way the notion of dimension and to prove a corresponding dimension theorem for arbitrary algebraic varieties over an algebraically closed field, to estimate the number of equations needed to define any algebraic variety in affine or projective space and certainly he knew already the special form of ”Hilbert’s Nullstellensatz”.

Not everything that came to Kronecker’s mind was laid down by him in a explicit and written form. Nevertheless a careful interpretation of his work suggests his deep understanding of the general structure of algebraic varieties.

A particular result, proved by Kronecker, says that any algebraic variety can be defined by finitely many equations. Later Hilbert generalized this result to his seminal ”Basissatz” introducing for its proof a new, nonconstructive method, far away from the traditional elimination–type arguments used by Kronecker and other contemporary mathematicians. It took some time to convince the mathematical world that ”mystics” and ”magics” are able to produce (correct) mathematical results, but finally the new discipline of commutative algebra became legitimated.

1: Universidad de Cantabria, Santander, Spain and Universidad de Buenos Aires, Argentina.

Hilbert’s discovery of the Basissatz was also the starting point for a long and huge conflict which dominated a considerable part of the history of modern algebraic geometry and which did not come to an end until today.

Classical algebraic geometry is motivated by the need – or the wish – to find tools which allow to ”solve” or to ”reduce” (whatever this means) systems of polynomial equations. This leads to the following questions:

• are commutative algebra and its modern derivate, namely todays scheme– theoretical algebraic geometry, able to absorbe classical algebraic geometry?

• is the solution to Hilbert’s ”Hauptproblem der Idealtheorie” (the ideal membership problem) the key to all computational issues in classical algebraic geometry?

These questions, implicitely raised by the work of Hilbert and of Macaulay, look very academic. However any enterprise to answer them has deep consequences.

Let us here outline just one possible way to answer these questions.

If we consider the ”Hauptproblem der Idealtheorie” as a question of pure theoretical computer science, this problem turns out to be computationally intractable, at least in worst case. More precisely, the ”Hauptproblem der Idealtheorie” turns out to be complete in exponential (memory) space ( [MM82]). On the other hand, almost all of the most fundamental problems of computational classical algebraic geometry are proved to be solvable in polynomial space (see e.g. [DFGS91, MT97, Mat]). Thus computational complexity is able to distinguish between geometry and algebra and supports the viewpoint of Kronecker (geometry) against the viewpoint of Hilbert and Macaulay (algebra).

It is well known that Kronecker’s personality was highly conflictive for his time. It is less known how much postume rejection Kronecker’s personality was able to produce. Hilbert’s writings are eloquent in this point, whereas Macaulay’s attack against Kronecker’s work on elimination was a rather well educated one. In this context let us also remind André Weil’s ”elimination of the elimination theory”.

Kronecker’s radical spirit did not recognize limitations. His radicalism was as universal as his spirit was. Of course he was right requiring that any mathematical reflection has to end up with finitely many and practically doable computations which settle the concrete (e.g. application) problem under consideration. However declaring the natural numbers as the only mathematical objects created by god for mankind and declaring the ”rest” (real, complex numbers, infinite cardinals and ordinals) as devils work, tempting humans to play with the infinite, he demonstrated that he was not able or willing to distinguish between syntaxis and semantics. He was right to require that mathematical expressions (algebra) have always to move within finitary limits, but he was wrong to exclude reflections about infinite mathematical objects (geometry) using a finitarian language. Of course his own work ended up to be godless enough to guarantee him mathematical recognition by his worst adversaries.

Kronecker’s own formulation of his elimination method in [Kro82] was unprecise and general enough to allow different interpretations of it, computationally efficient and inefficient ones. Possibly it was in his mind to leave open the door for future complexity issues of his method.

Hilbert’s and Macaulay’s attacks against Kronecker’s method were based on the computationally inefficient interpretation. They noticed that under this interpretation Kronecker’s elimination method leads to a hyperexponential swell of intermediate expression size and used this observation for the promotion of their own, more ”simple” and ”mathematical” point of view. Hilbert and Macaulay’s position became finally predominant in the future development of algebraic geometry (and commutative algebra). Their ideas led to the modern, computer implemented tool of Groebner basis algorithms for the symbolic resolution (simplification) of polynomial equation systems. This tool was introduced in the sixties by B. Buchberger (and his school) and represents today the core of all current computer algebra software packages.

The discovery of effective (affine) Nullstellensätze and their application to the complexity analysis of Groebner basis algorithms for the solution of geometrical problems, represented at the end of the eighties the turning point for a process which led finally back to Kronecker’s original ideas. This process was not a conscient motion with clear goals, but rather a slow emerging of mathematical insight and of algorithmic design within the scope of Kronecker’s intuitions.

The first step in this direction was even made as part of a mathematical proof and not of an algorithmic design. In its standard interpretation, Kronecker’s elimination method relies on an iterated use of resultants of suitable univariate polynomials with parametric coefficients. In fact, a resultant is nothing but the constant term of the characteristic polynomial of a suitable linear map determined by the polynomials under consideration. Replacing in this version of Kronecker’s elimination algorithm the occuring resultants just by the constant terms of the corresponding minimal polynomials, one obtains an enormous reduction of degree, height and also of straight–line program complexity for the polynomials produced during the procedure (see e.g. [CGH88, CGH89, GHS93]).

Other important ingredients of the emerging new algorithmic method were the parametric representation of equidimensional algebraic varieties (a rediscovery of Kronecker’s old idea) and the arithmetic circuit (straight–line program) representation of polynomials (which was neither out of the scope of Kronecker’s intuition nor clearly included in the main stream of his thinking).

The combination of these ingredients produced a considerable effect upon the worst case complexity of symbolic elimination procedures (see e.g. [GH93, KP96, GHMP95]).

Nevertheless all this progress did not suffice to allow the design of practically efficient symbolic elimination algorithms and in particular of algorithms which were able to compete in complexity aspects with their numerical counterparts. The traditional huge gap between symbolic and numeric polynomial equation solving methods remained open. Whereas numeric algorithms are very performant with respect to the number of arithmetical operations they require, they cannot be efficiently used in case of parametric, underdetermined, overdetermined or degenerate polynomial equation systems.

Symbolic algorithms are free from these restrictions but they are also too inefficient for any reasonable use in practice. A way out of this dilemma became appearent in [GHM^{+}98, GHH^{+}97] by a new interpretation of Newton’s classical method. Interpreting Newton’s approximation algorithm as a global procedure instead as a local one, allowed its use as a tool for data compression in the Kronecker–like elimination procedure of [GHMP95] ( which relied on the arithmetic circuit representation of polynomials). It turns out that Newton’s method is well adapted to exact symbolic computation if the correct (seminumerical) data structure is used. In this way a new algorithmic method finally emerged. This method is based on a combination of Kronecker’s and Newton’s ideas, and is able to distinguish dichotomically between ”well behaved” and ”badly behaved” polynomial equations systems. Moreover this algorithmic method is optimal for worst case (i.e. generic) systems.

Unlike Groebner basis algorithms this new method avoids any significant computational overflow during its execution. Roughly speaking, the new algorithms are always polynomial in the output size and even polynomial in the input size, if the given polynomial equation system is ”well behaved”.

This view of algorithmic algebraic geometry produced also the following new insight:

elimination polynomials are always ”smart”(i.e. not easy and not hard) to evaluate. How many variables they ever may contain, their evaluation complexity is always polynomial in their degree (whereas their number of monomials may be exponential in the number of their variables).

Although this insight is beyond of the scope of Kronecker’s way of thinking, the his formulation of the elimination method indicates that he might have intended to leave the door open for complexity issues.

A further development of this new algorithmic method was able to demonstrate its practical efficiency ( [GLS]). Moreover it turns out that the parameters which dominate the complexity of the new symbolic procedures determine also the efficiency of their numerical counterparts (at least if aspects of diophantine approximation are taken into account; see [CHMP]).

The new symbolic algorithms (and their numerical counterparts) have still a worst case complexity which is exponential in the (purely syntactical) input length. One may ask whether this fact is due to the algorithms and data structures employed or whether this is due to the intrinsic nature of geometric elimination.

The new results presented in this talk address this question. In order to discuss this point, let us turn back to our interpretation of Kronecker’s ideas behind geometric elimination. Kronecker’s elimination method (and theory) behaves well under specialization of the input equations. In fact, at any moment of the procedure one may consider the (parametric) input equations as given by their coefficients and these coefficients may be considered as purely algebraic objects, determined only by their algebraic relations. A given equation system may even be ”generalized”, i.e. the coefficients of the given input equations may be replaced by indeterminates and the discussion of the solvability of the generalized systems answers all questions about the solvability of the original system. This concept of specialization–generalization reveals an idea of universality (or uniformity) behind Kronecker’s elimination theory. This philosophical idea of universality became one of the corner stones of modern algebraic geometry and commutative algebra. Since we are (still) unable to think in a different way, we shall consider the input equations of a parametric elimination problem as functions which may be called by their values in the variables to be eliminated (black–box representation) or simply as being given by their coefficients (formal representation).

Any elimination algorithm we are able to imagine today starts from this kind of data. In other words, the black box representation constitutes today the most general way we may think the equations of our input system to be given. Of course each evaluation of the input equations has its costs and these costs may be measured by the size of a division–free arithmetic circuit which represents the input equations.

Any sufficiently uniform elimination procedure (avoiding ”unnecessary” branchings) becomes necessarily exponential in worst case, if the input equations are given in black–box representation.

This is a general and provable fact for any symbolic as well as for any numerical elimination procedure.

If an elimination procedure is used in order to assign ”coordinates” (i.e. in order to parametrize) suitable and easy–to–represent families of algebraic varieties the same conclusion holds, without any further restriction on the input representation (see [CHGP] and [HMPW98]).

Summing up, we may say: the by Kronecker initiated vision of elimination theory hides a concept of universality which obstructs general efficiency. The question what happens with complexity when we drop this universality requirement goes beyond the horizons of todays mathematical thinking and is equivalent to the question whether P = NP holds over the complex numbers (in the sense of the BSS complexity model; see [BCSS98]).

References

[BCSS98] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Real Complexity and Computation. Springer, 1998.

[CGH88] L. Caniglia, A. Galligo, and J. Heintz. Borne simple exponentielle pour les degrés dans le théorème des zéros sur un corps de charactéristique quelconque. C. R. Acad. Sci. Paris, 307:255–258, 1988.

[CGH89] L. Caniglia, A. Galligo, and J. Heintz. Some new effectivity bounds in computational geometry. In T. Mora, editor, Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-6, volume 357 of LNCS, pages 131–152. Springer, 1989.

[CHGP] D. Castro, J. Heintz, M. Giusti, G. Matera and L.M. Pardo. Data Structures and Smooth Interpolation Procedures in Elimination Theory. Manuscript, 1999.

[CHMP] D. Castro, K. Hägele, J.E. Morais, and L.M. Pardo. Kronecker’s and Newton’s approaches to solving : a first comparison. Manuscript, 1999.

[DFGS91] A. Dickenstein, N. Fitchas, M. Giusti, and C. Sessa. The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Applied Mathematics, 33:73–94, 1991.

[GH93] M. Giusti and J. Heintz. La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial. In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra, volume XXXIV of Symposia Matematica, pages 216–256. Cambridge University Press, 1993.

[GHH^{+}97] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for diophantine approximation. In Proceedings of MEGA’96. J. of Pure and Appl. Algebra, 117&118:277– 31, 1997.

[GHM^{+}98] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight–line programs in geometric elimination theory. J. of Pure and Appl. Algebra, 124:101–146, 1998.

[GHMP95] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast ? In G. Cohen, H. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11, volume 948 of LNCS, pages 205–231. Springer, 1995.

[GHS93] M. Giusti, J. Heintz, and J. Sabia. On the efficiency of effective Nullstellensätze. Computational Complexity, 3:56–95, 1993.

[GLS] M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial systems solving. Manuscript, 1999

[HMPW98] J. Heintz, G. Matera, L.M. Pardo and R. Wachenchauzer. The intrinsic complexity of parametric elimination methods. Electronic Journal of SADIO, vol. 1, no. 1, pp. 37-51 (1998) http://www.dc.uba.ar/sadio/ejs/

[KP96] T. Krick and L. M. Pardo. A computational method for diophantine approximation. In L. González-Vega and T. Recio, editors, Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, volume 143 of Progress in Mathematics, pages 193–254. Birkhäuser Verlag, 1996.

[Kro82] L. Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. reine angew. Math., 92:1–122, 1882.

[Mat] G. Matera. Some probabilistic algorithms for geometric elimination. to appear in Applicable Algebra in Engineering, Communication and Computation (AEECC Journal), 1999.

[MM82] E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., 46:305–329, 1982.

[MT97] G. Matera and J. M. Turull. The complexity space of elimination: upper bounds. In F.Cucker and M.Shub, editors, em Foundations of Comutational Mathematics. Proceedings of FoCM’97, pages 267– 267. Springer Verlag, 1997.