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

### Kowalski

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

## 5 thoughts on “Combinatorial cancellation”

1. Terence Tao says:

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.