## ICM Paper

Well, I finally finished my **ICM paper**. It’s only 30 pp, but it took many sleepless nights to write and maybe about 10 years to understand what exactly do I want to say. The published version will be a bit shorter – I had to cut section 4 to satisfy their page limitations.

Basically, I give a survey of various recent and not-so-recent results in *Enumerative Combinatorics* around three major questions:

**(1)** What is a formula?

**(2)** What is a good bijection?

**(3)** What is a combinatorial interpretation?

Not that I answer these questions, but rather explain how one *could answer* them from computational complexity point of view. I tried to cover as much ground as I could without overwhelming the reader. Clearly, I had to make a lot of choices, and a great deal of beautiful mathematics had to be omitted, sometimes in favor of the Computational Combinatorics approach. Also, much of the survey surely reflects my own POV on the subject. I sincerely apologize to everyone I slighted and who disagrees with my opinion! Hope you still enjoy the reading.

Let me mention that I will wait for a bit before posting the paper on the arXiv. I very much welcome all comments and suggestions! Post them here or email privately.

P.S. In thinking of how approach this paper, I read a large number of papers in previous ICM proceedings, e.g. papers by Noga Alon, Mireille Bousquet-Mélou, Paul Erdős, Philippe Flajolet, Marc Noy, János Pach, Richard Stanley, Benny Sudakov, and many others. They are all terrific and worth reading even if just to see how the field has been changing over the years. I also greatly benefited from a short introductory article by Doron Zeilberger, which I strongly recommend.

## How to write math papers clearly

Writing a mathematical paper is both an act of recording mathematical content and a means of communication of one’s work. In contrast with other types of writing, the style of math papers is incredibly rigid and resistant to even modest innovation. As a result, both goals suffer, sometimes immeasurably. The * clarity* suffers the most, which affects everyone in the field.

Over the years, I have been giving advice to my students and postdocs on how to write clearly. I collected them all in ** these notes.** Please consider reading them and passing them to your students and colleagues.

Below I include one subsection dealing with different reference styles and what each version really means. This is somewhat subjective, of course. Enjoy!

****

**4.2. How to cite a single paper.** The citation rules are almost as complicated as Chinese honorifics, with an added disadvantage of never being discussed anywhere. Below we go through the (incomplete) list of possible ways in the decreasing level of citation importance and/or proof reliability.

(1) “*Roth proved Murakami’s conjecture in* [Roth].” Clear.

(2) “*Roth proved Murakami’s conjecture *[Roth].” Roth proved the conjecture, possibly in a different paper, but this is likely a definitive version of the proof.

(3) “*Roth proved Murakami’s conjecture, see* [Roth].” Roth proved the conjecture, but [Roth] can be anything from the original paper to the followup, to some kind of survey Roth wrote. Very occasionally you have “*see* [Melville]”, but that usually means that Roth’s proof is unpublished or otherwise unavailable (say, it was given at a lecture, and Roth can’t be bothered to write it up), and Melville was the first to publish Roth’s proof, possibly without permission, but with attribution and perhaps filling some minor gaps.

(4) “*Roth proved Murakami’s conjecture* [Roth], *see also* [Woolf].” Apparently Woolf also made an important contribution, perhaps extending it to greater generality, or fixing some major gaps or errors in [Roth].

(5) “*Roth proved Murakami’s conjecture in* [Roth] (*see also* [Woolf]).” Looks like [Woolf] has a complete proof of Roth, possibly fixing some minor errors in [Roth].

(6) “*Roth proved Murakami’s conjecture* (*see* [Woolf]).” Here [Woolf] is a definitive version of the proof, e.g. the standard monograph on the subject.

(7) “*Roth proved Murakami’s conjecture, see e.g. * [Faulkner, Fitzgerald, Frost].” The result is important enough to be cited and its validity confirmed in several books/surveys. If there ever was a controversy whether Roth’s argument is an actual proof, it was resolved in Roth’s favor. Still, the original proof may have been too long, incomplete or simply presented in an old fashioned way, or published in an inaccessible conference proceedings, so here are sources with a better or more recent exposition. Or, more likely, the author was too lazy to look for the right reference, so overcompensated with three random textbooks on the subject.

(8) “*Roth proved Murakami’s conjecture* (*see e.g.* [Faulkner, Fitzgerald, Frost]).” The result is probably classical or at least very well known. Here are books/surveys which all probably have statements and/or proofs. Neither the author nor the reader will ever bother to check.

(9) “*Roth proved Murakami’s conjecture.*^{7} Footnote 7: *See* [Mailer].” Most likely, the author never actually read [Mailer], nor has access to that paper. Or, perhaps, [Mailer] states that Roth proved the conjecture, but includes neither a proof nor a reference. The author cannot

verify the claim independently and is visibly annoyed by the ambiguity, but felt obliged to credit Roth for the benefit of the reader, or to avoid the wrath of Roth.

(10) “*Roth proved Murakami’s conjecture.*^{7} Footnote 7: *Love letter from H. Fielding to J. Austen, dated December 16, 1975.*” This means that the letter likely exists and contains the whole proof or at least an outline of the proof. The author may or may not have seen it. Googling will probably either turn up the letter or a public discussion about what’s in it, and why it is not available.

(11) “*Roth proved Murakami’s conjecture.*^{7} Footnote 7: *Personal communication.*” This means Roth has sent the author an email (or said over beer), claiming to have a proof. Or perhaps Roth’s student accidentally mentioned this while answering a question after the talk. The proof

may or may not be correct and the paper may or may not be forthcoming.

(12) “*Roth claims to have proved Murakami’s conjecture in* [Roth].” Paper [Roth] has a well known gap which was never fixed even though Roth insists on it to be fixable; the author would rather avoid going on record about this, but anything is possible after some wine at a banquet. Another possibility is that [Roth] is completely erroneous as explained elsewhere, but Roth’s

work is too famous not to be mentioned; in that case there is often a followup sentence clarifying the matter, sometimes in parentheses as in “(*see, however,* [Atwood])”. Or, perhaps, [Roth] is a 3 page note published in *Doklady Acad. Sci. USSR* back in the 1970s, containing a very brief outline of the proof, and despite considerable effort nobody has yet to give a complete proof of its Lemma 2; there wouldn’t be any followup to this sentence then, but the author would be happy to clarify things by email.

UPDATE 1. (Nov 1, 2017): There is now a video of the MSRI talk I gave based on the article.

UPDATE 2. (Mar 13, 2018): The paper was published in the *Journal of Humanistic Mathematics*. Apparently it’s now number 5 on “Most Popular Papers” list. Number 1 is “My Sets and Sexuality”, of course.