Timeline for Generator density in $\mathbb{Z}^*_p$
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2012 at 7:43 | comment | added | Seva | 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. | |
| Mar 22, 2012 at 1:35 | comment | added | user22202 | More rigorously, suppose that $x$ is of size about $(\log p)^c$. If the radical of $p-1$ is the product of all primes up to $z$ (it is definitely an unsolved problem whether there are infinitely many such primes $p$), and if $p-1$ is equal to its radical (then $p$ is a primorial prime and this is even harder), then $p$ is of size about $e^{z/\log z}$ and $x$ is about $(z/\log z)^c$. Using inclusion-exclusion one gets an error of $2^{x^{1/c}}$. | |
| Mar 22, 2012 at 1:35 | comment | added | user22202 | Suppose $x$ is some parameter and $p$ is a large prime much larger than $x$. (It might be better if $p-1$ is squarefree to minimize the ratio between $p-1$ and its radical.) If one would actually know the density of numbers relatively prime to $p-1$ in a short range, say of size $x$, then one can estimate the set of numbers less than $x$ relatively prime to all primes dividing $p-1$ without using inclusion-exclusion. With inclusion-exclusion, one would get a $O(2^{\omega(p-1)})$ term, so it seems this would allow one to circumvent that. | |
| Mar 21, 2012 at 22:08 | comment | added | ogn | I have just relaxed the length of $[a,b]$, the length can be lower-bounded by $(\log p)^c$ for some small constant $c$. Is there any nontrivial answer? | |
| Mar 21, 2012 at 22:00 | history | edited | ogn | CC BY-SA 3.0 |
added 40 characters in body
|
| Mar 21, 2012 at 21:52 | comment | added | Gerry Myerson | 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. | |
| Mar 21, 2012 at 21:04 | comment | added | Marc Palm | It is standard for $\mathbb{Z}_p$ to refer to $p$ adic number. You want the quotient by the prime ideal. | |
| Mar 21, 2012 at 21:04 | history | edited | Marc Palm | CC BY-SA 3.0 |
added 2 characters in body
|
| Mar 21, 2012 at 21:02 | comment | added | Anthony Quas | just added the number theory tag | |
| Mar 21, 2012 at 21:02 | history | edited | Anthony Quas |
changed tags
|
|
| Mar 21, 2012 at 19:51 | comment | added | Emil Jeřábek | No, sorry, this bound was for quadratic nonresidues. For generators, it is $O((\log p)^6)$, according to Wikipedia. | |
| Mar 21, 2012 at 19:48 | comment | added | Emil Jeřábek | 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. | |
| Mar 21, 2012 at 19:26 | history | asked | ogn | CC BY-SA 3.0 |