McCallum, Scott; Parusiński, Adam; Paunescu, Laurentiu Validity proof of Lazard’s method for CAD construction. (English) Zbl 1419.14084 J. Symb. Comput. 92, 52-69 (2019). The authors provide a proof of Lazard’s method for cylindrical algebraic decomposition. This method was introduced by D. Lazard [in: Algebraic geometry and its applications. Collections of papers from Shreeram S. Abhyankar’s 60th birthday conference held at Purdue University, West Lafayette, IN, USA, June 1-4, 1990. New York: Springer-Verlag. 467–476 (1994; Zbl 0822.68118)]. It can be applied to any finite family of polynomials, without any assumption on the system of coordinates. The method therefore has wider applicability and may be more efficient than other projection and lifting schemes for cylindrical algebraic decomposition. However, the proof presented in the aforementioned article was not complete due to a gap in one of the key supporting results. In [S. McCallum and H. Hong, J. Symb. Comput. 72, 65–81 (2016; Zbl 1325.13026)] it was shown that Lazard’s projection is valid for cylindrical algebraic decomposition construction for so-called well oriented polynomial sets. The present article provides a complete validity proof of Lazard’s method using Lazard’s notion of valuation. The proof is based on the classical parametrized version of Puiseux’s theorem and basic properties of Lazard’s valuation. Reviewer: Nelly Villamizar (Swansea) Cited in 12 Documents MSC: 14P10 Semialgebraic sets and related spaces 68W30 Symbolic computation and algebraic computation 03C10 Quantifier elimination, model completeness, and related topics 14Q20 Effectivity, complexity and computational aspects of algebraic geometry Keywords:cylindrical algebraic decomposition; Lazard valuation; Puiseux with parameter theorem Citations:Zbl 0822.68118; Zbl 1325.13026 Software:QEPCAD PDFBibTeX XMLCite \textit{S. McCallum} et al., J. Symb. Comput. 92, 52--69 (2019; Zbl 1419.14084) Full Text: DOI arXiv References: [1] Abhyankar, S. S., On the ramification of algebraic functions, Am. J. Math., 77, 575-592, (1955) · Zbl 0064.27501 [2] Arnon, D. S.; Collins, G. E.; McCallum, S., Cylindrical algebraic decomposition I: the basic algorithm, SIAM J. Comput., 13, 4, 865-877, (1984) · Zbl 0562.14001 [3] Atiyah, M. F.; MacDonald, I. G., Introduction to Commutative Algebra, (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0175.03601 [4] Benedetti, R.; Risler, J.-J., Algebraic and Semi-Algebraic Sets, (1990), Hermann: Hermann Paris · Zbl 0694.14006 [5] Becker, T.; Weispfenning, V.; Kredel, H., Groebner Bases: A Computational Approach to Commutative Algebra, (1998), Springer: Springer New York, Corrected Second Printing [6] Bochnak, J.; Coste, M.; Roy, M.-F., Real Algebraic Geometry, (1998), Springer-Verlag: Springer-Verlag Berlin/Heidelberg · Zbl 0633.14016 [7] Bradford, R.; Davenport, J.; England, M.; McCallum, S.; Wilson, D., Truth table invariant cylindrical algebraic decomposition, J. Symb. Comput., 76, 1-35, (2016) · Zbl 1351.68314 [8] Brown, C. W., Improved projection for cylindrical algebraic decomposition, J. Symb. Comput., 32, 447-465, (2001) · Zbl 0981.68186 [9] Brown, C. W.; McCallum, S., On using bi-equational constraints in CAD construction, (Kauers, M., Proceedings of ISSAC’05, (2005), ACM Press: ACM Press New York), 76-83 · Zbl 1360.68925 [10] Brown, C. W.; McCallum, S., On delineability of varieties in CAD-based quantifier elimination with two equational constraints, (May, J., Proceedings of ISSAC’09, (2009), ACM Press: ACM Press New York), 71-78 · Zbl 1237.14067 [11] Brown, C.; Kahoui, M.; Novotni, D.; Weber, A., Algorithmic methods for investigating equilibria in epidemic modelling, J. Symb. Comput., 41, 1157-1173, (2006) · Zbl 1120.92034 [12] Busé, L.; Mourrain, B., Explicit factors of some iterated resultants and discriminants, Math. Comput., 78, 345-386, (2009) · Zbl 1200.13042 [13] (Caviness, B.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, (1998), Springer-Verlag) [14] Collins, G. E., Computer algebra of polynomials and rational functions, Am. Math. Mon., 80, 725-755, (1973) · Zbl 0275.68008 [15] Collins, G. E., Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition, Lecture Notes in Computer Science, vol. 33, 134-183, (1975), Springer-Verlag: Springer-Verlag Berlin, Reprinted in Caviness and Johnson (1998) [16] Collins, G.E., 1998. Quantifier elimination by cylindrical algebraic decomposition - twenty years of progress. In: Caviness and Johnson (1998); Collins, G.E., 1998. Quantifier elimination by cylindrical algebraic decomposition - twenty years of progress. In: Caviness and Johnson (1998) · Zbl 0900.03053 [17] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, J. Symb. Comput., 12, 299-328, (1991) · Zbl 0754.68063 [18] Danilov, V. I., Valuation, Online Encyclopaedia of Math, (2010), Springer-Verlag [19] Davenport, J. H.; Bradford, R.; England, M.; Wilson, D., Program Verification in the Presence of Complex Numbers etc, SYNASC’12, 83-88, (2012), IEEE [20] Gunning, H. C.; Rossi, C., Analytic Functions of Several Complex Variables, (2009), AMS Chelsea Publishing: AMS Chelsea Publishing Providence, Rhode Island · Zbl 1204.01045 [21] Hong, H., An improvement of the projection operator in cylindrical algebraic decomposition, (Watanabe, S.; Nagata, M., Proceedings of ISSAC’90, (1990), ACM Press: ACM Press New York), 261-264, Reprinted in Caviness and Johnson (1998) [22] Hong, H.; Liska, R.; Steinberg, S., Testing stability by quantifier elimination, J. Symb. Comput., 24, 161-187, (1997) · Zbl 0886.65087 [23] Jung, H. W.E., Darstellung der Funktionen eines algebraischen Koerpers zweier unabhaengigen Veraenderlichen x,y in der Umgebung einer Stelle x=a, y=b, J. Reine Angew. Math., 133, 289-314, (1908) · JFM 39.0493.01 [24] Kaltofen, E., Factorization of polynomials, (Computing, Supplementum 4: Computer Algebra - Symbolic and Algebraic Computation, (1982), Springer Verlag: Springer Verlag Vienna), 95-113 · Zbl 0519.68059 [25] Lazard, D., An improved projection for cylindrical algebraic decomposition, (Bajaj, C. L., Algebraic Geometry and Its Applications, (1994), Springer: Springer New York) · Zbl 0822.68118 [26] Lazard, D.; McCallum, S., Iterated discriminants, J. Symb. Comput., 44, 1176-1193, (2009) · Zbl 1206.13030 [27] Lazard, D., CAD and topology of semi-algebraic sets, Math. Comput. Sci., 4, 93-112, (2010) · Zbl 1205.14073 [28] (Lipman, J.; Teissier, B., Oscar Zariski: Collected Papers, Volume 4: Equisingularity on Algebraic Varieties, (1979), MIT Press: MIT Press Cambridge) [29] McCallum, S., An Improved Projection Operation for Cylindrical Algebraic Decomposition, (1984), University of Wisconsin-Madison, PhD thesis [30] McCallum, S., An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, J. Symb. Comput., 5, 141-161, (1988) · Zbl 0648.68054 [31] McCallum, S., 1998. An improved projection operation for cylindrical algebraic decomposition. In: Caviness and Johnson (1998); McCallum, S., 1998. An improved projection operation for cylindrical algebraic decomposition. In: Caviness and Johnson (1998) · Zbl 0900.68279 [32] McCallum, S., On projection in CAD-based quantifier elimination with equational constraint, (Dooley, S., Proceedings of ISSAC’99, (1999), ACM Press: ACM Press New York), 145-149 [33] McCallum, S., On propagation of equational constraints in CAD-based quantifier elimination, (Mourrain, B., Proceedings of ISSAC’01, (2001), ACM Press: ACM Press New York), 223-230 · Zbl 1356.68287 [34] McCallum, S.; Hong, H., On Lazard’s valuation and CAD construction, (2015) [35] McCallum, S.; Hong, H., On using Lazard’s projection in CAD construction, J. Symb. Comput., 72, 65-81, (2016) · Zbl 1325.13026 [36] Parusiński, A.; Paunescu, L., Arcwise analytic stratification, Whitney fibering conjecture and Zariski equisingularity, Adv. Math., 309, 254-305, (2017) · Zbl 1375.32048 [37] Parusiński, A.; Rond, G., The Abhyankar-Jung theorem, J. Algebra, 365, 29-41, (2012) · Zbl 1268.13008 [38] Pawłucki, W., Le théorème de Puiseux pour une application sous-analytique, Bull. Pol. Acad. Sci. Math., 32, 555-560, (1984) · Zbl 0574.32010 [39] Schwartz, J.; Sharir, M., On the “piano-movers” problem II: general techniques for computing topological properties of real algebraic manifolds, Adv. Appl. Math., 4, 298-351, (1983) · Zbl 0554.51008 [40] Weispfenning, V., Simulation and optimization by quantifier elimination, J. Symb. Comput., 24, 189-208, (1997) · Zbl 0883.68075 [41] Zariski, O., Studies in equisingularity I. Equivalent singularities of plane algebroid curves, Am. J. Math., 87, 507-536, (1965), Reprinted in Lipman and Teissier (1979) · Zbl 0132.41601 [42] Zariski, O., Studies in equisingularity II. Equisingularity in codimension 1 (and characteristic zero), Am. J. Math., 87, 972-1006, (1965), Reprinted in Lipman and Teissier (1979) · Zbl 0146.42502 [43] Zariski, O.; Samuel, P., Commutative Algebra Volume II, (1960), Springer-Verlag: Springer-Verlag New York 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.