arxiv: 2605.04718 · v1 · submitted 2026-05-06 · 💻 cs.SC · math.AG

Recognition: unknown

On Minimum CADs for Algebraic Sets in Dimension Three

Lucas Michel

Authors on Pith no claims yet

Pith reviewed 2026-05-09 16:30 UTC · model grok-4.3

classification 💻 cs.SC math.AG

keywords cylindrical algebraic decompositionminimum CADalgebraic setssemi-algebraic setsrefinement orderreal algebraic geometrydimension three

0 comments

The pith

A class of subsets of R^3 always admits a minimum adapted CAD and includes all algebraic sets.

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

Cylindrical algebraic decompositions adapted to a family of semi-algebraic sets can vary in how finely they divide space. Earlier results established that a coarsest such decomposition always exists in dimensions one and two but fails to exist for some families in dimension three and higher. This paper isolates a class of subsets of R^3 for which a coarsest adapted CAD is guaranteed. The class is constructed so that it contains every algebraic set. The existence proof for this class supplies the first general guarantee that a minimum adapted CAD exists for any non-trivial collection of sets in three dimensions.

Core claim

There exists a class of subsets of R^3 such that every member of the class possesses a minimum (coarsest) cylindrical algebraic decomposition adapted to it, and this class contains all algebraic sets. This supplies the first positive existence theorem for minimum adapted CADs on a non-trivial class of sets.

What carries the argument

The partial order of refinement on the set of all CADs adapted to a given family F of semi-algebraic sets; the paper defines a specific class of families in R^3 for which this poset always has a least element.

If this is right

Every algebraic set in R^3 belongs to the class and therefore admits a minimum adapted CAD.
CAD algorithms working in three dimensions can target the coarsest possible output when the input family lies in the class.
The result separates families for which unnecessary cell divisions can be avoided from those where they cannot.
Membership in the class becomes a decision problem that, if solvable, would let algorithms produce minimal decompositions directly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Analogous classes could be sought in dimensions greater than three by relaxing the geometric conditions that force the class to work in R^3.
Practical CAD implementations might benefit from a membership test for the class, allowing them to return the coarsest decomposition without extra merging steps.
The existence of the class shows that non-existence in general dimension three arises only from particular configurations that the class excludes.

Load-bearing premise

The class is defined so that the refinement poset of adapted CADs has a minimum element for every member, including all algebraic sets, without excluding important cases by hidden restrictions.

What would settle it

An explicit algebraic set in R^3 whose collection of adapted CADs forms a poset under refinement that has no least element.

read the original abstract

Cylindrical Algebraic Decomposition (CAD) algorithms typically produce a decomposition adapted to a finite family of semi-algebraic sets $\mathcal{F}$ (i.e. every member of $\mathcal{F}$ is a union of cells). Different algorithms may produce different outputs, and introduce unnecessary cell divisions. Recent work by Michel, Mathonet, and Z\'ena\"idi in ISSAC 2024 formalised this issue by studying the refinement order on the set of all CADs adapted to $\mathcal{F}$ and analysing the existence of a minimum (coarsest) adapted CAD. It was shown that such a minimum adapted CAD always exists for subsets of $\mathbb{R}$ and $\mathbb{R}^2$, but not of $\mathbb{R}^n$ ($n \geqslant 3$) in general. It is natural to seek natural classes of subsets of $\mathbb{R}^n$ that admit a minimum adapted CAD. In this paper, we identify a class of subsets of $\mathbb{R}^3$ that contains all algebraic sets for which minimum adapted CADs do exist. This provides the first positive existence theorem for minimum CAD for a non-trivial class of sets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines a geometric class in R^3 where minimum adapted CADs exist and proves the class contains every algebraic set that has one.

read the letter

The key takeaway is that this paper gives the first positive existence result for minimum adapted CADs on a non-trivial class in three dimensions. Michel defines a class of subsets of R^3 via a geometric or topological condition on semi-algebraic sets, proves that every member admits a minimum adapted CAD, and then shows that the class includes all algebraic sets for which such a minimum exists. The argument builds directly on the refinement order formalized in the 2024 ISSAC paper and stays clear of the general non-existence counterexamples for n >= 3. The reasoning looks order-theoretic and non-circular, with the class defined independently before the inclusion step. This is a measured step forward from the earlier negative result. The main limitation is that membership in the class may still require checking properties close to those that determine the existence of a minimum CAD in the first place, so the result characterizes the sets that work without immediately supplying broad new families of algebraic sets where the minimum can be found without extra verification. The paper also gives few concrete algebraic examples inside the class, which would help assess how often the condition holds in practice. Readers working on CAD algorithms or real algebraic geometry will get value from the characterization. It deserves peer review because the existence claim is new and the construction is grounded in prior formal work.

Referee Report

0 major / 2 minor

Summary. The paper builds on the ISSAC 2024 formalization of the refinement order on CADs adapted to a finite family of semi-algebraic sets. While minimum (coarsest) adapted CADs exist in dimensions 1 and 2 but not in general for n >= 3, the authors define an independent class of subsets of R^3 via a geometric or topological condition on semi-algebraic sets. They prove that every member of this class admits a minimum adapted CAD and that the class contains all algebraic sets in R^3 for which such a minimum exists, yielding the first positive existence theorem for a non-trivial class in dimension 3.

Significance. If the central claims hold, the result is significant: it supplies a concrete, non-trivial positive existence theorem in a setting where general non-existence is known for dimension 3 and higher. The direct constructive or order-theoretic argument (rather than an appeal to fitted parameters or the general negative result) strengthens the contribution and may inform algorithmic work on CAD refinement or characterization of when minima exist.

minor comments (2)

The precise geometric or topological condition defining the class of subsets should be stated explicitly in the introduction or early section, with a forward reference to the theorem that all qualifying algebraic sets belong to it.
Notation for the refinement order and adapted CADs should be cross-referenced to the ISSAC 2024 paper to aid readers unfamiliar with the prior formalization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of its contributions, and the recommendation for minor revision. The significance noted by the referee aligns with our view that this provides the first positive existence result for minimum adapted CADs in dimension 3 for a non-trivial class containing all algebraic sets where such minima exist.

Circularity Check

0 steps flagged

Minor self-citation to prior foundational work; central result independent

full rationale

The paper cites its own prior ISSAC 2024 work (Michel, Mathonet, Zénaïdi) to recall the refinement order on adapted CADs and the known existence/non-existence results in dimensions 1-2 versus n≥3. This citation supplies the ambient order-theoretic framework but does not define the new class of subsets of R^3, nor does the existence proof for members of that class reduce to any fitted parameter or to the prior non-existence statement. The class is introduced via an independent geometric/topological condition on semi-algebraic sets; the proof that every member admits a minimum adapted CAD is presented as a direct constructive argument within the order. The further claim that the class contains all algebraic sets possessing a minimum CAD is a containment statement, not a re-derivation of existence. No self-definitional loop, fitted-input prediction, or ansatz smuggling occurs. The single self-citation is therefore minor and non-load-bearing for the paper's positive existence theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no free parameters, axioms, or invented entities are described. The result is an existence theorem extending prior formalization of CAD refinement order.

pith-pipeline@v0.9.0 · 5492 in / 955 out tokens · 51609 ms · 2026-05-09T16:30:53.340601+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 10 canonical work pages

[1]

D. Arnon. 1981.Algorithms for the geometry of semi-algebraic sets. PhD Thesis. University of Winconsin - Madison

1981
[2]

D. S. Arnon, G. E. Collins, and S. McCallum. 1988. An adjacency algorithm for cylindrical algebraic decompositions of three-dimenslonal space.Journal of Symbolic Computation5, 1 (1988), 163–187. doi:10.1016/S0747-7171(88)80011-7

work page doi:10.1016/s0747-7171(88)80011-7 1988
[3]

Binyamini and D

G. Binyamini and D. Novikov. 2019. Complex cellular structures.Annals of Mathematics190, 1 (2019), 145–248. doi:10.4007/annals.2019.190.1.3

work page doi:10.4007/annals.2019.190.1.3 2019
[4]

Bochnak, M

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

work page doi:10.1007/978-3-662-03718-8 1998
[5]

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

work page doi:10.1007/3- 1975
[6]

J. H. Davenport, A. F. Locatelli, and G. K. Sankaran. 2020. Regular cylindrical algebraic decomposition.Journal of the London Mathematical Society101, 1 (2020), 43–59. doi:10.1112/jlms.12257

work page doi:10.1112/jlms.12257 2020
[7]

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

work page doi:10.1007/s11786-010-0047-0 2010
[8]

Locatelli

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

2016
[9]

L. Michel. 2026. On some Exotic Cylindrical Algebraic Decompositions and Cells. arXiv:2601.09795 [math.AG] https://arxiv.org/abs/2601.09795

work page arXiv 2026
[10]

Michel, P

L. Michel, P. Mathonet, and N. Zenaïdi. 2024. On Minimal and Minimum Cylindrical Algebraic Decompositions. InProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation(Raleigh, NC, USA)(IS- SAC ’24). Association for Computing Machinery, New York, NY, USA, 316–323. doi:10.1145/3666000.3669704

work page doi:10.1145/3666000.3669704 2024
[11]

Michel, P

L. Michel, P. Mathonet, and N. Zénaïdi. 2026. Further results on Minimal and Minimum Cylindrical Algebraic Decompositions. arXiv:2601.09548 [cs.SC] https: //arxiv.org/abs/2601.09548

work page arXiv 2026
[12]

J. R. Munkres. 2018.Topology(2nd ed.). Pearson, New York, NY

2018
[13]

A. Nair, J. H. Davenport, and G. Sankaran. 2020. Curtains in CAD: Why Are They a Problem and How Do We Fix Them?. InMathematical Software – ICMS 2020, Anna Maria Bigatti, Jacques Carette, James H. Davenport, Michael Joswig, and Timo de Wolff (Eds.). Springer International Publishing, Cham, 17–26. doi:10. 1007/978-3-030-52200-1_2

2020
[14]

1991.Functional analysis(2nd ed.)

Walter Rudin. 1991.Functional analysis(2nd ed.). McGraw-Hill, New York, NY

1991
[15]

Strzeboński

A. Strzeboński. 2017. CAD Adjacency Computation Using Validated Numerics. In Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation(Kaiserslautern, Germany)(ISSAC ’17). Association for Computing Machinery, New York, NY, USA, 413–420. doi:10.1145/3087604.3087641

work page doi:10.1145/3087604.3087641 2017