Ratfit

Ratfit recovers an exact rational function of one variable (a ratio of two polynomials with rational coefficients) from exact values at rational sample points, and confirms it on samples kept out of the fit. It uses Thiele's continued-fraction interpolationa classical way to interpolate a rational function through sample points one at a time, without solving a linear system for the coefficients, with the stopping test and the modular arithmetic that Peraro (arXiv:1608.01902) and Klappert, Klein and Lange (FireFly, arXiv:1904.00009, arXiv:2004.01463) made standard for amplitude calculations. It also designs sample grids, checks new samples against a reconstructed function, classifies stalled reconstructions modulo primes, and gives closed forms for a class of logarithmic integrals.

What it does

Differential equations for Feynman integrals are built from integration-by-parts reduction (the linear relations that reduce every integral of a family to a few master integrals). Each entry of their coefficient matrix is a rational function of the variable $t$ along the chosen kinematic path. A reduction run returns only the value of an entry at one numeric point. Ratfit takes sample points xs and values ys (Python Fractions) and returns numerator and denominator as exact flint.fmpq_poly polynomials. Everything runs in exact rational arithmetic; nothing here is a floating-point fit.

The package has these parts.

Ratfit has these limits:

Vopclose calls Ratfit for its exact entry reconstruction, and the sampled reductions typically come from Kira, FireFly and Fermat.

Examples

Reconstruct a rational function from 24 samples. The package's test samples $f=(3-2x+x^2)/(1+5x^2+7x^3)$ at $x=k/97$ and recovers it with and without the denominator. To run it, set up the package directory tools/ratfit/ first (see Requirements).

from fractions import Fraction
import flint
import ratfit

P_TRUE = flint.fmpq_poly([3, -2, 1])
Q_TRUE = flint.fmpq_poly([1, 0, 5, 7])
N_NODES = 24
XS = [Fraction(k, 97) for k in range(1, N_NODES + 1)]

def frac(v):
    return Fraction(int(v.p), int(v.q))

def feval(x):
    xq = ratfit.fq(x)
    return frac(P_TRUE(xq) / Q_TRUE(xq))

YS = [feval(x) for x in XS]

P, Q, ok, deg = ratfit.thiele_loo(XS, YS)
Pn, Qd, ok, deg = ratfit.ratrecon_with_denom(XS, YS, Q_TRUE)
assert ratfit.screen_modp(XS, YS, Q_TRUE) is True

Each fit returns numerator and denominator as fmpq_poly objects (ascending coefficients), a flag ok that is True only when the kept-out samples were reproduced exactly, and the degree. Here both give ok true and deg == 3, with str(Pn) == str(P_TRUE).

Adding 1 to ys[2] makes both blind routes return ok false, and screen_modp with the wrong cubic flint.fmpq_poly([2, 3, 1, 1]) returns False.

Design a sample grid on a kinematic path. For the straight path between two five-point configurations used in the tests, list the degenerate values of $t$, then ask for 30 fresh points that also avoid a known pole and two points sampled earlier.

from fractions import Fraction
from ratfit import coincidence_loci, design_grid

PA = dict(s12=-3, s23=-5, s34=-7, s45=-2, s15=-11, mm=1)
PB = dict(s12=-3, s23=-5, s34=-7, s45=-11, s15=-17, mm=2)

loci = coincidence_loci(PA, PB)
grid = design_grid(PA, PB, 30, exclude=("1/2", Fraction(7, 60)),
                   poles=("11/60",))

loci is keyed by exact fractions: on this path $s_{45}$ equals $s_{12}$, $s_{23}$ and $s_{34}$ at $t=1/9$, $1/3$ and $5/9$. grid is a list of 30 entries {"t": "p/q", "checked": ["no-coincidence", "no-pole", "fresh"]} drawn from $k/60$, $k/120$ and $k/240$, none equal to a locus, to $11/60$, or to an excluded point. Asking for more than the denominators can supply, design_grid(PA, PB, 6, denominators=(9,)), raises ValueError ("only 5/6 admissible t values ...") instead of returning five points.

Put a logarithmic integral in closed form and check that its divergences cancel. $\int_0^\infty \ln(1+t)\,/\,(t(1+t))\,dt=\pi^2/6$; after partial fractions it is two atoms, each divergent like $\ln^2\Lambda$ on its own.

import sympy as sp
from sympy import oo
import li2close as lc

atoms = [lc.Atom(1, 0, 1, 1, 1, 0, oo, 'pf.t'),
         lc.Atom(-1, 1, 1, 1, 1, 0, oo, 'pf.1pt')]
cl = lc.close_atoms(atoms)
f = lc.emitted_function(lc.emit_mpmath(cl.finite, 'val'), 'val')

Atom(c, W0, W1, P0, P1, lo, hi, tag) gives the coefficient, the denominator $W_0+W_1t$, the logarithm's argument $P_0+P_1t$ and the range. cl.finite is a sympy expression satisfying sp.simplify(cl.finite - sp.pi**2/6) == 0, and cl.ledger records the 'LE^0 LL^2' term with a verdict field showing it canceled. f(dps=50), compiled from the mpmath source that emit_mpmath writes, agrees with $\pi^2/6$ to at least 45 digits.

Passing only the first atom raises DivergenceError. Atoms that depend on a sympy symbol u need close_atoms(atoms, param=u, domain=(0, 1)).

Decide between another prime and a larger grid. Five coefficients on a $(50,100)$ grid refuse to lift; each was fitted at seven primes with the same degrees. The call is the first case of the submodule's self-test:

from ratfit.degree_alias import classify

r = classify((50, 100), [[((49, 99), (0, 0))] * 7] * 5)

Each inner list is one failing entry, each tuple one prime's fit as ((num_d, num_e), (den_d, den_e)). Here every numerator sits at the ceiling $(49, 99)$ over a trivial denominator, so r['verdict'] is 'ALIAS' and r['axis'] is 'd' (both axes are pinned and ties go to d). r['counts'] gives the breakdown, with n_fits and alias both 5.

Three entries on a $(29,101)$ grid with fits such as ((12, 46), (9, 47)) repeated at five primes give 'HEIGHT' with axis None. Replacing any entry by fits that disagree between primes makes the verdict 'INCONCLUSIVE'.

Routines

CommandWhat it does
python3 tools/thiele_gate.py IN.json [-o REPORT.json]Command-line form of gate_family: prints a summary, writes the report, exits with status 1 on any failure
python3 -m ratfit.degree_alias --selftestReplays the two reference cases and two inputs that must come back INCONCLUSIVE

IN.json is {"banked": [[x, [y, ...]], ...], "new": [...], "max_fit": 140} (optional "labels", "probe", "workers") with numbers as fraction strings; banked holds the trusted samples.

The fitting core and the grid design are loaded with import ratfit.

FunctionWhat it returns
thiele_loo(xs, ys)(P, Q, ok, deg) from the blind fit; thiele_loo_screened adds a modular pre-test before each exact fit
ratrecon_with_denom(xs, ys, Qknown)(Pnum, Qden, ok, deg): the numerator over a supplied denominator, tested on the kept-out samples, common factors divided out
screen_modp(xs, ys, Q)The modular version of that test; never rejects a correct Q; follow a True with ratrecon_with_denom
degree_budget(qex, n)Per row, for n samples: blind degree ceiling, highest denominator degree worth screening, projected denominator degrees for the next orders
parametric_rec_interp(rec_at_point, param_grid, normalize_key)Each recurrence coefficient as an exact polynomial in the parameters; mpoly_eval evaluates one
coincidence_loci(PA, PB){Fraction: "si=sj"}: every $t\in(0,1)$ on the straight path from PA to PB where two variables are equal
design_grid(PA, PB, n_points)n_points fresh rational $t$ values that avoid the loci, the poles in poles and the points in exclude

ratrecon_with_denom also returns ok False when Qknown vanishes at any sample point, because that sample would otherwise drop out of the fit unnoticed. qex maps each matrix entry $(i,j)$ and $\varepsilon$-order to a validated denominator's coefficients, and results are keyed by matrix row $i$.

parametric_rec_interp needs a complete tensor-product grid with at most deg_bound + 1 nodes per axis (deg_bound is 12 by default) and a normalize_key coefficient that is nonzero at every grid point. Its result must agree exactly at two parameter tuples off the grid. Otherwise it raises ValueError. coincidence_loci raises ValueError if two variables agree along the whole path, and design_grid if it cannot supply all the points.

The ratfit.thiele_gate submodule checks new samples against a reconstructed family.

FunctionWhat it returns
fit(xs, ys)A ThieleCF from an early-stopping fit that reproduces every sample left out of it, or None
gate(cf, new_pairs){'ok': n, 'fail': m, 'fails': [...]} for the untrusted samples
gate_family(banked, new)A report for vector-valued samples [(x, [y_0, ..., y_m]), ...], one fit per component

A ThieleCF is evaluated with cf(x) and raises CFDead at a true pole.

The ratfit.degree_alias submodule decides between primes and grid for a stalled modular reconstruction.

FunctionWhat it returns
classify(grid, cells){'verdict', 'axis', 'counts'} for a list of entries, with axis equal to 'd', 'eta' or None
classify_cell(grid, fits)The verdict for one failing entry

grid is the number of points per axis, $(n_d, n_\eta)$, and fits the per-prime list of ((num_d, num_e), (den_d, den_e)) fitted degrees. The rules are:

The ratfit.li2close submodule gives the closed forms for logarithmic integrals.

FunctionWhat it returns
Atom(c, W0, W1, P0, P1, lo, hi, tag)One term $c\ln\lvert P_0+P_1t\rvert/(W_0+W_1t)$ on $(lo, hi)$
close_atoms(atoms, param, domain)A Closure (.finite, .ledger, .pieces) after the divergence-cancellation check; raises DivergenceError if the check fails
emit_mpmath(expr, name, param)Standalone mpmath source defining name(dps=50) or name(param, dps=50); emitted_function(src, name) executes it
RLi2The sympy function $\mathrm{Re}\,\mathrm{Li}_2(x)$ used in the results

tools/thiele_gate.py, tools/li2close.py and tools/pathgrid.py forward to the package, so import thiele_gate, import li2close and from pathgrid import design_grid work too. degree_alias has no such file, but import degree_alias works with tools/ratfit/ itself on the path.

The optional arguments and the remaining functions (thiele, newton_interp, extract_stairs, row_lcm, validate, discriminator, ilin_atoms) are described in the docstrings of the four modules. The helpers fq, qpoly, poly_lcm and exact_div and the list SCREEN_PRIMES are in __all__ in tools/ratfit/__init__.py.

Used on this site

Requirements

Source and references

The code is tools/ratfit/ in the BootLoops repository. Thiele interpolation is classical. Ratfit applies it in exact rational arithmetic to a fixed set of samples. FiniteFlow and FireFly are two public programs that apply it modulo primes.

ReferenceWhat it supplies
T. Peraro, arXiv:1608.01902; code: FiniteFlow, arXiv:1905.08019Thiele interpolation of a rational function of one variable from sample points, with a stopping test on new points
J. Klappert and F. Lange, arXiv:1904.00009; J. Klappert, S. Y. Klein and F. Lange, arXiv:2004.01463; code: FireFlyThe same interpolation in FireFly; screening modulo a prime before an exact reconstruction follows FireFly's approach
python-flint (F. Johansson, O. Benjamin and contributors); mpmath (F. Johansson and the mpmath contributors); SymPy (its development team)The exact polynomials (fmpq_poly) of the fitting core; the numerical and symbolic parts of li2close

← back to the tools index