Fact-checked by Grok 2 weeks ago

Real algebraic geometry

Real algebraic geometry is the branch of algebraic geometry that focuses on the real solutions to systems of polynomial equations and inequalities with real coefficients, adapting classical methods from complex algebraic geometry to analyze geometric objects in real affine and projective spaces.^[1]^[2] It emerged from the foundations of Cartesian analytic geometry in the plane and predates its complex counterpart, with early developments driven by the need to understand physically meaningful configurations in real space.^[1] Central to the field are semi-algebraic sets, which are finite unions of sets defined by polynomial equalities and strict or non-strict inequalities, providing a framework for describing the feasible regions of these systems.^[2]^[3] Real varieties consist of the real points on complex algebraic varieties defined by real polynomials, such as the unit circle as the real locus of the equation x^2 + y^2 - 1 = 0.^[1] These structures enable the study of topological and geometric properties, including connectivity and Betti numbers, through algorithmic and theoretical tools.^[2] Key foundational results include the Tarski-Seidenberg theorem, which guarantees the elimination of quantifiers in the first-order theory of real closed fields, allowing existential statements about semi-algebraic sets to be decided algorithmically.^[2]^[3] Complementing this is the Positivstellensatz, a family of theorems providing algebraic certificates for the positivity or non-negativity of polynomials on semi-algebraic sets, building on Artin's 1927 solution to Hilbert's 17th problem, which affirms that every non-negative polynomial in \mathbb{R}[x_1, \dots, x_n] can be expressed as a sum of squares of rational functions.^[3] These theorems underpin applications in optimization, robotics, and control theory, where real feasibility is paramount.^[1]

Fundamentals

Real Algebraic Sets

In real algebraic geometry, real algebraic sets are defined as the common zero loci of finite collections of polynomials with real coefficients in the affine space \mathbb{R}^n or the projective space \mathbb{P}^n(\mathbb{R}). These sets, often denoted V(f_1, \dots, f_k) for polynomials f_i \in \mathbb{R}[x_1, \dots, x_n], capture the real solutions to systems of polynomial equations and serve as the primary objects of study, analogous to algebraic varieties over algebraically closed fields but restricted to real points. A classic example is the unit circle in \mathbb{R}^2, given by V(x^2 + y^2 - 1), which forms a one-dimensional compact manifold homeomorphic to S^1. This set is irreducible over the reals, meaning it cannot be expressed as the union of two proper real algebraic subsets. Over the complex numbers, the corresponding variety V_\mathbb{C}(x^2 + y^2 - 1) in \mathbb{C}^2 is also irreducible and one-dimensional, but its real points constitute a proper subset with distinct topological properties, such as boundedness. Another example is the hyperboloid of one sheet in \mathbb{R}^3, defined by V(x^2 + y^2 - z^2 - 1), a two-dimensional surface that is irreducible over the reals and connected, exhibiting hyperbolic geometry. In contrast, the complexification V_\mathbb{C}(x^2 + y^2 - z^2 - 1) is an irreducible quadric hypersurface of complex dimension 2, but the real points are constrained by sign conditions, leading to a non-compact, ruled surface structure. These examples illustrate how dimension—defined as the Krull dimension of the coordinate ring or the transcendence degree of the function field—remains the same over reals and complexes for the variety, but irreducibility may differ due to the absence of complex conjugation symmetries. Basic properties of real algebraic sets include their role in defining the Zariski topology on \mathbb{R}^n, where the closed sets are precisely the real algebraic sets, and the open sets are complements of such zeros (or loci where polynomials do not vanish). This topology is coarser than the Euclidean one, with real algebraic sets being constructible but potentially having empty interiors. A foundational result is the Real Nullstellensatz, which states that for any ideal I \subseteq \mathbb{R}[x_1, \dots, x_n], the vanishing ideal I(V_\mathbb{R}(I)) equals the real radical of I, defined as \{f \mid f^{2m} + \sum g_i^2 \in I \text{ for some } m \in \mathbb{N}, g_i \in \mathbb{R}[x_1, \dots, x_n]\}. This establishes a bijection between real radical ideals and real algebraic sets, ensuring that the radical of the vanishing ideal coincides with the vanishing ideal of the set. Unlike in complex algebraic geometry, where the field is algebraically closed and varieties correspond to radical ideals via Hilbert's Nullstellensatz, real algebraic sets may exhibit fewer connected components or even be empty despite nonempty complexifications, owing to sign conditions that restrict real solutions (e.g., V_\mathbb{R}(x^2 + y^2 + 1) = \emptyset). Real algebraic sets form the equality-defined core of the subject, which extends to semialgebraic sets through the inclusion of polynomial inequalities.

Semialgebraic Sets

Semialgebraic sets generalize real algebraic sets by incorporating polynomial inequalities alongside equalities, allowing for the description of more flexible geometric objects such as regions bounded by algebraic varieties. A semialgebraic set in \mathbb{R}^n is defined as a finite union of sets of the form \{x \in \mathbb{R}^n \mid f_1(x) = \cdots = f_s(x) = 0, \, g_1(x) > 0, \dots, g_t(x) > 0 \}, where the f_i and g_j are polynomials with real coefficients; more generally, these sets arise from finite Boolean combinations (unions, intersections, and complements) of such basic sets defined by polynomial equations f(x) = 0 and inequalities g(x) \geq 0 or g(x) > 0.^[4] This definition extends naturally to real closed fields, preserving the core structure.^[4] Representative examples include the closed unit disk \{(x,y) \in \mathbb{R}^2 \mid x^2 + y^2 \leq 1\}, which is defined by a single non-strict inequality, and half-spaces such as \{x \in \mathbb{R}^n \mid a \cdot x + b \geq 0\} for a vector a \in \mathbb{R}^n and scalar b \in \mathbb{R}, illustrating how linear polynomials capture affine regions. More complex examples, like the intersection of a sphere and a half-space, demonstrate how semialgebraic sets can model bounded domains with curved boundaries. These sets can be decomposed into cells—open subsets homeomorphic to Euclidean balls of various dimensions—facilitating their analysis.^[4] Semialgebraic sets exhibit remarkable closure properties: they are closed under finite unions and intersections, as well as complements, ensuring that Boolean operations preserve the class.^[4] Moreover, by the Tarski-Seidenberg projection theorem, the image of a semialgebraic set under a polynomial map (including projections onto coordinate subspaces) remains semialgebraic, which underpins many elimination techniques in real algebraic geometry.^[4] The collection of semialgebraic sets defines an o-minimal structure on \mathbb{R}, meaning that every definable subset of \mathbb{R} is a finite union of points and open intervals; this o-minimality implies a tame topology, where every semialgebraic set in \mathbb{R}^n has finitely many connected components and admits a finite cell decomposition into pieces homeomorphic to open balls (0,1)^k for k = 0, \dots, n. Such decompositions highlight the controlled complexity of these sets, contrasting with the potentially wild topology of arbitrary subsets of \mathbb{R}^n. In dimension theory, the dimension of a semialgebraic set S \subseteq \mathbb{R}^n is defined as the largest integer d such that S contains a nonempty open subset of \mathbb{R}^d (embedded in \mathbb{R}^n), or equivalently, the maximum dimension of the cells in a cell decomposition of S. This dimension coincides with the topological dimension and is invariant under semialgebraic homeomorphisms. Semialgebraic sets admit Whitney stratifications into finitely many smooth manifolds (strata) of varying dimensions, where each stratum is a semialgebraic set of pure dimension, and the strata satisfy the frontier condition: the closure of a stratum contains only lower-dimensional strata.^[4] This stratification provides a geometric framework for studying local and global properties, such as singularities and connectivity, with the dimension capturing the "degrees of freedom" within the set.

Historical Development

Early Foundations

The foundations of real algebraic geometry trace back to ancient Greek geometry, where conic sections were systematically studied as intersections of planes with a cone, laying the groundwork for understanding real algebraic curves. Apollonius of Perga, in his seminal work Conics (circa 200 BCE), provided a comprehensive treatment of ellipses, parabolas, and hyperbolas, emphasizing their geometric properties and diameters, which implicitly involved real points and loci defined by quadratic equations. This approach marked an early recognition of real solutions in algebraic varieties, influencing later developments in classifying curves over the real numbers.^[5] In the 17th century, René Descartes advanced the field through analytic geometry, linking algebraic equations directly to geometric curves in his La Géométrie (1637). Descartes classified algebraic curves by the degree of their defining equations, distinguishing "geometric" curves (of degree up to 6, constructible via ruler and compass motions) from "mechanical" ones, and solved problems like Pappus's locus theorem by reducing them to polynomial inequalities over the reals. His coordinate system enabled the study of real branches of curves, such as the folium, highlighting the distinction between real and complex solutions. Isaac Newton further contributed by classifying cubic curves into 72 species in Enumeratio Linearum Tertii Ordinis (1704), using projective methods and organic constructions to generate and resolve singularities in real algebraic curves of degree 3.^[6]^[7] The 19th century saw key milestones in addressing real solutions to polynomial systems. Joseph Fourier, in his 1826 memoir, developed an elimination algorithm for systems of linear inequalities, providing a method to determine the feasibility of real solutions in polyhedral sets defined by polynomials, which became foundational for real quantifier elimination. In 1876, Axel Harnack proved a theorem bounding the number of connected components of a nonsingular real projective plane curve of degree d by \frac{(d-1)(d-2)}{2} + 1, resolving a long-standing question on the topology of real algebraic varieties and establishing an upper limit on their oval components.^[8]^[9] David Hilbert's 17th problem, posed in 1900 at the International Congress of Mathematicians, asked whether every positive semidefinite polynomial in n real variables—that is, a polynomial f \in \mathbb{R}[x_1, \dots, x_n] with f(x) \geq 0 for all x \in \mathbb{R}^n—can be expressed as a sum of squares of rational functions. This problem highlighted the challenges in representing positivity in real algebra and remained unsolved at the time, encapsulating the era's focus on sums-of-squares decompositions for real polynomials.^[10]

Modern Advances

A pivotal advancement in the early 20th century came from Emil Artin in 1927, who provided an affirmative solution to Hilbert's 17th problem by demonstrating that every non-negative polynomial over the real numbers can be represented as a sum of squares of rational functions.^[11] This resolution relied on Artin's introduction of real closed fields, which are formally real fields where every positive element has a square root and every odd-degree polynomial has a root, enabling the algebraic characterization of positivity essential to the problem.^[11] Artin's work not only settled a longstanding conjecture but also laid foundational tools for subsequent developments in real algebra. Building on this, Alfred Tarski established in the 1930s that the first-order theory of real closed fields admits quantifier elimination, meaning every formula is equivalent to a quantifier-free one involving only polynomial inequalities.^[12] Tarski's result, fully published in 1951, provided a decision procedure for the theory of real numbers with addition, multiplication, and order, confirming its completeness and decidability.^[13] In the 1950s, Abraham Seidenberg offered an alternative algebraic proof of quantifier elimination, avoiding Tarski's model-theoretic approach and emphasizing projection methods that project semialgebraic sets onto lower dimensions while preserving their semialgebraic nature. The mid-20th century saw further breakthroughs with the Nash-Tognoli theorem, which asserts that every compact smooth manifold is diffeomorphic to a nonsingular real algebraic set. John Nash proved this in 1952 by constructing algebraic approximations to smooth embeddings using Nash functions, which are real analytic and satisfy certain algebraic conditions.^[14] Alberto Tognoli refined and simplified the result in 1962, showing that such an algebraic model exists as the zero set of polynomials defining a nonsingular variety, thus bridging differential geometry and real algebraic geometry. In the 21st century, real algebraic geometry has deepened connections to symplectic topology through enumerative invariants. Jean-Yves Welschinger introduced Welschinger invariants in 2003 for real symplectic 4-manifolds, providing signed counts of real rational pseudo-holomorphic curves that offer lower bounds on the number of real solutions to enumerative problems, contrasting with complex Gromov-Witten invariants.^[15] These invariants, robust under deformation, have advanced real enumerative geometry by quantifying topological complexities in real algebraic curves and surfaces. Key figures like Oleg Viro have further enriched the field with the patchworking technique, enabling the construction of real algebraic varieties with prescribed topology by gluing piecewise-defined polynomials over triangulations.^[16]

Key Theorems and Results

Positivstellensätze

Positivstellensätze provide algebraic certificates, typically in the form of sums of squares representations, for polynomials that are positive on semialgebraic sets, bridging geometric positivity properties with algebraic identities in the ring of polynomials. These theorems play a central role in real algebraic geometry by offering constructive ways to verify strict positivity over constrained domains, extending the scope beyond unconditional sums of squares. They emerged as key tools for addressing representation problems for positive polynomials, with foundational connections to orderings in real-closed fields.^[17] A landmark result in this area is Artin's positivstellensatz, which resolves Hilbert's 17th problem by affirming that every non-negative polynomial p \in \mathbb{R}[x_1, \dots, x_n] admits a representation as a sum of squares of rational functions, i.e., p = \sum q_i^2 where each q_i \in \mathbb{R}(x_1, \dots, x_n).^[17] More generally, for a polynomial p strictly positive on the real variety V(I) defined by an ideal I in \mathbb{R}[x_1, \dots, x_n], Artin's theorem implies that p is a sum of squares modulo I, meaning p - \sigma \in I for some sum of squares \sigma.^[18] This certificate modulo the ideal ensures that positivity on the variety V(I) translates to an algebraic identity, though the rational functions introduce denominators that complicate direct polynomial representations.^[17] Building on Artin's work, stronger polynomial-level versions without denominators were developed for compact semialgebraic sets. Schmüdgen's positivstellensatz (1991) states that if p > 0 on the compact basic closed semialgebraic set K = \{x \in \mathbb{R}^n \mid g_1(x) \geq \cdots \geq g_m(x) \geq 0 \}, then for any \epsilon > 0, p + \epsilon can be expressed as a conic combination of products of the g_i, specifically p + \epsilon = \sum_{\alpha \in \mathbb{N}^m} \sigma_\alpha \prod_{i=1}^m g_i^{\alpha_i} where each \sigma_\alpha is a sum of squares. Independently, Putinar's positivstellensatz (1993) provides a simpler form under the archimedeanness condition on the quadratic module generated by \{1, g_1, \dots, g_m\}—meaning there exists N > 0 such that N - \sum x_j^2 belongs to the module—asserting that p > 0 on K implies p = \sigma_0 + \sum_{i=1}^m \sigma_i g_i for sums of squares \sigma_0, \sigma_i \in \mathbb{R}[x_1, \dots, x_n]. These representations avoid the multi-index products of Schmüdgen's version, making Putinar's particularly useful for quadratic module theory when the set is "bounded" in a quadratic sense.^[19] The basic sum-of-squares representation underlying these theorems takes the form

p = \sigma_0 + \sum_{i=1}^m \sigma_i g_i,

where \sigma_0, \sigma_i are sums of squares, certifying strict positivity of p on the semialgebraic set defined by the g_i \geq 0.^[20] Such certificates distinguish global positivity on the entire set from local approximations via sums of squares alone, which may fail even for non-negative polynomials. For instance, the Motzkin polynomial M(x,y,z) = x^4 y^2 + x^2 y^4 + z^6 - 3 x^2 y^2 z^2 is non-negative everywhere (with equality only at the origin and along certain rays) but cannot be expressed as a sum of squares of polynomials, highlighting the need for positivstellensätze to capture global constraints via the g_i.^[21] This example, discovered in 1967, underscores applications in optimization, where positivstellensätze enable exact dual certificates for feasibility over semialgebraic domains, contrasting with the stricter sum-of-squares condition that suffices locally but not globally.

Projection Theorems

The Tarski-Seidenberg theorem, also known as the projection theorem or transfer principle, states that if S \subset \mathbb{R}^{n+m} is a semialgebraic set and \pi: \mathbb{R}^{n+m} \to \mathbb{R}^n is the linear projection onto the first n coordinates, then \pi(S) is semialgebraic.^[22] This result establishes the closure of the family of semialgebraic sets under projection, ensuring that existential quantifiers over polynomial conditions yield sets definable without quantifiers.^[23] In the context of the real spectrum of a real closed ring, the theorem extends to show that the projection of a constructible set in the spectrum is constructible, preserving the structure of basic open sets defined by sums of squares. The theorem implies the real quantifier elimination principle: every first-order formula over the ordered field of real numbers, involving addition, multiplication, and order, is equivalent to a quantifier-free formula in the same language.^[24] This decidability result for the theory of real closed fields underpins much of real algebraic geometry by reducing complex statements to Boolean combinations of polynomial inequalities.^[25] Alfred Tarski provided the first proof using model-theoretic techniques, embedding the reals into real closed fields and leveraging completeness properties in 1951. Abraham Seidenberg later gave a purely algebraic proof in 1954, avoiding model theory by constructing explicit elimination ideals and using Noetherian induction on the dimension.^[26] Among its consequences, the curve selection lemma asserts that for any semialgebraic set S \subset \mathbb{R}^n and point x \in \overline{S} \setminus S, there exists a continuous semialgebraic path \gamma: [0,1] \to \mathbb{R}^n such that \gamma(0) = x and \gamma((0,1]) \subset S.^[22] Another important outcome is the triangulation theorem: every bounded semialgebraic set admits a finite semialgebraic triangulation compatible with its stratification, where the image of the simplicial complex under a semialgebraic homeomorphism matches the set. As an illustrative example, consider the semialgebraic set S = \{(x,y) \in \mathbb{R}^2 \mid 0 \leq y^2 \leq x \leq 1\}. The projection \pi(S) onto the x-axis yields the interval [0,1], which is semialgebraic, demonstrating how the theorem preserves the definable nature under elimination of the y-variable.^[22]

Computational Aspects

Cylindrical Algebraic Decomposition

Cylindrical algebraic decomposition (CAD) is a method in real algebraic geometry that partitions \mathbb{R}^n into a finite collection of disjoint, connected semi-algebraic cells such that each input polynomial has constant sign on every cell.^[27] The decomposition is cylindrical, meaning that for a given variable ordering, say x_1, \dots, x_n, each cell in dimension k+1 is a product of a cell in dimension k and an open interval (or point or ray) in the (k+1)-th variable.^[27] This structure ensures compatibility with the zero sets of polynomials, allowing precise description of semi-algebraic sets defined by sign conditions.^[28] The algorithm was introduced by George E. Collins in 1975 as a refinement of Alfred Tarski's quantifier elimination procedure, providing an effective method for real closed fields.^[29] Collins' approach builds on the Tarski-Seidenberg theorem by constructing an explicit decomposition rather than a purely existential proof.^[29] It has been applied to solve systems of polynomial inequalities by identifying cells where all inequalities hold simultaneously.^[29] The CAD algorithm proceeds in two main phases: projection and lifting. In the projection phase, starting from a set of polynomials A \subset \mathbb{Z}[x_1, \dots, x_r], a projection operator computes a set of polynomials in \mathbb{Z}[x_1, \dots, x_{r-1}] whose roots delineate critical points in the lower dimension; this uses algebraic tools like resultants and discriminants to capture conditions where polynomials vanish or change sign.^[27] The process recurses until the univariate case in \mathbb{R}^1, where real root isolation yields intervals between roots as cells.^[27] In the lifting phase, the decomposition is extended dimension by dimension: for each cell in the lower-dimensional space, sample points are chosen to evaluate the original polynomials in the next variable, isolating roots to define cylindrical sections above that cell.^[27] This ensures the sign invariance property propagates upward. The computational complexity of Collins' algorithm is doubly exponential in the number of variables n, specifically bounded by (nd)^{2^{O(n)}}, where d is the maximum degree of the input polynomials; this arises from the recursive projection, which can square the number of factors at each step.^[29] Despite this, the method remains practical for low dimensions, such as n \leq 3, in applications like robotics path planning or chemical reaction analysis.^[28] As an illustrative example, consider the semialgebraic set defined by x^2 + y^2 \leq 1 in \mathbb{R}^2. The projection onto the x-axis yields cells (-\infty, -1), \{-1\}, (-1, 1), \{1\}, and (1, \infty). Over (-\infty, -1) and (1, \infty), the polynomial x^2 + y^2 - 1 > 0 for all y, forming unbounded cylindrical cells. Over \{-1\} and \{1\}, it touches zero at y=0, creating point and ray cells. Over (-1, 1), lifting isolates y \in (-\sqrt{1-x^2}, \sqrt{1-x^2}) as the interior disk section, with boundary points and exterior rays, resulting in a decomposition into disk interior, boundary arcs, and exterior regions aligned cylindrically along y.^[30] Limitations of CAD stem primarily from its high complexity, which renders it infeasible for high-dimensional problems without specialized refinements, though it excels in providing geometrically interpretable decompositions for semi-algebraic sets in small dimensions.^[28] Recent advances as of 2025 have focused on reducing complexity and improving practicality. Notable developments include the integration of CAD into software packages like Macaulay2, which incorporates modern projection improvements for better efficiency, and new heuristics for variable ordering to minimize cell count. Additionally, techniques inspired by computational logic and machine learning have optimized CAD for specific applications, pushing back the doubly exponential wall in low dimensions.^[31]^[32]^[33]

Real Quantifier Elimination

Real quantifier elimination is the algorithmic process of transforming a first-order formula in the language of real closed fields—built from polynomial equalities, inequalities, boolean connectives, and quantifiers ∃ and ∀—into an equivalent quantifier-free formula consisting of boolean combinations of atomic polynomial inequalities. This reduction preserves logical equivalence and enables decidability for the theory of real closed fields, as any quantified sentence can be decided by evaluating its quantifier-free form over the reals. The method underpins decision procedures for problems in real algebraic geometry, such as determining the existence of real solutions to polynomial systems.^[34] Alfred Tarski established the foundations of real quantifier elimination in the 1930s, proving that every formula in the first-order theory of real closed fields admits a quantifier-free equivalent; this result implies the decidability of the theory. His approach, detailed in a 1951 monograph, constructs such equivalents through a systematic procedure based on cylindrical algebraic decomposition, which decomposes the real space into cells where polynomials have constant sign, facilitating quantifier removal layer by layer. While theoretically complete, Tarski's original algorithm is primitive recursive but suffers from extremely high complexity, with runtime bounded by a tower of exponentials in the number of variables and polynomial degrees.^[24]^[25] Modern variants have improved efficiency for practical computations, particularly for formulas with few quantifiers or low degrees. Volker Weispfenning introduced virtual substitution in the 1990s, a technique that eliminates existential quantifiers by substituting parametrized test terms—such as linear or quadratic expressions—into the formula, reducing it to cases solvable over simpler structures like quadratic forms; this method excels for linear and quadratic polynomials and extends to higher degrees like cubics.^[35]^[36] The critical point method, developed by Saugata Basu, Richard Pollack, and Marie-Françoise Roy, leverages Morse theory to identify critical points of projection maps on semi-algebraic sets, enabling single-exponential time complexity for certain quantifier elimination tasks by focusing on topological invariants rather than full decompositions.^[37] These approaches often integrate with partial cylindrical algebraic decomposition for broader applicability.^[38] Real quantifier elimination finds applications in solving Diophantine approximation problems, where it certifies effective bounds on how well algebraic numbers can approximate transcendentals via quantifier-free conditions on Diophantine inequalities. It also supports automated theorem proving over the reals, as implemented in tools like QEPCAD and Redlog, by reducing geometric or analytic conjectures to decidable quantifier-free assertions for verification in hybrid systems and formal proofs.^[39]^[34] For instance, eliminating the existential quantifier in the formula \exists y \, (y^2 = x^3 - x + 1) yields a quantifier-free condition on x—typically involving the discriminant of the cubic—that precisely determines the real values of x for which the equation admits real roots, illustrating its role in analyzing real roots of polynomials. The overall complexity remains challenging, with primitive recursive bounds but practical implementations scaling poorly beyond 3–4 variables due to exponential growth in formula size.^[25] Recent developments as of 2025 include new algorithms for real QE, such as adaptations of CAD drawing from SAT solver techniques and machine learning-based optimizations to handle larger formulas more efficiently. Additionally, extensions to mixed integer-real arithmetic, like the Viras calculus, have broadened applicability to constraint satisfaction in optimization and verification. These advances, surveyed in recent works, continue to enhance decidability tools for real closed fields.^[33]^[32]^[40]

Applications and Connections

In Optimization and Control

Real algebraic geometry provides powerful tools for addressing non-convex polynomial optimization problems by relaxing them into convex semidefinite programs (SDPs) using sum-of-squares (SOS) hierarchies. In the early 2000s, Jean-Bernard Lasserre developed a sequence of SDP relaxations based on moment matrices and SOS decompositions to approximate the global minimum of a polynomial over a semialgebraic set, with convergence guaranteed under mild conditions such as compactness.^[41] These hierarchies exploit the dual representations of polynomial positivity via SOS certificates and moment functionals, transforming intractable problems into tractable ones solvable by interior-point methods.^[41] Positivstellensätze, such as those of Putinar and Schmüdgen, serve as the theoretical foundation for certifying the infeasibility or global optimality of semialgebraic programs by providing algebraic certificates of polynomial nonnegativity on constrained sets.^[42] In optimization contexts, these certificates can be constructed hierarchically through SOS relaxations to verify that no feasible point achieves a better objective value, ensuring finite convergence for bounded semialgebraic feasible sets.^[42] In robust control theory, SOS techniques enable the synthesis of Lyapunov functions as polynomials that are SOS and satisfy SOS inequalities derived from system dynamics, thus proving stability for uncertain polynomial systems.^[43] For instance, parameter-dependent Lyapunov functions can be optimized via SDPs to certify robust stability regions, accommodating polytopic or norm-bounded uncertainties in control design.^[43] Path planning in robotics benefits from real algebraic geometry by modeling obstacles as semialgebraic sets and constructing collision-free roadmaps through connectivity analysis of the configuration space. Seminal algorithms decompose the free space into cells and connect sample points with paths avoiding algebraic boundaries, enabling complete motion planning for manipulators amid polynomial-defined obstacles.^[44] A representative example is maximizing x^2 + y^2 subject to (x-1)^2 + y^2 \leq 1, which seeks the point in the unit disk centered at (1,0) farthest from the origin. This non-convex problem is solved using moment relaxations of order 2 or higher, yielding the exact optimum of 4 at (2,0). Practical implementations rely on software tools like GloptiPoly, which parses generalized moment problems and solves SDP hierarchies for polynomial optimization, and SOSTOOLS, a MATLAB toolbox for formulating SOS programs in control applications.^[45]

Links to Other Fields

Real algebraic geometry establishes profound connections with differential topology through the Nash-Tognoli theorem, which asserts that every compact smooth manifold is diffeomorphic to a nonsingular real algebraic variety.^[46] This result provides algebraic models for smooth manifolds, enabling the study of topological invariants via algebraic tools and bridging smooth and algebraic categories.^[47] In symplectic topology, real enumerative invariants, such as those introduced by Welschinger, count real rational curves in real symplectic manifolds and offer lower bounds for the number of such curves passing through real point configurations.^[48] These invariants extend Gromov-Witten theory to the real setting and relate to mirror symmetry, where real counts on one side correspond to complex enumerative problems on the dual side, as explored in works connecting tropical methods to symplectic invariants. Mikhalkin's contributions further link these invariants to tropical enumerative geometry, providing combinatorial interpretations that align real and complex curve counts. Tropical real algebraic geometry examines the asymptotic behavior of real algebraic varieties through amoebas—the images under the Log map of complex varieties—and their skeletons, which are determined by the Newton polytopes of defining polynomials. Amoebas capture the "tentacles" extending to infinity, corresponding to recession cones of the Newton polytope, facilitating asymptotic analysis of real loci as coefficients scale.^[49] This framework, intertwined with patchworking techniques like Viro's, constructs real varieties from piecewise linear data on tropical curves. Connections to o-minimal structures arise in logic and analysis, where semialgebraic sets—definable in the real field—form the basic o-minimal structure, ensuring tame topology with finitely many connected components and uniform finiteness for definable families. This tameness underpins applications in analytic geometry, such as cell decomposition and quantifier elimination, linking real algebraic definability to model-theoretic properties.^[50] A representative example is real Schubert calculus, which enumerates real points in Grassmannians satisfying incidence conditions; for instance, the signed count of real lines on a real quintic threefold in \mathbb{P}^4 provides invariants distinguishing real enumerative geometry from its complex counterpart, where the total is 2875.^[51]

References

[1]
[PDF] REAL ALGEBRAIC GEOMETRY FOR GEOMETRIC CONSTRAINTS
Real algebraic geometry adapts the methods and ideas from (complex) al- gebraic geometry to study the real solutions to systems of polynomial equations and.Missing: scholarly | Show results with:scholarly
[2]
[PDF] Algorithms in Real Algebraic Geometry: A Survey - Purdue Math
We survey both old and new developments in the theory of al- gorithms in real algebraic geometry – starting from effective quantifier elim- ination in the first ...
[3]
[PDF] Real Algebra and Geometry
Introduction: What is real algebra and geometry? Probably the most fundamental question in mathematics is about solvability of equations. Systems of linear ...
[4]
Real Algebraic Geometry | SpringerLink
The present volume is a translation, revision and updating of our book (published in French) with the title "Géométrie Algébrique Réelle".
[5]
[PDF] Saito.pdf
Chapter I of this paper is dedicated to an examination of the Conics of. Apollonius. Though the central part of the "geometric algebra" is usually explained as.
[6]
Descartes' Mathematics - Stanford Encyclopedia of Philosophy
Nov 28, 2011 · Specifically, Descartes offers innovative algebraic techniques for analyzing geometrical problems, a novel way of understanding the connection ...
[7]
[PDF] newton, the geometer - Stephen Huggett
Newton was aware of its importance in geometry, using it to generate algebraic curves, including those with singularities. 1. Introduction. Isaac Newton was a ...
[8]
[PDF] USING FOURIER-MOTZKIN VARIABLE ELIMINATION FOR MCSAT ...
The Fourier-Motzkin Elimination (FME) was the earliest method for solving linear inequality systems. It was discovered in 1826 by Joseph Fourier, and re- ...
[9]
https://link.springer.com/doi/10.1007/BF01442458
[10]
[PDF] REAL ALGEBRA FROM HILBERT'S 17th PROBLEM
Hilbert's 17th problem asks if every positive semidefinite polynomial in R^n is a sum of squares of rational functions. The answer is affirmative.
[11]
[1602.07330] On Hilbert's 17th problem in low degree - arXiv
Feb 23, 2016 · Title:On Hilbert's 17th problem in low degree ; MSC classes: 11E25, 14F20, 14P99 ; Cite as: arXiv:1602.07330 [math.AG] ; (or arXiv:1602.07330v2 [ ...Missing: Emil 1927 original
[12]
Alfred Tarski's elimination theory for real closed fields
Mar 12, 2014 · Alfred Tarski's elimination theory for real closed fields. Published online by Cambridge University Press: 12 March 2014. Lou Van Den Dries.
[13]
The birth of model theory - American Mathematical Society
Sep 8, 2009 · Already in 1931, Tarski proved quantifier elimination for the first or- der theory of the ordered real field [Tar31]. He noted in a footnote ...
[14]
Real Algebraic Manifolds - jstor
Printed in U.S.A.. REAL ALGEBRAIC MANIFOLDS. By JOHN NASH. (Received October 8, 1951). Introduction. The main purpose of this paper is to develop some ...
[15]
Invariants of real symplectic 4-manifolds and lower bounds in ... - arXiv
View a PDF of the paper titled Invariants of real symplectic 4-manifolds and lower bounds in real enumerative geometry, by Jean-Yves Welschinger.Missing: topology | Show results with:topology
[16]
[math/0611382] Patchworking real algebraic varieties - arXiv
Nov 13, 2006 · The author invented patchworking in 1979-81 and used it for constructing of real plane algebraic curves with complicated prescribed topology. In ...
[17]
[PDF] Positive polynomials - Hilbert's 17th problem - ISI Bangalore
xn] is a sum of squares of rational functions. The 17th problem was solved by E.Artin in 1926 in the affirma- tive. He proved it as an existence theorem. His ...
[18]
[PDF] arXiv:1709.09307v2 [math.OC] 27 Aug 2018
Aug 27, 2018 · Perhaps the most well- known Positivstellensatz of this type is due to Artin in 1927, in response to Hilbert's. 17th problem. Artin shows that ...
[19]
An effective version of Schmüdgen's Positivstellensatz for the ...
Sep 15, 2022 · Schmüdgen's Positivstellensatz then states that for any η > 0 , the nonnegativity of f + η on S can be certified by expressing f + η as a conic ...
[20]
[PDF] An algorithmic approach to Schmüdgen's Positivstellensatz
Jun 6, 2001 · We present a new proof of Schmüdgen's Positivstellensatz concerning the repre- sentation of polynomials f ∈ R[X1, ..., Xd] that are strictly ...
[21]
[PDF] Lecture 5: SOS Proofs and the Motzkin Polynomial
non-negative polynomials which are not sums of squares of polynomials. • Motzkin [Mot67] found the first explicit example. Page 23. Motzkin Polynomial.
[22]
[PDF] Real Algebraic Sets
Mar 23, 2005 · In this chapter we present some basic topological facts concerning semialgebraic sets, which are subsets of Rn defined by combinations of ...
[23]
Tarski-Seidenberg theorem in nLab
### Summary of Tarski-Seidenberg Theorem
[24]
[PDF] A Decision Method for Elementary Algebra and Geometry - RAND
Tarski (1940) found a decision method for the elementary theory of Boolean algebra. McKinsey (1943) gave a decision method for the class of true universal ...Missing: paper URL
[25]
[PDF] Algorithms in Real Algebraic Geometry: A Survey - Purdue Math
Sep 4, 2014 · This is an easy consequence of the Tarski-Seidenberg transfer principle (see for example [25, Theorem 2.80]). We now return to the discussion of ...
[26]
[PDF] Cylindrical Algebraic Decomposition I: The Basic Algorithm
Collins gave a cad construction algorithm in 1975, u part of • quantifier elimination procedure for real dosed fields. The algorithm has subsequently found.
[27]
Cylindrical Algebraic Decomposition I: The Basic Algorithm - SIAM.org
This paper describes and analyzes a variant of the algorithm of Collins and others for decomposing ℝ r into semi-algebraic cells so that the value of each ...
[28]
Quantifier elimination for real closed fields by cylindrical algebraic ...
May 25, 2005 · Collins, G.E., Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition ... 2 (April 1975), pp. 291–308 ...
[29]
[PDF] Simplification of Cylindrical Algebraic Formulas
Example 1 Consider the closed unit disk S defined by x2 + y2 ≤ 1. Then a. CAF associated with S is as below. (x = −1 ∧ y = 0) ∨ (−1 < x ∧ x < 1 ∧ y ...<|control11|><|separator|>
[30]
(PDF) Real Quantifier Elimination in Practice - ResearchGate
We give a survey of three implemented real quantifier elimination methods: partial cylindrical algebraic decomposition, virtual substitution of test terms, and ...
[31]
Quantifier Elimination for Real Algebra — the Quadratic Case and ...
The method generalizes the linear quantifier elimination method by virtual substitution of test terms in [9]. It yields a quantifier elimination method for an ...
[32]
Quantifier elimination for real algebra—the cubic case
The method extends the virtual substitution of parametrized test points developed in [Weispfenning 1, Loos &. We ispf.] for the linear case and in ...
[33]
[PDF] Critical Point Methods and Effective Real Algebraic Geometry
Dec 30, 2013 · These methods are used in algorithms for solving various problems such as deciding the existence of real solutions of polynomial sys- tems, ...
[34]
[PDF] On Quantifier Elimination by Virtual Term Substitution
This paper presents a new look at Weispfenning's method of quantifier elimination by virtual term substitution and provides two important im- provements.
[35]
[PDF] Quantifier Elimination and Applications in Control - DiVA portal
Quantifier elimination is a method for simplifying formulas that consist of poly- nomial equations, inequalities, and quantifiers. We give a brief introduction ...
[36]
Global Optimization with Polynomials and the Problem of Moments
We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x): {\mathbb{R}}^n\to {\mathbb{R}}$, as well as the global ...
[37]
Optimization of Polynomials on Compact Semialgebraic Sets
We give a short introduction to Lasserre's method for minimizing a polynomial f on a compact set S of this kind. It consists of successively solving tighter and ...
[38]
[PDF] A Tutorial on Sum of Squares Techniques for Systems Analysis
A Lyapunov function will be constructed for a region of the rest of the parameter space, to prove robust stability of the equilibrium. The equilibrium of the ...
[39]
Constructing roadmaps of semi-algebraic sets I: Completeness
This paper describes preliminary work on an algorithm for planning collision-free motions for a robot manipulator in the presence of obstacles.
[40]
[PDF] Moments for polynomial optimization - An illustrated tutorial
On Figure 1.4 we represent the set of moments (y1,y2,y3) in the monomial basis (x, x2,x3) of all probability measures (i.e. y0 = 1) on [−1,1]. It is the convex ...
[41]
SOSTOOLS - A sum of squares optimization toolbox for MATLAB
Sep 29, 2021 · SOSTOOLS is a free MATLAB toolbox for formulating and solving sums of squares (SOS) optimization programs. SOSTOOLS can be used to specify and ...Missing: GloptiPoly | Show results with:GloptiPoly
[42]
Approximation theorems and Nash conjecture - EuDML
Approximation theorems and Nash conjecture. Alberto Tognoli · Mémoires de la Société Mathématique de France (1974). Volume: 38, page 53-68; ISSN: 0249-633X ...
[43]
Improvement of the Nash-Tognoli theorem
The Nash-Tognoli theorem says that M can be arbitrarily well approximated (in the Cr-topology with r < ∞) in ℝn by a nonsingular real algebraic set under the ...
[44]
Invariants of real symplectic 4-manifolds and lower bounds in real ...
Jun 14, 2005 · We first build the moduli spaces of real rational pseudo-holomorphic curves in a given real symplectic 4-manifold.
[45]
https://www.cds.caltech.edu/sostools/
[46]
Lecture Notes on O-Minimal Structures and Real Analytic Geometry
This book will be a useful tool for graduate students or researchers from related fields who want to learn about expansions of o-minimal structures.
[47]
Real Schubert Calculus: Polynomial Systems and a Conjecture of ...
Boris and Michael Shapiro have a conjecture concerning the. Schubert calculus and real enumerative geometry and which would give infinitely many families of ...Missing: quintics | Show results with:quintics