Polynomials as coefficient sequences¶

Store a₀ + a₁x + … + aₙxⁿ as the finite sequence (a₀, a₁, …, aₙ), then use exact rational arithmetic to evaluate it and count real roots.

What we already know

Rational values have exact equality and arithmetic. They can therefore act as coefficients without introducing floating-point approximation.

By the end, you can

map a coefficient sequence to a polynomial;
explain why a custom initializer removes trailing zeroes;
follow Horner evaluation and the construction of a Sturm sequence;
state what Sturm's theorem contributes to the next chapter.

Read beside this chapter

Polynomial source and polynomial tests.

Definition

The sequence (a₀, a₁, a₂) means a₀ + a₁x + a₂x². Coefficients start at the constant term. Addition combines matching positions; multiplication performs coefficient convolution. Substitution uses Horner's identity:

a₀ + a₁x + a₂x² = (a₂x + a₁)x + a₀

Representation

@dataclass(frozen=True, slots=True, init=False, eq=False, repr=False)
class Polynomial:
    _coefficients: tuple[Rational, ...]

    def __init__(self, *coefficients: Rational) -> None:
        if not coefficients:
            coefficients = (Q_ZERO,)
        if any(not isinstance(value, Rational) for value in coefficients):
            raise TypeError("Polynomial coefficients must be Rational")

        normalized = [value.reduction() for value in coefficients]
        while len(normalized) > 1 and normalized[-1] == Q_ZERO:
            normalized.pop()
        object.__setattr__(self, "_coefficients", tuple(normalized))

init=False suppresses dataclass initialization. The custom method reduces coefficients and removes trailing zeroes, so (1,2) and (1,2,0) cannot remain two stored forms of the same polynomial. Because the dataclass is frozen, object.__setattr__ is used only during controlled construction.

Why normalize here but not earlier number systems?

Multiple integer and rational representatives teach equivalence classes. A trailing zero teaches no new construction, so canonical storage makes polynomial algorithms and equality clearer.

Implementation

@log(log_level=31)
def evaluate(self, value: object) -> tuple[Rational, LogMessage]:
    point = cast2r(value)
    result = Q_ZERO
    for coefficient in reversed(self.coefficients):
        result = (result * point + coefficient).reduction()
    return result, lambda: f"{self!r}: x={point!r} -> {result!r}"

For x² - 2, coefficients are (-2, 0, 1). At x=1, Horner's loop moves from 1 to 1 to -1, so the polynomial is negative. At x=2, it is positive.

Counting roots, not merely detecting a sign change¶

A sign change guarantees at least one root for a continuous polynomial, but not exactly one. The implementation uses a Sturm sequence:

def sturm_sequence(value: Polynomial) -> tuple[Polynomial, ...]:
    if not isinstance(value, Polynomial):
        raise TypeError("sturm_sequence expects a Polynomial")
    if value.degree <= 0:
        raise ValueError("a constant polynomial has no Sturm sequence")

    square_free = value.square_free()
    sequence = [square_free, square_free.derivative()]
    while sequence[-1]:
        remainder = sequence[-2] % sequence[-1]
        if not remainder:
            break
        sequence.append(-remainder)
    return tuple(sequence)

Sturm's theorem says that, when endpoints are not roots, the difference in sign variation counts at the endpoints equals the number of distinct real roots in the open interval. The course uses the theorem; it does not prove it.

Trace

Predict two exact values

Evaluate x² - 2 at 1 and 2 by Horner's loop. What do their signs imply, and what extra claim requires the Sturm count?

⌘ / Ctrl + Enter

Output

Separate endpoint signs from the root-count claim.

Test

Tests cover coefficient normalization, arithmetic, long division, derivatives, GCD, square-free parts, Sturm sequences, and root counts. Testing a known polynomial checks the implementation; Sturm's theorem supplies the general mathematical bridge from variations to roots.

Boundary

sign_at maps rational values to Python's exact arbitrary-precision integer ratios for performance. No floating-point approximation is introduced. The mapping is a documented implementation boundary that avoids enormous unary intermediates during interval refinement.

Next: isolate and refine one algebraic real root →