# The critical exponent in the multiplicative order of 2 modulo primes

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{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:
• 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.) – Vesselin Dimitrov Mar 2 '13 at 16:23