Keep and check exact algebra evidence¶

A coefficient array gives you an answer. A checked result also keeps the inputs and evidence needed to verify a stated relation. Use the _checked operations when a later calculation needs to validate the result independently.

"""Verify an exact division and a GCD from ascending coefficients."""
from apn_mojo import Rational
from poly import dense, exact
from std.testing import assert_equal, assert_true


def main() raises:
    var division = dense.divide_checked([1, 0, 1], [1, 2])
    assert_true(exact.check(division))
    var quotient = exact.quotient(division)
    assert_equal(quotient[0], Rational(-1, 4))
    assert_equal(quotient[1], Rational(1, 2))
    assert_equal(exact.remainder(division)[0], Rational(5, 4))
    var gcd = dense.gcd_checked([-1, 0, 1], [-1, 1])
    assert_true(exact.check(gcd))
    assert_equal(exact.value(gcd).to_list(), dense.asarray([-1, 1]).to_list())
    print("Exact division and GCD verified")

Exact division and GCD verified

The first calculation establishes

exact.check verifies the identity and the dense remainder's degree bound. The GCD check additionally establishes maximality through Bézout or coprimality evidence. exact.value returns the ordinary array, so subsequent calculations use the same functional API.

Choose the evidence you need¶

Both namespaces offer checked GCD, resultant, division, ordered list division, factorization, and squarefree decomposition. Dense interpolation and Hermite interpolation can retain their nodes and all value or derivative constraints. coprimality(a, b) returns optional evidence for coprime operands.

A check proves the relation documented for that operation. Factor checks prove recomposition; for AA and QQbar, they also verify irreducibility, monicity, and exact multiplicities. Other factorization domains keep the product-only check. resultant_checked proves an ideal-membership identity. Choose resultant_certified when you need verification of the complete Sylvester determinant over any supported exact field. The checked-results reference lists every claim so you can decide whether it meets your application's needs.

Share one Budget across preparation, production, output extraction, and checking when the entire workflow needs a work limit. Result copies share storage, while extracted polynomial arrays own independent data.

Exact queries and algorithm choices¶

Use sign_on_interval(p, low, high) to establish a strict sign throughout a closed interval. It returns 1 or -1 when the interval contains no root, and None when a root occurs anywhere, including either endpoint. A repeated root also prevents a strict sign, even if the polynomial never changes sign. Equal endpoints are allowed; reversed endpoints raise DOMAIN. Inputs and endpoints can be integers, rationals, or real algebraic values. Sparse input needs a one-variable power shape. This query returns an exact answer without retaining a certificate.

"""Exact sign queries, determinant proofs, and sparse algorithm choices."""
from std.testing import assert_equal, assert_true
from apn_mojo import Rational
from poly import dense, sparse, exact


def main() raises:
    # x^2 - 2 stays positive throughout [2, 3].
    var sign = dense.sign_on_interval([-2, 0, 1], 2, 3)
    assert_equal(sign.value(), 1)
    print("Positive throughout [2, 3]")

    # The determinant gives Res(x^2 + 1, x^2 - 2) = 9.
    var resultant = dense.resultant_certified([1, 0, 1], [-2, 0, 1])
    assert_true(exact.check(resultant))
    assert_equal(exact.value(resultant)[0], Rational(9))
    print("Resultant 9 verified from its determinant")

    var h = sparse.asarray([((1, 0), 1), ((0, 1), 1)])  # x + y
    var a = sparse.multiply(h, [((1, 0), 1), ((0, 0), 1)])
    var b = sparse.multiply(h, [((0, 1), 1), ((0, 0), 1)])
    var common = sparse.gcd_checked(a, b, method="modular")
    assert_true(exact.check(common))
    assert_equal(exact.value(common).to_list(), h.to_list())
    print("Sparse modular GCD: x + y")

    # Dividing x by x + y^2 illustrates how monomial order affects reduction.
    var x = sparse.asarray([((1, 0), 1)])
    var divisor = sparse.asarray([((1, 0), 1), ((0, 2), 1)])
    var lex = sparse.divide_checked(x, divisor)
    var graded = sparse.divide_checked(x, divisor, order="grlex")
    assert_true(exact.check(lex) and exact.check(graded))
    assert_equal(exact.remainder(lex).to_list(), sparse.asarray([((0, 2), Rational(-1))]).to_list())
    assert_equal(exact.remainder(graded).to_list(), sparse.asarray([((1, 0), Rational(1))]).to_list())
    print("Division remainders: -y^2 under lex, x under grlex")

Positive throughout [2, 3]
Resultant 9 verified from its determinant
Sparse modular GCD: x + y
Division remainders: -y^2 under lex, x under grlex

resultant_certified returns a coefficient array and a complete determinant transcript. Integer inputs promote to QQ; QQi, GF(p), AA, and QQbar retain their fields. Sparse inputs accept axis= to select the variable to eliminate, and the output retains the original power shape. As with other exact results, use exact.value, exact.check, and an immutable evidence() borrow. Keeping the elimination transcript can require substantial memory, so share a budget when working with larger degrees.

Choose method="modular" on sparse.gcd or sparse.gcd_checked to use sparse modular reconstruction over integers or rationals. The algorithm discovers and interpolates the occurring monomials, avoiding a dense box of parameter degrees. Both methods compute the same normalized GCD. The checked form also retains maximality evidence. method="auto" keeps the existing core dispatch; it does not automatically choose this dedicated sparse algorithm. Other method names raise DOMAIN; requesting modular reconstruction over QQi or a prime field raises UNSUPPORTED.

Choose the order for sparse division¶

divmod, divide_many, divide_checked, and divide_many_checked accept order="lex", "grlex", or "grevlex", plus an optional axes= permutation in descending priority. For example, axes=[1, 0] makes the second variable more significant. Every axis must appear exactly once; an empty list uses tuple order. The default remains lexicographic order with axis zero first.

In the example, lexicographic division reduces \(x\) by the leading \(x\) of \(x+y^2\), leaving \(-y^2\). Graded lexicographic order makes \(y^2\) the leading monomial, which cannot divide \(x\), so the quotient is zero and the remainder is \(x\). Reversing the axis priority under lexicographic order gives the same remainder in this example.

The chosen order affects the calculation, while output terms always return in canonical increasing lexicographic order. You can pass them straight into other array operations. Checked results retain the computational order in their evidence. Their checker establishes the recomposition identity; it does not independently certify reducedness or a unique remainder. Divisor list order also matters. Use a Gröbner basis when you need ideal normal forms.