On some Exotic Cylindrical Algebraic Decompositions and Cells
Lucas Michel · 2026
Read On some Exotic Cylindrical Algebraic Decompositions and Cells by Lucas Michel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09795.txt.
Introduction
Lucas Michel builds counterexamples in a theory used to carve space into simple cells. His 2026 arXiv paper constructs exotic cylindrical algebraic decompositions and cells. Such decompositions, enriched with topological properties, serve logic, algorithm design, and robot motion planning.
They also help study the topology of semi-algebraic sets. Michel gives explicit examples that refute several conjectures and open questions of J. H. Davenport and others. Counterexamples prune false hopes from the map of a theory like this one. They show exactly which nice properties a decomposition of this kind cannot always have in practice.
Catalog record
| CREATOR | Lucas Michel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-09795
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On some Exotic Cylindrical Algebraic Decompositions and Cells Lucas Michel Abstract Cylindrical Algebraic Decompositions (CADs) endowed with additional topological properties have found applications beyond their original logical setting, including algorithmic optimizations in CAD construction, robot motion planning, and the algorithmic study of the topology of semi-algebraic sets. In this paper, we construct explicit examples of CADs and CAD cells that refute several conjectures and open questions of J. H. Davenport, A. Locatelli, and G. K. Sankaran concerning these topological assumptions. \newnumbered assertionAssertion \newnumbered conjectureConjecture \newnumbered definition[theorem]Definition \newnumbered hypothesisHypothesis \newnumbered remark[theorem]Remark \newnumbered noteNote \newnumbered observationObservation \newnumbered problemProblem \newnumbered questionQuestion \newnumbered algorithmAlgorithm \newnumbered exampleExample \newunnumbered notationNotation \simpleequations \classno 14P10 (primary), 68W30, 14Q30 (secondary) \extraline The author is supported by the FNRS-DFG PDR Weaves (SMT-ART) grant 40019202. 1 Introduction Cylindrical Algebraic Decomposition (CAD) is a cornerstone tool in real algebraic geometry and underlies classical algorithms for Quantifier Elimination over real closed fields (QE) [ 8 ] . Beyond its foundational role in QE, CADs with strong topological properties have proved useful in various contexts. For instance, they play a role in algorithmic optimizations within CAD construction itself (see the clustering method [ 1 ] , [ 3 ] ), visualization of semi-algebraic sets, in applications such as the Piano Mover’s Problem (see [ 13 ] ), and in the study of the topology of semi-algebraic sets (see for instance [ 9 ] or [ 10 ] ). In this setting, several natural topological assumptions on CADs and their cells (such as being closure-finite, well-bordered, or locally boundary connected, …) frequently appear as convenient working hypotheses. These properties concern, in particular, CAD cells adjacencies, the behaviour of the boundaries of CAD cells and the way cells are arranged within the decomposition. A deeper analysis of these conditions is not only of theoretical interest but also of practical relevance: if a CAD (or a CAD cell) is known to satisfy certain topological properties, then some heavy computations can be safely avoided when designing or implementing algorithms. However, despite their frequent use, a precise understanding of these topological properties and their interrelations remains incomplete in the literature. From a topological point of view, a CAD cell of \mathbb{R}^{n} is rather simple, since it is a topological ball (also called a cell), that is, a singleton or a set homeomorphic to an open ball of some dimension less than or equal to n (see, for instance, Proposition 5.3 of [ 5 ] ). Note that this number is the dimension of the considered CAD cell. However, when considering its boundary, it is common to visualize a regular CAD cell (see below) in \mathbb{R}^{2} or \mathbb{R}^{3} and to assume that its closure behaves nicely. Similarly, one usually illustrates CADs of \mathbb{R}^{2} or \mathbb{R}^{3} with strong topological properties (for instance, a closure-finite and well-bordered CAD). In such examples, the closure of each cell can typically be expressed as a union of cells of the same CAD, and the dimension of the boundary decreases by exactly one compared to that of the original cell. This intuition is misleading: the topology of the boundary of CAD cells, and their arrangement within their ambient CAD can be more intricate (especially when n is large) as we will see below. In this paper, we construct explicit examples of CADs and CAD cells in \mathbb{R}^{4} that challenge or refute some conjectures and open questions related to these topological aspects (see [ 9 ] and the thesis [ 11 ] ). In Section 2 , we construct a family of CADs in \mathbb{R}^{4} that are closure-finite but not well-bordered. In Section 3 , we construct exotic examples of CAD cells in \mathbb{R}^{4} that exhibit topological phenomena that do not appear for CAD cells in lower-dimensional Euclidean spaces. 1.1 Notation and framework For every positive integer n\in\mathbb{N}^{*} , we consider CADs of \mathbb{R}^{n} with respect to a fixed variable ordering. Since the cells of such CADs are defined inductively from cells of CADs of \mathbb{R}^{k} ( k\leq n ) which are indexed by k -tuples, it is convenient to adopt the tuple notation of [ 12 ] and use the \odot shorthand of [ 6 ] to deal easily with sectors and sections. More precisely, we identify any k -tuple I=(i_{1},\ldots,i_{k})\in\mathbb{N}^{k} with the corresponding word i_{1}\ldots i_{k} . We say that I is odd (resp. even) if i_{k} is odd (resp. even). We denote by \varepsilon the empty tuple, which corresponds to the empty word. For j\in\mathbb{N} , we denote by I:j the k+1 tuple (i_{1},\ldots,i_{k},j) . For every subset S\subseteq\mathbb{R}^{n} , we denote (following the notation of [ 7 ] ) by \mathcal{S}^{0}(S) the ring of continuous semi-algebraic functions from S to \mathbb{R} . For f\in\mathcal{S}^{0}(S) , the section S\odot\{f\} with base S and bound f is simply the graph of f , that is S\odot\{f\}=\{(\textbf{x},y)\in\mathbb{R}^{n+1}\;|\;\textbf{x}\in S,y=f(\textbf{x})\}. For l\in\mathcal{S}^{0}(S)\cup\{-\infty\} and u\in\mathcal{S}^{0}(S)\cup\{+\infty\} such that l<u on S , the sector S\odot(l,u) with base S , lower bound l and upper bound u , is the set S\odot(l,u)=\{(\textbf{x},y)\in\mathbb{R}^{n+1}\;|\;\textbf{x}\in S,l(\textbf{x})<y<u(\textbf{x})\}. Similarly to [ 9 ] , we denote by \overline{S} the closure of S in the Euclidean topology, and by \partial S=\overline{S}\setminus S its (cell) boundary. Note that this should not be confused with the usual topological frontier of S , which is defined as the closure of S minus the interior of S . Recall that S is locally boundary connected if, for every p\in\partial S , there exists \delta>0 such that, for all \varepsilon\in(0,\delta) , the intersection \mathbb{B}(p,\varepsilon)\cap S is connected, where \mathbb{B}(p,\varepsilon) denotes the open ball in \mathbb{R}^{n} of radius \varepsilon and centred at p . Definition 1.1 . A cylindrical algebraic decomposition ( CAD ) of \mathbb{R}^{n} is a sequence \mathscr{C}=(\mathscr{C}_{1},\ldots,\mathscr{C}_{n}) such that for all k\in\{1,\ldots,n\} , the set \mathscr{C}_{k}=\left\{C_{i_{1}\cdots i_{k}}|\forall j\in\{1,\ldots,k\},i_{j}\in\{1,\ldots,2u_{i_{1}\cdots i_{j-1}}+1\}\right\} is a finite semi-algebraic partition of \mathbb{R}^{k} defined inductively by the following data: 1. there exist a natural number u_{\varepsilon}\in\mathbb{N} and real algebraic numbers \xi_{2}<\xi_{4}<\cdots<\xi_{2u_{\varepsilon}} (possibly none if u_{\varepsilon}=0 ) that define exactly all cells of \mathscr{C}_{1} by \displaystyle C_{2j} \displaystyle=\{\xi_{2j}\},\quad \displaystyle(1\leq j\leq u_{\varepsilon}) \displaystyle C_{2j+1} \displaystyle=(\xi_{2j},\xi_{2(j+1)}),\quad \displaystyle(0\leq j\leq u_{\varepsilon}) with the convention that \xi_{0}=-\infty and \xi_{2u_{\varepsilon}+2}=+\infty ; 2. for each cell C_{I}\in\mathscr{C}_{k} ( k<n ), there exist a natural number u_{I}\in\mathbb{N} and \xi_{I:2},\xi_{I:4},\ldots,\xi_{I:2u_{I}}\in\mathcal{S}^{0}(C_{I}) (possibly none if u_{I}=0 ) with \xi_{I:2}<\xi_{I:4}<\ldots<\xi_{I:2u_{I}} on C_{I} , that define exactly all cells of \mathscr{C}_{k+1} by \displaystyle C_{I:2j} \displaystyle=C_{I}\odot\{\xi_{I:2j}\},\hskip 9.24994pt \displaystyle(1\leq j\leq u_{I}) \displaystyle C_{I:2j+1} \displaystyle=C_{I}\odot(\xi_{I:2j},\xi_{I:2(j+1)}),\hskip 9.24994pt \displaystyle(0\leq j\leq u_{I}) with the convention that \xi_{I:0}=-\infty and \xi_{I:2u_{I}+2}=+\infty . We say that the element C_{I} of \mathscr{C}_{k} is a CAD cell of index I . For all k\in\{1,\ldots,n\} , we denote by \pi_{k}:\mathbb{R}^{n}\to\mathbb{R}^{k} the projection onto the first k coordinates, defined by \pi_{k}(x_{1},\ldots,x_{n})=(x_{1},\ldots,x_{k}) , and use the same notation for its natural successive extensions to subsets of \mathbb{R}^{n} and to families of subsets of \mathbb{R}^{n} . In particular, for every CAD \mathscr{C} of \mathbb{R}^{n} , we have \pi_{k}(\mathscr{C}_{n})=\mathscr{C}_{k} for every k\in\{1,\ldots,n\} . For this reason, we usually identify \mathscr{C} with \mathscr{C}_{n} when the context is clear. In general, one can refer to a CAD cell C of \mathbb{R}^{n} without referring to an ambient CAD, nor its index. If n=1 , then C is either a singleton, or an open interval (with real-algebraic bounds). If n>1 ,