What is Combinatorics?

Do you think you know the answer?  Do you think others have the same answer?  Imagine you could go back in time and ask this question to a number of top combinatorialists of the past 50 years.  What would they say?  Would you agree with them at all?

Turns out, these answers are readily available.  I collected them on this page of quotes.  The early ones are uncertain, defensive, almost apologetic.  The later ones are bolder, prouder of the field and its status.  All are enlightening.  Take your time, read them all in order.

Why bother?

During my recent MIT visit, Jacob Fox showed me this blog which I found to be rather derogatory in its treatment of combinatorics and notable combinatorialists.  This brought me back to my undergraduate days in Moscow, reminded of the long forgotten but back then very common view of combinatorics as “second rate mathematics”.  In the US, I always thought, this battle has been won before my time, back in the 1980s.  The good guys worked hard and paved the road for all younger combinatorialists to walk on, and be proud of the field.  But of course the internet has its own rules, and has room for every prejudice known to men.

While myself uninterested in engaging in conversation, I figured that there got to be some old “war-time” replies which I can show to the Owl blogger.  As I see it, only the lack of knowledge can explain these nearsighted generalizations the blogger is showing.  And in the age of Google Scholar, there really is no excuse for not knowing the history of the subject, and its traditional sensitivities.

But while compiling the list of quotes linked above, I learned a few things.  I learned how tumultuous was the history of combinatorics, with petty fights and random turns into blind alleys.  I learned how myopic were some of the people, and how clever and generous were others.  I also discovered that there is a good answer to the question in the title (see below), but that answer is not a definition.

What do authorities say?

Not a lot, actually.  The AMS MSC (which I love criticizing) lists Combinaorics as 05, on par with about 70 fields, such as Number Theory (11), Geometry (51), Probability (60) and Computer Science (68).  It is also on the same level as  Nonassociative rings (17), K-theory (19) and Integral equations (51), which are perfectly fine areas, just much smaller.  It is one of the 32 categories on the arXiv, but who knows how these came about.

At the level of NSF, it is one of the 11 Disciplinary Research Programs, no longer lumped with “Algebra and Number Theory” (which remain joined at the hip according to NSF).  Around the country, Combinatorics is fairly well represented at the top 100 universities, even if breaking “top 10″ barrier remains difficult.  Some are firmly in the “algebraic” camp, some in “probabilistic/extremal”, some have a lot of Graph Theory experts, but quite a few have a genuine mix.

This all reminded me of a story how I found out “What is mathematics“.  It started with me getting a Master of Arts degree from Harvard.  It arrived by mail, and made me unhappy.  I thought they made a mistake, that I should have been given Master of Sciences.  So I went to the registrar office, asked to see the director and explained the problem.  The director was an old lady, who listened carefully, and replied “let me check”.  She opened some kind of book, flipped a few pages and declared: “Yes, I see.  No mistake made.  Mathematics is an Art.”   Seeing my disappointed face, she decided to console me “Oh, don’t worry, dear, it’s always been that way at Harvard…”

What the experts are saying.

About the title question, I mean.  Let’s review the quotes page.  Turns out, a lot of things, often contradicting each other and sometimes themselves.  Some are cunning and ingenuous, while others are misleading or plain false. As the management maxim says, “where you stand depends on where you sit”.  Naturally, combinatorilists in different areas have a very different view on the question.

Few themes emerge.  First, that combinatorics is some kind of discrete universe which deals with discrete “configurations”, their existence and counting.  Where to begin?  This is “sort of” correct, but largely useless.  Should we count logic, rectifiable knots and finite fields in, and things like Borsuk conjecture and algebraic combinatorics out?  This is sort of like defining an elephant as a “large animal with a big trunk and big ears”.  This “descriptive” definition may work for Webster’s dictionary, but if you have never seen an elephant, you really don’t know how big should be the ears, and have a completely wrong idea about what is a trunk.  And if you have seen an elephant, this definition asks you to reject a baby elephant whose trunk and ears are smaller.  Not good.

Second theme: combinatorics is defined by its tools and methods, or lack of thereof.  This is more of a wishful thinking than a working definition.  It is true that practitioners in different parts of combinatorics place a great value on developing new extensions and variations of the available tools, as well as ingenuous ad hoc arguments.  But a general attitude, it seems, is basically “when it comes to problem solving, one can use whatever works”.  For example, our recent paper proves unimodality results for the classical Gaussian coefficients and their generalizations via technical results for Kronecker coefficients, a tool never been used for that before.  Does that make our paper “less combinatorial” somehow?  In fact, some experts openly advocate that the more advanced the tools are, the better, while others think that “term ‘combinatorial methods’, has an oxymoronic character”.

Third theme: combinatorics is “special” and cannot be defined.  Ugh…  This reminds me of an old (1866), but sill politically potent Russian verse (English translation) by Tyutchev.  I can certainly understand the unwillingness to define combinatorics, but saying it is not possible is just not true.

Finally, a piecemeal approach.  Either going over a long list of topics, or giving detailed and technical rules why something is and something isn’t combinatorics.  But this bound to raise controversy, like who decides?  For example, take PCM’s “few constraints” rule.  Really?  Somebody thinks block designs, distance-regular graphs or coding theory have too few constraints?  I don’t see it that way.  In general, this is an encyclopedia style approach.  It can work on Wikipedia which is constantly updated and the controversies are avoided by constant search for a compromise (see also my old post), but it’s not a definition.

My answer, after Gian-Carlo Rota.

After some reading and thinking, I concluded that Gian-Carlo Rota’s 44 y.o. explanation in “Discrete thoughts” is exactly right.  Let me illustrate it with my own (lame) metaphor.

Imagine you need to define Russia (not Tyutchev-style).  You can say it’s the largest country by land mass, but that’s a description, not a definition.  The worst thing you can do is try to define it as a “country in the North” or via its lengthy borders.  You see, Russia is huge, spead out and disconnected.  It lies to the North of China but has a disconnected common border, it has a 4253 mile border with Kazakhstan (longer than the US-Canada border excluding Alaska), surrounding the country from three sides, it lies North-West of Japan, East of Latvia, South-West of Lithuania (look it up!), etc.  It even borders North Korea, not that this tiny border is much in use.  Basically, Russian borders are complicated and are a result of numerous wars and population shifts; they have changed many times and might change again.

Now, Rota argues that Combinatorics is similarly formed by the battles, and can only be defined as such.  It is a large interconnected field concentrated (but not coinciding!) around basic discrete tools and problems, but with tentacles reaching deep into “foreign territory”.  Its current shape is a result of numerous “wars” – the borderline problems are tested on which tools are more successful, and whoever “wins”, gets to absorb a new subfield.  For example, in its “war” with topology, combinatorics “won” graph theory and “lost” knot theory (despite a strong combinatorial influence).  In other areas, such as computer science and discrete probability, Rota argues there a lot of cooperation, a mutually beneficial “joint governance” (all lame metaphors are mine).  But as a consequence, if one is to define Combinatorics (or Russia), the historical-cultural approach would go best.  Not all that different from Sheldon’s approach to define Physics ”from the beginning”.

Summary.

In conclusion, let’s acknowledge that Combinatorics can indeed be defined in the same (lengthy historical) manner as a large diverse country, but such definition would be neither short nor enlightening, more like a short survey.  As Danny Kleitman writes, in practice this lack of a clear and meaningful definition of the subject “never bothered him”, and we agree.  I think it’s time to stop worrying about that.  But if someone makes blank general statements painting all of combinatorics in a certain way, this is just indefensible.

Who computed Catalan numbers?

I became rather interested in the early history of Catalan numbers after reading multiple somewhat contradictory historical accounts.   Now that I checked the sources, most of which are available online (see my Catalan Numbers page), I think I understand what happened.  While I conclude that Euler deserve most of the credit, as I see it, what really happened is a bit more complicated. Basically, this is a story of research collaboration, only fragments of which are known.

Warning: I am assuming you are familiar with basic results on Catalan numbers, which allows me to concentrate on the story rather than the math.

Conventional wisdom

All sources basically agree that Catalan numbers are named after Eugène Catalan (1814–1894), though they were computed by Leonhard Euler.  There are several narratives in the literature, which are variations on the following statements, neither of which is really correct:

1.  The problem was introduced by Segner in his 1758 article and solved by Euler in an unsigned article in the same journal volume.

2. The problem was introduced by Euler in his 1758 unsigned article and solved by Segner by a recurrence relation in the same volume.

3. The problem was introduced/solved by Euler in a 1751 letter to Goldbach, but Segner’s paper is the first published solution.

4.  Although the problem was raised by Euler and/or Segner, neither of which found a proof.  The first proof was given by Lamé in 1838.

Let me delay the explanation of what I think happened.  Please be patient!

People and places

There are three heroes in this story: Leonhard Euler (1707–1783),  Christian Goldbach (1690–1764), and Johann von Segner (1704–1777).   Goldbach was the most senior of the three, he moved to St. Petersburg in 1725, tutored Tsarevich Peter II, and lived in Russia for the rest of his life.   When young Euler arrived to St. Petersburg in 1727, Goldbach became his mentor, lifelong friend and a correspondent for over 35 years.  Of the numerous letters between them, many were edited and published by Euler’s former assistant, a mathematician and grandson-in-law Nicolas Fuss (1755–1826).

Segner was a physician by trade, but in 1732 became interested in mathematics.  In 1735 he was appointed the first mathematics professor at the University of Göttingen (not a big deal at the time).  Euler left Russia in 1741 to a position at the Berlin Academy, and joined the court of Frederick the Great of Prussia, at which point he became a frequent correspondent with Segner.  Their relationship, perhaps, was closer to a friendly competition than a true friendship between Euler and Goldbach.  Although Segner and Euler were contemporaries, Euler rose to prominence very quickly and had a lot of political sway.  For example, he slyly engineered Senger’s position at the University of Halle in Saxony, where Segner moved in 1755.  Unfortunately, only letters from Segner to Euler survived (159 of them) and these have yet to be digitized.

In 1756, Frederick II overrun the Saxony as a part of initial hostilities of the Seven Year’s War, which put Prussia and Russia on different sides.  But Euler continued to publish in Russia, where he was widely respected.  When Russian troops marched through Berlin in 1760 (not for the last time), he did not leave the city.  Later, when his personal estate was marauded, he was eventually compensated by Catherine the Great (whose court he joined in 1766).

Letter exchange between Euler and Goldbach

* First letter:  September 4, 1751 letter, from Euler to Goldbach.

Near the end of the letter, Euler writes matter of factly, that he figured out the numbers of triangulations of the polygons with at most 10 sides.  Evidently, he does this by hand, and then takes ratios of successive number to guess the general product formula.  He writes:

Die Induction aber, so ich gebraucht, war ziemlich mühsam, doch zweifle ich nicht, dass diese Sach, nicht sollte weit leichter entwickelt werden können.

He continues to guess (correctly) a closed algebraic formula for the g.f. of the Catalan numbers sequence.

* Second letter:  October 16, 1751 letter, from Goldbach to Euler.

Here Goldbach suggests there is a way to verify Euler’s g.f. formula by algebraic manipulations.  Essentially, he rewrote Euler’s formula for the g.f. for Catalan numbers as a quadratic equation for power series.  He the checks the equation for the first few coefficients.

* Third letter:  December 4, 1751 letter, from Goldbach to Euler.

Here Euler uses the binomial theorem to show that the generating function formula indeed implies his product formula for the Catalan numbers.

Papers by Euler and Segner

* Segner’s paper in Novi Commentarii, volume 7 (dated 1758/59, but published only in 1761).

Here Segner finds and proves the standard quadratic relation between Catalan numbers.   He starts by attributing the problem to Euler and mentioning the first few Catalan numbers that Euler calculated.  He then uses this quadratic equation to calculate the first 18 Catalan numbers, but makes an arithmetic mistake, thus miscalculating the last 6.

* Euler’s paper in the same volume (unsigned, but universally attributed to Euler).  My fan translation into English.

Euler describes the number of triangulations problem, mentions Segner’s recurrence relation, and then his direct inductive formula for Catalan number, which he rewrites as a conventional product of  n-2  fractions.   He then uses this formula to correct and extend Segner’s table.

What happened (my speculation) :

This was a collaborative research effort.  First, Euler introduced the number of triangulations problem, which perhaps came from his map making work both in Russia and in Berlin (he hints to that in his “summary”).  Euler labored to compute by hand the first few Catalan numbers by using ad hoc methods; he correctly calculated them up to 1430 triangulations of a 10-gon.  He used these numbers to guess a simple product formula for the Catalan numbers by observing a pattern in successive ratios, and a closed form algebraic formula for the g.f.  He clearly realized that the proof of both is needed, but thought this was a difficult problem, at which point he writes to Goldbach.  In his reply, Goldbach suggested how to verify the analytic formula, but Euler took a different route and showed that one formula implies the other.  From a modern point of view, this was an open exchange of ideas between friends and collaborators, even if dominated by Euler’s genius.  

Some years later, Euler evidently suggested this problem to Segner, but never informed him of the product formula which he guessed back then.  While Euler’s letters to Segner did not survive, it is clear from Segner’s writing that he knew of some Euler’s calculations, but not the product formula (there is no way he would have made a mistake in the table otherwise), nor even the 1430 value (the largest number reported by Euler to him seemed to be 429).  No wonder Segner did not prove Euler’s product formula – he simply did not know what he should be proving, so presented his results as a method for computing Catalan numbers.  

Finally, when Euler saw Segner’s work, he immediately realized its value as the last missing piece.  Essentially, Segner’s recurrence is exactly what remained in the sequence 

combinatorial interpretation → recurrence relation → algebraic equation → closed algebraic formula → product formula,

where the first step is due to Segner, the second and third are easy and closely related to Goldbach’s approach, while the last step is due to Euler himself.  Those who teach undergaduates this particular proof, know how much of a pain to teach this last step.  As I understand, despite the war and geography, Euler continued editing the volumes of the St. Petersburg based Novi Commentarii.  In what should have been the “Summary” of Segner’s article, he included his formula as a way to both gently correct Segner and show the superiority of his product formula.  I should mention that Euler’s Latin original sugarcoated this.   It is a pity that Euler never published anything else on the subject.

What happened next:

This is much better documented.  First, in response to a question by Johann Pfaff, the above mentioned Nicolas Fuss published in 1791 a generalization of Segner’s recurrence relation, and converted it to a higher order algebraic equation for the g.f., thus generalizing Euler’s algebraic formula.  This allowed Liouville to give a product formula for this generalization using the Lagrange inversion formula, which was later rediscovered by Kirkman, Cayley and others. 

The problem was then studied French mathematician and promoter of Reform Judaism Olry Terquem (1782–1862).  As hinted by Liouville in a foonote to Lamé’s article, Terquem knew of both Euler’s and Segner’s articles, but not of the algebraic formulas.  He seem to have succeeded in proving that the recurrence relation implies the product formula, thus “achieving it with the help of some properties of factorials”.  In in 1838, he suggested the problem to Joseph Liouville (1809–1882), who in turn suggested the problem to a number of people, some of whom became to actively work on the subject.  Liouville’s colleague at École Polytechnique,  Gabriel Lamé (1795–1870), quickly found  an elegant combinatorial solution building on Segner’s approach.  Liouville extracted mathematical content from the letter Lamé wrote to him, and quickly published it (English translation), in the Journal de Mathématiques which he started two years earlier.  This became the first published complete proof of the product formula for Catalan numbers.  

In the following year, other colleagues joint the effort (Binet, Catalan, Rodrigues), and their effort was also published by Liouville.  In the following 175 years the problem has been repeatedly rediscovered and generalized (notably, by Bertrand in 1887, in the context of the ballot problem).  A small portion of these papers is listed here.  Henry Gould’s 2007 count gives 465 publications, surely undercounting the total.

What’s in a name?

Curiously, Catalan’s own contribution was helpful, but not crucial.  Netto singled him out in his 1901 monograph, as he favorited Catalan’s language of parenthesized expressions over the less formal discussion of polygon triangulations.  Catalan himself called them “Segner numbers“.  Given that Euler already has plenty of numbers named after him, it’s too late to change this name.  We are stuck with Catalan numbers!

Note:  This post is not a piece of research in History of Mathematics, which is a serious field with high standards for quality and rigor.  This is merely a speculation, my effort to put together some pieces of the story which do not seem to fit otherwise.

Update (Feb 28, 2013): S. Kotelnikow’s 1766 contribution is removed as he seem to have proved absolutely nothing.

College admissions II. What’s the hurry? Waste a year!

To say that college admissions are overhyped would be an understatement.  There are literally many thousands of articles written on the subject each year (GoogleNews counts 2,000 in December 2012 alone), most of which have nothing new to say, except that it is very, very important…  In my earlier post I discussed discrimination concerns and crude solutions by universities and the public (read: politicians) to deal with it.  But truth of the matter is, these issues are so difficult in part because people value college education so greatly.  While I am obviously a strong supporter of college education (also, it pays my bills), college admissions does not have to be that consequential.  Here I argue for waiting a year or two, which would decouple the issues, shift decision making from parents to students, and hopefully ease the tension.

The way things are here

When it comes to college admissions, high school students and their parents are anxious and busy with this increasingly costly and time consuming activity.  At the end, over 60% of them go to college.  Of these, about 76% get into college of their first choice, and of those who don’t, most are happy anyway.  Now, all this might seem like a case for “stay the course”, but in fact, lots of people agree on the need for change, but not everyone agrees on what the change should be.  Let me present a particular aspect of the problem, which in my view make college admission so hot as an issue.

If you a faculty, you know that many students come to college morally unprepared.  Many simply view college as a “high school without parents“.  The universities worry about this extended adolescence, but in general are happy to take over this part of parental responsibilities in exchange for higher tuition.  No wonder the college bureaucracy is expanding – the need is evident.  This is very different from an old model of college as a place of higher learning where either usable skills or arts and letters, are studied by young adults, in preparation of lifetime employment.

It is not a surprise then, that at the end of their college years the students are lost and confused, unprepared for real jobs, and often choose graduate schools as a way to avoid hard decisions.

Why do parents do it?

That is, why are they willing to spend exorbitant amounts of money for a mixture of parenting and education, instead of letting them travel the world or work odd jobs etc., until their children are ready for the education?  I it just peer pressure?  Probably not.   Mostly, because they can.  At 18, american high school graduates are not considered adults yet, and with no savings are not in a position to make their own choices.  But when parents choose, they are not necessarily governed with what’s best for the children.  Paul Graham explains this well in the context of choosing a college major (ht. L. Positselski):

The advice of parents will tend to err on the side of money. It seems safe to say there are more undergrads who want to be novelists and whose parents want them to be doctors than who want to be doctors and whose parents want them to be novelists. The kids think their parents are “materialistic.” Not necessarily. All parents tend to be more conservative for their kids than they would for themselves, simply because, as parents, they share risks more than rewards. If your eight year old son decides to climb a tall tree, or your teenage daughter decides to date the local bad boy, you won’t get a share in the excitement, but if your son falls, or your daughter gets pregnant, you’ll have to deal with the consequences.

So naturally the parents are scared that a year or two outside of the controlled environment will lead to a lifetime of disappointment.  They use the tuition money as the last tool they have to control their children, even if this bankrupts them in the meanwhile.  This also robs children of potential financial support down the road, whether to start their own business or pursue literary dreams, or house down payment when they start a family.

Why do students do it?

Oh, of course very few children say no to candy (college tuition in this case).  Deferred gratification requires a character, an adult quality.  The point is not to put the students into position when they have to make a difficult choice between the education they are uncertain about, and the lifestyle they want while contemplating their life goals and risking all this cash their parents saved for college.  Only later, some students drop out to pursue their dreams.

How do students fare?

That depends.  Sometimes very poorly.  They fail basic courses, study for 5 or more years to complete a college degree, drop out, and occasionally commit suicide.  The ones who are lucky and realize that their college does not meet their goals, transfer to other schools.

This is not as rare as some people think.  For example, Barack Obama transferred from Occidental College to Columbia.  Dick Cheney flanked out twice from Yale and eventually graduated from the University of Wyoming.  Sarah Palin famously attended 5 colleges before graduating from the University of Idaho.  As Tim Noah reports, her grades were good, but she was in constant search of a school which would fit better her ever changing sports and academic interests.

Can things be different?

Of course.  And I am not talking about New Guinea lessons.  If college was free or nearly free, this would greatly diminish parents’ influence.  The knowledge that cheap college will wait while they grow up, would allow many students take a year or two off before they start college.  This would allow them to grow up, discover themselves, learn what they really want to do with their life, and become motivated.

Western Europe, of course, has inexpensive education, but is misleading as an example, since most universities are public and tend to be equal in funding and opportunities (within each country).  Also, things are slowly changing.  But in Eastern Europe, the universities are often very different in quality and offered majors, while still inexpensive enough to allow students to ignore parents’ advice and enjoy several years of travel and self-discovery.  Occasionally, a foreign born celebrity laments on the lack of that in America, but is never taken seriously.  Too bad.

Really different models

Let us count the ways other societies and subcultures change the above equation to allow 18 year olds to grow up before they join college.  While I don’t specifically advocate for either of these, the list does show that a few years away from the studies can be beneficial, or at least does not harm teenagers as much as their parents tend to think.

The most common is the military service, which varies in length may include civil service.  It is required even in some of the most developed countries such as Finland, Norway, Switzerland, and South Korea.  Until relatively recently it was required in virtually all countries.  AmeriCorps (not to be confused with PeaceCorps) is the US civil service pre-college alternative to serving in the military, but with only about 10-15 thousand people joining each year.

In Israel, both men and women are drafted, although at different lengths.  At the end of the service it is customary for former soldiers to travel the world for six months to a year, in destinations ranging from Bolivia to Sri Lanka, doing various experiments considered illegal at home.  These overseas trips are commonly viewed almost as the rite-of-passage.  Virtually all of these former soldiers later come back to Israel and become law obedient productive citizen, many with college degrees.

Religion is another source of lengthy travel and civil commitments, which range from Rumspringa (Amish adolescents’ leaves to explore the world) to Mormon missionary work.  Famously, Mitt Romney spent 2.5 years in France, while Jon Huntsman was a missionary in Taiwan.

Both military and civil service tends to make students more mature and goal oriented, if only because they are older.  For example, after a 5 year service in the IDF, current Israel Prime Minister Bibi Netanyahu became a freshman at MIT at the age of 23, and earned two degrees (B.S. and M.B.A.) in four years (read why in the article).

Two personal anecdotes

After high school, I did not enroll at the university (not by choice, as I explained earlier), but went to  work as a C++ programmer at a bank (no, you don’t need a degree for that).  At the end of the year, I learned something about myself.  Turns out, I really dislike working all night to meet a deadline, providing mountains of documentation accompanying the code, or dealing with ever more demanding managers who understood little about the actual work.  So I promised myself to never ever do any programming again, a pledge that was easy to keep in my current vocation.

In another story, one of my distant relatives (let’s call him Mr. X) asked me what to do about his son suddenly being accepted to an Ivy League school.  With a high 5-figure salary he was rich enough not to be eligible for financial aid, and poor enough to afford the tuition.  After reading the rules, I told X that things are easier than he thinks.  All he had to do is defer enrollment for a year (this is allowed by many schools), send the kid to Russia live with a grandmother, and let him file his own taxes.  At the end of the year, X’s son can declare “financial independence” by signing a piece of paper in front of a notary public, that he is “abandoned by parents”.  Then, as a pauper, receive all financial aid available in such cases.  This trick would undoubtedly have saved Mr. X an upward of 100K.  But parental instincts are way too strong – instead he took a second mortgage on the house.  (Some minor details are changed to protect the identity of X’s family).

What can be done?

In general, rather little.  Changing the culture is hard, and rarely possible top-down without financial incentives.  Ideally, after high school the students should travel the world and explore different professions until they settle on what they want to do.  But as long as the colleges are expensive, the parents will continue to control the process sending the children to college immediately after high school, without giving them such opportunity.

Fortunately, there is a crisis in university education, with the offering of large scale online courses, and I mean “fortunately” in the same sense as Rahm Emanuel.  It has long been suggested by the advocated of inexpensive public education in California that most students should spend the first two years in local community colleges and then transfer to an appropriate UC or CalState school depending on their achievements.  Then schools such as Berkeley or UCLA would essentially become 2-year “finishing schools”.  The parents tend to revolt at this suggestions due to inherent uncertainty of the outcome.  I propose a variation on this approach, essentially bribing all the parties involved.

1. Make available online all standard introductory classes.
2. Allow an off-campus registration for at most 2 years, and charge only a fraction of the tuition for it.  Require B- average to maintain it.
3. Encourage more student transfers, both in and out, based on these grades.

Under there conditions with a guaranteed college spot, I believe many more students would choose to save on the tuition and travel the remote parts of the world, perhaps working part-time teaching conversational English, while taking the required few online classes to maintain college eligibility.  In a long run, this is also a good deal for the universities, as this would lead to smaller classes and more personalized attention to students who come back and enroll on campus.  The students themselves will be more mature and motivated, improving the graduation rate.

Hopefully, with time this will also reduce the temperature of college admission on all sides.  As the early online experience is equalizing and there is always a possibility of transfer later on, the potential admission mistakes become much less costly.  Baby steps…

College admissions I. Discrimination and lies, Jews and Harvard

Recent reports on alleged discrimination of Asian Americans at Ivy League schools (read a discussion here and view this graph), brought a lot of disgust in me, as well as some ambivalence. Here and in the next post I will try to deconstruct these feelings.

In this post I mention my family and my own history of dealing with discrimination.  I then briefly review and make parallels with the current discussion of the issues, and make some recommendations.  In the next post, I will explain why the whole issue is overhyped and what does that say about american culture.

Russian Jews go to school

Well, this is a really long story, but when it comes to educational opportunities, things were always pretty bad.  By 1880′s most universities and gymnasiums in Imperial Russia instituted a 5 to 10% Jewish quota, which remained in effect until the Russian revolution in 1917.  Read more on the history in this book (part III), and in amazing personal memoir (in Russian).

Communists abolished Jewish discrimination replacing it with anti-religious discrimination, often having similar effect.  In the 1930s, my grandmother was expelled from college after communist officials discovered that her father (my great-grandfather) was a rabbi.  A local newspaper went all schadenfreude about her, and published an anti-clerical article ”The wolf in sheep’s clothing”, apparently missing the irony of the origin of the title.

By the early 1960s, Israel became a super-enemy of USSR, and things were slowly getting hotter for the Jews.  For example, despite high exam grades, my father and few dozen Jews was denied admission to Moscow University (МГУ) on account of “lack of dorm space”.  Some scandal ensued and he was accepted a month later.   By the late 1960s, after the Six-Day War, the Mathematics Department of Мoscow University settled on 0.5% quota (about 2 Jewish students in a class of 450-500), which typically went to children of the university faculty and occasional party officials.  When I applied in 1988, I was rejected as the quota remained in effect.  In 1989, things were starting to change, and the quota was raised to about 4%.  I got in.  In the meantime, I became somewhat of an expert on “Jewish problems” (see also here and there), once even holding a seminar on them.

Curiously, the officials had supported the quota very openly, justifying it as follows:

1. We need to maintain proportion of Jews the same as in the country, so as they don’t take space from ethnically Russian students.
2. Jews are already privileged by the virtue of living in large cities, but Russians from small villages need extra help to get quality education.  Of course, Jews in Ukrainian, Lithuanian and Belorussian villages were mostly killed in the WWII as part of the Final Solution.
3. Future Russia needs an educated workforce. There is no point of preparing “cadres for Israel“.  Thus the “diploma tax“.

My little brush with discrimination in the US

In 1994, already a first year grad student at Harvard, I applied for NSF Graduate Fellowhip, which was highly selective but much less generous back then.  I mailed my proposed plan of research, letters of recommendation, transcripts, and the required GRE, both General and Subject.  I was rejected.  Since I received a more selective Hertz Foundation Fellowship (see my discussion of it here), I wasn’t too upset, but I was curious what did I do wrong.  So I filed a FOIA request, and got a reply a few weeks later.

What I learned was remarkable and made me really upset.  I discovered that the NSF reviewers rated A all my materials, both the transcript, all the letters, and plan of research.  I had a maximal GRE Subject score.  But you see, me being Russian and all, I had a mediocre to poor GRE General score on the Verbal Section.  The paperwork indicated that the committee then took weighted average of all these grades, made a list of top scorers and I didn’t make the cut.  Since I could not fathom why would I need a top GRE Verbal score for Math Ph.D., this seemed clearly discriminatory, on the basis of my native language.

So I found a lawyer (tiny Cambridge, MA is full of them).  He patiently explained to me that my Russian native language is not defining me as a member of protected class, and I have no case against NSF. He said that even politically, there is no such thing as “Russian language lobby” (despite our large numbers), and given that there was no harm done (my Hertz), I should go home and learn to be happy.  Naturally, I did.

Jews at Harvard and the geographic distribution

The story of Jews at Harvard has been described in great details at a variety of sources.  In short, Harvard instituted a 15% quota, which was later softened, substituted with geographic distribution preferences, having same effect on Jewish enrollment.   The following quote about the evolution of Harvard President James Conant (1933-1953) is revealing:

Conant’s pro-quote position in the early 1920s, his preference for more students from small towns and cities and the South and West, and his cool response to the plight of the Jewish academic refugees from Hitler suggest that he shared the mild antisemitism common to his social group and time. But his commitment to meritocracy made him more ready to accept able Jews as students and faculty.

While the quotas are both illegal and a thing of the past, the use of geographic distribution in admissions never went away.  While not discriminatory in the strict legal sense, they were created with a discriminatory intent, and still have discriminatory effect, as recent immigrants, Jews and other minorities tend to concentrate in large population centers.  Not unlike the Russian “village” arguments, this is a slight of hand, which first creates and then heavy-handedly destroys a straw man, all in an effort to deal with other issues which are kept out of sight.  We will see this in other cases as well.

All students are somebody’s children

Legacy preferences is another example of misleading practices potentially having discriminatory effect.  Universities are claiming that this creates a brand loyalty.  But that is misleading of course.  Do Ivy League schools really need to develop brand loyalty when they have 10-20 applicants per spot?  The truth, of course, is that children of alumni have money and willing to pay a full sticker price of the tuition, and the admission officers aim to have about 20% of such legacy students in each freshmen class.

In fact, the honest market based solution would be to auction this portion of the freshman class to the highest bidder, charging tuition perhaps as much as 100K per year.  This auction would raise significant funds which can pay for poor students’ scholarships and stipends, and open up these admission slots to everyone, not just children of alumni.  As it is, legacy candidates get preferences in admission and, perhaps counter intuitively, have their tuition subsidized as others may potentially be willing to pay more for their spots.  Now, I am NOT advocating for this, just showing how misguided and fundamentally unfair are the current admission policies.

Texas 10% solution

This rule was enacted in response to state losing in Hopwood v. Texas, as a novel legal way to introduce diversity in admissions.  An ultimate geographic preference, this rule fills about 75-80% of  the freshmen class at the leading Texas universities.  Note that the Fisher case is about the affirmative action for the remaining spots.

But it is exactly the kind of rule which makes wrong priorities for the students and the society.  In general, it is beneficial for the society when students have a choice which K12 school to attend.  It is undoubtedly good when they study in the most challenging environment, work hardest on the most advanced courses available.  This rule pushes students to take the easiest courses in the least challenging school, aiming to attain the highest GPA and enter the coveted 10%.  And guess what – Texas students do exactly that (this in addition to other rule troubles).

A case for honesty

As it stands, the universities are on the brink of losing another affirmative action case in the Supreme Court.  Perhaps this is not immediately apparent, but they are also on the brink of a giant PR disaster when it comes to their hidden quotas for Asian Americans.  With good intentions, the admission officers and politician keep coming up with twisted, misleading, uncomfortable and occasionally self-contradictory rationale as to why they do what they do (see above).   The problem is – with all the history, we’ve seen this all before, and nobody is buying it.  With so much public pressure, they probably have to stop and own up to their choices.

I think it is clear what many top colleges are doing.  They have a goal of a freshmen class which would have f(x)% students with property x, for many different x, which can be race, gender, wealth, political connections, geographic location, sexual orientation, sports, music, science and other achievements, etc.  So they produce all these policies like the early action, and many rationalizations aimed at reaching that goal.  One should have a lot of chutzpah to believe to know exactly the “right mix” function f, but of course they think that…

If it was up to me, I would give the universities a complete freedom to accept whoever they want without fear of lawsuits, in exchange for complete transparency.  Education is really not like housing or employment, it is fluid and highly competitive.  In exchange, make the universities publish the exact numbers of how many students with every property x have applied and got accepted.  For the sake of anonymity, delete all the names and zip codes, and publish on the web the rest of the data from their applications.  Let the future applicants, or nonprofits on their behalf, decide their chances of acceptance and make rational choice whether to spend their $75 and endless hours applying to that school.  Unfortunately, we don’t live in an ideal world, but you have to let colleges compete with each other, which is the most fair and offers the best model of education.

Finally, when it comes to Asian Americans – Harvard and the rest of the Ivies should just apologize, and starting next year accept twice as many as this year, to compensate for the real or perceived discrimination.  Otherwise, a hundred years from now, somebody might still be writing how stupid and morally twisted were these old early 21st century admission policies.

Warning:  Here I neither endorse nor reject the affirmative action, but rather advocate for some honesty, clarity and transparency.

Admission blues: How to fix GRE Mathematics and tweak the Putnam Competition

I was thinking about the Putnam competition and the GRE Mathematics test in the context of graduate admissions.  Are they useful?  If yes, which one is more relevant?  After crunching some numbers, I concluded that while they are useful to some extend, there are problems with both.  Even worse, a number of students who fall in the gap between “very good” and “exceptional”, are ill served with either.

1. Graduate admissions in mathematics

As I mention in my earlier post, every year the US produces around 1,600 Ph.D.’s in mathematical sciences (math, applied math, statistics) from over 100 accredited programs, of which about 900 are US citizen and permanent residents.  If you restrict to mathematics alone, the numbers drop by about 25% to about 1200. The overall 10 year completion rate is about 50%  according to the Council of Graduate Schools study, so perhaps about 3,000-3,200 students start graduate programs.

As a general rule, graduate programs in mathematics explicitly ask for the GRE Subject test scores, but are often happy to hear about the Putnam results as well.  In fact, some “how to” guides now recommend taking Putnam exam (and Putnam prep classes!) on par with the GRE test and REU programs (see e.g. here and there).  How the schools use either data is probably quite a bit different, and is the other side of our main question.

2. GRE Mathematics Subject test in numbers

The GRE Subject tests are developed and administered by ETS, which is nominally non-profit, but with about 1 billion dollars in revenue.  For a quick comparison with a for-profit, non-profit and public institutions, e.g. New York Times Corp, Harvard and UCLA, had 2.3, 3.7 and 4.3 bln dollars in 2011 operating revenues, respectively.

From the official GRE test preparation publication:  ”The questions are classified approximately as follows: calculus (50%), algebra (25%) and other topics (25%).”  This is already unfortunate, but more on that later.  Here are these “other topics”:

Introductory real analysis (sequences and series of numbers and functions, continuity, differentiability and integrability, elementary topology of R), discrete mathematics (logic, set theory, combinatorics, graph theory, and algorithms), general topology, geometry, complex variables, probability and statistics, and numerical  analysis.  The above descriptions of topics covered in the test should not be considered exhaustive [...]  (emphasis mine – IP)

The GRE Guide gives .92 value for the KR20 reliability test, a solid measure suggesting the test has many questions leading to different scores between strong and weak students.  The students have 170 minutes for about 65 questions.  The scores are on the scale from 200 to 990, are rounded to nearest multiple of 10, with standard errors 31 points, and 44 for the differences.  In other words, if I understand correctly (the guide is vague on this), one should not reliably compare students with scores differing by 50 points of less.  I am doubtful most grad schools  follow that.

In the same GRE guide, ETS reports that there were about 12,800 test takers in four years (July 2008 to June 2011), roughly 3200 a year.  This loosely coincides with our graduate student data, as the students take on average one GRE Subject test.  In other words, all students with GRE scores get accepted somewhere.  So one should not be surprised to see a high correlation (but not necessarily causation) between grad school ranking and GRE Subject scores. Curiously, ETS’s own study says GRE General are a very poor predictor of success in math graduate programs, at least when it comes to GPA and graduation rate.

So how do grad schools use the GRE Math scores? That’s very much unclear. Of course, all schools gather the statistics like averages of those applied, admitted and/or accepted (reported to the dean, external department reviewers, the NRC study, the US News, etc.), but very few make it publicly available.  In a rare moment of openness, Penn State admits what amounts to not much use of GRE scores: their average scores vary widely over the years, swinging from 650 to 890, with a positive trend in recent years.  In a general MO discussion on this, Pete Clark writes that University of Georgia does  not require GRE Subject, so he looks for high GRE General scores.  UCLA is a bit evasive: “those we offer admission to have GRE subject scores in or above the 80th percentile” which according to GRE chart amounts to minimum of about 790, suggesting relevance.   MIT is blunt but imprecise: “There is no minimum GRE test score required, but if the score on the math subject GRE is not very high, evidence of excellence must be present elsewhere in the application or in the letters of recommendation.” UPenn is actually helpful: “[GRE Math score] should be at least 750, though applicants with somewhat lower scores may be admitted if the rest of their application is sufficiently strong,” and that the recent average score is 820.  This all makes a very foggy picture.

3. Putnam competition in numbers

The premise is simple: first Saturday in December, 6 hours (in two sittings) to solve 12 problems in all areas of mathematics, maximum of 10 points per problem.  Joe Gallian wrote a nice summary. The problems are difficult: the maximal score 120 is achieved only very occasionally, once in about 10-15 years.  The median score is often either 0, 1 or 2 (out of 120!), and the mean is between 5 and 10 points.  I bet it must be depressing to spend 6 hours and get no or almost no points.

The top 5 scorers are “Putnam Fellows”, another 18-20 are “in the money”, and about 50-60 get “honorable mention”.  In 2011, there were “4,440 students from 572 colleges and universities in Canada and the United States”.  The historical data shows that there is a clear correlation between doing well on Putnam and doing well in mathematics, which is even more pronounced for the top 25, and especially Putnam fellows.

Of course, the competition is not aimed at helping graduate admissions, as emphasized by the mid-March results date (way after the applications are due and the admission decisions are made).  It does not even make the scores available in any official format.  In fact, historically, it is primarily a team competition, a nerdy alternative to college athletics.  Finally, a competition is not necessarily similar to do research.  As Kedlaya said, “A contest problem is meant to be solved in the space of minutes or hours, whereas in research, one sometimes works on the same problem for days, months, occasionally even years.”

4. A bissel of analysis

(a)  GRE Math.  While useful to some extend, mostly for the middle and bottom scoring students, it is largely useless for most of the better prepared students.  Indeed, in the “upper middle range” of 75 to 90 percentile, the test scores range between 770 and 850, comprising about 500 students every year.  By the rules of GRE, many of these students cannot be even compared.  Those who can, it is unclear whether they really are better candidates for doing research and teaching in mathematics.  Indeed, the excessive emphasis on calculus, real analysis and linear algebra shows the student’s ability to memorize concepts and quickly perform routine tasks.  This does not test problem solving.  Neither do “other topics” which are heavily testing definitions of a group, ring, metric space, etc.  I bet the performance in this part strongly correlates with the quality of the undergraduate institution: better colleges offer more serious math classes, and GRE Math preparation classes, which cover these basic topics; others do not.

For the top 10%, the GRE Math scores does distinguish between them, but that’s hardly necessary.  Of the top 250-300 students over half of them are international and often come with accolades like “the best student in N years from the XYZ university.” Last year I recall even one European student described as “the best student since World War II from … country”.  Those 100-150 that are from the US, are well served with numerous REU programs both national and at their home universities, by the Budapest and Moscow semesters, Putnam, IMO and other competitions, etc.  Their GRE scores seem irrelevant in retrospect.

Now, using AMS Classification, Group I of 48 top math graduate programs graduates about 550 Ph.D’s.  All are research oriented.  I am guesstimating that they must be accepting c. 800 students in total.  So after the top 300 are accepted, how are they suppose to choose the next 500 if GRE is irrelevant?

(b) Putnam.  Even though a majority receive only single digit score, there is a clear benefit for the top programs to know who the winners are.  The top 25 individuals, clearly possess excellent problem solving abilities, which is useful in a number of areas of mathematics.  The are multiple problems with this.  First, it would be nice to have the list of winners available by December.  Second, it would be nice if Putnam is offered overseas.  But even for the US/Canada based students, as it stands, the senior’s performance is not counted in admissions due calendar issues.  Since students often are encouraged to take their junior year abroad, the best performance they can include in their applications is from their sophomore year, which is often inferior to their senior year performance.  So with exception of the truly top students, Putnam results are not used in the admissions.

5. A modest proposal, Russian style

(a) GRE Math.  Split the GRE Mathematics into two parts.  Keep Calculus/Linear Algebra in the first half, more or less in the same multiple choice form as you have now.  It is clearly helpful for middle and bottom tier students and programs.  For the second part, make it a no-hard-math-required problem solving style.  Make many relatively simple problems, much much simpler than IMO problems, more like Moscow olympiads for the freshman-sophomore HS years (8-9th year out of 11).  This would allow relatively unbiased testing of problem solving, extremely useful to mathematics programs.  Both scores would need to be reported (kind of like 4 GRE General scores).

As revenue figures suggest, ETS is essentially a large utility company which does not want to rock the boat.  But it has made changes before, and this particular change would be relatively painless and have the added advantage that no “other fields” need to be argued about – all students will know exactly what is the scope of the test.

(b) Putnam.  Ugh.  It’s true that “if it ain’t broke, don’t fix it“, so I don’t want to propose major changes.  Just three minor tweaks, which will not change the core competition, but hopefully will make it more democratic and helpful for graduate admissions.

* First, move the competition to late September, so the scores can be revealed before Jan 1.  I really don’t see what exactly is hard about that.  Perhaps, some Putnam prep classes will have to be moved to the Spring.  So what?

* Second, open it for international students.  I know, I know, time difference, language issues, etc.  Whatever, keep it on the US time and only in English, as it is now.  If the overseas students want to participate, they might have to do this at night perhaps (simply allow unlimited tea, coffee and Red Bull).  This is still better than not giving them an opportunity at all.  Another issue is trust (in foreign faculty supervisors).  For that, use the technology.  Reveal the problem on some website for all at once.  Videotape what’s happening in all rooms where the competition is taking place.  Have all solutions uploaded as .pdf files to the main server within minutes after the end of the competition (they should still be graded locally, with top scores re-graded at a central location).  While some of this might be an obstacle for some universities in poor countries, the majority of foreign universities already have all the necessary technology to make this happen.

* Third, and most controversially, at least for the US/Canadian students allow an easy “parallel track”.  That is, come up with substantially easier problems which can be administered at the same time in parallel.  The students should be given a choice – either real problems which are hard, or easier problems which do not count.  This would be good for students’ morale as a means to prevent the annual 40% of 0 scores, and the scores can be useful for admission.  I am modelling this based on the widely successful Tournament of Towns, which has two levels and two tracks (harder and easier), see this problem archive.

P.S.  Full disclosure: I took GRE Math in 1994 and received maximal score available at that time. I recall finishing early, but missing a couple of problems possibly due to some English language difficulties.  I did not participate in the Putnam – was busy in Moscow.  More recently, I also participated in graduate admissions, but everywhere above made sure I use only open sources and no “inside information”.

What’s the Matter with Hertz Foundation?

Imagine you have plenty of money and dozens of volunteers.  You decide to award one or two fellowships a year to the best of the best of the best in math sciences.  Easy, right?  Then how do you repeatedly fail at this, without anyone notice?  Let me tell you how.  It’s an interesting story, so bear with me.

A small warning.  Although it may seem I am criticizing Hertz Foundation, my intention is to show its weakness so it can improve.

What is the Hertz Foundation?

Yesterday I wrote a recommendation letter to the Hertz Foundation.  Although a Fellow myself, I never particularly cared for the foundation, mostly because it changed so little in my life (I received it only for two out of five years of eligibility).  But I became rather curious as to what usually happens to Hertz Fellows.  I compiled the data, and found the results quite disheartening.  While perhaps excellent in other fields, I came to believe that Hertz does barely a mediocre job awarding fellowships in mathematics.  And now that I think about it, this was all completely predictable.

First, a bit of history.  John Hertz was the Yellow Cab founder and car rental entrepreneur (thus the namesake company), and he left a lot of money dedicated for education in “applied physical sciences”, now understood to include applied mathematics.  What exactly is “applied mathematics” is rather contentious, so the foundation wisely decided that “it is up to each fellowship applicant to advocate to us his or her specific field of interest as an ‘applied physical science’.”

In practice, according to the website, about 600 applicants in all areas of science and engineering apply for a fellowship.  Applications are allowed only either in the senior year of college or 1st year of grad school.  The fellowships are generous and include both the stipend and the tuition; between 15 and 20 students are awarded every year.  Only US citizen and permanent residents are eligible, and the fellowship can be used only in one of the 47 “tenable schools” (more on this below).  The Foundation sorts the applications, and volunteers interview some of them in the first round.  In the second round, pretty much only one person interviews all that advanced, and the decision is made.  Historically, only one or two fellowships in mathematical sciences are awarded each year (this includes pure math, applied math, and occasionally theoretical CS or statistics).

Forty years of Math Hertz Fellowships in numbers

The Hertz Foundation website has a data on all past fellows.  I compiled the data in Hertz-list which spanned 40 years (1971-2010), listed by the year the fellowship ended, which usually but not always coincided with graduation.  There were 67 awardees in mathematics, which makes it about 1.7 fellowships a year.  The Foundation states that it awarded “over 1000 fellowships” so I guess about 5-6% went into maths (perhaps, fewer in recent years).  Here is who gets them.

1) Which schools are awarded?  Well, only 44 US graduate programs are allowed to administer the fellowships.  The reasons (other than logistical) are unclear to me.  Of those programs that are “in”, you have University of Rochester (which nearly lost its graduate program), and UC Santa Cruz (where rumors say a similar move had been considered).  Those which are “out” include graduate programs at Brown, UPenn, Rutgers, UNC Chapel Hill, etc.  The real distribution is much more skewed, of course. Here is a complete list of awards per institution:

MIT – 14
Harvard, Princeton – 8
Caltech, NYU – 7
Berkeley, Stanford – 5
UCLA – 3
CMU, Cornell, U Chicago – 2
GA Tech, JHU, RPI, Rice – 1

In summary, only 15 universities had at least one award (34%), and just 7 universities were awarded 54 fellowships (i.e. 16% of universities received 81% of all fellowships).  There is nothing wrong with this per se, just a variation on the 80-20 rule you might argue.  But wait!  Hertz Foundation is a non-profit institution and the fellowship itself comes with a “moral commitment“.  Even if you need to interfere with “free marketplace” of acceptance decisions (see P.S. below), wouldn’t it be in the spirit of John Hertz’s original goal, to make a special effort to distribute the awards more widely?  For example, Simons Foundation is not shy about awarding fellowship to institutions many of which are not even on Hertz’s list.

2)  Where are they now?  After two hours of googling, I located almost all former fellows and determined their current affiliations (see the Hertz-list).  I found that of the 67 fellows:

University mathematicians – 27 (40%)
Of these, work at Hertz eligible universities – 14, or about 21% of the total (excluding 3 overseas)
At least 10 who did not receive a Ph.D. – 15%
At least 13 are in non-academic research – 19% (probably more)
At least 8 in Software Development and Finance – 12% (probably more)

Now, there is certainly nothing wrong with directing corporate research, writing software, selling derivatives, designing museum exhibits, and even playing symphony orchestra or heading real estate company, as some of the awardees do now.  Many of these are highly desirable vocations.  But really, was this what Hertz had in mind when dedicating the money?  In the foundation’s language, “benefit us all” they don’t.

I should mention that the list of Hertz Fellows in Mathematics does include a number of great academic success stories, but that’s not actually surprising.  Every US cohort has dozens of excellent mathematicians.  But the 60% drop out rate from academia is very unfortunate, only 21% working in “tenable universities” is dismaying, and the 15% drop out rate from graduate programs is simply miserable.  Couldn’t they have done better?

A bit of analysis

Every year, US universities award over 1,600 Ph.D.’s in mathematical sciences, of which over a half go to US citizen (more if you include permanent residents, but stats is not easily available).  So they are choosing 1.7 out of over 800 eligible students.  Ok, because of their “tenable schools” restriction this is probably more like 300-400.   Therefore, less than half of one percent of potential applicants are awarded!  For comparison, Harvard college acceptance rate is 10 times that.

Let me repeat: in mathematics, Hertz fellows drop out from their Ph.D. programs at a rate of 15%.  If you look into the raw 2006 NRC data for graduation rates, you will see that many of the top universities have over 90% graduation rate in the math programs (say, Harvard has over 91%).  Does that mean that Harvard on average does a better job selecting 10-15 grad students every year, while Hertz can’t choose one?

Yes, I think it does.  And the gap is further considering that Hertz has virtually no competition (NSF Fellowships are less generous in every respect).  You see, people at Harvard (or Princeton, MIT, UCLA, etc.) who read graduate applications, know what they are doing.  They are professionals who are looking for the most talented mathematicians from a large pool of applicants.  They know which letters need to be taken seriously, and which with a grain of salt.  They know which undergraduate research experience is solid and which is worthless.  They just know how things are done.

Now, a vast majority of Hertz interviewers are themselves former fellows, and thus about 95% of them have no idea about the mathematics research (they just assume it’s no different from the research they are accustomed to).  Nor does the one final interviewer, who is an applied physicist.  As a result, they are to some extend, flipping coins and rolling dies, in hope things will work out.  You can’t really blame them – they simply don’t know how to choose.  I still remember my own two interviews.  Both interviewers were nice, professional, highly experienced and well intentioned, but looking back I can see that neither had much experience with mathematical research.

You can also see this lack of understanding of mathematics culture is creeping up in other activities of the foundation, such as the thesis prize award (where are mathematicians?), etc.   Of course a private foundation can award anyone it pleases, but it seems to me it would do much more good if only some special care is applied.

A modest proposal

There is of course, a radical way to change the review of mathematics applicants – subcontract it to the AMS (or IMA, MSRI, IPAM – all have the required infrastructure).  For a modest fee, the AMS will organize a panel of mathematicians who will review and rank the applicants without interviewing them.  The panel will be taking into consideration only students’ research potential, not the university prestige, etc.  The Hertz people can then interview the top ranked and make a decision at the last stage, but the first round will be by far superior to current methods.  Even the NSA trusts AMS, so shouldn’t you?

Hertz might even save some money it currently spends on travel and lodging reimbursements.  The 13% operating budget is about average, but there is some room for improvement.  Subcontracting will probably lead to an increase in applications, as AMS really knows how to advertise to its members (I bet you currently receive only about 40 mathematics applications, out of a potential 400+ pool).  To summarize: really, Hertz Foundation, think about doing that!

P.S.  It is not surprising that the 7 top universities get a large number of the fellowships.  One might be tempted to assume that clueless interviewers are perhaps somewhat biased towards famous school names in the hope that these schools already made a good decision accepting these applicants, but this is not the whole story.  The described bias can only work for the 1st year grad applicants, but for undergraduate applicants a different process seems to hold.  Once a graduate school learns that an applicant received Hertz Fellowship (or NSF for that matter), it has every incentive to accept the student, as the tuition and the stipend are paid by the outside sources now.

P.P.S.  Of course, mathematicians’s reviews can also fail.  Even the super prestigious AIM Fellowship has at least one recipient who left academia for bigger and better things.

On triple crowns in mathematics and AMS badges

As some of you figured out from the previous post, my recent paper (joint with Martin Kassabov) was accepted to the Annals of Mathematics.  This being one of my childhood dreams (well, a version of it), I was elated for a few days.  Then I thought – normal children don’t dream about this kind of stuff.  In fact, we as a mathematical community have only community awards (as in prizes, medals, etc.) and have very few “personal achievement” benchmarks.  But, of course, they are crucial for the “follow your dreams” approach to life (popularized famously in the Last Lecture).  How can we make it work in mathematics?

I propose we invent some new “badges/statistics” which can be “awarded” by AMS automatically, based on the list of publications, and noted in the MathSciNet Author’s Profile.  The awardees can then proudly mention them on the department websites, they can be included in Wikipedia entries of these mathematicians, etc.   Such statistics are crucial everywhere in sports, and most are individual achievements.  Some were even invented to showcase a particular athlete.   So I thought – we can also do this.  Here is my list of proposed awards. Ok, it’s not very serious…  Enjoy!

Triple Crown in Mathematics

A paper in each of Annals of Mathematics, Inventiones, and Journal of AMS.  What, you are saying that “triple crown” is about horse racing?  Not true.  There are triple crowns in everything, from bridge to golf, from hiking to motor racing.  Let’s add this one to the list.

Other Journal awards

Some (hopefully) amusing variations on the Tripe Crown.  They are all meant to be great achievements, something to brag about.

Marathon – 300 papers

Ultramarathon – 900 papers

Iron Man – 5 triple crown awards

Big Ten – 10 papers in journals where “University” is part of the title

Americana – 5 papers in journals whose title may only include US cities (e.g. Houston), states (e.g. Illinois, Michigan, New York), or other parts of American geography (such as Rocky Mountains, Pacific Ocean)

Foreign lands – 5 papers in journals named after non-US cities (e.g. Bordeaux, Glasgow, Monte Carlo, Moscow), and five papers in journals named after foreign countries.

Around the world – 5 papers in journals whose titles have different continents (Antarctica Journal of Mathematics does not count, but Australasian Journal of Combinatorics can count for either continent).

What’s in a word - 5 papers in single word journals: (e.g. Astérisque, Complexity, Configurations, Constraints, Entropy, Integers, Nonlinearity, Order, Positivity, Symmetry).

Decathlon - papers in 10 different journals beginning with “Journal of”.

Annals track - papers in 5 different journals beginning with “Annals of”.

I-heart-mathematicians - 5 papers in journals with names of mathematicians (e.g. Bernoulli, Fourier, Lie, Fibonacci, Ramanujan)

Publication badges

Now, imagine AMS awarded badges the same way MathOverflow does, i.e. in bulk and for both minor and major contributions.  People would just collect them in large numbers, and perhaps spark controversies.  But what would they look like?  Here is my take:

enthusiast (bronze) – published at least 1 paper a year, for 10 years (can be awarded every year when applicable)

fanatic (silver) – published at least 10 papers a year, for 20 years

obsessed (gold) – published at least 20 papers a year, for 30 years

nice paper (bronze) – paper has at least 2 citations

good paper (silver) – paper has at least 20 citations

great paper (gold) – paper has at least 200 citations

famous paper (platinum) – paper has at least 2000 citations

necromancer (silver) – cited a paper which has not been cited for 25 years

asleep at the wheel (silver) – published an erratum to own paper 10 years later

destroyer (silver) – disproved somebody’s published result by an explicit counterexample

peer pressure (silver) – retracted own paper, purchased and burned all copies, sent cease and desist letters to all websites which illegally host it

scholar (bronze) – at least one citation

supporter (bronze) – cited at least one paper

writer (bronze) – first paper

reviewer (bronze) – first MathSciNet review

self-learner (bronze) – solved own open problem in a later paper

self-citer (bronze) – first citation of own paper

self-fan (silver) – cited 5 own papers at least 5 times each

narcissist (gold) – cited 15 own papers at least 15 times each

enlightened rookie (silver) – first paper was cited at least 20 times

dry spell (bronze) – no papers for the past 3 years, but over 100 citations to older papers over the same period

remission (silver) – first published paper after a dry spell

soliloquy (bronze) – no citation other than self-citations for the past 5 years

drum shape whisperer (silver) – published two new objects with exactly same eigenvalues

neo-copernicus (silver) – found a coordinate system to die for

gaussian ingenuity (gold) – found eight proofs of the same law or theorem

fermatist (silver) – published paper has a proof sketched on the margins

pythagorist (gold) – penned an unpublished and publicly unavailable preprint with over 1000 citations

homologist (platinum) – has a (co)homology named after

dualist (platinum) – has a reciprocity or duality named after

ghost-writer (silver) – published with a person who has been dead for 10 years

prince of nerdom (silver) – wrote a paper joint with a computer

king of nerdom (gold) – had a computer write a joint paper

sequentialist (gold) – authored a sequel of five papers with the same title

prepositionist (gold) – ten papers which begin with a preposition ”on”, “about”, “toward”, or “regarding” (prepositions at the end of the title are not counted, but sneered at).

luddite (bronze) – paper originally written NOT in TeX or LaTeX.

theorist (silver) – the implied constant in O(.) notation in the main result in greater than 10⁸⁰.

conditionalist (silver) – main result is a conditional some known conjecture (not awarded in Crypto and Theory CS until the hierarchy of complexity classes is established)

ackermannist (gold) – main result used a function which grows greater than any finite tower of 2′s.

What about you?  Do you have any suggestions?

How do you solve a problem like the Annals?

The Annals of Mathematics has been on my mind in the past few days (I will explain why some other day). More precisely, I was wondering

Does the Annals publish articles in Combinatorics? If not, why not?  If yes, what changed?

What’s coming is a lengthy answer to this question, and a small suggestion.

The numbers

I decided to investigate by searching the MR on MathSciNet (what else?)  For our purposes, Combinatorics is defined as “Primary MSC = 05″).  For a control group, I used Number Theory (“Primary MSC = 11″).   I chose a break point date to be the year 2000, a plausible dividing line between the “old days” and “modern times”.  I got the following numbers.

All MR papers:  about 2.8 mil, of which 1 mil after 2000.   In the Annals: 5422, of which 742 after 2000.

Combinatorics papers:  about 88k, of which 41k after 2000.  In the Annals: 18, of which 13 after 2000.

Number Theory papers:  about 58k, of which 29k after 2000.   In the Annals: 225, of which 129 after 2000.

So any way you slice it, as a plain number, as percentage of all papers, before 2000, after 2000, or in total – NT has about 10 times as many papers as Combinatorics.  The bias seems transparent, no?

Well, there is another way to look at the numbers.  MR finds that about 3% of all papers are in Combinatorics (which includes Graph Theory, btw).  The percentage of Combinatorics in the Annals is about 0.3%  Oops…  But the percentage in recent years clearly picked up – since 2000, 13 Combinatorics papers constitute about 1.7% of all Annals papers.  Given that there are over 50 major “areas” of mathematics (according to MSC), and Combinatorics is about 4.1% of all published papers since 2000, this is slightly below average, but not bad at all.

So what exactly is going on?  Has Combinatorics finally reached the prominence it deserves?  It took me awhile to figure this out, so let me tell this slowly.

The people

Let’s looks at individual combinatorialists.  Leonard Carlitz authored about 1000 papers, none in the Annals.  George Andrews wrote over 300 and Ron Graham over 450 papers, many classical ones.  Both аre former presidents of AMS.  Again, none in the Annals.  The list goes on:  W.T. Tutte, Gian-Carlo Rota, Richard Stanely, Don Knuth, Doron Zeilberger, Béla Bollobás, János Pach, etc. – all extremely prolific, and neither published a single paper in the Annals.  These are just off the top of my head, and in no particular order.

The case of Paul Erdős is perhaps the most interesting.  Between 1937 and 1955, he published 25 papers in the Annals in a variety of fields (Analysis, Number Theory, Probability, etc.)  Starting 1956, over the span of 40 years, he published over 1000 papers and none in the Annals.  What happened?  You see, in 1956 he coauthored a paper with Alfréd Rényi titled “On some combinatorical problems”, his very first paper with MSC=05.   Their pioneer paper ”On the evolution of random graphs“ came just four years later.  Nothing was ever the same again.  Good bye, the Annals!  Coincidence?  Maybe a little.  But from what I know about Erdős’s biography, his interests did shift to Combinatorics about that time…

Now, in NT and other fields things are clearly different.  After many trials, two champions I found are Manjul Bhargava (6 out of his 21 papers were published in the Annals), and Hassler Whitney (19 out of 65), both with about 30% rate.

The answer

In fact, it is easier to list those who have published Combinatorics papers in the Annals.  Here is the list of all 18 papers, as it really holds the clue to answering our initial question.  A close examination of the list shows that the 13 papers since 2000 are quite a bit diverse and interconnected to other areas of mathematics.  Some, but not most, are solutions to major open problems.  Some, but not most, are in a popular area of extremal/probabilistic combinatorics, etc.  Overall, a good healthy mix, even if a bit too small in number.

Note that in other fields things are different.  Check out Discrete Geometry (52C), a beautiful and rapidly growing area of mathematics.  Of the about 1800 papers since 2000, only three appeared in the Annals: one retracted (by Biss), and two are solutions of centuries old problems (by Hales and by Musin), an impossibly high standard.  One can argue that this sample is too small.  But think about it – why is it so small??

In summary, the answer to the first question is YES, the Annals does now publish Combinatorics papers.  It may look much warmer towards NT, but that’s neither important, nor the original question.  As for what caused the change, it seems, Combinatorics has become just like any other field.  It is diverse in its problems, has a long history, has a number of connections and applications to other fields, etc.  It may fall short on the count of faculty at some leading research universities, but overall became “normal”.  Critically, when it comes to Combinatorics, the old over the top criterion by the Annals (“must be a solution of a classical problem”), is no longer applied.  A really important contribution is good enough now.  Just like in NT, I would guess.

The moral

I grew up (mathematically) in a world where the Annals viewed Combinatorics much the same way it viewed Statistics – as a foreign to mathematics fields with its own set of journals (heck, even its own annals).  People rarely if ever submitted their papers to the Annals, because neither did the leaders of the field.  Things clearly have changed for the better.  Now the Annals does publish papers in Combinatorics, and will probably publish more if more are submitted.  The main difference with Statistics is obvious – statisticians worked very hard to separate themselves from Mathematics, to create a separate community with their own departments, journals, grants, etc.  They largely succeeded.  Combinatorialists on the other hand, worked hard to become a part of mainstream Mathematics, and succeeded as well, to some extent.  The change of attitude in the Annals is just a reflection on that.   

The over-representation of NT is also easy to explain.  I argued on MO that there is a bit of first-mover advantage going on, that some fields of mathematics feel grandfathered and push new fields away.  While clearly true, let’s ask who benefits?  Not the people in the area, which then has higher expectations for them (as in “What? No paper is the Annals yet?”).  While it may seem that as a result, an applicant in NT might get an unfair advantage over that in Combinatorics, the hiring committees know better.  This is bad for the Annals as well.  In these uncertain times of hundreds of mathematics journals (including some really strange), various journal controversies, often misused barely reasonable impact factors, and new journals appearing every day, it is good to have some stability.  Mathematics clearly needs at least one journal with universally high standards, and giving preferences to a particular field does not help anyone.

The suggestion

It seems, combinatorialists and perhaps people in other fields have yet to realize that the Annals is gradually changing in response to the changing state of the field(s).  Some remain unflinching in their criticism.  Notably, Zeilberger started calling it “snooty” in 1995, and continues now: “paragon of mathematical snootiness” that will “only publish hard-to-understand proofs” (2007),  “high-brow, pretentious” (2010).  My suggestion is trivial – ignore all that.  Combinatorialists should all try to send their best papers to the top journals in Math, not just in the field (which are plenty).  I realize that the (relative) reward may seem rather small, there is a lot of waiting involved, and the rejection chances are high, but still – this is important for the field.  There is clearly a lot of anxiety about this among job applicants, so untenured mathematicians are off the hook.  But the rest of us really should do this with our best work.  I trust the editors will notice and eventually more Combinatorics papers will get published.

P.S.  BTW, it is never too late.  Of the 100+ papers by Victor Zalgaller, his first paper in the Annals appeared in 2004, when he was 84, exactly 65 years after his very first paper appeared in Russia in 1939.

Computational combinatorics

Say, you have written a paper. You want to submit it to a journal. But in what field? More often than not, the precise field/area designation for this paper is easy to determine, or at least easy to place it into some large category. Even if the paper is in between fields, this is often well regarded and understood situation, nothing wrong with that. Say, the paper is resolving a problem in field X with tools from field Y. Submit to X-journal unless the application is routine and the crux of the innovation is in refining the tools. Then submit to Y-journal.

However, when it comes to CS, things are often less clear. This is in part because of the novelty of the subject, and in part due to the situation in CS theory, which is in constant flux and search for direction (a short Wikipedia article is as rather vague and unhelpful, even more so than these generic WP articles tend to be).

The point of this post is to introduce/describe the area of “Computational Combinatorics“. Although Google returns 20K hits for this term (including experts, courses, textbooks), the meaning is either obscure or misleading. We want to clarify what we mean, critique everyone else, and make a stake for the term!

1) What I want computational combinatorics to mean is “theoretical CS aspects of combinatorics” (and to a lesser extend “practical..”), which is essentially part of combinatorics but the tools and statements use compute science terminology (for a concise description of complexity aspects, see dated but excellent survey by David Shmoys and Eva Tardos). I will give a recent example below, but basically if you want to prove a negative result in combinatorics (as in “one should not expect a nice formula for the number of 3-colorings or perfect matchings of a general graph”), then CS language (and basic tools) is a way to go. When people use “computational combinatorics” to mean “basic results in combinatorics that are useful for further studies of computer science”, they are being misleading. A proper name for such course is “Introduction to Combinatorics” or “Combinatorics for Computer Scientists”, etc.

2) In two recent papers, Jed Yang and I proved several complexity results on tilings. To explain them, let me start with the following beautiful result by Éric Rémila, built on earlier papers by Thurston, Conway & Lagarias, and Kenyon & Kenyon:

Tileability of a simply connected region in the plane with two types of rectangles can be decided in polynomial time.

First, we show that when the number of rectangles is sufficiently large (originally about 10⁶, later somewhat decreased), one should not expect such a result. Formally, we prove that tileability is NP-hard in this case. We then show that in 3-dim the topology of the region gives no advantage. Among other results, we prove that tileability of contractible regions with 2x2x1 slabs is
NP-complete, and counting 2x1x1 domino tilings of contractible regions is #P-complete.

Now, the CS Theory point of view on these types of results changed drastically over time. Roughly, 30 years ago they were mainstream. About 20 years ago they were still of interest, but no longer important. Nowadays they are marginal at best – the field has moved on. My point is that the result are of interest in Combinatorics and Combinatorics only. Indeed, it has long been observed that applying combinatorial group theory to tilings (as done by Thurston, Rémila, etc.) is more of an art than a science. Although we believe that already for three general rectangles in the plane the problem is intractable, proving such a result is exceedingly difficult. Our various results solve weak versions of this problem.

3) The ontology (classification) in mathematics has always been a mess (this is not unusual). For example, combinatorial enumeration is the same as enumerative combinatorics. On the other hand, as far as I can tell, analytic geometry has nothing to do with geometric analysis. There is also no “monotonicity” to speak about: even though group theory is a part of algebra, the geometric group theory is neither a part of geometric algebra, nor of algebraic geometry, although traditionally contains combinatorial group theory. Distressingly, there are two completely different (competing) notions of “algebraic combinatorics” (see here and there), and algebraic graph theory which is remarkably connected to both of these. The list goes on.

4) So, why name a field at all, given the mess we have? That’s mostly because we really want to incorporate the CS aspects of combinatorics as a legitimate branch of mathematics. Theory CS is already over the top combinatorial (check out the number of people who believe that P=?NP will be resolved with combinatorics), but when a problem arises in combinatorics from within, this part of combinatorics needs a name to call home. I propose using the term computational combinatorics, in line with computational group theory, computational geometry, computational topology, etc., as a part of the loosely defined computational mathematics. I feel that the adjective “computational” is broad and flexible enough to incorporate both theoretical/complexity aspects as well as some experimental work, and combinatorial software development (as in WZ theory), compared to other adjectives, such as “algorithmic”, “computable”, “effective”, “computer-sciency”, etc. So, please, AMS, next time you revise your MSC, consider adding “Computational Combinatorics” as 05Fxx.

P.S. A well known petition asks for graph theory to have its own MSC code (specifically, 07), due to the heavy imbalance in the number of graph theory vs. the rest of combinatorics papers. Without venturing an opinion, let me mention that perhaps, adding a top level “computational combinatorics” subfield of combinatorics will remedy this as well – surely some papers will migrate there from graph theory. Just a thought…

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 such that , and for , is equal to the total number of partitions of integers into parts .

For example, for the first set is sequences is , while the second of partitions is , 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:

For example, for we get the following bijection:

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.