PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY S 0002-9939(02)06395-5 Article electronically published on January 23, 2002

THE DISTRIBUTION OF SEQUENCES IN RESIDUE CLASSES

CHRISTIAN ELSHOLTZ

(Communicated by David E. Rohrlich)

Abstract. We prove that any set of integers A ⊂ [1, x] with |A| ≫ (log x)^{r} lies in at least ν_{A}(p) ≫ p^{\frac{r}{r+1}} many residue classes modulo most primes p ≪ (log x)^{r+1}. (Here r is a positive constant.) This generalizes a result of Erdős and Ram Murty, who proved in connection with Artin’s conjecture on primitive roots that the integers below x which are multiplicatively generated by the coprime integers a_{1}, …, a_{r} (i.e. whose counting function is also c(log x)^{r}) lie in at least p^{\frac{r}{r+1} +ε(p)} residue classes, modulo most small primes p, where ε(p) → 0, as p → ∞.

Let ord_{p}(a) denote the order of a modulo p, where (a, p) = 1. A quantitative version of Artin’s conjecture on primitive roots states that for a fixed integer a, not a square, and not −1, there is a positive proportion of primes such that ord_{p}(a) = p − 1. (See [7] for a survey.) In favour of this conjecture, Erdős proved in [2] that for all but o(\frac{y}{log y}) of the primes p ≤ y one has

ord_{p}(2) > p^{\frac{1}{2}} .

This improved upon the lower bound of ord_{p}(2) > p^{δ} for all δ < \frac{1}{2}, proved by Bundschuh; see [1]. It is also implicit in section 3 of Hooley’s work on Artin’s conjecture (see [5]) that for all but O(\frac{y}{(log y)^{3}} ) primes p ≤ y one has ord_{p}(a) ≫ \frac{\sqrt{p}}{log p}. Erdős announced at the end of his paper that the lower bound can be slightly sharpened to

ord_{p}(2) ≥ p^{\frac{1}{2} +ε(p)},

where ε is any real function with lim_{p→∞} ε(p) = 0. The details of this were provided by Erdős and Ram Murty in [3]. For related results see also Pappalardi [8].

For a more general situation, they implicitly consider the following. Let a_{1}, …, a_{r} be mutually coprime positive integers and let p be a prime with (p, a_{1}a_{2} ⋯ a_{r}) = 1. Let A_{1} be the semigroup of positive integers multiplicatively generated by the a_{i} and let A = A_{1} ∩ [1, x]. Then the elements in A have the form a_{1}^{β_{1}}a_{2}^{β_{2}} ⋯ a_{r}^{β_{r}} ≤ x, where the β_{i} are nonnegative integers. Let f(p, a_{1}, …, a_{r}) denote the number of distinct residue classes modulo p which are needed to cover all elements of a ∈ A.

Note that the number of powers of a below x is asymptotically c_{a} log x, and that there are about c_{a_{1},... ,a_{r}}(log x)^{r} many integers below x which are generated

\begin{matrix}c \\ ◯ \end{matrix}2002 American Mathematical Society

Received by the editors March 9, 2001.

1991 Mathematics Subject Classification. Primary 11N69, 11N36; Secondary 11B50, 11A07.

Key words and phrases. Distribution of sequences in residue classes, Gallagher’s larger sieve, primitive roots, Artin’s conjecture.

multiplicatively by the a_{i}. Here and in the following, the c with various indices stand for positive constants.

In this situation,^{1} Erdős and Ram Murty prove that, for all but o(\frac{y}{log y}) many primes p ≤ y with (p, a_{1} ⋯ a_{r}) = 1 one has

f(p, a_{1}, …, a_{r}) ≥ p^{\frac{r}{r+1} +ε(p)},

where ε is an arbitrary real function with lim_{p→∞} ε(p) = 0.

Giving a more quantitative version of this statement one might consider the sequence up to x. It is then implicitly understood that y ≪ (log x)^{r+1}, since otherwise the sequence A does not have ≫ y^{\frac{r}{r+1}} elements below x.

In this note we generalize these results to arbitrary integer sequences. Therefore, the fact that the powers of some element a lie in many residue classes modulo many primes is not necessarily an argument in favour of Artin’s conjecture. However, for special sequences like the powers of a the result by Erdős and Ram Murty is stronger by the ε(p) refinement. We prove the following theorem:

Theorem. Let x > x_{0} and let A ⊆ [1, x] be a set of positive integers with |A| ≥ c_{1}(log x)^{r}. Let ν_{A}(p) denote the number of distinct residue classes modulo p which are necessary to cover A. Let y = c_{4}(log x)^{r+1}. Let

S = \{p ∈ P ∩ [1, y] : ν_{A}(p) ≤ c_{2}p^{\frac{r}{r+1}} \}

and c_{3} = \frac{|S|}{π(y)}. Let β = \frac{1}{r+1} and C = \frac{1}{β} (1 − (1 − c_{3})^{β})c_{4}^{β}. If C > c_{2}, then

\frac{c_{2}c_{3}c_{4}}{C − c_{2}} ≥ c_{1}.

In typical applications, the counting function A(x), i.e. c_{1} and r, might be known. Suppose one wants to make the proportion c_{3} of ‘bad primes’ very small so that one knows for essentially all primes p ≤ y, that ν_{A}(p) is large. Then one can make an admissible choice of c_{2} and c_{4} as follows: Choose a small c_{3}, choose c_{4} ≥ \frac{c_{1}}{c_{3}} ,

and put c_{2} = \frac{C}{2} . Then trivially C > c_{2} and

\frac{c_{2}c_{3}c_{4}}{C − c_{2}} = \frac{c_{2}c_{3}c_{4}}{c_{2}} = c_{3}c_{4} ≥ c_{1}.

This implies the following corollary.

Corollary. Let A be an infinite set of positive integers with counting function A(x) ≫ (log x)^{r}. Let ν_{A}(p) denote the number of distinct residue classes modulo p which are necessary to cover A ∩ [1, x]. Then for all c_{3} > 0 one can find positive c_{2} and c_{4} such that for all but at most \frac{c_{3}y}{log y} primes p ≤ y, where y = c_{4}(log x)^{r+1}, one has ν_{A}(p) ≥ c_{2}p^{\frac{r}{r+1}} .

Unfortunately, it appears, if one allows at most o(\frac{y}{log y}) exceptional primes, that is if one requires that c_{3} → 0 as x → ∞, then one has to allow that c_{2} and c_{4} vary accordingly.

1Strictly speaking, their theorem is stated in a more general form for rational numbers. Let us take the opportunity to mention that there is a slight inaccuracy in the description of the ε in Theorem 4 and part 3 of Theorem 5 of their results (and also in the abstracts in the Math.

Reviews and the Zentralblatt): Obviously, one should either replace p/ε(p) by pε(p) or one should take p/ε(p) with lim_{p→∞} ε(p) = ∞.

Our main tool is Gallagher’s larger sieve, which we state for completeness.

Lemma (Gallagher’s larger sieve; see [4]). Let A ⊆ [1, x] be a set that lies in at most ν_{A}(p) residue classes modulo p, for p ∈ S. Then

|A| ≤ \frac{− log x + ∑_{p∈S} log p}{− log x + ∑_{p∈S} \frac{log p}{ν_{A}(p)}} ,

provided the denominator is positive.

Proof of the Theorem. Since we deal with upper bounds and since log p and \frac{log p}{p^{\frac{r}{r+1}}}

are monotonic functions for p > p_{0}, the worst case distribution of the primes in S is that these primes are as large as possible. If x tends to infinity, then the intervals [0, c y] and [(1 − c)y, y] contain asymptotically the same number of primes, \frac{cy}{log y}. The worst case distribution is determined by the primes in [(1 − c_{3} + o(1))y, y]. For simplicity, we omit o(1) expressions and write ≲ instead of ≤. Moreover, recall that it follows from ∑_{p≤z} log p ∼ z by partial summation that for 0 < α < 1 one has

∑_{p≤z} \frac{log p}{p^{α}} ∼ \frac{z^{1−α}}{1 − α}.

With α = \frac{r}{r+1}, so that 1 − α = \frac{1}{r+1} = β, we find that

|A| ≲ \frac{− log x + ∑_{(1−c_{3})y≤p≤y} log p}{− log x + ∑_{(1−c_{3})y≤p≤y} \frac{log p}{c_{2}p^{\frac{r}{r+1}}}} ≲ \frac{c_{3}y}{− log x + \frac{1}{c_{2}β} (y^{β} − (1 − c_{3})^{β}y^{β})}

= \frac{c_{3}c_{4}(log x)^{r+1}}{− log x + \frac{C}{c_{2}} log x} = \frac{c_{2}c_{3}c_{4}}{C − c_{2}} (log x)^{r}.

Suppose that we have C > c_{2} but \frac{c_{2}c_{3}c_{4}}{C−c_{2}} < c_{1}. This is, for sufficiently large x, a contradiction to our assumption |A| ≥ c_{1}(log x)^{r}.

Remark. Matthews (see [6]) considered questions related to that of Erdős and Ram Murty in a more general context of algebraic groups and abelian varieties. For the classical case of Artin’s conjecture he proved that for almost all primes and for all positive ε one has ν(p) > p^{\frac{1}{2} −ε}. (Apparently he was unaware of [1] and [2].) He mentions further applications to nilpotent groups and to manifolds due to Milnor, Tits, and Wolf.

References

[1] Bundschuh, P., Solution of problem 618. Elemente der Mathematik 26 (1971), 43–44.

[2] Erdős, P., Bemerkungen zu einer Aufgabe in den Elementen. Arch. Math. 27 (1976), 159-163. MR 53:7969

[3] Erdős, P.; Murty, M. Ram, On the order of a (mod p). Number theory (Ottawa, 1996), 87–97, CRM Proc. Lecture Notes, 19. MR 2000c:11152

[4] Gallagher, P.X., A larger sieve. Acta Arith. 18 (1971), 77–81. MR 45:214

[5] Hooley, C., On Artin’s conjecture. J. Reine Angew. Math. 225 (1967), 209–220. MR 34:7445 [6] Matthews, C.R., Counting points modulo p for some finitely generated subgroups of algebraic

groups. Bull. London Math. Soc. 14 (1982), 149–154. MR 83c:10067 [7] Murty, M. Ram, Artin’s conjecture for primitive roots. Math. Intelligencer 10 (1988), 59–67.

MR 89k:11085

[8] Pappalardi, F., On the order of finitely generated subgroups of Q^{∗}(mod p) and divisors of p − 1. J. Number Theory 57 (1996), 207–222. MR 97d:11141

Institut für Mathematik, Technische Universität Clausthal, Erzstrasse 1, D-38678 Clausthal-Zellerfeld, Germany

  E-mail address: elsholtz@math.tu-clausthal.de