Proofs: Cylindrical algebraic decomposition

The plane CAD is cylindrical, sign-invariant and computed exactly, and it stops full

This proof shows: correctness, termination.

Let $F = \{f_1, \ldots, f_m\} \subset \mathbb{Q}[x, y]$. View each $f \ne 0$ as a polynomial in $y$ over $\mathbb{Q}[x]$. Its content $\operatorname{cont}(f) \in \mathbb{Q}[x]$ is the gcd of its coefficients and its primitive part is $\operatorname{prim}(f) = f / \operatorname{cont}(f)$. Let $T = \prod_f \operatorname{prim}(f)$, and let $S$ be the primitive squarefree part of $T$, $S = T / \gcd(T, \partial T / \partial y)$ made primitive. Let $D = \operatorname{res}_y(S, \partial S / \partial y)$ and let $P$ be the squarefree part of $\prod_f \operatorname{cont}(f) \cdot \operatorname{LC}(S) \cdot D$, where $\operatorname{LC}$ is the leading coefficient in $y$. These are the objects of line L1. By Gauss's lemma, $S$ has exactly the irreducible factors of $T$ that involve $y$, each once, and it has no factor in $\mathbb{Q}[x]$ alone. Since $S$ is squarefree over $\mathbb{Q}(x)$, it has no common factor with $\partial S/\partial y$, so $D \ne 0$ when $\deg_y S \ge 1$.

Lemma 1 (where $F$ vanishes). Let $f \in F$ be nonzero, and suppose $f(x_0, y_0) = 0$ at a real point. Then $\operatorname{cont}(f)(x_0) = 0$ or $S(x_0, y_0) = 0$. Moreover, $S(x_0, \cdot)$ is never the zero polynomial.

Proof. If $\operatorname{cont}(f)(x_0) \ne 0$ then $\operatorname{prim}(f)(x_0, y_0) = 0$. Every irreducible factor of $\operatorname{prim}(f)$ divides $T$ and therefore $S$, so $\operatorname{prim}(f)$ divides $S^k$ for some $k$. Hence $S(x_0, y_0)^k = 0$. The coefficients of $S$ have gcd 1 in $\mathbb{Q}[x]$, so they have no common complex root, and $S(x_0, \cdot) \ne 0$. $\square$

Lemma 2 (delineability). Let $k = \deg_y S \ge 1$, and let $I$ be an open interval on which $\operatorname{LC}(S)$ and $D$ have no zero. Then there are $r \ge 0$ and continuous functions $\theta_1 < \cdots < \theta_r$ on $I$ such that, for every $x \in I$, the real roots of $S(x, \cdot)$ are exactly $\theta_1(x), \ldots, \theta_r(x)$.

Proof. For $x \in I$, $S(x, \cdot)$ has degree $k$, and its derivative has degree $k - 1$ with leading coefficient $k \operatorname{LC}(S)(x) \ne 0$. So the resultant specializes: $\operatorname{res}(S(x, \cdot), \partial_y S(x, \cdot)) = D(x) \ne 0$. Then $S(x, \cdot)$ has $k$ distinct complex roots. Fix $x_0 \in I$ and choose disjoint closed discs around these roots, each disc symmetric under complex conjugation when its center is real, and not meeting the real axis when its center is not real. The roots of a polynomial of constant degree depend continuously on its coefficients. So for $x$ near $x_0$ each disc contains exactly one root of $S(x, \cdot)$. A disc that misses the real axis contains no real root. A symmetric disc contains a real root: if its only root $z$ were not real, then $\bar z$ would be a second root in the same disc. So the number of real roots is locally constant, hence constant on the connected set $I$, and each ordered real root stays in its disc, which makes it continuous. Distinct roots never meet, so the order $\theta_1 < \cdots < \theta_r$ is strict on all of $I$. $\square$

Lemma 3 (sign-invariance over an open column). Let $I$ be a connected component of $\mathbb{R}$ minus the real roots of $P$. Then for every $f \in F$, $f$ has a constant sign on each sector $\{(x, y) : x \in I,\ \theta_j(x) < y < \theta_{j+1}(x)\}$ (with $\theta_0 = -\infty$, $\theta_{r+1} = +\infty$) and on each section $\{(x, \theta_j(x)) : x \in I\}$.

Proof. Every root of $\operatorname{cont}(f)$, $\operatorname{LC}(S)$ and $D$ is a root of $P$, so none of these vanishes on $I$, and Lemma 2 applies (with $r = 0$ when $\deg_y S = 0$). By Lemma 1, the zeros of $f$ over $I$ lie on the graphs of the $\theta_j$. A sector is connected, being homeomorphic to $I$ times an open interval through the continuous $\theta_j$. Since $f$ is continuous with no zero on a sector, its sign is constant there.

For a section, write $S = h_1 \cdots h_s$ with distinct irreducible $h_l$. At each $x \in I$, the root $\theta_j(x)$ is simple, so it is a root of exactly one $h_l(x, \cdot)$. The sets $I_l = \{x \in I : h_l(x, \theta_j(x)) = 0\}$ are closed in $I$, disjoint and cover $I$, so by connectedness a single $h = h_l$ vanishes along the whole section. If $h$ divides $\operatorname{prim}(f)$, then $f$ is zero on the section. Otherwise suppose $f(x, \theta_j(x)) = 0$ at some $x \in I$. Since $\operatorname{cont}(f)(x) \ne 0$, some irreducible factor $h' \ne h$ of $\operatorname{prim}(f)$ vanishes there. That factor is one of the $h_l$, which contradicts uniqueness. So $f$ has no zero on the section, which is connected, and its sign is constant. $\square$

Lemma 4 (stacks over a point). For a real $\alpha$, let $\beta_1 < \cdots < \beta_r$ be the real roots of $S(\alpha, \cdot)$. Then each $f \in F$ has a constant sign on each open interval $\{\alpha\} \times (\beta_j, \beta_{j+1})$ and on each point $(\alpha, \beta_j)$.

Proof. If $\operatorname{cont}(f)(\alpha) = 0$, then $f(\alpha, \cdot) = 0$ and its sign is $0$ everywhere on the line. Otherwise, by Lemma 1, every real zero of $f(\alpha, \cdot)$ is some $\beta_j$, so $f(\alpha, \cdot)$ has no zero on the open intervals and keeps its sign on each. $\square$

Lemma 5 (exact computation). The implementation computes the roots, the stacks and the sign vectors exactly.

Proof. (a) Isolation. For a squarefree $p \in \mathbb{Q}[x]$, every real root lies in $(-B, B)$ with $B = 1 + \max_i |p_i / \operatorname{LC}(p)|$ (Cauchy). Sturm's theorem counts the distinct roots in $(a, b)$ at non-root endpoints. Bisection keeps the endpoints off the roots, since a midpoint that is a root is moved. It stops: once the intervals are shorter than the smallest gap between roots, each holds at most one root. The output is sorted, disjoint and complete, with one root per interval.

(b) Real algebraic numbers. A number $\alpha$ is held as a squarefree $p$ with $p(\alpha) = 0$ and an interval $(a, b)$ that contains no other root of $p$, with $p(a), p(b) \ne 0$, or as an exact rational. For a section column, $p$ is the smallest squarefree factor of a projection polynomial that changes sign on the isolating interval of $P$. Its roots are roots of $P$, so its only root there is $\alpha$. Refinement halves the interval by the sign of $p$ at the midpoint and keeps the invariant. Then is_zero(q) returns true exactly when $q(\alpha) = 0$. If the interval enclosure of $q$ on $[a, b]$ misses $0$, then $q(\alpha) \ne 0$. Otherwise let $g = \gcd(p, q)$. Since $p(\alpha) = 0$, we have $q(\alpha) = 0$ if and only if $g(\alpha) = 0$, and $g$, a divisor of the squarefree $p$, has at most one root in $(a, b)$, a simple one. So $g(\alpha) = 0$ exactly when $g$ changes sign on $(a, b)$. Then $p$ is replaced by $g$ or by $p / g$, whichever vanishes at $\alpha$, and the invariant holds. If $q(\alpha) \ne 0$, the enclosures shrink to $q(\alpha)$ as the interval shrinks, so sign_of stops with the right sign.

(c) Arithmetic in $\mathbb{Q}(\alpha)$. Reduction modulo $p$ commutes with evaluation at $\alpha$, since $x \mapsto \alpha$ defines a ring homomorphism $\mathbb{Q}[x]/(p) \to \mathbb{R}$. The decisions taken (is a leading coefficient zero at $\alpha$?) are exact by (b). An inverse is taken only for $q$ with $q(\alpha) \ne 0$. Removing $g = \gcd(p, q)$ from $p$ keeps $\alpha$ as a root, because $g(\alpha) \ne 0$. Then the extended Euclidean algorithm gives $s$ with $sq \equiv 1 \bmod p$, so $s(\alpha) = 1/q(\alpha)$. So the trimmed polynomials, remainders, monic gcds and derivatives computed over $\mathbb{Q}(\alpha)$ evaluate at $\alpha$ to those of the evaluated inputs in $\mathbb{R}[y]$. In particular, the stack polynomial $g$ evaluates to the monic squarefree part of $S(\alpha, y)$, and the Sturm sequence built from $g$ is the Sturm sequence of the real polynomial $g(\alpha, \cdot)$. Dividing by a monic multiple of $B$ leaves the remainder unchanged.

(d) Sections. As a polynomial in $y$ with coefficients in $\mathbb{Q}[x]/(p)$, $g$ has leading coefficient exactly $1$. With $p$ monic, Poisson's formula gives $\operatorname{res}_x(p(x), g(x, y)) = \prod_{p(\alpha') = 0} g(\alpha', y)$. This is a product of monic polynomials in $y$, so it is nonzero, has degree $\deg p \cdot \deg_y g$, and is recovered exactly by interpolation at that many points plus one. Every root of $g(\alpha, \cdot)$ is a root of this norm. Its squarefree part $N_s$ is isolated by (a). In each interval, which holds one root of $N_s$ and has endpoints that are not roots of $g(\alpha, \cdot)$, the Sturm count of $g(\alpha, \cdot)$ is $0$ or $1$. Keeping the intervals with count $1$ gives exactly the real roots of $S(\alpha, \cdot)$, in increasing order, with rational sector samples between them. For a rational $\alpha$, the squarefree part of $S(\alpha, y) \in \mathbb{Q}[y]$ is isolated directly.

(e) Signs. At a rational $y_0$, the sign of $f(\alpha, y_0)$ is sign_of of a polynomial in $\mathbb{Q}(\alpha)$, which is exact by (b). At a section $\beta$, the unique root of $N_s$ and of $g(\alpha, \cdot)$ in $(c, d)$: $f(\alpha, \beta) = 0$ if and only if $G = \gcd(f(\alpha, \cdot), g(\alpha, \cdot))$ has a root in $(c, d)$. $G$ divides a squarefree polynomial, so its Sturm count decides this. Otherwise $f(\alpha, \beta) \ne 0$, and the box enclosures of $f$ shrink to it: $\alpha$ is refined by (b), and $\beta$ is refined by bisection of $N_s$, whose only root in the interval is $\beta$. So the loop stops with the correct sign. $\square$

Theorem. cad(F) terminates and returns a cylindrical decomposition of $\mathbb{R}^2$ into connected cells, each with the correct sign vector of $F$, and every $f \in F$ has a constant sign on every cell.

Proof. Columns. By Lemma 5(a), lines L2 and L3 find all real roots $\alpha_1 < \cdots < \alpha_k$ of $P$. Each sector sample is the midpoint between the right end of one isolating interval and the left end of the next, or a point beyond the extreme intervals. It lies strictly between consecutive roots and is not a root. So the x-cells, the points $\alpha_i$ and the open intervals between them, partition $\mathbb{R}$.

Open columns. Let $I$ be an open x-cell with sample $a$. Lemma 2 gives $r$ continuous root functions on $I$. By Lemma 5(d), the stack computed at $a$ has exactly $r$ sections, so the sections and sectors over $I$ correspond one to one to the cells of the stack at $a$. By Lemma 3, each $f$ has a constant sign on each of these cells. By Lemma 5(e), the sign at the sample is computed exactly, so it is the sign on the whole cell.

Point columns. Over $\alpha_i$, the stack consists of the real roots of $S(\alpha_i, \cdot)$ and the open intervals between them (Lemma 5(d)). Signs are constant on them by Lemma 4 and computed exactly by Lemma 5(e).

Partition and cylindricity. Every vertical line is partitioned by the stack over its x-cell, so the cells partition $\mathbb{R}^2$. Their projections are exactly the x-cells, which makes the decomposition cylindrical. Each cell is connected, being a point, an interval, the graph of a continuous function over an interval, or the region between two such graphs.

Termination. Every loop either decreases a degree (the Euclidean and Sturm sequences, division), runs over a finite list (columns, cells, polynomials), or is a refinement loop. The refinement loops stop by Lemma 5(a), (b) and (e). $\blacksquare$