Metadata-Version: 2.5
Name: algrecognize
Version: 0.1.0
Summary: Recognize low-complexity algebraic numbers from high-precision numerical approximations using FLINT
Project-URL: Homepage, https://pypi.org/project/algrecognize/
Project-URL: Documentation, https://pypi.org/project/algrecognize/
Author: Bhuvanesh Bhatt (bhuvaneshbhatt@gmail.com)
License-Expression: GPL-3.0-only
License-File: LICENSE
Keywords: Arb,FLINT,LLL,algebraic-number,computational-number-theory,exact-arithmetic,integer-relation
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.11
Requires-Dist: python-flint<1.0,>=0.9.0
Provides-Extra: release
Requires-Dist: build>=1.2; extra == 'release'
Requires-Dist: twine>=6; extra == 'release'
Provides-Extra: test
Requires-Dist: pytest>=8; extra == 'test'
Description-Content-Type: text/markdown

# 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.

```python
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`](https://python-flint.readthedocs.io/) and is intended to
inform a future native FLINT implementation. Plausible future C entry points
might be:

```c
int fmpz_poly_algrecognize(...);
int qqbar_algrecognize(...);
```

## Installation

```bash
python -m pip install algrecognize
```

For development:

```bash
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`.

```python
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:

```python
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

```text
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:

```mermaid
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:

```python
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:

```python
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:

```python
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:

```mermaid
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:
```python
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:

```python
from algrecognize import DEFAULT_MAX_DEGREE
```

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

```python
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:

```text
"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

```python
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

```python
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

```python
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

```python
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.
$$

```python
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

```python
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:

```python
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:

```text
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:

```python
import algrecognize
print(algrecognize.__version__)
```

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

## Testing

Run the complete suite:

```bash
pytest
```

Run the higher-level regression suite:

```bash
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:

```bash
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`](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:

```c
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:

```c
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
