[seqfan] Re: [math-fun] Mathematical hell, sequence and the sequence A007699

[David Wilson]

You probably know that if sequence a obeys linear recurrence

     [1] SUM(k = 0..d; c_k*a(k)) = 0

Then the limit ratio r of a satisfies

     [2] SUM(k = 0..d; c_k*r^k) = 0

(certain restrictions apply, but works most of the time).

For example, the Fibonacci sequence obeys the linear recurrence

     F(n) + F(n+1) - F(n+2) = 0

So its limit ratio r obeys

     1 + r - r^2 = 0

of which one root is the golden ratio r = (sqrt(5)+1)/2 = 1.618...

Pisot sequences were presumably invented as integer approximations to 
geometric sequences.
True geometric sequences have constant ratio of adjacent terms:

     r = a(n) / a(n-1) = a(n-1) / a(n-2)

so that it obeys the recurrence

     a(n) = a(n-1)^2 / a(n-2)

Thus in a geometric sequence, two adjacent terms determine the next term.

A Pisot sequence adjusts this term to a nearby integer in order to 
generate an integer
sequence that approximates a geometric sequence:

     [3]  a(n) = adj(a(n-1)^2 / a(n-2))

where adj(x) takes real x to a nearby integer (e.g., adj = floor, 
ceiling or round). Two
arbitrary initial terms are chosen, the recurrence generates the rest.

For some reason unknown to me, the initial elements of Pisot sequences 
tend to obey
simple linear recurrences. Sometimes, the entire sequence obeys the 
recurrence, such as
A020701, where we can prove a(n) = Fib(n+4), and hence the recurrence

     a(n) + a(n+1) - a(n+2) = 0

holds globally.

For other Pisot sequences, the recurrence is obeyed only by some initial 
terms, but
eventually falters. A007699 is an extreme example, with the first 1402 
terms obeying
the recurrence

     a(n+4) - 22a(n+3) + 3a(n+2) - 18a(n+1) + 11a(n+4)

But the recurrence fails on the 1403rd term, after which A007699 
diverges from
A007698, which obeys the recurrence globally.

So which Pisot sequences obey recurrences globally, and which only for 
some finite
number of initial terms?

That depends on the recurrence. Once we have established a recurrence 
[1] above
for the initial terms of the sequence, we can easily construct the 
polynomial equation
[2] for its limit ratio. We can then actually solve a(n) in terms of the 
roots of [2].

For example, with a = A018910, the Pisot recurrence is

     [4] a(n) = ceil(a(n-1)^2 / a(n-2))

  initial-term recurrence is

     a(n+3) - 2a(n+2) + a(n) = 0

which gives polynomial equation

     r^3 - 2r^2 + 1 = 0 <=> (r - 1)(r^2 - r - 1) = 0

which factors into linear and quadratic factors with roots

     1, p = (1+r5)/2, and q = (1-r5)/2, where r5 = sqrt(5).

Using standard techniques, we can solve of a(n) in terms of these roots, 
usually
as a linear combination of powers of the root, in this case:

     a(n) = 2*1^n + ((5+2r5)/5) p^n + ((5-2r5)/5) q^n.

Given this expression for a(n), we can actually go back and prove [4], 
this proves
that the Pisot recurrence and the linear recurrence describe identical 
sequences.
The proof of [4] rests on certain nice properties of the roots 1, p, and 
q, which in
turn follow from the fact that they are rationals and quadratic roots. 
The nice
properties we need are equivalent to a continued fraction with bounded 
elements.

Unfortunately, roots of higher polynomials do not possess the nice algebraic
properties we need to prove [3] (the generalization of [4] in our 
example), and in
fact, I would conjecture that if the [2] does not have rational and 
quadratic roots,
then the linear recurrence is not equivalent to [4], that is, the Pisot 
sequence and
linear recurrence eventually part ways.

In the case of A007699, the limit ration equation ([2]):

     r^4 - 22r^3 + 3r^2 - 18r + 11

does not resolve into linear and quadratic factors. Thus we would not expect
A07699 to obey the linear recurrence

     a(n+4) - 22a(n+3) + 3a(n+2) - 18a(n+1) + 11a(n)

globally.

On 2/26/2012 7:46 AM, Simon Plouffe wrote:
>
>
> Hello,
>
>  there are many exotic examples like that.
>
>  Look at this one,
>
>  the sequence A007699, a(n)= {nearest integer to } a(n-1)^2 /a(n-2).
>
>  the sequence is : 10, 219, 4796, 105030, 2300104, 50371117, 
> 1103102046, ...
>
>  the ratio of a(n+1)/a(n) -->> 21.89949541893233438052532024370859294946
> 6190194047646611617481379446934015013...
> quite rapidly.
>
>  By testing that number for algebraicity, one quickly finds that
> it is one of the real roots of
>
>      4       3      2
> 11 x  - 18 x  + 3 x  - 22 x + 1
>
> , the root can be calculated explicitely but it is quite ugly.
>
>  BUT this is FALSE, the exact number, the ratio of a(n+1)/a(n)
> to high precision is :
>
> 21.89949541893233438052532024370859294946619019404764661\
>     1617481379446934015013222134632935910397445152107249\
>     9761349032053359109441276427149926005650693640825950\
>     1335437931357406880506038288883182166121707555714731\
>     7300725684058890389637589630893096102492114259366306\
>     8931460123024765848662425871358354508021664249361199\
>     6944188439509332536170556143293330518711985939602460\
>     9252047620048792957280978376910436207360514815505096\
> ...
>
>  Is NOT a simple algebraic the root of the <apparent> equation
> is valid up to 0.11357748460267988639402531902 * 10^(-1878).
>
>  As far as I know, nobody really knows WHY it behaves like
> that, those Pisot sequences are quite bizarre in my humble
> opinion.
>
>  There are others, like A010900, that one too is exotic
> enough. E(4,13).
>
>  A good idea would be to test against any asymptotics
> the sequence (21.8994954189323343805253202437085929494661)^n
> to see how far it is from the real sequence.
>
>  I discussed that topic with David Boyd (UBC) a while ago
> and the problem with these animals is that we could have
>  a situation where the exponents (or order)
> of the recurrence relation could be bery big. That
> means that we can have some approximations but the
> real thing is far more complicated.
>
> ps : I added this comment on the edit page of
> the sequence.
>
> PS2 : this is one example where whatever sophistication
> we now have with programs like PSLQ, LLL, Pari and
> all that, we still can find examples where it fails
> to give a definite answer.
>
>  best regards,
>  Simon Plouffe
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>