The shape of a number's divisors

A number’s divisors are usually met as a list: the divisors of sixty are one, two, three, four, five, six, ten, twelve, fifteen, twenty, thirty and sixty. A list is the least informative arrangement available, because the order it is written in — increasing — has nothing to do with how the divisors are related.

Every divisor of $60 = 2^2 \times 3 \times 5$ is $2^i 3^j 5^k$ with $i \le 2$, $j \le 1$, $k \le 1$, and nothing else is. So the divisors are the whole-number points of a box: three choices along one axis, two along each of the others.

Two facts fall straight out of the shape, and both of them are usually taught as formulas to be memorised.

The count is the box #

How many divisors does $60$ have? However many points are in a $3 \times 2 \times 2$ box, which is twelve. In general, for $n = p_1^{e_1} \cdots p_k^{e_k}$,

$$d(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1).$$

The $+1$ is the choice of taking none of that prime, and the multiplication is the independence of the choices.

The formula depends entirely on the fundamental theorem. If a number had two different factorisations, “the exponent of $p$ in $n$” would not name anything, the box would have no dimensions, and the count would be meaningless. Unique factorisation is what makes the coordinates well defined, and the lattice is the theorem drawn.

It also explains why the divisor count is so irregular. Highly composite numbers — $12$, $60$, $360$, $2520$ — are the ones whose exponents are arranged to make the box large for the number’s size, which means many small primes with modest exponents. A large prime contributes only a factor of two to the count while multiplying the number by itself. So the numbers with many divisors are the ones built from the smallest primes available, and Ramanujan’s study of them in 1915 is essentially an optimisation over the shape of this box.

The sum factorises because the rectangle does #

Adding the divisors up looks like a harder question and is the same one.

Row $j$ of the rectangle holds $3^j \times (1 + 2 + 4 + 8)$, so it totals $15 \times 3^j$. Adding the rows gives $15 \times (1 + 3 + 9) = 15 \times 13 = 195$, and $195$ is the sum of all twelve divisors of $72$.

Nothing was rearranged: the rectangle was added by rows instead of cell by cell, and rows factor because the rectangle is a product. In general

$$\sigma(n) = \prod_i \left(1 + p_i + p_i^2 + \cdots + p_i^{e_i}\right) = \prod_i \frac{p_i^{e_i + 1} - 1}{p_i - 1},$$

each bracket a finite geometric series, and the whole thing a distributed product.

This is counting one collection two ways in its purest form. The cells are the same cells; adding them one at a time gives a number with no structure, and adding them by rows gives the number written as a product. The identity is not proved so much as observed from a second reading of the same picture.

Multiplicative, and what that word is doing #

A function $f$ on the whole numbers is multiplicative if $f(mn) = f(m)f(n)$ whenever $m$ and $n$ are coprime. Both $d$ and $\sigma$ are, and the lattice says why in one sentence: if $m$ and $n$ share no prime, their axes are different axes, and the divisor lattice of $mn$ is the product of the two lattices.

The coprimality condition is not a technicality. $d(4) = 3$ and $d(2) = 2$, and $d(8) = 4$ rather than $6$, because multiplying two numbers that share a prime stretches an existing axis instead of adding a new one. The lattice makes the distinction visible: a new prime is a new dimension, a repeated prime is a longer edge, and only the first of those multiplies the count.

Multiplicativity is what makes such functions tractable. Knowing $f$ on prime powers determines it everywhere, so a question about all numbers becomes a question about $p^e$, which is one variable rather than infinitely many. Nearly every function in classical number theory is built this way — the divisor count, the divisor sum, Euler’s totient $\varphi$, the Möbius function — and each is defined on prime powers and extended by the product rule.

Euler’s totient is the one worth following, because its lattice reading is a subtraction rather than a count. $\varphi(n)$ counts the numbers below $n$ coprime to $n$: those sharing no prime with it. On the box, “shares a prime with $n$” means “lies on one of the coordinate hyperplanes”, so the coprime numbers are what is left when every hyperplane is removed — and inclusion–exclusion over the hyperplanes gives

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$

That product is the one the sieve’s density estimate is built from, arrived at here by a completely different route: there it was the fraction of numbers surviving a sequence of strikes, here it is the fraction of a box left after removing its faces. The two are the same calculation, and the shared appearance of $\prod(1 - 1/p)$ across half of this field is the reason so many results in it have a factor that looks like it belongs somewhere else.

Multiplicativity also has an unexpected consequence for the Farey sequences: their lengths are totient sums, so the number of fractions in lowest terms with denominator at most $n$ is governed by the same product, and grows like $3n^2/\pi^2$. The $\pi$ has no circle behind it. It comes from $\sum 1/k^2$, which is where the totient sum’s average leads, and it is the clearest sign that these counting functions are not really about individual numbers at all.

How the count behaves on average #

The divisor count jumps about violently — a prime has two divisors and the number next door may have twenty — so the useful question is what it does on average, and the answer comes from counting a region two ways.

Add $d(n)$ over all $n$ up to $x$. That total counts the pairs $(d, q)$ with $dq \le x$, since each divisor $d$ of each $n$ gives exactly one such pair. Those pairs are the lattice points under the hyperbola $dq = x$, and counting them by columns gives

$$\sum_{n \le x} d(n) = \sum_{d \le x} \left\lfloor \frac{x}{d} \right\rfloor \approx x \log x.$$

So the average number of divisors of a number near $x$ is about $\log x$ — which is small. A number near a million has, on average, about fourteen divisors.

The hyperbola trick is Dirichlet’s, and it is the same manoeuvre as the row-summing above at a larger scale: a two-dimensional region is being counted by slices rather than point by point, and the slices are easy while the points are not. Dirichlet went further and used symmetry about the line $d = q$ to improve the error term, which is why the sharp version reads $x \log x + (2\gamma - 1)x + O(\sqrt x)$. Improving that $\sqrt x$ is the divisor problem, it has been open since 1849, and the current record is an exponent of about $0.314$ against a conjectured $\tfrac14$.

That is a familiar shape by now. An exact statement about a lattice is available immediately; the error in the approximation is the hard part; and the hard part has been open for a century and a half.

The one place the picture stops #

The lattice is drawable for one, two or three distinct primes. A number with four is a four-dimensional box, and any drawing of it is a projection making claims a reader cannot check.

That is a real limitation rather than a presentational one. The numbers with many distinct prime factors are exactly the interesting ones for questions about divisor counts, and they are the ones outside the drawing. $2310 = 2 \times 3 \times 5 \times 7 \times 11$ has $32$ divisors sitting at the corners of a five-dimensional cube, and the fact that every divisor corresponds to a subset of the primes is clear from the algebra and invisible in any picture.

What the pictures do carry across is the reasoning, and that generalises where the drawing does not. A box in five dimensions is still a product of five independent choices, its point count is still a product, and adding its entries by hyperplanes still factorises the sum. The arguments in this essay are all one-dimensional arguments repeated, which is why they survive into dimensions no figure reaches.

What the divisors add up to #

The natural next question is which numbers have divisor sums worth remarking on, and the classical answer is a strange one.

A number is deficient if its proper divisors add to less than itself, abundant if more, and perfect if exactly. Perfection is rare — six, twenty-eight, four hundred and ninety-six, eight thousand one hundred and twenty-eight — and rare in a way that is still not understood, which is the subject of its own essay.

The lattice explains the general tendency, if not the exceptional cases. A number’s divisor sum relative to the number itself, $\sigma(n)/n$, equals $\prod (1 + 1/p + \cdots + 1/p^{e})$, which is bounded by $\prod (1 - 1/p)^{-1}$: it grows with the number of small primes and barely responds to large ones. So abundance is a property of being built from many small primes, and every multiple of six above six is abundant for exactly that reason.

The distribution of $\sigma(n)/n$ turns out to be well behaved in a way none of the individual values are. Davenport showed in 1933 that the proportion of numbers with $\sigma(n)/n$ below any given threshold exists as a limit — the ratio has a genuine distribution function, continuous and strictly increasing. The abundant numbers therefore have a density, and it is about $0.2476$: roughly one number in four has divisors adding to more than itself.

That a quantity this erratic has a smooth distribution is characteristic of the whole field. Individual values are unpredictable, statistics over them are not, and the bridge between the two is always multiplicativity — the ratio is a product over primes, the primes behave independently enough for the product to have a distribution, and the erratic behaviour averages out without ever becoming predictable.

Möbius, and reading the lattice backwards #

There is one more thing the box is good for, and it is the operation that inverts everything above.

Suppose a function $F$ is defined as the sum of $f$ over the divisors of $n$ — as $\sigma$ is the sum of the identity, and $d$ the sum of the constant one. Möbius inversion recovers $f$ from $F$:

$$f(n) = \sum_{d \mid n} \mu(d)\, F(n/d),$$

where $\mu(d)$ is zero if $d$ has a repeated prime factor, and otherwise $\pm 1$ according to the parity of the number of primes.

Drawn on the lattice, $\mu$ is a signed sum over the corners of the box with the interior thrown away, and the inversion is inclusion–exclusion: add over everything, subtract the over-counting on each face, add back the double-subtraction on each edge. The Möbius function is zero away from the corners precisely because inclusion–exclusion has nothing to say about a repeated prime.

This is the same alternating count that appears in the sieve’s density estimate, and it is the reason the two subjects share machinery: sieving is inclusion–exclusion over the primes dividing something, and Möbius inversion is inclusion–exclusion over the divisors of something. The lattice is where both of them live.

The lattice is an order, not just a picture #

The joins in the first figure are not decoration. Two divisors are connected when one divides the other by a single prime, and following the connections upward is the divisibility relation — so the drawing is a Hasse diagram of a partial order, and everything a partial order has, this one has.

It has a bottom element, $1$, and a top, $n$. Any two divisors have a greatest lower bound, their $\gcd$, and a least upper bound, their $\mathrm{lcm}$; on the lattice those are the componentwise minimum and maximum of the exponent vectors, which is why $\gcd(a,b) \times \mathrm{lcm}(a,b) = ab$ — the minimum and the maximum of two numbers add to their sum, coordinate by coordinate. That identity is usually proved by a page of case analysis and is one line of the picture.

The order structure also answers a question the list arrangement makes hard: how many chains run from $1$ to $n$? A chain multiplies one prime at a time, so it is an ordering of the multiset of prime factors, and there are $\frac{(e_1 + \cdots + e_k)!}{e_1! \cdots e_k!}$ of them — for $360$, with factors $2,2,2,3,3,5$, that is $60$. The divisor lattice of a number is the same object as the set of ways of arranging a word with repeated letters, which is not a resemblance anybody would predict from either description.

Where the ladder goes next #

The immediate continuation is the exceptional case the aliquot figure showed. Numbers that are the sum of their own parts takes the divisor sum as the object of study rather than as a tool, and gets a complete answer for even numbers and no answer at all for odd ones.

The other direction is a different kind of counting entirely. This essay counted the ways a number can be factored, arranging the results in a box. Counting the ways a number can be added up gives partitions, where the arrangement is a diagram of dots and turning it on its side proves things that no formula suggests. The two are the multiplicative and additive halves of the same question, and they behave nothing like each other.