Today I Learned

May 17th

Today I learned the finish of the proof of the poset combinatorial reciprocity theorem, from Combinatorial Reciprocity Theorems . As usual, our setup is to fix a poset $(X,\le)$ with lattice order ideals $\mathcal J(X)$ and let $W_X(n)$ be the number of number of weakly order-preserving maps from $X\to[n].$ We also let $S_X(n)$ be the number of strictly order-preserving maps. Two days ago we also introduced the incidence algebra $I(X)$ including the adjacency matrix\[\zeta_X(x,y)=\begin{cases} 1 & x \le y \\ 0 & \text{else}.\end{cases}\]In particular, we established the following result.

We showed this two days ago. That this holds for nonnegative integers was a combinatorial argument counting directed paths through $\mathcal J(X).$ That this holds for negative integers required some care and used the expansion of $\zeta^n(x,y)=(\zeta(x,y)-1_{x=y}(x,y))^n$ by the binomial theorem. $\blacksquare$

For the combinatorial reciprocity theorem, we are building towards the following.

We need to relate $W_X(-n)=\zeta_{\mathcal J(X)}^{-n}(\emp,X)$ to $S_X(n).$ Starting from what we understand, all we have gained from writing $W_X(-n)=\zeta_{\mathcal J(X)}^{-n}(\emp,X)$ is the ability to write\[\zeta_{\mathcal J(X)}^{-n}(\emp,X)=\underbrace{\left(\zeta^{-1}*\cdots*\zeta^{-1}\right)}_n(\emp,X)=\sum_{\emp=I_0\subseteq\cdots\subseteq I_n=X}\zeta^{-1}(I_0,I_1)\cdots\zeta(I_{n-1},I_n)\]by definition of our matrix-multiplication convolution product $*$ of the incidence algebra. (Note that all $\zeta$s are $\zeta_{\mathcal J(X)}.$) The point here is that this expansion is a sum over chains in the lattice of order ideals, from $I_0=\emp$ to $I_n=X.$

Now, we need a way to bring $S_X(n)$ into the picture. Because our current approach involved chains of order ideals, we bring in the following statement.

We showed this three days ago. Roughly speaking, $I_k$ corresponds to $\varphi^{-1}(k),$ and this correspondence can be carried through. $\blacksquare$

Looking at our summation, we need the summand to care about when some $I_k\setminus I_{k-1}$ is an antichain for $k\in[n],$ but the only factor of the sum which could possibly "detect'' this is $\zeta_{\mathcal J(X)}^{-1}(I_{k-1},I_k).$ So we hope that\[\zeta_{\mathcal J(X)}^{-1}(I_{k-1},I_k)\stackrel?=0\quad\text{ if }I_k\setminus I_{k-1}\text{ is not an antichain}.\]On the other hand, it's not totally clear what to make $\zeta_{\mathcal J(X)}^{-1}(I_{k-1},I_k)$ for $k\in[n]$ when $I_k\setminus I_{k-1}$ really is an antichain.

Because $S_X(n)$ is counting the number of chains $\emp=I_0\subseteq\cdots\subseteq I_n=X$ where the consecutive differences are antichains, and our expression for $\zeta_{\mathcal J(X)}^{-n}(\emp,X)$ is summed over such chains, it would be nice to make the individual $\zeta_{\mathcal J(X)}^{-1}(I_{k-1},I_k)$ merely indicators for $k\in[n].$ However, the theorem statement asserts that\[\zeta_{\mathcal J(X)}^{-n}(\emp,X)\stackrel?=W_X(n)=(-1)^{\#X}S_X(n),\]and that sign $(-1)^{\#X}$ has to come from somewhere. Looking at our sum\[\zeta_{\mathcal J(X)}^{-n}(\emp,X)=\sum_{\emp=I_0\subseteq\cdots\subseteq I_n=X}\zeta^{-1}(I_0,I_1)\cdots\zeta(I_{n-1},I_n),\]there is no obvious place to put this sign, so we try to evenly distribute it. The most natural way to do this is by conjecturing\[\zeta_{\mathcal J(X)}^{-1}(I_{k-1},I_k)\stackrel?=(-1)^{\#(I_k\setminus I_{k-1})}\quad\text{ if }I_k\setminus I_{k-1}\text{ is an antichain}.\]Our guesses are in fact correct.

Having motivated the statement, there isn't much to do in the proof. Note that $\zeta^{-1}$ is defined as having $\zeta^{-1}*\zeta=\delta,$ where $\delta$ is the identity\[\delta(x,y)=1_{x=y}(x,y)\]of the incidence algebra. By pushing a linear extension on the finite poset $X,$ we can turn the incidence algebra into proper linear algebra, meaning that the incidence algebra with its convolution mulitplication (which is matrix-multiplication in diguise) is a group, where our identity is $\delta.$

The point of saying this is that we merely have to verify that the provided $\zeta^{-1}$ in the statement actually satisfies $\zeta^{-1}*\zeta=\delta$ to show that it is the inverse. To start, note that\[\left(\zeta_{\mathcal J(X)}^{-1}*\zeta_{\mathcal J(X)}\right)(I,K)=\sum_{J\in\mathcal J(X)}\zeta_{\mathcal J(X)}^{-1}(I,J)\zeta_{\mathcal J(X)}(J,K).\]The terms here are $0$ by definition unless $I\subseteq J\subseteq K,$ so we might as well introduce that condition into the sum. While we're here, we note that $J\subseteq K$ implies $\zeta_{\mathcal J(X)}(J,K)=1,$ so we can remove that as well, giving\[\left(\zeta_{\mathcal J(X)}^{-1}*\zeta_{\mathcal J(X)}\right)(I,K)=\sum_{I\subseteq J\subseteq K}\zeta_{\mathcal J(X)}^{-1}(I,J).\]We would like to show that the sum is $\delta.$ We deal with easy cases. Note that $I\not\subseteq K$ makes the sum empty, giving the needed $0.$ We can also quickly deal with $I=K.$ Here, $I\subseteq J\subseteq K$ implies that $I=J=K,$ so there is only one term in the sum. In this case, $J\setminus I=\emp$ is (vacuously!) an antichain, so\[\left(\zeta_{\mathcal J(X)}^{-1}*\zeta_{\mathcal J(X)}\right)(I,I)=\sum_{I=J}\zeta_{\mathcal J(X)}^{-1}(I,I)=(-1)^0=1,\]which is what we needed.

It remains to deal with the case where $I\subsetneq K.$ In this case, we need to show\[\sum_{I\subseteq J\subseteq K}\zeta_{\mathcal J(X)}^{-1}(I,J)\stackrel?=0.\]This requires some thought, but luckily there is a nice combinatorial argument. The key idea is that $\zeta_{\mathcal J(X)}^{-1}(I,J)$ acts like a "counter'' when $J\setminus I$ is an antichain, flipping sign when we add one element to $J.$ So if we can biject pairs $(I,J)$ with a different pair where the $J$ term has one element different, these pairs have $\zeta_{\mathcal J(X)}^{-1}(I,J)$ of different signs, hopefully cancelling.

This is a bit harder than it looks because our one-element peturbation needs to keep $J$ an order ideal and $J\setminus I$ an antichain. For example, we don't want to add a "large'' element to $J,$ else we risk breaking $J$ being an order ideal.

Motivated by this, we find a minimal element $m\in J\setminus I$: note that $J\setminus I\subseteq X$ is a finite poset; to show minimal elements exist, take the proof that maximal elements exist from a few days ago and reverse the inequality signs. Then we claim $\varphi:\mathcal J(X)\to\mathcal J(X)$ by\[\varphi(J):=\begin{cases} J\cup\{m\} & m\notin J, \\ J\setminus\{m\} & m\in J,\end{cases}\]will work as our bijection. The hard part is showing that this is a well-defined map of order ideals $J$ giving $I\subseteq J\subseteq K$ making $J\setminus I$ an antichain. So we first show that this is a bijection, which is easier: it's involutive. On one hand, $m\notin J$ means $\varphi(J)=J\cup\{m\}$ which contains $m,$ implying \[\varphi(\varphi(J))=(J\cup\{m\})\setminus\{m\}=J.\]Similarly, $m\in J$ implies $\varphi(J)=J\setminus\{m\},$ which does not contain $m,$ so\[\varphi(\varphi(J))=(J\setminus\{m\})\cup\{m\}=J.\]So indeed, this is involutive. It also has no fixed points because $m\in J$ implies $m\notin\varphi(J)=J\setminus\{m\},$ and $m\notin J$ implies $m\in\varphi(J)=J\cup\{m\}.$

Now we show that $\varphi$ is a well-defined map of order ideals $J$ giving $I\subseteq J\subseteq K$ making $J\setminus I$ an antichain. We formally split this into two cases.

• If $m\in J,$ then we need to show $\varphi(J)=J\cup\{m\}$ is an order ideal between $I$ and $K$ with $\varphi(J)\setminus I$ an antichain. Because $m\in K\setminus I,$ we still have \[I\subseteq J\subseteq J\cup\{m\}\subseteq K,\] so we at least live between $I$ and $K.$

  To show $J\cup\{m\}$ is an order ideal, pick up $x\in J\cup\{m\}$ and suppose $y\le x.$ Note that $x\in K$ at least implies $y\in K.$ If $x\in J,$ then $y\in J\subseteq J\cup\{m\}$ already because $J$ is an order ideal. Alternatively, if $x=m,$ then $m$ minimal means $y=m$ (so $y\in J\cup\{m\}$ for free), or $y\notin K\setminus I.$ In particular, $y\in I\subseteq J\subseteq J\cup\{m\}.$

  To show that $(J\cup\{m\})\setminus I$ is an antichain, we borrow from the logic above. If we do manage to find $x,y\in J\cup\{m\}$ with $y\le x,$ then $x=m$ means $y\in I$ from above, so $(J\cup\{m\})\setminus I$ is safe. Alternatively, $x\in J$ means $y\in J,$ so $J\setminus I$ being an antichain implies $y\in I$ again. In all cases, we are safe.

• If $m\notin J,$ then we need to show $\varphi(J)=J\setminus\{m\}$ is an order ideal between $I$ and $K$ with $\varphi(J)\setminus I$ an antichain. Because $m\in K\setminus I,$ we still have \[I\subseteq J\setminus\{m\}\subseteq J\subseteq K,\] so we at least live between $I$ and $K.$

  To show $J\setminus\{m\}$ is an order ideal, pick up $x\in J\setminus\{m\}$ and suppose $y\le x.$ Note that $x\in J$ at least implies $y\in J$ because $J$ is an order ideal. But also $y\le x$ are comparable, so $J\setminus I$ antichain means one of $x,y$ lives in $I.$ But $x\in I$ implies $y\in I$ because $I$ is an order ideal, so surely $y\in I.$ In particular, $y\in J\setminus I.$

  To show that $(J\setminus\{m\})\setminus I,$ we note that $x,y\in(J\setminus\{m\})\setminus I$ also live in $J\setminus I,$ which is already an antichain, so it follows $x$ and $y$ are uncomparable.

Thus, we do have that $\varphi$ is an involution of order ideals $J$ between $I$ and $K$ such that $J\setminus I$ is an antichain. From this it follows\[\sum_{I\subseteq J\subseteq K}\zeta_{\mathcal J(X)}^{-1}(I,J)=\sum_{I\subseteq J\subseteq K}\zeta_{\mathcal J(X)}^{-1}(I,\varphi(J))=\sum_{I\subseteq J\subseteq K}-\zeta_{\mathcal J(X)}^{-1}(I,J)\]because $\varphi(J)$ always has one more or one less element than $J,$ making $(-1)^{\#(J\setminus I)}$ flip sign. It follows that the sum must be $0,$ completing the proof. $\blacksquare$

Having completed the proof of the lemma, we are pretty much done. Recall that\[W_X(-n)=\zeta_{\mathcal J(X)}^{-n}(\emp,X)=\sum_{\emp=I_0\subseteq\cdots\subseteq I_n=X}\left(\prod_{k=1}^n\zeta^{-1}(I_{k-1},I_k)\right).\]Using the above lemma, the sum only cares about terms where each difference $I_k\setminus I_{k-1}$ is an antichain, in which case we have\[W_X(-n)=\sum_{\substack{\emp=I_0\subseteq\cdots\subseteq I_n=X\\I_k\setminus I_{k-1}\text{ antichain}}}\left(\prod_{k=1}^n(-1)^{\#(I_k\setminus I_{k-1})}\right).\]Moving the product into the exponent as a sum, we are summing the size of $I_k\setminus I_{k-1}$ over $k\in[n].$ Telescoping, this is $\#(I_n\setminus I_0)=\#X,$ so we see\[W_X(-n)=\sum_{\substack{\emp=I_0\subseteq\cdots\subseteq I_n=X\\I_k\setminus I_{k-1}\text{ antichain}}}(-1)^{\#X}.\]Factoring out the $(-1)^{\#X}$ and using our proposition for $S_X(n)$ completes the proof. $\blacksquare$

That proof was long enough that I'm not super inclined to give comments. I will say that the cruz of the proof comes down to computing $\zeta^{-1}$ in the case of the lattice of order ideals. I am under the impression that $\zeta^{-1}$ is in general difficult to compute, and this should be unsurprising given that its computation is pretty much our combinatorial reciprocity theorem.