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 ${\displaystyle S}$ can be decomposed into finitely many regular semi-algebraic systems ${\displaystyle S_{1},\ldots ,S_{e}}$ such that a point (with real coordinates) is a solution of ${\displaystyle S}$ if and only if it is a solution of one of the systems ${\displaystyle S_{1},\ldots ,S_{e}}$. ^[1]

Formal definition

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

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

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

See also

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