This is a sequel to this MO question:

The multiplicative order of 2 modulo primes

As shown in Charles Matthews' paper linked to there, it is not hard to show that for each $\delta > 0$ there is a $c = c(\delta) > 0$ such that the set of primes $p$ for which the multiplicative order $n_p := \mathrm{ord}_p(2)$ of $2$ modulo $p$ satisfies $n_p < c\sqrt{p}$, has density $< \delta$. In particular, the set of primes with $n_p < p^{\frac{1}{2} - \epsilon}$ have zero density.

My question is, is $1/2$ really the critical exponent? For $\epsilon > 0$, is there a positive density of primes $p$ with $n_p < p^{\frac{1}{2} + \epsilon}$. Moreover, is there a $C < \infty$ for which the set of $p$ with $n_p < C\sqrt{p}$ has positive density?

I would also like to ask about the analogous question for elliptic curves: is $1/3$ really the critical exponent there? Given a point $P$ of infinite order, is there a $C < \infty$ for which the set of $p$ such that the order of $P \mod{p}$ is $< C \sqrt[3]{p}$ has positive density?


The Generalized Riemann Hypothesis (for Dedekind zeta functions of certain Kummerian fields) would show that the "critical exponent" for the multiplicative order problem is $1$. In fact, GRH implies that if $g$ is any function tending to infinity, then (asymptotically) 100% of primes $p$ satisfy $n_p > p/g(p)$. This follows from the methods of Hooley in his conditional solution of Artin's conjecture; an explicit reference is Theorem 23 in this paper of Kurlberg and Pomerance:


I suspect something similar can be said about your 2nd problem assuming GRH for Dedekind zeta functions associated to division fields. There's lots of relevant work in this area by Cojocaru, David, and others. But I'm not so knowledgeable about this, so I'll bow out now.

  • $\begingroup$ Thank you very much for this reference, that was very helpful! That is exactly what I wanted to know. By the way, the reference also indicates that $1/2$ is the critical exponent for which one can prove zero density unconditionally, i.e. without assuming GRH. (They refer to the paper by Pappalardi, where this was shown.) $\endgroup$ – Vesselin Dimitrov Mar 2 '13 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.