One-dimensional decomposition

To explain the cylindrical algebraic decomposition method, we first perform a semi-algebraic decomposition of ${\mathbb{R}}$, which is the final step in the projection sequence. Once this is explained, then the multi-dimensional case follows more easily.

Let ${\cal F}$ be a set of $m$ univariate polynomials,

$${\cal F}= \{ f_i \in {\mathbb{Q}}[x] \; \vert \; i = 1, \ldots, m\} ,$$ (6.18)

which are used to define some semi-algebraic set in ${\mathbb{R}}$. The polynomials in ${\cal F}$ could come directly from a quantifier-free formula $\phi$ (which could even appear inside of a Tarski sentence, as in (6.9)).

Define a single polynomial as $f = \prod_{i=1}^m f_i$. Suppose that $f$ has $k$ distinct, real roots, which are sorted in increasing order:

$$-\infty \; < \; {\beta}_1 \; < \; {\beta}_2 \; < \; \cdots \; < \... ...beta}_i \; < \; {\beta}_{i+1} \; < \; \cdots \; < \; {\beta}_k \; < \; \infty .$$ (6.19)

The one-dimensional semi-algebraic decomposition is given by the following sequence of alternating $1$-cells and 0-cells:

$$\begin{split}&(-\infty,{\beta}_1), \; [{\beta}_1,{\beta}_1], ... ...s, \; [{\beta}_k,{\beta}_k], \; ({\beta}_k,\infty). \end{split}$$ (6.20)

Any semi-algebraic set that can be expressed using the polynomials in ${\cal F}$ can also be expressed as the union of some of the 0-cells and $1$-cells given in (6.20). This can also be considered as a singular complex (it can even be considered as a simplicial complex, but this does not extend to higher dimensions).

Sample points can be generated for each of the cells as follows. For the unbounded cells $[-\infty,{\beta}_1)$ and $({\beta}_k,\infty]$, valid samples are ${\beta}_1 - 1$ and ${\beta}_k + 1$, respectively. For each finite $1$-cell, $({\beta}_i,{\beta}_{i+1})$, the midpoint $({\beta}_i+{\beta}_{i+1})/2$ produces a sample point. For each 0-cell, $[{\beta}_i,{\beta}_i]$, the only choice is to use ${\beta}_i$ as the sample point.

Figure 6.31: Two parabolas are used to define the semi-algebraic set $[1,2]$.

Figure 6.32: A semi-algebraic decomposition for the polynomials in Figure 6.31.

Example 6..5 (One-Dimensional Decomposition)   Figure 6.31 shows a semi-algebraic subset of ${\mathbb{R}}$ that is defined by two polynomials, $f_1(x) = x^2 - 2x$ and $f_2(x) = x^2 - 4x + 3$. Here, ${\cal F}= \{f_1,f_2\}$. Consider the quantifier-free formula

$$\phi (x) = (x^2 - 2x \geq 0) \wedge (x^2 - 4x + 3 \geq 0) .$$ (6.21)

The semi-algebraic decomposition into five $1$-cells and four 0-cells is shown in Figure 6.32. Each cell is sign invariant. The sample points for the $1$-cells are $-1$, $1/2$, $3/2$, $5/2$, and $4$, respectively. The sample points for the 0-cells are 0, $1$, $2$, and $3$, respectively.

A decision problem can be nicely solved using the decomposition. Suppose a Tarski sentence that uses the polynomials in ${\cal F}$ has been given. Here is one possibility:

$$\Phi = \exists x [(x^2 - 2x \geq 0) \wedge (x^2 - 4x + 3 \geq 0)]$$ (6.22)

The sample points alone are sufficient to determine whether $\Phi$ is TRUE or FALSE. Once $x=1$ is attempted, it is discovered that $\Phi$ is TRUE. The quantifier-elimination problem cannot yet be considered because more dimensions are needed. $\blacksquare$