Continued Fractions

Continued Fractions

Wieb Bosma Cor Kraaikamp

Sandra Hommersom Merlijn Keune Chris Kooloos

Willem van Loon Roy Loos

Ewelina Omiljan Geert Popma David Venhoek Maaike Zwart

2012?2013

2

Contents

1 Introduction

9

1.1 What is a continued fraction? . . . . . . . . . . . . . . . . . . 9

1.2 Finite real continued fractions . . . . . . . . . . . . . . . . . . 10

1.3 Infinite real continued fractions . . . . . . . . . . . . . . . . . 19

1.4 Basic properties and matrices . . . . . . . . . . . . . . . . . . 24

1.5 Periodic regular continued fractions . . . . . . . . . . . . . . . 26

2 Planetaria

35

2.1 Huygens's Planetarium . . . . . . . . . . . . . . . . . . . . . . 36

2.2 Eisinga's Planetarium . . . . . . . . . . . . . . . . . . . . . . 36

2.3 Mathematical Issues . . . . . . . . . . . . . . . . . . . . . . . 38

2.3.1 Take some Educated Guesses . . . . . . . . . . . . . . 40

2.3.2 Continued Fractions . . . . . . . . . . . . . . . . . . . 40

2.3.3 Gear Trains . . . . . . . . . . . . . . . . . . . . . . . . 41

2.3.4 Some last Comments . . . . . . . . . . . . . . . . . . . 42

3 The Stern-Brocot algorithm

43

3.1 Constructing the Rationals . . . . . . . . . . . . . . . . . . . 43

3.2 Application: Approximating Fractions . . . . . . . . . . . . . 47

3.2.1 Stern - Brocot . . . . . . . . . . . . . . . . . . . . . . 50

3.2.2 Brocot - Euclid . . . . . . . . . . . . . . . . . . . . . . 50

3.3 An Amusing Property of the Stern-Brocot Sequence . . . . . 51

3.3.1 Some last Comments . . . . . . . . . . . . . . . . . . . 57

4 Sums of squares

59

4.0.2 Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . 59

5 Pell equation

65

6 Markov numbers

73

3

4

CONTENTS

7 The nearest integer continued fraction

83

8 Continued fractions and the LLL algorithm

87

8.1 Lattices and bases . . . . . . . . . . . . . . . . . . . . . . . . 87

8.2 The geometry of continued fractions . . . . . . . . . . . . . . 90

8.3 The relation between LLL and NICF . . . . . . . . . . . . . . 92

9 Continued fractions and Ford circles

95

10 Decimals vs. continued fractions

105

10.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

10.2 Results of L?evy and Lochs . . . . . . . . . . . . . . . . . . . . 109

11 Entropy and the theorem of Lochs

115

11.1 Introduction to entropy . . . . . . . . . . . . . . . . . . . . . 115

11.2 Calculation of entropy . . . . . . . . . . . . . . . . . . . . . . 119

11.3 The theorom of Lochs . . . . . . . . . . . . . . . . . . . . . . 120

11.3.1 Computation of h(T ) . . . . . . . . . . . . . . . . . . . 120

11.3.2 Proof of the theorem . . . . . . . . . . . . . . . . . . . 123

12 Complex continued fractions

127

12.1 Greatest common divisor of two Gaussian integers . . . . . . 127

12.2 Generalized circles . . . . . . . . . . . . . . . . . . . . . . . . 128

12.3 Hurwitz mapping . . . . . . . . . . . . . . . . . . . . . . . . . 128

12.4 Finite number of g-circles . . . . . . . . . . . . . . . . . . . . 131

12.5 Bounded partial quotients . . . . . . . . . . . . . . . . . . . . 132

13 Geodesics

135

14 Hall's theorem

139

14.1 Cantor Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

15 Bounded complex partial quotients

151

16 Binary quadratic forms

157

16.1 Positive definite forms . . . . . . . . . . . . . . . . . . . . . . 159

16.2 Indefinite forms . . . . . . . . . . . . . . . . . . . . . . . . . . 159

17 CFs in power series fields

165

17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

17.1.1 Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . 166

CONTENTS

5

17.2 Properties of convergents . . . . . . . . . . . . . . . . . . . . 167 17.2.1 Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . 167 17.2.2 Lemma 3 . . . . . . . . . . . . . . . . . . . . . . . . . 167

17.3 Relations between continued fraction expansions . . . . . . . 168 17.3.1 Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . 168 17.3.2 Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . 169

17.4 M?obius transformations and matrix notation . . . . . . . . . 169 17.5 Pseudoperiodic continued fractions . . . . . . . . . . . . . . . 170

17.5.1 Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . 171 17.6 Calculating continued fraction . . . . . . . . . . . . . . . . . . 172

17.6.1 Step of type I . . . . . . . . . . . . . . . . . . . . . . . 173 17.6.2 Lemma 5 . . . . . . . . . . . . . . . . . . . . . . . . . 174 17.6.3 Step of type II . . . . . . . . . . . . . . . . . . . . . . 174 17.6.4 Lemma 6 . . . . . . . . . . . . . . . . . . . . . . . . . 174 17.6.5 Lemma 7 . . . . . . . . . . . . . . . . . . . . . . . . . 175 17.6.6 Calculating a continued fraction from a relation with

itself . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

18 Computing M?obius transformations

177

18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

18.2 Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

18.3 Finite automata . . . . . . . . . . . . . . . . . . . . . . . . . 178

18.4 Transducers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

18.4.1 Multi-symbol input . . . . . . . . . . . . . . . . . . . . 181

18.5 LR representation of the continued fraction expansion . . . . 182

18.6 Other 2 ? 2 matrices over N . . . . . . . . . . . . . . . . . . . 184

18.7 Enumerating matrices in RBn, CBn and DBn. . . . . . . . . . 186

18.8 Transformations on row balanced matrices . . . . . . . . . . . 187

18.9 Transducers for M?obius transformations . . . . . . . . . . . . 189

18.10Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download