IntegerRelations - Maple Programming Help

Home : Support : Online Help : Mathematics : Numerical Computations : Approximations : IntegerRelations Package : IntegerRelations/PSLQ

IntegerRelations

 PSLQ
 find an integer dependence (relation)

 Calling Sequence PSLQ(v)

Parameters

 v - list or Vector of (complex) floating-point numbers

Description

 • Given a list (or a Vector) v of $n$ real numbers, the PSLQ(v) command outputs a list (or a Vector) u of $n$ integers such that $\sum _{i=1}^{n}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{u}_{i}{v}_{i}$ is minimized.  Thus the PSLQ function finds an integer relation between a vector of linearly dependent real numbers if the input has enough precision.
 • Given a list (or a Vector) v of $n$ complex numbers, the PSLQ(v) command outputs a list (or a vector) u of $n$ complex integers (Gaussian integers) such that the norm of $\sum _{i=1}^{n}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{u}_{i}{v}_{i}$ is minimized.
 • This is an implementation of Bailey and Ferguson's PSLQ algorithm. You can also use the Lenstra-Lenstra-Lovasz (LLL) lattice reduction algorithm to find a linear relation.  For more information, see IntegerRelations[LLL]. Generally speaking, PSLQ is faster.
 • One application of PSLQ is to find the minimal polynomial of an algebraic number given a decimal approximation of the algebraic number.  The examples below illustrate this.  Generally speaking, if the height of the minimal polynomial is $m$ and its degree is $n$, then you need more than $n{\mathrm{log}}_{10}\left(m\right)$ correct decimal digits for the algebraic number.  If the input has $d$ digits and this is insufficient, the output of PSLQ will typically be a list of $n$ integers each with approximately $d$/$n$ digits long.

Examples

 > $\mathrm{with}\left(\mathrm{IntegerRelations}\right):$
 > $v≔\left[1.570796326,1.414213562,-1.101048032\right]$
 ${v}{≔}\left[{1.570796326}{,}{1.414213562}{,}{-}{1.101048032}\right]$ (1)
 > $u≔\mathrm{PSLQ}\left(v\right)$
 ${u}{≔}\left[{-}{2}{,}{3}{,}{1}\right]$ (2)

Check that the following linear combination is small.

 > ${u}_{1}{v}_{1}+{u}_{2}{v}_{2}+{u}_{3}{v}_{3}$
 ${2.}{}{{10}}^{{-9}}$ (3)

Finding a integer relation between non-algebraic constants.

 > $\mathrm{Logs}≔\mathrm{Vector}\left(\left[\mathrm{log}\left(2\right),\mathrm{log}\left(3\right),\mathrm{log}\left(5\right),\mathrm{log}\left(6\right),\mathrm{log}\left(10\right)\right]\right)$
 ${\mathrm{Logs}}{≔}\left[\begin{array}{c}{\mathrm{ln}}{}\left({2}\right)\\ {\mathrm{ln}}{}\left({3}\right)\\ {\mathrm{ln}}{}\left({5}\right)\\ {\mathrm{ln}}{}\left({6}\right)\\ {\mathrm{ln}}{}\left({10}\right)\end{array}\right]$ (4)
 > $u≔\mathrm{PSLQ}\left(\mathrm{Logs}\right)$
 ${u}{≔}\left[\begin{array}{r}{1}\\ {0}\\ {1}\\ {0}\\ {-}{1}\end{array}\right]$ (5)
 > $\mathrm{Relation}≔\mathrm{add}\left({\mathrm{Logs}}_{i}{u}_{i},i=1..5\right)=0$
 ${\mathrm{Relation}}{≔}{\mathrm{ln}}{}\left({2}\right){+}{\mathrm{ln}}{}\left({5}\right){-}{\mathrm{ln}}{}\left({10}\right){=}{0}$ (6)

Using PSLQ to find the minimal polynomial for $\sqrt{2}+\sqrt{3}$.

 > $r≔\sqrt{2}+\sqrt{3}$
 ${r}{≔}\sqrt{{2}}{+}\sqrt{{3}}$ (7)
 > $v≔\mathrm{expand}\left(\left[\mathrm{seq}\left({r}^{i},i=0..4\right)\right]\right)$
 ${v}{≔}\left[{1}{,}\sqrt{{2}}{+}\sqrt{{3}}{,}{5}{+}{2}{}\sqrt{{2}}{}\sqrt{{3}}{,}{11}{}\sqrt{{2}}{+}{9}{}\sqrt{{3}}{,}{49}{+}{20}{}\sqrt{{2}}{}\sqrt{{3}}\right]$ (8)

Approximate with $12$ digits and round to $10$ digits.

 > $v≔\mathrm{evalf}\left(v,12\right)$
 ${v}{≔}\left[{1.}{,}{3.14626436994}{,}{9.89897948556}{,}{31.1448064542}{,}{97.9897948556}\right]$ (9)
 > $v≔\mathrm{evalf}\left(v\right)$
 ${v}{≔}\left[{1.}{,}{3.146264370}{,}{9.898979486}{,}{31.14480645}{,}{97.98979486}\right]$ (10)
 > $u≔\mathrm{PSLQ}\left(v\right)$
 ${u}{≔}\left[{1}{,}{0}{,}{-}{10}{,}{0}{,}{1}\right]$ (11)
 > $\mathrm{add}\left({u}_{i}{v}_{i},i=1..5\right)$
 ${0.}$ (12)

The minimal polynomial for $r$

 > $m≔\mathrm{add}\left({u}_{i}{z}^{i-1},i=1..5\right)$
 ${m}{≔}{{z}}^{{4}}{-}{10}{}{{z}}^{{2}}{+}{1}$ (13)

Check that $r$ is a root of $m\left(z\right)$

 > $\mathrm{simplify}\left(\genfrac{}{}{0}{}{m}{\phantom{z=r}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{m}}{z=r}\right)$
 ${0}$ (14)

The next example involves complex numbers. First define a tenth root of unity.

 > $r≔\mathrm{cos}\left(\frac{\mathrm{π}}{5}\right)+I\mathrm{sin}\left(\frac{\mathrm{π}}{5}\right)$
 ${r}{≔}{\mathrm{cos}}{}\left(\frac{{1}}{{5}}{}{\mathrm{π}}\right){+}{I}{}{\mathrm{sin}}{}\left(\frac{{1}}{{5}}{}{\mathrm{π}}\right)$ (15)
 > $a≔\mathrm{evalf}\left(r\right)$
 ${a}{≔}{0.8090169943}{+}{0.5877852524}{}{I}$ (16)
 > $v≔\left[1,a,{a}^{2},{a}^{3},{a}^{4}\right]:$
 > $u≔\mathrm{PSLQ}\left(v\right)$
 ${u}{≔}\left[{1}{,}{-}{1}{,}{1}{,}{-}{1}{,}{1}\right]$ (17)
 > $\mathrm{add}\left({u}_{i}{v}_{i},i=1..5\right)$
 ${-}{1.}{}{{10}}^{{-10}}{-}{3.}{}{{10}}^{{-10}}{}{I}$ (18)
 > $m≔\mathrm{add}\left({u}_{i+1}{z}^{i},i=0..4\right)$
 ${m}{≔}{{z}}^{{4}}{-}{{z}}^{{3}}{+}{{z}}^{{2}}{-}{z}{+}{1}$ (19)
 > $\mathrm{simplify}\left(\genfrac{}{}{0}{}{m}{\phantom{z=r}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{m}}{z=r}\right)$
 ${0}$ (20)

In the next example, a Gaussian integer relation is found. We subsequently find an integer relation from the Gaussian integer relation by eliminating I.

 > $r≔\sqrt{1+2I}$
 ${r}{≔}\sqrt{{1}{+}{2}{}{I}}$ (21)
 > $v≔\mathrm{evalf}\left(\left[1,r,{r}^{2}\right]\right)$
 ${v}{≔}\left[{1.}{,}{1.272019650}{+}{0.7861513778}{}{I}{,}{1.}{+}{2.}{}{I}\right]$ (22)
 > $u≔\mathrm{PSLQ}\left(v\right)$
 ${u}{≔}\left[{1}{+}{2}{}{I}{,}{0}{,}{-}{1}\right]$ (23)
 > $m≔{u}_{1}+{u}_{2}x+{u}_{3}{x}^{2}$
 ${m}{≔}{-}{{x}}^{{2}}{+}{1}{+}{2}{}{I}$ (24)
 > $\genfrac{}{}{0}{}{m}{\phantom{x=r}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{m}}{x=r}$
 ${0}$ (25)
 > $m≔\mathrm{subs}\left(I=z,m\right)$
 ${m}{≔}{-}{{x}}^{{2}}{+}{2}{}{z}{+}{1}$ (26)
 > $m≔\mathrm{resultant}\left(m,{z}^{2}+1,z\right)$
 ${m}{≔}{{x}}^{{4}}{-}{2}{}{{x}}^{{2}}{+}{5}$ (27)
 > $\genfrac{}{}{0}{}{m}{\phantom{x=r}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{m}}{x=r}$
 ${0}$ (28)

The last example is of much larger degree requiring more than the default $10$ digits of precision.  In the example, we are using PSLQ to test if the algebraic number $r$ is of degree $10$ or less.

 > $r≔1+{2}^{\frac{1}{3}}-{3}^{\frac{1}{3}}$
 ${r}{≔}{1}{+}{{2}}^{{1}{/}{3}}{-}{{3}}^{{1}{/}{3}}$ (29)
 > $\mathrm{Digits}≔50$
 ${\mathrm{Digits}}{≔}{50}$ (30)
 > $v≔\mathrm{Vector}\left(\left[\mathrm{seq}\left({r}^{i},i=0..10\right)\right]\right):$

Compute to $55$ digits and round to $50$ digits.

 > $v≔\mathrm{evalf}\left(v,55\right):$
 > $v≔\mathrm{evalf}\left(v\right)$
 ${v}{≔}\left[\begin{array}{c}{1.}\\ {0.81767147958746478244557229649811876217838221120216}\\ {0.66858664853075383639048354397191016622964216439499}\\ {0.54668423413656577641146431210930096937662127202181}\\ {0.44700810659358576105260725836989622226160789792505}\\ {0.36550577990596844124463402408070205786826727820194}\\ {0.29886365185348346975488348385448631176655996274722}\\ {0.24437228440595079023352327191229754014349264986649}\\ {0.19981624736038252994573312957596287544943722672979}\\ {0.16338404662477883755114718040485659711884715361349}\\ {0.13359447514467024355385019361427542093983423064155}\end{array}\right]$ (31)
 > $u≔\mathrm{PSLQ}\left(v\right)$
 ${u}{≔}\left[\begin{array}{r}{-}{162}\\ {324}\\ {0}\\ {-}{297}\\ {108}\\ {27}\\ {27}\\ {-}{45}\\ {27}\\ {-}{8}\\ {1}\end{array}\right]$ (32)
 > $\mathrm{add}\left({u}_{i}{v}_{i},i=1..11\right)$
 ${-}{1.75}{}{{10}}^{{-48}}$ (33)
 > $m≔\mathrm{add}\left({u}_{i}{z}^{i-1},i=1..11\right)$
 ${m}{≔}{{z}}^{{10}}{-}{8}{}{{z}}^{{9}}{+}{27}{}{{z}}^{{8}}{-}{45}{}{{z}}^{{7}}{+}{27}{}{{z}}^{{6}}{+}{27}{}{{z}}^{{5}}{+}{108}{}{{z}}^{{4}}{-}{297}{}{{z}}^{{3}}{+}{324}{}{z}{-}{162}$ (34)

Check.

 > $\mathrm{simplify}\left(\genfrac{}{}{0}{}{m}{\phantom{z=r}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}|\phantom{\rule[-0.0ex]{0.1em}{0.0ex}}\genfrac{}{}{0}{}{\phantom{m}}{z=r}\right)$
 ${0}$ (35)
 > $\mathrm{factor}\left(m\right)$
 $\left({z}{+}{1}\right){}\left({{z}}^{{9}}{-}{9}{}{{z}}^{{8}}{+}{36}{}{{z}}^{{7}}{-}{81}{}{{z}}^{{6}}{+}{108}{}{{z}}^{{5}}{-}{81}{}{{z}}^{{4}}{+}{189}{}{{z}}^{{3}}{-}{486}{}{{z}}^{{2}}{+}{486}{}{z}{-}{162}\right)$ (36)

Thus, the minimal polynomial for $r$ must be the degree 9 factor.

Here is what happens if we mistakenly assume that algebraic number $r$ is of degree $6$ or less. The output of PSLQ looks like random $7$ digit integers, which indicates that it has not found anything interesting.

 > $u≔\mathrm{PSLQ}\left({v}_{1..7}\right)$
 ${u}{≔}\left[\begin{array}{r}{6336266}\\ {-}{4491855}\\ {6130884}\\ {-}{12073116}\\ {3103150}\\ {-}{6012678}\\ {2169170}\end{array}\right]$ (37)
 > $\mathrm{add}\left({u}_{i}{v}_{i},i=1..7\right)$
 ${1.99}{}{{10}}^{{-42}}$ (38)