The Hungarian Combinatorics from an Advanced Standpoint

Previous post: Conceptual mathematics vs. the classical (combinatorial) one.

Again,  this post is a long reply to questions posed by ACM. It is a complement to the previous post "Conceptual mathematics vs. the classical (combinatorial) one". The title is intentionally similar to the titles of three well known books by F. Klein.

First, the terminology in “Conceptual mathematics vs. the classical (combinatorial) one” is my and was invented at the spot, and the word "classical" is a very bad choice. I should find something better. The word "conceptual" is good enough, but not as catchy as I may like. I meant something real, but as close as possible to the Gowers's idea of "two cultures". I do not believe in his theory anymore; but by simply using his terms I will promote it.

Another choice, regularly used in discussions in Gowers's blog is "combinatorial". It looks like it immediately leads to confusion, as one may see from your question (but not only). First of all (I already mentioned it in Gowers's blog or here), there two rather different types of combinatorics. At one pole there is the algebraic combinatorics and most of the enumerative combinatorics. R. Stanley and the late J.-C. Rota are among the best (or the best) in this field. One can give even a more extreme example, mentioned by M. Emerton: symmetric group and its representations. Partitions of natural numbers are at the core of this theory, and in this sense it is combinatorics. One the other hand, it was always considered as a part of the theory of representations, a highly conceptual branch of mathematics.

So, there is already a lot of conceptual and quite interesting combinatorics. And the same time, there is Hungarian combinatorics, best represented by the Hungarian school. It is usually associated with P. Erdös and since the last year Abel prize is also firmly associated with E. Szemerédi. Currently T. Gowers is its primary spokesperson, with T. Tao serving as supposedly independent and objective supporter. Of course, all this goes back for centuries.

Today the most obvious difference between these two kinds of combinatorics is the fact that the algebraic combinatorics is mostly about exact values and identities, and Hungarian combinatorics is mostly about estimates and asymptotics. If no reasonable estimate is in sight, the existence is good enough. This is the case with the original version of Szemerédi's theorem. T. Gowers added to it some estimates, which are huge but a least could be written down by elementary means. He also proved that any estimate should be huge (in a precise sense). I think that the short paper proving the latter (probably, it was Gowers's first publication in the field) is the most important result around Szemerédi’s theorem. It is strange that it got almost no publicity, especially if compared with his other papers and Green-Tao's ones. It could be the case that this opinion results from the influence of a classmate, who used to stress that lower estimates are much more deep and important than the upper ones (for positive numbers, of course), especially in combinatorial problems.

Indeed, I do consider Hungarian combinatorics as the opposite of all new conceptual ideas discovered during the last 100 years. This, obviously, does not mean that the results of Hungarian combinatorics cannot be approached conceptually. We have an example at hand: Furstenberg’s proof of Szemerédi theorem. It seems that it was obtained within a year of the publication of Szemerédi’s theorem (did not checked right now). Of course, I cannot exclude the possibility that Furstenberg worked on this problem (or his framework for his proof without having this particular application as the main goal) for years within his usual conceptual framework, and missed by only few months. I wonder how mathematics would look now if Furstenberg would be the first to solve the problem.

One cannot approach the area (not the results alone) of Hungarian combinatorics from any conceptual point of view, since the Hungarian combinatorics is not conceptual almost by the definition (definitely by its description by Gowers in his “Two cultures”). I adhere to the motto “Proofs are more important than theorems, definitions are more important than proofs”. In fact, I was adhering to it long before I learned about this phrase; this was my taste already in the middle school (I should confess that I realized this only recently). Of course, I should apply it uniformly. In particular, the Hungarian style of proofs (very convoluted combinations of well known pieces, as a first approximation) is more essential than the results proved, and the insistence on being elementary but difficult should be taken very seriously – it excludes any deep definitions.

I am not aware of any case when “heuristic” of Hungarian combinatorics lead anybody to conceptual results. The theorems can (again, Furstenberg), but they are not heuristics.

I am not in the business of predicting the future, but I see only two ways for Hungarian combinatorics, assuming that the conceptual mathematics is not abandoned. Note that still not even ideas of Grothendieck are completely explored, and, according to his coauthor J. Dieudonne, there are enough ideas in Grothendieck’s work to occupy mathematicians for centuries to come – the conceptual mathematics has no internal reasons to die in any foreseeable future. Either the Hungarian combinatorics will mature by itself and will develop new concepts which eventually will turn it into a part of conceptual mathematics. There are at least germs of such development. For example, matroids (discovered by H. Whitney, one of the greatest topologists of the 20^th century) are only at the next level of abstraction after the graphs, but matroids is an immensely useful notion (unfortunately, it is hardly taught anywhere, which severely impedes its uses). Or it will remain a collection of elementary tricks, and will resemble more and more the collection of mathematical Olympiads problems. Then it will die out and forgotten.

I doubt that any area of mathematics, which failed to conceptualize in a reasonable time, survived as an active area of research. Note that the meaning of the word “reasonable” changes with time itself; at the very least because of the huge variations of the number of working mathematicians during the history. Any suggestions of counterexamples?

Next post: About Timothy Gowers.

The conceptual mathematics vs. the classical (combinatorial) one.

Previous post: Simons's video protection, youtube.com, etc.

This post is an attempt to answer some questions of ACM in a form not requiring knowledge of Grothendieck ideas or anything simlilar.

But it is self-contained and touches upon important and hardly wide known issues.

--------------------------------------------

It is not easy to explain how conceptual theorems and proofs, especially the ones of the level close to the one of Grothendieck work, could be at the same time more easy and more difficult at the same time. In fact, they are easy in one sense and difficult in another. The conceptual mathematics depends on – what one expect here? – on new concepts, or, what is the same, on the new definitions in order to solve new problems. The hard part is to discover appropriate definitions. After this proofs are very natural and straightforward up to being completely trivial in many situations. They are easy. Classically, the convoluted proofs with artificial tricks were valued most of all. Classically, it is desirable to have a most elementary proof possible, no matter how complicated it is.

A lot of efforts were devoted to attempts to prove the theorem about the distribution of primes elementary. In this case the requirement was not to use the theory of complex functions. Finally, such proof was found, and it turned out to be useless. Neither the first elementary proof, nor subsequent ones had clarified anything, and none helped to prove a much more precise form of this theorem, known as Riemann hypothesis (this is still an open problem which many consider as the most important problem in mathematics).

Let me try to do this using a simple example, which, perhaps, I had already mentioned (I am sure that I spoke about it quite recently, but it may be not online). This example is not a “model” or a toy, it is real.

Probably, you know about the so-called Fundamental Theorem of Calculus, usually wrongly attributed to Newton and Leibniz (it was known earlier, and, for example, was presented in the lectures and a textbook of Newton's teacher, John Barrow). It relates the derivatives with integrals. Nothing useful can be done without it. Now, one can integrate not only functions of real numbers, but also functions of two variables (having two real numbers as the input), three, and so on. One can also differentiate functions of several variables (basically, by considering them only along straight lines and using the usual derivatives). A function of, say, 5 variables has 5 derivatives, called its partial derivatives.

Now, the natural question to ask is if there is an analogue of the Fundamental Theorem of Calculus for functions of several variables. In 19^th century such analogues were needed for applications. Then 3 theorems of this sort were proved, namely, the theorems of Gauss-Ostrogradsky (they discovered it independently of each other, and I am not sure if there was a third such mathematician or not), Green, and Stokes (some people, as far as I remember, attribute it to J.C. Maxwell, but it is called the Stokes theorem anyhow). The Gauss-Ostrogradsky theorem deals with integration over 3-dimensional domains in space, the Green theorem with 2 dimensional planar domains, and the Stokes theorem deals with integration over curved surfaces in the usual 3-dimensional space. I hope that I did not mix them up; the reason why this could happen is at the heart of the matter. Of course, I can check this in moment; but then an important point would be less transparent.

Here are 3 theorems, clearly dealing with similar phenomena, but looking very differently and having different and not quite obvious proofs. But there are useful functions of more than 3 variables. What about them? There is a gap in my knowledge of the history of mathematics: I don’t know any named theorem dealing with more variables, except the final one. Apparently, nobody wrote even a moderately detailed history of the intermediate period between the 3 theorems above and the final version.

The final version is called the Stokes theorem again, despite Stokes has nothing do with it (except that he proved that special case). It applies to functions of any number of variables and even to functions defined on so-called smooth manifolds, the higher-dimensional generalization of surfaces. On manifolds, variables can be introduced only locally, near any point; and manifolds themselves are not assumed to be contained in some nice ambient space like the Euclidean space. So, the final version is much more general. And the final version has exactly the same form in all dimension, but the above mentioned 3 theorems are its immediate corollaries. This is why it is so easy to forget which names are associated to which particular case.

And – surprise! – the proof of general Stokes theorem is trivial. There is a nice short (but very dense) book “Calculus on manifolds” by M. Spivak devoted to this theorem.  I recommend reading its preface to anybody interested in one way or another in mathematics. For mathematicians to know its content is a must. In the preface M. Spivak explains what happened. All the proofs are now trivial because all the difficulties were transferred into definitions. In fact, this Stokes theorem deals with integration not of functions, but of the so-called differential form, sometimes called also exterior forms. And this is a difficult notion. It requires very deep insights to discover it, and it still difficult to learn it. In the simplest situation, where nothing depends on any variables, it was discovered by H. Grassmann in the middle of 19^th century. The discoveries of this German school teacher are so important that the American Mathematical Society published an English translation of one of his books few years ago. It is still quite a mystery how he arrived at his definitions. With the benefits of hindsight, one may say that he was working on geometric problems, but was guided by the abstract algebra (which did not exist till 1930). Later on his ideas were generalized in order to allow everything to depend on some variables (probably, E. Cartan was the main contributor here). In 1930ies the general Stokes theorem was well known to experts. Nowadays, it is possible to teach it to bright undergraduates in any decent US university, but there are not enough of such bright undergraduates. It should be in some of the required course for graduate students, but one can get a Ph.D. without being ever exposed to it.

To sum up, the modern Stokes theorem requires learning a new and not very well motivated (apparently, even the Grassmann did not really understood why he introduced his exterior forms) notion of differential forms and their basic properties. Then you have a theorem from which all 19^th century results follow immediately, and which is infinitely more general than all of them together. At the same time it has the same form for any number of variables and has a trivial proof (and the proofs of the needed theorems about differential forms are also trivial). There are no tricks in the proofs; they are very natural and straightforward. All difficulties were moved into definitions.

Now, what is hard and what is difficult? New definitions of such importance are infinitely rarer than new theorems. Most mathematicians of even the highest caliber did not discover any such definition. Only a minority of Abel prize winner discovered anything comparable, and it is still too early to judge if their definitions are really important. So, discovering new concepts is hard and rare. Then there is a common prejudice against anything new (I am amazed that it took more than 15 years to convince public to buy HD TV sets, despite they are better in the most obvious sense), and there is a real difficulties in learning these new notions. For example, there is a notion of a derived category (it comes from the Grothendieck school), which most of mathematicians consider as difficult and hardly relevant. All proofs in this theory are utterly trivial.

Final note: the new conceptual proofs are often longer than the classical proofs even of the same results. This is because in the classical mathematics various tricks leading to shortcut through an argument are highly valued, and anything artificial is not valued at all in the conceptual mathematics.

Next post: The Hungarian Combinatorics from an Advanced Standpoint.

Reply to Timothy Gowers

Previous post: Happy New Year!


Here is a reply to a comment by T. Gowers about my post My affair with Szemerédi-Gowers mathematics.

I agree that we have no way to know what will happen with combinatorics or any other branch of mathematics. From my point of view, your “intermediate possibility” (namely, developing some artificial way of conceptualization) does not qualify as a way to make it “conceptual” (actually, a proper conceptualization cannot be artificial essentially by the definition) and is not an attractive perspective at all. By the way, the use of algebraic geometry as a reference point in this discussion is purely accidental. A lot of other branches of mathematics are conceptual, and in every branch there are more conceptual and less conceptual subbranches. As is well known, even Deligne’s completion of proof of Weil’s conjectures was not conceptual enough for Grothendick.

Let me clarify how I understand the term “conceptual”. A theory is conceptual if most of the difficulties were moved from proofs to definitions (i.e. to concepts), or they are there from the very beginning (which may happen only inside of an already conceptual theory). The definitions may be difficult to digest at the first encounter, but the proofs are straightforward. A very good and elementary example is provided by the modern form of the Stokes theorem. In 19th century we had the fundamental theorem of calculus and 3 theorems, respectively due to Gauss-Ostrogradsky, Green, and Stokes, dealing with more complicated integrals. Now we have only one theorem, usually called Stokes theorem, valid for all dimensions. After all definitions are put in place, its proof is trivial. M. Spivak nicely explains this in the preface to his classics, “Calculus on manifolds”. (I would like to note in parentheses that if the algebraic concepts are chosen more carefully than in his book, then the whole theory would be noticeably simpler and the definitions would be easier to digest. Unfortunately, such approaches did not found their way into the textbooks yet.) So, in this case the conceptualization leads to trivial proofs and much more general results. Moreover, its opens the way to further developments: the de Rham cohomology turns into the most natural next thing to study.

I think that for every branch of mathematics and every theory such a conceptualization eventually turns into a necessity: without it the subject grows into a huge body of interrelated and cross-referenced results and eventually falls apart into many to a big extent isolated problems. I even suspect that your desire to have a sort of at least semi-intelligent version of MathSciNet (if I remember correctly, you wrote about this in your GAFA 2000 paper) was largely motivated by the difficulty to work in such a field.

This naturally leads us to one more scenario (the 3rd one, if we lump together your “intermediate” scenario with the failure to develop a conceptual framework) for a not conceptualized theory: it will die slowly. This happens from time to time: a lot of branches of analysis which flourished at the beginning of 20th century are forgotten by now. There is even a recent example involving a quintessentially conceptual part of mathematics and the first Abel prize winner, J.-P. Serre. As H. Weyl stressed in his address to 1954 Congress, the Fields medal was awarded to Serre for his spectacular work (his thesis) on spectral sequences and their applications to the homotopy groups, especially to the homotopy groups of spheres (the problem of computing these groups was at the center of attention of leading topologists for about 15 years without any serious successes). Serre did not push his method to its limits; he already started to move to first complex manifolds, then algebraic geometry, and eventually to the algebraic number theory. Others did, and this quickly resulted in a highly chaotic collection of computations with the Leray-Serre spectral sequences plus some elementary consideration. Assuming the main properties of these spectral sequences (which can be used without any real understanding of spectral sequences), the theory lacked any conceptual framework. Serre lost interest even in the results, not just in proofs. This theory is long dead. The surviving part is based on further conceptual developments: the Adams spectral sequence, then the Adams-Novikov spectral sequence. This line of development is alive and well till now.

Another example of a dead theory is the Euclid geometry.

In view of all this, it seems that there are only the following options for a mathematical theory or a branch of mathematics: to continuously develop proper conceptualizations or to die and have its results relegated to the books for gifted students (undergraduate students in the modern US, high school students in some other places and times).


Next post: Reply to JSE.