5
$\begingroup$

Background. Let $n$ be a nonnegative integer, and let $S_n$ denote the $n$-th symmetric group. The $0$-Hecke monoid $H_0\left(S_n\right)$ is defined to be the monoid given by generators $t_1, t_2, \ldots, t_{n-1}$ and relations

  • $t_i^2 = t_i$ for every $i \in \left\{1, 2, \ldots, n-1\right\}$;

  • $t_i t_{i+1} t_i = t_{i+1} t_i t_{i+1}$ for every $i \in \left\{1, 2, \ldots, n-2\right\}$;

  • $t_i t_j = t_j t_i$ for every $i$ and $j$ in $\left\{1, 2, \ldots, n-1\right\}$ satisfying $\left|i-j\right| > 1$.

(This is a particular case of a more general construction -- that of the $0$-Hecke monoid of a Coxeter group --; but I want to focus on the symmetric group.)

The monoid $H_0\left(S_n\right)$ has cardinality $n!$. More precisely, for every permutation $w \in S_n$, we can define an element $t_w$ of $H_0\left(S_n\right)$ by setting

$t_w = t_{i_1} t_{i_2} \cdots t_{i_k}$, where $\left(i_1, i_2, \ldots, i_k\right)$ is a reduced word for $w$ in $S_n$.

This element $t_w$ does not depend on the choice of the reduced word. The family $\left(t_w\right)_{w \in S_n}$ contains each element of $H_0\left(S_n\right)$ exactly once. Thus, we can define a monoid structure $\left(S_n, *\right)$ on the set $S_n$ as follows: For any $a \in S_n$ and $b \in S_n$, define $a * b$ to be the unique element of $S_n$ satisfying $t_{a * b} = t_a t_b$. Then, $\left(S_n, *\right)$ is an isomorphic copy of the $0$-Hecke monoid $H_0\left(S_n\right)$ whose elements are those of $S_n$. It has various interesting properties, which are spread across the literature (apparently very popular as exercises).

Question. Is there an equivalent definition of $*$ that is "synthetic", i.e., does not use the decomposition of a permutation into adjacent transpositions? (My intuition for $a * b$ is something along the lines of "the join of $a$ and $b$ on the Bruhat order lattice, if one squints hard enough to forget that the Bruhat order is not a lattice and that $*$ is not commutative".)

Motivation. For comparison, here is a similar object where the answer is "Yes". We define a zeroed monoid to be a monoid $M$ with a specified element $0$ which satisfies $0m = m0 = 0$ for every $m \in M$. We can define the nilCoxeter monoid $C_0\left(S_n\right)$ to be the monoid given by generators $u_1, u_2, \ldots, u_{n-1}, 0$ and relations

  • $0 u_i = u_i 0 = 0$ for every $i \in \left\{1, 2, \ldots, n-1\right\}$;

  • $u_i^2 = 0$ for every $i \in \left\{1, 2, \ldots, n-1\right\}$;

  • $u_i u_{i+1} u_i = u_{i+1} u_i u_{i+1}$ for every $i \in \left\{1, 2, \ldots, n-2\right\}$;

  • $u_i u_j = u_j u_i$ for every $i$ and $j$ in $\left\{1, 2, \ldots, n-1\right\}$ satisfying $\left|i-j\right| > 1$.

Similar results as for $H_0\left(S_n\right)$ hold; in particular, we can define a $u_w \in C_0\left(S_n\right)$ for every $w \in S_n$, and the family $\left(u_w\right)_{w \in S_n}$ contains each element of $C_0\left(S_n\right) \setminus \left\{0\right\}$ exactly once. We can again transfer this zeroed monoid structure onto the set $S_n \cup \left\{0\right\}$; in other words, we can define a binary operation $\sharp$ on $S_n \cup \left\{0\right\}$ by $u_{a \sharp b} = u_a u_b$ for all $a, b \in S_n \cup \left\{0\right\}$ (where I set $u_0 = 0$). But this multiplication $\sharp$ can be described without using reduced words: Namely, for any $a \in S_n$ and $b \in S_n$, we have

$a \sharp b = \begin{cases} ab, & \text{ if } \ell\left(ab\right) = \ell\left(a\right) + \ell\left(b\right); \\ 0, & \text{ otherwise} \end{cases}$,

where $\ell\left(w\right)$ means the Coxeter length of a permutation of $w$ (that is, the number of inversions of $w$). Of course, the Coxeter length of a permutation $w$ is the length of any reduced expression of $w$, but it can also be defined as the number of inversions of $w$, which does not rely on the representation of a permutation as composition of adjacent transpositions. I am looking for a similar description for the $0$-Hecke monoid.

(Note: None of the results above is mine, but it is hard to find proofs for them in the literature, so I don't even know whom to cite.)

$\endgroup$
2
  • $\begingroup$ Would this mathoverflow question: Is the following construction of the 0-Hecke monoid (well) known? be relevant? $\endgroup$ Commented Aug 26, 2015 at 14:18
  • $\begingroup$ @JEPin: Thank you! This is what I was looking for (although a proof would be much preferred). Care to make it an answer? $\endgroup$ Commented Aug 26, 2015 at 14:58

2 Answers 2

3
+200
$\begingroup$

Monoid H_0(S_n) can be defined as a monoid of permutation matrices under a special kind of multiplication, or equivalently of special integer matrices (unit-Monge matrices) under standard tropical multiplication. See my paper for details: https://doi.org/10.1007/s00453-013-9830-z

I am curious about your remark that the monoid's properties are popular as exercises: do you have any examples of those?

$\endgroup$
5
  • $\begingroup$ Wow, this is a nice and completely unexpected interpretation! Am I reading you right (reading between the lines, as I think you only say explicitly where the generators are mapped to) that if $a$ and $b$ are two permutations in $S_n$, and if $i, j \in \left\{0,1,\ldots,n\right\}$, then $\ell_{i,j}\left(a*b\right) = \min\limits_{k \in \left\{0,1,\ldots,n\right\}}\left(\ell_{i,k}\left(a\right) + \ell_{k,j}\left(b\right)\right)$, where $\ell_{i,j}\left(w\right)$ denotes the number of all $p \in \left\{1,2,\ldots,j\right\}$ satisfying $w\left(p\right) \geq i$ ? $\endgroup$ Commented May 22, 2020 at 10:18
  • $\begingroup$ As to the exercises, I believe I meant that everyone who uses the properties tend to leave them as exercises. I don't remember the details any more (I think I was reading Hivert/Schilling/Thiéry in particular). $\endgroup$ Commented May 22, 2020 at 10:22
  • $\begingroup$ (Correction: Read "$w\left(p\right) > i$" for "$w\left(p\right) \geq i$" in my first comment.) $\endgroup$ Commented May 22, 2020 at 13:51
  • $\begingroup$ Okay, whether or not I was reading you right, my claim is true (I've just proved it by checking that it holds whenever $b = s_u$ for some $u \in \left\{1,2,\ldots,u-1\right\}$, and then leveraging associativity of the tropical matrix product and of the $0$-Hecke $*$ product to conclude that it holds for all $a$ and $b$). What a nice result! $\endgroup$ Commented May 22, 2020 at 14:19
  • $\begingroup$ This seems related to Proposition 3.2 in Z. Hamaker and V. Reiner, Weak order and descents for monotone triangles, European Journal of Combinatorics (2020) 103083 (arXiv:1809.10571v2). Could the standard embedding of the symmetric group $S_n$ into $\operatorname{MT}_n$ (by treating each permutation matrix as an ASM, and sending it to the corresponding monotone triangle) be $H_n\left(0\right)$-equivariant, where the action of $H_n\left(0\right)$ on $S_n$ is via the $0$-Hecke product? $\endgroup$ Commented May 22, 2020 at 19:34
1
$\begingroup$

Comment converted to an answer on OP's suggestion.

This mathoverflow question: Is the following construction of the 0-Hecke monoid (well) known? might be relevant to your question.

Let me also mention two possibly relevant references On the representation theory of finite J-trivial monoids by Tom Denton, Florent Hivert, Anne Schilling, Nicolas M. Thiéry

A Combinatorial Formula for Orthogonal Idempotents in the $0$-Hecke Algebra of the Symmetric Group by Tom Denton

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.