## Stoner

Stoner, a 1965 novel by John Williams, has been named the 2013 Waterstones Book of the Year.

Pretty cool to see an old book recognized!  I read this a while back; it’s one of those books often mentioned as a “forgotten classic” and I read such books out of a sense of obligation.  But sometimes, like this time, it pays off.  (See also:  Independent People, The Bridge on the Drina.)  Stoner represents a certain strain in the mid-century American novel that I really like, and which I don’t think exists in contemporary fiction.  Anguish, verbal restraint, weirdness.  Among famous authors, maybe some of Salinger, maybe some of O’Connor (but not glowing like O’Connor, more subdued, and not funny like Salinger, more deadpan.)  Besides Stoner I am thinking of James Purdy and Richard Yates — not even so much Revolutionary Road but The Easter Parade, which is grinding and merciless but at the same time strangely mild-mannered, in the same way Stoner is.

What else belongs here?

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.

## Names and words

When you get the copy-edited manuscript of a book back, it comes with a document called “Names and Words,” this is a list of proper names or unusual words in the book which might admit variant spelling or typography, and the list is there to keep everybody on the production team uniform.

Here’s the A-B section of my list.  I think it gives a pretty good sense of what the book is about.

Niels Henrik Abel

Aish HaTorah

Alcmaeon of Croton

Alhazen (Abu ‘Ali al-Hasan ibn al-Haytham)

Spike Albrecht

Ray Allen

Scott Allen

Akhil and Vikram Amar

Apollonius of Perga

Yasser Arafat

John Arbuthnot

Dan Ariely

Kenneth Arrow

John Ashbery

Daryl Renard Atkins

Yigal Attali

David Bakan

Stefan Banach

Dror Bar-Natan

Joseph-Émile Barbier

Leroy E. Burney

Andrew Beal

Nicholas Beaudrot

Bernd Beber

Gary Becker

Armando Benitez

Craig Bennett

Jim Bennett

George Berkeley

Joseph Berkson

Daniel Bernoulli

Jakob Bernoulli

Nicholas Bernoulli

Alphonse Bertillon

Bertillonage

Joseph Bertrand

best seller

best-selling

R. H. Bing

Otto Blumenthal

Usain Bolt

Farkas Bolyai

János Bolyai

Jean-Charles de Borda

Bose-Chaudhuri-Hocquenghem code

Nick Bostrom

David Brooks

Derren Brown

Filippo Brunelleschi

Pat Buchanan

Georges-Louis LeClerc, Comte de Buffon

Dylan Byers

Daniel Byman

David Byrne

Tagged ,

## “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

## Sebastian Thrun, MOOC skeptic

The founder of Udacity no longer thinks MOOCs are the answer, says this Fast Company article.  As for me, I’ve become more optimistic about MOOCs as I’ve talked to the people at Wisconsin who are doing them, and seen what they’ve put together.

Although Thrun initially positioned his company as “free to the world and accessible everywhere,” and aimed at “people in Africa, India, and China,” the reality is that the vast majority of people who sign up for this type of class already have bachelor’s degrees, according to Andrew Kelly, the director of the Center on Higher Education Reform at the American Enterprise Institute. “The sort of simplistic suggestion that MOOCs are going to disrupt the entire education system is very premature,” he says.

I too was surprised to learn that most people who take Wisconsin’s MOOCs are 30 and up.  But that made me really happy! Right now we put a massive amount of effort into teaching things to people who are between 18 and 21, and after they leave the building, we’re done with them (except when we mail them a brochure asking for money.)  30-year-olds know a lot more about what they want to do and what they need to know than 18-year-olds do.  55-year-olds even more so, I’ll bet.  I hope we can make higher education a life-long deal.

Oh, also:

When Thrun says this, I nearly fall out of my chair. He is arguably the most famous scientist in the world

I feel like you have to be very deeply embedded in Silicon Valley culture to type this sentence.

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……

## True love and baseball

Happy World Series Day, my favorite secular yontif!  In the spirit of the season I have a piece in Slate about CJ’s love for baseball, and mine.  I was extremely pleased that Rob Neyer liked it.

Here’s the finish:

I tried to make my son into an Orioles fan, like me. But the day at Miller Park he saw Carlos Gomez steal second, then third, then break for home, scoring on a wild pitch, like he was playing Atari baseball against a team of hapless 8-bit defenders, he became a Brewers fan for life. (To be precise, he describes himself as 70 percent Brewers, 30 percent Orioles.) We get along fine, in our mixed household. The inconsistency of our rooting interests doesn’t bother him. If there is a lesson baseball can offer us, it’s one about our deepest commitments; that they’re arbitrary, and contingent, but we’re no less committed to them for that. If I’d been born in New York, I might have been a Yankees fan, but luckily for me, I was born in Maryland, so I’m not. Jerry Seinfeld once remarked that baseball fandom, in the age of free agency, amounted to rooting for laundry. That’s not an insult to the game, as Seinfeld, a giant Mets fan, surely understood; it’s a testament to its deepest strength. My son’s love for the Brewers, like mine for the Orioles, is a love with no reason and no justification. True love, in other words.

Seriously, non-Wisconsin people, if you haven’t been paying attention to Carlos Gomez you are missing out on some joyous baseball.

## 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.