INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A07

A SHORT PROOF OF A KNOWN DENSITY RESULT

Timothy Foo

Department of Mathematics and Computer Science, Rutgers University - Newark, Newark, NJ 07102, USA

                         tfoo@andromeda.rutgers.edu

Received: 7/26/06, Revised: 1/25/07, Accepted: 1/31/07, Published: 2/3/07

Abstract

A combination of elementary methods and Dirichlet’s theorem on the infinitude of primes in arithmetic progressions is used to prove that a certain interesting set is dense in the unit square. The construction of the set involves how an element is related to its multiplicative inverse in the group (Z/pZ)^{∗}.

1. Introduction

The main aim of this paper is to present a short proof of the density of a certain subset of the unit square. The set whose density is proved is the set ⋃_{p}\{(\frac{x}{p}, \frac{y}{p}) : 1 ≤ x, y < p, and xy = 1 mod p}. The results obtained here follow from known results on Kloosterman and hyper-Kloosterman sums. Stronger results can be obtained by using estimates for Kloosterman and hyper-Kloosterman sums. What actually happens (but is not proved here) is the following: Let μ be the normalized Haar measure on the unit square T^{2}. Let Y_{p} = \{(\frac{x}{p}, \frac{y}{p}) : 1 ≤ x, y < p, xy = 1 mod p}. Clearly, |Y_{p}| = p − 1. Let Ω be a domain in T^{2} with piecewise smooth boundary. Then |Y_{p} ⋂ Ω| = μ(Ω)(p − 1)+ “nice error term”. Therefore, if Ω is a circle of radius ϵ, |Y_{p} ⋂ Ω| > 1 for p sufficiently large. This implies density. See for example [1],[2],[3],[4] and the references therein. It is worth noting that although this proof is short, it uses Dirichlet’s theorem on the infinitude of primes in arithmetic progressions.

2. The Construction of the Set

Definition 1 Here, (Z/pZ)^{∗} will consist of the numbers 1, 2, …, p − 1 rather than the equivalence classes pZ+i. Then \frac{x}{p} is naturally a rational number between 0 and 1 and (\frac{x}{p}, \frac{y}{p}) is naturally a point in the unit square with rational coordinates for x, y ∈ (Z/pZ)^{∗}. By imposing the condition xy = 1 (mod p) for the point (\frac{x}{p}, \frac{y}{p}) and taking all such points for a given prime p, one obtains a finite number of points. By taking the union over all primes p of such a set, one obtains a countable subset of the unit square:

A = ⋃_{p}\{(\frac{x}{p}, \frac{y}{p}) : xy = 1 mod p, x, y ∈ (Z/pZ)^{∗}\}.

Definition 2 We denote the set B by B = \{(\frac{a}{n}, \frac{n}{b}) : (a, n) = (b, n) = 1, a < n < b\}.

3. Proof of Density

Lemma 1 The set B is dense in the unit square.

Proof. Take n to be prime to make the proof easier. For fixed n, the x-coordinates \frac{a}{n} are distance \frac{1}{n} apart while the distance between the y-coordinates \frac{n}{b} is bounded by

max(\frac{n}{(n+1)(n+2)}, \frac{2n}{(2n−1)(2n+1)}).

As n → ∞, the distances between the x and y coordinates go to zero. □

Lemma 2 For any point b ∈ B, there exist points in A that are arbitrarily close to b.

Proof. Let p ≡ −a^{−1}b (mod n) and p ≡ −1 (mod b). This is possible due to the Chinese Remainder Theorem. Then x = \frac{ap+b}{n} and y = \frac{n(p+1)}{b} are integers. Furthermore, it is easily verified that xy ≡ 1 (mod p). Then applying Dirichlet’s Theorem on the infinitude of primes in arithmetic progressions, there are infinitely many primes satisfying this property. Furthermore, as p → ∞, \frac{x}{p} → \frac{a}{n} and \frac{y}{p} → \frac{n}{b}. □

From Lemmas 1 and 2 we have the following result.

Theorem 1 A is dense in the unit square.

4. Generalizations to Congruence Classes.

Let C = uZ+v be any congruence class with infinitely many primes. So (u, v) = 1. Theorem 1 can be strengthened as follows.

Theorem 2 The set ⋃_{p∈C}\{(\frac{x}{p}, \frac{y}{p}) : xy ≡ 1 (mod p), x, y ∈ (Z/pZ)^{∗}\} is dense in the unit

square.

Proof. Modify the set B to the following set \{(\frac{a}{n}, \frac{n}{b}) : (a, n) = (b, n) = (u, n) = (u, b) = 1\}. This set is still dense in the unit square because u is divisible by a finite number of primes. If n is a fixed odd prime not dividing u, the distance between the x-coordinates is still \frac{1}{n} while the distance between the y-coordinates is still bounded by something depending only on n and the number of prime factors of u which is constant. More rigorously, let L_{u,n} = {l ∈ Z : l > n, (l, n) = (l, u) = 1}. Let a(u, n) be the difference between the minimum of L_{u,n} and n. Since u is fixed, we can always find infinitely many primes n so that n + 1 ∈ L_{u,n} which for those n would give a(u, n) = 1. Let r(u, n) be the largest possible difference between consecutive numbers in L_{u,n}. Then for fixed n, the difference between the y-coordinates in B is bounded by z(u, n) = \frac{n}{n+a(u,n)} − \frac{n}{n+a(u,n)+r(u,n)}. As n → ∞, r(u, n) is bounded for fixed u, so z(u, n) → 0. Now, since p ∈ C, the proof of Lemma 2 can be modified by adding the extra condition p ≡ v (mod u). The Chinese remainder theorem and Dirichlet’s theorem can still be applied. □

5. Generalizations to the Unit Hypercube

It would be interesting to try to generalize this in the following way: Let f(x_{1}, x_{2}, …, x_{k}) ∈ Z[x_{1}, x_{2}, …, x_{k}] and consider ⋃_{p}\{(\frac{x_{1}}{p} , …, \frac{x_{k}}{p}) : f(x_{1}, x_{2}, …, x_{k}) ≡ 0 (mod p), x_{1}, x_{2}, …, x_{k} ∈ (Z/pZ)^{∗}}. For what functions f is this dense in the k-dimensional unit hypercube? Here we shall consider f = ∏_{i} x_{i} − 1 and shall not even prove density but shall mimic the case f = xy − 1 to say something about the distribution of points.

Define the following sets:

A_{k} = ⋃_{p}\{(\frac{x_{1}}{p} , \frac{x_{2}}{p} , …, \frac{x_{k}}{p}) : ∏ x_{i} ≡ 1 (mod p), x_{i} ∈ (Z/pZ)^{∗}\};

B_{k} = \{(\frac{a_{0}}{a_{1}} , \frac{a_{1}}{a_{2}} , …, \frac{a_{k−1}}{a_{k}}) : (a_{i}, a_{j}) = 1 for i, j > 0, (a_{0}, a_{1}) = 1, a_{i} < a_{i+1}\}.

Theorem 3 For any point b ∈ B_{k}, there are points in A_{k} that are arbitrarily close to b.

Proof. Let p = −a_{0}^{−1}a_{k} mod a_{1} and p = −1 mod a_{i} for i = 2, …, k. This is possible by the Chinese Remainder Theorem. Let x_{1} = \frac{a_{0}p+a_{k}}{a_{1}} , x_{i} = \frac{a_{i−1}(p+1)}{a_{i}} for i = 2, …, k. Then for all i, x_{i} ∈ Z and ∏ x_{i} = 1 (mod p). Then apply Dirichlet’s Theorem and let p → ∞. Then \frac{x_{1}}{p} → \frac{a_{0}}{a_{1}} and \frac{x_{i}}{p} → \frac{a_{i−1}}{a_{i}} for i = 2, …, k. □

Acknowledgements I thank Professors Robert Sczech, Jacob Sturm and Zhengyu Mao for very helpful advice. Thanks also to the referee for helpful suggestions and the correction of a typo.

References

[1] M.R. Khan, I.E. Shparlinski, On the maximal difference between an element and its inverse modulo n, Period. Math. Hungar. 47 (2003), no. 1-2, 111–117.

[2] A. Granville, I.E. Shparlinski, A. Zaharescu, On the distribution of rational functions along a curve over F_{p} and residue races, J. Number Theory 112 (2005), no. 2, 216–237.

[3] K. Ford, M.R. Khan, I.E. Shparlinski, C.L. Yankov, On the maximal difference between an element and its inverse in residue rings, Proc. Amer. Math. Soc. 133 (2005), no. 12, 3463 – 3468.

[4] E. Alkan, F. Stan, A. Zaharescu, Lehmer k−tuples, Proc. Amer. Math. Soc. 134 (2006), no. 10, 2807 –