Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $p$ be prime. Consider $\Bbb Z_{p}$, the cyclic multiplicative group.

Is it possible to choose a generator $c$ as small as $O(\log(p))$? (wiki shows $c$ as small as $O(\log^{6}(p))$ is possible under GRH http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Upper_bounds)

share|improve this question
I don't understand: The wikipedia article you cite seems to give the state of the art on this question (and seems to indicate that there is a good chance that the answer to the question is "no". –  Igor Rivin Jul 13 '13 at 14:04
Hi Igor: It seems there are improvements. ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/… –  Turbo Jul 13 '13 at 15:15
Note that Bach does NOT look at the smallest residue, so this is not an improvement as far as your question is concerned. –  Igor Rivin Jul 13 '13 at 15:25
But he seems to have a conjectureon page 1725 relating to $\exp(\gamma)$? Plus in the last few lines he seems to suggest $O(\log{p}\log\log{p})$ may be possible? Is this unrelated? –  Turbo Jul 13 '13 at 15:30
The results mentioned in the Wikipedia article suggest that the question on $O(\log p)$ bounds has been asked a long time ago, and the negative results are to show that you certainly can't do better (after all, why not $O(\sqrt(\log p))$? A priori, no reason). Notice that the best (conditional) estimates on quadratic non-residues are $O(\log^2 p),$ so this is a lower bound on how well you can do with current technology. –  Igor Rivin Jul 13 '13 at 15:33

Your Answer


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

Browse other questions tagged or ask your own question.