PSLQ and LLL (external)

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

PSLQ and LLL are public algorithms with public implementations: BootLoops runs PSLQ from the mpmath Python library (Fredrik Johansson and collaborators) and LLL and BKZ lattice reduction from the fplll library, or from Nemo in Julia code. It uses them for the last step of a calculation, turning a number known to many digits into an exact formula in known constants. BootLoops adds the checks around them, in Lockpick and Gatekeeper. Every search runs at two precisions, the coefficient bound is matched to the digits available, a synthetic target must be found before a negative answer counts, and an LLL change of basis repairs ill-conditioned fits.

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 period. 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 fit, the same step turns them into exact rationals.

PSLQ (Ferguson, Bailey and Arno) takes the numbers at a set working precision and a bound on the coefficients, and returns either an integer vector whose combination vanishes to within a tolerance or None. LLL (Lenstra, Lenstra and Lovász) 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 and slower block version of LLL that fplll provides. LLL handles many numbers at once and copes better with ill-conditioned input; PSLQ is simpler to call and cheap 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, and 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. Independence: if the candidates themselves satisfy a relation, PSLQ returns that one, with a zero coefficient on the target, which 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 and stop with a message when they cannot be met; the raw library calls do not. 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, and 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 (three quarters of the working precision by default), 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 independence 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. 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]), 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), "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.

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 and 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

BootLoops adds no code inside mpmath or fplll; both are installed from upstream. BootLoops code written directly around them:

Around mpmath.pslq

Around LLL and BKZ

Used on this site

Requirements and source

mpmath is pure Python (BSD license), one of the core dependencies of BootLoops' bootloops-dev repository (GitHub organization BootLoops-ai; pip install mpmath); mpmath.org. fplll is a C++ library and command-line program (LGPL) with Python bindings fpylll; github.com/fplll/fplll. Without either form of fplll, Lockpick falls back to Nemo (Julia) or pure Python and loses BKZ. Self-tests that exercise both algorithms: python3 gatekeeper/test_gatekeeper.py from the repository's tools/ directory (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), and the --selftest command in the Routines list, which repeats the checks of Example 3 on inputs built with known answers. The wrappers are tools/lockpick/, tools/gatekeeper/ and tools/landau-alphabet/ in the bootloops-dev repository, released under the MIT license; mpmath and fplll are not bundled and keep their own licenses. References: H. R. P. Ferguson, D. H. Bailey and S. Arno, Math. Comp. 68 (1999) 351; A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, Math. Ann. 261 (1982) 515; Lockpick's rawlll multi-point construction follows arXiv:2507.17815.

← back to the tools index