Who named Catalan numbers?
The question. A year ago, on this blog, I investigated Who computed Catalan numbers. Short version: it’s Euler, but many others did a lot of interesting work soon afterwards. I even made a Catalan Numbers Page with many historical and other documents. But I always assumed that the dubious honor of naming them after Eugène Catalan belongs to Netto. However, recently I saw this site which suggested that it was E.T. Bell who named the sequence. This didn’t seem right, as Bell was both a notable combinatorialist and mathematical historian. So I decided to investigate who did the deed.
First, I looked at Netto’s Lehrbuch der Combinatorik (1901). Although my German is minuscule and based on my knowledge of English and Yiddish (very little of the latter, to be sure), it was clear that Netto simply preferred counting of Catalan’s brackets to triangulations and other equivalent combinatorial interpretations. He did single out Catalan’s work, but mentioned Rodrigues’s work as well. In general, Netto wasn’t particularly careful with the the references, but in fairness neither were were most of his contemporaries. In any event, he never specifically mentioned “Catalan Zahlen”.
Second, I checked the above mentioned 1938 Bell’s paper in the Annals. As I suspected, Bell mentioned “Catalan’s numbers” only in passing, and not in a way to suggest that Catalan invented them. In fact, he used the term “Euler-Segner sequence” and provided careful historical and more recent references.
Next on my list was John Riordan‘s Math Review MR0024411, of this 1948 Motzkin’s paper. The review starts with “The Catalan numbers…”, and indeed might have been the first time this name was introduced. However, it is naive to believe that this MR moved many people to use this expression over arguably more cumbersome “Euler-Segner sequence”. In fact, Motzkin himself is very careful to cite Euler, Cayley, Kirkman, Liouville, and others. My guess is this review was immediately forgotten, but was a harbinger of things to come.
Curiously, Riordan does this again in 1964, in a Math Review on an English translation of a popular mathematics book by A.M. Yglom and I.M. Yaglom (published in Russian in 1954). The book mentions the sequence in the context of counting triangulations of an n-gon, without calling it by any name, but Riordan recognizes them and uses the term “Catalan numbers” in the review.
The answer. To understand what really happened, see this Ngram chart. It clearly shows that the term “Catalan numbers” took off after 1968. What happened? Google Books immediately answers – Riordan’s Combinatorial Identities was published in 1968 and it used “the Catalan numbers”. The term took off and became standard within a few years.
What gives? It seems, people really like to read books. Intentionally or unintentionally, monographs tend to standardize the definitions, notations, and names of mathematical objects. In his notes on Mathematical writing, Knuth mentions that the term “NP-complete problem” became standard after it was used by Aho, Hopcroft and Ullman in their famous Data Structures and Algorithms textbook. Similarly, Macdonald’s Symmetric Functions and Hall Polynomials became a standard source of names of everything in the area, just as Stanley predicted in his prescient review.
The same thing happened to Riordan’s book. Although now may be viewed as tedious, somewhat disorganized and unnecessarily simplistic (Riordan admitted to dislike differential equations, complex analysis, etc.), back in the day there was nothing better. It was lauded as “excellent and stimulating” in P.R. Stein’s review, which continued to say “Combinatorial identities is, in fact, a book that must be read, from cover to cover, and several times.” We are guessing it had a tremendous influence on the field and cemented the terminology and some notation.
In conclusion. We don’t know why Riordan chose the term “Catalan numbers”. As Motzkin’s paper shows, he clearly knew of Euler’s pioneer work. Maybe he wanted to honor Catalan for his early important work on the sequence. Or maybe he just liked the way it sounds. But Riordan clearly made a conscious decision to popularize the term back in 1948, and eventually succeeded.
UPDATE (Feb. 8, 2014) Looks like Henry Gould agrees with me (ht. Peter Luschny). He is, of course, the author of a definitive bibliography of Catalan numbers. Also, see this curious argument against naming mathematical terms after people (ht. Reinhard Zumkeller).
Mathematician’s guide to holidays
Holiday season offers endless opportunities to celebrate, relax, rest, reflect and meditate. Whether you are enjoying a white Christmas or a palm tree Chanukkah, a mathematician in you might wonder if there is more to the story, a rigorous food for thought, if you will. So here is a brief guide to the holidays for the mathematically inclined.
1) Christmas tree lectures
I have my own Christmas tree tradition. Instead of getting one, I watch new Don Knuth‘s “Christmas tree lecture“. Here is the most recent one. But if you have time and enjoy binge-watching here is the archive of past lectures (click on “Computer musings” and select December dates). If you are one of my Math 206 students, compare how Knuth computed the number of spanning trees in a hypercube (in a 2009 lecture) with the way Bernardi did in his elegant paper.
2) Algorithmic version of Fermat’s Christmas theorem
Apparently, Fermat’s theorem on sums of two squares first appeared in Fermat’s long letter to Mersenne, written on Christmas Day (December 25, 1640). For background, see Catalan and French language Wikipedia articles. Zagier’s “one-sentence proof” is well known and available here. Long assumed to be mysterious, it was nicely explained by Elsholtz. Still mysteriously, a related proof also appears in a much earlier paper (in French), by a Russian-American mathematician J. Uspensky (ht. Ustinov). Can somebody explain to me what’s in that paper?
Interestingly, there is a nice polynomial time algorithm to write a prime p=1 mod 4 as a sum of two squares, but I could not find a clean version on the web. If you are curious, start with Cornacchia’s algorithm for more general quadratic Diophantine equations, and read its various proofs (advanced, elementary, short, textbook, in French). Then figure out why Fermat’s special case can be done in (probabilistic) polynomial time.
3) Dreidel game analysis
The dreidel is a well known Chanukkah game with simple rules. Less known is the mathematics behind it. Start with this paper explaining that it’s unfair, and continue to this paper explaining how to fix it (on average). Then proceed to this “squared nuts” conjecture by Zeilberger on the expected length of the game (I have a really good joke here which I will suppress). This conjecture was eventually resolved in this interesting paper, definitely worth $25 promised by Zeilberger.
Now, if you are underwhelmed with the dreidel game, try to prove the festive Star of David Theorem. When you are done, enjoy this ingenious proof, which is definitely “from the book”.
4) Santa Claus vs beautiful mathematics
Most readers of this blog are aware of existence of beautiful mathematics. I can only speculate that a clear majority of them would probably deny the existence of Santa Claus. However, there are millions of (mostly, very young) people who believe the exact opposite on both counts. Having grown up in the land of Ded Moroz, we have little to say on the great Santa debate, but we believe it’s worth carefully examining Santa proponent’s views. Could it be that their arguments can be helpful in our constant struggle to spread the gospel of beautiful mathematics?
We recommend reading “Yes, Virginia, there is Santa Claus“ column (fully available here), which was originally published by the New York Sun in 1897. In fact, read it twice, three times, even four times. I am reluctant to quote from it because it’s short and deserves to be read in full. But note this passage: ”The most real things in the world are those that neither children nor men can see.” The new Jewish editor of the Sun reports that the rabbis he consulted think this is “a joyous articulation of faith”. Maybe. But to me this evokes some beautiful advanced mathematics.
You see, when mathematicians try to explain that mathematics is beautiful, they tend to give simple visually appealing examples (like here). But I suggest closing your eyes and imagining beautiful mathematical objects, such as the 600-cell, Poincaré homolgy sphere, Lie group E8, Monster group, or many other less known higher dimensional constructions such as the associahedron, the Birkhoff polytope, Walz’s flexible cross-polyhedron, etc. Certainly all of these can be seen by “neither children nor men”. Yet we can prove that they “are real”. We can then spend years studying and generalizing them. This knowledge alone can bring joy to every holiday season…
HAPPY HOLIDAYS EVERYONE! С НОВЫМ ГОДОМ!
How many graduate students do we need?
In response to my previous post “Academia is nothing like a drug cartel“, a fellow blogger Adam Sheffer asks:
I was wondering what you think about a claim that I sometimes hear in this context – that one of the problems is that universities train too many Ph.D. students. That with a smaller number of math Ph.D. students the above will be less of a problem, and also that this way there will be a smaller number of people dealing with less “serious/important” topics (whatever this means exactly).
This question is certainly relevant to the “adjunct issue”. I heard it before, but always found it somewhat confusing. Specifically to the US, with its market based system, who exactly is supposed to decrease the number of Ph.D.’s? The student themselves should realize how useless in the doctoral degree and stop applying? The individual professors should refuse to accept graduate students? The universities should do this together, in some kind of union? The government? All these questions are a bit different and need untangling.
I was going to write a brief reply, but after Adam asked this question I found a yet another example of lazy journalism by Slate’s “education columnist” Rebecca Schuman who argues:
It is, simply put, irresponsible to accept so many Ph.D. students when you know graduate teaching may well be the only college teaching they ever do.
Of course, Dr. Schuman already has a Ph.D. (from our neighbor UC Irvine) — she just wants others not get one, perhaps to avoid her own fate of an adjunct at University of Missouri. Needless to say, I cannot disagree more. Let me explain.
Universities are not allowed to form a cartel
Let’s deal with the easy part. If the American universities somehow conspired to limit or decrease the number of graduate students they accepts, this would be a classical example of anti-competitive behavior. Simply put, the academia would form a cartel. A textbook example of a cartel is OPEC which openly conspires to increase or decrease oil production in order to control world energy prices. In the US, such activity is against the law due to to the Sherman Act of 1890, and the government/courts have been ruthless in its application (cf. European law to that effect).
One can argue that universities are non-profit institutions and by definition would not derive profit should they conspire, but the law makes no distinction on this, and this paper (co-authored by the celebrity jurist and economist Richard Posner) supports this approach. And to those who think that only giants such as Standard Oil, AT&T or Microsoft have to worry about anti-trust, the government offers plenty of example of going after small time cartels. A notable recent case is Obama’s FTC going after Music Teachers National Association, who have a non-poaching of music students recommendation in their “code of ethics”. Regardless what you think of that case, it is clear that the universities would never try to limit the number of graduate students in a similar manner.
Labor suppy and demand
As legions before her, Schuman laments that pospective grad students do not listen to “reason”:
Expecting wide-eyed, mind-loving intellectuals to embrace the eventual realities of their situations has not worked—yes, they should know better, but if they listened to reason, they wouldn’t be graduate students in the first place. Institutions do know better, so current Ph.D. recruitment is dripping with disingenuousness.
But can you really be “wide-eyed” in the internet era? There is certainly no shortage of articles by both journalists and academics on the “plight” of academic life – she herself links to sites which seem pretty helpful informing prospective graduate students (yes, even the link to Simpsons is helpful). I have my own favorites: this, that, that and even that. But all of these are misleading at best and ridiculous at worst. When I mentioned them on MO, José Figueroa-O’Farrill called them a “parallel universe”, for a good reason.
You see, in this universe people make (mostly) rational decisions, wide-eyed or not. The internet simply destroyed the information gap. Faced with poor future income prospects, graduate students either choose to go elsewhere or demand better conditions at the universities. Faced with a decreasing pool of candidates the universities make an effort to make their programs more attractive, and strive to expand the applicant pool by reaching out to underrepresented groups, foreign students, etc. Eventually the equilibrium is reached and labor supply meets demand, as it always has. Asking the universities (who “do know better”) to have the equilibrium be reached at a lower point is equivalent to asking that Ph.D. programs become less attractive. And I thought Schuman cares…
Impact of government actions
Now, when it comes to distorting of the labor market, the government is omnipotent and with a single bill can decrease the number of graduate students. Let’s say, the Congress tomorrow enacts a law mandating a minimum wage of $60,000 a year for all graduate students. Of course, large universities have small armies of lawyers and accountants who would probably figure out how to artificially hike up the tuition for graduate students and include it in their income, but let’s assume that the law is written to prevent any loopholes. What would happen next?
Obviously, the universities wouldn’t be able to afford that many graduate graduate students. The number of them will plunge. The universities would have to cut back on the TA/recitation/discussion sessions and probably hire more adjuncts to compensate for the loss. In time, this would lower the quality of education or lead to huge tuition increases, or mostly likely a little bit of both. The top private universities who would want to maintain small classes will become completely unaffordable for the middle class. Meanwhile the poorer state universities will commodify their education by creating huge classes with multiple choice machine testing, SAT-style, and further diminishing student-faculty interaction. In fact, to compensate for their increasing cost to universities, graduate students will be asked to do more teaching, thus extending their time-to-degree and decreasing the graduation rates.
Most importantly, this would probably have no positive effect on decreasing competition for tenure track jobs, since the academic market is international. In other words, a decreasing american supply will be immediately compensated with an increasing european supply aided with inflow from emerging markets (ever increasing in quantity and quality production of Ph.D.’s in Asia). In fact, there is plenty of evidence that this would have sharply negative effect on prospects of American students, as decreased competition would result in weaker research work (see below).
In summary, who exactly would be the winners of this government action? I can think of only one group: lazy journalists who would have many new reasons to write columns complaining about the new status quo.
The out of control academics
Let’s go back to Schuman’s “it is [..] irresponsible to accept so many Ph.D. students” quote I mentioned above, and judge in on moral merits. Irresponsible? Really? You are serious? Is it also irresponsible to give so many football scholarships to college students if only a few of them can make it to the NFL? Is it also irresponsible to have so many acting schools given that so few of the students become movie stars? (see this list in my own little town). In the previous post I already explain how graduate schools are apprenticeship programs. Graduate schools give students a chance and an opportunity to succeed. Some students do indeed, while others move to do something else, sometimes succeeding beyond expectations (see e.g. this humorous list).
What’s worse, Schuman implicitly assumes that the Ph.D. study can only be useful if directly applicable to obtain a professorship. This is plainly false. I notice from her CV that she teaches “The World of Kafka” and “Introduction to German Prose”. Excellent classes I am sure, but how exactly the students are supposed to use this knowledge in real life? Start writing in German or become a literary agent? Please excuse me for being facetious – I hope my point is clear.
Does fewer students means better math? (on average)
In effect, this is Adam’s speculation at the end of his question, as he suggested that perhaps fewer mathematics graduate students would decrease the number of ”less ‘serious/important’ topics”. Unfortunately, the evidence suggests the opposite. When there is less competition, this is a result of fewer rewards and consequently requires less effort to succeed. As a result, the decrease in the number of math graduate students will lead to less research progress and increase in “less important” work, to use the above language.
To see this clearly, think of sports. Compare this list of Russian Major League baseball players with this list by that of Japanese. What explains the disparity? Are more Japanese men born with a gift to play baseball? The answer is obvious. Baseball is not very popular in Russia. Even the best Russian players cannot compete in the american minor leagues. Things are very different in Japan, where baseball is widely popular, so the talented players make every effort to succeed rather than opt for possibly more popular sport (soccer and hockey in Russian case).
So, what can be done, if anything?
To help graduate students, that is. I feel there is a clear need to have more resources on non-academic options available for graduate student (like this talk or this article). Institutionally, we should make it easier to cross register to other schools within the university and the nearby universities. For example, USC graduate students can take UCLA classes, but I have never seen anyone actually doing that. While at Harvard, I took half a dozen classes at MIT – it was easy to cross register and I got full credit.
I can’t think of anything major the universities can do. Government can do miracles, of course…
P.S. I realize that the wage increase argument has a “fighting straw men” feel. However, other government actions interfering with the market are likely to bring similarly large economic distortions of the academic market, with easily predictable negative consequences. I can think of a few more such unfortunate efforts, but the burden is not on me but on “reformers” to propose what exactly do they want the government to do.
P.P.S. We sincerely wish Rebecca Schuman every success in her search for a tenure track appointment. Perhaps, when she gets such a position, she can write another article with a slightly sunnier outlook.
Academia is nothing like a drug cartel
It’s been awhile since I wanted to rant. Since the last post, really. Well, I was busy. But the time has come to write several posts.
This post is about a number of recent articles lamenting the prevalence of low paid adjuncts in many universities. To sensationalize the matter, comparisons were made with drug cartels and Ponzi schemes. Allegedly, this inequality is causing poverty and even homelessness and death. I imagine reading these articles can be depressing, but it’s all a sham. Knowingly or not, the journalists are perpetuating false stereotypes on what professors really do. These journalists seem to be doing their usual lazy work and preying on reader’s compassion and profound misunderstanding of the matter.
Now, if you are reading this blog, I am assuming you know exactly what professors do (Hint: not just teaching). But if you don’t, start with this outline by my old friend Daniel Liberzon, and proceed to review any or all of these links: one, two, three, four. When you are done, we can begin to answer our main semi-serious question:
What is academia, really, if it’s not a drug cartel or a Ponzi scheme?
I can’t believe this trivial question is difficult to some people, and needs a lengthy answer, but here it is anyway.
Academia rewards industriousness and creativity
This might seem obvious – of course it does! These are the main qualities needed to achieve success doing research. But reading the above news reports it might seem that Ph.D. is like a lottery ticket – the winnings are rare and random. What I am trying to say is that academia can be compared with other professions which involve both qualities. To make a point, take sculpture.
There are thousands of professional sculptors in the United States. The figures vary greatly, but same also holds for the number of mathematicians, so we leave it aside. The average salary of sculptors seems to be within reach from average salary in the US, definitely below that of an average person with bachelor degree. On the other hand, top sculptors are all multimillionaires. For example, recently a sculpture by Jeff Koons sold for $58.4 million. But at least it looked nice. I will never understand the success of Richard Serra, whose work is just dreadful. You can see some of his work at UCLA (picture), or at LACMA (picture). Or take a celebrated and much despised 10 million dollar man Dale Chihuly, who shows what he calls “art” just about everywhere… But reasonable people can disagree on this, and who am I to judge anyway? My opinion does not matter, nor is that of almost anyone. What’s important, is that some people with expertise value these creative works enough to pay a lot of money for them. These sculptors’ talent is clearly recognized.
Now, should we believe on the basis of the salary disparity that the sculpture is a Ponzi scheme, with top earners basically robbing all the other sculptors of good living? That would be preposterous, of course. Same with most professors. Just because the general public cannot understand and evaluate their research work and creativity, does not mean it’s not there and should not be valued accordingly.
Academia is a large apprenticeship program
Think of graduate students who are traditionally overworked and underpaid. Some make it to graduate with a Ph.D. and eventually become tenured professors. Many, perhaps most, do not. Sounds like a drug cartel to you? Nonsense! This is exactly how apprenticeships works, and how it’s been working for centuries in every guild. In fact, some modern day guilds don’t pay anything at all.
Students enter the apprenticeship/graduate program in hopes to learn from the teacher/professor and succeed in their studies. The very best do succeed. For example, this list of Rembrant‘s pupils/assistants reads somewhat similar to this list of Hilbert‘s students. Unsurprisingly, some are world famous, while others are completely forgotten. So it’s not about cheap labor as in drug cartels – this is how apprenticeships normally work.
Academia is a big business
Think of any large corporation. The are many levels of management: low, mid, and top-level. Arguably, all tenured and tenure-track faculty are low level managers, chairs and other department officers (DGS, DUS, etc.) are mid-level, while deans, provosts and presidents/chancellors are top-level managers. In the US, there is also a legal precedent supporting qualifying professors as management (e.g. professors are not allowed to unionize, in contrast with the adjunct faculty). And deservingly so. Professors hire TA’s, graders, adjuncts, support stuff, choose curriculum, responsible for all grades, run research labs, serve as PI’s on federal grants, and elect mid-level management.
So, why many levels? Take UCLA. According to 2012 annual report, we operate on 419 acres, have about 40 thousand students, 30 thousand full time employees (this includes UCLA hospitals), have $4.6 billion in operating revenue (of which tuition is only $580 million), but only about 2 thousand ladder (tenure and tenure-track) faculty. For comparison, a beloved but highly secretive Trader Joe’s company has about $8 billion in revenue, over 20 thousand employees, and about 370 stores, each with 50+ employees and its own mid and low-level management.
Now that you are conditioned to think of universities as businesses and professors as managers, is it really all that surprising that regular employees like adjuncts get paid much less? This works the same way as for McDonalds store managers, who get paid about 3 times as much as regular employees.
Higher echelons of academia is a research factory with a side teaching business
Note that there is a reason students want to study at research universities rather than at community colleges. It’s because these universities offer many other more advanced classes, research oriented labs, seminars, field works, etc. In fact, research and research oriented teaching is really the main business rather than service teaching.
Think revenue. For example, UCLA derives 50% more revenue from research grants than from tuition. Places like MIT are giving out so many scholarships, they are loosing money on teaching (see this breakdown). American universities cannot quit the undergraduate education, of course, but they are making a rational decision to outsource the low level service teaching to outsiders, who can do the same work but cheaper. For example, I took English in Moscow, ESL at a community college in Brooklyn, French at Harvard, and Hebrew at University of Minnesota. While some instructors were better than others, there was no clear winner as experience was about the same.
So not only the adjunct salaries are low for a reason, keeping them low is critical to avoid hiring more regular faculty and preventing further tuition inflation. The next time you read about adjuncts barely making a living wage, compare this to notorious Bangalore call centers and how much people make over there (between $100 and $250 a month).
Academia is a paradise of equality
College professors are different from drug gangsters not only in the level of violence, but also in a remarkable degree of equality between universities (but not between fields!) Consider for example this table of average full professor salaries at the top universities. The near $200,000 a year may seem high, but note that this is only twice that of average faculty at an average college. Given that most of these top universities are located in the uber-expensive metropolitan areas (NYC, Boston, San Francisco, Los Angeles, etc.), the effect is even further diminished.
Compare this with other professions. Forget the sculptors mentioned above whose pay ratios can go into thousands, let’s take a relatively obscure profession of an opera singer (check how many do you know from this list). Like academia and unlike sculpture, the operas are greatly subsidized by the governments and large corporations. Still, perhaps unsurprisingly, there is a much greater inequality than in academia. While some popular singers like Dmitri Hvorostovsky make over $3 million a year, the average salary is about $100,000 a year, giving a ratio of 30+.
In other words, given that some professors are much better than others when it comes to research (not me!), one can argue that they are being underpaid to subsidize the lackluster efforts of others. No wonder the top academics suffer from the status-income disequilibrium. This is the opposite of the “winner takes all” behavior argued by the journalists in an effort to explain adjuncts’ plight.
Academia is an experience
People come to universities to spend years studying, and they want to enjoy those years. They want to hear famous authors and thinkers, learn basic skills and life changing stories, make lasting friendships, play sports and simply have fun. Sometimes this does not work out, but we are good at what we do (colleges have been perfecting their craft for hundreds of years). Indeed, many students take away with them a unique deeply personal experience. Take my story. While at Moscow University, I heard lectures by Vladimir Arnold, attended Gelfand’s Seminar, and even went to a public lecture by President Roh Tae-woo. It was fun. While at Harvard, I took courses of Raoul Bott and Gian-Carlo Rota (at MIT), audited courses of such non-math luminaries as Stephan Thernstrom and William Mills Todd, III, and went to public lectures by people like Tim Berners-Lee, all unforgettable.
So this is my big NO to those who want to replace tenured faculty with adjuncts, leveling the academic salaries, and commodifying the education. This just would not work; it is akin to calls for abolition of haute cuisine in favor of more fast food. In fact, nobody really wants to do either of these. The inexpensive education is already readily available in the form of community colleges. In fact, students apply in large numbers trying to get to a place like UCLA, which offers a wide range of programs and courses. And it’s definitely not because of our celebrity adjuncts.
In conclusion
Academia is many things to many people. There are many important reasons why the ladder faculty are paid substantially better than TA’s and adjuncts, reasons both substantive and economical. But at no point does the academia resemble the Ponzi schemes and drug cartels, which are famous for creating the economic devastation and inequality (and, um, illegal). If anything, the academia is the opposite, as it creates economic opportunities and evens the playing field. And to those educational reformers who think they know better: remember, we heard it all before…
Combinatorial briefs
I tend to write longish posts, in part for the sake of clarity, and in part because I can – it is easier to express yourself in a long form. However, the brevity has its own benefits, as it forces the author to give succinct summaries of often complex and nuanced views. Similarly, the lack of such summaries can provide plausible deniability of understanding the basic points you are making.
This is the second time I am “inspired” by the Owl blogger who has a Tl;Dr style response to my blog post and rather lengthy list of remarkable quotations that I compiled. So I decided to make the following Readers Digest style summaries of this list and several blog posts.
1) Combinatorics has been sneered at for decades and struggled to get established
In the absence of History of Modern Combinatorics monograph, this is hard to prove. So here are selected quotes, from the above mentioned quotation page. Of course, one should reade them in full to appreciate and understand the context, but for our purposes these will do.
Combinatorics is the slums of topology – Henry Whitehead
Scoffers regard combinatorics as a chaotic realm of binomial coefficients, graphs, and lattices, with a mixed bag of ad hoc tricks and techniques for investigating them. [..] Another criticism of combinatorics is that it “lacks abstraction.” The implication is that combinatorics is lacking in depth and all its results follow from trivial, though possible elaborate, manipulations. This argument is extremely misleading and unfair. – Richard Stanely (1971)
The opinion of many first-class mathematicians about combinatorics is still in the pejorative. While accepting its interest and difficulty, they deny its depth. It is often forcefully stated that combinatorics is a collection of problems which may be interesting in themselves but are not linked and do not constitute a theory. – László Lovász (1979)
Combinatorics [is] a sort of glorified dicethrowing. – Robert Kanigel (1991)
This prejudice, the view that combinatorics is quite different from ‘real mathematics’, was not uncommon in the twentieth century, among popular expositors as well as professionals. – Peter Cameron (2001)
Now that the readers can see where the “traditional sensitivities” come from, the following quote must come as a surprise. Even more remarkable is that it’s become a conventional wisdom:
Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics. – John Stillwell (2010)
Of course, the prejudice has never been limited to Combinatorics. Imagine how an expert in Partition Theory and q-series must feel after reading this quote:
[In the context of Partition Theory] Professor Littlewood, when he makes use of an algebraic identity, always saves himself the trouble of proving it; he maintains that an identity, if true, can be verified in a few lines by anybody obtuse enough to feel the need of verification. – Freeman Dyson (1944), see here.
2) Combinatorics papers have been often ostracized and ignored by many top math journals
This is a theme in this post about the Annals, this MO answer, and a smaller theme in this post (see Duke paragraph). This bias against Combinatorics is still ongoing and hardly a secret. I argue that on the one hand, the situation is (slowly) changing for the better. On the other hand, if some journals keep the proud tradition of rejecting the field, that’s ok, really. If only they were honest and clear about it! To those harboring strong feelings on this, listening to some breakup music could be helpful.
3) Despite inherent diversity, Combinatorics is one field
In this post, I discussed how I rewrote Combinatorics Wikipedia article, largely as a collection of links to its subfields. In a more recent post mentioned earlier I argue why it is hard to define the field as a whole. In many ways, Combinatorics resembles a modern nation, united by a language, culture and common history. Although its borders are not easy to define, suggesting that it’s not a separate field of mathematics is an affront to its history and reality (see two sections above). As any political scientist will argue, nation borders can be unhelpful, but are here for a reason. Wishing borders away is a bit like French ”race-ban“ – an imaginary approach to resolve real problems.
Gowers’s “two cultures” essay is an effort to describe and explain cultural differences between Combinatorics and other fields. The author should be praised both for the remarkable essay, and for the bravery of raising the subject. Finally, on the Owl’s attempt to divide Combinatorics into “conceptual” which “has no internal reasons to die in any foreseeable future” and the rest, which “will remain a collection of elementary tricks, [..] will die out and forgotten [sic].” I am assuming the Owl meant here most of the “Hungarian combinatorics”, although to be fair, the blogger leaves some wiggle room there. Either way, “First they came for Hungarian Combinatorics” is all that came to mind.
What do math journals do? What will become of them in the future?
Recently, there has been plenty of discussions on math journals, their prices, behavior, technology and future. I have been rather reluctant to join the discussion in part due to my own connection to Elsevier, in part because things in Combinatorics are more complicated than in other areas of mathematics (see below), but also because I couldn’t reconcile several somewhat conflicting thoughts that I had. Should all existing editorial boards revolt and all journals be electronic? Or perhaps should we move to “pay-for-publishing” model? Or even “crowd source refereeing”? Well, now that the issue a bit cooled down, I think I figured out exactly what should happen to math journals. Be patient – a long explanation is coming below.
Quick test questions
I would like to argue that the debate over the second question is the general misunderstanding of the first question in the title. In fact, I am pretty sure most mathematicians are quite a bit confused on this, for a good reason. If you think this is easy, quick, answer the following three questions:
1) Published paper has a technical mistake invalidating the main result. Is this a fault of author, referee(s), handling editor, managing editor(s), a publisher, or all of the above? If the reader find such mistake, who she/he is to contact?
2) Published paper proves special case of a known result published 20 years earlier in an obscure paper. Same question. Would the answer change if the author lists the paper in the references?
3) Published paper is written in a really poor English. Sections are disorganized and the introduction is misleading. Same question.
Now that you gave your answers, ask a colleague. Don’t be surprised to hear a different point of view. Or at least don’t be surprised when you hear mine.
What do referees do?
In theory, a lot. In practice, that depends. There are few official journal guides to referees, but there are several well meaning guides (see also here, here, here, here §4.10, and a nice discussion by Don Knuth §15). However, as any editor can tell you, you never know what exactly did the referee do. Some reply within 5 min, some after 2 years. Some write one negative sentence, some 20 detailed pages, some give an advice in the style “yeah, not a bad paper, cites me twice, why not publish it”, while others a brushoff “not sure who this person is, and this problem is indeed strongly related to what I and my collaborators do, but of course our problems are much more interesting/important - rejection would be best”. The anonymity is so relaxing, doing a poor job is just too tempting. The whole system hinges on the shame, sense of responsibility, and personal relationship with the editor.
A slightly better questions is “What do good referees do?” The answer is – they don’t just help the editor make acceptance/rejection decision. They help the authors. They add some background the authors don’t know, look for missing references, improve on the proofs, critique the exposition and even notation. They do their best, kind of what ideal advisors do for their graduate students, who just wrote an early draft of their first ever math paper.
In summary, you can’t blame the referees for anything. They do what they can and as much work as they want. To make a lame comparison, the referees are like wind and the editors are a bit like sailors. While the wind is free, it often changes direction, sometimes completely disappears, and in general quite unreliable. But sometimes it can really take you very far. Of course, crowd sourcing refereeing is like democracy in the army – bad even in theory, and never tried in practice.
First interlude: refereeing war stories
I recall a curious story by Herb Wilf, on how Don Knuth submitted a paper under assumed name with an obscure college address, in order to get full refereeing treatment (the paper was accepted and eventually published under Knuth’s real name). I tried this once, to unexpected outcome (let me not name the journal and the stupendous effort I made to create a fake identity). The referee wrote that the paper was correct, rather interesting but “not quite good enough” for their allegedly excellent journal. The editor was very sympathetic if a bit condescending, asking me not to lose hope, work on my papers harder and submit them again. So I tried submitting to a competing but equal in statue journal, this time under my own name. The paper was accepted in a matter of weeks. You can judge for yourself the moral of this story.
A combinatorialist I know (who shall remain anonymous) had the following story with Duke J. Math. A year and a half after submission, the paper was rejected with three (!) reports mostly describing typos. The authors were dismayed and consulted a CS colleague. That colleague noticed that the three reports were in .pdf but made by cropping from longer files. Turns out, if the cropping is made straightforwardly, the cropped portions are still hidden in the files. Using some hacking software the top portions of the reports were uncovered. The authors discovered that they are extremely positive, giving great praise of the paper. Now the authors believe that the editor despised combinatorics (or their branch of combinatorics) and was fishing for a bad report. After three tries, he gave up and sent them cropped reports lest they think somebody else considers their paper worthy of publishing in the grand old Duke (cf. what Zeilberger wrote about Duke).
Another one of my stories is with the Journal of AMS. A year after submission, one of my papers was rejected with the following remarkable referee report which I quote here in full:
The results are probably well known. The authors should consult with experts.
Needless to say, the results were new, and the paper was quickly published elsewhere. As they say, ”resistance is futile“.
What do associate/handling editors do?
Three little things, really. They choose referees, read their reports and make the decisions. But they are responsible for everything. And I mean for everything, both 1), 2) and 3). If the referee wrote a poorly researched report, they should recognize this and ignore it, request another one. They should ensure they have more than one opinion on the paper, all of them highly informed and from good people. If it seems the authors are not aware of the literature and referee(s) are not helping, they should ensure this is fixed. It the paper is not well written, the editors should ask the authors to rewrite it (or else). At Discrete Mathematics, we use this page by Doug West, as a default style to math grammar. And if the reader finds a mistake, he/she should first contact the editor. Contacting the author(s) is also a good idea, but sometimes the anonymity is helpful – the editor can be trusted to bring bad news and if possible, request a correction.
B.H. Neumann described here how he thinks the journal should operate. I wish his views held widely today. The book by Krantz, §5.5, is a good outline of the ideal editorial experience, and this paper outlines how to select referees. However, this discussion (esp. Rick Durrett’s “rambling”) is more revealing. Now, the reason most people are confused as to who is responsible for 1), 2) and 3), is the fact that while some journals have serious proactive editors, others do not, or their work is largely invisible.
What do managing editors and publishers do?
In theory, managing editors hire associate editors, provide logistical support, distribute paper load, etc. In practice they also serve as handling editors for a large number of papers. The publishers… You know what the publishers do. Most importantly, they either pay editors or they don’t. They either charge libraries a lot, or they don’t. Publishing is a business, after all…
Who wants free universal electronic publishing?
Good mathematicians. Great mathematicians. Mathematicians who write well and see no benefit in their papers being refereed. Mathematicians who have many students and wish the publishing process was speedier and less cumbersome, so their students can get good jobs. Mathematicians who do not value the editorial work and are annoyed when the paper they want to read is “by subscription only” and thus unavailable. In general, these are people who see having to publish as an obstacle, not as a benefit.
Who does not want free universal electronic publishing?
Publishers (of course), libraries, university administrators. These are people and establishments who see value in existing order and don’t want it destroyed. Also: mediocre mathematicians, bad mathematicians, mathematicians from poor countries, mathematicians who don’t have access to good libraries (perhaps, paradoxically). In general, people who need help with their papers. People who don’t want a quick brush-off ”not good enough” or “probably well known”, but those who need advice on the references, on their English, on how the papers are structured and presented, and on what to do next.
So, who is right?
Everyone. For some mathematicians, having all journals to be electronic with virtually no cost is an overall benefit. But at the very least, “pro status quo” crowd have a case, in my view. I don’t mean that Elsevier pricing policy is reasonable, I am talking about the big picture here. In a long run, I think of journals as non-profit NGO‘s, some kind of nerdy versions of Nobel Peace Prize winning Médecins Sans Frontières. While I imagine that in the future many excellent top level journals will be electronic and free, I also think many mid-level journals in specific areas will be run by non-profit publishers, not free at all, and will employ a number of editorial and technical stuff to help the authors, both of papers they accept and reject. This is a public service we should strive to perform, both for the sake of those math papers, and for development of mathematics in other countries.
Right now, the number of mathematicians in the world is already rather large and growing. Free journals can do only so much. Without high quality editors paid by the publishers, with a large influx of papers from the developing world, there is a chance we might loose the traditional high standards for published second tier papers. And I really don’t want to think of a mathematics world once the peer review system is broken. That’s why I am not in the “free publishing camp” – in an effort to save money, we might loose something much more valuable – the system which gives foundation and justification of our work.
Second interlude: journals vis-à-vis combinatorics
I already wrote about the fate of combinatorics papers in the Annals, especially when comparison with Number Theory. My view was gloomy but mildly optimistic. In fact, since that post was written couple more combinatorics papers has been accepted. Good. But let me give you a quiz. Here are two comparable highly selective journals – Duke J. Math. and Composito Math. In the past 10 years Composito published exactly one (!) paper in Combinatorics (defined as primary MSC=05), of the 631 total. In the same period, Duke published 8 combinatorics papers of 681 total.
Q: Which of the two (Composito or Duke) treats combinatorics papers better?
A: Composito, of course.
The reasoning is simple. Forget the anecdotal evidence in the previous interlude. Just look at the “aim and scope” of the journals vs. these numbers. Here is what Compsito website says with a refreshing honesty:
By tradition, the journal published by the foundation focuses on papers in the main stream of pure mathematics. This includes the fields of algebra, number theory, topology, algebraic and analytic geometry and (geometric) analysis. Papers on other topics are welcome if they are of interest not only to specialists.
Translation: combinatorics papers are not welcome (as are papers in many other fields). I think this is totally fair. Nothing wrong with that. Clearly, there are journals which publish mostly in combinatorics, and where papers in none of these fields would be welcome. In fact there is a good historical reason for that. Compare this with what Duke says on its website:
Published by Duke University Press since its inception in 1935, the Duke Mathematical Journal is one of the world’s leading mathematical journals. Without specializing in a small number of subject areas, it emphasizes the most active and influential areas of current mathematics.
See the difference? They don’t name their favorite areas! How are the authors supposed to guess which are these? Clearly, Combinatorics with its puny 1% proportion of Duke papers is not a subject area that Duke “emphasizes”. Compare it with 104 papers in Number Theory (16%) and 124 papers in Algebraic Geometry (20%) over the same period. Should we conclude that in the past 10 years, Combinatorics was not “the most active and influential”, or perhaps not “mathematics” at all? (yes, some people think so) I have my own answer to this question, and I bet so do you…
Note also, that things used to be different at Duke. For example, exactly 40 years earlier, in the period 1963-1973, Duke published 47 papers in combinatorics out of 972 total, even though the area was only in its first stages of development. How come? The reason is simple: Leonard Carlitz was Managing Editor at the time, and he welcomed papers from a number of prominent combinatorialists active during that time, such as Andrews, Gould, Moon, Riordan, Stanley, Subbarao, etc., as well as a many of his own papers.
So, ideally, what will happen to math journals?
That’s actually easy. Here are my few recommendations and predictions.
1) We should stop with all these geography based journals. That’s enough. I understand the temptation for each country, or university, or geographical entity to have its own math journal, but nowadays this is counterproductive and a cause for humor. This parochial patriotism is perhaps useful in sports (or not), but is nonsense in mathematics. New journals should emphasize new/rapidly growing areas of mathematics underserved by current journals, not new locales where printing presses are available.
2) Existing for profit publishers should realize that with the growth of arXiv and free online competitors, their business model is unsustainable. Eventually all these journals will reorganize into a non-profit institutions or foundations. This does not mean that the journals will become electronic or free. While some probably will, others will remain expensive, have many paid employees (including editors), and will continue to provide services to the authors, all supported by library subscriptions. These extra services are their raison d’être, and will need to be broadly advertised. The authors would learn not to be surprised of a quick one line report from free journals, and expect a serious effort from “expensive journals”.
3) The journals will need to rethink their structure and scope, and try to develop their unique culture and identity. If you have two similar looking free electronic journals, which do not add anything to the papers other than their .sty file, the difference is only the editorial board and history of published papers. This is not enough. All journals, except for the very top few, will have to start limiting their scope to emphasize the areas of their strength, and be honest and clear in advertising these areas. Alternatively, other journals will need to reorganize and split their editorial board into clearly defined fields. Think Proc. LMS, Trans. AMS, or a brand new Sigma, which basically operate as dozens of independent journals, with one to three handling editors in each. While highly efficient, in a long run this strategy is also unsustainable as it leads to general confusion and divergence in the quality of these sub-journals.
4) Even among the top mathematicians, there is plenty of confusion on the quality of existing mathematics journals, some of which go back many decades. See e.g. a section of Tim Gowers’s post about his views of the quality of various Combinatorics journals, since then helpfully updated and corrected. But at least those of us who have been in the area for a while, have the memory of the fortune of previously submitted papers, whether our own, or our students, or colleagues. A circumstantial evidence is better than nothing. For the newcomers or outsiders, such distinctions between journals are a mystery. The occasional rankings (impact factor or this, whatever this is) are more confusing than helpful.
What needs to happen is a new system of awards recognizing achievements of individual journals and/or editors, in their efforts to improve the quality of the journals, attracting top papers in the field, arranging fast refereeing, etc. Think a mixture of Pulitzer Prize and J.D. Power and Associates awards – these would be a great help to understand the quality of the journals. For example, the editors of the Annals clearly hustled to referee within a month in this case (even if motivated by PR purposes). It’s an amazing speed for a technical 50+ page paper, and this effort deserves recognition.
Full disclosure: Of the journals I singled out, I have published once in both JAMS and Duke. Neither paper is in Combinatorics, but both are in Discrete Mathematics, when understood broadly.
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.
UPDATE (May 29, 2013)
I thought I would add a link to this article by Gian-Carlo Rota, titled “What ‘is’ mathematics?”
This was originally distributed by email on October 7, 1998. For those too young to remember the Fall of 1998, Bill Clinton’s testimony was released on September 21, 1998, with its infamous ”It depends on what the meaning of the word ‘is’ is” quote. Rota’s email never mentions this quote, but is clearly influenced by it.
