One of the most important proof techniques in combinatorics is double counting: proving that both sides of an identity count elements of some set in two different ways. This question is an attempt at understanding various forms of double counting for various motivic invariants such as Euler characteristics, counts of $\mathbb F_q$ rational points, cohomology etc.

Question: What are your favorite (or instructional) examples of identities that come from computing a motivic invariant for a space in two different ways?

I'll start by including some combinatorial examples I could think of.

Example 1: The simplest form of this is to do a straightforward $q$-analog of a classical double counting identity. For example Vandermonde's identity $$\binom{m+n}{k}=\sum_{j}\binom{m}{j}\binom{n}{k-j}$$ has a motivic lift to $$[Gr(k,m+n)]=\sum_{j}[Gr(j,m)][Gr(k-j,n)][\mathbb A^{j(m-k-j)}]$$ which gives us the q-analog of Vandermonde's identity.

Example 2: The Lagrangian Grassmannian $L(n,2n)$ of $n$-dimensional isotropic subspaces in a symplectic vector space is an example where we can write $[L(n,2n)]$ as a quotient $$[Sp_{2n}(\mathbb F_q)]/[\text{Stab}(\mathbb F_q)]=(1+q)(1+q^2)\cdots(1+q^n)$$ where $\text{Stab}$ is the stabilizer of the transitive action of the Symplectic group on $L(n,2n)$. On the other hand we can also express $[L(n,2n)]$ as a sum over cells which are bundles over grassmannians with fibers being affine spaces. This results in the q-binomial theorem $$[L(n,2n)]=\sum_{j}[Gr(j,n)][\mathbb A^{j(j+1)/2}].$$ (I personally like this example because it shows that the power set $P(\{1,2,\dots, n\})$ can be written as the n-element subsets of $\{1,2,\dots,n,\bar{1},\bar{2},\dots,\bar{n}\}$ which intersect every $\{i,\bar{i}\}$ in precisely one element, and this can be thought of as a kind of $\mathbb F_1$-Lagrangian Grassmannian somehow.)

Example 3: Loehr and Warrington defined a statistic on partitions $h_x$ for every $x\in [0,\infty)$ and gave bijective proofs of $$\sum_{\lambda} q^{|\lambda|}t^{h_x(\lambda)}=\prod_{i=1}^{\infty}\frac{1}{1-tq^i}$$ so in particular all $h_x$ have the same distribution on partitions independent of $x$. This has a geometric meaning for irrational $x$ (due to Haiman) since the RHS is the generating function of Poincare polynomials of Hilbert schemes $\operatorname{Hilb}_n(\mathbb A^2)$. All these Hilbert schemes come with an action of a 2 dimensional torus. If we pick a 1 dimensional subtorus with slope parameter $x$ and take Bialynicki-Birula decompositions from its action we get affine cells for every partition $\lambda$ (these index the torus fixed points) whose dimensions are distributed according to $h_x(\lambda)$. So this example is computing the Poincare polynomial of $\operatorname{Hilb}_n(\mathbb A^2)$ in infinitely many ways.

  • 2
    $\begingroup$ Related question: mathoverflow.net/questions/299998/… $\endgroup$ – Sam Hopkins Aug 20 '18 at 20:27
  • $\begingroup$ @SamHopkins Kind of :) I didn't want to put as much emphasis on F1/Fq translations as on the "interesting situations where cohomology for some space is computed in two different ways". $\endgroup$ – Gjergji Zaimi Aug 20 '18 at 20:44
  • $\begingroup$ A similar example to those mentioned: computing the Betti numbers of a hyperplane arrangement complement by counting points in the complement over finite fields (in combinatorics we call this enumeration the "characteristic polynomial" of the arrangement). I think it works for subspace arrangements too. $\endgroup$ – Sam Hopkins Aug 20 '18 at 21:40
  • 1
    $\begingroup$ @SamHopkins Good idea! For example, for the Poincare/characteristic polynomial of free arrangements, we have an alternating sum of $q^{\dim}$ on one side (if we count it by inclusion exclusion of hyperplane intersections), and $\prod (1+d_i q)$ on the other side where $d_i$ are the exponents of the arrangement. $\endgroup$ – Gjergji Zaimi Aug 21 '18 at 2:33

I will upgrade my comment to an answer. Let $\mathcal{A}$ be an $n$-dimensional hyperplane arrangement defined over the rational numbers $\mathbb{Q}$ (or equivalently by clearing denominators, over $\mathbb{Z}$). Associated to $\mathcal{A}$ is its characteristic polynomial $\chi(\mathcal{A};q)$.

There are various ways one can think about $\chi(\mathcal{A};q)$ and these lead to the kind of motivic double counting described in the question (although I don't know if it can be neatly expressed as a single equality of $q$-numbers).

On the one hand there is a purely combinatorial definition: $\chi(\mathcal{A};q) = \sum_{F \in L(\mathcal{A})}\mu(F)\,q^{\mathrm{dim}(F)}$, where $L(\mathcal{A})$ is the intersection poset of $\mathcal{A}$, and $\mu$ is the Möbius function of $L(\mathcal{A})$. Technically the intersection poset $L(\mathcal{A})$ depends on a field, but since we assumed $\mathcal{A}$ was defined over $\mathbb{Q}$ we can always take $\mathbb{Q}$ to be our field.

We can also think of the characteristic polynomial as (essentially) a Poincaré polynomial of a complex algebraic variety: $\chi(\mathcal{A};q)=q^n\sum_{i}b_i\,(-1/q)^{i}$, where $b_i$ is the $i$th Betti number of the complement $\mathbb{C}^n\setminus \mathcal{A}$.

Third, $\chi(\mathcal{A};q)$ also counts points of that "same" variety over finite fields $\chi(\mathcal{A};q)=\#(\mathbb{F}^n_{q}\setminus\mathcal{A})$, where $\mathbb{F}_q$ is a finite field with $q$ elements. Actually we require that $\mathbb{F}_q$ be of sufficiently large characteristic, depending on $\mathcal{A}$, for this to point-counting to hold.

There is something vaguely similar to the Weil conjectures here where the topology of a complex algebraic variety determines the point-counting function for that same variety over finite fields.

It is also worth mentioning the well known fact that $\chi(\mathcal{A};q)$ contains information about $\mathcal{A}$ viewed as a real arrangement as well: $(-1)^n\chi(\mathcal{A};-1)$ is the number of regions of $\mathcal{A}$ viewed as a real arrangement; and $(-1)^{\mathrm{rank}(\mathcal{A})}\chi(\mathcal{A};1)$ is the number of relatively bounded regions.

Finally, as Gjergji mentioned, in some special cases it may be that $\chi(\mathcal{A};q)$ factors nicely into linear terms: for instance, this happens when $\mathcal{A}$ is free. Freeness is a certain deep algebraic property of arrangements introduced by Terao in the 80s; it generalizes the combinatorial property of supersolvability which Stanley introduced in the 70s. We say $\mathcal{A}$ is free if its "module of logarithmic derivations" is a free module over the polynomial ring; in this case the module is generated by homogeneous elements whose degrees $d_1,\ldots,d_n$ are called the exponents of the arrangement. A celebrated theorem of Terao says that for a free arrangement we have $\chi(\mathcal{A};q) = \prod_i (q-d_i)$.

  • 1
    $\begingroup$ If you do want to extract a specific identity from this, you can choose a specific nice arrangement. For instance, the braid arrangement gives $\sum_{p\in\Pi_n}\mu(p)q^{n-\mathrm{rk}(p)} = q \cdot (q-1) \cdots (q-(n-1))$, where $\Pi_n$ is the lattice of set partitions of a set of size $n$. $\endgroup$ – Sam Hopkins Aug 21 '18 at 4:30
  • $\begingroup$ Shouldn't $\mathbb F_q \setminus \mathcal A$ be $\mathbb F_q^n \setminus \mathcal A$? $\endgroup$ – LSpice Aug 21 '18 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.