A New View on HJLS and PSLQ: Sums and Projections of Lattices

Jingwei Chen, Damien Stehlé and Gilles Villard

Abstract: The HJLS and PSLQ algorithms are the de facto standards for discovering non-trivial integer relations between a given tuple of real numbers. In this work, we provide a new interpretation of these algorithms, in a more general and powerful algebraic setup: we view them as special cases of algorithms that compute the intersection between a lattice and a vector subspace. Further, we extract from them the first algorithm for manipulating finitely generated additive subgroups of a euclidean space, including projections of lattices and finite sums of lattices. We adapt the analyses of HJLS and PSLQ to derive correctness and convergence guarantees. We also investigate another approach based on embedding the input in a higher dimensional lattice and calling the LLL lattice reduction algorithm.

Download: pdf.
Homepage