PSLQ - Maple Help

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}{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}{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.
 • The internal working precision of the PSLQ command corresponds to the value of Digits. For best results, the same value of Digits should be used with which the input approximation was obtained.

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}{c}{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{Pi}}{5}\right)+I\mathrm{sin}\left(\frac{\mathrm{Pi}}{5}\right)$
 ${r}{≔}{\mathrm{cos}}{}\left(\frac{{\mathrm{\pi }}}{{5}}\right){+}{I}{}{\mathrm{sin}}{}\left(\frac{{\mathrm{\pi }}}{{5}}\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)
 > $\mathrm{interface}\left(\mathrm{rtablesize}=11\right):$
 > $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}{c}{-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}{c}{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)