Regular semi-algebraic system

In computer algebra, a regular semi-algebraic system is a particular kind of triangular system of multivariate polynomials over a real closed field.

Introduction

Regular chains and triangular decompositions are fundamental and well-developed tools for describing the complex solutions of polynomial systems. The notion of a regular semi-algebraic system is an adaptation of the concept of a regular chain focusing on solutions of the real analogue: semi-algebraic systems.

Any semi-algebraic system $S$ can be decomposed into finitely many regular semi-algebraic systems $S_1, \ldots, S_e$ such that a point (with real coordinates) is a solution of $S$ if and only if it is a solution of one of the systems $S_1, \ldots, S_e$.^[1]

Formal definition

Let $T$ be a regular chain of ${{\mathbf{k}}}[x_1, \ldots, x_n]$ for some ordering of the variables $\mathbf{x} = x_1, \ldots, x_n$ and a real closed field ${{\mathbf{k}}}$. Let $\mathbf{u} = u_1, \ldots, u_d$ and $\mathbf{y} = y_1, \ldots, y_{n-d}$ designate respectively the variables of $\mathbf{x}$ that are free and algebraic with respect to $T$. Let $P \subset {{\mathbf{k}}}[\mathbf{x}]$ be finite such that each polynomial in $P$ is regular w.r.t.\ the saturated ideal of $T$. Define $P_{>} :=\{p>0\mid p\in P\}$. Let $\mathcal{Q}$ be a quantifier-free formula of ${{\mathbf{k}}}[\mathbf{x}]$ involving only the variables of $\mathbf{u}$. We say that $R := [\mathcal{Q}, T, P_{>}]$ is a regular semi-algebraic system if the following three conditions hold.

• $\mathcal{Q}$ defines a non-empty open semi-algebraic set $S$ of ${{\mathbf{k}}}^d$,
• the regular system $[T, P]$ specializes well at every point $u$ of $S$,
• at each point $u$ of $S$, the specialized system $[T(u), P(u)_{>}]$ has at least one real zero.

The zero set of $R$, denoted by ${Z}_{{{\mathbf{k}}}}(R)$, is defined as the set of points $(u, y) \in {{{\mathbf{k}}}}^d \times {{{\mathbf{k}}}}^{n-d}$ such that $\mathcal{Q}(u)$ is true and $t(u, y)=0$, $p(u, y)>0$, for all $t\in T$and all $p\in P$.

See also

• RegularChains
• Real algebraic geometry

References

1. Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Triangular decomposition of semi-algebraic systems. Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187–194, 2010.