4
$\begingroup$

We can say that a number $p$ is prime modulo $N$ if for any two numbers $1<a,b<p$, $ab \not\equiv p \pmod N$. We will define $p(n)$ to be the number of primes mod $n$. I'm wondering about the asymptotic value of $p(n)$. If $p \leq \sqrt n$ then $p$ is prime modulo $n$ iff it's prime, so $p(n) = \Omega(\frac {\sqrt n} {\log n})$. Experimentally I get that the ratio $\frac {p(n)}{\sqrt n}$ varies around 0.5. Is $p(n) = \Theta(\sqrt n)$? Does $\frac {p(n)}{\sqrt n}$ converge? To what? What about $\frac 1n \sum_{i=2}^n \frac {p(i)}{\sqrt i}$? For 10000 it's about 0.51, and for 9000 0.515. A possible approach I've thought about is to prove that for every $d, x$, the number of $n \leq x$ modulo which $d$ is prime is $O(\frac{x\sqrt x}d)$, which gives a bound of $O(\sqrt x \log \log x)$ on average. I believe this can be done using sieve methods like here, but it seems like the proof there only gives a bound of $O(\frac{x \root4\of x}{\sqrt d})$ which gives a bound of $O(x^\frac34)$ on average, and I don't know enough about sieve methods to improve on that.

Improve this question
$\endgroup$
7
  • $\begingroup$ Somewhat related: mathoverflow.net/questions/69509/… . I think Kloosterman sum methods may be able to show that such primes modulo $n$ must be of size $O(n^{3/4})$ (at least if $n$ is prime), but this is almost certainly suboptimal. $\endgroup$
    – Terry Tao
    Commented Jul 27, 2023 at 17:24
  • 1
    $\begingroup$ If you type a\equiv b(\mod c) you see $a\equiv b(\mod c),$ and if you type a\equiv b\pmod c you see $a\equiv b\pmod c.$ I edited this question so that that latter form is used. (If more than one object is to be included in the parenthesis, then you need curly braces { }, thus: a\equiv b\pmod{cd} gives you $a\equiv b\pmod{cd}. \qquad$ $\endgroup$
    – Michael Hardy
    Commented Jul 27, 2023 at 17:29
  • 1
    $\begingroup$ I am confused about this last claim. Isn't the number of mod-$n$ primes up to $\sqrt{n\log n}$ at most the number of primes up to $\sqrt{n\log n}$ and therefore at most $\approx \sqrt{n/log n}$ by the prime number theorem? So the claim that these are all but $O(1)$ contradicts the claim that the number of mod-$n$ primes should be comparable to $\sqrt{n}$. $\endgroup$
    – Will Sawin
    Commented Jul 27, 2023 at 17:53
  • $\begingroup$ Suppose $p$ is much smaller than $n$. Then to be a mod-$n$ prime, $p$ must be prime and the numbers $cn+p$ must have no divisors in the range $( \frac{cn+p}{p}, p ) \approx ( \frac{cn}{p} ,p) $ for all $1 \leq c \leq \frac{p(p-1)}{n} $. The average number of divisors in that range is $\log \frac{p^2}{cn}$. The range is symmetric so the number of divisors is even, and if the statistics are otherwise Poissonian then the probability of having no divisors in that range is $e ^{ - \frac{1}{2} \log \frac{p^2}{cn} }= \frac{ \sqrt{cn}}{p}$. $\endgroup$
    – Will Sawin
    Commented Jul 27, 2023 at 18:12
  • $\begingroup$ So we might heuristically estimate that the probability that $p$ is a mod $n$ prime is $\frac{1}{\log p} \prod_{ c \leq \frac{p^2}{n}} \frac{ \sqrt{cn}}{p} $ and note that $\prod_{ c \leq \frac{p^2}{n}} \frac{ \sqrt{cn}}{p} $ is a continuous function of $\frac{p^2}{n}$ which is integrable, which suggests we get a constant times $\frac{ \sqrt{n}}{\log n}$. I guess this is further from your empirical data than the $(1- \frac{1}{n})^{p^2}$ heuristic, even though it's ``more sophisticated" since it keeps track of sizes of potential divisors. Probably the Poissonian assumption is not so good. $\endgroup$
    – Will Sawin
    Commented Jul 27, 2023 at 18:12

0

Reset to default

You must log in to answer this question.