nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Geometry of Continued Fractions

verfasst von: Oleg Karpenkov

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Computation in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Traditionally a subject of number theory, continued fractions appear in dynamical systems, algebraic geometry, topology, and even celestial mechanics. The rise of computational geometry has resulted in renewed interest in multidimensional generalizations of continued fractions. Numerous classical theorems have been extended to the multidimensional case, casting light on phenomena in diverse areas of mathematics. This book introduces a new geometric vision of continued fractions. It covers several applications to questions related to such areas as Diophantine approximation, algebraic number theory, and toric geometry.

The reader will find an overview of current progress in the geometric theory of multidimensional continued fractions accompanied by currently open problems. Whenever possible, we illustrate geometric constructions with figures and examples. Each chapter has exercises useful for undergraduate or graduate courses.

Inhaltsverzeichnis

Frontmatter

Regular Continued Fractions

Frontmatter

Chapter 1. Classical Notions and Definitions

Abstract

In this chapter we bring together some basic definitions and facts on continued fractions. After a small introduction we prove a convergence theorem for infinite regular continued fractions. Further, we prove existence and uniqueness of continued fractions for a given number (odd and even continued fractions in the rational case). Finally, we discuss approximation properties of continued fractions.

Oleg Karpenkov

Chapter 2. On Integer Geometry

Abstract

In many questions, the geometric approach gives an intuitive visualization that leads to a better understanding of a problem and sometimes even to its solution. This chapter is entirely dedicated to notions, definitions, and basic properties of integer geometry. We start with general definitions of integer geometry, and in particular, define integer lengths, distances, areas of triangles, and indexes of angles. Further we extend the notion of integer area to the case of arbitrary polygons whose vertices have integer coordinates. Then we formulate and prove the famous Pick’s formula that shows how to find areas of polytopes simply by counting points with integer coordinates contained in them. Finally we formulate one theorem in the spirit of Pick’s theorem: it is the so-called twelve-point theorem.

Oleg Karpenkov

Chapter 3. Geometry of Regular Continued Fractions

Abstract

Continued fractions play an important role in the geometry of numbers. In this chapter we describe a classical geometric interpretation of regular continued fractions in terms of integer lengths of edges and indices of angles for the boundaries of convex hulls of all integer points inside certain angles. In the next chapter we will extend this construction to construct a complete invariant of integer angles. For the geometry of continued fractions with arbitrary elements see Chap. 11.

Oleg Karpenkov

Chapter 4. Complete Invariant of Integer Angles

Abstract

In this chapter we generalize the classical geometric interpretation of regular continued fractions presented in the previous chapter to the case of arbitrary integer angles, constructing a certain integer broken line called the sail of an angle. We combine the integer invariants of a sail into a sequence of positive integers called an LLS sequence. From one side, the notion of LLS sequence extends the notion of continued fraction, about which we will say more in the next chapter. From another side, LLS sequences distinguish the integer angles. Sails and LLS sequences of angles play a central role in the geometry of numbers. In particular, we use LLS sequences in integer trigonometry and its relations to toric singularities and in Gauss’s reduction theory. F. Klein generalized the notion of sail to the multidimensional case to study integer solutions of homogeneous decomposable forms. We will study this generalization in the second part of this book.

In this chapter we give definitions of an integer sines, sails of integer angles and corresponding LLS sequences. We prove that an LLS sequence is a complete invariant of an integer angle.

Oleg Karpenkov

Chapter 5. Integer Trigonometry for Integer Angles

Abstract

We explain how to interpret regular continued fractions related to LLS sequences in terms of integer trigonometric functions. Integer trigonometry has many similarities to Euclidean trigonometry (for instance, integer arctangents coincide with real arctangents; the formulas for adjacent angles are similar). From another point of view they are totally different, since integer sines and cosines are positive integers; there are two right angles in integer trigonometry, etc. In this chapter we discuss basic properties of integer trigonometry. For rational angles we introduce definitions of integer sines, cosines, and tangents. In addition to rational integer angles, there are three types of irrational integer angles: R-irrational, L-irrational, and LR-irrational angles. It is only for R-irrational angles that we have a definition of integer tangents. The trigonometric functions are not defined for L-irrational and LR-irrational angles.

Oleg Karpenkov

Chapter 6. Integer Angles of Integer Triangles

Abstract

In this chapter we study properties of integer triangles. We start with the sine formula for integer triangles. Then we introduce integer analogues of classical Euclidean criteria for congruence for triangles and present several examples. Further, we verify which triples of angles can be taken as angles of an integer triangle; this generalizes the Euclidean condition α+β+γ=π for the angles of a triangle (this formula will be used later in Chap. 13 to study toric singularities). Then we exhibit trigonometric relations for angles of integer triangles. Finally, we give examples of integer triangles with small area.

Oleg Karpenkov

Chapter 7. Continued Fractions and $\operatorname{SL}(2,{\mathbb{Z}})$ Conjugacy Classes. Elements of Gauss’s Reduction Theory. Markov Spectrum

Abstract

In this chapter we study the structure of the conjugacy classes of $\operatorname{SL}(2,\mathbb{Z})$. Recall that $\operatorname{SL}(2,\mathbb{Z})$ is the group of all invertible matrices with integer coefficients and unit determinant. We say that the matrices A and B from $\operatorname{SL}(2,\mathbb{Z})$ are integer conjugate if there exists an $\operatorname{SL}(2,\mathbb{Z})$ matrix C such that B=CAC ⁻¹. A description of integer conjugacy classes in the two-dimensional case is the subject of Gauss’s reduction theory, where conjugacy classes are classified by periods of certain periodic continued fractions.

In this chapter we discuss the main elements of classical Gauss reduction theory based on the theory of geometric continued fractions studied in previous chapters. In particular, we formulate several open problems and show relations to the Markov spectrum.

Oleg Karpenkov

Chapter 8. Lagrange’s Theorem

Abstract

The aim of this chapter is to study questions related to the periodicity of geometric and regular continued fractions. The main object here is to prove Lagrange’s theorem stating that every quadratic irrationality has a periodic continued fraction, conversely that every periodic continued fraction is a quadratic irrationality. One of the ingredients to the proof of Lagrange theorem is the classical theorem on integer solutions of Pell’s equation

$$m^2-dn^2=1. $$

So, there is a strong relation between periodic fractions and quadratic irrationalities.

We start with the study of so-called Dirichlet groups, which are the subgroups of $\operatorname{GL}(2,\mathbb{Z})$ preserving certain pairs of lines. These groups are closely related to the periodicity of sails. The structure of a Dirichlet group is induced by the structure of the group of units in orders (we will discuss this later in more detail for the multidimensional case; here we restrict ourselves to the simplest two-dimensional case). We also show how to take nth roots of two-dimensional matrices using Gauss’s reduction theory. Finally we study the solutions of Pell’s equation and prove Lagrange’s theorem.

Oleg Karpenkov

Chapter 9. Gauss–Kuzmin Statistics

Abstract

It turns out that the frequency of a positive integer k in a continued fraction for almost all real numbers is equal to

$$\frac{1}{\ln2}\ln \biggl(1+\frac{1}{k(k+2)} \biggr), $$

i.e., for a general real x we have 42 % of 1, 17 % of 2, 9 % of 3, etc. This distribution is traditionally called the Gauss–Kuzmin distribution. In this chapter we describe two strategies to study distributions of elements in continued fractions. A classical approach to the Gauss–Kuzmin distribution is based on the ergodicity of the Gauss map. The second approach is related to the geometry of continued fractions and its projective invariance. It is interesting to note that the frequencies of elements has an unexpected interpretation in terms of cross-ratios. Further we generalize the second approach to the multidimensional case (see Chap. 19).

Oleg Karpenkov

Chapter 10. Geometric Aspects of Approximation

Abstract

The approximation properties of continued fractions have attracted researchers for centuries. There are many different directions of investigation in this important subject (the study of best approximations, badly approximable numbers, etc.). In this chapter we consider two geometric questions of approximations by continued fractions. First, we prove two classical results on best approximations of real numbers by rational numbers. Second, we describe a rather new branch of generalized Diophantine approximations concerning arrangements of two lines in the plane passing through the origin. In this chapter we use some material related to basic properties of continued fractions of Chap. 1, to geometry of numbers of Chap. 3, and to Markov–Davenport forms of Chap. 7.

Oleg Karpenkov

Chapter 11. Geometry of Continued Fractions with Real Elements and Kepler’s Second Law

Abstract

In the beginning of this book we discussed the geometric interpretation of regular continued fractions in terms of LLS sequences of sails. Is there a natural extension of this interpretation to the case of continued fractions with arbitrary elements? The aim of this chapter is to answer this question.

We start with a geometric interpretation of odd or infinite continued fractions with arbitrary elements in terms of broken lines in the plane having a selected point (say the origin). Further, we consider differentiable curves as infinitesimal broken lines to define analogues of continued fractions for curves. The resulting analogues possess an interesting interpretation in terms of a motion of a body according to Kepler’s second law.

Oleg Karpenkov

Chapter 12. Extended Integer Angles and Their Summation

Abstract

Let us start with the following question. Suppose that we have arbitrary numbers a, b, and c satisfying a+b=c. How do we calculate the continued fraction for c knowing the continued fractions for a and b? It turns out that this question is not a natural question within the theory of continued fractions. One can hardly imagine any law to write the continued fraction for the sum directly. The main obstacle here is that the summation of rational numbers does not have a geometric explanation in terms of the integer lattice. In this chapter we propose to consider a “geometric summation” of continued fractions, which we consider a summation of integer angles.

We start with the notion of extended integer angles that are the integer analogues of Euclidean angles of the type kπ+φ for arbitrary integers k. We classify extended angles by writing normal forms representing all of them. Then we define the M-sums of extended angles and integer angles. Further, we express the continued fractions of extended angles in terms of the corresponding normal forms. Finally, we conclude the proof of theorem on the sum of integer angles in integer triangles, which is based on the techniques introduced in this chapter.

Oleg Karpenkov

Chapter 13. Integer Angles of Polygons and Global Relations for Toric Singularities

Abstract

This chapter is dedicated to one important application of continued fractions to algebraic geometry, to complex projective toric surfaces. Toric surfaces are described in terms of convex polygons, and their singularities are in a straightforward correspondence with continued fractions. So it is really important to know relations between continued fractions of integer angles in a convex polygon. In Chap. 6 we proved a necessary and sufficient criterion for a triple of integer angles to be the angles of some integer triangle. In this chapter we prove the analogous statement for the integer angles of convex polygons. After a brief introduction of the main notions and definitions of complex projective toric surfaces, we discuss two problems related to singular points of toric varieties using integer geometry techniques. As an output one has global relations on toric singularities for toric surfaces.

Oleg Karpenkov

Multidimensional Continued Fractions

Frontmatter

Chapter 14. Basic Notions and Definitions of Multidimensional Integer Geometry

Abstract

In this chapter we generalize integer two-dimensional notions and definitions of Chap. 2. As in the planar case, our approach is based on the study of integer invariants. Further, we use them to study the properties of multidimensional continued fractions. First, we introduce integer volumes of polytopes, integer distances, and integer angles. Then we express volumes of polytopes, integer distances, and integer angles in terms of integer volumes of simplices. Finally, we show how to compute integer volumes of simplices via certain Plücker coordinates in the Grassmann algebra (this formula is extremely useful for the computation of multidimensional integer invariants of integer objects contained in integer planes). We conclude this chapter with a discussion of the Ehrhart polynomials, which one can consider a multidimensional generalization of Pick’s formula in the plane.

Oleg Karpenkov

Chapter 15. On Empty Simplices, Pyramids, Parallelepipeds

Abstract

An integer polyhedron is called empty if it does not contain integer points other than its vertices. In this chapter we give the classification of empty tetrahedra and the classification of pyramids whose integer points are contained in the base of pyramids in $\mathbb{R}^{3}$. Later in the book we essentially use the classification of the mentioned pyramids for studying faces of multidimensional continued fractions. In particular, the describing of such pyramids simplifies the deductive algorithm of Chap. 20 in the three-dimensional case. We continue with two open problems related to empty objects in lattices. The first one is a problem of description of empty simplices in dimensions greater than 3. The second is the lonely runner conjecture. We conclude this chapter with a proof of a theorem on the classification of empty tetrahedra.

Oleg Karpenkov

Chapter 16. Multidimensional Continued Fractions in the Sense of Klein

Abstract

In 1839, C. Hermite posed the problem of generalizing ordinary continued fractions to the higher-dimensional case. Since then, there have been many different definitions generalizing different properties of ordinary continued fractions. In this book we focus on the geometric generalization proposed by F. Klein. We start this chapter with an introduction of general notions and definitions. Further we consider the case of finite continued fractions in more details. As an additional tool we will use multidimensional Kronecker’s approximation theory, which we formulate and prove it in this chapter. After that we discuss homeomorphic and polyhedral structure of the sails in general. Finally we classify all two-dimensional faces with integer distance to the origin greater then one and say a few words about the two-dimensional faces with integer distance to the origin equals one.

Oleg Karpenkov

Chapter 17. Dirichlet Groups and Lattice Reduction

Abstract

The main reason for the periodicity of algebraic multidimensional sails, is a regular structure of the corresponding Dirichlet groups. The simplest case of two-dimensional Dirichlet groups was studied in Chap. 8 in the first part of this book. In this chapter we study the general multidimensional case. We start with formulation of Dirichlet’s unity theorem on the structure of the group of units in orders. Further we describe the relation between Dirichlet groups and groups of units. Then we show how to calculate bases of the Dirichlet groups and positive Dirichlet groups respectively. Finally we briefly discuss the LLL-algorithm on lattice reduction which helps to decrease the computational complexity in many problems related to lattices (including the calculation of Dirichlet group bases).

Oleg Karpenkov

Chapter 18. Periodicity of Klein Polyhedra. Generalization of Lagrange’s Theorem

Abstract

The sails of algebraic multidimensional continued fractions possess combinatorial periodicity due to the action of the positive Dirichlet group on the sails. In case of one-dimensional geometric continued fractions this periodicity is completely described by the periodicity of the corresponding LLS sequences. The questions related to periodicity of multidimensional algebraic sails are important in algebraic number theory, since they are in correspondence with algebraic irrationalities. In particular, periods of algebraic sails characterize the groups of units in the corresponding orders.

This chapter is dedicated to such problems. First, we associate to any matrix with real distinct eigenvalues a multidimensional continued fraction. Second, we discuss periodicity of associated sails in the algebraic case. Further, we give examples of periods of two-dimensional algebraic continued fractions and formulate several questions arising in that context. Then we state and prove a version of Lagrange’s theorem for multidimensional continued fractions. Finally, we say a few words about the relation of the Littlewood and Oppenheim conjectures to periodic sails.

Oleg Karpenkov

Chapter 19. Multidimensional Gauss–Kuzmin Statistics

Abstract

In this chapter we study the distribution of faces in multidimensional continued fractions. The one-dimensional Gauss–Kuzmin distribution was described in Chap. 9, where we discussed the classical approach via ergodic theory and a new geometric approach. Currently, an ergodic approach to the distribution of faces in continued fractions has not been developed. In fact, it is a hard open problem to find an appropriate generalization of the Gauss map suitable to the study of ergodic properties of faces of multidimensional sails. This problem can be avoided, and in fact, the information on the distribution of faces is found via the generalization of the geometric approach via Möbius measures described in the second part of Chap. 9 for the one-dimensional case. We discuss the multidimensional analogue of the geometric approach in this chapter.

Oleg Karpenkov

Chapter 20. On Construction of Multidimensional Continued Fractions

Abstract

In the first part of this book we saw that the LLS sequences completely determine all possible sails of integer angles in the one-dimensional case. The situation in the multidimensional case is much more complicated. Of course, the convex hull algorithms can compute all the vertices and faces of sails for finite continued fractions, but it is not clear how to construct (or to describe) vertices of infinite sails of multidimensional continued fractions in general. What integer-combinatorial structures could the infinite sails have? There is no single example in the case of aperiodic infinite continued fractions of dimension greater than one. The situation is better with periodic algebraic sails, where each sail is characterized by its fundamental domain and the group of period shifts (i.e., the positive Dirichlet group).

In this chapter we show the main algorithms that are used to construct examples of multidimensional continued fractions (finite, periodic, or finite parts of arbitrary sails). We begin with some definitions and background. Further, we discuss one inductive and two deductive algorithms to construct continued fractions. Finally, we demonstrate one of the deductive algorithms on a particular example.

Oleg Karpenkov

Chapter 21. Gauss Reduction in Higher Dimensions

Abstract

In this chapter we continue to study integer conjugacy classes of integer matrices in general dimension. Namely we are aiming to contribute to the following problem: describe the set of integer conjugacy classes in $\operatorname{SL}(n,{\mathbb{Z}})$. Gauss‘s reduction theory gives a complete geometric description of conjugacy classes for the case n=2, as we have already discussed in Chap. 7. In the multidimensional case the situation is more complicated. It is relatively simple to check whether two given matrices are integer conjugate, but to distinguish conjugacy classes is a much harder task. Using multidimensional Gauss’s reduction theory, we give the solution to this problem for matrices whose characteristic polynomials are irreducible over the field of rational numbers. We study questions related to the three-dimensional case in more detail.

Oleg Karpenkov

Chapter 22. Approximation of Maximal Commutative Subgroups

Abstract

We have already discussed some geometric approximation aspects in the plane in Chap. 10: we have studied approximations, first, of an arbitrary ray with vertex at the origin, and second, of an arrangement of two lines passing through the origin. In this chapter we briefly discuss an approximation problem of maximal commutative subgroups of $\operatorname{GL}(n,\mathbb{R})$ by rational subgroups. In general this problem touches the theory of simultaneous approximation and both subjects of Chap. 10. The problem of approximation of real spectrum maximal commutative subgroups has much in common with the problem of approximation of nondegenerate simplicial cones. So it is clear that multidimensional continued fractions should be a useful tool here. Also we would like to mention that the approximation problem is linked to the so-called limit shape problems.

In this chapter we give general definitions and formulate the problem of best approximations of maximal commutative subgroups. Further, we discuss the connection of three-dimensional maximal commutative subgroup approximation to the classical case of simultaneous approximation of vectors in $\mathbb{R}^{3}$.

Oleg Karpenkov

Chapter 23. Other Generalizations of Continued Fractions

Abstract

In this chapter we present some other generalizations of regular continued fractions to the multidimensional case. The main goal for us here is to give different geometric constructions related to such continued fractions (whenever possible). We say a few words about Minkowski–Voronoi continued fractions, triangle sequences related to Farey addition, O’Hara’s algorithm related to decomposition of rectangular parallelepipeds, geometric continued fractions, and determinant generalizations of continued fractions. Finally, we describe the relation of regular continued fractions to rational knots and links.

We do not pretend to give a complete list of generalizations of continued fractions. The idea is to show the diversity of generalizations.

Oleg Karpenkov

Backmatter

Titel: Geometry of Continued Fractions
verfasst von: Oleg Karpenkov
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-39368-6
Print ISBN: 978-3-642-39367-9
DOI: https://doi.org/10.1007/978-3-642-39368-6