Skip to main content
define right ascents too
Source Link
darij grinberg
  • 33.8k
  • 4
  • 117
  • 253

Lemma 2: Let $u \leq w$ in Bruhat order, and let $s$ be a right ascent of $w$. (Here, a right ascent of an element $v \in W$ means a $t \in S$ satisfying $vt > v$.) Then $us \leq ws$.

We have $Q \setminus t_m$ is a subword of $T'$ so $\prod Q\setminus t_m \leq Dem(T')$$\prod \left(Q\setminus t_m\right) \leq Dem(T')$ by induction.

Lemma 2: Let $u \leq w$ in Bruhat order, and let $s$ be a right ascent of $w$. Then $us \leq ws$.

We have $Q \setminus t_m$ is a subword of $T'$ so $\prod Q\setminus t_m \leq Dem(T')$ by induction.

Lemma 2: Let $u \leq w$ in Bruhat order, and let $s$ be a right ascent of $w$. (Here, a right ascent of an element $v \in W$ means a $t \in S$ satisfying $vt > v$.) Then $us \leq ws$.

We have $Q \setminus t_m$ is a subword of $T'$ so $\prod \left(Q\setminus t_m\right) \leq Dem(T')$ by induction.

1) fix inequality (strict < fails for u = ws); 2) define right descents (not sure if everyone is on the same page on this notion); 3) the set, not the family (else, "unique" would be false, I believe)
Source Link
darij grinberg
  • 33.8k
  • 4
  • 117
  • 253

Claim: $Dem(T)$ is the unique Bruhat maximal element in the set $\big\{ \prod Q : Q \subseteq T\big\}$ (where $Q\subseteq T $$Q\subseteq T$ means that $Q $$Q$ is a subsequence of $T $$T$, and where $\prod Q $$\prod Q$ means the product of the entries of $Q $$Q$ in the order in which they appear in $Q$).

Proof of corollary: $T'$ is obtained from $T$ by replacIngreplacing a consecutive substring $x = stst\ldots$ of length $m(s,t)$ by $y = tsts\ldots$. For any subword $Q$ of $T$, one can now choose the same subword in $T′$ as long as $Q$ does not contain all of $x$. But if this is the case, one can choose the subword $Q'$ of $T'$ where $Q'$ is obtained from $Q$ by using $y$ instead of $x$. $\square$

Lemma 1 (lifting property): Let $u < w$ in Bruhat order, and let $s$ be a right descent of $w$ but not of $u$. (Here, a right descent of an element $v \in W$ means a $t \in S$ satisfying $vt < v$.) Then $us < w$$us \leq w$.

(Proof in Björner-Brenti, at least for the analogous statement about left descents; apply it to $u^{-1}$ and $w^{-1}$.)

If $Dem(T) = Dem(T')$, we are in the situation of Lemma 1 and conclude $$\prod Q < Dem(T') = Dem(T). \quad \square$$$$\prod Q \leq Dem(T') = Dem(T). \quad \square$$

Claim: $Dem(T)$ is the unique Bruhat maximal element in $\big\{ \prod Q : Q \subseteq T\big\}$ (where $Q\subseteq T $ means that $Q $ is a subsequence of $T $, and where $\prod Q $ means the product of the entries of $Q $).

Proof of corollary: $T'$ is obtained from $T$ by replacIng a consecutive substring $x = stst\ldots$ of length $m(s,t)$ by $y = tsts\ldots$. For any subword $Q$ of $T$, one can now choose the same subword in $T′$ as long as $Q$ does not contain all of $x$. But if this is the case, one can choose the subword $Q'$ of $T'$ where $Q'$ is obtained from $Q$ by using $y$ instead of $x$. $\square$

Lemma 1 (lifting property): Let $u < w$ in Bruhat order, and let $s$ be a right descent of $w$ but not of $u$. Then $us < w$.

(Proof in Björner-Brenti.)

If $Dem(T) = Dem(T')$, we are in the situation of Lemma 1 and conclude $$\prod Q < Dem(T') = Dem(T). \quad \square$$

Claim: $Dem(T)$ is the unique Bruhat maximal element in the set $\big\{ \prod Q : Q \subseteq T\big\}$ (where $Q\subseteq T$ means that $Q$ is a subsequence of $T$, and where $\prod Q$ means the product of the entries of $Q$ in the order in which they appear in $Q$).

Proof of corollary: $T'$ is obtained from $T$ by replacing a consecutive substring $x = stst\ldots$ of length $m(s,t)$ by $y = tsts\ldots$. For any subword $Q$ of $T$, one can now choose the same subword in $T′$ as long as $Q$ does not contain all of $x$. But if this is the case, one can choose the subword $Q'$ of $T'$ where $Q'$ is obtained from $Q$ by using $y$ instead of $x$. $\square$

Lemma 1 (lifting property): Let $u < w$ in Bruhat order, and let $s$ be a right descent of $w$ but not of $u$. (Here, a right descent of an element $v \in W$ means a $t \in S$ satisfying $vt < v$.) Then $us \leq w$.

(Proof in Björner-Brenti, at least for the analogous statement about left descents; apply it to $u^{-1}$ and $w^{-1}$.)

If $Dem(T) = Dem(T')$, we are in the situation of Lemma 1 and conclude $$\prod Q \leq Dem(T') = Dem(T). \quad \square$$

added 134 characters in body
Source Link
darij grinberg
  • 33.8k
  • 4
  • 117
  • 253

A complete combinatorial proof using Allen's comment:

Let $(W,S)$ be a Coxeter system, and let $Dem(T) \in W$ be the Demazure product or greedy product of a word $T$ in $S$.

Claim: $Dem(T)$ is the unique Bruhat maximal element in $\big\{ \prod Q : Q \subseteq T\big\}$ (where $Q\subseteq T $ means that $Q $ is a subsequence of $T $, and where $\prod Q $ means the product of the entries of $Q $).

The idea for the proof is to start with a subword $Q$ of $T$ and compare it with the subword $D$ of $T$ picked by the greedy product (you find the formal proof below). You scan through $Q$ from left to right and if you see a letter that is picked in $D$ but not in $Q$, you insert it into $Q$. If this goes up in Bruhat order, we are fine in doing so, and if you go down in Bruhat order, you find by the exchange condition a letter to its right that you can remove in exchange for the inserted letter. By this procedure, you only go up in Bruhat order and we are done.

Corollary: The Demazure product is well-defined in Artin groups. This is, let $T$ be a word of $S$ and let $T'$ be obtained from $T$ by a braid move. Then $Dem(T) = Dem(T')$.

Proof of corollary: $T'$ is obtained from $T$ by replacereplacIng a consecutive substring $x = stst\ldots$ of length $m(s,t)$ by $y = tsts\ldots$. For any subword $Q$ of $T$, one can now choose the same subword in $T′$ *asas long as $Q$ does not contain all of $x$. But if this is the case, one can choose the subword $Q'$ of $T'$ where $Q'$ is obtained from $Q$ by using $y$ instead of $x$. $\square$

Proof of Claim: This is a consequence of the following lifting property in Bruhat order as described in Proposition 2.2.7 of Björner-Brenti's Combinatorics of Coxeter groups

Lemma 1 (lifting property): Let $u < w$ in Bruhat order, and let $s$ be a right descent of $w$ but not of $u$. Then $us < w$.

(Proof in Björner-Brenti.)

Lemma 2: Let $u \leq w$ in Bruhat order, and let $s$ be a right ascent of $w$. Then $us \leq ws$.

Proof: Since $u \leq w$, we have that a reduced expression $a$ for $u$ which is a subword of a reduced expression $b$ for $w$. But since now $bs$ is a reduced expression for $ws$, it contains the expression $as$ (which might or might not be reduced) and we are done. $\square$

Final induction to prove the Claim: Let $T = t_1\cdots t_m$. The case $m \in \{0,1\}$ is trivial, so assume $m>1$, let $T' = t_1\cdots t_{m-1}$ and we know that $Dem(T')$ is the unique Bruhat maximal element in $\{ \prod Q : Q \subseteq T'\}$.

Let $Q$ be a subword of $T$. If $Q$ is a subword of $T'$ we are done since by assumption $\prod Q \leq Dem(T') \leq Dem(T)$, so we only treat the case that $Q$ uses the last letter $t_m$.

We have $Q \setminus t_m$ is a subword of $T'$ so $\prod Q\setminus t_m \leq Dem(T')$ by induction.

If $Dem(T) > Dem(T')$, we are in the situation of Lemma 2 and conclude $$\prod Q \leq Dem(T') \cdot t_m = Dem(T).$$

If $Dem(T) = Dem(T')$, we are in the situation of Lemma 1 and conclude $$\prod Q < Dem(T') = Dem(T). \quad \square$$

(As usual with MO proofs, please let me know if something is unclear or plainly wrong.)

A complete combinatorial proof using Allen's comment:

Let $(W,S)$ be a Coxeter system, and let $Dem(T) \in W$ be the Demazure product or greedy product of a word $T$ in $S$.

Claim: $Dem(T)$ is the unique Bruhat maximal element in $\big\{ \prod Q : Q \subseteq T\big\}$.

The idea for the proof is to start with a subword $Q$ of $T$ and compare it with the subword $D$ of $T$ picked by the greedy product (you find the formal proof below). You scan through $Q$ from left to right and if you see a letter that is picked in $D$ but not in $Q$, you insert it into $Q$. If this goes up in Bruhat order, we are fine in doing so, and if you go down in Bruhat order, you find by the exchange condition a letter to its right that you can remove in exchange for the inserted letter. By this procedure, you only go up in Bruhat order and we are done.

Corollary: The Demazure product is well-defined in Artin groups. This is, let $T$ be a word of $S$ and let $T'$ be obtained from $T$ by a braid move. Then $Dem(T) = Dem(T')$.

Proof of corollary: $T'$ is obtained from $T$ by replace a consecutive substring $x = stst\ldots$ of length $m(s,t)$ by $y = tsts\ldots$. For any subword $Q$ of $T$, one can now choose the same subword in $T′$ *as long as $Q$ does not contain all of $x$. But if this is the case, one can choose the subword $Q'$ of $T'$ where $Q'$ is obtained from $Q$ by using $y$ instead of $x$. $\square$

Proof of Claim: This is a consequence of the following lifting property in Bruhat order as described in Proposition 2.2.7 of Björner-Brenti's Combinatorics of Coxeter groups

Lemma 1 (lifting property): Let $u < w$ in Bruhat order, and let $s$ be a right descent of $w$ but not of $u$. Then $us < w$.

(Proof in Björner-Brenti.)

Lemma 2: Let $u \leq w$ in Bruhat order, and let $s$ be a right ascent of $w$. Then $us \leq ws$.

Proof: Since $u \leq w$, we have that a reduced expression $a$ for $u$ which is a subword of a reduced expression $b$ for $w$. But since now $bs$ is a reduced expression for $ws$, it contains the expression $as$ (which might or might not be reduced) and we are done. $\square$

Final induction to prove the Claim: Let $T = t_1\cdots t_m$. The case $m \in \{0,1\}$ is trivial, so assume $m>1$, let $T' = t_1\cdots t_{m-1}$ and we know that $Dem(T')$ is the unique Bruhat maximal element in $\{ \prod Q : Q \subseteq T'\}$.

Let $Q$ be a subword of $T$. If $Q$ is a subword of $T'$ we are done since by assumption $\prod Q \leq Dem(T') \leq Dem(T)$, so we only treat the case that $Q$ uses the last letter $t_m$.

We have $Q \setminus t_m$ is a subword of $T'$ so $\prod Q\setminus t_m \leq Dem(T')$ by induction.

If $Dem(T) > Dem(T')$, we are in the situation of Lemma 2 and conclude $$\prod Q \leq Dem(T') \cdot t_m = Dem(T).$$

If $Dem(T) = Dem(T')$, we are in the situation of Lemma 1 and conclude $$\prod Q < Dem(T') = Dem(T). \quad \square$$

(As usual with MO proofs, please let me know if something is unclear or plainly wrong.)

A complete combinatorial proof using Allen's comment:

Let $(W,S)$ be a Coxeter system, and let $Dem(T) \in W$ be the Demazure product or greedy product of a word $T$ in $S$.

Claim: $Dem(T)$ is the unique Bruhat maximal element in $\big\{ \prod Q : Q \subseteq T\big\}$ (where $Q\subseteq T $ means that $Q $ is a subsequence of $T $, and where $\prod Q $ means the product of the entries of $Q $).

The idea for the proof is to start with a subword $Q$ of $T$ and compare it with the subword $D$ of $T$ picked by the greedy product (you find the formal proof below). You scan through $Q$ from left to right and if you see a letter that is picked in $D$ but not in $Q$, you insert it into $Q$. If this goes up in Bruhat order, we are fine in doing so, and if you go down in Bruhat order, you find by the exchange condition a letter to its right that you can remove in exchange for the inserted letter. By this procedure, you only go up in Bruhat order and we are done.

Corollary: The Demazure product is well-defined in Artin groups. This is, let $T$ be a word of $S$ and let $T'$ be obtained from $T$ by a braid move. Then $Dem(T) = Dem(T')$.

Proof of corollary: $T'$ is obtained from $T$ by replacIng a consecutive substring $x = stst\ldots$ of length $m(s,t)$ by $y = tsts\ldots$. For any subword $Q$ of $T$, one can now choose the same subword in $T′$ as long as $Q$ does not contain all of $x$. But if this is the case, one can choose the subword $Q'$ of $T'$ where $Q'$ is obtained from $Q$ by using $y$ instead of $x$. $\square$

Proof of Claim: This is a consequence of the following lifting property in Bruhat order as described in Proposition 2.2.7 of Björner-Brenti's Combinatorics of Coxeter groups

Lemma 1 (lifting property): Let $u < w$ in Bruhat order, and let $s$ be a right descent of $w$ but not of $u$. Then $us < w$.

(Proof in Björner-Brenti.)

Lemma 2: Let $u \leq w$ in Bruhat order, and let $s$ be a right ascent of $w$. Then $us \leq ws$.

Proof: Since $u \leq w$, we have that a reduced expression $a$ for $u$ which is a subword of a reduced expression $b$ for $w$. But since now $bs$ is a reduced expression for $ws$, it contains the expression $as$ (which might or might not be reduced) and we are done. $\square$

Final induction to prove the Claim: Let $T = t_1\cdots t_m$. The case $m \in \{0,1\}$ is trivial, so assume $m>1$, let $T' = t_1\cdots t_{m-1}$ and we know that $Dem(T')$ is the unique Bruhat maximal element in $\{ \prod Q : Q \subseteq T'\}$.

Let $Q$ be a subword of $T$. If $Q$ is a subword of $T'$ we are done since by assumption $\prod Q \leq Dem(T') \leq Dem(T)$, so we only treat the case that $Q$ uses the last letter $t_m$.

We have $Q \setminus t_m$ is a subword of $T'$ so $\prod Q\setminus t_m \leq Dem(T')$ by induction.

If $Dem(T) > Dem(T')$, we are in the situation of Lemma 2 and conclude $$\prod Q \leq Dem(T') \cdot t_m = Dem(T).$$

If $Dem(T) = Dem(T')$, we are in the situation of Lemma 1 and conclude $$\prod Q < Dem(T') = Dem(T). \quad \square$$

(As usual with MO proofs, please let me know if something is unclear or plainly wrong.)

added 68 characters in body
Source Link
Christian Stump
  • 3.3k
  • 1
  • 20
  • 29
Loading
reorganization
Source Link
Christian Stump
  • 3.3k
  • 1
  • 20
  • 29
Loading
Source Link
Christian Stump
  • 3.3k
  • 1
  • 20
  • 29
Loading