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:
- Scan. A trial pair $(r,s)$ has $(r+1)(s+1)$ unknown coefficients and one linear equation per index $n$. The search requires at least five spare equations, so that a nonzero solution signals a real recurrence. Each system is solved modulo a prime $p \lt 2^{31}$ by Gaussian elimination on 64-bit integer numpy arrays, and every candidate is checked against all supplied terms. The degree $s$, which becomes the order of the differential operator, is the outer loop, so the first hit has minimal order.
- Reconstruct. With $(r,s)$ fixed, one exact rational nullspace at that single pair gives the coefficients as fractions. They are verified on trailing terms kept out of the fit (15 by default).
- Convert.
rec_to_thetaturns the recurrence into the operator $\sum_j x^{r-j} c_j(\theta - j)$ in the Euler derivative $\theta = x\,d/dx$.
The search has these limits:
- The output is a recurrence verified on every supplied term, not a proof that the sequence is holonomic.
- A pair found at one prime can occasionally be an artifact of that prime. Rerun with a second prime (the
pargument) before relying on it. - A return value of
Nonemeans that no recurrence with $r \le$rmaxand $s \le$smaxis consistent with the data modulo $p$. That rules out every pair $(r,s)$ in that range for which the sequence leaves at least five spare equations. Larger pairs are skipped and never tested. find_recurrence_fastscans by system size unless it is called withprefer='ode_order'. That scan is cheaper, but it can return an inflated order carrying spurious factors from apparent singularities (singular points of the operator at which every solution stays regular).- The modular kernel returns a single null vector, so it does not measure the dimension of the solution space.
nullspace_basis_modpin thefactor/module returns a basis (at most eight vectors unlesscapis raised) and the exact nullity. - The prime must be below $2^{31}$, the sequence at most a few thousand terms long, and the terms exact integers or fractions, not floating-point numbers.
Three optional modules factorize large operators modulo a prime once an operator is found. Most of them need python-flint.
ore/multiplies operators, tests whether one divides another from the right, and computes the least common left multiplethe lowest-order operator that each of the given operators divides from the right; its solutions are spanned by the solutions of all of them of several. It searches orders upward, so the first verified result is minimal. This arithmetic is classical (Ore).factor/extracts an order-4 right factor of an operator in $\theta$ form from its logarithmic series solutions at the origin. It verifies the factor by right division at several primes and reconstructs its rational coefficients by the Chinese remainder theorem.eigenring/separates right factors that right division alone cannot split, by the eigenring method of Singer and van Hoeij: it uses the maps of the operator's solution space to itself. It fits those maps with a series ansatz of guessed degree. It computes none of the valuation bounds (bounds on the order of each coefficient of the map at every singular point) of van Hoeij's Maple program, the reference implementation. A candidate factor is accepted only after it annihilates a separately generated series.
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.
| Function | What 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 |
P31 | The 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.
| Function | What it returns |
|---|---|
mul, apply_to_series, lclm, right_divide, op_to_recurrence, formal_solution in ore/ore_ops.py | Operator arithmetic over the rationals with sympy; needs no python-flint |
lclm_modp(summands_il, p) in ore/lclm_modp.py | The 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.py | The 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
- Threshold banana, CY₃ rung: reconstructed the exact order-six Picard–Fuchs operator over the rationals from the period series.
Requirements
- Runs on: Python 3 with numpy.
- Install: nothing is compiled. Run the commands from the root of the repository.
- Optional: sympy, for
rec_to_theta,ore/ore_ops.pyandore/known_factors.py. python-flint, forore/lclm_modp.py,ore/ore_rdiv_modp.py,factor/andeigenring/; without it the core still imports. - Self-test: the seven commands below.
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.
| Reference | What it supplies |
|---|---|
| B. Salvy and P. Zimmermann, gfun, ACM Trans. Math. Softw. 20 (1994) 163 | The fit of a recurrence or differential equation to series data |
| M. Kauers, Guess | The same fit |
| M. Kauers, M. Jaroschek, F. Johansson and M. Mezzarobba, ore_algebra | The 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.0917 | The trade-off between order and degree behind the order of the scan |
| M. van Hoeij, J. Symb. Comput. 24 (1997) 537 | Factorization 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.1705 | The 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 |