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

Tagged , ,

## This is not my beautiful pi

This post from It’s Okay To Be Smart got under my skin.  The pictures, generated from the digits of pi, are pretty.  But they should not be called “visualizations” of pi, because they have nothing to do with pi!  The page also shows the results of the same algorithm applied to e and the golden ratio.  They look kind of the same.  And they would look the same applied to random digits.  Because they are visualizations of random digits, not visualizations of pi.

## Wisconsin and the Common Core math standards

I have been inexcusably out of touch with the controvery in Wisconsin about the adoption of the Common Core state standards for mathematics.  I present without comment the text of a letter that’s circulating in support of the CCSSM, which I know has the support of many UW-Madison faculty members with kids in Wisconsin public schools.  All discussion (of CCSSM in general or the points made in this letter) very welcome.

(Related:  Ed Frenkel supports CCSSM in the Wall Street Journal.)

******
To whom it may concern,

We the undersigned, faculty members in mathematics, science and engineering at institutions of higher education in Wisconsin, wish to state our strong support for Wisconsin’s adoption of the Common Core State Standards for Mathematics (CCSSM).  In particular, we want to emphasize the high level of mathematical rigor exemplified by these standards.  The following points seem to us to be important:

• We know that what we have been doing in the past does not work.  Nationwide, over 40% of first-year college students require remedial coursework in either English or mathematics.[1] For many of these students, completing their remedial mathematics (that is to say, high school mathematics) requirement will be a significant challenge on their path to their chosen college degree.  The situation in Wisconsin mirrors the national one.  Over the University of Wisconsin system as a whole, 21.3% of all entering freshmen in the fall of 2009 required remedial education in mathematics.[2]  Over the Wisconsin Technical College System, the mathematics remediation figure is closer to 40%.[3]
• The CCSSM set a high, but realistic, level of expectations for all students.  It is unrealistic, and unnecessary, to expect all students to master calculus (for example) in high school.  That would be the “one size fits all” approach that is often brought up as an argument against the Common Core.  Instead, the CCSSM attempts to identify a coherent set of mathematical topics of which it can be reasonably be said that they are essential for students’ future success in our increasingly technological and data-driven society.  “College and career ready,” yes, but also life and citizenship ready.
• It is easy to point to a certain favorite topic and say that the Common Core delays discussion of that topic, or places it in a grade level higher than it has been taught previously.  It is also dangerous.  There is no merit in placing a topic at a grade level where students are unable to do more than repeat procedures without understanding or reasoning.  (One example would be the all-too-frequent expectation that students compute means and medians of sets of numbers, with no significant connection to context, and no discussion of when it would make sense to use one rather than the other.)  It is necessary to look at any set of standards as a coherent whole, and ask whether students who meet all expectations of the standards have been held to a sufficiently high level.
• Any set of standards is a floor, not a ceiling.  Any local school district, school or individual teacher may set expectations beyond the standards, if they choose to do so.  There are certainly many students who will need more mathematics in high school than is required by the CCSSM: Science, Technology, Engineering or Mathematics (STEM)-intending students, or students who hope to attend an elite college or university, are two obvious groups.  These students should indeed take more mathematics, and opportunities should be made available for them to do so. The standards question, however, is whether all students should be required to learn more mathematics than is in the CCSSM; our answer is “no.”
• Even for talented students, the rush to learn advanced topics and procedures should not come at the expense of students’ deeper understanding of the mathematical content being covered. Talented students also need quality guidance; they should not be rushed thoughtlessly for the sake of advancement.
• There are undoubtedly some professional mathematicians, scientists and engineers who claim that the CCSSM are insufficiently rigorous; it is our understanding that they are a small minority.

We entreat you to keep Wisconsin in the group of States that are adopting the CCSSM.  We see the consequences of failed educational policies in our classrooms every day, and we only have the well being of our students in mind. The CCSSM is the right balance: already far higher than our previous State standards but not beyond what one can expect from a majority of students.

[1] Beyond the Rhetoric: Improving College Readiness Through Coherent State Policy, accessed from http://www.highereducation.org/reports/college_readiness/gap.shtml on October 3, 2013.

[2] Report on Remedial Education in the UW System: Demographics, Remedial Completion, Retention and Graduation, September 2009, accessed from http://www.uwsa.edu/opar/reports/remediation.pdf on October 6, 2013.

[3] Findings of the Underprepared Learners Workgroup, accessed from http://systemattic.wtcsystem.edu/system_initiatives/prepared_learners/Findings.pdf on October 6, 2013.

## I now understand one thing about type theory

I was frustrated by my inability to get anything out of the brief writeup about Voevodsky’s univalent foundations in this month’s Notices.  Fortunately, one of our graduate students, who has been reading the homotopy type theory book, has promised to explain it to me.  I’m excited!

Already, hardly understanding anything, I have learned one interesting thing about type theory.  (I haven’t yet learned anything about homotopy type theory.)  It asks us to throw aside assertions like “P is true” as the basic objects of mathematical interest, and instead to concentrate on assertions like “p is a proof of P.”

In this context, what is conjunction?  To say “x is a proof of P and Q” is to say that x is a pair (p,q) where p is a proof of P and q is a proof of Q.”

What is disjunction?  In other words, what do we mean by “a proof of P or Q”?  Well, there are two kinds of proofs of P or Q; there are proofs of P, and there are proofs of Q.

And this is why intuitionistic logic (which as I understand it is the kind of logic you get when you take this point of view seriously) rejects the law of the excluded middle.  In the logic I know, you can just check from the truth table that (P or not-P) is always true, so (P or not-P) is the same thing as T.

But in type land, a proof of (P or not-P) must be either a proof of P or a proof of not-P.  If neither of these is available, then there’s no proof of (P or not-P), so it can’t be the same as T.

I know in some sense this seems tautological — but I do find it rather striking as an illustration of an actual substantial difference between the two set-ups.

As Vladimir teaches me more, I’ll keep posting!

P.S.:  by the way:  in type theory, a proof of an implication “P implies Q” is a function from proofs of P to proofs of Q.  (Or does it have to be an explicit algorithm that returns a proof of Q given a proof of P?  I don’t know.)  This is not the same as a proof of “not-P or Q”, which would have to be either a proof of not-P or a proof of Q, a completely different thing.  So the logical account of implication I’m used to also dies!

On the other hand, a proof of Q is a proof of (not-P or Q).  What’s more, if I have a proof q of Q, then the constant function sending every proof of P to q is a proof of (P implies Q).

I think the above paragraph is a correct proof in the type-theoretic sense of (Q implies (not-P or Q)) and also (Q implies (P implies Q)).  What do you think?

(Note that I haven’t told you what a type is yet.  That’s because I don’t know.  I told you, I only understand one thing so far.)