Combinatorial dimension theory of algebraic varieties (Q911659)

How can one compute the dimension of a projective algebraic subset, given by a system of equations? A first known method consists to think algebraically and to use the Hilbert function of the quotient ring. Unfortunately this method needs to construct a whole standard basis of the defining ideal of the variety from a given set of generators, and leads necessarily to a disastrous upper bound for the worst case complexity [cf. \textit{E. W. Mayr} and \textit{A. R. Meyer}, Adv. Math. 46, 305-329 (1972; Zbl 0506.03007) and \textit{M. Demazure}, Notes informelles de calcul formel, Prépublications Centre Math. Éc. Polytechnique, No.3, ``Le monoide de Mayr-Meyer'' and No.4, ``Le théorème de complexité de Mayr-Meyer (1985); see also Géométrie algébrique et applications, C. R. 2ième Conf. int., La Rabida/Espagne 1984, I, Trav. Cours 22, 35-38 (1987; Zbl 0626.20044)]. - Another way is to think geometrically and to cut the variety by linear subspaces. But it involves the costly introduction of generic coordinates. In the paper under review the author proposes an approach combining the combinatorial point of view (standard basis) and the geometric one (section/projection). He introduces two new characterizations of the dimension, which come in between the classical approaches in an interesting way, since this gives a new proof of the dimension theorem via their relationships with the classical definitions. Furthermore the author does not need a whole standard basis, which is a goal much too complicated, in order to extract a very partial useful information. Using this truncation idea the author gives an algorithm computing the dimension, the time and space complexity of which are polynomial in a suitable measure of the input data.