[seqfan] Re: A family of quadratic recurrences
A.N.W.Hone
A.N.W.Hone at kent.ac.uk
Thu Oct 1 16:53:06 CEST 2009
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/
More information about the SeqFan
mailing list