Does every symmetric group S_n have a single element of maximal word norm? 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)?
 A: 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.)  
A: 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}$.
A: 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}$.
A: 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)
A: 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$).
