Algebraic real roots through rational intervals¶

The positive root of x² - 2 is not rational. Identify it with a polynomial and an interval containing exactly one root, then shrink the interval without leaving exact rational arithmetic.

What we already know

Polynomials can be evaluated exactly at rational points, and a Sturm sequence counts distinct real roots in an open rational interval.

By the end, you can

state the invariants of a rational isolating interval;
connect those invariants to constructor validation;
follow one bisection branch from endpoint and midpoint signs;
explain what this object does not implement as a number type.

Read beside this chapter

Algebraic-root source and root tests.

Definition

An algebraic real number is a real root of a nonzero polynomial with integer coefficients. This project studies one root through:

a polynomial;
rational endpoints lower < upper;
neither endpoint being a root;
opposite endpoint signs;
exactly one distinct real root in the open interval.

For x² - 2, the interval [1,2] satisfies these conditions for the positive root. The root itself is not replaced by either endpoint.

Representation

@dataclass(frozen=True, slots=True)
class RationalInterval:
    lower: Rational
    upper: Rational

    def __post_init__(self) -> None:
        if not isinstance(self.lower, Rational) or not isinstance(
            self.upper, Rational
        ):
            raise TypeError("interval endpoints must be Rational values")
        lower_fraction = _as_fraction(self.lower)
        upper_fraction = _as_fraction(self.upper)
        if lower_fraction > upper_fraction:
            raise ValueError("lower must be less than or equal to upper")

The interval's width, midpoint, and is_point are properties derived from the endpoints. They cannot become inconsistent stored fields.

A property exposes derived state

interval.width looks like an attribute but computes from immutable endpoints. The representation has one source of truth.

Implementation

AlgebraicRoot.__post_init__ checks the full isolating contract:

def __post_init__(self) -> None:
    if not isinstance(self.polynomial, Polynomial):
        raise TypeError("polynomial must be a Polynomial")
    if not isinstance(self.interval, RationalInterval):
        raise TypeError("interval must be a RationalInterval")
    if self.polynomial.degree <= 0:
        raise ValueError("a root-defining polynomial must have positive degree")
    if self.interval.is_point:
        raise ValueError("the initial interval must have positive width")

    lower_sign = self.polynomial.sign_at(self.interval.lower)
    upper_sign = self.polynomial.sign_at(self.interval.upper)
    if lower_sign == 0 or upper_sign == 0:
        raise ValueError("initial interval endpoints cannot be roots")
    if lower_sign == upper_sign:
        raise ValueError("the polynomial must change sign across the endpoints")

    number_of_roots = count_real_roots(
        self.polynomial,
        self.interval.lower,
        self.interval.upper,
    )
    if number_of_roots != 1:
        raise ValueError(
            "the initial interval must contain exactly one distinct real root "
            f"(found {number_of_roots})"
        )

Once construction succeeds, bisection preserves the root:

def _bisect(
    polynomial_value: Polynomial,
    interval: RationalInterval,
) -> tuple[RationalInterval, LogMessage]:
    midpoint = interval.midpoint
    midpoint_sign = polynomial_value.sign_at(midpoint)
    if midpoint_sign == 0:
        result = RationalInterval(midpoint, midpoint)
    elif polynomial_value.sign_at(interval.lower) != midpoint_sign:
        result = RationalInterval(interval.lower, midpoint)
    else:
        result = RationalInterval(midpoint, interval.upper)
    return result, lambda: f"{polynomial_value!r}: {interval} -> {result}"

If the midpoint is exact, the interval becomes one point. Otherwise the half whose endpoint signs differ keeps the root guaranteed by continuity. Because the original interval contains exactly one root, the retained half still identifies that same root.

Trace

Predict the first interval

The midpoint of [1,2] is 3/2. Evaluate x²-2 there and decide which half remains.

⌘ / Ctrl + Enter

Output

Check nesting, sign preservation, and halving widths.

Test

Tests assert that widths halve, endpoints retain opposite signs, later intervals are nested, exact midpoints become point intervals, and invalid or multi-root intervals are rejected. They check the code's preservation of the documented invariant for representative cases.

Boundary

AlgebraicRoot is an educational root-isolation object, not a complete real or algebraic number type. It does not define arithmetic between roots or general mathematical equality. The course stops after exposing why rational endpoints can approach a non-rational value without ever becoming that value.

Return to the course overview →