Exact real roots¶

These operations count and isolate distinct real roots using exact rational arithmetic. Repeated roots count once. Sturm sequences retain the input and its derivative without normalization or squarefree preprocessing; every division, including the terminal zero remainder, has a quotient witness.

The root-count checker verifies polynomial identities and sign variations. It does not run polynomial division or reconstruct the producer's sequence. Nonzero constants use a one-element sequence and have no roots. Zero raises DOMAIN for sequence construction, counting, and isolation.

isolate_real_roots isolates the roots of the squarefree part by Descartes' rule of signs (see Descartes certificates), on an interval bounded by a power of two. Output intervals have nonroot dyadic endpoints, a sign change of the squarefree part, and width below 2**-40; refine accepts any positive rational target width. It validates the interval by Descartes' rule on the squarefree part, subdividing where the bound overcounts, so any interval with exactly one distinct root and nonroot endpoints is accepted, and narrows it by quadratic interval refinement to at most half the target width.

To recover all rational roots, including non-dyadic values such as 1/3, isolation narrows every interval below 1/(2*A*A), where A is the leading coefficient of the primitive squarefree part. The rational-root theorem bounds root denominators by A; Legendre's continued-fraction criterion then finds any such root among the midpoint's convergents. Each candidate is checked by exact evaluation. Dyadic rational roots met at split points are exact already. This is rational reconstruction after isolation, without integer factorization. Rational midpoint roots remain strictly inside the open interval returned by refine.

count_roots requires increasing nonroot endpoints. sign_on_interval accepts singleton intervals and returns no sign if any root lies in the closed interval. Budget exhaustion raises LIMIT and never returns a partial list.

Descartes certificates¶

A DescartesCertificate proves the real roots of an integer polynomial g without a Sturm sequence. Its leaves partition an interval (low, high) whose ends are not roots. Each leaf records Descartes' bound for the roots inside it: the sign variations of \((x+1)^n\,g(\ell + (h-\ell)/(x+1))\), which is at least the number of roots in the open leaf and has the same parity, so zero and one are exact counts. The shared leaf endpoints where g vanishes are listed in exact_roots. Every leaf with a bound of one, and every leaf marked resolved with a larger bound v, owns the next v brackets: disjoint intervals inside it, each an open interval where g changes sign or a point where g is zero. Each holds an odd number of roots, so v of them under a bound of v hold exactly one root each. A leaf with a bound of two or more and no brackets is unresolved and leaves its roots uncounted.

check_descartes verifies all of this from g and the certificate alone: the partition, every leaf's bound recomputed by a Taylor shift, the exact roots, and two signs per bracket. It does not need g to be squarefree. descartes_intervals lists the certified roots in increasing order, an exact root r as the point (r, r). A DescartesRootResult pairs a certificate with the squarefree part g of a polynomial f, the cofactor gcd(f, f'), the bound exponent of the certificate's interval and the outcome flags.

descartes_count counts the distinct real roots of f strictly between two ordered nonroot endpoints from a complete isolation: the exact roots between them and the brackets inside them, a bracket that contains an endpoint being decided by the sign of g there against the bracket's end. Its DescartesCountCertificate holds the isolation, the endpoints and the count, and check_descartes_count verifies the isolation and recounts. It is the evidence behind the array API's count_roots; count_roots here keeps its Sturm certificate.

Example¶

For \(p(x)=(x^2-2)(3x-1)\), count_roots certifies three distinct real roots. isolate_real_roots returns the rational root \(1/3\) in exact_roots and two isolating intervals for \(\pm\sqrt{2}\) in intervals:

"""Count real roots and distinguish rational roots from isolating intervals."""
from std.testing import assert_equal, assert_true
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, count_roots, check_root_count, isolate_real_roots


def main() raises:
    var work = Budget()
    var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
    var polynomial = DensePoly[QQ].from_sparse(ring.parse("(x^2 - 2)*(3*x - 1)", work), work, variable=Int64(0))
    var count = count_roots(polynomial, QQ(Rational(-2)), QQ(Rational(2)), work)
    assert_equal(count.count, 3)
    assert_true(check_root_count(polynomial, count, work))
    var roots = isolate_real_roots(polynomial, work)
    assert_equal(len(roots.exact_roots), 1)
    assert_equal(roots.exact_roots[0].value, Rational(1, 3))
    assert_equal(len(roots.intervals), 2)
    print("Distinct real roots:", count.count)
    print("Rational root:", roots.exact_roots[0].value)
    print("Irrational-root intervals:", len(roots.intervals))

Distinct real roots: 3
Rational root: 1/3
Irrational-root intervals: 2

Types and functions¶

SturmSequence¶

@fieldwise_init
struct SturmSequence(Copyable, Movable, Writable)

An unnormalized signed remainder sequence with exact quotient witnesses.

The final nonzero polynomial is retained, including for repeated roots.

Defined in src/polynomials/certificates.mojo.

RootCountCertificate¶

@fieldwise_init
struct RootCountCertificate(Copyable, Movable, Writable)

A Sturm sequence proving a distinct-root count on an open interval (T-C1).

Defined in src/polynomials/certificates.mojo.

check_root_count¶

def check_root_count(f: DensePoly[QQ], certificate: RootCountCertificate, mut budget: Budget) raises PolyError -> Bool

Check all Sturm identities and endpoint variations without polynomial division.

Arguments.

• f: The polynomial whose distinct roots are counted.
• certificate: The sequence, quotient witnesses, endpoints, and count.
• budget: The shared work allowance.

Returns. Whether the evidence establishes the count on the open interval.

Raises.

• PolyError: DOMAIN for incompatible representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

RootInterval¶

@fieldwise_init
struct RootInterval(Copyable, Movable, Writable)

An open rational interval containing exactly one distinct real root.

Defined in src/polynomials/roots.mojo.

RootIsolation¶

@fieldwise_init
struct RootIsolation(Copyable, Movable, Writable)

The distinct real roots as exact rationals and disjoint open intervals.

Defined in src/polynomials/roots.mojo.

sturm_sequence¶

def sturm_sequence(f: DensePoly[QQ], mut budget: Budget) raises PolyError -> SturmSequence

Construct the unnormalized Sturm sequence and every quotient witness.

Arguments.

• f: A nonzero rational polynomial; constants give a one-element sequence.
• budget: The shared work allowance.

Returns. The sequence starting with f and f-prime, including its last nonzero entry.

Raises.

• PolyError: DOMAIN for zero or malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/roots.mojo.

sign_changes¶

def sign_changes(sequence: SturmSequence, a: QQ, mut budget: Budget) raises PolyError -> Int

Count changes of sign at an exact point, omitting zero evaluations.

Arguments.

• sequence: The polynomial sequence to evaluate.
• a: The exact evaluation point.
• budget: The shared work allowance.

Returns. The number of adjacent opposite nonzero signs.

Raises.

• PolyError: LIMIT or CAPACITY on work limits.

Defined in src/polynomials/roots.mojo.

count_roots¶

def count_roots(f: DensePoly[QQ], a: QQ, b: QQ, mut budget: Budget) raises PolyError -> RootCountCertificate

Count distinct real roots in an open interval with nonroot endpoints.

Arguments.

• f: A nonzero polynomial, with repeated roots allowed.
• a: The lower endpoint.
• b: The upper endpoint.
• budget: The shared work allowance.

Returns. The count and a complete Sturm certificate.

Raises.

• PolyError: DOMAIN for zero, endpoint roots, or a not below b; LIMIT or CAPACITY on work limits.

Defined in src/polynomials/roots.mojo.

isolate_real_roots¶

def isolate_real_roots(f: DensePoly[QQ], mut budget: Budget) raises PolyError -> RootIsolation

Isolate every distinct real root by Descartes' rule of signs.

Arguments.

• f: A nonzero rational polynomial; constants have no roots.
• budget: The shared work allowance.

Returns. Every rational root exactly and sorted disjoint intervals of width below 2**-40 for the others.

Raises.

• PolyError: DOMAIN for zero or malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/roots.mojo.

refine¶

def refine(f: DensePoly[QQ], interval: RootInterval, width: QQ, mut budget: Budget) raises PolyError -> RootInterval

Narrow a validated isolating interval to strictly less than the requested width.

The interval is validated by Descartes' rule of signs on the squarefree part and narrowed by quadratic interval refinement.

Arguments.

• f: The polynomial defining the root.
• interval: An open interval with exactly one root and nonroot endpoints.
• width: The positive target width.
• budget: The shared work allowance.

Returns. A narrower open interval containing the same root, including rational roots.

Raises.

• PolyError: DOMAIN for nonpositive width or an invalid isolating interval, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/roots.mojo.

sign_on_interval¶

def sign_on_interval(f: DensePoly[QQ], low: QQ, high: QQ, mut budget: Budget) raises PolyError -> Optional[Int]

Determine the strict sign on a closed interval when no root occurs there.

Arguments.

• f: The rational polynomial.
• low: The lower endpoint.
• high: The upper endpoint, possibly equal to low.
• budget: The shared work allowance.

Returns. Positive or negative one for a root-free interval, otherwise None.

Raises.

• PolyError: DOMAIN for reversed endpoints or malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/roots.mojo.

DescartesLeaf¶

@fieldwise_init
struct DescartesLeaf(Copyable, Movable)

An open interval of a Descartes certificate with its root bound.

Defined in src/polynomials/descartes.mojo.

DescartesCertificate¶

@fieldwise_init
struct DescartesCertificate(Copyable, Movable)

Leaves partitioning (low, high), the roots of g at their shared ends, and a bracket for every other root.

Defined in src/polynomials/descartes.mojo.

DescartesRootResult¶

@fieldwise_init
struct DescartesRootResult(Copyable, Movable)

The distinct real roots of an exact polynomial with a Descartes certificate and outcome flags.

Defined in src/polynomials/descartes.mojo.

check_descartes¶

def check_descartes(g: DensePoly[ZZ], certificate: DescartesCertificate, mut budget: Budget) raises PolyError -> Bool

Verify a Descartes certificate for an integer polynomial without searching.

Checks that the leaves partition the certificate's interval at nonroots and at the listed exact roots, recomputes every leaf's Descartes bound, and checks the brackets of each resolved leaf: disjoint, inside it, and each with a sign change or a root. Unresolved leaves are accepted; they leave a result incomplete, not wrong.

Arguments.

• g: The polynomial the certificate is for; squarefree in practice, though the checks do not need it.
• certificate: The proposed certificate.
• budget: The shared work allowance.

Returns. Whether every claim of the certificate holds for g.

Raises.

• PolyError: LIMIT or CAPACITY on work limits.

Defined in src/polynomials/descartes.mojo.

descartes_intervals¶

def descartes_intervals(certificate: DescartesCertificate, mut budget: Budget) raises PolyError -> List[RootInterval]

List the certified roots of a Descartes certificate in increasing order.

Arguments.

• certificate: A certificate, checked or produced by this module.
• budget: The shared work allowance.

Returns. One interval per root: the point (r, r) for an exact root and the bracket otherwise; roots of unresolved leaves are omitted.

Raises.

• PolyError: LIMIT or CAPACITY on work limits.

Defined in src/polynomials/descartes.mojo.

DescartesCountCertificate¶

@fieldwise_init
struct DescartesCountCertificate(Copyable, Movable, Writable)

A complete Descartes isolation proving a distinct-root count on an open interval.

The isolation brackets every real root once; the count is the exact roots strictly between the endpoints and the brackets inside, a bracket holding an endpoint being decided by the squarefree part's sign there.

Defined in src/polynomials/descartes.mojo.

DescartesCountCertificate.write_to¶

def write_to[W: Writer](self, mut writer: W)

Write the endpoints, the count and the isolation.

Parameters.

• W: The writer type.

Arguments.

• writer: The destination.

descartes_count¶

def descartes_count(f: DensePoly[QQ], a: QQ, b: QQ, mut budget: Budget) raises PolyError -> DescartesCountCertificate

Count the distinct real roots of f strictly between nonroot endpoints by Descartes' rule.

Arguments.

• f: The nonzero polynomial.
• a: The lower endpoint, not a root of f.
• b: The upper endpoint, above a and not a root of f.
• budget: The shared work allowance.

Returns. The count with a complete Descartes isolation that check_descartes_count verifies.

Raises.

• PolyError: DOMAIN for a zero polynomial or unordered or root endpoints, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/descartes.mojo.

check_descartes_count¶

def check_descartes_count(f: DensePoly[QQ], certificate: DescartesCountCertificate, mut budget: Budget) raises PolyError -> Bool

Check a Descartes root count without searching.

Verifies the isolation with check_algebraic_descartes, requires ordered endpoints where f does not vanish, and recounts.

Arguments.

• f: The polynomial whose distinct roots are counted.
• certificate: The isolation, endpoints and count.
• budget: The shared work allowance.

Returns. Whether the evidence establishes the count on the open interval.

Raises.

• PolyError: DOMAIN for malformed polynomial data, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/descartes.mojo.