API REFERENCE/omnibias-difference

omnibias.difference.recurrence

0.1.0a2AlphaPython >=3.10Apache-2.0

Finite-difference stencils, confluence limits, polynomial sequences, and scoped derivative-extraction certificates.

import omnibias.difference.recurrence

Module contract & mathematical conventions

Exact rational recurrence fitting on finite sequence samples.

A fitted relation is verified on supplied samples; continuation beyond that prefix requires an independent mathematical argument.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

CLASS

RecurrenceRelation

omnibias.difference.recurrence.RecurrenceRelationSource ↗

class RecurrenceRelation

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

A homogeneous P-recursive relation sum_j p_j(n) a_{n-j} = 0 (exact).

coefficients[j][d] is the n^d coefficient of the polynomial p_j that multiplies the lag-j term a_{n-j}. order is the recurrence order (max lag) and index_degree the max polynomial degree in n.

Parameters

Name	Type & default	Contract
orderdataclass field	intRequired	See the operation contract and implementation below.
index_degreedataclass field	intRequired	See the operation contract and implementation below.
coefficientsdataclass field	tuple[tuple[Fraction, ...], ...]Required	See the operation contract and implementation below.

Executed regression · recurrence relation detects violation

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_recurrence_relation_detects_violation() -> None:
    rel = RecurrenceRelation(
        order=2, index_degree=0, coefficients=((Fraction(1),), (Fraction(-1),), (Fraction(-1),))
    )
    assert rel.is_satisfied_by(_fibonacci(12))
    assert not rel.is_satisfied_by([0, 1, 2, 4, 8, 16])  # geometric, not Fibonacci

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_recurrence_relation_detects_violation" -q

Regression example · recurrence relation evaluation and pretty

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_recurrence_relation_evaluation_and_pretty() -> None:
    # (n + 1) a_n + (2 - 4n) a_{n-1} = 0  (Catalan)
    rel = RecurrenceRelation(
        order=1,
        index_degree=1,
        coefficients=((Fraction(1), Fraction(1)), (Fraction(2), Fraction(-4))),
    )
    cat = _catalan(10)
    assert rel.coefficient_poly(0, 3) == 4  # 1 + 3
    assert rel.coefficient_poly(1, 3) == -10  # 2 - 12
    assert rel.is_satisfied_by(cat)
    assert rel.max_abs_residual(cat) == 0
    assert rel.pretty() == "(1 + n) a[n] + (2 - 4 n) a[n-1] = 0"
    assert rel.pretty(symbol="C").startswith("(1 + n) C[n]")

python -m pytest packages/omnibias-difference/tests/test_recurrence.py -k test_recurrence_relation_evaluation_and_pretty -q

Fields & methods

orderfield

order: int

Declared int field on RecurrenceRelation. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

index_degreefield

index_degree: int

Declared int field on RecurrenceRelation. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

coefficientsfield

coefficients: tuple[tuple[Fraction, ...], ...]

Declared tuple[tuple[Fraction, ...], ...] field on RecurrenceRelation. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

coefficient_polymethod

coefficient_poly(self, lag: int, n: int) -> Fraction

Evaluate the polynomial p_lag(n) at integer n.

Parameters

Name	Type & default	Contract
lagpositional-or-keyword	intRequired	See the operation contract and implementation below.
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returns: Fraction

Executed regression · recurrence relation detects violation

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_recurrence_relation_detects_violation() -> None:
    rel = RecurrenceRelation(
        order=2, index_degree=0, coefficients=((Fraction(1),), (Fraction(-1),), (Fraction(-1),))
    )
    assert rel.is_satisfied_by(_fibonacci(12))
    assert not rel.is_satisfied_by([0, 1, 2, 4, 8, 16])  # geometric, not Fibonacci

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_recurrence_relation_detects_violation" -q

Method implementation

    def coefficient_poly(self, lag: int, n: int) -> Fraction:
        """Evaluate the polynomial ``p_lag(n)`` at integer ``n``."""
        acc = Fraction(0)
        for degree, coef in enumerate(self.coefficients[lag]):
            acc += coef * Fraction(n) ** degree
        return acc

View source ↗

evaluate_residualsmethod

evaluate_residuals(self, samples: Sequence[Number]) -> list[Fraction]

sum_j p_j(n) a_{n-j} for every valid n (all zero iff satisfied).

Parameters

Name	Type & default	Contract
samplespositional-or-keyword	Sequence[Number]Required	See the operation contract and implementation below.

Returns: list[Fraction]

Executed regression · recurrence relation detects violation

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_recurrence_relation_detects_violation() -> None:
    rel = RecurrenceRelation(
        order=2, index_degree=0, coefficients=((Fraction(1),), (Fraction(-1),), (Fraction(-1),))
    )
    assert rel.is_satisfied_by(_fibonacci(12))
    assert not rel.is_satisfied_by([0, 1, 2, 4, 8, 16])  # geometric, not Fibonacci

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_recurrence_relation_detects_violation" -q

Method implementation

    def evaluate_residuals(self, samples: Sequence[Number]) -> list[Fraction]:
        r"""``sum_j p_j(n) a_{n-j}`` for every valid ``n`` (all zero iff satisfied)."""
        vals = _as_fractions(samples)
        residuals: list[Fraction] = []
        for n in range(self.order, len(vals)):
            acc = Fraction(0)
            for lag in range(self.order + 1):
                acc += self.coefficient_poly(lag, n) * vals[n - lag]
            residuals.append(acc)
        return residuals

View source ↗

max_abs_residualmethod

max_abs_residual(self, samples: Sequence[Number]) -> Fraction

See the class contract above and the exact method implementation below.

Parameters

Name	Type & default	Contract
samplespositional-or-keyword	Sequence[Number]Required	See the operation contract and implementation below.

Returns: Fraction

Executed regression · discover fibonacci c finite

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_discover_fibonacci_c_finite() -> None:
    rel = discover_recurrence(_fibonacci(15))
    assert rel is not None
    assert (rel.order, rel.index_degree) == (2, 0)
    # a_n - a_{n-1} - a_{n-2} = 0
    assert rel.coefficients == ((Fraction(1),), (Fraction(-1),), (Fraction(-1),))
    assert rel.max_abs_residual(_fibonacci(20)) == 0

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_discover_fibonacci_c_finite" -q

Method implementation

    def max_abs_residual(self, samples: Sequence[Number]) -> Fraction:
        residuals = self.evaluate_residuals(samples)
        return max((abs(r) for r in residuals), default=Fraction(0))

View source ↗

is_satisfied_bymethod

is_satisfied_by(self, samples: Sequence[Number]) -> bool

See the class contract above and the exact method implementation below.

Parameters

Name	Type & default	Contract
samplespositional-or-keyword	Sequence[Number]Required	See the operation contract and implementation below.

Returns: bool

Executed regression · recurrence relation detects violation

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_recurrence_relation_detects_violation() -> None:
    rel = RecurrenceRelation(
        order=2, index_degree=0, coefficients=((Fraction(1),), (Fraction(-1),), (Fraction(-1),))
    )
    assert rel.is_satisfied_by(_fibonacci(12))
    assert not rel.is_satisfied_by([0, 1, 2, 4, 8, 16])  # geometric, not Fibonacci

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_recurrence_relation_detects_violation" -q

Method implementation

    def is_satisfied_by(self, samples: Sequence[Number]) -> bool:
        return all(r == 0 for r in self.evaluate_residuals(samples))

View source ↗

prettymethod

pretty(self, symbol: str='a') -> str

Human-readable relation, e.g. (n + 1) a[n] + (-4 n + 2) a[n-1] = 0.

Parameters

Name	Type & default	Contract
symbolpositional-or-keyword	strDefault: 'a'	See the operation contract and implementation below.

Returns: str

Executed regression · recurrence relation evaluation and pretty

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_recurrence_relation_evaluation_and_pretty() -> None:
    # (n + 1) a_n + (2 - 4n) a_{n-1} = 0  (Catalan)
    rel = RecurrenceRelation(
        order=1,
        index_degree=1,
        coefficients=((Fraction(1), Fraction(1)), (Fraction(2), Fraction(-4))),
    )
    cat = _catalan(10)
    assert rel.coefficient_poly(0, 3) == 4  # 1 + 3
    assert rel.coefficient_poly(1, 3) == -10  # 2 - 12
    assert rel.is_satisfied_by(cat)
    assert rel.max_abs_residual(cat) == 0
    assert rel.pretty() == "(1 + n) a[n] + (2 - 4 n) a[n-1] = 0"
    assert rel.pretty(symbol="C").startswith("(1 + n) C[n]")

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_recurrence_relation_evaluation_and_pretty" -q

Method implementation

    def pretty(self, symbol: str = "a") -> str:
        """Human-readable relation, e.g. ``(n + 1) a[n] + (-4 n + 2) a[n-1] = 0``."""
        pieces: list[str] = []
        for lag in range(self.order + 1):
            poly = _format_poly(self.coefficients[lag])
            if poly is None:
                continue
            term = f"{symbol}[n]" if lag == 0 else f"{symbol}[n-{lag}]"
            pieces.append(f"({poly}) {term}")
        body = " + ".join(pieces) if pieces else "0"
        return f"{body} = 0"

View source ↗

Read the implementation

class RecurrenceRelation:
    r"""A homogeneous P-recursive relation ``sum_j p_j(n) a_{n-j} = 0`` (exact).

    ``coefficients[j][d]`` is the ``n^d`` coefficient of the polynomial ``p_j`` that
    multiplies the lag-``j`` term ``a_{n-j}``. ``order`` is the recurrence order (max
    lag) and ``index_degree`` the max polynomial degree in ``n``.
    """

    order: int
    index_degree: int
    coefficients: tuple[tuple[Fraction, ...], ...]

    def coefficient_poly(self, lag: int, n: int) -> Fraction:
        """Evaluate the polynomial ``p_lag(n)`` at integer ``n``."""
        acc = Fraction(0)
        for degree, coef in enumerate(self.coefficients[lag]):
            acc += coef * Fraction(n) ** degree
        return acc

    def evaluate_residuals(self, samples: Sequence[Number]) -> list[Fraction]:
        r"""``sum_j p_j(n) a_{n-j}`` for every valid ``n`` (all zero iff satisfied)."""
        vals = _as_fractions(samples)
        residuals: list[Fraction] = []
        for n in range(self.order, len(vals)):
            acc = Fraction(0)
            for lag in range(self.order + 1):
                acc += self.coefficient_poly(lag, n) * vals[n - lag]
            residuals.append(acc)
        return residuals

    def max_abs_residual(self, samples: Sequence[Number]) -> Fraction:
        residuals = self.evaluate_residuals(samples)
        return max((abs(r) for r in residuals), default=Fraction(0))

    def is_satisfied_by(self, samples: Sequence[Number]) -> bool:
        return all(r == 0 for r in self.evaluate_residuals(samples))

    def pretty(self, symbol: str = "a") -> str:
        """Human-readable relation, e.g. ``(n + 1) a[n] + (-4 n + 2) a[n-1] = 0``."""
        pieces: list[str] = []
        for lag in range(self.order + 1):
            poly = _format_poly(self.coefficients[lag])
            if poly is None:
                continue
            term = f"{symbol}[n]" if lag == 0 else f"{symbol}[n-{lag}]"
            pieces.append(f"({poly}) {term}")
        body = " + ".join(pieces) if pieces else "0"
        return f"{body} = 0"

FUNCTION

discover_recurrence

omnibias.difference.recurrence.discover_recurrenceSource ↗

discover_recurrence(samples: Sequence[Number], *, max_order: int=4, max_index_degree: int=3, min_equation_margin: int=2) -> RecurrenceRelation | None

Recover the minimal exact P-recursive relation sum_j p_j(n) a_{n-j} = 0.

Searches (order, index_degree) in increasing order (order-major, so the lowest-order / lowest-degree relation wins) and, for each, solves for the exact homogeneous null space of the design whose columns are n^d a_{n-j} (j = 0 .. order, d = 0 .. index_degree). A **unique** (nullity-one) null vector whose leading (a_n) and trailing (a_{n-order}) coefficient polynomials are both non-trivial is returned as a RecurrenceRelation; otherwise the search continues.

Unlike a monic least-squares fit, the leading coefficient p_0(n) is free to be a non-constant polynomial, so genuinely P-recursive sequences whose natural relation is *not* monic -- e.g. Catalan (n+1)C_n - (4n-2)C_{n-1} = 0 -- are recovered exactly. Returns None when no unique relation fits the supplied prefix within the search bounds. Neither a fit nor None proves a global sequence law.

Parameters

Name	Type & default	Contract
samplespositional-or-keyword	Sequence[Number]Required	See the operation contract and implementation below.
max_orderkeyword-only	intDefault: 4	See the operation contract and implementation below.
max_index_degreekeyword-only	intDefault: 3	See the operation contract and implementation below.
min_equation_marginkeyword-only	intDefault: 2	See the operation contract and implementation below.

ReturnsRecurrenceRelation | None

Explicit validation & failure cases

• When max_order < 1, raises ValueError(f'max_order must be >= 1, got {max_order}').
• When max_index_degree < 0, raises ValueError(f'max_index_degree must be >= 0, got {max_index_degree}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · discover recurrence validation

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_discover_recurrence_validation() -> None:
    with pytest.raises(ValueError):
        discover_recurrence(_fibonacci(15), max_order=0)
    with pytest.raises(ValueError):
        discover_recurrence(_fibonacci(15), max_index_degree=-1)

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_discover_recurrence_validation" -q

Regression example · discover returns none for non holonomic

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_discover_returns_none_for_non_holonomic() -> None:
    # Bell numbers and the partition function are not finitely P-recursive.
    assert discover_recurrence(_bell(17), max_order=4, max_index_degree=3) is None
    assert discover_recurrence(_PARTITION, max_order=4, max_index_degree=3) is None

python -m pytest packages/omnibias-difference/tests/test_recurrence.py -k test_discover_returns_none_for_non_holonomic -q

Read the implementation

def discover_recurrence(
    samples: Sequence[Number],
    *,
    max_order: int = 4,
    max_index_degree: int = 3,
    min_equation_margin: int = 2,
) -> RecurrenceRelation | None:
    r"""Recover the minimal exact P-recursive relation ``sum_j p_j(n) a_{n-j} = 0``.

    Searches ``(order, index_degree)`` in increasing order (order-major, so the
    lowest-order / lowest-degree relation wins) and, for each, solves for the exact
    homogeneous null space of the design whose columns are ``n^d a_{n-j}``
    (``j = 0 .. order``, ``d = 0 .. index_degree``). A **unique** (nullity-one) null
    vector whose leading (``a_n``) and trailing (``a_{n-order}``) coefficient
    polynomials are both non-trivial is returned as a :class:`RecurrenceRelation`;
    otherwise the search continues.

    Unlike a monic least-squares fit, the leading coefficient ``p_0(n)``
    is free to be a non-constant polynomial, so genuinely P-recursive sequences whose
    natural relation is *not* monic -- e.g. Catalan ``(n+1)C_n - (4n-2)C_{n-1} = 0`` --
    are recovered exactly. Returns ``None`` when no unique relation fits the supplied prefix within
    the search bounds. Neither a fit nor ``None`` proves a global sequence law.
    """
    if max_order < 1:
        raise ValueError(f"max_order must be >= 1, got {max_order}")
    if max_index_degree < 0:
        raise ValueError(f"max_index_degree must be >= 0, got {max_index_degree}")
    for order in range(1, max_order + 1):
        for index_degree in range(max_index_degree + 1):
            relation = try_recurrence(
                samples,
                order,
                index_degree,
                min_equation_margin=min_equation_margin,
            )
            if relation is not None:
                return relation
    return None

Related APIsomnibias.difference.recurrence.try_recurrence↗

FUNCTION

try_recurrence

omnibias.difference.recurrence.try_recurrenceSource ↗

try_recurrence(samples: Sequence[Number], order: int, index_degree: int, *, min_equation_margin: int=2) -> RecurrenceRelation | None

Exact nullity-one P-recurrence at one (order, index_degree) cell.

Parameters

Name	Type & default	Contract
samplespositional-or-keyword	Sequence[Number]Required	See the operation contract and implementation below.
orderpositional-or-keyword	intRequired	See the operation contract and implementation below.
index_degreepositional-or-keyword	intRequired	See the operation contract and implementation below.
min_equation_marginkeyword-only	intDefault: 2	See the operation contract and implementation below.

ReturnsRecurrenceRelation | None

Explicit validation & failure cases

• When order < 1, raises ValueError(f'order must be >= 1, got {order}').
• When index_degree < 0, raises ValueError(f'index_degree must be >= 0, got {index_degree}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · discover returns none for non holonomic

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_discover_returns_none_for_non_holonomic() -> None:
    # Bell numbers and the partition function are not finitely P-recursive.
    assert discover_recurrence(_bell(17), max_order=4, max_index_degree=3) is None
    assert discover_recurrence(_PARTITION, max_order=4, max_index_degree=3) is None

python -m pytest "packages/omnibias-difference/tests/test_recurrence.py::test_discover_returns_none_for_non_holonomic" -q

Read the implementation

def try_recurrence(
    samples: Sequence[Number],
    order: int,
    index_degree: int,
    *,
    min_equation_margin: int = 2,
) -> RecurrenceRelation | None:
    """Exact nullity-one P-recurrence at one ``(order, index_degree)`` cell."""

    if order < 1:
        raise ValueError(f"order must be >= 1, got {order}")
    if index_degree < 0:
        raise ValueError(f"index_degree must be >= 0, got {index_degree}")
    vals = _as_fractions(samples)
    width = index_degree + 1
    unknowns = (order + 1) * width
    row_indices = list(range(order, len(vals)))
    if len(row_indices) < unknowns + min_equation_margin:
        return None
    design: list[list[Fraction]] = []
    for n in row_indices:
        row: list[Fraction] = []
        for lag in range(order + 1):
            a_shift = vals[n - lag]
            for d in range(width):
                row.append(Fraction(n) ** d * a_shift)
        design.append(row)
    null = integer_null_space(_clear_denominators(design))
    if len(null) != 1:
        return None
    coeffs = _vector_to_coefficients(null[0], order, index_degree)
    if _poly_is_zero(coeffs[0]) or _poly_is_zero(coeffs[order]):
        return None
    relation = RecurrenceRelation(order=order, index_degree=index_degree, coefficients=coeffs)
    if relation.is_satisfied_by(vals):
        return relation
    return None

Related APIsomnibias.core.proof.integer_null_space↗omnibias.difference.recurrence.RecurrenceRelation↗

← Package overviewRunnable learning examples →