Annihilator

Annihilator takes the opening terms of a sequence, supplied exactly as integers or fractions, and finds the lowest-order linear recurrence with polynomial coefficients that those terms satisfy. From the recurrence it writes down the linear differential operator that annihilates the sequence's generating functionthe power series whose coefficients are the terms of the sequence, which for the series expansion of a period integral is its Picard–Fuchs operatorthe linear differential operator of lowest order, with polynomial coefficients, whose solutions include the period; its order and singular points encode the geometry behind the integral. The method is the one Salvy and Zimmermann use in their computer-algebra package gfun and Kauers uses in his package Guess: fit the recurrence to the series data by linear algebra.

What it does

Many sequences met in practice are holonomicsatisfying a linear recurrence whose coefficients are polynomials in the index; equivalently, the generating function satisfies a linear differential equation with polynomial coefficients: Taylor coefficients of a Feynman integral on its maximal cutthe integral with every internal line put on shell, moments of a random walk on a lattice, counting sequences such as the Catalan numbers. Such a sequence obeys

$$\sum_{j=0}^{r} c_j(n)\, a_{n+j} = 0, \qquad \deg c_j \le s,$$

with the order $r$, the degree bound $s$ and the polynomials $c_j$ unknown in advance. Annihilator finds them from the numbers alone: it needs no integrand and no formula for $a_n$, only enough exact terms.

Annihilator does the fit of gfun and Guess in Python, for long integer sequences reduced modulo a prime. Its scan goes by ascending differential order, as the search in gfun also does. Chen, Jaroschek, Kauers and Singer explain the trade-off between order and degree behind that choice.

The search has three steps:

The search has these limits:

Three optional modules factorize large operators modulo a prime once an operator is found. Most of them need python-flint.

When the integrand is available, the pf_rank probe in Dipstick computes the operator's order from the integrand polynomial for comparison.

The package notes give one large case: a recurrence of order 24 with coefficients of degree 19, found from 550 terms modulo a prime, for the exact four-species Jukes–Cantor marginal likelihood.

Examples

Run the self-tests. With numpy installed (see Requirements), run from the root of the BootLoops repository; the package directory is tools/annihilator/:

python3 tools/annihilator/nullspace_fast/test_nullspace_fast.py
python3 tools/annihilator/annihilator.py --selftest

The first script recovers two known recurrences from 100 terms each: Fibonacci (order 2, constant coefficients) and Catalan, $(n+2)C_{n+1} = (4n+2)C_n$. It prints one [PASS] line per check, fifteen in all, then ALL PASS. The second command builds the exact return-probability moments of the simple-cubic lattice walk in dimensions 2 through 5, whose operators have differential orders 2 through 5. It prints

[series_pf self-test] d-dim simple-cubic LGF, mode='auto' (ode_order-first)
  d=2: (r,s)=(1,2)  held-out=15  [0.03s]  PASS
  d=3: (r,s)=(2,3)  held-out=15  [0.07s]  PASS
  d=4: (r,s)=(2,4)  held-out=15  [0.13s]  PASS
  d=5: (r,s)=(3,5)  held-out=15  [0.26s]  PASS
ALL PASS

Each line gives the order $r$ and coefficient degree $s$ found, the number of trailing terms on which the exact coefficients were verified, and the run time. A line ends in PASS when $(r,s)$ is the known minimal pair for that dimension, whose $s$ equals the dimension, and the exact coefficients were recovered. The script exits with status 0 after ALL PASS and status 1 after SELFTEST FAILED.

A recurrence modulo a prime. The Catalan check from the test file is a template for any integer sequence already reduced modulo $p$:

from nullspace_fast import nullspace_mod_fast, find_recurrence_fast
p = 2147483629  # < 2^31, prime
cat = [1]
for n in range(99):
    cat.append(cat[-1] * (4 * n + 2) * pow(n + 2, p - 2, p) % p)
rec = find_recurrence_fast(cat, p, rmax=3, dmax=3)
r, d, w = rec

Run it from inside nullspace_fast/, as the test does, or import the same two functions from annihilator instead. The call returns r = 1, d = 1 and a flat list w of $(r+1)(d+1) = 4$ residues, ordered so that $c_0(n) = w_0 + w_1 n$ and $c_1(n) = w_2 + w_3 n$. Dividing through by $w_3$ modulo $p$ gives $(-2, -4, 2, 1)$, that is $-(4n+2)C_n + (n+2)C_{n+1} = 0$.

An exact operator from a moment sequence. The calls the built-in self-test makes, here for the three-dimensional lattice, followed by a printout of the recurrence:

from annihilator import moments_sc, pf_from_series, pretty_rec, rec_to_theta
d = 3
a = moments_sc(d, 100)
res = pf_from_series(a, rmax=14, smax=8, nverify=15, mode='auto')
r, s, coeffs, nver = res
print(pretty_rec(r, s, coeffs))

moments_sc returns 101 exact fractions beginning $1, \tfrac16, \tfrac{5}{72}, \dots$. pf_from_series finds $(r,s) = (2,3)$ modulo $2^{31}-1$, reconstructs the rational coefficients and verifies them on 15 unused terms (nver = 15). pretty_rec prints

(4*n^3+12*n^2+11*n+3)*a[n+0] + (-40*n^3+-180*n^2+-272*n+-138)*a[n+1] + (36*n^3+216*n^2+432*n+288)*a[n+2] = 0

which is $(n+1)(2n+1)(2n+3)\,a_n - (40n^3+180n^2+272n+138)\,a_{n+1} + 36(n+2)^3\,a_{n+2} = 0$. rec_to_theta(r, s, coeffs) then gives the third-order operator in $\theta$. With mode='modp' the same call returns (2, 3, None, 0), the pair without the coefficients. Repeating it with p=2147483629 and getting the same pair is the second-prime confirmation.

Routines

The core is loaded with import annihilator, with tools/ as the working directory or on PYTHONPATH. It needs numpy, and sympy only for rec_to_theta.

FunctionWhat it returns
pf_from_series(a, rmax, smax, nverify, mode, p)(r, s, coeffs, n_verified) for the minimal recurrence of an exact sequence, or None
find_recurrence_fast(Zs, p, rmax, dmax, overdet, prefer)(r, d, v) for an integer sequence modulo p, or None
nullspace_mod_fast(A, p)One null vector of an integer matrix modulo p, or None if the matrix has full column rank
rec_to_theta(r, s, coeffs)The operator in $\theta$, as a dict from (power of x, power of θ) to a fraction
pretty_rec(r, s, coeffs)The recurrence as a readable string
moments_sc(d, N)Exact return-probability moments of the d-dimensional simple-cubic lattice walk for n = 0..N
P31The default prime, $2^{31}-1$

In the result of pf_from_series, coeffs maps (j, k) to the fraction multiplying $n^k$ in $c_j(n)$. The mode is 'modp' (the pair only), 'exact' or 'auto' (modular scan, then exact coefficients). The files series_pf.py and nullspace_fast/nullspace_fast.py re-export the same functions.

The operator modules are imported explicitly, for example from annihilator.ore import lclm_modp.

FunctionWhat it returns
mul, apply_to_series, lclm, right_divide, op_to_recurrence, formal_solution in ore/ore_ops.pyOperator arithmetic over the rationals with sympy; needs no python-flint
lclm_modp(summands_il, p) in ore/lclm_modp.pyThe least common left multiple modulo p, as a list of coefficient polynomials, each stage verified by right division
ore_rightdiv_modp(L_il, R_il, p) in ore/ore_rdiv_modp.py(Q, S, e, content) with $\mathrm{lc}(R)^e\,L = Q\,R + S$; S identically zero means R divides L from the right
mum_tower_modp, fit_order4_modp, rows_ratrec, ore_rightdiv_Q in factor/rf_lib.pyThe parts of the order-4 right-factor extraction: series solutions, fit, rational reconstruction, exact right division

Operators in ore/ are lists [c0, ..., cn] for $c_0 + c_1 D_x + \dots + c_n D_x^n$. Operators in factor/ are in $\theta$ form, one ascending $z$-coefficient list per power of $\theta$. ore_rightdiv_modp is also exported by import annihilator, where it is None when python-flint is not installed.

ore/known_factors.py holds exact operators transcribed from the Ising-susceptibility paper of Assis, Boukraa, Hassani, van Hoeij, Maillard and McCoy; the lclm_modp.py self-test uses them. Its L5_4 is transcribed as printed, with a caveat in its docstring.

Besides the self-tests, the one command-line program is eigenring/s4_eigenring_pilot.py <p> <cache_L17_npz> <exact_inputs.json> <outdir>. It splits entangled right factors of a large operator modulo p and writes a JSON record to <outdir>. Its two input files are a cached operator and exact reference operators that the user prepares. Its --selftest needs no input files. GUIDE.md in the package describes each module.

Used on this site

Requirements

python3 tools/annihilator/annihilator.py --selftest
python3 tools/annihilator/nullspace_fast/test_nullspace_fast.py
python3 tools/annihilator/eigenring/s4_eigenring_pilot.py --selftest
python3 tools/annihilator/ore/ore_ops.py
python3 tools/annihilator/ore/ore_rdiv_modp.py
python3 tools/annihilator/ore/known_factors.py
python3 tools/annihilator/ore/lclm_modp.py

The first two end with ALL PASS. The eigenring script, ore_rdiv_modp.py and lclm_modp.py end with SELFTEST PASS, ore_ops.py with smoke tests passed and known_factors.py with OVERALL: PASS. Each finishes in seconds except lclm_modp.py, which takes about half a minute.

Source and references

The code is in tools/annihilator/ in the BootLoops repository. GUIDE.md there carries the credits.

ReferenceWhat it supplies
B. Salvy and P. Zimmermann, gfun, ACM Trans. Math. Softw. 20 (1994) 163The fit of a recurrence or differential equation to series data
M. Kauers, GuessThe same fit
M. Kauers, M. Jaroschek, F. Johansson and M. Mezzarobba, ore_algebraThe same fit, and operator arithmetic
S. Chen, M. Jaroschek, M. Kauers and M. F. Singer, "Desingularization explains order-degree curves for Ore operators", ISSAC 2013, 157, arXiv:1301.0917The trade-off between order and degree behind the order of the scan
M. van Hoeij, J. Symb. Comput. 24 (1997) 537Factorization of differential operators; the eigenring method of eigenring/ is due to Singer and van Hoeij
M. Assis, S. Boukraa, S. Hassani, M. van Hoeij, J.-M. Maillard and B. M. McCoy, J. Phys. A 45 (2012) 075205, arXiv:1110.1705The operators transcribed in ore/known_factors.py
numpy, sympy and python-flint (F. Johansson, O. Benjamin and contributors)The arrays, the symbolic steps and the modular polynomial arithmetic

← back to the tools index