Sturm Distinct Real Root Count

Sturm's theorem provides a powerful method to determine the exact number of distinct real roots of a polynomial within a given interval. Unlike numerical root-finding methods that approximate solutions, Sturm's theorem offers a mathematical certainty—a certified count—by analyzing the sign variations in a sequence of polynomials derived from the original function.

Worked Example: Counting Roots

Let's count the distinct real roots of the polynomial f(x) = x³ - 3x + 2 on the interval (-2, 1]. First, we must construct the Sturm sequence. To handle multiple roots correctly without counting them twice, we use the square-free part of the polynomial.

We find the derivative f'(x) = 3x² - 3. The greatest common divisor (GCD) of f(x) and f'(x) is x - 1. Dividing f(x) by this GCD gives the square-free polynomial p(x) = x² + x - 2, which has degree 2.

The Sturm sequence starts with p₀(x) = p(x) and p₁(x) = p'(x) = 2x + 1. Subsequent terms are the negative remainders of the Euclidean division of the previous two terms. Dividing p₀ by p₁, the negative remainder is p₂(x) = 9/4. Thus, the complete Sturm sequence is:

p₀(x) = x² + x - 2
p₁(x) = 2x + 1
p₂(x) = 9/4

Next, we evaluate the sign of this sequence at the endpoints a = -2 and b = 1.

At x = -2:
p_0(-2) = (-2)^2 + (-2) - 2 = 0
p_1(-2) = 2(-2) + 1 = -3 (negative)
p_2(-2) = 9/4 (positive)
Sequence of signs (ignoring zeros): -, +
Number of sign variations V(-2) = 1

At x = 1:
p_0(1) = 1^2 + 1 - 2 = 0
p_1(1) = 2(1) + 1 = 3 (positive)
p_2(1) = 9/4 (positive)
Sequence of signs (ignoring zeros): +, +
Number of sign variations V(1) = 0

By Sturm's theorem, the number of distinct real roots in (-2, 1] is V(-2) - V(1) = 1 - 0 = 1.

Experiment with Polynomials

You can use the interactive module to explore different polynomials and intervals: https://riano.app/module/sturm-distinct-root-count.

Select the Repeated polynomial: x³ - 3x + 2.
Set Endpoint a to -2.
Set Endpoint b to 1.
Observe the certified count: Distinct roots in interval is 1. The square-free degree is shown as 2.
Change the polynomial to Distinct (x³ - x) and the interval to [-1, 0]. The count updates to reflect the roots in that specific region.

Assumptions and Limitations

This method relies on exact rational arithmetic to avoid numerical instability during the Euclidean algorithm, which is highly sensitive to rounding errors in floating-point operations. Small deviations can flip the signs of sequence terms, completely invalidating the root count. The interval evaluated is strictly (a, b], excluding the lower endpoint and including the upper. If the endpoints are equal, the interval is empty, and the count is 0. Additionally, the polynomial coefficients must be exact rational numbers for this precise sequence construction.

References

The computational foundation for this counting method is described in the CGAL documentation: CGAL Polynomial Reference: number_of_real_roots.

Sturm Distinct Real Root Count