[seqfan] Re: A family of quadratic recurrences

[A.N.W.Hone]

Further to Jaume's question, these recurrences are also related to a generalization of the Hurwitz equation 
in L variables, which in turn is a generalization of Markoff's equation (L=3). This gives a simple 
direct proof that the recurrence has the Laurent property, and hence that the sequence has only integers, as follows: 

The generalized Hurwitz equation in question is 

\sum_j x_j^2  +  \sum_{j<k} x_j x_k = N \prod_j x_j,      ----(*)

where all sums here run from 1 to L, and N is a parameter. The equation (*) defines a hypersurface in 
L-dimensional space (\mathbb{C}^L, \mathbb{R}^L,\mathbb{Q}^L,... depending on which field 
you want to work in). 

The hypersurface (*) is invariant under the action of the permutation group S_L, corresponding 
to permutations of the coordinates. It is also invariant under the involution I which leaves L-1 of the 
coordinates, say x_2,...,x_L, the same but replaces one of them, say x_1, by \hat{x}_1, where 
\hat{x}_1 is the conjugate root to x_1 of the equation (*), considered as a quadratic in x_1. 

By the formula for the product and sum of roots of a quadratic, there are two (rational) formulae for 
\hat{x}_1, namely: 

I_1:     \hat{x}_1 x_1 = \sum ' _j  x_j^2  +  \sum ' _{j<k} x_j x_k, 

and 

I_2:    \hat{x}_1 +  x_1 = - \sum ' _j  x_j  +  N \prod ' _{j} x_j , 

where the dash on the sum/product denotes that the indices j,k are excluded from taking the value 1.
Moreover, each of the formulae above lift to birational involutions on L-dimensional space. Now consider 
the birational map defined by the composition of I_1 followed by a cyclic permutation of the 
coordinates, whose overall effect is 

(x_1,x_2, \ldots , x_L)   \mapsto   (x_2,x_3, \ldots , \hat{x}_1). 

Repeated application of this map is exactly equivalent to iteration of the recurrence 

a_{n+L} a_n  = \sum ' _j  a_{n+j}^2   +  \sum ' _{j<k} a_{n+j} a_{n+k},  ----(R1)

(where ' denotes indices running from 1 to L-1 only). From the above discussion, it should be clear 
that the rational quantity 

K_n = (\sum_j  a_{n+j}^2   +  \sum_{j<k} a_{n+j} a_{n+k}) / \prod_j a_{n+j} 

(indices run from 0 to L-1) is an invariant of the recurrence i.e. K_{n+1}=K_n for all n. 
Thus if the value K_0 = N is fixed by the initial data a_0,a_1,\ldots,a_{L-1}, 
then any set of adjacent L iterates (a_n,a_{n+1},\ldots,a_{n+L-1}) lie on the hypersurface (*). 

To see the Laurent property, observe that once the value of N has been fixed for n=0, then 
(using I_2) subsequent iterates also satisfy the recurrence 

a_{n+L} + a_n =   - \sum ' _j  a_{n+j}  +  N \prod ' _{j} a_{n+j}.  -----(R2) 

Now N=K_0 is a Laurent polynomial in the initial data, and since (R2) defines 
a_{n+L} as a polynomial in a_n,...,a_{n+L-1} and N, by induction all 
terms of the sequence are Laurent polynomials in the initial data a_0,...,a_{L-1}. 

For the case of the integer sequence defined by iterating (R1) starting from L ones, 
the value of N=L + L(L-1)/2=L(L+1)/2, so one gets an infinite sequence of 
integer points on the hypersurface (*) with this value of (N). 

Incidentally, to respond to Charles Greathouse's comment about these double-exponentially growing 
recurrences, in this case one can generate the terms of the sequence much more quickly using (R2) 
with N=L(L+1)/2, because this (polynomial) recurrence only involves +/- and multiplications, 
avoiding the costly divisions in (R1).

Best wishes,
Andy 

P.S. There are several ways to generalize (*) to get other recurrences of a similar type. For example, 
premultiply the term with \sum_{j<k} by an arbitrary (integer) parameter, add on a term of the 
form C \sum_j x_j for some (integer) parameter C, and add on a constant D to the left hand side 
of (*). Mutatis mutandis all the above arguments apply to such an equation, and will generate 
families of double-exponentially growing integer sequences. 




________________________________________
From: seqfan-bounces at list.seqfan.eu [seqfan-bounces at list.seqfan.eu] On Behalf Of A.N.W.Hone [A.N.W.Hone at kent.ac.uk]
Sent: 01 October 2009 10:53
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: A family of quadratic recurrences

Hi seqfans -

The fact that these sequences consist entirely of integers follows from Theoreom 1.10 in
Fomin and Zelevinsky's article "The Laurent Phenomenon", Advances in Applied Mathematics,
Volume 28 ,  Issue 2  (February 2002) Pages: 119 - 144  which is available on the arxiv at

http://arxiv.org/PS_cache/math/pdf/0104/0104241v1.pdf

These recurrences satisfy the Laurent property, which means that the iterates are
polynomials in the initial values (say a(0),a(1),...,a(L-1)) with integer coefficients.
So setting all L initial values to 1 gives an integer sequence.

These particular ones may also be related to generalized Hurwitz equations, studied by Baragar, Zagier
and others, but I'd need to check that.

Andy

On Wed, Sep 30, 2009 at 1:31 PM, Jaume Oliver i Lafont
<joliverlafont at gmail.com> wrote:
> Hello Seqfans,
>
> In the family of quadratic recurrences defined by
> a(n)=sum(i=1,L-1,a(n-i)*sum(j=i,L-1,a(n-j)))/a(n-L), with L initial ones,
> I have not been able to find any noninteger value.
>
> Do these recurrences yield only integers? For any L>=2?
>
> This search is related to sequence
> http://research.att.com/~njas/sequences/A165896,
> which is the case L=4.
>
> Regards,
> Jaume
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/