## DyingLoveGrape.## 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 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 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 ## 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: 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 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 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 ## The Elliott-Halberstam Conjecture.Indeed, there
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. |