Structure of Polynomials

Gödel’s Lost Letter and P=NP 2024-03-26

A feature in the current AMS Notices issue highlighting women in mathematics

Marie-Françoise Roy is a French mathematician, emerita of the Institute for Mathematical Research of the University of Rennes, where she has been since 1985. She works in real algebraic geometry, but her own statement of her research theme prefaces a key word: algorithmes de la géométrie algébrique réelle.

This theme is picked up in a wonderful article by Saugata Basu in this month’s special issue of the AMS Notices—which is dedicated to Women in Mathematics. He is a professor in the mathematics and computer science departments of Purdue University.

His article highlights Roy’s beautiful work on the structure of polynomials over the real numbers. These results are close to things near and dear to us in complexity theory. We don’t just mean single-variable polynomials that bound the running time and space usage of algorithms we regard as theoretically efficient. We mean multi-variable polynomials into which many combinatorial problems can be translated—in a manner often richer than the translations into Boolean formulas that we teach first in complexity theory.

The University of Bath gave Roy an honorary doctorate in 2022. The oration by Greg Sankaram hailed both Roy and Basu, after saying how Roy had broken a barrier of surprising differences between algebraic geometry over ${\mathbb{R}}$ versus over ${\mathbb{C}}$ :

Real algebraic geometry underlies algorithms that have many applications in computer science, engineering and other areas. Such algorithms are again surprisingly unlike most others. It took her another twenty years to break down that barrier, with a book written with Basu and [Richard] Pollack called “Algorithms in Real Algebraic Geometry.”

Some Results

The springboard for Basu’s article is Emil Artin’s positive solution to David Hilbert’s 17th problem:

Theorem 1 Every nonnegative polynomial over the reals can be written as a sum of squares of rational functions.

As Basu explains, the most accessible proof of this theorem is nonconstructive: Given a polynomial ${P(x_1,\dots,x_n)}$ that is assumed to have all nonnegative values, we suppose for sake of contradiction that ${P}$ is not a sum of squares of rational functions. Using Zorn’s lemma, we can then create an ordering ${\prec}$ of the field ${F}$ of rational functions ${\mathbb{R}(x_1,\dots,x_n)}$ such that some value of ${P}$ over ${F^n}$ is ${\prec 0}$ . This feature carries over to the real closure of this field. Then a theorem of Alfred Tarski and Abraham Seidenberg kicks in to show that ${P}$ must have a negative value over ${\mathbb{R}^n}$ , which is a contradiction.

This proof leaves open the questions:

Can we compute the sum-of-squares representation of ${P}$ ? If so, how long does it take?

After going through some of Roy’s other work, Basu comes back to Artin’s theorem and gives this key result of hers with Henri Lombardi and Daniel Perrucci:

Theorem 2 Let ${P \in \mathbb{R}[x_1 , ... , x_n]}$ be a nonnegative polynomial of degree at most ${d}$ . Then ${P}$ can be written as a sum of squares of rational functions, and the degrees of the numerators and denominators of these rational functions are bounded by
$\displaystyle 2^{2^{2^{d^{4^n}}}}.$

Well, that is a terrifying exponential stack. But it is at least a bound, and the proof is effective. Here is the end of what Basu says about it:

In summary, the idea behind the proof of this theorem is the following. Start from a quantifier elimination algorithm applied to the given sign condition. Convert the steps of the algorithm into a proof each of whose steps are logical deductions of a certain type. Prove weak inference-existence versions of these steps and make a careful accounting of how the degrees are growing in each step.

Better Bounds

Basu emphasizes complexity notions throughout his article, and focuses on the notion of a certificate. He prefaces his relevant sections on Roy’s work by citing Hilbert’s Nullstellensatz for polynomials over ${\mathbb{C}}$ . This says that if a set of polynomial equations

$\displaystyle P_1(x_1,\dots,x_n) = 0, \quad P_2(x_1,\dots,x_n) = 0, \dots, P_s(x_1,\dots,x_n) = 0$

is not solvable over ${\mathbb{C}}$ , then there are polynomials ${q_1,q_2,\dots,q_s}$ such that

$\displaystyle q_1 P_1 + q_2 P_2 + \cdots + q_s P_s = 1.$

This is an instant proof that the equations are unsolvable, because any solution would make ${0 = 1}$ here. This means that equation solving over ${\mathbb{C}}$ has certificates both ways:

If the equations are solvable, we can guess a solution and verify it.
If the equations are not solvable, there are ${q_1,\dots,q_s}$ that we can guess, and then verify that the above sum of products multiplies out to cancel all terms except ${1}$ .

We covered some logical ramifications of this long ago here. The reason this doesn’t put the equation solving problem into (an algebraic analogue of) ${\mathsf{NP \cap co}\text{-}\mathsf{NP}}$ is that the ${q_i}$ polynomials can need to be exponentially bigger than the given ${P_i}$ polynomials, for instance in their total degrees. But as Basu references, work in the past forty years have bounded the size by at worst a single exponential in that and some other respects.

The degree bound in the last section is far from a single exponential. Moreover, the Nullstellensatz does not hold over ${\mathbb{R}}$ : the single equation ${P_1 = x^2 + 1 = 0}$ is a counterexample. However, Basu exhibits how Roy has obtained certificates in more-specialized cases of equations and inequalities over ${\mathbb{R}}$ , often with single-exponential bounds. He also describes how Roy pays special attention to the two other complexity parameters besides ${n}$ here: the number ${s}$ of polynomials and their maximum degree ${d}$ .

More Certificates

In the case of Artin’s theorem, the certificate for ${P}$ being nonnegative over ${\mathbb{R}^n}$ is the finite set of rational functions ${r_1,\dots,r_s}$ such that

$\displaystyle P = r_1^2 + \cdots + r_s^2.$

As we’ve noted, Roy’s joint theorem is far from bringing the degrees of the numerators and/or denominators of the ${r_i}$ down to single exponential. There is, however, room for creativity in devising other kinds of certificates. This has led to various results grouped under the general name Positivstellensatz.

What is cool to us is the tradeoff: Often theorems about the existence of solutions to polynomial systems can be proved in a non-effective manner. But proving these results with effective bounds is often much harder. This is clearly of great importance to those of us interested in complexity theory. Proving there is an object is often much easier than proving a bound on the “size” of complexity of the object.

Basu says later in his article:

From her I learned that one does not really understand a proof (even one’s own) unless one is able to “see” it and the vital importance of proper notation in writing and communicating mathematics.

This segues us to a final mention of Roy’s work communicating the love of mathematics to women in particular. She was the first leader of France’s society Femmes et Mathematiques in the 1980s and served in a similar role for the European Women in Mathematics from 2009 to 2013. Basu mentions also her outreach activities in Africa.

Open Problems

How much can those stacks of exponentials be reduced? What further development of Roy’s work—and good new notations—might help to do so?

Other articles in this issue of the AMS Notices are great reads as well, and I believe you will enjoy them.