Proving an integer is non-negative by showing there is a vector space with it as its dimension.

The other day I attended a lecture on methods to show whether or not a number is an integer. We were given examples of showing it is the number of ways to count something, and to show there exist groups and subgroups and then apply Lagrange's theorem. But it was stated that from time to time it crops up where in order to prove that an integer is non-negative, one must show there exists a vector space with it as the dimension, hence proving it can't be negative. I really like the sound of this, but no example was given.

Could someone give a problem and solution demonstrating this method of proof?

Or at least allude to one.

Solution 1:

Here are two examples; I am afraid that complexity-wise they are a bit high for this site, but here it goes. Both examples share the property that certain numbers defined originally in combinatorial terms, are proven to be nonegative integers via their cohomological interpretation. (One can manufacture artificial examples of the same phenomenon by starting with some combinatorial quantities, like dimensions of some representations, which are manifestly nonnegative and then use alternative combinatorial descriptions of these quantities, where positivity is obscured. However, this is cheating, since such quantities are typically originally defined so that their nonegativity is clear.)

(1). McMullen's conjecture (Stanley theorem). Given a (rational) convex polytope $P\subset {\mathbb R}^d$, one defines a combinatorial quantity which captures numbers of faces of various dimensions, called $H$-vector: $(h_0,...,h_d)$. Even though it is more obscure (at the first glance) than the $F$-vector (the vector $F=(f_0,...f_d)$ simply records numbers of faces of $P$ of dimensions $0$ through $d$), it contains the same information and has better structural properties: $$ h_k= \sum_{i=0}^k (-1)^{k-i} {d-i\choose k-i} f_{i-1}. $$

Peter McMullen conjectured that $$ 1=h_0\le h_1\le h_2\le ...\le h_m, \quad m=[d/2]. $$ One can think of this conjecture as positivity of the differences $\delta_i=h_i-h_{i-1}$. Note that even positivity of the given $h_i$ (for $i$ large) is not immediate since its definition involves an alternating sum. Richard Stanley proved (see Corollary 3.2 here) McMullen's conjecture by reinterpreting the problem in algebro-geometric fashion, where the numbers $h_i$ are dimensions of intersection cohomology groups $IH^{2i}(X)$ for a toric variety $X$ associated with $P$. Then the numbers $\delta_i$ appear as coranks of the maps (cup products with the Kahler class of $X$) $$ IH^{2i-2}(X)\to IH^{2i}(X) $$ coming from the hard Lefschetz theorem.

(2). Kazhdan–Lusztig polynomials. There are important polynomials, called Kazhdan–Lusztig polynomials (see here) $P_{y,w}$ associated with Coxeter groups $W$ ($y$ and $w$ are elements of $W$ satisfying the inequality $y\le w$ in the Bruhat order on $W$). These polynomials appear as matrix coefficients in transition matrices from one basis to another in representations of Hecke algebras. The fact that coefficients of these polynomials are nonegative integers is not obvious at all. For finite Weyl groups (of crystallographic type) positivity and integrality of these coefficients again follows from their interpretation as dimensions of certain intersection cohomology groups. For general Coxeter groups positivity and integrality again follows from a cohomological interpretation of these coefficients (they again appear as dimensions of certain vector spaces). See the same wikipedia article above for details and references.

Solution 2:

I like the question, and add another example:

Let $M$ be an $m\times n$ matrix, and let $k$ be the rank of $M$. How do you show that $n-k$ is a non-negative integer?

You prove that $n-k$ is the dimension of the space of solutions of the system $MX=0$.

Solution 3:

I propose the Riemann Roch formula.

It is a very powerful tool in algebraic geometry. This formula relates four quantities which are integers. The proof, which is a wonderful but not simple piece of mathematics, proceeds exactly by showing that one of the quantities in play is the dimension of a certain vector space.

Solution 4:

There is something half-way between the two techniques you propose: namely, proving that an integer is non-negative by showing that it counts something. Counting bases of vector spaces is just one particular instance of that, and one can always reduce to that case because any set can be made into a free vector space with dimension equal to the cardinality of the original set.

A fun example combining both situations is the necklace-counting problem. Let $M(k, n)$ be the number of necklaces on $n$ beads of $k$ colors. Then

$$M(k,n) = \frac{1}{n}\sum_{d \mid n} \mu(n/d) k^d$$

where $\mu$ is the Möbius function. It is neither immediately obvious that $M(k, n)>0$ or that $M(k,n)$ is an integer. (In fact, it's not very hard to see directly that $M(k,n)>0$ because the term $k^n$ dominates the rest of the sum, but it's still nice to have it for free. Proving that $M(k,n)$ is an integer without relying on this combinatorial interpretation is trickier.)