DyingLoveGrape.

(home) (about) (diepedlop)

Primes and the Elliott-Halberstam Conjecture.


Introduction.

Sometimes simple questions have simple answers. Sometimes simple questions have extremely dense and difficult answers. Sometimes simple questions have such difficult answers that even starting to understand the answer requires years of study and expertise in a number of different fields.

Recently, an exciting attack on the Twin Primes Conjecture was detailed. Unfortunately, since I am not a number theorist, it was difficult for me to get through even the introduction to the papers giving the gist of the idea that the attack was using. Most of them require defining a certain error function and showing that a particular bound holds for this function. To motivate this error function, it is necessary to understand Euler's totient function. Therefore, my plan for this post is to detail and give examples for the totient function (for those who have not seen it before) and use it to motivate this error function.

Prereqs: Just general Calculus-level mathematical maturity. Also, some basic understanding of modular arithmetic.

Primes and Euler's Totient Function.

Much has been written about the totient function — I will just briefly touch on it. The idea behind the totient function is easy: $\phi(n)$ is defined to be the number of natural numbers less than $n$ which are relatively prime to $n$ . Hence, for example, \[\phi(8) = 4\] since the only natural numbers less than 8 which are relatively prime to 8 are: 1, 3, 5, 7. There's four of them, so $\phi(8) = 4$. Here's a few more: \[\begin{align*} \phi(1) &=1\\ \phi(2) &=1\\ \phi(3) &=2\\ \phi(4) &=2\\ \phi(5) &=4\\ \phi(6) &=2\\ \phi(7) &=6\\ \phi(8) &=4\\ \phi(9) &=6\\ \phi(10) &= 4\\ \phi(11) &= 10\\ \phi(12) &= 4\\ \phi(13) &= 12\\ \end{align*}\] One's initial reaction is to find a pattern — but there doesn't seem to be much of a pattern here at first glance. We notice that for some numbers $p$ that $\phi(p) = p-1$; indeed, if $p$ is a prime number then every number less than it is relatively prime to it, so we have $\phi(p) = p-1$. Moreover, it's a bit difficult to see from this chart, but if we were to make a chart of these numbers one would be able to see something interesting: \[\phi(p)\phi(q) = \phi(pq)\] for any natural numbers $p,q$ with $p,q$ relatively prime to each other. Plug in a few numbers and see that this works out. What's the reasoning behind this? Let's just think about what happens if $p$ and $q$ happen to be primes. Then what do we have? The right-hand side is all numbers less than and relatively prime to $pq$. Let's think about which numbers are not relatively prime to $pq$. Next, the multiples of $p$ less than $pq$ aren't relatively prime to $pq$: this is \[p, 2p, 3p, \dots, (q-1)p\] which will give us $q-1$ non-relatively prime numbers (make sure you understand why these numbers work!). Next, the multiples of $q$: this is \[q, 2q, \dots, (p-1)q\] which gives us $p-1$ non-relatively prime numbers. This is a total of $p-1 + q-1 = p + q - 2$ numbers which are less than but not relatively prime to $pq$. Since there are $pq-1$ numbers less than $pq$ in general, the number of relatively prime numbers is the ones which are left after we subtract off the non-relatively prime numbers; that is: \[(pq -1) - (p + q - 2) = pq - p - q + 1\] Now let's look back and notice that $\phi(p) = p-1$ and $\phi(q) = q-1$ for primes $p,q$ and that, moreover, \[(p-1)(q-1) = pq - p - q + 1\] which is what we found $\phi(pq)$ to be!

Unfortunately, if $p=q$ is prime, then we must be a bit more clever in thinking about $\phi(p^{2})$. What are the factors of $p^{2}$ less than $p^{2}$? There's a bunch: \[1, p, 2p, 3p, \dots, (p-1)p.\] Hence, we have that there are \[p^{2} - 1 - (p-1) = p^{2} - p\] relatively prime numbers less than $p^{2}$. A similar argument holds when we have higher powers of $p$: for example, the factors of $p^{n}$ are: \[1, p, 2p, 3p, \dots, p^{2}, (p+1)p, \dots, (p^{n-1}-1)p.\] Therefore, since we have $p^{n}-1$ numbers less than $p^{n}$ in general, those which are relatively prime are given by \[p^{n} - 1 - (p^{n-1} -1) = p^{n} - p^{n-1}.\] The general formula for $p$ prime and $n$ a natural number: \[\phi(p^{n}) = p^{n} - p^{n-1}.\]

Using all of the previous things we've learned, if we have some number $x$ which is not necessarily prime, we know that we may prime factorize $x$ and obtain: \[\begin{align*}\phi(x) &= \phi(p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{n}^{a_{n}}) \\ &=(p_{1}^{a_{1}} - p_{1}^{a_{1}-1})(p_{2}^{a_{2}} - p_{2}^{a_{2}-1}) \cdots (p_{n}^{a_{n}} - p_{n}^{a_{n}-1}) \end{align*}\] which is great, since it tells us we know $\phi$ for every number so long as we know $\phi$ for every prime which divides that number. This is a powerful idea! For example, counting the number of numbers less than and relatively prime to $30030$ would be pretty tedious without using what we've just shown: \[\begin{align*}\phi(30030) &= \phi(2\times 3\times 5\times 7\times 11\times 13)\\ &=\phi(2)\phi(3)\phi(5)\phi(7)\phi(11)\phi(13)\\ &=(2-1)(3-1)(5-1)(7-1)(11-1)(13-1)\\ &=(1)(2)(4)(6)(10)(12)\\ &=5760. \end{align*}\] There is a ton we can say about Euler's totient function, but we will restrict ourselves for now; the interested reader can probably figure a few things out at this point about the totient function which we haven't listed.

Approximating Primes.

At this point, we need some big guns.

Dirichlet's Prime Number Theorem says that, given two relatively prime numbers $a,d$ there are infinitely many primes of the form $a + nd$ where $n\geq 0$. This means that in the sequence \[a, a+d, a+2d, a+3d, \dots\] there will be infinitely many prime numbers. Let's test this out with $a = 2$ and $d = 5$ just to see if we get a whole bunch of prime numbers (infinitely many would take too long to check!). We get, \[2, 7, 12, 17, 22, 27, 32, 37, \dots\] and in that part of the sequence we have the primes $2, 7, 17, 37$. If we went onward (you may try this if you have some programming experience or a pencil and paper and some free time) we'd find many more primes in this sequence.

Let's investigate this a bit more. Let's say we fix some number $d$ and look at all the possible $a$'s less than $d$ which would work for Dirichlet's theorem. How many are there? We've seen that there are $\phi(d)$ such numbers

To be a bit concrete, let's work with $d = 7$. Then we may have the following numbers and their corresponding sequences: \[\begin{align*} 1 &: 1, 8, 15, 22, \dots\\ 2 &: 2, 9, 16, 23, \dots\\ 3 &: 3, 10, 17, 24, \dots\\ 4 &: 4, 11, 18, 25, \dots\\ 5 &: 5, 12, 19, 26, \dots\\ 6 &: 6, 13, 20, 27, \dots\\ \end{align*}\] Neat. Notice that besides the numbers in the sequence $7, 14, 21, \dots$ we have every natural number contained in some sequence. Here's something amazing: each of these sequences contains the same proportion of primes and the proportion is (therefore) equal to $\dfrac{1}{d-1}$. Note that this is true even if $d$ is not a prime number. That is, if we were to ask, ``Out of the total number of primes (which is infinite), what proportion does the sequence $1, 8, 15, 22, \dots$ contain?'' we'd recieve the answer that $\frac{1}{6}$th of the primes live in this sequence.

Perhaps a more telling example is if we allow $d = 4$. Then we obtain the sequences: \[\begin{align*} 1 &: 1, 5, 9, 13, \dots\\ 3 &: 3, 7, 11, 15, \dots\\ \end{align*}\] which, according to the claim above, each contain one-half of the primes each! Notice that, because the list of primes is infinite, it is a bit strange to take proportions: in particular, the prime number $2$ is in neither list. What does this claim mean then?

We certainly can't look at all of the primes at once, so let's choose some big number $x$ to fix and just look at all of the numbers which are less than or equal to $x$. Let's define \[\pi(x)\] to be the number of primes less than or equal to $x$. We want to see how many primes are in each of the sequences, so we do something sneaky: in the above example where $d = 4$ all of the primes in the list where $a = 1$ have the property that they are $1\mod 4$; that is, they are $a\mod d$. Similarly, when $a = 3$, all of the primes in that list are of the form $3\mod 4$ which is also $a\mod d$. If we want to count all the primes in a particular sequence, we just need to count the primes $p$ which have the property $p \equiv a\mod d$. To this end, let's define the function \[\pi(x; d,a)\] to be the number of primes less than or equal to $x$ which are equivalent to $a\mod d$.

A Quick Example.

A quick example might help solidify these concepts if you've never seen them before. Let's let $x = 25$ and let's let $d = 4$ again. Then we have the sequences \[\begin{align*} 1 &: 1, 5, 9, 13, 17, 21, 25.\\ 3 &: 3, 7, 11, 15, 19, 23.\\ \end{align*}\] We notice that \[\pi(25; 4,1) = 3\] since only $5, 13, 17$ are primes in that sequence. Similarly, we may count \[\pi(25; 4,3) = 4.\] Notice that these are not exactly equal but they are almost equal to each other at this point. For fun, we also note that \[\pi(25) = 9\] since $2,3,5,7,11,13,17,19,23$ are the only primes less than or equal to 25.

Since there are two sequences (since $\phi(4) = 2$) and each had to divide up $\pi(25) = 9$ primes, we'd expect them to have $\dfrac{\pi(25)}{\phi(4)} = \dfrac{9}{2} = 4.5$ each. That's not exactly what happened, but it's close to what happened; so we'll say that \[\pi(25;4,1) \approx \pi(25;4,3) \approx \dfrac{\pi(25)}{\phi(4)}\] or, because the value of $a$ doesn't really matter (since each sequence ought to have the same proportion of primes, approximately), \[\pi(25; 4,a)\approx \dfrac{\pi(25)}{\phi(4)}.\]

Let's try this again with $x = 500$. I won't write out all the terms, but I'll note \[\begin{align*} \phi(4) &= 2\\ \pi(500;4,1)&=44\\ \pi(500;4,3)&=50\\ \pi(500) &= 95\\ \end{align*}\] This time, we have that \[\dfrac{\pi(500;4,1)}{\pi(500)} \approx 0.463\dots\] \[\dfrac{\pi(500;4,3)}{\pi(500)} \approx 0.526\dots\] These are both relatively close to the value we'd expect, which is $\frac{1}{2}$. As $x$ gets larger, these values will get closer.

Just for kicks, one more time with $x = 1000000$. \[\begin{align*} \phi(4) &= 2\\ \pi(1000000;4,1)&=39175\\ \pi(1000000;4,3)&=39322\\ \pi(1000000) &= 78498\\ \end{align*}\] Then, \[\dfrac{\pi(1000000;4,1)}{\pi(1000000)} \approx 0.4990573\dots\] \[\dfrac{\pi(1000000;4,3)}{\pi(1000000)} \approx 0.50093\dots\] Pretty darn close.

And this doesn't just work with $d = 4$. Let's try one where $d$ is something slightly larger, just so you know nothing fishy is going on. Let's let $d = 9$. We know that $\phi(9) = \phi(3)^{2} = 4$ and the values of $a$ will be in $\{1, 2, 4, 8\}$. I'll use Mathematica to record the data we need up to $x = 100000$. \[\begin{align*} \phi(4) &= 2\\ \pi(100000;9,1)&=13063\\ \pi(100000;9,2)&=13099\\ \pi(100000;9,4)&=13070\\ \pi(100000;9,8)&=13099\\ \pi(100000) &= 52332\\ \end{align*}\] Then, \[\dfrac{\pi(100000;9,1)}{\pi(100000)} \approx 0.2496\dots\] \[\dfrac{\pi(100000;9,2)}{\pi(100000)} \approx 0.2503\dots\] \[\dfrac{\pi(100000;9,4)}{\pi(100000)} \approx 0.24975\dots\] \[\dfrac{\pi(100000;9,8)}{\pi(100000)} \approx 0.2503\dots\] We'd expect each to have the proportion $\frac{1}{4}$th of primes, and they seem to have approximately that proportion.

The Error.

What we've found is that these proportions are approximately correct — but how approximate are we claiming? The standard way to think about how close something is to its approximation is to consider the error term. In this case, we can think about the error as how close $\pi(x;d,a)$ is to $\dfrac{\pi(x)}{\phi(d)}$. Instead of proportions, we're now asking if the number of primes in $\pi(x;d,a)$ is close to the total number of primes less than or equal to $x$ divided into $\phi(d)$ parts. We can write this out as: \[E(x;d,a) = |\pi(x;d,a) - \dfrac{\pi(x)}{\phi(d)}|\] which gives us the error if we're given some $a$. Since there's a finite number of $a$'s to work with, we can actually bound our errors nicely just by talking about the largest error; in other words, recalling that $a \leq d$ by definition, \[E(x;d) = \max_{gcd(a,d) = 1}|\pi(x;d,a) - \dfrac{\pi(x)}{\phi(d)}|\] that is, $E(x;d)$ is the largest $E(x;d,a)$ when we plug in all of the possible values for $a$. There's nothing particularly crazy about this error, but we'd like to be able to say that it's bounded by something we like. Usually, bounds are given by some constant, or some polynomial, or some other function that we know a lot about (and preferably one which is simple!)...

The Elliott-Halberstam Conjecture.

Indeed, there is such a bound conjectured, but the Elliott-Halberstam conjecture states this bound in a somewhat strange way. First, it is taken over a sum of all possible values of $d$ which are somewhat smaller than $x$. This is a bit strange, but it will tell us that "on average" the error is not much larger than some particular function. Let's write it out.

Elliott-Halberstam Conjecture. For every $\theta \lt 1$ and every $A\gt 0$, there exists some constant $C\gt 0$ such that \[\sum_{1\leq d\leq x^{\theta}} E(x;d) \leq \frac{Cx}{(\log(x))^{A}}\] for every $x\gt 2$.

This conjecture has a number of interesting consequences. Moreover, this is a foundational conjecture which was altered slightly to prove some more recent theorems which were, in turn, altered slightly to create the technique which was used to attack the Twin Prime conjecture recently. We won't detail these new advancements in this post but hope that we've given the reader enough to look up some of these concepts in greater detail.