Analysis of PSLQ, an integer relation finding algorithm

Let K be either the real, complex, or quaternion number system and let O(K) be the corresponding integers. Let x = (x(1),..., x(n)) be a vector in K-n . The vector x has an integer relation if there exists a vector m = (m(1),. .., m(n)) is an element of O(K)(n), m not equal 0, such that m(1)x(1) + m(2 )x(2) + ... + m(n)x(n) = 0. In this paper we define the parameterized integ er relation construction algorithm PSLQ(tau), where the parameter tau can b e freely chosen in a certain interval. Beginning with an arbitrary vector x = (x(1),..., x(n)) is an element of K- n, iterations of PSLQ(tau) will produce lower bounds on the norm of any pos sible relation for x. Thus PSLQ(tau) can be used to prove that there are no relations for a of norm less than a given size. Let M-x be the smallest no rm of any relation for a. For the real and complex case and each fixed para meter tau in a certain interval, we prove that PSLQ( tau) constructs a rela tion in less than O(n(3) + n(2) log M-x) iterations.