About a year ago I had the pleasure of having a number of conversations with Abhishek Bhardwaj about the area of mathematics his PhD is on. This pair of posts is based on the fond memories I have of these conversations. Part two can be found here.
Optimization and Summing Squares
Optimization is a huge area of both pure and applied mathematics. Many questions and problems can be reduced to finding the minimum or maximum value of some function. That is we have a function and we wish to find the number
such that
,
or
.
By considering the function we can reduce finding the maximum of
to finding the minimum of another function. Minimizing a function isn’t always easy. Even when the function
is a relative simple function such as a polynomial, it can be a very difficult problem.
A different way of thinking about the problem of minimizing the function , is to instead think about the function
were
is a real number. The minimum of
is the largest value of
such that the function
is non-negative for all values
. Thus we have a reduced our optimization problem into the problem of working out for which values of
is the function
non-negative.

An example
Suppose our function was the following function that takes in two variables
.
To minimize this function we can look at the function which is equal to
.
We wish to work for which values of is this function
non-negative. By doing the following algebraic manipulations we can rewrite
like so
,
which is in turn equal to
Since and
are both squares of real numbers, they are both non-negative. Furthermore at the point
, we have that
. Thus
is non-negative if and only if
, that is if and only if
. Thus we can conclude that the minimum of
is
.
Sums of Squares
Note that the number can be written as
if and only if
. Thus, in the above example we have that
is non-negative if and only if
can be written as a sum of squares. That is
is non-negative if and only if
can be written as
for some polynomials
.
In general, if a polynomial can be written as a sum of squares of other polynomials, then the polynomial must be non-negative. A natural question to ask is if every non-negative polynomial can be written as a sum of squares. This would make our optimization problem a lot easier. To minimize , we can check for which values of
can
be written as a sum of squares.
This question of whether every non-negative polynomial can be written as a sum of squares was answered in the negative by David Hilbert in 1888. However, Hilbert’s proof was non-constructive, it didn’t give an explicit example of such a polynomial. The proof only showed that such polynomials exist out there somewhere. It took nearly nearly 80 years for the first explicit example to be given by the mathematician Theodore Motzkin in 1967. We will take a look at Motzkin’s polynomial in the next blog post.
One thought on “Sums of Squares – Part 1: Optimization”