13
$\begingroup$

Let $L$ be a finite distributive lattice with $n$ elements. Let $C=(c_{x,y})$ be the $n \times n$ matrix with entry 1 in case $x \leq y$ and 0 else. The Coxeter matrix of $L$ is defined as the matrix $G_L=-C^{-1}C^T$ (this is the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of the poset).

I noted that for $n \leq 10$ it was always true that the permanent of $G_L$ is either $1$ or $-1$. I was able to prove it only for some small cases such as Boolean algebras and some random examples.

Question 1: Is this true in general?

Question 2: Does one have a nice order theoretic characterisation when it is $1$ or $-1$ in case question 1 is true?

Question 3: Let $L_n$ be the set of distributive lattices with n elements. Is the sum $|\sum_{L \in L_n}^{}{\mathrm{Perm}(G_L)}|$ bounded for $n \rightarrow \infty$? For $n \leq 10$ it was at most 2.

It is also interesting to note that for arbitrary finite lattices it seems that the permanent of $G_L$ can be arbitrary large.

My knowledge of permanents is close to zero so I'm sorry in case this question is not suitable for MO.

The values of this statistic for posets has been entered recently here: http://www.findstat.org/StatisticsDatabase/St001472 .

$\endgroup$
4
  • $\begingroup$ @IlyaBogdanov Do you mean this statistic: findstat.org/StatisticsDatabase/St000914 ? If yes, then it might not be true since here the values -1 and 1 occur while in findstat.org/StatisticsDatabase/St000914 only the value 1 occurs for distributive lattices. $\endgroup$
    – Mare
    Oct 5, 2019 at 14:58
  • $\begingroup$ @IlyaBogdanov What you mean would be the sum of all entries of $C^{-1}$, or? $\endgroup$
    – Mare
    Oct 5, 2019 at 14:59
  • 1
    $\begingroup$ Oh! Yes, sorry, working further;) $\endgroup$ Oct 5, 2019 at 15:00
  • 1
    $\begingroup$ Note that the entries of $C^{-1}$ are the Mobius function of $L$. $\endgroup$ Oct 7, 2019 at 13:41

1 Answer 1

7
+100
$\begingroup$

$\def\low{\mathop{\mathrm{low}}}\def\perm{\mathop{\mathrm{perm}}}$This seems to be a (hopefully correct now) answer to Q1 and Q2. But this looks a bit strange --- perhaps, it is worth it to check some consequences on small lattices.

We implement Birkhoff's theorem in a dual form, identifying $L$ with the lattice of upper sets of some poset $P$ (the structure of which is known); we thus regard each $x\in L$ as an upper set in $P$, so that $x\leq y\iff y\subseteq x$ (!). Next, each element $x\in L$ is determined by the set $\min x$ of its minimal elements, and each independent set $Q\subseteq P$ determines an element $u_Q=\{x\in P\colon \exists q\in Q\quad x\geq q\}$ with $\min u_Q=Q$.

1. First, let us learn the structure of $C^{-1}=(\mu(x,y))$. As has been already mentioned in the comments, $\mu$ is the Möbius function of $L$. Fix an element $x$; for every $J\subseteq \min x$, introduce $x^J=x\setminus J$. Clearly, all the $x^J$ are pairwise distinct. Then one can easily see that $\mu(x,x^J)=(-1)^{|J|}$, and these are the only nonzero values of $\mu(x,\cdot)$ (indeed, the matrix $C'$ determined by these values satisfies $C'C=I$.

(Not needed) Similarly, denoting $\low y=\max(P\setminus y)$, we may define $y_J=y\cup J$ for any $J\subseteq \low y$ and see that $\mu(y_J,y)=(-1)^{|J|}$ are the only nonzero value of $\mu(\cdot,y)$.

2. Let now $-G_L=C^{-1}C^T=(g_{xy})$ (we omit the minus sign for clarity; this changes the sign of the permanent in a clear manner). We have $$ g_{xy}=\sum_{z\geq x\vee y}\mu(x,z) =\sum_{z\subseteq x\cap y}\mu(x,z) =\sum_{\textstyle{J\subseteq \min x\atop x\subseteq J\cup y}}\mu(x,x^J) =\begin{cases} (-1)^{|\min x|}, & y\cap x=x\setminus \min x;\\ 0, & \text{otherwise.} \end{cases} $$ To state it simple, the element $g_{xy}$ is nonzero if and only if $y\cap x=x\setminus \min x$, and all such elements for a fixed $x$ are the same, namely, they equal $(-1)^{|\min x|}$.

This already yields that all nonzero summands in $\perm G_L$ are equal --- namely, each of them equals $(-1)^{\sum_x|\min x|}$. This shows that the answer to Q1 is affirmative if and only if the permanent has a unique nonzero summand (which is what I called strange), and, given that, answers Q2. We are now to check that strange claim.

3. So, we need to show that there exists a unique permutation $\sigma\colon L\to L$ satisfying $x\cap \sigma(x)=x\setminus\min x$. We start with constructing such permutation $\tau$, and then show its uniqueness.

For any $x\in L$, let $$ \tau(x)=\bigcup_{\textstyle{y\in L\atop y\cap x=x\setminus\min x}}y; $$ that is, $\tau(x)$ is the minimal (in $L$) element satisfying the required property. We show that $\tau$ is a permutation by indicating its right inverse $\tau^{-1}$ as $$ \tau^{-1}(y)=u_Q,\qquad \text{where } Q=\max(P\setminus y). $$ Indeed, it is clearly seen that $\tau(\tau^{-1}(y))=y$ for all $y\in L$.

Finally, let $\sigma$ be a permutation satisfying the conditions above; then $\sigma(x)\subseteq \tau(x)$ for all $x\in L$. Then $$ \sum_{y\in L}|y|=\sum_{x\in L}|\sigma(x)|\leq \sum_{x\in L}|\tau(x)|=\sum_{y\in L}|y|, $$ so the middle inequality turns into equality. This may happen only if $\sigma=\tau$, which finishes the proof.

$\endgroup$
3
  • 5
    $\begingroup$ I believe the permutation $\sigma$ is the operation called "rowmotion" arxiv.org/abs/1108.1172 . Namely, given an upper ideal $X$, let $I = \min X$, let $\langle I \rangle$ be the <b>lower</b> ideal generated by $I$ and let $\overline{\langle I \rangle}$ be the complement of $\langle I \rangle$. The operation $X \mapsto \overline{\langle I \rangle}$ is called rowmotion. It is known to be a permutation and is very trendy right now. Mare might be particularly interested in front.math.ucdavis.edu/1805.00815 , which connects rowmotion to representation theory. $\endgroup$ Oct 7, 2019 at 15:51
  • $\begingroup$ @DavidESpeyer: Yes, it is the same operation. Thanks for the comment! $\endgroup$ Oct 7, 2019 at 16:14
  • $\begingroup$ For the benefit of anybody skimming: what is shown here is that the answer to Question 1 is yes, and a formula answering to Question 2 can be found in the details. $\endgroup$
    – Tim Campion
    Aug 30, 2020 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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