An integer relation between a set of real numbers x1, x2, ..., xn is a set of integers a1, a2, ..., an, not all 0, such that
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. [1]
For the case n = 2, an extension of the Euclidean algorithm can find any integer relation that exists between any two real numbers x1 and x2. The algorithm generates successive terms of the continued fraction expansion of x1/x2; if there is an integer relation between the numbers, then their ratio is rational and the algorithm eventually terminates.
Integer relation algorithms have numerous 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, x2, ..., xn}. 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 π. PSLQ has also helped find new identities involving multiple zeta functions and their appearance in quantum field theory; and in identifying bifurcation points of the logistic map. For example, where B4 is the logistic map's fourth bifurcation point, the constant α = −B4(B4 − 2) is a root of a 120th-degree polynomial whose largest coefficient is 25730. [12] [13] 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.
Integer relation finding can be used to factor polynomials of high degree. [14]
In mathematics, a polynomial is an expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1.
In algebra, a quadratic equation is any equation that can be rearranged in standard form as
In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are π and e.
In mathematics, a Diophantine equation is an equation of the form P(x1, ..., xj, y1, ..., yk) = 0 (usually abbreviated P(x, y) = 0) where P(x, y) is a polynomial with integer coefficients, where x1, ..., xj indicate parameters and y1, ..., yk indicate unknowns.
David Harold Bailey is a mathematician and computer scientist. He received his B.S. in mathematics from Brigham Young University in 1972 and his Ph.D. in mathematics from Stanford University in 1976. He worked for 14 years as a computer scientist at NASA Ames Research Center, and then from 1998 to 2013 as a Senior Scientist at the Lawrence Berkeley National Laboratory. He is now retired from the Berkeley Lab.
In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial x2 − 2 is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as if it is considered as a polynomial with real coefficients. One says that the polynomial x2 − 2 is irreducible over the integers but not over the reals.
Experimental mathematics is an approach to mathematics in which computation is used to investigate mathematical objects and identify properties and patterns. It has been defined as "that branch of mathematics that concerns itself ultimately with the codification and transmission of insights within the mathematical community through the use of experimental exploration of conjectures and more informal beliefs and a careful analysis of the data acquired in this pursuit."
In mathematics, a Pisot–Vijayaraghavan number, also called simply a Pisot number or a PV number, is a real algebraic integer greater than 1, all of whose Galois conjugates are less than 1 in absolute value. These numbers were discovered by Axel Thue in 1912 and rediscovered by G. H. Hardy in 1919 within the context of diophantine approximation. They became widely known after the publication of Charles Pisot's dissertation in 1938. They also occur in the uniqueness problem for Fourier series. Tirukkannapuram Vijayaraghavan and Raphael Salem continued their study in the 1940s. Salem numbers are a closely related set of numbers.
In mathematics, the Sturm sequence of a univariate polynomial p is a sequence of polynomials associated with p and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of p located in an interval in terms of the number of changes of signs of the values of the Sturm sequence at the bounds of the interval. Applied to the interval of all the real numbers, it gives the total number of real roots of p.
Peter Benjamin Borwein was a Canadian mathematician and a professor at Simon Fraser University. He is known as a co-author of the paper which presented the Bailey–Borwein–Plouffe algorithm for computing π.
Symmetry occurs not only in geometry, but also in other branches of mathematics. Symmetry is a type of invariance: the property that a mathematical object remains unchanged under a set of operations or transformations.
In mathematics, a variable is a symbol that represents a mathematical object. A variable may represent a number, a vector, a matrix, a function, the argument of a function, a set, or an element of a set.
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.
In mathematics, an algebraic expression is an expression built up from constant algebraic numbers, variables, and the algebraic operations. For example, 3x2 − 2xy + c is an algebraic expression. Since taking the square root is the same as raising to the power 1/2, the following is also an algebraic expression:
In mathematics, Neville's algorithm is an algorithm used for polynomial interpolation that was derived by the mathematician Eric Harold Neville in 1934. Given n + 1 points, there is a unique polynomial of degree ≤ n which goes through the given points. Neville's algorithm evaluates this polynomial.
Helaman Rolfe Pratt Ferguson is an American sculptor and a digital artist, specifically an algorist. He is also well known for his development of the PSLQ algorithm, an integer relation detection algorithm.
In algebraic geometry, a period is a number that can be expressed as an integral of an algebraic function over an algebraic domain. Sums and products of periods remain periods, so the periods form a ring.
The Bailey–Borwein–Plouffe formula is a formula for π. It was discovered in 1995 by Simon Plouffe and is named after the authors of the article in which it was published, David H. Bailey, Peter Borwein, and Plouffe. Before that, it had been published by Plouffe on his own site. The formula is
A system of polynomial equations is a set of simultaneous equations f1 = 0, ..., fh = 0 where the fi are polynomials in several variables, say x1, ..., xn, over some field k.
A mathematical constant is a key number whose value is fixed by an unambiguous definition, often referred to by a special symbol, or by mathematicians' names to facilitate using it across multiple mathematical problems. Constants arise in many areas of mathematics, with constants such as e and π occurring in such diverse contexts as geometry, number theory, statistics, and calculus.
