Skip to main content
deleted 572 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

The answer is yes. I claim there are at most $2^n$ elements of $W$ for which $\lambda(w) \neq 0$. Specifically, let $\vee$ be the join in weak order, which is a semi-lattice. If $\{ s_1, s_2, \ldots, s_j \} \subseteq S$ and $s_1 \vee s_2 \vee \cdots \vee s_j$ is defined, then I claim that $\lambda(s_1 \vee s_2 \vee \cdots \vee s_j)=(-1)^j$, and otherwise I claim that $\lambda(w)=0$. Thus $N$ can be taken to be the greatest length of $s_1 \vee s_2 \vee \cdots \vee s_j$, restricting ourselves to cases where this join is defined.

The condition $|v^{-1} w| = |w| - |v|$ says that $v \leq w$ in weak order. Therefore, this is the recursion defining the Mobius function of weak order. The Mobius functionsfunction of lattices are well understood, and I extracted the result in the first paragraph from a paper of Blass and Sagan on Mobius functions of lattices. But it is easy to prove directly.

We need to show that, for any $w \neq e$ in $W$, we have $$\sum_{v \leq w} \lambda(v) =0 \qquad (\ast)$$ where $\lambda$ is defined by the recipe in the first paragraph. Letfinite lattice $A$$L$ can be $\{ s \in S : s \leq w \}$computed by Rota's crosscut theorem. Since $w \neq e$, we have(The first online reference I could find was $\#(A) \geq 1$Theorem 1.3 here. Also) Namely, since $w$ is an upper bound forlet $A$, be the join $s_1 \vee \cdots \vee s_j$ exists for any subset $\{ s_1,\cdots, s_j \}$set of minimal elements of $A$$L$ -- in this case, and we havethis is the set $s_1 \vee \cdots \vee s_j \leq w$ for any such subset$S$. Then $$\mu(x) = \sum_{B \subseteq A,\ \bigvee B = x} (-1)^{|B|}.$$

On the other hand, ifSo $v = s_1 \vee \cdots \vee s_j$ for some subset$\mu(w)=0$ if $\{ s_1,\cdots, s_j \}$$w$ is not contained ina join of elements of $S$, I claim that $v \not \leq w$. Indeed, if $s_k \not\in A$, thenIf $v \geq s_k$ and$w$ is a join of elements of $w \not\geq s_k$$S$, then it is so $v \not\leq w$.

So the nonzero terms in only one way $(\ast)$ exactly come(this is a way that weak order is simpler than a general lattice) so we get the description from $v$ of the form $s_1 \vee \cdots \vee s_j$ for $\{ s_1,\cdots, s_j \} \subseteq A$. So $(\ast)$ is $\sum_{B \subseteq A} (-1)^{\#(B)} = \sum_{b=0}^{\#(A)} \binom{a}{b} (-1)^b = 0$first paragraph.

The answer is yes. I claim there are at most $2^n$ elements of $W$ for which $\lambda(w) \neq 0$. Specifically, let $\vee$ be the join in weak order, which is a semi-lattice. If $\{ s_1, s_2, \ldots, s_j \} \subseteq S$ and $s_1 \vee s_2 \vee \cdots \vee s_j$ is defined, then I claim that $\lambda(s_1 \vee s_2 \vee \cdots \vee s_j)=(-1)^j$, and otherwise I claim that $\lambda(w)=0$. Thus $N$ can be taken to be the greatest length of $s_1 \vee s_2 \vee \cdots \vee s_j$, restricting ourselves to cases where this join is defined.

The condition $|v^{-1} w| = |w| - |v|$ says that $v \leq w$ in weak order. Therefore, this is the recursion defining the Mobius function of weak order. Mobius functions of lattices are well understood, and I extracted the result in the first paragraph from a paper of Blass and Sagan on Mobius functions of lattices. But it is easy to prove directly.

We need to show that, for any $w \neq e$ in $W$, we have $$\sum_{v \leq w} \lambda(v) =0 \qquad (\ast)$$ where $\lambda$ is defined by the recipe in the first paragraph. Let $A$ be $\{ s \in S : s \leq w \}$. Since $w \neq e$, we have $\#(A) \geq 1$. Also, since $w$ is an upper bound for $A$, the join $s_1 \vee \cdots \vee s_j$ exists for any subset $\{ s_1,\cdots, s_j \}$ of $A$, and we have $s_1 \vee \cdots \vee s_j \leq w$ for any such subset.

On the other hand, if $v = s_1 \vee \cdots \vee s_j$ for some subset $\{ s_1,\cdots, s_j \}$ not contained in $S$, I claim that $v \not \leq w$. Indeed, if $s_k \not\in A$, then $v \geq s_k$ and $w \not\geq s_k$, so $v \not\leq w$.

So the nonzero terms in $(\ast)$ exactly come from $v$ of the form $s_1 \vee \cdots \vee s_j$ for $\{ s_1,\cdots, s_j \} \subseteq A$. So $(\ast)$ is $\sum_{B \subseteq A} (-1)^{\#(B)} = \sum_{b=0}^{\#(A)} \binom{a}{b} (-1)^b = 0$.

The answer is yes. I claim there are at most $2^n$ elements of $W$ for which $\lambda(w) \neq 0$. Specifically, let $\vee$ be the join in weak order, which is a semi-lattice. If $\{ s_1, s_2, \ldots, s_j \} \subseteq S$ and $s_1 \vee s_2 \vee \cdots \vee s_j$ is defined, then I claim that $\lambda(s_1 \vee s_2 \vee \cdots \vee s_j)=(-1)^j$, and otherwise I claim that $\lambda(w)=0$. Thus $N$ can be taken to be the greatest length of $s_1 \vee s_2 \vee \cdots \vee s_j$, restricting ourselves to cases where this join is defined.

The condition $|v^{-1} w| = |w| - |v|$ says that $v \leq w$ in weak order. Therefore, this is the recursion defining the Mobius function of weak order. The Mobius function of a finite lattice $L$ can be computed by Rota's crosscut theorem. (The first online reference I could find was Theorem 1.3 here.) Namely, let $A$ be the set of minimal elements of $L$ -- in this case, this is the set $S$. Then $$\mu(x) = \sum_{B \subseteq A,\ \bigvee B = x} (-1)^{|B|}.$$

So $\mu(w)=0$ if $w$ is not a join of elements of $S$. If $w$ is a join of elements of $S$, then it is so in only one way (this is a way that weak order is simpler than a general lattice) so we get the description from the first paragraph.

Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

The answer is yes. I claim there are at most $2^n$ elements of $W$ for which $\lambda(w) \neq 0$. Specifically, let $\vee$ be the join in weak order, which is a semi-lattice. If $\{ s_1, s_2, \ldots, s_j \} \subseteq S$ and $s_1 \vee s_2 \vee \cdots \vee s_j$ is defined, then I claim that $\lambda(s_1 \vee s_2 \vee \cdots \vee s_j)=(-1)^j$, and otherwise I claim that $\lambda(w)=0$. Thus $N$ can be taken to be the greatest length of $s_1 \vee s_2 \vee \cdots \vee s_j$, restricting ourselves to cases where this join is defined.

The condition $|v^{-1} w| = |w| - |v|$ says that $v \leq w$ in weak order. Therefore, this is the recursion defining the Mobius function of weak order. Mobius functions of lattices are well understood, and I extracted the result in the first paragraph from a paper of Blass and Sagan on Mobius functions of lattices. But it is easy to prove directly.

We need to show that, for any $w \neq e$ in $W$, we have $$\sum_{v \leq w} \lambda(v) =0 \qquad (\ast)$$ where $\lambda$ is defined by the recipe in the first paragraph. Let $A$ be $\{ s \in S : s \leq w \}$. Since $w \neq e$, we have $\#(A) \geq 1$. Also, since $w$ is an upper bound for $A$, the join $s_1 \vee \cdots \vee s_j$ exists for any subset $\{ s_1,\cdots, s_j \}$ of $A$, and we have $s_1 \vee \cdots \vee s_j \leq w$ for any such subset.

On the other hand, if $v = s_1 \vee \cdots \vee s_j$ for some subset $\{ s_1,\cdots, s_j \}$ not contained in $S$, I claim that $v \not \leq w$. Indeed, if $s_k \not\in A$, then $v \geq s_k$ and $w \not\geq s_k$, so $v \not\leq w$.

So the nonzero terms in $(\ast)$ exactly come from $v$ of the form $s_1 \vee \cdots \vee s_j$ for $\{ s_1,\cdots, s_j \} \subseteq A$. So $(\ast)$ is $\sum_{B \subseteq A} (-1)^{\#(B)} = \sum_{b=0}^{\#(A)} \binom{a}{b} (-1)^b = 0$.