algrecognize

algrecognize recognizes low-complexity algebraic numbers from high-precision real or complex numerical approximations using FLINT.

Status: algrecognize is alpha software. It is suitable for experimentation, testing, and computational mathematics workflows, but recognition heuristics and/or some public parameters may change before version 1.0.

from flint import arb, ctx
from algrecognize import algrecognize

ctx.prec = 256

x = arb(2).sqrt() + arb(3).sqrt()
result = algrecognize(x, max_degree=8)

print(result.polynomial)
# x^4 - 10*x^2 + 1

The project is a Python implementation built on python-flint and is intended to inform a future native FLINT implementation. Plausible future C entry points might be:

int fmpz_poly_algrecognize(...);
int qqbar_algrecognize(...);

Installation

python -m pip install algrecognize

For development:

python -m pip install -e ".[test]"
pytest

algrecognize currently requires Python 3.11+ and python-flint>=0.9.0,<1.0.

Good input versus misleading precision

For serious recognition, compute the value directly with arb or acb.

from flint import arb, ctx

ctx.prec = 300

# Good: the value itself is computed at high precision.
x = arb(2).sqrt()
result = algrecognize(x, max_degree=2)

Avoid computing a value first as a Python float and then merely increasing FLINT's working precision:

from flint import arb, ctx

x = 2.0**0.5      # only binary64 information
ctx.prec = 500
x = arb(x)        # still only contains the original binary64 information

The package explicitly caps Python float and complex inputs at 53 source bits so that high working precision is not mistaken for high input accuracy.

What the package does

Suppose a numerical computation produces

3.146264369941972342329135065715...

and mathematical context suggests that the value may be algebraic. In this case the number is

$$ \alpha=\sqrt2+\sqrt3, $$

whose minimal polynomial is

$$ x^4-10x^2+1. $$

algrecognize searches for a low-degree, low-height integer polynomial approximately satisfied by the input, factors the candidate exactly with FLINT, and attempts to identify a uniquely compatible certified root.

Conceptually:

flowchart TD
    A[Numerical approximation] --> B[Integer-relation search]
    B --> C[Primitive integer polynomial]
    C --> D[Exact factorization]
    D --> E[Certified root isolation]
    E --> F[AlgRecognizeResult]

Scope

Task	Supported?
Recover a low-complexity algebraic relation from a high-precision approximation	Yes
Exact integers and rationals	Yes, deterministic fast path
Real and complex algebraic numbers	Yes
Certified compatibility with a unique isolated polynomial root	Yes, when the input ball permits it
General integer relations among arbitrary vectors of constants	Not yet
Symbolic minimal polynomial from an already exact symbolic expression	Not the primary purpose
General symbolic constant recognition involving pi, logs, zeta values, etc.	No
Transcendental testing	No

Failure to recognize a number is not evidence of being transcendental.

Mathematical background

An algebraic number (\alpha) of degree at most (d) satisfies

$$ a_0+a_1\alpha+\cdots+a_d\alpha^d=0 $$

for integers (a_i), not all zero. Algebraic recognition can therefore be viewed as finding an integer relation among

$$ 1,\alpha,\alpha^2,\ldots,\alpha^d. $$

For an approximate input (\widetilde{\alpha}), exact equality is unavailable, so the package searches for a polynomial

$$ p(x)=\sum_{i=0}^{d} a_i x^i $$

whose residual (p(\widetilde{\alpha})) is exceptionally small relative to the input accuracy and polynomial complexity.

Degree and height

The coefficient height is

$$ H(p)=\max_i |a_i|. $$

Both degree and coefficient height represent complexity. A small residual is more compelling when it comes from a low-degree polynomial with small coefficients.

The search proceeds from degree 1 upward. The first sufficiently convincing irreducible relation wins, which strongly favors a simpler explanation over a higher-degree multiple.

Relation score

Candidate relations are scored using

$$ S(p,x)= -\log_2\left( \frac{|p(x)|}{H(p)\max(1,|x|)^{\deg p}} \right). $$

The implementation evaluates the score with Arb/Acb enclosures and uses a conservative lower bound for acceptance.

This is a recognition heuristic, not a theorem that arbitrary finite numerical input is algebraic.

LLL lattice construction

For a real approximation (x), choose a binary residual scale

$$ C=2^s. $$

For degree (d), construct rows resembling

$$ \left( w_i e_i,; \mathrm{round}(C x^i) \right), \qquad i=0,\ldots,d, $$

where (e_i) is a coefficient coordinate and

$$ w_i=(k+1)^i $$

when degree_cost=k.

An integer combination with coefficients (a_i) has a final coordinate approximately equal to

$$ C\sum_i a_i x^i=Cp(x). $$

LLL therefore searches for vectors that balance small coefficients against a small polynomial residual.

For complex (z), two residual columns are used:

$$ \mathrm{Re}p(z) \qquad\text{and}\qquad \mathrm{Im}p(z). $$

Magnitude-aware scaling

A fixed residual scale is poorly conditioned when (|x|) is large because

$$ 1,x,x^2,\ldots,x^d $$

can span many orders of magnitude.

After optional reciprocal normalization, algrecognize estimates a coarse binary magnitude exponent (e) and chooses, before guard bits,

$$s_{\mathrm{target}} = \max\left(A - d\max(0,e), \left\lfloor \frac{A}{2} \right\rfloor\right).$$

where $A$ is the estimated trustworthy input accuracy in bits.

The final automatic scale is

$$s = \max\left(16,; s_{\mathrm{target}} - 8 - \left\lceil \log_2(d+1) \right\rceil\right).$$

Large-magnitude inputs therefore use a smaller residual scaling exponent while temporary arithmetic uses additional guard precision to accommodate growth of (x^d).

The selected values are exposed as:

result.scale_bits
result.magnitude_exponent_bits

Reciprocal normalization

When the input is provably nonzero and satisfies (|x|<1), the search can use

$$ y=1/x. $$

This avoids rapidly shrinking powers of (x). If the search finds

$$ q(y)=0, $$

the relation is transformed back as

$$ p(x)=x^d q(1/x). $$

Disable this behavior with:

algrecognize(x, 8, reciprocal_normalization=False)

How FLINT is used

The expensive arithmetic is delegated to FLINT through Python-FLINT.

arb and acb

Used for:

• arbitrary-precision real and complex ball input;
• trustworthy-accuracy estimates;
• power formation;
• polynomial residual evaluation;
• rigorous upper and lower bounds;
• root-compatibility checks.

fmpz_mat

The integer relation lattice is represented as a dense multiprecision integer matrix. FLINT performs the LLL reduction:

reduced = lattice.lll()

fmpz_poly

Used for:

• exact integer polynomial representation;
• primitive normalization;
• coefficient content;
• factorization;
• certified complex-root isolation.

The Python-FLINT API provides exact rational numerator/denominator access, so exact integer and rational inputs are handled directly without an LLL search.

Recognition versus certification

Finite numerical data cannot by itself prove that an unknown exact number is algebraic. Every nonzero numerical neighborhood contains infinitely many nonalgebraic numbers.

algrecognize therefore distinguishes:

1. high-confidence recognition: a low-complexity relation passes the numerical score threshold;
2. certified root compatibility: the supplied Acb ball overlaps exactly one certified root enclosure of the selected irreducible polynomial;
3. exact rational handling: exact integer/rational input yields a deterministic linear relation and confidence == "exact".

result.certified is intentionally a statement about compatibility of enclosures, not a claim that an arbitrary decimal has been proven algebraic.

Algorithm

The recognition pipeline is:

flowchart TD
    A[Input value] --> B{Exact integer or rational?}
    B -- Yes --> C[Return exact linear relation qx - p]
    B -- No --> D[Estimate trustworthy input accuracy]
    D --> E[Optional reciprocal normalization]
    E --> F[Search degrees 1 through max_degree]

    F --> G[Estimate magnitude and working precision]
    G --> H[Choose magnitude-aware lattice scale]
    H --> I[Build real or complex integer-relation lattice]
    I --> J[Run FLINT LLL reduction]
    J --> K[Inspect several short lattice vectors]
    K --> L[Undo coefficient weights]
    L --> M[Primitive-normalize and deduplicate]
    M --> N[Apply coefficient-height filter]
    N --> O[Evaluate Arb or Acb residual and relation score]
    O --> P{Convincing candidate?}

    P -- No --> Q{More degrees available?}
    Q -- Yes --> F
    Q -- No --> R[Raise NoRelationFound]

    P -- Yes --> S[Factor strongest candidates exactly]
    S --> T[Score irreducible factors]
    T --> U[Compute certified complex root enclosures]
    U --> V[Identify compatible or nearest root]
    V --> W[Return AlgRecognizeResult]

The major stages have different roles:

1. LLL generates candidates. A short vector is not automatically assumed to be the correct minimal polynomial.
2. Numerical filtering ranks candidates. Primitive normalization, coefficient-height bounds, and Arb/Acb residual scoring eliminate weak relations before expensive exact work.
3. FLINT exact arithmetic validates structure. Promising polynomials are factored exactly and their roots are isolated with certified enclosures.
4. Recognition and certification remain distinct. A strong numerical relation can be returned even when the supplied input ball does not uniquely overlap a single root enclosure.

Exact rational inputs bypass the numerical pipeline entirely.

Public API

The public API looks like:

algrecognize(
    value,
    max_degree,
    *,
    max_height=None,
    min_relation_bits=None,
    mode="auto",
    lattice_scale_bits=None,
    degree_cost=0,
    reciprocal_normalization=True,
    candidates_per_degree=8,
    factor_candidates_per_degree=4,
    minimum_input_accuracy_bits=24,
    allow_large_degree=False,
)

value

Accepted public input types include:

• int
• fractions.Fraction
• flint.fmpz
• flint.fmpq
• float
• complex
• flint.arb
• flint.acb

Exact integers and rationals bypass LLL.

max_degree

Largest algebraic degree searched.

The default safety limit is available as:

from algrecognize import DEFAULT_MAX_DEGREE

Currently it is 128. Larger searches raise SearchLimitError unless explicitly enabled:

result = algrecognize(
    x,
    max_degree=160,
    allow_large_degree=True,
)

High-degree LLL searches can be expensive in both time and memory.

max_height

Optional hard bound on

$$ H(p)=\max_i |a_i|. $$

When omitted, an accuracy- and degree-dependent guard is used.

min_relation_bits

Minimum normalized relation score. The automatic threshold is currently about two thirds of estimated input accuracy, with a 24-bit floor.

mode

One of:

"auto"
"real"
"complex"

lattice_scale_bits

Advanced override for automatic magnitude-aware lattice scaling. Normally leave this unset.

degree_cost

Nonnegative integer controlling

$$ w_i=(\text{degree_cost}+1)^i. $$

Default: 0.

reciprocal_normalization

Use (1/x) when the input is provably nonzero and inside the unit circle.

Default: True.

Result object

algrecognize() returns AlgRecognizeResult.

Important fields:

• polynomial: selected primitive irreducible fmpz_poly;
• relation_polynomial: relation before selecting an irreducible factor;
• matched_root: certified acb root enclosure;
• residual: enclosure for (p(x));
• relation_score_bits: conservative relation score;
• acceptance_threshold_bits: threshold used for recognition;
• input_accuracy_bits: estimated trustworthy bits, or None for exact input;
• input_is_exact: whether an exact rational fast path was used;
• degree_searched: successful degree bound;
• polynomial_height: coefficient height;
• scale_bits: residual lattice scaling exponent;
• magnitude_exponent_bits: magnitude estimate used for scaling;
• lattice_vector: originating LLL vector, empty for exact rational input;
• certified: whether exactly one certified root enclosure overlaps the input;
• confidence: "exact", "certified", or "high_confidence";
• reciprocal_normalization_used: whether the reciprocal path was used.

Exceptions

from algrecognize import (
    AlgRecognizeError,
    InsufficientAccuracyError,
    NoRelationFound,
    SearchLimitError,
)

InsufficientAccuracyError is a subclass of NoRelationFound.

SearchLimitError indicates that the requested degree exceeds the default safety limit without explicit opt-in.

NoRelationFound otherwise means that no relation passed the configured search and confidence criteria. That can happen because:

• precision is insufficient;
• max_degree is too low;
• the defining polynomial has larger coefficients than allowed;
• min_relation_bits is too strict;
• the root geometry is ill-conditioned;
• the input is nonalgebraic;
• the algebraic relation is simply too complicated for the chosen budget.

Examples

Exact rational

from fractions import Fraction
from algrecognize import algrecognize

result = algrecognize(Fraction(3, 7), max_degree=1)

print(result.polynomial)
# 7*x - 3
print(result.confidence)
# exact

Quadratic irrational

from flint import arb, ctx
from algrecognize import algrecognize

ctx.prec = 200
x = arb(2).sqrt()

result = algrecognize(x, max_degree=4)

print(result.polynomial)
# x^2 - 2

Quartic

ctx.prec = 256
x = arb(2).sqrt() + arb(3).sqrt()

result = algrecognize(x, max_degree=8)

print(result.polynomial)
# x^4 - 10*x^2 + 1

Complex algebraic number

For

$$ z=\sqrt2+i\sqrt3, $$

one obtains

$$ z^4+2z^2+25=0. $$

from flint import acb, arb, ctx
from algrecognize import algrecognize

ctx.prec = 256
z = acb(arb(2).sqrt(), arb(3).sqrt())

result = algrecognize(z, max_degree=6)

print(result.polynomial)
# x^4 + 2*x^2 + 25

Small-magnitude input

ctx.prec = 220
x = arb(2).sqrt() / 10

result = algrecognize(
    x,
    max_degree=4,
    max_height=1000,
)

print(result.polynomial)
# 50*x^2 - 1
print(result.reciprocal_normalization_used)
# True

Choosing parameters

For most high-precision inputs, begin with only a plausible degree bound:

result = algrecognize(x, max_degree=8)

If recognition fails:

1. increase the input precision first;
2. increase max_degree if a higher algebraic degree is plausible;
3. increase max_height if large coefficients are expected;
4. inspect or adjust min_relation_bits;
5. experiment with degree_cost if high-order terms are favored too readily;
6. override lattice_scale_bits only for diagnostics or algorithm research.

Degree, coefficient height, and required precision trade against one another. Higher degree and larger coefficients generally require more trustworthy input information.

Applications

Possible uses include:

• experimental mathematics;
• recovering exact structure from high-precision numerical computations;
• conjecturing minimal polynomials;
• symbolic-numeric workflows;
• validating numerical implementations against exact algebraic structure;
• number-theoretic experimentation;
• regression testing for computations expected to produce algebraic values.

A failed recognition attempt should never be interpreted as evidence of being transcendental.

Performance and safety

At search degree (d), the real relation lattice has approximately

$$ (d+1)\times(d+2) $$

entries, and the complex lattice approximately

$$ (d+1)\times(d+3). $$

LLL cost grows rapidly with degree and integer bit size. The implementation therefore:

• searches low degrees first;
• inspects only several short reduced-basis rows;
• deduplicates primitive candidates;
• applies height and residual filters before exact factorization;
• factors only the strongest few candidates;
• imposes a default max_degree safety limit.

The incremental search currently repeats LLL at successive degrees. Reusing work between degree steps is an important future optimization.

Reproducibility

Recognition heuristics can evolve between alpha releases. For scientific or regression use, record at least:

algrecognize version
python-flint version
Python version
input construction and precision
max_degree
max_height
min_relation_bits
degree_cost
lattice_scale_bits (if overridden)
returned polynomial
relation_score_bits
certified

The package version is available as:

import algrecognize
print(algrecognize.__version__)

The version is read from installed package metadata rather than duplicated in the source.

Testing

Run the complete suite:

pytest

Run the higher-level regression suite:

pytest tests/regression_cases

The tests include:

• exact integer/rational fast paths;
• real and complex algebraic recovery;
• nested radicals and roots of unity;
• degree bounds below the true degree;
• degree-cost behavior;
• reciprocal normalization;
• magnitude-aware scaling;
• machine-float accuracy capping;
• high-threshold rejection tests;
• deterministic randomized known-algebraic inputs;
• large-degree safety behavior.

Continuous integration runs the suite on Python 3.11–3.14 across Linux, macOS, and Windows, and separately builds both source and wheel distributions and validates them with twine check.

Release process

Before a production PyPI release:

python -m pip install -e ".[test,release]"
pytest
python -m build
python -m twine check dist/*

Install the built wheel into a clean environment and rerun the tests before uploading.

A TestPyPI upload is recommended before publishing to the production index.

Repository, issue-tracker, and source-documentation URLs should be added to pyproject.toml once the public repository location is fixed; placeholder URLs are intentionally not published.

API stability

This is a 0.1.0 alpha release.

Before version 1.0, the following may change as benchmarking improves:

• default score thresholds;
• magnitude-scaling heuristics;
• automatic coefficient-height policy;
• result diagnostics;
• large-degree limits;
• advanced parameter names.

The core conceptual contract is intended to remain stable: recover a low-complexity algebraic relation from trustworthy numerical data and use FLINT exact arithmetic to validate and identify the corresponding root.

License

algrecognize is licensed under the GNU General Public License, version 3 only (GPL-3.0-only). See LICENSE.

Roadmap toward native FLINT

This Python pakcage is intended as an initial prototype to help with a possible native FLINT implementation.

A natural low-level API would return a primitive polynomial relation:

int fmpz_poly_algrecognize(
    fmpz_poly_t res,
    const acb_t x,
    slong max_degree,
    ...
);

A higher-level API could return the exact algebraic root:

int qqbar_algrecognize(
    qqbar_t res,
    const acb_t x,
    slong max_degree,
    ...
);

Questions to settle with benchmarks before proposing an upstream C API include:

• rigorous acceptance criteria;
• optimal magnitude-aware scaling;
• coefficient-height models;
• reuse across incremental degree searches;
• whether separate real and complex entry points are desirable;
• whether a second integer-relation method is worthwhile;
• which tuning parameters should remain internal;
• how failure reasons should map to C return codes.

References

FLINT

FLINT documentation:
https://flintlib.org/doc/

Python-FLINT documentation:
https://python-flint.readthedocs.io/

LLL

A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász (1982), “Factoring polynomials with rational coefficients,” Mathematische Annalen 261, 515–534.
https://doi.org/10.1007/BF01457454

Integer relations

H. R. P. Ferguson, D. H. Bailey, and S. Arno (1999), “Analysis of PSLQ, an integer relation finding algorithm,” Mathematics of Computation 68(225), 351–369.
https://doi.org/10.1090/S0025-5718-99-00995-3

Arb

Fredrik Johansson (2017), “Arb: efficient arbitrary-precision midpoint-radius interval arithmetic,” IEEE Transactions on Computers 66(8), 1281–1292.
https://doi.org/10.1109/TC.2017.2690633