signcondition

Signcondition, or sign condition, is a concept in real algebraic geometry used to describe the pattern of signs taken by a finite family of real polynomials at a point in real space.

Formally, let P = {p1, ..., pk} be polynomials in R[x1, ..., xn], and let a ∈ R^n. The sign condition s realized at a is the k-tuple (sign(p1(a)), ..., sign(pk(a))), where sign(t) ∈ {−1, 0, +1} according to whether t < 0, t = 0, or t > 0. The set S_s = {a ∈ R^n : sign(pi(a)) = s_i for all i} is the sign region corresponding to s. A sign condition is feasible if S_s ≠ ∅. The collection of all realized sign conditions partitions R^n into sign-invariant regions, each region described by polynomial inequalities and equalities.

Sign conditions are central to computational real algebraic geometry. They underlie decision procedures for systems of polynomial inequalities and are a key ingredient in cylindrical algebraic decomposition (CAD), which decomposes R^n into cells on which the sign of every pi is constant. They also appear in quantifier elimination and in sampling algorithms for semi-algebraic sets.

Example: Let P = {p1(x) = x, p2(x) = x^2 − 1} in R[x] (n = 1). At a point x, the sign vector is (sign(x), sign(x^2 − 1)). For x = 0.5, the vector is (+, −); for x = 2, it is (+, +); for x = 0, it is (0, −). The sign region for (+, +) is x > 1; for (−, +) it is x < −1.

See also: sign condition problem, real algebraic geometry, semi-algebraic set, cylindrical algebraic decomposition, quantifier elimination.