16
$\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
    $\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 '17 at 21:49

Your Answer

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

Browse other questions tagged or ask your own question.