Integer Relations Among Algebraic Numbers
Bettina Just · Mathematics of Computation · 1990
A vector $m = ({m_1}, \ldots ,{m_n}) \in {{\mathbf {Z}}^n}\backslash \{ 0\}$ is called an integer relation for the real numbers ${\alpha _1}, \ldots ,{\alpha _n}$, if $\sum {\alpha _i}{m_i} = 0$ holds. We present an algorithm that, when given algebraic numbers ${\alpha _1}, \ldots ,{\alpha _n}$ and a parameter $\varepsilon$, either finds an integer relation for ${\alpha _1}, \ldots ,{\alpha _n}$ or proves that no relation of Euclidean length shorter than $1/\varepsilon$ exists. Each algebraic number is assumed to be given by its minimal polynomial and by a sufficiently precise rational approximation. Our algorithm uses the Lenstra-Lenstra-Lovász lattice basis reduction technique. It performs \[ {\operatorname {poly}}\left ( {\log 1/\varepsilon ,n,\log \max \limits _i {\text {height}}({\alpha _i}),[{\mathbf {Q}}({\alpha _1}, \ldots ,{\alpha _n}):{\mathbf {Q}}]} \right )\] bit operations. The straightforward algorithm that works with a primitive element of the field extension ${\mathbf {Q}}({\alpha _1}, \ldots ,{\alpha _n})$ of Q would take \[ {\operatorname {poly}}\left ( {n,\log \max \limits _i {\text {height}}({\alpha _i}),\prod \limits _{i = 1}^n {{\text {degree}}({\alpha _i})} } \right )\] bit operations. In order to prove the correctness of the algorithm, we show a lower bound for $\left | {\sum {\alpha _1}{m_i}} \right |$ if m is not an integer relation for ${\alpha _1}, \ldots ,{\alpha _n}$, which may be interesting in its own right.