Analysis of PSLQ, an integer relation finding algorithm (Q4221985)

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 1229016
Language Label Description Also known as
default for all languages
No label defined
    English
    Analysis of PSLQ, an integer relation finding algorithm
    scientific article; zbMATH DE number 1229016

      Statements

      Analysis of PSLQ, an integer relation finding algorithm (English)
      0 references
      0 references
      0 references
      0 references
      3 December 1998
      0 references
      Euclidean algorithm
      0 references
      integer relation finding algorithm
      0 references
      Gaussian integer
      0 references
      Hamiltonian integer
      0 references
      polynomial time
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      Let \(\mathbb{K}\) be the real, complex or quaternion field and \(\mathbb{O}(\mathbb{K})\) the corresponding system of integers. A vector \(x\in\mathbb{K}^n\) is said to have an integer relation if there exist integers \(m_i\in\mathbb{O}(\mathbb{K})\), not all zero, such that \(m_{1}x_{1}+\dots+m_{n}x_{n}=0\). In recent years, several algorithms for finding such integer relations numerically have been developed. Application of such an algorithm to a vector \(x\) leads either to the construction of an integer relation for \(x\) or to a lower bound for the norm of any such relation. Only the second outcome constitutes a proof in a mathematical sense; an integer relation constructed by the algorithm could, with very low probability, be spurious and needs a separate proof. In this paper the authors define and investigate a class of such algorithms, the class PSLQ(\(\tau\)), where \(\tau\) is a parameter whose range depends on \(\mathbb{K}\). They prove the following (for \(\mathbb{K}=\mathbb{R}\) or \(\mathbb{C}\)). Assume that an integer relation for \(x\) exists and denote the smallest norm of all such relations by \(M_{x}\). Then PSLQ(\(\tau\)) constructs an integer relation in \(O(n^3+n^2\log M_{x})\) iterations, where the \(O\)-constant is given explicitly. The detected relation~\(m\) may have norm~\(| m| \) larger than \(M_{x}\), but not too much larger: the authors give an upper bound for \(| m| / M_{x}\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references