## Polynomial time algorithms for finding integer reations among real numbers.(English)Zbl 0606.68033

Theoretical aspects of computer science, 3rd Annu. Symp., Orsay/France 1986, Lect. Notes Comput. Sci. 210, 105-118 (1986).
[For the entire collection see Zbl 0578.00004.]
We present algorithms, which when given a real vector $$x\in {\mathbb{R}}^ n$$ and a parameter $$k\in {\mathbb{N}}$$ as input either find an integer relation $$m\in {\mathbb{Z}}^ n$$, $$m\neq 0$$ with $$x^ Tm=0$$ or prove there is no such integer relation with $$\| m\| \leq 2^ k$$. One such algorithm halts after at most $$O(n^ 3(k+n))$$ arithmetic operations using real numbers. It finds an integer relation that is no more than $$2^{(n-2)/2}$$ times longer than the length of the shortest relation for x. Given a rational input $$x\in {\mathbb{Q}}^ n$$ this algorithm halts in polynomially many bit operations. The basic algorithm of this kind is due to H. R. P. Ferguson and R. W. Forcade [Bull. Am. Math. Soc., New Ser. 1, 912- 914 (1979; Zbl 0424.10021)] and is closely related to the Lovász lattice basis reduction algorithm [A. K. Lenstra, H. W.Lenstra, and L. Lovász, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)].

### MSC:

 68Q25 Analysis of algorithms and problem complexity 11-04 Software, source code, etc. for problems pertaining to number theory 11H06 Lattices and convex bodies (number-theoretic aspects) 68W30 Symbolic computation and algebraic computation

### Citations:

Zbl 0578.00004; Zbl 0424.10021; Zbl 0488.12001