The Farey Sequence and Its Niche(s) - Report

The Farey Sequence and Its Niche(s) 1 Contents 1 Introduction to the Farey Sequence 3 2 A History of the Farey Sequence 3 3 Properties of the Farey Sequence 4 4 The Farey Dissection 7 5 Lattices and Farey Terms 5.1 What is a Lattice? . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 The Fundamental Lattice . . . . . . . . . . . . . . . . . . . . . . 5.3 Properties of the Fundamental Lattice . . . . . . . . . . . . . . . 8 8 9 9 6 What are Ford Circles? 11 6.1 Using the Farey Sequence to Prove Tangency . . . . . . . . . . . 12 6.2 Calculating Ford Circles . . . . . . . . . . . . . . . . . . . . . . . 13 7 Rational Approximation of Irrational Numbers 13 7.1 Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7.2 Using the Farey Dissection . . . . . . . . . . . . . . . . . . . . . . 15 8 Hurwitz’s Theorem 17 8.1 Proving Hurwitz’s Theorem with the Farey Sequence . . . . . . . 17 8.2 Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . 18 9 Conclusion 20 2 Abstract: Discovered by Haros in 1802, but named after a geologist 14 years later the properties of the Farey sequence remain a useful tool in mathematical proof. This paper will introduce the Farey sequence and its basic properties. Then continue onto many of its applications in the mathematical world. While the Farey sequence is mostly used in proof. Its properties give way to some surprising coincidences which generates further curiosity for this unique series of rational numbers. 1 Introduction to the Farey Sequence The Farey Sequence, sometimes called the Farey series, is a series of sequences in which each sequence consists of rational numbers ranging in value from 0 to 1. The first sequence, denoted F1 is simply { 10 , 11 }. Then to create the nth row we look at the (n − 1)st row and between consecutive fractions aa0 and bb0 insert a+b [4]. a0 + b0 However the denominator of each term in Fn can be no larger than n. The first five sequences are: 0 1 F1 = { , } 1 1 0 1 1 F2 = { , , } 1 2 1 0 1 1 2 1 F3 = { , , , , } 1 3 2 3 1 0 1 1 1 2 3 1 F4 = { , , , , , , } 1 4 3 2 3 4 1 0 1 1 1 2 1 3 2 3 4 1 F5 = { , , , , , , , , , , } 1 5 4 3 5 2 5 3 4 5 1 Note that the terms of each sequence are always increasing in size and are in simplest terms (gcd(a, b) = 1). The Farey sequence appears in many different mathematical entities such as lattices and Ford circles. They can also be used to rationally approximate irrational numbers. I will start this paper by introducing its founder and some basic qualities of the Farey sequence, then show how the Farey sequence appears in the mathematical world, and finally end the paper with how the Farey sequence can be used in rational approximation. 2 A History of the Farey Sequence The story of the Farey sequence and how it came to be is actually quite comical. It is named after John Farey, a geologist from England who was the “first” person to note the properties of rational numbers which make up the sequences. In 3 October of 1801, Farey was out of a job so he returned to London where he published around sixty articles between the years 1804 and 1824 in the magazines Rees’s Encyclopaedia, The Monthly Magazine, and Philosophical Magazine[5]. One of the only relevant articles he published was in 1816, titled On a curious property of vulgar fractions. The article consisted of four paragraphs. The first notes the curious property. The second he defines and states the Farey sequence. In the third he gives an example of F5 . In the final paragraph Farey writes, “I am not acquainted, whether this curious property of vulgar fractions has been before pointed out?; or whether it may admit of some easy or general demonstration?; which are points on which I should be glad to learn the sentiments of some of your mathematical readers ...[5]. One of the readers of Farey’s article, Augustin-Louis Cauchy, provided the proof in one his writings the same year Farey’s article was released, and since it was believed that Farey was the first to notice this property the sequence was named after him. Farey in fact was not the first person to observe the properties of the Farey sequence. Charles Haros, in 1802 noticed the property and explained how to construct the 99th sequence. For these reasons Farey is not looked fondly upon in the mathematical community, in G H Hardy’s, A mathematicians apology, he writes, “... Farey is immortal because he failed to understand a theorem which Haros had proved perfectly fourteen years before ...”[5]. 3 Properties of the Farey Sequence I will now begin to to cover some of the basic properties of the Farey sequence. These properties will allow us to prove much more powerful things in the future. First things first let us start by finding an equation for the length of Fn . However, before define the equation we must do a quick review of the Euler φ function. Definition: The Euler φ function or Euler’s Totient function, written φ(n) is the number of non-negative integers less than n that are relatively prime to n. Two integers are relatively prime when their greatest common denominator is equal to 1. Note that φ(1) = 1[2] as the only number that shares a greatest common denominator with 1 is 1 itself. Using the Euler φ function we will be 4 able to create a formula for the order of Fn . However, before define the equation we must do a quick review of the Euler φ function. First, we must note that Fn contains all the terms from the previous sequence Fn−1 . Now we just need to find the additional terms that are new to Fn . Going back to our definition of the Farey sequences we know that the additional terms will be of the form m n . However, if m and n are not relatively prime then the fraction m will have already been contained within the previous sequence. For n example, suppose m = 2 and n = 4. Obviously 2 and 4 and are not relatively prime, and the fraction 24 reduces to 21 which first appears in the sequence F2 and every sequence after. Note that the only additional terms added will be the fractions m n where m and n are relatively prime. Thus the formula for the length of the Farey sequences are: |Fn | = |Fn−1 | + φ(n). Then using the fact that |F1 | = 1 we can finalize our formula as |Fn | = 1 + n X φ(k). k=1 While the equation for the order of Fn is fun, it does not actually have any relevance in the proofs that will be covered in the rest of the paper. I will now introduce a simple yet very important property of the Farey sequence which can be used to solve some of the most difficult proofs. Theorem 1. [4] 0 If ab and ab0 are consecutive fractions in the in the nth row then a0 b − b0 a = 1. Proof: We can prove this inductively. Observe that this is true for n = 1 whose only two fractions are 01 and 11 . 1 ∗ 1 − 0 ∗ 1 = 1. Now assume that this is true for the (n − 1)st row, and note that there are three possible outcomes for consecutive fractions. They will be either       a a0 a a + a0 a + a0 a0 , , , , or , b b0 b b + b0 b + b0 b0 . For our first pair of consecutive terms we already know that a0 b − b0 a = 1. For the next two we get: b(a + a0 ) − a(b + b0 ) = ab + a0 b − ab − b0 a = a0 b − b0 a = 1 a0 (b + b0 ) − b0 (a + a0 ) = a0 b + a0 b0 − b0 a − b0 a0 = a0 b − b0 a = 1 Thus, proven by induction, If the nth row then a0 b − b0 a = 1. a b and 5 a0 b0 are consecutive fractions in the in The greatest use of this property is that we will be able so simplify and manipulate many complicated equations and end with the result we wanted. For example, we can use this property to prove another interesting property of the Farey sequence. Theorem 2. [4] 0 If ab and ab0 are consecutive fractions in any row, then among all rational (a+a0 ) (b+b0 ) fractions with value between these two, denominator. Proof:Note that the fraction 0 a+a0 b+b0 is the unique one with smallest will be the first fraction to be inserted between ab and ab0 in each row of the sequence. The first sequence that the fraction will appear in will be Fb+b0 . Since the terms of each sequence are listed in order of size we know: a + a0 a0 a < < 0. 0 b b+b b Now consider any fraction x y between a b and a0 b0 . So a x a0 < < 0. b y b From Theorem 1 we know a0 x a a0 y − b0 x bx − ay 1 1 b + b0 a0 a x + ≥ 0 + = . − =( 0 − )+( − )= 0 0 b b b y y b by by b y by bb0 y Continuing: b + b0 a0 b − ab0 1 ≤ = 0 bb0 y bb0 bb This implies that y ≥ b + b0 . If y > b + b0 then x y does not have least 0 a b a b0 dominator among fractions between and . From the definition of a Farey sequence we have a0 y − b0 x = 1 and bx − ay = 1. Thus, we know x = a + a0 and y = b + b0 . 0 0 a a Thus, a+a b+b0 is the unique rational fraction laying between b and b0 . Using the property from Theorem 1 we can also prove another property which will eventually lead us to a basic theorem about rational approximation. Theorem 3. [4] 0 If ab and ab0 are Farey fractions contained in Fn such that no other Farey fraction of order n lies between them, then a a + a0 1 1 | − ≤ , |= b b + b0 b(b + b0 ) b(n + 1) and | a0 a + a0 1 1 − |= 0 ≤ 0 [4]. b0 b + b0 b (b + b0 ) b (n + 1) 6 Proof: Using the property from Theorem 1 we know that: |a(b + b0 ) − b(a + a0 )| a a + a0 |ab + ab0 − ab − ba0 | 1 | = | − = = . 0 0 0 b b+b b(b + b ) b(b + b ) b(b + b0 ) Then since we know b + b0 ≥ n + 1 we can replace a a + a0 1 | − |= b b + b0 b(b + b0 ) with 1 1 ≤ 0 b(b + b ) b(n + 1) We can repeat these steps to prove the second formula is also true. 4 The Farey Dissection The Farey dissection is another way to visualize the Farey sequence. First we must look back at our knowledge of the Real numbers. When asked to visualize the Real numbers many people will come up with a number line. This is not a bad way, however a number line can get quite long. Let’s simplify this by representing the number line with a circle with a circumference of 1. We can do this by using the function e2πix which maps a circle when x is in the interval [0, 1). Since the Farey sequence is located between 0 and 1, e2πix serves our purposes nicely. Even though we are only looking at the interval [0, 1] note that we can represent all of the real numbers with this circle.Below is a diagram of our circle representing the continuum with our point at 41 . ( 14 ) Adding the Farey sequence to this, the figure below is our circle with the terms of F4 imposed onto it. 7 ( 13 ) ( 14 ) ( 12 ) ( 01 , 11 ) ( 23 ) ( 34 ) From here we can take the mediants between each point. Where the mediant of two fractions ab and dc is equal to a+c b+d For F4 our mediants would be: 1 2 2 3 5 4 , , , , , 5 7 5 5 7 5 Note that these mediants do not occur in F4 and some of them do not occur in F5 . If we apply the mediants we can divide the circle up into arcs, which we will call Farey arcs. Where each arc is bounded by two consecutive mediants. This means each arc will contain exactly one term of F5 . The aggregate of Farey arcs we call the Farey dissection of the circle [1]. We’ll revisit the Farey dissection later when we start looking at rational approximation. 5 5.1 Lattices and Farey Terms What is a Lattice? First let us define what a lattice is. If you look up lattice in the dictionary you would find the definition to be “a structure of crossed wooden or metal strips usually arranged to form a diagonal pattern of open spaces between the strips”, however if we swing over to the mathematical definition we will see that it is “a partially ordered set in which every subset containing exactly two elements has a greatest lower bound or intersection and a least upper bound or union”. If you need a more visual description imagine a plane with origin point Q, then add two more points W and E such that Q, W and E are not collinear, or not on the same line. We can add another point R to complete the parallelogram QW ER. Then produce the sides of QW ER, which are QW , W E, ER, and RQ infinitely and space them all equally from their original lines. The result would be a plane of equal parralelograms, or a lattice.Furthermore, ”a lattice is a figure of lines. It defines a figure of points, viz. the system of points of intersection of 8 the lines, or lattice points. Such a system we call a point-lattice” [1] . Note that two different lattices can be define the same point-lattice. For example using our old lattice. The lattice based on QW and QE is equivalent to the lattice based on QW and QR. If two lattices determine the same point-lattice then they are said to be equivalent [1]. Going back to our visual interpretation of a lattice, we can see that any point of our original points Q, W, E and R could have been our origin point. Thus, lattices are independent of choice of origin and are symmetrical about any origin point. W Q 5.2 R E The Fundamental Lattice “There exists a lattice which is if formed (when the rectangular coordinate axes are given) by parallels to the axes at unit distances, dividing the plane into unit squares” [1]. This is called the fundamental lattice L, and the point-lattice which it determines, in other words, the ”system of points (x, y) with integral coordinates, the fundamental point-lattice λ” [1]. Since any point-lattice can be described as a system of numbers or vectors we know this system s a modulus, which is a system of numbers such that the sum or difference of any two numbers in the system will result in another number in the system. With this in mind let us suppose that our point W and E are the points (x1 , y1 ) and (x2 , y2 ). Thus, any point in the lattice formed by QW and QE where Q is the origin point will be x = mx1 + nx2 and y = my1 + ny2 , where m and n are integers. 5.3 Properties of the Fundamental Lattice At this point we can define a transformation as x0 = ax + by and y 0 = cx + dy, where a, b, c, d are given integers. So, any given point (x, y) in λ can be transformed into another point (x0 , y 0 ) by the transformation we defined above, which 9 means λ can transform into itself. If we solve for x and y from the above transformation we get: x= dx0 − by 0 , ad − bc y=− cx0 − ay 0 .[1] ad − bc Let 4 = ad − bc, and suppose that 4 = ±1. Then any integral values of x0 and y 0 will give integral values of x and y, where an integral value is a whole number. Also, every lattice point (x0 , y 0 ) will correspond to a lattice point (x, y). Another way to see this is if λ can be transformed into itself, then every integral (x0 , y 0 ) must give an integral (x, y). We will let (x0 , y 0 ) be equal to (1, 0) or (0, 1). Then 4|a 4 |b 4 |c 4 |d. From here we know that 42 |ad − bc which leads us to 42 |4 Thus, 4 = ±1. Theorem 4. [1] Suppose that P and Q are visible points of λ, and that 4 is the area of the parallelogram J defined by OP and OQ. Then: (i) if 4 = 1, there is no point of λ inside J; (ii) if 4 > 1, there is at least one point of λ inside J, and, unless that point is the intersection of the diagonals of J, at least two, one in each of the triangles into which J is divided by P G. c d Remember that one of the properties of the Farey sequence is that if are consecutive terms then a b and ad − bc = 1. Also, every term ab in the Farey sequence is in simplest terms, or (a, b) = 1. Let’s see if we can make a lattice out of consecutive Farey terms. Let’s use two terms from F4 . Remember that   0 1 1 1 2 3 1 F4 = , , , , , , . 1 4 3 2 3 4 1 Let’s choose the terms 12 and 13 . Lets designate these two terms to be our vectors, < 1, 3 > and < 1, 2 >. We can make a matrix , A, out of these two vectors 10  1 2  1 . 3 Finding the determinant we get 3(1) − 2(1) = 1. Since the determinant is equal to ±1 we know that the inverse of the matrix will be made up of integers. Where   3 −2 −1 A = −1 1 Since the inverse matrix   is made up of integers we can transform A into any a combination of integers b by multiplying A by a vector   x . y     a 5 For example if = b 2 we can simply calculate       3 −2 5 11 · = −1 1 2 −3 This means that multiplying A by a vector will yield every possible combination of two integers. Applying this to a lattice, γ, created by these two vectors means that γ will contain every possible combination of two integers in the form of points. Also, since the points are integers, this means that every point is visible. Since every point is visible this means that 4 = ±1. 6 What are Ford Circles? Ford circles are another mathematical entity in which the Farey sequence appear in. Like the Farey sequence, Ford circles are a sequence of circles that are all tangent to each other. Ford circles are created by choosing any two relatively prime integers, p and q. Then the Ford circle created from these two integers would be the circle C(p, q) of radius 2q12 centered at   p 1 , ± 2 .[6] q 2q We can start making a visual of the Ford circles by starting with integers 0 and 1, the Ford circle C(0, 1) would have radius 21 and be centered at (0, ± 12 ). We could continue choosing any integers possible and we would quickly end up with the image below. 11 Note that the sequence of Ford circles is infinite, thus the circles continue to get smaller until they can not be seen by the naked eye. 6.1 Using the Farey Sequence to Prove Tangency After reading about Ford circles you can immediately see some similarities between them and the Farey sequence. The first being that p and q are always relatively prime, while every each term of a Farey sequence consists of the a fraction made from two relatively prime positive integers. Using the Farey sequence we can prove the tangentiality of the Ford circles. Proof: [6] Suppose we have two Ford circles C(p, q) and C(p0 , q 0 ). First we will calculate the squared distance between their centers.  2  2 p p0 1 1 d2 = − 0 + − . q q 2q 2 2q 02 Next we will calculate the sum of the two circles radii. 1 1 + 02 . 2q 2 2q If we take the difference of d2 and s2 we are left with: s = r1 + r2 = (p0 q − pq 0 )2 − 1 . q 2 q 02 From here we can use the fact that if we have two consecutive Farey terms ab and dc then cb − ad = 1. Thus, if (p, q) and (p0 , q 0 ) are consecutive Farey terms then we know that (p0 q − pq 0 )2 − 1 ≥ 1. q 2 q 02 Thus, as long as the terms of the Ford circles match the terms of the Farey sequence, the circles will always be tangent to each other and we can find every Ford circle by looking at the Farey sequence. d2 − s2 = 12 6.2 Calculating Ford Circles To demonstrate this I will try my hand at creating the first few Ford circles made from Farey terms on Tikz. I will take terms from F3 : We already know that C(0, 1) has radius 12 and is centered at (0, ± 21 . 1 1 For C(1, 3) we get that its radius is 18 and it is centered at ( 31 , ± 18 ). 1 1 1 C(1, 2) has radius 8 and is centered at ( 2 , ± 8 . 1 1 and is centered at ( 23 , ± 18 ). C(2, 3) has radius 18 1 Finally, C(1, 1) has radius 2 and is centered at (1, ± 12 ). 7 Rational Approximation of Irrational Numbers For the rest of this paper I will be going over how the Farey sequence can be utilized in the rational approximation of irrational numbers. Rational approximation of irrational numbers is representing irrational numbers with rational √ numbers. For example, there are many ways to represent 2. In its decimal notation we get 1.41421356237..., now we can turn that into a fraction, however the denominator get quite large rather fast. The goal of rational approximation of irrational numbers is to represent an irrational number with a fraction √ with as small of a denominator as possible. For √ example, we can represent 2 with the fraction 57 . Although 75 is not equal to 2 it is within fourteen hundredths. Obviously the larger the denominator gets, the closer we will be able to come, however we will always strive for the most aesthetically pleasing answer. The Farey sequence can be used to prove theorems that state how close we can get to approximating rational numbers with an infinite amount of rational numbers. As the Farey sequence is mostly used in proofs, the rest of this paper will be very theorem and proof heavy. 7.1 Theorems At the beginning of my research I came across a series of theorems that resulted in a powerful theorem of rational approximation. These proofs to these theorems incorporate some of the properties of the Farey sequence which was covered at the beginning of the paper. 13 Theorem 5. [4] If n is a positive integer and x is a real number, there is a fraction that 0 ≤ n and 1 a ≤ x− b b(n + 1) a b such Proof: Recall Theorem 3 that 1 1 a a+c = − ≤ b b+d b(b + d) b(n + 1) Now, suppose that a real number x is between frations Theorem 3, a a+c 1 a ≤ ≤ x− − b b b+d b(n + 1) a b and a+c b+d . Then by Using theorem 5 we will be able to prove our first proof of rational approximation. Theorem 6. [4] If ξ is a real and irrational number, then there are infinitely many fractions a such that b a 1 ξ− < 2 b b Proof: For any integer n > 0 we can find an an and bn using Theorem 5 where 0 < bn ≤ n and an 1 ξ− < . bn bn (n + 1) Now we will assume by way of contradiction that there are only a finite number of distinct values. If this was true then there would be a value k such that ak an ≥ bn bk for all n > 0. This means that ξ− an ak ≥ ξ− . bn bk Since ξ is irrational, we know ξ− ak > 0. bk This means that we can find a large enough n such that 1 ak > ξ− . n+1 bk 14 This leads to the contradiction ξ− an ak 1 ak 1 ≤ ξ− ≤ . ≤ < ξ− bk bn b(n + 1) n+1 bk The result of this last proof is quite amazing. If we have a rational number with a denominator of 10, then we can use that number to be within a hundredth of an irrational number. If the denominator is increased to 1, 000, then we know it to be within a millionth of an irrational number. 7.2 Using the Farey Dissection We left off on the Farey dissection with the introduction of Farey arcs. Remember that the each Farey arc is bordered by a mediant of each Farey term in the sequence. For example the mediants of F4 are: 1 2 2 3 5 4 , , , , , . 5 7 5 5 7 5 Adding these to our circle with the terms of F4 we get: As we can see there is one term between each pair of mediants which is to be expected. Calculating the length of each Farey arc we must find the difference between consecutive mediants of Farey terms. Suppose ab11 , ab22 and ab33 are consecutive Farey terms and . The two mediants of these three terms will be: a1 + a2 a2 + a3 , b1 + b2 b2 + b3 Taking the difference of these two mediants we get: a2 b1 + a3 b1 + a3 b2 − a1 b2 − a1 b3 − a2 b3 . b1 b2 + b22 + b1 b3 + b2 b3 15 Due to the complications of the answer we can break this into two parts: a2 a1 + a2 1 a2 + a3 a2 1 − = and − = . b2 b1 + b2 b2 (b1 + b2 ) b2 + b3 b2 b2 (b2 + b3 ) Before going any further let me introduce two theorems which we will use in the future. Theorem 7. [1] If n > 1, then no two succesive terms of Fn have the same denominator. Proof : We can prove this by way of contradiction. Let ab11 and successive terms in a Farey sequence. Note that a1 + 1 ≤ a2 . Then a2 b2 be a1 a1 a1 + 1 a2 < < ≤ b1 b1 − 1 b1 b2 1 is also true. This means that b1a−1 is a term in between ab11 and ab22 , a contradiction. Thus, no two successive terms can have the same denominator. Theorem 8. [1] If a1 b1 and a2 b2 are two successive terms of Fn , then b1 + b2 > n. Proof : Observe that the mediant of the two terms is equal to lies within the interval   a1 a2 , . b1 b2 So if b1 + b2 < n, then and not a mediant. a1 +a2 b1 +b2 a1 +a2 b1 +b2 would be another Farey term between a1 b1 which and a2 b2 From these two theorems we get that if ab11 and ab22 are consecutive farey terms then: b1 + b2 < 2n and b1 + b2 > n. With these last two theorems and the two part equation for the length of a Farey arc we get another theorem. Theorem 9. [1] In the Farey dissection of order n, where n > 1, each part of the arc which contains the representative of ab has a length between 1 1 and . b(2n − 1) n+1 Finally we can use this to prove another theorem of rational approximation. Theorem 10. [1] If ξ is any real number, and n a positive integer, then there is an irreducible fraction ab such that 0 < b ≤ n, or ξ− ξ− 1 a ≤ b b(n + 1) a 1 ≤ . b b(2n − 1) 16 Proof : Suppose that 0 < ξ < 1, this means that ξ will fall within an interval bounded by two successive fractions of Fn , but more importantly a Farey arc. a2 +a3 2 Let’s suppose the Farey arc is bounded by ab11 +a +b2 and b2 +b3 . Then, ξ will be bounded by either     a1 + a2 a2 a2 a2 + a3 , or , . b1 + b2 b2 b2 b2 + b3 This theorem shows us that we can get even closer than b12 to an irrational number using the Farey sequence. Next we shall look at Hurwitz’s theorem which is the closest we can approximate an irrational number using rational approximation. 8 Hurwitz’s Theorem Hurwitz’s theorem is: Theorem 11. [4] Given any irrational number ξ, there exists infinitely many rational numbers hk such that ξ− h 1 <√ k 5k 2 has infinitely many rational solutions p q. During my research I came across two methods to solve Hurwitz’s theorem. One of these methods uses the Farey sequence while the second uses continued fractions. I will first go over the method that incorporates the Farey sequence and then introduce continued fractions. 8.1 Proving Hurwitz’s Theorem with the Farey Sequence Proof:[3] Let’s suppose that ξ ∈ (0, 1). We will show that if ab < ξ < consecutive Farey fractions from Fn , then one of the three fractions c d for two a c e , , b d f satisfies the inequality, where fe is equal to the mediant a+c b+d . Note that as we squeeze ξ between the Farey fractions of Fn we can simply continue increasing n which gives us infinite fractions that satisfy the inequality. Now we will prove the inequality by the way of contradiction. Let’s assume that none of the three fractions satisfy the inequality. This means that ξ− a 1 e 1 c 1 ≥ √ , ξ− ≥ √ , −ξ ≥ √ . b f 5b2 5f 2 d 5d2 17 Note that we are assuming that ξ lies between fe and dc , which makes ξ negative in the last equation due to applying the absolute values. Also note that equalities may occur. Now if we add the first and third inequality, and the second and third inequality we are left with the two inequalities     1 1 c a 1 1 e 1 1 c + 2 , + 2 . − ≥√ − ≥√ d b d d f d 5 b2 5 f2 Observe that c a bc − ad 1 c e cf − de 1 − = = , − = = . d b bd bd d f df df So now we are left with the two inequalities     1 1 1 1 1 1 1 1 √ ≥√ + ≥ + , . bd d2 df d2 5 b2 5 f2 √ √ If we mulitply the first inequality by 5b2 d2 and the second by 5d2 f 2 , then adding the results we are left with √ √ d 5(b + f ) = d 5(2b + d) ≥ b2 + 2d2 + f 2 = 2b2 + 3d2 + 2bd, which is equivalent to 0≥ 1 √ (( 5 − 1)d − 2b)2 . 2 √ This implies that ( 5 − 1)d − 2b = 0, which leads us to √ 5=1− 2b . d This means that 2b d is an irrational number which is a contradiction. Thus, Hurwitz’s theorem has been proven. 8.2 Continued Fractions A finite continued fraction can be denoted as < a0 , a1 , a2 , · · ·, an >. This is equivalent to the fraction a0 + 1 [4]. < a1 + a2 + · · ·an > Note that any finite continued fraction can be represented by a rational number, likewise we can represent any rational number as a finite continued fraction. Delving into infinite continued fractions we meet with my meager explanation of what a convergent is and what the nth convergent is. While the nth convergent is a rational number and is denoted as hknn , the value of any infinite continued 18 fraction is irrational. As the value of n increases, the nth convergent will be successively closer to the value of its infinite continued fraction, that is ξ− hn−1 hn < ξ− . kn kn−1 This is why continued fractions are so useful in approximating irrational numbers. This leads us to a handy theorem. Theorem 12. [4] Let ξ denote any irrational number. If there is a rational number rs with (r, s) = 1 and s ≥ 1 such that ξ− then ξ. r s r 1 < 2, s 2s is one of the convergents of the simple continued fraction expansion of From this thoerem we are lead to another. Theorem 13. [4] The nth convergent of x1 is the reciprical of the (n − 1)st convergent of x if x is any real number greater than 1. Proof: Let x =< a0 , a1 , · · · > and the convergents for x and 1 x 1 x =< 0, a0 , a1 , · · · > . If = 1, = a0 , h0n h0k are h0n = an−1 h0n−1 + h0n−2 k0 = 1, k1 = a1 , k10 and respectively, then h00 , h01 = 1, h02 = a1 , k00 hn hk kn−1 = an−1 kn−2 + kn−3 k20 0 0 kn0 = an−1 kn−1 + kn−2 = a0 a1 + 1, h0 = a0 , h1 = a0 a1 + 1, hn−1 = an−1 hn−2 + hn−3 . The rest of the theorem can be proven through mathematical induction. With this brief introduction to continued fractions we are now able to prove Hurwitz’s theorem. Proof:[4] For every three consecutive convergents beyond hkoo , at least one will satisfy the inequality we are hoping to prove. Let us define γn by γn = k 3 ξ − hn , kn so we need to prove that one of γn , γn−1 is less than will lie between one of these numbers we have ξ− √1 . 5 Since we know that ξ hn−1 hn hn−1 hn 1 = − + ξ− = kn kn−1 kn kn−1 kn kn−1 19 where the last equality follows from a previous theorem covered in Niven’s book 2 which I shall revisit next week. If we multiply this by kn2 kn−1 we get 2 γn kn−1 + γn−1 kn2 − kn kn−1 = 0. If we replace n with n + 1, we have 2 γn+1 kn2 + γn kn+1 − kn kn+1 = 0. Since we are dealing with an infinite continued fraction it is implied that kn+1 − kn−1 = an+1 kn , thus we have 2 γn2 a2n+1 + 2γn (γn−1 − γn+1 ) = 1 − a−2 n+1 (γn − 1 − γn + 1) . The right side of the equation must be less than 1 unless γn−1 = γn+1 . However, this is impossible because if the previous equation is true, then 2 kn−1 ξ− hn+1 hn−1 2 = kn+1 ξ− . kn−1 kn1 This is equivalent to 2 kn−1  hn−1 ξ− kn−1  = 2 kn+1   hn+1 . ξ− kn+1 Which implies that ξ is rational since kn−1 6= kn+1 , thus γn−1 6= γn+1 . We know that γn2 a2n+1 + 2γn (γn−1 − γn+1 ) < 1 from the above equation. Writing γ for min(γn − 1, γ, γn + 1), we have 2 γ 2 (a2n+1 + 4) ≤ γ 2 a2n+1 + 2γn (γn+1 + γn+1 ) < 1. Since an+1 ≥ 1, 5γ 2 < 1. Thus we have the desired result, 1 min(γn − 1, γ, γn + 1) < √ . 5 1 Hurwitz’s theorem, or √5k , is the closest we can approximate with infinite 2 1 we begin to only find finite rational numbers[4]. Once we get closer than √5k 2 examples of approximation. 9 Conclusion It has been a pleasure to work for an extended time with the Farey sequence.If I had more time to continue researching I would start by continuing to learn more about continued fractions. With more knowledge I would be able to understand 1 the theorem and proof that shows that √5k is the closest we will ever be 2 able to infinitely approximate an irrational number. From there on I would continue to investigate continued fractions uses in rational approximation. At the beginning I had no idea what I was getting into, but the characteristics of the Farey sequence are quite charming and I would gladly recommend anyone to put some time into studying this sequence of numbers that was discovered by a geologist. 20 Acknowledgments I would like to give thanks to everyone who has helped me during the time of this project and my time at Whitman. If it was not for taking Patrick Keef’s Math 260 class, I would have never started the path towards a degree in Mathematics. Thank you to Barry Balof for coordinating the Senior Project class and putting up with my numerous gramatical and mathematical errors. Thank you to Casey Schafer for being an amazing peer editing partner and a good friend. Lastly I would like to thank the rest of the Math department who made me look forward to going to class every day. I would not have succeeded if it was not for each and every one of these people. 21 References [1]G.H Hardy and E.M Wright. An Introduction to The Theory of Numbers. Oxford University Press, New York, 1938. [2]Patrick Keef and David Guichard. An Introduction to Higher Mathematics 2013. [3]Martin Klazar. Introduction to Number Theory. {http://kam.mff.cuni.cz/~klazar/ln_utc.pdf} [4]Ivan Niven and Herbert S. Zuckerman. An introduction to the Theory of Numbers. John Wiley Sons, Inc, New York, 1960. [5]JJ O’Connor E F Robertson. John Farey. February 2009. [6]Eric W. Weisstein. Ford Circle. {http://mathworld.wolfram.com/FordCircle.html} 22 Alphabetical Index Hardy, 4 Cauchy, 4 Charles Haros, 4 circumference, 7 continued fraction, 18 convergent, 18 Euler φ function, 4 Farey arc, 8, 15, 17 Farey dissection, 8, 16 farey fraction, 17 Farey Sequence, 3 Farey sequence, 16 fundamental lattice, 9 Hurwitz’s Theorem, 17 John Farey, 3 lattice, 8 mediant, 8, 15, 17 modulus, 9 point-lattice, 9 rational approximation, 13 23