Permutations that separate close elements

Abstract

Let $n$ be a fixed integer with $n\ge 2$. For $i,j\in {\mathbb{Z}}_n$, define $||i,j|{|}_n$ to be the distance between $i$ and $j$ when the elements of ${\mathbb{Z}}_n$ are written in a cycle. So $||i,j|{|}_n=\min \{(i-j)\mathrm{mod}n,(j-i)\mathrm{mod}n\}$. For positive integers $s$ and $k$, the permutation $\pi :{\mathbb{Z}}_n\to {\mathbb{Z}}_n$ is \emph{$(s,k)$-clash-free} if $||\pi (i),\pi (j)|{|}_n\ge k$ whenever $||i,j|{|}_n<s$ with $i\ne j$. So an $(s,k)$-clash-free permutation $\pi$ can be thought of as moving every close pair of elements of ${\mathbb{Z}}_n$ to a pair at large distance. More geometrically, the existence of an $(s,k)$-clash-free permutation is equivalent to the existence of a set of $n$ non-overlapping $s\times k$ rectangles on an $n\times n$ torus, whose centres have distinct integer $x$-coordinates and distinct integer $y$-coordinates. For positive integers $n$ and $k$ with $k<n$, let $\sigma (n,k)$ be the largest value of $s$ such that an $(s,k)$-clash-free permutation on ${\mathbb{Z}}_n$ exists. In a recent paper, Mammoliti and Simpson conjectured that \[ \lfloor (n-1)/k\rfloor-1\leq σ(n,k)\leq \lfloor (n-1)/k\rfloor \] for all integers $n$ and $k$ with $k<n$. The paper establishes this conjecture, by explicitly constructing an $(s,k)$-clash-free permutation on ${\mathbb{Z}}_n$ with $s=\lfloor (n-1)/k\rfloor -1$. Indeed, this construction is used to establish a more general conjecture of Mammoliti and Simpson, where for some fixed integer $r$ we require every point on the torus to be contained in the interior of at most $r$ rectangles.

12 pages, 3 figures. More discussion added. An example, and some typos, corrected