1.1. MAIN DEFINITIONS AND PRINCIPAL PROPERTIES 9

continued fraction map and its close relatives may be found in [132], [133], [278],

[279], [552], [638], [639], [901], [1077], [1086], [1151].

More straightforward iterations of the floor function F(X) = |_a-^J

a(x + 1) = [aa(x)\ , xGN ,

are also of interest [402]. The literature contains many further examples: For

instance, recurrence sequences on algebraic varieties [291], [967] and on elliptic

curves [992].

The Lyness sequences arising from the iteration

u(n + 1) + a

and the generalization

u(n + 2) =

u(n + 2)

u(n)

u(n + 1) + a

u(n) -f b

have been extensively studied as dynamical systems and have intimate connections

with elliptic curves (see [766], [648] and [1376] and references for modern treat-

ments.)

1.1.17. Elliptic divisibility sequences and Somos sequences. In the pa-

pers [1329] and [1330], Morgan Ward considered two-sided sequences satisfying the

equation

(1.10) a(x + y)a(x - y) = a(y + l)a(y -

l)a(x)2

- a(x + l)a(x -

l)a(y)2.

Such sequences are called elliptic because they can be parametrized by elliptic

(theta) functions, and there are non-trivial connections between their growth rates

and the canonical height on an associated elliptic curve. There is a surprising

variety of such sequences. The sequences defined by a(x) = x, a(x) = (§) (the

Legendre symbol modulo 3), and

a(x) = ( a ^ ) - * * - 1 ' / 2 ^ ^

a \ — OL2

for any ct\ ^0.2, satisfy (1.10). These matters will be expanded on in Chapter 10.

An emerging theory of bilinear recurrence sequences (see Section 1.1.20) may sub-

sume many of the known results about both linear recurrence sequences and elliptic

divisibility sequences.

A Somos-k sequence is one which satisfies the recurrence relation

Lfc/2j

(1.11) a(n)a(n — k) = 2 ,

a(n

~

i)a(n

~ k + i), nk.

2 = 1

For example, when k — 4, the sequence

(1.12) 1,1,1,1,2,3,7,23,...

occurs frequently as a test sequence for conjectures. See Section 11.1.3 below for

a recent combinatorial interpretation of this sequence. The recurrence (1.11) with

initial values a(0) = • • • = a(k — 1) = 1, is an integer sequence for k = 4, 5, 6, 7 but

not for k = 8 [1084], see also [499, Sect. E15]. The thesis of Christine Swart [1268]

proves some of Raphael Robinson's conjectures from [1084]. For example, it is

known that not all primes can divide a term of (1.12) — for example 5 and 29

divide no term. In [1084] it is conjectured that if p is an odd prime dividing a term