You'll notice that as we near the end of the course, the more we will be seeing results and the less we will be giving full proofs or expecting calculations. Don't worry! Our goal, after all, is (as always) to see connections with the rest of mathematics. We are really beginning to enter the most cuttingedge questions, and of necessity there is less that I can ask of students to reinforce it. Enjoy the ride!
For today, our theme will be several of the many contributions of the great Russian mathematician Chebyshev (Чебышёв). He made fundamental advances in this type of number theory as well as in statistics!
One of his observations was that our familiar categories of primes  the classes $4k+1$ and $4k+3$  don't always seem to have the same size.
Click to the left again to hide and once more to show the dynamic interactive window 
Click to the left again to hide and once more to show the dynamic interactive window 
Do you detect the bias Chebyshev did?
Of course, for this question to make sense, we need to make sure this "prime race" won't suddenly run out of gas. We know there are infinitely many primes, but what about each type of prime?
Proposition: There are infinitely many primes congruent to 3 modulo 4.
Proposition: There are infinitely many primes congruent to 1 modulo 4.
Proof (of first proposition):
Proof (of the second proposition):
Notice that the first proof is quite elementary, and almost like the proof of the infinitude of primes, while the second one really does need something equivalent to the idea of a square root of $1$ existing modulo some primes but not modulo others.
Now, it looks like the $4k+3$ ones will always stay ahead, from what we've seen. But that's not quite right.

Up to k=26860, there are 1472 primes p\equiv 1\text{ mod }(4) and 1472 primes p\equiv 3\text{ mod }(4). Up to k=26862, there are 1473 primes p\equiv 1\text{ mod }(4) and 1472 primes p\equiv 3\text{ mod }(4). Up to k=26864, there are 1473 primes p\equiv 1\text{ mod }(4) and 1473 primes p\equiv 3\text{ mod }(4). Up to k=26880, there are 1473 primes p\equiv 1\text{ mod }(4) and 1474 primes p\equiv 3\text{ mod }(4). Up to k=26860, there are 1472 primes p\equiv 1\text{ mod }(4) and 1472 primes p\equiv 3\text{ mod }(4). Up to k=26862, there are 1473 primes p\equiv 1\text{ mod }(4) and 1472 primes p\equiv 3\text{ mod }(4). Up to k=26864, there are 1473 primes p\equiv 1\text{ mod }(4) and 1473 primes p\equiv 3\text{ mod }(4). Up to k=26880, there are 1473 primes p\equiv 1\text{ mod }(4) and 1474 primes p\equiv 3\text{ mod }(4). 
There are other places as well, and it can be fun to look for them. The next such place is over six hundred thousand, for a little while; after that, over twelve million.
Indeed, there is a theorem that there are infinitely many places where this will happen, and even that
Fact: No matter how far out you go, there exists a place $x$ where the $4k+1$ team is ahead at $x$ by $$\frac{1}{2}\frac{\sqrt{x}}{\ln(x)}\ln(\ln(\ln(x)))\; .$$
That this fact is highly nontrivial is seen in the following interact. Even though we can see the difference surge to become positive a few times, it seems hopeless to ever reach even the extremely slow $\ln(\ln(\ln(x)))$. But it does.
Click to the left again to hide and once more to show the dynamic interactive window 
We can check out other races, too. What is the pattern here?
Click to the left again to hide and once more to show the dynamic interactive window 
It turns out there are several types of theorems/conjectures one can make about such races. The key is to recognize that the 'slow' ones are the residue classes $[a]$ such that $4n+a$ can be a perfect square; in our case, only $4k+1$ and $8k+1$ are possible perfect (odd) squares.
Let's now look at the best prime race of all  of $\pi(x)$ against its approximations! Since we saw that $x/\ln(x)$ didn't seem to be as good an approximation, we'll leave it out for now.
Click to the left again to hide and once more to show the dynamic interactive window 
It seems pretty clear that $Li(x)$, even if it's a good approximation, will not ever be less than the actual count of primes. But the English mathematician Littlewood (who is also responsible for some of the first results in the prime races above) proved the following analogous result:
Fact: For any number $x$, there is an $x'>x$ such that $$Li(x')<\pi(x')\; .$$
Fact: The first time this happens is no higher than $$10^{10^{10^{10^{1000}}}}\; .$$
This bound originally had a $34$ in the last spot, but this result is without any special assumptions. In fact, today we know that
Fact: The first time this happens is no higher than $$1.4\times 10^{316}\; .$$
This sounds terrible, but actually is good news. After all, if $\pi$ beats $Li$ once in a while, then $Li$ must indeed be a great approximation. And indeed this is true.
Prime Number Theorem: If $\pi(x)$ is the number of primes $p\leq x$, then $$\lim_{x\to\infty}\frac{\pi(x)}{x/\log(x)}=1\, .$$ Equivalently, $$\lim_{x\to\infty}\frac{\pi(x)}{Li(x)}=1\; .$$
This was proved about 100 years after the initial investigations of Gauss by the French and Belgian mathematicians Jacques Hadamard and CharlesJean de la ValleePoussin. They made good use of the analytic methods we are slowly approaching.
Here are some of the many possible better approximations to $\pi(x)$ that come out of this sort of thinking. Later, we'll see more of this.
Click to the left again to hide and once more to show the dynamic interactive window 
Chebyshev made a number of contributions to these questions. The first was to prove a conjecture known (even today!) as Bertrand's Postulate.
Fact: For any integer $n\geq 2$, there is a prime between $n$ and $2n$.
Click to the left again to hide and once more to show the dynamic interactive window 
More immediately germane to our task of looking at $\pi(x)$ and its value, Chebyshev proved the first substantial result on the way to the Prime Number Theorem, validating Legendre's intuition.
Theorem: It is true both that $\pi(x)$ is $O(\frac{x}{\ln(x)})$ and that $\frac{x}{\ln(x)}$ is $O(\pi(x))$.
See the exercises to see that this is not the same as the Prime Number Theorem!
We can at least show the gist of a small piece of this:
Proposition: For big enough $x$, $$\pi(x)<2\frac{x}{\ln(x)}\; .$$
Proof Sketch:
It's not hard to verify this for $x<1000$:

Now we'll proceed by induction, in an unusual way  namely, assume it is true for $n$, and prove it is true for $2n$! This needs a little massaging for odd numbers, but is a legitimate induction method.
We end with a substantial piece of a real proof in the direction of the Prime Number Theorem. It is dense, but just like the last few proofs, requires nothing beyond calculus and a willingness to allow a lot of algebraic and integral manipulation for the purposes of estimation.
Functions: First, we'll review the main function. Think of the prime counting function $\pi$ as a socalled `step' function, where every time you hit a new prime you add 1.
Click to the left again to hide and once more to show the dynamic interactive window 
But now, instead of adding 1 each time, let's add $\log(p)$ (that is, the natural logarithm  we'll use that for the rest of this section) each time we hit a prime $p$. Of course, this will get bigger as $p$ gets bigger.
Click to the left again to hide and once more to show the dynamic interactive window 
We call this Chebyshev's theta function, and we write $$\Theta(x)=\sum_{p\leq x}\log(p)\, .$$ It turns out the Prime Number Theorem implies the following limit (in fact, they're equivalent): $$\lim_{x\to\infty}\frac{\Theta(x)}{x}=1\, .$$ Here is a plot of both limits, along with the constant function 1.
Click to the left again to hide and once more to show the dynamic interactive window 
So we will prove this implication  that if the Prime Number Theorem is true, it is also true that $\Theta(x)/x$ approaches $1$.
An Integral Formula: In order to prove this, we will first need a formula telling us about $\Theta(x)$. It turns out that integrals will help!
The Final Step: Now we have a formula for $\Theta$ which will allow us to prove something. To recap, we have: $$\frac{\Theta(x)}{x}=\frac{\pi(x)\log(x)}{x}\frac{\int_{2}^{x}\frac{\pi(t)}{t}dt}{x}\, ,$$ so, given that the Prime Number Theorem says that $\lim_{x\to\infty}$ of the fraction with $\pi(x)$ in it is 1, proving that $\lim_{x\to\infty}$ of $\frac{\Theta(x)}{x}$ is also 1 is equivalent to proving $$\lim_{x\to\infty}\frac{1}{x}\int_{2}^{x}\frac{\pi(t)}{t}dt=0\, .$$ But since the PNT essentially says that in the limit $\frac{\pi(t)}{t}\sim \frac{1}{\log(t)}$, we can write that $$\frac{1}{x}\int_{2}^{x}\frac{\pi(t)}{t}dt\sim \frac{1}{x}\int_{2}^{x}\frac{dt}{\log(t)}\, .$$ Now look at the following graph. An upper sum for the integral of $1/\log(t)$ between 2 and 9 is the area of the two rectangles shown, one with area $\frac{1}{\log(2)}(\sqrt{9}2)$ and the other with area $\frac{1}{\log(\sqrt{9})}(9\sqrt{9})$, where of course $\sqrt{9}=3$.
Click to the left again to hide and once more to show the dynamic interactive window 
So in general, the overestimate of $\int_2^x dt/\ln(t)$ will be $$\frac{1}{\log(2)}(\sqrt{x}2)+\frac{1}{\log(\sqrt{x})}(x\sqrt{x})$$ and we want the limit as $x\to\infty$ of $\frac{1}{x}$ times that quantity. This can be simplified a lot with logarithmic identities:
$$\frac{1}{x}\left(\frac{1}{\log(2)}(\sqrt{x}2)+\frac{1}{\log(\sqrt{x})}(x\sqrt{x})\right)=\frac{1}{\log(2)x^{1/2}}\frac{2}{x\log(2)}+\frac{1}{\log(\sqrt{x})}\frac{1}{\log(\sqrt{x})x^{1/2}}$$ $$=\frac{1}{\log(2)x^{1/2}}\frac{2}{x\log(2)}+\frac{2}{\log(x)}\frac{2}{\log(x)x^{1/2}}$$
Click to the left again to hide and once more to show the dynamic interactive window 
This clearly goes to zero as $x\to\infty$, and the picture seems to indicate this as well. Hence we have proved that the limit of $\frac{\theta(x)}{x}$ is the same as that of $\frac{\pi(x)}{x/\ln(x)}$, which is what we desired!
(The last few paragraphs was the other part that disappeared  I knew it was there before!)
Homework:

