Overview of the IntegerRelations Package - Maple Programming Help

Home : Support : Online Help : Mathematics : Packages : IntegerRelations

Overview of the IntegerRelations Package

 Calling Sequence IntegerRelations[command](arguments) command(arguments)

Description

 • The IntegerRelations package contains two routines, LLL, and PSLQ, which are used to solve specific computational problems. LLL is the Lenstra, Lenstra, Lovasz lattice basis reduction. PSLQ is Bailey and Ferguson's partial sum of least squares algorithm. The LinearDependency routine is a user-level routine for applying PSLQ or LLL to solve the integer relation problem, defined as follows.
 Given decimal approximations for $n$ real or complex numbers ${x}_{1},{x}_{2},...,{x}_{n}$, find an integer relation between them, that is, find integers ${u}_{1},{u}_{2},...,{u}_{n}$ such that ${u}_{1}{x}_{1}+{u}_{2}{x}_{2}+\mathrm{...}+{u}_{n}{x}_{n}$ is small, if such ${u}_{i}$ exist.
 • Each command in the IntegerRelations package can be accessed by using either the long form or the short form of the command name in the command calling sequence.
 As the underlying implementation of the IntegerRelations package is a module, it is also possible to use the form IntegerRelations:-command to access a command from the package. For more information,  see Module Members.

List of IntegerRelations Package Commands

 The following is a list of available commands.

 To display the help page for a particular IntegerRelations command, see Getting Help with a Command in a Package.

Examples

The identify Command  and the IntegerRelations Package

The identify command uses the LLL and PSLQ routines to identify exact constants from decimal numbers, for example, given $x=4.555806216,\mathrm{identify}\left(x\right)$ outputs $\mathrm{\pi }+\sqrt{2}$

The process is described as follows. Consider $x=2.414213562$. The identify command first tests if $x$ is close to a small rational constant. Next identify tests if $x$ is close to an algebraic number. To do this, identify first tests if $x$ is a root of a quadratic polynomial.  It computes $\mathrm{PSLQ}\left(\left[1,x,{x}^{2}\right]\right)$.  PSLQ outputs $\left[-1,-2,1\right]$ an integer relation with small integer coefficients satisfying ${x}^{2}-2x-1=\frac{1}{1000000000}$, which is small.  From this relation you have the minimal polynomial for $x$, namely ${x}^{2}-2x-1$. The identify command then solves for $x$ to obtain $x=1+-\sqrt{2}$ from which it determines that $x=1+\sqrt{2}$. The algorithms in the identify routine can find other relations, for example:

 > $\mathrm{with}\left(\mathrm{IntegerRelations}\right)$
 $\left[{\mathrm{LLL}}{,}{\mathrm{LinearDependency}}{,}{\mathrm{PSLQ}}\right]$ (1)
 > $\mathrm{Digits}≔20$
 ${\mathrm{Digits}}{≔}{20}$ (2)
 > $x≔0.31783724519578224473$
 ${x}{≔}{0.31783724519578224473}$ (3)
 > $\mathrm{PSLQ}\left(\left[1,x,{x}^{2},{x}^{3},{x}^{4}\right]\right)$
 $\left[{1}{,}{0}{,}{-10}{,}{0}{,}{1}\right]$ (4)
 > $\mathrm{solve}\left({y}^{4}-10{y}^{2}+1,y\right)$
 $\sqrt{{3}}{-}\sqrt{{2}}{,}{-}\sqrt{{3}}{+}\sqrt{{2}}{,}\sqrt{{3}}{+}\sqrt{{2}}{,}{-}\sqrt{{3}}{-}\sqrt{{2}}$ (5)
 > $\mathrm{identify}\left(x\right)$
 $\sqrt{{3}}{-}\sqrt{{2}}$ (6)