MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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