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 most of the 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 these posts 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, height $g(n)$ on $[n, n+1]$, and the integral is the area under the curve. Because $g$ decreases, the curve sits under that staircase and over the same staircase slid one unit left, so $\sum_{n \ge N+1} g(n) \le \int_N^\infty g(x)\,dx \le \sum_{n \ge N} g(n)$.
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, only slightly faster than $1/a$. (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 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 no primitive set 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)$ equals $\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$, more than half of it from the prime $2$, and all the composites together score about $0.193$. A few small numbers settle the contest.
- 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 harsh enough that the primes have a finite score, but not so harsh that every set does. 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 integral over $t \ge 1$ of the scores $a^{-t}$. We will not need this identity for the proof. It is how Henri Cohen computed $f(\mathcal{P})$ (integrate $\sum_p p^{-t}$ over $t$; adding up the primes directly converges far too slowly). It also explains a warning. If the stronger comparison $\sum_{a \in A} a^{-t} \le \sum_p p^{-t}$ held at every $t > 1$, integrating it would prove the theorem. It does not: it holds only for $t \ge \tau \approx 1.1403$. Shift the original weight slightly to $1/(a(\log a+h))$ and the primes lose for every $h$ above $0.8035\ldots$: the integers with exactly $k$ prime factors, for large $k$, beat them (Lichtman). 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 are $\sim$ the terms of a convergent series also 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 row multiplies the cutoff by $100$, yet the gap shrinks only by a factor of about $1/2$, then $2/3$, then $3/4$. 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 idea the rest of the series builds on: 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.