2
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 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
    Commented Mar 21, 2012 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
    Commented Mar 21, 2012 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
    Commented Mar 21, 2012 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
    Commented Mar 21, 2012 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
    Commented Mar 22, 2012 at 7:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .