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$ .

References

↑ 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.

Regular semi-algebraic system

Introduction

Formal definition

See also

References