11-29-2017, 08:12 PM

PSLQ (Partial Sums LQ Decomposition) can be used to determine if there exists a set of integer coefficients \( \mathbf{a} = (a_1, a_2, \dotsm, a_n) \) for a given vector \( \mathbf{x} = (x_1, x_2, \dotsm, x_n) \) such that their dot product is 0 (i.e. \( \sum a_i x_i = 0 \) ).

Please note that this is beta; I have not implemented a full set of exit conditions!

This can be used to solve a number of interesting "algebraic form" problems. For example, the number 3.96811878507 is the decimal approximation of \( x=\sqrt{3} + \sqrt{5} \). The value \( x \) is a root of the polynomial \( x^4 - 16x^2 + 4 \). Moreover, numbers of the form \( \sqrt{a} + \sqrt{b} \) are roots of \( x^4 - 2(a+b)x^2 + (a-b)^2 \). We can use PSLQ on the vector \( ( x^4, x^3, x^2, x, 1 ) \) to obtain the result: \( ( 1, 0, -16, 0, 4 ) \). Additionally solving \( -2(a+b) = -16 \) and \( (a-b)^2=4 \) simultaneously results in the values a=3 and b=5.

Another example may be to rewrite \( x \approx 7.09439510239 \) in the preferred form \( 2\pi/3 + 5 \). Notice that \( x \) satisfies: \( 0 = 2\pi -3x + 15 \). So if we apply PLSQ to the vector \( (\pi, 7.09439510239, 1 ) \) we get the vector \( (2,-3,15) \)

Also, if we have a number of the form \( x= r_1 + \sqrt{r_2} \) where the \( r_i \)'s are rational numbers, then simply apply PSLQ to \( ( x^2, x, 1) \) since such numbers are roots of some quadratic polynomial. The result from PSLQ -- \( ( a,b,c ) \) -- are the coefficient of the quadratic polynomial, and can then be used to rewrite \( x\) into a nice algebraic form using \( x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} \)

Please note that this is beta; I have not implemented a full set of exit conditions!

Code:

`NINT(x)`

BEGIN

local n:=IP(x);

if x > n+.5 then return(n+1); end;

if x < n-.5 then return(n-1); end;

return(n);

END;

EXPORT PSLQ(lst)

BEGIN

local MA,MB,MH;

local j,k,n,m,r;

local s:={}, y:={};

local t;

local g:=2/sqrt(3);

local M1,M2;

local t0,t1,t2,t3,t4;

local run:=0;

n:=size(lst);

MA:=idenmat(n);

MB:=MA;

MH:=MA;

MH:=delcol(MH,n);

for k from 1 to n do

s(k):=sqrt(sum(lst(j)^2,j,k,n));

end;

t:=1/s(1);

//for k from 1 to n do

// y(k):=t*lst(k);

// s(k):=t*s(k);

//end;

y:=t*lst;

s:=t*s;

for j from 1 to n-1 do

MH(j,j):=s(j+1)/s(j);

for k from j+1 to n do

MH(k,j):=-y(k)*y(j)/(s(j)*s(j+1));

end;

end;

for k from 2 to n do

for j from k-1 downto 1 do

t:=NINT(MH(k,j)/MH(j,j));

y(j):=y(j)+t*y(k);

for m from 1 to j do

MH(k,m):=MH(k,m)-t*MH(j,m);

end;

for m from 1 to n do

MA(k,m):=MA(k,m)-t*MA(j,m);

MB(m,j):=MB(m,j)+t*MB(m,k);

end;

end;

end;

// iterate

repeat

m:=1; M1:=g*abs(MH(1,1));

for k from 2 to n-1 do

M2:=g^k*abs(MH(k,k));

if M2>M1 then

m:=k; M1:=M2;

end;

end;

M2:=y(m);

y(m):=y(m+1);

y(m+1):=M2;

MH:=swaprow(MH,m,m+1);

MA:=swaprow(MA,m,m+1);

MB:=swapcol(MB,m,m+1);

if m<=n-2 then

t0:=sqrt(MH(m,m)^2+MH(m,m+1)^2);

t1:=MH(m,m)/t0;

t2:=MH(m,m+1)/t0;

for j from m to n do

t3:=MH(j,m);

t4:=MH(j,m+1);

MH(j,m):=t1*t3+t2*t4;

MH(j,m+1):=-t2*t3+t1*t4;

end;

end;

for k from m+1 to n do

for j from min(k-1,m+1) downto 1 do

t:=NINT(MH(k,j)/MH(j,j));

y(j):=y(j)+t*y(k);

for r from 1 to j do

MH(k,r):=MH(k,r)-t*MH(j,r);

end;

for r from 1 to n do

MA(k,r):=MA(k,r)-t*MA(j,r);

MB(r,j):=MB(r,j)+t*MB(r,k);

end;

end;

end;

m:=1; M1:=abs(y(1));

for j from 2 to n do

M2:=abs(y(j));

if M2<M1 then M1:=M2; m:=j; end;

end;

run:=(M1<1E-10);

until run end;

return(col(MB,m));

END;

This can be used to solve a number of interesting "algebraic form" problems. For example, the number 3.96811878507 is the decimal approximation of \( x=\sqrt{3} + \sqrt{5} \). The value \( x \) is a root of the polynomial \( x^4 - 16x^2 + 4 \). Moreover, numbers of the form \( \sqrt{a} + \sqrt{b} \) are roots of \( x^4 - 2(a+b)x^2 + (a-b)^2 \). We can use PSLQ on the vector \( ( x^4, x^3, x^2, x, 1 ) \) to obtain the result: \( ( 1, 0, -16, 0, 4 ) \). Additionally solving \( -2(a+b) = -16 \) and \( (a-b)^2=4 \) simultaneously results in the values a=3 and b=5.

Code:

X:=SQRT(3)+SQRT(5);

PSLQ({X^4,X^3,X^2,X,1); // returns {1,0,-16,0,4}

Another example may be to rewrite \( x \approx 7.09439510239 \) in the preferred form \( 2\pi/3 + 5 \). Notice that \( x \) satisfies: \( 0 = 2\pi -3x + 15 \). So if we apply PLSQ to the vector \( (\pi, 7.09439510239, 1 ) \) we get the vector \( (2,-3,15) \)

Code:

X:=2*PI/3+5;

PSLQ({PI,X,1}); // returns {2,-3,15}

Also, if we have a number of the form \( x= r_1 + \sqrt{r_2} \) where the \( r_i \)'s are rational numbers, then simply apply PSLQ to \( ( x^2, x, 1) \) since such numbers are roots of some quadratic polynomial. The result from PSLQ -- \( ( a,b,c ) \) -- are the coefficient of the quadratic polynomial, and can then be used to rewrite \( x\) into a nice algebraic form using \( x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} \)

Code:

X:=2/3+4*SQRT(3);

PSLQ({X^2,X,1}); // returns {9,-12,-428}