Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

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

share|cite|improve this answer

Your Answer


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.