7
$\begingroup$

Generate $S_n$ by transpositions $s_i$ of (i) and (i+1). Both $S_3$ and $S_4$ have single elements of maximal word norm associated with this presentation. In fact, the Cayley graph of $S_3$ can be seen as a tiling of $S^1$, and the Cayley graph of $S_4$ a tiling of $S^2$. The element of maximal length is then antipodal to e.

Does every symmetric group $S_n$ have a single element of maximal word norm? If so, is there a formula for its length l(n)?

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answers. All are helpful - both the basic proof and bigger theory. $\endgroup$
    – ian
    Dec 14, 2010 at 14:57

5 Answers 5

33
$\begingroup$

It is amazing how a fact that I was taught in a middle school can be proved using big theories where I don't understand half of the words. Let me add a straightforward proof (for $S_n$ and only $S_n$).

For a permutation $\sigma:\{1,\dots,n\}\to\{1,\dots,n\}$, let $\lambda(\sigma)$ denote the number of inversions in $\sigma$, that is the number of pairs $(i,j)$ such that $i<j$ and $\sigma(i)>\sigma(j)$. Then $\lambda(\sigma)$ equals the length of $\sigma$ with respect to the generating set $\{s_i\}$.

Indeed, left-multiplying $\sigma$ by $s_i$ only interchanges $\sigma(i)$ and $\sigma(i+1)$, and hence changes $\lambda(\sigma)$ by at most 1. Therefore the length is bounded below by $\lambda$. On the other hand, if $\sigma$ is not the identity, there exists $i$ such that $\sigma(i+1)<\sigma(i)$, then left-multiplying by $s_i$ decreases $\lambda(\sigma)$ by 1. Repeating this procedure, one reaches the identity from $\sigma$ by exactly $\lambda(\sigma)$ multiplications by generators.

Now it is clear that the maximum length equals $n(n-1)/2$ and is attained only at the order reversing permutation (the one given by $\sigma(i)=n+1-i$ for all $i$).

$\endgroup$
2
  • 2
    $\begingroup$ +1 for the first sentence :) $\endgroup$
    – JBL
    Dec 14, 2010 at 12:40
  • 4
    $\begingroup$ To combine with Qiaochu's answer: inversions $\sigma(i)>\sigma(j)$ correspond to flipped roots $e_i-e_j$. So the proof here extends easily to other root systems with their own notion of inversions, e.g. for the group of signed permutations. $\endgroup$ Dec 14, 2010 at 19:06
8
$\begingroup$

Yes; this is known as the longest element, and it exists and is unique for every finite Coxeter group (including the ones which do not arise as Weyl groups). The length of the longest element is the number of positive roots in the corresponding root system; here that number is ${n \choose 2}$. A standard reference here is Humphreys' Reflection groups and Coxeter groups; Proposition 5.6b is relevant, and this is the content of Exercise 2 in that section.

To be more explicit (and to explain Tobias' answer), specialized to symmetric groups Proposition 5.6b says the following: let $S_n$ act on the orthogonal complement of the all-ones vector in $\mathbb{R}^n$ in the obvious way. This complement is spanned by elements of the form $e_i - e_j, 1 \le i \neq j \le n$; a choice of positive roots for the corresponding root system can be obtained by considering the elements with $i > j$, of which there are ${n \choose 2}$. Then the length of $w \in S_n$ is the number of positive roots $e_i - e_j$ sent to their negatives $e_j - e_i$ (which, one readily verifies, is the number of inversions in $w$). And there is a unique permutation that does this to every positive root: just send $k$ to $n + 1 - k$.

One way to interpret this result is that the length of an element $w \in S_n$ (with its usual Coxeter system) is the least number of steps required to sort the word $w_1 w_2 ... w_n$ using bubblesort, and of course the word $n (n-1) (n-2) ... 3 2 1$ takes ${n \choose 2}$ steps to sort and is maximal (since $n$ is moved $n-1$ times, $n-1$ is moved $n-2$ times, etc.)

$\endgroup$
1
  • $\begingroup$ The bit "...their negatives $e_j - e_i$..." is wrong above. It should just be "negative roots," but this seems like too minor an edit to bump for. $\endgroup$ Nov 20, 2013 at 7:31
7
$\begingroup$

The Cayley graph of $S_n$ is the skeleton of the Permutahedron of order $n$. This polytope is the Minkowski sum of the $\frac{n(n-1)}{2}$ segments connecting pairs of the standard basis vectors. You can now visualize that the element of maximal length is antipodal to the identity vertex and has length exactly $\frac{n(n-1)}{2}$.

$\endgroup$
1
  • 1
    $\begingroup$ Note that this is just a response to the observation that the Cayley graph of $S_n$ looks like $S^n$, the simplest proof is given by Sergei Ivanov in the other answer. $\endgroup$ Dec 14, 2010 at 9:51
6
$\begingroup$

A more explicit version of Qiaochu's answer : $S_n$ can be viewed as a Coxeter group of type $A_{n-1}$. The maximal length is $\frac{n(n-1)}{2}$, achieved by the element $$s_1(s_2s_1)(s_3s_2s_1) \ldots (s_{n-1}s_{n-2} \ldots s_2s_1)$$.

This is a classical result in Coxeter groups theory. Sketch of the proof : for each $i \in [1,n-1]$ let $G_i$ be the so-called parabolic subgroup generated by $T_i=\lbrace s_1,s_2, \ldots ,s_n \rbrace $. For any $w\in G_k (1 \leq k \leq n-1)$ we can write $w=w_1w_2w_3 \ldots w_r$ where each $w_i \in T_k$ and $r$ is minimal. Among all those decompositions, we choose the one with as many generators in $T_{k-1}$ on the left as possible. This shows that $w$ can be written $w=w'x$, with $w'\in G_{k-1}$, and $x\in X_k$ where $X_k$ consists of the element $x\in G_k$ all of whose minimal decompositions start with $s_k$.

It is not hard to show that the pair $(w',x)$ is unique (this is because $G_{k-1}$ and $X_k$ are disjoint) and trivially we have $l(w)=l(w')+l(x)$. By induction, any $w\in S_n$ can be written uniquely $w=x_1x_2 \ldots x_n$, where each $x_i$ is in $X_i$, and furthermore $l(w)=l(x_1)+l(x_2)+ \ldots +l(x_n)$.

Now, when the group is $S_n$ it is a straightforward exercise to show that $$X_k=\lbrace s_{k},s_{k}s_{k-1}, \ldots, s_{k}s_{k-1} \ldots s_{2}s_{1} \rbrace$$ for any $k$. Therefore $X_k$ has a unique element of maximal length, $\xi_k=s_{k}s_{k-1} \ldots s_{2}s_{1}$, and we deduce that $S_n$ has a unique element of maximal length which is the product $\xi_1\xi_2 \ldots \xi_{n-1}$.

$\endgroup$
4
$\begingroup$

Yes, all $S_n$ have a unique longest element. One way to see this is that $S_n$ is the Weyl-group of the simple Lie algebra of type $A_{l-1}$, and here the length can be characterized by fixing a set of simple roots (and thus of positive roots). The length is then the number of positive roots that are sent to negative roots. The unique longest element is then the one that sends each simple root to its negative (the product of the simple reflections corresponding to each simple root)

$\endgroup$

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.