Wednesday, 14 September 2011

inequalities - Examples of inequality implied by equality.

Over real-closed fields such as $langle mathbb{R}, +, *, -, <, 0, 1 rangle$, there is an interesting simple answer: every polynomial inequality is equivalent to a projected equation. E.g.,
Given $p_1, p_2 in mathbb{Q}[vec{x}]$ we have $left( p_1 > p_2 iff exists z text{ s.t. } z^2(p_1 - p_2) - 1 = 0 right),$ and $left( p_1 geq p_2 iff exists z text{ s.t. } p_1 - p_2 - z^2 = 0 right).$



Geometrically, this is the simple observation that every semialgebraic set defined as the set of $n-$dimensional real vectors satisfying an inequality is the projection of an $n+1$-dimensional real-algebraic variety defined by a single equation. Semialgebraic sets defined by boolean combinations of equations and inequalities can be similarly encoded as the set of satisfying real vectors of (an) equation(s) by using the Rabinowitsch encoding $(p_1 = 0 vee p_2 = 0 iff p_1p_2 = 0)$ and $(p_1 = 0 wedge p_2 = 0 iff p_1^2 + p_2^2 = 0).$



Combining the above two observations, one obtains the fact that every semi-algebraic set $S subseteq mathbb{R}^n$ is the projection of a real algebraic variety $V subseteq mathbb{R}^{n+k}$, where $k$ is the number of inequality symbols appearing in the defining Tarski formula for $S$. In fact, due to a construction of Motzkin [``The Real Solution Set of a System of Algebraic Inequalities is the Projection of a Hypersurface in One More Dimension,'' Inequalities II, O. Shisha, ed., 251-254, Academic Press (1970)], it is known that every such $S$ is in fact the projection of a real-algebraic variety in $mathbb{R}^{n+1}$.

No comments:

Post a Comment