# How does one do analytic number theory?

By this point in my math journey, I'm aware that there are a lot of different types of intuition in the subject. Like visual intuition that helps in subjects like geometry and even calculus. Or algebraic intuition that helps me understand the core idea of Galois theory and helps me understand which theorems are useful in a problem. Even in "traditional" number theory (before any algebra or analysis was involved), I can still manage to tackle a problem with intuition.

But I recently began reading through "A classical introduction in number theory" and the a part of the second chapter focuses on proving the prime number theorem, the result that gave birth to analytic number theory. Of course, I know that this book is more about algebraic number theory and that the whole book isn't like this but I'm still curious on the techniques used in the proof. For example, this is one of the shorter proofs that gives a bound on the prime counting function:

I get the reasoning, but I feel like I don't understand it in the sense that I could have never come up with this myself. I know that a LOT of time went into this proof, but this just looks like random manipulations to inequalities until we get a nice bound, not to mention that the result itself looks random. Sometimes when I watch math on YouTube channels like Veritasum about number theory problems there is the time when he says something like "... and then in 2003, XYZ mathematician gave the lower bound of the function which is $$\frac{1}{3}\sqrt{\frac{\left(\log\left(\log x\right)\right)}{\sqrt{2}x}+\sqrt{5x\left(\log x\right)!}+5x^{2}}$$" (I'm making this stuff up). All these results look like random combinations of square roots, logarithms, and factorials and yet they just seem to work.

Analytic number theory is a subject that I find fascinating because I think of it as the portal between the discrete and continuous but at the same time I have absolutely no idea how mathematicians in the field do it. So I have a few questions:

1. How do people even come up with conjectures for these bounds? Computer simulations?
2. After a conjecture, how does one approach the typical problem in the field? Not crazy unsolved problems, but like something you'd find in the "challenging problems" section of a textbook.
3. What is the "intuition" of analytic number theory like?

The intuition comes from analysis. There is really no substitute here for taking a course or working through a standard text on real analysis, for example Rudin.

This specific proof about $$\pi(x)$$, as written, is very terse; as you say, it's easy for it to look like "random manipulations to inequalities." Actually the manipulations are not random at all but the underlying ideas have been obscured. The first idea is the following:

The prime-counting function $$\pi(n)$$ and the $$n^{th}$$ prime $$p_n$$ are essentially inverses and are monotonically increasing, so proving that $$\pi(n)$$ grows at least as fast as some function is equivalent to proving that $$p_n$$ grows at most as fast as some corresponding function. More precisely, if $$f : \mathbb{R}_{+} \to \mathbb{R}_{+}$$ is a strictly monotonically increasing function on the positive reals, so it has an inverse $$f^{-1} : \mathbb{R}_{+} \to \mathbb{R}_{+}$$ with the same property, then $$\pi(n) \ge f(n)$$ iff $$p_n \le f^{-1}(n)$$ (possibly up to some small error).

Explicitly, we have by definition $$\pi(p_n) = n$$, so $$\pi(n) \ge f(n)$$ implies $$\pi(p_n) = n \ge f(p_n)$$ and hence (using that $$f^{-1}$$ is monotonic) $$f^{-1}(n) \ge p_n$$. Conversely, if $$p_n \le f^{-1}(n)$$ then $$\pi(p_n) = n \le \pi(f^{-1}(n))$$, so substituting $$x = f^{-1}(n)$$ (which is not necessarily an integer) we have $$\pi(x) \ge f(x)$$ (for $$x$$ of this form).

Once you've thoroughly internalized this idea (which is the sort of thing that working through real analysis would help with!) it's clear that proving $$\pi(n) \ge \log \log n$$ is basically equivalent to proving that $$p_n \le e^{e^n}$$, since $$\log \log x$$ and $$e^{e^x}$$ are monotonically increasing inverse functions, and this is what the argument does, using Euler's proof of the infinitude of the primes to conclude that $$p_{n+1}$$ must be at most as large as $$p_1 \dots p_n + 1$$.

The second idea is about how to extract a bound from the inequality $$p_{n+1} \le p_1 \dots p_n + 1$$. It would have been pedagogically cleaner to start here first and see what upper bound this implies on $$p_n$$, and then what lower bound this implies on $$\pi(n)$$, rather than presenting the lower bound first, which comes out of nowhere. The powers of $$2$$ in the exponent of the bound $$p_n < 2^{2^n}$$ come from the following: if we define a sequence recursively by

$$a_0 = 1$$ $$a_{n+1} = a_n + \dots + a_0$$

then we have $$a_1 = 1, a_2 = 2, a_3 = 4, a_4 = 8$$, and in general $$a_n = 2^{n-1}$$ for $$n \ge 1$$ by induction. This situation is like a multiplicative version of that situation, except we have a recursive inequality instead of a recursion, and there's also that $$+1$$. But these don't turn out to affect the basic idea.

The fiddly details don't really matter because this is a very weak bound and you can, without too much difficulty, prove stronger ones. The idea is just to explore what Euler's proof alone gives you, without any harder ideas. Also the difference between working with powers of $$2$$ and powers of $$e$$ doesn't really matter because it makes very little difference to the final bound on $$\pi(n)$$; this is again the sort of thing that training in analysis helps with, understanding what the significant parts of a bound are and what's mostly irrelevant.

The significant thing about this argument is that we've lower bounded $$\pi(x)$$ by an explicit function which clearly tends to infinity; that's all.

• There is sort of a missing "intermediate" math class, "introduction to bigness," which concerns the fundamental question: how big (or small) is this? (This function, this sequence, etc.) This is a basic question in analysis, analytic number theory, combinatorics, etc. and there are a lot of elementary techniques that could go into a class like this, and it would be a good opportunity to develop experience and intuition in learning how to bound things and figure out how big (or small) they are. Commented Jul 25 at 4:48