Archive

Posts Tagged ‘Partition theory’

A lost bijection

July 11, 2012 1 comment

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.

Britannica, Wikipedia and Combinatorics

March 16, 2012 Leave a comment

All right, as we just learned, Britannica is done publishing.  Wikipedia won.  It wasn’t much of a contest, really.  We all expected this a long time ago.  Even if WP wasn’t as big as it is now (English language WP has about 4 mil pages), looking up there is noticeably faster than figuring out which volume of Britannica has your information.  So should we celebrate or commiserate?  I think neither, but we should instead turn this crisis into an opportunity.

First, how to think of the Britannica?  I say, as a series of historical documents, written by some of the best writers and scientists.  The case in point: Combinatorics article, which exists both in WP and in Britannica (the webpage has a free access this month).  Let’s review:

1) The Britannica Combinatorics article is overly long and incomplete at the same time, somewhat biased, very out of date, and barely coherent.  Lots of little examples are mentioned (multinomial coefficients, PBIB, etc.) and a few big things (graph theory, Ramsey theory, combinatorical geometry).  Nothing remotely recent (like algebraic combinatorics), most references from the 1960s and a couple of 1980s textbooks which are “accessible to laymen” (a lovely turn of phrase).  Sort of reminds me of this bridge – nice, useful in the past, but ultimately useless nowdays.

2) The Wikipedia Combinatorics article was in a horrible shape only about 3 years ago.  As a big WP fan, I was upset over this, and over the 1998 winter break largely rewrote the page myself.  The current version is still about 95% the same as I made it.  Rather than give silly examples and historical discussions, I simply made it into a portal with wikilinks to relevant subfields and few sentences describing each.  I thought I would get back to the article and write some more, but never did.  Sorry!

So, what gives?  Neither version is really a winner.  The Britannica article is outdated.  The WP article by itself has very little information.  The real difference can be seen only by going along the links – the total scope and quality of WP articles in combinatorics is noticeably better.  Still, some areas have WP pages which are not well written and/or have little information.  In summary, neither article gives a picture of the field.  If I were to choose a well written and accessible Combinatorics encyclopedia article, I would suggest Enumerative and Algebraic Combinatorics by Zeilberger, Extremal and Probabilistic Combinatorics by Alon and Krivelevich, and other articles from The Princeton Companion in Mathematics (Ed. by Tim Gowers).   

On the other hand, if viewed as a historical document Britannica article has a number of hidden treasures.  Written (at least in part) by Grünbaum (I am guessing in the 1960s), it correctly predicts the future growth of the extremal cominatorics and discrete geometry.  It is off base when it come to some other areas, like Polya’s theory which is rarely taught now and viewed as old fashioned.  Still, the page gives a window into the 1960 (or 1980?) thinking of what combinatorics is about.  In fact, even the name of the article was different – until recently it was “Combinatorial Analysis”.

My favorite “hidden gem” is the section on Partition Theory.  Check out theorem (F1) there, which has both the statement and the proof (!).  This is common for WP (see e.g. this page), but rather unique for the Britannica.  It so happens, this section was originally written by Percy MacMahon in the 1911 Britannica (which is out of copyright now).  His version was up to date and beautifully written, later corrupted and shortened but never completely disappeared.  In fact, compared to 1911, new mistakes were introduced, e.g. an unpleasant typo in the section title “The Ferrer diagram” which I noticed in the 1960 edition managed to survive all these decades (they are named after Norman Ferrers).

Finally, my modest suggestion.  Treat the Britannica as a historical treasure that is up for sale (not unlike this one, sold in 1998).  After all, it dates back to 1768, three times older than this “Historic Cultural Monument” in my neighborhood.  The Britannica currently sells its digital version, but I bet this line of income will also dry up.  We (the people) should simply buy the whole thing and make it free and publicly available on the web.  Make sure to have available on the web all editions, not just the latest one.  This would give an instant window of how the same subject was treated over time.  Perhaps UNESCO?  Google?  Microsoft?  (it’s better than your Encarta, really!)  Amazon?  NSF?  Anyone with money?  I bet it’s cheap…

P.S.  A side comment – I want to praise Harald Helfgott’s recent serious effort to overhaul the Number Theory WP article.