Geometry of Continued Fractions

Preface to the Second Edition
Acknowledgements
Preface to the First Edition
Contents
Part I Regular Continued Fractions
Chapter 1 Classical Notions and Definitions
1.1 Continued fractions
1.1.1 Definition of a continued fraction
1.1.2 Regular continued fractions for rational numbers
1.1.3 Regular continued fractions and the Euclidean algorithm
1.1.4 Continued fractions with arbitrary elements
1.2 Convergence of infinite regular continued fractions
1.3 Continuants
1.4 Existence and uniqueness of a regular continued fraction for a given real number
1.5 Monotone behavior of convergents
1.6 Approximation rates of regular continued fractions
1.7 Exercises
Chapter 2 On Integer Geometry
2.1 Basic notions and definitions
2.1.1 Objects and congruence relation of integer geometry
2.1.2 Invariants of integer geometry
2.1.3 Index of sublattices
2.1.4 Integer length of integer segments
2.1.5 Integer distance to integer lines
2.1.6 Integer area of integer triangles
2.1.7 Index of rational angles
2.1.8 Congruence of rational angles
2.2 Empty triangles: their integer and Euclidean areas
2.3 Integer area of polygons
2.4 Pick’s formula
2.5 Integer-regular polygon
2.6 The twelve-point theorem
2.7 Exercises
Chapter 3 Geometry of Regular Continued Fractions
3.1 Classical construction
3.2 Geometric interpretation of the elements of continued fractions
3.3 Index of an angle, duality of sails
3.4 Exercises
Chapter 4 Complete Invariant of Integer Angles
4.1 Integer sines of rational angles
4.2 Sails for arbitrary angles and their LLS sequences
4.3 On complete invariants of angles with integer vertex
4.4 Equivalent tails of the angles sharing an edge
4.5 Two algorithms to compute the LLS sequence of an angle
4.5.1 Brute force algorithm
4.5.2 Explicite formulae for LLS sequences via given coordinates of the angle
4.6 Exercises
Chapter 5 Integer Trigonometry for Integer Angles
5.1 Definition of trigonometric functions
5.2 Basic properties of integer trigonometry
5.3 Transpose integer angles
5.4 Adjacent integer angles
5.5 LLS sequences for adjacent angles
5.6 Right integer angles
5.7 Opposite interior angles
5.8 Exercises
Chapter 6 Integer Angles of Integer Triangles
6.1 Integer sine formula
6.2 On integer congruence criteria for triangles
6.3 On sums of angles in triangles
6.4 Angles and segments of integer triangles
6.5 Examples of integer triangles
6.6 Exercises
Chapter 7 Minima of Quadratic Forms, the Markov Spectrum and the Markov-Davenport Characteristics
7.1 Calculation of minima of quadratic forms
7.2 Some properties of Markov spectrum
7.3 Markov numbers
7.4 Markov—Davenport characteristic
7.5 Exercises
Chapter 8 Geometric Continued Fractions
8.1 Definition of a geometric continued fraction
8.2 Geometric continued fractions of hyperbolic GL(2,R) matrices
8.3 Duality of sails
8.4 LLS sequences for hyperbolic matrices
8.5 Algebraic sails and their LLS cycles
8.5.1 Algebraic sails
8.5.2 LLS periods and LLS cycles of GL(2,Z) matrices
8.6 Computing LLS cycles of GL(2,Z) matrices
8.6.1 Differences of sequences
8.6.2 LLS cycles for SL(2,Z) matrices with positive eigenvalues
8.6.3 LLS cycles for GL(2,Z) matrices
8.7 Exercises
Chapter 9 Continuant Representation of GL(2,Z) Matrices
9.1 Generators of SL(2,Z) and the modular group
9.2 Basic properties of matrices Ma1,...,an
9.3 Matrices of GL(2,Z) in terms of continuants
9.4 An expression of matrices in terms of MS and MT
9.5 Exercises
Chapter 10 Semigroup of Reduced Matrices
10.1 Definition and basic properties of reduced matrices
10.1.1 Reduced matrices
10.1.2 Continuant representations of reduced matrices
10.1.3 A necessary and sufficient condition for a matrix to be reduced
10.1.4 LLS cycles of reduced matrices
10.2 Existence of reduced matrices in every integer conjugacy class of GL(2,Z)
10.3 Exercises
Chapter 11 Continued Fractions and SL(2,Z) Conjugacy Classes. Elements of Gauss’s Reduction Theory
11.1 Conjugacy classes of GL(2,Z) in general
11.2 Elliptic case
11.3 Parabolic case
11.4 Hyperbolic case
11.4.1 The set of reduced matrices integer conjugate to a given one
11.4.2 Complete invariant of integer conjugacy classes
11.4.3 Algebraicity of matrices with periodic LLS sequences
11.5 Computation of all reduced matrices integer conjugate to a given one
11.5.1 Explicit computation via LLS cycles
11.5.2 Algorithmic computation: Gauss Reduction theory
11.6 Statistical properties of reduced SL(2,Z) matrices
11.6.1 Complexity of reduced matrices
11.6.2 Frequencies of reduced matrices
11.7 Exercises
Chapter 12 Lagrange’s Theorem
12.1 The Dirichlet group
12.2 Construction of the integer nth root of a GL(2,Z) matrix
12.3 Pell’s equation
12.4 Periodic continued fractions and quadratic irrationalities
12.5 Exercises
Chapter 13 Gauss—Kuzmin Statistics
13.1 Some information from ergodic theory
13.2 The measure space related to continued fractions
13.2.1 Definition of the measure space related to continued fractions
13.2.2 Theorems on density points of measurable subsets
13.3 On the Gauss map
13.3.1 The Gauss map and corresponding invariant measure
13.3.2 An example of an invariant set for the Gauss map
13.3.3 Ergodicity of the Gauss map
13.4 Pointwise Gauss—Kuzmin theorem
13.5 Original Gauss—Kuzmin theorem
13.6 Cross-ratio in projective geometry
13.6.1 Projective linear group
13.6.2 Cross-ratio, infinitesimal cross-ratio
13.7 Smooth manifold of geometric continued fractions
13.8 Möbius measure on the manifolds of continued fractions
13.9 Explicit formulas for the Möbius form
13.10 Relative frequencies of edges of one-dimensional continued fractions
13.11 Exercises
Chapter 14 Geometric Aspects of Approximation
14.1 Two types of best approximations of rational numbers
14.1.1 Best Diophantine approximations
14.1.2 Strong best Diophantine approximations
14.2 Rational approximations of arrangements of two lines
14.2.1 Regular angles and related Markov—Davenport forms
14.2.2 Integer arrangements and their sizes
14.2.3 Discrepancy functional and approximation model
14.2.4 Lagrange estimates for the case of continued fractions with bounded elements
14.2.5 Periodic sails and best approximations in the algebraic case
14.2.6 Finding best approximations of line arrangements
14.3 Exercises
Chapter 15 Geometry of Continued Fractions with Real Elements and Kepler’s Second Law
15.1 Continued fractions with integer coefficients
15.2 Continued fractions with real coefficients
15.2.1 Broken lines related to sequences of arbitrary real numbers
15.2.2 Continued fractions related to broken lines
15.2.3 Geometry of continued fractions for broken lines
15.2.4 Proof of Theorem 4.16
15.3 Areal and angular densities for differentiable curves
15.3.1 Notions of real and angular densities
15.3.2 Curves and broken lines
15.3.3 Some examples
15.4 Exercises
Chapter 16 Extended Integer Angles and Their Summation
16.1 Extension of integer angles. Notion of sums of integer angles
16.1.1 Extended integer angles and revolution number
16.1.2 On normal forms of extended angles
16.1.3 Trigonometry of extended angles. Associated integer angles
16.1.4 Opposite extended angles
16.1.5 Sums of extended angles
16.1.6 Sums of integer angles
16.2 Relations between extended and integer angles
16.3 Proof of Theorem 6.9(i)
16.3.1 Two preliminary lemmas
16.3.2 Conclusion of the proof of Theorem 6.9(i)
16.4 Exercises
Chapter 17 Integer Angles of Polygons and Global Relations for Toric Singularities
17.1 Theorem on angles of integer convex polygons
17.2 Toric surfaces and their singularities
17.2.1 Definition of toric surfaces
17.2.2 Singularities of toric surfaces
17.3 Relations on toric singularities of surfaces
17.3.1 Toric singularities of n-gons with fixed parameter n
17.3.2 Realizability of a prescribed set of toric singularities
17.4 Exercises
Part II Multidimensional Continued Fractions
Chapter 18 Basic Notions and Definitions of Multidimensional Integer Geometry
18.1 Basic integer invariants in integer geometry
18.1.1 Objects and the congruence relation
18.1.2 Integer invariants and indices of sublattices
18.1.3 Integer volume of simplices
18.1.4 Integer angle between two planes
18.1.5 Integer distance between two disjoint planes
18.2 Integer and Euclidean volumes of basis simplices
18.3 Integer volumes of polyhedra
18.3.1 Interpretation of integer volumes of simplices via Euclidean volumes
18.3.2 Integer volume of polyhedra
18.3.3 Decomposition into empty simplices
18.4 Lattice Plücker coordinates and calculation of integer volumes of simplices
18.4.1 Grassmann algebra on R^n and k-forms
18.4.2 Plücker coordinates
18.4.3 Oriented lattices in R^n and their lattice Plücker embedding
18.4.4 Lattice Plücker coordinates and integer volumes of simplices
18.5 Ehrhart polynomials as generalized Pick’s formula
18.6 Integer-regular polyhedra
18.6.1 Definition of integer-regular polyhedra
18.6.2 Schläfli symbols
18.6.3 Euclidean regular polyhedra
18.6.4 Preliminary integer notation
18.6.5 Integer-regular polyhedra in arbitrary dimensions
18.7 Exercises
Chapter 19 On Empty Simplices, Pyramids, Parallelepipeds
19.1 Classification of empty integer tetrahedra
19.2 Classification of completely empty lattice pyramids
19.3 Two open problems related to the notion of emptiness
19.3.1 Problem on empty simplices
19.3.2 Lonely runner conjecture
19.4 Proof of White’s theorem and the empty tetrahedra classification theorems
19.4.1 IDC-system
19.4.2 A lemma on sections of an integer parallelepiped
19.4.3 A corollary on integer distances between the vertices and the opposite faces of a tetrahedron with empty faces
19.4.4 Lemma on one integer node
19.4.5 Proof of White’s theorem
19.4.6 Deduction of Corollary 19.3 from White’s theorem
19.5 Exercises
Chapter 20 Multidimensional Continued Fractions in the Sense of Klein
20.1 Background
20.2 Some notation and definitions
20.2.1 A-hulls and their boundaries
20.2.2 Definition of multidimensional continued fraction in the sense of Klein
20.2.3 Face structure of sails
20.3 Finite continued fractions
20.4 On a generalized Kronecker’s approximation theorem
20.4.1 Addition of sets in R^n
20.4.2 Integer approximation spaces and affine irrational vectors
20.4.3 Formulation of the theorem
20.4.4 Proof of the Multidimensional Kronecker’s approximation theorem
20.5 Polyhedral structure of sails
20.5.1 The intersection of the closures of A-hulls with faces of corresponding cones
20.5.2 Homeomorphic types of sails
20.5.3 Combinatorial structure of sails for cones in general position
20.5.4 A-hulls and quasipolyhedra
20.6 Two-dimensional faces of sails
20.6.1 Faces with integer distance to the origin equal one
20.6.2 Faces with integer distance to the origin greater than one
20.7 Exercises
Chapter 21 Dirichlet Groups and Lattice Reduction
21.1 Orders, units, and Dirichlet’s Unit Theorem
21.2 Dirichlet groups and groups of units in orders
21.2.1 Notion of a Dirichlet group
21.2.2 On isomorphisms of Dirichlet groups and certain groups of units
21.2.3 Dirichlet groups related to orders that do not have complex roots of unity
21.3 Calculation of a basis of the additive group Γ (A)
21.3.1 Step 1: preliminary statements
21.3.2 Step 2: application of the LLL-algorithm
21.3.3 Step 3: calculation of an integer basis having a basis of an integer sublattice
21.4 Calculation of a basis of the positive Dirichlet group Ξ+(A)
21.5 Lattice reduction and the LLL-algorithm
21.5.1 Reduced bases
21.5.2 The LLL-algorithm
21.6 Exercises
Chapter 22 Periodicity of Klein polyhedra. Generalization of Lagrange’s Theorem
22.1 Continued fractions associated to matrices
22.2 Algebraic periodic multidimensional continued fractions
22.3 Torus decompositions of periodic sails in R^3
22.4 Three single examples of torus decompositions in R^3
22.5 Examples of infinite series of torus decomposition
22.6 Two-dimensional continued fractions associated to transpose Frobenius normal forms
22.7 Some problems and conjectures on periodic geometry of algebraic sails
22.8 Generalized Lagrange’s Theorem
22.9 Littlewood and Oppenheim conjectures in the framework of multidimensional continued fractions
22.10 Exercises
Chapter 23 Multidimensional Gauss—Kuzmin Statistics
23.1 Möbius measure on the manifold of continued fractions
23.1.1 Smooth manifold of n-dimensional continued fractions
23.1.2 Möbius measure on the manifolds of continued fractions
23.2 Explicit formulae for the Möbius form
23.3 Relative frequencies of faces of multidimensional continued fractions
23.4 Some calculations of frequencies for faces in the two-dimensional case
23.4.1 Some hints for computation of approximate values of relative frequencies
23.4.2 Numeric calculations of relative frequencies
23.4.3 Two particular results on relative frequencies
23.5 Exercises
Chapter 24 On the Construction of Multidimensional Continued Fractions
24.1 Inductive algorithm
24.1.1 Some background
24.1.2 Description of the algorithm
24.1.3 Step 1a: construction of the first hyperface
24.1.4 Step 1b, 4: how decompose the polytope into its faces
24.1.5 Step 2: construction of the adjacent hyperface
24.1.6 Step 2: test of the equivalence class for the hyperface F′ to have representatives in the set of hyperfaces D
24.2 Deductive algorithms to construct sails
24.2.1 General idea of deductive algorithms
24.2.2 The first deductive algorithm
24.2.3 The second deductive algorithm
24.2.4 Test of the conjectures produced in the two-dimensional case
24.2.5 On the verification of a conjecture for the multidimensional case
24.3 An example of the calculation of a fundamental domain
24.4 Exercises
Chapter 25 Gauss Reduction in Higher Dimensions
25.1 Organization of this chapter
25.2 Hessenberg matrices and conjugacy classes
25.2.1 Notions and definitions
25.2.2 Construction of perfect Hessenberg matrices conjugate to a given one
25.2.3 Existence and finiteness of ς -reduced Hessenberg matrices
25.2.4 Families of Hessenberg matrices with given Hessenberg type
25.2.5 ς-reduced matrices in the 2-dimensional case
25.3 Complete geometric invariant of conjugacy classes
25.3.1 Continued fractions in the sense of Klein—Voronoi
25.3.2 Geometric complete invariants of Dirichlet groups
25.3.3 Geometric invariants of conjugacy classes
25.4 Algorithmic aspects of reduction to ς-reduced matrices
25.4.1 Markov—Davenport characteristics
25.4.2 Klein—Voronoi continued fractions and minima of MD-characteristics
25.4.3 Construction of ς-reduced matrices by Klein—Voronoi continued fractions
25.5 Diophantine equations related to the Markov—Davenport characteristic
25.5.1 Multidimensional w-sails and w-continued fractions
25.5.2 Solution of Equation 25.1
25.6 On reduced matrices in SL(3,Z) with two complexconjugate eigenvalues
25.6.1 Perfect Hessenberg matrices of a given Hessenberg type
25.6.2 Parabolic structure of the set of NRS-matrices
25.6.3 Theorem on asymptotic uniqueness of ς-reduced NRS-matrices
25.6.4 Examples of NRS-matrices for a given Hessenberg type
25.6.5 Proof of Theorem 25.43
25.6.6 Proof of Theorem 25.48
25.7 Open problems
25.8 Exercises
Chapter 26 Approximation of Maximal Commutative Subgroups
26.1 Rational approximations of MCRS-groups
26.1.1 Maximal commutative subgroups and corresponding simplicial cones
26.1.2 Regular subgroups and Markov—Davenport forms
26.1.3 Rational subgroups and their sizes
26.1.4 Discrepancy functional
26.1.5 Approximation model
26.1.6 Diophantine approximation and MCRS-group approximation
26.2 Simultaneous approximation in R3 and MCRS-group approximation
26.2.1 General construction
26.2.2 A ray of a nonreal spectrum operator
26.2.3 Two-dimensional golden ratio
26.3 Exercises
Chapter 27 Other Generalizations of Continued Fractions
27.1 Relative minima
27.1.1 Relative minima and the Minkowski—Voronoi complex
27.1.2 Minkowski—Voronoi tessellations of the plane
27.1.3 Minkowski—Voronoi continued fractions in R^3
27.1.4 Combinatorial properties of the Minkowski—Voronoi tessellation for integer sublattices
27.2 Farey addition, Farey tessellation, triangle sequences
27.2.1 Farey addition of rational numbers
27.2.2 Farey tessellation
27.2.3 Descent toward the absolute
27.2.4 Triangle sequences
27.3 Decompositions of coordinate rectangular bricks and O’Hara’s algorithm
27.3.1 Π-congruence of coordinate rectangular bricks
27.3.2 Criteron of Π-congruence of coordinate bricks
27.3.3 Geometric version of O’Hara’s algorithm for partitions
27.4 Algorithmic generalized continued fractions
27.4.1 General algorithmic scheme
27.4.2 Examples of algorithms
27.4.3 Algebraic periodicity
27.4.4 A few words about convergents
27.5 Branching continued fractions
27.6 Continued fractions and rational knots and links
27.6.1 Necessary definitions
27.6.2 Rational tangles and operations on them
27.6.3 Main results on rational knots and tangles
References
Index