mixedmath

Explorations in math and programming
David Lowry-Duda

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.

On Examples, Exercises, Problems, and ProjectsThere are actually only exercises and problems here. Any examples we come across are sufficiently important to be in the main text.

When I write examples, exercises, problems, and projects, each of these have distinct meanings. Each example should be immediately clear and help contextualize understanding. If you don't understand an example, take the time to figure out what's going on, rereading or talking to others as necessary. An exercise is a bit more involved and might take some work; but probably not too much work. These are meant to help synthesize different topics and to inspire some lines of inquiry. Sometimes, later exposition or results rely on exercises; the reader should solve every exercise. A problem is a completely optional, open-ended prompt. It is a potential starting point for experimentation and exploration. A problem doesn't have a ''right answer''. I am very happy to discuss directions based on recommended problems. Finally, a project is like a problem with at least one line of inquiry that I've thought through and think is worth exploring. Any significant progress on a project is worth writing down and sharing with others.

Rough Estimates

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

The prime number theorem implies that the $n$th prime $p_n$ is approximately $n \log n$ on average. How good is this approximation? What is the average gap between the $n$th prime and the $(n+1)$st prime?

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.

Using Exercise 2, we should expect $$\label{eq:bad_approx} \sum_{p \leq N} \sqrt{p} \approx \sum_{n = 1}^{N/\log N} \sqrt{n \log n}.$$ In particular, explain the upper bound on the summation.

Continuing from Exercise 3, we now make a crude upper bound for \eqref{eq:bad_approx}. Show the largest summand in \eqref{eq:bad_approx} has size $\approx \sqrt{N}$. (This must be, as this is a similar computation as for the upper bound on summation from Exercise 3.) Show the total number of summands in \eqref{eq:bad_approx} is $N/\log N$. (Don't overthink it). Conclude that the sum is (approximately) bounded above by $N^{3/2} / \log N$.

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.

Can you devise a heuristic argument to show that \eqref{eq:bad_approx} should be approximately bounded below by $N^{3/2} / \log N$ too? We will show this in various ways later in this note. Now is your chance to think about this before these are revealed further.

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.

Show that $$\label{eq:sum_first} \sum_{p \leq N} \sqrt{p} = \sum_{n \leq N} \sqrt{n} \big(\pi(n) - \pi(n-1)\big).$$

Show that $$\label{eq:sum_second} \sum_{p \leq N} \sqrt{p} = \pi(N)\sqrt{N + 1} - \sum_{n = 2}^N \pi(n) (\sqrt{n + 1} - \sqrt{n}).$$

Using the prime number theorem \eqref{eq:pnt}, show that we can already show \begin{equation*} \sum_{p \leq N} \sqrt{p} \leq \frac{N^{3/2}}{\log N} + O\left(\frac{N^{3/2}}{\log^2 N}\right). \end{equation*} How is this similar or dissimilar to Exercise 4?

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*}

Show that \begin{equation*} \big(\sqrt{n} - \sqrt{n + 1}\big) = -\frac{1}{2\sqrt{n}} + O(n^{-3/2}). \end{equation*} Note that to prove the error bound, it's not sufficient to truncate the binomial theorem; it's necessary to consider the entire tail. This is often annoying. But in this case, this is made much easier by noting (or showing) that $\lvert {1/2 \choose k} \rvert \leq 1$ and then bounding the tail as a geometric series.

Show that \begin{align*} \sum_{p \leq N} \sqrt{p} &= \frac{N \sqrt{N + 1}}{\log N}\left(1 + O(1/\log N) \right) \\ &\quad - \sum_{n = 2}^N \frac{\sqrt{n}}{2\log n} + O\left( \sum_{n = 2}^N \frac{\sqrt{n}}{(\log n)^2} \right). \end{align*}

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 $$\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}$$ 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$.

Verify that choose $Y = N/\log N$ nearly minimizes \eqref{eq:sum_fourth}. We say ''nearly'' because the exact point is annoying to write down. We use this approximation here. (If you are inclined, you can further optimize the cutoff point).

Show that \begin{equation*} \sum_{n = 2}^N \frac{\sqrt{n}}{2 \log n} \leq \frac{1}{3} \frac{N^{3/2}}{\log N} + O\left( \frac{N^{3/2}}{\log^{3/2} N} \right). \end{equation*} This implies that \begin{equation*} \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*}

Finally, we prove the much simpler lower bound. We have \begin{equation*} \sum_{n = 2}^N \frac{\sqrt{n}}{2 \log n} \geq \sum_{n = 2}^N \frac{\sqrt{n}}{2 \log N} = \frac{1}{2 \log N} \sum_{n = 2}^N \sqrt{n} = \frac{1}{3} \frac{N^{3/2}}{\log N} + O(\sqrt{N}). \end{equation*}

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.

\begin{equation*} \sum_{p \leq N} \sqrt{p} = \frac{2}{3} \frac{N^{3/2}}{\log N} + O\left(\frac{N^{3/2}}{\log^{3/2} N}\right). \end{equation*}

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.

Let $\{ a(n) \}$ denote a sequence of complex numbers for $n \geq 1$. Define the partial sum function \begin{equation*} A(t) := \sum_{1 \leq n \leq t} a(n), \end{equation*} and let $f$ be a continuously differentiable function. Then \begin{equation*} \sum_{n = 1}^N a(n) f(n) = A(N)f(N) - \int_0^N A(t) f'(t) dt. \end{equation*}

I do not expect the proof to be approachable to the intended audience of this note. For now, we'll take this as given.

But at the end of this note I'll sketch the ideas that lead to the proof of this. This is a surprisingly powerful tool.

Define $\mathrm{isprime}(n)$ to be the prime indicator function, \begin{equation*} \mathrm{isprime}(n) = \begin{cases} 1 & \text{if } n \; \text{is prime}, \\ 0 & \text{else}. \end{cases} \end{equation*} Let $a(n) = \mathrm{isprime}(n)$ above. Then $\pi(t) = A(t)$. Let $f(x) = \sqrt{x}$. Then \begin{equation*} \sum_{p \leq N} \sqrt{p} = \sum_{n = 1}^N a(n) f(n) \end{equation*} in the notation of Abel Summation.

This is a direct continuation of the previous exercise. Show that \begin{equation*} \sum_{p \leq N} \sqrt{p} = \pi(N) \sqrt{N} - \frac{1}{2}\int_2^N \frac{\pi(t)}{\sqrt{t}} dt. \end{equation*} Using the prime number theorem, we have \begin{equation*} \sum_{p \leq N} \sqrt{p} = \frac{N^{3/2}}{\log N} \left(1 + O(1/\log N) \right) - \frac{1}{2}\int_2^N \frac{\sqrt{t}}{\log t} \left(1 + O(1/\log t)\right) dt. \end{equation*}

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 $$\label{eq:limit} \lim_{X \to \infty} \frac{I(X)}{\frac{X^{3/2}}{\log X}}.$$

If the limit in \eqref{eq:limit} were $0$, conclude that \begin{equation*} \sum_{p \leq N} \sqrt{p} \sim \frac{N^{3/2}}{\log N}. \end{equation*} (This isn't true, of course; but it's still a good thought exercise).

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*}

Verify this limit computation. The fundamental theorem of calculus may be useful.

Show that this shows that for large $X$, we have \begin{equation*} \int_{1}^X \frac{\pi(t)}{\sqrt{t}} dt \sim \frac{2}{3} \frac{X^{3/2}}{\log X}. \end{equation*}

Conclude that \begin{equation*} \sum_{p \leq N} \sqrt{p} \sim \frac{2}{3} \frac{N^{3/2}}{\log N}, \end{equation*} giving another (partial) proof of Proposition Proposition 13.

Unfortunately, using l'Hôpital's rule as above prevents us from tracking the error term in the above approximation. It actually is possible to massage this method to extract an error term as well, but this is a bit complicated.

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.

Show that \begin{equation*} \int_2^N \frac{t^{1/2}}{\log^{A + 1} t} dt = O\left( \frac{N^{3/2}}{\log^{A + 1} N} \right). \end{equation*} Almost every technique we've described up to now works. Forcan use l'Hôpital's rule (as we don't care about further error terms), split the integral at a midpoint, or use heuristics similar to our initial heuristics.

Give another proof of Proposition Proposition 13. What error term do you get now? (If you're careful, it's the best error term yet).

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$.

Prove that \begin{equation*} \sum_{p \leq N} p \sim \frac{1}{2} \frac{N^2}{\log N} \end{equation*} in at least two different ways.

Prove that \begin{equation*} \sum_{p \leq N} \frac{1}{p} \sim \log \log N \end{equation*} in at least two different ways.

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 interval1 1the 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.

bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using $(inline math)$ or $$(your display equation)$$.