Polynomial Time Algorithms for Finding Integer Relations among Real Numbers (Q3033848)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4132272
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Polynomial Time Algorithms for Finding Integer Relations among Real Numbers |
scientific article; zbMATH DE number 4132272 |
Statements
Polynomial Time Algorithms for Finding Integer Relations among Real Numbers (English)
0 references
1989
0 references
continued fraction
0 references
approximation algorithms
0 references
computational number theory
0 references
integer relation
0 references
multidimensional Euclidean algorithm
0 references
0.89517695
0 references
0.8762958
0 references
0.8752972
0 references
0 references
0.86727405
0 references
0 references
0.8541666
0 references
0.8536535
0 references
Let \({\mathfrak x}=(x_ 1,...,x_ n)\in {\mathbb{R}}^ n\) be a real vector. An integer relation for \({\mathfrak x}\) is a nonzero vector \({\mathfrak m}=(m_ 1,...,m_ n)\in {\mathbb{Z}}^ n\), such that the inner product \(<{\mathfrak x},{\mathfrak m}>=\sum^{n}_{i=1}m_ ix_ i=0\). An algorithm is presented that computes small integer relations for real vectors, or proofs that no such relation exists. Let \(\lambda\) (x) be the smallest length of a nonzero integer relation for \({\mathfrak x}\in {\mathbb{R}}^ n\). The value \(\lambda\) (\({\mathfrak x})\) is set to \(\infty\) if no such relation exists. For input \({\mathfrak x}\in {\mathbb{R}}^ n\) and \(k\in {\mathbb{N}}\) it either finds an integer relation \(m\in {\mathbb{Z}}^ n\), with \(\| {\mathfrak m}\| \leq 2^{n-2}\lambda ({\mathfrak x})^ 2\), or it proves that \(\lambda\) (\({\mathfrak x})>2^ k\). The execution time of the algorithm is at most \(O(n^ 3(k+n))\) arithmetical operations on real numbers. The algorithm is similar to the Lenstra-Lenstra-Lovász algorithm to compute small vectors in a lattice. It is also similar to the multidimensional Euclidean algorithm of Ferguson and Forcade. Several variants of the algorithm are presented. For instance more than one independent integer relation may be computed, with a similar halting condition. Moreover simultaneous relations for a set of real vectors may be computed.
0 references