Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Let $P_n$ be group of all permutations of the set $\{1,\dots,n\}$. I have trouble with construction a Lipschitz function $f:P_n \longrightarrow R$.

Any help would be appreciate.

Thank you.

share|cite|improve this question
Which metric do you put on $P_n$? – Davide Giraudo Mar 10 '12 at 22:36
The metric is the following: $d_n(p_1, p_2)=\frac 1n \#\{i:p_1(i)\neq p_2(i), \quad p_1, p_2 \in P_n\}$. – Michael Mar 10 '12 at 22:47
how about a constant function? I don't really understand point of question though as $P_n$ is finite. – ShawnD Mar 10 '12 at 23:01
up vote 2 down vote accepted

Every function $f$ on a finite metric space $(X,d)$ is Lipschitz.

To wit, call $D$ the minimal distance between distinct points of $X$, and $M$ the diameter of the range of $f$, that is, the maximal difference between the images by $f$ of different points of $X$.

Then, $|f(x)-f(y)|\leqslant (M/D)d(x,y)$ for every $x$ and $y$ in $X$ hence $f$ is Lipschitz on $X$ with constant $M/D$.

share|cite|improve this answer

$d_n$ is indeed a metric, and we know that if $(X,d)$ is a metric space, for each $x_0\in X$ the map $x\mapsto d(x,x_0)$ is Lipschitz of constant $1$ (it's a consequence of triangular inequality). So for example you can take $f(\sigma):=\frac 1n\operatorname{card}(i:\sigma(i)\neq i)$, or for a fixed permutation $\sigma_0$: $$f_{\sigma_0}(\sigma)=\frac 1n\operatorname{card}(i:\sigma(i)\neq \sigma_0(i)).$$

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.