Analysis of PSLQ, an integer relation finding algorithm

Source abstract

Let K {\mathbb {K}} be either the real, complex, or quaternion number system and let O ( K ) {\mathbb {O}}({\mathbb {K}}) be the corresponding integers. Let x = ( x 1 , … , x n ) x = (x_{1}, \dots , x_{n}) be a vector in K n {\mathbb {K}}^{n} . The vector x x has an integer relation if there exists a vector m = ( m 1 , … , m n ) ∈ O ( K ) n m = (m_{1}, \dots , m_{n}) \in {\mathbb {O}}({\mathbb {K}})^{n} , m ≠ 0 m \ne 0 , such that m 1 x 1 + m 2 x 2 + … + m n x n = 0 m_{1} x_{1} + m_{2} x_{2} + \ldots + m_{n} x_{n} = 0 . In this paper we define the parameterized integer relation construction algorithm PSLQ ( τ ) (\tau ) , where the parameter τ \tau can be freely chosen in a certain interval. Beginning with an arbitrary vector x = ( x 1 , … , x n ) ∈ K n x = (x_{1}, \dots , x_{n}) \in {\mathbb {K}}^{n} , iterations of PSLQ ( τ ) (\tau ) will produce lower bounds on the norm of any possible relation for x x . Thus PSLQ ( τ ) (\tau ) can be used to prove that there are no relations for x x of norm less than a given size. Let M x M_{x} be the smallest norm of any relation for x x . For the real and complex case and each fixed parameter τ \tau in a certain interval, we prove that PSLQ ( τ ) (\tau ) constructs a relation in less than O ( n 3 + n 2 log ⁡ M x ) O(n^{3} + n^{2} \log M_{x}) iterations.