Integer relation algorithm

Integer relation algorithm

An integer relation between a set of real numbers "x"1, "x"2, ..., "x""n" is a set of integers "a"1, "a"2, ..., "a"n, not all 0, such that

:a_1x_1 + a_2x_2 + cdots + a_nx_n = 0.,

An integer relation algorithm is an algorithm for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain upper bound. [Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.]

History

For the case "n" = 2, an extension of the Euclidean algorithm can determine whether there is an integer relation between any two real numbers "x"1 and "x"2. The algorithm generates successive terms of the continued fraction expansion of "x"1/"x"2; if there is an integer relation between the numbers then their ratio is rational and the algorithm eventually terminates.

The first general algorithm that was proved to work for all values of "n" was the Ferguson-Forcade algorithm, published in 1979 by Helaman Ferguson and R.W. Forcade. [MathWorld|urlname=IntegerRelation|title=Integer Relation] Subsequent developments, focussing on improving both efficiency and numerical stability, produced the following algorithms:

*The LLL algorithm, developed by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. [MathWorld|urlname=LLLAlgorithm|title=LLL Algorithm]
*The PSOS algorithm, developed by Ferguson in 1988. [MathWorld|urlname=PSOSAlgorithm|title=PSOS Algorithm]
*The HJLS algorithm, developed by Ferguson and David Bailey in 1992. [MathWorld|urlname=HJLSAlgorithm|title=HJLS Algorithm]
*The PSLQ algorithm, also developed by Ferguson and Bailey in 1992 and substantially simplified by Ferguson, Bailey, and Arno in 1999. [MathWorld|urlname=PSLQAlgorithm|title=PSLQ Algorithm] [ [http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf "A Polynomial Time, Numerically Stable Integer Relation Algorithm"] by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992]

In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by Jack Dongarra and Francis Sullivan. [ [http://amath.colorado.edu/resources/archive/topten.pdf "The Best of the 20th Century: Editors Name Top 10 Algorithms"] by Barry A. Cipra; SIAM News, Volume 33, Number 4]

Applications

Integer relation algorithms have two main applications. The first application is to determine whether a given real number "x" is likely to be algebraic, by searching for an integer relation between a set of powers of "x" {1, "x", "x"2, ..., "x""n"}. The second application is to search for an integer relation between a real number "x" and a set of mathematical constants such as "e", π and ln(2), which will lead to an expression for "x" as a linear combination of these constants.

A typical approach in experimental mathematics is to use numerical methods and arbitrary precision arithmetic to find an approximate value for an infinite series, infinite product or an integral to a high degree of precision (usually at least 100 significant figures), and then use an integer relation algorithm to search for an integer relation between this value and a set of mathematical constants. If an integer relation is found, this suggests a possible closed-form expression for the original series, product or integral. This conjecture can then be validated by formal algebraic methods. The higher the precision to which the inputs to the algorithm are known, the greater the level of confidence that any integer relation that is found is not just a numerical artifact.

A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the Bailey-Borwein-Plouffe formula for the value of π.

Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the Inverse Symbolic Calculator or Plouffe's Inverter.

References

External links

* [http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html "Recognizing Numerical Constants"] by David H. Bailey and Simon Plouffe
* [http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf "Ten Problems in Experimental Mathematics"] by David H. Bailey, Jonathan M. Borwein, Vishaal Kapoor, and Eric W. Weisstein


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… …   Wikipedia

  • Cornacchia's algorithm — In computational number theory, Cornacchia s algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1]. Contents 1 The algorithm …   Wikipedia

  • Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Integer — This article is about the mathematical concept. For integers in computer science, see Integer (computer science). Symbol often used to denote the set of integers The integers (from the Latin integer, literally untouched , hence whole : the word… …   Wikipedia

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

  • Division algorithm — This article is about a mathematical theorem. For a list of division algorithms, see Division (digital). In mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be… …   Wikipedia

  • Index calculus algorithm — In group theory, the index calculus algorithm is an algorithm for computing discrete logarithms. This is the best known algorithm for certain groups, such as mathbb{Z} m^* (the multiplicative group modulo m ).Dubious|date=April 2008 Description… …   Wikipedia

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”