Anabelian puzzle 4: What is the probability that a set of n points has no 3 collinear?

OK, this isn’t really an anabelian puzzle, but it was presented to me at the anabelian conference by Alexei Skorobogatov.

Let X_n be the moduli space of n-tuples of points in A^2 such that no three are collinear.  The comment section of this blog computed the number of components of X_n(R) back in January.  Skorobogatov asked what I could say about the cohomology of X_n(C).  Well, not a lot!  But if I were going to make a good guess, I’d start by trying to estimate the number of points on X_n over a finite field F_q.

So here’s a question:  can you estimate the number of degree-n 0-dimensional subschemes S of A^2/F_q which have no three points collinear?  It seems very likely to me that the answer is of the form

P(1/q) q^{2n} + o(q^{2n})

for some power series P.

One way to start, based on the strategy in Poonen’s Bertini paper:  given a line L, work out the probability P_L that S doesn’t have three points on L.  Now your first instinct might be to take the product of P_L over all lines in A^2; this will be some version of a special value of the zeta function of the dual P^2.  But it’s not totally clear to me that “having three points on L_1″ and “having three points on L_2″ are independent.

Tagged , , , , , , ,

15 thoughts on “Anabelian puzzle 4: What is the probability that a set of n points has no 3 collinear?

  1. Greg Martin says:

    “Having three points on L_1″ and “having three points on L_2″ are definitely not indepedent in general – just consider n=3 and n=4, for which the probability is 0 that an n-tuple of points in A^2/F_q both has three points on L_1 and has three points on L_2 (for L_1, L_2 distinct). I doubt they’re exactly independent for any n.

    There’s no reason (in theory) one has to think about the lines themselves: there is a set F of forbidden configurations, namely the (q+1) \binom{q}{3} triples of collinear points in A^2, and we’re trying to count how many n-subsets of A^2 avoid them all. Given some particular set S of s distinct triples of collinear points, let u denote the cardinality of the union of the s elements of S (so u is at most 3s, but sometimes smaller). Then inclusion-exclusion tells us that the number of n-subsets of A^2 with no three points collinear is exactly

    \sum_{S \subset F} (-1)^s \binom{q^2-u}{n-u}.

    Of course, now one has to analyze this expression…. Is it harder or easier than the original problem to ask the question: how many subsets S of F consist of exactly s triples, the union of which has exactly u elements of A^2?

  2. Lior says:

    In the model where the points are chosen independently (that is, they are not necessarily distinct), the probability of a given line containing at most two points is

    (1-1/q)^n \left( 1 + \frac{n}{q-1} + \frac{n(n-1)}{2(q-1)^2} \right),

    which is

    1 – \binom{n-1}{2} q^{-2} + O(q^-3).

    It follows that the expected number of lines containing at least three points is \binom{n-1}{2} + O(q^-1).

    The lines are not quite independent, but they should be rather uncorrelated: except for their intersection (at most one point, which is unlikely to be chosen), the only interaction is that points that are on one cannot be on the other; since we expect very few points on a line anyway, this should be a small effect. This leads me to expect that the variance will also be a power-series in 1/q.

  3. JSE says:

    I doubt they’re exactly independent for any n.

    I agree with this, though I think the more relevant question is whether they are “independent in the limit as n -> infinity.” I like your reformulation — though as in the original formulation the inevitable inclusion-exclusion is a bit intimidating.

  4. Lior says:

    Is the limit n->infinity or q->infinity with n fixed?

  5. JSE says:

    Oh, sorry! The relevant question is q fixed, n -> infinity. With q -> infinity it’s surely just q^{2n} on the nose; I presume this space is irreducible.

  6. JSE says:

    A relevant almost-reformulation — you can take a configuration of n points in A^2, i.e. a point on the Hilbert scheme of A^2 / F_p, i.e. an ideal I in F_p[X,Y] of codimension n, and you can associate to it a pair (A,B) of commuting nxn matrices in M_n(F_p), up to conjugacy; just consider the action of “multiplication by X” and “multiplication by Y” on the n-dimensional vector space F_[X,Y]/I.

    So I think the above question is morally the same as:

    For fixed q and n large, and A and B a randomly chosen pair of commuting matrices over F_q, what is the probability that there do not exist a,b,c in F_q such that

    aA + bB + cId

    has rank at most n-3?

    (Note: the analogous problem in A^1 transforms into: what’s the probability that there’s no c such that A – c has rank at most n-2, or, equivalently, what’s the probability that the characteristic polynomial of A is squarefree? I suppose that’s 1-1/q (at least, that’s the probability that a random polynomial is squarefree.)

  7. Lior says:

    There must be some subtlety here I’m missing: If n is much larger than q^2 then with high probability every point of the plane will be chosen, so in that limit the probability of non-collinearity must be o(q^{2n}). Is “a point on the Hilbert scheme of degree n” different than “a multiset of cardinality n”?

    By the way, if some point occurs in the configuration with multiplicity three, does this count as three collinear points?

  8. JSE says:

    Two subtleties:

    1. A point on this moduil space is an n-tuple of points which is defined, AS A SET, over F_q; not an n-tuple of F_q-rational points. So they could, e.g., all be Galois-conjugate over F_q^n. Otherwise, as you say, once n is very large you’re going to have three points which coincide and which are thus certainly collinear. Which speaks to

    2. My interpretation is that there are no multiple points, since the line through a multiple point and an arbitrary distinct point intersects your set three times. (You could, I guess, consider the “fat point” Spec F_q[x,y]/(x,y)^2 to be a case with a multiple point where “no three points are collinear,” but this is an accident of small n.

  9. Jim Bryan says:

    JSE: I disagree with your analysis for multiple points. A length two subscheme can be thought of as a point along with a direction. A line meeting that point in a direction other than preferred direction will intersect with multiplicity 1. The correct formulation of the condition that there exist “3 colinear point” should give us a closed subscheme of the Hilbert scheme (in fact it is a divisor).

    There is an old paper of Feit and Fine which gives a beautiful generating function for the number of commuting nxn matrices over F_q. In fact there argument yields a formula for the motive of the commuting variety which is not unrelated to the motive of the Hilbert scheme of points in A^2.

    Jordan, this would be a lot easier to have this discussion with me and Greg and Lior if you were simply here at UBC. In fact, we are hiring in arithmetic algebraic geometry, why don’t you apply? It would make life a lot easier.

    P.S. Seriously, consider applying. Vancouver and UBC rock.

  10. JSE says:

    Jim is, of course, correct about the double points; there is then the “configuration space” version of this question (where the points are required to be distinct) and the “Hilbert scheme” version, where you are allowed to have multiple points, as long as the multiple points are at worst double and the line they determine doesn’t hit any other point of the set. (That’s right now, isn’t it, Jim?)

  11. Jim Bryan says:

    The Hilbert scheme version of the problem is attractive in that I think the original problem (about the topology of the space) is fairly tractable. The Hilbert scheme itself is smooth and its topology and geometry are pretty well understood. The configuration space that we are talking about is the compliment of a divisor which I’m pretty sure can be made pretty explicit — it will be a tautological section of some universal line bundle on the Hilbert scheme that shouldn’t be hard to write down. Now I’m not saying that the topology of divisor compliments are easy, but if know the ambient space and you have a good handle on the divisor, then you have a chance. In particular the motive of the compliment should be gettable (and this would solve the Hilbert scheme version of the points over F_q probability problem).

    The schemes with multiple points that will be included in the Hilbert scheme version are anything which is the limit of a family of (distinct) points having no colinear triples. In general, this will include “most” of the boundary, and will contain multiple points of length greater than 2.

  12. JSE says:

    But wait, the configuration space we want is open in the Hilbert scheme — so why should it be closed under limits? I mean, you can just contract everything by dilation to a scheme supported at the origin, but surely we don’t want this to be counted..?

  13. Jim Bryan says:

    Sorry, what I said is wrong; I didn’t apply my negations and quantifiers correctly. I want the part that you throw out to be closure of the set of distinct points have a colinear triple. So what I should have said is that we will include those subschemes which are *not* the limits of a family of subschemes which *do* have a colinear triple. You might object and just say why not throw out the whole boundary (which is itself a divisor). I just think that you have a better chance of determining the complement of a irreducible divisor. Pretty typical mathematician’s trick: change the original problem to a different problem that I like better.

  14. JSE says:

    Just so I understand: let F be the Fano variety of lines in A^2. You have a subscheme I of F x Hilb_n A^2 containing (L,S) whenever the restriction of the 0-dimensional scheme S to L has degree at least 3. You take the scheme-theoretic image of I under the projection F x Hilb_n A^2 -> Hilb_n A^2. Is that your divisor?

  15. Jim Bryan says:

    Yes, I think they are the same. Your divisor obviously contains my divisor but could a prior have some other component that lives purely in the boundary, but I’m pretty sure that doesn’t happen.

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 578 other followers

%d bloggers like this: