### Archive

Archive for the ‘Mathematics’ Category

## What if math dies?

April 7, 2019 2 comments

Over the years I’ve heard a lot about the apparent complete uselessness and inapplicability of modern mathematics, about how I should always look for applications since without them all I am doing is a pointless intellectual pursuit, blah, blah, blah.  I had strangers on the plane telling me this (without prompting), first dates (never to become second dates) wondering if “any formulas changed over the last 100 years, and if not what’s the point“, relatives asking me if I ever “invented a new theorem“, etc.

For whatever reason, everyone always has an opinion about math.  Having never been accused of excessive politeness I would always abruptly change the subject or punt by saying that the point is “money in my Wells Fargo account“.  I don’t even have a Wells Fargo account (and wouldn’t want one), but what’s a small lie when you are telling a big lie, right?

Eventually, you do develop a thicker skin, I suppose.  You learn to excuse your friends as well meaning but uneducated, journalists as maliciously ignorant, and strangers as bitter over some old math learning experience (which they also feel obliged to inform you about).  However, you do expect some understanding and respect from fellow academics. “Never compare fields” Gian-Carlo Rota teaches, and it’s a good advice you expect sensible people to adhere.  Which brings me to this:

#### The worst idea I’ve heard in a while

In a recent interview with Glenn Loury, a controversial UPenn law professor Amy Wax proposed to reduce current mathematics graduate programs to one tenth or one fifteenth of their current size (start at 54.30, see also partial transcript).  Now, I get it.  He is a proud member of the “intellectual dark web“, while she apparently hates liberal education establishment and wants to rant about it.  And for some reason math got lumped into this discussion.  To be precise, Loury provoked Wax without offering his views, but she was happy to opine in response.  I will not quote the discussion in full, but the following single sentence is revealing and worth addressing:

If we got rid of ninety percent of the math Ph.D. programs, would we really be worse off in any material respect?  I think that’s a serious question.

She followed this up with “I am not advocating of getting rid of a hundred percent of them.”  Uhm, thanks, I guess…

#### The inanity of it all

One is tempted to close ranks and ridicule this by appealing to authority or common sense.  In fact, just about everyone — from Hilbert to Gowers — commented on the importance of mathematics both as an intellectual endeavor and the source of applications.  In the US, we have about 1500-2000 new math Ph.D.’s every year, and according to the AMS survey, nearly all of them find jobs within a year (over 50% in academia, some in the industry, some abroad).

In fact, our math Ph.D. programs are the envy of the world.  For example, of the top 20 schools worldwide between 12 and 15 are occupied by leading US programs depending on the ranking (see e.g. here or there for recent examples, or more elsewhere).  Think about it: math requires no capital investment or infrastructure at all, so with the advent of personal computing, internet and the arXiv, there are little or no entry barriers to the field.  Any university in the world can compete with the US schools, yet we are still on the top of the rankings.  It is bewildering then, why would you even want to kill these super successful Ph.D. programs?

More infrastructurally, if there are drastic cuts to the Ph.D. programs in the US, who would be the people that can be hired to teach mathematics by the thousands of colleges whose students want to be math majors?  The number of the US math majors is already over 40,000 a year and keep growing at over 5% a year driven in part by the higher salary offerings and lifetime income (over that of other majors).  Don’t you think that the existing healthy supply and demand in the market for college math educators already determined the number of math Ph.D.’s we need to produce?

Well, apparently Wax doesn’t need convincing in the importance of math.  “I am the last person to denigrate pure mathematics.  It is a glory of mankind…”   She just doesn’t want people doing new research.  Or something.  As in “enough already.”  Think about it and transfer this thought to other areas.  Say — no new music is necessary — Bach and Drake said it all.  Or — no new art is necessary — Monet and Warhol were so prolific, museums don’t really have space for new works.  Right…

#### Economics matters

Let’s ask a different question: why would you want to close Ph.D. programs when they actually make money?  Take UCLA.  We are a service department, which makes a lot of money from teaching all kinds of undergraduate math courses + research grants both federal, state and industrial.  Annually, we graduate over 600 students with different types of math/stat majors, which constitutes about 1.6% of national output, the most of all universities.

Let’s say our budget is $25 mil (I don’t recall the figures), all paid for. That would be out of UCLA budget of$7.5 billion of which less than 7% are state contributions.  Now compare these with football stadiums costs which are heavily subsidized and run into hundreds of millions of dollars.  If you had to cut the budget, is math where you start?

#### Can’t we just ignore these people?

Well, yes we can.  I am super happy to dismiss hurried paid-by-the-word know-nothing journalists or some anonymous YouTube comments.  But Amy Wax is neither.  She is smart and very accomplished:  summa cum laude from Yale, M.D. cum laude from Harvard Medical School, J.D. from Columbia Law School where she was an editor of Columbia Law Review, argued 15 cases in the US Supreme Court, is a named professor at UPenn Law School, has dozens of published research papers in welfare, labor and family law and economics.  Yep.

One can then argue — she knows a lot of other stuff, but nothing about math.  She is clearly controversial, and others don’t say anything of that nature, so who cares.  That sounds right, but so what?  Being known as controversial is like license to tell “the truth”…  er… what they really think.  Which can include silly things based on no research into our word.  This means there are numerous other people who probably also think that way but are wise enough or polite enough not to say it.  We need to fight this perception!

And yes, sometimes these people get into positions of power and decide to implement the changes.  Two cases are worth mentioning: the University of Rochester failed attempt to close its math Ph.D. program, and the Brown University fiasco.  The latter is well explained in the “Mathematical Apocrypha Redux” (see the relevant section here) by the inimitable Steven Krantz.  Rating-wise, this was a disaster for Brown — just read the Krantz’s description.

The Rochester story is rather well documented and is a good case of study for those feeling too comfortable.  Start with this Notices article, proceed to NY Times, then to protest description, and this followup in the Notices again.  Good news, right?  Well, I know for a fact that other administrators are also making occasional (largely unsuccessful) moves to do this, but I can’t name them, I am afraid.

#### Predictable apocalypse

Let’s take Amy Wax’s proposal seriously, and play out what would happen if 90-93% of US graduate programs in mathematics are closed on January 1, 2020.  By law.  Say, the US Congress votes to deny all federal funds to universities if they maintain a math Ph.D. program, except for the top 15 out of about 180 graduate programs according to US News.  Let’s ignore the legal issues this poses.  Just note that there are various recent and older precedents of federal government interfering with state and private schools (sometimes for a good cause).

Let’s just try to quickly game out what would happen.  As with any post-apocalyptic fiction, I will not provide any proofs or reasoning.  But it’s all “reality based”, as two such events did happened to mathematicians in the last century, one of them deeply affecting me: the German “academic reforms” in late 1930s (see e.g. here or there), and the Russian exodus in early 1990s (see e.g. here or there, or there).  Another personally familiar story is an implosion of mathematics at Bell Labs in late 1990s.  Although notable, it’s on a much smaller scale and to my knowledge has not been written about (see the discussion here, part 6).

First, there will be huge exodus of distinguished mathematics faculty from school outside of the 15 schools.  These include members of the National Academy of Sciences, numerous ICM speakers, other award winners, etc.  Some will move overseas (Canada, Europe, Japan, China, etc.), some will retire, some leave academia.  Some will simply stop doing research given the lack of mathematical activity at the department and no reward for doing research.

Second, outside of top 15, graduate programs in other subjects notice falling applications resulting in their sliding in world ranking.  These include other physical sciences, economics and computer science.  Then biological and social sciences start suffering.  These programs start having their own exodus to top 15 school and abroad.

Third, given the sliding of graduate programs across the board, the undergraduate education goes into decline across the country.  Top US high school students start applying to school abroad. Many eventually choose to stay in these countries who welcome their stem excellence.

Fourth, the hitech, fintech and other science heavy industries move abroad closer to educated employees.  United States loses its labor market dominance and starts bleeding jobs across all industries.   The stocks and housing market dip down.

Fifth, under strong public pressure the apocalyptic law is repealed and all 180 Ph.D. programs are reinstated with both state and federal financial support.  To everyone’s surprise, nobody is moving back.  Turns out, destroying is much faster and easier than rebuilding, as both Germany and Russia discovered back in the 20th century.  From that point on, January 1, 2020 became known as the day the math died.

#### Final message:

Dear Amy Wax and Glenn Loury!  Please admit that you are wrong.  Or at least plead ignorance and ask for forgiveness.  I don’t know if you will ever see this post or have any interest in debating the proposition I quoted, but I am happy to do this with you.  Any time, any place, any style.  Because the future of academia is important to all of us.

## The status quo of math publishing

March 18, 2019 2 comments

We all like the status quo.  It’s one of my favorite statuses…  The status quo is usually excellent or at least good enough.  It’s just so tempting to do nothing at all that we tend to just keep it.  For years and years which turn into decades.  Until finally the time has come to debate it…

Some say the status quo on math publishing is unsustainable.  That the publishers are much too greedy, that we do all the work and pay twice, that we should boycott the most outrageous of these publishers, that the University of California, German, HungaryNorway and Swedish library systems recent decisions are a watershed moment calling for action, etc.  My own institution (UCLA) is actually the leader in the movement.  While I totally agree with the sentiment, I mostly disagree with the boycott(s) as currently practiced and other proposed measures.  It comes from a position of weakness and requires major changes to the status quo.

Having been thinking about this all for awhile, I am now very optimistic.  In fact, there is a way we can use our natural position of strength to achieve all the goals we want while keeping the status quo.  It may seem hard to believe, but with a few simple measures we can get there in a span of a few years.  This post is a long explanation of how and why we do this.

#### What IS the current status quo?

In mathematics, it’s pretty simple.  We, the mathematicians, do most of the work:  produce a decent looking .pdf file, perform a peer review on a largely volunteer basis (some editors do get paid occasionally), disseminate the results as best as we can, and lobby our libraries to buy the journal subscriptions.  The journals collect the copyright forms, make minor edits to the paper to conform to their favorite style, print papers on paper, mail them to the libraries, post the .pdf files on the internet accessible via library website, and charge libraries outrageous fees for these services.  They also have armies of managers, lawyers, shareholders, etc. to protect the status quo.

Is it all good or bad?  It’s mostly good, really.  We want all these basic services, just disagree on the price.  There is an old Russian Jewish proverb, that if a problem can be solved with money — it’s not a real problem but a business expense (here is a modern version).  So we should deal with predatory pricing as a business issue and not get emotional by boycotting selective journals or publishers.  We can argue for price decreases completely rationally, by showing that their product lost 90%, but not all its value, and that it’s in our common interest to devalue it, but not kill it.

#### Why keep the status quo?

This is easy.  We as a community tend to like our journals more than we hate them.  They compete for our papers.  We compete with each other to get published in best places.  This means we as a community know which journals are good, better or best in every area, or in the whole field of mathematics.  This means that each journal has composed the best editorial board it could.  It would be a waste to let this naturally formed structures go.

Now, in the past I strongly criticized top journals, the whole publishing industry, made fun of it, and more recently presented an ethical code of conduct for all journals.   Yet it’s clear that the cost of complete destruction of existing journal nomenclature is too high to pay and thus unlikely to happen.

#### Why changing the status quo is impractical?

Consider the alternatives.  Yes, the editorial board resignations do happen, most recently in the Journal of Algebraic Combinatorics (JACO) which resigned in mass to form a journal named Algebraic Combinatorics (ALCO) But despite laudations, the original journal exists and doing fine or at least ok.  To my dismay and mild disbelief, the new Editorial Board of JACO has some well-known and wildly respected people.  Arguably, this is not the outcome the resigners aimed for (for the record, I published twice in JACO and recently had a paper accepted by ALCO).

Now, at first, starting new journals may seems like a great idea.  Unfortunately, by the conservative nature of academia they always struggle to get off the ground.  Some survive, such as EJC or EJP, have been pioneers in the area, but others are not doing so well.  The fine print is also an issue — the much hyped Pi and Sigma charge $1000 per article for “processing”, whatever that entails. Terry Tao wrote that these journals suggest “alternatives to the status quo”. Maybe. But how exactly is that an improvement? (Again, for the record, I published in both EJC, EJP, and recently in Sigma. No, I didn’t pay, but let me stay on point here — that story can wait for another time.) Other alternatives are even less effective. Boycotting selective publishers gives a free reign to others to charge a lot, at the time when we need a systemic change. I believe that it gives all but the worst publishers the cover they need to survive, while the worst already have enough power to survive and remain in the lead. There is a long argument here I am trying to avoid. Having had it with Mark Wilson, I know it would overwhelm this post. Let me not rebut it thoroughly point-by-point, but present my own vision. #### What can we do? Boycott them all! I mean all non-free journals, at all times, at all cost. By that I don’t mean everyone should avoid submission, refereeing, being on the editorial board. Not at all, rather opposite. Please do NOT boycott anyone specifically, proceed with your work, keep the status quo. What I mean is this. Boycott all non-free journals as a consumer! Do NOT download papers from journal websites. I will give detailed suggestions below, after I explained my rationale. In short, every time you download a paper from the journal website it gives publishers leverage to claim they are indispensable, and gives libraries the fear of faculty revolt if they unsubscribe. They (both the publishers and the libraries) have no idea how little we need the paid journal websites. #### Detailed advice on how to boycott all math journal publishers Follow the following simple rules. On your side as an author, make every(!) paper you ever wrote freely accessible. Not just the latest – all of them! Put them on the arXiv, viXra, your own website, or anywhere you like as long as the search engines can find them. If you don’t know how, ask for help. If you can read this WP blog post, you can also post your papers on some WP site. If you are afraid of the copyright, snap out of it! I do this routinely, of course. Many greats have also done this for all their papers, e.g. Noga Alon and Richard Stanley. Famously, all papers by Paul Erdős are online. So my message for all of you reading this: if you don’t have all your papers free online, go ahead, just post them all! Yes, that means right now! Stop reading and come back when you are done. Now, for reading papers the rules are more complicated. Every time you need to download an article, don’t go to MathSciNet. Instead, google it first. Google Scholar usually gives you multiple options on the download location. Choose the one in the arXiv or author’s website. Done. If you fail, but feel the paper could be available from some nefarious copyright violating websites, consider using Yandex, DuckDuckGo, or other search engines which are less concerned about the copyright. Now, suppose the only location is the journal website. Often, this happens when the paper is old or old-ish, i.e. outside the 4 year sliding window for Elsevier. As far as I am concerned, this part of the publisher is “free” since anyone in the world can download it without charge. Make sure you download the paper without informing your campus library. This is easy off campus — use any browser without remote access (VPN). On campus, use a browser masking your ip address, i.e. the Opera. Now, suppose nothing works. Say, the paper is recent but inaccessible for free. Then email to the authors and request the file of paper. Shame them into putting the paper online while you are at it. Forward them this blog post, perhaps. Suppose now the paper is inaccessible for free, but the authors are non-responsive and unlikely to ever make the paper available. Well, ok — download it from the journal website then via your library. But then be a mensch. Post the paper online. Yes, in violation of copyright. Yes, other people already do it. Yes, everyone is downloading them and would be grateful. No, they won’t fight us all. Finally, suppose you create a course website. Make sure all or at least most of your links are to free version of the articles. Download them all and repost them on your course website so the students can bypass the library redirect. Every bit helps. #### Why would this work? I. Shaming is powerful. Well, in mathematics shaming is widespread and actually works except in some extreme cases. It’s routine, in fact, to shame authors for not filling gaps in their proofs, for not acknowledging priority, or for not retracting incorrect papers (when the authors refuse to do it, the journals can also be shamed). Sometimes the shaming doesn’t work. Here is my own example of shaming fail (rather extreme, unfortunately), turned shaming success on pages of this blog. More broadly, public shaming is one of the key instruments in the 21st century. Mathbabe (who is writing a book about shaming) notably shamed Mochizuki for not traveling around to defend his papers. Harron famously shamed white cis men for working in academia. Again, maybe not in all cases, but in general public shaming works rather well, and there is a lot of shaming happening everywhere. So think about it — what if we can shame every working mathematician into posting all their papers online? We can then convince libraries that we don’t need to renew all our math journal subscriptions since we can function perfectly well without them. Now, we would still want the journal to function, but are prepared to spend maybe 10-15% of the prices that Springer and Elsevier currently charge. Just don’t renew the contract otherwise. Use the savings to hire more postdocs, new faculty, give students more scholarships to travel to conferences, make new Summer research opportunities, etc. #### Why would this work? II. Personal perspective. About a year ago I bought a new laptop and decided to follow some of the rules above as an experiment. The results were surprisingly good. I had to download some old non-free papers from publisher sites maybe about 4-5 times a month. I went to the library about once every couple of months. For new papers, I emailed the authors maybe the total of about once every three months, getting the paper every time. I feel I could have emailed more often, asking for old papers as well. Only occasionally (maybe once a month) I had to resort to overseas paper depositaries, all out of laziness — it’s faster than walking to the library. In summary — it’s already easy to be a research mathematician without paying for journals. In the future, it will get even easier. #### Why would this work? III. Librarian perspective. Imagine you are a head librarian responsible for journal contracts and purchasing. You have access to the download data and you realize that many math journals continue to be useful and even popular. The publishers bring you a similar or possibly more inflated date showing their products in best light. Right now you have no evidence the journals are largely useless are worried about backslash which would happen if you accidentally cut down on popular journals. So you renew just about everything that your library has always been subscribing and skip on subscribing to new journals unless you get special requests for the faculty that you should. Now imagine that in 2-3 years your data suggests rapidly decreasing popularity of the journals. You make a projection that the downloads will decrease by a factor of 10 within a few more years. That frees you from worrying about cancelling subscriptions and gives you strong leverage in negotiating. Ironically that also helps you keeps the status quo — the publishers slash their price but you can keep most of the subscriptions. #### Why would this work? IV. Historical perspective. The history is full of hard fought battles which were made obsolete by cultural and technological changes. The examples include the “war of the currents“, the “war” of three competing NYC subway systems, same with multiple US railroads, the “long-distance price war“, the “browser war” and the “search engine war“. They were all very different and resolved in many different ways, but have two things in common — they were ruthless at the time, and nobody cares anymore. Even the airlines keep slashing prices, making services indistinguishably awful to the point of becoming near-utilities like electric and gas companies. The same will happen to the journal publishing empires. In fact, the necessary technology has been available for awhile — it’s the culture that needs to change. Eventually all existing print journals will become glorified versions of arXiv overlay publications with substantially scaled down stuff and technical production. Not by choice, of course — there is just no money in it. Just like the airline travel — service will get worse, but much cheaper. The publishers will continue to send print copies of journals to a few dozen libraries worldwide which will be immediately put into off-campus underground bunker-like storages as an anti-apocalyptic measure, and since the reader’s demand will be close to nonexistent. They will remain profitable by cutting cost everywhere since apparently this is all we really care about. The publishers already know that they are doomed, they just want to prolong the agony and extract as much rent as they can before turning into public utilities. This is why the Elsevier refuses to budge with the UC and other systems. They realize that publicly slashing prices for one customer today will lead to an avalanche of similar demands tomorrow, so they would rather forgo a few customers than start a revolution which would decimate their journal value in 5 years (duration of the Elsevier contract). None of this is new, of course. Odlyzko described it all back in 1997, in a remarkably prescient yet depressing article. Unfortunately, we have been moving in the wrong direction. Gowers is right that publishers cannot be shamed, but his efforts to shame people into boycotting Elsevier may be misplaced as it continues going strong. The shaming did lead to the continuing conversation and the above mentioned four year sliding window which is the key to my proposal. #### What’s happening now? Why is Elsevier not budging? As everyone who ever asked for a discount knows, you should do this privately, not publicly. Very quietly slashing the prices by a factor of 2, then trying to play the same trick again in 5 years would have been smarter and satisfied everybody. To further help Elsevier hide the losses from shareholders and general public, the library could have used some bureaucratic gimmicks like paying the same for many journals but getting new books for free or something like that. This would further confuse everybody except professional negotiators on behalf of other library systems, thus still helping to push the prices down. But the UC system wanted to lead a revolution with their public demands, so here we are, breaking the status quo for no real reason. There are no winners here. Even my aunt Bella from Odessa who used to take me regularly to Privoz Market to watch her bargain, could have told you that’s exactly what’s going to happen… Again, the result is bad for everybody — the Elsevier would have been happier to get some money — less than the usual amount, but better than nothing given the trivial marginal costs. At the same time, we at UCLA still need the occasional journal access while in the difficult transition period. #### AMS, please step up! There is one more bad actor in the whole publishing drama whose role needs to change. I am speaking about the AMS, which is essentially a giant publishing house with an army of volunteers and a side business of organizing professional meetings. Let’s looks at the numbers, the 2016 annual report (for some reason the last one available). On p.12 we read: of the$31.8 mil operating revenue dues make up about 8%, meetings 4%, while publishing a whopping 68%.  No wonder the AMS is not pushing for changes in current journal pay structure — they are conflicted to the point of being complicit in preserving existing prices.

But let’s dig a little deeper.  On p.16 we see that the journals are fantastically profitable!  They raise $5.2 mil with$1.5 mil in operating expenses, a 247% profit margin.  With margins like that who wants to rock the boat?  Compare this with next item — books.  The AMS made $4.1 mil while spent$3.6 mil.  That’s a healthy 14% profit margin.  Nice, but nothing to write home about.  By its nature, the book market is highly competitive as libraries and individuals have option to buy them or not on a per title basis.  Thus, the competition.

If you think the AMS prices are lower than of other publishers, that’s probably right.  This very dated page by Kirby is helpful.  For example, in 1996, the PTRF (Springer) charged $2100, the Advances (Academic Press, now Elsevier)$1326, the Annals (Princeton Univ. Press) $200, while JAMS only$174.  Still…

What should be done?  Ideally, the AMS should sell its journal business to some university press and invest long-term the sale profits.  That would free it to pursue the widely popular efforts towards free publishing.  In reality that’s unlikely to happen, so perhaps some sort of “Chinese wall” separating journal publishing and the AMS political activities.  This “wall” might already exist, I wouldn’t know.  I am open to suggestions.  Either way, I think the AMS members should brace themselves for the future where the AMS has a little less money.  But since the MathSciNet alone brings 1/3 of the revenue, and other successful products like MathJobs are also money makers, I think the AMS will be fine.

I do have one pet peeve.  The MathSciNet, which is a good product otherwise, should have a “web search” button next to the “article” button.  The latter automatically takes you to the journal website, while the former would search the article on Google Scholar (or Microsoft Academic, I suppose, let the people choose a default).  This would help people circumvent the publishers by cutting down on clicks.

#### What gives?

I have always been a non-believer in boycotts of specific publishers, and I feel the history proved me more right than wrong.  People tend to avoid boycotts when they have significant cost, and without the overwhelming participation boycotts simply don’t work.  Asking people not to submit or referee for the leading journals in their fields is like asking to voluntarily pay higher taxes.  Some do this, of course, but most don’t, even those who generally agree with higher taxes as a good public policy.

In fact, I always thought we need some kind of one-line bill by the US Congress requiring all research made at every publicly funded university being available for free online.  In my conspiratorial imagination, the AMS being a large publisher refused to bring this up in its lobbying efforts, thus nothing ever happened.  While I still think this bill is a good idea, I no longer think it’s a necessary step.

Now I am finally optimistic that the boycott I am proposing is going to succeed.  The (nearly) free publishing is coming!  Please spread the word, everybody!

UPDATE (March 19, 2019):  Mark Wilson has a blog post commenting and clarifying ALCO vs. JACO situation.

## What we’ve got here is failure to communicate

September 14, 2018 21 comments

Here is a lengthy and somewhat detached followup discussion on the very unfortunate Hill’s affair, which is much commented by Tim Gowers, Terry Tao and many others (see e.g. links and comments on their blog posts).  While many seem to be universally distraught by the story and there are some clear disagreements on what happened, there are even deeper disagreements on what should have happened.  The latter question is the subject of this blog post.

Note:  Below we discuss both the ethical and moral aspects of the issue.  Be patient before commenting your disagreements until you finish the reading — there is a lengthy disclaimer at the end.

#### Review process:

1. When the paper is submitted there is a very important email acknowledging receipt of the submission.  Large publishers have systems send such emails automatically.  Until this email is received, the paper is not considered submitted.  For example, it is not unethical for the author to get tired of waiting to hear from the journal and submit elsewhere instead.  If the journal later comes back and says “sorry for the wait, here are the reports”, the author should just inform the journal that the paper is under consideration elsewhere and should be considered withdrawn (this happens sometimes).
2. Similarly, there is a very important email acknowledging acceptance of the submission.  Until this point the editors ethically can do as they please, even reject the paper with multiple positive reports.  Morality of the latter is in the eye of the beholder (cf. here), but there are absolutely no ethical issues here unless the editor violated the rules set up by the journal.  In principle, editors can and do make decisions based on informal discussions with others, this is totally fine.
3. If a journal withdraws acceptance after the formal acceptance email is sent, this is potentially a serious violation of ethical standards.  Major exception: this is not unethical if the journal follows a certain procedural steps (see the section below).  This should not be done except for some extreme circumstances, such as last minute discovery of a counterexample to the main result which the author refuses to recognize and thus voluntarily withdraw the paper.   It is not immoral since until the actual publication no actual harm is done to the author.
4. The next key event is publication of the article, whether online of in print, usually/often coupled with the transfer of copyright.  If the journal officially “withdraws acceptance” after the paper is published without deleting the paper, this is not immoral, but depends on the procedural steps as in the previous item.
5. If a journal deletes the paper after the publication, online or otherwise, this is a gross violation of both moral and ethical standards.  The journals which do that should be ostracized regardless their reasoning for this act.  Major exception: the journal has legal reasoning, e.g. the author violated copyright laws by lifting from another published article as in the Dănuț Marcu case (see below).

#### Withdrawal process:

1.  As we mentioned earlier, the withdrawal of accepted or published article should be extremely rare, only in extreme circumstances such as a major math error for a not-yet-published article or a gross ethical violation by the author or by the handling editor of a published article.
2. For a published article with a major math error or which was later discovered to be known, the journal should not withdraw the article but instead work with the author to publish an erratum or an acknowledgement of priority.  Here an erratum can be either fixing/modifying the results, or a complete withdrawal of the main claim.  An example of the latter is an erratum by Daniel Biss.  Note that the journal can in principle publish a note authored by someone else (e.g. this note by Mnёv in the case of Biss), but this should be treated as a separate article and not a substitute for an erratum by the author.  A good example of acknowledgement of priority is this one by Lagarias and Moews.
3. To withdraw the disputed article the journal’s editorial board should either follow the procedure set up by the publisher or set up a procedure for an ad hoc committee which would look into the paper and the submission circumstances.  Again, if the paper is already published, only non-math issues such as ethical violations by the author, referee(s) and/or handling editor can be taken into consideration.
4. Typically, a decision to form an ad hoc committee or call for a full editorial vote should me made by the editor in chief, at the request of (usually at least two) members of the editorial board.  It is totally fine to have a vote by the whole editorial board, even immediately after the issue was raised, but the threshold for successful withdrawal motion should be set by the publisher or agreed by the editorial board before the particular issue arises.  Otherwise, the decision needs to be made by consensus with both the handling editor and the editor in chief abstaining from the committee discussion and the vote.
5. Examples of the various ways the journals act on withdrawing/retracting published papers can be found in the case of notorious plagiarist Dănuț Marcu.  For example, Geometria Dedicata decided not to remove Marcu’s paper but simply issued a statement, which I personally find insufficient as it is not a retraction in any formal sense.  Alternatively, SUBBI‘s apology is very radical yet the reasoning is completely unexplained. Finally, Soifer’s statement on behalf of Geombinatorics is very thorough, well narrated and quite decisive, but suffers from authoritarian decision making.
6. In summary, if the process is set up in advance and is carefully followed, the withdrawal/retraction of accepted or published papers can be both appropriate and even desirable.  But when the process is not followed, such action can be considered unethical and should be avoided whenever possible.

#### Author’s rights and obligations:

1. The author can withdraw the paper at any moment until publication.  It is also author’s right not to agree to any discussion or rejoinder.  The journal, of course, is under no obligation to ask the author’s permission to publish a refutation of the article.
2. If the acceptance is issued, the author has every right not go along with the proposed quiet withdrawal of the article.  In this case the author might want to consider complaining to the editor in chief or the publisher making the case that the editors are acting inappropriately.
3. Until acceptance is issued, the author should not publicly disclose the journal where the paper is submitted, since doing so constitutes a (very minor) moral violation.  Many would disagree on this point, so let me elaborate.  Informing the public of the journal submission is tempting people in who are competition or who have a negative opinion of the paper to interfere with the peer review process.  While virtually all people virtually all the time will act honorably and not contact the journal, such temptation is undesirable and easily avoidable.
4. As soon as the acceptance or publication is issued, the author should make this public immediately, by the similar reasoning of avoiding temptation by the third parties (of different kind).

#### Third party outreach:

1.  If the paper is accepted but not yet published, reaching out to the editor in chief by a third party requesting to publish a rebuttal of some kind is totally fine.  Asking to withdraw the paper for mathematical reasons is also fine, but should provide a clear formal math reasoning as in “Lemma 3 is false because…”  The editor then has a choice but not an obligation to trigger the withdrawal process.
2. Asking to withdraw the not-yet-published paper without providing math reasoning, but saying something like “this author is a crank” or “publishing this paper will do bad for your reputation” is akin to bullying and thus a minor ethical violation.  The reason it’s minor is because it is journal’s obligations to ignore such emails.  Journal acting on such an email with rumors or unverified facts is an ethical violation on its own.
3. If a third party learns about a publicly available paper which may or may not be an accepted submission with which they disagree for math or other reason, it it ethical to contact the author directly.  In fact, in case of math issues this is highly desirable.
4. If a third party learns about a paper submission to a journal without being contacted to review it, and the paper is not yet accepted, then contacting the journal is a strong ethical violation.  Typically, the journal where the paper is submitted it not known to public, so the third party is acting on the information it should not have.  Every such email can be considered as an act of bullying no matter the content.
5. In an unlikely case everything is as above but the journal’s name where the paper is submitted is publicly available, the third party can contact the journal.  Whether this is ethical or not depends on the wording of the email.  I can imagine some plausible circumstances when e.g. the third party knows that the author is Dănuț Marcu mentioned earlier.  In these rare cases the third party should make every effort to CC the email to everyone even remotely involved, such as all authors of the paper, the publisher, the editor in chief, and perhaps all members of the editorial board.  If the third party feels constrained by the necessity of this broad outreach then the case is not egregious enough, and such email is still bullying and thus unethical.
6. Once the paper is published anyone can contact the journal for any reason since there is little can be done by the journal beyond what’s described above.  For example, on two different occasions I wrote to journals pointing out that their recently published results are not new and asking them to inform the authors while keeping my anonymity.  Both editors said they would.  One of the journals later published an acknowledgement of retribution.  The other did not.

#### Editor’s rights and obligations:

1. Editors have every right to encourage submissions of papers to the journal, and in fact it’s part of their job.  It is absolutely ethical to encourage submissions from colleagues, close relatives, political friends, etc.  The publisher should set up a clear and unobtrusive conflict of interest directive, so if the editor is too close to the author or the subject he or she should transfer the paper to the editor in chief who will chose a different handling editor.
2. The journal should have a clear scope worked out by the publisher in cooperation with the editorial board.  If the paper is outside of the scope it should be rejected regardless of its mathematical merit.  When I was an editor of Discrete Mathematics, I would reject some “proofs” of the Goldbach conjecture and similar results based on that reasoning.  If the paper prompts the journal to re-evaluate its scope, it’s fine, but the discussion should involve the whole editorial board and irrespective of the paper in question.  Presumably, some editors would not want to continue being on the board if the journal starts changing direction.
3. If the accepted but not yet published paper seems to fall outside of the journal’s scope, other editors can request the editor in chief to initiate the withdrawal process discussed above.  The wording of request is crucial here – if the issue is neither the the scope nor the major math errors, but rather the weakness of results, then this is inappropriate.
4. If the issue is the possibly unethical behavior of the handling editor, then the withdrawal may or may not be appropriate depending on the behavior, I suppose.  But if the author was acting ethically and the unethical behavior is solely by the handling editor, I say proceed to publish the paper and then issue a formal retraction while keeping the paper published, of course.

#### Complaining to universities:

1. While perfectly ethical, contacting the university administration to initiate a formal investigation of a faculty member is an extremely serious step which should be avoided if at all possible.  Except for the egregious cases of verifiable formal violations of the university code of conduct (such as academic dishonesty), this action in itself is akin to bullying and thus immoral.
2. The code of conduct is usually available on the university website – the complainer would do well to consult it before filing a complaint.  In particular, the complaint would typically be addressed to the university senate committee on faculty affairs, the office of academic integrity and/or dean of the faculty.  Whether the university president is in math or even the same area is completely irrelevant as the president plays no role in the working of the committee.  In fact, when this is the case, the president is likely to recuse herself or himself from any part of the investigation and severe any contacts with the complainer to avoid appearance of impropriety.
3. When a formal complaint is received, the university is usually compelled to initiate an investigation and set up an ad hoc subcommittee of the faculty senate which thoroughly examines the issue.  Faculty’s tenure and life being is on the line.  They can be asked to retain legal representation and can be prohibited from discussing the matters of the case with outsiders without university lawyers and/or PR people signing on every communication.  Once the investigation is complete the findings are kept private except for administrative decisions such as firing, suspension, etc.  In summary, if the author seeks information rather than punishment, this is counterproductive.

#### Complaining to institutions:

1. I don’t know what to make of the alleged NSF request, which could be ethical and appropriate, or even common.   Then so would be complaining to the NSF on a publicly available research product supported by the agency.  The issue is the opposite to that of the journals — the NSF is a part of the the Federal Government and is thus subject to a large number of regulations and code of conduct rules.  These can explain its request.  We in mathematics are rather fortunate that our theorems tend to lack any political implications in the real world.  But perhaps researchers in Political Science and Sociology have different experiences with granting agencies, I wouldn’t know.
2. Contacting the AMS can in fact be rather useful, even though it currently has no way to conduct an appropriate investigation.  Put bluntly, all parties in the conflict can simply ignore AMS’s request for documents.  But maybe this should change in the future.  I am not a member of the AMS so have no standing in telling it what to do, but I do have some thoughts on the subject.  I will try to write them up at some point.

#### Public discourse:

1. Many commenters on the case opined that while deleting a published paper is bad (I am paraphrasing), but the paper is also bad for whatever reason (politics, lack of strong math, editor’s behavior, being out of scope, etc.)  This is very unfortunate.  Let me explain.
2. Of course, discussing math in the paper is perfectly ethical: academics can discuss any paper they like, this can be considered as part of the job.  Same with discussing the scope of the paper and the verifiable journal and other party actions.
3. Publicly discussing personalities and motivation of the editors publishing or non-publishing, third parties contacting editors in chief, etc. is arguably unethical and can be perceived as borderline bullying.  It is also of questionable morality as no complete set of facts are known.
4. So while making a judgement on the journal conduct next to the judgement on the math in the paper is ethical, it seems somewhat immoral to me.  When you write “yes, the journals’ actions are disturbing, but the math in the paper is poor” we all understand that while formally these are two separate discussions, the negative judgement in the second part can provide an excuse for misbehavior in the first part.  So here is my new rule:  If you would not be discussing the math in the paper without the pretext of its submission history, you should not be discussing it at all.

#### In summary:

I argue that for all issues related to submissions, withdrawal, etc. there is a well understood ethical code of conduct.  Decisions on who behaved unethically hinge on formal details of each case.  Until these formalities are clarified, making judgements is both premature and unhelpful.

Part of the problem is the lack of clarity about procedural rules by the journals, as discussed above.  While large institutions such as major universities and long established journal publishers do have such rules set up, most journals tend not to disclose them, unfortunately.  Even worse, many new, independent and/or electronic journals have no such rules at all.  In such environment we are reduced to saying that this is all a failure to communicate.

#### Lengthy disclaimer:

1. I have no special knowledge of what actually happened to Hill’s submission.  I outlined what I think should have happened in different scenarios if all participants acted morally and ethically (there are no legal issues here that I am aware of).  I am not trying to blame anyone and in fact, it is possible that none of these theoretical scenarios are applicable.  Yet I do think such a general discussion is useful as it distills the arguments.
2. I have not read Hill’s paper as I think its content is irrelevant to the discussion and since I am deeply uninterested in the subject.  I am, however, interested in mathematical publishing and all academia related matters.
3. What’s ethical and what’s moral are not exactly the same.  As far as this post is concerned, ethical issues cover all math research/university/academic related stuff.  Moral issues are more personal and community related, thus less universal perhaps.  In other words, I am presenting my own POV everywhere here.
4. To give specific examples of the difference, if you stole your officemate’s lunch you acted immorally.  If you submitted your paper to two journals simultaneously you acted unethically.  And if you published a paper based on your officemate’s ideas she told you in secret, you acted both immorally and unethically.  Note that in the last example I am making a moral judgement since I equate this with stealing, while others might think it’s just unethical but morally ok.
5. There is very little black & white about immoral/unethical acts, and one always needs to assign a relative measure of the perceived violation.  This is similar to criminal acts, which can be a misdemeanor, a gross misdemeanor, a felony, etc.

## ICM Paper

March 14, 2018 2 comments

Well, I finally finished my ICM paper. It’s only 30 pp, but it took many sleepless nights to write and maybe about 10 years to understand what exactly do I want to say. The published version will be a bit shorter – I had to cut section 4 to satisfy their page limitations.

Basically, I give a survey of various recent and not-so-recent results in Enumerative Combinatorics around three major questions:

(1) What is a formula?
(2) What is a good bijection?
(3) What is a combinatorial interpretation?

Not that I answer these questions, but rather explain how one could answer them from computational complexity point of view. I tried to cover as much ground as I could without overwhelming the reader. Clearly, I had to make a lot of choices, and a great deal of beautiful mathematics had to be omitted, sometimes in favor of the Computational Combinatorics approach. Also, much of the survey surely reflects my own POV on the subject. I sincerely apologize to everyone I slighted and who disagrees with my opinion! Hope you still enjoy the reading.

Let me mention that I will wait for a bit before posting the paper on the arXiv. I very much welcome all comments and suggestions! Post them here or email privately.

P.S. In thinking of how approach this paper, I read a large number of papers in previous ICM proceedings, e.g. papers by Noga Alon, Mireille Bousquet-Mélou, Paul Erdős, Philippe Flajolet, Marc Noy, János Pach, Richard Stanley, Benny Sudakov, and many others. They are all terrific and worth reading even if just to see how the field has been changing over the years. I also greatly benefited from a short introductory article by Doron Zeilberger, which I strongly recommend.

## How to write math papers clearly

July 12, 2017 7 comments

Writing a mathematical paper is both an act of recording mathematical content and a means of communication of one’s work.  In contrast with other types of writing, the style of math papers is incredibly rigid and resistant to even modest innovation.  As a result, both goals suffer, sometimes immeasurably.  The clarity suffers the most, which affects everyone in the field.

Over the years, I have been giving advice to my students and postdocs on how to write clearly.  I collected them all in these notes.  Please consider reading them and passing them to your students and colleagues.

Below I include one subsection dealing with different reference styles and what each version really means.  This is somewhat subjective, of course. Enjoy!

****
4.2. How to cite a single paper. The citation rules are almost as complicated as Chinese honorifics, with an added disadvantage of never being discussed anywhere. Below we go through the (incomplete) list of possible ways in the decreasing level of citation importance and/or proof reliability.

(1) “Roth proved Murakami’s conjecture in [Roth].” Clear.

(2) “Roth proved Murakami’s conjecture [Roth].” Roth proved the conjecture, possibly in a different paper, but this is likely a definitive version of the proof.

(3) “Roth proved Murakami’s conjecture, see [Roth].” Roth proved the conjecture, but [Roth] can be anything from the original paper to the followup, to some kind of survey Roth wrote. Very occasionally you have “see [Melville]”, but that usually means that Roth’s proof is unpublished or otherwise unavailable (say, it was given at a lecture, and Roth can’t be bothered to write it up), and Melville was the first to publish Roth’s proof, possibly without permission, but with attribution and perhaps filling some minor gaps.

(4) “Roth proved Murakami’s conjecture [Roth], see also [Woolf].” Apparently Woolf also made an important contribution, perhaps extending it to greater generality, or fixing some major gaps or errors in [Roth].

(5) “Roth proved Murakami’s conjecture in [Roth] (see also [Woolf]).” Looks like [Woolf] has a complete proof of Roth, possibly fixing some minor errors in [Roth].

(6) “Roth proved Murakami’s conjecture (see [Woolf]).” Here [Woolf] is a definitive version of the proof, e.g. the standard monograph on the subject.

(7) “Roth proved Murakami’s conjecture, see e.g. [Faulkner, Fitzgerald, Frost].” The result is important enough to be cited and its validity confirmed in several books/surveys. If there ever was a controversy whether Roth’s argument is an actual proof, it was resolved in Roth’s favor. Still, the original proof may have been too long, incomplete or simply presented in an old fashioned way, or published in an inaccessible conference proceedings, so here are sources with a better or more recent exposition. Or, more likely, the author was too lazy to look for the right reference, so overcompensated with three random textbooks on the subject.

(8) “Roth proved Murakami’s conjecture (see e.g. [Faulkner, Fitzgerald, Frost]).” The result is probably classical or at least very well known. Here are books/surveys which all probably have statements and/or proofs. Neither the author nor the reader will ever bother to check.

(9) “Roth proved Murakami’s conjecture.7 Footnote 7: See [Mailer].” Most likely, the author never actually read [Mailer], nor has access to that paper. Or, perhaps, [Mailer] states that Roth proved the conjecture, but includes neither a proof nor a reference. The author cannot
verify the claim independently and is visibly annoyed by the ambiguity, but felt obliged to credit Roth for the benefit of the reader, or to avoid the wrath of Roth.

(10) “Roth proved Murakami’s conjecture.7 Footnote 7: Love letter from H. Fielding to J. Austen, dated December 16, 1975.” This means that the letter likely exists and contains the whole proof or at least an outline of the proof. The author may or may not have seen it. Googling will probably either turn up the letter or a public discussion about what’s in it, and why it is not available.

(11) “Roth proved Murakami’s conjecture.7 Footnote 7: Personal communication.” This means Roth has sent the author an email (or said over beer), claiming to have a proof. Or perhaps Roth’s student accidentally mentioned this while answering a question after the talk. The proof
may or may not be correct and the paper may or may not be forthcoming.

(12) “Roth claims to have proved Murakami’s conjecture in [Roth].” Paper [Roth] has a well known gap which was never fixed even though Roth insists on it to be fixable; the author would rather avoid going on record about this, but anything is possible after some wine at a banquet. Another possibility is that [Roth] is completely erroneous as explained elsewhere, but Roth’s
work is too famous not to be mentioned; in that case there is often a followup sentence clarifying the matter, sometimes in parentheses as in “(see, however, [Atwood])”. Or, perhaps, [Roth] is a 3 page note published in Doklady Acad. Sci. USSR back in the 1970s, containing a very brief outline of the proof, and despite considerable effort nobody has yet to give a complete proof of its Lemma 2; there wouldn’t be any followup to this sentence then, but the author would be happy to clarify things by email.

UPDATE 1. (Nov 1, 2017): There is now a video of the MSRI talk I gave based on the article.

UPDATE 2. (Mar 13, 2018): The paper was published in the Journal of Humanistic Mathematics. Apparently it’s now number 5 on “Most Popular Papers” list. Number 1 is “My Sets and Sexuality”, of course.

## Fibonacci times Euler

November 5, 2016 2 comments

Recall the Fibonacci numbers $F_n$ given by 1,1,2,3,5,8,13,21… There is no need to define them. You all know. Now take the Euler numbers (OEIS) $E_n$ 1,1,1,2,5,16,61,272… This is the number of alternating permutations in $S_n$ with the exponential generating function $\sum_{n=0}^\infty E_n t^n/n! = \tan(t)+\sec(t)$.  Both sequences are incredibly famous. Less known are connection between them.

(1) Define the Fibonacci polytope $\Phi_n$ to be a convex hull of  0/1 points in $\Bbb R^n$ with no two 1 in a row. Then  $\Phi_n$ has $F_{n+1}$ vertices and vol$(\Phi_n)=E_n/n!$ This is a nice exercise.

(2) $F_n \cdot E_n \ge n!$ (by just a little). For example, $F_4 \cdot E_4 = 5 \cdot 5 = 25 > 4!$. This follows from the fact that

$F_n \sim \frac{1}{\sqrt{5}} \, \phi^{n+1}$ and $E_n\sim \frac{4}{\pi}\left(\frac{2}{\pi}\right)^{n} n!$, where $\phi=(1+\sqrt{5})/2$ is the golden ratio. Thus, the product $F_n \cdot E_n \sim c n! \left(\frac{2\phi}{\pi}\right)^n$. Since $\pi = 3.14$ and $2\phi = 3.24$, the inequality $F_n \cdot E_n \ge n!$ is easy to see, but still a bit surprising that the numbers are so close.

Together with Greta Panova and Alejandro Morales we wrote a little note “Why is π < 2φ?” which gives a combinatorial proof of (2) via a direct surjection. Thus we obtain an indirect proof of the inequality in the title.  The note is not a research article; rather, it is aimed at a general audience of college students.  We will not be posting it on the arXiv, so I figure this blog is a good place to advertise it.

The note also explains that the inequality (2) also follows from Sidorenko’s theorem on complementary posets. Let me briefly mention a connection between (1) and (2) which is not mentioned in the note.  I will assume you just spent 5 min and read the note at this point.  Following Stanley, the volume of $\Phi_n$ is equal to the volume of the chain polytope (=stable set polytope), see Two Poset Polytopes.  But the latter is exactly the polytope that Bollobás, Brightwell and Sidorenko used in their proof of the upper bound via polar duality.

## The power of negative thinking, part I. Pattern avoidance

May 26, 2015 2 comments

In my latest paper with Scott Garrabrant we disprove the Noonan-Zeilberger Conjecture. Let me informally explain what we did and why people should try to disprove conjectures more often.  This post is the first in a series.  Part II will appear shortly.

#### What did we do?

Let F ⊂ Sk be a finite set of permutations and let Cn(F) denote the number of permutations σ ∈ Sn avoiding the set of patterns F. The Noonan-Zeilbeger conjecture (1996), states that the sequence {Cn(F)} is always P-recursive. We disprove this conjecture.  Roughly, we show that every Turing machine T can be simulated by a set of patterns F, so that the number aof paths of length n accepted by by T is equal to Cn(F) mod 2.  I am oversimplifying things quite a bit, but that’s the gist.

What is left is to show how to construct a machine T such that {an} is not equal (mod 2) to any P-recursive sequence.  We have done this in our previous paper, where give a negative answer to a question by Kontsevich.  There, we constructed a set of 19 generators of GL(4,Z), such that the probability of return sequence is not P-recursive.

When all things are put together, we obtain a set F of about 30,000 permutations in S80 for which {Cn(F)} is non-P-recursive.  Yes, the construction is huge, but so what?  What’s a few thousand permutations between friends?  In fact, perhaps a single pattern (1324) is already non-P-recursive.  Let me explain the reasoning behind what we did and why our result is much stronger than it might seem.

#### Why we did what we did

First, a very brief history of the NZ-conjecture (see Kirtaev’s book for a comprehensive history of the subject and vast references).  Traditionally, pattern avoidance dealt with exact and asymptotic counting of pattern avoiding permutations for small sets of patterns.  The subject was initiated by MacMahon (1915) and Knuth (1968) who showed that we get Catalan numbers for patterns of length 3.  The resulting combinatorics is often so beautiful or at least plentiful, it’s hard to imagine how can it not be, thus the NZ-conjecture.  It was clearly very strong, but resisted all challenges until now.  Wilf reports that Richard Stanley disbelieved it (Richard confirmed this to me recently as well), but hundreds of papers seemed to confirm its validity in numerous special cases.

Curiously, the case of the (1324) pattern proved difficult early on.  It remains unresolved whether Cn(1324) is P-recursive or not.  This pattern broke Doron Zeilberger’s belief in the conjecture, and he proclaimed that it’s probably non-P-recursive and thus NZ-conjecture is probably false.  When I visited Doron last September he told me he no longer has strong belief in either direction and encouraged me to work on the problem.  I took a train back to Manhattan looking over New Jersey’s famously scenic Amtrack route.  Somewhere near Pulaski Skyway I called Scott to drop everything, that we should start working on this problem.

You see, when it comes to pattern avoidance, things move from best to good to bad to awful.  When they are bad, they are so bad, it can be really hard to prove that they are bad.  But why bother – we can try to figure out something awful.  The set of patterns that we constructed in our paper is so awful, that proving it is awful ain’t so bad.

#### Why is our result much stronger than it seems?

That’s because the proof extends to other results.  Essentially, we are saying that everything bad you can do with Turing machines, you can do with pattern avoidance (mod 2).  For example, why is (1324) so hard to analyze?  That’s because it’s even hard to compute both theoretically and experimentally – the existing algorithms are recursive and exponential in n.  Until our work, the existing hope for disproving the NZ-conjecture hinged on finding an appropriately bad set of patterns such that computing {Cn(F)} is easy.  Something like this sequence which has a nice recurrence, but is provably non-P-recursive.  Maybe.  But in our paper, we can do worse, a lot worse…

We can make a finite set of patterns F, such that computing {Cn(F) mod 2} is “provably” non-polynomial (Th 1.4).  Well, we use quotes because of the complexity theory assumptions we must have.  The conclusion is much stronger than non-P-recursiveness, since every P-recursive sequence has a trivial polynomial in n algorithm computing it.  But wait, it gets worse!

We prove that for two sets of patterns F and G, the problem “Cn(F) = Cn(G) mod 2 for all n” is undecidable (Th 1.3).  This is already a disaster, which takes time to sink in.  But then it gets even worse!  Take a look at our Corollary 8.1.  It says that there are two sets of patterns F and G, such that you can never prove nor disprove that Cn(F) = Cn(G) mod 2.  Now that’s what I call truly awful.

#### What gives?

Well, the original intuition behind the NZ-conjecture was clearly wrong.  Many nice examples is not a good enough evidence.  But the conjecture was so plausible!  Where did the intuition fail?  Well, I went to re-read Polya’s classic “Mathematics and Plausible Reasoning“, and it all seemed reasonable.  That is both Polya’s arguments and the NZ-conjecture (if you don’t feel like reading the whole book, at least read Barry Mazur’s interesting and short followup).

Now think about Polya’s arguments from the point of view of complexity and computability theory.  Again, it sounds very “plausible” that large enough sets of patterns behave badly.  Why wouldn’t they?  Well, it’s complicated.  Consider this example.  If someone asks you if every 3-connected planar cubic graph has a Hamiltonian cycle, this sounds plausible (this is Tait’s conjecture).  All small examples confirm this.  Planar cubic graphs do have very special structure.  But if you think about the fact that even for planar graphs, Hamiltonicity is NP-complete, it doesn’t sound plausible anymore.  The fact that Tutte found a counterexample is no longer surprising.  In fact, the decision problem was recently proved to be NP-complete in this case.  But then again, if you require 4-connectivity, then every planar graph has a Hamiltonian cycle.  Confused enough?

Back to the patterns.  Same story here.  When you look at many small cases, everything is P-recursive (or yet to be determined).  But compare this with Jacob Fox’s theorem that for a random single pattern π, the sequence {Cn(π)} grows much faster than originally expected (cf. Arratia’s Conjecture).  This suggests that small examples are not representative of complexity of the problem.  Time to think about disproving ALL conjectures based on that evidence.

If there is a moral in this story, it’s that what’s “plausible” is really hard to judge.  The more you know, the better you get.  Pay attention to small crumbs of evidence.  And think negative!

#### What’s wrong with being negative?

Well, conjectures tend to be optimistic – they are wishful thinking by definition.  Who would want to conjecture that for some large enough a,b,c and n, there exist a solution of an + bn = cn?  However, being so positive has a drawback – sometimes you get things badly wrong.  In fact, even polynomial Diophantine equations can be as complicated as one wishes.  Unfortunately, there is a strong bias in Mathematics against counterexamples.  For example, only two of the Clay Millennium Problems automatically pay \$1 million for a counterexample.  That’s a pity.  I understand why they do this, just disagree with the reasoning.  If anything, we should encourage thinking in the direction where there is not enough research, not in the direction where people are already super motivated to resolve the problem.

In general, it is always a good idea to keep an open mind.  Forget all this “power of positive thinking“, it’s not for math.  If you think a conjecture might be false, ignore everybody and just go for disproof.  Even if it’s one of those famous unsolved conjectures in mathematics.   If you don’t end up disproving the conjecture, you might have a bit of trouble publishing computational evidence.  There are some journals who do that, but not that many.  Hopefully, this will change soon…

#### Happy ending

When we were working on our paper, I wrote to Doron Zeilberger if he ever offered a reward for the NZ-conjecture, and for the disproof or proof only?  He replied with an unusual award, for the proof and disproof in equal measure.  When we finished the paper I emailed to Doron.  And he paid.  Nice… 🙂

## You should watch combinatorics videos!

May 2, 2015 4 comments

Here is my collection of links to Combinatorics videos, which I assembled over the years, and recently decided to publish.  In the past few years the number of videos just exploded.  We clearly live in a new era.  This post is about how to handle the transition.

#### What is this new collection?

I selected over 400 videos of lectures and seminars in Combinatorics, which I thought might be of interest to a general audience.  I tried to cover a large number of areas both within Combinatorics and related fields.  I have seen many (but not all!) of the talks, and think highly of them.  Sometimes I haven’t seen the video, but have heard this talk “live” at the same or a different venue, or read the paper, etc.  I tried to be impartial in my selection, but I am sure there is some bias towards some of my favorite speakers.

The collection includes multiple lectures by Noga Alon, Persi Diaconis, Gil Kalai, Don Knuth, László Lovász, János Pach, Vic Reiner, Paul Seymour, Richard Stanley, Terry Tao, Xavier Viennot, Avi Wigderson, Doron Zeilberger, and many many others. Occasionally the speakers were filmed giving similar talks at different institutions, so I included quick links to those as well so the viewer can choose.

Typically, these videos are from some workshops or public lecture series.  Most are hosted on the institution websites, but a few are on YouTube or Vimeo (some of these are broken into several parts).  The earliest video is from 1992 and the most recent video was made a few days ago.   Almost all videos are from the US or Canada, with a few recent additions from Europe.  I also added links to a few introductory lectures and graduate courses on the bottom of the page.

#### Why now?

Until a couple of years ago, the videos were made only at a few conference centers such as Banff, MSRI and IAS.  The choice was sparse and the videos were easy to find.  The opposite is true now, on both counts.  The number of recorded lectures in all areas is in tens of thousands, they are spread across the globe, and navigating is near impossible unless you know exactly what you are looking for.  In fact, there are so many videos I really struggled with the choice of which to include (and also with which of them qualify as Combinatorics).  I am not sure I can maintain the collection in the future – it’s already getting too big.  Hopefully, some new technology will come along (see below), but for now this will do.

#### Why Combinatorics?

That’s what I do.  I try to think of the area as broad as possible, and apologize in advance if I omitted a few things.  For the subarea division, I used as a basis my own Wikipedia entry for Combinatorics (weirdly, you can listen to it now in a robotic voice).  The content and the historical approach within sub-areas is motivated by my views here on what exactly is Combinatorics.

#### Why should you start watching videos now?

First, because you can.  One of the best things about being in academia is the ability (in fact, necessity) to learn.  You can’t possibly follow everything what happens in all fields of mathematics and even all areas of combinatorics.  Many conferences are specialized and the same people tend to meet a year after year, with few opportunities for outsiders to learn what’s new over there.  Well, now you can.  Just scroll down the list and (hopefully) be amazed at the number of classical works (i.e. over 5 y.o.) you never heard of, the variety of recent developments and connections to other fields.  So don’t just watch people in your area from workshops you missed for some reason.  Explore other areas!  You might be surprised to see some new ideas even on your favorite combinatorial objects.  And if you like what you see, you can follow the links to see other videos from the same workshops, or search for more videos by the same speaker…

Second, you should start watching because it’s a very different experience.  You already know this, of course.  One can pause videos, go back and forward, save the video to watch it again, or stop watching it right in the beginning.  This ability is to popular, Adam Sandler even made an awful movie about it…  On the other hand, the traditional model of lecture attendance is where you either listen intently trying to understand in real time and take notes, or are bored out your mind but can’t really leave.  It still has its advantages, but clearly is not always superior.  Let me elaborate on this below.

#### How to watch videos?

This might seem like a silly question, but give me a chance to suggest a few ideas…

0) Prepare for the lecture.  Make sure to have enough uninterrupted time.  Lock the door.  Turn off the cell phone.  Download and save the video (see below).  Download and save the slides.  Search for them if they are not on the lecture website (some people put them on their home pages).  Never delete anything – store the video on an external hard drive if you are running out of space.  Trust me, you never know when you might need it again, and the space is cheap anyway…

Some years ago I made a mistake by not saving Gil Kalai’s video of a talk titled “Results and Problems around Borsuk’s Conjecture”.  I found it very inspiring — it’s the only talk I referenced it in my book.  Well, apparently, in its infinite wisdom, PIMS lost the video and now only the audio is available, which is nearly useless for a blackboard talk.  What a shame!

1) Use 2 devices.  Have the video on a big screen, say, a large laptop or a TV hooked to your  laptop.  If the TV is too far, use a wireless mouse to operate a laptop from across the room or something like a Google stick to project from a far.  Then, have the slides of the talk opened on your tablet if you like taking computer notes or just like scrolling by hand gestures, or on your other laptop if you don’t.  The slides are almost universally in .pdf and most software including the Adobe Reader allows to take notes straight in the file.

Another reason to have slides opened is the inability for some camera people to understand what needs to be filmed.  This is especially severe if they just love to show the unusual academic personalities, or are used to filming humanities lectures where people read at the podium.  As a result, occasionally, you see them pointing a camera to a slide full of formulas for 2 seconds (and out of focus), and then going back for 2 minutes filming a speaker who is animatedly pointing to the screen (now invisible), explaining the math.  Ugh…

2) If the subject is familiar and you feel bored with the lengthy introduction, scroll the slides until you see something new.  This will give you a hint to where you should go forward in the video.  And if you did miss some definition you can pause the video and scroll the slides to read it.

3) If there are no slides, or you want to know some details which the speaker is purposefully omitting, pause the video and download the paper.  I do this routinely while listening to talks, but many people are too shy to do this out of misplaced fear that others might think they are not paying attention.  Well, there is no one to judge you now.

4) If you are the kind of person who likes to ask questions to clarify things, you still can.  Pause the video and search the web for the answer.  If you don’t find it, ask a colleague by skype, sms, chat, email, whatever.  If everything fails – write to the speaker.  She or he might just tell you, but don’t be surprised if they also ignore your email…

5) If you know others who might be interested in the video lecture, just make it happen.  For example, you can organize a weekly seminar where you and your graduate students watch the lectures you choose (when you have no other speakers).  If students have questions, pause the video and try to answer them.  In principle, if you have a good audience the speaker may agree to answer the questions for 5-10 min over skype, after you are done watching.  Obviously, I’ve never seen this happen (too much coordination?).  But why not try this – I bet if you ask nicely many speakers would agree to this.

6) If you already know a lot about the subject, haven’t been following it recently but want to get an update, consider binge watching.  Pick the most recent lecture series and just let it run when you do house shores or ride a subway.  When things get interesting, you will know to drop everything and start paying attention.

#### Why should you agree to be videotaped?

Because the audience is ready to see your talks now.  Think of this as another way of reaching out with your math to a suddenly much broader mathematical community (remember the “broad impact” section on your NSF grant proposal?).  Let me just say that there is nothing to fear – nobody is expecting you to have acting skills, or cares that you have a terrible haircut.  But if you make a little effort towards giving a good talk, your math will get across and you might make new friends.

Personally, I am extremely uncomfortable being videotaped – the mere knowledge of the camera filming makes me very nervous.  However I gradually (and grudgingly) concluded that this is now a part of the job, and I have to learn how to do this well.  Unfortunately, I am not there yet…

Yes, I realize that many traditionalists will object that “something will be missing” when you start aiming at giving good video talks at the expense of local audience.  But the world is changing if hasn’t changed already and you can’t stop the tide.  This happened before, many times.  For example, at some point all the big Hollywood studios have discovered that they can make movies simpler and make a great deal more money overseas to compensate for the loss in the US market.  They are completely hooked now, and no matter what critics say this global strategy is likely irreversible.  Of course, this leaves a room for a niche market (say, low budget art-house movies), but let’s not continue with this analogy.

#### How to give video lectures?

Most people do nothing special.  Just business as usual, hook up the mike and hope it doesn’t distort your voice too bad.  That’s a mistake.  Let me give a number of suggestions based mostly on watching many bad talks.  Of course, the advice for giving regular talks apply here as well.

0) Find out ahead of time if you get filmed and where the camera is.  During the lecture, don’t run around; try to stand still in full view of the camera and point to the screen with your hands.  Be animated, but without sudden moves.  Don’t use a laser pointer.  Don’t suddenly raise your voice.  Don’t appeal to the previous talks at the same workshop.  Don’t appeal to people in the audience – the camera can rarely capture what they say or do.  If you are asked a question, quickly summarize it so the viewer knows what question you are answering.  Don’t make silly off-the-cuff jokes (this is a hard one).

1) Think carefully whether you want to give a blackboard or a computer talk.  This is crucial.  If it’s a blackboard talk, make sure your handwriting is clear and most importantly BIG.  The cameras are usually in the very back and your handwriting won’t be legible otherwise.  Unless you are speaking the Fields Institute whose technology allows one to zoom into the high resolution video, nobody might be able to see what you write.  Same goes for handwritten slides unless they are very neat, done on a laptop, and the program allows you to increase their size.  Also, the blackboard management becomes a difficult issue.  You should think through what results/definitions should stay on the blackboard visible to the camera at all times and what can be safely deleted or lifted up if the blackboard allows that.

2) If it’s a computer talk, stick to your decision and make a lot of effort to have the slides look good.  Remember, people will be downloading them…  Also, make every effort NOT to answer questions on a blackboard next to the screen.  The lightning never works – the rooms are usually dimmed for a computer talk and no one ever thinks of turning the lights on just for 30 seconds when you explain something.  So make sure to include all your definition, examples, etc, in the slides.  If you don’t want to show some of them – in PowerPoint there is a way to hide them and pull them up only if someone asks to clarify something.  I often prepare the answers to some standard questions in the invisible part of my slides (such as “What happens for other root systems?” or “Do your results generalize to higher dimensions?”), sometimes to unintended comedic effect.  Anyhow, think this through.

3) Don’t give the same videotaped talk twice.  If you do give two or more talks on the same paper, make some substantial changes.  Take Rota’s advice: “Relate to your audience”…  If it’s a colloquium talk, make a broad accessible survey and include your results at the end.  Or, if it’s a workshop talk, try to make an effort to explain most proof ideas, etc.  Make sure to have long self-explanatory talk titles to indicate which talk is which.  Follow the book industry lead for creating subtitles.  For example use “My most recent solution of the Riemann hypothesis, an introduction for graduate students” or “The Pythagorean theorem: How to apply it to the Langlands Program and Quantum Field Theory”.

5) In the future, we would probably need to consider having a general rule about adding a file with errata and clarifications to your talk, especially if something you said is not exactly correct, or even just to indicate, post-factum, whether all these conjectures you mentioned have been resolved and which way.  The viewers would want to know.

For example, my student pointed out to me that in my recent Banff talk, one of my lemmas is imprecise.  Since the paper is already available, this is not a problem, but if it wasn’t this could lead to a serious confusion.

6) Watch other people’s videos.  Pay attention to what they do best.  Then watch your own videos.  I know, it’s painful.  Turn off the sound perhaps.  Still, this might help you to correct the worst errors.

7) For advanced lecturers – try to play with the format.  Of course, the videos allow you to do things you couldn’t do before (like embedding links to papers and other talks, inserting some Java demonstration clips, etc.), but I am talking about something different.  You can turn the lecture into an artistic performance, like this amazing lecture by Xavier Viennot.  Not everyone has the ability or can afford to do this, but having it recorded can make it worthwhile, perhaps.

#### Know your rights

There are some delicate legal issues when dealing with videos, with laws varying in different states in the US (and in other countries, of course).  I am not an expert on any of this and will write only as I understand them in the US.  Please add a comment on this post if you think I got any of this wrong.

1) Some YouTube videos of math lectures look like they have been shut by a phone.  I usually don’t link to those.  As I understand the law on this, anyone can film a public event for his/her own consumption.  However, you and the institution own the copyright so the YouTube posting is illegal without both of yours explicit permission (written and signed).  You can fight this by sending a “cease and desist” letter to the person who posted the video, but contacting YouTube directly might be more efficient – they have a large legal department to sort these issues.

2) You are typically asked to sign away your rights before your talk.  If an institution forgot to do this, you can ask to take your talk down for whatever reason.  However, even if you did sign the paper you can still do this – I doubt the institution will fight you on this just to avoid bad publicity.  A single email to the IT department should suffice.

4)  You can the edit the video by using numerous software, some of which is free to download.  Your can remove the outside noise, make the slides sharper, everything brighter, etc.  I wouldn’t post a heavily edited video when someone else owns a copyright, but a minor editing as above is ok I think.

#### What will happen in the future?

Yes, I will be making some predictions.  Not anything interesting like Gian-Carlo Rota’s effort I recently analyzed, but still…

1) Watching and giving video lectures will become a norm for everyone.  The ethical standards will develop that everyone gets to have the files of videos they made.  Soon enough there will be established some large well organized searchable (and not-for-profit!) math video depositories arXiv-style where you can submit your video and link to it from your website and where others can download from.  Right now companies like DropBox allow you to do this, but it’s for-profit (your have to pay extra for space), and it obviously needs a front like the arXiv.  This would quickly make my collection a thing of the past.

2) Good math videos will become a “work product”, just like papers and books.  It is just another venue to communicate your results and ideas.  People will start working harder on them.  They will become a standard item on CVs, grant applications, job promotions, etc.  More and more people will start referencing them just like I’ve done with Kalai’s talk.  Hopefully part 1) will happen soon enough so all talks get standard and stable links.

3) The video services will become ubiquitous.  First, all conference centers will acquire advanced equipment in the style of the Banff Center which is voice directed and requires no professional involvement except perhaps at the editing stage.  Yes, I am thinking of you, MFO.  A new library is great, but the talks you could have recorded there are priceless – it’s time to embrace the 21st century….

Second, more and more university rooms will be equipped with the cameras, etc.  UCLA already has a few large rooms like that (which is how we make the lamely named BruinCasts), but in time many department will have several such rooms to hold seminars.  The storage space is not an issue, but the labor cost, equipment and the broadband are.  Still, I give it a decade or two…

4) Watching and showing math videos will become a standard part of the research and graduate education.  Ignore the doomsayers who proclaim that this will supplant the traditional teaching (hopefully, not in our lifetime), but it’s clear already there are unexplored educational benefits from this.  This should be of great benefit especially to people in remote locations who don’t have access to such lectures otherwise.  Just like the Wikipedia has done before, this will even the playing field and help the talent to emerge from unlikely places.  If all goes well, maybe the mathematics will survive after all…

Happy watching everyone!

## Grading Gian-Carlo Rota’s predictions

November 27, 2014 3 comments

In this post I will try to evaluate Gian-Carlo Rota‘s predictions on the future of Combinatorics that he made in this 1969 article.  He did surprisingly well, but I am a tough grader and possibly biased about some of the predictions.  Judge for yourself…

#### It’s tough to make predictions, especially about the future

It is a truth universally acknowledged that humans are very interested in predicting the future. They do this incessantly, compiling the lists of the best and the worst, and in general can’t get enough of them. People tend to forget wrong predictions (unless they are outrageously wrong).  This allows a person to make the same improbable predictions over and over and over and over again, making news every time.  There are even professional prognosticators who make a living writing about the future of life and technology.  Sometimes these predictions are rather interesting (see here and there), but even the best ones are more often wrong than right…

Although rarely done, analyzing past predictions is a useful exercise, for example as a clue to the truthiness of the modern day oracles.  Of course, one can argue that many of the political or technology predictions linked above are either random or self-serving, and thus not worth careful investigation. On the other hand, as we will see below, Rota’s predictions are remarkably earnest and sometimes even brave.  And the fact that they were made so long ago makes them uniquely attractive, practically begging to be studied.

Now, it has been 45 years since Rota’s article, basically an eternity in the life span of Combinatorics. There, Rota describes Combinatorics as “the least developed branches of mathematics“. A quick review of the last few quotes on this list I assembled shows how much things have changed. Basically, the area moved from an ad hoc collection of problems to a 360-degree panorama of rapidly growing subareas, each of which with its own deep theoretical results, classical benchmarks, advanced tools and exciting open problems. This makes grading rather difficult, as it suggests that even random old predictions are likely to be true – just about anything people worked on back in the 1960 has been advanced by now. Thus, before turning to Rota, let’s agree on the grading scale.

#### Grading on a curve

To give you the feel for my curve, I will use the celebrated example of the 1899-1901 postcards in the En L’An 2000 French series, which range from insightful to utter nonsense (click on the titles to view the postcards, all available from Wikimedia).

Electric train.  Absolutely.  These were introduced only in 1940s and have been further developed in France among other countries.  Note the aerodynamic shape of the engine.  Grade:  A.

Correspondance cinema.  Both the (silent) cinema and phonograph were invented by 1900; the sound came to movie theaters only in 1927.  So the invention here is of a home theater for movies with sound.  Great prediction although not overly ambitious. Grade:  A-.

Military cyclists.  While bicycle infantry was already introduced in France by 1900, military use of motorcycles came much later.  The idea is natural, but some designs of bikes from WW2 are remarkably similar.  Some points are lost due to the lack of widespread popularity in 2000.  Grade: B+.

Electric scrubbing.  This is an electric appliance for floor cleaning.  Well, they do exist, sort of, obviously based on different principles.  In part due to the modern day popularity, this is solid prediction anyway.  Grade:  B.

Auto-rollers.  Roller skates have been invented in 18th century and by 1900 became popular.  So no credit for the design, but extra credit for believing in the future of the mean of transportation now dominated by rollerblades. Thus the author’s invention is in the category of “motorized personal footwear”. In that case the corresponding modern invention is of the electric skateboard which has only recently become available, post-2000 and yet to become very popular. Grade: B-.

Barber.  The author imagines a barber operating machinery which shaves and cuts customer’s hair.   The design is so ridiculous (and awfully dangerous), it’s a good thing this never came about.  There are however electric shavers and hair cutters which are designed very differently.  Grade:  C.

•  Air cup.  The Wright brothers’ planes had similar designs, so no credit again.  The author assumes that personal air travel will become commonplace, and at low speeds and heights.  This is almost completely false.  However, unfortunately, and hopefully only very occasionally, some pilots do enjoy one for the road.  Grade:  D.

Race in Pacific.  The author imagines that the public spectacle of horse racing will move underwater and become some kind of fish racing.  Ridiculous.  Also a complete failure to envision modern popularity of auto racing which already began in Paris in 1887.  Grade:  F.

#### Rota’s predictions on combinatorial problems:

In his paper, Rota writes:

Fortunately, most combinatorial problems can be stated in everyday language. To give an idea of the present state of the field, we have selected a few of the many problems that are now being actively worked upon.

We take each of these “problems” as a kind of predictions of where the field is going.  Here are my (biased and possibly uninformed) grades for each problem he mentions.

1)  The Ising Problem.  I think it is fair to say that since 1969 combinatorics made no contribution in this direction.  While physicists and probabilists continue studying this problem, there is no exact solution in dimension 3 and higher.  Grade: F.

2)  Percolation Theory.  The study of percolation completely exploded since 1969 and is now a subject of numerous articles in both probability, statistical physics and combinatorics, as well as several research monographs.  One connection is given by an observation that p-percolation on a complete graph Kn gives the Erdős–Rényi random graph model. Even I accidentally wrote a few papers on the subject some years ago (see one, two and three).  Grade: A.

3)  The Number of Necklaces, and Polya’s Problem.  Taken literally, the necklaces do come up in combinatorics of words and free Lie algebra, but this context was mentioned by Rota already. As far as I can tell, there are various natural (and interesting) generalizations of necklaces, but none surprising.  Of course, if the cyclic/dihedral group action here is replaced by other actions, e.g. the symmetric group, then modern developments are abundant.  But I think it’s a reach too far, since Rota knew the works of Young, MacMahon, Schur and others but does not mention any of it.  Similarly, Polya’s theorem used to be included in all major combinatorics textbooks (and is included now, occasionally), but is rarely taught these days.  Simply put, the g.f. implications haven’t proved useful.  Grade: D.

4)  Self-avoiding Walk. Despite strong interest, until recently there were very few results in the two-dimensional case (some remarkable results were obtained in higher dimensions). While the recent breakthrough results (see here and there) do use some interesting combinatorics, the authors’ motivation comes from probability. Combinatorialists did of course contribute to the study of somewhat related questions on enumeration of various classes of polyomino (which can be viewed as self-avoiding cycles in the grid, see e.g. here).  Grade: C.

5)  The Traveling Salesman Problem. This is a fundamental problem in optimization theory, connected to the study of Hamiltonian cycles in Graph Theory and numerous other areas. It is also one of the earliest NP-hard problems still playing a benchmark role in Theoretical Computer Science. No quick of summary of the progress in the past 45 years would give it justice. Note that Rota’s paper was written before the notions of NP-completeness. In this light, his emphasis on algorithmic complexity and allusions to Computability Theory (e.g. unsolvable problems) are most prescient.  So are his briefly mentioned connections to topology which are currently a popular topic.  Well done!  Grade: A+.

6)  The Coloring Problem.  This was a popular topic way before Rota’s article (inspired by the Four Color Theorem, the chromatic polynomial, etc.), and continues to be even more so, with truly remarkable advances in multiple directions.  Note Rota’s mentioning of matroids which may seem extraneous here at first, but in fact absolutely relevant indeed (in part due to Rota’s then-ongoing effort).  Very good but unsurprising prediction.  Grade: A-.

7)  The Pigeonhole Principle and Ramsey’s Theorem. The Extremal Graph Theory was about to explode in many directions, with the the Erdős-Stone-Simonovits theorem proved just a few years earlier and the Szemerédi regularity lemma a few years later.  Still, Rota never mentions Paul Erdős and his collaborators, nor any of these results, nor potential directions.  What a missed opportunity!  Grade: B+.

#### Rota’s predictions on combinatorial areas:

In the concluding section “The Coming Explosion”, Rota sets this up as follows:

Before concluding this brief survey, we shall list the main subjects in which current work in combinatorial theory is being done.

Here is a list and more of my comments.

1)  Enumerative Analysis.  Sure.  But this was an easy prediction to make given the ongoing effort by Carlitz, Polya, Riordan, Rota himself and many other peope.  Grade: A-.

2)  Finite Geometries and Block Designs.  The subject was already popular and it did continue to develop but perhaps at a different pace and directions than Rota anticipated (Hadamard matrices, tools from Number Theory).  In fact, a lot of later work was connection with with Group Theory (including some applications of CFSG which was an ongoing project) and in Coding Theory (as Rota predicted).  Grade: B-.

3)  Applications to Logic.  Rota gives a one-sentence desctiption:

The development of decision theory has forced logicians to make wide use of combinatorial methods.

There are various important connections between Logic and Combinatorics, for example in Descriptive Set Theory (see e.g. here or more recent work by my future UCLA colleague there).  Note however, that Infinitary Combinatorics was already under development, after the Erdős-Rado theorem (1956).  Another very interesting and more recent connection is to Model Theory (see e.g. here).  But the best interpretation here I can think of here are the numerous applications to Game Theory, which already existed (Nash’s equilibrium theorem is from 1950) and was under rapid development.  Either way, Rota was too vague in this case to be given much credit.  Grade: C.

4)  Statistical Mechanics.   He mentions the Ising model again and insists on “close connections with number theory”.  One can argue this all to be too vague or misdirected, but the area does indeed explode in part in the directions of problems Rota mentions earlier. So I am inclined to give him benefit of the doubt on this one. Grade: A-.

#### The final grade

In total, Rota clearly got more things right than wrong.  He displayed an occasional clairvoyance, had some very clever insights into the future, but also a few flops.  Note also the near complete lack of self-serving predictions, such as the Umbral Calculus that Rota was very fond of.  Since predictions are hard, successes have a great weight than failures.  I would give a final grade somewhere between A- and B+ depending on how far into the future do we think he was making the predictions.  Overall, good job, Gian-Carlo!

P.S.  Full disclosure:  I took a few advanced classes with Gian-Carlo Rota as a graduate student cross registering from Harvard to MIT, and he may have graded my homeworks (this was in 1994-1996 academic years).  I don’t recall the final grades, but I think they were good.  Eventually Rota wrote me a letter of recommendation for a postdoc position.

UPDATE (October 16, 2019)

I would still give a failing grade for Race in Pacific.   But having seen The Aquaman, the similarities are too eerie to ignore, so this prediction needs an upgrade.  Say, D-.

## Who named Catalan numbers?

February 5, 2014 2 comments

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. Yaglom 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).

UPDATE (Aug 25, 2014):  I did more historical research on the subject which is now reworked into an article History of Catalan Numbers.

UPDATE (Oct 13, 2016):  I came across a quote from Riordan himself (see below) published in this book review. In light of our investigation, this can be read as a tacit admission that he misnamed the sequence.  Note that Riordan seemed genially contrite yet unaware of the fact that Catalan learned about the sequence from Liouville who knew about Euler and Segner’s work. So the “temporary blindness” he is alleging is perhaps misaddressed…

“Nevertheless, the pursuit of originality and generality has its perils. For one
thing, the current spate of combinatorial mappings has produced the feeling
that multiplicity abounds. Perhaps the simplest example is the continuing
appearances of the Catalan numbers [..] Incidentally, these numbers
are named after E. Catalan because of a citation in Netto’s Kombinatorik, in
relation to perhaps the simplest bracketing problem, proposed in 1838. An
earlier appearance, which I first learned from Henry Gould, is due to the
Euler trio, Euler-Fuss-Segner, dated 1761. There are now at least forty
mappings, hence, forty diverse settings for this sequence; worse still, no end
seems in sight. In this light, the Catalan (or Euler-Fuss-Segner) originality
may be regarded as temporary blindness.”