Python API

Polynomial API

Explicit polynomial representation types backed by FLINT.

UniPoly

class

class UniPoly

#source

Dense univariate polynomial with exact integer or rational coefficients, backed by FLINT's fmpq_poly_t.

All arithmetic operators are supported: +, -, *, ** (integer exponent), // (exact quotient), % (remainder):

Python

p = UniPoly.from_symbolic(x**2 + pool.integer(-1), x)
q = UniPoly.from_symbolic(x + pool.integer(-1), x)
print(p * q)   # x^3 - x^2 - x + 1
print(p // q)  # x + 1
print(p % q)   # 0

Properties

leading_coeff

#source

Leading (highest-degree) coefficient, as an exact Python int.

0 for the zero polynomial, matching degree == -1 there. Lossless for coefficients of any size, as coefficients() also now is — so both are safe on the output of factor_z, resultants and pseudo-division, where the coefficients grow past 64 bits.

A property, not a method: it is a single FLINT coefficient read.

degree

#source

Degree of the polynomial (-1 for the zero polynomial).

is_zero

#source

True if this is the zero polynomial.

Methods

from_symbolic(expr, var)

staticmethod

#source

Convert a symbolic expression to a univariate polynomial in var.

Example:

Python

p = UniPoly.from_symbolic(x**3 + pool.integer(-2) * x + pool.integer(1), x)

Raises

ConversionError: If expr contains non-polynomial terms.

from_coefficients(coefficients, var)

staticmethod

#source

Construct a UniPoly from coefficients (constant term first).

Each coefficient may be a Python int or an integer Expr from the same pool as var.

`` `python p = ExprPool() x = p.symbol("x")

poly = UniPoly.from_coefficients([-1, 0, 1], x)

also accepted:

poly = UniPoly.from_coefficients([p.integer(-1), p.integer(0), p.integer(1)], x) ` ``

Raises TypeError if any coefficient is not an int / integer expression. Raises OverflowError if any coefficient overflows i64.

coefficients() → list

#source

Coefficients in ascending degree order, as exact Python ints.

Lossless for coefficients of any size. This used to go through coefficients_i64(), which does not merely saturate — it returned 0 for anything past i64, so 2**100 * x**2 + 1 came back as [1, 0, 0]: a quadratic reading as the constant 1, with no exception and no flag. That is exactly the silent-error class this project gates against, and it is reachable from ordinary use, since factor_z, resultants and pseudo-division all grow coefficients past 64 bits.

gcd(other)

#source

Compute the GCD via FLINT's subresultant PRS.

factor_z()

#source

Factor over ℤ (FLINT; x**n ± 1 and u**n * x**n ± v**n through cyclotomic polynomials).

factor_list() is in a canonical order that depends only on the factors: ascending degree, then coefficients compared as signed integers from the leading term down, then multiplicity. x**12 - 1 gives x - 1, x + 1, x**2 - x + 1, x**2 + 1, x**2 + x + 1, x**4 - x**2 + 1.

MultiPoly

class

class MultiPoly

#source

Sparse multivariate polynomial over ℤ. Terms are stored as a map from exponent vectors to coefficients.

+, -, * are supported between MultiPoly objects with the same variable list.

Properties

is_zero

#source

True if this is the zero polynomial.

total_degree

#source

Highest total degree over all terms (0 for the zero polynomial).

Methods

from_symbolic(expr, vars=None)

staticmethod

#source

Build a multivariate polynomial from a symbolic expression.

If vars is omitted, free symbols of expr are used (sorted by internal id for a deterministic order).

integer_content() → int

#source

Return the GCD of all coefficients.

primitive_part()

#source

gcd(other)

#source

GCD over ℤ (multivariate FLINT).

factor_z()

#source

Factor over ℤ (multivariate FLINT).

factor_list() is in a canonical order that depends only on the factors: ascending total degree, then coefficients over the monomials in descending lexicographic order (variables in ring order), then multiplicity.

Sparse interpolation

function

sparse_interp_univariate(eval, term_bound, prime)

#source

Recover a sparse univariate polynomial over F_p from black-box evaluations using the Ben-Or/Tiwari (Prony-style) algorithm.

Parameters

evalcallable: Black-box oracle x ↦ f(x) mod p. Called with a single int argument and must return an int.
term_boundint: Upper bound T on the number of nonzero terms. Exactly 2·T oracle calls are made.
primeint: Field characteristic p. Must satisfy p > 2·T and p > max_degree(f).

Returns

list[tuple[int, int]]: List of (coefficient, exponent) pairs.

Raises

SparseInterpError: On invalid prime, prime too small, or inconsistent oracle.
Example:: p = 997 def f(x): return (x100 + 3*x17 + 5) % p terms = sparse_interp_univariate(f, 3, p)

terms ≈ [(1, 100), (3, 17), (5, 0)]

function

sparse_interp(
    eval,
    vars,
    term_bound,
    degree_bound,
    prime,
    seed=0
)

#source

Recover a sparse multivariate polynomial over F_p from black-box evaluations using Zippel's variable-by-variable algorithm.

Parameters

evalcallable: Black-box oracle (x₁, …, xₙ) ↦ f(x₁, …, xₙ) mod p. Called with a Python list[int] (one int per variable) and must return an int.
varslist[Expr]: Symbolic variable expressions in the same order as the coordinates passed to eval.
term_boundint: Upper bound T on the number of nonzero terms.
degree_boundint: Upper bound D on the degree of each individual variable. For the dense fallback, set D ≤ T.
primeint: Field characteristic p. Must satisfy p > 2·T and p > D.
seedint, optional: PRNG seed for random evaluation points (default 0). Change the seed to recover from occasional Vandermonde singularities.

Returns

MultiPolyFp: Recovered polynomial with coefficients in [0, p). On 20-variable inputs this is typically ≥ 5× faster in oracle calls than dense interpolation.

Raises

SparseInterpError: On invalid prime, prime too small, or inconsistent oracle.
Example:: pool = ExprPool() x, y = pool.symbol("x"), pool.symbol("y") p = 1009 def f(pt): x_, y_ = pt return (x_ * y_ + 3) % p result = sparse_interp(f, [x, y], term_bound=4, degree_bound=3, prime=p)

function

gcd_sparse(f, g, term_bound, degree_bound, seed=0)

#source

Compute the primitive GCD of two multivariate polynomials over ℤ using sparse interpolation and the Chinese Remainder Theorem (Zippel method).

Both polynomials must have the same variable list. The result is the primitive part of gcd(f, g) with positive leading coefficient.

Parameters

f, gMultiPoly: Input polynomials with the same variable list.
term_boundint: Upper bound on the number of nonzero terms in the GCD.
degree_boundint: Upper bound on the per-variable degree of the GCD in x₂,…,xₙ. The degree in x₁ is probed automatically.
seedint, optional: PRNG seed. Change on failure (default 0).

Returns

MultiPoly: The primitive GCD with positive leading coefficient.

Raises

SparseGcdError: If the interpolation fails or the variable lists are incompatible.

Examples

Python

pool = ExprPool()
x, y = pool.symbol("x"), pool.symbol("y")
f = MultiPoly.from_symbolic((x - pool.integer(1)) * (x + y), [x, y])
g = MultiPoly.from_symbolic((x + pool.integer(1)) * (x + y), [x, y])
h = gcd_sparse(f, g, term_bound=4, degree_bound=3)
# h represents x + y

RationalFunction

class

class RationalFunction(numer, denom)

#source

Construct a RationalFunction from two UniPoly numerator / denominator.

`python p = ExprPool() x = p.symbol("x") numer = UniPoly.from_coefficients([p.integer(-1), p.integer(0), p.integer(1)], x) # x²-1 denom = UniPoly.from_coefficients([p.integer(-1), p.integer(1)], x) # x-1 rf = RationalFunction(numer, denom) # → (x+1) after GCD reduction `

Raises ValueError if denom is the zero polynomial.

Properties

is_zero

#source

True if the numerator is the zero polynomial.

Methods

from_symbolic(numer, denom, vars)

staticmethod

#source

Construct a rational function and normalize by GCD.

Example:

Python

# (x^2 - 1) / (x - 1) → normalized to x + 1
rf = RationalFunction.from_symbolic(
    x**2 + pool.integer(-1),
    x + pool.integer(-1),
    [x]
)
print(rf)  # x + 1

numer()

#source

denom()

#source

Polynomial utilities

function

horner(expr, var)

#source

Convert a polynomial expression to Horner form.

expr must be a univariate polynomial in var. Returns a new Expr in Horner form a₀ + x*(a₁ + x*(…)).

Roots, resultants and factorisation

function

real_roots(poly, var)

#source

Isolate all real roots of a polynomial expression.

Returns a list of RootInterval objects sorted by lower endpoint. Each interval contains exactly one real root of the squarefree part of poly. Repeated roots appear once each.

Parameters

polyExpr: A univariate polynomial expression with integer coefficients.
varExpr: The polynomial variable.

Returns

list[RootInterval]

Raises

RealRootError: If poly is not a polynomial with integer coefficients, or is the zero polynomial.
Example:: pool = ExprPool() x = pool.symbol("x") roots = real_roots(x**2 - pool.integer(4), x)

function

refine_root(poly, interval, var)

#source

Refine a RootInterval to at least prec bits of precision.

Uses bisection with floating-point Horner evaluation. For exact rational roots (lo == hi), returns a zero-radius ball.

Parameters

polyExpr: The same polynomial passed to real_roots().
intervalRootInterval: One element of the list returned by real_roots().
varExpr: The polynomial variable.
precint: Desired precision in bits (minimum 53, clamped to max(53, prec)).

Returns

ArbBall: Rigorous floating-point ball containing the root.
Example:: pool = ExprPool() x = pool.symbol("x") ivs = real_roots(x2 - pool.integer(2), x) ball = refine_root(x2 - pool.integer(2), ivs[1], x, 53)

class

class RootInterval

#source

A closed rational interval [lo, hi] isolating exactly one real root.

For an exact rational root r, lo == hi == r.

Properties

lo

#source

Lower bound as a float (may be slightly inexact).

hi

#source

Upper bound as a float (may be slightly inexact).

Methods

lo_exact()

#source

Exact lower bound as (numerator_str, denominator_str).

hi_exact()

#source

Exact upper bound as (numerator_str, denominator_str).

function

resultant(p, q, var)

#source

Compute the resultant of two polynomial expressions with respect to a variable.

Both p and q must be polynomial expressions with integer coefficients. The returned expression is:

An integer constant in the univariate case (only var appears).
A polynomial in the remaining variables in the multivariate case (var has been eliminated).

The returned DerivedResult carries a "Resultant" derivation step tagged with the Lean 4 theorem Polynomial.resultant_eq_zero_iff_common_root.

Raises ResultantError if either input is not a polynomial with integer coefficients.

Example:

Python

pool = ExprPool()
x = pool.symbol("x")
y = pool.symbol("y")
p = x**2 + y**2 - pool.integer(1)
q = y - x
r = resultant(p, q, y)
# r.value == 2*x^2 - 1

function

subresultant_prs(p, q, var)

#source

Compute the subresultant polynomial remainder sequence of two univariate polynomials with integer coefficients.

Returns a Python list of Expr objects ordered [p, q, S₂, S₃, …, Sₖ].

Both polynomials must be univariate in var with integer coefficients. Multivariate inputs raise ResultantError.

Example:

Python

pool = ExprPool()
x = pool.symbol("x")
p = x**2 - pool.integer(1)
q = x - pool.integer(1)
prs = subresultant_prs(p, q, x)
# prs == [p, q, last_element]

function

routh_hurwitz(poly, var)

#source

Symbolic / parametric Routh–Hurwitz stability analysis.

Given a characteristic polynomial poly in the analysis variable var whose coefficients may be symbolic expressions in free parameters, returns a dict with:

"degree": the degree of poly in var;
"first_column": the Routh-array first-column entries (top to bottom) as Expr objects in the parameters;
"condition": the stability condition as a single predicate Expr — a conjunction of entry > 0 over the non-trivial first-column entries.

For example s**2 + a*s + b yields the condition a > 0 ∧ b > 0 and s**3 + a*s**2 + b*s + c yields a > 0 ∧ a*b - c > 0 ∧ c > 0.

function

factor_univariate_mod_p(coeffs, modulus)

#source

Factor a dense univariate polynomial over $\mathbb{F}_p$ from ascending integer coefficients (reduced mod p).

p must be prime (E-POLY-009 otherwise) and the polynomial non-zero mod p (E-POLY-008). The factors are monic; .unit is the leading coefficient that restores the input. factor_list() is sorted by ascending degree, then by the residues from the leading term down.

class

class UniPolyFactorization

#source

No docstring.

Properties

unit

#source

verification

#source

Exact in-kernel reconstruction evidence for this factorization.

Methods

factor_list()

#source

class

class UniPolyFactorModP

#source

No docstring.

Properties

modulus

#source

unit

#source

The leading coefficient u of the input mod p: the input is u * prod(f**e for f, e in factor_list()) with every f monic.

Methods

factor_list()

#source

class

class MultiPolyFactorization

#source

No docstring.

Properties

unit

#source

verification

#source

Exact in-kernel reconstruction evidence for this factorization.

Methods

factor_list()

#source

Modular arithmetic

function

binomial_mod(a, b, p, k)

#source

binomial(a, b) mod p**k, exactly, for p prime.

Uses the Andrew Granville / Davis–Webb factorisation of n! into its p-free part, which at k = 1 is Lucas' theorem exactly. The cost is O(p·k³ + log_p(a)·p·k) and does not grow with a beyond the logarithm, so a far larger than p is the ordinary case rather than the hard one.

b < 0 and b > a are not errors: the binomial coefficient is 0.

Python

>>> import alkahest as ak
>>> ak.binomial_mod(2 * 11 - 1, 10, 11, 3)   # Wolstenholme
1
>>> ak.binomial_mod(1_000_000, 3, 7, 4)
2261
>>> ak.binomial_mod(5, 9, 7, 4)
0

Raises

HolonomicError: E-HOLO-006 when p is not prime, k < 1, or p**k >= 2**62; E-HOLO-008 when the work budget would be exceeded.

Polynomial API

#UniPoly

#also accepted:

#MultiPoly

#Sparse interpolation

#terms ≈ [(1, 100), (3, 17), (5, 0)]

#RationalFunction

#Polynomial utilities

#Roots, resultants and factorisation

#Modular arithmetic

UniPoly

also accepted:

MultiPoly

Sparse interpolation

terms ≈ [(1, 100), (3, 17), (5, 0)]

RationalFunction

Polynomial utilities

Roots, resultants and factorisation

Modular arithmetic