# Best Lipschitz constant

I am trying to find the Lipschitz constant for the following function: $$f(\pi)=\left|\sum_{i=1}^{m}c_{\pi(i)}-\sum_{i=m+1}^{2m}c_{\pi(i)}\right|,$$ where $c_i \in R$ and $\pi$ is a permutation of the set $\{1,..., 2m\}$ with counting metric $\rho_{2m}=\#\{i: \pi_1(i)\neq \pi_2(i); \pi_1, \pi_2 \in S_{2m}\}$.

I've got Lipschitz constant $2\lVert c\rVert_{\infty}$. I am wondering if one can do something better?

-
What is the metric on $S_{2m}$? –  scineram Mar 26 '12 at 19:31
Sorry, I forgot to mention: the metric on the group of permutations is a counting metric:$\rho_{2m}=\#\{i: \pi_1\neq\pi_2\}$ –  Michael Mar 26 '12 at 20:08

## 1 Answer

It seems we can't do better. Consider the case $c_j=\begin{cases}1&\mbox{ if }1\leq j\leq m\\\ -1&\mbox{ if }m+1\leq j\leq 2m \end{cases}$. Then $\lVert c\rVert_{\infty}=1$, $f(\operatorname{Id})=2m$ and if we consider $\pi$ the transposition of $1$ and $m+1$ then $$f(\pi)=\left|c_{m+1}+\sum_{j=2}^mc_j-\sum_{j=m+2}^{2m}c_j-c_1\right|=|-1+m-1+(m-1)-1|=2m-4$$ so $|f(\operatorname{Id})-f(\pi)|=4=2\rho_{2m}(\operatorname{Id},\pi)\lVert c\rVert_{\infty}$.

-