### Archive

Archive for the ‘Mathematics’ Category

## How to write math papers clearly

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

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

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!

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”. 4) Download and host your own videos on your website alongside your slides and your relevant paper(s), or at least make clear links to them from your website. You can’s trust anyone to keep your files. Some would argue that re-posting them on YouTube will then suffice. There are two issues here. First, this is rarely legal (see below). Second, as I mentioned above, many viewers would want to have a copy of the file. Hopefully, in the future there will be a copyright-free arXiv-style video hosting site for academics (see my predictions below). 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. 3) If the file with your talk is posted, it is (obviously) legal for you to download it, but not to post it on your website or repost elsewhere such as YouTube or WordPress. As far as I am concerned, you should go ahead and post it on your university website anyway (but not on YT or WP!). Many authors typically post all their papers on their website even if they don’t own a copyright on them (which is the case or virtually all papers before 2000). I am one of them. The publishers just concluded that this is the cost of doing business – if they start going after people like us, the authors can revolt. The same with math videos. The institutions probably won’t have a problem with your university website posting as long as you acknowledge the source. But involving a third party creates a host of legal problems since these internet companies are making money out of the videos they don’t own a copyright for. Stay away from this. 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. 5) If the institution’s website does not allow to download the video but has a streaming option (typically, the Adobe Flash or HTML5), you can still legally save it on your computer, but this depends on what software you choose. There are plenty of software which capture the video being played on your computer and save it in a file. These are 100% legal. Other websites play the videos on their computers and allow you to download afterwards. This is probably legal at the institutions, but a gray area at YouTube or Vimeo which have terms of service these companies may be violating. Just remember – such videos can only be legal for personal consumption. Also, the quality of such recording is typically poor – having the original file is much better. #### 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.” ## Mathematician’s guide to holidays December 20, 2013 Leave a comment Holiday season offers endless opportunities to celebrate, relax, rest, reflect and meditate. Whether you are enjoying a white Christmas or a palm tree Chanukkah, a mathematician in you might wonder if there is more to the story, a rigorous food for thought, if you will. So here is a brief guide to the holidays for the mathematically inclined. #### 1) Christmas tree lectures I have my own Christmas tree tradition. Instead of getting one, I watch new Don Knuth‘s “Christmas tree lecture“. Here is the most recent one. But if you have time and enjoy binge-watching here is the archive of past lectures (click on “Computer musings” and select December dates). If you are one of my Math 206 students, compare how Knuth computed the number of spanning trees in a hypercube (in a 2009 lecture) with the way Bernardi did in his elegant paper. #### 2) Algorithmic version of Fermat’s Christmas theorem Apparently, Fermat’s theorem on sums of two squares first appeared in Fermat’s long letter to Mersenne, written on Christmas Day (December 25, 1640). For background, see Catalan and French language Wikipedia articles. Zagier’s “one-sentence proof” is well known and available here. Long assumed to be mysterious, it was nicely explained by Elsholtz. Still mysteriously, a related proof also appears in a much earlier paper (in French), by a Russian-American mathematician J. Uspensky (ht. Ustinov). Can somebody explain to me what’s in that paper? Interestingly, there is a nice polynomial time algorithm to write a prime p=1 mod 4 as a sum of two squares, but I could not find a clean version on the web. If you are curious, start with Cornacchia’s algorithm for more general quadratic Diophantine equations, and read its various proofs (advanced, elementary, short, textbook, in French). Then figure out why Fermat’s special case can be done in (probabilistic) polynomial time. #### 3) Dreidel game analysis The dreidel is a well known Chanukkah game with simple rules. Less known is the mathematics behind it. Start with this paper explaining that it’s unfair, and continue to this paper explaining how to fix it (on average). Then proceed to this “squared nuts” conjecture by Zeilberger on the expected length of the game (I have a really good joke here which I will suppress). This conjecture was eventually resolved in this interesting paper, definitely worth$25 promised by Zeilberger.

Now, if you are underwhelmed with the dreidel game, try to prove the festive Star of David Theorem.  When you are done, enjoy this ingenious proof, which is definitely “from the book”.

#### 4)  Santa Claus vs beautiful mathematics

Most readers of this blog are aware of existence of beautiful mathematics.  I can only speculate that a clear majority of them would probably deny the existence of Santa Claus.  However, there are millions of (mostly, very young) people who believe the exact opposite on both counts.  Having grown up in the land of Ded Moroz, we have little to say on the great Santa debate, but we believe it’s worth carefully examining Santa proponent’s views.  Could it be that their arguments can be helpful in our constant struggle to spread the gospel of beautiful mathematics?

We recommend reading “Yes, Virginia, there is Santa Claus column (fully available here), which was originally published by the New York Sun in 1897.  In fact, read it twice, three times, even four times.  I am reluctant to quote from it because it’s short and deserves to be read in full.  But note this passage:  “The most real things in the world are those that neither children nor men can see.”  The new Jewish editor of the Sun reports that the rabbis he consulted think this is “a joyous articulation of faith”.  Maybe.  But to me this evokes some beautiful advanced mathematics.

You see, when mathematicians try to explain that mathematics is beautiful, they tend to give simple visually appealing examples (like here).  But I suggest closing your eyes and imagining beautiful mathematical objects, such as the 600-cell, Poincaré homolgy sphereLie group E8, Monster group, or many other less known higher dimensional constructions such as the associahedron, the Birkhoff polytope, Walz’s flexible cross-polyhedron, etc.  Certainly all of these can be seen by “neither children nor men”.  Yet we can prove that they “are real”.  We can then spend years studying and generalizing them.  This knowledge alone can bring joy to every holiday season…

HAPPY HOLIDAYS EVERYONE!   С НОВЫМ ГОДОМ!

## Combinatorial briefs

I tend to write longish posts, in part for the sake of clarity, and in part because I can – it is easier to express yourself in a long form.  However, the brevity has its own benefits, as it forces the author to give succinct summaries of often complex and nuanced views.  Similarly, the lack of such summaries can provide plausible deniability of understanding the basic points you are making.

This is the second time I am “inspired” by the Owl blogger who has a Tl;Dr style response to my blog post and rather lengthy list of remarkable quotations that I compiled.  So I decided to make the following Readers Digest style summaries of this list and several blog posts.

#### 1)  Combinatorics has been sneered at for decades and struggled to get established

In the absence of History of Modern Combinatorics monograph, this is hard to prove.  So here are selected quotes, from the above mentioned quotation page.  Of course, one should reade them in full to appreciate and understand the context, but for our purposes these will do.

Combinatorics is the slums of topology – Henry Whitehead

Scoffers regard combinatorics as a chaotic realm of binomial coefficients, graphs, and lattices, with a mixed bag of ad hoc tricks and techniques for investigating them. [..]  Another criticism of combinatorics is that it “lacks abstraction.” The implication is that combinatorics is lacking in depth and all its results follow from trivial, though possible elaborate, manipulations. This argument is extremely misleading and unfair. – Richard Stanlеy (1971)

The opinion of many first-class mathematicians about combinatorics is still in the pejorative. While accepting its interest and difficulty, they deny its depth. It is often forcefully stated that combinatorics is a collection of problems which may be interesting in themselves but are not linked and do not constitute a theory. – László Lovász (1979)

Combinatorics [is] a sort of glorified dicethrowing.  – Robert Kanigel (1991)

This prejudice, the view that combinatorics is quite different from ‘real mathematics’, was not uncommon in the twentieth century, among popular expositors as well as professionals.  –  Peter Cameron (2001)

Now that the readers can see where the “traditional sensitivities” come from, the following quote must come as a surprise.  Even more remarkable is that it’s become a conventional wisdom:

Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics.  – John Stillwell (2010)

Of course, the prejudice has never been limited to Combinatorics.  Imagine how an expert in Partition Theory and q-series must feel after reading this quote:

[In the context of Partition Theory]  Professor Littlewood, when he makes use of an algebraic identity, always saves himself the trouble of proving it; he maintains that an identity, if true, can be verified in a few lines by anybody obtuse enough to feel the need of verification.  – Freeman Dyson (1944), see here.

#### 2)  Combinatorics papers have been often ostracized and ignored by many top math journals

This is a theme in this post about the Annals, this MO answer, and a smaller theme in this post (see Duke paragraph).  This bias against Combinatorics is still ongoing and hardly a secret.  I argue that on the one hand, the situation is (slowly) changing for the better.  On the other hand, if some journals keep the proud tradition of rejecting the field, that’s ok, really.  If only they were honest and clear about it!  To those harboring strong feelings on this, listening to some breakup music could be helpful.

#### 3)  Despite inherent diversity, Combinatorics is one field

In this post, I discussed how I rewrote Combinatorics Wikipedia article, largely as a collection of links to its subfields.  In a more recent post mentioned earlier I argue why it is hard to define the field as a whole.  In many ways, Combinatorics resembles a modern nation, united by a language, culture and common history.  Although its borders are not easy to define, suggesting that it’s not a separate field of mathematics is an affront to its history and reality (see two sections above).  As any political scientist will argue, nation borders can be unhelpful, but are here for a reason.  Wishing borders away is a bit like French “race-ban”  – an imaginary approach to resolve real problems.

Gowers’s “two cultures” essay is an effort to describe and explain cultural differences between Combinatorics and other fields.  The author should be praised both for the remarkable essay, and for the bravery of raising the subject.  Finally, on the Owl’s attempt to divide Combinatorics into “conceptual” which “has no internal reasons to die in any foreseeable future” and the rest, which “will remain a collection of elementary tricks, [..] will die out and forgotten [sic].”  I am assuming the Owl meant here most of the “Hungarian combinatorics”, although to be fair, the blogger leaves some wiggle room there.  Either way, “First they came for Hungarian Combinatorics” is all that came to mind.

## What do math journals do? What will become of them in the future?

Recently, there has been plenty of discussions on math journals, their prices, behavior, technology and future.   I have been rather reluctant to join the discussion in part due to my own connection to Elsevier, in part because things in Combinatorics are more complicated than in other areas of mathematics (see below), but also because I couldn’t reconcile several somewhat conflicting thoughts that I had.  Should all existing editorial boards revolt and all journals be electronic?  Or perhaps should we move to “pay-for-publishing” model?  Or even “crowd source refereeing”?  Well, now that the issue a bit cooled down, I think I figured out exactly what should happen to math journals.  Be patient – a long explanation is coming below.

#### Quick test questions

I would like to argue that the debate over the second question is the general misunderstanding of the first question in the title.  In fact, I am pretty sure most mathematicians are quite a bit confused on this, for a good reason.  If you think this is easy, quick, answer the following three questions:

1)  Published paper has a technical mistake invalidating the main result.  Is this a fault of author, referee(s), handling editor, managing editor(s), a publisher, or all of the above?  If the reader find such mistake, who she/he is to contact?

2)  Published paper proves special case of a known result published 20 years earlier in an obscure paper.  Same question.  Would the answer change if the author lists the paper in the references?

3) Published paper is written in a really poor English.  Sections are disorganized and the introduction is misleading.  Same question.

Now that you gave your answers, ask a colleague.  Don’t be surprised to hear a different point of view.  Or at least don’t be surprised when you hear mine.

#### What do referees do?

In theory, a lot.  In practice, that depends.  There are few official journal guides to referees, but there are several well meaning guides (see also here, here, here,  here §4.10, and a nice discussion by Don Knuth §15).  However, as any editor can tell you, you never know what exactly did the referee do.  Some reply within 5 min, some after 2 years.  Some write one negative sentence, some 20 detailed pages, some give an advice in the style “yeah, not a bad paper, cites me twice, why not publish it”, while others a brushoff “not sure who this person is, and this problem is indeed strongly related to what I and my collaborators do, but of course our problems are much more interesting/important  – rejection would be best”.  The anonymity is so relaxing, doing a poor job is just too tempting.  The whole system hinges on the shame, sense of responsibility, and personal relationship with the editor.

A slightly better questions is “What do good referees do?”  The answer is – they don’t just help the editor make acceptance/rejection decision.  They help the authors.  They add some background the authors don’t know, look for missing references, improve on the proofs, critique the exposition and even notation.  They do their best, kind of what ideal advisors do for their graduate students, who just wrote an early draft of their first ever math paper.

In summary, you can’t blame the referees for anything.  They do what they can and as much work as they want.  To make a lame comparison, the referees are like wind and the editors are a bit like sailors.  While the wind is free, it often changes direction, sometimes completely disappears, and in general quite unreliable.  But sometimes it can really take you very far.  Of course, crowd sourcing refereeing is like democracy in the army – bad even in theory, and never tried in practice.

#### First interlude: refereeing war stories

I recall a curious story by Herb Wilf, on how Don Knuth submitted a paper under assumed name with an obscure college address, in order to get full refereeing treatment (the paper was accepted and eventually published under Knuth’s real name).  I tried this once, to unexpected outcome (let me not name the journal and the stupendous effort I made to create a fake identity).  The referee wrote that the paper was correct, rather interesting but “not quite good enough” for their allegedly excellent journal.  The editor was very sympathetic if a bit condescending, asking me not to lose hope, work on my papers harder and submit them again.  So I tried submitting to a competing but equal in statue journal, this time under my own name. The paper was accepted in a matter of weeks.  You can judge for yourself the moral of this story.

A combinatorialist I know (who shall remain anonymous) had the following story with Duke J. Math.  A year and a half after submission, the paper was rejected with three (!) reports mostly describing typos.  The authors were dismayed and consulted a CS colleague.  That colleague noticed that the three reports were in .pdf  but made by cropping from longer files.   Turns out, if the cropping is made straightforwardly, the cropped portions are still hidden in the files.  Using some hacking software the top portions of the reports were uncovered.  The authors discovered that they are extremely positive, giving great praise of the paper.  Now the authors believe that the editor despised combinatorics (or their branch of combinatorics) and was fishing for a bad report.  After three tries, he gave up and sent them cropped reports lest they think somebody else considers their paper worthy of publishing in the grand old Duke (cf. what Zeilberger wrote about Duke).

Another one of my stories is with the  Journal of AMS.  A year after submission, one of my papers was rejected with the following remarkable referee report which I quote here in full:

The results are probably well known.  The authors should consult with experts.

Needless to say, the results were new, and the paper was quickly published elsewhere.  As they say, “resistance is futile“.

#### What do associate/handling editors do?

Three little things, really.  They choose referees, read their reports and make the decisions.  But they are responsible for everything.  And I mean for everything, both 1), 2) and 3).  If the referee wrote a poorly researched report, they should recognize this and ignore it, request another one.  They should ensure they have more than one opinion on the paper, all of them highly informed and from good people.  If it seems the authors are not aware of the literature and referee(s) are not helping, they should ensure this is fixed.  It the paper is not well written, the editors should ask the authors to rewrite it (or else).   At Discrete Mathematics, we use this page by Doug West, as a default style to math grammar.  And if the reader finds a mistake, he/she should first contact the editor.  Contacting the author(s) is also a good idea, but sometimes the anonymity is helpful – the editor can be trusted to bring bad news and if possible, request a correction.

B.H. Neumann described here how he thinks the journal should operate.  I wish his views held widely today.  The  book by Krantz, §5.5, is a good outline of the ideal editorial experience, and this paper outlines how to select referees.  However, this discussion (esp. Rick Durrett’s “rambling”) is more revealing.  Now, the reason most people are confused as to who is responsible for 1), 2) and 3), is the fact that while some journals have serious proactive editors, others do not, or their work is largely invisible.

#### What do managing editors and publishers do?

In theory, managing editors hire associate editors, provide logistical support, distribute paper load, etc.  In practice they also serve as handling editors for a large number of papers.  The publishers…  You know what the publishers do.  Most importantly, they either pay editors or they don’t.  They either charge libraries a lot, or they don’t.  Publishing is a business, after all…

#### Who wants free universal electronic publishing?

Good mathematicians.  Great mathematicians.  Mathematicians who write well and see no benefit in their papers being refereed.  Mathematicians who have many students and wish the publishing process was speedier and less cumbersome, so their students can get good jobs.  Mathematicians who do not value the editorial work and are annoyed when the paper they want to read is “by subscription only” and thus unavailable.  In general, these are people who see having to publish as an obstacle, not as a benefit.

#### Who does not want free universal electronic publishing?

Publishers (of course), libraries, university administrators.  These are people and establishments who see value in existing order and don’t want it destroyed.  Also: mediocre mathematicians, bad mathematicians, mathematicians from poor countries, mathematicians who don’t have access to good libraries (perhaps, paradoxically).  In general, people who need help with their papers.  People who don’t want a quick brush-off  “not good enough” or “probably well known”, but those who need advice on the references, on their English, on how the papers are structured and presented, and on what to do next.

#### So, who is right?

Everyone.  For some mathematicians, having all journals to be electronic with virtually no cost is an overall benefit.  But at the very least, “pro status quo” crowd have a case, in my view.  I don’t mean that Elsevier pricing policy is reasonable, I am talking about the big picture here.  In a long run, I think of journals as non-profit NGO‘s, some kind of nerdy versions of Nobel Peace Prize winning Médecins Sans Frontières.  While I imagine that in the future many excellent top level journals will be electronic and free, I also think many mid-level journals in specific areas will be run by non-profit publishers, not free at all, and will employ a number of editorial and technical stuff to help the authors, both of papers they accept and reject.  This is a public service we should strive to perform, both for the sake of those math papers, and for development of mathematics in other countries.

Right now, the number of mathematicians in the world is already rather large and growing.  Free journals can do only so much.  Without high quality editors paid by the publishers, with a large influx of papers from the developing world, there is a chance we might loose the traditional high standards for published second tier papers.  And I really don’t want to think of a mathematics world once the peer review system is broken.  That’s why I am not in the “free publishing camp” – in an effort to save money, we might loose something much more valuable – the system which gives foundation and justification of our work.

#### Second interlude: journals vis-à-vis combinatorics

I already wrote about the fate of combinatorics papers in the Annals, especially when comparison with Number Theory.  My view was gloomy but mildly optimistic.  In fact, since that post was written couple more combinatorics papers has been accepted.  Good.  But let me give you a quiz.  Here are two comparable highly selective journals – Duke J. Math. and Composito Math.  In the past 10 years Composito published exactly one (!) paper in Combinatorics (defined as primary MSC=05), of the 631 total.  In the same period, Duke published 8 combinatorics papers of 681 total.

Q: Which of the two (Composito or Duke) treats combinatorics papers better?

A: Composito, of course.

The reasoning is simple.  Forget the anecdotal evidence in the previous interlude.  Just look at the “aim and scope” of the journals vs. these numbers.  Here is what Compsito website says with a refreshing honesty:

By tradition, the journal published by the foundation focuses on papers in the main stream of pure mathematics. This includes the fields of algebra, number theory, topology, algebraic and analytic geometry and (geometric) analysis. Papers on other topics are welcome if they are of interest not only to specialists.

Translation: combinatorics papers are not welcome (as are papers in many other fields).  I think this is totally fair.  Nothing wrong with that.  Clearly, there are journals which publish mostly in combinatorics, and where papers in none of these fields would be welcome.  In fact there is a good historical reason for that.  Compare this with what Duke says on its website:

Published by Duke University Press since its inception in 1935, the Duke Mathematical Journal is one of the world’s leading mathematical journals. Without specializing in a small number of subject areas, it emphasizes the most active and influential areas of current mathematics.

See the difference?  They don’t name their favorite areas!  How are the authors supposed to guess which are these?  Clearly, Combinatorics with its puny 1% proportion of Duke papers is not a subject area that Duke “emphasizes”.  Compare it with 104 papers in Number Theory (16%) and 124 papers in Algebraic Geometry (20%) over the same period.  Should we conclude that in the past 10 years, Combinatorics was not “the most active and influential”, or perhaps not “mathematics” at all? (yes, some people think so)  I have my own answer to this question, and I bet so do you…

Note also, that things used to be different at Duke.  For example, exactly 40 years earlier, in the period 1963-1973, Duke published 47 papers in combinatorics out of 972 total, even though the area was only in its first stages of development.  How come?  The reason is simple: Leonard Carlitz was Managing Editor at the time, and he welcomed papers from a number of prominent combinatorialists active during that time, such as Andrews, Gould, Moon, Riordan, Stanley, Subbarao, etc., as well as a many of his own papers.

#### So, ideally, what will happen to math journals?

That’s actually easy.  Here are my few recommendations and predictions.

1)  We should stop with all these geography based journals.  That’s enough.  I understand the temptation for each country, or university, or geographical entity to have its own math journal, but nowadays this is counterproductive and a cause for humor.  This parochial patriotism is perhaps useful in sports (or not), but is nonsense in mathematics.  New journals should emphasize new/rapidly growing areas of mathematics underserved by current journals, not new locales where printing presses are available.

2)  Existing for profit publishers should realize that with the growth of arXiv and free online competitors, their business model is unsustainable.  Eventually all these journals will reorganize into a non-profit institutions or foundations.  This does not mean that the journals will become electronic or free.  While some probably will, others will remain expensive, have many paid employees (including editors), and will continue to provide services to the authors, all supported by library subscriptions.  These extra services are their raison d’être, and will need to be broadly advertised.  The authors would learn not to be surprised of a quick one line report from free journals, and expect a serious effort from “expensive journals”.

3)  The journals will need to rethink their structure and scope, and try to develop their unique culture and identity.  If you have two similar looking free electronic journals, which do not add anything to the papers other than their .sty file, the difference is only the editorial board and history of published papers.  This is not enough.  All journals, except for the very top few, will have to start limiting their scope to emphasize the areas of their strength, and be honest and clear in advertising these areas.  Alternatively, other journals will need to reorganize and split their editorial board into clearly defined fields.  Think  Proc. LMS,  Trans. AMS, or a brand new  Sigma, which basically operate as dozens of independent journals, with one to three handling editors in each.  While highly efficient, in a long run this strategy is also unsustainable as it leads to general confusion and divergence in the quality of these sub-journals.

4)  Even among the top mathematicians, there is plenty of confusion on the quality of existing mathematics journals, some of which go back many decades.  See e.g. a section of Tim Gowers’s post about his views of the quality of various Combinatorics journals, since then helpfully updated and corrected.  But at least those of us who have been in the area for a while, have the memory of the fortune of previously submitted papers, whether our own, or our students, or colleagues.  A circumstantial evidence is better than nothing.  For the newcomers or outsiders, such distinctions between journals are a mystery.  The occasional rankings (impact factor or this, whatever this is) are more confusing than helpful.

What needs to happen is a new system of awards recognizing achievements of individual journals and/or editors, in their efforts to improve the quality of the journals, attracting top papers in the field, arranging fast refereeing, etc.   Think a mixture of Pulitzer Prize and J.D. Power and Associates awards – these would be a great help to understand the quality of the journals.  For example, the editors of the Annals clearly hustled to referee within a month in this case (even if motivated by PR purposes).  It’s an amazing speed for a technical 50+ page paper, and this effort deserves recognition.

Full disclosure:  Of the journals I singled out, I have published once in both  JAMS  and  Duke.  Neither paper is in Combinatorics, but both are in Discrete Mathematics, when understood broadly.

## On triple crowns in mathematics and AMS badges

September 9, 2012 1 comment

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

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

### Triple Crown in Mathematics

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

### Other Journal awards

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

Marathon – 300 papers

Ultramarathon – 900 papers

Iron Man – 5 triple crown awards

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

scholar (bronze) – at least one citation

supporter (bronze) – cited at least one paper

writer (bronze) – first paper

reviewer (bronze) – first MathSciNet review

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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