[seqfan] Re: A158415

[Reed Kelly]

Hi Vladimir,

Please excuse me if this is too basic. There is a chance that you have
already thought this through and dismissed it as not useful. If I say
something inaccurate, please let me know.

I think that one can choose a value for the calculated difference between
two candidates. The problem is that the bound may be too small to be
practical.

To see that a bound is possible, consider the following.

All the numbers being considered are algebraic numbers having a
corresponding polynomial with integer coefficients for which they are a
solution. For example, sqrt(1+1+sqrt(1+sqrt(1+1))) is the solution of

  ((x^2-2)^2-1)^2-2 == 0

Let d be the difference between two such numbers. Clearly, d is also
algebraic, so it is also the solution of a polynomial with integer
coefficients. If we knew that the sum of the absolute values of the
coefficients was at most A, and that the constant term had an absolute value
of 'a', then the difference would either be 0, or it's absolute value would
be greater than a/A. As long as a/A > eps, then an approach like the PARI
listing should work.

In order to provide an upper bound on A (and therefore a lower bound on
eps), we need to keep track of the degrees and coefficient sums of each step
in the construction of the numbers.

Taking a square root doubles the degree, but it does not change the sum of
the absolute value of the coefficients.

Adding 1 only increases the sum by 1.

Adding two algebraic numbers is the tricky part. If the two numbers are 'a'
and 'b' with degrees 'm' and 'n' and sums of absolute values of coefficients
A and B, then the degree of a+b is at most m*n and a very crude upper bound
can theoretically be found for the sum of the abs val of the coeff of a+b
minimal integer polynomial coefficients.

If you actually had the two polynomials that 'a' and 'b' were roots of, then
you could derive m*n potentially independent equations for terms
representing a^i*b^j. Each of the intermediate equations would have
coefficients having a sum of abs vals <= A^i*B^j. Solving the system of
equations for a+b would result in a new equation with coefficients having a
sum of abs vals < a-huge-number. Using Gaussian elimination to solve the
system of m*n equations should introduce at most an additional factor of
(A^m*B^n)^(m*n*(m*n+1)/2). I think this puts the upper bound somewhere
around:
	(A^m*B^n)^(1+m*n*(m*n+1)/2)

Unless I am totally off base, someone may be able to improve the estimate. I
hope that this helps in determining whether eps can be computed. 

For smaller terms, the degree and sum of absolute values of the coefficients
of the corresponding minimal integer polynomial can be computed directly in
Mathematica with help from the function: RootReduce[]. For example,
RootReduce[Sqrt[2]+Sqrt[3]] returns:
Root[1 - 10 #1^2 + #1^4 &, 4]. This is degree 4 and has a sum of 12.

Reed


> -----Original Message-----
> From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu]
> On Behalf Of Vladimir Reshetnikov
> Sent: Sunday, March 22, 2009 9:55 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: A158415
> 
> On Sun, Mar 22, 2009 at 1:00 PM, Robert Gerbicz
> <robert.gerbicz at gmail.com>wrote:
> 
> > 2009/3/22 Vladimir Reshetnikov <v.reshetnikov at gmail.com>
> >
> > > Dear all,
> > >
> > > Can anybody suggest an algorithm for calculating the terms of A158415?
> > >
> > > Thanks
> > > Vladimir
> > >
> > > _______________________________________________
> > >
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > Hi!
> >
> > There are two possibilities for N symbols: u=sqrt(x) where x is using N-
> 1
> > symbols, or u=x+y where x is using 1<=j<N and y is using 1<=N-1-j<N
> > symbols.
> > Extension of the sequence (I've already submitted):
> > 1,1,2,3,5,8,13,20,33,54,91,154,264,455,791,1379,2424,4277,7588,13513,
> > 24162,43336,77978,140683,254487,461409,838433,1526536
> >
> > A quick PARI-Gp code for it:
> > allocatemem(2*10^8);\
> > a=L=vector(28);eps=10^(-20);a[1]=[1];L[1]=1;print1(1",");\
> > for(i=2,28,b=vector(L[i-1]+sum(j=1,(i-1)\2,L[j]*L[i-j-1]));\
> > up=0;for(j=1,L[i-1],up++;b[up]=sqrt(a[i-1][j]));\
> > for(j=1,(i-1)\2,for(k=1,L[j],for(l=1,L[i-1-j],\
> > up++;b[up]=a[j][k]+a[i-1-j][l])));\
> > c=vector(up,j,b[j]);c=vecsort(c);s=0;\
> > for(j=1,up,if((j==1)||(c[j]>c[j-1]+eps),s++));\
> > a[i]=vector(s);s=0;\
> > for(j=1,up,if((j==1)||(c[j]>c[j-1]+eps),s++;a[i][s]=c[j]));\
> > L[i]=s;print1(L[i]","))
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
> 
> How did you prove that eps=10^(-20) is sufficient? In my view, the main
> problem here is how to rigorously determine equality of two expressions.
> 
> Thanks
> Vladimir
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/