Return to Answer

Example:

Take $n=4, k=4$. Four points are equidistributed on a $n-2 = 2$-sphere as the vertices of a tetrahedron. I would like to embed such an arrangement in a sphere lying in the trace-zero hyperplane $\sum x_i = 0$ in $\mathbb{R}^{n=4}$. I could take the vertices as $$(3,-1,-1,-1),(-1,3,-1,-1),(-1,-1,3,-1),(-1,-1,-1,3).$$ (There is no need to constrain them to be on the unit sphere because we can tell what chamber they end up in just from the order of the coordinates.)

Now the issue with these vertices is that they have lots of collisions between the coordinates, so they do not lie in the interiors of the Coxeter chambers. So I want to perturb the whole thing slightly with a small orthogonal transformation that preserves the trace-zero hyperplane. Doing this by hand: switching to column notation for $\mathbb{R}^4$, how about the transformation

$$ T = \begin{pmatrix}\cos \epsilon & -\sin \epsilon & & \\ \sin \epsilon & \cos \epsilon & & \\ & &1& \\ & & &1\end{pmatrix}$$

except with respect to the basis

$$B = \begin{pmatrix}1/2\\-1/2\\-1/2\\1/2\end{pmatrix},\; \begin{pmatrix}1/2\\-1/2\\1/2\\-1/2\end{pmatrix},\; \begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix},\; \begin{pmatrix}1/2\\1/2\\1/2\\1/2\end{pmatrix}$$

in order to preserve the trace-zero subspace. If my calculation is right we have $T' = BTB^{-1} = \frac{1}{2}\begin{pmatrix}\cos \epsilon + 1& -\cos \epsilon + 1 & -\sin \epsilon & \sin\epsilon \\ -\cos\epsilon + 1& \cos \epsilon + 1& \sin\epsilon & -\sin\epsilon\\ \sin\epsilon & -\sin \epsilon & \cos\epsilon + 1 & -\cos\epsilon + 1\\ -\sin\epsilon & \sin\epsilon & -\cos\epsilon + 1 & \cos\epsilon + 1\end{pmatrix}$

I have to multiply this matrix by the four points of the tetrahedron and observe the order of the coordinates. Since I am doing this by hand and thus looking for shortcuts, I observe that the four points each have the form $(-1,-1,-1,-1)^T + 4e_i$ for $i=1,2,3,4$, and $T'(-1,-1,-1,-1)^T = (-2,-2,-2,-2)^T$, thus the order of the coordinates of the $i$th point will simply be given by $T'e_i$, i.e. the $i$th column of $T'$. Since $\epsilon$ is supposed to be small positive, we have $-\sin\epsilon<0<1-\cos \epsilon < \sin \epsilon < 1 < 1 + \cos\epsilon$, and thus the four permutations (reading from greatest to least, because why not) are

1324, 3142, 4213, 2431

The Kendall tau distances are all at least 3. I believe this is optimal.

This is only a partial answer.

The problem is a discrete version of equidistributing $k$ points in an $n-2$-sphere. We see this as follows:

The pairwise Kendall tau distance between permutations $\pi$ and $\rho$ is the number of inversions of $\pi\rho^{-1}$, since $\pi(i)>\pi(j)$ while $\rho(i)<\rho(j)$ if and only if $\pi\rho^{-1}(i')>\pi\rho^{-1}(j')$ while $i'<j'$, by letting $i'=\rho(i),j'=\rho(j)$, and similarly for the reverse inequalities.

This in turn is equivalent to the distance in the graph metric for the Cayley graph of $S_n$ with transpositions of adjacent letters as generators.

Since $S_n$ is a Coxeter group of rank $n-1$ with these generators as Coxeter generators, this graph is the dual of the Coxeter complex, and therefore embeds regularly in an $n-2$-sphere. (One can think of this sphere as being the intersection of the unit sphere in $\mathbb{R}^n$ with the hyperplane $\sum x_i=0$. The Coxeter complex is the simplicial complex structure on this sphere given by intersecting it with all the hyperplanes $x_i=x_j$. The vertices of the Cayley graph could be taken to be the barycenters of the top-dimensional simplices, and the edges would link any two of these that are adjacent across one of the $x_i=x_j$ hyperplanes.) The graph distance is reasonably well approximated by the Riemannian distance in the sphere.

This is only a partial answer.

The problem is a discrete version of equidistributing $k$ points in an $n-2$-sphere. We see this as follows:

The pairwise Kendall tau distance between permutations $\pi$ and $\rho$ is the number of inversions of $\pi\rho^{-1}$, since $\pi(i)>\pi(j)$ while $\rho(i)<\rho(j)$ if and only if $\pi\rho^{-1}(i')>\pi\rho^{-1}(j')$ while $i'<j'$, by letting $i'=\rho(i),j'=\rho(j)$, and similarly for the reverse inequalities.

This in turn is equivalent to the distance in the graph metric for the Cayley graph of $S_n$ with transpositions of adjacent letters as generators.

Since $S_n$ is a Coxeter group of rank $n-1$ with these generators as Coxeter generators, this graph is the dual of the Coxeter complex, and therefore embeds regularly in an $n-2$-sphere. (One can think of this sphere as being the intersection of the unit sphere in $\mathbb{R}^n$ with the hyperplane $\sum x_i=0$. The Coxeter complex is the simplicial complex structure on this sphere given by intersecting it with all the hyperplanes $x_i=x_j$. The vertices of the Cayley graph could be taken to be the barycenters of the top-dimensional simplices, and the edges would link any two of these that are adjacent across one of the $x_i=x_j$ hyperplanes.) The graph distance is reasonably well approximated by the Riemannian distance in the sphere.

Addendum:

Actually I think this idea can be used to translate an optimal distribution of $k$ points on an $n-2$-sphere to a close-to-optimal distribution of permutations. (Not sure how close exactly, because of uncertainty about the relation between the Cayley graph distance and the Riemannian distance, but I'd be surprised if it wasn't quite close.)

For this I think it's easiest to forget the Cayley graph and think about the Coxeter complex directly. Permutations biject with chambers of the Coxeter complex, and the distance is given by the minimum number of walls (hyperplanes $x_i=x_j$) crossed to get from one chamber to another. Just take an optimal distribution of $k$ points and isometrically embed it in the Coxeter complex so that each point is in a chamber (if any points hit walls, perturb the embedding slightly), and then just look at which chambers the points are in! If we use the description of the Coxeter complex given above, this is easy, because points of $\mathbb{R}^n$ minus all the hyperplanes $x_i=x_j$ have distinct coordinates, and are thus canonically associated to permutations by looking at the order of the coordinates.

This is only a partial answer.

The pairwise Kendall tau distance between permutations $\pi$ and $\rho$ is the number of inversions of $\pi\rho^{-1}$, since $\pi(i)>\pi(j)$ while $\rho(i)<\rho(j)$ if and only if $\pi\rho^{-1}(i')>\pi\rho^{-1}(j')$ while $i'<j'$, by letting $i'=\rho(i),j'=\rho(j)$, and similarly for the reverse inequalities.

This in turn is equivalent to the distance in the graph metric for the Cayley graph of $S_n$ with transpositions of adjacent letters as generators.

Since $S_n$ is a Coxeter group of rank $n-1$ with the transpositions of adjacent letters as Coxeter generators, this graph is the dual of the Coxeter complex, and therefore embeds regularly in an $n-2$-sphere. (One can think of this sphere as being the intersection of the unit sphere in $\mathbb{R}^n$ with the hyperplane $\sum x_i=0$. The Coxeter complex is the simplicial complex structure on this sphere given by intersecting it with all the hyperplanes $x_i=x_j$. The vertices of the Cayley graph could be taken to be the barycenters of the top-dimensional simplices, and the edges would link any two of these that are adjacent across one of the $x_i=x_j$ hyperplanes.) The graph distance is reasonably well approximated by the Riemannian distance in the sphere.

Thus the problem is a discrete version of equidistributing $k$ points in an $n-2$-sphere.

This is only a partial answer.

The problem is a discrete version of equidistributing $k$ points in an $n-2$-sphere. We see this as follows:

The pairwise Kendall tau distance between permutations $\pi$ and $\rho$ is the number of inversions of $\pi\rho^{-1}$, since $\pi(i)>\pi(j)$ while $\rho(i)<\rho(j)$ if and only if $\pi\rho^{-1}(i')>\pi\rho^{-1}(j')$ while $i'<j'$, by letting $i'=\rho(i),j'=\rho(j)$, and similarly for the reverse inequalities.

This in turn is equivalent to the distance in the graph metric for the Cayley graph of $S_n$ with transpositions of adjacent letters as generators.

Since $S_n$ is a Coxeter group of rank $n-1$ with these generators as Coxeter generators, this graph is the dual of the Coxeter complex, and therefore embeds regularly in an $n-2$-sphere. (One can think of this sphere as being the intersection of the unit sphere in $\mathbb{R}^n$ with the hyperplane $\sum x_i=0$. The Coxeter complex is the simplicial complex structure on this sphere given by intersecting it with all the hyperplanes $x_i=x_j$. The vertices of the Cayley graph could be taken to be the barycenters of the top-dimensional simplices, and the edges would link any two of these that are adjacent across one of the $x_i=x_j$ hyperplanes.) The graph distance is reasonably well approximated by the Riemannian distance in the sphere.