Pith. sign in

REVIEW 6 minor 18 references

On Minimal and Minimum Cylindrical Algebraic Decompositions

T0 review · 0 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every semi-algebraic set in the plane has a unique coarsest adapted cylindrical algebraic decomposition, while in dimensions three and above some sets do not.

desk verdict Solid structural results on minimal CADs: minima in dimensions 1 and 2, a sharp counterexample in dimension 3, and a confluence characterization; minor presentation gaps only. read the letter →

arxiv 2411.13218 v1 pith:L7C47TAS submitted 2024-11-20 cs.SC

Lucas Michel , Pierre Mathonet , Naïm Zénaïdi This is my paper · ORCID
classification cs.SC MSC 14P1068W30
keywords cylindricalalgebraicdecompositionsemi-algebraicsetminimalCADminimumelementrefinementorderabstractreductionsystemconfluencerealgeometry
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks when a cylindrical algebraic decomposition (CAD) adapted to a semi-algebraic set can be simplified to a canonical coarsest one. It proves that every semi-algebraic set in $\mathbb{R}$ or $\mathbb{R}^2$ has a minimum adapted CAD, meaning all adapted decompositions share a single coarsest common refinement. In dimension three and above this fails: the authors exhibit explicit semi-algebraic sets, such as the 'trousers', with several distinct minimal adapted CADs and hence no minimum. They also show that the existence of a minimum is equivalent to confluence of a reduction system that merges redundant cells, and they use that system to give an algorithm that simplifies any adapted CAD to a minimal one.

What carries the argument

The engine of the analysis is the poset $\mathrm{CAD}(S)$ of adapted CADs under the refinement order, together with a tree representation of a CAD whose leaves are labelled by whether the cell lies in $S$ or in its complement. A reduction rule merges a section with its two neighbouring sectors when the three cells are all inside $S$ or all inside the complement, and when such a rule lifts geometrically it yields a coarser adapted CAD. The key structural tool is Corollary 3.5, which forces the section functions of two minimal CADs to agree on overlapping base cells, making gluing possible in dimensions one and two. Confluence of the resulting rewriting system is then shown to be equivalent to the existence of a minimum CAD.

What would settle it

Find two distinct minimal adapted CADs for a single semi-algebraic set in the plane, or show for the three-dimensional 'trousers' set that there exists an adapted CAD coarser than both of the two minimal CADs described in the paper; either observation would refute the corresponding theorem.

Watch

Extended reading notes

Core claim

The central discovery is a sharp dimension cut-off for canonical CAD simplification. For every semi-algebraic set $S$ in $\mathbb{R}$ and $\mathbb{R}^2$, any two minimal CADs adapted to $S$ must coincide (Theorem 4.1), so their common refinement is a minimum; the proof glues sections above adjacent base cells using the fact that section functions agree on overlaps (Corollary 3.5). For $n \geq 3$, the set $T = \{(x,y,z)\in\mathbb{R}^3 : (x\leq 0 \lor y\leq 0) \land z=0\} \cup \{(x,y,z)\in\mathbb{R}^3 : x>0,\ y>0,\ z=-x/2\}$ has two distinct minimal adapted CADs and therefore no minimum (Proposition 4.4), with a direct extension to all higher dimensions (Corollary 4.6). The paper concludes with Theorem 5.15: the poset of adapted CADs for $S$ has a minimum if and only if the associated reduction system is confluent.

Load-bearing premise

The proof that planar minimal decompositions coincide assumes that the cutting points and cutting curves of two minimal decompositions match wherever their regions overlap, and that the three neighbouring pieces around a cutting point always meet the corresponding region of the other decomposition; if that matching or those overlaps fail, the coarser decomposition used to force uniqueness cannot be built.

Editorial extensions

If this is right

  • In dimensions 1 and 2, any CAD algorithm's output can be post-processed to a unique coarsest adapted CAD, independent of the algorithm's choices.
  • In dimension 3 and higher, no canonical simplification exists for some semi-algebraic sets, so any choice of minimal CAD is arbitrary without extra criteria.
  • Minimal adapted CADs provide tight lower bounds on the number of cells needed to represent a given set, which can serve as benchmarks for CAD algorithms.
  • The reduction system yields an algorithmic route to a minimal CAD by repeatedly applying liftable reduction rules, avoiding exhaustive search over all coarser partitions.
  • The confluence criterion connects the existence of a minimum to a terminating rewriting system, placing the problem in the standard framework of abstract reduction systems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A practical implication the authors leave implicit is that for high-dimensional problems 'the' simplified CAD cannot be defined canonically, so CAD post-processing pipelines must either accept arbitrary minimal outputs or use additional user-chosen criteria to select among them.
  • The trousers construction suggests that failure of a minimum arises when a cell is a section in one CAD and part of a sector in another, forcing the glued function to become discontinuous; this may be a general mechanism for non-uniqueness.
  • One could test whether the confluence criterion is decidable for sets given by polynomial data, since the reduction system is terminating and admits only finitely many reduction rules at each stage.
  • The result mirrors the role of confluence in Gröbner basis theory, raising the question of whether a completion procedure could be developed for adapted CADs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies the poset CAD(S) of cylindrical algebraic decompositions adapted to a semi-algebraic set S, ordered by refinement. It proves that every adapted CAD can be reduced to a minimal one (Proposition 3.1), that uniqueness of minimal elements is equivalent to existence of a minimum (Proposition 3.3), and that in a minimal CAD the last-level section functions over each base cell are exactly the boundary of the corresponding slice S_x (Proposition 3.4). The main structural result is Theorem 4.1: for n=1 and n=2 every semi-algebraic S admits a minimum adapted CAD, while for n≥3 there exist explicit semi-algebraic sets, such as the 'trousers' T and its higher-dimensional versions, whose poset has no minimum (Proposition 4.4 and Corollary 4.6). Section 5 introduces CAD-tree reductions, gives an algorithm for computing minimal CADs, and proves that CAD(S) has a minimum if and only if its reduction system is confluent (Theorem 5.15).

Significance. If correct, these are clean structural results about a natural combinatorial object attached to any semi-algebraic set. The dimension threshold 1,2 versus ≥3 is surprising and well illustrated by the explicit trousers example. The paper is purely deductive: it uses no fitted parameters, no data, and no reliance on the authors' prior results; the proofs rest on standard facts such as Collins' theorem and Newman's lemma, together with the authors' explicit constructions. The confluence characterization in Theorem 5.15 connects CADs to abstract reduction systems in an elegant way and gives a useful conceptual counterpart to the Gröbner-basis theory of confluence. The reduction-based algorithm also provides a plausible post-processing framework. I specifically checked the delicate gluing step in the proof of Theorem 4.1: Corollary 3.5, together with the fact that ξ_{2i} is an interior point of the sector C'_{2j-1}, supplies the needed equality of section counts and restrictions, so the uniqueness argument is valid.

minor comments (6)
  1. [§4, proof of Theorem 4.1] The defining display of e𝒞₂ lists merged unions only for l=1,...,2u'_{2j-1} and thereby omits the top-sector union corresponding to l=2u'_{2j-1}+1; taken literally, e𝒞₂ is not a partition. The surrounding text and the argument clearly intend the full range, so this is a typographical error, but it should be corrected.
  2. [Corollary 4.6] In the definition of T_n, the second line of the union is written as a subset of R^3; it should be a subset of R^n. This is a typo but could confuse readers.
  3. [Example 4.8] The claim that neither B nor U admits a minimum CAD is asserted without proof: for B the construction is explicitly omitted, and for U the authors only say that the trousers construction applies after replacing -x/2 by -x/y. Since the main n≥3 counterexample is already fully established by Proposition 4.4 and Corollary 4.6, this omission does not threaten the central claim, but the statements should be proved or the example should be removed.
  4. [Example 5.11] The sentence 'Similar considerations show that Ψ₃₂ does not lift to a CAD reduction for 𝒞′' is very terse. The argument for the first reduction rule is spelled out; the second case should be expanded so that the minimality proof for the second trousers CAD is self-contained.
  5. [Proof of Proposition 4.4] The notation 'the function x ↦ -x/2 χ(x,y)' is formally incorrect, since the domain of the section is a cell in R^2 and the variable is (x,y); it should read (x,y) ↦ -x/2 χ(x,y). The same issue appears in Example 4.8.
  6. [Proof of Theorem 5.9] The final sentence says 'We finally show by induction that 𝒟ₖ ⪯ 𝒞ₖ for k∈{p,...,n}', but the induction is not written out. A few sentences explaining the inductive step would make the proof complete.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation is self-contained and deductive throughout.

full rationale

The paper's derivation chain is self-contained. The main results are proven directly from Collins's CAD theorem and the definition of the refinement poset: Proposition 3.1 is a finite descent argument, Proposition 3.4 and Corollary 3.5 derive equality of section data from minimality, and Theorem 4.1 glues those sections using nonempty overlaps, since the open interval C'_{2j-1} contains the section point xi_{2i}. The n >= 3 counterexamples rest on the explicitly defined trousers T, and the minimality of the two CADs C and C' is justified in Example 5.11 by showing, via Theorem 5.9, that the only tree reduction rules do not lift to CAD reductions. No fitted parameters, empirical data, or prior results of the present authors are used as load-bearing inputs; Theorem 5.15 follows from Theorem 5.9 and the standard Newman's lemma. The only caveats are presentational: Example 4.8 omits the analogous construction for B, and the displayed definition of eC_2 in Theorem 4.1 lists merged unions only up to l = 2u'_{2j-1} while the surrounding text intends the full range through l = 2u'_{2j-1} + 1. These do not affect the validity or circularity of the argument.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims rest on Collins' CAD existence theorem and Newman's lemma from rewriting theory, both standard. The paper also uses the standard fact that fibers of semi-algebraic sets are semi-algebraic, which is implicit in the CAD framework. No free parameters, no ad hoc axioms, and no invented entities appear.

assumptions (3)
  • standard math Collins' theorem: for any finite list of semi-algebraic sets S_1,...,S_p in R^n, there exists a CAD adapted to all of them simultaneously (Remark 2.3).
    Used to ensure CAD(S) is non-empty and to build a common finer CAD for two arbitrary adapted CADs in the proof of Theorem 5.15.
  • standard math Newman's lemma: a terminating and locally confluent abstract rewriting system is confluent (Lemma 5.14).
    Bridges local and global confluence of the CAD reduction system; cited from Baader and Nipkow [2].
  • domain assumption The fibers S_x = {y in R | (x,y) in S} of a semi-algebraic set are semi-algebraic subsets of R, and their boundaries are finite sets of algebraic points.
    Used in Proposition 3.4 to characterize the last-level sections of a minimal CAD; this follows from the definition of semi-algebraic sets and CADs, though not stated explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Minimal and Minimum Cylindrical Algebraic Decompositions." pith.science (2026). https://pith.science/paper/L7C47TAS

@misc{pith2026241113218,
  author       = {Pith},
  title        = {Pith review of: On Minimal and Minimum Cylindrical Algebraic Decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L7C47TAS}},
  note         = {Machine review of arXiv:2411.13218}
}
abstract

We consider cylindrical algebraic decompositions (CADs) as a tool for representing semi-algebraic subsets of $\mathbb{R}^n$. In this framework, a CAD $\mathscr{C}$ is adapted to a given set $S$ if $S$ is a union of cells of $\mathscr{C}$. Different algorithms computing an adapted CAD may produce different outputs, usually with redundant cell divisions. In this paper we analyse the possibility to remove the superfluous data. More precisely we consider the set CAD$(S)$ of CADs that are adapted to $S$, endowed with the refinement partial order and we study the existence of minimal and minimum elements in this poset. We show that for every semi-algebraic set $S$ of $\mathbb{R}^n$ and every CAD $\mathscr{C}$ adapted to $S$, there is a minimal CAD adapted to $S$ and smaller (i.e. coarser) than or equal to $\mathscr{C}$. Moreover, when $n=1$ or $n=2$, we strengthen this result by proving the existence of a minimum element in CAD$(S)$. Astonishingly for $n \geq 3$, there exist semi-algebraic sets whose associated poset of adapted CADs does not admit a minimum. We prove this result by providing explicit examples. We finally use a reduction relation on CAD$(S)$ to define an algorithm for the computation of minimal CADs. We conclude with a characterization of those semi-algebraic sets $S$ for which CAD$(S)$ has a minimum by means of confluence of the associated reduction system.

Figures

Figures reproduced from arXiv: 2411.13218 by the authors.

Figure 2
Figure 2. The CADs 𝒞 and 𝒞′ These CADs 𝒞 and 𝒞′ , which are obviously distinct, are adapted to T because T = 𝐶112 ∪𝐶122 ∪𝐶132 = 𝐶 ′ 112 ∪𝐶 ′ 212 ∪𝐶 ′ 312 ∪𝐶 ′ 322 ∪𝐶 ′ 332. A careful but direct inspection then shows that these CADs are indeed minimal. □ Remark 4.5. In order to show the minimality of 𝒞 and 𝒞′ in the previous proof by considering all the partitions that are strictly smaller than 𝒞 and 𝒞′ , one is led to investi… view at source ↗
Figure 1
Figure 1. The Trousers T Proposition 4.4. There is no minimum CAD adapted to the trousers T. Proof. We describe two distinct minimal CADs 𝒞 and 𝒞′ which are adapted to T and conclude by Proposition 3.3. For the first one, the partition 𝒞1 contains the unique cell 𝐶1 = R while 𝒞2 consists in the three cells 𝐶11 = 𝐶1 × (−∞, 0),𝐶12 = 𝐶1 × {0},𝐶13 = 𝐶1 × (0, +∞). The partition 𝒞3 is built with the nine cells 𝐶1𝑗1 = 𝐶1𝑗 × (−∞, 0),… view at source ↗
Figure 3
Figure 3. Semi-algebraic sets with two distinct minimal CADs [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The CADs 𝒞 and 𝒞′ and their associated CAD trees 5 and properly relabelling the other nodes (by subtracting 2 to the 1-prefixes of subtrees with prefixes 6 and 7). In order perform these operations in the general case, we make use of the 𝑘 th prefix map 𝑝𝑘 : Ø+∞ 𝑙=0 (N…
Figure 6
Figure 6. Figure 6: Tree(𝒞) and Tree(𝒞′ ) Remark 5.12. In the previous example we just had to show that two particular partitions were not CADs. This should be compared with the large number of elements in SSP(𝒞) and SSP(𝒞′ ) that would have been processed by direct inspection (see Remark…
Figure 7
Figure 7. Figure 7: Non-confluence of the trousers Definition 5.13. The reduction system CAD(𝑆) is globally con￾fluent if for all 𝒞, 𝒞, 𝒞′ ∈ CAD(𝑆) such that 𝒞 ∗← 𝒞 ∗→ 𝒞′ , there exists 𝒞 ∈ CAD(𝑆) such that 𝒞 ∗→ 𝒞 ∗← 𝒞′ . It is locally confluent if for all 𝒞, 𝒞, 𝒞′ ∈ CAD(𝑆) such that 𝒞 ← …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 9 canonical work pages

  1. [1]

    D. S. Arnon, G. E. Collins, and S. McCallum. 1998. Cylindrical Algebraic De- composition I: The Basic Algorithm. In Quantifier Elimination and Cylindrical Algebraic Decomposition, B. F. Caviness and J. R. Johnson (Eds.). Springer Vienna, Vienna, 136–151. https://doi.org/10.1007/978-3-7091-9459-1_6

    work page doi:10.1007/978-3-7091-9459-1_6 1998

  2. [2]

    Baader and T

    F. Baader and T. Nipkow. 1998.Term rewriting and all that. Cambridge University Press, USA. https://doi.org/10.1017/CBO9781139172752

    doi:10.1017/cbo9781139172752 1998

  3. [3]

    S. Basu, R. Pollack, and M.F. Coste-Roy. 2007. Algorithms in Real Algebraic Geometry. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-33099-2

    doi:10.1007/3-540-33099-2 2007

  4. [4]

    Bochnak, M

    J. Bochnak, M. Coste, and M-F. Roy. 1998. Real Algebraic Geometry . Springer. https://doi.org/10.1007/978-3-662-03718-8

    doi:10.1007/978-3-662-03718-8 1998

  5. [5]

    C. W. Brown. 2001. Improved Projection for Cylindrical Algebraic Decomposition. Journal of Symbolic Computation 32, 5 (2001), 447–465. https://doi.org/10.1006/ jsco.2001.0463

    work page arXiv 2001

  6. [6]

    C. W. Brown. 2001. Simple CAD Construction and its Applications. Journal of Symbolic Computation 31, 5 (2001), 521–547. https://doi.org/10.1006/jsco.2000. 0394

    work page doi:10.1006/jsco.2000 2001

  7. [7]

    C. W. Brown. 2017. Projection and Quantifier Elimination Using Non-Uniform Cylindrical Algebraic Decomposition. In Proceedings of the 2017 ACM on Inter- national Symposium on Symbolic and Algebraic Computation (Kaiserslautern, Germany) (ISSAC ’17). ACM, New York, NY, USA, 53–60. https://doi.org/10.1145/ 3087604.3087651

    arXiv 2017

  8. [8]

    Chen and M

    C. Chen and M. M. Maza. 2014. Quantifier Elimination by Cylindrical Algebraic Decomposition Based on Regular Chains. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Kobe, Japan) (ISSAC ’14). ACM, New York, NY, USA, 91–98. https://doi.org/10.1145/2608628.2608666

    arXiv 2014

Show all 18 references
  1. [9]

    G. E. Collins. 1975. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Lecture Notes in Computer Science (1975). https://doi. org/10.1007/3-540-07407-4_17

    1975 doi

  2. [10]

    J. H. Davenport, A. S. Nair, G. K. Sankaran, and A. K. Uncu. 2023. Lazard- Style CAD and Equational Constraints. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC ’23) . Association for Computing Machinery, New York, NY, USA, 218–2...

    2023

  3. [11]

    Huang, M

    Z. Huang, M. England, D. Wilson, J. H. Davenport, L. C. Paulson, and J. Bridge

  4. [12]

    D. Lazard. 2010. CAD and Topology of Semi-Algebraic Sets. Math. Comput. Sci. 4, 1 (2010), 93–112. https://doi.org/10.1007/S11786-010-0047-0

    2010 doi

  5. [13]

    Locatelli

    A. Locatelli. 2016. On the regularity of cylindrical algebraic decompositions . PhD Thesis. University of Bath

    2016

  6. [14]

    McCallum

    S. McCallum. 1998. An Improved Projection Operation for Cylindrical Algebraic Decomposition. In Quantifier Elimination and Cylindrical Algebraic Decomposition, Bob F. Caviness and Jeremy R. Johnson (Eds.). Springer Vienna, Vienna, 242–268. https://doi.org/10.1007/978-3-7091-9459-1_12

    1998 doi

  7. [15]

    piano movers

    J. T. Schwartz and M. Sharir. 1983. On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics 4, 3 (1983), 298–351. https://doi.org/10.1016/ 0196-8858(83)90014-3

    1983

  8. [16]

    D. Wilson. 2014. Advances in Cylindrical Algebraic Decomposition . PhD Thesis. University of Bath

    2014

  9. [107]

    https://doi.org/10.1007/978-3-319-08434-3_8

    doi

  10. [2014]

    In Intelligent Computer Mathematics

    Applying Machine Learning to the Problem of Choosing a Heuristic to Select the Variable Ordering for Cylindrical Algebraic Decomposition. In Intelligent Computer Mathematics. Springer International Publishing, Cham, 92–

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.