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

Hello,

Consider the multiplicative group $(\mathbb{Z}/p)^*$ for a given prime $p$. We know that the number of generators in this group is $\phi(p-1)$ --- the Euleur totient function. The question is, for $0 \leq a < a + \log^{c} p < b \leq p-1$ where $c$ is a constant (say $c=10$), how many generators of the group belongs to $[a,b]$? In other words, what is the density of generators in a given interval $[a,b]$ (compared to the density $\phi(p-1)/p-1$)? Is it easier if $b=p-1$?

For a given prime $p$, what is the densest interval in term of generators?

share|improve this question
1  
As far as I am aware, the shortest intervals known to include at least one generator have length $O((\log p)^2)$, assuming the Generalized Riemann Hypothesis. Unconditionally, you can’t even get anywhere near that. Thus, I doubt you can get any nontrivial answer. –  Emil Jeřábek Mar 21 '12 at 19:48
1  
No, sorry, this bound was for quadratic nonresidues. For generators, it is $O((\log p)^6)$, according to Wikipedia. –  Emil Jeřábek Mar 21 '12 at 19:51
1  
It is standard for $\mathbb{Z}_p$ to refer to $p$ adic number. You want the quotient by the prime ideal. –  plusepsilon.de Mar 21 '12 at 21:04
4  
It is standard for ${\bf Z}_p$ to refer to whatever the person using it says it refers to. The usage in this question was perfectly clear and not in any need of editing. –  Gerry Myerson Mar 21 '12 at 21:52
4  
A fairly standard character sum technique leads to the conclusion that the number of primitive roots mod $p$ in an interval of length $Q$ is $$ \frac{\phi(p-1)}{p-1)}\,\big(Q+2^{k+1}\theta\sqrt p\log p\big), $$ where $k$ is the number of distinct prime divisors of $p-1$ and $|\theta|<1$ (see Vinogradov's "Elements of Number Theory", Chapter VI, Problem 14-b-$\beta$). I hardly believe there are any substantial improvements known. –  Seva Mar 22 '12 at 7:43
show 4 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.