8
1. DEFINITIONS AND TECHNIQUES
1.1.16. Non-linear recurrence relations; in particular continued frac-
tions. A non-linear recurrence sequence satisfies a relation of the form
(1.9) a(x + n) F (x,a(x + n 1),... ,a(x)), x E Z
+
.
Here F is often a polynomial or a rational function, or some arithmetic function.
Even choosing the simplest functions F yields a great variety of interesting se-
quences, from coefficients of algebraic functions and of solutions to differential
equations, to the sequences appearing in the still unsolved
c3x
+ 1' or 'Collatz'
problem (see Chapter 3). Even when n = 1 and F is independent of x, this encom-
passes iterations of functions as dynamical systems see [581] for an attractive
overview.
Non-linear recurrences can be used to define novel entire functions. A striking
recent example is the recurrence
x-l
a(x + 1) = x2a(x) + ] T a(j)a(x + 1 - j), k 2, a(2) = a(l) - a(l) 2 ,
which arises in the tritronquee solution of a Painleve equation [564]. In [541] it is
shown that the limit lima:_+00 a(x)/[(x l)!]2 exists and defines an entire function
of a(2).
A particularly important example of a non-linear recurrence sequence for num-
ber theory is given by the Gauss map
F(x)
=
{i}'
x^0'
where {z} denotes the fractional part of z G R. Define the notation [c$ , C\, c2 , .. ],
by
[CO , Ci , C2 , . . . , Cn] = Co + l / [ c i , C2 , . . . , C
n
].
If a = [CQ , c\ , C2 , . •. ] is the continued fraction expansion of an irrational real
number then the sequence a$ = [a\, ax+i = F(ax), x = 0,1, 2,... , is the sequence
of complete quotients ax [cx , cx+\ , ... ].
The continued fraction expansion of a quadratic irrational is eventually peri-
odic, which implies that the numerators px and denominators qx of its convergents
satisfy linear recurrence relations. In Section 9.2 we shall see that the converse
holds as well.
It is pointed out in [129] that for any algebraic number a the convergents
Px/Qx satisfy a non-linear recurrence relation. Specifically, the partial quotients cx
are given in terms of the previous convergents and the defining polynomial of the
algebraic number. For example, in the case a = one has
1 3 ( - l ) ^ 2 _
1
qx_2 I
L ^ - i ( P x - i - 2 ^ - i ) Qx-i\'
The continued fraction map is ergodic with respect to an absolutely continuous
measure on (0,1), which gives many results on the behaviour of typical orbits under
F, and hence of the continued fraction expansion for almost every real number
(see [260] or [280] for these results, and [1152] for an extensive discussion of
generalizations of the continued fraction map; a 'normal number' for the continued
fraction map, analogous to Champernowne's classical result in [219], is exhibited
in [2]). Further work on normality, ergodicity and Diophantine properties for the
Previous Page Next Page