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