\documentclass[11pt]{article} \usepackage[a4paper,margin=27mm]{geometry} \usepackage[T1]{fontenc} \usepackage{indentfirst} \usepackage{xcolor} \setlength{\parindent}{1.5em} \usepackage{lmodern,amsmath,amssymb,amsthm,mathrsfs,mathtools,booktabs,enumitem,microtype} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark}\newtheorem{remark}[theorem]{Remark} \newcommand{\R}{\mathbb R} \newcommand{\Q}{\mathbb Q} \newcommand{\Z}{\mathbb Z} \newcommand{\CAD}{\operatorname{CAD}} \newcommand{\Res}{\operatorname{Res}} \newcommand{\diag}{\operatorname{diag}} \urlstyle{same} \hypersetup{pdftitle={Disproof of minimum CAD existence for algebraic sets in dimensions n >= 4},pdfauthor={Qiyue Tang}} \title{Disproof of minimum CAD existence for algebraic sets in dimensions $n\ge4$} \author{Qiyue Tang} \date{5 November 2026} \begin{document} \maketitle \begingroup \renewcommand{\thefootnote}{} \begin{NoHyper}\footnotetext{\textit{2020 Mathematics Subject Classification.} Primary 14P10; Secondary 14P05, 68W30.\par \textit{Keywords.} Cylindrical algebraic decomposition, minimum decomposition, real algebraic set, semialgebraic set.}\end{NoHyper} \endgroup \begin{abstract} We give real algebraic counterexamples to the existence of a minimum adapted cylindrical algebraic decomposition in every dimension $n\ge4$, for a fixed coordinate order. \end{abstract} \begingroup \color{blue} \section*{AI use and scholarly credit} The main results and proofs were developed using GPT-6-Pro. The archived research session lasted 1 hour, 55 minutes, 29 seconds, measured from research start to packaging. Codex was used to audit the arguments and polish the manuscript. The manuscript passed an AI review using Rethlas-OSV~\cite{RethlasOSV}, which incorporates the OSVerify framework of Nie et al.~\cite{Nie2026}. By posting this manuscript on this platform, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in preparing a finished account or checking the arguments; the eventual scholarly credit should go to those who undertake that work. \par \endgroup \section{Introduction} Cylindrical algebraic decomposition represents semialgebraic sets by finite partitions compatible with successive coordinate projections. A decomposition adapted to a given family may contain cuts that are unnecessary for representing that family. Michel, Mathonet, and Z\'ena\"idi~\cite{MMZ2024} formulated the problem of removing these cuts in terms of the refinement order on adapted decompositions. They proved that every adapted decomposition has a minimal adapted coarsening, and that a least adapted decomposition exists in dimensions one and two. Their examples show that such a least element can fail to exist for semialgebraic sets in every dimension at least three. Their subsequent work~\cite{MMZ2026} treats the corresponding questions for differentiability classes and gives further counterexamples. Michel~\cite{Michel2026} proved that every finite family of real algebraic subsets of $\R^3$ admits a minimum CAD. At the end of that paper he asked whether this remains true in arbitrary dimension. We answer this question negatively in every dimension at least four, already for a family consisting of one algebraic hypersurface. The construction starts with an open semialgebraic subset of $\R^3$ and two adapted Nash decompositions that admit no common adapted coarsening. A polynomial in one additional variable realizes that open set as its projection and has exactly four globally ordered simple real roots over every point of the projection. These roots lift both decompositions without subdividing their base cells. We also prove this transfer for every open semialgebraic set, using Pecker's elimination of inequalities~\cite{Pecker1990}, and construct a contractible four-dimensional example. \section{CADs and the main result} A semialgebraic set is a finite Boolean combination of real polynomial equality and inequality sets. All coefficients may be real. For a real polynomial $P$ in $n\ge1$ variables, write \[ Z_{\R}(P)=\{v\in\R^n:P(v)=0\}. \] At a real zero $v$, nonsingularity means that at least one first partial derivative of $P$ is nonzero. Absolute irreducibility means irreducibility over $\mathbb C$. For a polynomial $P(w)=\sum_{j=0}^d p_jw^j$, with integer $d\ge0$, and an integer $j\ge0$, the coefficient $[w^j]P$ is $p_j$, or zero when the power is absent. The degree in $w$ is the largest exponent with nonzero coefficient; the total degree is the largest sum of exponents in a nonzero monomial. A root of a univariate polynomial is simple when the derivative at that root is nonzero. For $V\subset\R^{m+1}$, its last-coordinate fiber over $v\in\R^m$ is $\{w\in\R:(v,w)\in V\}$. Fix an integer $n\ge1$ and the coordinate order $x_1\prec\cdots\prec x_n$, with projection onto initial coordinates. A complete cylindrical algebraic decomposition (CAD) is a sequence $\mathscr C=(\mathscr C_1,\ldots,\mathscr C_n)$ of finite semialgebraic partitions of $\R,\ldots,\R^n$. The first partition consists of finitely many points and their intervening open intervals, including the unbounded intervals. For $2\le k\le n$, over each cell $B\in\mathscr C_{k-1}$ choose an integer $q\ge0$ and continuous semialgebraic functions $f_1<\cdotsh(x,y)\}. \end{equation} All square roots denote the nonnegative real square root. The function $h$ is negative off $y=0$. It is Nash there, since $x^2+y^4>0$. On $x<0$, rationalization gives \begin{equation}\label{eq:rationalized} h(x,y)=-\frac{y^2}{\sqrt{x^2+y^4}-x}. \end{equation} The radicand and denominator are strictly positive on this half-plane, so this formula proves that $h$ is Nash also across $y=0$ when $x<0$. Furthermore, \begin{equation}\label{eq:threshold-values} h(0,y)=-1\ (y\ne0),\qquad h(0,0)=0,\qquad \lim_{y\to0,\,y\ne0}h(x,y)=-\infty\quad(x>0). \end{equation} For the last limit, the numerator in~\eqref{eq:h} tends to $2x>0$ and the denominator tends to zero through positive values. Define the polynomial \begin{equation}\label{eq:T} T(x,y,z)=y^2\bigl[y^2(1-z^2)-2xz\bigr]. \end{equation} Then \begin{equation}\label{eq:S} S=\{(x,y,z):z>0\}\cup\{(x,y,z):T(x,y,z)>0\}. \end{equation} Indeed, when $y\ne0$, the two roots in $z$ of $y^2(1-z^2)-2xz$ are \[ h(x,y)<0<\frac{-x+\sqrt{x^2+y^4}}{y^2}. \] The quadratic has negative leading coefficient, so it is positive exactly between these roots. Its positive interval, together with $z>0$, is exactly $z>h(x,y)$. Multiplication by $y^2>0$ preserves the inequality. When $y=0$, both descriptions reduce to $z>0$. In particular $S$ is open and semialgebraic. Construct two CADs in the order $x\prec y\prec z$. The CAD $\mathscr C$ has one first-level cell $\R$ and the three planar cells \[ \R\times(-\infty,0),\quad\R\times\{0\},\quad\R\times(0,\infty). \] Over each planar cell use $z=h(x,y)$ and its two sectors. Thus $\mathscr C$ has nine cells, three in $S$. The CAD $\mathscr D$ cuts the $x$-axis at zero. Over $x<0$ it uses the whole $y$-line; over $x=0$ and $x>0$ it cuts at $y=0$. These give seven planar cells. Over each use $z=h$ and its two sectors, giving twenty-one cells, seven in $S$. Formula~\eqref{eq:rationalized} proves the Nash property on the negative-$x$ planar cell. On the remaining planar cells the sections are either restrictions of~\eqref{eq:h} or constants. Both CADs are therefore Nash and adapted to $S$. \begin{lemma}\label{lem:no-common} The CADs $\mathscr C$ and $\mathscr D$ have no common $S$-adapted continuous semialgebraic coarsening. Each is minimal among continuous semialgebraic CADs adapted to $S$. \end{lemma} \begin{proof} In a stack adapted to $S$, every section and sector has a fixed membership label: it is either contained in $S$ or disjoint from $S$. Since each fiber of $S$ is the nonempty proper upper ray $(h(x,y),\infty)$, its boundary value must be one of the section values. Otherwise the sector containing the boundary value would contain points both inside and outside $S$. The first stack cell labeled inside $S$ is always the sector immediately above that boundary section. The labels are fixed over the base, so the boundary section has one fixed index. In particular $h$ must be continuous on each base cell of any adapted stack. Suppose $\mathscr E\preceq\mathscr C,\mathscr D$ is adapted to $S$. Since $\mathscr C_1=\{\R\}$, projection gives $\mathscr E_1=\{\R\}$. The cell $(-\infty,0)\times\R$ of $\mathscr D_2$ must be contained in one cell of $\mathscr E_2$. A section over the whole $x$-axis intersects this cell on every line $x=x_0<0$, splitting it between a section and sectors. Thus the stack of $\mathscr E_2$ has no section, and $\mathscr E_2=\{\R^2\}$. The finitely many final section functions of $\mathscr E$ would be continuous on $\R^2$ and hence simultaneously bounded on a neighborhood of $(1,0)$. One of their values at each $(1,y)$ must be $h(1,y)$, contradicting~\eqref{eq:threshold-values}. This proves the first assertion. For minimality, a coarser section over a fixed base cannot intersect the interior of a finer sector, since that sector would then meet two coarser cells. If the finer stack has the sole section zero, every coarser section must therefore equal zero. The only possibilities are to keep that section or delete it. Every coarsening of $\mathscr C$ has the same first-level cell. At level two it either keeps $y=0$ or deletes it. Deletion leaves the impossible whole-plane base just considered. Once the planar cells are retained, the section $h$ over each is mandatory by the upper-ray boundary argument, so the last-level stacks are also retained. For $\mathscr D$, deletion of $x=0$ would leave the whole $x$-axis; its negative-$x$ whole-$y$ cell would then force the whole-plane base, again impossible. Retain $x=0$. Over $x<0$ there is no planar cut to remove. Over $x=0$, removing $y=0$ would require a continuous boundary function on the whole $y$-line, contrary to $h(0,y)=-1$ for $y\ne0$ and $h(0,0)=0$. Over $x>0$, removing $y=0$ contradicts the divergence in~\eqref{eq:threshold-values}, with any fixed positive $x$. All planar cells and their mandatory final boundary sections therefore remain. Hence both CADs are minimal. \end{proof} \section{A polynomial for a binary disjunction}\label{sec:binary} In $\Z[a,b,w]$, with independent variables $a,b,w$, put $\Delta=a^2-ab+b^2$, the discriminant factor of the quadratic used below. Define \begin{align} A&=2\Delta\bigl(w^2-2(a+b)\bigr)-1,\notag\\ B&=2\bigl[(a+b)(w^2-a-b)-\Delta\bigr],\notag\\ H_{a,b}(w)&=\bigl[A^2+\Delta B^2-4(a+b)\Delta\bigr]^2\label{eq:circuit}\\ &\hspace{12mm}-\Delta\bigl[2AB-2((a+b)^2+\Delta)\bigr]^2.\notag \end{align} The four-variable polynomial of Theorem~\ref{thm:main} is \begin{equation}\label{eq:final-H} H(x,y,z,w)=H_{z,T(x,y,z)}(w), \end{equation} with $T$ from~\eqref{eq:T}. \begin{lemma}\label{lem:four-roots} For all real $a,b$, the polynomial $H_{a,b}$ has four distinct simple real roots when $a>0$ or $b>0$, and has no real roots otherwise. On the open set $\{(a,b):a>0\text{ or }b>0\}$ its four ordered roots are Nash functions. \end{lemma} \begin{proof} For real $u,d$, define \begin{equation}\label{eq:G} G(u,d,w)=\bigl[ud(w^2-u)-1\bigr]^2-u^2d. \end{equation} If $u=0$ or $d=0$, this polynomial equals $1$. For $d<0$ and $u\ne0$, it is a square plus the positive number $-u^2d$, so has no real zero. For $d>0$ and $u\ne0$, solving the squared equation gives the two possible values \[ w^2=u+\frac1{ud}\pm\frac1{\sqrt d} =\frac{(u\sqrt d\pm\tfrac12)^2+\tfrac34}{ud}. \] The numerator is positive, so both values have the sign of $u$. If $u<0$ there are no real roots. If $u>0$ the values are positive and distinct, and each gives two real roots. At such a root $w\ne0$, $ud\ne0$, and \[ \bigl[ud(w^2-u)-1\bigr]^2=u^2d>0. \] Consequently \[ \frac{\partial G}{\partial w} =4udw\bigl[ud(w^2-u)-1\bigr]\ne0, \] so the four roots are simple. The monic quadratic \[ Q(u)=u^2-2(a+b)u+3ab \] has roots $u_\pm=a+b\pm\sqrt\Delta$. The identity \[ \Delta=(a-\tfrac12b)^2+\tfrac34b^2 \] shows that $\Delta>0$ unless $a=b=0$. If $a,b\le0$, then $a+b\le0$ and $\Delta\le(a+b)^2$, so $u_+\le0$. If $ab<0$, then $\Delta>(a+b)^2$, so $u_+>0$. If $a,b\ge0$ and one is positive, then $a+b>0$ and $u_+>0$. These cases prove \[ u_+>0\quad\Longleftrightarrow\quad a>0\text{ or }b>0. \] When $(a,b)\ne(0,0)$, also $Q'(u_\pm)=\pm2\sqrt\Delta$. For a monic polynomial $P(u)$ of degree $d$ and a polynomial $R(u,w)$, the resultant in $u$ satisfies \[ \Res_u(P,R)=\prod_{j=1}^d R(\alpha_j,w), \] where $\alpha_j$ are the roots of $P$ in a splitting field, counted with multiplicity. This identity follows from the determinant definition of the resultant and holds after every parameter specialization for which $P$ remains monic of degree $d$. We have the polynomial identity \begin{equation}\label{eq:norm} H_{a,b}(w)=\Res_u\bigl(Q(u),G(u,2(u-a-b),w)\bigr). \end{equation} To verify it, work first with independent $a,b$ and adjoin $r$ with $r^2=\Delta$. Direct multiplication gives \begin{align*} 2r(a+b+r)(w^2-a-b-r)-1&=A+rB,\\ 2r(a+b+r)^2&=4(a+b)\Delta+2r((a+b)^2+\Delta). \end{align*} Substitution in~\eqref{eq:G} therefore gives \begin{align*} G(a+b+r,2r,w) &=A^2+\Delta B^2-4(a+b)\Delta\\ &\quad+r\bigl[2AB-2((a+b)^2+\Delta)\bigr]. \end{align*} Multiplying by its conjugate under $r\mapsto-r$ yields~\eqref{eq:circuit}. The monic resultant product gives~\eqref{eq:norm}. Both sides are polynomials in $a,b,w$, so the identity holds also at all specialized real parameters. If $(a,b)\ne(0,0)$, the product specializes to \[ H_{a,b}(w)=G(u_+,2\sqrt\Delta,w)G(u_-,-2\sqrt\Delta,w). \] The second factor has no real root. The first has four simple real roots exactly when $u_+>0$. At any of these roots the derivative of the first factor and the value of the second are nonzero, so their product has nonzero derivative. At $a=b=0$, formula~\eqref{eq:circuit} gives $H_{0,0}=1$. On the disjunction domain set $u=a+b+\sqrt\Delta>0$ and $d=2\sqrt\Delta>0$. The two positive functions \[ t_\pm=u+\frac1{ud}\pm\frac1{\sqrt d},\qquad 04$, use $V\times\R^{n-4}$, placing the free coordinates last, and append whole-line stacks to the two witness CADs. Projection of any common adapted coarsening to the first four coordinates would give a common adapted coarsening of their original lifts. Thus the same obstruction holds in every dimension $n\ge4$. \end{proof} \section{Absolute irreducibility} \begin{theorem}\label{thm:absolute} The polynomial $H$ in~\eqref{eq:final-H} is irreducible in $\mathbb C[x,y,z,w]$. \end{theorem} \begin{proof} First take algebraically independent $a,b$ and work over $K=\mathbb C(a,b)$. The polynomial $\Delta=a^2-ab+b^2$ factors as \[ \Delta=\left(a-\frac{1+\mathrm i\sqrt3}{2}b\right) \left(a-\frac{1-\mathrm i\sqrt3}{2}b\right),\qquad \mathrm i^2=-1. \] These distinct linear factors each occur to exponent one, so $\Delta$ is not a square in $K$: the exponent of any irreducible polynomial in a rational-function square is even. Adjoin $r$ with $r^2=\Delta$ and write $L=K(r)$, a quadratic extension. Set $u=a+b+r$ and $d=2r$, both nonzero in $L$. In fact $r\ne0$, and $u=0$ would imply $(a+b)^2=\Delta$, contradicting $3ab\ne0$. The monic normalization of~\eqref{eq:G} is the quartic \[ f(w)=\frac{G(u,d,w)}{u^2d^2} =\left(w^2-u-\frac1{ud}\right)^2-\frac1d\in L[w]. \] We prove it irreducible by two quadratic extensions. Define \[ \tau=b/a,\qquad e=r/a,\qquad F=\mathbb C(\tau,e),\qquad e^2=1-\tau+\tau^2. \] Here $\tau$ is transcendental over $\mathbb C$, $e$ is algebraic over $\mathbb C(\tau)$, and $L=F(a)$. Thus $F$ has transcendence degree one and $L$ has transcendence degree two, forcing $a$ to be transcendental over $F$. In these coordinates $d=2ea$ and $u=a(1+\tau+e)$. The constants $e$ and $1+\tau+e$ are nonzero in $F$; the latter could vanish only if $(1+\tau)^2=1-\tau+\tau^2$, which would give $3\tau=0$. In $F(a)$, the order of vanishing at $a=0$ assigns to a nonzero rational function the exponent of $a$ in its numerator minus that in its denominator after cancellation. A square has even order, whereas $d=2ea$ has order one. Hence $d$ is not a square in $L$. Choose $\delta$ in an algebraic closure with $\delta^2=d$, so $[L(\delta):L]=2$. Since $a=\delta^2/(2e)$, \[ M:=L(\delta)=F(\delta). \] The element $\delta$ is transcendental over $F$, as otherwise $a$ would be algebraic over $F$. The local coordinate change has isolated this transcendental parameter for a second order-of-vanishing calculation. Let $k=(1+\tau+e)/(2e)\in F\setminus\{0\}$, so $u=k\delta^2$. Consider \[ \beta=u+\frac1{ud}+\frac1\delta =\frac{k^2\delta^6+k\delta^3+1}{k\delta^4}\in M. \] Its numerator is a degree-six polynomial in the transcendental variable $\delta$ over $F$. Its derivative is $3k\delta^2(2k\delta^3+1)$. A common root of the numerator and derivative would have either $\delta=0$, where the numerator is $1$, or $k\delta^3=-1/2$, where it is $3/4$. Thus the numerator is squarefree. Its constant term is one, so none of its irreducible factors divides $\delta$. Any such factor occurs in $\beta$ with exponent one and does not divide the denominator. Therefore $\beta$ is not a square in the rational function field $F(\delta)$. Choose an algebraic element $\omega$ with $\omega^2=\beta$. Then $[M(\omega):M]=2$ and \[ \delta=\left(\omega^2-u-\frac1{ud}\right)^{-1}\in L(\omega). \] The denominator equals $1/\delta$ and is nonzero. Thus $M\subset L(\omega)$, $M(\omega)=L(\omega)$, and \[ [L(\omega):L]=[M(\omega):M][M:L]=4. \] Since $f(\omega)=\delta^{-2}-d^{-1}=0$, the element $\omega$ is a root of the monic quartic $f$. Thus $f$ is its minimal polynomial over $L$ and is irreducible. Let $\sigma$ be the nontrivial automorphism of $L/K$, defined by $\sigma(r)=-r$. It sends $f$ to another monic irreducible quartic. Their coefficients of $w^2$ are distinct, since the difference between the corresponding centers is \begin{align*} &\left(a+b+r+\frac1{2r(a+b+r)}\right) -\left(a+b-r-\frac1{2r(a+b-r)}\right)\\ &\qquad=2r+\frac{a+b}{r((a+b)^2-r^2)} =2r+\frac{a+b}{3abr} =\frac{6ab\Delta+a+b}{3abr}\ne0. \end{align*} The last numerator is a nonzero polynomial: its degree-four part and its degree-one part cannot cancel. By~\eqref{eq:norm}, $H_{a,b}$ is a nonzero element of $K$ times $f\,\sigma(f)$. A monic factor of this product over $K$ factors over $L$ as a product of a subset of these two distinct monic irreducible quartics. Its coefficients are fixed by $\sigma$, so its subset must be invariant under their exchange. Only the empty and full subsets are invariant. Thus $H_{a,b}$ is irreducible in $K[w]$. For the specific substitution, $a=z$ and $b=T=y^4(1-z^2)-2xy^2z$ satisfy the rational inverse \[ z=a,\qquad x=\frac{y^4(1-a^2)-b}{2ay^2}. \] This is an equality in the function field; its denominator is a nonzero polynomial. Consequently \[ \mathbb C(z,T,y)=\mathbb C(x,y,z). \] The right side has transcendence degree three, so the three generators $z,T,y$ on the left are algebraically independent. Hence this is a purely transcendental extension of $\mathbb C(z,T)$ by $y$. Irreducibility over a field is preserved on adjoining a transcendental element: if $E=K[w]/(g)$ is a field for an irreducible $g$, then $E[y]$ is an integral domain, and localization by $K[y]\setminus\{0\}$ shows that $K(y)[w]/(g)$ is an integral domain. Applying this to $H_{a,b}$ proves irreducibility of $H$ in $\mathbb C(x,y,z)[w]$. It remains to check that the coefficients of $H$ as a polynomial in $w$ have no common nonconstant factor in $\mathbb C[x,y,z]$. Such a factor, called a content factor, must divide the leading coefficient \[ 144z^2T^2\Delta(z,T)^2. \] The defining formula and the coordinate-axis specializations give \begin{align} H_{a,b}&\equiv1\pmod\Delta,\notag\\ H_{a,0}(w)&=\bigl[4a^2(w^2-2a)-1\bigr]^2-8a^3,\label{eq:axis}\\ H_{0,b}(w)&=\bigl[4b^2(w^2-2b)-1\bigr]^2-8b^3.\notag \end{align} For the congruence, $A\equiv-1\pmod\Delta$ in~\eqref{eq:circuit}, and all remaining terms outside $A^4$ contain $\Delta$. The second identity also follows from~\eqref{eq:coefficients} at $b=0$, giving coefficients $16a^4$, $-64a^5-8a^2$, and $64a^6+8a^3+1$ at powers $w^4,w^2,1$. The third follows by the symmetry in $a,b$. Let $p$ be an irreducible content factor. The unique factorization property implies that $p$ divides $\Delta(z,T)$, $T$, or $z$. In the first case $H\equiv1\pmod p$, a contradiction. In the second case reduction modulo $p$ gives $H\equiv H_{z,0}$, whose $w^4$ coefficient is $16z^4$. Thus $p$ also divides $z$. But $z$ is prime and $T\bmod z=y^4\ne0$, so $z$ and $T$ have no common factor. In the third case $p$ is associated to $z$, while the $w^4$ coefficient of $H\bmod z=H_{0,y^4}$ is $16y^{16}\ne0\pmod z$. This is again a contradiction. Thus the content is constant. Gauss's lemma now transfers irreducibility from $\mathbb C(x,y,z)[w]$ to $\mathbb C[x,y,z,w]$, completing Theorem~\ref{thm:main}. \end{proof} \section{Polynomial families of counterexamples} \begin{proposition}\label{prop:family} Let $A\in\R[x]$ and $B\in\R[y]$ satisfy \[ \operatorname{sign}(A(x))=\operatorname{sign}(x)\quad(x\in\R),\qquad B(y)=0\ \Longleftrightarrow\ y=0. \] Here $\operatorname{sign}$ takes values $-1,0,1$ on negative, zero, and positive numbers. Define \[ T_{A,B}(x,y,z)=B(y)^2\bigl[B(y)^2(1-z^2)-2A(x)z\bigr]. \] Then $H_{z,T_{A,B}}(w)$ has degree eight in $w$, its real zeros satisfy $\partial_w H_{z,T_{A,B}}\ne0$, and its real zero set has two minimal adapted Nash CADs with $33$ and $77$ cells and no common adapted continuous semialgebraic coarsening. \end{proposition} \begin{proof} For $y\ne0$, put \[ h_{A,B}(x,y)=-\frac{\sqrt{A(x)^2+B(y)^4}+A(x)}{B(y)^2}, \] and set $h_{A,B}(x,0)=0$. This function is negative off $y=0$. On $x<0$ it equals \[ -\frac{B(y)^2}{\sqrt{A(x)^2+B(y)^4}-A(x)}, \] whose radicand and denominator are positive even at $y=0$. Thus it is Nash on that half-plane and on $y\ne0$. Since $A(0)=0$, it has value $-1$ at $x=0,y\ne0$ and value zero at $(0,0)$. For any fixed $x>0$, its numerator tends to $2A(x)>0$ as $y\to0$, whereas $B(y)^2\to0$; hence it tends to $-\infty$. The two roots in $z$ of $B(y)^2(1-z^2)-2A(x)z$ have opposite signs when $y\ne0$, with lower root $h_{A,B}$. The quadratic sign argument of~\eqref{eq:S}, and the separate case $y=0$, give \[ \{z>h_{A,B}(x,y)\}=\{z>0\}\cup\{T_{A,B}>0\}. \] The nine- and twenty-one-cell patterns of Section~\ref{sec:seed} are Nash for this threshold by the formulas just established. The proof of Lemma~\ref{lem:no-common} uses exactly the negative-$x$ full-$y$ cell, the jump at $(0,0)$, and the divergence for each fixed $x>0$; all hold here. Thus both patterns are minimal and have no common adapted coarsening. Apply Lemma~\ref{lem:four-roots} with $a=z$, $b=T_{A,B}$ and then Lemma~\ref{lem:transfer}. Every cell in the epigraph has four root sections, giving the same counts $3\cdot9+6=33$ and $7\cdot9+14=77$. The roots are simple, so the last derivative is nonzero. The leading coefficient is $144z^2T_{A,B}^2\Delta(z,T_{A,B})^2$. The polynomial $B$ is nonzero and nonconstant, and $T_{A,B}(x,y,0)=B(y)^4\ne0$. Thus $T_{A,B}$ is nonzero. Also $\Delta(z,T_{A,B})$ is nonzero, since at $z=0$ it equals $B(y)^8$. The leading coefficient is therefore nonzero, proving degree eight in $w$. \end{proof} In particular $A(x)=x^{2p+1}$ and $B(y)=y^q$, for integers $p\ge0$ and $q\ge1$, give such a family with integer coefficients. \section{Algebraization of open semialgebraic sets} All polynomial derivatives in this section are taken with respect to the last displayed polynomial variable. \begin{lemma}\label{lem:selector} For an integer $r\ge1$ and $a=(a_1,\ldots,a_r)\in\R^r$, define the monic degree-$r$ polynomial \[ Q_a(t)=\prod_{j=1}^r(t-a_j)-\sum_{j=1}^r a_j\prod_{\substack{1\le k\le r\\k\ne j}}(t-a_k). \] All its roots are real. It has a positive root exactly when some $a_j>0$. On this parameter domain its largest root is simple and is a Nash function of $a$. Among the roots $u$ of $Q_a$, the conditions \begin{equation}\label{eq:selector-general} u>0,\qquad Q_a^{(j)}(u)>0\quad(1\le j0. \] Thus $B$ has a positive definite symmetric square root $B^{1/2}$. For $t\ne a_1,\ldots,a_r$, the determinant formula for a rank-one perturbation gives \[ \det(tI-DB)=\prod_{j=1}^r(t-a_j) \left(1-\sum_{j=1}^r\frac{a_j}{t-a_j}\right)=Q_a(t). \] $tI-DB=(tI-D)-D\mathbf1\mathbf1^T$; factoring out the diagonal matrix $tI-D$ reduces the determinant to $\det(I-v\mathbf1^T)=1-\mathbf1^Tv$, with $v_j=a_j/(t-a_j)$. The latter identity follows by decomposing the vector space into the kernel of $\mathbf1^T$ and one complementary direction, on which the remaining diagonal entry is $1-\mathbf1^Tv$. Polynomial identity then extends the determinant formula to all $t$. The matrix $DB$ is similar to the symmetric matrix $B^{1/2}DB^{1/2}$, since \[ B^{1/2}(DB)B^{-1/2}=B^{1/2}DB^{1/2}. \] Hence all roots are real. For a symmetric matrix, a positive eigenvalue exists exactly when its quadratic form is positive on some vector. Since $B^{1/2}$ is invertible, the values \[ v^T B^{1/2}DB^{1/2}v=(B^{1/2}v)^TD(B^{1/2}v) \] range through those of the diagonal quadratic form of $D$. Such a positive value exists exactly when some $a_j>0$. Assume some $a_j>0$. For $t>\max_j a_j$, define \[ g(t)=\sum_{j=1}^r\frac{a_j}{t-a_j}-1. \] As $t$ decreases to $\max_j a_j>0$, the terms at the maximum tend to $+\infty$ and the others remain bounded. As $t\to\infty$, $g(t)\to-1$. Thus $g$ has a zero. At every zero, \[ tg'(t)=-\sum_j\frac{ta_j}{(t-a_j)^2} =-\sum_j\left(\frac{a_j}{t-a_j}+\frac{a_j^2}{(t-a_j)^2}\right) =-1-\sum_j\frac{a_j^2}{(t-a_j)^2}<0. \] It therefore crosses from positive to negative at each zero. It is a nonzero rational function and has finitely many zeros on this interval. Two consecutive zeros are impossible: its sign immediately to the right of the first would be negative and immediately to the left of the second positive, forcing another zero between them. Hence there is exactly one zero, and it is simple. The nonzero factor $\prod_j(t-a_j)$ in the determinant identity shows that this is also a simple root of $Q_a$, and the only root above $\max_j a_j$. It is therefore the largest root. The largest eigenvalue of a continuous real symmetric matrix is continuous, by the Rayleigh formula $\lambda_{\max}(M)=\max_{\sum v_j^2=1}v^TMv$: convergence of the matrix entries gives uniform convergence of the quadratic forms on this compact sphere. The positive largest root is simple, so the implicit function theorem makes it real analytic locally in $a$. These local functions coincide with the continuous largest root. Let $\lambda$ be this root and list the other roots $\mu$ with multiplicity. Then \[ Q_a(\lambda+v)=v\prod_{\mu}(v+\lambda-\mu). \] Every difference $\lambda-\mu$ is positive. The coefficients of all powers $v^j$, $1\le j\le r$, are therefore positive, and equal to $Q_a^{(j)}(\lambda)/j!$. Conversely, at any root $u$ satisfying~\eqref{eq:selector-general}, Taylor's exact polynomial formula gives \[ Q_a(u+v)=\sum_{j=1}^{r-1}\frac{Q_a^{(j)}(u)}{j!}v^j+v^r>0 \quad(v>0). \] There is no root larger than $u$. For $r\ge2$ its first derivative is positive, so it is simple; for $r=1$ the derivative is the constant one. The equation $Q_a(u)=0$ and the strict polynomial inequalities in \eqref{eq:selector-general} therefore describe the graph of the selected function. Its graph is semialgebraic; together with its real analyticity this proves the Nash assertion. \end{proof} \begin{lemma}\label{lem:pecker} For $n\ge1$, real inputs $x_1,\ldots,x_n$, and a polynomial variable $U$, define $p_1(x_1,U)=U-x_1$. For $n\ge2$, put \[ s=\sum_{j=1}^n x_j,\qquad \alpha_i=(x_1+\cdots+x_i)x_{i+1}\quad(1\le is^2-\sum_jx_j^2=2\sum_i\alpha_i, \] contradicting the lower-root bound in (ii). Hence all inputs are nonnegative, completing (iii). If every $x_j>0$, all $\alpha_i>0$. List the lower roots as \[ 0<\rho_1<\cdots<\rho_{2^{n-2}}0$, and no real roots otherwise. These roots have a global Nash ordering on the positive orthant. At $q=0$ the polynomial equals $1$ for $k\ge2$ and $-1$ for $k=1$. \end{lemma} \begin{proof} For $k\ge2$, expand in the last input: \[ p_k(X_1,\ldots,X_k,U) =\sum_{j=0}^{2^{k-1}} p_{k,j}(X_1,\ldots,X_{k-1},U)X_k^j, \] where the coefficient polynomials $p_{k,j}$ are defined by this equality. Lemma~\ref{lem:pecker}(i) gives $p_{k,2^{k-1}}=1$. Thus the cleared expression is \[ F_k(f;w)=\sum_{j=0}^{2^{k-1}} q^{2^{k-1}-j}p_{k,j}(f_1,\ldots,f_{k-1},w^2). \] It is polynomial, and at $q=0$ only its constant last term survives, giving $1$. For $k=1$, the formula is directly $F_1=f_1w^2-1$. If $q\ne0$, all the substituted inputs $f_1,\ldots,f_{k-1},1/q$ are nonzero. By Lemma~\ref{lem:pecker}(iii), a real root exists exactly when these inputs are positive. This is equivalent to positivity of all $f_j$: positivity of the first $k-1$ and of their product with $f_k$ forces $f_k>0$, and the converse is immediate. For $k=1$ this says $1/f_1>0$ exactly when $f_1>0$. When all $f_j>0$, Lemma~\ref{lem:pecker}(iv) gives $2^{k-1}$ positive simple $U$-roots. Each gives the two nonzero square roots $w=\pm\sqrt U$. At any such root, \[ \frac{\partial F_k}{\partial w} =2wq^{2^{k-1}}\frac{\partial p_k}{\partial U} (f_1,\ldots,f_{k-1},1/q,w^2)\ne0. \] The ordered formulas in Lemma~\ref{lem:pecker}, composed with $1/q$ and these square roots, give a global Nash ordering of the $2^k$ roots. \end{proof} \begin{theorem}\label{thm:general} Let $m\ge1$ and let $S\subset\R^m$ be open and semialgebraic. There exist $J\in\R[x_1,\ldots,x_m,w]$ and an integer $N\ge1$ such that $Z_{\R}(J)$ has exactly $N$ simple real points in every last-coordinate fiber over $S$ and no points over its complement. The ordered roots are Nash functions on $S$, and $\partial J/\partial w\ne0$ at every real zero. Projection and canonical lifting preserve the existence of a minimum adapted CAD and give mutually inverse bijections on minimal adapted CADs, in each regularity class of Theorem~\ref{thm:main}. Given a finite strict-inequality description as in~\eqref{eq:CNF}, the polynomial $J$ is obtained by polynomial arithmetic and resultants over its coefficient field. \end{theorem} \begin{proof} For $S=\varnothing$ take $J=1$, and for $S=\R^m$ take $J=w$. The assertion about a fixed number of roots is vacuous on an empty $S$; the empty-domain root functions allow $N=1$. Lemma~\ref{lem:transfer} applies in both cases. For a nonempty proper $S$, use the finite strict-inequality representation of open semialgebraic sets, as in the proof of Pecker's principal theorem~\cite[p.~312]{Pecker1990}. In conjunction-of-disjunctions form it is \begin{equation}\label{eq:CNF} S=\bigcap_{i=1}^{\ell}\bigcup_{j=1}^{r_i} \{x\in\R^m:a_{ij}(x)>0\}, \end{equation} where $x=(x_1,\ldots,x_m)$, $\ell,r_i\ge1$ are integers, and $a_{ij}$ are real polynomials. This representation also follows by distributing intersections over a finite union of basic open sets, each defined by a conjunction of strict polynomial inequalities. For each clause $i$, form the monic polynomial \[ Q_i(x,u_i)=Q_{(a_{i1}(x),\ldots,a_{ir_i}(x))}(u_i) \] from Lemma~\ref{lem:selector}. Introduce $u=(u_1,\ldots,u_\ell)$ and concatenate the polynomial lists \[ u_i,\quad \partial_{u_i}Q_i(x,u_i),\quad\ldots,\quad \partial_{u_i}^{r_i-1}Q_i(x,u_i) \qquad(1\le i\le\ell) \] into a vector $f(x,u)$ of length $K=\sum_{i=1}^{\ell}r_i$. When $r_i=1$, its list consists only of $u_i$. Define polynomials successively by \begin{align*} R_0(x,u,w)&=F_K(f(x,u);w),\\ R_i&=\Res_{u_i}(Q_i,R_{i-1})\quad(1\le i\le\ell),\qquad J=R_\ell. \end{align*} After step $i$, $R_i$ is independent of $u_1,\ldots,u_i$. Each $Q_i$ is monic in $u_i$, independent of the other auxiliary variables, and has fixed degree $r_i$. Hence the resultant product formula specializes without any leading-coefficient qualification. Fix a real $x$, and list the roots of $Q_i(x,\cdot)$ with multiplicity as $\lambda_{i,1},\ldots,\lambda_{i,r_i}$. Lemma~\ref{lem:selector} makes all these numbers real. Iterating the monic product identity gives exactly \begin{equation}\label{eq:general-product} J(x,w)=\prod_{j_1=1}^{r_1}\cdots\prod_{j_\ell=1}^{r_\ell} F_K\bigl(f(x,\lambda_{1,j_1},\ldots,\lambda_{\ell,j_\ell});w\bigr). \end{equation} If $x\in S$, each clause has a unique selected root satisfying~\eqref{eq:selector-general}, and this root is simple. Thus exactly one root tuple makes every entry of $f$ positive, and this tuple occurs once in the product. Its factor has exactly $N=2^K$ simple real roots by Lemma~\ref{lem:strict}. Every other tuple has at least one nonpositive input and contributes a factor with no real roots. If $x\notin S$, one clause has no selected root, so every factor has no real roots. No factor in either case is the zero polynomial, since a zero polynomial would have real roots. At a real zero $w_0$ of $J(x,\cdot)$, only the selected factor vanishes. The derivative of~\eqref{eq:general-product} is its nonzero $w$-derivative multiplied by the nonzero values of all other factors. It is therefore nonzero. The selected tuple is a Nash function of $x$ on $S$ by Lemma~\ref{lem:selector}. Composing it with $f$ gives positive Nash inputs for $F_K$, whose global ordered root functions are Nash by Lemma~\ref{lem:strict}. These compositions supply the asserted $N$ root functions for $J$. Lemma~\ref{lem:transfer} now proves the claims about adapted CADs. \end{proof} \begin{samepage} \section{Contractible algebraic zero sets} \begin{proposition}\label{prop:connected} For $0\le j\le8$, let $h_j(x,y,z)=[w^j]H(x,y,z,w)$ and define \begin{equation}\label{eq:connected} F(x,y,z,w)=\sum_{j=0}^8 h_j(x,y,z)(z-1)^{9-j}w^j. \end{equation} The real zero set of $F$ is contractible. In the order $x\prec y\prec z\prec w$ it has two adapted Nash CADs with $63$ and $147$ cells and no common adapted continuous semialgebraic coarsening. The polynomial is reducible and has singular real zeros at every $(x,y,1,0)$. \end{proposition} \end{samepage} \begin{proof} For $z\ne1$, formula~\eqref{eq:connected} equals $(z-1)^9H(x,y,z,w/(z-1))$. At $z=1$ it vanishes for all $w$. Let $r_1<\cdots1. \] Over the first two, use the whole $w$-line, since their bases are outside $S$. Over $z=1$ also use the whole $w$-line, now contained in the zero set. Over $h1$, use the four scaled root sections $(z-1)r_i$ and their five sectors. For $z<1$ their order is reversed, and for $z>1$ it is preserved. On each base these functions are Nash and strictly ordered. Thus this gives adapted Nash CADs. Per planar cell, their final counts are $1+1+9+1+9=21$, yielding $3\cdot21=63$ and $7\cdot21=147$. A common adapted coarsening projects to an $S$-adapted CAD in $\R^3$. The first two levels of each witness are still those of $\mathscr C$ and $\mathscr D$. The first two levels of the common coarsening are therefore forced to be $\{\R\}$ and $\{\R^2\}$ by the negative-$x$ cylinder argument in Lemma~\ref{lem:no-common}. Its final stack cannot be adapted to $S$ because $h(1,y)\to-\infty$ while finitely many continuous global sections are locally bounded. This proves the coarsening assertion. The polynomial $F$ has the factor $z-1$, and the quotient is nonconstant because its $w^8$ coefficient is the nonzero polynomial $h_8$. Thus it is reducible. Every term has a factor $(z-1)^{9-j}w^j$ of degree nine in $z-1,w$. Differentiation with respect to any one variable leaves a factor of positive degree in these two variables. Hence all first partial derivatives vanish at $z=1,w=0$, proving the singularity assertion. \end{proof} \begin{proposition}\label{prop:contractible-general} Let $m\ge1$ and let $S\subset\R^m$ be open and semialgebraic. There exists a contractible real algebraic zero set in $\R^{m+2}$ such that projection onto the first $m$ coordinates and an explicit lifting preserve minimum existence and restrict to mutually inverse bijections on minimal adapted CADs. The statement holds in each cellwise regularity class of Theorem~\ref{thm:main}. \end{proposition} \begin{proof} Let $x=(x_1,\ldots,x_m)$ and let $J(x,w)$ be the polynomial from Theorem~\ref{thm:general}. Write \[ J(x,w)=\sum_{j=0}^d j_j(x)w^j, \] where $d$ is its degree in $w$ and $j_j$ are its coefficient polynomials. Use the order $x_1\prec\cdots\prec x_m\prec t\prec w$ and define \begin{equation}\label{eq:contractible-general} K(x,t,w)=\sum_{j=0}^d j_j(x)t^{d+1-j}w^j. \end{equation} At $t=0$ this is zero for every $w$; for $t\ne0$ it equals $t^{d+1}J(x,w/t)$. Thus its real zero set consists of the entire hyperplane $t=0$ and, off that hyperplane, the scaled root graphs $w=tr_i(x)$ for $x\in S$, where $r_1<\cdots