🔢 mathematics

On Minimum CADs for Algebraic Sets in Dimension Three

This paper establishes the first positive existence theorem for minimum Cylindrical Algebraic Decompositions by identifying a specific class of subsets in $\mathbb{R}^3$ , which includes all algebraic sets admitting such decompositions, thereby extending previous results that were limited to dimensions one and two.

Original authors: Lucas Michel

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lucas Michel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a messy room filled with various objects: books, clothes, toys, and furniture. Your goal is to organize this room into distinct, non-overlapping zones (like "book zone," "clothes zone," etc.) so that every single item belongs to exactly one zone.

In the world of mathematics, specifically Computational Real Algebraic Geometry, this "room" is a space (like a 3D volume), and the "objects" are shapes defined by mathematical equations (algebraic sets). The tool used to organize these shapes is called a Cylindrical Algebraic Decomposition (CAD).

Think of a CAD as a set of instructions for slicing the room into layers, then slicing those layers into columns, and so on, creating a grid of "cells." Every shape in your room must be made up of a perfect combination of these cells.

The Problem: Too Many Cuts

The paper starts by pointing out a common annoyance. Different algorithms (different organizers) might slice the room in different ways.

Organizer A might slice the room into 100 tiny pieces to be safe.
Organizer B might slice it into 50 pieces.
Organizer C might slice it into 200 pieces.

All of them successfully separate the objects, but some are doing unnecessary work. They are making "superfluous cell divisions"—cutting a piece of cake into 10 slices when 2 would have done the job.

Mathematicians want the Minimum CAD: the "coarsest" possible map. This is the version with the fewest number of pieces that still perfectly describes every shape. It's the most efficient, "no-waste" way to organize the room.

The Discovery: It's Harder in 3D

For a long time, mathematicians knew that for 1D (a line) and 2D (a flat plane), a perfect, minimum map always exists. No matter how messy the shapes are, there is always one "best" way to slice them up.

However, when they moved to 3D (three dimensions), things broke. Previous research (by the same author and colleagues in 2024) showed that in 3D, you can have a set of shapes where no single minimum map exists. It's like having a room where two different organizers both claim to have the "best" map, but their maps are completely different and neither can be improved to match the other. There is no single "gold standard" for these specific 3D messes.

The Solution: A Special Class of Shapes

This paper asks: "Is there any group of 3D shapes where a perfect, minimum map does exist?"

The author, Lucas Michel, says yes. He identifies a specific class of shapes that always allows for a minimum CAD.

He calls these shapes "Closed and Curtained." Here is what that means in plain English:

Closed: The shape includes its own edges and boundaries. It's a complete, solid object, not a shape with holes or missing edges.
Curtained: This is the key geometric rule. If you take a vertical line and poke it through the shape, the line either:
- Hits the shape in a few scattered points (like a few beads on a string), OR
- The entire line is inside the shape (like a solid pillar).
- Crucially: The line cannot hit the shape in a weird, infinite, scattered pattern that doesn't fill the whole line.

The Main Result (Theorem 1.1):
The paper proves that every finite collection of algebraic sets in 3D space admits a minimum CAD.

Why is this a big deal? Because "algebraic sets" (shapes defined by polynomial equations, like spheres, cubes, or complex curves) are the most common types of shapes used in this field. The paper shows that while arbitrary 3D shapes might be too chaotic to have a single best map, the specific shapes we actually care about in math and engineering (algebraic sets) are always well-behaved enough to have one.

How They Proved It

The author didn't just guess; he built a logical bridge:

He showed that algebraic sets are always "closed" and "curtained."
He proved that for any "closed and curtained" shapes in 3D, you can always merge the unnecessary slices together until you reach the absolute minimum.
He used a concept called confluence. Imagine you have two different ways to simplify a map. "Confluence" means that no matter which path you take to simplify, you will eventually arrive at the same final, simplest map. He proved that for these specific 3D shapes, the path always leads to the same destination.

The Limitations and Future

The paper is careful to note that this magic trick works specifically for 3D.

1D and 2D: We already knew minimum maps exist.
3D: This paper proves they exist for algebraic sets.
4D and higher: The author admits we don't know yet. The geometric rules that make 3D work (specifically how the "curtains" behave) might break down in 4D or 5D. The question of whether a minimum map exists for 4D algebraic sets remains an open mystery.

Summary

Think of this paper as finding a rule for a very complex puzzle.

The Puzzle: Organizing 3D shapes into the fewest possible pieces.
The Bad News: Some weird, abstract 3D shapes make this impossible (no single best solution).
The Good News: All the "real" shapes we use in math (algebraic sets) follow a specific rule (being closed and curtained) that guarantees a single, perfect, most-efficient solution exists.

This is the first time a positive proof has been found for a non-trivial class of sets in three dimensions, solving a problem that was previously thought to be a dead end.

Technical Summary: On Minimum CADs for Algebraic Sets in Dimension Three

Problem Statement
Cylindrical Algebraic Decomposition (CAD) is a fundamental algorithm in computational real algebraic geometry, used for quantifier elimination, symbolic computation, and SMT solving. A CAD is a partition of $\mathbb{R}^n$ into semi-algebraic cells such that a given finite family of semi-algebraic sets $\mathcal{F}$ is a union of these cells. Different CAD algorithms often produce different decompositions for the same input, frequently introducing unnecessary cell divisions.

The paper investigates the existence of a minimum CAD (a canonical, coarsest decomposition) adapted to a family $\mathcal{F}$ . While it was previously established that minimum CADs always exist for subsets of $\mathbb{R}$ and $\mathbb{R}^2$ , counterexamples in $\mathbb{R}^n$ for $n \geq 3$ demonstrated that such a minimum does not generally exist; specifically, some families admit multiple distinct minimal CADs that cannot be coarsened further, preventing the existence of a unique minimum. The central problem addressed is identifying natural classes of sets in higher dimensions (specifically $\mathbb{R}^3$ ) that guarantee the existence of a minimum CAD.

Methodology
The paper employs a formal framework based on the refinement order ( $\preceq$ ) on the set of all CADs adapted to $\mathcal{F}$ . A CAD $C$ is smaller than $D$ if every cell of $C$ is a union of cells of $D$ . The existence of a minimum CAD is equivalent to the confluence of the reduction system on the set of irreducible CADs.

The methodology proceeds through the following steps:

Restriction to Irreducible CADs: The authors define a subset $\text{CAD}_{n\text{-irr}}(\mathcal{F})$ consisting of CADs that are irreducible at the last level (no further reductions are possible at dimension $n$ ). They prove that the poset $(\text{CAD}(\mathcal{F}), \preceq)$ admits a minimum if and only if the reduction system on $\text{CAD}_{n\text{-irr}}(\mathcal{F})$ is confluent.
Topological Characterization: To ensure confluence, the paper introduces two topological properties for semi-algebraic sets: closedness and curtainedness.
- A set is curtained if, for every point in the projection space, the fiber is either finite or the entire line.
- The authors prove that all algebraic sets are closed and curtained.
Lifting Tree Reductions: The core technical challenge is determining when a combinatorial reduction on the CAD tree (merging cells) lifts to a valid geometric CAD reduction. This requires proving the continuity of functions formed by the union of section boundaries.
Topological Analysis of Planar Cells: A significant portion of the technical work involves proving that every CAD cell in the plane ( $\mathbb{R}^2$ ) is locally boundary connected. This property, combined with the closedness and curtainedness assumptions, ensures that the limits of adjacent cell boundaries behave predictably, allowing the "pasting lemma" to be applied to verify the continuity of merged functions.

Key Contributions and Results

Theorem 1.1 (Main Result): Every finite family of algebraic sets in $\mathbb{R}^3$ admits a minimum CAD.
Theorem 4.1 (Stronger Result): Every finite family of closed and curtained semi-algebraic sets in $\mathbb{R}^3$ admits a minimum CAD. Since algebraic sets satisfy these conditions, Theorem 1.1 follows.
Proof of Confluence: The paper provides a proof that the reduction system for closed and curtained sets in $\mathbb{R}^3$ is confluent. This is achieved by analyzing cases of tree reductions (where reduction indices $A$ and $B$ have equal or different lengths) and demonstrating that the resulting merged functions are continuous.
Topological Lemma: The paper establishes that every CAD cell in $\mathbb{R}^2$ is locally boundary connected (Theorem 3.20). This result is presented as a new topological property of CAD cells, which is crucial for verifying the continuity conditions required for the main proof.
Independence from Previous Criteria: The proof of Theorem 1.1 is independent of the general criterion (Theorem 6.3 of [11]), which relies on specific properties of the input family that are difficult to verify in this context. Instead, this work relies on confluence properties and topological arguments specific to dimension three.

Significance
The paper claims to provide the first positive existence theorem for minimum CADs for a non-trivial class of sets in dimension three or higher. Prior to this work, it was known that minimum CADs do not exist in general for $n \geq 3$ . By identifying the class of closed and curtained sets (which includes all algebraic sets) as admitting a minimum CAD, the paper delineates a boundary where the non-existence phenomena observed in general semi-algebraic sets do not occur.

The authors note that their techniques do not immediately generalize to $\mathbb{R}^n$ for $n \geq 4$ , as the local boundary connectedness of planar cells (Corollary 3.22) fails in higher dimensions. Consequently, the question of whether every finite family of algebraic sets in $\mathbb{R}^n$ ( $n \geq 4$ ) admits a minimum CAD remains open. The paper concludes that while the results are theoretical, they lay the groundwork for future work on developing effective criteria for lifting tree reductions and designing projection operators that directly produce minimum CADs.