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$.

  • 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 Jul 29 '13 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 Jul 29 '13 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 Jul 29 '13 at 9:05
  • $\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 Jul 29 '13 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 Jul 29 '13 at 13:23

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)$.

  • 1
    $\begingroup$ I doubt you can find a constant multiple of $x$; surely it's $x/\log(x)$? $\endgroup$ – user25199 Jul 29 '13 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 Jul 29 '13 at 9:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.