zbMATH — the first resource for mathematics

Thom’s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets. (English) Zbl 0689.14006
Summary: Thom’s lemma, a very simple and basic result in real algebraic geometry, and explained in section 1, has a lot of interesting computational consequences. We shall outline two of these.
The first one is the fact that a real root \(\xi\) of a polynomial P of degree n with real coefficients may be distinguished from the other real roots of P by the signs of the derivatives \(P^{(i)}\) of P at \(\xi\), \(i=1,...,n-1\). This offers a new possibility for the coding of real algebraic numbers and for computation with these numbers (see section 2).
The second is based on a generalisation of Thom’s lemma to the case of several variables. It gives, after a linear change of coordinates, a cylindric algebraic decomposition of a semialgebraic set where the incidence relation between the cells is easily obtained (see section 3).

14Pxx Real algebraic and real-analytic geometry
94B40 Arithmetic codes
Full Text: DOI
[1] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, J. computation systems sci, 32, 251-264, (1986) · Zbl 0634.03031
[2] Bochnak, J.; Coste, M.; Roy, M.-F., Geométrie algébrique réelle, () · Zbl 0633.14016
[3] Collins, G., Quantifier elimination for real closed fields by cylindric algebraic decomposition, (), 134-183
[4] Coste, M., Ensembles semi-algébrique, (), 109-138
[5] Efroymson, G., Substitution in Nash functions, Pac. J. math, 54, 109-138, (1976)
[6] Lojasiewicz, S., Ensembles semi-anatytiques, Lecture notes, L.H.E.S., (1965)
[7] Loos, R., Generalized polynomial remainder sequences, () · Zbl 0577.13001
[8] Roy, M.-F., Computation of the topology of a real algebraic curve, Congress on “computational geometry and topology and computation in teaching mathematics”, (1987), Seville (to appear)
[9] Roy, M.-F. Szpirglas, A. (In prep.). Complexity of computation on real algebraic numbers. · Zbl 0723.68054
[10] Schwartz, J.T.; Sharir, M., On the “piano mover’s” problem, I1. advan. applied math, 4, 298-351, (1983) · Zbl 0554.51008
[11] Sylvester, A.J., On a theory of syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm’s function, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.