Let $w_0$ be the unique longest element in $W=S_n$. Let us show that $$l(ww_0)=l(w_0)-l(w)$$ for any $w \in W$.
We proceed by induction on $l(w)$. First, let $S$ be the generating set for $W$. In the case where $l(w)=1$, we must have $w=s \in S$. So $l(ww_0)=l(w_0)\pm 1$. By maximality of $l(w_0)$, it follows that $l(ww_0)=l(w_0)-1$.
Now assume that $l(w) > 1$ and that the induction hypothesis holds for all $w' \in W$ with $l(w') < l(w)$. Since $l(w) > 1$, it follows that $w=sw'$, for some $w' \in S_n$ with $l(w)=l(w')+1$. Let $s_{1} \cdots s_k$ be a reduced expression for $w'$. Then we claim that $$ww_0=w's_kw_0.$$ This is because
$$ww_0=(sw')w_0=ss_1\cdots s_kw_0=(ss_1\cdots s_{k-1})(s_kw_0).$$
Since $(ss_1\cdots s_{k-1})$ is an expression of length $k$, it is a reduced expression for $w'$, so $ww_0=w's_kw_0.$ I don't know how to proceed. How can I argue that $s$ decreases the length of $w'w_0$ by $1$?
Also, to show that $w_0 = (1 \;\; n)(2\;\; n-1)\cdots (\lfloor n/2 \rfloor \;\; \lceil n/2 \rceil +1) \in S_n$, is the following possible? Show that for any element $w \in S_n$, the reduced expression for $w$ is contained in the reduced expression for $w_0$, so $l(w_0) \geq l(w)$.
Please note, if these are wrong approaches, it would appreciate comments on where I went wrong and hints rather than a correct solution, as I would like to write the proof myself. Thanks.
Best Answer
This proof works for any finite Coxeter group $W$ generated by the set $S$ of simple reflections (whence $W$ has the unique longest element $w_0$). We need the following ingredients for the proof:
Let $w\in W$ be arbitrary. Note that $w_0=w^{-1}(ww_0)$. Consequently, $$l(w_0)\leq l(w^{-1})+l(ww_0)\,.$$ Because $l(w^{-1})=l(w)$, we obtain $$l(ww_0)\geq l(w_0)-l(w^{-1})=l(w_0)-l(w)\,.$$
Now, we shall prove $l(ww_0)\leq l(w_0)-l(w)$ by induction on $k:=l(w_0)-l(w)$. If $k=0$, then $w=w_0$ and so $ww_0=w_0^2=1_W$. That is, $$l(ww_0)=l(1_W)=0=l(w_0)-l(w_0)=l(w_0)-l(w)=k\,.$$ Suppose now that $w\neq w_0$ and $k=l(w_0)-l(w)>0$. There exists $s\in S$ such that $l(w)<l(sw)$. Define $w':=sw$. Hence, $l(w_0)-l(w')<l(w_0)-l(w)=k$. Therefore, from $ww_0=s^{-1}(sww_0)=s(w'w_0)$ (recalling that $s^2=1_W$), we get $$l(ww_0)\leq l(w'w_0)+l(s)=l(w'w_0)+1.$$ By induction hypothesis, $l(w'w_0)\leq l(w_0)-l(w')$. Note that $l(w')=l(w)+1$. Therefore, $$l(ww_0)\leq \big(l(w_0)-l(w')\big)+1=l(w_0)-\big(l(w')-1\big)=l(w_0)-l(w)=k\,.$$
From the results above, we conclude that $l(ww_0)=l(w_0)-l(w)$. On the other hand, $$l(w_0w)=l\big((w_0w)^{-1}\big)=l(w^{-1}w_0^{-1})\,.$$ Because $w_0^{-1}=w_0$, we get $$l(w_0w)=l(w^{-1}w_0)=l(w_0)-l(w^{-1})=l(w_0)-l(w)=l(ww_0)\,.$$
Now, let $W:=\mathfrak{S}_n$, which is generated by $$S:=\big\{(1\;\;2),(2\;\;3),\ldots,({n-1}\;\;n)\big\}\,.$$ We want to show that $w_0$ is the order-reversing permutation $w_0'$ given by $$(1,2,3,\ldots,n-2,n-1,n)\mapsto (n,n-1,n-2,\ldots,3,2,1)\,.$$
For each $w\in W$, let $L(w)$ be the number of pairs $(i,j)$ such that $i,j\in\{1,2,\ldots,n\}$, $i<j$, and $w(i)>w(j)$. Then, for $s\in S$, $$L(sw)=L(w)\pm 1\,.$$ If we pick $s:=(i\;\;i+1)$ where $i\in\{1,2,\ldots,n-1\}$ satisfies $w(i)>w(i+1)$, then $L(sw)=L(w)-1$. From this observation, any reduced expression for $w$ must have exactly $L(w)$ simple reflections. Therefore, $l(w)=L(w)$ for every $w\in W$.
This argument also proves that $\displaystyle l(w)=L(w)\leq \binom{n}{2}$ for all $w\in W$ (because there are precisely $\displaystyle \binom{n}{2}$ pairs $(i,j)$ such that $i,j\in\{1,2,\ldots,n\}$ and $i<j$, so at most $\displaystyle \binom{n}{2}$ such pairs also satisfy $w(i)>w(j)$). Particularly, because $L(w_0')=\displaystyle \binom{n}{2}$, this means $w_0=w_0'$ and $l(w_0)=\displaystyle \binom{n}{2}$.