Winnow

The content on this page was written by AI under human supervision.

Winnow is a Python library for the elimination step of integration-by-parts (IBP) reduction, carried out modulo a prime at one numerical kinematic point. You give it the sparse linear identities, an elimination order and the columns that stand for master integrals. It returns every eliminated integral written in terms of the masters, an independently checkable certificate for each row you ask about, and a JSON log of the run. The package imports as ibplapper (import winnow is an alias). Seedling uses it as its elimination engine, and its certificate checker is a byte-identical copy of the receipt module of Trust.

What it does

A multi-loop Feynman-integral calculation produces a large, sparse linear system, the IBP identitieslinear relations among the integrals of one family, obtained by integrating a total derivative; they reduce thousands or millions of integrals to a few master integrals. Laporta's algorithm solves it by Gaussian elimination in a fixed order, most complicated integrals first, so that everything is expressed through a small basis of master integrals. Reduction programs such as Kira do this in a prime field $\mathbb F_p$ at numerical values of the dimension and the invariants and reconstruct the rational coefficients from many samples. Winnow is that one elimination as a library with a fixed contract. It never sees an integral or an invariant: columns are opaque integers, and the physics enters through three dictionaries. order ranks the columns (higher rank eliminated first), forbid lists the master columns (never used as pivots), and the optional stratum_of groups columns into blocks solved one after another, highest stratum first.

The call is eliminate(System, Schedule). In the result, subs maps each pivot column $t$ to a closed row $r$ over master columns only, with the convention $I_t + \sum_m r[m]\, I_m = 0 \pmod p$. Relations among the masters themselves (a redundant basis or a rank-deficient system) come back in leftover and are never dropped. The four pivot policies B2, B3, B2F and B2FT give identical answers and differ only in fill-in and running time. A Schedule may carry a Bank, an append-only on-disk table that stores each block's reduced rows under a key, refuses to overwrite a key and verifies a SHA-256 checksum on every read. It may also carry caps (stratum_wall_s, total_wall_s, stratum_fill), checked at the end of each block; when one is exceeded the run raises CensoredError with the partial log attached instead of returning a truncated table.

For any pivot listed in witness_targets, witnesses="retrofit" produces a certificate: sparse multipliers $\lambda_i$ over the input rows $R_i$ and the claimed master coefficients $c_m$ such that

$$\sum_i \lambda_i\, R_i \;=\; e_t - \sum_m c_m\, e_m \pmod p .$$

If the identity holds, the row $I_t=\sum_m c_m I_m$ is an exact linear consequence of the input system at that point and prime, whatever code produced it. The check is exact integer arithmetic with no tolerance, about a millisecond per row; the checker, ibplapper.receipt, imports nothing from the solver and is meant to be run against your own parse of the input rows. The certificate is deliberately narrow: one kinematic point, one prime, no statement about a symbolic table, and no statement that the input system itself was correct or complete. The package's README records why every table should carry one anyway: a reduction table that had full rank and agreed at two primes was wrong, and only the certificate check rejected it.

Two adapters build a System from files on disk. The first reads Kira's intermediate files. Run Kira with run_initiate: true (generate and select the identities, no back-substitution); adapters.kira.load then turns the SYSTEM_.gz files into a System, with masters forbidden and each column's stratum set to the number of propagators in its sector. SYSTEM_.gz is an undocumented internal Kira format that the adapter decodes empirically; the decode was validated for Kira 3.1 (kira.db version 2.1, integral ordering 5), so the adapter refuses other packing constants (KiraVersionError) and records ABSENT-UNGUARDED when there is no kira.db. Kira does not export its weight-to-integral dictionary, so the readable master labels the adapter attaches are best effort and must be confirmed by the certificate check. Nothing is written back into Kira. The second adapter, adapters.user_system.load, reads equation files in Kira's documented user_defined_system input format (one integral*coefficient term per line, blank lines between equations, integer weights or name[indices] labels, plain or gzipped) and needs no Kira installation or version check. You pass the numerical value of every symbol in the coefficients; an undeclared symbol stops the load with an error. With name[indices] labels the adapter assigns standard Laporta ranks and propagator-count strata, which you may override.

Winnow does not generate identities, apply sector symmetries, choose the ordering, combine primes by Chinese remaindering or reconstruct rational functions; that stays with the caller. The default engine is pure Python on dictionary rows; the largest system measured had about 454,000 equations and took roughly 14 minutes and 20 GB per numerical point. An optional dense backend (backend="dense", PyTorch, policies B2F/B2FT, $p \lt 2^{31}$) reproduces the default output exactly. Certificates are solved for after the elimination and cost a few seconds per row per prime on a 7,000-equation system, so estimate the time for a large batch before requesting one. witnesses="native" instead records the multipliers during the elimination, with no solve afterwards; it runs with policies B2F/B2FT on the default backend only (B2, B3 and backend="dense" raise NotImplementedError), and since the tracking adds fill, each run writes its measured cost into ledger["witnesses"]["transcript_fill"]. In both modes the certificate is verified through ibplapper.receipt before it is returned.

Examples

A three-identity system with certificates. Columns 201 to 203 are integrals to eliminate, 101 and 102 are masters; the snippet is the untampered case of the package's tamper test (tests/test_sabotage.py; OUT is a scratch directory).

import os
import ibplapper as lap

P = 2147483647
ROWS = [{203: 1, 101: (-5) % P},
        {202: 1, 203: (-3) % P, 102: (-7) % P},
        {201: 1, 202: (-2) % P, 101: (-1) % P}]

sys_ = lap.System(ROWS, P, {201: 3, 202: 2, 203: 1}, forbid={101, 102})
res = lap.eliminate(sys_, lap.Schedule(policy="B2FT"), witnesses="retrofit",
                    witness_targets=[201, 202, 203],
                    witness_dir=os.path.join(OUT, "wits"))

res.subs[202] is {101: P-15, 102: P-7}, that is $I_{202} = 15\,I_{101} + 7\,I_{102}$; likewise $I_{203}=5\,I_{101}$ and $I_{201}=31\,I_{101}+14\,I_{102}$, and res.leftover is empty. Each res.witnesses[t] records the certified coefficients c ({101: 15, 102: 7} for 202), status "CERTIFIED", verify_pass True, the nonzero multipliers lam, and witness_path, here OUT/wits/w_2147483647_202.json. res.ledger holds the prime, the policy, a SHA-256 fingerprint of the input rows, per-stratum statistics and a witness summary; res.save_ledger(path) appends it to a file as one JSON line. To check a certificate later against rows you parsed yourself (README):

from ibplapper import receipt
ok, detail = receipt.verify(my_own_rows_parse, "w_2147483647_....json")

ok is True only on an exact match; otherwise detail["reason"] names the failure (identity failed, row count differs, fingerprint mismatch).

Checking a certificate with nothing installed. The site hosts the same three-row system, its certificate for column 202, a tampered copy, and a short checker in standard-library Python. Put winnow-evaluate.py, system.jsonl, w_202.json and w_mut.json in one directory and run

python3 winnow-evaluate.py

The output begins

[0] loaded system: 3 rows
[1] verify(true witness w_202): PASS (exact match; target e_202 = 15*e_101 + 7*e_102 mod 2147483647)
[2] verify(mutated witness w_mut): FAIL as required (mismatch (extra cols [], missing [], wrong-value [101, 102]))
[3] table-mode: wrong claimed row FAILS (mismatch (extra cols [], missing [], wrong-value [101])); true claimed row PASSES

followed by a note that the optional benchmark step was skipped and a summary line; the exit status is 0. Step 3 is the case that matters in practice: the certificate is valid, and a table claiming different coefficients for the same row is rejected because it disagrees with what the certificate proves.

Behind Kira, or from equation files. After a Kira run with run_initiate: true, load one numerical slice of the generated system and eliminate it (README quickstart):

from ibplapper.adapters import kira
system, sysd = kira.load(art_dir, family, p, d0, eta0,
                         expect_counters={"eqs": 7135, "terms": 42286})
res = lap.eliminate(system, lap.Schedule(policy="B2FT"))

art_dir is the Kira working directory (with tmp/<family>/SYSTEM_*.gz, results/<family>/masters, sectormappings/); d0 and eta0 are the integers at which $d$ and the auxiliary parameter $\eta$ are evaluated modulo p. expect_counters is optional: if the loaded equation and term counts differ from the declared ones, load raises ProvenanceError rather than reducing a system other than the one you intended. sysd keeps the adapter's bookkeeping (counters with the version_guard record, masters, sector_of), and system.meta carries the same labels through untouched. res.subs is keyed by Kira's integer weights; a relation among Kira's declared masters would appear in res.leftover.

Without Kira, the same kind of slice loads from equation files in the user_defined_system format (README quickstart):

from ibplapper.adapters import user_system
system, sysd = user_system.load(
    "eqs/", p, values={"d": d0, "s": s0, "m2": m20},   # one numeric slice
    forbid=[("T", (1, 0, 0))],                         # masters, by label
    expect_counters={"eqs": 7135, "terms": 42286})
res = lap.eliminate(system, lap.Schedule(policy="B2FT"))

eqs/ is a file or a directory of .kira/.kira.gz files, and forbid takes (family, indices) labels or raw column ids. sysd["labels"] maps each column back to its integral, so res.subs can be read as reduction rules; a downstream check re-parses the same files and calls receipt.verify, as for every route.

Routines

Library (import ibplapper as lap; import winnow exposes the same names)

Certificates (ibplapper.receipt, the copy of Trust's receipt module; ibplapper.witness; ibplapper.certify)

Adapters (ibplapper.adapters.kira, ibplapper.adapters.user_system)

Lower level (ibplapper.engine, .coverage, .backends)

Scripts

Requirements and source

Python 3.10 or newer with NumPy; python-flint only for the tests (an independent dense row reduction to compare against), PyTorch only for backend="dense". Run the self-tests with tests/run_tests.sh [scratch_dir]: the suites that need only this package run as is, and those that replay archived Kira systems print SKIP unless WINNOW_BANKED_ROOT and WINNOW_T1_ROOT point at the files. The code is tools/winnow/ in BootLoops' bootloops-dev repository (GitHub organization BootLoops-ai), released under the MIT license (package ibplapper, alias winnow; the checker under ibplapper/receipt/ is a verbatim copy of the checker modules in tools/trust/receipt/ (core.py, emitter.py, detector.py), and a test enforces that the copies stay identical). The site also hosts a benchmark bundle (checksum): pre-generated IBP systems of about 2,000 to 180,000 equations with reference reductions. The driver run_bench.sh listed above needs only numpy, mpmath and python-flint, not Kira. Background: Laporta, hep-ph/0102033; Kira, arXiv:2008.06494.

← back to the tools index