# construct a Lipschitz function

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.

-
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

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