10
1. DEFINITIONS AND TECHNIQUES
then for all r 1,
pr
will divide some term. She has extended this to other bilinear
recurrence sequences (see Section 1.1.20) with k 4, and has proved several other
conjectures from [1084]. These sequences were originally studied by Michael Somos
in the late 1980's, in an attempt to take a purely combinatorial approach to the
theory of elliptic curves (Zagier has also pondered this possibility.) Jim Propp and
Noam Elkies have been taking strides to try to understand the deep arithmetic and
combinatorial properties of these sequences. The theory is still in its infancy, so we
refer to [421], [422], [775], [1084], [1232] and the web site maintained by Propp
[1052] for more details.
1.1.18. Several variable generalizations. Sequences indexed by N can be
generalized to the multi-variate case. For example, one can consider subsequences
of the coefficients of power series expansions of rational functions in several vari-
ables [736].
Another way to generalize linear recurrence sequences to the many variable
case is as follows. First note that linear recurrence sequences can be considered as
the 'additive' generalization of single exponential functions. One can consider the
'multiplicative' generalization as well. That is, given multiplicatively independent
elements Ai,... , Ar G l consider the finitely-generated multiplicative group
(1.13) V = {\?...\? : xi,... ,xreZ}.
For example, the trace
T
K
/Q(^A^
1
...
A^r)
provides an exponential polynomial in
several variables.
1.1.19. Other linear recurrence relations. For all the sequences men-
tioned thus far, the x-th term a(x) is expressed in terms of one or several previous
terms, typically a(x 1),... ,a(x n). A large class of very interesting sequences
is defined by recurrence relations where the x-th term is expressed in terms of more
distant terms, say in terms of
a ([x/2\),... , a ([x/n\) or a (x [x/2\),... , a (x [x/n\).
In fact, as has become clear relatively recently, their genesis is in automata the-
ory where these relations arise quite naturally. Generally speaking, such sequences
are beyond our scope. Several interesting examples reveal links to classical linear
recurrence sequences; see Sections 9.3 and 14.1. These sequences arise from nat-
ural questions about binary (or g-ary) expansions of integers; they also arise in
an algorithm for fast computation of elliptic divisibility sequences due to Shipsey
[1166].
Going further, the subscripts may depend on the sequence itself. Some exam-
ples in the number-theory literature are
a(x) = a (x a(x 1)) + a (x a(x 2))
and
a(x) = a (x a(x 1)) + a (a(x 1))
with a(l) = a(2) = 1 in both cases. The sequence satisfying
a(x) = a(x a(a(x 1))) + 1,
sometimes called Golomb's sequence, grows like ( x ^ 5 ) . We refer to [402] and
to [499, Sect. E31] for precise references and some generalizations. A particularly
Previous Page Next Page