Every third coefficient

The twelfth row of Pascal’s triangle is 1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1, and its entries add to $2^{12} = 4096$. Take every third entry, starting from the first: $1 + 220 + 924 + 220 + 1 = 1366$. The entries one place along add to $12 + 495 + 792 + 66 = 1365$, and the entries two places along to $66 + 792 + 495 + 12 = 1365$.

Three sums, each within one of a third of 4096, and the first class is the one that gets the extra unit. Nothing in the row suggests either fact. Both are forced, and the forcing happens in the complex plane, at the three cube roots of one.

Making the unwanted terms cancel #

A polynomial $p(x) = a_0 + a_1 x + a_2 x^2 + \dots$ holds its coefficients in a form that is easy to add all at once: $p(1)$ is their total. Adding only some of them needs a value of $x$ that treats different positions differently, and the cube roots of one are the cheapest such values.

Let $\omega$ be the root a third of a turn round the circle, so that $\omega^3 = 1$ and the three roots add to nothing: $1 + \omega + \omega^2 = 0$. Evaluate $p$ at $\omega$ and each power of $x$ becomes a power of $\omega$, which depends only on the remainder of the exponent: $x^3$, $x^6$ and $x^9$ all become 1, while $x^4$ and $x^7$ both become $\omega$.

Now add the three values $p(1) + p(\omega) + p(\omega^2)$. A coefficient whose position is a multiple of 3 is multiplied by 1 each time, so it appears three times. A coefficient at a position $3j + 1$ is multiplied in turn by $1$, $\omega$ and $\omega^2$, which add to nothing, so it disappears. One at a position $3j + 2$ is multiplied by $1$, $\omega^2$ and $\omega^4 = \omega$, and disappears too. What is left is

$$a_0 + a_3 + a_6 + \dots = \tfrac13\bigl(p(1) + p(\omega) + p(\omega^2)\bigr).$$

The other two classes need one adjustment. To keep the positions $3j + 1$ instead, turn each value back before adding it — multiply $p(\omega)$ by $\omega^{-1}$ and $p(\omega^2)$ by $\omega^{-2}$ — so that the wanted coefficients are brought round to 1 and the rest are left spread evenly round the circle, cancelling.

The recipe works with any number $m$ in place of 3. Average $\zeta^{-jr}\,p(\zeta^j)$ over the $m$-th roots of one, and exactly the coefficients at positions leaving remainder $r$ survive. It is usually called the roots-of-unity filter, and it is nothing more than the vanishing sum doing a job.

Two arrows of length one #

For a row of Pascal’s triangle the polynomial is $(1 + x)^n$, and evaluating it at the three cube roots needs only three numbers: $1 + 1 = 2$, $1 + \omega$ and $1 + \omega^2$. Those are the three arrows in the figure.

The first is plain, and for row 12 it contributes $2^{12} = 4096$. The second is where the answer is decided. The root $\omega$ is $-\tfrac12 + \tfrac{\sqrt3}{2}i$, so $1 + \omega = \tfrac12 + \tfrac{\sqrt3}{2}i$, a number of length exactly one sitting a sixth of a turn round from 1. Multiplying by it is a pure turn of sixty degrees with no stretch, so its twelfth power is twelve sixths of a turn, which is two whole turns: $(1 + \omega)^{12} = 1$. The third arrow is the reflection of the second, and its twelfth power is also 1.

So $p(1) + p(\omega) + p(\omega^2) = 4096 + 1 + 1 = 4098$, and a third of that is 1366. For the class one place along, the two small values are turned back by $\omega^{-1}$ and $\omega^{-2}$ before they are added, which makes them $\omega^2$ and $\omega$; those add to $-1$, and the total is $(4096 - 1)/3 = 1365$. The third class comes out the same.

The long arrow supplies the third and the two short arrows supply the rounding. That is why every total sits so close to $2^n/3$. The correction terms are powers of numbers on the unit circle, so however large $n$ becomes they never grow. Written out for any row, the total of the class $r$ is

$$\frac{2^n + 2\cos\bigl((n - 2r)\pi/3\bigr)}{3},$$

and a cosine lies between $-1$ and $1$, so no class is ever more than two-thirds of a unit away from an exact third.

A pattern of six rows #

The cosine formula predicts a short cycle and the table shows it. The gap between three times a class total and $2^n$ is $2\cos((n - 2r)\pi/3)$, which takes the values $2$, $1$, $-1$, $-2$, $-1$ and $1$ as $n$ runs through six consecutive rows. At row 0 the first class holds the single entry 1 and the others hold nothing, so the gaps are $+2$, $-1$ and $-1$. At row 12 they are $+2$, $-1$ and $-1$ again, which is where 1366, 1365 and 1365 came from.

The period is six because $1 + \omega$ is itself a root of unity — a sixth root, since it lies a sixth of a turn round the circle. Its powers run round a hexagon and return to their start every six steps, and they carry the correction terms with them. That is a small coincidence worth pausing on. The cube roots of one were brought in to pick out every third coefficient, and the number that decides the rounding turns out to be a sixth root of one that nobody chose.

Two consequences can be read straight off the table. The three classes never differ from one another by more than one, so the entries of any row taken by position three apart carry almost exactly a third of its total. And which class gets the extra unit depends only on the row’s remainder on division by six, so row 18 behaves like row 12, row 6 and row 0.

None of this is visible in the recurrence that builds the triangle, which adds neighbouring entries and knows nothing about positions three apart. The regularity lives in a different description of the row — its values at three points of the circle — and it is invisible from inside the one everybody draws.

When the other arrows are longer #

The same recipe with $m = 4$ uses the four fourth roots of one, $1$, $i$, $-1$ and $-i$, and needs the values $1 + 1 = 2$, then $1 + i$, then $1 + (-1) = 0$, then $1 - i$.

One arrow has vanished and two have grown. The vanished one is harmless: it contributes nothing to any class in any row after the first. The two that have grown are the problem. The number $1 + i$ has length $\sqrt2$, so its tenth power has length $2^5 = 32$, and at that size it is no longer a rounding. For row 10 the class of positions $4j + 1$ comes out at $(1024 + 64)/4 = 272$ and the class of positions $4j + 3$ at $(1024 - 64)/4 = 240$, while the other two sit exactly on $1024/4 = 256$.

The imbalance grows without limit, and yet as a share of the row it still disappears. The gaps grow like $\sqrt2^{\,n}$ while the row’s total grows like $2^n$, so the four classes approach a quarter each at the rate $(\sqrt2/2)^n$, about 0.707 per row.

In general the arrows for the $m$-th roots are the numbers $1 + \zeta^j$, of length $2|\cos(j\pi/m)|$, and the longest after the first belongs to $j = 1$, with length $2\cos(\pi/m)$. So the classes of a row even out at the rate $\cos(\pi/m)^n$: in a single step when $m = 3$, where that rate is exactly a half and the gaps never grow at all; slowly for $m = 12$, where it is 0.966 per row. How evenly Pascal’s triangle shares itself among remainders is decided by a single cosine.

The same rate, reached by a walk #

That rate has been met before, somewhere that looks nothing like Pascal’s triangle.

Divide a row by $2^n$ and it becomes the distribution of the number of heads in $n$ tosses of a fair coin. Its class totals mod $m$ are then the chances that the number of heads leaves each remainder on division by $m$. And the remainder of the number of heads is a walk round a ring of $m$ positions, in which each toss either stays put or moves one place on, each with probability one half. How evenly the classes are filled after $n$ tosses is therefore the question of how long a chain takes to forget where it started.

That essay’s answer is that the distance to the settled state shrinks at a rate set by the second-largest eigenvalue of the chain. For a walk round a ring the eigenvalues can be written down, because a step is an average of staying and moving, and moving is a rotation. They are the numbers $(1 + \zeta^j)/2$ — the arrows in the figures, halved. The largest is 1, from $\zeta^0$, and the next in length is $\cos(\pi/m)$.

The rounding in Pascal’s triangle and the mixing rate of a walk on a ring are the same number, found from two different ends. The walk on a ring of three halves its distance from even with every toss. The walk on a ring of twelve takes about twenty tosses to halve it, since $0.966$ multiplied by itself twenty times is about a half.

Nothing about coins went into the first calculation, and nothing about binomial coefficients into the second. The meeting point is the arrows. They are the characters of the rotation group — the functions that turn a step round the ring into a turn of the circle — and, as Fourier’s coefficients do for a periodic curve, they split both problems into independent pieces at once.

Dice that divide evenly #

The filter needs only a polynomial, and any counting problem that combines independent choices supplies one. A single die is $x + x^2 + x^3 + x^4 + x^5 + x^6$, with the exponent recording the number rolled, and $k$ dice are its $k$-th power, because multiplying polynomials adds exponents and pairs every roll of one die with every roll of the others.

The number of throws whose total is divisible by $m$ is the average of the die’s $k$-th power over the $m$-th roots. At the root 1 the die is worth 6, which gives the expected share $6^k/m$. At every other root it is worth $\zeta + \zeta^2 + \dots + \zeta^6$, and whether that sum is zero decides everything.

For a cube root the six powers go twice round a triangle and add to nothing, so every correction vanishes and the total of any number of dice is divisible by 3 exactly a third of the time — not approximately, and not only in the limit. The same holds for 2 and for 6, whose roots also close up in six steps.

For a fourth root the six powers run once and a half round a square and stop at $i - 1$, of length $\sqrt2$, so the share is wrong and the error grows with the number of dice, as it did mod 4 in the triangle. For a fifth root the six powers wrap round a pentagon and one step beyond, and add to $\zeta$ itself, of length one. For a seventh root they add to $-1$. Those errors stay bounded, and the filter turns them into exact formulas with a small correction: the number of throws of $k$ dice whose total is divisible by 7 is $(6^k + 6(-1)^k)/7$, which is 30 for three dice and 186 for four.

Subsets, and a count that belongs to necklaces #

The last use is the strangest, because the answer it produces already has a name somewhere else.

Take the numbers $1, 2, \dots, m$ and ask how many of the $2^m$ subsets have a total divisible by $m$. The polynomial is $(1 + x)(1 + x^2)\cdots(1 + x^m)$, each factor either leaving its number out or putting it in, and the filter averages it over the $m$-th roots.

At a root $\zeta^j$ of order $d$, the powers $\zeta^j, \zeta^{2j}, \dots, \zeta^{mj}$ run $m/d$ times through all $d$ of the $d$-th roots of one. The product of $1 + \eta$ over those $d$ roots $\eta$ comes from setting $x = -1$ in $x^d - 1 = \prod (x - \eta)$, and it is 2 when $d$ is odd and 0 when $d$ is even. So a root of even order contributes nothing to the average, and a root of odd order $d$ contributes $2^{m/d}$.

The count is therefore $\frac1m\sum \varphi(d)\,2^{m/d}$, taken over the odd divisors $d$ of $m$, where $\varphi(d)$ counts the roots of order exactly $d$. Taken over all the divisors, the same sum is the number of necklaces of $m$ beads in two colours counted up to rotation — the count that proves Fermat’s little theorem. The two agree precisely when $m$ has no even divisors, which is when $m$ is odd.

The coincidence has a reason. Counting necklaces means averaging over the $m$ rotations of a ring, and a rotation of order $d$ leaves exactly $2^{m/d}$ colourings unchanged. Averaging over the $m$-th roots of one is averaging over the same rotations, written as numbers, and the subset problem simply gives every rotation of even order a weight of nothing. At a prime $m = p$ both counts are $(2^p + 2(p - 1))/p$, which at $p = 7$ is twenty.

What the average cannot see #

The filter is exact and it is narrow, and both halves are worth stating.

It sorts by position and by nothing else. It picks out the coefficients whose index leaves a given remainder, which is a question about the exponent of $x$. Asking which binomial coefficients are themselves divisible by 3 is a question about their values, and it has a different answer, read off the digits of $n$ in base 3.

The values at the roots are complex numbers, and the answers are whole numbers. The figures evaluate $(1 + \zeta)^n$ and the dice and subset products as pairs of floating-point numbers and require the average to land within a millionth of the whole-number total found by adding. At row 16 the largest value involved is 65536 and the arithmetic has digits to spare; at row 60 it would not, and the computation would need exact arithmetic with the roots themselves. The whole-number totals are never in doubt, because they come from adding, but the route through the roots is a numerical agreement at the sizes drawn and a theorem everywhere else.

The pictures stop at small rows and small moduli. Rows are drawn to thirteen and moduli to seven. A table of fourteen rows shows two cycles of a pattern of six and cannot show that the pattern never breaks; the cosine formula shows that, and so does the fact that $1 + \omega$ is a root of one, which no table can display.

The question it leaves: which points on the circle come home #

Every calculation above rested on points of the unit circle whose powers return: $\omega$ after three steps, $1 + \omega$ after six, $i$ after four. The rounding stayed bounded mod 3 because the short arrows were such points, and grew mod 4 because the short arrows had left the circle altogether.

That invites a converse. A point lying exactly on the unit circle has powers that never grow and never shrink, just as $1 + \omega$ does. Does lying on the circle make it a root of one? If it did, a bounded correction and a periodic one would be the same thing. They are not, and the point $(3 + 4i)/5$ — on the circle, and a turn by an angle that is no fraction of a whole turn — is where the difference first shows. What separates the two kinds of point is a condition on the numbers they are tied to by their polynomials, and it is Kronecker’s.

There is also an older direction: which sums of roots of one vanish. The filter used the simplest vanishing sum there is, all $m$ roots taken together, and there are others — the three cube roots sit among the sixth roots and add to nothing on their own. How many terms a vanishing sum of $m$-th roots can have, counting repetitions, was settled only in 2000 by Lam and Leung: exactly the numbers that can be written as sums of primes dividing $m$.

Evaluating where the terms cancel #

A polynomial’s coefficients can be pulled apart without computing them one at a time, by evaluating the polynomial at points chosen so that the unwanted ones cancel. The roots of one are the points that do this for classes of exponents, because their powers depend only on a remainder and their sums vanish.

What makes the method more than a trick is what is left over once the cancelling is done. For the triangle it is powers of $1 + \zeta$; for dice, powers of $\zeta + \dots + \zeta^6$; for subsets, products of $1 + \zeta^k$. In every case the length of the leftover is the whole story. A leftover of zero gives an exact share, a leftover of length one gives a bounded error, and a leftover longer than one gives an error that grows and still vanishes as a fraction of the whole.

When a count is shared almost evenly, find the points at which the sharing is decided and measure how long the leftovers are there. The size of the unevenness, and the rate at which it disappears, are both lengths in the complex plane.