[seqfan] Re: Divisibility sequences in OEIS. (fwd)

[Richard Guy]

It may be that someone else is interested
in (parts of) this reply that I just made.

Can anyone prove that  A047817  in OEIS
is in fact a divisibility sequence?   R.

---------- Forwarded message ----------
Date: Tue, 15 Dec 2009 13:57:08 -0700 (MST)
From: Richard Guy <rkg at cpsc.ucalgary.ca>
To: Georgi Guninski <guninski at guninski.com>
Cc: Richard Guy <rkg at cpsc.ucalgary.ca>
Subject: Re: [seqfan]  Divisibility sequences in OEIS.

The Hurwitz numbers evidently form a div seq,
but I don't know what they are, so don't know
how to prove it.

[snip]

More exciting is that the numbers of
points (including the pt at infty) on
any elliptic curve over the field  F(q^n)
form a fourth order divisibility sequence,
with  nth  term
                  q^n + 1 - t_n
where  {t_n} is a 2nd order recurring sequence
generated by  x^2 - tx + q,  with  t_0 = 2
(giving  a(0) = q^0 + 1 - 2 = 0)  and  t_1 = t
where  t  is the `trace of Frobenius' (Hecke
eigenvalue) for the curve mod q.  a(1) = q+1-t
is a common factor of all the terms.

It's an interesting (at least to me) paradox
that  2 + 2 = 2 x 2.  I.e., the sum of two
second order recurring sequences [ q^n + 1
satisfies the recurrence  x^2 - (q+1)x + q ]
form a 4th order one, which is the product
of 2 second order div seqs (of integers
in a quadratic extension field of  Q), the
4 roots being the products of the 2 roots
of each of the two quadratics.

There's a 2-parameter (q \& t) infinite family
of such sequences, but  A002248  is the only
one I've spotted in OEIS.  Your search didn't
pick this one up.  Several hundred should be
in OEIS, e.g., for  q = the first 8 or 10 primes
and  t = 0, +-1, +-2, ...  Note that although
Hasse tells us that |t| <= 2 * sqrt(q), you
still get divisibility seqs with  t  outside
that range.

The fact that it's a divisibility sequence
follows from the group structure of points
on an elliptic curve.  Also my colleague
Hugh Williams has recently proved that a
large (3-parameter) family of 4th order
recurring sequences, which includes these
as a particular case, are div seqs.

[snip]