Given positive integers $m$, $r$ and $n$, let $\pi(m,r,n)$ denote the number of prime numbers $p \leq n$ in the residue class $r$ (mod $m$). Further let $1 = r_1 < r_2 < \dots < r_{\varphi(m)} = m-1$ be the prime residues (mod $m$), and let $\sigma \in {\rm Sym}(\{r_1, \dots, r_{\varphi(m)}\})$ be a permutation of them. Are there always infinitely many $n \in \mathbb{N}$ such that $\pi(m,\sigma(r_1),n) < \pi(m,\sigma(r_2),n) < \dots < \pi(m,\sigma(r_{\varphi(m)}),n)$?

If the answer is yes, are explicit bounds $B(m)$ known such that for every permutation $\sigma$ of the prime residues (mod $m$) there is at least one such $n$ less than $B(m)$?

If the answer is no, for which permutations $\sigma$ are there infinitely many such $n$, and for which are not?

  • 4
    $\begingroup$ There is a nice survey paper related to your question here by Granville and Martin: arxiv.org/pdf/math.NT/0408319.pdf See especially the discussion of work by Rubinstein and Sarnak (1994) beginning on p. 24 and, if I am understanding your question correctly, the remarks (under suitable assumptions) at the top of p. 26, as well as the discussion thereafter. $\endgroup$ – Benjamin Dickman May 25 '14 at 13:03

The answer is conjectured to be "yes." Further, assuming GRH and GSH Rubinstein and Sarnak, Chebyshev's Bias, Exp. Math 1994 even could show results on the logarithmic densities of the resepactive sets (which in particular is non-zero). I do not know about general explicit upper bounds.

Without GRH a lot less is known. The problem you mention sometimes goes by Shanks--Rényi race problem. A very good exposition of this circle of ideas is Prime Number Races by Granville and Martin; see page 22 and subsequent ones for the discussion of Rubinstein and Sarnak's results. (Added note: this is in fact the same paper Benjamin Dickman mentions in a comment I had not seen before.)

| cite | improve this answer | |
  • 1
    $\begingroup$ Thank you very much for your answer! -- So the question is open, with a conjectured answer "yes". A guess on what might be explicit upper bounds in case the conjecture holds would be nice anyway. $\endgroup$ – Stefan Kohl May 25 '14 at 16:50

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.