Partial Franel Sums

R. Tomás CERN CH 1211 Geneva 23 Switzerland

                 rogelio.tomas@cern.ch

Abstract

We derive analytical expressions for the position of irreducible fractions in the Farey sequence F_{N} of order N for a particular choice of N, obtaining an asymptotic behavior with a lower error bound than in previous results when these fractions are in the vicinity of 0/1, 1/2, or 1/1.

Franel’s famous formulation of Riemann’s hypothesis uses the summation of distances between irreducible fractions and evenly spaced points in [0, 1]. We define “partial Franel sum” as a summation of these distances over a subset of fractions in F_{N} and we demonstrate that the partial Franel sum in the range [0, i/N], with N = lcm(1, 2, …, i), grows strictly slower than O(log N).

1 Introduction and statement of the main results

The Farey sequence F_{N} of order N is an ascending sequence of irreducible fractions between 0 and 1 whose denominators do not exceed N [1]. Riemann’s hypothesis implies that the irreducible fractions tend to be regularly distributed in [0, 1]. A formulation of this statement follows [2, 3],

∑_{n=1}^{|F_{N} |} |F_{N}(n) − \frac{n}{|F_{N}|}| = O(N^{\frac{1}{2} +ϵ}) ,

where F_{N}(n) is the n^{th} irreducible fraction in F_{N}. Here we define the partial Franel sum in the range [a_{1}/b_{1}, a_{2}/b_{2}] as

P (\frac{a_{1}}{b_{1}} , \frac{a_{2}}{b_{2}} ) = ∑_{n=I_{N} (a_{1}/b_{1})}^{I_{N} (a_{2}/b_{2})} |F_{N}(n) − \frac{n}{|F_{N}|}| ,

where I_{N} (a/b) is the position that a/b occupies in F_{N}. Dress [4] established the upper bound of the distance |F_{N}(n) − n/|F_{N}|| to be 1/N and to be located at F_{N}(2) = 1/N. This motivates the study of partial Franel sums in ranges including 1/N. Furthermore, another equivalent formulation of the Riemann’s hypothesis involving sums over irreducible fractions in the range [0, 1/4] follows [5],

∑_{n=1}^{I_{N} (1/4)} (F_{N}(n) − \frac{I_{N}(1/4)}{2|F_{N}|}) = O(N^{\frac{1}{2} +ϵ}) ,

showing again the relevance of the vicinity of 1/N.

Guthery [6, Chapter 6] attempted to find a closed expression for the i^{th} fraction in F_{N} ending in an “analytical hole”. This paper achieves this goal for fractions in the range [0, i/N], with N = lcm(1, 2, …, i) as explained in the following. Note that N = lcm(1, 2, …, i) = e^{ψ(i)}, where ψ(i) is the second Chebyshev function that fulfills the property ψ(i) = (1+o(1))i, and hence i = (1 + o(1)) log N.

Let the subsequence F_{N}^{a_{1}/b_{1}, a_{2}/b_{2}} of F_{N}, contain all the fractions of F_{N} in [a_{1}/b_{1}, a_{2}/b_{2}]. The cardinality of F_{N}^{a_{1}/b_{1}, a_{2}/b_{2}} is well known to be [7]

|F_{N}^{a_{1}/b_{1}, a_{2}/b_{2}} | = \frac{3}{π^{2}} (\frac{a_{2}}{b_{2}} − \frac{a_{1}}{b_{1}} ) N^{2} + O(N log N) .

As I_{N} (a_{2}/b_{2}) is the position that a_{2}/b_{2} occupies in F_{N}, it follows that

I_{N} (\frac{a_{2}}{b_{2}} ) = |F_{N}^{0/1, a_{2}/b_{2}} | = \frac{3}{π^{2}} \frac{a_{2}}{b_{2}} N^{2} + O(N log N) .  (1)

A first result of this paper is the derivation of an analytical expression for I_{N} (1/q) where N = lcm(1, 2, …, i) and N/i ≤ q ≤ N in Theorem 3 as

I_{N} (\frac{1}{q}) = 2 + N ∑_{j=1}^{i} \frac{φ(j)}{j} − qΦ(i) ,

where φ(i) is the totient function and Φ(i) is the summatory totient function defined as

Φ(i) = ∑_{j=1}^{i} φ(j) .

Theorem 3 also includes a more general expression giving the location of other fractions in F_{N}. To reach this relation a series of bijections are established in Theorem 1 between F_{i′}, with i′ ≤ i, and subsequences of F_{N} covering all elements in F_{N}^{0/1, 1/q}. Thanks to these bijections the cardinality of F_{N}^{0/1, 1/q} can be expressed as function of all |F_{i′}| as shown in Corollary 2. These bijections are illustrated in Table 1 for N = lcm(1, 2, …, 5) = 60. This result is used to derive the equivalent asymptotic estimate of (1) with a smaller residual error in Corollary 4 as follows:

I_{N} (\frac{1}{q}) = \frac{3}{π^{2}} q (\frac{N^{2}}{q^{2}} − \{\frac{N}{q} \}^{2}) + O (Nδ_{A} (⌊\frac{N}{q} ⌋)) ,

where {x} = x − ⌊x⌋ and δ_{A}(x) is a decreasing function defined as

δ_{A}(x) = exp (−A\frac{log^{0.6} x}{(log log x)^{0.2}} ) ,  (2)

where A > 0.

As the final result of this work Theorem 5 establishes that the partial Franel sum in the range [0, 1/(N/i)] is given by

P (\frac{0}{1}, \frac{1}{N/i}) = O(log(N)δ_{B}(log N)) ,

with 0 < B < A and again N = lcm(1, 2, …, i). Therefore, this partial Franel sum grows strictly slower than O(log N). If we would assume the Riemann hypothesis and a uniform distribution density of Farey elements in [0, 1], we would expect this partial Franel sum to decrease as O(log(N)/N^{1/2−ϵ}). Theorem 5 includes equivalent results for partial Franel sums in ranges including 1/2 or 1/1. The generalization to compute partial Franel sums in the vicinity of any irreducible fraction is explored. Earlier results of this work were applied to resonance diagrams [8, 9].

The following definitions are used in the rest of the paper. We say that two elements of a Farey sequence, a_{1}/b_{1} and a_{2}/b_{2}, form a Farey pair if |a_{1}b_{2} − a_{2}b_{1}| = 1. In this report we exceptionally allow 0/1 and 1/0 to form a Farey pair even if 1/0 is not a proper fraction. The mediant of a Farey pair, a_{1}/b_{1} and a_{2}/b_{2}, is given by

\frac{a_{1} + a_{2}}{b_{1} + b_{2}}

which is an irreducible fraction existing between a_{1}/b_{1} and a_{2}/b_{2} and forms two Farey pairs with a_{1}/b_{1} and a_{2}/b_{2}.

2 Results

Theorem 1. Let a_{1}/b_{1} and a_{2}/b_{2} be a Farey pair with b_{1} > b_{2}. Let N be multiple of b_{1}i(i+1) with i being a natural number such 0 < i < N. Let q be an integer fulfilling

\frac{N}{b_{1}(i + 1)} < q ≤ \frac{N}{b_{1}i} and b_{1}q + b_{2} ≤ N .

Let F′_{i} be a subsequence of F_{i} defined as

F′_{i} = \{\frac{h}{k} : \frac{h}{k} ∈ F_{i} , k(b_{1}q + b_{2}) − b_{1}h ≤ N\} ,

noting that for a_{1}/b_{1} = 0/1 and a_{2}/b_{2} = 1/0, F′_{i} = F_{i}.

There is a bijective map M between F′_{i} and F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} , given by

M : F′_{i} → F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} , \frac{h}{k} ↦ \frac{k(a_{1}q + a_{2}) − a_{1}h}{k(b_{1}q + b_{2}) − b_{1}h} .

M^{−1} : F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} → F′_{i} , \frac{u}{l} ↦ \frac{q(b_{1}u − la_{1}) + b_{2}u − la_{2}}{b_{1}u − la_{1}} .

The bijective map is order-preserving when a_{2}/b_{2} > a_{1}/b_{1} and order-inverting when a_{2}/b_{2} < a_{1}/b_{1}.

Proof. We first demonstrate that M is injective. The fractions \frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} and \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}} form a Farey pair since a_{1}/b_{1} and a_{2}/b_{2} form a Farey pair:

|(a_{1}q + a_{2})(b_{1}(q − 1) + b_{2}) − (b_{1}q + b_{2})(a_{1}(q − 1) + a_{2})| = |b_{2}a_{1} − a_{2}b_{1}| = 1 .

Let u/l be the image of h/k under M,

\frac{u}{l} = \frac{k(a_{1}q + a_{2}) − a_{1}h}{k(b_{1}q + b_{2}) − b_{1}h} .

By virtue of this expression u/l is obtained by applying the mediant operation successively between \frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} and \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}} in the same fashion as h/k is obtained by applying the mediant between 0/1 and 1/1, meaning

\frac{h}{k} = \frac{(k − h) · 0 + h · 1}{(k − h) · 1 + h · 1} ,
\frac{u}{l} = \frac{(k − h) · (a_{1}q + a_{2}) + h · (a_{1}(q − 1) + a_{2})}{(k − h) · (b_{1}q + b_{2}) + h · (b_{1}(q − 1) + b_{2})} .

Therefore u/l is a Farey fraction in the interval of interest:

[\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} , \frac{a_{1}(q − 1) + a_{2}}{b_{1}(q − 1) + b_{2}} ] .

The fraction u/l belongs to F_{N} by definition of the domain F′_{i}, meaning that h/k belonging to F′_{i} needs l ≤ N. Therefore M is injective.

Now we demonstrate that M^{−1} is also injective. Let u/l belong to F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} and assume a_{2}/b_{2} > a_{1}/b_{1}, so that

\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} ≤ \frac{u}{l} ≤ \frac{a_{1}(q − 1) + a_{2}}{b_{1}(q − 1) + b_{2}} .  (3)

Let h/k be the image of u/l under M^{−1},

\frac{h}{k} = \frac{q(b_{1}u − la_{1}) + ub_{2} − la_{2}}{b_{1}u − la_{1}} .  (4)

This equality implies gcd(h, k)= gcd(ub_{2} − la_{2}, b_{1}u − la_{1}). Using

gcd(u, l) = gcd(a_{1}, b_{1}) = gcd(a_{2}, b_{2}) = 1 ,

a_{2}b_{1} −a_{1}b_{2} = 1, and known equalities [10] implies gcd(h, k) = 1. Hence, h/k is an irreducible fraction. Furthermore, operating with the inequalities in (3):

q(b_{1}u − la_{1}) ≥ −(ub_{2} − la_{2}) ≥ (b_{1}u − la_{1})(q − 1),

and therefore 0 ≤ h ≤ k. This shows that h/k belongs to F_{k}. In the following we demonstrate that k ≤ i so that h/k belongs to F_{i} too.

From relations (3) and (4)

k = b_{1}u − la_{1} ≤ b_{1}l\frac{a_{1}(q − 1) + a_{2}}{b_{1}(q − 1) + b_{2}} − la_{1} = \frac{l}{b_{1}(q − 1) + b_{2}}

and using that l ≤ N and b_{1}(q − 1) ≥ \frac{N}{i+1}, which derives from q > \frac{N}{b_{1}(i+1)},

k ≤ \frac{N}{\frac{N}{i+1} + b_{2}} = \frac{i + 1}{1 + \frac{i+1}{N}b_{2}} < i + 1 .

If b_{2} > 0 this implies k ≤ i and gathering the above results 0 ≤ h ≤ k ≤ i and gcd(h, k)=1, hence h/k ∈ F_{i}. To demonstrate that h/k belongs to F′_{i} it is easy to verify that k(b_{1}q + b_{2}) − b_{1}h ≤ N.

If b_{2} = 0 we are in the exceptional case included in this report of a_{1}/b_{1} = 0/1 and a_{2}/b_{2} = 1/0, that implies h/k = (qu − l)/u. Note that k = u. We only need to show that k ≤ i also in this case. From the inequalities in (3) and \frac{N}{i} ≥ q > \frac{N}{i+1},

\frac{i}{N} ≤ \frac{1}{q} ≤ \frac{u}{l} ≤ \frac{1}{q − 1} ≤ \frac{i + 1}{N} .

The fraction (i+1)/N is not irreducible, as N is taken as a multiple of i(i+1), and therefore it does not belong to F_{N}. Similarly for i/N when i > 1. In the range [i/N, (i + 1)/N] there cannot be fractions with denominator N other than 1/N when i = 1. Therefore if i = 1 we directly have k = u ≤ i and for i > 1 we have l ≤ N − 1 and hence

k = u ≤ l\frac{i + 1}{N} ≤ i .

Corollary 2. The cardinalities of F_{i}, F′_{i} and F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} are related as follows:

• If q = N/(b_{1}i), then

|F_{i}| ≥ |F′_{i}| = |F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} | > |F_{i}| − i .

• If q < N/(b_{1}i) or b_{2} = 0, then

|F_{i}| = |F′_{i}| = |F_{N}^{\frac{a_{1}q+a_{2}}{b_{1}q+b_{2}} , \frac{a_{1}(q−1)+a_{2}}{b_{1}(q−1)+b_{2}}} | .

Proof. The first inequality is evident from the definition of F′_{i}. The first equality derives from the bijective map in Theorem 1.

If q = N/(b_{1}i), let u/l be the image of h/k via the map M in Theorem 1, then l = k(N/i + b_{2}) − b_{1}h. To prove that |F′_{i}| > |F_{i}| − i we should count how many h/k ∈ F_{i} fulfill k(N/i + b_{2}) − b_{1}h > N. Dividing both sides of the later inequality by k and operating we obtain

b_{2} − b_{1} \frac{h}{k} > \frac{N}{k} − \frac{N}{i} = N \frac{i − k}{ki} ,

b_{2} ≥ b_{2} − b_{1} \frac{h}{k} > N \frac{i − k}{ki} ≥ 0 .

To fulfill these inequalities it is required that k = i. Otherwise for any k < i and recalling that N is a multiple of b_{1}i(i + 1):

b_{2} > N \frac{i − k}{ki} ≥ b_{1} \frac{i + 1}{k}(i − k) > b_{1} ,

which is inconsistent with the assumption b_{2} < b_{1} in Theorem 1. Then, k = i implies h/i < b_{2}/b_{1} < 1 and in F_{i} there are fewer than i irreducible fractions of the form h/i below b_{2}/b_{1}, hence |F′_{i}| > |F_{i}| − i.

If q < N/(b_{1}i) we define g > 0 such that q = N/(b_{1}i) − g; therefore, l = k(N/i − gb_{1} + b_{2}) − b_{1}h. Now, we need to count how many h/k in F_{i} have l > N,

b_{2} − b_{1} \frac{h}{k} − b_{1}g > N \frac{i − k}{ki} ,

and there are no h/k which can fulfill this equation as b_{2} − b_{1}g < 0. Hence, |F_{i}| = |F′_{i}| when q < N/(b_{1}i).

If b_{2} = 0 we should show that there are no h/k in |F_{i}| fulfilling kb_{1}q − b_{1}h > N. The largest possible value of q is N/(b_{1}i) and therefore kb_{1}q − b_{1}h ≤ kN/i − b_{1}h < N, for i > 1, so there is no h/k fulfilling the previous condition and |F_{i}| = |F′_{i}|. Note that i = 1 and h/k = 0/1 would not have given kb_{1}q − b_{1}h > N as b_{1}q + b_{2} ≤ N from the assumptions in Theorem 1.

Theorem 3. Let N = b_{1}lcm(1, 2 …, i_{max}), \frac{N}{b_{1}(i + 1)} < q ≤ \frac{N}{b_{1}i}, with a_{1}/b_{1} and a_{2}/b_{2}

forming a Farey pair, b_{1} > b_{2} and i < i_{max}. Then

• For b_{1} > 1:

I_{N} (\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} ) = I_{N} (\frac{a_{1}}{b_{1}} ) + s (\frac{N}{b_{1}} ∑_{j=1}^{i} \frac{φ(j)}{j} − qΦ(i)) + O(i^{2}) ,  (5)

with s = +1 when a_{1}/b_{1} < a_{2}/b_{2} and s = −1 otherwise.

• For a_{1}/b_{1} = 0/1 and a_{2}/b_{2} = 1/0:

I_{N} (\frac{1}{q}) = 2 + N ∑_{j=1}^{i} \frac{φ(j)}{j} − qΦ(i) .

Proof. To simplify equations we assume s = +1 in the following. We count the number

of elements in F_{N}^{\frac{a_{1}}{b_{1}} , \frac{a_{1}q+a_{2}}{b_{1}q+b_{2}}} using the bijective maps described in Theorem 1 and adding up the cardinalities of the sets involved from Corollary 2. Thanks to the fact that N is a multiple of all natural numbers i′ such that i′ ≤ i we can establish bijections between F′_{i}

and F_{N}^{\frac{a_{1}p+a_{2}}{b_{1}p+b_{2}} , \frac{a_{1}(p−1)+a_{2}}{b_{1}(p−1)+b_{2}}} where p can take all values fulfilling \frac{N}{b_{1}(i′ + 1)} < p ≤ \frac{N}{b_{1}i′}, covering all

elements in F_{N}^{\frac{a_{1}}{b_{1}} , \frac{a_{1}q+a_{2}}{b_{1}q+b_{2}}} when scanning over all i′ ≤ i and the corresponding p. For a given i′ the number of values p takes is given by

\frac{N}{b_{1}i′} − \frac{N}{b_{1}(i′ + 1)} = \frac{N}{b_{1}} (\frac{1}{i′} − \frac{1}{i′ + 1}) .

In a first step we compute the number of elements in F_{N}^{\frac{a_{1}}{b_{1}} , \frac{a_{1}q′+a_{2}}{b_{1}q′+b_{2}}} with q′ = N/(b_{1}i),

I_{N} (\frac{a_{1}q′ + a_{2}}{b_{1}q′ + b_{2}} ) − I_{N} (\frac{a_{1}}{b_{1}} ) = \frac{N}{b_{1}} ∑_{i′=1}^{i−1} (\frac{1}{i′} − \frac{1}{i′ + 1}) (|F′_{i′}| − 1)

= \frac{N}{b_{1}} ∑_{i′=1}^{i−1} [(\frac{1}{i′} − \frac{1}{i′ + 1}) Φ(i′) + O(i′)]

= \frac{N}{b_{1}} ∑_{j=1}^{i−1} \frac{φ(j)}{j} − \frac{N}{b_{1}} \frac{Φ(i − 1)}{i} + O(i^{2}) .

In particular, when b_{2} = 0 the term O(i^{2}) does not appear according to Corollary 2. In a

second step we compute the number of elements in F_{N}^{\frac{a_{1}q′+a_{2}}{b_{1}q′+b_{2}} , \frac{a_{1}q+a_{2}}{b_{1}q+b_{2}}} , that is, Φ(i)(q′−q)+O(i). Adding both contributions gives

I_{N} (\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} ) − I_{N} (\frac{a_{1}}{b_{1}} ) = \frac{N}{b_{1}} ∑_{j=1}^{i−1} \frac{φ(j)}{j} − \frac{N}{b_{1}} \frac{Φ(i − 1)}{i}

+ Φ(i) (\frac{N}{b_{1}i} − q) + O(i^{2})

= \frac{N}{b_{1}} ∑_{j=1}^{i} \frac{φ(j)}{j} − qΦ(i) + O(i^{2}) ,

which demonstrates the theorem for s = 1. For s = −1, following the same steps leads to the desired result.

Corollary 4. Let N = b_{1}lcm(1, 2, …, i_{max}) and \frac{N}{b_{1}(i + 1)} < q ≤ \frac{N}{b_{1}i}, with i < i_{max}. Then,

I_{N} (\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} ) = I_{N} (\frac{a_{1}}{b_{1}} ) + s\frac{3}{π^{2}} q (\frac{N^{2}}{b_{1}^{2}q^{2}} − \{\frac{N}{b_{1}q} \}^{2}) + O(Nδ_{A}(i)) ,

with δ_{A}(x) defined in (2). In particular, for a_{1}/b_{1} = 0/1 and a_{2}/b_{2} = 1/0,

I_{N} (\frac{1}{q}) = \frac{3}{π^{2}} q (\frac{N^{2}}{q^{2}} − \{\frac{N}{q} \}^{2}) + O(Nδ_{A}(i)) ,

and for a_{1}/b_{1} = 1/2 and a_{2}/b_{2} = 1/1,

I_{N} (\frac{q + 1}{2q + 1}) = \frac{|F_{N}|}{2} + \frac{3}{π^{2}} q (\frac{N^{2}}{2^{2}q^{2}} − \{\frac{N}{2q} \}^{2}) + O(Nδ_{A}(i)) .

Proof. The following known relations [11, 12] are needed:

∑_{k=1}^{N} φ(k) = \frac{3}{π^{2}} N^{2} + E(N),  (6)

∑_{k=1}^{N} \frac{φ(k)}{k} = \frac{6}{π^{2}} N + H(N) ,
E(x) = O(x log^{2/3} x(log log x)^{4/3}) ,
E(x) = xH(x) + O(xδ_{A}(x)) ,

with A > 0 and δ_{A}(x) is a decreasing factor. From the definitions of i, q, and N it follows that

i = ⌊\frac{N}{qb_{1}} ⌋ = \frac{N}{qb_{1}} + O(1) ,
i < i_{max} = (1 + o(1)) log N/b_{1} .

Inserting the above equalities in expression (5) of Theorem 3,

I_{N} (\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} ) = I_{N} (\frac{a_{1}}{b_{1}} ) + s\frac{N}{b_{1}} \frac{6}{π^{2}} i − sq \frac{3}{π^{2}} i^{2} + s\frac{N}{b_{1}} H(i) − sqE(i) + O(i^{2})
= I_{N} (\frac{a_{1}}{b_{1}} ) + s\frac{N}{b_{1}} \frac{6}{π^{2}} i − sq \frac{3}{π^{2}} i^{2} + sq(iH(i) − E(i)) + O(i^{2})
= I_{N} (\frac{a_{1}}{b_{1}} ) + s\frac{N}{b_{1}} \frac{6}{π^{2}} i − sq \frac{3}{π^{2}} i^{2} + O(Nδ_{A}(i))
= I_{N} (\frac{a_{1}}{b_{1}} ) + s\frac{3}{π^{2}} \frac{N^{2}}{b_{1}^{2}q} − s\frac{3}{π^{2}} q \{\frac{N}{b_{1}q} \}^{2} + O(Nδ_{A}(i)) .

Theorem 5. Let N be N = b_{1}lcm(1, 2, …, i). Then the partial Franel sum over all Farey

fractions in the range [\frac{a_{1}}{b_{1}} , \frac{a_{1} \frac{N}{b_{1}i} + a_{2}}{b_{1} \frac{N}{b_{1}i} + b_{2}} ] is given by the following expressions:

• For a_{1}/b_{1} = 0/1, a_{2}/b_{2} = 1/0 and for a_{1}/b_{1} = 1/2, a_{2}/b_{2} = 0/1:

P (\frac{0}{1}, \frac{1}{N/i}) = ∑_{j=1}^{I_{N}(\frac{1}{N/i})} |F_{N}(j) − \frac{j}{|F_{N}|}| = O(log(N)δ_{B}(log N)) ,

P (\frac{1}{2}, \frac{N/(2i)}{N/i + 1}) = ∑_{j=I_{N}(\frac{1}{2})}^{I_{N}(\frac{N/(2i)}{N/i+1})} |F_{N}(j) − \frac{j}{|F_{N}|}| = O(log(N)δ_{B}(log N)) ,

with 0 < B < A. The same result holds for a_{1}/b_{1} = 1/2, a_{2}/b_{2} = 1/1.

• For b_{1} > 2 and b_{2} < b_{1}:

∑_{j=I_{N} ( \frac{a_{1}}{b_{1}} )}^{I_{N} ( \frac{a_{1} \frac{N}{b_{1}i} +a_{2}}{b_{1} \frac{N}{b_{1}i} +b_{2}} )} |F_{N}(j) − \frac{j}{|F_{N}|}| ≤ |\frac{a_{1}}{b_{1}} − \frac{I_{N} (\frac{a_{1}}{b_{1}} )}{|F_{N}|}| O(iN) + O(iδ_{B}(i)) ,

which cannot be further developed as no general expression for I_{N}(a_{1}/b_{1}) is known.

Proof. By virtue of Theorem 1 the partial Franel sum under study is written as

P (\frac{a_{1}}{b_{1}} , \frac{a_{1} \frac{N}{b_{1}i} + a_{2}}{b_{1} \frac{N}{b_{1}i} + b_{2}} ) = ∑_{i′=1}^{i−1} ∑_{q= \frac{N}{b_{1}(i′+1)} +1}^{\frac{N}{b_{1}i′}} ∑_{n=2}^{|F′_{i′}|} |\frac{k(a_{1}q + a_{2}) − a_{1}h}{k(b_{1}q + b_{2}) − b_{1}h} − \frac{I_{N} (\frac{k(a_{1}q+a_{2})−a_{1}h}{k(b_{1}q+b_{2})−b_{1}h})}{|F_{N}|}| ,

where the sum over n runs over the elements h/k in F′_{i′}, approximately n = I_{i′}(h/k) + O(i′). By virtue of Theorem 1 and Corollary 4

I_{N} (\frac{k(a_{1}q + a_{2}) − a_{1}h}{k(b_{1}q + b_{2}) − b_{1}h}) = I_{N} (\frac{a_{1}q + a_{2}}{b_{1}q + b_{2}} ) + sI_{i′} (\frac{h}{k}) + O(i′)

= I_{N} (\frac{a_{1}}{b_{1}} ) + s\frac{3}{π^{2}} \frac{N^{2}}{b_{1}^{2}q} − s\frac{3}{π^{2}} q \{\frac{N}{b_{1}q} \}^{2} + s\frac{3}{π^{2}} ⌊\frac{N}{b_{1}q} ⌋^{2} \frac{h}{k} + O(Nδ_{A}(i′)) ,

where we have used i′ = ⌊\frac{N}{qb_{1}} ⌋. Furthermore

\frac{I_{N} (\frac{k(a_{1}q+a_{2})−a_{1}h}{k(b_{1}q+b_{2})−b_{1}h})}{|F_{N}|} = \frac{I_{N} (\frac{a_{1}}{b_{1}} )}{|F_{N}|} + \frac{s}{b_{1}^{2}q} − \frac{sq}{N^{2}} \{\frac{N}{b_{1}q} \}^{2} + \frac{s}{N^{2}} ⌊\frac{N}{b_{1}q} ⌋^{2} \frac{h}{k} + O (\frac{δ_{A}(i′)}{N}) .

The Farey element inside the partial Franel sum is approximated as

\frac{k(a_{1}q + a_{2}) − a_{1}h}{k(b_{1}q + b_{2}) − b_{1}h} = \frac{k(a_{1}q + a_{2}) − a_{1}h}{k(b_{1}q + b_{2}) − b_{1}h} − \frac{a_{1}}{b_{1}} + \frac{a_{1}}{b_{1}}
= \frac{s}{b_{1}^{2}q} \frac{1}{1 + \frac{b_{2}}{qb_{1}} − \frac{h}{qk}} + \frac{a_{1}}{b_{1}}
= \frac{s}{b_{1}^{2}q} (1 − \frac{b_{2}}{qb_{1}} + \frac{h}{qk} ) + \frac{a_{1}}{b_{1}} + O(1/q^{3}) ,

where we have used (b_{1}a_{2} − a_{1}b_{2}) = s. The partial Franel sum under study becomes

∑_{i′=1}^{i−1} ∑_{q= \frac{N}{b_{1}(i′+1)} +1}^{\frac{N}{b_{1}i′}} |F′_{i′}| |\frac{a_{1}}{b_{1}} − \frac{I_{N} (\frac{a_{1}}{b_{1}} )}{|F_{N}|} − \frac{sb_{2}}{b_{1}^{3}q^{2}} + \frac{sq}{N^{2}} \{\frac{N}{b_{1}q} \}^{2} + O (\frac{δ_{A}(i′)}{N})| ,

where the terms proportional to 1/q and h/k have canceled out leaving a negligible residue. The sum over n has been evaluated just by multiplying by |F′_{i′}| as the dependency on h/k disappeared. Evaluating the asymptotics of the sums of the individual terms within the absolute value gives

∑_{i′=1}^{i−1} ∑_{q= \frac{N}{b_{1}(i′+1)} +1}^{\frac{N}{b_{1}i′}} |F′_{i′}| = O (iN) ,
∑_{i′=1}^{i−1} ∑_{q= \frac{N}{b_{1}(i′+1)} +1}^{\frac{N}{b_{1}i′}} \frac{|F′_{i′}|}{q^{2}} = O (\frac{i^{4}}{N} ) ,
∑_{i′=1}^{i−1} ∑_{q= \frac{N}{b_{1}(i′+1)} +1}^{\frac{N}{b_{1}i′}} |F′_{i′}|\frac{q}{N^{2}} = O(log i) ,
∑_{i′=1}^{i−1} ∑_{q= \frac{N}{b_{1}(i′+1)} +1}^{\frac{N}{b_{1}i′}} |F′_{i′}|\frac{δ_{A}(i′)}{N} = O (iδ_{B}(i)) ,

with 0 < B < A. Keeping the two dominant terms gives

P (\frac{a_{1}}{b_{1}} , \frac{a_{1} \frac{N}{b_{1}i} + a_{2}}{b_{1} \frac{N}{b_{1}i} + b_{2}} ) ≤ |\frac{a_{1}}{b_{1}} − \frac{I_{N} (\frac{a_{1}}{b_{1}} )}{|F_{N}|}| O(iN) + O(iδ_{B}(i)) ,

which is the searched result for b_{1} > 2. For 1 ≤ b_{1} ≤ 2 we have

\frac{0}{1} − \frac{I_{N} (\frac{0}{1})}{|F_{N}|} = O(1/N^{2}) , \frac{1}{2} − \frac{I_{N} (\frac{1}{2})}{|F_{N}|} = O(1/N^{2}) , \frac{1}{1} − \frac{I_{N} (\frac{1}{1})}{|F_{N}|} = 0 ,

and O(iδ_{B}(i)) dominates. The theorem is demonstrated.

Appendix

Table 1 illustrates the bijections between the first 90 elements in F_{60} and other Farey sequences of lower order.

i′ q h/k u/l I_{N}(\frac{u}{l}) i′ q h/k u/l I_{N}(\frac{u}{l}) i′ q h/k u/l I_{N}(\frac{u}{l})
∈ F_{i′} ∈ F_{N}  ∈ F_{i′} ∈ F_{N}  ∈ F_{i′} ∈ F_{N}
- -  -  \frac{0}{1}  1  1 32  \frac{1}{1}  \frac{1}{31}  31  3 18  \frac{1}{3}  \frac{3}{53}  61
1 60  \frac{0}{1}  \frac{1}{60}  2  1 31  \frac{1}{1}  \frac{1}{30}  32  3 18  \frac{1}{2}  \frac{2}{35}  62
1 60  \frac{1}{1}  \frac{1}{59}  3  2 30  \frac{1}{2}  \frac{2}{59}  33  3 18  \frac{2}{3}  \frac{3}{52}  63
1 59  \frac{1}{1}  \frac{1}{58}  4  2 30  \frac{1}{1}  \frac{1}{29}  34  3 18  \frac{1}{1}  \frac{1}{17}  64
1 58  \frac{1}{1}  \frac{1}{57}  5  2 29  \frac{1}{2}  \frac{2}{57}  35  3 17  \frac{1}{3}  \frac{3}{50}  65
1 57  \frac{1}{1}  \frac{1}{56}  6  2 29  \frac{1}{1}  \frac{1}{28}  36  3 17  \frac{1}{2}  \frac{2}{33}  66
1 56  \frac{1}{1}  \frac{1}{55}  7  2 28  \frac{1}{2}  \frac{2}{55}  37  3 17  \frac{2}{3}  \frac{3}{49}  67
1 55  \frac{1}{1}  \frac{1}{54}  8  2 28  \frac{1}{1}  \frac{1}{27}  38  3 17  \frac{1}{1}  \frac{1}{16}  68
1 54  \frac{1}{1}  \frac{1}{53}  9  2 27  \frac{1}{2}  \frac{2}{53}  39  3 16  \frac{1}{3}  \frac{3}{47}  69
1 53  \frac{1}{1}  \frac{1}{52}  10  2 27  \frac{1}{1}  \frac{1}{26}  40  3 16  \frac{1}{2}  \frac{2}{31}  70
1 52  \frac{1}{1}  \frac{1}{51}  11  2 26  \frac{1}{2}  \frac{2}{51}  41  3 16  \frac{2}{3}  \frac{3}{46}  71
1 51  \frac{1}{1}  \frac{1}{50}  12  2 26  \frac{1}{1}  \frac{1}{25}  42  3 16  \frac{1}{1}  \frac{1}{15}  72
1 50  \frac{1}{1}  \frac{1}{49}  13  2 25  \frac{1}{2}  \frac{2}{49}  43  4 15  \frac{1}{4}  \frac{4}{59}  73
1 49  \frac{1}{1}  \frac{1}{48}  14  2 25  \frac{1}{1}  \frac{1}{24}  44  4 15  \frac{1}{3}  \frac{3}{44}  74
1 48  \frac{1}{1}  \frac{1}{47}  15  2 24  \frac{1}{2}  \frac{2}{47}  45  4 15  \frac{1}{2}  \frac{2}{29}  75
1 47  \frac{1}{1}  \frac{1}{46}  16  2 24  \frac{1}{1}  \frac{1}{23}  46  4 15  \frac{2}{3}  \frac{3}{43}  76
1 46  \frac{1}{1}  \frac{1}{45}  17  2 23  \frac{1}{2}  \frac{2}{45}  47  4 15  \frac{3}{4}  \frac{4}{57}  77
1 45  \frac{1}{1}  \frac{1}{44}  18  2 23  \frac{1}{1}  \frac{1}{22}  48  4 15  \frac{1}{1}  \frac{1}{14}  78
1 44  \frac{1}{1}  \frac{1}{43}  19  2 22  \frac{1}{2}  \frac{2}{43}  49  4 14  \frac{1}{4}  \frac{4}{55}  79
1 43  \frac{1}{1}  \frac{1}{42}  20  2 22  \frac{1}{1}  \frac{1}{21}  50  4 14  \frac{1}{3}  \frac{3}{41}  80
1 42  \frac{1}{1}  \frac{1}{41}  21  2 21  \frac{1}{2}  \frac{2}{41}  51  4 14  \frac{1}{2}  \frac{2}{27}  81
1 41  \frac{1}{1}  \frac{1}{40}  22  2 21  \frac{1}{1}  \frac{1}{20}  52  4 14  \frac{2}{3}  \frac{3}{40}  82
1 40  \frac{1}{1}  \frac{1}{39}  23  3 20  \frac{1}{3}  \frac{3}{59}  53  4 14  \frac{3}{4}  \frac{4}{53}  83
1 39  \frac{1}{1}  \frac{1}{38}  24  3 20  \frac{1}{2}  \frac{2}{39}  54  4 14  \frac{1}{1}  \frac{1}{13}  84
1 38  \frac{1}{1}  \frac{1}{37}  25  3 20  \frac{2}{3}  \frac{3}{58}  55  4 13  \frac{1}{4}  \frac{4}{51}  85
1 37  \frac{1}{1}  \frac{1}{36}  26  3 20  \frac{1}{1}  \frac{1}{19}  56  4 13  \frac{1}{3}  \frac{3}{38}  86
1 36  \frac{1}{1}  \frac{1}{35}  27  3 19  \frac{1}{3}  \frac{3}{56}  57  4 13  \frac{1}{2}  \frac{2}{25}  87
1 35  \frac{1}{1}  \frac{1}{34}  28  3 19  \frac{1}{2}  \frac{2}{37}  58  4 13  \frac{2}{3}  \frac{3}{37}  88
1 34  \frac{1}{1}  \frac{1}{33}  29  3 19  \frac{2}{3}  \frac{3}{55}  59  4 13  \frac{3}{4}  \frac{4}{49}  89
1 33  \frac{1}{1}  \frac{1}{32}  30  3 19  \frac{1}{1}  \frac{1}{18}  60  4 13  \frac{1}{1}  \frac{1}{12}  90

Table 1: Correspondence between elements in F_{i′}, with 0 < i′ < 5 and first 90 elements in F_{N}, given by u/l = h/(hq − k) with N/(i′ + 1) < q ≤ N/i′ and N = lcm(1, 2, 3, 4, 5) = 60. Note that the images of elements 1/1 and 0/1 of adjacent maps are equal and only the 1/1 case is shown on the table. The illustrated maps originate from the map M in Theorem 1 with a_{1}/b_{1} = 0/1 and a_{2}/b_{2} = 1/0.

References

[1] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1996.

[2] J. Franel, Les suites de Farey et le problème des nombres premiers, Nachr. von der Ges. der Wiss. zu Göttingen Math.-Phys. Kl. (1924), 198–201.

[3] E. Landau, Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel, Nachr. von der Ges. der Wiss. zu Göttingen Math.-Phys. Kl. (1924), 202–206.

[4] F. Dress, Discrépance des suites de Farey, J. Théor. Nombres Bordeaux 11 (1999), 345–367.

[5] S. Kanemitsu and M. Yoshimoto, Farey series and the Riemann hypothesis, Acta Arith. 75 (1996), 351–374.

[6] S. B. Guthery, A Motif of Mathematics: History and Application of the Mediant and the Farey Sequence, Docent Press, 2011.

[7] C. Cobeli, M. Vâjâitu, and A. Zaharescu, On the intervals of a third between Farey fractions, Bull. Math. Soc. Sci. Math. Roumanie, 53 (2010), 239–250.

[8] R. Tomás, From Farey sequences to resonance diagrams, Phys. Rev. ST Accel. Beams 17 (2014), 014001.

[9] R. Tomás, Asymptotic behavior of a series of Euler’s totient function φ(k) times the index of 1/k in a Farey sequence, preprint, 2014. Available at https://arxiv.org/

pdf/1406.6991.pdf.

[10] R. Tomás, Equalities between greatest common divisors involving three coprime pairs, Notes Number Theory Discrete Math. 26 (2020), 5–7.

[11] S. Kanemitsu, T. Kuzumaki, and M. Yoshimoto, Some sums involving Farey fractions II, J. Math. Soc. Japan 52 (2000), 915–947.

[12] A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin, 1963.

2010 Mathematics Subject Classification: Primary 11B57; Secondary 11M26. Keywords: Farey sequence, Riemann hypothesis.

Received September 2 2021; revised version received September 5 2021; September 12 2021; January 2 2022; January 11 2022. Published in Journal of Integer Sequences, January 12 2022.

Return to Journal of Integer Sequences home page.