## 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*avoiding the set of patterns

_{n}*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*of paths of length n accepted by by T is equal to

_{n }*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 _{80}* 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*^{n} + *b*^{n} = *c*^{n}? 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… 🙂

## On triple crowns in mathematics and AMS badges

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

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

### Triple Crown in Mathematics

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

### Other Journal awards

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

**Marathon** – 300 papers

**Ultramarathon** – 900 papers

**Iron Man** – 5 triple crown awards

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

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

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

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

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

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

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

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

### Publication badges

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

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

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

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

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

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

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

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

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

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

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

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

**scholar** (bronze) – at least one citation

**supporter** (bronze) – cited at least one paper

**writer** (bronze) – first paper

**reviewer** (bronze) – first MathSciNet review

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

**theorist** (silver) – the implied constant in O(.) notation in the main result in greater than 10^{80}.

**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.