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

*F**of dimension*

_{p}^{k}*k*over the finite field with

*p*elements. Then consider

where, for any subset *I* of ** G**, we let

(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

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?

Dear Emmanuel,

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

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

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

.

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.

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.

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

…

Then we can write your sum as

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

Interchanging summation, we have

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.

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.

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.