# Relation between two permutation metrics

Consider the following two metrics on permutations of $$\{1,2,\dots,n\}$$:

$$d_{swap}(\sigma,\tau)$$ is the minimum number of swaps of adjacent elements that are required to reach $$\tau$$ from $$\sigma$$ (or $$\sigma$$ from $$\tau$$). Alternatively, it is the number of discordant pairs for $$\sigma$$ and $$\tau$$. A pair of distinct elements $$(x,y)$$ is called a discordant pair for $$\sigma$$ and $$\tau$$ if $$x$$ and $$y$$ have different relative orderings in the two permutations. If I am not missing anything, $$d_{swap}$$ is identical to the Kendell tau distance.

$$d_{sum}(\sigma, \tau)$$ is given by $$\sum_{i=1}^n |pos_{\sigma}(i) - pos_{\tau}(i)|$$, where $$pos_{\pi}$$ indicates the position of $$i$$ in the permutation $$\pi$$.

I need to understand the relationship between these two metrics for another problem I am working on. In particular, I would like to know whether the following two conjectures I have are true:

• $$d_{sum} \geq d_{swap}$$
• there exists a constant $$C < 1$$, such that $$d_{swap} \geq C \cdot d_{sum}$$

While I am sure that these distances have been well studied, I did not manage to find the answer to these questions. If you know the answer or even any relevant literature feel free to help me out :)

• Are your permutations in "line form" like if $n=4$ then $1432$ maps 1 and 3 to themselves and interchanges 2 and 4? [Or in cycle form or etc.] Nov 11, 2021 at 11:21
• They are in line form. Nov 11, 2021 at 11:25
• math.stackexchange.com/q/2492954 Nov 11, 2021 at 11:44
• I had found that post. It is interesting, but does not appear to address any of my questions. Nov 11, 2021 at 11:49
• About the first conjecture $d_{sum} \ge d_{swap}$: For which small $n$ have you checked it? E.g. checked for $n\le 10$. It seems a program could be made to check it, I wonder when the checking time gets unmanagably long in terms of $n$. [That likely depends on software used.] Nov 11, 2021 at 19:37

This problem was studied by Diaconis and Graham: Spearman's Footrule as a Measure of Disarray.

What you call $$d_{\text{swap}}$$ they call $$I$$, and what you call $$d_{\text{sum}}$$ they call $$D$$. They show

$$I + T \leq D \leq 2 I$$

where $$T$$ is the number of transpositions needed to put the permutation in order, also called the reflection-length of a permutation. This language comes from the study of Coxeter Groups.