Analysis of PSLQ, an integer relation finding algorithm
From MaRDI portal
Let \(\mathbb{K}\) be the real, complex or quaternion field and \(\mathbb{O}(\mathbb{K})\) the corresponding system of integers. A vector \(x\in\mathbb{K}^n\) is said to have an integer relation if there exist integers \(m_i\in\mathbb{O}(\mathbb{K})\), not all zero, such that \(m_{1}x_{1}+\dots+m_{n}x_{n}=0\). In recent years, several algorithms for finding such integer relations numerically have been developed. Application of such an algorithm to a vector \(x\) leads either to the construction of an integer relation for \(x\) or to a lower bound for the norm of any such relation. Only the second outcome constitutes a proof in a mathematical sense; an integer relation constructed by the algorithm could, with very low probability, be spurious and needs a separate proof. In this paper the authors define and investigate a class of such algorithms, the class PSLQ(\(\tau\)), where \(\tau\) is a parameter whose range depends on \(\mathbb{K}\). They prove the following (for \(\mathbb{K}=\mathbb{R}\) or \(\mathbb{C}\)). Assume that an integer relation for \(x\) exists and denote the smallest norm of all such relations by \(M_{x}\). Then PSLQ(\(\tau\)) constructs an integer relation in \(O(n^3+n^2\log M_{x})\) iterations, where the \(O\)-constant is given explicitly. The detected relation~\(m\) may have norm~\(| m| \) larger than \(M_{x}\), but not too much larger: the authors give an upper bound for \(| m| / M_{x}\).
Recommendations
- Extending the PSLQ Algorithm to Algebraic Integer Relations
- The PSLQ algorithm for empirical data
- Integer Relations Among Algebraic Numbers
- Two variants of HJLS-PSLQ with applications
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
- On the hardness of approximating shortest integer relations among rational numbers
- Applications of integer relation algorithms
- A new view on HJLS and PSLQ: sums and projections of lattices
- A noninductive GL(n, Z) algorithm that constructs integral linear relations for n Z-linearly dependent real numbers
Cites work
- A Fortran 90-based multiprecision system
- A more efficient algorithm for lattice basis reduction
- A noninductive GL(n, Z) algorithm that constructs integral linear relations for n Z-linearly dependent real numbers
- Algorithm 719: Multiprecision translation and execution of FORTRAN programs
- Diophantine approximation of complex numbers
- Experimental Evaluation of Euler Sums
- Factoring polynomials with rational coefficients
- Fractional and Trigonometric Expressions for Matrices
- Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 3119278 (Why is no real title available?)
- scientific article; zbMATH DE number 3140585 (Why is no real title available?)
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 3745287 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 194764 (Why is no real title available?)
- Improved low-density subset sum algorithms
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Numerical results on the transcendence of constants involving 𝜋,𝑒, and Euler’s constant
- On the rapid computation of various polylogarithmic constants
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
- Ratio in early Greek mathematics
- The Generalized Basis Reduction Algorithm
- Vanishing sums in function fields
Cited in
(96)- Exact asymptotics of the characteristic polynomial of the symmetric Pascal matrix
- The hyperelliptic integrals and
- The structure of the spectra of Pisot numbers.
- Three-point functions in \(\mathcal{N}=4\) SYM: the hexagon proposal at three loops
- Towards the five-loop beta function for a general gauge group
- Five-particle phase-space integrals in QCD
- Five-loop quark mass and field anomalous dimensions for a general gauge group
- Complete renormalization of QCD at five loops
- The Sudakov form factor at four loops in maximal super Yang-Mills theory
- Formal proofs of degree 5 binary BBP-type formulas
- Applications of integer relation algorithms
- Charge asymmetry in electron/positron energy loss in nuclear Bremsstrahlung
- The four-loop \(\mathcal{N} = 4\) SYM Sudakov form factor
- BBP-type formulas -- an elementary approach
- Binomiality testing and computing sparse polynomials via witness sets
- On the use of Montgomery multiplication in the computation of binary BBP-type formulas for mathematical constants
- New series for powers of \(\pi\) and related congruences
- Four-loop collinear anomalous dimensions in QCD and \(\mathcal{N} = 4\) super Yang-Mills
- Harmonic-binomial Euler-like sums via expansions of \((\arcsin x)^p\)
- On the computation and verification of \(\pi\) using BBP-type formulas
- High-precision arithmetic in mathematical physics
- Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
- Evaluating `elliptic' master integrals at special kinematic values: using differential equations and their solutions via expansions near singular points
- The two-loop hexagon Wilson loop in \(\mathcal{N}=4\) SYM
- Calculation of the quark and gluon form factors to three loops in QCD
- Irreducible constituents of monomial representations.
- Position-space cuts for Wilson line correlators
- MB tools reloaded
- Analytic computation of three-point energy correlator in QCD
- Parallel integer relation detection: techniques and applications
- Two variants of HJLS-PSLQ with applications
- A new view on HJLS and PSLQ: sums and projections of lattices
- The leading-order dressing phase in ABJM theory
- Analytic results for planar three-loop four-point integrals from a Knizhnik-Zamolodchikov equation
- On the rapid computation of various polylogarithmic constants
- Extending the PSLQ Algorithm to Algebraic Integer Relations
- Advances in the theory of box integrals
- Using integer relations algorithms for finding relationships among functions
- Analytic results for massless three-loop form factors
- scientific article; zbMATH DE number 3980478 (Why is no real title available?)
- scientific article; zbMATH DE number 17811 (Why is no real title available?)
- Six-loop anomalous dimension of twist-three operators in \(\mathcal{N} = 4\) SYM
- Analytic epsilon expansion of three-loop on-shell master integrals up to four-loop transcendentality weight
- Numerical results on relations between fundamental constants using a new algorithm
- scientific article; zbMATH DE number 1114499 (Why is no real title available?)
- Special values of multiple polylogarithms
- Constructing exact symmetric informationally complete measurements from numerical solutions
- Experimental math for Math Monthly problems
- The PSLQ algorithm for empirical data
- On the Random Character of Fundamental Constant Expansions
- A complete algorithm to find exact minimal polynomial by approximations
- On the Euler scale and the \({\mu}\)Euclidean integer relation algorithm
- Expected distances on manifolds of partially oriented flags
- Empirical determinations of Feynman integrals using integer relation algorithms
- Calculating four-loop corrections in QCD
- Jonathan Borwein: Renaissance Mathematician
- LLL: a tool for effective Diophantine approximation
- Selected applications of LLL in number theory
- A numerical transcendental method in algebraic geometry: computation of Picard groups and related invariants
- The constructive membership problem for discrete two-generator subgroups of \(\operatorname{SL}_2(\mathbb{R})\)
- Several BBP-type formulas for
- Jonathan Borwein: Experimental Mathematician
- Evaluating multiple polylogarithm values at sixth roots of unity up to weight six
- Recognition of Computationally Constructed Loci
- Random Generators and Normal Numbers
- Introduction [From analysis to visualization. A celebration of the life and legacy of Jonathan M. Borwein]
- Two-loop corrections to Lamb shift and hyperfine splitting in hydrogen via multi-loop methods
- On the Landau-Khalatnikov-Fradkin transformation in quenched \(\text{QED}_3\)
- An off-shell Wilson loop
- Off-shell form factor in \(\mathcal{N} =4\) sYM at three loops
- Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
- Trilateration using unlabeled path or loop lengths
- \(\mathcal{O}(m \alpha^2(Z\alpha)^6)\) contribution to Lamb shift from radiative corrections to the Wichmann-Kroll potential
- Analytic auxiliary mass flow to compute master integrals in singular kinematics
- Near mass-shell double boxes
- Periodic point processes: theory and application
- Enhanced and generalized one-step Neville algorithm: fractional powers and access to the convergence rate
- Computer algebra in the service of enumerative combinatorics
- Three-leg form factor on Coulomb branch
- Analytic regression of Feynman integrals from high-precision numerical sampling
- Monodromy of multiloop integrals in d dimensions
- Special values of generalized polylogarithms
- New formulae of BBP-type with different moduli
- Rationalisation of multiple square roots in Feynman integrals
- Electroweak double-box integrals for Møller scattering
- Factoring polynomials and the knapsack problem
- Calculation of massless Feynman integrals using harmonic sums
- Toward the analytic bootstrap of energy correlators
- General four-loop beta function for scalar-fermion theories in three dimensions
- On the generalized summation of series with rational coefficients
- HyperPrecision: a Mathematica package for high-precision numerical evaluation of multivariate hypergeometric functions
- The Lieb-Liniger model
- Reconstructing rational functions on finite abelian groups with higher autocorrelations
- BootLoops: an LLM-driven toolkit for exact quantitative science
- Hexagon functions and the three-loop remainder function
- Massive Feynman diagrams and inverse binomial sums
This page was built for publication: Analysis of PSLQ, an integer relation finding algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4221985)
