DISTRIBUTION OF DIFFERENCE BETWEEN INVERSES OF CONSECUTIVE INTEGERS MODULO P

Tsz Ho Chan

Department of Mathematics, Case Western Reserve University, Cleveland, OH 44106, USA

                             txc50@cwru.edu

Received: 11/19/03, Revised: 2/9/04, Accepted: 3/24/04, Published: 3/25/04

Abstract

Let p > 2 be a prime number. For each integer 0 < n < p, define \overline{n} by the congruence n\overline{n} ≡ 1 (mod p) with 0 < \overline{n} < p. We are led to study the distribution behavior of \overline{n} − \overline{n + 1} in order to prove the asymptotic formula

∑_{n=1}^{p−2} |\overline{n} − \overline{n + 1}| = \frac{1}{3}p^{2} + O(p^{3/2} log^{3} p).

1. Introduction

For any prime p and any integer 0 < n < p, there is one and only one \overline{n} with 0 < \overline{n} < p satisfying n\overline{n} ≡ 1 (mod p). We are interested in how the inverses \overline{n} fluctuate as n runs from 1 to p − 1. In particular, we look at the sum

S_{p} = ∑_{n=1}^{p−2} |\overline{n} − \overline{n + 1}|  (1)

For any integer k, one can easily show that there are at most 2 solutions to the congruence equation \overline{n} − \overline{n + 1} ≡ k (mod p). From this, we have

\frac{1}{8}p^{2} − \frac{1}{2}p ≤ ∑_{n=1}^{[p/4]} 4k ≤ S_{p} ≤ ∑_{n=p−[p/4]−2}^{p−2} 4k ≤ \frac{7}{8}p^{2} + \frac{7}{2}p

where [x] denotes the greatest integer ≤ x. So, S_{p} has order p^{2} and the natural question is whether lim_{p→∞} S_{p}/p^{2} exists. To this, we have the following.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A03 2

Theorem 1. For any prime p > 2,

S_{p} = ∑_{n=1}^{p−2} |\overline{n} − \overline{n + 1}| = \frac{1}{3}p^{2} + O(p^{3/2} log^{3} p).

Hence, on average, the difference between inverses of consecutive integers, |\overline{n}−\overline{n + 1}|, is about p/3. More generally, we have the following result.

Theorem 2. For any prime p > 2 and λ > 0,

∑_{n=1}^{p−2} |\overline{n} − \overline{n + 1}|^{λ} = \frac{2}{(λ + 1)(λ + 2)}p^{λ+1} + O(p^{λ+1/2} log^{3} p).

To prove Theorem 1 or 2, we are led to study

T_{+}(p, k) = #\{n : 0 < n < p, 0 < \overline{n} − \overline{n + 1} ≤ k\},
T_{−}(p, k) = #\{n : 0 < n < p, −k ≤ \overline{n} − \overline{n + 1} < 0\}, and
T (p, k) = T_{+}(p, k) + T_{−}(p, k) = #\{n : 0 < n < p, 0 < |\overline{n} − \overline{n + 1}| ≤ k\}

for integer 0 < k < p. We have

Theorem 3. For any prime p > 2 and any integer 0 < k < p,

T_{±}(p, k) = k − \frac{k^{2}}{2p} + O(p^{1/2} log^{3} p).

Our method of proof is motivated by Professor W.P. Zhang’s paper [5] involving Kloosterman sums and trigonometric sums. The proofs of Theorems 1, 2 and 3 extend to pairs \overline{n} and \overline{n + l} for fixed integer l ≢ 0 (mod p) with slight modifications.

2. Exponential and Kloosterman sums

First, we start with some notation. Letting e(y) = e^{2πiy}, we denote the Kloosterman sum

S(m, n; q) := ∑_{d (mod q)} ; (d,q)=1 e(\frac{md + n\overline{d}}{q}).

Lemma 1. Let p be a prime number. For any integer a and b ≢ 0 (mod p),

\begin{matrix}p \\ ∑ & ′ \\ x=1 \end{matrix} e( \frac{\frac{ax+b}{x(x±1)}}{p} ) ≪ p^{1/2}

where ∑′ is over all x (mod p) except the roots of x(x ± 1) in F_{p}.

Proof. It follows from the Bombieri-Weil bound [1] for exponential sums in the form by Moreno and Moreno [4, Theorem 2] provided that \frac{ax+b}{x(x±1)} is not of the form h(x)^{p} − h(x) with h(x) ∈ \overline{F}_{p}, where \overline{F}_{p} is the algebraic closure of F_{p}. This is true in our situation. For otherwise, say

\frac{ax + b}{x(x ± 1)} = (\frac{F (x)}{G(x)})^{p} − \frac{F (x)}{G(x)}

with F (x) and G(x) polynomials over \overline{F}_{p} such that (F (x), G(x)) = 1. Then

(ax + b)G(x)^{p} = x(x ± 1)F (x)(F (x)^{p−1} − G(x)^{p−1}).  (2)

Since F (x) and G(x) are relatively prime, we have G(x)^{p}|x(x ± 1). This forces G(x) to be a nonzero constant polynomial. Contradiction occurs if one compares the degrees in (2). □

Lemma 2. Let p > 2 be a prime number. For any integers r and s,

∑_{n=1}^{p−1} e(\frac{±n}{p})S(r, n; p)\overline{S(s, n; p)} ≪ p^{3/2}.  (3)

Here \overline{S(s, n; p)} stands for the complex conjugate of S(s, n; p).

Proof.

1. r ≡ 0 (mod p). Then S(r, n; p) = −1 for 1 ≤ n ≤ p − 1. So, the left side of (3) is

\begin{matrix}= & ∑_{n=1}^{p−1} e(\frac{±n}{p}) ∑_{d=1}^{p−1} e(\frac{−sd − n\overline{d}}{p}) \\ = & ∑_{d=1}^{p−1} e(\frac{−sd}{p}) ∑_{n=1}^{p−1} e(\frac{−n(\overline{d} ∓ 1)}{p}) ≪ ∑_{d=1}^{p−1} ; \overline{d}≢±1(p) 1 + p ≪ p. \end{matrix}

2. s ≡ 0 (mod p). Similar to case 1.

3. r ≢ s (mod p) and (r, p) = 1 = (s, p). The left hand side of (3)

\begin{matrix}= & ∑_{n=1}^{p−1} e(\frac{±n}{p}) ∑_{a=1}^{p−1} e(\frac{ra + n\overline{a}}{p}) ∑_{b=1}^{p−1} e(\frac{−sb − n\overline{b}}{p}) \\ = & ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{ra − sb}{p}) ∑_{n=1}^{p−1} e(\frac{(\overline{a} − \overline{b} ± 1)n}{p}) \\ = & ∑_{c=1}^{p−1} ∑_{d=1}^{p−1} e(\frac{r\overline{c} − s\overline{d}}{p}) ∑_{n=1}^{p−1} e(\frac{(c − d ± 1)n}{p}) \\ = & (p − 1) \begin{matrix}p \\ ∑ & ′ \\ d=1 \end{matrix} e(\frac{r\overline{d ∓ 1} − s\overline{d}}{p}) − \begin{matrix}∑_{c=1}^{p−1} & ∑_{d=1}^{p−1} \\ c≠d∓1 \end{matrix} e(\frac{r\overline{c} − s\overline{d}}{p}) \\ = & p \begin{matrix}p \\ ∑ & ′ \\ d=1 \end{matrix} e(\frac{r\overline{d ∓ 1} − s\overline{d}}{p}) − ∑_{c=1}^{p−1} e(\frac{r\overline{c}}{p}) ∑_{d=1}^{p−1} e(\frac{−s\overline{d}}{p}) \\ = & p \begin{matrix}p \\ ∑ & ′ \\ d=1 \end{matrix} e(\frac{[(r − s)d ± s]\overline{d(d ∓ 1)}}{p}) − 1 ≪ p\sqrt{p} \end{matrix}

by Lemma 1. Here ∑′ means summation over all d with (d, p) = 1 = (d ∓ 1, p). Note: The first sum in the second last line is a special case of Cobeli and Zaharescu [2, Lemma 1] or Cobeli, Gonek and Zaharescu [3, Lemma 1].

4. r ≡ s ≢ 0 (mod p). Similar to case 3. □

3. Theorem 3 when 0 < k < p/2

Now, we try to express T_{±}(p, k) as exponential sums similar to [5].

Lemma 3. For any prime p > 2 and any integer 0 < k < p/2,

\begin{aligned}T_{±}(p, k) = & \frac{1}{p^{2}} ∑_{m=1}^{p} ∑_{n=1}^{p} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p})[∑_{a=1}^{p−1} ∑_{b=1}^{p−k} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ & + ∑_{a=p−k+1}^{p−1} ∑_{b=p−k+1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p})]. \end{aligned}

Proof. We shall only prove the formula for T_{+}(p, k); the proof for T_{−}(p, k) is similar. Observe that T_{+}(p, k) = #\{a : 0 < a − b ≤ k, \overline{b} − \overline{a} = 1\}. Thus, as

∑_{n=1}^{p} e(\frac{nr}{p}) = \{ \begin{matrix}p, & p |r; \\ 0, & p |̸r, \end{matrix}  (4)

\begin{aligned}T_{+}(p, k) = & ∑_{t=1}^{k} \begin{matrix}∑_{a=1}^{p−1} & ∑_{b=1}^{p−1} \\ a−b=t,\overline{b}−\overline{a}=1 \end{matrix} 1 \\ = & \frac{1}{p^{2}} ∑_{m=1}^{p} ∑_{n=1}^{p} ∑_{t=1}^{k} \begin{matrix}∑_{a=1}^{p−1} & ∑_{b=1}^{p−1} \\ a>b \end{matrix} e(\frac{m(a − b − t)}{p})e(\frac{n(\overline{b} − \overline{a} − 1)}{p}) \\ = & \frac{1}{p^{2}} ∑_{m=1}^{p} ∑_{n=1}^{p} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{−mt}{p})[\begin{matrix}∑_{a=1}^{p−1} & ∑_{b=1}^{p−k} \\ a>b \end{matrix} e(\frac{ma − n\overline{a}}{p})e(\frac{−mb + n\overline{b}}{p}) \\ & + \begin{matrix}∑_{a=p−k+1}^{p−1} & ∑_{b=p−k+1}^{p−1} \\ a>b \end{matrix} e(\frac{ma − n\overline{a}}{p})e(\frac{−mb + n\overline{b}}{p})] \end{aligned} (5)

Note that we do not need the condition \overline{b} > \overline{a} because −p + 2 ≤ \overline{b} − \overline{a} ≤ p − 2 which does not allow \overline{b}−\overline{a} = 1−p (the only alternative besides 1 may be counted). Now t−p ≤ k−p. It is valid to drop the condition a > b in both double sums within the brackets because k − p < 1 − (p − k) ≤ a − b and k − p < −k < (p − k + 1) − (p − 1) ≤ a − b respectively (note: k < p/2 is used for the second chain of inequalities). Hence, only a − b = t is counted even without condition a > b and we have the lemma. □

Lemma 4. For any prime p > 2 and any integer 0 < k < p,

\begin{matrix}∑_{m=1}^{p} ∑_{n=1}^{p} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−k} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ = & kp(p − k) + O(p^{5/2} log^{2} p). \end{matrix}

Proof. We separate the left hand side into three pieces according to: (i) m = n = p, (ii) n = p and 1 ≤ m ≤ p − 1, (iii) 1 ≤ m ≤ p and 1 ≤ n ≤ p − 1. The left hand side of Lemma 4

\begin{matrix}= & kp(p − k) + O(p^{2}) + ∑_{m=1}^{p−1} ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−k} e(\frac{±ma}{p})e(\frac{∓mb}{p}) \\ + & ∑_{m=1}^{p} ∑_{n=1}^{p−1} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−k} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ = & kp(p − k) + O(p^{2}) + S_{1} + S_{2}. \end{matrix}  (6)

S_{1} ≤ ∑_{m=1}^{p−1} | ∑_{t=1}^{k} e(\frac{∓mt}{p})|| ∑_{b=1}^{p−k} e(\frac{∓mb}{p})| ≤ ∑_{m=1}^{p−1} \frac{1}{| sin (πm/p)|^{2}} ≪ ∑_{m=1}^{p−1} \frac{p^{2}}{m^{2}} ≪ p^{2} (7)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A03 6

by summing the geometric series and sin πx ≥ 2x for 0 ≤ x ≤ 1/2. By (4),

∑_{a=1}^{p−1} ∑_{b=1}^{p−k} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p})

=\frac{1}{p} ∑_{r=1}^{p} ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) ∑_{c=1}^{p−k} e(\frac{r(b − c)}{p})
=\frac{1}{p} ∑_{r=1}^{p} ∑_{c=1}^{p−k} e(\frac{−cr}{p})S(r ∓ m, ±n; p)\overline{S(∓m, ±n; p)}.

Hence, by Lemma 2,

S_{2} ≪\frac{1}{p} ∑_{m=1}^{p} | ∑_{t=1}^{k} e(\frac{∓mt}{p})| ∑_{r=1}^{p−1} | ∑_{c=1}^{p−k} e(\frac{−cr}{p})|p^{3/2} + ∑_{m=1}^{p} | ∑_{t=1}^{k} e(\frac{∓mt}{p})|p^{3/2}
≪p^{1/2}k ∑_{r=1}^{p−1} \frac{1}{| sin (πr/p)|} + p^{1/2}[∑_{m=1}^{p−1} \frac{1}{| sin (πm/p)|}]^{2} + p^{3/2}k
+p^{3/2} ∑_{m=1}^{p−1} \frac{1}{| sin (πm/p)|} ≪ p^{1/2}[∑_{m=1}^{[p/2]} \frac{p}{m}]^{2} + p^{3/2} ∑_{m=1}^{[p/2]} \frac{p}{m} ≪ p^{5/2} log^{2} p.

(8)

Combining (6), (7) and (8), we have the lemma. □ Lemma 5. For any prime p > 2 and any integer 0 < k < p/2,

\begin{aligned}& ∑_{m=1}^{p} ∑_{n=1}^{p} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=p−k+1}^{p−1} ∑_{b=p−k+1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ = & \frac{1}{2}pk^{2} + O(p^{5/2} log^{3} p). \end{aligned}

Proof. Similar to Lemma 4, we split the left hand side into three pieces which

\begin{matrix}= & k^{3} + O(p^{2}) + ∑_{m=1}^{p−1} ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=p−k+1}^{p−1} ∑_{b=p−k+1}^{p−1} e(\frac{±ma}{p})e(\frac{∓mb}{p}) \\ + ∑_{m=1}^{p} ∑_{n=1}^{p−1} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=p−k+1}^{p−1} ∑_{b=p−k+1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ = & k^{3} + O(p^{2}) + S_{1} + S_{2}. \end{matrix} (9)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A03 7

Replacing a by p − a and b by p − b,

\begin{matrix}S_{1} = & ∑_{m=1}^{p−1} ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{k−1} ∑_{b=1}^{k−1} e(\frac{∓ma}{p})e(\frac{±mb}{p}) \\ = & ∑_{t=1}^{k} ∑_{a=1}^{k−1} ∑_{b=1}^{k−1} ∑_{m=1}^{p} e(\frac{±m(b − a − t)}{p}) − k^{3} + O(k^{2}) \\ = & p ∑_{t=1}^{k} \begin{matrix}∑_{a=1}^{k−1} & ∑_{b=1}^{k−1} \\ b−a=t \end{matrix} 1 − k^{3} + O(k^{2}) = \frac{1}{2}pk^{2} − k^{3} + O(pk) \end{matrix}  (10)

because we may count b − a = t or b − a = t − p but the second case is not possible as t − p ≤ k − p < −k + 2 ≤ b − a. Here k < p/2 is crucial.

Applying (4) twice,

∑_{a=p−k+1}^{p−1} ∑_{b=p−k+1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p})

=\frac{1}{p^{2}} ∑_{r=1}^{p} ∑_{s=1}^{p} ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p})

× ∑_{c=p−k+1}^{p−1} e(\frac{r(a − c)}{p}) ∑_{d=p−k+1}^{p−1} e(\frac{s(b − d)}{p})

=\frac{1}{p^{2}} ∑_{r=1}^{p} ∑_{s=1}^{p} K(r)K(s)S(s ∓ m, ±n; p)\overline{S(∓m − r, ±n; p)}

where K(x) = ∑_{n=p−k+1}^{p−1} e(−nx/p). Rearranging the sums and applying Lemma 2,

S_{2} =\frac{1}{p^{2}} ∑_{m=1}^{p} ∑_{t=1}^{k} e(\frac{mt}{p}) ∑_{r=1}^{p} ∑_{s=1}^{p} K(r)K(s)

× ∑_{n=1}^{p−1} e(\frac{−n}{p})S(s ∓ m, ±n; p)\overline{S(∓m − r, ±n; p)}

≪\frac{1}{p^{1/2}} ∑_{m=1}^{p} | ∑_{t=1}^{k} e(\frac{mt}{p})| ∑_{r=1}^{p} |K(r)| ∑_{s=1}^{p} |K(s)|
≪\frac{1}{p^{1/2}} [k + ∑_{m=1}^{[p/2]} \frac{1}{| sin (πm/p)|}]^{3} ≪ \frac{1}{p^{1/2}} (k + p log p)^{3} ≪ p^{5/2} log^{3} p.

(11)

Combining (9), (10) and (11), we have the lemma. □

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A03 8

To prove Theorem 3 when 0 < k < p/2, apply Lemma 4 and 5 to Lemma 3 and get

T_{±}(p, k) = \frac{1}{p^{2}} [kp(p − k) + \frac{1}{2}pk^{2} + O(p^{5/2} log^{3} p)] = k − \frac{k^{2}}{2p} + O(p^{1/2} log^{3} p)

which gives Theorem 3 in that range of k.

4. Theorem 3 when p/2 < k < p Before proceeding, let us introduce some notation.

U_{+}(p, k) =#\{n : 0 < n < p, p − k ≤ \overline{n} − \overline{n + 1} < p\},
U_{−}(p, k) =#\{n : 0 < n < p, −p < \overline{n} − \overline{n + 1} ≤ −p + k\},
V_{+}(p, k) =#\{n; 0 < n < p, \overline{n} − \overline{n + 1} ≡ t (mod p) for 1 ≤ t ≤ k\},
V_{−}(p, k) =#\{n; 0 < n < p, \overline{n} − \overline{n + 1} ≡ −t (mod p) for 1 ≤ t ≤ k\}.

Then one can easily see that

V_{+}(p, k) = T_{+}(p, k) + U_{−}(p, k) and V_{−}(p, k) = T_{−}(p, k) + U_{+}(p, k).  (12)

Lemma 6. For any prime p > 2 and any integer 0 < k < p,

V_{±}(p, k) = \frac{1}{p^{2}} ∑_{m=1}^{p} ∑_{n=1}^{p} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}).

Proof. Use (4). Note: it is easier than Lemma 3 because one does not need to worry about a > b or a < b. □ Lemma 7. For any prime p > 2 and any integer 0 < k < p,

\begin{matrix}∑_{m=1}^{p} ∑_{n=1}^{p} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ = & kp^{2} + O(p^{5/2} log p) \end{matrix}

Proof. Similar to Lemma 4, we split the left hand side into three pieces which

\begin{matrix}= & kp^{2} + O(p^{2}) + ∑_{m=1}^{p−1} ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{±ma}{p})e(\frac{∓mb}{p}) \\ + ∑_{m=1}^{p} ∑_{n=1}^{p−1} e(\frac{−n}{p}) ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{a=1}^{p−1} ∑_{b=1}^{p−1} e(\frac{±ma ∓ n\overline{a}}{p})e(\frac{∓mb ± n\overline{b}}{p}) \\ = & kp^{2} + O(p^{2}) + S_{1} + S_{2}. \end{matrix}  (13)

By (4),

S_{1} ≤ ∑_{m=1}^{p−1} ∑_{t=1}^{k} 1 ≪ p^{2}.  (14)

After rearranging summations,

S_{2} = ∑_{m=1}^{p} ∑_{t=1}^{k} e(\frac{∓mt}{p}) ∑_{n=1}^{p−1} e(\frac{−n}{p})S(∓m, ±n; p)\overline{S(∓m, ±n; p)}

≪p^{3/2} ∑_{m=1}^{p}|∑_{t=1}^{k} e(\frac{∓mt}{p})|

≪p^{3/2}[k + ∑_{m=1}^{[p/2]} \frac{1}{| sin (πm/p)|}] ≪ p^{3/2}(k + p log p) ≪ p^{5/2} log p

(15)

by Lemma 2, summing the geometric series and sin (πx) ≥ 2x. We have the lemma by (13), (14) and (15). □

Lemma 8. For any prime p > 2 and any integer 0 ≤ k < p/2,

U_{±}(p, k) = \frac{k^{2}}{2p} + O(p^{1/2} log^{3} p).

Proof. First note that when k = 0, U_{±}(p, k) = 0. Now assume k > 0. From (12), U_{±}(p, k) = V_{∓}(p, k) − T_{∓}(p, k). Thus, by Lemma 6, 7 and Theorem 3 in the range 0 < k < p/2,

U_{±}(p, k) = k + O(p^{1/2} log p) − (k − \frac{k^{2}}{2p} + O(p^{1/2} log^{3} p))

which gives the lemma. □

To prove Theorem 3 when p/2 < k < p, observe that 0 ≤ p − k − 1 < p/2 and

T_{±}(p, k) =T_{±}(p, \frac{p − 1}{2}) + [U_{±}(p, \frac{p − 1}{2}) − U_{±}(p, p − k − 1)]
=\frac{p − 1}{2} − \frac{(\frac{p−1}{2})^{2}}{2p} + [\frac{(\frac{p−1}{2})^{2}}{2p} − \frac{(p − k − 1)^{2}}{2p} ] + O(p^{1/2} log^{3} p)
=\frac{p}{2} − \frac{p^{2} − 2pk + k^{2}}{2p} + O(1) + O(p^{1/2} log^{3} p)
=k − \frac{k^{2}}{2p} + O(p^{1/2} log^{3} p)

by Theorem 3 in the range 0 < k < p/2 and Lemma 8.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A03 10

5. Proof of Theorems 1 and 2 By Theorem 3, T (p, k) = 2k −k^{2}/p+O(p^{1/2} log^{3} p) for integer 0 < k < p. More generally,

T (p, u) = #\{n : 0 < |\overline{n} − \overline{n + 1}| ≤ u\} = 2u − \frac{u^{2}}{p} + O(p^{1/2} log^{3} p)  (16)

for any real number 0 ≤ u ≤ p. Using the Riemann-Stieltjes integral, integration by parts, and (16),

∑_{n=1}^{p−2} |\overline{n} − \overline{n + 1}|^{λ} = ∫_{0}^{p} u^{λ} dT (p, u) = T (p, p)p^{λ} − λ ∫_{0}^{p} u^{λ−1}T (p, u)du

=p^{λ+1} + O(p^{λ}) − λ ∫_{0}^{p} 2u^{λ} − \frac{u^{λ+1}}{p} + O(u^{λ−1}p^{1/2} log^{3} p) du
=p^{λ+1} − [\frac{2λ}{λ + 1}p^{λ+1} − \frac{λ}{λ + 2}p^{λ+1}] + O(p^{λ+1/2} log^{3} p)
=\frac{2}{(λ + 1)(λ + 2)}p^{λ+1} + O(p^{λ+1/2} log^{3} p)

which gives Theorem 2 and hence Theorem 1.

Numerical calculations (by a C++ program) suggest that the error term in Theorem 3 is probably best possible except for the extra logarithms.

Let m_{p}^{±} = max_{1≤k<p} |T_{±}(p, k) − (k − \frac{k^{2}}{2p})|.

\begin{matrix}p & 101 & 103 & 107 & 109 & 113 & 127 & 131 & 137 \\ m_{p}^{+}/\sqrt{p} & 0.4951 & 0.6103 & 0.9794 & 0.7504 & 0.4595 & 0.9122 & 0.6133 & 0.6401 \\ m_{p}^{−}/\sqrt{p} & 0.5951 & 0.7098 & 0.6993 & 0.4956 & 0.4812 & 0.7976 & 0.9067 & 0.5416 \end{matrix}

\begin{matrix}p & 5501 & 5503 & 5507 & 5519 & 5521 & 5527 & 5531 & 5557 \\ m_{p}^{+}/\sqrt{p} & 0.5786 & 0.6384 & 0.7021 & 0.6350 & 1.1337 & 0.4528 & 0.6928 & 0.7150 \\ m_{p}^{−}/\sqrt{p} & 0.5945 & 0.6532 & 0.7342 & 0.5888 & 1.0775 & 0.4621 & 0.7291 & 0.7530 \end{matrix}

\begin{matrix}p & 12301 & 12323 & 12329 & 12343 & 12347 & 12373 & 12377 & 12379 \\ m_{p}^{+}/\sqrt{p} & 0.5249 & 0.6978 & 0.8166 & 1.0416 & 1.1251 & 0.6540 & 0.8172 & 0.6914 \\ m_{p}^{−}/\sqrt{p} & 0.5521 & 0.6745 & 0.8101 & 1.0346 & 1.1069 & 0.6789 & 0.8144 & 0.6778 \end{matrix}

\begin{matrix}p & 60013 & 60017 & 60029 & 60037 & 60041 & 60077 & 60083 & 60089 \\ m_{p}^{+}/\sqrt{p} & 0.5172 & 0.7776 & 0.5806 & 0.8265 & 0.8441 & 0.9457 & 0.4469 & 0.5922 \\ m_{p}^{−}/\sqrt{p} & 0.5312 & 0.7789 & 0.5792 & 0.8411 & 0.8489 & 0.9514 & 0.4373 & 0.5897 \end{matrix}

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A03 11

We conclude with the following Conjecture 1.

m_{p}^{±} ≪ p^{1/2} and m_{p}^{+} − m_{p}^{−} = o(p^{1/2}).

Note: After finishing this paper, we came across Cobeli and Zaharescu [2], and found that it is far more general and would give

T_{±}(p, k) = k − \frac{k^{2}}{2p} + O(p^{5/6} log^{2/3} p).

Hence their method gives our results except for a bigger error term.

References

[1] E. Bombieri, On exponential sums in finite fields, Amer. J. Math. 88 (1966), 71-105.

[2] C.I. Cobeli and A. Zaharescu, The order of inverses mod q, Mathematika 47 (2000), 87-108.

[3] C.I. Cobeli, S.M. Gonek and A. Zaharescu, The distribution of patterns of inverses modulo a prime, J. Number Theory 101 (2003), 209-222.

[4] C.J. Moreno and O. Moreno, Exponential sums and Goppa codes. I, Proc. Amer. Math. Soc. 111 (1991), no. 2, 523-531.

[5] W.P. Zhang, On the Distribution of Inverses Modulo n, J. Number Theory 61 (1996), 301-310.