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
      0 references
      0 references
      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references