## The trouble with billionaires

Cathy blogs today about the enthusiasm for billionaires displayed at the AMS public face of math panel, and her misgivings about it.  Cathy points out that, while gifts from big donors obviously accomplish real, useful, worthwhile goals for mathematics, they have a way of crowding out the public support we might otherwise have gotten, and sapping our will to fight for that support.

I think there’s an even deeper problem.  When we’re talking about putting up buildings or paying people’s salaries, we’re talking about things that require many millions of dollars, and asking:  who’s going to pay for them?  It’s not crazy that the answer “a rich person” is one of the things that comes to mind.

But when we talk about improving the public image of mathematics, we are not talking about something that automatically costs lots of money.  We’re talking about something that we can do on social media, something we can do in the newspaper, something we can — and frankly, should — do in the classroom.  Cathy describes the conversation as centering on “How can we get someone to hire a high-priced PR agent for mathematics?”  That means that the billionaire solution isn’t just crowding out other sources of money, it’s crowding out the very idea that there are ways to solve problems besides spending money.

Tagged

## The existence of designs

The big news in combinatorics is this new preprint by Peter Keevash, which proves the existence of Steiner systems, or more generally combinatorial designs, for essentially every system of parameters where the existence of such a design isn’t ruled out on divisibility grounds.  Remarkable!

I’m not going to say anything about this paper except to point out that it has even more in it than is contained in the top-billed theorem; the paper rests on the probabilistic method, which in this case means, more or less, that Keevash shows that you can choose a “partial combinatorial design” in an essentially random way, and with very high probability it will still be “close enough” that by very careful modifications (or, as Keevash says, “various applications of the nibble” — I love the names combinatorists give their techniques) you can get all the way to the desired combinatorial design.

This kind of argument is very robust!  For instance, Keevash gets the following result, which in a way I find just as handsome as the result on designs.  Take a random graph on n vertices — that is, each edge is present with probability 1/2, all edges independent.  Does that graph have a decomposition into disjoint triangles?  Well, probably not, right?  Because a union of triangles has to have even degree at each vertex, while the random graph is going to have n/2 of its vertices with odd degree. (This is the kind of divisibility obstruction I mentioned in the first paragraph.)  In fact, this divisibility argument shows that if the graph can be decomposed as a union of triangles with M extra edges, M has to be at least n/4 with high probability, since that’s how many edges you would need just to dispose of the odd-degree vertices.  And what Keevash’s theorem shows is there really is (with high probability) a union of disjoint triangles that leaves only (1+o(1))(n/4) edges of the random graph uncovered!

More details elsewhere from Vuhavan and Gil Kalai.

## What do Aner Shalev and Nike Vatsal have in common?

My mother-in-law was toting around a book of short stories translated from the Hebrew and I saw a familiar name on the front:  Aner Shalev.  Not the same Aner Shalev as the group theorist I know, surely — but no, I checked, and it’s him!  Good story, too, actually not a story but an excerpt from his 2004 novel Dark Matter (or I guess I should say Hachomer Haafel since it doesn’t seem to exist in English.)  It was good!

Sometime last year I was in a coffee shop in Berkeley doing math with Tom Church and on the bookshelf there was an old issue of Story, and in the table of contents I found Vinayak Vatsal.  Not the same Vinayak Vatsal as the number theorist I know, surely, but….  yep, it was him.  I only got to read the beginning of Nike’s story because I was supposed to be doing math, but that one was good too, what I read.

How many mathematicians are secretly placing stories in literary magazines, I’d like to know?

Tagged ,

## Proof school: it’s not just for math kids anymore

A while back I complained, I hope good-naturedly, about Proof School’s self-description as “a school just for math kids.”  A little Ravi told me that the website has since been revamped, and the new version, with tagline “For kids who love math,” is much more to my liking.  The phrase “math kids” is still around, but I think it presents them (us?) as less of a separate species, and more of an tribe bound by common culture:

By “math kids” we mean children who are truly talented and passionate about math. We say we’re looking for students who are internally pulled by math, not externally pushed into it. Of course, math kids have many interests beyond math or computer science–it’s more just a term of convenience and endearment, really–not an absolute. Almost a nickname. If you know any math kids, you know what we mean. Maybe you were one, once, too.

I’m OK with this!

I will say, though, that 6 occurrences of the words “passion” or “passionate” in the FAQ is too many.

Tagged

## An incidence conjecture of Bourgain over fields of positive characteristic (with Hablicsek)

Marci Hablicsek (a finishing Ph.D. student at UW) and I recently posted a new preprint, “An incidence conjecture of Bourgain over fields of finite characteristic.”

The theme of the paper is a beautiful theorem of Larry Guth and Nets Katz, one of the early successes of Dvir’s “polynomial method.”  They proved a conjecture of Bourgain:

Given a set S of points in R^3, and a set of N^2 lines such that

• No more than N lines are contained in any plane;
• Each line contains at least N points of S;

then S has at least cN^3 points.

In other words, the only way for a big family of lines to have lots of multiple intersections is for all those lines to be contained in a plane.  (In the worst case where all the lines are in a plane, the incidences between points and lines are governed by the Szemeredi-Trotter theorem.)

I saw Nets speak about this in Wisconsin, and I was puzzled by the fact that the theorem only applied to fields of characteristic 0, when the proof was entirely algebraic.  But you know the proof must fail somehow in characteristic p, because the statement isn’t true in characteristic p.  For example, over the field k with p^2 elements, one can check that the Heisenberg surface

$X: x - x^p + yz^p - zy^p = 0$

has a set of p^4 lines, no more than p lying on any plane, and such that each line contains at least p^2 elements of X(k).  If the Guth-Katz theorem were true over k, we could take N = p^2 and conclude that |X(k)| is at least p^6.  But in fact, it’s around p^5.

It turns out that there is one little nugget in the proof of Guth-Katz which is not purely algebraic.  Namely:  they show that a lot of the lines are contained in some surface S with the following property;  at every smooth point s of S, the tangent plane to S at s intersects S with multiplicity greater than 2.  They express this in the form of an assertion that a certain curvature form vanishes everywhere.  In characteristic 0, this implies that S is a plane.  But not so in characteristic p!  (As always, the fundamental issue is that a function in characteristic p can have zero derivative without being constant — viz., x^p.)  All of us who did the problems in Hartshorne know about the smooth plane curve over F_3 with every point an inflection point.  Well, there are surfaces like that too (the Heisenberg surface is one such) and the point of the new paper is to deal with them.  In fact, we show that the Guth-Katz theorem is true word for word as long as you prevent lines not only from piling up in planes but also from piling up in these “flexy” surfaces.

It turns out that any such surface must have degree at least p, and this enables us to show that the Guth-Katz theorem is actually true, word for word, over the prime field F_p.

If you like, you can think of this as a strengthening of Dvir’s theorem for the case of F_p^3.  Dvir proves that a set of p^2 lines with no two lines in the same direction fills up a positive-density subset of the whole space.  What we prove is that the p^2 lines don’t have to point in distinct directions; it is enough to impose the weaker condition that no more than p of them lie in any plane; this already implies that the union of the lines has positive density.  Again, this strengthening doesn’t hold for larger finite fields, thanks to the Heisenberg surface and its variants.

This is rather satisfying, in that there are other situations in this area (e.g. sum-product problems) where there are qualitatively different bounds depending on whether the field k in question has nontrivial subfields or not.  But it is hard to see how a purely algebraic argument can “see the difference” between F_p and F_{p^2}.  The argument in this paper shows there’s at least one way this can happen.

Satisfying, also, because it represents an unexpected application for some funky characteristic-p algebraic geometry!  I have certainly never needed to remember that particular Hartshorne problem in my life up to now.

## “Homological stability for Hurwitz spaces… II” temporarily withdrawn

Akshay Venkatesh, Craig Westerland and I have temporarily withdrawn our preprint “Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields, II,” because there is a gap in the paper which we do not, at present, see how to remove.  There is no reason to think any of the theorems stated in the paper aren’t true, but because some of them are not proved at this time, we’ve pulled back the whole paper until we finish preparing a revised version consisting just of the material that does in fact follow from the arguments in their current form, together with some patches we’ve come up with.   We are extremely grateful to Oscar Randall-Williams for alerting us to the problem in the paper.

I’ll explain where the gap is below the fold, and which parts of the paper are still OK, but first a few thoughts about the issue of mistakes in mathematics.  Of course we owe a lot of people apologies.  All three of us have given talks in which we told people we had a proof of (a certain version of) the Cohen-Lenstra conjecture over F_q(t).  But we do not.  I know several people who had work in progress using this theorem, and so of course this development disrupts what they were doing, and I’ve kept those people up-to-date with the situation of the paper.  If there are others planning immediately to use the result, I hope this post will help draw their attention to the fact that they need to go back to treating this assertion as a conjecture.

One thing I found, when I talked to colleagues about this situation, is that it’s more common than I thought.  Lots of people have screwed up and said things in public or written things in papers they later realized were wrong.  One senior colleague told me an amazing story — he was in the shower one day when he suddenly realized that a paper he’d published in the Annals four years previously, a result he hadn’t even thought about in months, was wrong; there was an induction argument starting from a false base case!  Fortunately, after some work, he was able to construct a repaired argument getting to the same results, which he published as a separate paper.

Naturally nobody likes to talk about their mistakes, and so it’s easy to get the impression that this kind of error is very rare.  But I’ve learned that it’s not so rare.  And I’m going to try to talk about my own error more than I would in my heart prefer to, because I think we have to face the fact that mathematicians are human, and it’s not safe to be certain something is true because we found it on the arXiv, or even in the Annals.

In a way, what happened with our paper is exactly what people predicted would happen once we lost our inhibitions about treating unrefereed preprints as papers.  We wrote the paper, we made it public, and people cited it before it was refereed, and it was wrong.

But what would have happened in a pre-arXiv world?  The mistake was pretty subtle, resting crucially on the relation between this paper and our previous one.  Would the referee have caught it, when we didn’t?  I’m not so sure.  And if the paper hadn’t been openly shared before publication, Oscar wouldn’t have seen it.  It might well have been published in its incorrect form.  On balance, I’d guess wide distribution on arXiv makes errors less likely to propagate through mathematics, not more.

Sociology of mathematics ends here; those who want to know more about the mistake, keep reading past the fold.

## Is online education good or bad for equality?

It seems like it would obviously be good — now kids who don’t have money and don’t live near universities have, in principle, access to much of the world’s knowledge as long as they have a cheap computer and an internet connection.

But in math, I’ve heard anecdotally that this isn’t really happening.  I thought we were going to see an influx of mathematical talent, smart kids from Mississippi who couldn’t get any math past calculus from their peers, their local high school, or the public library, but who trained themselves hardcore on Art of Problem Solving or Mathematics Stack Exchange.  But I don’t think this is happening so much.  (Correct me if I’m wrong about this!)

Tagged

## My other daughter is a girl

I like Cathy’s take on this famous probability puzzle.  Why does this problem give one’s intuition such a vicious noogie?

It is relevant that the two questions below have two different answers.

• I have two children.  One of my children is a girl who was born on Friday.  What’s the probability I have two girls?
• I have two children.  One of my children is a girl.  Before you came in, I selected a daughter at random from the set of all my daughters, and this daughter was born on Friday.  What’s the probability I have two girls?

## Random simplicial complexes

This is a post about Matt Kahle’s cool paper “Sharp vanishing thresholds for cohomology of random flag complexes,” which has just been accepted in the Annals.

The simplest way to make a random graph is to start with n vertices and then, for each pair (i,j) independently, put an edge between vertices i and j with probability p.  That’s called the Erdös-Rényi graph G(n,p), after the two people who first really dug into its properties.  What’s famously true about Erdös-Rényi graphs is that there’s a sharp threshold for connectness.  Imagine n being some fixed large number and p varying from 0 to 1 along a slider.  When p is very small relative to n, G(n,p) is very likely to be disconnected; in fact, if

$p = (0.9999) \frac{\log n}{n}$

there is very likely to be an isolated vertex, which makes G(n,p) disconnected all by itself.

On the other hand, if

$p = (1.0001) \frac{\log n}{n}$

then G(n,p) is almost surely connected!  In other words, the probability of connectedness “snaps” from 0 to 1 as you cross the barrier p = (log n)/n.  Of course, there are lots of other interesting questions you can ask — what exactly happens very near the “phase transition”?  For p < (log n)/n, what do the components look like?  (Answer:  for some range of p there is, with probability 1, a single “giant component” much larger than all others.  For instance, when p = 1/n the giant component has size around n^{2/3}.)

I think it’s safe to say that the Erdös-Rényi graph is the single most-studied object in probabilistic combinatorics.

But Kahle asked a very interesting question about it that was completely new to me.  Namely:  what if you consider the flag complex X(n,p), a simplicial complex whose k-simplices are precisely the k-cliques in G(n,p)?  X(n,p) is connected precisely when G(n,p) is, so there’s nothing new to say from that point of view.  But, unlike the graph, the complex has lots of interesting higher homology groups!  The connectedness threshold says that dim H_0(X(n,p)) is 1 above some sharp threshold and larger below it.  What Kahle proves is that a similar threshold exists for all the homology.  Namely, for each k there’s a range (bounded approximately by $n^{1/k}$ and $(log n / n)^{1/(k+1)}$) such that H_k(X(n,p)) vanishes when p is outside the range, but not when p is inside the range!  So there are two phase transitions; first, H^k appears, then it disappears.  (If I understand correctly, there’s a narrow window where two consecutive Betti numbers are nonzero, but most of the time there’s only one nonzero Betti number.)  Here’s a graph showing the appearance and disappearance of Betti in different ranges of p:

This kind of “higher Erdös-Rényi theorem” is, to me, quite dramatic and unexpected.  (One consequence that I like a lot; if you condition on the complex having dimension d, i.e. d being the size of the largest clique in G(n,p), then with probability 1 the homology of the complex is supported in middle degree, just as you might want!)  And there’s other stuff there too — like a threshold for the fundamental group of X(n,p) to have property T.

For yet more about this area, see Kahle’s recent survey on the topology of random simplicial complexes.  The probability that a random graph has a spectral gap, the distribution of Betti numbers of X(n,p) in the regime where they’re nonzero, the behavior of torsion, etc., etc……

## Equidistribution with moving targets

Tom Church, Benson Farb and I have a new paper about FI-modules on the arXiv.  This one concerns a family of questions we were thinking about at the very beginning of the project, and which we now have enough tools to talk about properly.

The paper is in some measure expository —  many or perhaps most of the results we talk about can be proved by other means.  But setting things up in FI-module language expresses everything in a nice uniform way.

Here’s one way to think about what’s going on.   Suppose you let P(q,n) be the probability that a monic squarefree polynomial over F_q is irreducible.  Now you can work out a closed formula for this number, but I want you to strike that from your mind for a second, because that’s not what I want to think about.

Each squarefree polynomial f of degree n has a partition of n attached to it; namely, the one that breaks n up into the degrees of the irreducible factors of q.  Another view:  if we let Y_n be the space of ordered n-tuples of distinct points in A^1 (i.e. the complement of the fat diagonals in A^n) then Y_n carries a natural action of S_n, and the quotient, which we’ll call X_n, is nothing more than the space of monic squarefree polynomials:  the map is

(z_1, .. z_n) -> (x-z_1)…(x-z_n).

So every monic squarefree over F_q, i.e. every point of X_n(F_q), induces a Frobenius element of Gal(Y_n/X_n) = S_n, at least up to conjugacy, and this conjugacy class of S_n is the one whose cycle type is the partition described above.

So for each q we get a set of |X_n(F_q)| = q^n – q^{n-1} elements of S_n, or at least elements up to conjugacy.  And if we let q vary over larger and larger powers of a prime p, we get an infinite sequence of elements of S_n, and the Weil conjectures tell us that these elements become equidistributed in S_n.  In particular, the chance that they are n-cycles (i.e. the chance that f is irreducible) is just the proportion of S_n taken up by n-cycles, which is 1/n.  And that is why P(q,n)/{q^n – q^{n-1}) converges to 1/n as q goes up.

But what if n goes up with q fixed?  We still have an infinite sequence of permutations

g_1, g_2, g_3, …

(really, permutations defined up to conjugacy) but now the permutations are getting larger and larger, with only finitely many landing in any particular S_n!  So here’s the question:  what, if anything, can it mean to say that these elements are equidistributed, when there’s no fixed group for them to equidistribute in?  In other words, what is equidistribution with moving targets?

Here’s one thing you might mean.  Let X_k be the class function on S_n sending each permutation to the number of k-cycles in its cycle decomposition.  When g is a random element of S_n for n large, X_k is more or less a Poisson variable with mean 1/k.  So as a kind of consequence of “equidistribution with moving targets” one might ask that

$\lim_{n \ra \infty} 1/n \sum_{i=1}^n X_k(g_i) = 1/k$.

Makes sense, right?  We have as a slogan “A random permutation has 1 fixed point,” without reference to the size of the set being permuted; so if the sequence g_i is to be called “equidistributed” in any sense, the average number of fixed points of g_i should be 1.

In fact, if P is any polynomial in the X_i, the mean of P on S_n approaches a limit a(P) as n grows, and so one might ask more generally that the average of the P(g_i) approaches a(P).

Now it turns out that the g_i coming from squarefree polynomials don’t have this property.  For instance, the average number of fixed points of g_i — that is, the average number of linear factors of a squarefree polynomial — is q/(q+1), not 1.  But at least that limit exists!  And as q goes to infinity, the limit goes to 1, so at least the sequence is in some sense closer and closer to being “equidistributed” as q grows.

ANYWAY:  The point of the linked paper is to show that this kind of behavior is quite general for sequences of permutations coming from (sequences of) moduli spaces whose cohomology groups form finitely generated FI-modules.  The two motivating examples are:

• decomposition into irreducible factors of random squarefree degree-n polynomials over F_q;
• decomposition into F_q-rational tori of random tori in GL_n(F_q).

And we show that these two sequences of (conjugacy classes of) permutations both “approximately equidistribute” in the sense sketched above.  The actual limits are different, though!  For instance, the average number of rational 1-dimensional tori is not 1, and not q/(q+1), but q/(q-1).  And you can also, in a fairly uniform way, generate asymptotics for how often the partition has only one part, how often it has no small parts, etc.  Most of the actual facts we assert about these sequences are known, or knowable, by existing means; but the point is to observe that they are true for the same reason in both cases, and that the precise limits can be read off the structure of some finitely-generated FI module of interest.