Combinatorial cancellation

Here is the example of sums exhibiting a large amount of combinatorial cancellation that I mentioned in a comment on my previous post. First, some notation: p is a prime number, k is a positive integer, and G is the set of hyperplanes in the vector space Fpk of dimension k over the finite field with p elements. Then consider

\sum_{\emptyset\not=I\subset \mathbf{G}}{\frac{(-1)^{|I|+1} }{1-p^{j(I)-k}}}

where, for any subset I of G, we let

j(I)=\mathrm{dim} \bigcap_{H\in I}{H}

(the dimension of the intersection of the hyperplanes in I).

The terms of this sum are of absolute value of size roughly 1, if p is large (since I is non-empty, the intersection is contained in any of the hyperplanes in I, so j(I)<k), but there are many of them, namely

2^{|\mathbf{G}|}-1=2^{p^k+\cdots+p+1}-1,

so one may suspect that the overall sum is quite large.

And yet, it turns out that, for fixed k and p going to infinity, the sum converges to k. My explanation for this is rather indirect, and I will explain it in another post soon, but maybe some readers can see a direct reason?

Published by

Kowalski

I am a professor of mathematics at ETH Zürich since 2008.

5 thoughts on “Combinatorial cancellation”

  1. Dear Emmanuel,

    One can use the geometric series formula to expand the expression as

    \sum_n \sum_I (-1)^{|I|+1} p^{n(j(i)-k)}

    (where I is summed as above), which can be written probabilistically as

    \sum_{n=0}^\infty E_{x_1,\ldots,x_n} \sum_{I: x_1,\ldots,x_n \in I} (-1)^{|I|+1}

    where $x_1,\ldots,x_n$ are chosen uniformly and independently from $F_p^k$. But by the binomial formula, the inner sum vanishes unless $x_1,\ldots,x_n$ fail to span $F_p^k$, in which case the sum is 1. So the sum simplifies to

    \sum_n P( x_1,\ldots,x_n\ do\ not\ span\ F_p^k).

    For p large, the probability is close to 1 for n < k, and close to zero otherwise, which explains why the sum converges to k as p gets large.

  2. Thanks!

    This is actually close to (but simpler than) the argument I have, which is also probabilistic and also based on issues of when n-tuples generate F_p^k.

  3. This is less elegant than Terry’s approach, but I’ll put it out there anyway as an example of how I would try to brute force this.

    Let h(p,j) be the function which has the following property:

    For any subspace V of F_p^k, we have

    $latex \sum_{V \subseteq W \subseteq F_p^k} h(p, dim W)
    = 1/(1-p^{dim V-k})$

    The function h is determined by a collection of linear equations which are upper triangular; the first few are

    h(p,k)=1/(1-p^{-k})
    h(p,k-1)+h(p,k)=1/(1-p^{-k+1})
    h(p,k-2)+(p+1)h(p,k-1)+h(p,k)=1/(1-p^{-k+2})

    Then we can write your sum as

    \sum_{I \neq \emptyset} (-1)^{I+1} \sum_{W^{\perp} \supseteq I} h(p,dim W )

    where W^{\perp} is the set of hyperplanes containing W.

    Interchanging summation, we have

    \sum_{W \subseteq F_p^k} h(p,dim W) \sum_{\emptyset \neq I \subseteq W^{\perp}} (-1)^{I+1}.

    The inner sum is just 1, so we get

    $latex \sum_{W \subseteq F_p^k} h(p,dim W) =
    \sum_{j=1}^k (p^{j(k-j)}+\ldots)*h(p,j).$

    Here we have used that the number of j-dimensional subspaces of F_p^k is p^{j(k-j)} plus lower order terms.

    Experimentally, it appears that h(p,j) ~ p^{-j(k-j)}, so each of the summands approaches 1 as p goes to infinity.

    Obviously, this isn’t a proof until I show that this is the leading term of h(p,j) for all j. However, it does contain two ideas which are generally useful.

    (1) Whenever you have a sum sum_v over a partially ordered set, like the set of subspaces of a vector space, try rewriting the sum as sum_{w \leq v} and then removing the sum on v. In the special case where your partially ordered set is the set of divisors of an integer n, this is Mobius inversion; when the partially ordered set is the subsets of a given set, this is inclusion-exclusion; when the partially ordered set is {1,2,…,n}, this is summation by parts. In general, the combinatorial key phrase you want to look for is “the Mobius function of the poset”.

    (2) A sum over sets, weighted by (-1)^{|I|}, usually wants to be turned into something to which you can apply sum (-1)^r (n choose r)=0.

  4. Note: I’ve taken the liberty of editing Comments 1 and 3 to add the proper latex markers so that the displayed formula are more readable.

  5. This second method (Comment 3) is also quite elegant, and certainly will be useful indeed as a general technique. I have the impression that parts of my own proof may be tantamount to actually computing h(p,j), or something closely related.

Leave a Reply

Your email address will not be published. Required fields are marked *