Farey fractions have long been a subject of interest to mathematicians since their classification in 1816, providing a convenient way to order fractions and often showing up in unexpected places in Number Theory. Diophantine Approximation, the study of approximating irrational numbers with rational numbers, has many practical uses, including in public key cryptography (where it provides a method to attack the well-known RSA Cryptosystem) and the study of transcendental numbers. In this paper, we investigate the ties between Farey Sequences and Diophantine Approximation. We cover elementary results relating to Farey Fractions that become central to later parts of the paper. We then link the notion of Farey Sequences with the study of Diophantine Approximation. We build up to Hurwitzâ€™s Approximation Theorem, known to be an optimal theorem for approximating irrational numbers with rationals, using only Farey Fractions, and then discuss further improvements on Hurwitzâ€™s Theorem with a few adjustments. We continue this discussion via the natural extension to the Lagrange Spectrum, where we discuss the significance of Lagrange Numbers, their connection with Markov Numbers, and a few elementary results. Finally, we present a geometric interpretation of Farey Fractions known as Ford Circles, which can also be used to illustrate weaker Diophantine Approximation results.

## Introduction

The name Farey fractions^{1}^{ }comes from the English geologist John Farey Sr., who wrote a letter about these sequences that was published in the Philosophical Magazine in 1816. Interestingly enough, another mathematician, Charles Haros, independently published similar results in 1802, which was not known to Farey. Thus, the Farey Sequence is sometimes known as Haros-Farey Sequence. In the context of this paper, we use Farey Sequences to prove results relating to Diophantine Approximation.

Farey Sequences are also closely related to continued fractions^{2}. Their relationship is most clearly seen through the Stern-Brocot Tree^{3}, of which the left subtree containing the rational numbers between 0 and 1 is the Farey Tree. Most recently, continued fractions are being looked at in the context of p-adic numbers; a survey of recent work and open problems on the subject was written by Romeo^{4}. As weâ€™ll also see later in the paper, continued fractions have applications in cryptography as well.

Diophantine approximation^{5}, named after Diophantus of Alexandria, involves the approximation of real numbers using rational numbers. It is certainly not a topic limited to the scope of Farey Fractions. Most recently, James Maynard of Oxford University received a Fields Medal for his work in Diophantine Approximation, proving the Duffin-Schaeffer Conjecture^{6}, which is now aptly named the Koukoulopoulosâ€“Maynard Theorem.

Diophantine Approximation is also closely related to Transcendental Number Theory ^{6}, and many of the techniques and results from Diophantine Approximation also apply to Transcendental Number Theory. Diophantine Approximation also have some applications in cryptography â€“ for example^{7}, Worleyâ€™s Theorem in Diophantine Approximation provides the basis for Wienerâ€™s Attack on the RSA cryptosystem. As we will also see, this is not the only theorem in Diophantine Approximation contributing to Wienerâ€™s Attack!

In this paper weâ€™ll discuss and prove some interesting results that the Farey Fractions yield and their relationship to Diophantine Approximation. Weâ€™ll also cover some nice geometric interpretations of the Farey Sequences.

The assumed knowledge for the following paper is a thorough understanding of algebra and geometry.

## Definitions and Properties

**Definition 2.1.** We define the Farey Sequence of order , denoted , as the sequence of rational numbers of the form , where and are positive integers such that and (reduced form). We write the Farey Sequence in increasing order, starting from and ending with .

Example. The Farey Sequence of order 3 is the sequence of numbers:

Due to the bounds on Farey fractions, we’ll assume for the rest of the paper that fractions are in the range , unless otherwise specified, and that all fractions are in reduced form.

We can deduce one elementary property of the Farey Sequence.

**Corollary 2.2.** The number of elements in the Farey Sequence is , where is the Euler Totient Function, which counts the number of integers up to relatively prime to .

Proof: The +1 accounts for the fraction . Each element of the summation accounts for the number of fractions in reduced form with denominator in the interval .

More complicated questions arise when talking about the mechanics of the Farey Sequences. For example, given two rational numbers in the interval , are they ever consecutive in some Farey Sequence?

**Theorem 2.3.** Two distinct rational numbers and are consecutive in where , if and only if .

We will prove this in a few parts. First, we introduce the notion of the mediant of two fractions.

**Definition 2.4.** The mediant of two fractions and is defined as .

The mediant of two fractions offers an interesting property if these two fractions happen to be consecutive in some Farey Sequence.

**Proposition 2.5. **.

Proof: Observe that

which follows from . On the other side,

in a similar fashion.

**Corollary 2.6.** For consecutive Farey Fractions and , is in reduced form.

Proof: Observe that . Since is between and in some Farey Sequence, the fraction in reduced form cannot have a denominator less than or equal to . Suppose for contradiction that . Then

But , a contradiction to the consecutive nature of and , hence is in reduced form.

The key idea is that each fraction is the mediant of two other consecutive fractions of a previous sequence. This can also be phrased as:

**Corollary 2.7.** For consecutive Farey Fractions and , the fraction is the first fraction in any future sequences to come between these two fractions. Moreover, comes between these two fractions in the Farey Sequence . So, and remain consecutive in the Farey Sequences between and , inclusive.

This property is key to proving many identities about Farey Fractions. For example, now we can go ahead and prove Theorem 2.3. There is an algebraic proof using mediants, but it’s. nicer to consider a geometric interpretation of the mediant of two consecutive Farey fractions; we present it below.

Consider a model as in Figure 1 where two consecutive fractions and can be represented as the vectors and . Then, Corollary 2.7 is represented by the fact that no lattice points are present inside the parallelogram formed by the vectors, as shown above. Note that if a lattice point is inside the parallelogram, then there exists a fraction between and , namely ; moreover, this point satisfies , implying that a fraction arises before , a contradiction. Hence, no lattice points exist inside the parallelogram.

This gives rise to a proof of Theorem 2.3, which Amen^{9} presents as follows. From Pick’s Theorem, the area of the parallelogram with sides being the vectors and is equal to , where is the number of interior points in the parallelogram and is the number of boundary lattice points of the parallelogram. Note that and for consecutive Farey Fractions; arises from the vertices of the parallelogram, and we’ve already seen that . Hence,

At the same time, from the Shoelace Formula, the area of such a parallelogram is , hence .

In summary:

Corollary 2.8. If no integer lattice points exist strictly inside the parallelogram generated by the vectors and , where and , then and are consecutive fractions in the Farey Sequences up until .

## Diophantine Approximation

The central idea around this is approximating irrational numbers with rational numbers. From the denseness of the rational numbers, we know that, for every real number and , there exist integers with

As an example, we’ll use

We could get approximations by taking fractions like

but this is pointless. Diophantine Approximation aims to minimize the denominator while getting as close as possible to the value at hand.

**Theorem 3.1.** (Weak Diophantine Approximation.) For every positive irrational number and , there exist infinitely many with

Proof: Bound between any two rational numbers with the same denominator, i.e. choose such that

Then choose the fraction is closer to; since the sum of the distances from to both fractions adds to , it follows that either

or

In fact, this bound is tight because is irrational.

The choice of and can be made for any positive integer , hence infinitely many such approximations exist.

This bound is a little weak, however, as evidenced by the fact that it can be done for all choices of . If we take a look at the example of again, then is a very tight approximation for ; in particular,

This looks more like an approximation of or distance away; how close can we get?

In Theorem 3.1, we bounded by two fractions of the same denominator. Can we find a better bound, though? The answer is through Farey Fractions.

**Theorem 3.2.** For every positive irrational number and , there exist infinitely many with .

Proof: Without loss of generality, assume . (Otherwise, we can shift to be in this interval.) Now, in some Farey Sequence , bound by the two consecutive fractions and with . We claim that either

or

Suppose for contradiction that neither of these are true. Then we must have

At the same time, we also have

following from Theorem 2.3. Now observe that

Thus, we must have

This is a contradiction as ; no two consecutive Farey Fractions apart from and have the same denominator. This follows from Theorem 2.3; if , then , which is impossible for integers unless . Thus, at least one of the inequalities holds, implying that we’ve found an approximation.

In fact, as grows larger, the fractions generated by and , i.e., and so forth, will split the consecutive fraction interval in which is in infinitely many times; thus, infinitely many such approximations exist for .

As an interesting sidenote, the above theorem feeds into Legendre’s Theorem on Continued Fractions, which is as follows:

**Theorem 3.3.** (Legendre’s Theorem on Continued Fractions.) Consider a positive irrational number and with . Then is a convergent of the continued fraction expansion of .

Errpfi: See here^{10}.

Theorem 3.3 has applications in public key cryptography. In particular, Wiener’s Attack Attack^{11}, a method of attacking the RSA cryptosystem, is based on this theorem.

We now return to our discussion of Theorem 3.2. Do there exist better constants apart from 2 for As it turns out, there do. The proof once again follows from Farey Fractions!

**Theorem 3.4. **(Hurwitz’s Approximation Theorem) For every positive irrational number and , there exist infinitely many with

Proof: We’ll follow an algebraic proof of Zukin’s^{12}.

In particular, we’ll show that the above inequality is satisfied by one of the fractions

where and are consecutive in some Farey Sequence. Assume without loss of generality that is bounded by and .

For contradiction purposes, assume that

For simplicity sake, let and . Adding the first and third inequalities yields

and adding the second and third inequalities yields

Since and are consecutive in some Farey Sequence as is and , we can write

Clearing the denominators gives us

Now, adding the two yields

which can be rewritten as

Thus,

a contradiction because is irrational. Thus, at least one of the three original inequalities holds.

Lagrange Numbers

Consider the inequality

for a constant . We covered the cases of and . The natural question that arises is why these two numbers?

Recall in the discussion after Theorem 3.4 that is the maximum such that

has infinitely many approximations . Moreover, we mentioned that, for , the golden ratio cannot be approximated. What if we don’t consider and its associated irrationals (i.e. for a rational )? Then, we can improve our constant . In particular, infinitely many approximations for exist where

where is not one of ‘s associated rationals. So, in fact, we can generalize Corollary 3.4 to all numbers .

Now, just as is approximated with difficulty for , the value is approximated with difficulty using . In other words, there do not exist infinitely many approximations with

for . Now, once again barring and its associated rationals, we can increase the constant further.

These constants , i.e., constants that can be used barring “bad” irrational numbers, are known as Lagrange Numbers, denoted . Taking all these irrational numbers forms the Lagrange Spectrum. There’s a curious relationship^{13} with Lagrange Numbers and Markov Numbers that does not relate to Diophantine Approximation, but is nevertheless interesting. Markov Numbers describe all positive integers that are a solution to the equation

for positive integers . When rearranged in increasing order, it follows that

For example, we have due to the triple , so as expected. Moreover, due to the triple , so . Also, through this equation, we get the following obvious result:

\textbf{Corollary 4.1.}

Moreover, infinitely many Markov Numbers exist^{14}, due to an algorithm for generating a new triple given the triple satisfying the Markov Diophantine Equation. Hence:

**Corollary 4.2.** Infinitely many Lagrange Numbers exist. In other words, we can keep increasing the constant , which grows asymptotically towards 3.

## Ford Circles

When talking about Farey Sequences and Diophantine Approximations, it’s impossible not to mention Ford Circles as well. The topics of Farey Sequences and Diophantine Approximation go hand in hand because Farey Sequences deal with fractions of a maximum denominator, while Diophantine Approximation is about finding the closest approximation to an irrational number given limits on the denominator. Ford Circles provide the perfect geometric representation of these two concepts.

Figure 2 shows the Ford Circles diagram. Reading left to right, a few Farey Sequences can be seen when looking at the fractions written in each circle. Why is this?

Construction^{15}. For each in , draw the circle centered at with radius . (Do this as approaches .)

The main observation to be made from this picture is that two circles appear to be tangent if and only if their corresponding Farey Fractions are consecutive in some Farey Sequence.

This is the main result following from Ford Circles.

**Theorem 5.1.** Take two Farey Fractions and and consider the circles generated by the above construction. The circles are externally tangent if and only if and are consecutive in some .

Proof: For two circles to be tangent to each other, the sum of their radii must be equal to the distance between their centers. In other words, we must have

Squaring both sides and rearranging, this is equivalent to

Thus, we must have

which is Theorem 2.3. The theorem is bidirectional, so we reach our desired conclusion.

How does this relate to Diophantine Approximation? Consider any irrational number and represent it as an -coordinate. The idea is that there exist infinitely many Ford Circles that contain a point with as the -coordinate. Putting this more concretely:

**Corollary 5.2.** The line intersects infinitely many Ford Circles, for all irrational . Moreover, if intersects a Ford Circle whose center has coordinate , then approximates . Shifting by an integer yields the same result for all .

For example, let be an irrational number with . The line intersects one of the circles denoted by or in Figure 2. So, one of or approximates ; in other words, one of the following is true:

This offers an alternate geometric interpretation for why 2 is a viable constant in the inequality

for all irrational .

## References

- Farey sequence. Wikipedia(2024). https://en.wikipedia.org/ wiki/Farey_sequence. [↩]
- Continued fraction. Wikipedia(2024). https://en.wikipedia.org/wiki/Continued_fraction. [↩]
- Stern-Brocot tree. Wikipedia(2024). https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree. [↩]
- G. Romeo. Continued fractions in the Field of
*p*-adic Numbers. American Mathematical Society, Volume 61, no. 2, 343-371 (2024). https://www.ams.org/journals/bull/2024-61-02/S0273-0979-2024-01819-9/S0273-0979-2024-01819-9.pdf. [↩] - Diophantine Approximation. Wikipedia(2024). https://en.wikipedia.org/wiki/Diophantine_approximation. [↩]
- Duffin-Schaeffer Theorem. Wikipedia(2024). https://en.wikipedia.org/wiki/Duffin%E2%80%93Schaeffer_theorem. [↩] [↩]
- A. Dujella, B. Ibrahimpa?siÂ´c. On Worleyâ€™s theorem in Diophantine approximations. University of Zagreb(2008). https://web.math.pmf.unizg.hr/~duje/pdf/bernadinduje.pdf. [↩]
- R. Mikhael (2018). https://upload.wikimedia.org/wikipedia/commons/6/62/Mediant.png. [↩]
- J. Amen. Farey sequences, Ford circles and Pickâ€™s Theorem. MAT Exam Expository Papers (2006). https://digitalcommons. unl.edu/mathmidexppap/2. [↩]
- G. H. Hardy, E. M. Wright. An Introduction to the Theory of Numbers. Oxford (1975). [↩]
- M. J. Wiener, Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, Volume 36, no. 3, 553-558 (1990). https://ieeexplore.ieee.org/document/54902. [↩]
- D. Zukin. The Farey sequence and its niche(s). Whitman College (2016). www.whitman.edu/Documents/Academics/Mathematics/2016/Zukin.pdf. [↩]
- J. Enouen. What are the Markov and Lagrange Spectra? Ohio State University(2018). https://math.osu.edu/sites/math.osu.edu /files/What_is_2018_Markov_Lagrange_Spectra.pdf. [↩]
- Markov number. Wikipedia (2024). https://en.wikipedia.org/wiki/Markov_number. [↩]
- Ford circle. Wikipedia (2024). https://en.wikipedia.org/wiki/Ford_circle. [↩]