Primitive Sets: I · II · III · IV · V
To rank infinite sets we weigh each element and add. This volume builds the weight $1/(a\log a)$, explains why it is the only sensible choice, and computes the score to beat: $f(\mathcal{P}) = 1.6366\ldots$
Vol. I ended with a wish list for a ruler: notice small integers more than large ones, stay finite on infinite sets, and be exactly harsh enough that primitivity is what keeps the score bounded. Every item on that list is a statement about infinite sums, so we start there.
infinite sums
We will compare primitive sets by adding infinitely many positive numbers. Two facts from calculus, and two applications, are the entire analytic toolkit.
A series of positive terms has only two possible fates. Its partial sums increase, so either they stay below some fixed number (and then they settle to a limit: the series converges), or they do not (and then they grow past every bound: the series diverges, and we write $\sum = \infty$). There is no oscillation to worry about. That is why every sum in this series can be manipulated freely: rearranged, grouped, split into pieces.
The harmonic series diverges. Group the terms of $\sum 1/n$ into blocks whose lengths are powers of two:
\[1 + \frac12 + \underbrace{\Bigl(\frac13+\frac14\Bigr)}_{\ge \frac12} + \underbrace{\Bigl(\frac15+\cdots+\frac18\Bigr)}_{\ge \frac12} + \underbrace{\Bigl(\frac19+\cdots+\frac1{16}\Bigr)}_{\ge \frac12} + \cdots.\]There are infinitely many blocks, each at least $1/2$, so the sum is infinite. We write $\sum 1/n = \infty$. It diverges slowly: the first $N$ terms add up to about $\log N$.
The integral test. If $g(x)$ is positive and decreasing, the series $\sum_{n \ge N} g(n)$ and the integral $\int_N^\infty g(x)\,dx$ either both settle to a finite number or both run off to infinity. The picture is that the sum is a staircase of rectangles of height $g(n)$ and width $1$, and the integral is the area under the curve. The curve sits under the staircase starting at $N$ and over the staircase starting at $N+1$, so they sandwich each other.
Two integrals we will use. Substitute $u = \log x$, so $du = dx/x$:
\[\int_3^{\infty} \frac{dx}{x\log x} \;=\; \int_{\log 3}^{\infty} \frac{du}{u} \;=\; \infty,\] \[\int_3^{\infty} \frac{dx}{x(\log x)^2} \;=\; \int_{\log 3}^{\infty} \frac{du}{u^2} \;=\; \frac{1}{\log 3} \;<\; \infty.\]So $\sum 1/(n\log n)$ diverges, and $\sum 1/(n(\log n)^2)$ converges. One extra $\log$ in the denominator is the difference between “infinite” and “finite.” That borderline is where the whole subject lives.
Notice how slowly $\sum 1/(n\log n)$ diverges: its partial sum up to $x$ is about $\log\log x$. At $x = 10^{100}$, $\log\log x \approx 5.4$. You would never see it diverge on a computer. Proofs, not experiments, decide convergence at this borderline.
A word on notation: we write $g(x) \sim h(x)$ to mean $g(x)/h(x) \to 1$ as $x \to \infty$. The two sides become indistinguishable as a percentage, even if they still differ by a large number. So $x^2 + x \sim x^2$, although the difference $x$ grows without bound.
the scale $f(A)$
Each integer $a$ is given a positive weight that gets smaller as $a$ gets larger, but slowly. (Reminder: $\log$ is $\ln$, so $\log 6 \approx 1.792$, not $\log_{10} 6$.)
A small set, computed by hand. For $A = \lbrace 6, 10, 15\rbrace$:
\[\log 6 \approx 1.792, \quad 6\log 6 \approx 10.75, \quad \frac{1}{6\log 6} \approx 0.093,\] \[\log 10 \approx 2.303, \quad \frac{1}{10\log 10} \approx 0.043, \qquad \log 15 \approx 2.708, \quad \frac{1}{15\log 15} \approx 0.025.\]So $f(\lbrace 6,10,15\rbrace) \approx 0.161$. Tiny.
The primes, the first few terms. Write $\mathcal{P}$ for the set of all primes.
| $p$ | $f(p) = 1/(p\log p)$ | running sum |
|---|---|---|
| $2$ | $0.7213$ | $0.7213$ |
| $3$ | $0.3034$ | $1.0248$ |
| $5$ | $0.1243$ | $1.1490$ |
| $7$ | $0.0734$ | $1.2224$ |
| $11$ | $0.0379$ | $1.2604$ |
| $13$ | $0.0300$ | $1.2903$ |
| $17$ | $0.0208$ | $1.3111$ |
| $19$ | $0.0179$ | $1.3290$ |
The first two primes already contribute more than $1$. The first eight already contribute $1.33$, against $0.161$ for $\lbrace 6,10,15\rbrace$. Henri Cohen computed the full sum:
\[f(\mathcal{P}) \;=\; 1.6366\ldots\](That the infinite sum settles at all is not obvious. We prove it at the end of this volume.) This is the score to beat, and the theorem of the series is that nobody beats it.
why this weight?
Why $1/(a\log a)$, and not another weight? Try the neighbours.
- Weight $1/a$. The primes score $\sum 1/p = \infty$. The numbers with $\Omega(n) = 2$ score infinity too: their sum $\sum_{p\le q} 1/(pq)$ contains $\frac12\bigl((\sum 1/p)^2 - \sum 1/p^2\bigr)$. The scale cannot tell the contestants apart.
- Weight $1/a^2$. Everything converges too easily. The primes score only $\sum_p 1/p^2 \approx 0.452$, and a pile of small composites can compete. The scale no longer sees the primes as special.
- Weight $1/(a(\log a)^2)$. The primes still converge, but for a bad reason: the integral test already says $\sum_n 1/(n(\log n)^2)$ converges, so every set of integers has a finite score. Primitivity is no longer the constraint that keeps the sum finite, and the contest stops being about the divisibility structure.
The weight $1/(a\log a)$ sits on the knife-edge: $\sum_n 1/(n\log n)$ diverges, while $\sum_p 1/(p\log p)$ converges. The scale is sensitive enough to see the primes as a finite budget, but not so harsh that composites become irrelevant. Primitivity is exactly what makes the sum finite. That is Erdős’s theorem of 1935, and it is Vol. III.
Watch the knife-edge. Pick a weight and drag the cutoff. The two curves are the partial sums over all integers $2\le n\le x$ and over the primes $p \le x$.
The horizontal axis is logarithmic, from $10$ to $10^6$. Under $1/(a\log a)$ the orange curve keeps climbing, like $\log\log x$, while the blue one flattens toward the dashed line at $1.6366$. The shaded gap is the tail still to come, about $1/\log x$.
There is also a calculus identity behind the weight. For any $a \ge 2$,
\[\int_1^{\infty} a^{-t}\,dt \;=\; \frac{1}{a\log a}.\]To see it, write $a^{-t} = e^{-t\log a}$ and substitute $u = t\log a$, so $du = \log a\, dt$:
\[\int_1^{\infty} e^{-t\log a}\,dt \;=\; \frac{1}{\log a} \int_{\log a}^{\infty} e^{-u}\,du \;=\; \frac{1}{\log a}\cdot e^{-\log a} \;=\; \frac{1}{a\log a}.\]So $1/(a\log a)$ is the $t$-average of the scores $a^{-t}$. We will not need this identity for the proof. It is here because it is where the weight comes from, and because it explains a warning: if you ask for the stronger comparison $\sum_{a \in A} a^{-t} \le \sum_p p^{-t}$ at every $t > 1$, the answer is no. That holds only for $t \ge \tau \approx 1.1403$. Shift the original weight slightly to $1/(a(\log a+h))$ and the primes stop winning as soon as $h \ge 1.04$. The theorem, once proved, is only just true.
why $f(\mathcal{P})$ is finite
We have been using $f(\mathcal{P}) = 1.6366\ldots$ as a finite number. Here is why the series converges.
The prime number theorem, taken as a named fact, says that the number of primes up to $x$ is about $x/\log x$. Equivalently, near $t$ the primes have density about $1/\log t$, and the $n$th prime is $p_n \sim n\log n$. Then
\[\frac{1}{p_n \log p_n} \;\sim\; \frac{1}{n\log n \cdot \log(n\log n)}.\]And $\log(n\log n) = \log n + \log\log n \sim \log n$, so
\[\frac{1}{p_n \log p_n} \;\sim\; \frac{1}{n(\log n)^2}.\]We already know $\sum 1/(n(\log n)^2)$ converges, by the integral test. By the limit comparison test, a series of positive terms that behaves like a convergent series converges. So $\sum_p 1/(p\log p)$ converges.
The same integral explains the tail. The amount contributed by primes larger than $x$ is about
\[\int_x^\infty \frac{1}{t\log t}\cdot\frac{dt}{\log t} \;=\; \frac{1}{\log x},\]where the second factor $dt/\log t$ is the prime number theorem’s “number of primes in $[t, t+dt]$”:
| primes up to | partial sum | gap to $1.6366$ | $1/\log x$ |
|---|---|---|---|
| $10^2$ | $1.4216$ | $0.215$ | $0.217$ |
| $10^4$ | $1.5282$ | $0.108$ | $0.109$ |
| $10^6$ | $1.5642$ | $0.072$ | $0.072$ |
| $10^8$ | $1.5823$ | $0.054$ | $0.054$ |
Each extra two orders of magnitude in the cutoff trims the gap by a factor of about $2/3$, not by an order of magnitude. That is what a $1/\log x$ tail looks like. It is also why the conjecture cannot be checked by adding up primitive sets until $10^{12}$ and comparing: the tail is large enough to hide a counterexample sitting out at infinity.
Where the sum sits among its neighbours:
| series | converges? | value / growth |
|---|---|---|
| $\sum_p 1/p^2$ | yes | $0.4522\ldots$ |
| $\sum_p 1/(p\log p)$ | yes | $1.6366\ldots$ |
| $\sum_p 1/p$ | no | $\sim \log\log x$ |
| $\sum_n 1/(n\log n)$ | no | $\sim \log\log x$ |
The extra $\log$ in the denominator is not enough to make the sum over all integers converge. It is enough once you keep only the primes, because the primes themselves contribute another $1/\log n$ of sparsity. That second logarithm is a gift of the prime number theorem.
Check yourself. The sums over the primes of $1/p$ and over all $n$ of $1/(n\log n)$ both grow like $\log\log x$. Why is that no coincidence?
They are the same integral. The primes near $t$ have density $1/\log t$, so $\sum_{p\le x} 1/p \approx \int^x \frac{1}{t}\cdot\frac{dt}{\log t}$, which is exactly the integral that controls $\sum_{n\le x} 1/(n\log n)$. Substituting $u = \log t$ turns it into $\int du/u = \log u = \log\log x$. Thinning the integers to the primes costs one factor of $\log$, the same factor the weight $1/(a\log a)$ puts on every integer.
where this goes
We have the ruler, $f(A) = \sum 1/(a\log a)$. We know it sits on the knife-edge: over all integers it diverges, over the primes it converges to $1.6366$. And we know experiments cannot settle anything here, because tails decay like $1/\log x$.
The first real question is whether every primitive set has a finite score. It does, and the proof is the most beautiful idea in the series: give each element of $A$ a private territory of integers, show that primitivity keeps the territories from overlapping, and let the size of the number line pay the bill. That is Vol. III.
Next: Vol. III: Territories and the $e^\gamma$ Bound
Primitive Sets: Vol. I · Vol. II · Vol. III · Vol. IV · Vol. V