Why you shouldn’t be too pessimistic

In our math research we make countless choices. We chose a problem to work on, decide whether its claim is true or false, what tools to use, what earlier papers to study which might prove useful, who to collaborate with, which computer experiments might be helpful, etc. Choices, choices, choices… Most our choices are private. Others are public. This blog is about wrong public choices that I made misjudging some conjectures by being overly pessimistic.

The meaning of conjectures

As I have written before, conjectures are crucial to the developments of mathematics and to my own work in particular. The concept itself is difficult, however. While traditionally conjectures are viewed as some sort of “unproven laws of nature“, that comparison is widely misleading as many conjectures are descriptive rather than quantitative. To understand this, note the stark contrast with experimental physics, as many mathematical conjectures are not particularly testable yet remain quite interesting. For example, if someone conjectures there are infinitely many Fermat primes, the only way to dissuade such person is to actually disprove the claim.

There is also an important social aspect of conjecture making. For a person who poses a conjecture, there is a certain clairvoyance respected by other people in the area. Predictions are never easy, especially of a precise technical nature, so some bravery or self-assuredness is required. Note that social capital is spent every time a conjecture is posed. In fact, a lot of it is lost when it’s refuted, you come out even if it’s proved relatively quickly, and you gain only if the conjecture becomes popular or proved possibly many years later. There is also a “boy who cried wolf” aspect for people who make too many conjectures of dubious quality — people will just tune out.

Now, for the person working on a conjecture, there is also a betting aspect one cannot ignore. As in, are you sure you are working in the right direction? Perhaps, the conjecture is simply false and you are wasting your time… I wrote about this all before in the post linked above, and the life/career implications on the solver are obvious. The success in solving a well known conjecture is often regarded much higher than a comparable result nobody asked about. This may seem unfair, and there is a bit of celebrity culture here. Thinks about it this way — two lead actors can have similar acting skills, but the one who is a star will usually attract a much larger audience…

Stories of conjectures

Not unlike what happens to papers and mathematical results, conjectures also have stories worth telling, even if these stories are rarely discussed at length. In fact, these “conjecture stories” fall into a few types. This is a little bit similar to the “types of scientific papers” meme, but more detailed. Let me list a few scenarios, from the least to the most mathematically helpful:

(1) Wishful thinking. Say, you are working on a major open problem. You realize that a famous conjecture A follows from a combination of three conjectures B, C and D whose sole motivation is their applications to A. Some of these smaller conjectures are beyond the existing technology in the area and cannot be checked computationally beyond a few special cases. You then declare that this to be your “program” and prove a small special case of C. Somebody points out that D is trivially false. You shrug, replace it with a weaker D’ which suffices for your program but is harder to disprove. Somebody writes a long state of the art paper disproving D’. You shrug again and suggest an even weaker conjecture D”. Everyone else shrugs and moves on.

(2) Reconfirming long held beliefs. You are working in a major field of study aiming to prove a famous open problem A. Over the years you proved a number of special cases of A and became one the leaders of the area. You are very optimistic about A discussing it in numerous talks and papers. Suddenly A is disproved in some esoteric situations, undermining the motivation of much of your older and ongoing work. So you propose a weaker conjecture A’ as a replacement for A in an effort to salvage both the field and your reputation. This makes happy everyone in the area and they completely ignore the disproof of A from this point on, pretending it’s completely irrelevant. Meanwhile, they replace A with A’ in all subsequent papers and beamer talk slides.

(3) Accidental discovery. In your ongoing work you stumble at a coincidence. It seem, all objects of a certain kind have some additional property making them “nice“. You are clueless why would that be true, since being nice belongs to another area X. Being nice is also too abstract to be checked easily on a computer. You consult a colleague working in X whether this is obvious/plausible/can be proved and receive No/Yes/Maybe answers to these three questions. You are either unable to prove the property or uninterested in problem, or don’t know much about X. So you mention it in the Final Remarks section of your latest paper in vain hope somebody reads it. For a few years, every time you meet somebody working in X you mention to them your “nice conjecture”, so much that people laugh at you behind your back.

(4) Strong computational evidence. You are doing computer experiments related to your work. Suddenly certain numbers appear to have an unexpectedly nice formula or a generating function. You check with OEIS and the sequence is there indeed, but not with the meaning you wanted. You use the “scientific method” to get a few more terms and they indeed support your conjectural formula. Convinced this is not an instance of the “strong law of small numbers“, you state the formula as a conjecture.

(5) Being contrarian. You think deeply about famous conjecture A. Not only your realize that there is no way one can approach A in full generality, but also that it contradicts some intuition you have about the area. However, A was stated by a very influential person N and many people believe in A proving it in a number of small special cases. You want to state a non-A conjecture, but realize the inevitable PR disaster of people directly comparing you to N. So you either state that you don’t believe in A, or that you believe in a conjecture B which is either slightly stronger or slightly weaker than non-A, hoping the history will prove you right.

(6) Being inspirational. You think deeply about the area and realize that there is a fundamental principle underlying certain structures in your work. Formalizing this principle requires a great deal of effort and results in a conjecture A. The conjecture leads to a large body of work by many people, even some counterexamples in esoteric situations, leading to various fixes such as A’. But at that point A’ is no longer the goal but more of a direction in which people work proving a number of A-related results.

Obviously, there are many other possible stories, while some stories are are a mixture of several of these.

Why do I care? Why now?

In the past few years I’ve been collecting references to my papers which solve or make some progress towards my conjectures and open problems, putting links to them on my research page. Turns out, over the years I made a lot of those. Even more surprisingly, there are quite a few papers which address them. Here is a small sampler, in random order:

(1) Scott Sheffield proved my ribbon tilings conjecture.

(2) Alex Lubotzky proved my conjecture on random generation of a finite group.

(3) Our generalized loop-erased random walk conjecture (joint with Igor Gorodezky) was recently proved by Heng Guo and Mark Jerrum.

(4) Our Young tableau bijections conjecture (joint with Ernesto Vallejo) was resolved by André Henriques and Joel Kamnitzer.

(5) My size Ramsey numbers conjecture led to a series of papers, and was completely resolved only recently by Nemanja Draganić, Michael Krivelevich and Rajko Nenadov.

(6) One of my partition bijection problems was resolved by Byungchan Kim.

The reason I started collecting these links is kind of interesting. I was very impressed with George Lusztig and Richard Stanley‘s lengthy writeups about their collected papers that I mentioned in this blog post. While I don’t mean to compare myself to these giants, I figured the casual reader might want to know if a conjecture in some paper had been resolved. Thus the links on my website. I recommend others also do this, as a navigational tool.

What gives?

Well, looks like none of my conjectures have been disproved yet. That’s a good news, I suppose. However, by going over my past research work I did discover that on three occasions when I was thinking about other people’s conjectures, I was much too negative. This is probably the result of my general inclination towards “negative thinking“, but each story is worth telling.

(i) Many years ago, I spent some time thinking about Babai’s conjecture which states that there are universal constants C, c >0, such that for every simple group G and a generating set S, the diameter of the Cayley graph Cay(G,S) is at most C(log |G|)^c. There has been a great deal of work on this problem, see e.g. this paper by Sean Eberhard and Urban Jezernik which has an overview and references.

Now, I was thinking about the case of the symmetric group trying to apply arithmetic combinatorics ideas and going nowhere. In my frustration, in a talk I gave (Galway, 2009), I wrote on the slides that “there is much less hope” to resolve Babai’s conjecture for A_n than for simple groups of Lie type or bounded rank. Now, strictly speaking that judgement was correct, but much too gloomy. Soon after, Ákos Seress and Harald Helfgott proved a remarkable quasi-polynomial upper bound in this case. To my embarrassment, they referenced my slides as a validation of the importance of their work.

Of course, Babai’s conjecture is very far from being resolved for A_n. In fact, it is possible that the diameter is always O(n²). We just have no idea. For simple groups of Lie type or large rank the existing worst case diameter bounds are exponential and much too weak compared to the desired bound. As Eberhard and Jezernik amusingly wrote in the paper linked above, “we are still exponentially stupid“…

(ii) When he was my postdoc at UCLA, Alejandro Morales told me about a curious conjecture in this paper (Conjecture 5.1), which claimed that the number of certain nonsingular matrices over the finite field F_q is polynomial in q with positive coefficients. He and coauthors proved the conjecture is some special cases, but it was wide open in full generality.

Now, I thought about this type of problems before and was very skeptical. I spent a few days working on the problem to see if any of my tools can disprove it, and failed miserably. But in my stubbornness I remained negative and suggested to Alejandro that he should drop the problem, or at least stop trying to prove rather than disprove the conjecture. I was wrong to do that.

Luckily, Alejandro ignored my suggestion and soon after proved the polynomial part of the conjecture together with Joel Lewis. Their proof is quite elegant and uses certain recurrences coming from the rook theory. These recurrences also allow a fast computation of these polynomials. Consequently, the authors made a number of computer experiments and disproved the positivity of coefficients part of the conjecture. So the moral is not to be so negative. Sometimes you need to prove a positive result first before moving to the dark side.

(iii) The final story is about the beautiful Benjamini conjecture in probabilistic combinatorics. Roughly speaking, it says that for every finite vertex transitive graph G on n vertices and diameter O(n/log n) the critical percolation constant p_c <1. More precisely, the conjecture claims that there is p<1-ε, such that a p-percolation on G has a connected component of size >n/2 with probability at least δ, where constants ε, δ>0 depend on the constant implied by the O(*) notation, but not on n. Here by “p-percolation” we mean a random subgraph of G with probability p of keeping and 1-p of deleting an edge, independently for all edges of G.

Now, Itai Benjamini is a fantastic conjecture maker of the best kind, whose conjectures are both insightful and well motivated. Despite the somewhat technical claim, this conjecture is quite remarkable as it suggested a finite version of the “p_c<1″ phenomenon for infinite groups of superlinear growth. The latter is the famous Benjamini–Schramm conjecture (1996), which was recently proved in a remarkable breakthrough by Hugo Duminil-Copin, Subhajit Goswami, Aran Raoufi, Franco Severo and Ariel Yadin. While I always believed in that conjecture and even proved a tiny special case of it, finite versions tend to be much harder in my experience.

In any event, I thought a bit about the Benjamini conjecture and talked to Itai about it. He convinced me to work on it. Together with Chis Malon, we wrote a paper proving the claim for some Cayley graphs of abelian and some more general classes of groups. Despite our best efforts, we could not prove the conjecture even for Cayley graphs of abelian groups in full generality. Benjamini noted that the conjecture is tight for products of two cyclic groups, but that justification did not sit well with me. There seemed to be no obvious way to prove the conjecture even for the Cayley graph of S_n generated by a transposition and a long cycle, despite the very small O(n²) diameter. So we wrote in the introduction: “In this paper we present a number of positive results toward this unexpected, and, perhaps, overly optimistic conjecture.”

As it turns out, it was us who were being overly pessimistic, even if we never actually stated that we believe the conjecture is false. Most recently, in an amazing development, Tom Hutchcroft and Matthew Tointon proved a slightly weaker version of the conjecture by adapting the methods of Duminil-Copin et al. They assume the O(n/(log n)^c) upper bound on the diameter which they prove is sufficient, for some universal constant c>1. They also extend our approach with Malon to prove the conjecture for all Cayley graphs of abelian groups. So while the Benjamini conjecture is not completely resolved, my objections to it are no longer valid.

Final words on this

All in all, it looks like I was never formally wrong even if I was a little dour occasionally (Yay!?). Turns out, some conjectures are actually true or at least likely to hold. While I continue to maintain that not enough effort is spent on trying to disprove the conjectures, it is very exciting when they are proved. Congratulations to Harald, Alejandro, Joel, Tom and Matthew, and posthumous congratulations to Ákos for their terrific achievements!