Why a quarter of numbers overshoot

Six is perfect, twelve is abundant, and so are eighteen, twenty, twenty-four and thirty. Below a thousand, 246 numbers have proper divisors adding to more than themselves; below a million, 247,545 do. The proportion drifts toward a quarter and settles there, and the divisor rectangle records the value it settles at: about $0.2476$.

That sentence hides a theorem, and the theorem is less obvious than the number. A proportion of the whole numbers need not exist. The share of numbers below $x$ whose first digit is 1 swings between about a ninth and more than a half as $x$ runs through the powers of ten, and never settles at all. A set can be defined by a rule as simple as that and have no density. The abundant numbers do have one, and the reason is a structural fact about divisor sums that is worth taking apart.

The picture already shows the structure. The dots are not scattered; they form horizontal bands, and each band is a family. The numbers of the form $2p$, with $p$ a prime, sit just above $1.5$; the numbers $4p$ just above $1.75$; the numbers $6p$ just above two; the numbers $12p$ just above $2.33$. In each family the abundancy is $\sigma(m)/m$ for the small part $m$, times $1 + 1/p$ for the prime, and as $p$ grows that second factor sinks toward one and the dots crowd down onto the band’s floor.

So a number’s abundancy is set almost entirely by its small factors, and the numbers divisible by 6 sit at or above two because 6 itself does. Abundance is not a property numbers happen to have one at a time. It is passed down.

Abundance is inherited #

The abundancy $\sigma(n)/n$ is the sum of $1/d$ over the divisors $d$ of $n$, since dividing each divisor into $n$ just reorders the list. Multiply $n$ by any $k$ and every divisor $d$ of $n$ gives a divisor $d$ of $kn$ — and $kn$ may have more — so

$$\frac{\sigma(kn)}{kn} = \sum_{d \mid kn} \frac1d \;\ge\; \sum_{d \mid n} \frac1d = \frac{\sigma(n)}{n},$$

with strict inequality whenever $k > 1$, because $kn$ has itself as a divisor and $n$ does not. Multiplying a number never lowers its abundancy. So every proper multiple of a perfect number is abundant, and every multiple of an abundant number is abundant.

That turns the set of abundant numbers into a set of multiples. Call an abundant number primitive if every proper divisor of it is deficient — if it is the first number in its line of descent to overshoot. Every abundant number is then a multiple either of a perfect number or of a primitive abundant one, and the whole set is generated by those.

Five primitive abundant numbers and two perfect numbers account for all sixty-nine abundant numbers below three hundred. Twelve, eighteen, twenty-four and thirty are there as multiples of six; fifty-six as a multiple of twenty-eight; forty as a multiple of twenty. The generators are sparse and their descendants are dense, which is the whole situation in miniature.

A set of multiples need not have a density #

A set generated as the multiples of finitely many numbers is periodic: whether $n$ belongs depends only on $n$ modulo the least common multiple of the generators, so its density is simply the share of one period, computable exactly by inclusion and exclusion. Multiples of 6 or 20 have density $1/6 + 1/20 - 1/60 = 1/5$.

With infinitely many generators nothing of the kind is guaranteed, and in 1934 Abram Besicovitch showed that it genuinely fails. He constructed an infinite list of numbers whose set of multiples has no density at all: the share of multiples below $x$ keeps oscillating between two different values as $x$ grows, forever. His generators were chosen in long blocks of consecutive numbers, placed at ever larger scales, so that each new block adds a burst of multiples in its own range and almost nothing elsewhere.

So the abundant numbers having a density is a fact about which generators they have. The structural argument above reduces the question to one about the primitive abundant numbers, and the answer depends on how thinly those are spread.

Sparse enough to add up #

The criterion that separates the good cases from Besicovitch’s is the sum of reciprocals. If the generators $a_1, a_2, \dots$ satisfy

$$\sum_i \frac{1}{a_i} < \infty,$$

then the set of their multiples has a density. The argument is an approximation: the multiples of the first $N$ generators form a periodic set with an exact density $\delta_N$, which increases with $N$; and the multiples contributed by all the later generators have upper density at most $\sum_{i > N} 1/a_i$, which the convergence makes as small as desired. The upper and lower densities of the whole set are therefore trapped between $\delta_N$ and $\delta_N + \sum_{i>N} 1/a_i$ for every $N$, and the gap closes. Besicovitch’s generators were arranged so that this sum diverges.

Erdős proved in the 1930s that the primitive abundant numbers are that sparse. Their count up to $x$ is smaller than $x/(\log x)^k$ for every fixed $k$, which is far more than enough for the reciprocals to converge. Together with the structural argument, that settles the existence of the density.

The figure is an honest picture of a convergent series that nobody could guess converges from its graph. It rises in steps at 20, 70, 88 and 104, then keeps climbing on a logarithmic axis through six decades without any visible flattening. That is not in tension with the theorem. Primitive abundant numbers are sparse on average but not very sparse — their count up to $x$ falls short of $x$ by a factor that grows more slowly than any power of $x$ — and a sum whose tail shrinks that slowly looks exactly like this over any range a computer can reach.

Why no number is ever typical #

The bands in the first figure also explain the most surprising feature of the distribution, which is that it has no gaps and no spikes.

Every value $\sigma(m)/m$ is the floor of a band, and above it lie infinitely many dots, one for each large prime. Those floors are dense: for any interval above one, however short, some $m$ has abundancy inside it. So there is no range of abundancies that numbers avoid, and the distribution has no flat stretches.

At the same time no single value collects a positive share of all numbers. The dots in a band approach its floor without reaching it, and hitting one exact value needs the small part and the large part of a number to cooperate precisely, which few numbers do. Davenport’s theorem makes that precise: the distribution is continuous, so every individual value of the abundancy, two included, is taken by a set of density nought. The perfect numbers have density nought for the same reason every other exact abundancy does — not because two is special, but because no number is typical enough to share its value with a positive proportion of the others.

That is a clean way to see a fact that the perfect numbers’ own theory establishes by much harder means. Even if there were infinitely many perfect numbers, odd ones included, they would occupy no share of the integers at all, and the quarter of numbers above the line and the three quarters below it would not change by any amount.

Where the quarter comes from #

Davenport had shown in 1933, by a different route, that the ratio $\sigma(n)/n$ has a genuine distribution: for every threshold $t$, the share of numbers with $\sigma(n)/n \ge t$ tends to a limit. The abundant density is the value of that function at $t = 2$.

The band was established by Marc Deléglise in 1998, and the method is the approximation above run as an algorithm. Take the primitive abundant numbers up to some bound, compute the exact density of their multiples, and bound the contribution of everything beyond — the only difficulty being that the exact density of a set of multiples of thousands of generators needs cleverness rather than inclusion–exclusion, since the least common multiples involved are astronomically large. Later work pushed the same method further and pinned the value to about $0.2476$.

The convergence in the figure is fast, and that is also worth understanding. A number’s abundancy is decided mostly by its small prime factors — the factor $(1 + 1/p + 1/p^2 + \cdots)$ from a large prime is barely above one — so whether $n$ is abundant is almost determined by $n$ modulo a product of small primes. A range of a few thousand already contains many full periods of the patterns that matter, and the share settles long before the rare large-primed exceptions have been sampled properly.

Counting multiples when no period fits in a computer #

The existence proof suggests an algorithm, and running it exposes a difficulty the proof never has to face.

The density of the multiples of a finite list is exact and rational. For two generators it is a three-term inclusion–exclusion; for the 1,734 primitive abundant numbers below a million it is a sum over every subset of them, weighted by the reciprocal of the subset’s least common multiple — $2^{1734}$ terms, most of them attached to least common multiples far larger than anything a computer can hold. The period of the set is the least common multiple of all the generators at once, a number with thousands of digits. The quantity is finite, exact and uncomputable by the obvious method.

The way through is to stop treating the generators as arbitrary. Every abundant number has a small part — its factors below some cut-off — that nearly decides its abundancy, and a large part made of primes above the cut-off that nudges it by a factor close to one. So the density can be computed by running over the possible small parts, which are finite in number for a given cut-off, and for each one asking what share of the large parts push it over two. That second question is about numbers with no small prime factors, and it is answered by the kind of estimate the sieve written as a product supplies, with a rigorous error term rather than a heuristic one.

Rigorous bounds come from computations organised along these lines, with the errors from both halves controlled, and the width of the 1998 band — six parts in ten thousand — reflects how far the cut-off could be pushed. Narrowing it means raising the cut-off, which multiplies the number of small parts to consider, which is why each additional decimal place of the abundant density costs far more than the one before.

There is a moral in that for densities generally. A density defined by a limit can exist, be proved to exist, and be approximable from both sides with certified error, and still resist every attempt to write it down. The prime counting function is the standing example of a quantity that is easy to define and has no formula; the abundant density is a constant of the same kind, one level simpler, and it is known to four places.

The odd ones #

Every abundant number in the first figure that lies far above the line is even, and the reason is arithmetic. The abundancy of $n$ is at most the product of $p/(p-1)$ over the primes dividing it, and for the prime 2 that factor is 2 on its own. An odd number has to reach two using only odd primes, whose factors are $3/2$, $5/4$, $7/6$, $11/10$ and so on, each smaller than the last.

The first three odd primes give $\tfrac32 \cdot \tfrac54 \cdot \tfrac76 = 2.1875$, which is above two only in the limit of infinitely high powers. Raising 3 to the cube gets close enough: $945 = 3^3 \cdot 5 \cdot 7$ has abundancy $\tfrac{40}{27}\cdot\tfrac65\cdot\tfrac87 = 2.032$, and it is the smallest odd abundant number. Every one of the seven in the figure is 315 times something, and 315 is $3^2 \cdot 5 \cdot 7$.

The density of the odd abundant numbers is about $0.002$ — roughly one odd number in two hundred and fifty. That is small but positive, and it is where the odd perfect number would have to live if it existed: an odd number sitting exactly on the line, among a population where reaching the line at all takes a factorisation rich in small odd primes. The constraint list for an odd perfect number is a precise version of that observation.

The same count explains why odd aliquot sequences almost always fall. An odd sequence stays among odd numbers, where overshooting happens about once in two hundred and fifty steps; an even sequence stays among even numbers, where it happens about half the time.

The whole distribution #

Two is a threshold chosen for its meaning, and the distribution function answers the same question for every threshold at once.

Three features of this curve are theorems, and one is an artefact.

It is continuous. No single value of the abundancy is taken by a positive share of all numbers — not even two, which is why the perfect numbers have density nought. Davenport’s proof of this is the deep part of his theorem.

It is positive at every threshold. The abundancy of the product of the first $k$ primes is $\prod (1 + 1/p)$, and since the sum of the reciprocals of the primes diverges, that product grows without bound. So every threshold is exceeded by some number, and then by all of its multiples, which have positive density.

It falls extremely fast. Reaching abundancy $t$ requires a factor from essentially every prime up to about $e^{t e^{-\gamma}}$, since by Mertens’ theorem the product of $p/(p-1)$ over primes up to $y$ grows only like $e^{\gamma}\log y$. So the share above $t$ decays like a double exponential in $t$. The drop from $0.2475$ at two to $0.0202$ at three to $0.00023$ at four is the beginning of that collapse.

The artefact is the cliff near one. In the limit the curve is continuous there too, and the share of numbers with abundancy below $1 + \varepsilon$ tends to nought as $\varepsilon$ does. But the numbers responsible are those with no prime factor below about $1/\varepsilon$, and their share decays only like $1/\log$ of that — so at any computable range a fifth of all numbers are still crowded just above one, and the curve looks as if it jumps.

What a million numbers cannot show #

Every figure here is computed up to a thousand, five thousand or a million, and every theorem quoted is about the limit. The density figure settles quickly and happens to agree with the limit to three decimal places; the primitive reciprocal sum does not settle at all in the same range; the distribution’s cliff near one is a feature of the range rather than of the limit. The three together are a lesson in how differently finite computation tracks limiting statements that are all true.

The grid of primitive abundant numbers shows the inheritance argument for three hundred numbers, and inheritance is a statement about all multiples. The picture checks it on the range and proves nothing beyond it; the one-line inequality does.

And no picture shows Besicovitch’s counterexample, because a set of multiples with no density looks, over any finite range, like a set of multiples with one. The failure is in the limit and nowhere else. That is precisely why the existence of the abundant density needed a proof, and why the computation alone could never have supplied one.

Still open: what the number is #

The density of the abundant numbers is known to about four decimal places and nothing is known about its nature. Nobody knows whether it is rational, whether it has a closed form in terms of known constants, or whether it is related to anything outside the arithmetic of divisor sums. The digits come from an algorithm whose cost grows steeply with each additional digit, because every digit needs the primitive abundant numbers up to a larger bound and the exact density of a much larger set of multiples.

The same is true of the value of the distribution function at any other threshold, and of the density of the odd abundant numbers. These are among the simplest constants arithmetic defines — the probability that a number’s divisors outweigh it — and they are known only as outputs of long computations, in the same condition as the constants the prime sieve produces when its heuristic is pushed past what it can prove.

Passed down from a sparse few #

The abundant numbers look, on a list, like a quarter of the integers picked more or less at random. Structurally they are something quite different: the descendants of a thin set of ancestors — the perfect numbers and the primitive abundant ones — spread across the integers by multiplication. That one fact is what makes their proportion exist, and it is also what makes the proportion computable at all.

It connects the two extremes of this subject. The perfect numbers are the rarest objects the divisor sum defines, with density nought and perhaps finitely many of them. Every proper multiple of every one of them is abundant. So the rarest objects in the subject are among the ancestors of one of its commonest, and a question about a quarter of all numbers begins with the six, twenty-eight and four hundred and ninety-six that sit exactly on the line.