Lower bounding the multiplicative order of 2 modulo p

Question

For $p$ prime denote by $\mathsf{ord}_p(2)$ the multiplicative order of $2$ modulo $p$.

Does there exist $N > 0$ such that, for ALL primes $p$, $\mathsf{ord}_p(2)$ is at least $\frac{(p-1)}{N}$?

If there are infinitely many Mersenne primes then the answer is "no". Since the order of $2$ modulo a Mersenne prime $p=2^k-1$ is only $k$, which is not greater than $\frac pN$ for sufficiently large $p$.

Is there a proof that the answer is "no"?

It is possible that the following question answers this, but it wasn't clear to me: The critical exponent in the multiplicative order of 2 modulo primes

Thanks Steven Galbraith

Answer 1

Fix a prime $q>N$ and find a prime $p$ that splits completely in the splitting field of $x^q-2$. Then $p \equiv 1 \pmod q$ and $2$ is a $q$-th power modulo $p$, so the order of $2$ is at most $(p-1)/q$. Using effective Chebotarev, you can even give an upper bound for the smallest $p$.

Welcome to MO!

Answer 2

$\def\ord{\operatorname{ord}}$On the other hand, there are results which say that $\ord_p(2)$ is generally fairly large. For example, an old result of Erdos and Turan says that for any $a\ge2$ and any $\epsilon>0$, the following sum converges: $$ \sum_{m=1}^\infty \frac{1}{m\cdot \ord_m(a)^\epsilon}. $$ If you're just interested in primes, there's the following more precise result (Murty, Rosen, me) $$ \sum_{p~\text{prime}} \frac{\log p}{p\cdot\ord_p(a)^\epsilon} \le \log\log a + \frac2\epsilon + C $$ for an absolute constant $C$. One can use this to show that the (upper) density of the set $\{p : \ord_p(a)\le p^\theta\}$ is at most $2\theta$. Pomerance has stronger estimates for this density using deeper methods.

Let me second Felipe's welcome to MathOverflow.

Answer 3

Here are a few aspects that have not yet been mentioned by Felipe, Joe and Vesselin.

a) Assuming GRH, 2 is a primitive root mod $p$ for a positive density of primes. (The density is 0.373955, known as Artin's constant). For a great survey on this see Pieter Moree, Integers, Volume 12A (2012), A13: Artin's Primitive Root Conjecture -- A Survey -- http://www.integers-ejcnt.org/vol12a.html

Moreover, on GRH Hooley proved that for fixed $L$ there is a positive density of primes, where the order of 2 mod p, $\text{ord}_p(2)$ is $\frac{p-1}{L}$. ($L$ is also called the index). Murata worked out that this density roughly decreases as $1/L^2$. The sum (over $L$) of these densities converges to 1.

For a convenient statement of this see Pappalardi, On Hooley's Theorem with weights. Rend. Sem. Mat. Polit. Univ. Torino 53 No. 4 (1995) 375-388. http://www.mat.uniroma3.it/users/pappa/papers/Rend_Sem_Torino_53_1995.pdf

For another statement, assuming GRH, that the average value of the order is quite large, see for example Thm. 2 of Kurlberg and Pomerance: ON A PROBLEM OF ARNOLD: THE AVERAGE MULTIPLICATIVE ORDER OF A GIVEN INTEGER

https://math.dartmouth.edu/~carlp/arnoldfinal.pdf

b) Your question whether $\frac{p-1}{\text{ord}_p(2)}$ can actually be bounded has appeared in the Monthly a while ago:

E3216 Jon Froemke, Jerrold W. Grossman, O. P. Lossers The American Mathematical Monthly, Vol. 96, No. 4 (Apr., 1989), p. 361.

http://www.jstor.org/stable/2324098?seq=1#page_scan_tab_contents

In short, the published solution gives a proof that it is not bounded, based on Dirichlet's theorem on primes in progression, and mentions that other proofs exist that are "not completely elementary", (e.g. including Chebotarev).

c) Unconditionally, one can show that $\text{ord}_p(2)\geq p^{1/2 + \varepsilon(p)}$, for most primes, where $\varepsilon(p)$ tends to 0, as $p$ tends to infinity. See Erdos and Ram Murty, On the order of a mod p, CRM Proceedings and Lecture Notes, Volume 19, (1999) pp. 87-97. http://www.mast.queensu.ca/~murty/erdos.dvi

Moreover, one can show that for a positive proportion of primes the order is a bit larger, $> p^{0.677}$, where the exponent comes from a result of Baker and Harman on the largest prime factor of $p-1$. See Lemma 20, Kurlberg and Pomerance, On the period of the linear congruential and power generators, P. Kurlberg and C. Pomerance, Acta Arith. 119 (2005), 149–169. http://www.math.dartmouth.edu/~carlp/PDF/par13.pdf

In other words, what is known unconditionally is much weaker than what is known on GRH.

Answer 4

In the paper

On the Order of Finitely Generated Subgroups of $\mathbb{Q}^{*}$ (mod $p$) and Divisors of $p-1$, Journal of Number Theory 57, pp. 207-222

by F. Pappalardi,

Let $a>1$ non-square. Denote by $l_a(p)$ the multiplicative order of $a$ modulo $p$. Then we have for some positive $\gamma$, $$ \sum_{p<x} \frac{1}{l_a(p)} \ll \frac{\sqrt{x}}{(\log x)^{1+\gamma}}.$$

It seems that breaking $\sqrt x$ on the upper bound is very difficult.

If your assertion is true, then the upper bound would have $N \log\log x$ which is way beyond the upper bound $\sqrt x / (\log x)^{1+\gamma}$.