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