Positivstellensatz

In fields from robotics to chemical engineering, guaranteeing a system's safety or stability often hinges on a fundamental mathematical question: is a particular function always positive within a given operating region? While simple for one-variable functions, this becomes incredibly difficult for the complex, multi-variable polynomials that describe real-world systems. This article addresses this challenge by exploring a powerful framework from algebraic geometry that provides verifiable "certificates" of positivity. The first chapter, "Principles and Mechanisms", will introduce the core concept of Sum of Squares (SOS) polynomials, explain the limitations that led to the development of the Positivstellensatz, and detail how these theorems provide computationally tractable proofs for positivity on constrained sets. Following this theoretical foundation, the second chapter, "Applications and Interdisciplinary Connections", will demonstrate how these abstract ideas become indispensable engineering tools for certifying stability, ensuring safety, and even synthesizing controllers for complex systems, bridging the gap between pure mathematics and applied technology.

Imagine you are an engineer designing a complex system—an autonomous drone, a power grid, or a chemical reactor. A critical question you must answer is: will this system be stable? Will it stay within safe operating limits? Often, these questions boil down to a deceptively simple mathematical challenge: proving that a certain function, say an energy function $V(x)$, is always positive within a given region of operation.

If $V(x)$ were a simple, one-variable parabola like $x^2 + 1$, you'd know instantly it's always positive. But what if it's a sprawling polynomial with many variables, like $V(x_1, x_2, x_3) = x_1^8 + x_2^6 - 2x_1^3 x_2^2 x_3 + 5x_3^4$? How can you be certain it never dips below zero? You could test millions of points, but that's just gathering evidence, not a proof. This is the positivity puzzle, and its solution takes us on a beautiful journey through algebra, geometry, and computation.

Let's start with a wonderfully simple idea. What if we could rewrite our complicated polynomial, $p(x)$, as a sum of other polynomials that have been squared? For instance, something like:

If we can do this, then the non-negativity of $p(x)$ is self-evident. Since we are working with real numbers, the square of any number is non-negative. A sum of non-negative things must also be non-negative. So, $p(x) \ge 0$ for all possible values of $x$. Finding such a representation is like finding an undeniable, algebraic "certificate" of non-negativity. We call such a polynomial a ​​sum of squares​​, or ​​SOS​​.

This certificate is incredibly powerful because it replaces a difficult geometric question (is the graph of the function always above the axis?) with a purely algebraic one (can the polynomial be factored in this specific way?).

This SOS idea seems so natural that you might guess that any polynomial that is non-negative must be a sum of squares. For polynomials of a single variable, this is actually true. For a long time, mathematicians wondered if it was true for multiple variables. In 1888, David Hilbert posed this as part of his famous list of problems. The answer, surprisingly, is no.

There exist polynomials that are non-negative everywhere but cannot be written as a sum of squares of other polynomials. The most famous of these is the ​​Motzkin polynomial​​:

Using a clever inequality (the AM-GM inequality), one can prove that $M(x_1, x_2) \ge 0$ for all real numbers $x_1$ and $x_2$. However, it is impossible to find polynomials $h_i(x_1, x_2)$ such that $M(x_1, x_2) = \sum_i h_i(x_1, x_2)^2$. It's as if the polynomial is non-negative by a "geometric coincidence" that its algebra cannot directly express in the SOS form.

This reveals a fascinating and subtle gap between the geometric property of non-negativity and the algebraic property of being a sum of squares. So, while being SOS is a sufficient condition for non-negativity, it is not a necessary one.

(As a side note, Emil Artin later resolved Hilbert's 17th problem by showing that any non-negative polynomial can be written as a sum of squares of rational functions—that is, fractions of polynomials. While theoretically beautiful, this introduces denominators that make computation much harder.)

If the SOS trick isn't perfect, why has it revolutionized fields like control theory? The answer lies in computational complexity. Deciding if a general multivariate polynomial is non-negative is an NP-hard problem, meaning it is computationally "hard" in the worst case—the required time could grow exponentially with the size of the problem. For all practical purposes, it's often impossible.

In stark contrast, deciding if a polynomial is a sum of squares is "easy"! It can be transformed into a type of problem called a ​​semidefinite program (SDP)​​, which can be solved efficiently by modern computers. The key insight is the ​​Gram matrix representation​​.

Any polynomial $p(x)$ of degree $2d$ that is a sum of squares can be written in the form:

Here, $z(x)$ is a vector containing all the monomials up to degree $d$ (e.g., for two variables and degree 1, $z(x) = \begin{pmatrix} 1 & x_1 & x_2 \end{pmatrix}^\top$), and $Q$ is a special kind of constant matrix: it must be ​​positive semidefinite​​. A positive semidefinite matrix is the matrix equivalent of a non-negative number and is a central object in optimization.

The search for an SOS certificate for $p(x)$ becomes a search for a positive semidefinite matrix $Q$ that satisfies the linear equations generated by matching the coefficients of $p(x)$ with the expansion of $z(x)^\top Q z(x)$. This is precisely what an SDP is: an optimization problem with linear constraints and a positive semidefinite matrix variable. This is a ​​convex optimization problem​​, a class of problems for which we have reliable and efficient algorithms.

So, by replacing the non-negativity condition with the stronger SOS condition, we trade a bit of mathematical generality for immense computational power.

In many real-world problems, we don't need a function to be positive everywhere in the universe. We only care about a specific operating region, like a drone staying within a certain distance of its operator, or a robot arm moving within its physical limits. This region, let's call it $K$, can often be described by a set of polynomial inequalities, like $g_i(x) \ge 0$. For instance, the inside of a unit circle is described by $g(x) = 1 - (x_1^2 + x_2^2) \ge 0$.

How can we certify that a polynomial $p(x)$ is non-negative on this constrained set $K$? We can't just check if $p(x)$ is SOS, because it might be negative somewhere outside of $K$. We need a certificate that cleverly incorporates the constraints $g_i(x)$.

The inspiration comes from a classic result for quadratic polynomials called the ​​S-lemma​​. It states that for two quadratic functions $p(x)$ and $g(x)$, $p(x) \ge 0$ whenever $g(x) \ge 0$ if and only if there's a non-negative "fudge factor" $\lambda \ge 0$ such that the new polynomial $p(x) - \lambda g(x)$ is non-negative everywhere. This brilliantly converts a constrained problem into an unconstrained one.

Generalizing this idea to multiple, non-quadratic polynomials leads to the core idea of the ​​Positivstellensatz​​ (German for "theorem of the positive"). We can construct a certificate for the non-negativity of $p(x)$ on the set $K = \{x \mid g_i(x) \ge 0\}$ using SOS multipliers. One common form of such a certificate is the identity:

where each $\sigma_i(x)$ is an SOS polynomial. Let's see why this works. For any point $x$ inside our set $K$, we know that each $g_i(x)$ is non-negative. We also know that each $\sigma_i(x)$ is non-negative because it's a sum of squares. So, every term on the right-hand side is non-negative, and their sum, $p(x)$, must be non-negative too! This expression is a member of the ​​quadratic module​​ generated by the constraints $\{g_i\}$.

For a more complex set, we might need a more complex certificate that includes products of the constraints, like $\sigma_{12}(x) g_1(x) g_2(x)$. This more general structure is called a ​​preordering​​.

Now for the crucial question: if a polynomial $p(x)$ is indeed positive on our set $K$, can we always find such an SOS-based certificate?

The answer, again, is "not always," but we can if the set $K$ is "well-behaved." A landmark result by Mihai Putinar provides the precise condition. ​​Putinar's Positivstellensatz​​ gives us a powerful guarantee. It states that if a polynomial $p(x)$ is strictly positive on $K$, then it has a certificate of the simpler quadratic module form, provided that the set of constraints satisfies a condition known as being ​​Archimedean​​.

What is this Archimedean property? Intuitively, it means that the constraint inequalities $g_i(x) \ge 0$ themselves force the set $K$ to be bounded—that is, contained within some giant ball. Algebraically, it means that for some large number $R$, the polynomial $R - \|x\|^2$ can be written using the certificate structure based on the $g_i$'s. This property is crucial because it ensures the problem is confined, preventing functions from behaving strangely at infinity. If the Archimedean property holds, it guarantees that the Lasserre hierarchy, a powerful method for solving polynomial optimization problems, will converge to the true answer. If your problem is on a non-compact set, you can sometimes restore this property by adding a large but redundant ball constraint, a very clever practical trick.

Putinar's theorem is a cornerstone of modern polynomial optimization. It provides a computationally tractable way to certify positivity on constrained sets, forming a bridge between abstract algebra and practical problems in engineering and control. It's more popular in practice than a related result by Schmüdgen, which applies to any compact set but may require the more complex preordering certificate structure.

Putinar's theorem is a promise: a certificate exists. However, it's a bit like a treasure map that guarantees a treasure exists but doesn't say how deep you have to dig. The theorem doesn't tell us the degree of the SOS multiplier polynomials $\sigma_i(x)$ required.

In some nasty cases, this degree can be astronomically high. Consider a polynomial that is positive but becomes very flat—approaching zero with many zero derivatives—near the boundary of the set $K$. Certifying the positivity of such a polynomial requires SOS multipliers of extremely high degree.

This is not just a theoretical curiosity; it has profound practical consequences. A high-degree SOS multiplier means the corresponding Gram matrix in the SDP will be enormous. This leads to SDPs that are not only slow to solve but also numerically fragile, prone to errors, and may fail to converge at all. This is a major challenge and an active area of research. Engineers and mathematicians are constantly developing new techniques, such as using more restricted but computationally cheaper forms of SOS like DSOS (diagonal sum-of-squares), to strike a balance between theoretical guarantees and practical solvability.

The journey from a simple question of positivity to the frontiers of computational mathematics reveals a beautiful interplay of ideas. The Positivstellensatz provides a powerful framework, but its practical application demands a deep understanding of both its power and its limitations, pushing us to find ever more clever ways to solve the problems that matter.

At first glance, a theorem like the Positivstellensatz, a deep result from real algebraic geometry, seems to belong to the most abstract realms of pure mathematics. It answers a question that sounds deceptively simple: when can we know for certain that a polynomial—a familiar expression of variables and coefficients—is non-negative over a particular region? You might wonder what this has to do with the tangible world of physics and engineering, of flying robots, power grids, and autonomous vehicles. The answer, it turns out, is everything.

The bridge between abstract algebra and the real world is the concept of a ​​certificate​​. In many critical applications, it is not enough to believe something is safe or stable; we must be able to prove it with mathematical certainty. The Positivstellensatz provides a remarkable, constructive way to generate such proofs, turning questions of geometry and dynamics into problems of algebra that a computer can solve. Let's take a journey through some of these applications to see how this beautiful piece of mathematics becomes a powerful engineering tool.

The first and most fundamental application is in the study of stability. Imagine a marble at the bottom of a perfectly shaped bowl. Nudge it, and it will roll back to the bottom. This is the essence of a stable equilibrium. In the 19th century, the great Russian mathematician Aleksandr Lyapunov formalized this intuition. He showed that a system is stable if one can find an energy-like function, which we now call a Lyapunov function $V(x)$, that is always positive except at the equilibrium (where it's zero) and whose value always decreases as the system evolves. Geometrically, the system's state $x$ is always rolling downhill on the surface described by $V(x)$.

This is a beautiful idea, but how do we find such a function $V(x)$ for a complex system, say, one whose motion is described by a set of polynomial equations $\dot{x} = f(x)$? And how can we be sure that its derivative, $\dot{V}(x) = \nabla V(x)^\top f(x)$, is truly negative everywhere it needs to be?

This is where our theorem enters the stage. If we decide to look for a polynomial Lyapunov function $V(x)$, then the conditions for stability—$V(x) > 0$ and $\dot{V}(x) < 0$—become questions about the positivity of polynomials. While checking if a polynomial is positive everywhere is computationally very hard, there is a much simpler, sufficient condition: checking if it can be written as a ​​Sum of Squares (SOS)​​ of other polynomials. If a polynomial $p(x)$ can be expressed as $p(x) = \sum_i h_i(x)^2$, it is obviously non-negative. This check can be transformed into a highly efficient type of convex optimization problem known as a Semidefinite Program (SDP), which computers can solve.

Thus, we can ask a computer to search for a polynomial $V(x)$ such that $V(x) - \epsilon \|x\|^2$ and $-\dot{V}(x) - \delta \|x\|^2$ (for some small positive constants $\epsilon, \delta$) are both sums of squares. If the computer finds such a $V(x)$, we have an ironclad certificate of stability! This SOS approach has a crucial limitation, however: not every non-negative polynomial is a sum of squares. Furthermore, in practice, we must limit the degree of the polynomials we search over. This means our search is conservative; failure to find a Lyapunov function doesn't prove the system is unstable, only that we didn't find one with the structure we looked for. Nonetheless, it is an incredibly powerful method for certifying stability in complex nonlinear systems.

Stability is about staying near a single point. But often, we have a more general goal: ensuring a system's state remains within a designated "safe set" $\mathcal{S}$ and never enters an "unsafe set" $\mathcal{U}$. Think of a chemical reactor whose temperature must stay within a certain range, or a self-driving car that must remain on the road.

Here, we can use a similar idea, but instead of a bowl, we imagine an "electric fence." Let's define a ​​barrier certificate​​ $B(x)$, a polynomial such that the safe set is where $B(x) \le 0$ and the unsafe set is where $B(x) > 0$. If we can prove that whenever the system reaches the boundary of the safe set (where $B(x)=0$), the dynamics $\dot{x}=f(x)$ are always pushing it back into the safe set, then the system can never escape. The mathematical condition for this is that the derivative $\dot{B}(x)$ must be non-positive on the boundary.

This, once again, is a question about the sign of a polynomial on a set. Suppose our safe set is defined by polynomial inequalities, say $\mathcal{S} = \{ x \mid g_i(x) \ge 0 \}$. To prove a property like $\dot{B}(x) \le 0$ on this set, we can invoke the full power of the Positivstellensatz. The theorem provides an algebraic recipe: to prove that a polynomial $p(x)$ is non-negative on the set where all $g_i(x)$ are non-negative, we can search for a set of SOS "multiplier" polynomials $s_i(x)$ such that the expression $p(x) - \sum_i s_i(x) g_i(x)$ is itself a sum of squares. Finding these multipliers provides a certificate of the property. The theorem guarantees that for any polynomial that is strictly positive on a compact set, such a representation exists. For a polynomial that is merely non-negative, we can add a tiny positive "slack" term $\varepsilon$ and prove that the shifted polynomial is positive, which is often sufficient in practice. In this way, we can construct certified safety fences for complex polynomial systems.

So far, we have been acting as detectives, analyzing a system that is already built. But the real thrill is to be the architect—to design a controller that makes a system behave as we wish. Consider a system with control inputs, $\dot{x} = f(x) + G(x)u$. The stability or safety conditions on $V(x)$ or $B(x)$ now depend on the control $u$. For a ​​Control Lyapunov Function (CLF)​​, the condition becomes: for every state $x$, does there exist a control $u$ that makes $\dot{V}(x)$ negative?

This "there exists" quantifier is the key. Instead of just verifying a property, we are now asking to synthesize a control law. The Positivstellensatz framework allows us to do just that. We can decide to search for a polynomial controller $u(x)$ and a Lyapunov function $V(x)$ simultaneously. The condition $\dot{V}(x, u(x)) < 0$ becomes a large polynomial inequality involving the unknown coefficients of both $V(x)$ and $u(x)$. We can then formulate this as a massive SOS program. If the program is feasible, it doesn't just tell us the system is stabilizable; it hands us the controller that does the job, and it gives us the Lyapunov function that proves it! The same logic applies to synthesizing controllers that guarantee safety using ​​Control Barrier Functions (CBFs)​​.

The framework is so flexible that we can even incorporate real-world physical constraints, such as actuator saturation. If our control input has a maximum value, $|u| \le u_{max}$, this is just another polynomial inequality, $u_{max}^2 - u^2 \ge 0$. We can add this to our SOS program, using another multiplier, to ensure the controller we design is physically realizable.

A persistent question in all of this is: where does the polynomial model $\dot{x} = f(x)$ come from? For simple physical systems, we can derive it from first principles. But for many complex systems in biology, economics, or robotics, we may not know the governing equations. All we have is data—observations of how the system behaves.

This is where the Positivstellensatz provides a stunning connection to the world of data science and machine learning. The modern approach is a two-step dance. First, use machine learning techniques to fit a polynomial model, $\hat{f}(x)$, to the available data. This gives us a candidate model of reality. Second, take this data-driven polynomial model and apply the entire SOS and Positivstellensatz machinery to it. We can then search for a Lyapunov function to certify the stability of our learned model. This provides a formal, rigorous guarantee rooted in data, bridging the gap between the uncertain world of empirical observation and the certain world of mathematical proof. It allows us to make trustworthy statements about systems we may not fully understand.

We have seen that the Positivstellensatz and its computational counterpart, Sum-of-Squares programming, offer a unified and powerful framework for the analysis and design of systems described by polynomials. It allows us to certify stability, guarantee safety, and even synthesize controllers, sometimes from data alone.

But this power does not come for free. The size of the semidefinite programs we need to solve grows combinatorially with the number of variables and the degree of the polynomials involved. This "curse of dimensionality" means that while the theory is elegant, its application is an engineering art. A blind search for high-degree certificates will quickly overwhelm any computer.

In practice, engineers use intelligent, adaptive strategies. They start by searching for low-degree certificates. If the search fails, it doesn't mean a certificate doesn't exist, only that a simple one doesn't. The optimization can even provide a "counterexample"—a state where the condition is most violated. Guided by this information, the engineer can choose to increase the degree of the Lyapunov function or, more selectively, the degree of the specific multipliers associated with the "active" constraints. This human-in-the-loop process balances the theoretical completeness of the Positivstellensatz with the practical limits of computation.

And so, we arrive at a beautiful picture. A deep theorem from abstract algebra provides the foundation for a computational tool that, when wielded with skill and intuition, allows us to build the safe, reliable, and complex technologies of the future. It is a profound testament to the intricate and often surprising connections that unify the world of mathematics and the world around us.