Analysis of PSLQ, an integer relation finding algorithm

Abstract:

Let ${\mathbb {K}}$ be either the real, complex, or quaternion number system and let ${\mathbb {O}}({\mathbb {K}})$ be the corresponding integers. Let $x = (x_{1}, \dots , x_{n})$ be a vector in ${\mathbb {K}}^{n}$. The vector $x$ has an integer relation if there exists a vector $m = (m_{1}, \dots , m_{n}) \in {\mathbb {O}}({\mathbb {K}})^{n}$, $m \ne 0$, such that $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}, \dots , x_{n}) \in {\mathbb {K}}^{n}$, iterations of PSLQ$(\tau )$ will produce lower bounds on the norm of any possible relation for $x$. Thus PSLQ$(\tau )$ can be used to prove that there are no relations for $x$ of norm less than a given size. Let $M_{x}$ be the smallest norm of any relation for $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})$ iterations.