Introduction
Determining the location of a polynomial's zeros is a fundamental problem in control theory, signal processing, and algebraic combinatorics. While classical tools like the Routh-Hurwitz criterion or Sturm's sequences exist, they can be computationally intensive or difficult to generalize. In "Polynomials with All Zeros Real and in a Prescribed Interval," Jean B. Lasserre introduces a finite, algebraic method to verify if all zeros of a univariate polynomial are real and contained within a specific interval $[a, b]$.
The Moment Problem Framework
The core innovation of Lasserre's approach is bridging polynomial algebra with the $K$-moment problem. The $K$-moment problem asks whether a given sequence of numbers can represent the moments of a measure supported on a set $K$.
Lasserre treats the $n$ zeros of a polynomial $\theta(x)$ as the support of a discrete probability measure. If one can prove that a measure with specific "moments" must be supported on $[a, b]$, then the roots of the polynomial must also lie within that interval.
1. Newton’s Sums as Moments
The process begins by converting the polynomial's coefficients into normalized Newton’s sums ($s_k$). For a polynomial with zeros $x_1, \dots, x_n$, the $k$-th Newton sum is defined as: $$s_k = \frac{1}{n} \sum_{i=1}^n x_i^k$$ These sums can be calculated recursively from the coefficients using Newton's identities, avoiding the need to actually find the roots.
2. Matrix Construction
From these sums, two primary matrices are constructed:
- Moment Matrix $M(n, s)$: A Hankel matrix where the entry at $(i, j)$ is $s_{i+j-2}$. This matrix captures the global properties of the distribution of roots.
- Localizing Matrix $B(n, s)$: A matrix derived from the moment sequence that "localizes" the support. For example, to check if roots are in $[0, \infty)$, one examines a matrix related to the sequence $s_{k+1}$.
Key Theoretical Results
The paper provides definitive algebraic conditions for root localization using semidefinite programming (SDP) principles.
Theorem 3.1: Nonpositive Real Zeros
A polynomial has all zeros real, nonpositive, and distinct if and only if:
- The moment matrix $M(n, s)$ is positive semidefinite ($M(n, s) \succeq 0$).
- The localizing matrix $B(n, s)$ is negative semidefinite ($B(n, s) \preceq 0$).
- The rank of $M(n, s)$ equals the number of distinct zeros.
Theorem 3.2: General Interval $[a, b]$
For a general closed interval $[a, b]$, the condition is expressed as a "sandwich" inequality: $$bM(n, s) \succeq B(n, s) \succeq aM(n, s)$$ This elegant formulation allows researchers to verify root properties through standard linear algebra checks or SDP solvers.
Insights and Implications
- Rank and Multiplicity: A significant finding is that the rank of the moment matrix $M(n, s)$ exactly matches the number of distinct zeros. This provides a simultaneous check for both the location and the multiplicity of roots.
- Constructive Nature: Unlike theoretical results that require infinite checks (like those involving infinite Toeplitz matrices), Lasserre’s method is entirely constructive and finite. The paper demonstrates this with a 3rd-degree polynomial example, showing exactly how the $3 \times 3$ matrices are formed from coefficients.
Limitations and Future Directions
While theoretically robust, the method faces practical challenges:
- Numerical Sensitivity: Hankel matrices are famously ill-conditioned. For high-degree polynomials, small errors in coefficients or Newton sums can lead to significant numerical instability when checking for positive semidefiniteness.
- Multivariate Extension: The current work is restricted to univariate polynomials. A natural extension involves characterizing the common zeros of multivariate systems—determining if they lie within a specific box, sphere, or semi-algebraic set.
Summary updated