9
$\begingroup$

Is there a known elementary function bound in terms of $a,b,n$ for the $n$-th prime equal to $b$ modulo $a$ (coprime to $b$)?

Bounds on Linnik's constant answer this for the first prime in each progression. Is there a known analogue for an $n$-th prime in a progression? And I found some references on an error term for the prime number theorem for arithmetic progressions. But I don't see how to turn these into a construction for arbitrary $a,b,n$.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ One "construction" is simply to check all the numbers to see if they're prime. Is there even a better way to find the $n$th prime among all the primes? $\endgroup$
    – Will Sawin
    Commented Jul 29, 2013 at 3:34
  • 1
    $\begingroup$ The error term should give an explicit $x_0$ and an explicit positive constant $C \lt 1/\varphi(a)$ such that $|\{p \leq x : p \equiv b \pmod{a}\}| \geq Cx/\log x$ for all $x \geq x_0$. Then the first $x \geq x_0$ such that $Cx/\log x \geq n$ gives an upper bound on the $n$-th prime $b \pmod{a}$. $\endgroup$
    – François G. Dorais
    Commented Jul 29, 2013 at 6:33
  • 1
    $\begingroup$ Actually Will Sawin's comment is incorrect, though it led to improving the question. Brute force will find the $n$-th prime only if there is one! In other words, it is not a constructive technique unless you can bound how long the search needs to be. It seems you can bound it. $\endgroup$
    – Colin McLarty
    Commented Jul 29, 2013 at 9:05
  • 1
    $\begingroup$ @François G. Dorais: The versions of Dirichlet's theorem before Linnik's theorem did not give an explicit $C$, because the $C$ furnished by the proof depended on a possible Siegel zero for the modulus $a$. See also my response below. $\endgroup$
    – GH from MO
    Commented Jul 29, 2013 at 9:19
  • $\begingroup$ The case of primes $1 \pmod{n}$ is provable (with a much worse bound) in PA using the argument from mathoverflow.net/a/15221/2000 $\endgroup$
    – François G. Dorais
    Commented Jul 29, 2013 at 13:23

1 Answer 1

Reset to default
5
$\begingroup$

Corollary 18.8 in Iwaniec-Kowalski's Analytic number theory shows the existence of an explicitly computable $L>3/2$ such that for $x>a^L$ and $(a,b)=1$, the number of primes less than $x$ and congruent to $b$ modulo $a$ is at least a constant times $\frac{x}{\varphi(a)\sqrt{a}\log x}$. So the $n$-th prime congruent to $b$ modulo $a$ is less than a constant times $a^L n\log (2n)$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I doubt you can find a constant multiple of $x$; surely it's $x/\log(x)$? $\endgroup$
    – user25199
    Commented Jul 29, 2013 at 8:16
  • $\begingroup$ @Carl: You are right, I had the Chebyshev function $\psi(x,a,b)$ in mind rather than the prime counting function $\pi(x,a,b)$. I updated my response accordingly. $\endgroup$
    – GH from MO
    Commented Jul 29, 2013 at 9:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .