Farey Sequences Definition

tarix	24.06.2016
ölçüsü	216 Kb.

Farey Sequences

Definition

A Farey sequence is a complete sequence of reduced form rational fractions in the range of the form with for . The sequence is complete in the sense that, given a Farey sequence as defined above, we can find no rational fraction with such that .

Theorem

Given a Farey sequence , the following equality holds for :

where

Proof

Proof is by induction. For , we have the trivial Farey sequence where the above equality holds for . Given a Farey sequence , the sequence comprises a merge of and the sequence . If some is not in reduced form then it can be represented as a reduced form rational fraction with . But this fraction will already be a member of since is complete. Thus only reduced form fractions will be members of and will be merged with . The merge is such that all elements of are inserted in their correct position in the sequence in order to produce . (This observation enables an algorithm for the construction of for any to be designed.)

The complete proof will use the following 4 lemmas.

Lemma 1

There exists integers

and

such that

for

Proof

Choose . It is easy to verify that .

Lemma 2

After merging, no two consecutive members of will be consecutive members of . Thus we can always find some fraction such that and where .

Proof

This follows directly from Lemma 1 since .

Lemma 3

Given a Farey sequence , for any , .

Proof

This follows directly from the theorem .

This applies for all

and can be applied successively to create a sequence

.
But

and hence

for

.
From Lemma 2 we have some

such that

are consecutive members of

and where

and

are consecutive members of

and

is in reduced form.
Consider the rational fractions

. We can prove the following lemma.

Lemma 4

Proof

Assume

which follows from Lemma 3. But

Since

is an integer, our original assumption is false and

. Since

because there is no rational fraction

such that

is complete.
The second equality can be proved using a similar technique

Assume

which follows from Lemma 3. But

Since

is an integer, our original assumption is false and

. Since

because there is no rational fraction

such that

is complete.
This proves Lemma 4.

From Lemmas 3 and 4, the proof of the theorem follows directly.

This shows that the rational fraction inserted into obeys the equality given in the Theorem. However, we still have to consider preceding values to check whether the Theorem is generally applicable to .

There are 2 possibilities:

and

where

are consecutive terms in sequence

Taking the first possibility,

for some integer

because

Thus the equality holds for when is the third term in the triplet. An identical proof shows that the equality holds when is the first term of the triplet and so

Taking the second possibility

for some integer

Thus the equality holds in this case also.
We have thus proved by induction that if the equality holds for

, then it must hold for

which completes the proof of the Theorem.