ICM2014 — Barak, Guralnick, Brown

Here’s a little puzzle to get this post started. Of the fourteen 21st-century Fields medallists (if you count Perelman), seven — Lafforgue, Voevodsky, Tao, Werner, Smirnov, Avila and Mirzakhani — have something interesting in common that the others lack. What is this property?

That’s a fairly easy question, so let’s follow it up with another one: how surprised should we be about this? Is there unconscious bias towards mathematicians with this property? Of this year’s 21 plenary lecturers, the only one with the property was Mirzakhani, and out of the 20 plenary lecturers in 2010, the only one with the property was Avila. What is going on?

On to more serious matters. After Candès’s lecture I had a solitary lunch in the subterranean mall (Korean food of some description, but I’ve forgotten exactly what) and went to hear Martin Hairer deliver his Fields medal lecture, which I’m not going to report on because I don’t have much more to say about his work than I’ve already said.

By and large, the organization of the congress was notably good — for example, I almost never had to queue for anything, and never for any length of time — but there was a little lapse this afternoon, in that Hairer’s lecture was scheduled to finish at 3pm, exactly the time that the afternoon’s parallel sessions started. In some places that might have been OK, but not in the vast COEX Seoul conference centre. I had to get from the main hall to a room at the other end of the centre where theoretical computer science talks were taking place, which was probably about as far as walking from my house in Cambridge to the railway station. (OK, I live close to the station, but even so.)

Inevitably, therefore, I arrived late to Boaz Barak’s talk, but he welcomed me, and a few others in my position, with the reassuring words that everything he had said up to now was bullshit and we didn’t need to worry about it. (He was quoting a juggler he had seen in Washington Square.)

I always like it when little themes recur at ICMs in different contexts. I’ve already mentioned the theme of looking at big spaces of objects in order to understand typical objects. Another one I mentioned when describing Candès’s lecture: that one should not necessarily be afraid of NP-complete problems, a theme which was present in Barak’s talk as well. I’m particularly fond of it because I’ve spent a lot of time in the last few years thinking about the well-known NP-complete problem where the input is a mathematical statement and the task (in the decision version) is to say whether there is a proof of that statement of length at most n — in some appropriate formal system. The fact that this problem is NP-complete does not deter mathematicians from spending their lives solving instances of it. What explains this apparent success? I dream that there might be a very nice answer to this question, rather than just a hand-wavy one that says that the instances studied by mathematicians are far from general.

Barak was talking about something a little different, however. He too has a dream, which is to obtain a very precise understanding of why certain problems are hard (in the complexity sense of not being soluble with efficient algorithms) and others easy. He is not satisfied with mere lists of easy and hard problems, with algorithms for the former and reductions to NP-complete or other “known hard” problems for the latter. He wants a theory that will say which problems are hard and which easy, or at least do that for large classes of problems. And the way he wants to do it is to find “meta-algorithms” — which roughly speaking means very general algorithmic approaches with the property that if they work then the problem is easy and if they fail then it’s hard.

Why is there the slightest reason to think that that can be done? Isn’t there a wide variety of algorithms, each of which requires a lot of ingenuity to find? If one approach fails, might there not be some clever alternative approach that nobody had thought of?

These are all perfectly reasonable objections, but the message, or at least a message, of Barak’s talk is that it is not completely outlandish to think that it really is the case that there is what one might call a “best possible” meta-algorithm, in the sense that if it fails, then nothing else can succeed. Again, I stress that this would be for large and interesting classes of algorithm problems (e.g. certain optimization problems) and not for every single describable Boolean function. One reason to hold out hope is that if you delve a little more deeply into the algorithms we know about, you find that actually many of them are based on just a few ideas, such as linear and semidefinite programming, solving simultaneous linear equations, and so on. Of course, that could just reflect our lack of imagination, but it could be an indication that something deeper is going on.

Another reason for optimism is that he has a candidate: the sum-of-squares algorithm. This is connected with Hilbert’s 17th problem, which asked whether every multivariate polynomial that takes only non-negative values can be written as a sum of squares of rational functions. (It turns out that they can’t necessarily be written as a sum of squares of polynomials: a counterexample is z^6+x^4y^2+x^2y^4-3x^2y^2z^2.) An interesting algorithmic problem is to write a polynomial as a sum of squares when it can be so written. One of the reasons this problem interests Barak is that many other problems can be reduced to it. Another, which I don’t properly understand but I think would understand if I watched his talk again (it is here, by the way), is that if the unique games conjecture is false, and recall that it too is sort of saying that a certain algorithm is best possible, then the sum-of-squares algorithm is waiting in the wings to take over as the new candidate that will do the job.

An unfortunate aspect of going to Barak’s talk was that I missed Harald Helfgott’s. However, the sacrifice was rewarded, and I can always watch Harald on Youtube.

After another longish walk, but with a non-zero amount of time for it, I arrived at my next talk of the afternoon, given by Bob Guralnick. This was another very nice talk, just what an ICM invited lecture should be like. (By that I mean that it should be aimed principally at non-experts, while at the same time conveying what has been going on recently in the field. In other words, it should be more of a colloquium style talk than a research seminar.)

Guralnick’s title was Applications of the Classification of Finite Simple Groups. One thing he did was talk about the theorem itself, how a proof was announced in 1983 but not actually completed for another twenty years, and how there are now — or will be soon — “second-generation” proofs that are shorter, though still long, and use new ideas. He also mentioned a few statements that can be proved with the classification theorem and are seemingly completely out of reach without it. Here are a few of them.

1. Every finite simple group is generated by two elements.

2. The probability that a random pair of elements generates a finite simple group tends to 1 as the size of the group tends to infinity.

3. For every non-identity element x of a finite simple group, there exists an element y such that x and y generate the group.

4. For every finite simple group there exist conjugacy classes C and D such that for every c\in C and every d\in D the elements c and d generate the group.

Why does the classification of finite simple groups help with these problems? Because it means that instead of having to give an abstract proof that somehow uses the condition of having no proper normal subgroups, you have the option of doing a proof that involves calculations in concrete groups. Because the list of (families of) groups you have to consider is finite, this is a feasible approach. Actually, it’s not just that there are only finitely many families, but also that the families themselves are very nice, especially the various families of Lie type. As far as I can tell from the relevant Wikipedia article, there isn’t a formal definition of “group of Lie type”, but basically it means a group that’s like a Lie group but defined over a finite field instead of over $\mathbb{R}$ or $\mathbb{C}$. So things like PSL$(2,q)$ are finite simple groups of Lie type.

Just as the geometrization theorem didn’t kill off research in 3-manifolds, the classification of finite simple groups didn’t kill off group theory, even though in the past many mathematicians have thought that it would. It’s easy to see how that perception might have arisen: the project of classifying finite simple groups became such a major focus for group theorists that once it was done, a huge chunk of what they were engaged in was no longer available.

So what’s left? One answer, one might imagine, is that not all groups are simple. That is not a completely satisfactory answer, because groups can be put together from simple groups in such a way that for many problems it is enough to solve them just for simple groups (just as in number theory one can often prove a result for primes and prove that the product of two numbers that satisfy the result also satisfies the result). But it is part of the answer. For example p-groups (that is, groups of prime power order) are built out of copies of a cyclic group of prime order, but that doesn’t begin to answer all the questions people have about p-groups.

Another answer, which is closer to the reason that 3-manifold theory survived Perelman, is that proving results even for specific families of groups is often far from easy. For example, have a go at proving that a random pair of (equivalence classes of) matrices generates PSL$(2,q)$ with high probability when q is large: it’s a genuine theorem rather than simply a verification.

I want to mention a very nice result that I think is due to Guralnick and his co-authors, though he didn’t quite explicitly say so. Let f\in\mathbb{F}_q[x] be a polynomial of degree n, with n coprime to q. Then for every a, either f is bijective on the field \mathbb{F}_{q^a} or the set of values it takes has size at most (5/6)q^a+O(q^{a/2}).

What’s so nice about that? Well, the result is interesting, but even more interesting (at least to me) is the fact that the proof involved the classification of finite simple groups, and Guralnick described it (or more accurately, a different result just before it but I think the same remark applies) as untouchable without CFSG, even though the statement is about polynomials rather than groups.

Here is the video of Guralnick’s lecture.

The third invited lecture I went to was given by Francis Brown. Although I was expecting to understand very little, I wanted to go to it out of curiosity, because I knew Francis Brown when he was an undergraduate at Trinity — I think I taught him once or twice. After leaving Trinity he went to France, where he had been ever since, until very recently taking up a (highly prestigious) professorial fellowship at All Soul’s in Oxford. It was natural for him to go to France, because his mother is French and he is bilingual — another aspect that interests me since two of my children are in the same position. I heard nothing of him for a long time, but then in the last few years he suddenly popped up again as the person who has proved some important results concerning motivic zeta functions.

The word “motivic” scares me, and I’m not going to try to say what it means, because I can’t. I first heard of motives about twenty years ago, when the message I got was that they were objects that people studied even though they didn’t know how to define them. That may be a caricature, but my best guess as to the correct story is that even though people don’t know the right definition, they do know what properties this definition should have. In other words, there is a highly desirable theory that would do lots of nice things, if only one could find the objects that got you started.

However, what Brown was doing appeared not to be based on layers of conjecture, so I suppose it must be that “motivic versions” of certain objects have been shown to exist.

This was a talk in which I did not take notes. To do a decent job describing it, I’d need to watch it again, but rather than do that, I’ll just describe the traces it left in my memory.

One was that he mentioned the famous problem of the irrationality of \zeta(n) for odd n\geq 5, and more generally the problem of whether the vector space over the rationals generated by \zeta(3),\zeta(5),\dots,\zeta(2n+1) has dimension n. (It has been shown by Ball and Rivoal to have dimension that tends to infinity with n, which was a major result when it was proved.)

Another was that he defined multiple zeta values, which are zeta-like functions of more than one integer variable, which come up naturally when one takes two zeta values, multiplies them together, and expands out the result. They were defined by Euler.

He also talked about periods, a very interesting concept defined (I think for the first time) by Kontsevich and Zagier. I highly recommend looking at their paper, available here in preprint form. At least the beginning of it is accessible to non-experts, and contains a very interesting open problem. Roughly speaking, a period is anything you can define using reasonably nice integrals. For example, \pi is a period because it is the area of the unit disc, which has a nice polynomial equation x^2+y^2\leq 1. The nice problem is to prove that an explicit number is not a period. There are only countably many periods, so such numbers exist in abundance. If you want a specific number to try, then you can begin with e. Best of luck.

While discussing what motivic zeta values are, he said that there were two approaches one could use, one involving Betti numbers and the other involving de Rham cohomology. He preferred the de Rham approach. “Betti” and “de Rham” became a sort of chorus throughout the talk, and even now I have ringing in my head phrases like “\lambda-Betti or \lambda-de Rham”.

If I understood correctly, linear dependences between motivic zeta values (which are much fancier objects that still depend on tuples of integers) imply the corresponding dependences between standard zeta values. (I’m talking about both single and multiple zeta values here.) That’s not much help if you are trying to prove independence of standard zeta values, but it does do two things for you. One is that it provides a closely related context in which the world seems to be a tidier place. As I understand it, all the conjectures one wants to be true for standard zeta values are true for their motivic cousins. But it has also enabled Brown to discover unexpected dependences between standard zeta values: for instance every multiple zeta value is a linear combination of multiple zeta values where every argument is 2 or 3. (I suppose multiple must mean “genuinely multiple” here.) Actually, looking very briefly at the relevant part of the talk, which is round about the 27th minute, I see that this was proving something called the Hoffman conjecture, so perhaps it is wrong to call it unexpected. But it is still a very interesting result, given that the proof was highly non-trivial and went via motivic zeta values.

My remaining memory trace is that the things Brown was talking about were related to a lot of other important parts of mathematics, and even theoretical physics. I’d love to understand this kind of thing better.

So although a lot of this talk (which is here) went over my head, enough of it didn’t that my attention was engaged throughout. Given the type of material, that was far from obviously going to be the case, so this was another very good talk, to round off a pretty amazing day.

About these ads

45 Responses to “ICM2014 — Barak, Guralnick, Brown”

  1. Tom Says:

    Is the property explained anywhere? It’s not easy for me …

    • gowers Says:

      That’s interesting — maybe it felt easier to me because I knew the answer. No I didn’t explain it anywhere, because I wanted to give people a chance to solve it for themselves.

    • Roenardi Says:

      +1

    • Sarah Says:

      Hint: If it helps, it looks like the only Fields Medalists from the 20th century who have the property are Kodaira, Smale, and Hironaka, skimming through Wikipedia (assuming I’ve got the answer correct, that is, and I may have missed someone even then).

    • DS Says:

      Hint: If there were very few people in the world, the necessary condition for the property would not arise

  2. BQ Says:

    In my (mathematics) department, 8 out of 142 people have this property, so it does look fairly unusual.

  3. FZ Says:

    Galileo, Ampère, Green, Helmholtz,…

  4. Toma Says:

    Here’s a hint: try to think that this “title” they take together touches too tinily their theories.

    • BQ Says:

      Very nice zero-knowledge proof! Even the number of words used in the hint is the same as the number of Fields medalists in this century.

  5. kuessner Says:

    The probability for this to happen should be something like 3.8%. (Well, probably somewhat larger, as things are not equidistributed.)

  6. Veky Says:

    After a day of thinking, I still can’t see it. Can you say does the property depend on a specific individual (like e.g. “having an Erdös number”), or is it invariant to renaming of individuals?

  7. domotorp Says:

    My wife could have acquired this property but she chose not to.

  8. Hany El-Hosseiny Says:

    It’s a proper property.

  9. anon Says:

    Some find the property interesting; others don’t, and hence have trouble guessing it.

    • Anonymous Says:

      Agreed. I spent far too long trying to get it because it was described as “something interesting.”

    • gowers Says:

      Apologies for that. I meant interesting in the sense of simple to describe and with fairly small probability.

    • Mike Shulman Says:

      The question “Is there unconscious bias towards mathematicians with this property?” also misled me, because it suggested that the property was something that it would be important to ask that question about seriously.

      I wonder whether the property of “finding this property interesting” is correlated with other things. (-:

  10. BQ Says:

    What is the chance of a mistake in the classification of finite simple groups? If you solve P vs. NP problem using it, will it really count?

    • gowers Says:

      I’m not an expert, but my impression is that the chances of a mistake are pretty high, but the chances of a serious mistake that people can’t see how to correct are very small. So I’d say that it’s right to be confident in the truth of the theorem and to regard it as established.

    • QA Says:

      “… the chances of a mistake are pretty high, but the chances of a serious mistake that people can’t see how to correct are very small.”

      An amusingly paradoxical statement! (Why should a corrected proof prove the same theorem?) It reminds me of an anecdote told by Mostow in his memorial talk for Harish-Chandra, relating to a course of lectures by Chevalley at Princeton that they had attended in their youth:

      . . . The lectures were consistently polished with all details nicely in place, but on that particular day, Chevalley got stuck. Those of you who are familiar with Chevalley’s uncompromisingly rigorous style may be amused to hear how Chevalley coped: he crouched against the blackboard, drew a diagram which he covered with his body, stared at it, finally erased the figure, and announced, “My assertion is certainly correct, but I don’t see at the moment how to prove it,” and he deferred the point for the following lecture. On our way back to the Institute, Harish declared with genuine puzzlement, “How can one know that a mathematical statement is true without knowing how to prove it?”

  11. Roy Abrams Says:

    Who are seven people who have not been in my kitchen?

  12. graboluk Says:

    took me two days; at least if i miss any important deadlines I have an excellent excuse

  13. Tony Pay Says:

    The ‘property’ reminded me of playing the game of ‘Harry Hooper’, in which Harry likes coffee but not tea; beer but not wine; Littlewood but not Hardy; and, Harry Hooper – but not himself:-)

  14. Anonymous Says:

    Are there any Chinese-born mathematicians with the property?

  15. Anonymous Says:

    Bbhbhhhjhjjjjjjkjjkkkkjjkjkjkikijjbjkljkkkkkkkkkkjjjkkojjjkjnnkkojjjjiiiiijjoimojjkpjjkmlpjjkiujj

  16. VK Says:

    To those who have figured out the connection: can you please tell the rest of us what it is?

  17. Roy Abrams Says:

    Sufferin Succotash, this ought to be a Clay Problem.

  18. Greg Marks Says:

    If you’re familiar with the classification of division algebras over number fields whose orders are the squares of their degrees, then you know a striking instance of the property.

  19. Jeff Jacobs Says:

    Jumping Jehosaphat, that was tough!

  20. Anonymous Says:

    The last person executed in Australia.

  21. mathlogscienceblogs Says:

    More precisely, the probability for this to happen for a single person is about 6,55%, taking into account that things are not equidistributed. The probability that a large group has this property for at least half of its members is about 1 to 10 billions. (Though one may debate whether 14 makes a large enough group for this computation to be correct.) Some computations (sorry, in German) at http://scienceblogs.de/mathlog/2014/08/30/der-fieldsmedaillenbetrug/

    • gowers Says:

      What you say about large groups is not correct. If the probability of an event is p, and p is substantially less than 1/2, then the probability that out of 2n trials, the event happens at least n times tends to zero (rapidly) as n tends to infinity. So to get a fixed answer like one in a billion, you need a fixed n.

      I’ve just checked using this binomial distribution calculator that if the probability is 6.55% and you look for the probability of exactly 7 successes out of 14 (which gives a good approximation to the probability of at least 7 successes), then you get about 1 in 10,000. I think the 6.55% is probably a slight underestimate as well. If you go for 10% then it’s more like 1 in 6000.

  22. Jack Says:

    The puzzle has a really Silly Solution

  23. GrazziDad Says:

    It is related to Cantor’s diagonalization, kinda sorta.

  24. John Sidles Says:

    Prof. Gowers’ observations beginning with the sentence “I always like it when little themes recur at ICMs …” illuminate (as it seems to me) several considerations that are of central significance to the STEAM community; they are quoted extensively on Scott Aaronson’s fine weblog, in a comment under this week’s topic Microsoft SVC.

    Thank you Prof. Gowers, for these well-considered, timely observations.

  25. ashwingokhale95 Says:

    Holy microns! I couldn’t figure out the property they shared.Can anyone provide an answer?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,598 other followers

%d bloggers like this: