Igor Pak's blog

Just in time for the holidays, Colleen Robichaux and I wrote this paper on positivity of Schubert coefficients. This paper is unlike any other paper I had written, both in the content and the way we obtained the results. To me, writing it was a religious experience. No, no, the paper is still mathematical, it’s just, uhm, different. Read this post till the end to find out how, or go straight to the paper (or perhaps both!)

Faith, religion and miracles — math got them all!

Mathematicians rarely if ever discuss the subject. When they do, they get either apologetic about it “there are no contradictions…”, or completely detached as if you can be deeply religious on Sunday morning and completely secular on Tuesday afternoon. See e.g. Robert Aumann’s extensive interview or this short clip by Freeman Dyson, two of the most admired people in their respective fields.

I have neither a religious education nor a specialized knowledge to speak on the subject, obviously. But in the age of Twitter (uhm, X.com, sorry) that minor issue never stopped anyone. So having said that, let me give a very vague and far-fetching primer to mathematicians in the language you could relate. This might prove helpful later on.

Faith is the foundation of it all. You really can’t do math without foundations. Outside of certain areas you don’t really need to understand it or even think about it all that that much. Just accept it and you’ll better off. For example, it is likely that the more you think about consistency of PA the less certain you get about what you are doing, so stay on the happy side.

This does not mean you need to be consistent with your owb tenants of faith. For example, it’s perfectly fine to have a paper in algebra using the Axiom of Choice (AC) while in another in descriptive set theory, where you go out of your way to avoid AC, and that’s the whole point of the paper. Still, it’s not like you were ever doubting AC — more like you have a multifaith personality.

Belief system is what it sounds like. If you are a working mathematician you probably already have a lot of opinions on a wide range of research questions, conjectures, etc. For example, maybe you accept some conjectures like Riemann Hypothesis, reject others like Navier-Stokes, remain very interested but undecided on problems like P vs. NP, and couldn’t care less about others like Yang-Mills. It’s all well and good, obviously.

There are many more shades of gray here. For example, you might believe in the abc conjecture, think that it hasn’t been proved yet, but willing to use it to prove other results whatever the status. Or perhaps, you believe that Goldbach’s conjecture is definitely true, that it’s a matter of time until it’s proved, but are completely unwilling to use it as an assumption (I used it as an assumption once, maddening some old school referees; luckily the odd version of GC holds and was sufficient). Or perhaps you are aware that the original proof of the Lyusternik-Schnirelmann theorem on three closed geodesics had major issues, as were many subsequent proofs of the theorem; still you are willing to trust Wikipedia that the theorem is true because you don’t care all that much anyway.

Ideally, you should question your beliefs whenever possible. If you are thinking about a conjecture, are you sure you believe in it? Maybe you should try to disprove it instead? It’s ok to change your mind, to try both directions, to believe or even to disbelieve all authorities on the matter. I have written extensively about the issue in this blog post, so let’s not rehash it.

One more thing about a belief system is that different beliefs usually have different levels of confidence. Some beliefs are core and people rarely change their mind. These don’t fall into faith category, in a sense that different people can have different core beliefs, sometimes in contradiction with each other. This is usually why a vast majority might strongly believe some conjecture is true, while a vocal minority might believe it’s false just as strongly.

For example, some people believe that mathematical order is absolutely fundamental, and tend to believe that various structures bring such an order. My core belief is sort of the opposite — because of whatever childhood trauma I experienced, I believe in universality theorems (sometimes phrased as Murphy’s law), that things can be wildly complicated to the extreme unless there is a good reason for them not to. Mnëv’s universality theorem is perhaps the most famous example, but there are many many others. This is why I disprove conjectures often enough and prove many NP– and #P-completeness results — these are different manifestations of the same phenomenon.

Religion is what you do with your belief system, as in practicing religion. If you have a lot of beliefs that doesn’t make you smart. That makes you opinionated. To be considered smart you need to act on your beliefs and actually prove something. To be considered wise you need the ability to learn to adjust your belief system to avoid contradictions with your other beliefs as new evidence emerges, and make choices that lead somewhere useful.

In mathematics, to practice an organized religion is to be professional, when you get paid for doing research. The process is fundamentally communal involving many people playing different roles (cf. this Thurston’s MO answer). Beside the obvious — researcher, editor, referee, publisher — there are many others. These include colleagues inviting you to give talks, departmental committees promoting you based on letter written by your letter writers. Some graduate students will be studying and giving talks on your work, others will be trying to simplify the arguments and extend them further. The list goes on.

In summary, it is absolutely ok to be an amateur and have your own religious practice. But within a community of like-minded scholars is where your research becomes truly valuable.

Miracles are the most delightful things that ever happen to you when learning or when doing mathematical research. It’s when you discover somethings, perhaps even prove that it works, but remain mystified as to why? What exactly is going on that made this miracle happen? Over time, you might learn one or several reasons, giving you a good explanation after the fact. But you have to remember your first impression when you just learned about the miracle.

It’s even harder to see and acknowledge miracles in celebrated textbook results. You have to train yourself to see the miracles for what they are, rather than for what they now appear to be when textbook packages them in neat nice boxes with a bow on top. One way to remind yourself of miracle powers is to read “Yes, Virginia“ column that I mentioned in this holiday post — it will melt you heart! Another way is to teach your favorites — when you see a joyful surprise in your students’ eyes, you know you just conveyed a miracle!

This may depend on your specific area, but in bijective combinatorics you have to believe in miracles! Otherwise you can never fully appreciate prior work, and can never let yourself loose enough to discover new miracles. To give just one example, the RSK correspondence is definitely on everyone’s the top ten list of miracles in the area. By now there are at least half a dozen ways to understand and explain it, but I still consider RSK to be a miracle.

Of course, one should not get overexcited about every miracle they see and learn to look deeper. For example, a combinatorial interpretation of Littlewood–Richardson coefficients is definitely a miracle, no doubt about it. But after some meditation you may realize that it’s really the same miracle as RSK (see §11.4 in my OPAC survey).

Backstory of the bunkbed conjecture paper

After I wrote this blog post about our disproof of the Bunkbed Conjecture (BBC), the paper became viral for 15 minutes. Soon after, I received several emails and phone calls from journalists (see links in the P.P.S. of that post). They followed the links to my earlier blog post about disproofs of conjectures and asked me questions like “What is the next conjecture do you plan to disprove?” and “Do you think disproving conjectures is more important than proving them?” Ugh… 😒

While that earlier post was written in a contrarian style, that was largely for entertainment purposes, and not how I actually think about math. Rather, I have an extensive somewhat idiosyncratic belief system that sometimes leads me think that certain conjectures are false. But breaking with conventional wisdom is a long and occasionally painful process. Worse, being a contrarian gives you a bad rap as you are often get confused with being nihilistic.

So let me describe how I came to believe that BBC is false. I was asked this multiple times, always declining out of fear of being misunderstood and misquoted. but it’s a story worth telling.

This all started with my long FOCS paper (joint with Christian Ikenmeyer), where we systematically studied polynomial inequalities and developed a rather advanced technology to resolve questions like “which of these can be proved combinatorially by a direct injection?” To give a basic example, if the defect (difference between two sides) is a polynomial that is an exact square, then the polynomial is obviously nonnegative but it often can be shown that the defect has no combinatorial interpretation, i.e. not in #P. See more in this blog post on this.

Now, I first learned about the Bunkbed Conjecture soon after coming to UCLA about 15 years ago. Tom Liggett who was incredibly kind to me, mentioned it several times over the years, always remarking that I am “the right person” to prove it. Unfortunately, Tom died just four years ago, and I keep wondering what he would have made of the story…

Anyway, when writing my OPAC survey two years ago, I was thinking about the problem again in connection to combinatorial interpretations, since BBC becomes a polynomial inequality when all edge probabilities are independent variables. Like everyone else, I assumed that BBC is true. But I figured that the counting version is not in #P since otherwise a combinatorial proof would have been found already (since many strong people have tried). So I made this into Conjecture 5.5 in the OPAC paper, and suggested it to my PhD student Nikita Gladkov.

I believed at that time that there must be a relatively small graph on which the BBC defect will be a square of some polynomial, or at least some positive polynomial (on a [0,1]ⁿ hypercube of n variables) with negative coefficients. That was our experience in the FOCS paper. Unfortunately, this guess was wrong. In our numerous experiments, the polynomials in the defect seemed to have positive coefficients without an obvious pattern. It was clear that having a direct injective proof would have been a miracle, the kind of miracle that one shouldn’t expect in the generality of all graphs.

This led to a belief contradiction — either a stronger version of BBC holds for a noncombinatorial reason, or BBC is false. In the language above, I had a core belief in the power of combinatorial injections when there are no clear obstructions. On the other hand, I had only a vague intuition that BBC should hold because it’s the most natural thing and because if true it would bring a bit of order to the universe. So I changed my mind about BBC and we started looking for a counterexample.

Over the next two years I asked about BBC to everyone I met, suggesting that it might be false in hope someone, anyone, gives a hint on how to proceed and what to rule out. Among those who knew and had an opinion about the problem, everyone was sure it’s true. Except for Jeff Kahn who lowered his voice and very quietly told me that he also thinks it’s false, but made me a promise not to tell anyone (I hope it’s ok now?) I think he was hinting I shouldn’t say these things out loud to avoid getting the crank reputation. I didn’t listen, obviously. Not being in the area helped — nobody took me seriously anyway.

In the meantime, Nikita and his friend Alexander Zimin made quite a bit of effort to understand multiple correlation inequalities (FKG style) for percolation on general graphs. This eventually led to the disproof as explained in the BBC blog post mentioned above.

Schubert positivity

In Algebraic Combinatorics, Schubert coefficients are nonnegative integers which generalize the Littlewood-Richardson (LR) coefficients mentioned above. Since the latter have extremely well studied combinatorial interpretations, the early hope was that Schubert coefficients would also have one. After decades of effort and advances in a handful of special cases, this became a major open problem in the area, the subject of numerous talks and papers.

I never believed this hope, not for a second. In the OPAC survey, I stated this as a conjecture: “Schubert coefficients are not in #P” (see Conj. 10.1). Again, this not because I was a contrarian — I had my reasons, three in fact.

First, that’s because I studied the miracle of RSK and the related miracle of LR-coefficients for over thirty years (yes, I am that old!) As a bijection, RSK is extremely rigid. So if any of the (essentially equivalent) combinatorial interpretations of LR-coefficients could generalize directly, it would have been done already. However, the progress has been exceedingly difficult (see e.g. Knutson’s 2022 ICM paper).

Second, I also have a strong belief that miracles are rare and don’t happen to the same combinatorial objects twice for different reasons. This is a variation on “lightening doesn’t strike twice” idea. It is in principle possible that LR-coefficients have a completely new combinatorial interpretation radically different from the 20+ combinatorial interpretations (see OPAC survey, §11.4), all of them related by relatively easy bijections. But I had my doubts.

Third, I knew quite a bit about efforts to find a combinatorial interpretation for Kronecker coefficients which also generalize LR-coefficients in a different direction. Joint with Greta Panova, I have written extensively on the subject. I was (still am) completely confident that Kronecker coefficients are not in #P for many reasons too long to list (this is Conjecture 9.1 in my OPAC survey). So I simply assumed that Schubert coefficients are also not in #P, by analogy.

Having concluded that one should work in the negative direction, Colleen and I made a major effort towards proving that Schubert coefficients are not in #P, aiming to emulate the strategy in my paper with Chan, and in earlier work with Ikenmeyer and Panova. The basic idea is to show that the positivity problem is not in the polynomial hierarchy PH, which would imply that the counting problem is not in #P. We failed but in a surprisingly powerful way which led me to rethink my whole belief system when it comes to Schubert calculus.

By the Schubert positivity problem we mean the decision problem that Schubert coefficients are positive. This problem is a stepping stone towards finding a combinatorial interpretation, and is also of independent interest. In our previous paper with Colleen, we proved that the positivity problem is in the complexity class AM assuming the Generalized Riemann Hypothesis (GRH). This is a class that is sandwiched between first and second level of the polynomial hierarchy, so in particular in contains NP and BPP, and is contained in Π₂. In particular, my dream of proving that the positivity problem is not in PH was doomed from the start (assuming PH does not collapse).

Now that that Schubert positivity is in PH this explains the earlier failures, but leaves many questions. First, should we believe that Schubert coefficients are in #P? That would imply that Schubert positivity is in NP, a result we don’t have. Second, where did we go wrong? Which of my beliefs were mistaken, and what does that say about the rest of my belief system?

Let me start with the second which easier to answer. I continue to stand by our first belief (the miracle of RSK and LR) — this is going nowhere. I am no longer confident in the second belief. It is possible that #P is so much larger than traditional combinatorial interpretations that there is more to the story. And lightnings can strike twice if the buildings are especially tall…

More importantly, I now completely reject the third belief of analogy between Kronecker and Schubert coefficients. While the former is fundamentally representation-theoretic (RT), as our proof shows the latter is fundamentally algebro-geometric (AG). They have nothing in common except for the LR-coefficients. At the end, while we proved that Schubert positivity is in AM (assuming GRH) using the Hilbert’s Nullstellensatz, a key problem in AG.

Faced with a clash of core beliefs, Colleen and I needed to completely rethink the strategy and try to explain what do our results really mean? Turned out, my issues were deeper than I thought. At the time I completely lacked faith in derandomization, which is getting close to be a foundation belief in computational complexity, on par with P ≠ NP. I was even derisive about it in the P.S. to my BBC blog post.

On a personal level, saying that P = BPP is weird, or at least unintuitive. It contradicts everything I know about Monte Carlo methods used across the sciences. It undermines the whole Markov chain Monte Carlo technology I worked on in my PhD thesis and as a postdoc. I even remember a very public shouting match on the subject between the late Steven Rudich and my PhD advisor Persi Diaconis — it wasn’t pretty.

After talking to Avi Wigderson while at IAS, I decided to distance myself and think rationally rather than emotionally. Could P = BPP be really true? Unless you know much about derandomization, even P = ZPP seems unmotivated. But these conjectures have a very good reason in their favor.

Namely, the Impagliazzo–Wigderson’s theorem says that under a reasonable extension of the exponential time hypothesis (EHT), itself an advance extension of P ≠ NP, we have P = BPP. Roughly speaking, if hard NP problems are truly hard (require exponential size circuits), one can simulate binary strings by embedding meshed up solutions into the strings which then look random in a sense of poly-time algorithms can’t tell them apart. This is extremely vague and somewhat misleading — read up more on this in Vadhan’s monograph (Chapter 7).

There is also a CS Theory community based argument. In this 2019 poll conducted by Gasarch, there is near unanimous 98% belief that P = BPP by the “experts” (others people were close to even split). Given that P ≠ NP has 99% belief by the same experts, this crosses from speculation to the standard assumption territory. So it became clear that I should completely switch my core belief from P ≠ BPP to P = BPP.

And why not? I have blindly believed the Riemann Hypothesis (RH) for decades without any in-depth knowledge of analytic number theory beyond a standard course I took in college. I am generally aware of applications of RH across number theory and beyond, see quotes and links here, for example. From what I can tell, RH withstood all attempts to disprove it numerically (going back to Turing), and minor dissents (discussed here) do not look promising.

This all reminded me of a strange dialogue I had with Doron Zeilberger (DZ) over lunch back in October, when we went to celebrate the BBC disproof:

DZ: What conjectures do you believe? Do you believe that RH is true?

IP: I am not sure. Probably, but I don’t have enough intuition either way.

DZ: You are an idiot! It’s 100% true! Do you believe that P ≠ NP?

IP: Yes, I do.

DZ: Ok, you are not a complete idiot.

Anyway, back to the story. I figured that if you believe in RH you may as well believe in GRH. And if you believe in P ≠ NP you may as well believe in ETH. And if you believe in ETH you may as well believe in the Impagliazzo–Wigderson’s Assumption (IWA) which implies that P = BPP. And if you believe in IWA you may as well believe in the Miltersen–Vinodchandran Assumption (MVA) which is an interactive proof version of IWA introduced in this paper, and which implies that NP = AM. Once you break this it into steps, the logic of this implication becomes clear and the conclusion extremely believable.

Having thought through these implications, Colleen and I wrote this note which prompted this blog post. We aim at people in algebraic combinatorics and obtain the following:

Main Theorem [Robichaux–P.] Schubert positivity is in NP (i.e., has a positive rule) assuming GRH and MVA.

The theorem is the closest we got to proving that Schubert coefficients are in #P. The note is written in a somewhat unusual style, explaining the results and refuting potential critiques. Quotes by Poincaré and Voltaire are included in support of the case. Check it out!

In summary, the theorem above completely resolves the Schubert positivity problem albeit conditionally and from computational complexity point of view. It assumes two very hard conjectures, each stronger than a million dollar problem. But so what? It’s not even the first theorem which assumes two million dollars worth of conjectures (it’s a long article — search for “two million dollars”). And with inflation, one million in 2000 is about two millions now, so it’s probably ok to assume two such conjectures in one theorem anyway… 😉

Happy Holidays! Happy New Year! Best wishes everyone!