On using Lazard's projection in CAD construction (Q492024)

The concept of cylindrical algebraic decomposition (CAD) of the Euclidean \(n\)-space \(E^n\) has been introduced by \textit{G. E. Collins} in [Lect. Notes Comput. Sci. 33, 134--183 (1975; Zbl 0318.02051)]. It is closely related to the classical simplicial and CW-complexes of algebraic topology and has several applications. Given a finite set \(A\) of \(n\)-variate integral polynomials, a CAD is \(A\)-invariant if the polynomials of \(A\) are sign-invariant in each of the regions of the decomposition. The definition of CAD is based on a sort of induction on the dimension of the Euclidean space and a key point for \(A\)-invariant CAD construction is the choice of a \textit{projection} of the polynomials of \(A\), i.e.~a certain set of \((n-1)\)-variate integral polynomials. This paper is devoted to the investigation of \(A\)-invariant CAD construction focusing on the projection proposed by \textit{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)], whose proof presented some flaws. Despite these flaws, the authors show that Lazard's projection \(P_L(A)\) is valid when the set \(A\) is well-oriented with respect to \(P_L(A)\) (see Definition 3.4). In Section 2, the authors analyze the flaws of Lazard's projection and compare it with the projection introduced by \textit{S. McCallum} [J. Symb. Comput. 5, No. 1--2, 141--161 (1988; Zbl 0648.68054); in: Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993. Wien: Springer. 242--268 (1998; Zbl 0900.68279)] and with the Brown-McCallum projection [\textit{C. W. Brown}, J. Symb. Comput. 32, No. 5, 447--465 (2001; Zbl 0981.68186)], motivating the interest for a reinstatement of Lazard's method with several arguments (e.g., see Remark 3.2 and Section 4). Section 3 contains the main result (Theorem 3.1) which leads to the development of a CAD algorithm using Lazard's projection (Section 3.2). The rest of Section 3 is devoted to the proof of the main result, especially to the study of a technical lemma (Lemma 3.12) obtained as a consequence of an important theorem of Abhyankar and Jung to which a final Appendix is also devoted.