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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica Mar 21 '12 at 19:48
  • 1
    $\begingroup$ No, sorry, this bound was for quadratic nonresidues. For generators, it is $O((\log p)^6)$, according to Wikipedia. $\endgroup$ – Emil Jeřábek supports Monica Mar 21 '12 at 19:51
  • 1
    $\begingroup$ It is standard for $\mathbb{Z}_p$ to refer to $p$ adic number. You want the quotient by the prime ideal. $\endgroup$ – Marc Palm Mar 21 '12 at 21:04
  • 4
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Mar 21 '12 at 21:52
  • 4
    $\begingroup$ 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. $\endgroup$ – Seva Mar 22 '12 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.