🔢 mathematics

Making Non-Negative Polynomials into Sums of Squares

This paper develops a theory of linear operators and semi-groups on polynomial spaces, specifically constructing an efficient transformation that maps non-negative polynomials on a set with non-empty interior to sums of squares while requiring minimal memory and computational operations.

Original authors: Philipp J. di Dio

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Philipp J. di Dio

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy room filled with objects. Some objects are "good" (they are non-negative, meaning they are zero or positive), and some are "bad" (they are negative). In the world of math, these objects are polynomials (equations with variables like $x$ and $y$ ).

Mathematicians have long struggled with a specific problem: How do you take a "good" object that isn't a perfect square (like a perfect cube or a perfect sphere) and turn it into a Sum of Squares?

Why does this matter? Because "Sums of Squares" are like the "gold standard" of good objects. They are easy to check, easy to calculate with, and very stable. If you can turn any "good" object into a "Sum of Squares," you can solve huge, difficult problems much faster.

This paper is about building a magic machine (a linear operator) that does exactly this: it takes a messy pile of "good" polynomials and transforms them into the neat, organized pile of "Sums of Squares."

Here is how the author, Philipp di Dio, explains the mechanics of this machine using simple concepts:

1. The "Time-Travel" Machine

Usually, if you want to change a shape, you might try to stretch or twist it. But this paper uses a concept called a flow. Imagine you have a video of the room. You press "play," and over time, the objects in the room slowly morph.

The author studies a specific type of machine that runs on a "time dial" ( $t$ ). As you turn the dial forward, the machine applies a gentle, continuous push to the polynomials.

The Goal: Find the right "push" (a generator $A$ ) so that if you let the machine run for a certain amount of time, every "good" polynomial ends up as a "Sum of Squares."
The Result: The paper proves that for polynomials up to a certain size (degree), there is a specific time $\tau$ where, if you run the machine, every non-negative polynomial becomes a Sum of Squares.

2. The "Infinite Library" vs. The "Finite Shelf"

Polynomials can be infinitely complex. You could have a polynomial with $x^{1,000,000}$ .

The Problem: If you try to build a machine for all polynomials at once, it's like trying to organize an infinite library. It's impossible to do efficiently.
The Solution: The author realizes that in the real world, we usually only care about polynomials up to a certain size (e.g., up to degree 10 or 20).
The Magic Trick: The paper shows that even though the library is infinite, the machine only needs to look at a finite shelf at a time. It treats the infinite library as a stack of finite shelves. This allows the machine to work without getting stuck in an infinite loop.

3. The "Super-Efficient" Calculator

This is the most surprising part of the paper. Usually, transforming a list of numbers (a matrix) is like moving a mountain.

The Old Way: If you have a list of $N$ items, transforming them usually takes about $N^3$ steps (like $1,000,000$ steps for a small list). This is slow and computationally expensive.
The New Way: The author designs a machine so special that it only takes about $N^2$ steps (like $1,000$ steps).
The "One-Click" Inverse: Even more amazing, if you want to undo the transformation (go back to the original messy room), the machine doesn't need to do a complex calculation. It just needs to perform one single division. It's like having a magic button that instantly reverses time.

4. The "Impossible" Task

The paper also draws a line in the sand. It proves that if you try to do this for every single polynomial in the universe (without limiting the size), it is impossible.

The Metaphor: Imagine trying to fit an infinite ocean into a finite bucket. The paper shows that no matter how clever your machine is, you cannot turn every non-negative polynomial into a Sum of Squares if you allow the polynomials to get infinitely large. You must set a size limit (a degree bound) for the magic to work.

5. A Glimpse into Chaos (The "Non-Markov" Example)

In the final section, the author shows what happens when you use a machine that isn't this perfect, smooth flow. He uses an equation from fluid dynamics (Burgers' equation) to show that if the rules change too wildly, the "good" objects can suddenly turn "bad" (negative) in a finite amount of time. This is like a smooth river suddenly hitting a waterfall and splashing into chaos. It serves as a warning: the smooth, predictable machine described in the main part of the paper is special and necessary for this job.

Summary

The paper builds a mathematical time-machine that, when set to the right speed, instantly organizes any "good" polynomial (up to a certain size) into a perfect "Sum of Squares."

It is extremely fast (much faster than standard methods).
It is reversible with almost zero effort.
It works perfectly only if you limit the size of the polynomials.

The author essentially says: "We found a way to turn a messy, hard-to-check pile of numbers into a clean, easy-to-check pile, and we did it with a machine that is surprisingly cheap to run."

Technical Summary: Making Non-Negative Polynomials into Sums of Squares

Problem Statement
The paper addresses the challenge of transforming sets of non-negative polynomials, denoted as $\text{Pos}(K)$ for a closed set $K \subseteq \mathbb{R}^n$ , into the cone of sums of squares (SOS), denoted as $\Sigma \mathbb{R}[x_1, \dots, x_n]^2$ . While non-negative polynomials and moment sequences are well-studied, they are computationally difficult to handle because not all non-negative polynomials are sums of squares (Motzkin, 1967) and not all square-positive functionals are moment functionals (Scheiderer, 1979). The author investigates linear operators $T: \mathbb{R}[x_1, \dots, x_n] \to \mathbb{R}[x_1, \dots, x_n]$ that map $\text{Pos}(K)$ into the SOS cone, effectively "preconditioning" the set of non-negative polynomials to a more tractable form. This is motivated by applications in optimization where minimizing a functional over a set $S$ can be transformed into minimizing over $TS$, potentially improving numerical stability or enabling the use of SOS-based solvers.

Methodology
The core methodology relies on the theory of regular Fréchet Lie groups and their associated Lie algebras acting on the space of polynomials.

Operator Semigroups: The author studies operators of the form $T_t = e^{tA}$ , where $A$ is a linear generator. The set of such generators, denoted $\mathfrak{g}$ , is characterized by the property that $e^{tA}$ maps polynomials to polynomials for all $t \in \mathbb{R}$ .
Canonical Representation: Utilizing the canonical representation of linear operators on polynomials, $T = \sum q_\alpha \cdot \partial^\alpha$ , the paper connects $K$ -positivity preservers to $K$ -moment sequences via Theorem 1.1 (from dD25).
Finite-Dimensional Invariant Subspaces: A key technical tool is Theorem 3.3, which establishes that for any $A \in \mathfrak{g}$ , there exists a filtration of finite-dimensional invariant subspaces $V_i$ covering the polynomial ring. This allows the infinite-dimensional operator exponential to be computed via limits of matrix exponentials on these finite subspaces.
Specific Operator Construction: To achieve the mapping from non-negative polynomials to SOS, the author constructs a specific rank-one operator $A$ defined by $Ap = \ell(p) \cdot f$ , where $\ell$ is a linear functional positive on the cone and $f$ is an interior point of the target SOS cone.

Key Contributions and Results

Characterization of Generators ( $\mathfrak{g}$ ): The paper fully characterizes the set $\mathfrak{g}$ of generators for which $e^{tA}$ is a well-defined group on the polynomial ring. It is shown that $\mathfrak{g}$ is a cone but not a vector space (it is not closed under addition or multiplication in general). However, subsets of $\mathfrak{g}$ sharing common invariant finite-dimensional subspaces form regular Fréchet Lie algebras.
Stochel's Theorem (Three-Line Proof): The author provides a concise proof of Stochel's Theorem (2001), which states that a sequence is a $K$ -moment sequence if and only if its truncations are truncated $K$ -moment sequences. This proof relies on the duality between polynomials and sequences and Haviland's Theorem.
Generators of $K$ -Positivity Preserving Semigroups: Theorem 6.3 provides a resolvent description for generators $A \in \mathfrak{g}$ that preserve $K$ -positivity. This generalizes previous results and offers a complete, albeit abstract, characterization.
Transformation to Sums of Squares (Theorem 7.1): The central result demonstrates that for a fixed degree bound $d$ , there exists a linear operator $T = e^{\tau A}$ that maps any set of non-negative polynomials $S \subseteq \text{Pos}(K)_{\le 2d}$ into the cone of sums of squares $\Sigma \mathbb{R}[x_1, \dots, x_n]^2_{\le d}$ .
Computational Efficiency: The paper emphasizes that the specific structure of the constructed operator $T$ $T$ (a rank-one update to the identity) leads to extreme computational efficiency:
- Memory: Storing the operator matrix $\tilde{T}$ requires only $2N + 1$ scalars (where $N = \dim \mathbb{R}[x]_{\le 2d}$ ), reducing storage from $O(N^2)$ to $O(N)$ .
- Complexity: Matrix-vector multiplication ($Tv$) requires at most $4N + 1$ operations. Matrix-matrix multiplication ( $\tilde{T}M$ ) requires at most $4N^2 + 1$ operations.
- Inversion: Calculating the inverse operator $\tilde{T}^{-1}$ requires only one operation (a division), a stark contrast to the $O(N^3)$ or higher complexity of standard matrix inversion.
Impossibility Result (Theorem 7.5): The paper proves that for compact $K$ , no injective linear operator $T$ exists that maps the entire infinite-dimensional cone $\text{Pos}(K)$ into the SOS cone without degree bounds. This highlights the necessity of the degree constraints in the main theorem.
Non-Markovian Example: Section 8 presents an example using the Burgers' equation to illustrate a time-evolution that is not a homogeneous Markov process, demonstrating that the theory of $e^{tA}$ does not cover all possible polynomial evolutions.

Significance and Claims
The paper claims that the developed theory provides a computationally feasible method to transform non-negative polynomials into sums of squares, a task that is generally hard due to the gap between non-negativity and SOS. The significance lies in the algorithmic efficiency of the proposed transformation. By utilizing operators from regular Fréchet Lie groups with specific structural properties, the author achieves a complexity that meets the trivial lower bound for matrix operations ( $O(N^2)$ ) and reduces inversion to a single operation.

The author explicitly states that while the transformation $T$ and its inverse are efficient to compute, the approach is limited to fixed degree bounds. The paper does not claim to solve the general problem of representing all non-negative polynomials as SOS (which is impossible), but rather provides a tool to move specific subsets of non-negative polynomials into the SOS cone for the purpose of optimization or numerical stability (preconditioning). The work serves as a bridge between the abstract theory of infinite-dimensional Lie groups and practical computational algebraic geometry.