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 ⊂ S_k be a finite set of permutations and let C_n(F) denote the number of permutations σ ∈ S_n avoiding the set of patterns F. The Noonan-Zeilbeger conjecture (1996), states that the sequence {C_n(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 a_n of paths of length n accepted by by T is equal to C_n(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 {a_n} 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 S₈₀ for which {C_n(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 C_n(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 {C_n(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 {C_n(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 “C_n(F) = C_n(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 C_n(F) = C_n(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 {C_n(π)} 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 aⁿ + bⁿ = cⁿ?  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!

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!