find an integer dependence (relation) - Maple Help

Online Help

All Products    Maple    MapleSim


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 i=1nuivi 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 i=1nuivi 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 nlog10m 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

withIntegerRelations:

v:=1.570796326,1.414213562,1.101048032

v:=1.570796326,1.414213562,1.101048032

(1)

u:=PSLQv

u:=2,3,1

(2)

Check that the following linear combination is small.

u1v1+u2v2+u3v3

2.10-9

(3)

Finding a integer relation between non-algebraic constants.

Logs:=Vectorlog2,log3,log5,log6,log10

Logs:=ln2ln3ln5ln6ln10

(4)

u:=PSLQLogs

u:=10101

(5)

Relation:=addLogsiui,i=1..5=0

Relation:=ln2+ln5ln10=0

(6)

Using PSLQ to find the minimal polynomial for 2+3.

r:=2+3

r:=2+3

(7)

v:=expandseqri,i=0..4

v:=1,2+3,5+223,112+93,49+2023

(8)

Approximate with 12 digits and round to 10 digits.

v:=evalfv,12

v:=1.,3.14626436994,9.89897948556,31.1448064542,97.9897948556

(9)

v:=evalfv

v:=1.,3.146264370,9.898979486,31.14480645,97.98979486

(10)

u:=PSLQv

u:=1,0,10,0,1

(11)

adduivi,i=1..5

0.

(12)

The minimal polynomial for r

m:=adduizi1,i=1..5

m:=z410z2+1

(13)

Check that r is a root of mz

simplifymz=r|mz=r

0

(14)

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

r:=cosπ5+Isinπ5

r:=cos15π+Isin15π

(15)

a:=evalfr

a:=0.8090169943+0.5877852524I

(16)

v:=1,a,a2,a3,a4:

u:=PSLQv

u:=1,1,1,1,1

(17)

adduivi,i=1..5

1.10-103.10-10I

(18)

m:=addui+1zi,i=0..4

m:=z4z3+z2z+1

(19)

simplifymz=r|mz=r

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:=1+2I

r:=1+2I

(21)

v:=evalf1,r,r2

v:=1.,1.272019650+0.7861513778I,1.+2.I

(22)

u:=PSLQv

u:=1+2I,0,1

(23)

m:=u1+u2x+u3x2

m:=x2+1+2I

(24)

mx=r|mx=r

0

(25)

m:=subsI=z,m

m:=x2+2z+1

(26)

m:=resultantm,z2+1,z

m:=x42x2+5

(27)

mx=r|mx=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+213313

r:=1+21/331/3

(29)

Digits:=50

Digits:=50

(30)

v:=Vectorseqri,i=0..10:

Compute to 55 digits and round to 50 digits.

v:=evalfv,55:

v:=evalfv

v:=1.0.817671479587464782445572296498118762178382211202160.668586648530753836390483543971910166229642164394990.546684234136565776411464312109300969376621272021810.447008106593585761052607258369896222261607897925050.365505779905968441244634024080702057868267278201940.298863651853483469754883483854486311766559962747220.244372284405950790233523271912297540143492649866490.199816247360382529945733129575962875449437226729790.163384046624778837551147180404856597118847153613490.13359447514467024355385019361427542093983423064155

(31)

u:=PSLQv

u:=16232402971082727452781

(32)

adduivi,i=1..11

1.7510-48

(33)

m:=adduizi1,i=1..11

m:=z108z9+27z845z7+27z6+27z5+108z4297z3+324z162

(34)

Check.

simplifymz=r|mz=r

0

(35)

factorm

z+1z99z8+36z781z6+108z581z4+189z3486z2+486z162

(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:=PSLQv1..7

u:=63362664491855613088412073116310315060126782169170

(37)

adduivi,i=1..7

1.9910-42

(38)

See Also

identify, IntegerRelations, IntegerRelations[LinearDependency], IntegerRelations[LLL]


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam