Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)?

share|improve this question
1  
Thanks for the answers. All are helpful - both the basic proof and bigger theory. –  ian Dec 14 '10 at 14:57
add comment

5 Answers 5

up vote 23 down vote accepted

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$).

share|improve this answer
2  
+1 for the first sentence :) –  JBL Dec 14 '10 at 12:40
3  
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. –  Allen Knutson Dec 14 '10 at 19:06
add comment

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.)

share|improve this answer
    
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. –  Qiaochu Yuan Nov 20 '13 at 7:31
add comment

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}$.

share|improve this answer
1  
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. –  Gjergji Zaimi Dec 14 '10 at 9:51
add comment

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)

share|improve this answer
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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