Binomial Coefficient Coincidences

In 1997, De Weger conjectured that every equation between binomial coefficients follows from the four known systematic equations and the seven coincidences I showed you:

• Benjamin M. M. de Weger, Equal binomial coefficients: some elementary considerations, Journal of Number Theory 63, no. 2 (1997), 373–386.

At that time, he and his collaborators checked there were no others involving binomial coefficients less than 10³⁰. Later they checked that there are none involving binomial coefficients less than 10⁶⁰:

• Aart Blokhuis, Andries Brouwer and Benne de Weger, Binomial collisions and near collisions.

So, De Weger’s conjecture stands open. The four infinite families, by the way, are these:

and the only nontrivial one: the Lind–Singmaster family involving the Fibonacci numbers where :

The first three equations in the Lind–Singmaster family are these:

When I said De Weger conjectured every equation between binomial coefficients follows from the four known systematic equations and the seven coincidences, I really meant it. For example, the first of the Lind-Singmaster equations combines with the coincidence

and other systematic equations to give

In fact, if de Weger’s conjecture is true, the number 3003 shows up as a binomial coefficient in more ways than any other positive integer!

I’ll explain the Lind–Singmaster family later. Here’s the question I’m most interested in now:

Is there any good explanation for the seven binomial coefficient coincidences?

My collaborator Paul Schwahn found a beautiful explanation of the first one, namely

His explanation uses representation theory. The Lie algebra has a 10-dimensional representation, the ‘vector’ representation , and also two 16-dimensional representations, the ‘left and right-handed spinor’ representations There’s an isomorphism of representations

and similarly for but we might as well work with Here means the kth exterior power. For any vector space we have

Thus, taking dimensions, the isomorphism of representations

instantly gives

It is not super-easy to prove this isomorphism of representations, but it’s still nice to find a deeper layer of meaning underlying what might otherwise seem like a meaningless coincidence!

Can we find good explanations for the other six coincidences?

First let me explain two failed attempts using representation theory, and then three successes using combinatorics.

Representation theory

First: we can look for isomorphisms like

involving representations of for larger In fact this isomorphism is part of a pattern! The next one involves the vector and left-handed spinor representations of But it’s this:

so it gives

or

So we fail to get an equation between binomial coefficients, but we’re close: we’re only off by one.

The second paper I cited, Binomial collisions and near collisions, presents a list of cases where two binomial coefficients differ by one. This is on the list. So we failed to explain an equation between binomial coefficients, but we explained a near-miss.

Here’s another failed attempt at explaining an equation between binomial coefficients. The equation

is fascinating to anyone who knows their exceptional Lie groups. 78 is the dimension of while 14 is the dimension of is a subgroup of because is the automorphism group of the octonions and is the isometry group of the bioctonionic plane. We’d get the above equation if the 2nd exterior power of the adjoint representation of upon being restricted to were isomorphic to the 6th exterior power of the adjoint representation of

Amazingly, it seems these two representations of are not isomorphic even though their dimensions are the same: both 3003.

Even more amazingly, and both have irreducible representations of dimension 3003, but they are not the representations I just mentioned.

I would be happy for someone to check these two claims.

Combinatorics

It turns out that the following three coincidences can all be explained by the same style of combinatorial argument:

The argument is not very elegant, but it’s moderately interesting. Mike Stay got it started by asking ChatGPT, and I finished it off.

In each case the argument has three steps. The first two steps are what combinatorialists call bijective proofs: we prove an equation between numbers by proving a natural isomorphism between structures on sets and then taking cardinalities. The third step is non-bijective because it involves taking an equation and dividing both sides by the same number. Maybe we can make it closer to bijective by using groupoid cardinality, which allows for division, but I haven’t tried that.

Step 1: pairs of edges in a complete graph

Starting from the left-hand binomial coefficient in each equation we’re trying to prove, note that the number on top is a triangular number:

Note that counts unordered pairs of distinct edges in the complete graph on vertices. Two distinct edges either share a vertex or are disjoint, so there are two cases:

• Sharing a vertex: the pair spans 3 vertices and is determined by this 3-element set together with a choice of which vertex is shared. That gives pairs.

• Disjoint: the pair spans 4 vertices and is determined by this 4-element set together with one of its 3 splittings into two pairs. That gives pairs.

By Pascal’s rule, But this also has a bijective proof: add a new point to the set of vertices, and a 4-element subset of the enlarged set either contains the new point (so involves a 3-element subset of the old ones) or does not (so involves a 4-element subset of the old ones). Hence we have a bijective proof that

This holds for all For our three cases we get bijective proofs of the following equations:

It thus remains to prove

Step 2: a double count

Each of the above equations follows by counting a single set in two ways, and then a nonbijective step: dividing these counts by the same number.

• Showing . In a 10-element set, count triples in two different ways, where is a 4-element subset and are distinct points outside . Choosing first we see there are triples. Choosing and first we see there are triples. So, we get a bijective proof that You can see what we’ll do next.

• Showing In a 19-element set, count pairs with and . On the one hand, there are choices of and for each there are 15 choices of since we can add an extra point in 15 ways. On the other hand, there are choices of and for each there are 5 choices of since we can choose in ways. So we get a bijective proof that Again, you can see what we’ll do next!

• Showing In a 14-element set, count pairs with and . On the one hand, there are choices of and for each there are 45 choices of since we can add 2 other points in ways. On the other hand there are choices of and for each there are 15 choices of since we can choose 4 points in ways. This gives a bijective proof that Again you can see what we’ll do next.

Step 3: division

Having proved

we can now divide by 30, 5 and 15, respectively, and get

as we wanted, completing our proof that

I don’t see how to use tricks of the same general sort to explain the remaining coincidences

The Lind–Singmaster family

Lind and Singmaster were trying to find all with

I’ll rapidly sketch the key steps of their argument. Simplifying the equation above we get

or

Solve for using the quadratic formula. This formula turns out to have

in it. So we need to be a perfect square!

Now we’re trying to find integer solutions of

A quadratic diophantine equation! Multiply by 5 and complete the square:

is an integer when is, so we need to find integer solutions of

This is a ‘Pell equation’, and people know how to solve these. In this particular case we get all the solutions from this fact:

where are the Fibonacci numbers 0, 1, 1, 2, 3, … and are the Lucas numbers 2, 1, 3, 4, 7, …. These are two sequences satisfying the same famous recurrence relation, just with different initial conditions.

We want odd, to get

It turns out with odd give all solutions of the Pell equation

However, remember I said is an integer when is. But the converse isn’t always true, and we need to be an integer! This clearly happens iff

So we need to know when Apparently this happens iff I won’t think about this now… but this is the last hard step.

In summary, we’ve seen

if and only if is a Lucas number with We could quit here, but people like to use the identity

to get a formula for in terms of Fibonacci numbers. This is gilding the lily, I’d say, but it eventually leads to the formula that de Weger presents:

The takeaway message is: our problem can easily be reduced to a quadratic diophantine equation, then put in Pell form… and it’s known that the sequence of integer solutions of a Pell equation obeys a linear recurrence relation! We luck out in this case and get solutions connected to Lucas and Fibonacci numbers.

It’s probably a lot easier to show that the Lind–Singmaster equations hold. The above argument does a lot more, by showing that every equation of the form

is in the Lind–Singmaster family. De Weger gets into a lot more number theory trying to rule out various other kinds of coincidences between binomial coefficients. It’s downright scary how these questions pull you into the deep, icy waters of mathematics.