# Number of permutations differing in at least $d$ spots in pairwise comparisons

A friend and I were thinking about this problem today but we were unable to come up with a solution.

Problem:

Consider the the numbers $$S=\{1,\ldots,n\}$$. Given $$2\le d \le n$$ what is the maximal number of permutations $$p(d)$$ of $$S$$ you can choose such that the following holds: Whenever you compare two chosen permutations, they differ in at least $$d$$ spots?

Note that we always have $$2\le d\le n$$ since two permutations cannot differ in exactly one spot.

Note also that $$n\le p(d)\le n!$$ for all $$d:$$ $$p$$ is non-increasing and for $$d=n$$ one can choose the natural order first and proceed cyclically by writing $$\begin{matrix} 1 & 2 & \ldots & n-1 & n \\ 2 & 3 & \ldots & n & 1 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ n & 1 & \ldots & n-2 & n-1 \\ \end{matrix}$$ so that $$p(n) \ge n.$$ Actually $$p(n)=n$$ since when writing the $$n$$ permutations differing in $$n$$ spots in pairwise comparisons into the rows of a matrix, the first column will contain all $$n$$ numbers. Thus it is not possible to add a row to the matrix that differs from all previous rows at the first index.

Example: for $$n=3$$ all possible permutations are: $$\begin{matrix} 1 & 2 & 3\\ 1 & 3 & 2\\ 2 & 1 & 3\\ 2 & 3 & 1\\ 3 & 1 & 2\\ 3 & 2 & 1 \end{matrix}$$ For $$d=3$$ we get $$p(d) = 3$$ since $$n=3,$$ by the reasoning outlines above, and for $$d=2$$ we get $$p(d) = 6$$ since all distinct permutations differ in at least two spots.

You are looking for size of permutation code with Hamming distance. I have found a two years old survey of it - http://www.math.uvic.ca/~dukes/pc-talk.pdf. Most problems are open - for example, even sizes for $$n = 7, d = 4$$ and $$n = 7, d = 5$$ are unknown.
• Do you understand why slide 44 says "Theorem $M(n,4) = (n-1)!$" when the penultimate slide says $343 \le M(7, 4) \le 535$? – Peter Taylor Apr 24 at 13:49
• I suspect it's a typo and should be $M(n, 4) \leqslant (n - 1)!$, as the "proof idea" speaks about upper bound, and then there is a better bound $\frac{n!}{n+2}$ for square $n$. – mihaild Apr 24 at 14:30