Disclaimer: everything in this post will be toy examples.

sieve

(references: Elkies 259 notes, Maynard IAS talk)

Suppose you want to determine the number of primes in \([n,2n]\). You could write down an “inclusion-exclusion” formula.

\[n - \text{num multiples of 2} - \text{num multiples of 3} + \text{multiples of 6} + \cdots\]

But it doesn’t really work. Everything is wrong. The error term completely eats everything.

But say you were interested in a different quantity. How many numbers between \([n,2n]\) have all their prime factors larger than \(z\)?

Then we have a nice truncated inclusion exclusion. If \(z<\log n\) say, then the error term isn’t swamped.

Let \(D\subset [n,2n]\) be the set of numbers that have all of their prime divisors smaller than \(z\). Let \(\mu(d)\) be \(-1^{\text{number of divisors of d}}\) if \(d\) is square-free and \(0\) otherwise. We get \[ \sum_{d\in D} \mu(d) (\frac{n}{d} +O(1)) \le n \prod_{p\le z} (1- \frac{1}{p}) + O(2^{\pi(z)}) = \frac{nc}{\log z}+O(2^{\pi(z)}).\]

I think in Elkies lecture notes he uses the Selberg sieve to prove something like a mildly quantitative version of dirichlet’s theorem?

can’t state it here yet, it’s rather technical.

circle method

https://terrytao.wordpress.com/2012/05/20/heuristic-limitations-of-the-circle-method/ https://en.wikipedia.org/wiki/Hardy%E2%80%93Ramanujan%E2%80%93Littlewood_circle_method

In fact, I think the resource I’m eventually going to use to learn more about this is “Additive Number Theory: The Classical Bases” By Nathanson. It looks to be approachably written. It also talks about sieve theory. So yeah, a book worth checking out for sure. Apostol’s “Intro to Analytic Number Theory” also seems like a resource worth reading. As do the Elkies lecture notes of course.

Suppose we have some (usually infinite) set \(A\) and we want to count the number of solutions to the equation \(n = a_1+a_2+a_3\) with \(a_1,a_2,a_3\in A\). Let \(r_3(n)\) denote the number of such solutions.

Lots of problems can be described like this.

• Goldbach’s conjecture: all even numbers larger than 2 can be written as the sum of two primes
• Harding Warring problem: express numbers as sum of a bounded number of powers

Let \[f(z) = \sum_{n\ge 0} \mathbb{1}_A(n) z^{n}.\] Observe that \[ f(z)^{3} = \sum_{n\ge 0} r_3(n) z^{n}.\]

So, the question becomes, is there a nice way to extract the coefficient we want from this sum? The answer is, maybe if you’re lucky.

Consider \[ \frac{f(z)^{3}}{z^{n+1}}. \] The coefficient of the \(1/z\) term in this is precisely the thing we want: \(r_3(n)\).

So I guess we have \[ r_3(n) = \oint_\gamma \frac{f(z)^{3}}{z^{n+1}} .\]

Here’s a funny example from the “mathgeeks” youtube channel which I recently ran across (which has some videos half in chinese! which I’ve enjoyed)

Let \(A = \mathbb{N}\). So \(r_3(n)\) is the number of ways to have three numbers that sum to \(n\). Of course this is trivial to compute: \(\binom{n+2}{2}\) I believe. But here’s how you can do it with analytic number theory:

\[ f(z) = \sum_{n\ge 0}z^{n} = \frac{1}{1-z}.\] So we need to compute \[ \oint_\gamma \frac{1}{(1-z)^{3}} \frac{1}{z^{n+1}} \] You do a Laurent expansion for \(\frac{1}{(1-z)^{3}}\) around \(0\) and then you use cauchy integral formula or whatever. I think we have by the negative binomial formula \[ (1-z)^{-3} = \sum_{k\ge 0} \binom{-3}{k} (-z)^{k} \]

Recall negative binomial coefficient is defined as \[ \binom{-5}{3} = \frac{(-5)(-4)(-3)}{3!}. \]

Anyways we do the integral thing and it turns out to extract the correct coefficient.

So usually when you do the circle method you aren’t going to actually exactly compute the integral in question. You’ll approximate it.