‘w‘fi-——v—-——v— V

 

SOME ERGODIC PROPERTIES OF

’MULTI-DIMENSIONAL F--EXPANSIONS

Thesis for the Degree of Ph. D.

MICHIGAN STATE UNIVERSITY

MICHAEL SPENCER WATERMAN
1969

LIBRARY '

Michigan State
University

 

This is torcertifg that the
thesis entitled
SOME ERGODIC PROPERTIES
MULTI-DIMENSIONAL F-EXPANSIONS \

presented by

Michael Spencer Waterman

has been accepted towards fulfillment
of the requirements for

__Eh_._D_._ degree inms &
Probab ility

 

I
// Major professor I

Date @4415 f

0-169

   

 

 

 

 

 

 

 

 

 

 

ABSTRACT
SOME ERGODIC PROPERTIES

OF
MULTI-DIMENSIONAL F-EXPINSIONS

By

Michael Spencer Waterman

Let F be a one to one mapping of a convex set A<: Rn
onto (0,1)n with nonzero Jacobian. For x 6 (0,1)“, we consider
{ak(x)}k21, ak(x) = [F'1(5k'1(x))] where 6(x) = F'1(x) - [F'1(x)]
and ['] is the greatest integer function taken coordinate by
coordinate. For each set of coordinates k1,...,kv, we define the
cYlinder BV = {x : ai(x) = ki, i = l,...,v} and Jv(t)’ the
Jacobian of F0:1 +F(k2 +3..+ F(kv + t)...)). Also

Bv(x) = {y : ai(y) = ai(x), i = 1,...,v}. The following assumptions

are imposed (m denotes n-dimensional Lebesgue measure):

 

sup lJv(t)l
V V
:65 B
C) inf [Jv(tfl S C °
t66va
L) o < L s m(5"B")

Av+1 . .
Q) For each BV there exists B , a collection of cylinders

B:+1<: Bv satisfying 6

v+le+1 = (0,1)“, such that

Av+l

O < q S m v °
m(B)

 

”'1‘ v“ ~-

 

 

 

 

Michael Spencer Waterman

Under these conditions we show there exists a measure p ~ m
so that 5 is a measure preserving transformation. If
ufix : diam Bv(x) a 0} = 1, then 5 is ergodic.

If 6 is ergodic with respect to n, then we have rates on

v
the measure of B (x) as v a m:

1 1
1m 3 log u<B"(x>) = lim 3 log m<B"(x)) = - I log IJ _1(t)Idu-(t) a.e. l
‘H’ W” (0.1)“
If m{x : diam Bv(x) a 0} = 1, the above integral is the entropy r
of 6.

We obtain the analog of Kuzmin's theorem for continued fractions.
Our result gives rates at which iteration of an arbitrary function
converges to g% (x). These rates are utilized in proving a strong
mixing condition. A central limit theorem and a law of the iterated
logarithm are then obtained.

In addition to a class of one-dimensional examples we have the
n-dimensional continued fraction (the Jacobi algorithm) as an example.
A simple generalization of the Jacobi algorithm is discussed.

The above results are an extension of Kinney and Pitcher (The
dimension of some sets defined in terms of f-expansions. E.

Wahrscheinlichkeitstheorie verw. 953. 4 (1966), 293‘315 ) and a

 

series of papers by F. Schweiger culminating in "MetriSChe Theorie
einer Klasse Zahlentheoretischer Transformationen" Q5352 AEEEE- 32

(1968), 1-18).

 

SOME ERGODIC PROPERTIES

OF
MULTI -DIMENSIONAL F-EXPANSIONS

 

By
Michael Spencer Waterman I
I.»
‘1

A THESIS
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Department of Statistics and Probability

1969

 

 

 

 

ACKNOWLEDGMENTS

I would first like to express my gratitude to Professor J.R.
Kinney for introducing me to information theory. His encouragement,
assistance, and patience during the preparation of this thesis are
deeply appreciated.

Also, I would like to thank Janell Mesic and Professor Esther
Seiden for their assistance in translating certain papers.

Finally, I would like to express my appreciation to the
Department of Statistics and Probability, Michigan State University,
and the National Science Foundation for financial support during the

preparation of this thesis.

ii

 

.2!

   

 

 

 

II.

III.

IV.

VI.

VII.

VIII.

IX.

XI.

XII.

XIII.

 

TABLE OF CONTENTS

INTRODUCTION ... ...... ................. .............
NOTATION AND ASSUMPTIONS .............. ........... ..
CALCULATION OF THE INVARIANT MEASURE ...............
ERGODICITY OF THE SHIFT ............. ...... . ...... ..
CONVERGENCE OF F-EXPANSIONS ......... ............. ..
ROHllN'S FORMULA ........................... ...... ..
ENTROPY OF F-EXPANSIONS ................ ..... .......
EXAMPLES .............................. .............
A KUZMIN THEOREM FOR F-EXPANSIONS ..................
DEFINITION AND CONVERGENCE OF A MODIFIED JACOBI
AIGORITHM ..........................................
ERGODIC AND INFORMATION THEORY OF THE MODIFIED
JACOBI ALGORITHM ..... . ..... .......... ..... .........
A NON-CLASSICAL CONVERGENCE PROOF FOR THE MODIFIED
JACOBI AlGORITHM ...................................
A CLASS OF F-EXPANSIONS AND SOME LIMIT THEORY ......

BIBLIOGMM .0.........OOOOOOOOOOOOOOO...00.0.00...

iii

10
l4
18
30
4O
43
51

54

66

78

83

86

93

 

" :zw

 

I. INTRODUCTION

This paper is concerned with probabilistic aspects of the
expansions of points in n-dimensional Euclidean space. The ex-
pansions we consider need not converge although previous work has
required convergence. The results presented in this paper have

historical precedent and we now give a short acc0unt of this history.

 

The first interesting example to be examined from the measure
theoretic point of view was the classical continued fraction.
. __ =1 .1.
Beginning with x 6 (0,1), let a1(x) [:1 and r1(x) x [x]
(where ['1 denotesthe greatest integer function). We proceed by
. . _ 1 _ l l
induction, defining an(x) [;;:;?;;fl and rn(x) E--?;Sfi.

rn_1(X) rn-l

The number x can be approximated by

= [a1,a2,...,an_1,an].

Of course x = [a1(x),az(x),...,an(x) + rn(x)1. All numbers in (0,1)
have a (finite or infinite) continued fraction expansion (see ul]).
Gauss fll] proved the following result in connection with continued

fractions:

 

‘w— 1

 

 

 

Let

mn(X) = mIoz : rn (oz) < x}

(where m is Lebesgue measure). Then

‘ = M
lim mh(x) 103(2) , O.< x < 1”

n—m

He posed the problem of estimating

'. ;_.-_:=a‘

_ loggl+x2
Inn (X) log (2) °

Since {mh(x)}n20 satisfies

qw-M'r‘" "Fm

co

- l .L.
mn+1(x) - £21{mn(k) - m.n k+x)} O s x s l, n 2 O,

formal differentiation yields

 

°° 1 1
m' (X) " 2 111' (—) -
+1 k=1 (kfix)2 n kfix

The following theorem due to Kuzmin [14] in 1928 solves Gauss' problem.

Theorem4(Kuzmin). Suppose {fn}n21 are defined by

co
1 l
f (x) = 2 '--- f (--), n 2 O.
n+1 k=l (kfix)2 n k+x

If (O<x<1)

O< fo(x) <M

 

and
‘f;(x)l<us
then
_ a -i/h
fn(X)-'f_'-;+9Ae ,O<x<1,
1 1
where a = log 2 g fo(x)dx, ‘9‘ < 1, and I and A are positive

5|]

     

COHS tants .

ll
H

Gauss' problem is solved by noting mg(x) — so that an

application of Kuzmin's Theorem above yields

1

I -Vn
(i-I-xnoga)‘ < A e ’ 0 < x < 1’

' -
Imn (X)
and by integrating we obtain

log(l+x) -x/n
‘mn(x) - 108(2) I‘< A e

. #3.,

Rylerardzewski [21] define86(x) = r1(x), the shift on the co-

efficients of the continued fraction: I
5(X) = 8([81(X),82(X),...]) = [a2(x),a3(x),...].

He then proves that 6 is indecomposable with respect to Lebesgue
measure. That is, if 5-1E = E then m(E) is O or 1. The most
important result of his paper was that u defined by

uw>=f dx
E (log 2) (1+x)

has the preperty u(5-1E) =‘i(E). That is, p is an invariant measure
for 6. u is known as Gauss' measure. This result was, as we see
below, already contained in Kuzmin's Theorem, but Ryll-Nardzewski

made an application of the individual ergodic theorem to obtain, for

all Lebesgue integrable f,

 

-1 1
, 1 n k 1 f t
11111; )3 f(6 (x)) = 10 21.7143; dt, a.e. [In].
n—m k=0 g o

This result yields various measure theoretic results on continued

fractions such as

 

 

xrwu

 

 

 

 

For each natural number p, the frequence of p in

 

2
. 1 (112)
the sequence {an(x)} 15 log 2 log p(p+2) for al

most all x.

The next advance came in 1957 when A. Renyi [18] established
similar results for the f-expansions of Everett [6] and Bissinger
[3]. Suppose f maps a subset of the real line onto (0,1) in a

(1-1) fashion. We formally define 6(x) = r1(x) where

also =[f‘1(x>], r1(x> = f‘1<x) - [51ch

and

ancx) =[f'1<rn_1<x>>1. rn<x> = f'1<rn_1(x>) - [f'1<rn_1<x)>].

 

Note an(6(x)) = an*1(x). That is 6 is still the shift operator.
When f(x) = %3 we obtain the continued fraction coefficients and
w a (x)
when f(x) = 2- we obtain the q-adic expansion x = 2 nn .
n=l q

Convergence theorems are stated below.
A) The following conditions for decreasing f are due to
Bissinger [3]. We assume
Al) f(1) = 1
A2) f(t) is non—negative, continuous, and strictly de-
creasing for 1 s t s T and f(t) = 0 for t 2 T
where 2 < T is an integer or +-m.
A3) |f(t2) - f(t1)| s |t2 - 1:1] for 1 _<. t < t and

l 2
there is a constant I E (0,1) such that

if 1+f(2)<t <t.

[f(tz) - f(t1)| s lItz - t 1 2

1I

Under these assumptions {an(x)] represents all x G (0,1). That is

_.'-..:to.-.a..u-. .
. 4' '

_§r- -*-".' r
A

 

 

   

 

 

x = lim f(a1(x) + f(a2(x) +...+ f(an(x))...)).

mm

B) The following conditions for increasing f are due to

Everett [6]. We assume

B1) f(0) = 0

B2) f(t) continuous, strictly increasing for

and f(t) = 1, t 2 T where T > 1 is an integer or

+00.
f(tz) - f(tl)

t2":1

Then for all x 6 (0,1), we have

B3)

 

<1,0st1<t2.

x = lim f(a1(x) + f(a2(x) +...+ f(an(x))...)).

n—nm
Renyi then imposes the following condition:

Define

Hn(x,t) = g? f(a1(x) + f(a2(x) +...+ f(an(x) + t)..

We say that condition C) is met if

sup Hn(x,t)
0<t<1

inf H (x,t)
0<t<1 n

sC<+oo

is satisfied for some C independent of x and n.

theorem is then proved by Renyi [l8]:

OstsT

.0. 4“ .t —
. ill: J
M

“3-" “W: “- “‘-

.)).

The following

Theorem. Suppose f satisfies conditions A) or B) and also that

condition C) holds. Then

a) All sets E satisfying B-IE = E are such that

m(E) =0 or 1.

b) There exists a (unique) probability measure u on (0,1)

such that p ~ m and n is an invariant measure for 5.

 

 

6

c) Letting p(x) = g%(x), we have

c-1 s p(x) s c

d) If g is Lebesgue integrable on (0,1), then
1 n-l k 1

11m 3 2 to (x)) =2] gamut), a.e. [m]-

nam k=0

Rohlin [20] connects Renyi's work on f-expansions with

entropy. We choose an f for which Renyi's Theorem holds and

;; “I
define E J
Bn(x) = {t : ai(t) = ai(x)s i = 1s--'an} r

to be the cylinder of order n generated by x. It is obvious that
x e Bn(x), and in fact that Bn(X) is by definition the set of all
t with identical n-th approximate to x. Bn(x) is always an in-
terval here. Rohlin [20] proves the following theorem as an
application of some general work. Define m = f_1. The definition
of entropy will be given in Section VII below.

Theorem (Rohlin). Suppose the conditions of Renyi's Theorem are met.
Then, if log|m'(-)l is Lebesgue integrable on (0,1), the entropy

of 6, h(6) is given by

1
has) = J“ 108ltp'(X)ldu(X)
0

and
lint-3: log “—1 = lim% log -+—— = has) a.e. [m].
n—m mm (X)) we MB (X))

The form of the ergodic theorem suggests that there "should"
be theorems such as the central limit theorem associated with

stationary processes. I.A. Ibragimov [7], [8], [9] has proven such

 

 

a theorem. His result of the normality of the sum
—1— n51 gakax 1))

c./n k=0 j
(where T is the shift of the stationary random sequence [xj})
hinges on a strongly mixing condition. Ibragimov [8] applies his
theorem to the base 2 expansion and to the continued fraction
expansion. The proof of strongly mixing for the continued fraction
comes directly from Kuzmin's Theorem. Vinh-Hien [31] later extends
this central limit theorem to a general subclass of Renyi's f-
expansions by proving the following generalization of Kuzmin's

Theorem:

Theorem (ginh-Hien). Suppose f satisfies condition A) or con-
dition B) with f(t2) - f(tl) s 1(t2 - t1) where 1 C (0,1). Also

assume
2 ‘9‘ H (x t)l s c < +-«
dt n ’ l

uniformly in n, x, and t; and where the sum is extended over all
possible (and distinct) sequences a1(x),...,an(x). Furthermore

choose f so that
Id— (x)| <N x6 (0 1)
dx p 3 Q '
Then if {Yn}n21 are defined by
Yn+1(x) =i ‘f‘(x+k)]‘1’n(f(x+k))
0 < Yo(x) < M

0<x< 1
It;(x)l<e

 

 

 

 

 

 

 

then.
was) = a Mac) + e A e'V“, M < 1.
l

where a = I Yo(x)dx and A, I are positive constants.
0

Reznik [19], following Ibragimov, has proven the law of the
iterated logarithm for some stationary processes. He uses Vinh-Hien's

result to prove [I
n-l k
2 g(5 (0)
n4» (2 a log log n)

 

for the same class of f-expansions and g's satisfying some
regularity conditions.

In 1869 Jacobi [10] presented an extension of the continued
fraction to two dimensions. Perron [17] in 1907 extended Jacobi's
work to n-dimensions. In 1964 F. Schwieger [23] began an examination
of the measure theoretic preperties of Jacobi's Algorithm. His first
two papers on this topic [23], [24] followed Khinchin's book and did
not explicitly consider any ergodic prOperties. His next paper [25]
established that the shift for the Jacobi Algorithm was indecomposable
for n-dimensional Lebesgue measure. The following paper [26] showed
the existence of an invariant measure for the Jacobi Algorithm. Both
of these papers followed Ryll-Nardzewski rather than Renyi. His
following paper [27] has a theorem corresponding to Rohlin's Theorem
above. This proof does follow Rohlin. Finally Schwieger [29] has
proved a Kuzmin Theorem for the Jacobi Algorithm for the case n = 2.

The purpose of this paper then is to define the notion of
F-expansions for n-dimensional Euclidean Space and to develop the

correSponding theory. We are able to generalize all of Schwieger's

 

 

 

 

 

 

 

l-'¢1“-€=t‘work, including the Kuzmin Theorem. In addition, some results

on convergence of our algorithms are given and a modified Jacobi
Algorithm is presented. The limit theory seems to be difficult to
obtain and does not appear here.

The basic notion is that we choose a suitably nice function

mapping some set in n-dimensions onto (0,1)n. For each x 6 (0,1)n,

l 2
we have an associated sequence of n-tuples of integers k (x),k (x),....
The one-dimensional cylinders have their correSponding n-dimensional

cylinders Bv(k1(x),...,kv(x)) = B"(x), and we will, via a Rohlin

... ‘r---- _—...—-.a- -..—...

‘5.

Theorem, calculate an almost everywhere rate on the convergence of
the areas of these cylinders as v a.m, In Rohlin's calculation

of the entropy of f-expansions, essential use if made of the identity
(goh)' = g'(h)h'. In n-dimensions the identity is the chain rule

for Jacobians ([1], p. 140), Jéég = Jg(h(-))Jh('). In each case the
chain rule allows one to obtain a product, take logarithm to obtain

a sum, and, using the individual ergodic theorem [2],obtain an almost

everywhere limit. Our method of obtaining the chain rule is related

to some work of Parry [15], [16].

 

 

 

 

 

II. NOTATION AND ASSUMPTIONS

In this section we define the symbols that we use throughout
the paper. The underlying assumptions are made and some special
assumptions are stated and labeled. To avoid repetition, we later
use the symbols defined here without redefining them. The reason
for making some of the assumptions will be pointed out when they
come into use.

Suppose F is a 1-1, continuous map of A onto (0,1)n
where A is a convex set contained in RP. We assume JF(x),
the Jacobian of F evaluated at x, exists, the components of F
have continuous first order partial derivatives, and JF(x) # O
for almost all x 6 A. Let D = F-l. 'We define the sequence of
coordinates (n tuples of integers) associated with x 6 (0,1)n

as follows:

also [Dos], a (x) = we - [Don],

ak<x> [Domes], ek<x> = Dok'lx) - [D<sk'1<x))].

where [z] = ([21],...,[zn]) for z E Rn. ([zi] denotes the
integral part of the real number 21.)
Note that 6k(x) need not belong to (0,1)n, that is,
k

6j(x) = 0 may occur for some j G [1,...,n]. To avoid these

difficulties we define the algorithm on the restricted set

10

 

 

 

 

 

 

 

11

(0.1); = {x e (0,1)n : 5%) e (0,1)n for k

1,2,..O}O
We impose the assumption that
n
m(O,l)F = l

where m denotes n-dimensional Lebesgue measure. Our underlying
measure Space, then, is to be m on the Lebesgue measurable subsets
n
of (0,1)F.
We define the cylinder of order v generated by a Specified

. 1 v
set of coordinates k ,...,k as

Bv = Bv(k1,...,kv) = {x 6 (0,1); : ai(x) = kj, j = 1,...,e1.

We remark that

a Bv(k1,...,kv) = Bv-1(k2,...,kv).

That is, 5 is a shift operator. Here B0 = (0,1); by definition.

Of course we only consider k1,...,ky which are admissible, that is

which could arise by application of the algorithm to some x 6 Bo.

This is to assume Bv # ¢. Also Bv(x) = Bv(a1(x),...,av(x)) is

assumed to satisfy m(Bv(x)) > O for all x E (0,1): and the

closure of Bv(x) is assumed Jordan measurable for all x 6 (0,1);.
The identity x = F(a1(x) +-F(a2(x) +;..+'F(av(x) +-5V(x))...))

can be written x = f 1 o f 2 o...o f v(6V(x)) if f i(t) = F(ai + t).

a a a a

Since'there is a chain rule for Jacobians ([1], p. 140) just as there

is for functions of one variable, and since the integral of a Jacobian

is area ([1], p. 271), we make fundamental use of this composition of

functions. The entire theory we construct is based on the following

observation:

 

 

 

12

1
Lemma 2.1. If B" is generated by k ,...,k", then

V
Bv = f 1 o f 2 o...o f (5VBV) = n o f i(5"3").
k k kV i=1 k
Proof.
f 1 o f 2 o...o f v(6VBV) = U {F(k1 +F(k2 +...+ F(kv + 6v(x))..))} =
k k k xer
= lJ {x} = Bv.
xEB\J

The assumptions on F made above will be used throughout and
when they hold we will write F E 3. Below we make three additional
assumptions on F. Every use of these conditions will be clearly
indicated.

The following condition generalizes condition C) of Renyi [18]:

 

sup ‘Jf (t)|
teavsv v
C) SC<+oo
inf Jf (t)]
t€5va v
v
where fv = H o f i for each v 2 l and all admissible cylinders
i=1 k

Bv(k1,...,ky). This condition is to assure us that no path of the

process is too flat or too Steep. That is, condition C) is a reg-
ularity condition on the flow.
v v n .

It should be remarked that 6 B ; (0,1)F but Strict con-
tainment can occur. In the n-dimensional continued fraction (to be
discussed below) for example, 6VBv = [x : xj < xn, j s n-l; xn 6 (0,1)]
occurs a countable number of times (whenever ky = (k,...,k), k 2 1).
If bva = (0,1);, we say Bv is proper; otherwise BV is said to

be improper. Difficulties associated with imprOper cylinders lead

 

 

 

 

13

“3 t0 the next two conditions.
v v o
L) m(éB (x))2L>O for all xEB ,v=1,2,... .

. . v .
Condition L) assures us that 6 Bv is never too small.

A \)+l

For each Bv(x), there exists B a collection of proper

cylinders of order v + 1 contained in Bv (x) such that
m ev+l o

q) Lv 2q>O forall xEB,v=1,2,....
11103 (X))

Condition q) implies that the sum of the measures of the proper

cylinders of any given order is at least q > O.

 

 

III. CALCULATION OF THE INVARIANT MEASURE

For any F 6 3 with conditions C) and L) satisfied, we Show
there exists a probability measure u invariant with respect to 6.
This is the initial step in establishing an ergodic theory for g.
The proofs follow Renyi's [18] technique for the one-dimensional case
but must be modified to handle 5V3” # (0:1);- It is this techni-
cality that complicates F. Schwieger's [26] calculation of the
results of Ryll-Nardzewski's Theorem for the n-dimensional Jacobi
Algorithm.

Theorem 3.1. Suppose that F 6 5 satisfies condition C) and con-

 

dition L). Then, if g is any Lebesgue integrable function on
(0,1)“, we have (by an Ergodic Theorem)

1 v-l j A
lim'; 2 g(6 (X)) = 8(X)
van j=0

exists for a.a. [m] x E (0,1)n . g E L and g = E(g]l) where

l
I = {E : 6-1E = E] and E(-) is with respect to u below. Also
there exists a probability measure n on (0,1)n such that u << m

and 6 is a measure preserving transformation for u. Moreover

u(E) S'i'm(E) holds for measurable E<: (0,1)“.
V

Proof. Let J (t) = J (t), f = n o f ., and 3V = Bv(k1,...,kv).
v i=1 k
By an area theorem for Jacobians and Lemma 2.1

I. ‘Jv(t)]dt = m(Bv).

5V3V

14

 

 

   

 

 

15

Lfit <3 denote an admissible sequence k1,,,,,kv, If 6 runs
v

over all admissible sequences

From this we obtain

la
2 inf ‘Jv(t)‘m(6va) s 1 s 2 sup ‘Jv‘m(6va)
6v 5"}3" 6v 6va I '
and 1
I
(3.1) L: inf IJ (t)] s 1 s2 sup Id l. i .1
v v V 6 v v v
v 6 B v 6 B
It
Now we set E = X [a,,b,) where O s a, s b, s l.
, 1 1 1. 1
i=1
6-V(E) = (F(k1 + F(k2 +...+ Fae" + t)...)) : t e E n (9’3").
5
V

Due to the 1-1 property of F, the above union is disjoint. By a

Jacobian argument similar to the one above, we obtain

m(b’vE) = z I \J (t)Idt s z sup N Im(6VBv n E) s
6 v v V 5 v v V
v 6 B OE v 6 B 0E

_<. 2 sup ‘Jva(E) = m(E) z sup lJvI.
(3v 6va 6v 6va

Using the earlier inequality (3.1),

 

z supIJ I
s V C
-v m(E) v __
““6 E) S L z inflJvls me)'
6V
This yields
1 v-l _.
(3.2) 3 z m(6 JE) s f m(E)

j=O

 

It

 

 

 

 

l6

VVQTEE E is the product of rectangles, and hence (3.2) holds all
measurable subsets of (0,1)n.
By the direct application of a theorem of Dunford and Miller [5],
(3.2) implies
1 V']. k A
(3.3) lim - E g(6 x) = g(x)
v
v4» j=0
exists for all g F L1(0,1)n and a.a. x 6 (0,1)“. We may also

define (applying (3.3) above)
1 v-l -j
”(E) = 11m; 2 m(6 E)
van j=0
which easily has the properties

ME) s §m<E)
and
ME) = lim % ”£1 m(a'jE) = 11m ‘3; V51 m(s'j (5412)) = Me'lE).
V*” i=0 yaw j=0
If condition q) also holds, the proper subcylinders add up
to at least q of each cylinder. This allows us to obtain a lower
bound on n(E) and have n equivalent to m. Renyi has no difficulty
here because all of his cylinders are proper.
Theorem 3.2. Suppose we have an F E S with condition C), condition
L), and condition q) holding. Then, if g is any Lebesgue integrable
function on (0,1)n, we have (by the Ergodic Theorem)
. 1‘”1 j _«
lim— 2 g(6 (x)) - g(x)
vem v j=0
exists a.e. [m] . g E L1(m) and g = E(gl1) where I = [E : 6-1E = E].
Also there exists a probability measure n on (0,1)n such that

n ~ m and 6 is a measure preserving transformation for u. Moreover

 

 

 

 

 

 

 

l7

%m(E) s p.02) s fm(E)

holds for measurable E C (0,1)“.

Proof. The only additional work beyond Theorem 3.1 is to establish

the lower bound on u(E). Below 2 will denote a summation over
8

all admissible cylinders of order 3;

2' will denote a summation over all proper admissible cylinders of

6

v
order v.

-1
For each v-l cylinder Bv , condition q) states that there exists

Av
B , a collection of proper cylinders of order v such that

m 13" 2 q m(BV’l).

Thus
2' m(BV) 2 E m(fiv) 2 E q m(Bv-l) = q,
as 6v-1 6v-l
and
v
2' sup‘JVI 2 3' I ‘Jv(t)Idt ==§' m.B 2 q.
v v 6va v
Now

m(IS-VB) = 2 [ |J (t)|dt 2
6 v v V
v 6 B OE
2 2' I ‘J (t)]dt 2
6 v v v
v 6 B GE
2 2' ianJ Im(E)
6 v

v
z lquJvl
2q—v—"—- m(E)2%m(E)o
2' sup‘J I
6 v

V

 

 

 

 

 

IV. ERGODICITY OF THE SHIFT

To complete the ergodic theory for S we would like to Show
that our measure preserving transformation 6 is also ergodic with
respect to m (and hence with respect to n). This allows us to
replace the g(x) in Theorems 3.1 and 3.2 by the constant
Ig(x)du(x) (a.e. n). 6 is ergodic if all measurable sets E that
satisfy 6-1E = E have m(E) = 0 or 1. It is in this section that
the most difficulty in generalizing Renyi [18] is encountered. In
fact the statement of Lemmas and Theorem follows Schwieger's [25]
treatment of the Jacobi Algorithm. Renyi's [18] one-dimensional
case makes essential use of the fact that the intervals generated by
his f's cover (0,1) in the sense of Vitali. He was thus able
to make use of a theorem of Knopp [13] (which is essentially a one-
dimensional Lebesgue density theorem) to conclude ergodicity.

To employ the Lebesgue density theorem [22] we show first
that invariant sets of positive measure have positive density in
the prOper cylinders. Under condition q) prOper cylinders approximate
321 cylinders. Thus invariant sets have positive density in all
cylinders. Finally we assume the cylinder diameters tend to zero so
that cylinders approximate the cubes, a covering in the sense of
Vitali. Finally, since the invariant sets have positive density in

the cubes, the Lebesgue density theorem yields the result.

18

1'

 

1
I

 

19

Although first showing the invariant sets to have positive
density in the cube is Schwieger's notion [25], the style of proof
in Lemma 4.1 owes much to Renyi [18] and unifies the approachs of
the preceeding section with this one.

Lemma 4.1. Suppose F E S and condition C) holds. Then, if

1

E 6 Id = {D : D a rectangle, m(D) = d, 5' D = D] (o < d < 1),

there exists d' > 0 such that

v
EMELQ_§_2.2 d'
v
m(B )
uniformly in E 6 Id and proper Bv, v 2 0.

Proof. As usual we write Jv(x) = Jf (x), fv =

v i 1 k1
v v n
B = B (k1,...,k ). We Show the inequality for E = X (ai’b 1,
i=1
0 3 a1 S b1 3 1, where m(E) = d.
Since 6-vE = E,
1 (x) = 1 (x) = 1 (5vx) = 1 (f’lcx)) for x 6 EV
E -v E E v ’ ' '

6 E

Then,using the transformation theorem for Jacobians,

f1E(x)dx =]‘1E(f;1(x))dx =
13V . BV

= I IE(t)|Jv(t)|dt.
oVBV

Using this relationship (and 6VBV = (0,1);),

m(Bv n E) 2 inf ‘Jv(°)‘ I IE(t)dt = m(E) inf ‘Jv(.)] 2
(0.1);l

SUP‘JV(')I

2 m(E) ____E_____ .

 

[ii 1..

 

 

 

 

 

20

But

sup ‘Jv(-)| 2 I IJth)Idt = m(Bv),
n n
(0,1)F (0.1)F
so that
m(E n Bv) 2 LII-g)- m(Bv)
or

—SE—-—lm nBv 2é=d'>0.
mas") C

Next we note that condition q) allows us to replace an im-
proper cylinder by the proper cylinders contained in it and lose an
arbitrarily small portion of the cylinder. Lemma 4.2 corresponds
directly to a result of Schwieger [25] concerning the Jacobi
Algorithm.
Lemma 4.2. Suppose F E 8 and satisfies condition q). Then for an
arbitrary cylinder Bv and e > 0, there exists countably many dis-

joint prOper cylinders B“ and an integer v = v0(e) such that

v 0
o
(i) BVD U B”
a u=v+l
and
V
v o u
(ii) m(B .. U B)<e
u=v+l

It is clear that (ii) can only be improved by taking the union over

all proper cylinders of order n contained in Bv.
Av+l

Proof. Let B be a collection of proper cylinders of order v + 1

. . V
contained in B such that

s mGV:1

m(B)

q

 

 

 

 

 

21

3311“» U' denotes the union over proper cylinders of order n.

u
+ + .+
m(s" ~u'b" 1) =nn" - m(u's" 1) sinus") — boa" 1) s
v v
smaa ) -qm<B") = (1-q>m<B).
+ ..+
Take any Bv 1 CZBV which is imprOper. Let Bv 2 be a proper

cylinder such that

 

v+2
mas" )
Then
+ .
m(Bv 1 ... U.B\)+2 ) S (1 _ q)tn(BV+1)
.. + +
Bv 2:3v l
which implies
mas" ., ((U'BV-H) u (U'Bv+2)) s (1 - tongs" .. u's"+1) s

2 v
S(1-q)m(B)-
We proceed by induction and let

v0(e) = min{p= (1 - q)p < e}.

Lemma 4.2 allows us to conclude that E 6 Id has positive
density with respect to any cylinder.
Corollagy 4.1. Suppose F E 8 and satisfies condition C) and con-

dition a). Then there exists d" > 0 Such that
v
Wzdtl>o
m(B)

uniformly in E 6 Id and BV (v 2 0).

 

 

 

 

22

Ptoof. We apply Lamas 4.1 and 4.2. 2' denotes a summation over

11.
proper cylinders as above. For all e > 0,

 

v Vo
' V'l']. ' O V p,
m(Eij:=zm(EnB )+...+zm(EnB )+m(EnB "#13”
v v v
m(B ) 2'm(Bv+1) +...+ 2'm(B 0) + m(Bv ... \H’I B“)

t V
22 m(E n Bv+lj +...+Z'mG n B o)

v
Z'm(BV+1) +...+2'm(B o) + e

If we let 6 —» O, we can obtain

m(En sz 29:: d"
2 .

m(BV)

We now must define a Vitali covering. We follow Saks and Banach([22],
p. 105-118). ‘Suppose EC Rn' Then

r(E) = inf BE)-

, m(J) ’
where the infimum is taken over all cubes J23 E. {En}n21 will be
called a regular if there exists a > 0 such that r(En) >'a for
n = 1,2,... . We say that {EnInzl tends to a point x if,
x 6 En’ n 2 l and diam(En) » O as n ~»m. A family .8 of sets
is said to cover A in the sense of Vitali, if for every point
x E A, there exists a regular sequence of sets in .b tending to x.
The Lebesgue density theorem then states that

m(En C B)

lim———— =I (x) for a.a. x.
En-tx m(En) B

We can now prove the following theorem.

 

 

23

“\EOrem 4.1. Suppose F 6 :3 satisfies condition C) and condition q).

M

Also assume [Bv]v20 covers (0,1); in the sense of Vitali. Then

-1
6 E = E implies m(E) = 0 or 1.

Proof. Suppose m(E) = d > O and 6-1E = E. Then we have a Vitali
covering in which the relative density of E in each set Ev E [Bv]v20

is strictly greater than 0. The Lebesgue density theorem asserts

m(Ev O E)
lim -————————-= I (x) for a.a. x.
qux m(Ev) E
m(E fl Ev)
ll
But Corollary 4.1 proves "ETE‘T" 2 d > O for all Ev. Thus

v
IE(x) = l a.e. and m(E) = 1.

Since there exist interesting examples (which include the n-
dimensional continued fraction) where {Bv}v20 is not a Vitali cover,
we proceed to extend Theorem 4.1. Our method will be to construct
an ”approximate" Vitali cover from the EV.

We will be considering cases similar to the f-expansions of
Everett [6] and Bissinger [3]. The generalization to be considered
is diam(Bv(x)) a O which will be alternatively written as Bv(x) a x.
The idea is that x E Bv(x) for all v. If y # x satisfies
y e B"(x) for all v then dianai"(x)) 2 IIx-yII > 0. Thus the
generalization is a natural extension of the one-dimensional con-
vergence. Notice that if {Bv]v20 covers (0,1); in the sense of
Vitali, we have Bv(x) a x for all x. The following theorem
characterizes this convergence. Schwieger [25] uses conditions
ii) and iii) in showing ergodicity. We will make use of the theorem
in connection with proving a.e. convergence and constructing the

approximate Vitali cover below.

 

 

and

3£811

"here

 

 

24

r‘ihjfi-Orem 4.2. Suppose F E 8 and condition q) holds. Then
v
m(x : B (x) a x) = 1

if and only if for all Bv and all e >'0, there exists countably
many disjoint Bu<: Bv and v0 = vo(e) such that
v v0
i) B :3 U B”
u=v+l
ii) diamcs”) < e
and v

V 0
iii) m(E ,, U B”) < e.
u=v+l

'ggggf. Assume m(x : Bv(x) a x) = 1. Therefore for a.a. x there
exists v(x) such that diam(BV(x)(x)) < e. For each v we search
for the set of Bk such that x E Bv and Bk(x) = Bk(x)(x). Then
the x E U Bk is removed from further consideration. The remark
above allows us to write

m(B" .. U B”) = 0.
IJ-ZV'H-

The B” in the union are countable and disjoint. Thus

L
lim m(B" .. U B“) = 0
L—m p=v+l

and there exists a (L = v0 such that iii) holds. Conversely suppose
i), ii), and iii) hold. Choose 6 > 0. Then repeatedly apply the

o O O O O
assumption with B minus certain cylinders and 6/2v to obtain

0 v-l u
sv(e> = (B .. u Sk(e)) .. U s
k=l u

where diam(Bu) < 9/2v where m(Sv(e)) < e/Zv. Let

 

 

 

25

(D Q
3(a) = U Sv(e). m(S(e)) S E m(Sv(e)) = e. But x 6 Bo ~ 8(a)
v=1 V=1
unplies diam Bv(x) * 0. Therefore

m(x : diam B"(x) —. o} 2 1 - m(S(e)) 2 1 - e
for all e > O and we conclude
m(x : diam s"(x)) -. 0) = 1.

If (0,0,...,0) belongs to the closure of 6va(x) for each

x then if F(a'(x) + F(a2(x) +...+ F(av(x))...)) exists and is

 

continuous there, it belongs to the closure of Bv(x) and

lim F(a'(x) +F(a2(x) +...+ F(a"(x))...)) = x a.e.

vdw
This is the direct extension of the one-dimensional f—expansion.

The following lemma asserts that when Bv(x) a x a.e., the

cylinders are essentially equivalent to a Vitali covering. The
equivalence of course only holds when we consider properties holding
almost everywhere with respect to m(-). The lemma and its proof
are due to Schwieger [25].
Lemma 4.3. Suppose F E 8 is such that Bv(x) a x for a.a. x.
Then, if Q is an arbitrary cube in B0, for each s > 0 there
exists a countable disjoint collection of the B” such that

V

o
m(Q a U 3") < e.
u=1
Proof. Let Q have sides of length a. Form a covering of 3(0)
according to i), ii), and iii) of Theorem 4.2, with 0 z e' = §—-;:I- .
2na +1

This effectively replaces B0 by countably many cylinders with

diameter less than 5'. Choose all B” in this cover that intersect

 

 

 

26

Q. 'Tlie measure of the points in these B” that lie outside Q
cannot exceed e'(2nan-1) since the diameter of the B” are all
less than 6' and Q has 2n sides of area an-l. Also no more
than 6' of Q can fail to be covered according to Theorem 4.2.

v

o p. n-l

Therefore m(Q .. U B ) s e'(2na + l) = e.

u=1

Finally we come to the theorem that unifies and summarizes

the results of this section.
Theorem 4.3. Suppose F E 3 satisfies condition C), condition q)
and m[x : Bv(x) —» x] = 1. Then 6-1E = E implies mE = 0 or 1.

Proof. Suppose 6-1E = E, m(E) = d > 0, and E G Id' Then by

 

 

Lemma 4.3
v
1 v0 0 u
Zm(EnB)+...+):m(EnB )+m(En (Q... UB)
MEOQ)= u=1 2
m(Q) v v0
2m(Bl) +...+2m(B °) +m(Q... u B”)
u=1
1 v0
sz(EnB)+...+zm(EnB)
v
Email) +...+Zm(B o)‘l'e

holds for all e > 0. We apply Corollary 4.1 to obtain

ESELIllll 2 d" >~0
m(Q)

for all cubes in Bo. Since the [Q] form a Vitali cover of B0,
we apply the Lebesgue density theorem as in Theorem 4.1 to obtain
IE(-) = l a.e. Since the theorem holds for all rectangles, we

conclude it true for all measurable E Such that 6-1E = E.

 

 

27

It should be again remarked that Theorem 4.3 contains Theorem
9-1. For x E Bv(x) for all v if x 6 Bo, and Bv(x) is the only
cylinder of order U such that x E Bv. But if y # x and y E Bv(x)
for all u then diam B"(x) .t o, and {13"} would not be Vitali.

It is quite natural to ask whether all F E 5 satisfying
condition C), condition q), and 6 ergodic have the property that
m{x : Bv(x) a x} = 1. This is not the case as the following example
shows.

Define
l
F(x,y) = (,7. y + E mod 1)

where g is irrational and F : (l,m) x (0,1) a (0,1)2. Now
lJF(x,Y)I = l? f 0 for all x G (1,m), and the cylinders are well
X

behaved rectangles.

D<t1,t2) = (L

t1, t2 - 5 mod 1)

and
6(t1.t2) = (fi—l - [3—1]. c2 - g mod 1) = (slap, 62(t2))-

Now 51(t1) is the Shift transformation for the one-dimensional

continued fraction. The invariant measure u is defined by

= dx dy
dp.(x,y) (10g 2) (1+x) '

To see this define E = (0,a) X (0,8). 6-1E = (611(0,a), 6;1(O,B)).

 

 

 

28

 

 

 

'1 _ dx = dx
”<5 E) ' [1 [I dy log 2(l+x) B [1 (log 2) (1+x)
dx
= 8
{0,00 log 2(1+x)
= dygdx

 

(0,01)X(0,3) (108 2) (1+x)

Here we use the fact that the invariant measure for 6 is

 

1
dx (Gauss' measure)
log 2(l-l-x) °
To establish 6 ergodic we note (see Billingsley [2])
l) 61 is ergodic on (0,1)
and

2) 62 is ergodic on (0,1)

Then 6-1(E1 X E2) = E X E if and only if 611E1 = E and

l 2 l

-l _ . . _ -
62 E2 - E2. This implies mlE1 — O or 1 and mlE2 O or 1
So that m(E1 X E2) = O or 1. The usual argument on cylinders

yields E 6.62, 6-1E = E implies m(E) = 0 or 1. We next verify

the necessary conditions:
q), L) 5VBV = (0,1): so that L = 1 = q.

G) Let k1 = (ai,0). Then (following Renyi [18])

 

 

v p (a + t ) +ip
-1 v 1 v-2
of.(t)=(" ,t+\)§modl)
i=1 k1 qv-l(aV‘+ t1) +qv-Z 2
and
v
Jv (t) - ('1) 2
H o f (qv-1(an+t) +qu-2)

 

[3.

 

 

29

andt thuds

sup IJf (t)|

" =(1+—‘—‘=—1-)2s4=c.
inf IJf (t)| qn

V

 

We calculate the rate at which m Bv(x) a 0 below but here
the interesting thing to notice is that Bv(x1,x2) is a rectangle
of height 1 erected above the one-dimensional continued fraction

cylinder for x Therefore diam(Bv(x)) = l.

1.

 

V. CONVERGENCE OF F-EXPANSIONS

In the introductory section we stated theorems of Everett
[6] and Bissinger [3] on sufficient conditions for
(5.1) lim f(a'(x) + f(az(x) + f(... + f(a"(x)...))) = x
vac
for all x 6 (0,1). (f is monotone increasing on (0,m) or de-
creasing on (1,m).) Let Bv(x) = {y 6 (0,1) : ai(y) = ai(x), i = 1,...,v}.

In the present one-dimensional case (5.1) holds if and only if
diam Bv(x) = m Bv(x) a 0 as v a m.

Since diameter and measure do not coincide if n > 1, it does not seem
to be easy to generalize the methods on one-dimension and obtain the
same conclusion. As noted above, we will consider F to expand on
n-dimensional number x if diam Bv(x) ~ 0 as x a m, and write

this convergence as Bv(x) a x. Theorem 4.2 is restated here for
convenience.

Theorem 4.2. Suppose F E 3 and condition q) holds. Then
v
mfx : B (x) a x] = 1

if and only if for all Bv and all e > 0, there exists countably

many disjoint Bpl CIBv and v = v (e) such that
v o o

O
i) B”: U B”
u=v+l

30

 

31

ii) diam (31") < e

and v

0
iii) mas"- U 3“)”.
u-firtl

We now use this theorem to deduce sufficient conditions on
Bv(x) a x a.e. The hypothesis clearly contains a version of con-
dition q).
Theorem 5.1. Let F E 3. Also suppose there exists L 2 l, I G (0,1),
q' > 0 such that for each Bv there exists Bv+i ; Bv, a cylinder of
order v +-L, satisfying

a) dismay-FL) s x diam (BV)

and ev+1
b) 0<q'sElV—l.
m(B)
Then

m(x : diam B"(x) —. 0) = 1.

Proof. We deduce equivalent conditions i), ii), and iii) of Theorem

4.2. Choose Bv and e > 0. Repeatedly applying our hypothesis,
Av+kL

there exists B such that

' k
diam fivflq’ s 1k diam Bv S I. < e

and

a +
k m(fi"+k’“1 913% = M

o < q" = (q') S mév+(k-1)L) mas") him")

9

where k = min {r : )r < c]. This implies (taking the union over all

V + k6 cylinders with diameter less than c)

m(BV ~ U BV'l'kL) S m BV - m(fiV'l'kL) S (1 _ qll)m(BV).

 

Ail

 

   

32

Proceeding as in Lemma 4.2, we obtain

P
" .. U 3“”) s <1 - q">"m<B">.

u=1

m(B

We let vo(e) = min {p 2 (1 ' Q")p < c}.

This theorem is applied to

 

X
= _1. .1
F(X1,...,xn) (x , M2 x ,ooo,Mn x
n n n

with M1 2 1, Mi > O, i = 2,...,n in Section XII below. The

application is rather involved and needs the Special properties
of the F deve10ped in Section X. As a simple illustration of

Theorem 5.1, we consider
= i .1
F(X,Y) (2 9 2).
2
F 3 (0’2) X (032) " (0:1) 9

D(X,Y) = (2X:ZY)

Suppose we have a cylinder Bv(k1,...,kY) (which is a square). Then
+ .. +
Bv 1(k1,k2,...,kv,(1,l)) = BV 1 is the Square in the upper right hand
corner of Bv.
. +
(3" 1) firm")
and
diam 6" = % dianas")
_ l _ . _ 1 . _
Thus ) - 2. and q - q - 4' (With L - 1).

Since convergence seems to be difficult to deduce, we consider

cases when B"(x) —. B(x)=n B"(x) satisfies m(B(x)) = o. This is
v21

 

33

cleathy Inuch weaker than Bv(x) A x but is somewhat easier to show.
The F considered in Section IV above, F(x,y) = fig , y + 5 mod 1),

has cylinders which are rectangles of height 1 which converge to

vertical lines having measure 0. Observations on this version of

convergence are contained in the next proposition.

Progosition 5.1. Let F E 3. Then

a) sup [ squ [J (t)!} a 0 as v a m implies m( 0 Bv(x)) = 0
EV tE6vB v v=1
for all x.

b) If condition C is also satisfied,

as
sup [ inf ‘Jv(t)l} » 0 as v ~ w implies m( n Bv(x)) = 0
v

B tE6va v=l
for all x.
c) Suppose for a.a.' x, Bv(x) is regular. Then
sup [ sup ‘Jv(t)|} a 0 as v a m implies m{x : diam Bv(x) a 0] = l.
v v v
B 6 B

Proof.

a) m(B"(x))= [I |Jv<t)|dcs sup lJV(t)l.

5”3V(x) tE6va(x)
Therefore
m(Bv(x)) 5 Sup sup ‘Jv(t)| a 0 as v a m,
BV 1:66va (x)
and

a:

m( n B“(x)) = o.
v=1

b) By condition C,

sup lJv(t)‘ S C inf ‘J (t)la
éva 6va v

 

0C

34

 

 

sup sup IJv (t)| s C sup inf ‘Jv (t)‘

V V
BV 5V3v B 5 3V

c) {Bv(x)}v21 regular implies there exists

v
r(Bv(x)) = inf W)" > ax-

a > 0 such that
X

v
Thus there exists a sequence of cubes Jx such that

m Bv(x) 2 “x m(J:).

Let J: have sides of length a x' Then

V)

V
m 2 a o
B (X) ax V ,X

By the hypothesis

lim m Bv(x) =
v-coo

n
Therefore a 2.0 so that a .4 0. But
v,x v,x

, v
diam B (x) s g av,x

where g is fixed and positive. This completes the proof.

One basic technique for satisfying conditions in Proposition 5.1

is to utilize the chain rule for Jacobians.

of this rule we obtain

v
(5.2) .Jf (t) = n .( 11 o f kj(t)).
v i=—1Jk1j=i+l
v
where f = U f .. Our method is to work on
V i=1 k1

By repeated application

F which satisfy

t

3 all. 3‘-.. '

 

 

35

lJf in” s 1, t e (0.1);
k

and such that in any sequence of r consecutive terms of the product
in (5.2) we find at least one which is in magnitude less than or equal
to I (l 6 (0,1)). The most trivial situation is when

‘J i(t)| s l < 1 for all t 6 (0,1): and for coordinates ki. Then
k
v v
v v
m(B ) s sulev(t)] = supl n J i( 11 o f j(t))| s 1
i=1k j=i+l k

If, for example,

 

 

M x x
F(X ,...,X)=(_1',M Kla---3M m); M.>0
l n x 2 n n x J
n n
then
i i
_ Ml k1+tl kn-l+tn-l
f i(t1,...,tn) — ( i , M2 1 ,..., M —I---—fl
k k+t k+t “k +t
n n n n n n

and n

U M

Jr (9 = H)" 'El—ji—m-
k1 x +kn)

Now

n

U Mj

(if (m 21L.
i Mn
k l
n n
If M > U M , then we have m( n Bv(x)) = 0 for all x. As even
1 j=2 j v21

the non-classical convergence proof of Section XII requires M1 2 1,

this result is distinct although the conclusion is weaker. If
n
M: = H Mj’ then we must examine (5.2) more closely.
i=2
Next we illustrate our method by proving the convergence theorem

of Bissinger [3]. Let F be a real valued function of a real variable

 

 

 

   

36

satisfying

 

Al) F(l) = 1
A2) F(t) 2 O, F(t) continuous and strictly decreasing for
1 s t s T and F(T) = O for t 2 T, where 2 < T S +m.
(F(hn) = lim F(t)).
t—o-I-oo

and

A3) F is everywhere differentiable and

lF'(t)‘ s l for t 2 1, and

there is l 6 (0,1) such that
IF'(t)| s i if 1 + F(2) s t.

(Bissingerls condition has to do with slope instead of derivatives,
but as we are to deal with Jacobians, derivatives suit our purposes.)

We now prove Bv(x) # x for all x E (0,1)F. As above

V V
mag") = f n f'i( n o f j(t))dt.
6VBV i=1 R j=1+l k
i i V i
If k 22, then k + n ofj(t)2k 2l+12l+F(2).
j=i+l k
V i V
Thus |£'i( n o f j(t))| = |F'(k + n o f .(t))| s 1.
k j=i+l k j=i+l kJ
Similarly if ki+1 2 2,
. I
If' (n of (t)) Si.
1+
k 1j=i+2 kj
Thus suppose k1 = k1+1 = 1. Then
V
l+F(l+ n ofj(t))21+F(l+l) =1+F(2),
j=i+2 k

(cm s i.

v
and again ‘f'i( U o f j
k j=i+l k

 

 

 

 

 

37

Thus
r21 21
-2 2
rum") 3 m(6VBV) 1 s 1 .
Since m(Bv) = diam(BV) we have Shown the convergence of the algorithm.
Bissinger's technique is essentially the same. The regularity of
cylinders allows us to see the relevancy of part c) of Proposition 5.1.

Next we perform analogous calculations on

 

M x x

_. _l .;L n-l
F(xl’ooo,xn) - 9 M2 X ,’° 3 Mn x )

n n n

where Mj > O for j = l,...,n.
- M1"_,2 M_1_ _y_3 E13,, :1
D(y1:°°':yn) (M: 3'”: M 9 )-

y1 ”3 Y1 n y1 y1

Thus k; 2 M1 for all i. We consider an arbitrary sequence of

n + 1 consecutive coordinates k1, ki+1,..., ki+n. If any

k: 2 M + l, we have

 

 

 

l
n n
in 1Mi U M3
”13 (t)|= jn+1S -1 n+1 °
3 (t n+k n) (M +1)
k 1
Next suppose kg = M1 for J = i, i+l,..., i+n. Then
i J
( M1 M tl+kl M tn-l n-l)
,..., = ’ + ’°°°’ +
fkj(xl xn) M1+tn 2 M1 tn n M1 tn
iii . .
Suppose kn- 1 2 1, j = 1,2,...,n. The n-th coordinate of f i+j(t)
j k
t 1+kn- 1
is M. -E:--- and thus satisfies
n t +'M
n l
kj M
M n-1 n-1 2 n
n t +M1 M1+1 '

This implies

 

38

J (f (t))ls .
‘ f ki--+j -1 ki+j M n+1

For our induction hypothesis, we suppose

wt...
ll
:2
u.
I

- l,...,l'H‘l

k31_1=0 , j=i+1,...,i+n

_ i+L,ooo,i-H1

i+l
Now consider the assumption that kn::_1 = k 2 1. We must evaluate the

..
l

'r

I!

I
'A

i

1

.M
l 1

'1

:
E

..

x .
’I‘. ‘-
g .
I

n-th coordinate of f . o...o f
1+1

(t):
k kid-1+1,

f

. (t)
k1+1-hf,

(...M $22.1 M i=1...,MEn;1_)
’ n-L M1 + tn ’ n-ul M1+tn ’ ’ an-Pcn

f o f . (t) =
ki+L k1+£+1

( k+tn-L-1. tn-L
”" 4, nL+1M (M-I-t )+Mt ’- MMn-L+l n—L+2 2 ’

n-l M1+M1tn +Mn c “_1

MnMn-ltn-Z
O O O , 2 )

M1+Mltn “Win t “_1

L

U o f .+ (t) =
j=0 k1 l+j
( (k + tn-L-1)Mn-LMn-.Q+1”.Mn )
ML+1'HV{’t +ML‘1M t +...+M M ...M
l 1 n 1 n

t
n-l 1n n-L-i-Z t:n-Jf,-l-1+M n Mn-L-l-l n-L

' =0 k=1t= =...= = '
Setting tn_‘{’_1 , , n tn-l tn-l l, we obtain a

lower bound for the n-th coordinate

 

 

39

 

n n
H M W M
gal-L j = j=n-L j
L+1 - 9 (M ) ’
+0.. 0.. .0.
M1 Mimi 1Mn +Man Mn—L+2+Mn Mn-L+l L 1
+1 L L-1
= I O I C I C + I I C
where 91,011) Mi + M1 + 1 Mn + + Man Mn-L+2 Mn Mn-L+1’
L 2 1. The same result holds for fki+jo...o fki+J+L(t)’ 1 s j s n-L,
and
:1
LI (L f (cm s 1'21 M
i+j-1 H ° 1+j+v n '
f v=0 k V M
r2“ , r n+1
+ ___lu__
(“1 amp )

Thus we may now consider the hypothesis (5.3) with L = L + 1. This

brings us to L = n - 1

and the end of our calculations. If

 

n n
H M U M
i=1 i r=l r
l = max { +1 ; , L = l,...,n-l} < l,
(M +1)n “
1 , rEn_ Mr n+1
(M +
1 9.1041)
then
1—"—J
+1
m(BV(x>) s 1 “

and our result holds. We note that when M = M =...= M = 1,

1 2 n

 

 

VI. ROHLIN'S FORMULA

In this section we obtain rates and bounds on rates for the

u-measure and the m-measure of Bv(x) for large v. Our formula
will be similar to that which Rohlin [20] used to compute the
entropy of one-dimensional f-expansions. Kinney and Pitcher [12]
have used Rohlin's formula for rates on one-dimensional f-expansions
when the formula did not represent entropy. The calculations of this
section follow Rohlin [20] as Schwieger [27] did in his computation
of entrOpy for the Jacobi Algorithm. Jv(t) will denote Jf (t),
fv = 1510 fki. The next theorem corresponds to Theorem 3.1 2nd
only gives an upper bound on the rate for u(Bv(x)).
Theorem 6.1. Suppose that F e 8 satisfies condition C) and con-
dition L). Assume log ‘JD(-)| is Lebesgue integrable on (0,1)n
and that 6 is ergodic (indecomposable) with respect to m. Then,
if we take u to be the measure of Theorem 3.1,

lim‘ 1 log 1

= + log J (t) du(t)
v—m V m(B"(x)) I ‘ D ‘

for a.a. x. Also

23-1- log ——1——— 2 +j‘ log |JD(t)|du(t).

v
WV MB ()0)
Proof. By Theorem 3.1, u(E) s %-m(E). Then
v
filog—i——-%log—:——=%logL@-Jlsllogg.
mas (x)) MB (x)) mas > "
40

 

 

 

or.'l=_.”'a§fi.9 '.:n'J-'.L'-.!.‘.I'IIL\ L
a; wv-H . h ‘4 r
it, _ .

 

 

 

 

Thus, if lim 1 log

v—m

lim 1 log

v—m

Condition L) and

l

1
‘-'log
v m Bv(x)

We next obtain a

to lim 1 log

V

mas"(x))

41

 

v exists,
m(B x)
l

1 s lim 1 log-—-1;-—-
M13 (X))

m(B"(x)) v7; "

condition C) imply

 

1
‘JV(5vx)|

limit for ‘1 log which will then be equal
v

1 For x E Bv, fv 0 6v(x) = x so that

Jf 06V(X) = 19
V

and by the chain rule

f 06

Therefore

Jf
V

Noting J - JD

6

(X)

V

v-l

n J6(6i(x)).

Jf (5"(x))
V

= Jf (5"(x))
v i=0

1 V'1 i
v = W J6(6 (x)).
(6 (x)) i=0

we have

 

 

 

 

42

v-l
llog 1 :1
V

" \Jf (6"<x))|
V

 

z log‘JD(6i(x))|.
i=0

By the Ergodic Theorem

 

lim log 1\) = + _f log ‘JD(t)ldu.(t)
v—m ‘Jf (6 (x))1 (0.1)“
V

exists for a.a. t 6 (0,1)“.

If we add condition q), then Theorem 3.2 gives us a u ~ m
and the new condition allows us to conclude that m(Bv(x)) and
u(BV(x)) have the same rates. The conclusions of this theorem
fully correspond to Rohlin [20].

Theorem 6.2. Suppose we have an F E 3 with additional conditions
C), L), and q). Assume log ‘JD(-)l is Lebesgue integrable on
(0,1)n and that 6 is ergodic (indecomposable) with respect to m.
Then if we take H to be the measure of Theorem 3.2,

lim 1 log 1 = lim --1- log 1

= +-. log |J (t)‘du(t),
v-m v m(Bv(X)) v-*°° V u(Bv(X)) f D

for a.a. x 6 (0,1)“.

Proof. Since Theorem 6.1 can be applies, we need only establish

liml log --l-- = lim l log --l-- . By Theorem 3.2

H. V m(B"(x)) v—m " u(BV(x))

%m(E) s p,(E) 5 % m(E).

This implies (letting C' max {£3 £1)

1

--—--‘ s 1-log 0'
1) Exam V

—log-——-—---10g

B
u:
3?
v
C

 

 

 

VII. ENTROPY OF F-EXPANSIONS

Rohlin [20] has shown that in the case of one-dimensional

f-expansions the entrOpy of 5, h(6), is given by

11(6) = f log lcp'(t)ldu(t)

where m = f . Since Theorem 6.2 above has an integral of the
same form, it is natural to conjecture that, if

nfix : Bv(x) a x} = 1, then

M6) = I log IJD(t)|du(t).

Under some additional assumptions, this is the result of Theorem 7.2
below. To obtain this result, we must utilize the results of Rohlin
[20] which are concerned mainly with partitions which have as a limit
the collection of almost all the points of the Space. Notations and
definitions will be introduced as necessary.

Let «3J3,P) be a measure space. We call a countable system
{Ba : a E A} of measurable sets a basis for 0 if the c-algebra
generated by {Ba : a E A} is equal to a6 modulo sets of measure
0 (modulo 0) and if x,y E O, x # y, then there exists Bv such
that x 6 Ba’ y é Ba or y C Ba, x é Ba. If P63) = l and 0 has
a basis we call «1J3,P) separable. A separable Space «1J3,P) is
said to be complete modulo 0 with respect to (Ba : a E A}, its basis,

if almost every intersection q E # ¢ where E = B or Q ~ B .
afiA 0’ C1 CY 0'

43

 

 

 

 

 

 

 

44

A separable space complete modulo 0 with resPect to some basis is
called a Lebesgue Space and its measure a Lebesgue measure. In
Rohlin's terminology a measure preserving transformation on (0,8,P)
is called an endomorphism. T is said to be exact if 1: T-vB is
composed of sets of P-measure 0 or 1. The following ThZZem appears
in Rohlin [20] .
Let (9,5,P) be a Lebesgue space, T be an endomorphism, and fl
suppose P is non-atomic. Let a be a countable collection of sets ' . »

of positive measure in ,8 such that disjoint unions of sets in a

are everywhere dense in 6’. If there exists a positive integer

 

valued function n(A), A E d, and a number M > 1 such that

P(Tn(A) (A)) = 1 (A E d) and for all measurable sets X,C A with
measurable image ‘ .Tn (A) (X)
nOA)

(A)) s Mm

Pa PQ)’

then T is an exact endomorphism.

Theorem 7.1. Let F E 8 satisfy condition C), condition L), con-7
dition q), and m(x : Bv(x) 4 x) = 1. Then 6 is an exact endo-
morphism for ((0,1)“, 6“, u), where p is as defined in Theorem 2.
3522:. If we consider ((0,1)“, 8“, m) and the basis

Bv,b = {x 6 (0,1)n : [ZVx] = b} (b is an n-dimensional vector of
zeros and ones) we observe that we have a Lebesgue space with con-
tinuous measure. Since u N m, the same statement holds for
((0,1)n, 6n, p). 6 is, of course, an endomorphism. We take ¢7
to be the collection of all proper F-cylinders of all orders. To
index the set a' we define Bv(x), x 6 (0,1);, to be the v-th

proger cylinder containing x. We apply Lemma4.2(letting e -' O)

to obtain Bv(x) exists for a.a. x. Thus, since BV(x) ..x a.e.

 

45

n
and Bv(x) 3 B (x), we have Bv(x) -» x a.e. Consider x E X [ai’bi)°
v .
i=1
For a.a. x there exists Bv(x) such that
diam B (x) < min {x - a1, b, - x}. Therefore the union of these
i=1,ooo,n n 1
cylinders is equal X [ai’bi) modulo 0. Now, the o-algebra gen-
i=1

erated by d is contained in 8n and we have just shown 4 can,
modulo 0, make up a generating ring for 1am. Thus the o-algebras
coincide and d is thus dense in 3. If Bv(x) = BV(X) (x) 6 a,

then
5"(")CB\,(x)) = 5"(")B"(")(x) = (0,1);l 8° that 11(6"(X)Bv) = 1’

and we have only to establish

v
11(6 X) sMLLQVL
n(B )
for prOper cylinders Bv and measurable X<: Bv such that 6v(X)

is measurable.

(13") = J (1;) dm(t) s sup J (-)
m 611; 1 v 1 1 V 1

and

m(X) = idx = I ‘Jv(t)‘dt 2 inf ‘Jv‘ m(69x).

6Vx

Therefore

m(X) C mix) m

m(avcx» s . s s c ..
inf |JV(-)‘ sulev(-)‘ m(BV)

Also, from Theorem 3.2
9. 9.
C m(E) s ”(E) s L m(E).

Thus

 

 

R1

We

 

3
Lp.(5"X) 5m(5"x) s C2Q%_S€__fl§3_
C m(n) (11103)

or
(6VX)5i v
p‘ qL 11(3)
C4
The theorem is proved by setting M = ;_E > 1.

According to the classical definition, an endomorphim is
mixing if for any two measurable sets A and B
lim u(T-vA n B) = n(A)1L(B)o
qu
This definition has been generalized as follows: Consider
vectors Ar = (k0,k1,...,kr) of non-negative integers. We define

M(Ar) = inf |k

’k,lc
0si<jsr i 3

An endomorphism T is defined to be mixing of degree r if for any

r + 1 meaSurable sets A ,A

0 1,...,Ar and arbitrary sequences of

vectors A: Such that
. r _
11m M(A ) - +00,
van v
we have

r 483 r

limu(fiT 1Ai) = 1111011)-

vam i=0 i=0
Rohlin [20] proves an exact endomorphism mixing of all degrees. Thus
we have

Corollary 7.1. Let F E g satisfy condition C), condition L), con-

dition q), and m{x : Bv(x) a x} = 1. Then 6 is mixing of all degrees.

 

 

 

47

Let n be a partition of 0. Then we write n s n' modulo 0
if 11' is a subpartition of n after removal of sets of measure 0.
By Rohlin, for every collection of measurable partitions “a, there
exists n "a defined as the partition n such that

a

l) “a s n modulo 0 for all a,

2) ”a s n' modulo 0 implies fl s-n' modulo 0.

We define g to be a generator with respect to an endomorphism T if

so
u T-Vg = e modulo 0
v=0
where e is the partition of 0 into its points.
Suppose, C, is a countable partition of O with elements Ck-

Then we define
H(G) = - i P(Ck) log P(Ck).

to be the entropy of the partition Ck h(T,§), the entropy of T

with respect to the partition g, is defined by

n-l
h(T,§) = 1im%H( TI T'kg).
nam k=0

Finally h(T), the entropy of the endomorphism T, is defined by
h(T) = sup h(T:§)

where the sup is taken over measurable partitions of 0. An elegant

result of Rohlin is that when T possesses a measurable generator §

h(T) = h(T,§)-

This allows us to prove Theorem 7.2.

Theorem 7.2. Suppose F E 8 satisfies condition C), condition L),

 

and condition q) with log ‘JD(-)| Lebesgue integrable on (0,1)“.

 

 

48

Px180 assume Bv(x) —.x for a.a. X. Then

h(6) = I log ‘JD(t)‘du(t),

and
h(5) = lim'gj log -—\1)-—- = lim% log + a.e. [m‘1.
v—m 11105 (X)) v—m MB ()0)

Proof. We define g = [B1(x) : x 6 Bo}.

9: ‘..‘L _l A:

. V n 1 1
Since B (x) a x for a.a. x 6 (0,1) , and 1 ;
3 1
- + g 1
5 vg = {B\) 1(x) : x 6 Bo}, we have i A
~ .
.. _v u
U 5 g = e modulo 0. ‘
v=0

By Rohlin's generalization of the Kolmogorov-Sinai [2] Theorem

h(6) = h(5,§)-

The Shannon-MCMillan-Breiman-Chung Theorem ([2], [4]) then allows us to

conclude

1im 1 log --l-—- = h(5) for a.a. x.

v—m " uCBV(x))

if we have

 

as) =811(Bl)10g 11 < +..,
MB)

where the sum is taken over all admissible cylinders of order 1. An
application of Theorem 6.2 then completes the proof. We Show that

H(§) < +-» if and only if log ‘JD(-)‘ is Lebesgue integrable. Since

m(B) = f |Jl(t)|dt,
GB

we have

 

 

49

L inf [J1(-)| s m(B) s sup |J1<'>|»
5 B 6 B

and

 

 

 

l 1 1
(7.1) m(B) log (sup ‘J1(-)l) s m(B) log m(B) s m(B) log L inf ‘J1(.)‘ .
6B 6 B

AS in Section VII,

__1.__
J (6(X)) °
f1

Taking supremum and infimum over B,

JD(X) = J6(x) =

11"

 

 

“- 7...-—'-..._,_——.-.—-1. ”uJ-l
a 1:1: 3"
n

1 1
sup ‘Jl(')‘ S ‘JD(X)‘ S inf ‘J1(‘)1 , x E B.
6 B 6 B

Thus

 

 

1 1
(7.2) m(B) log sup ‘J1(-)[ Sflog ‘JD(x)|dx s m(B) log inf 131('y1 .
6 B 6 B

Summing (7.1) and (7.2) over B,

l l 1
Z m(B) 10g . s 2 m B 10g -—-S E m(B) log - log L
[J1( )l mB inf'J1(°)l

 

sup
6 B 6 B

and

 

 

l l
2 m(B)log sup [J1(-)‘ s I nlog ‘JD(x)‘dx s z m(B) log inf 1J1(')T .
6 B (0,1)F 6 B

 

 

But 0 s m(B) log inf1}1(')[ - m(B) log sup 1:1(')1 s m(B) log C so
6 B 6 B

that the Sums bounding H(§) and I log ‘JD(x)\dx converge and
n

diverge together. Therefore H(§) < +-m if and only if

I log ‘JD(X)|dx < +00.

 

50

c.0t0118ry 7.1. Suppose F E 3 satisfies condition C), condition L),

and condition q). Then
1 l
HG)=-zmm)hgmm)<+w
if and only if

log lJD(')| e L1(m, (0,1)“).

fin.xw;ikfafi.fif—n n 3‘

 

 

VIII. EXAMPLES

In this section we develop applications of our general theory
to two main examples. Besides the independence example developed first,
we present the Jacobi algorithm. In his paper on one-dimensional
f—expansions, Renyi [18] considers the following examples: q-adic,
continued fraction, Bolyai, and B-expansions. Thus we cannot expect
many concrete examples in our situation.

AS has been stated earlier, the motivating example for our
work is the Jacobi continued fraction algorithm. But the most

natural and easily handled algorithm is
F(X1:'° ° axn) = (f1(x1) ,f2(X2) a°°°afn(xn)) 3

n
(A1: B1) " (0:1) .

vs
11>¢n

1 1

where f1 is either in the class of increasing f's or decreasing

f's. That is, f satisfies condition A) or condition B) of the

i

introductory section.
_ -l -1
Now D(y1,...,yn) - (f1 (yl),...,fn (yn))

and

6(t1,...,tn)
= (51(t1),...,sn<tn))

where 51(-) is the Shift for the process generated by fi'

51

(f;1(t1) - [f;1(t1)],...,f;1(tn) - [f;1(tn)]) =

 

nth. W“. ‘V .. ‘nfl' NJ“! a”.

 

 

52

First we consider condition C). Following Renyi, we define
ui<t)=d—f(a()+f(a()+f< +£(a()+t) )))
vx, dtilx izx i... inx ...

and assume
sup lH:(x,t)l
0<t<1

inf lHi(x,t)‘
0<t<1 V

n
Now ‘Jv(t)‘ = .UI‘H:(xi, ti)| where aj(xi) = kg (Bv = Bv(kl,...,kv)).
1:

Also
sup n‘Jv(t)l sup ‘Hi(x,t)l n
tE(0,l) _ 0<t<l ” s U c _ C
inf = i

lJv(t)| _ i=1 inf lH:(x,t)‘ i 1
0<b<1

n
tE(0,l)
By the construction of the F, each cylinder is a proper
cylinder and q = L = l.
Renyi [18] (or our earlier work with n = 1) has shown that for
each 51, there exists an invariant probability measure pi equivalent

to one-dimensional Lebesgue measure. The obvious p for our F is

n
p = X p . To check this consider
1
i=1 -
n
E= X Ei
i=1
n
5'1E = x 5713.
i=1 1 1
and
- n _1 n
”(a 11:) = x “1‘51 E1) = x 11021) =u(E)
i=1 i=1

Thus u is an invariant measure for 6.

 

 

S3

)1 -1
.VV Setting fi = mi and assuming log |m£(-)I 6 L1(0,1), we
Yunve
n 1
has) = z , log ‘cp'.(t) amt)
i=1 6 1 ‘ 1
and
lim fi-log -—-€%—-— = lim é-log --:fL-— = h(6).
vdw m B (X) vdm n(B (X))

For the Simple F(x,y) = (i, y +’§ modulo 1) considered in

Section IV we obtain

1 2
l l 1 dx n
lim - log -—-——— =‘f 10g (——) __________ = +._______ .
v m Bv(x) 0 x2 log 2(1-l-x) 6 log 2 2
__E____
- 6 log 2 V

The area of Bv(x), a rectangle of height 1, is of the order e

Finally we comment on Jacobi's algorithm:

X

 

 

X
F(x1,...,Xn) _ (x , x ,..., x )
n n n
xn n
F : {x : x 2 1, 2 1, j = 2,...,n} a (0,1)
n xj-l

The algorithm is studied in a more general setting in Section XI, but

some results are stated here for completeness.

 

SUP IJV(')|
V V
6 B n+1
+ =
inf ”VON s (1 2n) C.
6va

6va 2 [x : 0 < xj S xn, xn 6 (0,1)} so that

v V 1 _
m(6 B ) 2 n! L.

1
n! (l+n)n+1(1+2n)n+1

Thus our results can be applied. (See Theorem 11.1 below.)

 

 

 

IX. A KUZMIN THEOREM.FOR.F-EXPANSIONS

Much of the value of our work is dependent on calculating
h(6), the entropy of the shift associated with a given F-expansion.

Under the conditions of Section VII, h(6) is given by

has) = _1 log 1JD<t)1du<t)
(0.1)“

where u ~ m has been discussed in Section III. But even in the
one-dimensional case M or, equivalently, du/dm is difficult to
find for a given F. However, in the one-dimensional case, some
recent work of S. Guthery finds an F for which a given 6 is
the invariant measure (personal communication). Unfortunately his
results do not extend to the n-dimensional case.

In the introduction we stated results of Kuzmin [14] and

Vinh-Hien [30] which give a rate at which

1n +1(x) =13 1n(f(x+k))1f'<x+k)1

approaches p(x), the density for the invariant measure associated
with f. Recently F. Schwieger [29] has generalized the Kuzmin
theorem to the Jacobi Algorithm when n = 2. In this section we
prove a Kuzmin theorem for arbitrary F-expansions satisfying certain
regularity conditions.

We consider F G 8 satisfying condition C), condition L),
condition q), and m[x : Bv(x) a x} = 1. Theorem 3.2 and Theorem

4.3 give the existence of u ~ m such that 6 is a measure

54

 

 

 

55

Preserving, ergodic transformation with reSpect to U»- Also

%s%(x)=p(x)sfc:.

For each admissible cylinder of order 1, B(k), we have
6 B(k) C (0,1);. Since there are a countable number of first
order cylinders, the sets 6 B'(k) can be used to partition the
set B0. (The induced partition is the finest countable partition
measurable with respect to the o-algebra generated by 6 B'(k).)

m 0
We denote our partition by {Ai}i=1° With each Ai we associate

61 = {k : 6 B(k):3 A1}.

Since our interest is in statements true almost everywhere we may
assume m(Ai) > 0 for all i without loss of generality. It is

clear that

6123 {k : B(k) is proper}.

Next we obtain a Kuzmin relation for p(-). Suppose E<: Ai'

ME) = LNG-IE) and

6-1(E) = {x : 6(x) G E} = U {fk(t) : t E E} = U fk(E)'
kEai kEKi

Due to the 1-1 nature of F the unions above are disjoint. Thus

”(E) g p(x)dx = I p(x)dx = Z I p(x)dx =

6-1E RG61 ka

2. p<f<x>>1J (x)1dx.
keai‘g 1‘ fk

This implies p(°) satisfies

 

 

3
D
I! .,

 

 

(9.1) p(X) = z: p(fk(x))‘Jf (X)! a X 6 Ai.
kesi k

The relation (9.1) suggests that we formulate a Kuzmin theorem
where the recursion is done in separate components. The following
lemma points out that such an approach is feasible:

Lemma 9.1. Let Yo(x) be given and Yv(x) be defined by

156.) = z: ‘i’v_1(fk(x))‘Jfk(x)|, x 6 A1, 1 = 1,2,...

REGi
Then
()01
YV(X) = z Yo(fv(X))‘va(X)\. x 6 Ai.
v
where f = n o f i and the last summation is over all admissible
i=1 R

cylinders (k1,...,ky) where ky E 61-

Proof. The proof is by induction. Assume
_ (v)
11v(x)- z Yo(fv(x))‘va(x)‘ , x 6 A1, 1 = 1,2,...,
where the sum is over all admissible (k1,...,ky) with kV E 6i.
For v = l the induction hypothesis holds by definition. Now, for

XEA.:
l

1v+1<x)= z 1v(fk(x))|Jfk(x)l

kesi
(V)j

1:6 2 10(fv(fk(x)))1va(fk(x))|lJfk(X>|:
i

where the second summation is taken over all admissible (k1,...,kv)

with kv E 6 and fk(x) E Aj.

3

Since fk(x) E Aj and (V)j

that 6va:3 Aj’ then (k1,...,kY,k) with (k1,...,kv) C (v)j runs

are all admissible sequences Such

 

 

57

0‘79]? all admissible sequences ending in k. This allows us to write

(Using the chain rule)

(v+l)i

11mm = z 1110(1.=v+1<x))1Jf (:61. x e 51.
v+1

Lemma 9.1 motivates Theorem 9.1 below.

Theorem 9.1. Let p(-) be any function (g s p(x) s'%) on B0

satisfying

p(X) = Z 13(fk(X))|Jf (X)! . X 6 A1. 1 = 1,2,...
kéa. k
1
Let {y } 0 be a sequence of recursively defined real-valued
v v2

functions satisfying

1 (x) = z 1 (f (x))lJ (x)\ .XEA.. i=1,2,....
v+1 k66i v k fk 1

where O < m s Yo s M;“l’o and p have continuous first order
partials satisfying

15‘“

6

—x-‘ <11; ‘33‘ < A , j = l,...,n.

Further we assume lJf (X)‘ S D 1< +w uniformly in v and x, and

l
v
N (X)
'2 "a—x——‘ s D2, 2 Tl 3 D3, uniform in v and x.
j J
Then

who.) - a p(x)\ < b(e"‘/" + am»)
where a, b, A are constants and

0(x) = sup (diam Bv(y)), v s x < v + l.

o
YGB

 

   

58

Remark. (i) o(x) is monotone decreasing
(ii) o(x) -+ 0 as x —. co
(iii) diam Bv(x) s 0(v)

Proof. We fix x é Ai. By Lemma 9.1

 

 

(v)i
YV(X) = z Yo(fv(X))lva(X)l . X 6 Ai.
(v). aJ (X)
3‘11 (x) 1 n a? B(f (x)) f
v __o_ v k v
1 a x, 1 s 2 {kil‘axk(fv(x”n_a xj |1va<x)1 +1ro<fv(x))1——a j
and
lavzvoc) (“)1 n ‘a<f\,(x)>k‘ (v)i‘anv(x)‘
s N D 2 z -——————— +-M. z -—-—-—- s
3 xj 1 l k=1 5 xj 8 xj

s n N D1D3 +~M D2 = D4.

We now establish another Lemma to be used in the remainder
of the proof:

Lemma 9.2. If constants t, T exist such that

t p(x) < V") < T p(x). x 6 3°.
then

0
t p(x) < Yv+1(x) < T p(x), x E B .
Proof. The hypothesis implies
t p(fk(x)) < Yv(fk(x)) < T p(fk(x)); k c 81, x 6 Ai

Then

(V)i (V). (v)i

1
c z p(fkcx))1Jfk(x)| < )3 11v<fk<x))|)f (x)1 <1: )3 p<£k<x))1Jfk(x)1

k

I}

 

'1

.. ”—1 ‘ _1_, __‘_.

 

59

anxl
t p(x) < Yv+1(x) < T p(x).
We make the first application of Lemma 9.2 by recalling
0 < m s Yo(x) s M
and

O < g-s p(x) S

F‘IO

Fitting these together

8 p(x) < 251‘ p(x) s 10(X) s C—q! p(x) < c p(x).

B
1-1
m
5
0..
c:
I
F”
3
H
5‘
m
s

where g =

g p(X) < m(x) < G p(x).

We define

cpv(X) 1V6) - .g p(x)

and

gvoc) c p(X) - mac).

By application of Lemma 9.1, we have

Mi
cpv(X) = z cpo(fV(X))‘Jf (x)!
V
and
(V)i
56‘“) = z go<fv(x))1.1f (x)|.
V

Using condition C)

 

 

 

      

‘.
1'.
1

    
   
 

_. 'H 32‘

 

60

mag") s sup p (-)1 s c inf [J (-)| s c |J (-)|,
GVBV V V V
and

(v).

()21 1(f())(B"
mv x C 2 mo v x m ).

We let C; = {Bv(k1,...,ky) : kv E 61}. By the mean value theorem

for integrals([1], p. 279),

(v).

1 l
= V
I. 60(y)dy z momma) ).
Ci

By the mean value theorem for functions of several variables([l], p. 117),

1120(1)) - ¢o(y')| s 1106) - ‘1’0(y')l +g1p<y> - p(y')| s

an (N + g A)Hy - y'H an (N + g A)O(v)

where y and y' belong to BV, and H°H is Euclidean distance.

Combining the above results

(v).

1

“’69) 2 fifv wo(x)dx +% z (epo(fv(x)) - wooymm") >

CI
(v)i

>3? (po(x)dx - %/n (N + g A)c(v) - z m(B") >
c‘.’
l

1 -/n
>EI cpo(x)dx - E— (N + g A)O'(V) .

a:

Now define

1
Li = E'I mo(x)dx > 0.
C?

l

 

61

We now write

> - Q + = - .
m(x) Li C (N g A)a(v) Li claw)
In the same manner we obtain

9. 2% z go<fv<x>>masv),

(v).

I co<y>dy=zlg<y1flmmn
V
Ci

1
1500’) ' €001)! s/n (N +6 A)a(v); m e 3".

Finally

z; (x) >-(1:vj‘ go(x)dx - — “(N +c A)0‘(v)
o.
1

or,defining

1

1
- d >0,
L. =Cft; t;o(X)x
a:

§v(x) >uL: - C2 C(v).

It now follows that

L1 0100:)
YV(X) > 8 p(x) +Li - C100,) = p(X)(g +m - p(x)
C c C(v)
L 1
2 p(x)(g +35% - ———q ).

and

 

 

 

   

62

l

1 Li C26(v)
- -|- = _.:—.——.+__.___
Yv(x)<Gp(x) Li 02 0(v) p(X)(G p(x) p(x) )5
LAL: C C
s p(x)(G - 'ET"+'—E— 5(V))-
There exists a v0 such that v 2 v0 implies
C c d(v)
_ L __1__
and F7
cc 2
= _ L. 1 _2__ a 5,1
G1 G CLi+ q 0(v)<G. . .
g
E
G-g=G-g-1“-(L +L1)+(£(C +C))c(v). 33.
1 1 C i i q 1 2 Li
Now
1 1 Mi
_ _ G- G- v
Li Mi ‘63 (go(x) +cpo(X))dX "534‘ p(x)dx =—C$ >3 mas > 2
v v
Ci Ci

2 G—EE E'm(Bv) >- 'G—;E(q).

where the last summation (2') is over prOper cylinders of order

v and the last inequality is due to condition q). The importance
of this result is to establish lower bound on Li +'L: which is
uniform in i and v. It is this bound which allows us to iterate
below and obtain the geometric bound. Now

L
G -gls(c-g)<1-93->+c

6(v).
1 C

3

Now 0 < q s 1, O < L s 1, and without loss of generality C > 1.

Thus 0 < a = l - Q§Lu< 1, and
C

61 - g1 s (G - 2M + c3 o(v).

 

 

63

We now summarize the result just obtained. From the conditions

that
g p(X) < YO(X) < G p(X).
‘a—XQ‘ < N: j = 19°°°9na
J
we have shown that for sufficiently large v as

g1p<x> < wvcx) < clam

‘9.
A
g.
u
E
a.
1..
Q.
0

where g < g13< G13< G; G1 - g1 S (G - g)& +303 0(V)-

By noting that we have earlier shown

 

a?

8;:1 < D4 , j = 1,...,n,

we can repeat the argument to obtain (for a fixed v 2 v0)

gzp(x) < Y2v (x) < G2p(x)

< C , and

where g1 < g2 < G2 1

(:2 - 82 s (G1 - gl)q + C4 0(v)

where C4 is a function of D4.

The argument for g2 and G2 can be iterated to obtain

grp(X) < Yrvm < Grp (X)
where

Gr - gr s (Gr-1 - gr_1)q +-C4 o(v) s...s

A ‘1 A“
s qr(G - g) +C4 C(V)(ar + qr 2 +...+-1) s

Ar 04
S <1 (G - g) +fi0(v)-

 

 

64

Therefore
G - g s C e-xr + C o(v)
5 6
C4
where -x = log a, C5 = G - g, C6 = l:€" and ii: Gr = :2: gr = a
follows. If we set r = v,
Iv (x) -ap<x>l<p<x)(c -g)s9(c e'“+c 0(v))- p
v2 v v L 5 6 :fi]

This gives us

a = limf ‘i’ 2(x)dx.

Vac) 0 \)
B

Eta-h. .. ' 3 T.‘
....
.

2 2
Finally choose N E [v , (v+l) ). Applying Lemma 9.2

-XV

-Xv

a p(x) - §(c5 e + (:6 am) < v 2(x) < a p(x) +§(c5 e + c6 cm)
v
implies
a p(x) - -Ig:(c5 a-“ + (:6 o(v)) < YN(x) < a p(x) + %(cs e'x" + c6 o(v))
or
m(x) - a p(x)] < %(CS e’“ + c6 o(v)) s fa:5 efle‘MVH) + c6 CC/N)).

Setting b = max{§ C5 L 6’

m(x) - a p(x)\ < b(e"‘/N +o(/N)).

Corollary 9.1. The constant
a = I Yo(x)dx.

o
B

9+9- c - ‘Yv(x) - a p(x)|, v =

l,...,vo},

a of the previous theorem has the value

 

 

65

Proof.

(v).

1
f0 Yv(x)dx =13 Yv(x)dx =2 2 J; ‘1’0(fv(x))lJv(x)|dx
B i -

1

But f takes A 1-1 onto f (A,). Thus
v i v 1

(v).
1
j‘ Yv(x)dx=r 2 f_ Yo(fv(x))lJv(x)|dx =
8° 1 f f (A.)
V V 1.
M1
= E Z Y (X) J (X) dx = Y (x)dx.
i £v A1 0 l v 3 £0 0

To obtain F. Schwieger's result for

5(x,Y) = (i ‘ [519xl'[$1)s

we observe that B((k1,k2)) is proper if k1 < k2, and is improper

if k1 = k2. Also 6(B(k.k)) = {(X.y)

: 0 < y'< 1, 0 < x < y}. Thus

A1={(x,y) :0<y< 1.0<X<y}013°,

61 = {(k1,k2) : k22 1, o s kls k2},
A2={(X:Y) :0<y< 1, ny<‘l}nBo,

62 = {(k1,k2) : k2 2 1, 0 s k1< k2}.

Equation (9.1) and the corresponding equations of Theorem 9.1 have

two components.

X. DEFINITION AND CONVERGENCE OF A MODIFIED JACOBI AIGORITHM

In 1869 Jacobi [10] published an extension of the continued
fraction algorithm to two dimensions. In 1907, Perron [17] developed
a fairly natural extension of the Jacobi algorithm to n-dimensions.
F. Schweiger ([23], [24], [25], [26], [27], V28], [29]) has lately
established information theoretic results concerning the Jacobi
algorithm.

In this section a modified Jacobi algorithm is defined and
deve10ped. Besides proving two versions of convergence of the
algorithm, results corresponding to some of the work of F. Schweiger
[25], [26], [27], [28] are later established as application of
Sections III, IV, and VII.

The algorithm presented here contains the Jacobi algorithm
as a special case. It also yields a generalization of an example
of Kinney and Pitcher [12] who consider f(x) = E‘ defined on
[M, +uo) .

Let M1, M2,..., M.n be a fixed set of positive real numbers

such that M 2 l for j = l,...,n. We consider the function F(-)

 

J

defined as
M M
F(x x x ) = 6!; 2X1 ... -£:E:l)
19 2,°°',n X 3 X 9 3 x
n n n
where
z

(x1,x2,...,xn) E [(zl,...,zn) : zn 2 M1;

66

' ..sm-_n_ar.- .A.-.’1‘D..'“-" o
-!
, ...
..

 

' .) M'Qy

 

67

 

lfiovv
z n
F({zzz 2N; “ 2M..1=2,...,n}>=<o,1>
n 1 2, J
1-1
-1 . . n
and D = F 18 defined on (0,1) by

M
13 23 3 “ M2 3'13 M3 y1 3 3 Mn 3'1 y1

Theorem 10.1. Let P = {x E (0,1)n : 5:(x) = O for some k 2 1}.

P is equal to a countable number of hyperplanes intersected with

(0,1)“.

Proof. From

M M M
= fl :2 .11; _1 _1_
6(x1,x2,ooo,xn) x -[M x],ooo,x -£X ])
2 1 2 1 l l
we obtain
k-l
M 5
5k = 0 iff ‘-l ._Z__ = m for some integer m.
l M k-l
. 2 61
and
k-l k-l
M162 -mM2 61 -0.

Now suppose (letting 5: = l for all v)

 

n
z: b, 5‘33” = 0.
i=0 1 1
Then
n-l M 5" M
'+ +1 1 +
330+ 331(M1 :1 33333 )+bn(v 33335—0
i=1 1+1 5 5
1 1
or
n
2 b! 6 = 0
. 1

 

68

where b'= b M1
n
I = _ \1+1
b1 b0 .E bi ai
1-1
M1
b' =—-—'b, for i=1,...,n-1.
i+l M1+1 1

which can be obtained by allowing m to range over the non-negative
integers and ak over k-tuples of positive integers. Therefore
6:(x) = 0 is equivalent to x being on one of a countable set of
hyperplanes (intersected with (0,1)n). Since k runs over a

countable set we have proven the theorem.

Corollary 10.1. m(P) = 0.

We will thus use our algorithm to expand x 6 (0,1): = (0,1)n n F.
The usual one-dimensional continued fraction expansion of

x E (0,1) can be set into matrix form: 3

+ n
OH 1(x) = H ,0 l
k=1 1 ak(x)

, 0'(X) = I-

=_]: =1--.
where of course a1(x) [x], 61(X) x, [I],

_ _13_3_ = 1__._ 1__.
ak+1(X) - [6k(x)]’ 6k+1(x) 6k(x) [6k(x)],

0n+1(x) = Pn_1(x) pn(X)

qn_1(X) qn(X)

where

 

69

P_1(X) = 1, P0(X) = 0. pn(X) = an(X)pn_1(X) + pn_2(X), n 2 1,

q_1(x) = 0. qo(X) = 1. qn(X) = an(X)qn_1(X) + qn_2(><). n 2 1-

P (X)
The convergence theorem says that lim an?;7 = x. Another useful
n—oco

property is
n+1 _ n
det G (x) = pn_1(X)qn(X) - qn_1(X)pn(X) - (-1) , n 2 0.

These coefficient matrices have analogies for the present trans-
formation. The connection between the matrices defined below and

F is given in Corollary 10.3 below.

 

1
0 O 0 0 O F
n
1 0 0 . 0 O 0
A0 = M2 ,
O -— 0 0 0 O
F
1
Mn
0 0 0 0 0
n-l
0 0 0 M1
k
l 0 0 Fla1
1
A = k
0 l . 0 F232 ’
o o . 1 Fak
n n
and
0 0 . 0 1
k
l 0 0 Fla1
k
A = , k 2 2,

 

7O

 

Whet'e n
(n M )j/n+1
._ 1
Fj = 131 , j = 1,2,...,n.
n M.
i=1 1
Next we define
k-l
k
a (x) = U A"(x> =
v:
k
- (wij) ’ 1=0,...,n .

0,...,n

Luis
ll

k+1
The relation det 0 (x) = (-l)k, k 2 0, of the one-dimensional

continued fraction has an analog in our case.

 

 

n
, ‘ k nk H Mi
Proposition 10.1. det O (x) = {-1) i=1 , k 2 2
n
n F
i=1 1
n
Proof. fl M1
det A0 = (_1)n 1:2 ,
n F
i=1 1
det A1 = (-1)n M ,
det A33 = {-1)“, k > 1.
Therefore
n
H M
k = i
det G = U det A3 - (-l)nk inl , k 2 2
i=1 n F.
i=1 1

The following lemma allows us to recover x and corresponds

to a result of Perron [l7].

 

 

71

'Leunna 10.1. If x 6 (0,1);, then

\—

 

 

 

 

 

 

n
k
:+1 + Z w: . F
Xi— ,n i=1 a] J J
9
k+1 “ k k
m + 2 w 6 F
0.n 1=1 0.1 1 1
k k
where k = 1,2,..., 1 = 1,2,...,n, and wij E O (x).
Proof. Let k = 1. Then the assertion is
n
+ l 6' F
“’m 131 “’31 j J
x = .
i 2 n ' '
+ w 6 F
“’0,“ 3321 0,1 J 1
Now let i = 1. Then
n
w2 2 w 6' F
+
l, j=1 lj j j M1 0 = M1, = x
n I 1_. I M X 1
wZ + E w' , a + F 6 Fn l l
0,“ _ OJ J j n
j-l
For i 2 2
n
M
(.0 + E (D3 53 F I .i I
i n j=1 j j J a1-1 Mi + Fi_1 61-1F1-1
n =
I I M/x
3330,n+ E (00:16ij 1 l
j-l
M x
l i
M. -— -)
= i 1 M1 = x
Ml/x1 1

Thus the lemma is established for k = l with {F1}:=1 arbitrary.

They will be determined in the calculation for the induction step.
Suppose the formula holds for k - 1. We reduce the formula

for k to that for k - l, establishing the induction step. Now by

the form of AR, k 2 2, and Qk+1 = Qk Ak we have

 

 

 

1'1
3.3331 =u> + E a33 3.3.
and
k _ k-l _
“31,1 1,j-H. , j 0, ..,n 1.
Thus
k+l “ k
w E w. 6 F =
i,n 3:1 1,1 j j
k n k
= + F a +
“’1.0 jilu’m 1(1 51)
k-l
i,0 1:1 1,j j j+1 61- 1,n n 61—
k-1
=FnM1{wk +2101 F3 k-l+wk L,
6E-1 1,n j=1 1,j FnMj+l j+l i,0 Fan
k-l
= Fan {wk + “£1 wk-l Fj k-l +_wk-1 E;__ }
5E-1 1,n j=1 i,j+l FnMj+1 3+1 1,1 Fan

We would like the quantity in brackets equal to

n
z w?31 F. 5k'1.
j=1 1,j J j

i,n

This yields the following system of equations

 

 

1
F =
1 Fan
F -1
Fj = fii§« , j = 2,...,n
j n
or
1
F —
1 Fan
1
F =
2 2
M1M2Fn
F = 1
n

 

73

Tfilus

With these Fj’ then,

:1

 

 

k+l k k '01 k n k- k-1
= +
“’i.n E “’1.1 51 F1 k-l ”i,n 2. “’m 131 33 3
j-1 1 j-1
In a like fashion
n
k+l k k n 1 k -1 k-l
w + )3 u) .6 F = _ {w + 2 (n F 6 }
0,11 j=1 0).] j J 03:1 0,11 j=1 09.3] .3] j

and by appropriate division the induction step is complete.

Corollary 10.2.

 

n
wk+1 + Z wk+j-n 6k F
1,n =1 i,n j j
X = j
i n
w:+: + Z wg3a-n E F.
9 j=1 : J
k = k-1 = = k+J-n
Proof. wi,j wi,j+l ... mi,“ .
1 2 k _
Corollary 10.3. F(a (x) + F(a (x) +...+ F(a (x)...)) —
k+1 k+1
= (wln (x) wnn (x))
k+l )""’ k+l( ) '
(”0n (x (”cm x

1
Proof. Note that x = F(a (x) + F(a2(x) +...+ F(ak(x) + 6k(x))...)).
Now the equation in Lemma 10.1 holds not only for x 6 (0,1); but
for any x such that a1(x),...,ak(x) is defined. If we set

y = F(al(x) + F(a2(x) +...+ F(ak(x))...)); aj(y) = aj(x) for

 

 

 

 

 

74

1 s; j s k and 6j(y) = 0. Applying the identity in Lemma 10.1

we obtain our result.

Thus the approximates of x are obtained from Ok(x).

Next we prove a theorem analogous to the convergence theorem
of continued fractions. The proof is similar to the one which Perron
[17] supplied for Jacobi's Algorithm but has minor changes.

Theorem 10.2. If x 6 (0,1); then

k
mi n(x)
lim -—*—-—- = x,, i = 1,2,...,n.
k 1
ka m (X)
0,n

Proof. By Corollary 10.2, we have

n

 

 

 

k+1 k+j-n k
mi,“ + E wi,n éj Fj n+1 k wk+j-n
-l i
X- = 1 = E I Ting—a
1 (”k+1 + 2 wk+j—n 6k}? j=1 3%:
0,n H cm 1 J ’
wk+1
where xk+1 0,n ,
“ k+1 “ k+j-n k
w + w 6 F
0 n j'l 0,n j j
and
k+L-n k
k w 6 F
A = 03“ l 3 9 L = 1:23' -In
k+1 + Z wk+j-n k
0,n j=1 0,n J j
k n+1 k
If we note that 3j 2 0 and 2 3j = l for all k and assume
i=1
that
k
w
lim —%‘E
k4” u30,n

exists (and equals 81’ say), then we conclude xi = $1.

 

 

 

k
w.
TVuas we need only show lim -i*fl exists for i = l,...,n.
kam m
0,n
Define
k .1; n 032‘“:
Bi = min{;E*- ,..., _Eifi }
0,n “’o,n
and
k k+n
mi n i n
Bl = max{F_ , , “Fa-*3}
0,n 0,n
We have
“ k+j k+n
k+n+l w. + 2 w. F a k+j
w. 1,n _ 1,n j j n w,
1,n j-l = Z 1 1,n
u)k'l'u'rl k n k+j k+n n=0 J wk-l-j
0,n w + z m F a. 0,n
0,“ _ 0:“ j J
j—l
where
k+n k+j
k a F mo n = 1 m _ 1
lj k+n+l (F0 , 8° - 1 for al m).
0,n
Thus
wkfln+l n
i n k k
_a__ =
k+n+l 2 E 33- Bi 5
w n=0
0,n
and therefore
k+1 wk+n+l
k+1 i n i n k
Bi — minf-E$T ,..., giifili ] 2 Bi .
w0,n 0,n

Similarly, BE+1 S BE, and

k + +
OSB.SBFISB331sBl.3.
1 1 1 1

Define a = lim 8% and B, = lim BF. Then
1 Raw 1 1 1

k—m

 

 

76

OSBESBiSBiSBI'

 

k
w.
Choose e > 0 such that k > k' implies in > Bi - e-
w
Then 0n
k+n+l k+j k+n
win 33 k 3331,n “'1 k k (”in
—____. = - + —_—— _
k+n+l 520 "j k+j > f 3‘j (Bi 3) 33n (”k+n
wOn w0,n on
k+n
_ k k i n
—(1‘)\n)(Bi'€)+)\n k-l-n’
w
0,n
or
k+n+1 k+n
m

-iE—- - a > 1k 31*3 - e ) -
k+n+1 1 n ( k+n i e '
on u30,n

We now show

_1 I
n-j ’
n (Fan)

5’37:- 133%
V\
u: L- a:

k+n “ k~1+j k-l+n k+n-1 k-1+n
w = w F, a 2 w a
n,n j=0 n,n J j n,n n n
- + _
2 wk+n 1 F M 2...2 wk 3 (F M )n 3.
n,n n 1 n,n n l
M y M M
Also, since -l -i s -l y, s -l , we have
Y y J y
j 1 l
1. 1 1’;
1'
aj s an and L s
n
Therefore
k k+n k+j
11 = w 5 _1 1
k -
1 1313+" F (1)3333" Fn (F M )In j
n n n nn n 1

 

 

 

1
1=kk+...+)\ks)\k{max (F) --1— -{1+F—M-+.. .+——}=
o n n . Fn Fn M1 (F M )n
J n 1
k
=‘x B.
n o
k 1
Thus xnzB >0, so that
o
wk+n+1 k+n
1_ in - -
k—w-m+l 81>]; (k+n Bi) ’3
u’On o wOn
By induction we obtain
k+n+v k+n
w_i.2n__ >1_(win _ )_ (1+1—4. +1—)
k+n-h) Bi v k+n 91 e B (B )v-1°
w0,n o wOn o o
E“
0f any consecutive sequence of n+1 terms 6&3 , we have at
0n

least one less than or equal to Hi and at least one greater than

or equal to Bi. Thus we can choose k C> k') such that

kin
win
k+n 2 Bi

u)On

 

and then choose v E [1,2,...,n} such that

“"15?”
k+n-h) S Bi '
0n

 

0.)

Thus we obtain

 

o 1 _ - 1_ L.
> (B )V (Bi Bi) 3(1 + Bo +...+ BV-l),

O 0

and, by noting Bi 2 Bi’ we have (letting a a O) B. = 6,.

 

XI. ERGODIC AND INFORMATION THEORY OF THE MODIFIED JACOBI AIGORITHM

The main task here is to show that the conditions of our above
work are met. When this is accomplished direct application of the
theorems yield our results.

Our most difficult job will be in evaluating Jf (t) where

 

v v v 1 v
fv(t) = 1'1 0 f i(t). Set B = B (k ,...,k"). Then Lemma 10.1
i=1 k
states
v+l v v V
min + E wiL XL FL wio Z wit 0L
(f (x)) = L21 = L21
V i wv+1 + Z wv X F wv + Z wv fl
0n L21 0& L L 00 L21 1L L

whe e = x + kv F . Define = F = l. B differentiatin
r aL ( L L) L do 0 y 8

 

\J V
B(fv)1 _ . wii - yi mo.
axj ’Fj 2: v ‘
(D 0’
L20 0L L

Thus we wish to compute

v _ v v _
det(wij - (fv)i woj) —————-————-— det{w. LEO mOL aL

This determinant can be evaluated in identically the same fashion
that Schweiger [23] makes a similar evaluation. As the computation

is quite long, we simply state the result.

78 —

   

1; I. f f

  

 

79
v V v v v n—l n v
d. - + , = -1 d t .
et(wij2w0£al{’ wOijLLo/L} QwOLaL) () e O
n
W M.
v _ nk i=1 1 .
We apply det Q - (-l) —;———— to obtain
H F
i=1 1
n
(-1)Ink n M.
. 1
i=1

 

 

 

L20 0L L 1 l 1
Finally we obtain
n
H M
n . 1
_ 1 i=1 _
‘Jv(x)‘ - .n F1 v n+1 n _
i=1 ( Z 0L QL) H F
L20 i=1 1
n
U M.
= i=1 1
v+1 “ v n+1
+ F
(“’On 1,21 “’01, x4, I.)

The remarks that wv 2 mV

kv d v v
On Oj’ n 2 1, an k.n 2 kj are useful

in computing bounds:

v+1 n v v n v v
= + +
0’01: + E ”’04. XL FL "’00 E “m(x aL)FL
L—l L-
implies
F a. wv s wV+1 +- ; wv X F S wV +' 2 mV (1 + av)F S
n n On On _ 0% L L On _ On n L
L‘1 L-l
V V V n
v v v
2 = .
S wOn an +-LEI w0n( an)FL wOn an (1 +'2 Lil EL)

This implies

 

80

 

 

n n
n Mi U Mi
1: 1 n+1 i=1 1 n+1
n n+1 aV v ) S ‘JV(X)| S F )n+l ( V v ) O
(1 + 2 2 FL) n wOn ( n u)On
{F1
This yields
n
l + +1
SUP IJ (')I 2 [:1 FL n
V S = C < +00.
inf |J (-)| F
v n

so that condition C) is verified.
It is difficult to verify condition L) for arbitfiary Mi.

If M2 = M3 =...= Mn = l with M1 an integer, then

v . l l

6 BV‘D {x : xj S xn, xn F (0,1) and x E (0,1)F}, which occurs if
and only if k" = (k,k,k,...,k), k 2 1. Thus m(s‘fis") 2 ‘11—! = L > o

and condition L) is verified.

Using this bound

 

 

 

 

 

n n
W Mi U M
i=1 1 v i=1 1
L n n+1 (av v )n+l S m(B ) S (F )n+l (av v )n+l
(1 + 2 2 FL) n wOn n n 0n
L=1
and for BV-I-1 C Bv
n n
W Mi W M.
i=1 1 v+1 i= 1
L n n+1 ' v+l v+l n+1 5 “‘03 ) S (F )n+1 ( v+l v+l n+1 '
(1 + 2 2 FL) (an u’On ) n n (”0n )
L=1
Now
v
n w
v+l v v v v v 0n
= + = ...+
wOn uJ00 Lil mob at FL u)On an (Fn + wv av)
0n n

so that

 

 

.31 :2; u... < . «a. ~_ -. . 9:5..smigx

 

 

 

 

n
F a u," swVH V a" (1+ 2 F)-
n On On 0 n L=1 L
Therefore
n+1
L (Fn) l S mg§v+12 S
n n v+l n+1 v
+
(1 +2 2 FL)n+1(l+ 2 FL)“ I“ ) (B)
L=1 L=1
n n+1
'(1+2 2 F)
s 1 45;"
+1 +1 2 +1
(a: >“ L(Fn) (“ )

Thus given any cylinder Bv we choose a proper cylinder

 

A + A
Bv 1 inside Bv with aV+1 = (0,0,0,...,M). This gives condition
q) with
F ' n+1
q = L n n n > 0.
(1+ 2: FL)(1+2 2 FIN“)
[4:1 {1:1 -’
MI 1 n
Now (noting ‘JD(x)‘ = n (;-) ), we make an application
H M.
i=2 1

of our general theory:

M M.x 'M x
Theorem 11.1. For F(x1,...,xn) = (;l', -§-l',..., -2;E:l) as above

 

n n n
(assume condition L) holds), we have

a) There exists a probability measure u on (0,1)n such
that p ~ m and 6 is a measure preserving and ergodic

transformation for u. Mbreover

%S§:(x> =p(x)£%

for a.a. x E (0,1)n, where C, q, and L are defined above,

b) 5 is an exact endomorphism,

 

82

awui
c) Letting h(5) denote the entropy of 5,

n

has) = n log M1 - 2 log ML - n f log (x1)p(x)dm(x).

=2 ' n
L ms)
Also
h(5) = lim é-log'-l--— = lim fi'log--—%——- a.e.
Vam m B (x) vdw u 3 (x)

Proof. We need only establish m(Bv(x) a x} = l to conclude our
theorem. Now suppose x s B0 such that Bv(x) 4 x. Then there

exists y E Bv(x) for all v such that x # y. But

ll
>4

lim F(a1(x) +-F(a2(x) +;..+ F(ak(x))...))

k-a

lim F(a1(y) + F(a2(y) +...+ F(ak(y))...))

k—aoo

ll
‘<

implies that there is a v such that av(x) # av(y). Therefore

yéfsx

 

XII. A NON-CLASSICAL CDNVERGENCE ROOF FOR THE MODIFIED JACOBI
AIGORITHM

It should be noted that the theorems applied in Theorem 11.1
above did not require that Bv(x) » x for all x F (0,1); but that
m(BV(x) a x) = 1. It can then be asked if there is an alternate to
the classical Jacobi-Perron technique of establishing this result.
We establish this alternate by means of Theorem 5.1 in the section
concerning convergence of F-expansions. Lemma 10.1 above is required.

We write D(61-1) = (dj,...,di). Then by Lemma 10.1

 

 

 

n n
+ R
(”11211 + 2 03:1 61; F “’10 + Z an:j <11; F.
x = i=1 J = i=1 J =
i n n
k+1 k k k k k
U.) + 2 u) 5, F u) + Z 0) d F
n
wlf-n + 2 (”1.6-1 m d1? F
in 1:1 1n J j
k-n n k+j-n k
(”On + jEI (”On dj J

Thus for all u 2 O we can write

v n +- +n
w, +' Z w? j dv F

 

X, -
1 n
w; +- Z w3+j dV+n F.
n j=1 n j J
+n

Now we consider the diameter of Bv :

83

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

“in n (x - x ) wv-l-n
_ in = )3 dv+n v+j i 1 _ 1n =
1 u)v-I-n j=0 J j 011 F d\J-I-n v+n 1 wv-l-n
0n n n On 0n
+ +n “ v+n v+j
2 03:3 dv F -xi )3 d, F (110 F dv-l-n v-I-n
3:0 n J j j=0 J n + x _ n n will
d\H‘n v+n i F v+n v+n
Fn n (”On n n Ll)On
n 1 v+j v+n n—l v+j win
in dj Fj E (”On dj F.
= j=o _ x j o J
F dv-ln v+n i F d\H-n v+n
n n (”0n n n u’On
v-I-n v+j v+j
= _ n 1 F d (”On x _ u)in
+n v+n 1 v+j
dv
j=0 Fn n u)On u)On
v+n v+n _ v+n . v v v+1 .
Now dn 2 dj , dn 2 1, kn (”0n s (”0n g1ves us
v+n v+j
x _ win “51 F l x _ u"in
' + + + - +
1 wv+n j=0 Fn k” jk‘J j 1...kV+“ 1 ~1 wv 3
0n n n n 0n
v+j
Letting F = max {F /F } and x, - m s diam B(Vfi),
.=0 n-l j n 1 u)V'l‘j
J ,.I., on
we obtain
(1):? n-1 1 v+j
x - s F 2 —-——-——— diam B
‘ +n + + +1 +n-l '
1 wv j=0 kv jky 3 ...kV
0n n n n

+
Since diam B” j g diam BV for j 2 o and kg 2 1.

 

 

 

v+n v
in Lung.
xi v+n S “F v+n-l '
w k
0n n

 

 

-2!qu -- ,...,...- Hm

 

85

'B\1t if x = (x1,...,xn) ranges over BV+11 we obtain from the

triangle inequality

+n di v
diam B" s ZnF -———m B
kv-l-n-l

n

We choose a cylinder §v+n whose

k:*“'1 = (0,0,...,o, max {M1.2([2nF] + 1)}>- Thus we have

(v+n-l)-st coordinate is

diam év+n s 1 diam (3”), 1 c (0,1)

uniformly in v where §v+n is determined only (at this point)

to the coordinates k1,k2,...,kV and kv+n-1.

The work above established

 

n n+1
L F2+l 1 \
S
n n v+l v+2 v+n
(1+2 2 FL)“+1(1+ 2 13’1““ kn kn "'kn
{1:1 L=1
mfiv-I-n
S v
m(B)

Specifying kj = (0,0,...,0,M1) for j = v+l,...,v+n-2, v+n, we

have

/ Fn+1 \n n+1
L n 1

F )n+l M2-1(max{M1:2([2nF]+1)})

L

q:
n n+1 n
(1+EFL) (1+2

i=1 L=1

Thus we have established an alternative to the classical

approach of Theorem 10.2. Since Lemma 10.1 was not dependent of the

Mi being greater than or equal to l we need only have M 2 l and

M2 > 0,...,Mn > 0 for the proof of this section to hold. Therefore
the result is weaker but holds over a wider range of parameters than

the classical one does.

 

XIII. A CLASS OF F-EXPANSIONS AND SOME LIMIT THEORY

Since the above sections were completed, some recent work
of F. Schweiger [30] has come to our attention. His results,
similar to ours, are established for a general class of F-expansions
with the property that all cylinders of all orders are proper. This
is a natural generalization of Renyi [18] and does not include the
Jacobi algorithm. Besides showing convergence, Schweiger constructs
a meaSure ergodic and invariant with respect to 6, proves a Kuzmin
Theorem, generalizes a theorem of Gauss, obtains a strong mixing
condition, calculates the entropy of the shift, and proves other
number theoretic results. These results are established in much
the same manner as our results, although the difficulties are fewer
since all cylinders are proper.

In this section we restate the conditions on the class of F-
expansions Schweiger considers. Then we generalize Gauss' Theorem
and obtain a strong mixing condition. The latter result allows us
to obtain some limit theory for F-expansions.

For f = E o f i’ define

- k

i-l

H H B(f ).
J = sup
V lsi,jsn 5x1

Then F satisfies condition S) if

31) F e 3

$2) ”JV“ 3 m(v)

86

 

 

 

 

87

where T(') is a non-negative, decreasing function on [l,m)

such that T(1) s l and lim T(X) = O. This inequality must

xqm v
hold uniformly for admissible k ,...,k .

83) All cylinders of all orders are prOper.

Theorem 13.1 (Schweiger). If F satisfies condition S), then

diam.Bv(x) » O as v a m for all x.

The theorem is proved by considering the components of fv
and applying the mean value theorem for functions of n variables.
Then 82) yields the result. This work gives a relationship between
the Jacobian and the diameter of the cylinders. It would be useful
to apply Bissinger's [3] technique to give conditions that F

satisfy condition S). However it is not easy to apply Theorem 13.1 to
I x +'k,
i 1
2
+k
(Xu H)

matrix (but are lost when the determinant is taken).

the Jacobi algorithm due to the terms which occur in the

In Schweiger's proof showing the shift ergodic, it is remarked
that the Lebesgue density theorem can be applied. It cannot be applied

directly as the following example.shows. Let

F(X:Y) = ()3: ’ %)’

 

 

then
”Jo“ = :v+l
and condition 8) is satisfied. However m(Bv) = Z-vA-v = 2-3v while
the smallest cube covering the rectangle Bv has area (Z-v)2. There-
fore
2-3v
r(x) = lim = 0,

2-2v

 

 

 

88

Enid {Bv(x)} is not regular for any x.
Following Schweiger's use of a technique of Billingsley([2], p. 44)
‘we can shorten Section IV. Corollary 4.1 essentially states
m(E n Bv) 2 C-1m(E)m(BV) for all cylinders BV. In Section VII we
show that the cylinders generate the Borel sets. Thus we have
m(E n E) 2 C-1m(E)m(E) and m(E) = O or 1.
The Kuzmin Theorem appears in Schweiger's paper with an error

bound of the form b T(V). He then uses this result to generalize a

result of Gauss that states

m(6"’(E>> - ME).

We have no difficulty generalizing Schweiger's Theorem to the general

F-expansions considered above.
Theorem 13.2. Let F E 8 satisfy condition C), condition L), con-

dition q), and m{x : Bv(x) a x} = 1. Also assume that the hypothesis

of Kuzmin's Theorem 9.1 is satisfied for p and fv' Then

|m<a“’<E>> - ME)! < b m(EMe'V" + we».

for all Borel sets E.

Proof. Define Yo(x) = 1. Then Theorem 9.1 states
(13.1) m(x) - a p(x)} < b(e'V" + am»)

But corollary 9.1 shows a = _ Multiplying (13.1)
Y (x)dx - 1.
B0 0
by IE(x) and integrating, we have

If IE(x)‘i’v(x)dx - u(E)| < b m(E)(e"‘/" + cm,»
0
B

 

 

89

We complete the proof by

f0 IE(x)‘1’v(x)dx = 2: g YV(X)IE(x)dx =

B 1
(V)i
=§ z {owo<fv<x>)IE(x)1Jv(x>ldx =
1
Mi
._ V _
- E 2 £ A. IE(6 x)dx -
\) 1

"V

= I I (x)dx = m(6-vE).
3° 5 E

The next application of the Kuzmin Theorem gives us a rate on

the strong mixing condition. It is this result which allows us to

obtain the limit theory.

Theorem 13.3. Let F E 3 satisfy condition C), condition L), con-

 

dition q), and mfx : Bv(x) a x} = 1. Also assume the hypothesis

of Theorem 9.1 is satisfied for p and fu' Then

‘u(B(k1.o.-.ks) n 6-V'SE) - n(B(k1.-o-.k§))u(E)l s

s 9:} (e'W + UC/n))u(B(k1,o--,ks))u(E).

for all admissible k1,...,kS and Borel sets E.

Proof. Let B(k1,...,ks) = B8 be a preper cylinder.
I s(X)
100:) = 45-8- p(X)-
uCB )

As usual Yv is defined by

Define

 

 

   

90

(v).
1
(13.2) Yv(x) = z Yo(fv(x))|Jv(X)‘-

Since Yo(x) = O for x 4 BS, we cannot apply Kuzmin's Theorem to

{Yv}v20° However, since 6113 {k : B(k) is proper},

p(f (x))
1’30.) = —:—— |Js(x)|, x 6 Bo.
MB)
The hypothesis of Theorem 9.1 then applies to the sequence {Yv}v28’
and
-Vn
(13.3) mac) - a p(x>| < b(e + 01/11)).

Applying Corollary 9.1 to {Yv}v20 gives a = 1. We multiply (13.3)

by IE(-) and integrate to obtain

\f IE(x)‘i’v(x)dx - “(ml < b(e'V“ + quantum) s
0
B

C b -1/h

s (e

+ «fawn-(E)-

Proceeding as in Corollary 9.1,

I rIE(X)‘1’V(X)dx = )3 f IE(x)‘i’v(x)dx =

BO 1 Ai

(em)i

=2; 2 j; IE<xwo<fm<x>>|Jv<x>|dx =
1
(SW).
1 s+v
=1; 2 I Yo(x)IE(6 (x))dx =j1ro(x)1 (x)dx =
1 fv+s(Ai) Bo 6-s-v

uCBS n 6-8-VE) .
S

MB)

 

 

91

Thus the conclusion of our theorem holds for proper cylinders.
Leanna 4.2 states that the measure of any cylinder can be approximated
by the measure of countably many disjoint proper cylinders whenever

condition q) holds. This completes the proof.

To apply the limit theory developed by Ibragimov ([7], [8],

[9]) and Reznik [19] we need the following assumption

-L/ k

M) 2 (e “ +a(/n)) < +...

v-l

For the cylinder Bv(x) and g 6 L2(O,l)n we write

(x) 1
[s] = ——-j‘ E .11
V n(BV(x)) Bv(x)

Hen, =11 32cm?
Then we have
Theorem 13.4. Suppose F E 8 satisfies condition C), condition L),
condition q), condition M) and mfx : diam Bv(x) a 0} = 1. Also
suppose the hypothesis of Theorem 9.1 is satisfied for p and fv.
Assume g E L2(0,1)n and I g du = 0. Then if
a
21113 - [glvflub < +..,

it follows that

usnfi + 2 2 1 g<t>g<s"(t))dt =.2< +..
V n
(0.1)

and, if a # 0,

—

 

 

92

(i) (Ibragimov)
v-l

k .12
2 gas 0:» z _ 3—
k=0 1
u.{t:————-<z}—.—_-Ie du as v—voo,
0' fV [211' -oo
and
(ii) (Reznik)
v-l k
l 2 3(6 (t))|
11m ————¥—2 = 1 a.e. [m]. 9%
v—m (2 oLanv) :‘ -.
One-dimensional examples of Theorem 13.4 (i) and (ii) can be E
1
found in Vinh-Hien [31], Ibragimov [8], and Reznik [19]. i

 

BIBLIOGRAPHY

 

10.

11.

12.

 

BIBLIOGRAPHY

Apostol, Tom M., Mathematical Analysis. A Modern Approach
to Advanced CalCulus. Addison4Wesley Publishing Company,

Inc.: Reading, Massachusetts, U.S.A. and London, England

(1960).

Billingsley, Patrick, Ergodic Theory and Information. John
Wiley & Sons, Inc.: New York, London, and Sidney (1965).

Bissinger, B.H., A generalization of continued fractions.
Bull. Amer. Math. Soc. 50 (1944), 868-876.

Chung, K.L., A note on the ergodic theorem of information
theory. Ann. Math. Statist. 32 (1961), 612-614.

Dunford, N. and D.S. Miller, 0n the ergodic theorem. Trans.
Amer. Math. Soc. 60 (1946), 538-549.

Everett, G.I., Representations for real numbers. Bull. Amer.
Math. Soc. 52 (1946), 861-869.

Ibragimov, I.A., Some limit theorems for stochastic processes
stationary in the strict sense. Dokl. Akad. Nauk. SSSR 125
(1959), 711-714; English transl., Selected Transl. Math."""
Stat. and Prob. 4 (1963), 99-103.

 

 

 

 

 

 

, Asymptotic distribution of the values of certain
sums. Vestnik Leningrad. Univ. 12 Z (1960), 81-115;
English transl., Selected Transl. Math. Stat. 32d Prob. 5
(1965), 33-48. ”

, Some limit theorems for stationary processes.
Theor. Probability Appl. l, 4 (1962), 349-382.

Jacobi, C.G.J., Allgemeine theorie der kettenbruchghnlichen
algorithmen, in welchen jede Zahl aus drei vorhergehenden
gebildet wird. J. Reine Angew. Math. 69 (1868), 29-64.

Khinchin, A. Ya, Continued Fractions. The University of
Chicago Press: Chicago and London (1964).

Kinney, J. and T. Pitcher, The dimension of some sets defined

in terms of f-expansions. ;. Wahrscheinlichkeitstheorie verw.
Geb. 4 (1966), 293-315.

93 -

g.—

 

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

 

94

Knopp, K., Mengen theoretische behandlung einiger problem der
diophantischen approximationen und der transfiniten wahrscheinlich-
keiten. Math. Annalen 95 (1926), 409-426.

Kuzmin, R.O., Sur un probleme de Gauss. Atti del Congresso
Internazionale del Matematici Bologpa 6 (1928), 83-89.

 

Parry, W., 0n Rohlin's formula for entropy. Acta Math. Acad.
Sci. Hungar. 15 (1964), 107-113.

Parry, William, Entropy and Generators 13 Ergodic Theory. W.A.
Benjamin, Inc.: New York and Amsterdam (1969).

Perron, Oskar, Grundlagen fur eine Theorie des Jacobischen
kettenbruchalgorithmus. Math. Ann. 64 (1907), 1-76.

Renyi, A., Representations for real numbers and their ergodic
properties. Acta.Math. Acad. Sci. Hungar. 8 (1957), 477-493.

Reznik, M.H., The law of the iterated logarithm for some
classes of stationary processes (in Russian). Teor. Verojatnost.
i Primenen. 8 4 (1968), 642-656.

WV ‘Wm"‘W

Rohlin, V.A., Exact endomorphisms of a Lebesgue Space. Izv. Akad.
Nauk. SSSR, Ser. Mat. 24 (1960), 499-530; English Transl., Amer.
Math. Soc. Transl. Ser. 2 39 (1964), l-36.

 

 

Ryll-Nardzewski, C., On the ergodic theorems (II). Ergodic
theory of continued fractions. Studia Math. 12 (1951), 74-79.

Saks, 8., Theory pf the Integral. Hafner Publishing Company:
New York (1937).

Schweiger, F., Geometrische und elementar metrische satze Hber
den Jacobischen algorithmus. Sitzgsber. Akad. Wien, Math.-
naturw. Klasse, Abt. I1 173 (1964), 59-92.

, Metrische Sgtze fiber den Jacobischen algorithmus.
Monatsh. Math. 62 (1965), 243-255.

Ergodische theorie des Jacobischen algorithmus. Acta
Arith. 11 (1966), 451-460.

, Existenz eines invarianten masses beim Jacobischen
algorithmus. Acta Arith. 12 (1967), 263-268.

, Mischungseigenschaften und entropie beim Jacobischen
algorithmus. J. Reine Angew. Math. 229 (1968), 50-56.

, Induzierte masse und Jacobischen algorithmus. Acta
Arith. 13 (1968), 419-422.

 

 

 

29.

30.

31.

 

95

Schweiger, F., Ein Kuzminscher satz fiber den Jacobischen
algorithmus. J. Reine Angew. Math. 232 (1968), 35-40.

, Metrische theorie einer Klasse zahlentheoretischer
transformationan.Acta Arith. 15 (1968), l-18.

Vinh-Hien, Tran., The central limit theorem for stationary
processes generated by number theoretic endomorphisms (in
Russian). Vestnik Moskov Univ. §E£- J. Mpg. Mpg. 5, l
(1963), 28-34. "