Adaptive Precision Search for Integer Relations: The APS Algorithm

Finding integer relations is an important problem in computational mathematics. Given a set of real numbers, the task is to determine whether there exist small integer coefficients such that their linear combination equals zero. This paper presents APS (Adaptive Precision Search), an algorithm that uses an integer lattice embedding and LLL reduction to generate candidate integer relations. Unlike a single, direct application of LLL, APS uses several levels of computational precision. At each level, an integer lattice is constructed, LLL reduction is performed to obtain a transformation matrix, and candidates are extracted from that matrix. The original real-valued residual is computed for each candidate. Candidates that remain stable as precision increases are preferred over accidental approximate relations. In the experiments conducted, APS successfully recovered the prescribed relations in dimensions ranging from 4 to 30. At higher dimensions, a substantial runtime advantage over PSLQ was observed. In a dimension-30 test with a coefficient bound of 10, APS ran in approximately 0.027 seconds, whereas the PSLQ implementation used took approximately 6.41 seconds, achieving a speedup of approximately 258x.