The Petersson-Knopp Identity and Farey Points

Kurt Girstmair Institut für Mathematik Universität Innsbruck Technikerstr. 13/7 A-6020 Innsbruck Austria

               Kurt.Girstmair@uibk.ac.at

Abstract

We study Dedekind sums S(a, b) for arguments a near Farey points of the interval [0, b]. The Petersson-Knopp identity connects each of these Dedekind sums with a set of other Dedekind sums. In the case considered here, this identity has a very specific interpretation, inasmuch as each Dedekind sum occurring in this identity is close to a certain expected value. Conversely, each of these expected values occurs with a certain frequency, a frequency that is consistent with the Petersson-Knopp identity.

1 Introduction and results

Let b be a positive integer and a ∈ ℤ. The classical Dedekind sum s(a, b) is defined by

s(a, b) = ∑_{k=1}^{b}((k/b))((ak/b))

where ((…)) is the “sawtooth function”, defined by

((t)) = \begin{cases}t − ⌊t⌋ − 1/2, & if t ∈ ℝ ∖ ℤ; \\ 0, & if t ∈ ℤ; \end{cases}

see, for instance, [7]. In many cases it is more convenient to work with

S(a, b) = 12s(a, b)

instead. We call S(a, b) a normalized Dedekind sum. In addition, we say that S(a, b) is a primitive Dedekind sum if gcd(a, b) = 1. In the opposite case S(a, b) is called imprimitive. Note that

S(ad, bd) = S(a, b)

for every positive integer d; see [7, Th. 1]. Therefore, each imprimitive Dedekind sum S(a, b) is equal to the primitive Dedekind sum S(a/d, b/d), where d = gcd(a, b). We also note the periodicity

S(a + b, b) = S(a, b)  (1)

of (not necessarily primitive) Dedekind sums.

Let us start with a special case of what we are going to do in the sequel. Let a < b be positive integers, gcd(a, b) = 1, and p a prime not dividing a, b. Then the normalized Dedekind sums

S(pa, b) and S(a + jb, pb), j ∈ {0, …, p − 1},  (2)

are primitive with one exception. Indeed, if a + jb ≡ 0 (mod p), then S(a + jb, pb) = S((a + jb)/p, b). Suppose we know that all Dedekind sums (2) are positive. Then we also know that S(a, b) is positive. Moreover, we know that at least one of the Dedekind sums (2) is ≥ S(a, b), whereas the sum of any p of them must be < (p + 1)S(a, b). This is an immediate consequence of the Petersson-Knopp identity, which, in this special case, reads

S(pa, b) + ∑_{j=0}^{p−1} S(a + jb, pb) = (p + 1)S(a, b).

In what follows we discuss a situation where we know much more, namely, that one of the Dedekind sums (2) is close to pS(a, b), whereas each of the p remaining ones is close to S(a, b)/p. Hence the Petersson-Knopp identity has a very specific interpretation in this context.

In two previous papers [1, 2] we studied the behavior of primitive Dedekind sums near Farey points. We briefly recall the necessary notation. Let the positive integer b be given and assume b ≥ 4. For a positive integer d, d < b^{1/4}, let c ∈ ℤ, gcd(c, d) = 1. Then c/d is a Farey fraction of an order < b^{1/4} in the usual sense; see [4, p. 125]. We say that b · c/d is a Farey point with respect to b. Put

α = \sqrt{b/d^{3}}.  (3)

We consider the interval

{x ∈ ℝ : |x − b · c/d| ≤ α − 1}

around the Farey point b · c/d. Let a be an integer, gcd(a, b) = 1, inside this interval. Then the primitive Dedekind sum S(a, b) satisfies

S(a, b) \begin{cases}< 0, & if a < b · c/d; \\ > 0, & if a > b · c/d; \end{cases}

see [1, Th. 1 and formula (5)]. In order to avoid tedious distinctions, we restrict ourselves to integers a in the right half of this interval, so S(a, b) > 0. The whole theory remains valid for integers in the left half, but with S(a, b) negative.

Hence we say that a ∈ ℤ, gcd(a, b) = 1, is a neighbor of the Farey point b · c/d if

0 ≤ a − b · c/d ≤ α − 1.  (4)

Note that a − b · c/d ≠ 0 since a/b = c/d is impossible (both fractions are reduced, and 0 < d < b). For such a neighbor a, S(a, b) is not only positive, but its value is, as a rule, close to an expected value, which can be defined as follows. Put

q = ad − bc.  (5)

Then q > 0 since q/d = a − b · c/d > 0. Now the expected value of S(a, b) is

E(a, b) = \frac{b}{dq}  (6)

(which is > 0).

Of course, this definition requires some justification. To this end we consider the threeterm relation for Dedekind sums

S(a, b) = \frac{b}{dq} + S(c, d) + S(t, q) + \frac{d}{bq} + \frac{q}{db} − 3;  (7)

see [1, Lemma 3]. Here q is defined by (5) and t is an integer defined by a, b, c, d. The exact value of t is not of interest for our purpose. First we observe d < b and, by (4) and (5), q < \sqrt{b/d} < b. We have, thus,

0 < \frac{d}{bq} + \frac{q}{db} < 2.

Next we note

|S(c, d)| < d and |S(t, q)| < q;  (8)

see [6, Satz 2]. Hence S(a, b) is close to E(a, b) = b/(dq) whenever d and q are small. For instance, we may assume a − b · c/d ≤ b^{1/12} for a sufficiently large number b. Then q ≤ b^{1/12}b^{1/4} = b^{1/3}, but b/(dq) ≥ b^{5/12}. Because b^{1/3} is small relative to b^{5/12}, S(a, b) is close to E(a, b).

In most cases, however, S(a, b) is close to E(a, b) even if a is only a neighbor of b · c/d in the above sense, since |S(c, d)| is much smaller than d and |S(t, q)| much smaller than q.

Indeed, it is reasonable to expect |S(c, d)| ≤ 5 log d and |S(t, q)| ≤ 5 log q, say. This is due to the main result of the paper [8], which allows to determine the asymptotic proportion of pairs (c, d), 0 ≤ c < d ≤ N, gcd(c, d) = 1, such that |S(c, d)| < C log d for a given constant C > 0, as N tends to infinity. For C = 5 this proportion is about 76.8% , and for C = 10 about 88.0%.

Another argument in favor of small values of |S(c, d)| and |S(t, q)| is the mean value of all numbers |S(c, d)|, 0 ≤ c < d, gcd(c, d) = 1, for a given positive integer d. As d tends to infinity, this mean value is ≤ log^{2} d · 6/π^{2} + O(log d); see [3].

The Petersson-Knopp identity is a relation between S(a, b) and certain other Dedekind sums; see [5]. Indeed, if n is a natural number, then

∑_{r | n} ∑_{j=0}^{r−1} S (\frac{n}{r}a + jb, rb) = σ(n)S(a, b).  (9)

Here r runs through the (positive) divisors of n and σ(n) = ∑_{r | n} r is the sum of the divisors of n.

The Dedekind sums in (9) are not necessarily primitive. In order to apply results about neighbors of Farey points, we need primitive Dedekind sums, however. In view of the periodicity (1), it suffices to restrict c to the range 0 ≤ c < d, gcd(c, d) = 1. Let a be a neighbor of b · c/d. For r | n and j ∈ {0, …, r − 1} put

k(r, j) = (\frac{n}{r}a + jb, rb) and m(r, j) = (\frac{n}{r}c + jd, rd) .

So both k(r, j) and m(r, j) are positive integers. Moreover, put

a(r, j) = \frac{\frac{n}{r}a + jb}{k(r, j)}, b(r, j) = \frac{rb}{k(r, j)},

c(r, j) = \frac{\frac{n}{r}c + jd}{m(r, j)}, d(r, j) = \frac{rd}{m(r, j)}.

In the sequel we simply write

S′(r, j) = S(a(r, j), b(r, j)) = S (\frac{n}{r}a + jb, rb)

and

E′(r, j) = E(a(r, j), b(r, j)).

Then we have the following result.

Theorem 1. In the above setting, let 0 ≤ c < d, gcd(c, d) = 1, α ≥ n^{3/2} + n and

0 < a − b · c/d ≤ α/n − 1.

For each pair (r, j), r | n, j ∈ {0, …, r − 1}, the number a(r, j) is a neighbor of the Farey point b(r, j) · c(r, j)/d(r, j) of the interval [0, b(r, j)]. Hence S′(r, j) is positive. Its expected value is

E′(r, j) = \frac{m(r, j)^{2}}{n} · E(a, b),  (10)

where E(a, b) is the expected value of S(a, b), see (6).

In view of the Petersson-Knopp identity (9), one expects that

∑_{r | n} ∑_{j=0}^{r−1} E′(r, j) = σ(n)E(a, b).  (11)

This is true, but we have a much more precise result about the expected values E′(r, j). Indeed, they follow a very regular pattern.

Theorem 2. In the above setting, the numbers m(r, j) divide n. Conversely, for every positive divisor m of n,

# \{(r, j) : r | n, j ∈ \{0, …, r − 1\}, E′(r, j) = \frac{m^{2}}{n} E(a, b)\} = \frac{n}{m}.  (12)

By (10) and (12), the left hand side of (11) reads

∑_{m | n} \frac{n}{m} · \frac{m^{2}}{n} E(a, b),

which obviously equals σ(n) · E(a, b).

Example 3. Let n = 12. In this case there are σ(12) = 28 Dedekind sums S′(r, j). The corresponding values of E′(r, j)/E(a, b) are 1/12, 1/3, 3/4, 4/3, 3, 12, respectively. Let d = 9 and c = 1. We chose b so large that α/n − 1 ≥ 10. This means b ≥ 12702096. Then it is obvious that α ≥ 132 ≥ n^{3/2} + n ≈ 53.569. We used a random generator to produce a number b, 1.28 · 10^{7} < b < 10^{8}. It gave us b = 31537789. The Farey point b · c/d is approximately 3504198.78. Since α/n − 1 ≈ 16.33, we can choose a = 3504214, which is prime to b, and a − b · c/d ≈ 15.22. Then S(a, b) ≈ 25537.432 and E(a, b) ≈ 25578.093. We computed the relative deviation

|\frac{S′(r, j)}{E′(r, j)} − 1|  (13)

of each of the said 28 Dedekind sums from its expected value. It turns out that the largest relative deviation is ≈ 0.04659 or nearly 4.7%. It occurs for r = 6, j = 1, where E′(r, j) = (1/12)E(a, b). The mean relative deviation, i.e., the arithmetic mean of all values (13), is ≈ 0.0060 or 0.6%. Further empirical results can be found in Section 3.

Remark 4. The example shows that there are, compared with the size of b, only few integers a such that 0 < a − b · c/d ≤ α/n − 1 for a fixed value of d and 0 ≤ c < d, gcd(c, d) = 1. In the case of the example their number amounts to ≈ 6 · 15 = 90. However, one should be aware of the fact that each number a of this kind also satisfies a − b · c/d ≤ α/n′ − 1 for all integers n′, 1 ≤ n′ < n. Therefore, if gcd(a, b) = 1, the number a gives rise not only to the σ(n) Dedekind sums S′(r, j) for n, but also to σ(n′) analogous Dedekind sums for each positive integer n′ < n (the case n′ = 1 includes S(a, b)). For n = 12 their totality amounts to σ(1) + σ(2) + ⋯ + σ(12) = 112. In general,

∑_{n′=1}^{n} σ(n′) = \frac{π^{2}}{12}n^{2} + O(n log n);

see [4, p. 113]. Hence there is quite a number of Dedekind sums whose expected values are known.

2 Proofs

Suppose that the assumptions of Theorem 1 hold. In particular, let r divide n and j ∈ {0, …, r − 1}.

We first show that m(r, j) divides n. Let p be a prime. We use the p-exponent v_{p}(t) of an integer t ≠ 0, which is given by t = p^{v_{p}(t)}t′, gcd(p, t′) = 1. We show that v_{p}(m(r, j)) ≤ v_{p}(n) for all primes p. To this end recall that m(r, j) = gcd(\frac{n}{r}c+jd, rd). First suppose p ∤ d. Then v_{p}(m(r, j)) ≤ v_{p}(r) ≤ v_{p}(n). Next let p | d, so v_{p}(d) = s ≥ 1. Since gcd(c, d) = 1, v_{p}(c) = 0 and v_{p}(\frac{n}{r}c) = v_{p}(\frac{n}{r}). If v_{p}(\frac{n}{r}) < s, then v_{p}(\frac{n}{r}c + jd) = v_{p}(\frac{n}{r}) ≤ v_{p}(n). If v_{p}(\frac{n}{r}) ≥ s, then v_{p}(n) ≥ v_{p}(r) + s. In this case v_{p}(rd) = v_{p}(r) + s ≤ v_{p}(n), and v_{p}(m(r, j)) ≤ v_{p}(rd) ≤ v_{p}(n).

The same arguments work for k(r, j) = (\frac{n}{r}a + jb, rb) and a, b instead of c, d. They show that k(r, j) divides n.

Proof of Theorem 1. In order to simplify the notation for the purpose of this proof, we write a′ = a(r, j), b′ = b(r, j), c′ = c(r, j), d′ = d(r, j), k′ = k(r, j), and m′ = m(r, j). First we observe b′ ≥ b/k′ ≥ b/n, and since α ≥ 2n, we have b′ ≥ 4.

Next we consider

q′ = a′d′ − b′c′.  (14)

A short calculation shows

q′ = \frac{n}{k′m′} q,  (15)

where q = ad − bc; see (5). Now a′ is a neighbor of b′ · c′/d′, if 0 < a′ − b′ · c′/d′ ≤ \sqrt{b′/d^{′3}} − 1, i.e.,

0 < q′ ≤ \sqrt{b′/d′} − d′;

see (4). Here q′ > 0 follows from (15), since q > 0. Because \sqrt{b′/d′} = \sqrt{m′/k′} · \sqrt{b/d}, a′ is a neighbor of b′ · c′/d′, if

\frac{n}{k′m′} q ≤ \sqrt{\frac{m′}{k′}} · \sqrt{\frac{b}{d}} − \frac{rd}{m′} ,

by (15). This condition can be written as

a − b · \frac{c}{d} = \frac{q}{d} ≤ \frac{k^{′1/2}m^{′3/2}}{n} · α − \frac{rk′}{n} .  (16)

Let ρ be the right hand side of (16), i.e.,

ρ = \frac{k^{′1/2}m^{′3/2}}{n} · α − \frac{rk′}{n} .

If k′ = m′ = 1 and r = n, then ρ becomes α/n − 1. We show that ρ is always ≥ α/n − 1, provided that α ≥ n^{3/2} + n. In this case the condition q/d ≤ α/n − 1 implies that a′ is a neighbor of b′ · c′/d′ for all r, j in question.

In the case k′ = 1 we have rk′/n ≤ r/n ≤ 1 and ρ ≥ α/n − 1. Hence assume k′ > 1. Since ρ is ≥ k^{′1/2}α/n − rk′/n, ρ < α/n − 1 implies k^{′1/2}α − rk′/n < α/n − 1. Because k^{′1/2} > 1, this inequality can be written as α < (rk′ − n)/(k^{′1/2} − 1). Since r ≤ n, it implies α < n(k^{′1/2} + 1). We know that k′ divides n, hence we obtain α < n^{3/2} + n as a necessary condition for ρ < α/n − 1.

Finally, we compute

E(a′, b′) = \frac{b′}{d′q′} = \frac{rb/k′}{rd/m′ · q · n/(k′m′)} = \frac{m^{′2}}{n} \frac{b}{dq} = \frac{m^{′2}}{n} E(a, b).

In the sequel we need the following notation. For positive integers r and d let (r)_{d} and (r)_{d}^{⊥} denote the d-part and the d-free part of r, respectively, i.e.,

(r)_{d} = ∏_{p | r, p | d} p^{v_{p}(r)} and (r)_{d}^{⊥} = ∏_{p | r, p ∤ d} p^{v_{p}(r)},

where v_{p}(r) is defined as above. The proof of Theorem 2 is more complicated than that of Theorem 1 and is based on the following lemmas.

Lemma 5. Let r, d be positive integers and s ∈ ℤ such that gcd(s, d) = 1. Then

#\{\overline{k} ∈ ℤ/rℤ : \overline{s + kd} ∈ (ℤ/rℤ)^{×}\} = (r)_{d} φ((r)_{d}^{⊥}),

where φ denotes Euler’s totient function.

Proof. We use the Chinese remainder theorem to decompose ℤ/rℤ into its p-parts ℤ/p^{e_{p}}ℤ, where e_{p} = v_{p}(r) ≥ 1.

Case 1: p | d. Then for all k ∈ ℤ we have s + kd ≡ s ≢ 0 (mod p), i.e., \overline{s + kd} ∈ (ℤ/p^{e_{p}}ℤ)^{×}. Hence

#\{\overline{k} ∈ ℤ/p^{e_{p}}ℤ : \overline{s + kd} ∈ (ℤ/p^{e_{p}}ℤ)^{×}\} = p^{e_{p}}.

Case 2: p ∤ d. Let k ∈ ℤ. Let d^{∗} be an inverse of d (mod p). Then s + kd ≢ 0 (mod p) if, and only if, k ≢ −sd^{∗} (mod p). Therefore,

#\{\overline{k} ∈ ℤ/p^{e_{p}}ℤ : \overline{s + kd} ∈ (ℤ/p^{e_{p}}ℤ)^{×}\} = p^{e_{p}}(1 − 1/p) = φ(p^{e_{p}}).

Lemma 6. Let n be a positive integer and m > 0 a divisor of n. Let c, d ∈ ℤ, 0 ≤ c < d, gcd(c, d) = 1, and δ = gcd(m, d). Put n′ = n/δ, m′ = m/δ and d′ = d/δ. Then

# \{(r, j) : r | n, 0 ≤ j ≤ r − 1, m = gcd (\frac{n}{r}c + jd, rd)\} =

∑_{{m′ | r | n′ \atop gcd(n/r,d)=δ}}(r/m′)_{d′} φ((r/m′)_{d′}^{⊥}).  (17)

Proof. For given positive divisors m, r of n we determine

# \{j : 0 ≤ j ≤ r − 1, m = gcd (\frac{n}{r}c + jd, rd)\} .  (18)

First we show that (18) equals 0 if gcd(n/r, d) ≠ δ. To this end suppose that m = gcd(\frac{n}{r}c + jd, rd) for some j. Since δ | m, we have δ | \frac{n}{r}c + jd, and because δ | d, we obtain δ | \frac{n}{r}c. But gcd(c, d) = 1, and so δ | \frac{n}{r}. Put d_{r} = gcd(\frac{n}{r}, d). We have seen δ | d_{r}. Conversely, d_{r} divides both \frac{n}{r}c + jd and rd, whence d_{r} | m. But d_{r} | d, which implies d_{r} | gcd(m, d) = δ. Altogether, d_{r} = δ. This means that m = gcd(\frac{n}{r}c + jd, rd) can hold only if d_{r} = δ.

Therefore, we can restrict our investigation of (18) to those r for which gcd(\frac{n}{r}, d) = δ. As above, put d′ = d/δ and n′ = n/δ. Since δ | n/r, r divides n′. Suppose that m = gcd(\frac{n}{r}c + jd, rd). Then m = δm′ with m′ = gcd(\frac{n′}{r} c + jd′, rd′). Because gcd(\frac{n}{r}, d) = δ, we have gcd(\frac{n′}{r} , d′) = 1 and gcd(\frac{n′}{r} c + jd′, d′) = 1. Accordingly,

m′ = gcd (\frac{n′}{r} c + jd′, r) .  (19)

Conversely, suppose that m′ = m/δ divides r. Since gcd(m′, d′) = 1, there is a number j_{0} ∈ \{0, …, m′ − 1\} such that \frac{n′}{r} c + j_{0}d′ ≡ 0 (mod m′). If m′ has the form (19) for a number j ∈ {0, …, r − 1}, then j ≡ j_{0} (mod m′), and so j = j_{0} + km′ for a uniquely determined k ∈ {0, …, r/m′ − 1}. For such a number j, we have

(\frac{n′}{r} c + jd′) /m′ = s + kd′

with s = (\frac{n′}{r} c + j_{0}d′)/m′. Now (19) holds if, and only if,

gcd(s + kd′, r/m′) = 1.

Therefore, we have to count the \overline{k} ∈ ℤ/\frac{r}{m′} ℤ such that \overline{s + kd′} ∈ (ℤ/\frac{r}{m′} ℤ)^{×}. From Lemma 5 we know that the number of these elements \overline{k} equals

(r/m′)_{d′} φ ((r/m′)_{d′}^{⊥}) .  (20)

This number equals that of (18). We have to sum up the numbers (20), observing that gcd(n/r, d) = δ. This yields (17).

For positive integers n, m, m | n, let A(m, n) denote the number of (17), i.e.,

A(m, n) = # \{(r, j) : r | n, 0 ≤ j ≤ r − 1, m = gcd (\frac{n}{r}c + jd, rd)\} .

Lemma 7. Let n, m be positive integers, m | n, and suppose n = n_{1}n_{2} for positive integers n_{1}, n_{2} such that gcd(n_{1}, n_{2}) = 1. Put m_{1} = gcd(m, n_{1}) and m_{2} = gcd(m, n_{2}). Then

A(m, n) = A(m_{1}, n_{1})A(m_{2}, n_{2}).

Proof. All entries of the right hand side of (17) are multiplicative. Indeed, put δ_{1} = gcd(δ, n_{1}) and δ_{2} = gcd(δ, n_{2}). Then δ = δ_{1}δ_{2}. In the same way, r = r_{1}r_{2} with r_{1} = gcd(r, n_{1}) and r_{2} = gcd(r, n_{2}). We also have n′ = n′_{1}n′_{2} with n′_{1} = n_{1}/δ_{1} and n′_{2} = n_{2}/δ_{2}. The respective identity holds for m′ and m′_{1} = m_{1}/δ_{1} and m′_{2} = m_{2}/δ_{2}. Further, gcd(n/r, d) = δ if, and only if, gcd(n_{1}/r_{1}, d) = δ_{1} and gcd(n_{2}/r_{2}, d) = δ_{2}. We note (r/m′)_{d′} = (r_{1}/m′_{1})_{d′_{1}}(r_{2}/m′_{2})_{d′_{2}}, where d′_{1} = d/δ_{1} and d′_{2} = d/δ_{2}. The same identity holds when we apply the ⊥ to the respective items. Finally, the function φ is also multiplicative. In view of all that, we can write the sum over r as the product of two sums over r_{1} and r_{2} and obtain the desired result.

Proof of Theorem 2. We have to show that A(m, n) = n/m. By Lemma 7, it suffices to prove this identity for prime powers n = p^{e} and m | n. Suppose that m = p^{k}, k ≤ e, and (d)_{p} = p^{s}.

Case 1: k ≥ s. Then δ = p^{s}. We have m′ = p^{k−s} and n′ = p^{e−s}. Let r = p^{t} with k − s ≤ t ≤ e − s. By Lemma 6,

A(m, n) = ∑_{{k−s≤t≤e−s \atop gcd(p^{e−t},p^{s})=p^{s}}} φ(p^{t+s−k}),

since r/m′ = p^{t+s−k} and (d′)_{p} = (d/δ)_{p} = 1. Obviously, gcd(p^{e−t}, p^{s}) = p^{s} holds for all t in question, because e − t ≥ s. We obtain

A(m, n) = ∑_{u=0}^{e−k} φ(p^{u}) = p^{e−k} = n/m.

Case 2: k < s. Then δ = p^{k}. Moreover, m′ = 1 and n′ = p^{e−k}. If r = p^{t}, 0 ≤ t ≤ e − k, we have

gcd(n/r, d) = gcd(p^{e−t}, p^{s}) = \begin{cases}p^{e−t}, & if e − t ≤ s, \\ p^{s}, & if e − t > s. \end{cases}

Since r must satisfy gcd(n/r, d) = δ = p^{k} and k < s, only the first case is suitable for our purpose, and, indeed, only for e − t = k, i.e., t = e − k. So only the summand for r = p^{e−k} remains. We have (d′)_{p} = p^{s−k} with s − k ≥ 1. Accordingly, (r/m′)_{d′} = (r)_{d′} = r = p^{e−k} and A(m, n) = n/m, again.

3 Numerical evidence for the expected values

We return to the setting of the Theorems 1 and 2. Suppose that the size of d is fixed, say d ≤ n, whereas b may become large. As in Theorem 1, assume α ≥ n^{3/2} + n and q/d ≤ α/n − 1. Accordingly, all Dedekind sums S(a(r, j), b(r, j)) = S′(r, j) are positive for r | n, 0 ≤ j ≤ r − 1. The expected value of S′(r, j) equals E′(r, j) = (m(r, j)^{2}/n)E(a, b). By Theorem 2, we know that m(r, j) is a divisor of n, and, conversely, each positive divisor m of n has the form m = m(r, j) for exactly n/m pairs (r, j).

Empirical data shows that the relative deviation (13) of S′(r, j) from E′(r, j) may be large, in the main, if m(r, j) = k(r, j) = 1 and q/d is close to α/n. In this case E′(r, j) = (1/n)E(a, b). This empirical observation can be explained as follows. We have

q(r, j) = a(r, j)d(r, j) − b(r, j)c(r, j) = \frac{n}{k(r, j)m(r, j)} q;

see (14), (15). Because m(r, j) = k(r, j) = 1, we obtain q(r, j) = nq. The influence of S(c(r, j), d(r, j)) on S′(r, j) in the sense of (7) is limited since |S(c(r, j), d(r, j))| ≤ d(r, j) ≤ rd ≤ n^{2}. However, the influence of S((t(r, j), q(r, j)) may be significant if q(r, j) = nq is close to E′(r, j) = (1/n)E(a, b) = b/(ndq), i.e., if q/d is close to α/n.

Let (r, j) be of this kind and, in addition, the pair (r_{1}, j_{1}) such that m(r_{1}, j_{1}) ≥ 2. Then we have

q(r_{1}, j_{1}) = \frac{n}{k(r_{1}, j_{1})m(r_{1}, j_{1})} q ≤ \frac{n}{2} q = \frac{q(r, j)}{2}.

On the other hand E′(r_{1}, j_{1}) ≥ (4/n)E(a, b) = 4E′(r, j). This means

\frac{q(r_{1}, j_{1})}{E′(r_{1}, j_{1})} ≤ \frac{1}{8} · \frac{q(r, j)}{E′(r, j)},

which is a much better proportion than q(r, j)/E′(r, j), in particular, in the bad case q(r, j) ≈ E′(r, j).

As to empirical data, we performed numerous computations, of which, however, we present only the case n = 12 and d = 9. We computed the mean value of the relative deviation (13) both for all 28 pairs (r, j), r | 12, j = 0, …, r − 1, and only for those (r, j) with m(r, j) = 1 (and expected value E′(r, j) = (1/12)E(a, b)). By the above, it is not surprising that the first mean value is always smaller than the second.

We consider b = 10^{8} + k, 1 ≤ k ≤ 10000, and choose the integer a close to b · c/d + α/n. To be precise, a is either ⌊b · c/d + α/n⌋ − 1 or ⌊b · c/d + α/n⌋ − 2. If none of these values of a satisfies gcd(a, b) = 1, the number b is ruled out. In this way there always remain ≥ 8000 pairs (b, a) to be investigated. The following table lists the percentage of b’s such that the first mean value

M_{1} = \frac{1}{σ(n)} ∑_{r | n} ∑_{j=0}^{r−1} |\frac{S′(r, j)}{E′(r, j)} − 1|

is either ≥ 0.05 or < 0.01. The table also displays the percentage of b’s such that the second mean value

M_{2} = \frac{1}{n} ∑_{m(r,j)=1} |\frac{S′(r, j)}{E′(r, j)} − 1|

is either ≥ 0.05 or < 0.01.

c  1  2  4  5  7  8
M_{1} ≥ 0.05 1.2 % 1.3 % 1.3 % 1.3 % 1.3 % 1.3 %
M_{1} < 0.01 93.4 % 93.7 % 93.7 % 93.6 % 93.8 % 92.9 %
M_{2} ≥ 0.05 1.9 % 2.0 % 1.9 % 2.0 % 2.0 % 2.0 %
M_{2} < 0.01 73.6 % 80.5 % 78.7 % 78.8 % 80.6 % 70.6 %
Table 1: n = 12, d = 5, b = 10^{8} + k, 1 ≤ k ≤ 10000

We list the same data for numbers b = 10^{9} + k, 1 ≤ k ≤ 10000.

c  1  2  4  5  7  8
M_{1} ≥ 0.05 0.4 % 0.4 % 0.4 % 0.3 % 0.3 % 0.4 %
M_{1} < 0.01 97.9 % 98.0 % 98.0 % 98.2 % 98.2 % 97.9 %
M_{2} ≥ 0.05 0.6 % 0.6 % 0.6 % 0.5 % 0.5 % 0.6 %
M_{2} < 0.01 94.4 % 94.5 % 94.7 % 95.2 % 95.1 % 94.2 %
Table 2: n = 12, d = 5, b = 10^{9} + k, 1 ≤ k ≤ 10000

We obtain similar results when we use (pseudo-) random numbers b of the same order of magnitude instead of the (more or less) consecutive numbers b of the tables. The tables suggest that the approximation of E′(r, j) by S′(r, j) becomes better when b increases while d and n are fixed. This observation is supported by further computations.

References

[1] K. Girstmair, Dedekind sums with predictable signs, Acta Arith. 83 (1998), 283–294.

[2] K. Girstmair, Zones of large and small values for Dedekind sums, Acta Arith. 109 (2003), 299–308.

[3] K. Girstmair and J. Schoissengeier, On the arithmetic mean of Dedekind sums, Acta Arith. 116 (2005), 189–198.

[4] L. K. Hua, Introduction to Number Theory, Springer-Verlag, 1982.

[5] L. A. Parson, Dedekind sums and Hecke operators, Math. Proc. Cambridge Philos. Soc. 88 (1980), 11–14.

[6] H. Rademacher, Zur Theorie der Dedekindschen Summen, Math. Z. 63 (1956), 445–463.

[7] H. Rademacher and A. Whiteman, Theorems on Dedekind sums, Amer. J. Math. 63 (1941), 377–407.

[8] I. Vardi, Dedekind sums have a limiting distribution, Internat. Math. Res. Notices 1993, 1–12.

2010 Mathematics Subject Classification: Primary 11F20. Keywords: Dedekind sum, Petersson-Knopp identity, Farey point, expected value of a Dedekind sum.

Received February 19 2020; revised version received May 17 2020. Published in Journal of Integer Sequences, May 17 2020.

Return to Journal of Integer Sequences home page.