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