Archive
On faith, religion, conjectures and Schubert calculus
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]n 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 Π2. 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!
Concise functions and spanning trees
Is there anything new in Enumerative Combinatorics? Most experts would tell you about some interesting new theorems, beautiful bijections, advanced techniques, connections to other areas, etc. Most outsiders would simply scoff, as in “what can possibly be new about a simple act of counting?” In fact, if you ask traditional combinatorialists they would be happy to tell you they they like their area to be trend-resistant. They wouldn’t use these words, obviously, but rather say something about timeless, or beautiful art, or “balls in boxes”. The following quote is a classic of this genre:
Combinatorialists use recurrence, generating functions, and such transformations as the Vandermonde convolution; others, to my horror, use contour integrals, differential equations, and other resources of mathematical analysis. (J. Riordan, Combinatorial identities, 1968)
If you’ve been reading this blog for a while, then you already know how I feel about such backward-looking views. When these win, the area becomes stale, isolated, and eventually ignored by both junior researchers and the “establishment” (leading math journals, granting agencies, etc.) Personally, I don’t I don’t see this happening in part due to the influence of Theoretical Computer Science (TCS) that I discussed back in 2012 in this blog post.
In fact, the influence of TCS is so great on all aspects of Combinatorics (and Mathematics in general), let me just list three ideas with the most impact on Enumerative Combinatorics:
- Thinking of a “closed formula” for a combinatorial counting function as algorithm for computing the function, leading to Analysis of Algorithms type analysis (see Wilf’s pioneer article and my ICM paper).
- The theory of #P-completeness (and related notions such as #P-hard, #EXP-complete, class GapP, etc.) explaining why various functions do not have closed formulas. This is now a core part of Computational Complexity (see e.g. Chapter 13 in this fun textbook).
- The idea that a “combinatorial interpretation” is simply a function in #P. This is my main direction these days, see this blog post, this length survey and this OPAC talk and this StanleyFest talk.
All three brought remarkable changes in the way the community understands counting problems. In my own case, this led to many interesting question resulting in dozens on papers. Last year, in the middle of a technical complexity theoretic argument, I learned of a yet another very general direction which seem to have been overlooked. I will discuss it briefly in this blog post.
Complete functions
Let A be a set of combinatorial objects with a natural parametrization: A = ∪ An. For example, these can be graphs on n vertices, posets on n elements, regions in the square grid with n squares, etc. Let f: A → N be a function counting objects associated with A. Such functions can be, for example, the number of 3-colorings or the number of perfect matchings of a graph, the number of order ideals or the number of linear extensions of a poset, the number of domino tilings of a region, etc.
We say that f is complete if f(A)=N. Similarly, f is almost complete if f(A) contains all sufficiently large integers. For example, the number of perfect matchings of a simple graph is complete as can be seen from the following nice construction:
Moreover, the number of domino tilings of a region in Z2 is complete since for every integer k, there is a staircase-type region like you see below with exactly k domino tilings (this was observed in 2014 by Philippe Nadeau).
In fact, most natural counting functions are either complete or almost complete. For example, the number of spanning trees of a simple graph is almost complete since the number of spanning trees in an n-cycle is exactly n, for all n>2. Similarly, the number of standard Young tableaux |SYT(λ)| of a partition λ is almost complete since |SYT(m,1)|=m. Many other natural examples are in our paper with Swee Hong Chan (SHC) which started this investigation.
Concise functions
Let f be an almost complete function. We say that f is concise if for all large enough k, there exist an element a ∈ An such that f(a) = k and n < C (log k)c, for some C, c>0. Just like explicit constructions in the context of Graph Theory (made famous by expanders), this notion makes perfect sense irrespectively from our applications in computational complexity (see our paper with SHC linked above).
Note that none of the simple constructions mentioned above imply that the corresponding functions are concise. This is because the size of combinatorial objects is linear in each case, not poly-logarithmic as we need it to be. For the number of perfect matchings, an elegant construction by Brualdi and Newman (1965) shows that one can take n = O(log k). This is the oldest result that we know, that some natural combinatorial counting function is concise.
For the number of domino tilings, SHC and I proved an optimal bound: there is a region with O(log k) squares with exactly k domino tilings. The proof is entirely elementary, accessible to a High School student. The idea is to give explicit transformations k → 2k and k → 2k-1 using gadgets of the following kind:
As always, there are minor technical details in this construction, but the important takeaway is that we obtain an optimal bound, but the regions we construct are not simply-connected. For simply-connected regions the best bound we have is O(log k log log k) for the snake (ribbon) regions, via connection to continued fractions that was recently popularized by Schiffler. Whether one can obtain O(log k) bound in this case is an interesting open problem, see §6.4 in our paper with SHC.
Many concise functions
For the number of spanning trees, whether this function is concise remained an open problem for over 50 years. Even a sublinear bound was open. The problem was recently resolved by Stong in this beautiful paper, where he gave O((log k)3/2/(log log k)) upper bound. Sedláček (1967) conjectured that o(log k) bound for general graphs, a conjecture which remains wide open.
For some functions, it is easy to see that they are not concise. For example, for a partition λ of n, the number of standard Young tableaux |SYT(λ)| is a divisor of n! Thus, for k prime, one cannot take n<k in this case.
Curiously, there exist functions, for which being almost complete and concise are equivalent notions. For example, let T ∈ R2 be a set of n points in general positions in the plane. Denote by g(T) the number of triangulations of T. Is g almost complete? We don’t know but my guess is yes, see Conjecture 6.4 in our paper with SHC. However, we do know exponential lower and upper bounds Cn < g(T) <Dn. Thus, if g is almost complete it is automatically concise with an optimal O(log k) upper bound.
Our final example is much too amusing to be skipped. Let e(P) denote the number of linear extensions of a poset on n elements. This function generalized the number of standard Young tableaux, and appears in a number of applications (see our recent survey with SHC). Tenner proved a O(√k) bound, the first sublinear bound. The conciseness was shown recently by Kravitz and Sah, where they established O(log k log log k) upper bound. The authors conjectured O(log k) bound, but potentially even O((log k)/(log log k)) might hold.
Consider now a restriction of the function e to posets of height two. In our paper with SHC, we have Conjecture 5.17 which claims that such e is still almost complete. In other words, for all large enough k, one can find a poset of height two with exactly k linear extensions. Since the number of linear extensions of such posets is at least (n/2)!2 this would give an optimal bound for general posets as well, so a very sharp extension of the Kravitz–Sah bound. We should mention an observation of Soukup (p. 80), that 13,168,189,439,999 is not the number of linear extensions of a height two poset. This suggests that our conjecture is either false, or likely to be very hard.
Latest news: back to spanning trees
In our most recent paper with Swee Hong Chan and Alex Kontorovich, we resolve one Sedláček’s question and advance another. We study the number τ(G) of spanning trees in a simple planar graph G on n vertices. This function τ is concise by Stong’s theorem (his construction is planar), and it is easy to show by planarity that τ(G) < 6n. Thus, a logarithmic upper bound O(log k) is the best one can hope for. Clearly, proving such result would be a major advancement over Stong’s poly-logarithmic bound.
While we don’t prove O(log k) bound, we do get very close — we prove that this bound holds for the set of integers k of density 1. The proof is both unusual (to me as a combinatorialist), and involves a mixture of graph theory, number theory, ergodic theory, and some pure luck. Notably, the paper used the remarkable Bourgain–Kontorovich technology developed towards the celebrated Zaremba’s Conjecture. You can read it all in the paper or this longish post by Alex.
P.S. Being stubborn and all, I remain opposed to the “unity of mathematics” philosophy (see this blog post which I wrote about the ICM before later events made it obsolete). But I do understand what people mean when they say these words — something like what happened in our paper with Alex and Swee Hong with its interdisciplinary tools and ideas. And yet, to me the paper is squarely in Combinatorics — we just use some funky non-combinatorial tools to get the result.
The bunkbed conjecture is false
What follows is an unusual story of perseverance. We start with a conjecture and after some plot twists end up discussing the meaning of truth. While the title is a spoiler, you might not be able to guess how we got there…
The conjecture
The bunkbed conjecture (BBC) is a basic claim about random subgraphs. Start with a finite graph G=(V,E) and consider a product graph G x K2 obtained by connecting the corresponding vertices on levels V(1) and V(2). Sort of like a bunkbed. Now consider random subgraphs of a this product graph.
Bunkbed Conjecture: The probability that vertices u(1) and v(1) are connected is greater or equal than the probability that vertices u(1) and v(2) are connected.
In other words, the probability of connecting two vertices on the same level cannot be smaller than when connect vertices on different levels. This is completely obvious, of course! And yet the conjecture this problem defeated several generations of probabilists and remained open until now. For a good reason, of course. It was false!
The origins of the conjecture are murky, but according to van den Berg and Kahn it was conjectured by Kasteleyn in the early 1980s. There are many versions of this conjecture; notably one can condition on the subset of vertical edges and ask the same question. Many partial results are known, as well as results for other probabilistic models. The conjecture is false nonetheless!
The direction
Why look for a counterexample if the conjecture is so obviously true? Well, because you always should. For any conjecture. Especially if everyone else is so sure, as in completely absolutely sure without a doubt, that the conjecture is true. What if they are all wrong? I discuss this at length in this blog post, so there is no need to rehash this point.
The counterexample
We disprove the conjecture in a joint paper with Nikita Gladkov (UCLA) and Alexandr Zimin (MIT), both graduate students. Roughly speaking we take the following 3-hypergraph from a recent paper by Hollom.
We then replace each yellow triangle with the following gadget using n=1204, placing a in the shaded vertex, while v1 and vn are placed in the other vertices of the triangle (so the red path goes into the red path). For a stronger version of the conjecture that’s all there is. For a weaker version, some additional tweaks needed to be made (they are not so important). And we are done!
The resulting graph is has 7523 vertices and 15654 edges. The difference between probabilities for paths between u1 and u10 at the same and different levels as in the conjecture is astronomically small, on the order of -10-6500. But it’s negative, which is all we need. Very very roughly speaking, the red path is the only path which avoids shaded vertices and creates a certain bias which give this probability gap. Formalizing this is a bit technical.
The experiments
Of course, the obvious way to verify our counterexample computationally would fail miserably — the graph is much too large. Instead, we give a relatively elementary completely combinatorial disproof of the BBC that is accessible to a wide audience. I would rather not rehash technical details and ideas in the proof — it’s all in our paper, which is only 12 pages! See also the GitHub code and some explanation.
I do want to mention that giving formal disproof was not our first choice. It’s what we ended up doing after many failures. There is always a bit of a stigma people have about publicly discussing their failures. I know very few examples, only this one famous enough to be mentioned. So let me mention briefly how we failed.
Since I was sure the bunkbed conjecture is false (for reasons somewhat different from my contrarian philosophy), we started with a myriad of computer experiments trying all small graphs. When those failed, we tried to use AI and other computer assisted tools. We burned many hours on a giant UCLA Hoffman2 Cluster getting closer for a while. In hindsight, we didn’t look in the right place, obviously. After several months of computer experiments and no clear counterexample, it felt we are wasting time. We then thought a bit more about philosophy of what we are doing and stopped.
Before I tell you why we stopped, let me make a general recommendation. Please do try computer experiments for whatever you are working on. Make an effort to think it through and design a good experiment. Work hard to test as much as your computer technology allows. If you need some computing power, ask around. Your university might just have the resources. Occasionally, you can even ask a private company to donate theirs.
If you succeed, write a paper and publish it. Make your code and work notes publicly available. If you fail, do exactly the same. If the journals refuse to publish your paper, just keep it on the arXiv. Other people in your area would want to know. And as far as the NSF is concerned, all of this is “work product”. You can’t change the nature of the problem and the results you are getting, but you deserve the credit regardless.
Let me repeat: Do not fear telling other you have not succeeded in your computer testing. Fear others making the same mistakes or repeating the same work that you did.
The curse
One reason we stopped is because in our initial rush to testing we failed to contemplate the implications of Monte Carlo testing of even moderately large graphs. Here is a quote from the paper:
Suppose we did find a potential counterexample graph with only m=100 edges and the probability gap was large enough to be statistically detectable. Since analyzing all of 2m ≈ 1030 subgraphs is not feasible, our Monte Carlo simulations could only confirm the desired inequality with high probability. While this probability could be amplified by repeated testing, one could never formally disprove the bunkbed conjecture this way, of course.
This raises somewhat uncomfortable questions whether the mathematical community is ready to live with an uncertainty over validity of formal claims that are only known with high probability. It is also unclear whether in this imaginary world the granting agencies would be willing to support costly computational projects to further increase such probabilities (cf. [Garrabrant+’16], [Zeilberger’93]). Fortunately, our failed computational effort avoided this dystopian reality, and we were able to disprove the bunkbed conjecture by a formal argument.
Societal implications aside, it is an interesting question whether a reputable math journal should accept a counterexample that is tested with 99.99% confidence, and the results can be replicated and rechecked by others. Five sigma may be a gold standard in nuclear physics, but math journals tend to prefer 100% correctness (even though some papers they publish are 100% incorrect).
What I do know, is that most journals would refuse to even consider a “five sigma counterexample”. While details of the situations differ quite a bit, I knew what happened to the (rather interesting) Sills–Zeilberger paper, which was eventually published, but not after several desk rejections. But PhD students need jobs in reality, not in theory. That is really why we stopped. Why persevere and create controversy when you can just try doing something else?
P.S. There is yet another layer to all of this. Back in 1999, I asked Avi Wigderson if P=BPP? He said “Yes“. Last week I asked him again. This is 25 years later, almost to the day. He said “Yes, I am absolutely sure of that.” It’s one of his favorite conjectures, of course. If he is right, every probabilistic counterexample can be turned into deterministic. In other words, there would be a fully rigorous way to estimate both probabilities and prove on a computer that the conjecture is false. But you must have guessed what I was thinking when I heard what he said — now he used “absolutely sure“…
P.P.S. There is a very nice YouTube video about our paper made by Trefor Bazett. Another (even better) YouTube video by Johann Beurich (in German). See also this article in Quanta Magazine, this in IFLScience, that in Pour la Science (in French) and that in Security Lab (in Russian) about our work and this blog post.
UPDATE (June 13, 2025). This took awhile, but the paper was just published at PNAS.
We deserve better journals
By and large, math journals treat the authors like a pesky annoyance, sort of the way a local electric company treats its customers. As in — yes, serving you is our business, but if you don’t like our customer service where else are you going to go? Not all editors operate that way, absolutely not all referees, but so many it’s an accepted norm. We all know that and all play some role in the system. And we all can do better, because we deserve better.
In fact, many well meaning mathematicians do become journal editors, start new journals, and even join the AMS and other professional societies’ governing bodies which oversee the journals. This helps sometimes, but they quickly burn out or get disillusioned. At the end, this only makes second order improvements while the giant sclerotic system continues its descent from bad to worse.
Like everyone else, I took this as a given. I even made some excuses: evil publishers, the overwhelming growth of submissions, everyone stressed and overworked, papers becoming more technical and harder to referee, etc., etc. For decades I watched many math journals turn from friendly if not particularly warm communal endeavors, to zones of hostility.
Only most recently, it occurred to me that it doesn’t have to be this way. We should have better journals, and we deserve a better treatment (I was really off the mark in my first line of this post). Demanding better journals is neither a fantasy nor a manifesto. In fact, physicists have already figured it all out. This post is largely about how they do it, with some lessons and suggestions.
What we have
If you don’t know what I am talking about, walk to any mathematician you see at a conference. If you have a choice, choose the one who looks bored, staring intensely at their shoes. Ask them for their most frustrating journal publishing story. You may as well sit down — the answer might take awhile. Even if they don’t know you (or maybe especially if they don’t know you), they will just unload a litany of the most horrifying stories that would make you question the sanity of people staying in this profession.
Then ask them why do they persevere and keep submitting and resubmitting their papers given that the arXiv is a perfectly fine way to disseminate their work. You won’t hear a coherent answer, but rather the usual fruit salad of practical matters: something about jobs, CVs, graduate students, grants, Deans, promotions, etc. Nobody will ever mention that their goal is to increase their readership, verify the arguments, improve their presentation style, etc., ostensibly the purpose of mathematical journals.
While my personal experience is a relatively happy one, I do have some scars to show and some stories to tell (see this, that and a bit in that blog posts on publishing struggles). There is no need to rehash them. I also know numerous stories of many people because I have asked them these questions. In fact, every time I publish something like this blog post (about the journals’ hall of shame), I get a host of new horror stories by email, with an understanding that I am not allowed to share them.
The adversarial relationship and countless bad experiences make it is easy to lose sight of the big picture. In many ways we are privileged in mathematics to have relatively few bad and for-profit actors. Money and grant funding matters less. We don’t have extreme urgency to publish. We have some relatively objective ways to evaluate papers (by checking the proofs). One really can work on the Moon, as long as one has a laptop and unlimited internet (and breathable air, I suppose).
We have it good, or at least we did when we started sliding into abyss. Because the alarms are not ringing, the innovation in response has stuttered. We are all just chugging along. Indeed, other than a few new online journals, relatively little has changed in the past two decades.
This is in sharp contrast with physics, which had very few of the advantages that math has (depending on the area). Besieged on all sides, physics community was forced to adapt faster and arguably better in response to changes in the publishing landscape. In fact, the innovations they made are so natural to them, their eyes open wide in disbelief when they hear how we continue to publish math papers.
The following is a story of the Physical Review E (PRE), one of the journals of the American Physical Society (APS). I will start with what I learned about the PRE and APS inner working, their culture, successes and challenges, some of which ring very familiar. Only afterwards I will get back to math publishing, the AMS and how we squandered our advantages.
What’s special about PRE?
I chose to write about the PRE because I published my own paper there and enjoyed the experience. To learn more about the journal, I spoke to a number of people affiliated with PRE in different capacities, from the management to members of the Editorial Board, to frequent authors and reviewers. These interviews were rather extensive and the differences with the math publishing culture are much too vast to summarize in a single blog post. I will only highlight things I personally found remarkable, and a few smaller things that can be easily emulated by math journals.
PRE’s place in the physics journal universe
PRE is one of five similarly named “area journals”: PRA, PRB, etc. More generally, it is one of 18 journals of the APS. Other journals include Physical Review Letters (PRL is APS’s flagship journal which published only very short papers), Physical Review X (PRX is another APS’s leading journal, online only, gold open access, publishes longer articles, extremely selective), Reviews of Modern Physics (APS’s highest cited journal which publishes only survey articles), and a number of more specialized journals.
The APS is roughly similar to the the AMS in its prominence and reach in the US. APS’s main publishing competition include the Institute of Physics (IOP, a UK physics society with 85 titles, roughly similar to the LMS), Nature Portfolio (a division of Springer Nature with 156 titles only a few of them in physics), and to a lesser extent Science by AAAS, various Elsevier, SIAM journals, and some MDPI titles.
Journal structure
The PRE editorial structure is rather complicated. Most of the editorial work is done by an assortment of Associate Editors, some of whom are employed full time by the APS (all of them physics PhD’s), and some are faculty in physics or adjacent fields from around the world, typically full time employed at research universities. Such Associate Editors receive a 2 year renewable contract and sometimes work with the APS for many years. Both professional and part time editors do a lot of work handling papers, rejecting some papers outright, inviting referees, etc.
The leadership of PRE is currently in flux, but until recently included Managing Editor, a full time APS employee responsible for running the journal (such as overseeing the work of associate editors), and a university based Lead Editor overseeing the research direction. The APS is currently reviewing applications for a newly created position of Chief Editor who will presumably replace Managing Editor, and is supposed to oversee the work of the Lead Editor and the rest of the editorial team (see this ad).
There is also an “Editorial Board”, whose name might be confusing to math readers. This is really a board of appeals (more on this later), where people serve a 3 year term without pay, giving occasional advice to associate editors and lending their credibility to the journal. Serving on the Editorial Board is both a service to the community and minor honor.
Submissions
The APS is aware of the role the arXiv plays in the community as the main dissemination venue, with journals as an afterthought. So it encourages submissions consisting of arXiv numbers and subject areas. Note that this makes it different from Nature and Science titles, which forbid arXiv or other online postings both for copyright reasons and so not to spoil future headline worthy press releases.
The submissions to all APS journals are required to be in a house two column style with a tiny font. Тhere are sharp word count limits for the “letters” (short communications) and the “articles”. These are rather annoying to calculate (how do you count formulas? tables?), and the journals’ online software is leaves much to be desired.
Desk rejections
At PRE, about 15-20% of all papers are rejected within days after the initial screening by managing or associate editors, who then assign the remaining papers according to research areas. Some associate editors are reluctant to do this at all, and favor at least one report supplemented by initial judgement. This percentage is a little lower than at the (more selective) PRL where it is reported to be 20-25%. Note that all APS journals pay special attention to the style, so it’s important to make an effort to avoid being rejected by a non-expert just because of that.
Curiously, before 2004, the percentage was even lower at PRL, but the APS did some rather interesting research on the issue. It concluded that such papers consume a lot of resources and rarely survive the review process (see this report). Of course, this percentage is relatively low by math standards — several math journals I know have about 30-50% desk rejections, with another 30-40% after a few quick opinions. On the other hand, at Science, over 83% papers get rejected without an external review.
Review process
Almost all the work is handled by associate editors closest to the area. The APS made a major overhaul of its classification of physics areas in 2016, to bring it to modern age (from the old one which resembles the AMS MSC). Note aside: I have been an advocate for an overhaul of MSC for a while, which I called a “historical anachronism” in this long MO answer (itself written about 14 years ago). At the very least the MSC should upgrade its tree structure (with weird horizontal “see also…” links) to a more appropriate poset structure.
Now, associate editors start with desk rejections. If the paper looks publishable, they send it to referees with the goal of obtaining two reports. The papers tend to be much shorter and more readable by the general scientific audience compared with the average math paper, and good style is emphasized as a goal. The reviewers are given only three weeks to write the report, but that time can be extended upon request (by a few more weeks, not months).
Typically, editors aim to finish the first round in three months, so the paper can be published in under six months. Only few papers lag beyond six months at which point, the editors told me, they get genuinely embarrassed. The reason is often an extreme difficulty in finding referees. Asking 4-8 potential referees is normal, but on rare occasions the numbers can be as high as 10-20.
Acceptance rate
In total, PRE receives about 3,500-4,000 submissions a year, of which about 55-60% get accepted, an astonishingly high percentage when compared to even second tier math journals. The number of submissions has been slowly decreasing in recent years, perhaps reflecting many new publications venues. Some editors/authors mentioned MDPI as new evil force (I called MDPI parasitic rather than predatory in this blog post).
For comparison, PRL is an even bigger operation which handles over twice as many papers. I estimate that PRL accepts roughly 20-25% of submissions, probably the lowest rate of all APS journals. In a more extreme behavior, Nature accepts about 8% submissions to publish about 800 papers, while Science accepts about 6% submissions to publish about 640 papers per year.
It is worth putting number published paper in perspective by comparing them with other journals. PRE and PRL publish about 1,800 and 2,100 papers per year, respectively. Other APS journals publish even more: PRD publishes about 4,000, and PRB close to 5,000 papers a year.
For math journals true acceptance ratios are hard to find and these numbers tend to be meaningless anyway due to self-selection and high cost of waiting for rejection. But numbers of published papers are easily available: Jour. AMS publishes about 25, Mathematika about 50, Proc. LMS about 60, Forum Math. Sigma in the range of 60-120, Bull. LMS in the range of 100-150, Trans. AMS about 250, Adv. Math. about 350, IMRN in the range of 300-500, and Proc. AMS about 450 papers per year. These are boutique numbers compared to the APS editorial machine. In the opposite extreme, MDPI Mathematics recently achieved the output of about 5,000 papers a year (I am sure they are very proud).
Publication
When a paper is accepted at PRE, it is sent to production which APS outsources. There are two quick rounds of approval of LaTeX versions compiled in the house style and proofread by a professional. It then gets published online with a unique identifier, usually within 2-3 weeks from the date of acceptance. Old fashioned volumes and numbers do exist, but of no consequence as they are functions of the publication date. There is zero backlog.
Strictly speaking there is still a print version of the PRE. I was told it is delivered to about 30 libraries worldwide that apparently are unconcerned with deforestation and willing to pay the premium. In truth, nobody really wants to read these paper versions. The volumes are so thick and heavy, it is hard to even lift them up from a library shelf. Not to dwell on this too much, but some graduate students I know are unaware even which building houses our math library at UCLA. It’s hard to blame them, especially after COVID…
Appeals
When a paper is rejected, the authors have the right to appeal the decision. The paper is sent to a member of the Editorial Board closest to the area. The editor reads both the paper and the referee reports, then writes their own report, which they sign and send to the authors. More often than not the decision is confirmed, but reversals do happen.
Since what’s “important” is ultimately subjective, appeals serve an important check on Associate Editors and helps keep peace in the community. Numerically, only about 3-5% of rejected papers are sent for an appeal, about 2-3 papers per Editorial Board member each year.
Embarrassingly for the whole field, I cannot think of a single math journal with an appeals process (except, interestingly, for MDPI Mathematics, which famously has the selectivity of a waste bucket). Even Nature has an appeals process, and nobody ever thinks of them as too friendly.
Note: some math journals do allow resubmissions of previously rejected papers. These papers tend to be major revisions of previous versions and typically go the same editor, defeating the point of the appeal.
Editorial system
The APS has its own online editorial system which handles the submissions, and has an unprecedented level of transparency compared to that of math journals I am familiar with. The authors can see a complete log of dates of communications with (anonymized) referees, the actions of editors, etc. In math, the best you can get is “under review” which brings cold comfort.
The editors work as a team, jointly handling all incoming email and submission/resubmission traffic. Routine tasks like forwarding the revision to the first round referees are handled by first person available, but the editorial decisions (accept/reject, choices of referees), are made by the assigned Associate Editor. If an Associate Editor has a week long backlog or is expecting some inactivity, his queue is immediately redistributed between other editors.
Relations between APS journals
Many PRE papers first arrive to PRL where they are quickly rejected. The editorial system allows editors from one journal see all actions and reports in all other APS journals. If the rejected PRL paper fits the scope of PRE and there are reports suggesting PRE might be suitable, PRE editors try to invite such papers. This speeds up the process and simplifies life to everyone involved.
For longer papers, PRE editors also browse rejections from PRX, etc. From time to time, business oriented managers at the APS raise a possibility of creating a lower tier journal where they would publish many papers rejected from PRA–PRE (translation: “why shouldn’t APS get some of MDPI money?”), but the approach to maintain standards keep winning for now. From what I hear, this might change soon enough…
Note: In principle, several editorial systems by Elsevier and the like, do allow transferring papers between math journals. In practice, I haven’t seen this feature ever used (I could be wrong). Additionally, often there are firewalls which preclude editors in one journal from see reports in the other, making the feature useless.
Survey articles
The APS publishes Reviews of Modern Physics, which is fully dedicated to survey articles. Associate Editors are given a budget to solicit such articles and incentivize the authors by paying them about $1,500 for completion within a year, but only $750 is the project took longer. The articles vary in length and scope, from about 15 to about 70 pages (when converted from APS to the bulky AMS style, these pages numbers would more than double). There are also independent submissions which very rarely get accepted as the journal aims to maintain its reputation and relevance. Among all APS publications, this journal is best cited by a wide margin.
We note that there are very few math journals dedicated to surveys, despite a substantial need for expository work. Besides Proc. ICM and Séminaire Bourbaki series which are by invitation only, we single out the Bull. AMS, EMS Surveys and Russian Math Surveys (in Russian, but translated by IOP). Despite Rota’s claim “You are more likely to be remembered by your expository work“, publishing surveys remains difficult unless you opt for a special issue or a conference proceedings. In the last two years I wrote two rather long surveys — on combinatorial interpretations and on linear extensions. Word of advice: if you want to have an easy academic life I don’t recommend doing that — they just eat up your time.
At PRE, there are no surveys, but the editors occasionally solicit “perspectives”. These are forward looking articles suggesting important questions and directions (more like public NSF grant applications than surveys). They publish about five such articles a years, hoping to bring the number up to about ten in the future.
Profiled articles
In 2014, following the approach of popular magazines, PRE started making “Editors’ Suggestions”. These are a small number of articles the editors chose to highlight, both formally and on the website. They are viewed as minor research award that can be listed on CVs by the authors.
Outstanding referee award
The APS instituted this award in 2008, to encourage quick and thorough refereeing. This is a lifetime award and comes with a diploma size plaque which can be hang on the wall. More importantly, it can be submitted to your Department Chair and your friendly Dean as a community validation of your otherwise anonymous efforts.
Each year, there are a total of about 150 awardees selected across all APS journals (out of tens of thousands referees), of which about 10 are from PRE. This selection is taken very seriously. The nominations are done by Associate Editors and then discussed at the editorial meetings. For further details, see this 2009 article about the award by the former Editor-in-Chief of Physical Reviews, which ends with
We feel that the award program has been most successful, and we will be continuing it at APS. [Gene D. Sprouse, Recognizing referees at the American Physical Society]
Note that such distinguished referee awards are not limited to APS or even physics. It’s a simple idea which occurred to journals across “practical” disciplines: accounting, finance, economic geography, economics, public management, regional science, etc., but also e.g. in atmospheric chemistry and philosophy. Why wouldn’t a single math journal have such an award?? Count be flabbergasted.
Community relations
As we mentioned above, in much of physics, the arXiv is a preferred publication venue since the field tends to develop at rapid pace, so strictly speaking the journal publications are not necessary. In some areas, a publication in Nature or Science is key to success, especially for a junior researcher, so the authors are often willing to endure various associated indignities (including no arXiv postings) and if successful pay for the privilege. However, in many theoretical and non-headline worthy areas, these journals are not an option, which is where PRL, PRE and other APS journals come in.
In a way, PRE operates as a digital local newspaper which provides service to the community in the friendliest way possible. It validates the significance of papers needed for job related purposes, helps the authors to improve the style, does not bite newcomers, and does not second guess their experimental finding (there are other venues which do that). It provides a quick turn around and rarely rejects even moderately good papers.
When I asked both the editors and the authors how they feel about PRE, I heard a lot of warmth, the type of feeling I have not heard from anyone towards math journals. There is a feeling of community when the editors tell me that they often publish their own papers at PRE, when the authors want to become editors, etc. In contrast, I heard a lot of vitriol towards Nature and Science, and an outright disdain towards MDPI physics journals.
It could be that my sample size was too small and heavily biased. Indeed, when I polled the authors of MDPI Mathematics (a flagship MDPI journal), most authors expressed high level of satisfaction with the journal, that they would consider submitting there again. One of my heroes, Ravi P. Agarwal who I profiled in this blog post, published an astounding 37 papers in that journal, which clearly found its target audience (so much that it stopped spamming people, or maybe it’s just me).
Note aside: Personally, the only journal I actually cared about was the storied JCTA where my senior colleague Bruce Rothschild was the Editor in Chief for 25 years, and where I would publish my best combinatorics papers. In 2020, the editorial board resigned in mass and formed Combin. Theory. I am afraid, my feelings have not transferred to CT, nor have they stayed with JCTA which continues to publish. They just evaporated.
Money matters
Despite a small army of professional editors, the APS journals provide a healthy albeit slowly decreasing revenue stream (about $43 mil. in 2022, combined from all journals, see 2022 tax disclosures on ProPublica website). The journals are turning a profit for the APS (spent on managers and various APS activities) despite all the expenses. They are spending more and making more money than the AMS (compare with their 2022 tax disclosures on ProPublica). There is much more to say here, but this post is already super long and the fun part is only starting.
Back to math journals
In the 20th century world with its print publishing, having a local peer review print journals made sense. A university of a group of universities would join forces with a local publisher and starts the presses. That’s where local faculty would publish their own papers, that’s where they would publish conference proceeding, etc. How else do you explain Duke Mathematical Journal, Israel Journal of Mathematics, Moscow Mathematical Journal, Pacific Journal of Mathematics, and Siberian Journal of Mathematics? I made a lot of fun at the geographical titles in this blog post, and I maintain that they sound completely outdated (I published in all five of these, naturally).
Now, in the 21st century, do we really need math journals? This may sound like a ridiculous question, with two standard replies:
- We need peer review, i.e. some entity must provide a certificate that someone anonymous read the paper and takes responsibility for its validity (sound weak isn’t it?).
- We need formal validation, i.e. we need to have something to write on our CVs. Different journals have different levels of prestige associated with them leading to distinctions in research recognition (and thus jobs, promotions, grants, etc.)
Fair enough, but are you sure that the journals as we have them are the best vehicles for either of these goals? Does anyone really believes that random online journals do a serious peer review? Where is this idea coming from, that the journals with its obvious biases should be conferring importance of the paper?
How are we supposed to use journals to evaluate the candidates, if these journals have uncertain rankings and in fact the relative rankings of two journals can vary depending on the area? Shouldn’t we separate the peer review aspect which makes multiple submission costly and unethical, from the evaluation aspects which desperately needs competition between the journals?
Again, this all sounds ridiculous if you don’t step back and look objectively at our publishing mess where a math paper can languish in journals for over a year, after which it is returned without a single referee report just because someone decided that at the end the paper is not good enough to be refereed. This happened to me multiple times, and to so many other people I lost count (in one instance, this happened after 3 years of waiting!)
Publishing utopia
Now, I know a lot of people whose dream publishing universe is a lot of run-by-mathematicians not for profit small online publications. It’s great to rid of Elsevier and their ilk, but it would not solve the issues above. In fact, this would bring a lot of anarchy and further loss of standards.
From my perspective, in a perfect world, “the people” (or at least the AMS), would create one mega journal, where the arXiv papers could be forwarded by the authors if they wish. Hundreds of editors (some full time, some part time) divided into arXiv subject areas, would make the initial screening, and keep say 30-40% of them to be send for review. Based on my reading of the arXiv stats, that gives about 10-15K papers a year to be refereed, a number way below what APS handles. The mega journal would only check validity and “publish” only based on correctness.
Publication at the mega journal would already be a distinction albeit a minor one. To ensure some competition, we would probably need to break this mega journal into several (say, 3-5) independently run baby megas, so the authors have a choice where to submit. In the utopia I am imagining, the level of rigor would be the same across all baby megas. It would also be a way to handle MDPI journals which would be left with a reject pile.
This wouldn’t take anything away from the top journals (think Annals) who would not want to outsource their peer review. In fact, I heard of major Annals papers studied by six (!) independent teams of referees, that’s above and beyond. But I also heard of Annals papers which seem to had no technical check at all (like this one by this guy), so the quality is maybe inconsistent.
So what about distinctions? The remnants of the existing general journals would be free from peer review. They would place bids on the best papers attracting them “modulo publication in the mega journal” with some clear set deadlines. The authors would accept the best bid, like graduate admissions, and the paper will be linked to the journal website in the “arXiv overlay” style.
Alternatively, some specialized or non-exclusive journals will make their own selections for best papers in their areas, which could be viewed as awards. One paper could get multiple such awards, and “best journal where the paper could be accepted” optimization issue would disappear completely. This would make a better, more fair world. At the very least, such awards would remove the pressure to publish in the top journals if you have a strong result.
Even better, one can imagine a competitive conference system in the style of CS theory conferences (but also in some areas of Discrete Math) emerging in this scenario. The conference submission could require a prior arXiv posting and later keep track of “verified” papers (accepted to the mega journal). When disentangled from the peer review, these conference could lead to more progress on emerging tools and ideas, and to even the playing field for researchers from small and underfunded universities across the world.
Note that there are already some awards for math papers given by third parties, but only a handful. Notably, AIM has this unusual award. More recently, a new Frontiers of Science Award was introduced for “best recent papers” (nice cash prize for a paper already published in the Annals and the like). Of course, most CS theory conferences have been giving them for decades (the papers later get published by the journals).
Would it work? Wouldn’t the mega journal be just another utility company with terrible service? Well, I don’t know and we will probably never get to find out. That’s why I called it a utopia, not a serious proposal. But it can hardly get any worse. I think pure math and CS theory are unique in requiring true correctness. When correctness is disentangled from evaluating novelty and importance, the point of the mega journal would be to help the authors get their proofs right and the papers accepted. Until then, journal editors (and referees to a smaller degree) have a conflict of interest — helping the authors might mean hurting the journal and vice versa. Guess who usually gets hurt at the end?
Back to reality
Obviously, I have no hopes that the “mega journal” would ever come to life. But NOT because it’s technically impossible or financially unsound. In other fields, communities manage somehow. The APS is a workable approximation of that egalitarian idea. Recently, eLife made another major experiment in publishing — we’ll see how that works out.
But in a professional society such as the AMS where new leadership handpicks two candidates for future leadership in a stale election? With a declining membership? Which claims the Fellow of the AMS award as it biggest achievement? Oh, please! Really, the best we can hope for is for a large “lower tier” journals with a high acceptance ratio. Why would AMS want that? I am glad you asked:
Case for higher acceptance rates at AMS journals
One argument why so few papers get published in good (think top 100) math journals is that math papers can be much longer than typical physics papers, so they take more print space and take longer to referee. However, this argument does not translate well into the digital age. Nor does that apply to Bull. LMS or Proc. AMS, of course, which publish mostly short papers. We mention in passing that while greater length is unavoidable sometimes, mathematicians tend to forget that brevity is a feature, not a bug.
Of course, math editors’ main argument in favor of low acceptance ratios is that this allows one to maintain high quality of papers. While true on its face, when applied uniformly this approach has major negative implications to the community.
Think of college acceptance rates. It’s true that Harvard maintains its prestige by having a ridiculously low acceptance ratio, and being private it’s hard to blame it (not that I am fan of the choices they make either, but this post is about something else). But should major public universities like UCLA do the same? What about community colleges? You see what I mean.
There is an obvious public good in AMS maintaining a large, free, friendly but thorough publication venue for papers that don’t meet the Trans. AMS threshold. This might not be the “mega journal” utopia, but it would be a major step forward. If SIAM, EMS, LMS and other major math societies set up something similar, we would actually be in a good place as the middle tier small journals would start changing their publishing model in response.
Short list of minor suggestions
As you can probably tell by now, in my opinion most math publishers are behind the curve in innovation and community relations. Let me summarize some basic ideas based on the discussion above that seem more approachable:
- Stop wasting paper and fully move to electronic publishing.
- Do not limit numbers of papers or pages. Rather, aim for as many good papers as you can.
- Improve your electronic editorial system to make it more transparent.
- Help editors work as a team, and incentivize them financially. Pay for 20% employment to experts across the world to help you run the journal.
- Set up new math journals fully dedicated to survey articles, both solicited and contributed.
- Create an appeals procedure and add a new type of senior editors who would take the job seriously.
- Institute a number of awards: for best long, short and survey articles in your journal, and for best referees. Make an effort to be fair by taking input from all editors.
Journal studies
If you read up to this point, you are probably wondering why most of these simple ideas hadn’t been widely discussed. Clearly, somebody is asleep at the wheel. Or, perhaps, doesn’t want to rock the boat (I am mixing my metaphors here, sorry). In case of for profit publishers like Springer and Elsevier, I can see why — they know all this stuff from their journals in other areas, but are very busy counting the money.
But the AMS Council can sure use a “Chair of journal innovation” whose job would be to conduct journal studies (like the many APS studies I mentioned above), or at least read other publishers’ studies. An amateur like me shouldn’t be able to tell you anything new that you couldn’t learn by googling. Perhaps, start by subscribing to an excellent newsletter Journalology fully dedicated to these ideas.
Acknowledgements.
I am extremely grateful to editors Dirk Jan Bukman, Alexander Kusenko, Valerio Lucarini, Mason Porter and Uwe Täuber, for kindly agreeing to be interviewed on the subject and for being so generous with their time. I am also thankful to several frequent APS contributors who wished to remain anonymous. If I misstated or misunderstood anything, the fault is all mine, obviously.
P.S. Mark Wilson kindly invited me to write a column for the AMS Notices on the issue of publishing. This prompted me to spend many hours thinking about the subject and talking to many physicists. At the end, I submitted a very short and non-polemical version of this blog post. If it ever gets accepted and published I will link it here.
UPDATE (August 14, 2024): The note has been accepted to the AMS Notices, and is available here. It is likely to appear in the January 2025 issue.
Two constructions
In the past two weeks I posted on the arXiv two very different papers. One is in Discrete Geometry (joint with Karim Adiprasito) and another is in Asymptotic Group Theory (joint with Martin Kassabov). Both are fundamentally combinatorial, resolve (or at least advance) some rather old open problems, and leave some room for future work. And both are completely constructive, in a way a combinatorialist would appreciate.
If there is any moral of these two completely unrelated research projects, it’s that explicit combinatorial constructions are underrated and understudied. This is easy to explain. The elegance in structural results can be delightful and they bring order to a small part of the mathematical universe and can serve as a foundation for future work.
In contrast, new constructions create a mess that cannot be easily explained away and it can take time until they become accepted as a useful tool in the area. This phenomenon is similar to disproving famous conjectures that we talked about in this old blog post. Potentially, there are many more explicit combinatorial constructions both in positive and negative direction. All for the better, of course.
Stellar subdivisions
The paper All triangulations have a common stellar subdivision is available here (see also Karim’s blog post). The results are very general, but new already in the plane for triangulations of convex polygons. Let me state the main theorem in that case to give you a flavor what’s going on.
Let Q be a convex polygon in the plane. A triangulation of Q is a subdivision (face to face partition) of Q into triangles. For example, here is a triangulation of a triangle.
We now define stellar subdivisions as certain local transformations of triangulations. In the plane, there are two types: you can either place a new vertex inside the triangle and connect to vertices of the triangle, or you can place it on the edge and connect to vertices of triangles adjacent to this edge.
One can iterate such stellar subdivisions making triangulations more and more complicated, since at each step one new vertex is being added. If a triangulation C can be obtained from triangulations A and B by iterated stellar subdivisions, we say that A and B have a common subdivision C.
Theorem (Adiprasito-P.): Every two triangulations of a convex polygon in the plane have a common subdivision.
This may seem like a high school olympiad problem, and some day it probably will be. However, initially we thought this problem should have a negative answer. It was just too old and famous to have a positive solution, right? People must have tried everything, have they not? Well, I guess not.
In fact, it is well known and not very difficult to see that every two triangulations are connected by a sequence of stellar subdivisions and their inverses (in the plane, this was proved by Danilov in 1983, see refs in the paper). So the theorem really says that every two triangulations are connected by a sequence of stellar subdivisions followed by a sequence of inverse stellar subdivisions.
We give two closely related constructions in the paper: one that is more elementary and one that is less intuitive but is the starting point of a general construction (in a all dimensions). This resolves Oda’s (weighted) strong factorization conjecture. Another important consequence of our work is the proof of Alexander’s conjecture, which is essentially the same result but in topological setting.
The key open problem that’s left is the unweighted strong factorization conjecture, where the added points have additional constraints on their location (see Question 7.1 in the paper). It is unclear if one should believe in that conjecture at all, but our proof definitely breaks down.
Spectral radius
The paper Monotone parameters on Cayley graphs of finitely generated groups is available here. We obtain the main results about eight years ago, and only now got around to writing them. While writing, we generalized them to other what we call monotone parameters, but let me discuss only the spectral radius.
Let Γ=Cay(G,S) be a Cayley graph of an infinite group G with a symmetric generating set S. Let c(n) denote the number of words in S of length n equal to the identity e. Equivalently, c(n) is the number of loops in Γ of length n, starting and ending at e. The spectral radius ρ is defined as the limit
Famously, ρ=1 if an only if group G is amenable. There are several families of Cayley graphs where the spectral radius is known explicitly (free groups, free products of finite groups, etc.), but we really know very little:
Open Problem: What is the set X of all values of ρ over all pairs (G,S)? In particular, is X=(0,1]? If not, is X dense?
One version of the problem that I discuss in my ICM paper is this: Can one find an example of (G,S) such that ρ is transcendental? In this direction, Sarnak’s question (discussed e.g. here, Section G) asks whether the spectral radius for the surface group is transcendental? We give the following answer to the first question.
Theorem (Kassabov-P.) The set X of all spectral radii has cardinality of the continuum.
The result is proved by an explicit construction of a large family of 4-generated groups which gives an embedding of the Cantor set into X. Unfortunately, we are unable to give a single transcendental number which is a spectral radius of some group. One would think that there is some kind of Liouville number that comes out from the construction, and there surely is one, we just can’t give one explicitly.
The construction we give is based on another famous construction of the Grigorchuk group which disproved Milnor’s conjecture. This is a remarkable 4-generated group that has intermediate growth (both superpolynomial and subexponential). This group is the most famous example of a large uncountable family of such groups, and remains the source of many results and open problems.
While Grigorchuk’s groups are all amenable, of course, the flexibility of their structure allows one to decorate them. In our previous paper with Martin, we decorated them with finite expander quotients placed far apart to allow the oscillating intermediate growth. In this paper, we decorate them with nonamenable quotients to vary the spectral radii.
Of the many open problems that remain, let me single out one that is especially interesting from the computational combinatorics point of view. Recall that the Grigorchuk groups is not finitely presented, but is in fact recursively presented. Famously, it is not known whether there exist a finitely presented group of intermediate growth. Does there exists a finitely presented group with transcendental growth? Or at least recursively presented? We are nowhere close to resolving these questions.
UPDATE (Apr. 30, 2024). A finitely presented group with transcendental growth was just discovered by Corentin Bodart in this paper. Congratulations, Corentin!
The power of negative thinking: Combinatorial and geometric inequalities
It’s been awhile since I blogged about mathematics. You know why, of course — there are so many issues in the real world, the imaginary world is just not as relevant as it used to be. Well, at least that’s how I felt until now. But the latest paper we wrote with Swee Hong Chan was so much fun (and took so much effort), the wait is over. There is also some interesting backstory before we can state the result.
What is the inverse problem in Enumerative Combinatorics?
Before focusing on combinatorics, note that inverse problems are everywhere in mathematics. Sometimes they are obvious and stated as such, and sometimes we are so used to these problems we don’t think of them as inverse problems at all. You are probably thinking of major problems (both solved and unsolved), like the inverse Galois problem, Cauchy problem, Minkowski problem or the Alexandrov existence theorem. But really, even prime factorization, integration, taking logs and subtraction can be viewed this way. As I said — they are everywhere.
In Enumerative Combinatorics, a typical problem goes like this: given some set A, find the number N:=|A|. Finding a combinatorial interpretation is an inverse problem: given N, find A such that N=|A|. This might seem silly to an untrained eye: obviously, every nonnegative integer counts something. But it is completely normal to have constraints on the type of solution that you want — this case is no different.
Indeed, if you think about it, the direct problem is not all that well-defined either. For example, do you want an asymptotics or just some kind of bounds on N? Or maybe you want a closed formula? But what is a closed formula? Does it have to be a product formula, or some kind of summation will work? Can it be a multisum with both positive and negative terms? Or maybe you are ok with a closed formula for the generating function in case A=UAn? But what exactly is a closed formula for a GF? The list of questions goes on.
Five years ago, I discussed various different answers to these question in my ICM paper, with ideas goes back to Wilf’s beautiful paper (see also Stanley’s answer). If anything, the answers are not short and sometimes technical. Although my formulations are well-defined, positive results can be hard to prove, while negative results can be really hard to prove. Such is life, I suppose.
So what exactly is a combinatorial interpretation?
It is easy to go philosophical (as Rota does or I do on somewhat broader questions), but let’s focus on math here. I started thinking about the problem when I came to UCLA over twelve years ago, and struggled to find a good answer. I discussed the problem in my Notices paper when I finally made peace with the computational complexity approach. Of the multiple definitions, there is only one that is both convincing, workable and broad enough:
Combinatorial interpretation = #P
I explain the answer in my lengthy OPAC survey on the subject, and in my somewhat entertaining OPAC talk (slides). I have miles to say about this, maybe some other time.
To understand why I case, it’s worth thinking of the origin of the problem. Say, you have an inequality a ≥ b between number of certain combinatorial objects, where a=|A|, b=|B|. If you have a nice explicit injection φ : B → A, this gives a combinatorial interpretation for the defect (a–b) as the number of elements in A without a preimage. If φ and its inverse are computable in polynomial time, this shows that (a–b) counts the number of objects which can be certified to be correct in polynomial time. Thus, the definition of #P.
Now, as always happens in these cases, the reason for the definition is not to give a positive answer (“you know it when you see it” was a guiding principle for a long time), but to give a negative answer. What if many of these combinatorial interpretation problems Stanley discusses in his famous survey simply don’t have a solution? (see my OPAC survey linked above, and this MO discussion for the state of art).
To list my favorite open problem, do Kronecker coefficients g(λ,μ,ν) have a combinatorial interpretation? I don’t believe so, but to give a negative answer we need a definition. There is just no way around it. Note that we already have g(λ,μ,ν)= a(λ,μ,ν) – b(λ,μ,ν) for some numbers of combinatorial objects a and b (formally, these are #P functions). It is the injection that doesn’t seem to work. But why not?
Unfortunately, the universe of “not in #P” results is very small and includes only this FOCS paper with Christian Ikenmeyer and this SODA paper with Christian Ikenmeyer and Greta Panova. Simply put, such results are rare and hard to prove. Let me not explain them, but rather turn in the direction of my current work.
Poset inequalities
Since the inequalities like g(λ,μ,ν) ≥ 0 are so unapproachable in full generality, some four years ago I turned to inequalities on the number of linear extensions of finite posets. Many such inequalities are known in the literature, e.g. the XYZ inequality, the Sidorenko inequality, the Björner–Wachs inequality, etc. It is unclear whether the defect of the XYZ inequality has a combinatorial interpretation, but the other two certainly do (see our “Effective poset inequalities” paper with Swee Hong Chan and Greta Panova).
What we found most interesting and challenging, is the following remarkable Stanley’s inequality on the log-concavity of the number of certain linear extensions:
(this is a slide from my 2021 talk). In a remarkable breakthrough, Stanley resolved the Chung-Fishburn-Graham conjecture using the Alexandrov–Fenchel inequality (more on this later). What I was interesting in the following problem: Is the defect of Stanley’s inequality N(k)^2-N(k-1) N(k+1) in #P? This is still an open problem, and we don’t have tools to resolve it.
It gets worse: in an effort to show that this inequality is in #P, two years ago we introduced a whole new technology of combinatorial atlas. We used this technology to prove a lot new inequalities in this paper with Swee Hong Chan, including multivariate extensions of Stanley inequalities and correlation inequalities. We now know why this technology was never going to apply to the #P problem, but that’s all yet another story.
What we did in our new paper is attacked a similar problem for the generalized Stanley inequality, which has the same statement but with additional constraints that L(xi)=ci for all 1 ≤ i ≤ m, where xi are fixed poset elements and ci are fixed integers. Stanley derived the log-concavity of these more general numbers from the AF inequality in one big swoosh. In our paper, we prove:
Corollary 1.5. The defect of the generalized Stanley inequality is not in #P, for all m ≥ 2 (unless PH collapses to a finite level).
Curiously, in addition to a lot of poset theoretic technology we are using the Yao-Knuth theorem in number theory. Our main result is stronger:
Theorem 1.3. The equality cases of the generalized Stanley inequality are not in PH, for all m ≥ 2 (unless PH collapses to a finite level).
Clearly, if the defect was in #P, then the “defect =? 0″ is in coNP, and the “not in #P” result follows. The complexity theoretic idea of the proof is distilled in our companion paper where we explain why the coincidence problem for domino tilings in R3 is not in PH, and the same holds for many other hard combinatorial problems.
This underscores both the strength and the weakness of our approach. On the one hand, we prove a stronger result than we wanted. On the other hand, for m=0 it is known that the equality cases of the generalized Stanley inequality are in P. This is a remarkable result of Shenfeld and van Handel (actually, a consequence of the their remarkable theory). In fact, we reprove and generalize the result in our combinatorial atlas paper. In the new paper, we prove the m=1 version of this result, using a (also remarkable) followup paper by Ma and Shenfeld. We conjecture that m=2, the defect is already not in #P (Conjecture 10.2), but there seem to be difficult number theoretic obstacles to the proof.
In summary, we now know for sure that the defect of the generalized Stanley inequality does not have a combinatorial interpretation. In particular, there is no direct injective proof similar to that for the Sidorenko inequality, for example (cf. this old blog post). If you are deeply engaged with the subject (and why would you be, obviously?), you are happy. But if not — you probably shrug. Let me now explain why you should still care.
Geometric inequalities
It is rare when when you can honestly say this, but the geometric inequalities really do go back to antiquity (see e.g. here and there), when the isoperimetric inequality in the plane was first discovered. Of the numerous inequalities that followed, note the Brunn–Minkowski inequality and the Minkowski quadratic inequality (MQI) for three convex bodies in R3. These are all consequences of the Alexandrov–Fenchel inequality mentioned above. However, when it comes to equality conditions there is a bit of wrinkle.
For the isoperimetric inequality in the plane, the equality cases are obvious (discs), and there is an interesting history of proofs by symmetrization. For the BM inequality, the equality cases are homothetic convex bodies, but the proof is very far from obvious and requires the mixed volume machinery. For the MQI, the equality conditions were know only in some special cases, and resolved in full generality only recently by Shenfeld and van Handel.
For the AF inequality, the effort to understand the equality conditions goes back to A. D. Alexandrov, who found equality conditions in some cases:
Serious difficulties occur in determining the conditions for equality to hold in the general inequalities just derived. [Alexandrov, 1937]
In 1985, Rolf Schneider formulated a workable conjecture on the equality conditions, which remains out of reach in full generality. He made a strong case for the importance of the problem:
As [AF inequality] represents a classical inequality of fundamental importance and with many applications, the identification of the equality cases is a problem of intrinsic geometric interest. Without its solution, the Brunn–Minkowski theory of mixed volumes remains in an uncompleted state. [Schneider, 1994]
In the remarkable paper mentioned above, Shenfeld and van Handel resolved several special cases of the conjecture. Notably, they gave a complete characterization of the equality conditions for convex polytopes, in a sense of extracting all geometry from the problem, and stating the condition in terms of equality of certain mixed volumes. This is where we come in.
Equality cases of the AF inequality are not in PH
To understand the way Stanley derived his inequality from the AF inequality, it’s worth first explaining the connection to log-concavity:
Stanley considered sections P, Q of the order polytope associated with a given poset and concluded log-concavity for the numbers N(k) via a simple calculation.
Now, our “not in PH” theorem on the equality cases of Stanley’s inequality and this Stanley’s calculation imply that equality cases of the AF inequality are also not in PH (under the same complexity assumptions plus computational setup on how the polytopes are presented). In some sense, this says that the equality cases of the AF inequality can never be fully described, or at least the description by Shenfeld and van Handel is probably the best one can do.
In the spirit of the #P application, our result also implies, that there is unlikely to be a stability result for the AF inequality in full generality (in this sense), see Corollary 1.2 in the paper. Omitting precise statements and technicalities, let us only mention that Bonnesen’s inequality is a basic stability result which can be viewed as a sharp extension of the isoperimetric inequality, including the equality conditions. What we are saying is — don’t expect to ever see anything like that for the AF inequality (see the paper for details).
UPDATE (Feb. 7, 2024). The “m ≥ 6” was later improved to “m ≥ 2“, see our paper on the arXiv. See this video of my Oberwolfach talk on the subject. See also this blog post by Gil Kalai. Note: This paper was accepted to appear at STOC 2024.
UPDATE (Dec 26, 2024). The paper was published in Forum Math. Pi., see here.
How to start a paper?
Starting a paper is easy. That is, if you don’t care for the marketing, don’t want to be memorable, and just want to get on with the story and quickly communicate what you have proved. Fair enough.
But that only works when your story is very simple, as in “here is a famous conjecture which we solve in this paper”. You are implicitly assuming that the story of the conjecture has been told elsewhere, perhaps many times, so that the reader is ready to see it finally resolved. But if your story is more complicated, this “get to the point” approach doesn’t really work (and yes, I argue in this blog post and this article there is always a story). Essentially you need to prepare the reader for what’s to come.
In my “How to write a clear math paper” (see also my blog post) I recommend writing the Foreword — a paragraph or two devoted to philosophy underlying your work or a high level explanation of the key idea in your paper before you proceed to state the main result:
Consider putting in the Foreword some highly literary description of what you are doing. If it’s beautiful or sufficiently memorable, it might be quoted in other papers, sometimes on a barely related subject, and bring some extra clicks to your work. Feel free to discuss the big picture, NSF project outline style, mention some motivational examples in other fields of study, general physical or philosophical principles underlying your work, etc. There is no other place in the paper to do this, and I doubt referees would object if you keep your Foreword under one page. For now such discussions are relegated to surveys and monographs, which is a shame since as a result some interesting perspectives of many people are missing.
Martin Krieger has a similar idea which he discusses at length in his 2018 AMS Notices article Don’t Just Begin with “Let A be an algebra…” This convinced me that I really should follow his (and my own) advice.
So recently I took a stock of my open opening lines (usually, joint with coauthors), and found a mixed bag. I decided to list some of them below for your amusement. I included only those which are less closely related to the subject matter of the article, so might appeal to broader audience. I am grateful to all my collaborators which supported or at least tolerated this practice.
Combinatorics matters
Combinatorics has always been a battleground of tools and ideas. That’s why it’s so hard to do, or even define.
Combinatorial inequalities (2019)
The subject of enumerative combinatorics is both classical and modern. It is classical, as the basic counting questions go back millennia; yet it is modern in the use of a large variety of the latest ideas and technical tools from across many areas of mathematics. The remarkable successes from the last few decades have been widely publicized; yet they come at a price, as one wonders if there is anything left to explore. In fact, are there enumerative problems that cannot be resolved with existing technology?
Complexity problems in enumerative combinatorics (2018), see also this blog post.
Combinatorial sequences have been studied for centuries, with results ranging from minute properties of individual sequences to broad results on large classes of sequences. Even just listing the tools and ideas can be exhausting, which range from algebraic to bijective, to probabilistic and number theoretic. The existing technology is so strong, it is rare for an open problem to remain unresolved for more than a few years, which makes the surviving conjectures all the more interesting and exciting.
Pattern avoidance is not P-recursive (2015), see also this blog post.
In Enumerative Combinatorics, the results are usually easy to state. Essentially, you are counting the number of certain combinatorial objects: exactly, asymptotically, bijectively or otherwise. Judging the importance of the results is also relatively easy: the more natural or interesting the objects are, and the stronger or more elegant is the final formula, the better. In fact, the story or the context behind the results is usually superfluous since they speak for themselves.
Hook inequalities (2020)
Proof deconstruction
There are two schools of thought on what to do when an interesting combinatorial inequality is established. The first approach would be to treat it as a tool to prove a desired result. The inequality can still be sharpened or generalized as needed, but this effort is aimed with applications as the goal and not about the inequality per se.
The second approach is to treat the inequality as a result of importance in its own right. The emphasis then shifts to finding the “right proof” in an attempt to understand, refine or generalize it. This is where the nature of the inequality intervenes — when both sides count combinatorial objects, the desire to relate these objects is overpowering.
Effective poset inequalities (2022)
There is more than one way to explain a miracle. First, one can show how it is made, a step-by-step guide to perform it. This is the most common yet the least satisfactory approach as it takes away the joy and gives you nothing in return. Second, one can investigate away every consequence and implication, showing that what appears to be miraculous is actually both reasonable and expected. This takes nothing away from the miracle except for its shining power, and puts it in the natural order of things. Finally, there is a way to place the apparent miracle as a part of the general scheme. Even, or especially, if this scheme is technical and unglamorous, the underlying pattern emerges with the utmost clarity.
Hook formulas for skew shapes IV (2021)
In Enumerative Combinatorics, when it comes to fundamental results, one proof is rarely enough, and one is often on the prowl for a better, more elegant or more direct proof. In fact, there is a wide belief in multitude of “proofs from the Book”, rather than a singular best approach. The reasons are both cultural and mathematical: different proofs elucidate different aspects of the underlying combinatorial objects and lead to different extensions and generalizations.
Hook formulas for skew shapes II (2017)
Hidden symmetries
The phrase “hidden symmetries” in the title refers to coincidences between the numbers of seemingly different (yet similar) sets of combinatorial objects. When such coincidences are discovered, they tend to be fascinating because they reflect underlying algebraic symmetries — even when the combinatorial objects themselves appear to possess no such symmetries.
It is always a relief to find a simple combinatorial explanation of hidden symmetries. A direct bijection is the most natural approach, even if sometimes such a bijection is both hard to find and to prove. Such a bijection restores order to a small corner of an otherwise disordered universe, suggesting we are on the right path in our understanding. It is also an opportunity to learn more about our combinatorial objects.
Bijecting hidden symmetries for skew staircase shapes (2021)
Hidden symmetries are pervasive across the natural sciences, but are always a delight whenever discovered. In Combinatorics, they are especially fascinating, as they point towards both advantages and limitations of the tools. Roughly speaking, a combinatorial approach strips away much of the structure, be it algebraic, geometric, etc., while allowing a direct investigation often resulting in an explicit resolution of a problem. But this process comes at a cost — when the underlying structure is lost, some symmetries become invisible, or “hidden”.
Occasionally this process runs in reverse. When a hidden symmetry is discovered for a well-known combinatorial structure, it is as surprising as it is puzzling, since this points to a rich structure which yet to be understood (sometimes uncovered many years later). This is the situation of this paper.
Hidden symmetries of weighted lozenge tilings (2020)
Problems in Combinatorics
How do you approach a massive open problem with countless cases to consider? You start from the beginning, of course, trying to resolve either the most natural, the most interesting or the simplest yet out of reach special cases. For example, when looking at the billions and billions of stars contemplating the immense challenge of celestial cartography, you start with the closest (Alpha Centauri and Barnard’s Star), the brightest (Sirius and Canopus), or the most useful (Polaris aka North Star), but not with the galaxy far, far away.
Durfee squares, symmetric partitions and bounds on Kronecker coefficients (2022)
Different fields have different goals and different open problems. Most of the time, fields peacefully coexist enriching each other and the rest of mathematics. But occasionally, a conjecture from one field arises to present a difficult challenge in another, thus exposing its technical strengths and weaknesses. The story of this paper is our effort in the face of one such challenge.
Kronecker products, characters, partitions, and the tensor square conjectures (2016)
It is always remarkable and even a little suspicious, when a nontrivial property can be proved for a large class of objects. Indeed, this says that the result is “global”, i.e. the property is a consequence of the underlying structure rather than individual objects. Such results are even more remarkable in combinatorics, where the structures are weak and the objects are plentiful. In fact, many reasonable conjectures in the area fail under experiments, while some are ruled out by theoretical considerations.
Log-concave poset inequalities (2021)
Sometimes a conjecture is more than a straightforward claim to be proved or disproved. A conjecture can also represent an invitation to understand a certain phenomenon, a challenge to be confirmed or refuted in every particular instance. Regardless of whether such a conjecture is true or false, the advances toward resolution can often reveal the underlying nature of the objects.
On the number of contingency tables and the independence heuristic (2022)
Combinatorial Interpretations
Finding a combinatorial interpretation is an everlasting problem in Combinatorics. Having combinatorial objects assigned to numbers brings them depth and structure, makes them alive, sheds light on them, and allows them to be studied in a way that would not be possible otherwise. Once combinatorial objects are found, they can be related to other objects via bijections, while the numbers’ positivity and asymptotics can then be analyzed.
What is in #P and what is not? (2022)
Traditionally, Combinatorics works with numbers. Not with structures, relations between the structures, or connections between the relations — just numbers. These numbers tend to be nonnegative integers, presented in the form of some exact formula or disguised as probability. More importantly, they always count the number of some combinatorial objects.
This approach, with its misleading simplicity, led to a long series of amazing discoveries, too long to be recounted here. It turns out that many interesting combinatorial objects satisfy some formal relationships allowing for their numbers to be analyzed. More impressively, the very same combinatorial objects appear in a number of applications across the sciences.
Now, as structures are added to Combinatorics, the nature of the numbers and our relationship to them changes. They no longer count something explicit or tangible, but rather something ephemeral or esoteric, which can only be understood by invoking further results in the area. Even when you think you are counting something combinatorial, it might take a theorem or a even the whole theory to realize that what you are counting is well defined.
This is especially true in Algebraic Combinatorics where the numbers can be, for example, dimensions of invariant spaces, weight multiplicities or Betti numbers. Clearly, all these numbers are nonnegative integers, but as defined they do not count anything per se, at least in the most obvious or natural way.
What is a combinatorial interpretation? (2022)
Covering all bases
It is a truth universally acknowledged, that a combinatorial theory is often judged not by its intrinsic beauty but by the examples and applications. Fair or not, this attitude is historically grounded and generally accepted. While eternally challenging, this helps to keep the area lively, widely accessible, and growing in unexpected directions.
Hook formulas for skew shapes III (2019)
In the past several decades, there has been an explosion in the number of connections and applications between Geometric and Enumerative Combinatorics. Among those, a number of new families of “combinatorial polytopes” were discovered, whose volume has a combinatorial significance. Still, whenever a new family of n-dimensional polytopes is discovered whose volume is a familiar integer sequence (up to scaling), it feels like a “minor miracle”, a familiar face in a crowd in a foreign country, a natural phenomenon in need of an explanation.
Triangulations of Cayley and Tutte polytopes (2013)
The problem of choosing one or few objects among the many has a long history and probably existed since the beginning of human era (e.g. “Choose twelve men from among the people” Joshua 4:2). Historically this choice was mostly rational and random choice was considered to be a bad solution. Times have changed, however. [..] In many cases random solution has become desirable, if not the only possibility. Which means that it’s about time we understand the nature of a random choice.
When and how n choose k (1996)
Books are ideas
In his famous 1906 “white suit” speech, Mark Twain recalled a meeting before the House of Lords committee, where he argued in favor of perpetual copyright. According to Twain, the chairman of the committee with “some resentment in his manner,” countered: “What is a book? A book is just built from base to roof on ideas, and there can be no property in it.”
Sidestepping the copyright issue, the unnamed chairman had a point. In the year 2021, in the middle of the pandemic, books are ideas. They come in a variety of electronic formats and sizes, they can be “borrowed” from the “cloud” for a limited time, and are more ephemeral than long lasting. Clinging to the bygone era of safety and stability, we just keep thinking of them as sturdy paper volumes.
When it comes to math books, the ideas are fundamental. Really, we judge them largely based on the ideas they present, and we are willing to sacrifice both time and effort to acquire these ideas. In fact, as a literary genre, math books get away with a slow uninventive style, dull technical presentation, anticlimactic ending, and no plot to speak of. The book under review is very different. [..]
See this books review and this blog post (2021).
Warning: This post is not meant to be a writing advice. The examples I give are merely for amusement purposes and definitely not be emulated. I am happy with some of these quotes and a bit ashamed of others. Upon reflection, the style is overly dramatic most likely because I am overcompensating for something. But hey — if you are still reading this you probably enjoyed it…
What to publish?
This might seem like a strange question. A snarky answer would be “everything!” But no, not really everything. Not all math deserves to be published, just like not all math needs to be done. Making this judgement is difficult and goes against the all too welcoming nature of the field. But if you want to succeed in math as a profession, you need to make some choices. This is a blog post about the choices we make and the choices we ought to make.
Bedtime questions
Suppose you tried to solve a major open problem. You failed. A lot of time is wasted. Maybe it’s false, after all, who knows. You are no longer confident. But you did manage to compute some nice examples, which can be turned into a mediocre little paper. Should you write it and post it on the arXiv? Should you submit it to a third rate journal? A mediocre paper is still a consolation prize, right? Better than nothing, no?
Or, perhaps, it is better not to show how little you proved? Wouldn’t people judge you as an “average” of all published papers on your CV? Wouldn’t this paper have negative impact on your job search next year? Maybe it’s better to just keep it to yourself for now and hope you can make a breakthrough next year? Or some day?
But wait, other people in the area have a lot more papers. Some are also going to be on a job market next year. Shouldn’t you try to catch up and publish every little thing you have? People at other universities do look at the numbers, right? Maybe nobody will notice this little paper. If you have more stuff done by then it will get lost in the middle of my CV, but it will help get the numbers up. Aren’t you clever or what?
Oh, wait, maybe not! You do have to send your CV to your letter writers. They will look at all your papers. How would they react to a mediocre paper? Will they judge you badly? What in the world should you do?!?
Well, obviously I don’t have one simple answer to that. But I do have some thoughts. And this quote from a famous 200 year old Russian play about people who really cared how they are perceived:
Chatsky: I wonder who the judges are! […]
Famusov: My goodness! What will countess Marya Aleksevna say to this?
[Alexander Griboyedov, Woe from Wit, 1823, abridged.]
You would think our society had advanced at least a little…
Who are the champions?
If we want to find the answers to our questions, it’s worth looking at the leaders of the field. Let’s take a few steps back and simply ask — Who are the best mathematicians? Ridiculous questions always get many ridiculous answers, so here is a random ranking by some internet person: Newton, Archimedes, Gauss, Euler, etc. Well, ok — these are all pretty dead and probably never had to deal with a bad referee report (I am assuming).
Here is another random list, from a well named website research.com. Lots of living people finally: Barry Simon, Noga Alon, Gilbert Laporte, S.T. Yau, etc. Sure, why not? But consider this recent entrant: Ravi P. Agarwal is at number 20, comfortably ahead of Paul Erdős at number 25. Uhm, why?
Or consider Theodore E. Simos who is apparently the “Best Russian Mathematician” according to research.com, and number 31 in the world ranking:
Uhm, I know MANY Russian mathematicians. Some of them are truly excellent. Who is this famous Simos I never heard of? How come he is so far ahead of Vladimir Arnold who is at number 829 on the list?
Of course, you already guessed the answer. It’s obvious from the pictures above. In their infinite wisdom, research.com judges mathematicians by the weighted average of the numbers of papers and citations. Arnold is doing well on citations, but published so little! Only 157 papers!
Numbers rule the world
To dig a little deeper into this citation phenomenon, take a look at the following curious table from a recent article “Extremal mathematicians“ by Carlos Alfaro:
If you’ve been in the field for awhile, you are probably staring at this in disbelief. How do you physically write so many papers?? Is this even true???
Yes, you know how Paul Erdős did it — he was amazing and he had a lot of coauthors. No, you don’t know how Saharon Shelah does it. But he is a legend, and you are ok with that. But here we meet again our hero Ravi P. Agarwal, the only human mathematician with more papers than Erdős. Who is he? Here is what the MathSciNet says:
Note that Ravi is still going strong — in less than 3 years he added 125 papers. Of these 1727 papers, 645 are with his favorite coauthor Donal O’Regan, number 3 on the list above. Huh? What is going on??
What’s in a number?
If the number of papers is what’s causing you to worry, let’s talk about it. Yes, there is also number of citations, the h-index (which boils down to the number of citations anyway), and maybe other awful measurements of research productivity. But the number of papers is what you have a total control over. So here are a few strategies how you can inflate the number that I learned from a close examination of publishing practices of some of the “extremal mathematicians”. They are best employed in combination:
(a) Form a clique. Over the years build a group of 5-8 close collaborators. Keep writing papers in different subsets of 3-5 of them. This is easier to do since each gets to have many papers while writing only a fraction. Make sure each papers cites heavily all other subsets from the clique. To an untrained eye of an editor, these would appear to be experts who are able to referee the paper.
(b) Form a cartel. This is a strong for of a clique. Invent an area and call yourselves collaborative research in that area. Make up a technical name, something like “analytic and algebraic topology
of locally Euclidean metrizations of infinitely differentiable Riemannian manifolds“. Apply for collaborative grants, organize conferences, publish conference proceedings, publish monographs, start your own journal. From outside it looks like a normal research activity, and who is to judge after all?
(c) Publish in little known, not very selective or shady journals. For example, Ravi P. Agarwal published 26 papers in Mathematics (MDPI Journal) that I discussed at length in this blog post. Note aside: since Mathematics is not indexed by the MathSciNet, the numbers above undercount his total productivity.
(d) Organize special issues with these journals. For example, here is a list of 11(!) special issues Agarwal served as a special editor with MDPI. Note the breadth of the collection:
(e) Become an editor of an established but not well managed journal and publish a lot there with all your collaborators. For example, T.E. Simos has a remarkable record of 150 (!) papers in the Journal of Mathematical Chemistry, where he is an editor. I feel that Springer should be ashamed of such a poor oversight of this journal, but nothing can be done I am sure since the journal has a healthy 2.413 impact factor, and Simos’s hard work surely contributed to its rise from just 1.056 in 2015. OTOH, maybe somebody can convince the MathSciNet to stop indexing this journal?
Let me emphasize that nothing on the list above is unethical, at least in a way the AMS or the NAS define these (as do most universities I think). The difference is quantitative, not qualitative. So these should not be conflated with various paper mill practices such as those described in this article by Anna Abalkina.
Disclaimer: I strongly recommend you use none of these strategies. They are abusing the system and have detrimental long term effects to both your area and your reputation.
Zero-knowledge publishing
In mathematics, there is another method of publishing that I want to describe. This one is borderline unethical at best, so I will refrain from naming names. You figure it out on your own!
Imagine you want to prove a major open problem in the area. More precisely, you want to become famous for doing that without actually getting the proof. In math, you can’t get there without publishing your “proof” in a leading area journal, better yet one of the top journals in mathematics. And if you do, it’s a good bet the referees will examine your proof very carefully. Sounds like a fail-proof system, right?
Think again! Here is an ingenuous strategy that I recently happen to learn. The strategy is modeled on the celebrated zero-knowledge proof technique, although the author I am thinking of might not be aware of that.
For simplicity, let’s say the open problem is “A=? Z”. Here is what you do, step by step.
- You come up with a large set of problems P,Q,R,S,T,U,V,W,X,Y which are all equivalent to Z. You then start a well publicized paper factory proving P=Q, W=X, X=Z, Q=Z, etc. All these papers are correct and give a good vibe of somebody who is working hard on the A=?Z problem. Make sure you have a lot of famous coauthors on these papers to further establish your credibility. In haste, make the papers barely readable so that the referees don’t find any major mistakes but get exhausted by the end.
- Make another list of problems B,C,D,E,F,G which are equivalent to A. Keep these equivalences secret. Start writing new papers proving B=T, D=Y, E=X, etc. Write them all in a style similar to previous list: cumbersome, some missing details, errors in minor arguments, etc. No famous people as coauthors. Do try to involve many grad students and coauthors to generate good will (such a great mentor!) They will all be incorrect, but none of them would raise a flag since by themselves they don’t actually prove A=Z.
- Populate the arXiv with all these papers and submit them to different reputable journals in the area. Some referees or random readers will find mistakes, so you fix one incomprehensible detail with another and resubmit. If crucial problems in one paper persist, just drop it and keep going through the motions on all other papers. Take your time.
- Eventually one of these will get accepted because the referees are human and they get tired. They will just assume that the paper they are handling is just like the papers on the first list – clumsily written but ultimately correct. And who wants to drag things down over some random reduction — the young researcher’s career is on the line. Or perhaps, the referee is a coauthor of some of the paper on the first list – in this case they are already conditioned to believe the claims because that’s what they learned from the experience on the joint paper.
- As soon as any paper from the second list is accepted, say E=X, take off the shelf the reduction you already know and make it public with great fanfare. For example, in this case quickly announce that A=E. Combined with the E=X breakthrough, and together with X=W and W=Z previously published in the first list, you can conclude that A=Z. Send it to the Annals. What are the referees going to do? Your newest A=E is inarguable, clearly true. How clever are you to have figured out the last piece so quickly! The other papers are all complicated and confusing, they all raise questions, but somebody must have refereed them and accepted/published them. Congratulations on the solution of A=Z problem! Well done!
It might take years or even decades until the area has a consensus that one should simply ignore the erroneous E=X paper and return to “A=?Z” the status of an open problem. The Annals will refuse to publish a retraction — technically they only published a correct A=E reduction, so it’s all other journals’ fault. It will all be good again, back to normal. But soon after, new papers such as G=U and B=R start to appear, and the agony continues anew…
From math to art
Now that I (hopefully) convinced you that high numbers of publications is an achievable but ultimately futile goal, how should you judge the papers? Do they at least make a nonnegative contribution to one’s CV? The answer to the latter question is “No”. This contribution can be negative. One way to think about is by invoking the high end art market.
Any art historian would be happy to vouch that the worth of a painting hinges heavily on the identity of the artist. But why should it? If the whole purpose of a piece of art is to evoke some feelings, how does the artist figures into this formula? This is super naïve, obviously, and I am sure you all understand why. My point is that things are not so simple.
One way to see the a pattern among famous artists is to realize that they don’t just create “one off” paintings, but rather a “series”. For example, Monet famously had haystack and Rouen Cathedral series, Van Gogh had a sunflowers series, Mondrian had a distinctive style with his “tableau” and “composition” series, etc. Having a recognizable very distinctive style is important, suggesting that painting in series are valued differently than those that are not, even if they are by the same artist.
Finally, the scarcity is an issue. For example Rodin’s Thinker is one of the most recognizable sculptures in the world. So is the Celebration series by Jeff Koons. While the latter keep fetching enormous prices at auctions, the latest sale of a Thinker couldn’t get a fifth of the Yellow Balloon Dog price. It could be because balloon animals are so cool, but could also be that there are 27 Thinkers in total, all made from the same cast. OTOH, there are only 5 balloon dogs, and they all have distinctly different colors making them both instantly recognizable yet still unique. You get it now — it’s complicated…
What papers to write
There isn’t anything objective of course, but thinking of art helps. Let’s figure this out by working backward. At the end, you need to be able to give a good colloquium style talk about your work. What kid of papers should you write to give such a talk?
- You can solve a major open problem. The talk writes itself then. You discuss the background, many famous people’s attempts and partial solutions. Then state your result and give an idea of the proof. Done. No need to have a follow up or related work. Your theorem speaks for itself. This is analogous to the most famous paintings. There are no haystacks or sunflowers on that list.
- You can tell a good story. I already wrote about how to write a good story in a math paper, and this is related. You start your talk by telling what’s the state of the sub-area, what are the major open problems and how do different aspects of your work fit in the picture. Then talk about how the technology that you develop over several papers positioned you to make a major advance in the area that is your most recent work. This is analogous to the series of painting.
- You can prove something small and nice, but be an amazing lecturer. You mesmerize the audience with your eloquence. For about 5 minutes after your talk they will keep thinking this little problem you solved is the most important result in all of mathematics. This feeling will fade, but good vibes will remain. They might still hire you — such talent is rare and teaching excellence is very valuable.
That’s it. If you want to give a good job talk, there is no other way to do it. This is why writing many one-off little papers makes very little sense. A good talk is not a patchwork quilt – you can’t make it of disparate pieces. In fact, I heard some talks where people tried to do that. They always have coherence of a portrait gallery of different subjects by different artists.
Back to the bedtime questions — the answer should be easy to guess now. If your little paper fits the narrative, do write it and publish it. If it helps you tell a good story — that sounds great. People in the area will want to know that you are brave enough to make a push towards a difficult problem using the tools or results you previously developed. But if it’s a one-off thing, like you thought for some reason that you could solve a major open problem in another area — why tell anyone? If anything, this distracts from the story you want to tell about your main line of research.
How to judge other people’s papers
First, you do what you usually do. Read the paper, make a judgement on the validity and relative importance of the result. But then you supplement the judgement with what you know about the author, just like when you judge a painting.
This may seem controversial, but it’s not. We live in an era of thousands of math journals which publish in total over 130K papers a year (according to MathSciNet). The sheer amount of mathematical research is overwhelming and the expertise has fractured into tiny sub-sub-areas, many hundreds of them. Deciding if a paper is a useful contribution to the area is by definition a function of what the community thinks about the paper.
Clearly, you can’t poll all members of the community, but you can ask a couple of people (usually called referees). And you can look at how previous papers by the author had been accepted by the community. This is why in the art world they always write about recent sales: what money and what museum or private collections bought the previous paintings, etc. Let me give you some math examples.
Say, you are an editor. Somebody submits a bijective proof of a binomial identity. The paper is short but nice. Clearly publishable. But then you check previous publications and discover the author has several/many other published papers with nice bijective proofs of other binomial identities, and all of them have mostly self-citations. Then you realize that in the ocean of binomial identities you can’t even check if this work has been done before. If somebody in the future wants to use this bijection, how would they go about looking for it? What will they be googling for? If you don’t have good answers to these questions, why would you accept such a paper then?
Say, you are hiring a postdoc. You see files of two candidates in your area. Both have excellent well written research proposals. One has 15 papers, another just 5 papers. The first is all over the place, can do and solve anything. The second is studious and works towards building a theory. You only have time to read the proposals (nobody has time to read all 20 papers). You looks at the best papers of each and they are of similar quality. Who do you hire?
That depends on who you are looking for, obviously. If you are a fancy shmancy university where there are many grad students and postdocs all competing with each other, none working closely with their postdoc supervisor — probably the first one. Lots of random papers is a plus — the candidate clearly adapts well and will work with many others without need for a supervision. There is even a chance that they prove something truly important, it’s hard to say, right? Whether they get a good TT job afterwards and what kind of job would that be is really irrelevant — other postdocs will be coming in a steady flow anyway.
But if you want to have this new postdoc to work closely with a faculty at your university, someone intent on building a something valuable, so that they are able to give a nice job talk telling a good story at the end, hire the second one. They first is much too independent and will probably be unable to concentrate on anything specific. The amount of supervision tends to go less, not more, as people move up. Left to their own devices you expect from these postdocs more of the same, so the choice becomes easy.
Say, you are looking at a paper submitted to you as an editor of an obscure journal. You need a referee. Look at the previous papers by the authors and see lots of the repeated names. Maybe it’s a clique? Make sure your referees are not from this clique, completely unrelated to them in any way.
Or, say, you are looking at a paper in your area which claims to have made an important step towards resolving a major conjecture. The first thing you do is look at previous papers by the same person. Have they said the same before? Was it the same or a different approach? Have any of their papers been retracted or major mistakes found? Do they have several parallel papers which prove not exactly related results towards the same goal? If the answer is Yes, this might be a zero-knowledge publishing attempt. Do nothing. But do tell everyone in the area to ignore this author until they publish one definitive paper proving all their claims. Or not, most likely…
P.S. I realize that many well meaning journals have double blind reviews. I understand where they are coming from, but think in the case of math this is misguided. This post is already much too long for me to talk about that — some other time, perhaps.
How I chose Enumerative Combinatorics
Apologies for not writing anything for awhile. After Feb 24, the math part of the “life and math” slogan lost a bit of relevance, while the actual events were stupefying to the point when I had nothing to say about the life part. Now that the shock subsided, let me break the silence by telling an old personal story which is neither relevant to anything happening right now nor a lesson to anyone. Sometimes a story is just a story…
My field
As the readers of this blog know, I am a Combinatorialist. Not a “proud one”. Just “a combinatorialist”. To paraphrase a military slogan “there are many fields like this one, but this one is mine”. While I’ve been defending my field for years, writing about its struggles, and often defining it, it’s not because this field is more important than others. Rather, because it’s so frequently misunderstood.
In fact, I have worked in other (mostly adjacent) fields, but that was usually because I was curious. Curious what’s going on in other areas, curious if they had tools to help me with my problems. Curious if they had problems that could use my tools. I would go to seminars in other fields, read papers, travel to conferences, make friends. Occasionally this strategy paid off and I would publish something in another field. Much more often nothing ever came out of that. It was fun regardless.
Anyway, I wanted to work in combinatorics for as long as I can remember, since I was about 15 or so. There is something inherently discrete about the way I see the world, so much that having additional structure is just obstructing the view. Here is how Gian-Carlo Rota famously put it:
Combinatorics is an honest subject. […] You either have the right number or you haven’t. You get the feeling that the result you have discovered is forever, because it’s concrete. [Los Alamos Science, 1985]
I agree. Also, I really like to count. When prompted, I always say “I work in Combinatorics” even if sometimes I really don’t. But in truth, the field is much too large and not unified, so when asked to be more specific (this rarely happens) I say “Enumerative Combinatorics“. What follows is a short story of how I made the choice.
Family vacation
When I was about 18, Andrey Zelevinsky (ז״ל) introduced me and Alex Postnikov to Israel Gelfand and asked what should we be reading if we want to do combinatorics. Unlike most leading mathematicians in Russia, Gelfand had a surprisingly positive view on the subject (see e.g. his quotes here). He suggested we both read Macdonald’s book, which was translated into Russian by Zelevinsky himself just a few years earlier. The book was extremely informative but dry as a fig and left little room for creativity. I read a large chunk of it and concluded that if this is what modern combinatorics looks like, I want to have nothing to do with it. Alex had a very different impression, I think.
Next year, my extended family decided to have a vacation on a Russian “river cruise”. I remember a small passenger boat which left Moscow river terminal, navigated a succession of small rivers until it reached Volga. From there, the boat had a smooth gliding all the way to the Caspian Sea. The vacation was about three weeks of a hot Summer torture with the only relief served by mouth-watering fresh watermelons.
What made it worse, there was absolutely nothing to see. Much of the way Volga is enormously wide, sometimes as wide as the English channel. Most of the time you couldn’t even see the river banks. The cities distinguished themselves only by an assortment of Lenin statues, but were unremarkable otherwise. Volgograd was an exception with its very impressive tallest statue in Europe, roughly as tall as the Statue of Liberty when combined with its pedestal. Impressive for sure, but not worth the trip. Long story short, the whole cruise vacation was dreadfully boring.
One good book can make a difference
While most of my relatives occupied themselves by reading crime novels or playing cards, I was reading a math book, the only book I brought with me. This was Stanley’s Enumerative Combinatorics (vol. 1) whose Russian translation came out just a few months earlier. So I read it cover-to-cover, but doing only the easiest exercises just to make sure I understand what’s going on. That book changed everything…
Midway through, when I was reading about linear extensions of posets in Ch. 3 with their obvious connections to standard Young tableaux and the hook-length formula (which I already knew by then), I had an idea. From Macdonald’s book, I remembered the q-analogue of #SYT via the “charge“, a statistics introduced by Lascoux and Schützenberger to give a combinatorial interpretation of Kostka polynomials, and which works even for skew Young diagram shapes. I figured that skew shapes are generic enough, and there should be a generalization of the charge to all posets. After several long days filled with some tedious calculations by hand, I came up with both the statement and the proof of the q-analogue of the number of linear extensions.
I wrote the proof neatly in my notebook with a clear intent to publish my “remarkable discovery”, and continued reading. In Ch. 4, all of a sudden, I read the “P-partition theory” that I just invented by myself. It came with various applications and connections to other problems, and was presented so well, much nicer than I would have!
After some extreme disappointment, I learned from the notes that the P-partition theory was a large portion of Stanley’s own Ph.D. thesis, which he wrote before I was born. For a few hours, I did nothing but meditate, staring at the vast water surrounding me and ignoring my relatives who couldn’t care less what I was doing anyway. I was trying to think if there is a lesson in this fiasco.
It pays to be positive and self-assure, I suppose, in a way that only a teenager can be. That day I concluded that I am clearly doing something right, definitely smarter than everyone else even if born a little too late. More importantly, I figured that Enumerative Combinatorics done “Stanley-style” is really the right area for me…
Epilogue
I stopped thinking that I am smarter than everyone else within weeks, as soon as I learned more math. I no longer believe I was born too late. I did end up doing a lot of Enumerative Combinatorics. Much later I became Richard Stanley’s postdoc for a short time and a colleague at MIT for a long time. Even now, I continue writing papers on the numbers of linear extensions and standard Young tableaux. Occasionally, I also discuss their q-analogues (like in my most recent paper). I still care and it’s still the right area for me…
Some years later I realized that historically, the “charge” and Stanley’s q-statistics were not independent in a sense that both are generalizations of the major index by Percy MacMahon. In his revision of vol. 1, Stanley moved the P-partition theory up to Ch. 3, where it belongs IMO. In 2001, he received the Steele’s Prize for Mathematical Exposition for the book that changed everything…
Are we united in anything?
Unity here, unity there, unity shmunity is everywhere. You just can’t avoid hearing about it. Every day, no matter the subject, somebody is going to call for it. Be it in Ukraine or Canada, Taiwan or Haiti, everyone is calling for unity. President Biden in his Inaugural Address called for it eight times by my count. So did former President Bush on every recent societal issue: here, there, everywhere. So did Obama and Reagan. I am sure just about every major US politician made the same call at some point. And why not? Like the “world peace“, the unity is assumed to be a universal good, or at least an inspirational if quickly forgettable goal.
Take the Beijing Olympic Games, which proudly claims that their motto “demonstrates unity and a collective effort” towards “the goal of pursuing world unity, peace and progress”. Come again? While The New York Times isn’t buying the whole “world unity” thing and calls the games “divisive” it still thinks that “Opening Ceremony [is] in Search of Unity.” Vox is also going there, claiming that the ceremony “emphasized peace, world unity, and the people around the world who have battled the pandemic.” So it sounds to me that despite all the politics, both Vox and the Times think that this mythical unity is something valuable, right? Well, ok, good to know…
Closer to home, you see the same themes said about the International Congress of Mathematicians to be held in St. Petersburg later this year. Here is Arkady Dvorkovich, co-chair of the Executive Organizing Committee and former Deputy Prime Minister of Russia: “It seems to us that Russia will be able to truly unite mathematicians from all over the world“. Huh? Are you sure? Unite in what exactly? Because even many Russian mathematicians are not on board with having the ICM in St. Petersburg. And among those from “all over the world”, quite a few are very openly boycotting the congress, so much that even the IMU started to worry. Doesn’t “unity” mean “for all”, as in ∀?
Unity of mathematics
Frequent readers of this blog can probably guess where I stand on the “unity”. Even in my own area of Combinatorics, I couldn’t find much of it at all. I openly mocked “the feeling of unity of mathematics” argument in favor of some conjectures. I tried but could never understand Noga Alon’s claim that “mathematics should be considered as one unit” other than a political statement by a former PC Chair of the 2006 ICM.
So, about this “unity of mathematics”. Like, really? All of mathematics? Quick, tell me what exactly do the Stochastic PDEs, Algebraic Number Theory, Enumerative Combinatorics and Biostatistics have in common? Anything comes to mind? Anything at all? Ugh. Let’s make another experiment. Say, I tell you that only two of these four areas have Fields medals. Can you guess which ones? Oh, you can? Really, it was that easy?? Doesn’t this cut against all of this alleged “unity”?
Anyway, let’s be serious. Mathematics is not a unit. It’s not even a “patterned tapestry” of connected threads. It’s a human endeavor. It’s an assorted collection of scientific pursuits unconstrained by physical experiments. Some of them are deep, some shallow, some are connected to others, and some are motivated by real world applications. You check the MSC 2020 classification, and there is everything under the sun, 224 pages in total. It’s preposterous to look for and expect to find some unity there. There is none to be found.
Let me put it differently. Take poetry. Like math, it’s a artistic endeavor. Poems are written by the people and for the people. To enjoy. To recall when in need or when in a mood. Like math papers. Now, can anyone keep a straight face and say “unity of poetry“? Of course not. If anything, it’s the opposite. In poetry, having a distinctive voice is celebrated. Diverse styles are lauded. New forms are created. Strong emotions are evoked. That’s the point. Why would math be any different then?
What exactly unites us?
Mathematicians, I mean. Not much, I suppose, to the contrary of math politicians’ claims:
I like to think that increasing breadth in research will help the mathematical sciences to recognize our essential unity. (Margaret Wright, SIAM President, 1996)
Huh? Isn’t this like saying that space exploration will help foster cross-cultural understanding? Sounds reasonable until you actually think about what is being said…
Even the style of doing research is completely different. Some prove theorems, some make heavy computer computations, some make physical experiments, etc. At the end, some write papers and put them on the arXiv, some write long books full of words (e.g. mathematical historians), some submit to competitive conferences (e.g. in theoretical computer science), some upload software packages and experimental evidence to some data depositary. It’s all different. Don’t be alarmed, this is normal.
In truth, very little unites us. Some mathematicians work at large state universities, others at small private liberal arts colleges with a completely different approach to teaching. Some have a great commitment to math education, some spend every waking hour doing research, while others enjoy frequent fishing trips thanks to tenure. Some go into university administration or math politics, while others become journal editors.
In truth, only two things unites us — giant math societies like the AMS and giant conferences like ICMs and joint AMS/MAA/SIAM meetings. Let’s treat them separately, but before we go there, let’s take a detour just to see what an honest unrestricted public discourse sounds like:
What to do about the Olympics
The answer depends on who you ask, obviously. And opinions are abound. I personally don’t care other than the unfortunate fact that 2028 Olympics will be hosted on my campus. But we in math should learn how to be critical, so here is a range of voices that I googled. Do with them as you please.
Some are sort of in favor:
I still believe the Olympics contribute a net benefit to humanity. (Beth Daley, The Conversation, Feb. 2018)
Some are positive if a little ambivalent:
The Games aren’t dead. Not by a longshot. But it’s worth noting that the reason they are alive has strikingly little to do with games, athletes or medals. (L. Jon Wertheim, Time, June 2021)
Some like The New York Times are highly critical, calling it “absurdity”. Some are blunt:
More and more, the international spectacle has become synonymous with overspending, corruption, and autocratic regimes. (Yasmeen Serhan, The Atlantic, Aug. 2021)
yet unwilling to make the leap and call it quits. Others are less shy:
You can’t reform the Olympics. The Olympics are showing us what they are, and what they’ve always been. (Gia Lappe and Jonny Coleman, Jacobin, July 2021)
and
Boil down all the sanctimonious drivel about how edifying the games are, and you’re left with the unavoidable truth: The Olympics wreck lives. (Natalie Shure, The New Republic, July 2021)
What is the ICM
Well, it’s a giant collective effort. A very old tradition. Medals are distributed. Lots of talks. Speakers are told that it’s an honor to be chosen. Universities issue press releases. Yes, like this one. Rich countries set up and give away travel grants. Poor countries scramble to pay for participants. The host country gets dubious PR benefits. A week after it’s over everyone forgets it ever happened. Life goes on.
I went to just one ICM, in Rio in 2018. It was an honor to be invited. But the experience was decidedly mixed. The speakers were terrific mathematicians, all of them. Many were good speakers. A few were dreadful in both content and style. Some figured they are giving talks in their research seminar rather than to a general audience, so I left a couple of such talks in middle. Many talks in parallel sections were not even recorded. What a shame!
The crowds were stupefying. I saw a lot of faces. Some were friendly, of people I hadn’t seen in years, sometimes 20 years. Some were people I knew only by name. It was nice to say hello, to shake their hand. But there were thousands more. Literally. An ocean of people. I was drowning. This was the worst place for an introvert.
While there, I asked a lot of people how did they like the ICM. Some were electrified by the experience and had a decent enough time. Some looked like fish out of the water — when asked they just stared at me incomprehensively silently saying “What are you, an idiot?” Some told me they just went to the opening ceremony and left for the beach for the rest of the ICM. Assaf Naor said that he loved everything. I was so amused by that, I asked if I could quote him. “Yes,” he said, “you can quote me: I loved absolutely every bit of the ICM”. Here we go — not everyone is an introvert.
Whatever happened at the ICM
Unlike the Olympics, math people tend to be shy in their ICM criticism. In his somewhat unfortunately titled but otherwise useful historical book “Mathematicians of the World, Unite!” the author, Guillermo Curbera, largely stays exuberant about the subject. He does mention some critical stories, like this one:
Charlotte Angas Scott reported bluntly on the presentation of papers in the congress, which in her opinion were “usually shockingly bad” since “instead of speaking to the audience, [the lecturer] reads his paper to himself in a monotone that is sometimes hurried, sometimes hesitating, and frequently bored . . . so that he is often tedious and incomprehensible.” (Paris 1900 Chapter, p. 24)
Curbera does mention in passing that the were some controversies: Grothendieck refused to attend ICM Moscow in 1966 for political reasons, Margulis and Novikov were not allowed by the Soviet Union to leave the country to receive their Fields medals. Well, nobody’s perfect, right?
Most reports I found on the web are highly positive. Read, for example, Gil Kalai’s blog posts on the ICM 2018. Everything was great, right? Even Doron Zeilberger, not known for holding his tongue, is mostly positive (about the ICM Beijing in 2002). He does suggest that the invited speakers “should go to a ‘training camp‘” for some sort of teacher training re-education, apparently not seeing the irony, or simply under impression of all those great things in Beijing.
The only (highly controversial) criticism that I found was from Ulf Persson who starts with:
The congresses are by now considered to be monstrous affairs very different from the original intimate gatherings where group pictures could be taken.
He then continues to talk about various personal inconveniences, his misimpressions about the ICM setting, the culture, the city, etc., all in a somewhat insensitive and rather disparaging manner. Apparently, this criticism and misimpressions earned a major smackdown from Marcelo Viana, the ICM 2018 Organizing Committee Chair, who wrote that this was a “piece of bigotry” by somebody who is “poorly informed”. Fair enough. I agree with that and with the EMS President Volker Mehrmann who wrote in the same EMS newsletter that the article was “very counterproductive”. Sure. But an oversized 4 page reaction to an opinion article in a math newsletter from another continent seem indicative that the big boss hates criticism. Because we need all that “unity”, right?
Anyway, don’t hold your breath to see anything critical about the ICM St. Petersburg later this year. Clearly, everything is going to be just fantastic, nothing controversial about it. Right…
What to do about the ICM
Stop having them in the current form. It’s the 21st century, and we are starting the third year of the pandemic. All talks can be moved online so that everyone can watch them either as they happen, or later on YouTube. Let me note that I’ve sat in the bleachers of these makeshift 1000+ people convention center auditoriums where the LaTeX formulas are barely visible. This is what the view is like:
Note that the ICM is not like a sports event — there is literally nothing at stake. Also, there are usually no questions afterwards anyway. You are all better off watching the talks later on your laptop, perhaps even on a x1.5 speed. To get the idea, imagine watching this talk in a huge room full of people…. Even better, we can also spread out these online lectures across the time zones so that people from different countries can participate. Something like this World Relay in Combinatorics.
Really, all that CO2 burned to get humans halfway across the world to seat in a crowded space is not doing anyone any good. If the Nobel Prizes can be awarded remotely, so can the Fields medals. Tourism value aside, the amount of meaningful person-to-person interaction is so minimal in a large crowd, I am struggling to find a single good reason at all to have these extravaganzas in-person.
What to do about the AMS
I am not a member of any math societies so it’s not my place to tell them what to do. As a frequent contributor to AMS journals and a former editor of one of them, I did call on the AMS to separate its society business form the publishing, but given that their business model hinges on the books and journals they sell, this is unlikely. Still, let me make some quick observations which might be helpful.
The AMS is clearly getting less and less popular. I couldn’t find the exact membership numbers, but their “dues and outreach” earnings have been flat for a while. Things are clearly not going in the right direction, so much that the current AMS President Ruth Charney sent out a survey earlier this week asking people like me why do we not want to join.
People seem to realize that they have many different views on all thing math related and are seeking associations which are a better fit. One notable example is the Just Mathematics Collective which has several notable boycott initiatives. Another is the Association for Mathematical Research formed following various controversies. Note that there is a great deal of disagreements between these two, see e.g. here, there and there.
I feel these are very good developments. It’s healthy to express disagreements on issues you consider important. And while I disagree with other things in the article below, I do agree with this basic premise:
Totalitarian countries have unity. Democratic republics have disagreement. (Kevin Williamson, Against Unity, National Review, Jan. 2021)
So everyone just chill. Enjoy diverse views and opinions. Disagree with the others. And think twice before you call for “unity” of anything, or praise the ephemeral “unity of mathematics”. There is none.
Igor Pak's blog 
You must be logged in to post a comment.