Home > Mathematics, New papers > A lost bijection

A lost bijection

One can argue whether some proofs are from the book, while others maybe not. Some such proofs are short but non-elementary, others are elementary but slightly tedious, yet others are short but mysterious, etc. (see here for these examples). BTW, can one result have two or more “proofs from the book”?

However, very occasionally you come across a proof that is both short, elementary and completely straightforward. One would call such a proof trivial, if not for the fact that it’s brand new. I propose a new term for these – let’s call them lost proofs, loosely defined as proofs which should have been discovered decades or centuries ago, but evaded this fate for whatever accidental historical circumstances (as in lost world, get it?) And when you find such a proof you sort of can’t believe it. Really? This is true? This is new? Really? Really?!?

Let me describe one such lost proof. This story started in 1857 when Arthur Cayley wrote “On a problem in the partition of numbers”, with the following curious result:

The number of integer sequences (a_1,\ldots,a_n) such that 1\le a_1 \le 2, and 1\le a_{i+1} \le 2 a_i for 1\le i < n, is equal to the total number of partitions of integers N \in \{0,1,\ldots,2^{n}-1\} into parts 1,2,4,\ldots,2^{n-1}.

For example, for n=2 the first set is sequences is \{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4)\}, while the second of partitions is \{21, 2, 1^3, 1^2, 1, \varnothing\}, both with six elements.

This result was discovered about 20-25 years too soon. In 1879-1882, while at Johns Hopkins University, Sylvester pioneered what he called a “constructive partition theory”, and had he seen his good friend’s older paper, he probably would have thought about finding a bijective proof. Apparently, he didn’t. In all fairness to everybody involved, Cayley had written over 900 papers.

Now, the problem was rediscovered by Minc (1959), and notably by Andrews, Paule, Riese and Strehl (2001) as a biproduct of computer experiments. Both Cayley’s and APRS’s proofs are analytic (using generating functions). More recent investigations by Corteel, Lee and Savage (2005 and 2007 papers), and Beck, Braun and Le (2011) proved various extensions, still using generating functions.

We are now ready for the “lost proof”, which is really a lost bijection. It’s given by just one formula, due to Matjaž Konvalinka and me:

\Psi: (a_1,a_2,a_3,\ldots,a_n) \to [2^{n-1}]^{2-a_1} [2^{n-2}]^{2a_1-a_2}[2^{n-3}]^{2a_2-a_3} \ldots 1^{2a_{n-1}-a_n}

For example, for n=2 we get the following bijection:

\Psi: (1,1) \to 21, \ (1,2) \to 2, \ (2,1) \to 1^3, \ (2,2) \to 1^2, \ (2,3) \to 1, \ (2,4) \to \varnothing.

Of course, once the bijection is found, the proof of Cayley’s theorem is completely straightforward. Also, once you have such an affine formula, many extensions become trivial.

One wonders, how does one can come up with such a bijection. The answer is: simply compute it assuming there is an affine map. It tends to be unique. Also, we have done this before (for convex partitions and LR-coefficients). There is a reason why this bijection is so similar to Sylvie Corteel’s “brilliant human-generated one-line proof” in the words of Doron Zeilberger. So it’s just amazing that this simple proof has been “lost” for over 150 years, until now…

See our paper (Konvalinka and Pak, “Cayley compositions, partitions, polytopes, and geometric bijections”, 2012) for applications of this “lost bijection” and my survey (Pak, “Partition Bijections, a Survey”, 2006) for more on partition bijections.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: