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 CO₂ 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.

2021 Abel Prize

I am overjoyed with the news of the Abel prize awarded to László Lovász and Avi Wigderson. You can now see three (!) Abel laureates discussing Combinatorics — follow the links in this blog post from 2019. See also Gil Kalai’s blog post for further links to lectures.

What if they are all wrong?

Conjectures are a staple of mathematics. They are everywhere, permeating every area, subarea and subsubarea. They are diverse enough to avoid a single general adjective. They come in al shapes and sizes. Some of them are famous, classical, general, important, inspirational, far-reaching, audacious, exiting or popular, while others are speculative, narrow, technical, imprecise, far-fetched, misleading or recreational. That’s a lot of beliefs about unproven claims, yet we persist in dispensing them, inadvertently revealing our experience, intuition and biases.

The conjectures also vary in attitude. Like a finish line ribbon they all appear equally vulnerable to an outsider, but in fact differ widely from race to race. Some are eminently reachable, the only question being who will get there first (think 100 meter dash). Others are barely on the horizon, requiring both great effort, variety of tools, and an extended time commitment (think ironman triathlon). The most celebrated third type are like those Sci-Fi space expeditions in requiring hundreds of years multigenerational commitments, often losing contact with civilization it left behind. And we can’t forget the romantic fourth type — like the North Star, no one actually wants to reach them, as they are largely used for navigation, to find a direction in unchartered waters.

Now, conjectures famously provide a foundation of the scientific method, but that’s not at all how we actually think of them in mathematics. I argued back in this pointed blog post that citations are the most crucial for the day to day math development, so one should take utmost care in making references. While this claim is largely uncontroversial and serves as a raison d’être for most GoogleScholar profiles, conjectures provide a convenient idealistic way out. Thus, it’s much more noble and virtuous to say “I dedicated my life to the study of the XYZ Conjecture” (even if they never publish anything), than “I am working hard writing so many papers to gain respect of my peers, get a promotion, and provide for my family“. Right. Obviously…

But given this apparent (true or perceived) importance of conjectures, are you sure you are using them right? What if some/many of these conjectures are actually wrong, what then? Should you be flying that starship if there is no there there? An idealist would argue something like “it’s a journey, not a destination“, but I strongly disagree. Getting closer to the truth is actually kind of important, both as a public policy and on an individual level. It is thus pretty important to get it right where we are going.

What are conjectures in mathematics?

That’s a stupid question, right? Conjectures are mathematical claims whose validity we are trying to ascertain. Is that all? Well, yes, if you don’t care if anyone will actually work on the conjecture. In other words, something about the conjecture needs to interesting and inspiring.

What makes a conjecture interesting?

This is a hard question to answer because it is as much psychological as it is mathematical. A typical answer would be “oh, because it’s old/famous/beautiful/etc.” Uhm, ok, but let’s try to be a little more formal.

One typically argues “oh, that’s because this conjecture would imply [a list of interesting claims and known results]”. Well, ok, but this is self-referential. We already know all those “known results”, so no need to prove them again. And these “claims” are simply other conjectures, so this is really an argument of the type “this conjecture would imply that conjecture”, so not universally convincing. One can argue: “look, this conjecture has so many interesting consequences”. But this is both subjective and unintuitive. Shouldn’t having so many interesting conjectural consequences suggest that perhaps the conjecture is too strong and likely false? And if the conjecture is likely to be false, shouldn’t this make it uninteresting?

Also, wouldn’t it be interesting if you disprove a conjecture everyone believes to be true? In some sense, wouldn’t it be even more interesting if until now everyone one was simply wrong?

None of this are new ideas, of course. For example, faced with the need to justify the “great” BC conjecture, or rather 123 pages of survey on the subject (which is quite interesting and doesn’t really need to be justified), the authors suddenly turned reflective. Mindful of self-referential approach which they quickly discard, they chose a different tactic:

We believe that the interest of a conjecture lies in the feeling of unity of mathematics that it entails. [M.P. Gomez Aparicio, P. Julg and A. Valette, “The Baum-Connes conjecture“, 2019]

Huh? Shouldn’t math be about absolute truths, not feelings? Also, in my previous blog post, I mentioned Noga Alon‘s quote that Mathematics is already “one unit“. If it is, why does it need a new “feeling of unity“? Or is that like one of those new age ideas which stop being true if you don’t reinforce them at every occasion?

If you are confused at this point, welcome to the club! There is no objective way to argue what makes certain conjectures interesting. It’s all in our imagination. Nikolay Konstantinov once told me that “mathematics is a boring subject because every statement is equivalent to saying that some set is empty.” He meant to be provocative rather than uninspiring. But the problem he is underlying is quite serious.

What makes us believe a conjecture is true?

We already established that in order to argue that a conjecture is interesting we need to argue it’s also true, or at least we want to believe it to be true to have all those consequences. Note, however, that we argue that a conjecture is true in exactly the same way we argue it’s interesting: by showing that it holds is some special cases, and that it would imply other conjectures which are believed to be true because they are also checked in various special cases. So in essence, this gives “true = interesting” in most cases. Right?

This is where it gets complicated. Say, you are working on the “abc conjecture” which may or may not be open. You claim that it has many consequences, which makes it both likely true and interesting. One of them is the negative solution to the Erdős–Ulam problem about existence of a dense set in the plane with rational pairwise distances. But a positive solution to the E-U problem implies the Harborth’s conjecture (aka the “integral Fáry problem“) that every graph can be drawn in the plane with rational edge lengths. So, counterintuitively, if you follow the logic above shouldn’t you be working on a positive solution to Erdős–Ulam since it would both imply one conjecture and give a counterexample to another? For the record, I wouldn’t do that, just making a polemical point.

I am really hoping you see where I am going. Since there is no objective way to tell if a conjecture is true or not, and what exactly is so interesting about it, shouldn’t we discard our biases and also work towards disproving the conjecture just as hard as trying to prove it?

What do people say?

It’s worth starting with a general (if slightly poetic) modern description:

In mathematics, [..] great conjectures [are] sharply formulated statements that are most likely true but for which no conclusive proof has yet been found. These conjectures have deep roots and wide ramifications. The search for their solution guides a large part of mathematics. Eternal fame awaits those who conquer them first. Remarkably, mathematics has elevated the formulation of a conjecture into high art. [..] A well-chosen but unproven statement can make its author world-famous, sometimes even more so than the person providing the ultimate proof. [Robbert Dijkgraaf, The Subtle Art of the Mathematical Conjecture, 2019]

Karl Popper thought that conjectures are foundational to science, even if somewhat idealized the efforts to disprove them:

[Great scientists] are men of bold ideas, but highly critical of their own ideas: they try to find whether their ideas are right by trying first to find whether they are not perhaps wrong. They work with bold conjectures and severe attempts at refuting their own conjectures. [Karl Popper, Heroic Science, 1974]

Here is how he reconciled somewhat the apparent contradiction:

On the pre-scientific level we hate the very idea that we may be mistaken. So we cling dogmatically to our conjectures, as long as possible. On the scientific level, we systematically search for our mistakes. [Karl Popper, quoted by Bryan Magee, 1971]

Paul Erdős was, of course, a champion of conjectures and open problems. He joked that the purpose of life is “proof and conjecture” and this theme is repeatedly echoed when people write about him. It is hard to overestimate his output, which included hundreds of talks titled “My favorite problems“. He wrote over 180 papers with collections of conjectures and open problems (nicely assembled by Zbl. Math.)

Peter Sarnak has a somewhat opposite point of view, as he believes one should be extremely cautious about stating a conjecture so people don’t waste time working on it. He said once, only half-jokingly:

Since we reward people for making a right conjecture, maybe we should punish those who make a wrong conjecture. Say, cut off their fingers. [Peter Sarnak, UCLA, c. 2012]

This is not an exact quote — I am paraphrasing from memory. Needless to say, I disagree. I don’t know how many fingers he wished Erdős should lose, since some of his conjectures were definitely disproved: one, two, three, four, five, and six. This is not me gloating, the opposite in fact. When you are stating hundreds of conjectures in the span of almost 50 years, having only a handful to be disproved is an amazing batting average. It would, however, make me happy if Sarnak’s conjecture is disproved someday.

Finally, there is a bit of a controversy whether conjectures are worth as much as theorems. This is aptly summarized in this quote about yet another champion of conjectures:

Louis J. Mordell [in his book review] questioned Hardy‘s assessment that Ramanujan was a man whose native talent was equal to that of Euler or Jacobi. Mordell [..] claims that one should judge a mathematician by what he has actually done, by which Mordell seems to mean, the theorems he has proved. Mordell’s assessment seems quite wrong to me. I think that a felicitous but unproved conjecture may be of much more consequence for mathematics than the proof of many a respectable theorem. [Atle Selberg, “Reflections Around the Ramanujan Centenary“, 1988]

So, what’s the problem?

Well, the way I see it, the efforts made towards proving vs. disproving conjectures is greatly out of balance. Despite all the high-minded Popper’s claims about “severe attempts at refuting their own conjectures“, I don’t think there is much truth to that in modern math sciences. This does not mean that disproofs of famous conjectures aren’t celebrated. Sometimes they are, see below. But it’s clear to me that the proofs are celebrated more frequently, and to a much greater degree. I have only anecdotal evidence to support my claim, but bear with me.

Take prizes. Famously, Clay Math Institute gives $1 million for a solution of any of these major open problems. But look closely at the rules. According to the item 5b, except for the P vs. NP problem and the Navier–Stokes Equation problem, it gives nothing ($0) for a disproof of these problems. Why, oh why?? Let’s look into CMI’s “primary objectives and purposes“:

To recognize extraordinary achievements and advances in mathematical research.

So it sounds like CMI does not think that disproving the Riemann Hypothesis needs to be rewarded because this wouldn’t “advance mathematical research”. Surely, you are joking? Whatever happened to “the opposite of a profound truth may well be another profound truth“? Why does the CMI wants to put its thumb on the scale and support only one side? Do they not want to find out the solution whatever it is? Shouldn’t they be eager to dispense with the “wrong conjecture” so as to save numerous researches from “advances to nowhere“?

I am sure you can see that my blood is boiling, but let’s proceed to the P vs. NP problem. What if it’s independent of ZFC? Clearly, CMI wouldn’t pay for proving that. Why not? It’s not like this kind of thing never happened before (see obligatory link to CH). Some people believe that (or at least they did in 2012), and some people like Scott Aaronson take this seriously enough. Wouldn’t this be a great result worthy of an award as much as the proof that P=NP, or at least a nonconstructive proof that P=NP?

If your head is not spinning hard enough, here is another amusing quote:

Of course, it’s possible that P vs. NP is unprovable, but that that fact itself will forever elude proof: indeed, maybe the question of the independence of P vs. NP is itself independent of set theory, and so on ad infinitum! But one can at least say that, if P vs. NP (or for that matter, the Riemann hypothesis, Goldbach’s conjecture, etc.) were proven independent of ZF, it would be an unprecedented development. [Scott Aaronson, P vs. NP, 2016].

Speaking of Goldbach’s Conjecture, the most talked about and the most intuitively correct statement in Number Theory that I know. In a publicity stunt, for two years there was a $1 million prize by a publishing house for the proof of the conjecture. Why just for the proof? I never heard of anyone not believing the conjecture. If I was the insurance underwriter for the prize (I bet they had one), I would allow them to use “for the proof or disproof” for a mere extra $100 in premium. For another $50 I would let them use “or independent of ZF” — it’s a free money, so why not? It’s such a pernicious idea of rewarding only one kind of research outcome!

Curiously, even for Goldbach’s Conjecture, there is a mild divergence of POVs on what the future holds. For example, Popper writes (twice in the same book!) that:

[On whether Goldbach’s Conjecture is ‘demonstrable’] We don’t know: perhaps we may never know, and perhaps we can never know. [Karl Popper, Conjectures and Refutations, 1963]

Ugh. Perhaps. I suppose anything can happen… For example, our civilizations can “perhaps” die out in the next 200 years. But is that likely? Shouldn’t the gloomy past be a warning, not a prediction of the future? The only thing more outrageously pessimistic is this theological gem of a quote:

Not even God knows the number of permutations of 1000 avoiding the 1324 pattern. [Doron Zeilberger, quoted here, 2005]

Thanks, Doron! What a way to encourage everyone! Since we know from numerical estimates that this number is ≈ 3.7 × 10¹⁰¹⁷ (see this paper and this follow up), Zeilberger is suggesting that large pattern avoidance numbers are impossibly hard to compute precisely, already in the range of only about 1018 digits. I really hope he is proved wrong in his lifetime.

But I digress. What I mean to emphasize, is that there are many ways a problem can be resolved. Yet some outcomes are considered more valuable than others. Shouldn’t the research achievements be rewarded, not the desired outcome? Here is yet another colorful opinion on this:

Given a conjecture, the best thing is to prove it. The second best thing is to disprove it. The third best thing is to prove that it is not possible to disprove it, since it will tell you not to waste your time trying to disprove it. That’s what Gödel did for the Continuum Hypothesis. [Saharon Shelah, Rutgers Univ. Colloqium, 2001]

Why do I care?

For one thing, disproving conjectures is part of what I do. Sometimes people are a little shy to unambiguously state them as formal conjectures, so they phrase them as questions or open problems, but then clarify that they believe the answer is positive. This is a distinction without a difference, or at least I don’t see any (maybe they are afraid of Sarnak’s wrath?) Regardless, proving their beliefs wrong is still what I do.

For example, here is my old bog post on my disproof of the Noonan-Zeiberger Conjecture (joint with Scott Garrabrant). And in this recent paper (joint with Danny Nguyen), we disprove in one big swoosh both Barvinok’s Problem, Kannan’s Problem, and Woods Conjecture. Just this year I disproved three conjectures:

1. The Kirillov–Klyachko Conjecture (2004) that the reduced Kronecker coefficients satisfy the saturation property (this paper, joint with Greta Panova).
2. The Brandolini et al. Conjecture (2019) that concrete lattice polytopes can multitile the space (this paper, joint with Alexey Garber).
3. Kenyon’s Problem (c. 2005) that every integral curve in R³ is a boundary of a PL surface comprised of unit triangles (this paper, joint with Alexey Glazyrin).

On top of that, just two months ago in this paper (joint with Han Lyu), we showed that the remarkable independence heuristic by I. J. Good for the number of contingency tables, fails badly even for nearly all uniform marginals. This is not exactly disproof of a conjecture, but it’s close, since the heuristic was introduced back in 1950 and continues to work well in practice.

In addition, I am currently working on disproving two more old conjectures which will remain unnamed until the time we actually resolve them (which might never happen, of course). In summary, I am deeply vested in disproving conjectures. The reasons why are somewhat complicated (see some of them below). But whatever my reasons, I demand and naively fully expect that my disproofs be treated on par with proofs, regardless whether this expectation bears any relation to reality.

My favorite disproofs and counterexamples:

There are many. Here are just a few, some famous and some not-so-famous, in historical order:

1. Fermat‘s conjecture (letter to Pascal, 1640) on primality of Fermat numbers, disproved by Euler (1747)
2. Tait’s conjecture (1884) on hamiltonicity of graphs of simple 3-polytopes, disproved by W.T. Tutte (1946)
3. General Burnside Problem (1902) on finiteness of periodic groups, resolved negatively by E.S. Golod (1964)
4. Keller’s conjecture (1930) on tilings with unit hypercubes, disproved by Jeff Lagarias and Peter Shor (1992)
5. Borsuk’s Conjecture (1932) on partitions of convex sets into parts of smaller diameter, disproved by Jeff Kahn and Gil Kalai (1993)
6. Hirsch Conjecture (1957) on the diameter of graphs of convex polytopes, disproved by Paco Santos (2010)
7. Woods’s conjecture (1972) on the covering radius of certain lattices, disproved by Oded Regev, Uri Shapira and Barak Weiss (2017)
8. Connes embedding problem (1976), resolved negatively by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen (2020)

In all these cases, the disproofs and counterexamples didn’t stop the research. On the contrary, they gave a push to further (sometimes numerous) developments in the area.

Why should you disprove conjectures?

There are three reasons, of different nature and importance.

First, disproving conjectures is opportunistic. As mentioned above, people seem to try proving much harder than they try disproving. This creates niches of opportunity for an open-minded mathematician.

Second, disproving conjectures is beautiful. Let me explain. Conjectures tend to be rigid, as in “objects of the type pqr satisfy property abc.” People like me believe in the idea of “universality“. Some might call it “completeness” or even “Murphy’s law“, but the general principle is always the same. Namely: it is not sufficient that one wishes that all pqr satisfy abc to actually believe in the implication; rather, there has to be a strong reason why abc should hold. Barring that, pqr can possibly be almost anything, so in particular non-abc. While some would argue that non-abc objects are “ugly” or at least “not as nice” as abc, the idea of universality means that your objects can be of every color of the rainbow — nice color, ugly color, startling color, quiet color, etc. That kind of palette has its own sense of beauty, but it’s an acquired taste I suppose.

Third, disproving conjectures is constructive. It depends on the nature of the conjecture, of course, but one is often faced with necessity to construct a counterexample. Think of this as an engineering problem of building some pqr which at the same time is not abc. Such construction, if at all possible, might be difficult, time consuming and computer assisted. But so what? What would you rather do: build a mile-high skyscraper (none exist yet) or prove that this is impossible? Curiously, in CS Theory both algorithms and (many) complexity results are constructive (you need gadgets). Even the GCT is partially constructive, although explaining that would take us awhile.

What should the institutions do?

If you are an institution which awards prizes, stop with the legal nonsense: “We award […] only for a publication of a proof in a top journal”. You need to set up a scientific committee anyway, since otherwise it’s hard to tell sometimes if someone deserves a prize. With mathematicians you can expect anything anyway. Some would post two arXiv preprints, give a few lectures and then stop answering emails. Others would publish only in a journal where they are Editor-in-Chief. It’s stranger than fiction, really.

What you should do is say in the official rules: “We have [this much money] and an independent scientific committee which will award any progress on [this problem] partially or in full as they see fit.” Then a disproof or an independence result will receive just as much as the proof (what’s done is done, what else are you going to do with the money?) This would also allow some flexibility for partial solutions. Say, somebody proves Goldbach’s Conjecture for integers > exp(exp(10¹⁰⁰⁰⁰⁰)), way way beyond computational powers for the remaining integers to be checked. I would give this person at least 50% of the prize money, leaving the rest for future developments of possibly many people improving on the bound. However, under the old prize rules such person gets bupkes for their breakthrough.

What should the journals do?

In short, become more open to results of computational and experimental nature. If this sounds familiar, that’s because it’s a summary of Zeilberger’s Opinions, viewed charitably. He is correct on this. This includes publishing results of the type “Based on computational evidence we believe in the following UVW conjecture” or “We develop a new algorithm which confirms the UVW conjecture for n<13″. These are still contributions to mathematics, and the journals should learn to recognize them as such.

To put in context of our theme, it is clear that a lot more effort has been placed on proofs than on finding counterexamples. However, in many areas of mathematics there are no small counterexamples, so a heavy computational effort is crucial for any hope of finding one. Such work is not be as glamorous as traditional papers. But really, when it comes to standards, if a journal is willing to publish the study of something like the “null graphs“, the ship has sailed for you…

Let me give you a concrete example where a computational effort is indispensable. The curious Lovász conjecture states that every finite connected vertex-transitive graph contains a Hamiltonian path. This conjecture got to be false. It hits every red flag — there is really no reason why pqr = “vertex transitive” should imply abc = “Hamiltonian”. The best lower bound for the length of the longest (self-avoiding) path is only about square root of the number of vertices. In fact, even the original wording by Lovász shows he didn’t believe the conjecture is true (also, I asked him and he confirmed).

Unfortunately, proving that some potential counterexample is not Hamiltonian is computationally difficult. I once had an idea of one (a nice cubic Cayley graph on “only” 3600 vertices), but Bill Cook quickly found a Hamiltonian cycle dashing my hopes (it was kind of him to look into this problem). Maybe someday, when the TSP solvers are fast enough on much larger graphs, it will be time to return to this problem and thoroughly test it on large Cayley graphs. But say, despite long odds, I succeed and find a counterexample. Would a top journal publish such a paper?

Editor’s dilemma

There are three real criteria for evaluation a solution of an open problem by the journal:

1. Is this an old, famous, or well-studied problem?
2. Are the tools interesting or innovative enough to be helpful in future studies?
3. Are the implications of the solution to other problems important enough?

Now let’s make a hypothetical experiment. Let’s say a paper is submitted to a top math journal which solves a famous open problem in Combinatorics. Further, let’s say somebody already proved it is equivalent to a major problem in TCS. This checks criteria 1 and 3. Until not long ago it would be rejected regardless, so let’s assume this is happening relatively recently.

Now imagine two parallel worlds, where in the first world the conjecture is proved on 2 pages using beautiful but elementary linear algebra, and in the second world the conjecture is disproved on a 2 page long summary of a detailed computational search. So in neither world we have much to satisfy criterion 2. Now, a quiz: in which world the paper will be published?

If you recognized that the first world is a story of Hao Huang‘s elegant proof of the induced subgraphs of hypercubes conjecture, which implies the sensitivity conjecture. The Annals published it, I am happy to learn, in a welcome break with the past. But unless we are talking about some 200 year old famous conjecture, I can’t imagine the Annals accepting a short computational paper in the second world. Indeed, it took a bit of a scandal to accept even the 400 year old Kepler’s conjecture which was proved in a remarkable computational work.

Now think about this. Is any of that fair? Shouldn’t we do better as a community on this issue?

What do other people do?

Over the years I asked a number of people about the uncertainty created by the conjectures and what do they do about it. The answers surprised me. Here I am paraphrasing them:

Some were dumbfounded: “What do you mean this conjecture could be false? It has to be true, otherwise nothing I am doing make much sense.”

Others were simplistic: “It’s an important conjecture. Famous people said it’s true. It’s my job to prove it.”

Third were defensive: “Do you really think this conjecture could be wrong? Why don’t you try to disprove it then? We’ll see who is right.”

Fourth were biblical: “I tend to work 6 days a week towards the proof and one day towards the disproof.”

Fifth were practical: “I work on the proof until I hit a wall. I use the idea of this obstacle to try constructing potential counterexamples. When I find an approach to discard such counterexamples, I try to generalize the approach to continue working on the proof. Continue until either side wins.”

If the last two seem sensible to you to, that’s because they are. However, I bet fourth are just grandstanding — no way they actually do that. The fifth sound great when this is possible, but that’s exceedingly rare, in my opinion. We live in a technical age when proving new results often requires great deal of effort and technology. You likely have tools and intuition to work in only one direction. Why would you want to waste time working in another?

What should you do?

First, remember to make conjectures. Every time you write a paper, tell a story of what you proved. Then tell a story of what you wanted to prove but couldn’t. State it in the form of a conjecture. Don’t be afraid to be wrong, or be right but oversharing your ideas. It’s a downside, sure. But the upside is that your conjecture might prove very useful to others, especially young researchers. In might advance the area, or help you find a collaborator to resolve it.

Second, learn to check your conjectures computationally in many small cases. It’s important to give supporting evidence so that others take your conjectures seriously.

Third, learn to make experiments, explore the area computationally. That’s how you make new conjectures.

Fourth, understand yourself. Your skill, your tools. Your abilities like problem solving, absorbing information from the literature, or making bridges to other fields. Faced with a conjecture, use this knowledge to understand whether at least in principle you might be able to prove or disprove a conjecture.

Fifth, actively look for collaborators. Those who have skills, tools, or abilities you are missing. More importantly, they might have a different POV on the validity of the conjecture and how one might want to attack it. Argue with them and learn from them.

Sixth, be brave and optimistic! Whether you decide to prove, disprove a conjecture, or simply state a new conjecture, go for it! Ignore the judgements by the likes of Sarnak and Zeilberger. Trust me — they don’t really mean it.

Some good news

Two of my former Ph.D. students won major prizes recently — Matjaž Konvalinka and Danny Nguyen.  Matjaž is an Associate Professor at University of Ljubljana, Danny is a Lewis Research Assistant Professor at University of Michigan, Ann Arbor.  Congratulations to both of them!

(1) The 2019 Robbins Prize is awarded to Roger Behrend, Ilse Fischer and Matjaž Konvalinka for their paper “Diagonally and antidiagonally symmetric alternating sign matrices of odd order”.  The Robbins Prize is given in Combinatorics and related areas of interest is named after the late David P. Robbins and is given once every 3 years by AMS and MAA.

In many ways, this paper completes the long project of enumerating alternating sign matrices (ASMs) initiated by William Mills, David Robbins, and Howard Rumsey in the early 1980s.  The original #ASM(n)=#TSSCPP(n) conjecture follows from Andrews’s proof of the conjectured product formula for #TSSCPP(n), and Zeilberger’s 84 page computer assisted proof of the the same conjectured product formula for #ASM(n).  This led to a long series of remarkable developments which include Kuperberg’s proof using the Izergin-Korepin determinant for the six vertex model, the Cantini–Sportiello proof of the Razumov-Stroganov conjecture, and a recent self-contained determinantal proof for the number of ASMs by Fischer.  Bressoud’s book (and this talk, slides) is a good introduction.  But the full story is yet to be written.

(2)  The 2018 Sacks Prize is awarded to Danny Nguyen for his UCLA Ph.D. dissertation on the complexity of short formulas in Presburger Arithmetic (PA) and many related works (some joint with me, some with others).  See also the UCLA announcement.  The Sacks Prize is given by the international Association for Symbolic Logic for “the most outstanding doctoral dissertation in mathematical logic“.  It is sometimes shared between two awardees, and sometimes not given at all.  This year Danny is the sole winner of the prize.

Danny’s dissertation is a compilation of eight (!) papers Danny wrote during his graduate studies, all on the same or closely related subject.  These papers advance and mostly finish off the long program of understanding the boundary of what’s feasible in PA. The most important of these is our joint FOCS paper which basically says that Integer Programming and Parametric Integer Programming is all that’s left in P, while all longer formulas are NP-hard.  See Featured MathSciNet Review by Sasha Barvinok and an overlapping blog post by Gil Kalai discussing these results.  See also Danny’s FOCS talk video and my MSRI talk video presenting this work.

 

ICM 2018 Speakers

UCLA recently outed me (with permission) as a speaker at the next ICM in Rio. I am incredibly honored to be chosen, alongside my fantastic colleagues Matthias Aschenbrenner, Andrea Bertozzi, Ciprian Manolescu and Sucharit Sarkar.

P.S.  I have more to say on the subject of ICM, but that can wait perhaps.

***************

FINAL UPDATE:
A complete list of ICM speakers is available here.

The power of negative thinking, part I. Pattern avoidance

In my latest paper with Scott Garrabrant we disprove the Noonan-Zeilberger Conjecture. Let me informally explain what we did and why people should try to disprove conjectures more often.  This post is the first in a series.  Part II will appear shortly.

What did we do?

Let F ⊂ S_k be a finite set of permutations and let C_n(F) denote the number of permutations σ ∈ S_n avoiding the set of patterns F. The Noonan-Zeilbeger conjecture (1996), states that the sequence {C_n(F)} is always P-recursive. We disprove this conjecture.  Roughly, we show that every Turing machine T can be simulated by a set of patterns F, so that the number a_n of paths of length n accepted by by T is equal to C_n(F) mod 2.  I am oversimplifying things quite a bit, but that’s the gist.

What is left is to show how to construct a machine T such that {a_n} is not equal (mod 2) to any P-recursive sequence.  We have done this in our previous paper, where give a negative answer to a question by Kontsevich.  There, we constructed a set of 19 generators of GL(4,Z), such that the probability of return sequence is not P-recursive.

When all things are put together, we obtain a set F of about 30,000 permutations in S₈₀ for which {C_n(F)} is non-P-recursive.  Yes, the construction is huge, but so what?  What’s a few thousand permutations between friends?  In fact, perhaps a single pattern (1324) is already non-P-recursive.  Let me explain the reasoning behind what we did and why our result is much stronger than it might seem.

Why we did what we did

First, a very brief history of the NZ-conjecture (see Kirtaev’s book for a comprehensive history of the subject and vast references).  Traditionally, pattern avoidance dealt with exact and asymptotic counting of pattern avoiding permutations for small sets of patterns.  The subject was initiated by MacMahon (1915) and Knuth (1968) who showed that we get Catalan numbers for patterns of length 3.  The resulting combinatorics is often so beautiful or at least plentiful, it’s hard to imagine how can it not be, thus the NZ-conjecture.  It was clearly very strong, but resisted all challenges until now.  Wilf reports that Richard Stanley disbelieved it (Richard confirmed this to me recently as well), but hundreds of papers seemed to confirm its validity in numerous special cases.

Curiously, the case of the (1324) pattern proved difficult early on.  It remains unresolved whether C_n(1324) is P-recursive or not.  This pattern broke Doron Zeilberger’s belief in the conjecture, and he proclaimed that it’s probably non-P-recursive and thus NZ-conjecture is probably false.  When I visited Doron last September he told me he no longer has strong belief in either direction and encouraged me to work on the problem.  I took a train back to Manhattan looking over New Jersey’s famously scenic Amtrack route.  Somewhere near Pulaski Skyway I called Scott to drop everything, that we should start working on this problem.

You see, when it comes to pattern avoidance, things move from best to good to bad to awful.  When they are bad, they are so bad, it can be really hard to prove that they are bad.  But why bother – we can try to figure out something awful.  The set of patterns that we constructed in our paper is so awful, that proving it is awful ain’t so bad.

Why is our result much stronger than it seems?

That’s because the proof extends to other results.  Essentially, we are saying that everything bad you can do with Turing machines, you can do with pattern avoidance (mod 2).  For example, why is (1324) so hard to analyze?  That’s because it’s even hard to compute both theoretically and experimentally – the existing algorithms are recursive and exponential in n.  Until our work, the existing hope for disproving the NZ-conjecture hinged on finding an appropriately bad set of patterns such that computing {C_n(F)} is easy.  Something like this sequence which has a nice recurrence, but is provably non-P-recursive.  Maybe.  But in our paper, we can do worse, a lot worse…

We can make a finite set of patterns F, such that computing {C_n(F) mod 2} is “provably” non-polynomial (Th 1.4).  Well, we use quotes because of the complexity theory assumptions we must have.  The conclusion is much stronger than non-P-recursiveness, since every P-recursive sequence has a trivial polynomial in n algorithm computing it.  But wait, it gets worse!

We prove that for two sets of patterns F and G, the problem “C_n(F) = C_n(G) mod 2 for all n” is undecidable (Th 1.3).  This is already a disaster, which takes time to sink in.  But then it gets even worse!  Take a look at our Corollary 8.1.  It says that there are two sets of patterns F and G, such that you can never prove nor disprove that C_n(F) = C_n(G) mod 2.  Now that’s what I call truly awful.

What gives?

Well, the original intuition behind the NZ-conjecture was clearly wrong.  Many nice examples is not a good enough evidence.  But the conjecture was so plausible!  Where did the intuition fail?  Well, I went to re-read Polya’s classic “Mathematics and Plausible Reasoning“, and it all seemed reasonable.  That is both Polya’s arguments and the NZ-conjecture (if you don’t feel like reading the whole book, at least read Barry Mazur’s interesting and short followup).

Now think about Polya’s arguments from the point of view of complexity and computability theory.  Again, it sounds very “plausible” that large enough sets of patterns behave badly.  Why wouldn’t they?  Well, it’s complicated.  Consider this example.  If someone asks you if every 3-connected planar cubic graph has a Hamiltonian cycle, this sounds plausible (this is Tait’s conjecture).  All small examples confirm this.  Planar cubic graphs do have very special structure.  But if you think about the fact that even for planar graphs, Hamiltonicity is NP-complete, it doesn’t sound plausible anymore.  The fact that Tutte found a counterexample is no longer surprising.  In fact, the decision problem was recently proved to be NP-complete in this case.  But then again, if you require 4-connectivity, then every planar graph has a Hamiltonian cycle.  Confused enough?

Back to the patterns.  Same story here.  When you look at many small cases, everything is P-recursive (or yet to be determined).  But compare this with Jacob Fox’s theorem that for a random single pattern π, the sequence {C_n(π)} grows much faster than originally expected (cf. Arratia’s Conjecture).  This suggests that small examples are not representative of complexity of the problem.  Time to think about disproving ALL conjectures based on that evidence.

If there is a moral in this story, it’s that what’s “plausible” is really hard to judge.  The more you know, the better you get.  Pay attention to small crumbs of evidence.  And think negative!

What’s wrong with being negative?

Well, conjectures tend to be optimistic – they are wishful thinking by definition.  Who would want to conjecture that for some large enough a,b,c and n, there exist a solution of aⁿ + bⁿ = cⁿ?  However, being so positive has a drawback – sometimes you get things badly wrong.  In fact, even polynomial Diophantine equations can be as complicated as one wishes.  Unfortunately, there is a strong bias in Mathematics against counterexamples.  For example, only two of the Clay Millennium Problems automatically pay $1 million for a counterexample.  That’s a pity.  I understand why they do this, just disagree with the reasoning.  If anything, we should encourage thinking in the direction where there is not enough research, not in the direction where people are already super motivated to resolve the problem.

In general, it is always a good idea to keep an open mind.  Forget all this “power of positive thinking“, it’s not for math.  If you think a conjecture might be false, ignore everybody and just go for disproof.  Even if it’s one of those famous unsolved conjectures in mathematics.   If you don’t end up disproving the conjecture, you might have a bit of trouble publishing computational evidence.  There are some journals who do that, but not that many.  Hopefully, this will change soon…

Happy ending

When we were working on our paper, I wrote to Doron Zeilberger if he ever offered a reward for the NZ-conjecture, and for the disproof or proof only?  He replied with an unusual award, for the proof and disproof in equal measure.  When we finished the paper I emailed to Doron.  And he paid.  Nice… 🙂

What do math journals do? What will become of them in the future?

Recently, there has been plenty of discussions on math journals, their prices, behavior, technology and future.   I have been rather reluctant to join the discussion in part due to my own connection to Elsevier, in part because things in Combinatorics are more complicated than in other areas of mathematics (see below), but also because I couldn’t reconcile several somewhat conflicting thoughts that I had.  Should all existing editorial boards revolt and all journals be electronic?  Or perhaps should we move to “pay-for-publishing” model?  Or even “crowd source refereeing”?  Well, now that the issue a bit cooled down, I think I figured out exactly what should happen to math journals.  Be patient – a long explanation is coming below.

Quick test questions

I would like to argue that the debate over the second question is the general misunderstanding of the first question in the title.  In fact, I am pretty sure most mathematicians are quite a bit confused on this, for a good reason.  If you think this is easy, quick, answer the following three questions:

1)  Published paper has a technical mistake invalidating the main result.  Is this a fault of author, referee(s), handling editor, managing editor(s), a publisher, or all of the above?  If the reader find such mistake, who she/he is to contact?

2)  Published paper proves special case of a known result published 20 years earlier in an obscure paper.  Same question.  Would the answer change if the author lists the paper in the references?

3) Published paper is written in a really poor English.  Sections are disorganized and the introduction is misleading.  Same question.

Now that you gave your answers, ask a colleague.  Don’t be surprised to hear a different point of view.  Or at least don’t be surprised when you hear mine.

What do referees do?

In theory, a lot.  In practice, that depends.  There are few official journal guides to referees, but there are several well meaning guides (see also here, here, here,  here §4.10, and a nice discussion by Don Knuth §15).  However, as any editor can tell you, you never know what exactly did the referee do.  Some reply within 5 min, some after 2 years.  Some write one negative sentence, some 20 detailed pages, some give an advice in the style “yeah, not a bad paper, cites me twice, why not publish it”, while others a brushoff “not sure who this person is, and this problem is indeed strongly related to what I and my collaborators do, but of course our problems are much more interesting/important  – rejection would be best”.  The anonymity is so relaxing, doing a poor job is just too tempting.  The whole system hinges on the shame, sense of responsibility, and personal relationship with the editor.

A slightly better questions is “What do good referees do?”  The answer is – they don’t just help the editor make acceptance/rejection decision.  They help the authors.  They add some background the authors don’t know, look for missing references, improve on the proofs, critique the exposition and even notation.  They do their best, kind of what ideal advisors do for their graduate students, who just wrote an early draft of their first ever math paper.

In summary, you can’t blame the referees for anything.  They do what they can and as much work as they want.  To make a lame comparison, the referees are like wind and the editors are a bit like sailors.  While the wind is free, it often changes direction, sometimes completely disappears, and in general quite unreliable.  But sometimes it can really take you very far.  Of course, crowd sourcing refereeing is like democracy in the army – bad even in theory, and never tried in practice.

First interlude: refereeing war stories

I recall a curious story by Herb Wilf, on how Don Knuth submitted a paper under assumed name with an obscure college address, in order to get full refereeing treatment (the paper was accepted and eventually published under Knuth’s real name).  I tried this once, to unexpected outcome (let me not name the journal and the stupendous effort I made to create a fake identity).  The referee wrote that the paper was correct, rather interesting but “not quite good enough” for their allegedly excellent journal.  The editor was very sympathetic if a bit condescending, asking me not to lose hope, work on my papers harder and submit them again.  So I tried submitting to a competing but equal in statue journal, this time under my own name. The paper was accepted in a matter of weeks.  You can judge for yourself the moral of this story.

A combinatorialist I know (who shall remain anonymous) had the following story with Duke J. Math.  A year and a half after submission, the paper was rejected with three (!) reports mostly describing typos.  The authors were dismayed and consulted a CS colleague.  That colleague noticed that the three reports were in .pdf  but made by cropping from longer files.   Turns out, if the cropping is made straightforwardly, the cropped portions are still hidden in the files.  Using some hacking software the top portions of the reports were uncovered.  The authors discovered that they are extremely positive, giving great praise of the paper.  Now the authors believe that the editor despised combinatorics (or their branch of combinatorics) and was fishing for a bad report.  After three tries, he gave up and sent them cropped reports lest they think somebody else considers their paper worthy of publishing in the grand old Duke (cf. what Zeilberger wrote about Duke).

Another one of my stories is with the  Journal of AMS.  A year after submission, one of my papers was rejected with the following remarkable referee report which I quote here in full:

The results are probably well known.  The authors should consult with experts.  

Needless to say, the results were new, and the paper was quickly published elsewhere.  As they say, “resistance is futile“.

What do associate/handling editors do?

Three little things, really.  They choose referees, read their reports and make the decisions.  But they are responsible for everything.  And I mean for everything, both 1), 2) and 3).  If the referee wrote a poorly researched report, they should recognize this and ignore it, request another one.  They should ensure they have more than one opinion on the paper, all of them highly informed and from good people.  If it seems the authors are not aware of the literature and referee(s) are not helping, they should ensure this is fixed.  It the paper is not well written, the editors should ask the authors to rewrite it (or else).   At Discrete Mathematics, we use this page by Doug West, as a default style to math grammar.  And if the reader finds a mistake, he/she should first contact the editor.  Contacting the author(s) is also a good idea, but sometimes the anonymity is helpful – the editor can be trusted to bring bad news and if possible, request a correction.

B.H. Neumann described here how he thinks the journal should operate.  I wish his views held widely today.  The  book by Krantz, §5.5, is a good outline of the ideal editorial experience, and this paper outlines how to select referees.  However, this discussion (esp. Rick Durrett’s “rambling”) is more revealing.  Now, the reason most people are confused as to who is responsible for 1), 2) and 3), is the fact that while some journals have serious proactive editors, others do not, or their work is largely invisible.

What do managing editors and publishers do?

In theory, managing editors hire associate editors, provide logistical support, distribute paper load, etc.  In practice they also serve as handling editors for a large number of papers.  The publishers…  You know what the publishers do.  Most importantly, they either pay editors or they don’t.  They either charge libraries a lot, or they don’t.  Publishing is a business, after all…

Who wants free universal electronic publishing?

Good mathematicians.  Great mathematicians.  Mathematicians who write well and see no benefit in their papers being refereed.  Mathematicians who have many students and wish the publishing process was speedier and less cumbersome, so their students can get good jobs.  Mathematicians who do not value the editorial work and are annoyed when the paper they want to read is “by subscription only” and thus unavailable.  In general, these are people who see having to publish as an obstacle, not as a benefit.

Who does not want free universal electronic publishing?

Publishers (of course), libraries, university administrators.  These are people and establishments who see value in existing order and don’t want it destroyed.  Also: mediocre mathematicians, bad mathematicians, mathematicians from poor countries, mathematicians who don’t have access to good libraries (perhaps, paradoxically).  In general, people who need help with their papers.  People who don’t want a quick brush-off  “not good enough” or “probably well known”, but those who need advice on the references, on their English, on how the papers are structured and presented, and on what to do next.

So, who is right?

Everyone.  For some mathematicians, having all journals to be electronic with virtually no cost is an overall benefit.  But at the very least, “pro status quo” crowd have a case, in my view.  I don’t mean that Elsevier pricing policy is reasonable, I am talking about the big picture here.  In a long run, I think of journals as non-profit NGO‘s, some kind of nerdy versions of Nobel Peace Prize winning Médecins Sans Frontières.  While I imagine that in the future many excellent top level journals will be electronic and free, I also think many mid-level journals in specific areas will be run by non-profit publishers, not free at all, and will employ a number of editorial and technical stuff to help the authors, both of papers they accept and reject.  This is a public service we should strive to perform, both for the sake of those math papers, and for development of mathematics in other countries.

Right now, the number of mathematicians in the world is already rather large and growing.  Free journals can do only so much.  Without high quality editors paid by the publishers, with a large influx of papers from the developing world, there is a chance we might loose the traditional high standards for published second tier papers.  And I really don’t want to think of a mathematics world once the peer review system is broken.  That’s why I am not in the “free publishing camp” – in an effort to save money, we might loose something much more valuable – the system which gives foundation and justification of our work.

Second interlude: journals vis-à-vis combinatorics

I already wrote about the fate of combinatorics papers in the Annals, especially when comparison with Number Theory.  My view was gloomy but mildly optimistic.  In fact, since that post was written couple more combinatorics papers has been accepted.  Good.  But let me give you a quiz.  Here are two comparable highly selective journals – Duke J. Math. and Composito Math.  In the past 10 years Composito published exactly one (!) paper in Combinatorics (defined as primary MSC=05), of the 631 total.  In the same period, Duke published 8 combinatorics papers of 681 total.

Q: Which of the two (Composito or Duke) treats combinatorics papers better?

A: Composito, of course.

The reasoning is simple.  Forget the anecdotal evidence in the previous interlude.  Just look at the “aim and scope” of the journals vs. these numbers.  Here is what Compsito website says with a refreshing honesty:

By tradition, the journal published by the foundation focuses on papers in the main stream of pure mathematics. This includes the fields of algebra, number theory, topology, algebraic and analytic geometry and (geometric) analysis. Papers on other topics are welcome if they are of interest not only to specialists.

Translation: combinatorics papers are not welcome (as are papers in many other fields).  I think this is totally fair.  Nothing wrong with that.  Clearly, there are journals which publish mostly in combinatorics, and where papers in none of these fields would be welcome.  In fact there is a good historical reason for that.  Compare this with what Duke says on its website:

Published by Duke University Press since its inception in 1935, the Duke Mathematical Journal is one of the world’s leading mathematical journals. Without specializing in a small number of subject areas, it emphasizes the most active and influential areas of current mathematics.

See the difference?  They don’t name their favorite areas!  How are the authors supposed to guess which are these?  Clearly, Combinatorics with its puny 1% proportion of Duke papers is not a subject area that Duke “emphasizes”.  Compare it with 104 papers in Number Theory (16%) and 124 papers in Algebraic Geometry (20%) over the same period.  Should we conclude that in the past 10 years, Combinatorics was not “the most active and influential”, or perhaps not “mathematics” at all? (yes, some people think so)  I have my own answer to this question, and I bet so do you…

Note also, that things used to be different at Duke.  For example, exactly 40 years earlier, in the period 1963-1973, Duke published 47 papers in combinatorics out of 972 total, even though the area was only in its first stages of development.  How come?  The reason is simple: Leonard Carlitz was Managing Editor at the time, and he welcomed papers from a number of prominent combinatorialists active during that time, such as Andrews, Gould, Moon, Riordan, Stanley, Subbarao, etc., as well as a many of his own papers.

So, ideally, what will happen to math journals?

That’s actually easy.  Here are my few recommendations and predictions.

1)  We should stop with all these geography based journals.  That’s enough.  I understand the temptation for each country, or university, or geographical entity to have its own math journal, but nowadays this is counterproductive and a cause for humor.  This parochial patriotism is perhaps useful in sports (or not), but is nonsense in mathematics.  New journals should emphasize new/rapidly growing areas of mathematics underserved by current journals, not new locales where printing presses are available.

2)  Existing for profit publishers should realize that with the growth of arXiv and free online competitors, their business model is unsustainable.  Eventually all these journals will reorganize into a non-profit institutions or foundations.  This does not mean that the journals will become electronic or free.  While some probably will, others will remain expensive, have many paid employees (including editors), and will continue to provide services to the authors, all supported by library subscriptions.  These extra services are their raison d’être, and will need to be broadly advertised.  The authors would learn not to be surprised of a quick one line report from free journals, and expect a serious effort from “expensive journals”.

3)  The journals will need to rethink their structure and scope, and try to develop their unique culture and identity.  If you have two similar looking free electronic journals, which do not add anything to the papers other than their .sty file, the difference is only the editorial board and history of published papers.  This is not enough.  All journals, except for the very top few, will have to start limiting their scope to emphasize the areas of their strength, and be honest and clear in advertising these areas.  Alternatively, other journals will need to reorganize and split their editorial board into clearly defined fields.  Think  Proc. LMS,  Trans. AMS, or a brand new  Sigma, which basically operate as dozens of independent journals, with one to three handling editors in each.  While highly efficient, in a long run this strategy is also unsustainable as it leads to general confusion and divergence in the quality of these sub-journals.

4)  Even among the top mathematicians, there is plenty of confusion on the quality of existing mathematics journals, some of which go back many decades.  See e.g. a section of Tim Gowers’s post about his views of the quality of various Combinatorics journals, since then helpfully updated and corrected.  But at least those of us who have been in the area for a while, have the memory of the fortune of previously submitted papers, whether our own, or our students, or colleagues.  A circumstantial evidence is better than nothing.  For the newcomers or outsiders, such distinctions between journals are a mystery.  The occasional rankings (impact factor or this, whatever this is) are more confusing than helpful.

What needs to happen is a new system of awards recognizing achievements of individual journals and/or editors, in their efforts to improve the quality of the journals, attracting top papers in the field, arranging fast refereeing, etc.   Think a mixture of Pulitzer Prize and J.D. Power and Associates awards – these would be a great help to understand the quality of the journals.  For example, the editors of the Annals clearly hustled to referee within a month in this case (even if motivated by PR purposes).  It’s an amazing speed for a technical 50+ page paper, and this effort deserves recognition.

Full disclosure:  Of the journals I singled out, I have published once in both  JAMS  and  Duke.  Neither paper is in Combinatorics, but both are in Discrete Mathematics, when understood broadly.

What’s the Matter with Hertz Foundation?

Imagine you have plenty of money and dozens of volunteers.  You decide to award one or two fellowships a year to the best of the best of the best in math sciences.  Easy, right?  Then how do you repeatedly fail at this, without anyone notice?  Let me tell you how.  It’s an interesting story, so bear with me.

A small warning.  Although it may seem I am criticizing Hertz Foundation, my intention is to show its weakness so it can improve.

What is the Hertz Foundation?

Yesterday I wrote a recommendation letter to the Hertz Foundation.  Although a Fellow myself, I never particularly cared for the foundation, mostly because it changed so little in my life (I received it only for two out of five years of eligibility).  But I became rather curious as to what usually happens to Hertz Fellows.  I compiled the data, and found the results quite disheartening.  While perhaps excellent in other fields, I came to believe that Hertz does barely a mediocre job awarding fellowships in mathematics.  And now that I think about it, this was all completely predictable.

First, a bit of history.  John Hertz was the Yellow Cab founder and car rental entrepreneur (thus the namesake company), and he left a lot of money dedicated for education in “applied physical sciences”, now understood to include applied mathematics.  What exactly is “applied mathematics” is rather contentious, so the foundation wisely decided that “it is up to each fellowship applicant to advocate to us his or her specific field of interest as an ‘applied physical science’.”

In practice, according to the website, about 600 applicants in all areas of science and engineering apply for a fellowship.  Applications are allowed only either in the senior year of college or 1st year of grad school.  The fellowships are generous and include both the stipend and the tuition; between 15 and 20 students are awarded every year.  Only US citizen and permanent residents are eligible, and the fellowship can be used only in one of the 47 “tenable schools” (more on this below).  The Foundation sorts the applications, and volunteers interview some of them in the first round.  In the second round, pretty much only one person interviews all that advanced, and the decision is made.  Historically, only one or two fellowships in mathematical sciences are awarded each year (this includes pure math, applied math, and occasionally theoretical CS or statistics).

Forty years of Math Hertz Fellowships in numbers

The Hertz Foundation website has a data on all past fellows.  I compiled the data in Hertz-list which spanned 40 years (1971-2010), listed by the year the fellowship ended, which usually but not always coincided with graduation.  There were 67 awardees in mathematics, which makes it about 1.7 fellowships a year.  The Foundation states that it awarded “over 1000 fellowships” so I guess about 5-6% went into maths (perhaps, fewer in recent years).  Here is who gets them.

1) Which schools are awarded?  Well, only 44 US graduate programs are allowed to administer the fellowships.  The reasons (other than logistical) are unclear to me.  Of those programs that are “in”, you have University of Rochester (which nearly lost its graduate program), and UC Santa Cruz (where rumors say a similar move had been considered).  Those which are “out” include graduate programs at Brown, UPenn, Rutgers, UNC Chapel Hill, etc.  The real distribution is much more skewed, of course. Here is a complete list of awards per institution:

MIT – 14
Harvard, Princeton – 8
Caltech, NYU – 7
Berkeley, Stanford – 5
UCLA – 3
CMU, Cornell, U Chicago – 2
GA Tech, JHU, RPI, Rice – 1

In summary, only 15 universities had at least one award (34%), and just 7 universities were awarded 54 fellowships (i.e. 16% of universities received 81% of all fellowships).  There is nothing wrong with this per se, just a variation on the 80-20 rule you might argue.  But wait!  Hertz Foundation is a non-profit institution and the fellowship itself comes with a “moral commitment“.  Even if you need to interfere with “free marketplace” of acceptance decisions (see P.S. below), wouldn’t it be in the spirit of John Hertz’s original goal, to make a special effort to distribute the awards more widely?  For example, Simons Foundation is not shy about awarding fellowship to institutions many of which are not even on Hertz’s list.

2)  Where are they now?  After two hours of googling, I located almost all former fellows and determined their current affiliations (see the Hertz-list).  I found that of the 67 fellows:

University mathematicians – 27 (40%)
Of these, work at Hertz eligible universities – 14, or about 21% of the total (excluding 3 overseas)
At least 10 who did not receive a Ph.D. – 15%
At least 13 are in non-academic research – 19% (probably more)
At least 8 in Software Development and Finance – 12% (probably more)

Now, there is certainly nothing wrong with directing corporate research, writing software, selling derivatives, designing museum exhibits, and even playing symphony orchestra or heading real estate company, as some of the awardees do now.  Many of these are highly desirable vocations.  But really, was this what Hertz had in mind when dedicating the money?  In the foundation’s language, “benefit us all” they don’t.

I should mention that the list of Hertz Fellows in Mathematics does include a number of great academic success stories, but that’s not actually surprising.  Every US cohort has dozens of excellent mathematicians.  But the 60% drop out rate from academia is very unfortunate, only 21% working in “tenable universities” is dismaying, and the 15% drop out rate from graduate programs is simply miserable.  Couldn’t they have done better?

A bit of analysis

Every year, US universities award over 1,600 Ph.D.’s in mathematical sciences, of which over a half go to US citizen (more if you include permanent residents, but stats is not easily available).  So they are choosing 1.7 out of over 800 eligible students.  Ok, because of their “tenable schools” restriction this is probably more like 300-400.   Therefore, less than half of one percent of potential applicants are awarded!  For comparison, Harvard college acceptance rate is 10 times that.

Let me repeat: in mathematics, Hertz fellows drop out from their Ph.D. programs at a rate of 15%.  If you look into the raw 2006 NRC data for graduation rates, you will see that many of the top universities have over 90% graduation rate in the math programs (say, Harvard has over 91%).  Does that mean that Harvard on average does a better job selecting 10-15 grad students every year, while Hertz can’t choose one?

Yes, I think it does.  And the gap is further considering that Hertz has virtually no competition (NSF Fellowships are less generous in every respect).  You see, people at Harvard (or Princeton, MIT, UCLA, etc.) who read graduate applications, know what they are doing.  They are professionals who are looking for the most talented mathematicians from a large pool of applicants.  They know which letters need to be taken seriously, and which with a grain of salt.  They know which undergraduate research experience is solid and which is worthless.  They just know how things are done.

Now, a vast majority of Hertz interviewers are themselves former fellows, and thus about 95% of them have no idea about the mathematics research (they just assume it’s no different from the research they are accustomed to).  Nor does the one final interviewer, who is an applied physicist.  As a result, they are to some extend, flipping coins and rolling dies, in hope things will work out.  You can’t really blame them – they simply don’t know how to choose.  I still remember my own two interviews.  Both interviewers were nice, professional, highly experienced and well intentioned, but looking back I can see that neither had much experience with mathematical research.

You can also see this lack of understanding of mathematics culture is creeping up in other activities of the foundation, such as the thesis prize award (where are mathematicians?), etc.   Of course a private foundation can award anyone it pleases, but it seems to me it would do much more good if only some special care is applied.

A modest proposal

There is of course, a radical way to change the review of mathematics applicants – subcontract it to the AMS (or IMA, MSRI, IPAM – all have the required infrastructure).  For a modest fee, the AMS will organize a panel of mathematicians who will review and rank the applicants without interviewing them.  The panel will be taking into consideration only students’ research potential, not the university prestige, etc.  The Hertz people can then interview the top ranked and make a decision at the last stage, but the first round will be by far superior to current methods.  Even the NSA trusts AMS, so shouldn’t you?

Hertz might even save some money it currently spends on travel and lodging reimbursements.  The 13% operating budget is about average, but there is some room for improvement.  Subcontracting will probably lead to an increase in applications, as AMS really knows how to advertise to its members (I bet you currently receive only about 40 mathematics applications, out of a potential 400+ pool).  To summarize: really, Hertz Foundation, think about doing that!

P.S.  It is not surprising that the 7 top universities get a large number of the fellowships.  One might be tempted to assume that clueless interviewers are perhaps somewhat biased towards famous school names in the hope that these schools already made a good decision accepting these applicants, but this is not the whole story.  The described bias can only work for the 1st year grad applicants, but for undergraduate applicants a different process seems to hold.  Once a graduate school learns that an applicant received Hertz Fellowship (or NSF for that matter), it has every incentive to accept the student, as the tuition and the stipend are paid by the outside sources now.

P.P.S.  Of course, mathematicians’ review can also fail.  Even the super prestigious AIM Fellowship has at least one recipient who left academia for bigger and better things.

UPDATE (April 15, 2019).  Over the years since this blog post, I have been contacted by people from the Hertz Foundation board.  I have also followed up on the story and the recent fellowship recipients.  I am happy to say that the foundation implemented various important changes vis-à-vis math interviews, to the visible effect.  At the moment, the numbers are too small to report statistics and the changes I know are not a public information.   I concluded that my criticism no longer applies, a happy ending to the story.  I encourage now everyone to support the foundation financially as well as recommend your best students to apply.