This is a supplementary note I wrote for students working on a research project this summer.I wrote this note in tex and converted it here. There are a small number of formatting oddities that appear. Let me know if you find anything that you think got lost in the formatting. We explore how to use straightforward, direct approaches to obtain asymptotics for sums over primes. Although there are higher powered techniques available, some of the ideas here apply very widely.

Introduction

We talked about the sum of primes up to $N$ on Monday, \begin{equation*} \sum_{p \leq N} \sqrt{p}. \end{equation*} I think there are several interesting techniques and possibilities to handle this sort of estimate. This extended note gives some details on some of these ideas.

This contrasts with the task of actually exactly computing sums over primes (the main topic of the project). Here, we are concerned only with estimates and approximations. It is much easier to get an answer that is close to being right than it is to get an answer that is exactly right.

I maintain the same meaning of examples, exercises, problems, and projects and in my project brief.

Rough Estimates

We first try to keep as elementary an approach as possible to study \begin{equation}\label{eq:base_sum} \sum_{p \leq N} \sqrt{p}. \end{equation} We will make heavy use of the prime number theorem, in the form \begin{equation}\label{eq:pnt} \pi(n) = \frac{n}{\log n} + O\left( \frac{n}{\log^2 n} \right), \end{equation} where $\pi(n)$ counts the number of primes up to $n$.

The challenge with \eqref{eq:base_sum} is that we're summing over primes. Primes are varied and hard to understand individually. But with nothing more than the prime number theorem, we can make pretty good guesses.

This pattern is often true. Sums $\sum_{p \leq N} f(p)$ with positive, ''sufficiently nice'' functions $f$ often behave approximately like $(\log N)^{-1} \sum_{n \leq N} f(n)$. These last three exercises give one explanation for this heuristic.

Keeping sums

For our first approach, we will try to use a direct, elementary approach to study \begin{equation*} \sum_{p \leq N} \sqrt{p} \end{equation*} directly.

To do better than an upper bound, we need to study the difference of square roots more closely. To do this, we use the binomial theorem. First, we rewrite \begin{equation*} \big(\sqrt{n} - \sqrt{n + 1}\big) = \sqrt{n} \left( 1 - \sqrt{1 + \tfrac{1}{n}} \right). \end{equation*} For $n \geq 2$, the binomial theorem shows that \begin{equation*} \sqrt{1 + \tfrac{1}{n}} = \sum_{k \geq 0} { 1/2 \choose k } \big( \tfrac{1}{n} \big)^k = 1 + \frac{1}{2n} - \frac{1}{8n^2} + \frac{1}{16 n^3} + \cdots \end{equation*} where recall that we define the binomial coefficient in terms of the falling factorial: \begin{equation*} { r \choose k } = \frac{r(r-1) \cdots (r - k + 1)}{k!} = \frac{(r)_k}{k!}. \end{equation*}

We have now removed most of the ''number theory'' content, and we are left with a purely analytic problem. To solve this problem, we will split the sum at some middle point $Y$ and consider the smaller and larger parts separately.

Write \begin{equation*} \sum_{n = 2}^N \frac{\sqrt{n}}{2 \log n} = \sum_{n = 2}^{Y} \frac{\sqrt{n}}{2 \log n} + \sum_{n = Y + 1}^N \frac{\sqrt{n}}{2 \log n}. \end{equation*} The first sum is bounded in absolute value by \begin{equation*} \sum_{n = 2}^{Y} \sqrt{n} \ll Y^{3/2}. \end{equation*} For the second sum, as $n \geq Y$, we have that $\log n \geq \log (Y)$, hence \begin{equation*} \sum_{n = Y + 1}^N \frac{\sqrt{n}}{2 \log n} \leq \frac{1}{2 \log Y} \sum_{n = Y + 1}^N \sqrt{n} \ll \frac{1}{\log Y} N^{3/2}. \end{equation*} Together, this shows that \begin{equation}\label{eq:sum_fourth} \sum_{n = 2}^N \frac{\sqrt{n}}{2 \log n} \ll Y^{3/2} + \frac{1}{\log Y} N^{3/2} \end{equation} for any $Y$ satisfying $2 < Y < N$. We get the best possible bound when the two terms on the right hand side are equal, which is close to when $Y = N/\log N$.

Assembling together, we can now prove that \begin{equation*} \frac{2}{3} \frac{N^{3/2}}{\log N} + O\left(\frac{N^{3/2}}{\log^2 N}\right) \leq \sum_{p \leq N} \sqrt{p} \leq \frac{2}{3} \frac{N^{3/2}}{\log N} + O\left(\frac{N^{3/2}}{\log^{3/2} N}\right), \end{equation*} which implies the following.

Approximation by integration

A second way to approach $\sum_{p \leq N} \sqrt{p}$ is through integration. To transform a sum into in integral, we apply a method called Abel Summation.

This last expression is very similar to the expression from Exercise 8. It would be possible to do similar analysis here: choose a cutoff point $Y$, split the integral, and optimize the choice of $Y$. But since we're dealing with integrals, we have the tools of calculus at our disposal.

We apply l'Hôpital's rule directly to our heuristic from Exercise 4: where we expect $N^{3/2}/\log N$ to be the approximate answer.

Let \begin{equation*} I(X) := \int_2^X \frac{\pi(t)}{\sqrt{t}} dt \end{equation*} and consider the limit \begin{equation}\label{eq:limit} \lim_{X \to \infty} \frac{I(X)}{\frac{X^{3/2}}{\log X}}. \end{equation}

The limit is of the form $\infty / \infty$ (if this isn't clear, then prove it). Both the numerator and denominator are differentiable. Thus we can try to study the limit by studying \begin{equation*} \lim_{X \to \infty} \frac{I'(X)}{\frac{d}{dx} \frac{X^{3/2}}{\log X}} = \frac{3}{2}. \end{equation*}

Less clever

We can also be less clever and approach the integral directly. I sketch this directly, ignoring error terms.

We want to study \begin{equation*} \frac{1}{2} \int_2^N \frac{\sqrt{t}}{\log t} dt. \end{equation*} Integrating by parts, this is equal to \begin{equation*} \left[ \frac{1}{3} \frac{t^{3/2}}{\log t} \right]_2^N + \frac{1}{3} \int_2^N \frac{t^{1/2}}{\log^2 t} dt. \end{equation*} Repeated applications of integration by parts allow more and more main terms, with an integral of the form \begin{equation*} \int_2^N \frac{t^{1/2}}{\log^{A+1} t} dt \end{equation*} after $A$ iterations of integraion by parts.

Generalization

Although this was a deep investigation into one asymptotic, this set of techniques applies to general sums of the form \begin{equation*} \sum_{p \leq N} f(p) \end{equation*} for many ''nice'' functions $p$.

The quality of being ''nice'' doesn't have a strict definition. This is part of what makes this line of questioning interesting.

Appendix

Riemann-Stieltjes Integration

Finally, we briefly touch on a very powerful idea in integration that is very commonly used in number theory. This is a more general theory of integration than the standard theory of Riemann integration taught in early calculus classes.

For a function $f$ defined on an interval $[a, b]$, we can define the integral as a limit of sums of the form \begin{equation*} \int_a^b f(t) dt = \lim \sum_{i} f(c_i) [x_{i} - x_{i - 1}]. \end{equation*} This shorthand is an abuse of notation. With more words, we consider partitions \begin{equation*} a = x_0 \le x_1 \le \cdots \le x_n = b \end{equation*} of the interval $[a, b]$. We call the width of the partition to be \begin{equation*} \max_{1 \leq i \leq n} (x_i - x_{i-1}). \end{equation*} Then we say that a function $f$ is Riemann-integrable over $[a, b]$ if all sums of the form \begin{equation*} \sum_{i = 1}^n f(c_i) (x_i - x_{i-1}) \end{equation*} over a partition of $[a, b]$ (and where $c_i \in (x_{i-1}, x_i)$) tend to a particular value as the width of the partitions tend to $0$. If this occurs, then $f$ is Riemann-integrable and that common value is called \begin{equation*} \int_a^b f(t) dt. \end{equation*}

Sometimes we learn the equivalent definition of requiring the lower-sums (where $f(c_i) = \min_{t \in [x_{i-1}, x_i]} f(t)$) and upper sums (where $f(c_i) = \max_{t \in [x_{i-1}, x_i]} f(t)$) tend to a common limit. (This is the theory of Darboux integration, which is equivalent to Riemann integration).

We now resume abuse of notation. Stated differently, Riemann integration consists of integrals with the shape \begin{equation*} \int_a^b f(t) dt \approx \sum f(t_i) \Delta(t_i), \end{equation*} where $\Delta(t_i) = (t_i - t_{i-1})$ stands for the difference in $t$.

On the other hand, Riemann-Stieltjes integration consists of integrals of the shape \begin{equation*} \int_a^b f(t) d(g(t)) \approx f(t_i) \Delta\big( g(t_i) \big), \end{equation*} where $f$ and $g$ are both ''nice'' functions. The theory is much simpler if $g$ is taken to be nondecreasing.

If $g(t) = t$, then Riemann-Stieltjes integration is exactly Riemann integration. But $g(t)$ can be many things.

For example, we can take $g(t) = \pi(t)$, the prime counting function. Let's consider \begin{equation*} \int_1^X f(t) d \pi(t) \approx \sum f(t_i) \Delta\big( \pi(t_i) \big). \end{equation*} When $t_{i-1} < p < t_i$ for a prime $p$, we have that $\Delta \big( \pi(t_i) \big) = 1$. On all other intervals, $\Delta\big( \pi(t_i) \big) = 0$. As the width of the partitions tends to $0$, for the relevant interval^{1 1}the index $i$ implicitly depends on the prime $p$. $[t_{i-1}, t_i]$ containing a fixed prime $p$, we must have $t_{i-1} \to p$ and $t_i \to p$; if $f$ is continuous, then $f(c_i) \to f(p)$ for all $c_i \in [t_{i-1}, t_i]$. Altogether, this means that the interval$[t_{i-1}, t_i]$ containing a prime $p$ with $1 \le p \leq X$ contributes $f(p) \cdot 1$ to $\int_1^X f(t) d \pi(t)$. In total, adding the contributions from intervals around each prime, we get that \begin{equation*} \int_1^X f(t) d \pi(t) = \sum_{p \leq X} f(p) \end{equation*} for continuous functions $f$.

Thus far, we haven't gained anything. But many aspects of typical Riemann integration carry over. In particular, we still have integration by parts. Here, it takes the form \begin{equation*} \int_a^b f(t) dg(t) = \Big[ f(t) g(t) \Big]_a^b - \int_a^b g(t) d f(t). \end{equation*} If $g$ is nondecreasing and ''nice'', and $f$ is differentiable, then \begin{equation*} \int_a^b g(t) df(t) = \int_a^b g(t) f'(t) dt. \end{equation*}

For example, when $g(t) = \pi(t)$, integration by parts tells us that \begin{equation*} \sum_{a \le p \leq b} f(p) = \int_a^b f(t) d \pi(t) = \Big[ f(t) \pi(t) \Big]_a^b - \int_a^b \pi(t) f'(t) dt. \end{equation*} This is exactly the application of Abel Summation (Theorem 14) we used above.

More generally, given a sequence of numbers $\{a(n)\}$ for $n \geq 1$, define $A(t) = \sum_{n \leq t} a(t)$. Then \begin{equation*} \sum_{n = 1}^N a(n) f(n) = \int_0^N f(t) dA(t) = \Big[ f(t) A(t) \Big]_0^N - \int_0^N A(t) f'(t) dt, \end{equation*} which is the proof of Theorem 14. This is an extremely powerful tool.

Leave a comment

Comment via email