PSLQ and LLL (external)
PSLQ and LLL are public algorithms that turn a number known to many digits into an exact formula in known constants. PSLQ is by Ferguson, Bailey and Arno and LLL by Lenstra, Lenstra and Lovász; BootLoops runs PSLQ from mpmath (Fredrik Johansson and collaborators) and LLL from fplll or the Julia package Nemo. It uses them for the last step of a calculation and adds the checks around them, in Lockpick and Gatekeeper.
Where it comes from
The algorithms and the libraries are other people's work. BootLoops adds no code inside mpmath or fplll; both are installed from upstream.
| Part | Source | Authors |
|---|---|---|
| PSLQ | pslq in mpmath | Ferguson, Bailey and Arno (algorithm); Fredrik Johansson and the mpmath contributors (library) |
| LLL and its block version BKZ | fplll, with its Python bindings fpylll | Lenstra, Lenstra and Lovász (LLL); the FPLLL development team (library) |
| LLL in Julia code | lll in Nemo | C. Fieker, W. Hart, T. Hofmann, F. Johansson and contributors |
| The multi-point lattice fit | arXiv:2507.17815 | Barrera, Dersy, Husain, Schwartz and Zhang; Lockpick's rawlll construction and Landau Alphabet's lattice_fit follow their paper |
| The checks, and the LLL used when no library is installed | Lockpick and Gatekeeper | BootLoops code |
Please cite the authors' papers when you use these routines. BootLoops is not affiliated with or endorsed by the authors of mpmath, fplll or Nemo.
What it does
An integer relation among real numbers $x_0,\dots,x_n$ is a vector of integers $(c_0,\dots,c_n)$, not all zero, with
$$c_0x_0+c_1x_1+\dots+c_nx_n=0 .$$
Take $x_0$ to be a Feynman integral computed numerically to 100 or 200 digits and $x_1,\dots,x_n$ to be candidate constants such as $\pi^2$, $\zeta(3)$, $\log 2$ or an elliptic periodan integral around a closed cycle of an elliptic curve. A relation with small coefficients that holds to all those digits says $x_0=-(c_1x_1+\dots+c_nx_n)/c_0$: an exact formula read off from decimals. Applied to the floating-point coefficients of a least-squares fita fit whose coefficients minimize the sum of squared differences from the data, the same step turns them into exact rationals.
PSLQ takes the numbers at a set working precision and a bound on the coefficients. It returns either an integer vector whose combination vanishes to within a tolerance or None. LLL reaches the same answer through lattice reductionreplacing a set of long, nearly parallel integer vectors that span a lattice by short, nearly orthogonal ones spanning the same lattice. Each number, multiplied by $10^p$ and rounded, is appended to a unit vector. After reduction a genuine relation appears as a short vector whose last entry is nearly zero and whose other entries are the $c_i$. BKZ is a stronger block version of LLL that fplll provides.
LLL handles many numbers at once and copes better with ill-conditionedsaid of a fit in which small errors in the input produce large errors in the coefficients input. PSLQ is simpler to call for a handful of constants. BootLoops usually runs both on the same data, because they fail in different ways.
The output of either algorithm is numerical evidence, never a proof. Its strength rests on three things the algorithms do not check:
- Digits. Telling a true relation with coefficients up to $H$ among $n$ candidates apart from a chance near-miss needs roughly $(n+1)\log_{10}H$ digits plus a margin. With fewer, the search returns nothing or a spurious vector of large integers.
- Dependent candidates. If the candidates themselves satisfy a relation, PSLQ returns that one, with a zero coefficient on the target. It is easy to misread as "no formula exists" (Example 1).
- Confirmation. An accepted relation should reappear at a higher precision and reproduce values that were not used to find it.
The BootLoops wrappers enforce these points. Every search runs at two precisions, and the coefficient bound is matched to the digits available. A synthetic target, a number built from the candidates with known coefficients, must be found before a negative answer counts. An LLL change of basis repairs ill-conditioned fits. The wrappers stop with a message when a check cannot be met; the raw library calls do not.
The method has these limits:
- An integer-relation search is the wrong tool when the quantity can be derived symbolically, or when the digits available fall short of the count above.
- It only recognizes combinations of the constants it is given.
Examples
Raw PSLQ in mpmath (from the mpmath documentation). Verify Machin's formula $\pi/4=4\,\mathrm{acot}\,5-\mathrm{acot}\,239$, then try to discover a formula for $\pi$ from $\mathrm{acot}\,2,\dots,\mathrm{acot}\,10$.
>>> from mpmath import * >>> mp.dps = 30 >>> pslq([pi/4, acot(5), acot(239)]) [1, -4, 1] >>> pslq([pi] + [acot(n) for n in range(2,11)]) [0, 1, -1, 0, 0, 0, -1, 0, 0, 0] >>> pslq([pi] + [acot(n) for n in range(2,11) if n not in (3, 5)]) [1, -8, 0, 0, 4, 0, 0, 0]
pslq(x) returns integers $c$ with $\sum_k c_kx_k=0$ to the tolerance, or None when no relation with coefficients below maxcoeff (default 1000) is found. The second call shows the dependent-list pitfall: $\mathrm{acot}\,2=\mathrm{acot}\,3+\mathrm{acot}\,7$ holds among the candidates alone, so PSLQ returns that relation with a zero in the slot for $\pi$. With the dependent entries removed, the third call finds $\pi=8\,\mathrm{acot}\,2-4\,\mathrm{acot}\,7$.
Lockpick's members_audit runs this dependence check before any search, and its search raises DegeneratePoolError rather than returning the misleading vector.
An integer relation by LLL (Gatekeeper's test T5). Build a number from five constants with known integer coefficients and recover them by lattice reduction. With mpmath installed (see Requirements), run it from the repository's tools/ directory so that import gatekeeper works.
import mpmath as mp
from gatekeeper import pslq_with_lll
mp.mp.dps = 80
b = [mp.zeta(3), mp.pi ** 2 * mp.log(2), mp.log(2) ** 3,
mp.mpf(1), mp.catalan * mp.log(2)]
target = 7 * b[0] - 2 * b[1] + 11 * b[2] - 5 * b[3] + 3 * b[4]
rel, method = pslq_with_lll([target] + b, prec=60, max_coeff_bits=20)
The test suite prints T5 pslq_with_lll: PASS (method=lll, rel=[1, -7, 2, -11, 5, -3]). This is the relation $\mathrm{target}-7b_0+2b_1-11b_2+5b_3-3b_4=0$, found by LLL on the numbers scaled to 60 digits.
method is "lll" when a reduced lattice vector passes a residual check at full precision with every coefficient below $2^{20}$ (max_coeff_bits). It is "pslq" when only the mpmath fallback succeeded, and None with rel = None when neither did.
A checked PSLQ search (Lockpick's library form, from the module's usage text). Identify one number, given as the decimal string target_str, against named constants. It runs from the same tools/ directory.
from pslq_gate import two_prec_stable, controls, reverify
pool = {'1': '1.000...', 'pi^2': '9.8696...'} # >=200-digit strings
vec = two_prec_stable(target_str, ['1','pi^2'], pool, dps_pair=(120,200),
maxcoeff=10**6)
two_prec_stable runs mpmath.pslq at 120 and at 200 digits. It returns $(c_0,c_1,c_2)$, common factor removed and first nonzero entry positive, only if both runs agree; otherwise None. It raises DigitsError if a string carries fewer than 200 digits, CapacityError if maxcoeff needs more digits than the 120-digit run holds, and DegeneratePoolError if the pool is dependent.
controls(pool) must recover the synthetic target $(3b_1-7b_2)/5$ with the same settings before a null result is reported, and reverify recomputes an accepted relation at 210 digits. The command-line form and the multi-point lattice fitter are on the Lockpick page.
Routines
These are the BootLoops routines written directly around the two libraries. Commands are given from the repository root.
| Command | What it does |
|---|---|
python3 tools/pslq_gate.py --target file.json:key --pool pool.json | The checked single-number search of Example 3 |
python3 tools/lockpick/sealrun/t6_close.py --target-string-file FILE [--label NAME] [--out DIR] | The same search in a fixed form: one real constant, to at least 150 digits, against a frozen list of 24 constants |
python3 tools/lockpick/bilmine/selftest.py | Self-test of the bilmine scripts, which search for integer bilinear relations among the entries of period matrices |
| Function | What it returns |
|---|---|
two_prec_stable, members_audit, capacity, controls, reverify, canonicalize | The checked search of Example 3 and its separate checks, in tools/lockpick/pslq_gate.py |
gatekeeper.pslq_with_lll(values, prec=None, max_coeff_bits=64) | (relation, method): LLL on the relation lattice first, mpmath.pslq as fallback (Example 2) |
gatekeeper.auto_condition(basis_matrix, target_cond=1e6, prec=None, drop_tol_digits=None) | (U, cond_before, cond_after, AU): an integer change of basis for an ill-conditioned basis matrix, and the reduced matrix |
lockpick.mplll_lattice.reduce_rows(rows, backend=None, bkz_beta=0) | A triple whose first two entries are the reduced vectors and the name of the backend used |
lockpick.mplll.mplll_fit(...) | The multi-point fit: one lattice from a target function and a basis sampled at many points |
lattice_fit, integer_relation, fit_residual | The same constructions in Julia, on Arb ball values (numbers carried with error bounds) with Nemo's LLL, in Landau Alphabet |
graded_basket, odd_zeta_pool and load_amflow_targets are further routines of tools/lockpick/pslq_gate.py. The Lockpick page has the signatures of the main routines, the second input form and the exit codes of t6_close.py, and the reduction backends with the environment variables that select them. gatekeeper.heldout_certify applies auto_condition on its own unless it is called with auto_cond=False.
In Landau Alphabet, FitResult.ok is the coefficient-size check alone. The residual and the values left out of the fit are checked separately.
PMflow, Vopclose, SubTropica's fibrate.py and Lockpick's ring15 table builder call mpmath.pslq on their own output to recognize rationals or short combinations. Coalescer's pslq_calpha.py runs Lockpick's checked search in the t6_close.py form instead.
Used on this site
- Banana: returned the exact coefficients $(7\zeta_3,\ 0,\ 0,\ {-1})$ of the two-term formula in the basis of solutions.
- Kite: recognized the five coefficients as rational multiples of $1$, $\pi^2$ and $\mathrm{Cl}_2(2\pi/3)$.
- Unequal-mass kite: searches on the boundary constant $N_{\rm kite}$, which found no expression in the constants tried.
- Sunrise: fixed the rational coefficients and identified the boundary constant as $\tfrac32\sqrt3\,L(\chi_{-3},2)$.
- Light-by-light box with a sunrise insertion: identified the boundary constants $B^{(0)}$, $B^{(1)}$ and $B^{(2)}$.
- Crossed light-by-light box: identified four boundary constants of the word form among zeta values and found no relation for the other five through weight eight.
Requirements
- Runs on: Python 3 with mpmath. The Landau Alphabet routines need Julia with the packages listed in
tools/landau-alphabet/LandauAlphabet.jl/Project.toml(Nemo and Arblib among them). - Install:
pip install mpmath. mpmath is one of the core dependencies of the BootLoops repository. mpmath and fplll are not bundled. - Self-test:
python3 gatekeeper/test_gatekeeper.pyfrom the repository'stools/directory ends withALL TESTS PASS; it needs sympy. T4 recovers exact coefficients from a basis matrix with condition number above $10^{61}$, where least squares plus PSLQ finds nothing. T5 is Example 2. - Self-test of the checked search:
python3 tools/pslq_gate.py --selftestfrom the repository root ends with a line beginningSELFTEST PASS. It repeats the checks of Example 3 on inputs built with known answers. - Optional: fplll, a C++ library and command-line program with Python bindings
fpylll. Without either form of fplll, Lockpick falls back to Nemo (Julia) or pure Python and loses BKZ.
Source and references
The wrappers are tools/lockpick/, tools/gatekeeper/ and tools/landau-alphabet/ in the BootLoops repository. The links to mpmath and fplll are in the table under Where it comes from.
| Reference | What it supplies |
|---|---|
| H. R. P. Ferguson, D. H. Bailey and S. Arno, Math. Comp. 68 (1999) 351 | The PSLQ algorithm |
| A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, Math. Ann. 261 (1982) 515 | The LLL algorithm |
| O. Barrera, A. Dersy, R. Husain, M. D. Schwartz and X. Zhang, arXiv:2507.17815 | The multi-point lattice fit that Lockpick's rawlll construction follows |