Analysis of PSLQ, An Integer Relation Finding Algorithm

Abstract. Let K be either the real, complex, or quaternion number system and let O(K) be the corresponding integers. Let x =(x1,...,xn) be a vector in K n. The vector x has an integer relation if there exists a vector m = (m1,...,mn) ∈ O(K) n, m � = 0, such that m1x1 + m2x2 +...+ mnxn =0. In this paper we define the parameterized integer relation construction algorithm PSLQ(τ), where the parameter τ can be freely chosen in a certain interval. Beginning with an arbitrary vector x =(x1,...,xn) ∈ K n, iterations of PSLQ(τ) will produce lower bounds on the norm of any possible relation for x. Thus PSLQ(τ) can be used to prove that there are no relations for x of norm less than a given size. Let Mx be the smallest norm of any relation for x. For the real and complex case and each fixed parameter τ in a certain interval, we prove that PSLQ(τ) constructs a relation in less than O(n 3 + n 2 log Mx) iterations. Ref: Mathematics of Computation, to appear (1999) Key words and phrases. Euclidean algorithm, integer relation finding algorithm, gaussian integer, hamiltonian integer, polynomial time.