CHAPTER 1

Overview

In mathematics and its applications, we are often faced with a system of multi-

variate polynomial equations whose solutions we need to study or to find. Systems

that arise naturally typically possess some geometric or combinatorial structure that

may be exploited to better understand their solutions. Such structured systems are

studied in enumerative algebraic geometry, which has given us the deep and pow-

erful tools of intersection theory [54] to count and analyze their complex solutions.

A companion to this theoretical work are algorithms, both symbolic (based on

Gr¨ obner bases [154] or resultants) and numerical (many based on numerical homo-

topy continuation [137]) for solving and analyzing systems of polynomial equations.

An elegant and elementary introduction into algebraic geometry, algorithms, and

its applications is given in the two-volume series [31, 30].

Despite these successes, this line of research largely sidesteps the often pri-

mary goal of formulating problems as solutions to systems of equations—namely to

determine or study their real solutions. This deficiency is particularly acute in ap-

plications, from control [25], to kinematics [22], statistics [114], and computational

biology [110], for it is typically the real solutions that are needed in applications.

One reason that traditional algebraic geometry ignores the real solutions is that

there are few elegant theorems or general results available to study real solutions.

Nevertheless, the demonstrated importance of understanding the real solutions to

systems of equations demands our attention.

In the 19th century and earlier, many elegant and powerful methods were de-

veloped to study the real roots of univariate polynomials (Sturm sequences, Budan-

Fourier Theorem, Routh-Hurwitz criterion), which are now standard tools in some

applications of mathematics. These and other results lead to a rich algorithmic

theory of real algebraic geometry, which is developed in [4]. In contrast, it has

only been in the past few decades that serious attention has been paid toward

understanding the real solutions to systems of multivariate polynomial equations.

This recent work has concentrated on systems possessing some, often geomet-

ric, structure. The reason for this is two-fold: Not only do systems from nature

typically possess some special structure that should be exploited in their study, but

it is highly unlikely that any results of substance hold for general or unstructured

systems. From this work, a story has emerged of bounds (both upper and lower)

on the number of real solutions to certain classes of systems, as well as the dis-

covery and study of systems that have only real solutions. This overview chapter

will sketch this emerging landscape and the subsequent chapters will treat these

ongoing developments in more detail.

We will use the notations N, Z, Q, R, and C, to denote the natural numbers,

integers, rational numbers, real numbers, and complex numbers. We write R

for the positive real numbers, and

R∗

(or TR) and

C∗

(or T) for the nonzero real

1

http://dx.doi.org/10.1090/ulect/057/01