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

Richard Guy rkg at cpsc.ucalgary.ca
Wed Dec 16 00:31:56 CET 2009

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.


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.


More information about the SeqFan mailing list