SIMULTANEOUS APPROXIMATIONS AND COVERING BY ARITHMETIC PROGRESSIONS IN 𝔽_{p}

VSEVOLOD F. LEV

Abstract. Given a set A = {a_{1}, …, a_{n}} ⊆ 𝔽_{p} of residues modulo prime p, we seek α, δ ∈ 𝔽_{p} (δ ≠ 0) which simultaneously minimize all the distances ∥δa_{i} − α∥ from the zero residue, and investigate the quantity

m_{n} = max_{|A|=n} min_{α,δ} max_{1≤i≤n} ∥δa_{i} − α∥,

the outer maximum being taken over all n-element subsets of 𝔽_{p}.

It is shown that this extremal simultaneous approximation problem is equivalent to the combinatorial problem of finding minimal l_{n} such that any set of n residues modulo p can be covered by an arithmetic progression of the length l_{n}.

For n ≥ 4, we determine the order of magnitude of m_{n} and prove that

\frac{1}{2}p^{1− \frac{1}{n−1}} (1 + o(1)) < m_{n} < n^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} (1 + o(1))

(as p → ∞ and n is small compared to p). For n = 3, we find a sharp asymptotic and moreover, prove that

−\sqrt[4]{p/3} < m_{3} − \sqrt{p/3} < 1/2.

These results answer a question of Straus about the maximum possible affine diameter of an n-element set of residues modulo a prime.

1. Introduction

One of the classical problems in Diophantine analysis is that of simultaneous approximation of n real numbers a_{i} (i = 1, …, n) by rational numbers p_{i}/q with common denominator q. The precision of such an approximation is usually measured by

max_{1≤i≤n} |qa_{i} − p_{i}|.

It is well-known that q ≠ 0 and p_{i} can always be chosen in such a way that the maximum above is less than q^{−1/n}, and this can be improved to cq^{−1/n} with a constant c = c(n) < 1. However, the exact determination of the smallest constant c with this property is a longstanding and apparently, very difficult problem.

The parallel problem for residues a_{i} modulo a prime p is to find a non-zero residue q which simultaneously minimizes all the distances ∥a_{i}q/p∥ from the nearest integers, the quality of approximation being measured by the product

p^{n}∥a_{1}q/p∥ … ∥a_{n}q/p∥.

2 VSEVOLOD F. LEV

In this case, even the order of magnitude of the minimal possible product for all q ∈ 𝔽_{p}^{×} is unknown. (See [3] or [4] for more details.)

In the present paper, we consider the following “interpolation” of these two problems. Let A = {a_{1}, …, a_{n}} ⊆ 𝔽_{p} be a set of residues modulo prime p. Define

m(A) = min_{α,δ} max_{1≤i≤n} ∥δa_{i} − α∥,

where α runs over all, and δ over all non-zero elements of 𝔽_{p}. Here and below we use the ∥ · ∥ sign to denote the distance from the zero residue: say, ∥2∥ = ∥ − 2∥ = 2 and ∥8∥ = 3 in 𝔽_{11}.

How large can m(A) be for a set A of given cardinality n = |A|? We write

m_{n} = max_{|A|=n} m(A).

Clearly, if A = {a_{1}} contains just one element, then m(A) = 0, and hence m_{1} = 0. Similarly, if A = {a_{1}, a_{2}}, then we choose δ to be the inverse in 𝔽_{p} of the difference a_{2} − a_{1} and choose α = δa_{1} to see that m(A) = 1, and therefore m_{2} = 1. However, the problem of estimating m_{3} is already non-trivial.

We now introduce another and closely related quantity. For A as above, let l(A) be the length of the shortest arithmetic progression modulo p which contains A:

l(A) = min_{\begin{matrix}a,d: \\ A⊆\{a,a+d,...,a+ld\} \end{matrix}} l.

Here a (the first term of the progression) runs over all, and d (the difference) over all non-zero elements of 𝔽_{p}. Note, that by the length of a progression we mean the number which is less by one than its cardinality. Finally, we define

l_{n} = max_{|A|=n} l(A),

the minimal integer l such that any n-element subset of 𝔽_{p} can be covered by an arithmetic progression of the length l.

The quantity l(A) was considered in [2] by Straus, who called it “the affine diameter of A” and raised the problem of estimating l_{n} — the maximum diameter of an n-element subset of 𝔽_{p}. (Straus’ original notation was d(A) for l(A) and g(n, p) for l_{n}.) We give this problem a complete solution and proceed to find as precise estimates of l_{n} as possible. For n = 3 we will even establish a sharp asymptotic: l_{3} = \sqrt{p/3} (1 + o(1)).

It follows immediately from the definition that l(A) = 0 if A = {a_{1}}, and l(A) = 1 if A = {a_{1}, a_{2}}. Thus, l_{1} = 0, and l_{2} = 1. In the sequel, we assume n ≥ 3.

It is easy to see that studying m_{n} is essentially equivalent to studying l_{n}.

SIMULTANEOUS APPROXIMATIONS IN 𝔽_{p} 3

Proposition 1. For any A ⊆ 𝔽_{p},

0 ≤ 2m(A) − l(A) ≤ 1.

Therefore,

0 ≤ 2m_{n} − l_{n} ≤ 1.

Proof. Write l = l(A). There exist a, d ∈ 𝔽_{p} such that A ⊆ {a, a + d, …, a + ld}. Let δ be the inverse of d in 𝔽_{p}. Then (a_{i} − a)δ ∈ {0, 1, …, l}(mod p) for any element a_{i} ∈ A, which shows that

m(A) ≤ ⌈\frac{l}{2}⌉ ≤ \frac{l(A) + 1}{2}.

On the other hand, write m = m(A). There exist δ ≠ 0 and α such that ∥δa_{i}−α∥ ≤ m for any a_{i} ∈ A. Define d to be the inverse of δ in 𝔽_{p}. Then a_{i} ∈ {αd − md, αd − (m − 1)d, …, αd + md} for all i = 1, …, n, and thus

l(A) ≤ 2m = 2m(A).
□

Proposition 1 allows us to formulate our results in terms of one of the quantities l_{n} and m_{n} only, whichever is more convenient.

Theorem 1. Suppose that p > 6^{n−1}/n. Then

p^{1− \frac{1}{n−1}} (1 − np^{− \frac{1}{n−1}} ) < l_{n} < 2n^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} .

This theorem establishes the order of magnitude of l_{n} (and hence also m_{n}) as p → ∞ and n is relatively small, say p > (2n)^{n−1}. We can cover a wider range of n at the expense of a slight relaxation of the coefficients:

Theorem 2. For any p and n,

(n/2)^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} − 1 < l_{n} < 2p^{1− \frac{1}{n−1}} (1 + \{p^{\frac{1}{n−1}} \}/⌊p^{\frac{1}{n−1}} ⌋) ,

where {·} stands for the fractional, and ⌊·⌋ for the integer part functions.

The upper bounds of Theorems 1 and 2 are proved in Section 2, and the lower bounds in Section 3.

Which of the estimates of Theorem 1 is closer to reality when n is fixed and p → ∞? Both Theorem 3 below and the numerical evidence for n = 4 suggest that it is the upper-bound estimate.

Conjecture 1. Suppose that n ≥ 3 is fixed and p → ∞. Then

l_{n} = 2n^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} (1 + o(1)).

Our next result (proved in Section 4) establishes a strong form of this conjecture for n = 3.

Theorem 3. For p ≥ 3,

2\sqrt{p/3} − 2\sqrt[4]{p/3} < l_{3} < 2\sqrt{p/3}.

Note that no analogous results are known for the two problems mentioned in the beginning of this section.

In certain additive problems, the following question is important (see [1]): given a set A ⊆ 𝔽_{p} of n residues, can one cover A by an arithmetic progression of length less than p/2? The upper bound of Theorem 2 shows that this is always possible provided

(1)  n ≤ \frac{1}{2} log_{2} p

(whence p^{1/(n−1)} > 4). On the other hand, the lower bound of Theorem 2 implies that l_{n} > p/2 as soon as 2^{n−1}/n > p. Thus, if n is so large, there exists an n-element set A ⊆ 𝔽_{p} such that l(A) > p/2. Theorem 2, however, provides no explicit construction for this A. We give such a construction in the last section of our paper. Specifically, we consider

A = {0, 1, 2, 4, …, 2^{n−2}} (mod p),

where n is defined by p/2 < 2^{n−2} < p, and prove that l(A) > p/2. This implies that l_{n} > p/2 for n = ⌊log_{2} p⌋ + 2, and thus (1) is not only sufficient, but also essentially necessary in order for l(A) < p/2 to hold.

2. Upper-bound estimates

It is easy to obtain an upper-bound estimate for m_{n} (and thus for l_{n}) using the Dirichlet boxing principle in the same way one does in the real case.

Given a set A = {a_{1}, …, a_{n}} ⊆ 𝔽_{p}, with any residue u ∈ 𝔽_{p} we associate an integer vector z^{(u)} = (z_{1}^{(u)}, …, z_{n}^{(u)}) ⊆ [0, p)^{n}, where the ith coordinate z_{i}^{(u)} is the integer number in [0, p) which satisfies z_{i}^{(u)} ≡ a_{i}u(mod p). We partition the n-dimensional cube [0, p)^{n} into (⌊p^{1/n}⌋)^{n} < p small cubes with the edge lengths p/⌊p^{1/n}⌋ = p^{1−1/n}(1 + o(1)), and notice that there exist two points z^{(u)}, z^{(v)} (corresponding to two distinct residues u, v ∈ 𝔽_{p}) in the same small cube. We then define δ = u − v to obtain ∥δa_{i}∥ < p^{1−1/n}(1 + o(1)) for all i. As A is arbitrary, this proves

m_{n} < p^{1− \frac{1}{n}} (1 + o(1))

(for p sufficiently large compared to n).

A comparison with Theorem 1 shows that the order of magnitude in this estimate is close, but not equal to the true one. We can improve it and obtain an estimate of

SIMULTANEOUS APPROXIMATIONS IN 𝔽_{p} 5

best possible order if we observe that m(A) does not change under translations of A: specifically, m(A − c) = m(A) for any c ∈ 𝔽_{p}, and similarly, l(A − c) = l(A). This is readily seen from the definitions of m(A) and l(A). Thus, when estimating m(A) we can assume a_{n} = 0. Now, with each u ∈ 𝔽_{p} we associate the vector z^{(u)} = (z_{1}^{(u)}, …, z_{n−1}^{(u)}) of dimension n − 1 (sic!), all z_{i}^{(u)} being defined as above, and we repeat the argument to get

m_{n} < p/⌊p^{\frac{1}{n−1}} ⌋ = p^{1− \frac{1}{n−1}} (1 + o(1)).

To prove the upper bound of Theorem 2 we apply Proposition 1:

(2)  l_{n} ≤ 2m_{n} < 2p/⌊p^{\frac{1}{n−1}} ⌋ = 2p^{1− \frac{1}{n−1}} (1 + \{p^{\frac{1}{n−1}} \}/⌊p^{\frac{1}{n−1}} ⌋) .

To obtain a better constant and prove the upper bound of Theorem 1, we replace the boxing principle by Minkowski’s theorem. Instead of the finite system of points z^{(u)}, we consider the lattice Λ of all the integer points which are congruent modulo p to any of the points z^{(u)}:

Λ = {z = (z_{1}, …, z_{n}) ∈ ℤ^{n}: z_{1} ≡ ua_{1}, …, z_{n} ≡ ua_{n} (mod p) for some u ∈ 𝔽_{p}}.

As Λ is a union of p disjoint translates of the lattice pℤ^{n}, we have

det Λ = [ℤ^{n} : Λ] = \frac{1}{p} [ℤ^{n} : pℤ^{n}] = p^{n−1}.

Instead of the small cubes, we consider now a convex body

K(λ) = {x = (x_{1}, …, x_{n}) ∈ ℝ^{n}: |x_{i} − x_{j}| ≤ λ for all 1 ≤ i, j ≤ n, and |x_{n}| < p},

where λ is a positive parameter, to be specified below.

For ξ ∈ ℝ, let K_{ξ}(λ) be the intersection of K(λ) with the hyperplane x_{n} = ξ. Clearly, K_{ξ}(λ) = ∅, if |ξ| ≥ p, and K_{ξ}(λ) = (ξ, …, ξ) + K_{0}(λ), if |ξ| < p. Thus, by Cavalieri’s principle, the volume of K(λ) is

(3)  μ(K(λ)) = 2pμ(K_{0}(λ))

(we use the same letter μ to denote both “volumes” and “areas” in ℝ^{n}.) To evaluate μ(K_{0}(λ)) we need the following technical lemma.

Lemma 1. For t ∈ [1/2, 1], define

B_{n}(t) = {x = (x_{1}, …, x_{n}) ∈ ℝ^{n}: |x_{i}| ≤ t, |x_{i} − x_{j}| ≤ 1 for all 1 ≤ i, j ≤ n}.

Then

μ(B_{n}(t)) = 2nt − (n − 1).

Proof. We argue by induction by n. For n = 1 the assertion is trivial. For n ≥ 2,

μ(B_{n}(t)) = 2 ∫_{0}^{t} dx_{n} ∫ ⋯ ∫\begin{matrix}|x_{i}−x_{j}|≤1 \\ max\{x_{n}−1,−t\}≤x_{i}≤t \end{matrix} dx_{1} … dx_{n−1}

= 2 ∫_{0}^{1−t} dx_{n} ∫ ⋯ ∫\begin{matrix}|x_{i}−x_{j}|≤1 \\ −t≤x_{i}≤t \end{matrix} dx_{1} … dx_{n−1}

+ 2 ∫_{1−t}^{t} dx_{n} ∫ ⋯ ∫\begin{matrix}|x_{i}−x_{j}|≤1 \\ x_{n}−1≤x_{i}≤t \end{matrix} dx_{1} … dx_{n−1}

(the indices i and j in the integrals’ limits range from 1 to n − 1.) The first of the inner integrals on the right-hand side is clearly μ(B_{n−1}(t)). In the second inner integral we introduce new variables y_{i} = x_{i} + (1 − x_{n} − t)/2 to rewrite it as

∫ ⋯ ∫ \begin{matrix}|y_{i}−y_{j}|≤1 \\ |y_{i}|≤(1−x_{n}+t)/2 \end{matrix}dy_{1} … dy_{n−1} = μ(B_{n−1}((1 − x_{n} + t)/2)).

Now by the induction hypothesis,

μ(B_{n}(t)) = 2(1 − t)(2(n − 1)t − (n − 2)) + 2 ∫_{1−t}^{t}((n − 1)(1 − x_{n} + t) − (n − 2))dx_{n}
= 2(1 − t)(2(n − 1)t − (n − 2)) + (n − 1)(4t^{2} − 1) − 2(n − 2)(2t − 1)
= 2nt − (n − 1).
□

We continue the proof of the upper-bound estimate of Theorem 1. Identifying the hyperplane x_{n} = 0 with ℝ^{n−1}, we can write K_{0}(1) = B_{n−1}(1), and by (3) and Lemma 1,

μ(K(λ)) = 2pλ^{n−1}μ(K_{0}(1)) = 2pλ^{n−1}μ(B_{n−1}(1)) = 2npλ^{n−1}.

Suppose that λ > 2n^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} . Then

μ(K(λ)) = 2npλ^{n−1} > 2^{n}p^{n−1} = 2^{n} det Λ,

and by the theorem of Minkowski on convex body, there exists a non-zero point z = (z_{1}, …, z_{n}) ∈ Λ ∩ K(λ). It follows that there also exists such a point in Λ ∩ K(λ_{0}), where λ_{0} = ⌊2n^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} ⌋.

Let now u ∈ 𝔽_{p} be the residue satisfying z_{i} ≡ ua_{i} (mod p) (for i = 1, …, n.) We first show that u ≢ 0(mod p). Indeed, otherwise z_{i} ≡ 0(mod p) for all indices i, which in view of |z_{n}| < p, |z_{i} − z_{n}| ≤ λ_{0} < p would imply z_{n} = 0 and then z_{i} = 0 for all i.

Therefore, we have found a non-zero residue u such that ∥a_{i}u − a_{j}u∥ ≤ λ_{0} for all pairs of indices 1 ≤ i, j ≤ n. Since

λ_{0} < 2p(np)^{− \frac{1}{n−1}} < p/3,

SIMULTANEOUS APPROXIMATIONS IN 𝔽_{p} 7

(here we use the assumption p > 6^{n−1}/n), this clearly implies a_{i}u ∈ {a, a + 1, …, a + λ_{0}} (mod p) for some integer a, thus l(A) ≤ λ_{0} < 2n^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} , completing the proof.

3. Lower-bound estimates

To obtain a first rough estimate of l_{n} from below, one can use a straightforward counting argument^{1}. We have as many as p(p − 1) arithmetic progressions of the length l_{n}, for there are p choices for the first element and p − 1 choices for the difference of the progression. Next, each progression covers \binom{l_{n}+1}{n} subsets of 𝔽_{p} of cardinality n. Since any subset is covered at least twice (to any covering by a progression with the difference d there corresponds a covering by a progression with the difference −d), we can write

(4)  p(p − 1) \binom{l_{n} + 1}{n} ≥ 2\binom{p}{n},

or equivalently

p(p − 1) \frac{(l_{n} + 1)l_{n} ⋯ (l_{n} + 2 − n)}{p(p − 1) ⋯ (p + 1 − n)} ≥ 2.

In view of

\frac{l_{n} − i + 1}{p − i} ≤ \frac{l_{n} + 1}{p} (i = 0, 1, …)

this yields

p^{2} (\frac{l_{n} + 1}{p})^{n} > 2,

l_{n} > 2^{\frac{1}{n}} p^{1− \frac{2}{n}} − 1. (5)

This estimate can be improved to produce a correct order of magnitude using an idea, similar to that we employed for upper bounds. Namely, we observe that any n-element subset of 𝔽_{p} can be covered by a progression of length l_{n} in such a special way that the first term of the progression is an element of the subset under consideration. Each progression covers in this way \binom{l_{n}}{n−1} subsets, whence (4) can be replaced by the stronger inequality

p(p − 1) \binom{l_{n}}{n − 1} ≥ 2\binom{p}{n},

1I discovered the paper of Straus [2] when my own paper was already completed. It turned out that I went exactly the same way as Straus, who used the same kind of ideas to establish estimates similar to (2) and (3). The reader will see how close Straus was to answering his own question about the true order of magnitude of l_{n}.

which gives

(p − 1) \frac{l_{n}(l_{n} − 1) ⋯ (l_{n} + 2 − n)}{(p − 1)(p − 2) ⋯ (p + 1 − n)} ≥ \frac{2}{n},

p (\frac{l_{n} + 1}{p})^{n−1} > \frac{2}{n},

l_{n} > (n/2)^{− \frac{1}{n−1}} p^{1− \frac{1}{n−1}} − 1

proving the lower-bound estimate of Theorem 2.

We use an explicit construction to obtain a better constant and prove the lower bound of Theorem 1.

Specifically, for x ∈ ℤ, x ≥ 1 consider

A_{x} = {0, 1, x, x^{2}, …, x^{n−2}} (mod p).

Clearly, l(A_{x}) ≤ x^{n−2}. We show that equality holds provided

(6)  x^{n−1} − x ≤ p.

Choosing then x = ⌊p^{\frac{1}{n−1}} ⌋, we obtain

l_{n} ≥ (p^{\frac{1}{n−1}} − \{p^{\frac{1}{n−1}} \})^{n−2}
= p^{1− \frac{1}{n−1}} (1 − \{p^{\frac{1}{n−1}} \}p^{− \frac{1}{n−1}} )^{n−2}
> p^{1− \frac{1}{n−1}} (1 − np^{− \frac{1}{n−1}} ) .

Therefore, to complete the proof of Theorem 1 it remains to verify that l(A_{x}) = x^{n−2}, provided (6) holds true.

Assume the opposite: l(A_{x}) < x^{n−2}. Then there exist a, d ∈ 𝔽_{p} (d ≠ 0) and pairwise distinct integers 1 ≤ k′, k_{0}, k_{1}, …, k_{n−2} ≤ x^{n−2} such that

{a + k′d ≡ 0 (mod p) a + k_{0}d ≡ 1 (mod p) a + k_{1}d ≡ x (mod p) ⋮ a + k_{n−2}d ≡ x^{n−2} (mod p) .

SIMULTANEOUS APPROXIMATIONS IN 𝔽_{p} 9

Subtracting first of these congruences from the others, we get

{(k_{0} − k′)d ≡ 1 (mod p) (k_{1} − k′)d ≡ x (mod p) ⋮ (k_{n−2} − k′)d ≡ x^{n−2} (mod p) .

Now we divide each congruence, except for the first, by the previous one:

(7)  {k_{1} − k′  ≡ (k_{0} − k′)x (mod p) ; ⋮ ; k_{n−2} − k′ ≡ (k_{n−3} − k′)x (mod p) .

The crucial observation is that for each index i ∈ [1, n − 2], we have

(k_{i−1} − k′)x − (k_{i} − k′) = k_{i−1}x − k′(x − 1) − k_{i}
≤ x^{n−2}x − (x − 1) − 2
= x^{n−1} − x − 1
≤ p − 1,

and similarly,

(k_{i−1} − k′)x − (k_{i} − k′) = k_{i−1}x − k′(x − 1) − k_{i}
≥ x − x^{n−2}(x − 1) − (x^{n−2} − 1)
= −x^{n−1} + x + 1
≥ −p + 1.

Therefore, (7) implies the system of equalities in ℤ:

{k_{1} − k′  = (k_{0} − k′)x ; ⋮ ; k_{n−2} − k′ = (k_{n−3} − k′)x.

Multiplying through, we obtain

k_{n−2} − k′ = x^{n−2}(k_{0} − k′).

However, this is impossible in view of

|k_{n−2} − k′| ≤ x^{n−2} − 1 < x^{n−2} ≤ x^{n−2}|k_{0} − k′|.

This contradiction completes the proof of (the lower bound of) Theorem 1.

10 VSEVOLOD F. LEV

4. Determining the constant for n = 3

In this section we prove Theorem 3. In fact, its upper-bound estimate is a particular case of Theorem 1, and we concentrate on the lower bound. Our proof requires p to be sufficiently large, specifically, p ≥ 487. We assume this to be satisfied below; for 3 ≤ p < 487, we used a Maple program to verify the assertion.

We have to prove the existence of a 3-element subset A ⊆ 𝔽_{p} such that

l(A) > 2\sqrt{p/3} − 2\sqrt[4]{p/3}.

We seek a set of the special form A = {0, 1, a}. (The point here is that any 3-element subset of 𝔽_{p} can be reduced to a set of this form by a linear transformation without changing its length.) It is convenient to consider the elements of A as integer numbers, identifying them with the corresponding residues and assuming a ∈ [2, p). Let v and δ be integers such that

(8)  A = {0, 1, a} ⊆ {v, v + δ, …, v + l(A)δ} (mod p).

Defining d, u and v′ to be integer numbers in the range (−p/2, p/2) which satisfy

dδ ≡ 1, u ≡ ad, v′ ≡ vd (mod p),

we get

(9)  {0, d, u} ⊆ {v′, v′ + 1, …, v′ + l(A)} (mod p).

Moreover, we can assume d to be positive and therefore in the range d ∈ [1, p/2) — otherwise replace v by v + l(A)δ and δ by −δ in (8).

Since l(A) ≤ l_{3} < \sqrt{p/3} < p/2 and since 0 is an element of the set on the right-hand side of (9), it follows that this set is a subset of (−p/2, p/2), and thus actually

{0, d, u} ⊆ {v′, v′ + 1, …, v′ + l(A)},

both sides considered as sets of integers. This shows that the difference of any two numbers from {0, d, u} does not exceed l(A) in absolute value, whence

1 ≤ d ≤ l(A), d − l(A) ≤ u ≤ l(A).

We put

X = 2\sqrt{p/3} − 2\sqrt[4]{p/3},
Y = \sqrt{3p} + 3\sqrt[4]{p/3},
Z = ⌈Y ⌉,

so that

ZX < (Y + 1)X = 2p − 4\sqrt{p/3} − 2\sqrt[4]{p/3} < 2p.

SIMULTANEOUS APPROXIMATIONS IN 𝔽_{p} 11

It follows from the discussion above that if l(A) ≤ X for any 3-element set A ⊆ 𝔽_{p}, then to each a ∈ [2, p) there correspond u, d ∈ ℤ such that

1 ≤ d ≤ X, d − X ≤ u ≤ X,

and

u ≡ ad (mod p).

Our first step is to make this congruence an equality between integer numbers by choosing a in the range X < a ≤ Z. Indeed, in this case

X < a ≤ ad = (a − 1)d + d ≤ (Z − 1)X + d < 2p + d − X,
ad − 2p < d − X, ad > X,

implying u = ad − p. To sum up: assuming l_{3} ≤ X, for each a ∈ (X, Z] there exists d ∈ [1, X] such that d − X ≤ ad − p ≤ X, and so the interval

I_{a} = [β_{a}, γ_{a}] = [\frac{p − X}{a − 1} , \frac{p + X}{a} ]

contains an integer number d. We show, however, that this is not true. (It is worth pointing out that the length of I_{Z} is

|I_{Z}| = γ_{Z} − β_{Z} = 1 − O(p^{−1/2}),

and I_{a} for a < Z is even longer, so we must be very accurate in carrying this plan out.) We notice that

β_{Z} < β_{Z−1} < β_{Z−2} < …,
γ_{Z} < γ_{Z−1} < γ_{Z−2} < …,

so that each interval I_{a−1} is situated “to the right” of the interval I_{a}. Furthermore, I_{a−3} and I_{a} are disjoint for any a ∈ (X + 3, Z]:

I_{a} ∩ I_{a−3} = ∅.

This follows from

ZX < 2p,
aX < 2(p + X),
(p + X)(a − 4) < (p − X)a,
γ_{a} < β_{a−3}.

We now consider the union

(10)  I_{Z} ∪ I_{Z−3} ∪ ⋯ ∪ I_{Z−3k} ⊆ [β_{Z}, γ_{Z−3k}],

12 VSEVOLOD F. LEV

where k is a positive integer satisfying

(11)  Z − 3k > X,

the exact value of which will be specified later. Since we assume each of the k + 1 intervals on the left-hand side of (10) to contain an integer number, and the intervals are pairwise disjoint, we must have

γ_{Z−3k} − β_{Z} ≥ k,

that is

(12)  f(Z, k) ≥ 0,

where

f(ζ, κ) = \frac{p + X}{ζ − 3κ} − \frac{p − X}{ζ − 1} − κ.

To get rid of the “smallest integer symbol” in the definition of Z, we observe that

\frac{∂f(ζ, κ)}{∂ζ} = \frac{p − X}{(ζ − 1)^{2}} − \frac{p + X}{(ζ − 3κ)^{2}} < 0,

whence (12) implies

f(Y, k) ≥ 0

in view of Y ≤ Z.

To obtain a contradiction, we define

k = ⌈\sqrt[4]{p/3}⌉ ,

so that condition (11) is easily seen to be satisfied. As

\frac{∂f(Y, κ)}{∂κ} = \frac{3(p + X)}{(Y − 3κ)^{2}} − 1 > 0

for κ ≥ \sqrt[4]{p/3}, it suffices to verify that f(Y, \sqrt[4]{p/3} + 1) ≤ 0, i.e., that

(p + X)(Y − 1) − (p − X)(Y − 3\sqrt[4]{p/3} − 3) ≤ (\sqrt[4]{p/3} + 1)(Y − 1)(Y − 3\sqrt[4]{p/3} − 3).

After substitution of the values of X and Y and simplifications, this can be rewritten as

p^{3/4} − 7 · 3^{−3/4}p^{1/2} − 14 · 3^{−1/2}p^{1/4} + 3 ≥ 0.

A routine verification shows that this holds for all p ≥ 487.

This completes the proof of Theorem 3.

Computations show that in fact, the value of l_{3} is amazingly close to its upper bound 2\sqrt{p/3}. For instance, for over 55% of all 81 prime numbers between 100000 and 101000, we have l_{3} > 2\sqrt{p/3} − 3; for all the rest, l_{3} is within a distance of at most 6.5 from 2\sqrt{p/3}. Here is another striking example. By Proposition 1, the inequality l_{3} < 2\sqrt{p/3} implies that m_{3} < \sqrt{p/3} + 1/2, and at the first sight the constant 1/2 on the right-hand

SIMULTANEOUS APPROXIMATIONS IN 𝔽_{p} 13

side might be regarded as a technical annoyance. However, there are 5 primes in the range above for which m_{3} > \sqrt{p/3} !

5. Covering by arithmetic progressions of length p/2

In this section we show that the set

A = {0, 1, 2, 4, …, 2^{n−2}} (mod p),

where n is defined by p/2 < 2^{n−2} < p, is “long”: l(A) > p/2 (see Section 1 for related discussion). While the construction of Section 3 makes this fairly plausible, we cannot use the estimate established there as the condition x^{n−1} − x ≤ p is not satisfied with x = 2 — except in the very special case of Mersenne prime p = 2^{n−1} −1. For this reason, we have to employ another argument.

Assume that l(A) < p/2. Then there exist residues a, δ ∈ 𝔽_{p} such that δ ≠ 0 and

(13)  A_{δ} ∩ C(a) = ∅,

where A_{δ} and C(a) are subsets of 𝔽_{p} defined by

A_{δ} = {0, δ, 2δ, 4δ, …, 2^{n−2}δ},
C(a) = {a + 1, a + 2, …, a + (p − 1)/2}.

Letting i be the minimum non-negative integer such that a − i ∈ A_{δ}, we can replace a by a − i to obtain a ∈ Aδ. Moreover, if a = 0, then

{0, δ, 2δ, 4δ, …, 2^{n−2}δ} ∩ {1, 2, …, (p − 1)/2} = ∅

(considering both sets as subsets of 𝔽_{p}), whence

{0, −δ, −2δ, −4δ, …, −2^{n−2}δ} ∩ {(p + 1)/2, …, p − 2, p − 1} = ∅

also, and this shows that in (13) we can assume not only a ∈ A_{δ}, but also a ≠ 0. Thus, we suppose a = 2^{i}δ for some i ∈ [0, n − 2].

We observe now that

2a = a + a ∈ C(a),

as otherwise

a ∉ {1, 2, …, (p − 1)/2} (mod p),
a ∈ {(p + 1)/2, (p + 3)/2, …, p} (mod p)

and hence 0 ∈ C(a) ∩ A_{δ}. It follows that in a = 2^{i}δ we actually have i = n − 2, as if i < n − 2 then

2a = 2^{i+1}δ ∈ A_{δ}

which is inconsistent with 2a ∈ C(a).

Let integer numbers α_{0}, α_{1}, …, α_{n−2} ∈ [1, p − 1] be defined by

α_{j} ≡ 2^{j}δ (mod p), j = 0, …, n − 2.

Thus, α_{n−2} ≡ a(mod p) and

(14)  α_{n−2} < p/2

since 0 ∉ C(a).

We use descending induction to show that

(15)  α_{n−2} = 2^{n−2−j}α_{j} for j = n − 2, n − 3, …, 0.

Indeed, suppose (15) to be proved for n − 2, n − 3, …, j + 1 (with 0 ≤ j ≤ n − 3). To establish (15) for j, we first prove that α_{j+1} is even. Assuming the opposite, we would have

α_{j} ≡ \frac{p + α_{j+1}}{2} ≡ a + \frac{p − 2α_{n−2} + α_{j+1}}{2} ∈ C(a) (mod p)

in view of

2α_{n−2} − α_{j+1} < (2 − 2^{−(n−3−j)}) \frac{p}{2} = (1 − 2^{−(n−2−j)})p < p.

Thus α_{j+1} is even and by α_{j+1} ≡ 2α_{j} (mod p), this immediately gives α_{j+1} = 2α_{j}. Therefore,

α_{n−2} = 2^{n−3−j}α_{j+1} = 2^{n−2−j}α_{j}

proving (15) for the index j.

In particular, applying (15) with j = 0 we see that

α_{n−2} = 2^{n−2}α_{0} ≥ 2^{n−2} > p/2

which does not agree with (14). Thus the assumption that l(A) < p/2 leads to a contradiction.

References

[1] Yu. Bilu, V. Lev and I.Z. Ruzsa, Rectification principles in additive number theory, Discrete & Computational Geometry, 19 (1998), no. 3, Special Issue, 343–353.

[2] E.G. Straus, Differences of residues (mod p), J. Number Theory, 8 (1976), 40–42.

[3] T.W. Cusick, Products of simultaneous approximations of rational numbers, Archiv der Mathematik, 53 (1989), 154–158.

[4] , Zaremba’s conjecture and sums of the divisor function, Mathematics of Computation, 61 (203) (1993), 171–176.

Department of Mathematics, The University of Georgia, Athens, GA 30602, USA

  E-mail address: seva@@math.uga.edu