24
$\begingroup$

So I was messing around with the famous prime race that comes down to this:


We make a list of primes. The list has two rows; the top row is for primes $1\mod 4$ and the bottom row for primes $3\mod 4$. Our list, up to the 10th prime:

5  13  17  29
3   7  11  19  23  31

The idea is that the two rows are "racing" to be longest, and the bottom row always seems to be winning.


An intuitive visual representation of this would be, we start at $0$ on the number line, and start going through the primes. Whenever we encounter a prime $1\mod 4$ we do a step right, and whenever the prime is $3\mod 4$, we do a step left. This is not quite such an interesting visualization however; it's just a line. However, this becomes more interesting when we generalize it.

The generalization.

We generalize this by picking a number, and do the prime race $\mod n$. Apart from a couple (certainly finite number of) exceptions, all primes fit in one of the $\varphi(n)$ categories. With this, I mean, let $U(n)=\{u_1,u_2,\cdots,u_{\varphi(n)}\}$ with $0\leq u_i<n$, and $i<j\iff u_i<u_j$, and $\gcd(u_i,n)=1$, then each $u_i$ represents a category; all primes $p$ (except for the ones that are divisors of $n$) must have $p\equiv u_i\mod n$ for exactly one $u_i$. Now we start going through the primes, and whenever we encounter a prime $p\equiv u_i\mod n$, we take a step length $1$ in the direction $\tfrac{2i\pi}{\varphi(n)}$.

An example, $n=8$. This is a relatively easy example to try on grid paper, since $\phi(8)=4$, so we have $4$ directions to go in. For the first $10^3$, $10^4$ and $10^5$ primes, this looks like this (the red dot is the starting point, the blue dot is the end. Open the image in a new tab to see it at full resolution)

racing-mod-eight

Interestingly enough, the red dot, the start, is in all images the right-most point in the entire thing, even though it is seemingly random. So this is the case for $n=4$, and for $n=8$. Maybe it's the powers of $2$, let's try $n=10$ (which happens to have $\phi(10)=4$ as well). We get (again, for the first $10^3$, $10^4$ and $10^5$ primes):

racing-mod-ten

We see this time it's tending more to the bottom-left rather than just the left; but again, one side (the top-right) remains untouched. Let's try this again, but this time with an $n$ without $\phi(n)=4$. We try $n=11$ through $n=15$:

$n=11$ racing-mod-eleven $n=12$ racing-mod-twelve $n=13$ racing-mod-thirteen $n=14$ racing-mod-fourteen and $n=15$ racing-mod-fifteen

We see $n=12$ is very convincingly going to the left and not touching the right, and $n=15$ is leaning towards the top-left, and leaves the bottom-left almost untouched. $n=11$, $n=13$ and $n=14$ however there's no specific way the blob seems to lean.


Question.

Why do the blobs with $\varphi(n)=4$ lean so convincingly to one side, while not even touching the other? Do there exist similar patterns for other $n$ with different $\varphi$? Are they related to the fact that the $\varphi$ is a power of $2$ (since $n=15$ has similar behaviour)?

I expected them to stay around the middle a lot more since the density of the primes $\mod n$ is evenly spaced, that is, picking any prime, it has chance $\frac{1}{\varphi(n)}$ to be $i\mod n$ (where $\gcd(i,n)=1$).

$\endgroup$
3
  • 3
    $\begingroup$ Despite primes distribute uniformly over the possible residues in the long term, usually primes with quadratic non-residues are preferred (see chebychev-bias) $\endgroup$
    – Peter
    Mar 20, 2017 at 21:49
  • $\begingroup$ "The idea is that the two rows are "racing" to be longest, and the bottom row always seems to be winning." is not true. In 1957, Leech showed that there are more primes $1$ mod $4$ than the primes $3$ mod $4$, if we count the number of primes upto $26861$. Refer chapter $26$ of the book 'A Friendly Introduction to Number Theory by Joseph H Silvermann.' $\endgroup$ Feb 25, 2020 at 15:42
  • $\begingroup$ The following question has a collection of prime path visualisations: math.stackexchange.com/q/2072308/207316 It's not about prime races, but I figure it makes sense to link together prime visualisation questions. $\endgroup$
    – PM 2Ring
    Dec 10, 2020 at 15:41

1 Answer 1

4
$\begingroup$

The phenomenon that most of the time, there are more primes $p=3\pmod 4$ than $1\pmod 4$ is known as Chebyshev's Bias. Let $P_{a,b}(N)$ denote the number of primes congruent to $a \pmod b$ $ ≤ N$. Hardy and Littlewood showed that $P_{1,4}(N) - P_{3,4}(N) = 0$ for infinitely many $N$. In other words, $P_{1,4}(N)$ and $P_{3,4}(N)$ switch leads in the prime race infinitely often. However, one residue does not have any siginifant lead over another residue, and as $N → ∞$, $P_{3,4}(N) - P_{1,4}(N) = 0$. This also holds for any integers $a$ and $c$ relatively prime to $b$: $P_{a,b}(N) - P_{c,b}(N) = 0$ as $N → ∞$.

A generalization of Chebyshev's Bias states that most of the time, $P_{a,b}(N) > P_{c,b}(N)$ if $a$ is a quadratic non-residue $\pmod b$ and $c$ is a quadratic residue $\pmod b$. This usually works best if $b$ is prime, but if $b$ is composite, there is more than one way to group the elements $\pmod b$ into quadratic residue and non-residue groups.

For example, let $b=8$.

The elements $1,3,5,7$ are all coprime to $8$, and each odd prime will fall into one of these $4$ categories. Following from a generalization of Chebyshev's Bias, we can assume either of $3$ scenarios:

$P_{1,8}+P_{5,8} < P_{3,8}+P_{7,8}$ (this is the same as the original Chebyshev's Bias, categorized by $-1$ being a quadratic residue $\pmod p$)

$P_{1,8}+P_{3,8} < P_{5,8}+P_{7,8}$ (categorized by $-2$ being a quadratic residue $\pmod p$)

$P_{1,8}+P_{7,8} < P_{3,8}+P_{5,8}$ (categorized by $2$ being a quadratic residue $\pmod p$)

In either case, $1\pmod 8$ appears on the left hand side $3$ of $3$ times, so it would make sense that it might be behind in the race when individually compared to the rest of the residues. As for comparing $3,5,7 \pmod 8$, all of them fall into exactly one residue class, having $-2,-1,2$ as quadratic residues, respectively. Therefore, there appears to be no bias for these three residues and can evidently be seen here.

This phenomenon can be observed $\pmod {12}$ and $\pmod {24}$: $1$ trails far behind the rest of the residues. The more highly composite the modulus $b$ is, the more bias there will be.

This also appears to be the case when comparing primes solely congruent to $3\pmod 4$ with other primes congruent to $3\pmod 4$, with a different modulus $b$. For example, there should be no bias between $P_{7,12}$ and $P_{11,12}$. The argument is simple.

If we look at $-3$ being a quadratic non-residue $\pmod p$, then we can assume that most of the time, $P_{7,12} > P_{11,12}$. However, if we look at $3$ being a quadratic non-residue $\pmod p$, then most of the time, $P_{7,12} > P_{11,12}$, a contradiction. Therefore, there should be no bias between $P_{7,12}$ and $P_{11,12}$.

For general $b$, if $p=3\pmod 4$, then either $b$ is a quadratic residue, or $-b$ is a quadratic residue $\pmod p$, so no residue (already assuming all primes in the race are $3 \pmod 4$) should have any lead over the other.


Edit: I have investigated the prime race $\mod 8$ more extensively. It appears that up to a bound $10^{10}$, there is no integer $1 < N < 10^{10}$ such that .$P_{1,8} > [P_{3,8}$ and $P_{5,8}$ and $P_{7,8}]$ (In other words, $1 \pmod 8$ does not lead the prime race below $10^{11}$). I did compare $P_{1,8}$ with $P_{[[{3,5,7}]],8}$ individually up to $10^{11}$. The only time(s) when $P_{1,8}$ has a lead over any of the other residues is at $N=588067889$, when $P_{1,8} > P_{5,8}$.

I have also attempted to study more generalizations. From numeric evidence, it appears that the more residues $\pmod b$ there are, the less likely that $P_{1,b}$ will be the most behind in the race, but it will still have a tendency to fall behind in the race when compared to the rest of the residues:

For example, $\mod 120$, the only $a$ with no integer $N < 10^{10}$ such that $P_{1,120} > P_{a,120}$ is $a=59$. It is also observed that most of the time, $P_{1,120}$ is not the least behind in the race, it is more likely that it is $2$nd, $3$rd, $4$th least.

List the coprime elements $\pmod b$ from left to right based on the value of $P_{a,b}$ from least to greatest, notice that $1$ will have a tendency to gradually shift toward the right as the modulus $b$ increases, explaining the more darker grids for $n=11,12,13,14,15$ as for your original question.

$\endgroup$
0

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.