# Permutations that separate close elements, and rectangle packings in the
torus

Simon R. Blackburn  Department of Mathematics, Royal Holloway, University of
London, Egham, Surrey TW20 0EX, United Kingdom<EMAIL_ADDRESS>Tuvi
Etzion Supported in part by the Israeli Science Foundation under grant no.
222/19. Computer Science Department, Technion–Israel Institute of Technology,
Haifa 32000, Israel<EMAIL_ADDRESS>
###### Abstract

Let $n$, $s$ and $k$ be positive integers. For distinct
$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 circle. So

$||i,j||_{n}=\min\\{(i-j)\bmod n,(j-i)\bmod n\\}.$

A permutation $\pi:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ is _$(s,k)$
-clash-free_ if $||\pi(i),\pi(j)||_{n}\geq k$ whenever $||i,j||_{n}<s$. So an
$(s,k)$-clash-free permutation moves every pair of close elements (at distance
less than $s$) to a pair of elements at large distance (at distance at least
$k$). The notion of an $(s,k)$-clash-free permutation can be reformulated in
terms of certain packings of $s\times k$ rectangles on an $n\times n$ torus.

For integers $n$ and $k$ with $1\leq k<n$, let $\sigma(n,k)$ be the largest
value of $s$ such that an $(s,k)$-clash-free permutation of $\mathbb{Z}_{n}$
exists. Strengthening a recent paper of Blackburn, which proved a conjecture
of Mammoliti and Simpson, we determine the value of $\sigma(n,k)$ in all
cases.

##  1 Introduction

Let $n$, $s$ and $k$ be positive integers. As in the abstract, for
$i,j\in\mathbb{Z}_{n}$ we define $||i,j||_{n}$ to be the distance between $i$
and $j$ when the elements of $\mathbb{Z}_{n}$ are written in a circle. In
other words, $||i,j||_{n}$ is the Lee metric modulo $n$, and
$||i,j||_{n}=\min\\{(i-j)\bmod n,(j-i)\bmod n\\}$. Let
$\pi:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ be a permutation of
$\mathbb{Z}_{n}$. An _$(s,k)$ -clash_ is a pair of distinct elements
$i,j\in\mathbb{Z}_{n}$ such that $||i,j||_{n}<s$ and
$||\pi(i),\pi(j)||_{n}<k$. (So $i$ and $j$, and their image under $\pi$ are
both close.) The permutation $\pi$ is _$(s,k)$ -clash-free_ if there are no
$(s,k)$-clashes.

For integers $n$ and $k$ with $1\leq k<n$, we define $\sigma(n,k)$ be the
largest value of $s$ such that an $(s,k)$-clash-free permutation $\pi$ of
$\mathbb{Z}_{n}$ exists. What can be said about $\sigma(n,k)$? This question
was first considered by Mammoliti and Simpson [9], who showed that
$\sigma(n,k)\leq\lfloor(n-1)/k\rfloor$ and conjectured that

$\sigma(n,k)\in\\{\lfloor(n-1)/k\rfloor-1,\lfloor(n-1)/k\rfloor\\}$ (1)

for all $n$ and $k$. This conjecture was proved by Blackburn [3], who gave an
explicit construction of an $(s,k)$-clash-free permutation with
$s=\lfloor(n-1)/k\rfloor-1$ for all $n$ and $k$.

As pointed out in [9], we can think of the problem of constructing
$(s,k)$-clash-free permutations as a problem of packing rectangles on a torus
as follows. Consider an $n\times n$ array consisting of $n^{2}$ cells, each
cell indexed by a pair of elements in $\mathbb{Z}_{n}$. We index the cells in
cartesian fashion, so for example cell $(0,0)$ is at the lower left corner of
the array, and cell $(n-1,0)$ is at the lower right corner of the array. Given
a permutation $\pi$ of $\mathbb{Z}_{m}$, we add $n$ dots to the array in cells
$(i,\pi(i))$ for $i\in\mathbb{Z}_{n}$. (This is sometimes known as the _graph_
of the permutation.) We add $s\times k$ rectangles (so rectangles that are $s$
cells wide and $k$ cells high) to the array, by shading cells $(i+x,\pi(i)+y)$
for $0\leq x<s$ and $0\leq y<k$. Then $\pi$ is $(s,k)$-clash-free if and only
if these rectangles do not overlap. See Figure 1 for an example. So we may
rephrase the problem of constructing an $(s,k)$-clash-free permutation as
finding a (non-overlapping) packing of $n$ rectangles of size $s\times k$ in
an $n\times n$ discrete torus, such that no two rectangles share the same
lower side or the same left hand side.

Figure 1: When $n=40$, $k=s=6$ and
$\pi:\mathbb{Z}_{40}\rightarrow\mathbb{Z}_{40}$ is the permutation mapping
$0,1,2,3,4,\ldots$ to $0,6,27,33,12,\ldots$ respectively.

The case $k=2$ of this problem has been considered [1, 5, 8] under the name of
cyclic matching sequencibility of graphs. Non-cyclic versions of the problem
(in which we work over the integers $\\{0,1,\ldots,n-1\\}$ rather than modulo
$n$) have also been studied [9]. (The special case of the non-cyclic problem
when $k=s=2$ can be rephrased as the problem of placing $n$ non-attacking
kings on an $n\times n$ chessboard, one in each row and each column. This is
the problem of Hertzsprung [6] from 1887, rediscovered by Kaplansky [7] in
1944.) Packings of diamonds rather than rectangles (called permuted packings)
have applications to permutation patterns [2, 4]; here we are looking for
permutations whose dots have large minimum distance in the Manhattan metric
(the $\ell_{1}$ metric).

Given (1), a very natural question to ask is: When does
$\sigma(n,k)=\lfloor(n-1)/k\rfloor$? Mammoliti and Simpson found many
parameters where this is the case. For example, they showed [9, Theorem 3.7]
that, setting $s=\lfloor(n-1)/k\rfloor$, we have $\sigma(n,k)=s$ when

$k|n,\,s|n,\,\gcd(n,k)=1,\text{ or }\gcd(n,s)=1.$ (2)

Indeed, using this result and the fact that an $(s,k)$-clash-free permutation
is $(s^{\prime},k^{\prime})$-clash-free when $s^{\prime}\leq s$ and
$k^{\prime}\leq k$, they were able to show that
$\sigma(n,k)=\lfloor(n-1)/k\rfloor$ for all choices of $n$ and $k$ with $n\leq
30$, apart from $(n,k)\in\\{(18,4),(26,4),(26,6)\\}$. In these last three
cases, they showed by computer search that
$\sigma(n,k)=\lfloor(n-1)/k\rfloor-1$. As pointed out in [3], the first open
cases with $n>30$ after applying the techniques in [9] are
$(n,k)\in\\{(34,4),(34,8),(38,6),(39,6),(40,6)\\}$.

The main theorem in this paper completely resolves the question of the value
of $\sigma(n,k)$, for all values of $n$ and $k$. Indeed, we prove the
following theorem:

######  Theorem 1.

Let $n$ and $k$ be fixed positive integers, with $k<n$. Write
$s=\lfloor(n-1)/k\rfloor$, so $n=sk+r$ where $1\leq r\leq k$. Define
$d_{k}=\gcd(n,k)$ and $d_{s}=\gcd(n,s)$.

  * •

If $r\geq s$ or $k=r$, then $\sigma(n,k)=\lfloor(n-1)/k\rfloor$.

  * •

If $r<s$ and $r<k$ and $d_{s}d_{k}$ divides $n$, then
$\sigma(n,k)=\lfloor(n-1)/k\rfloor$.

  * •

If $r<s$ and $r<k$ and $d_{s}d_{k}$ does not divide $n$, then
$\sigma(n,k)=\lfloor(n-1)/k\rfloor-1$.

Given (1), this theorem is equivalent to the assertion that an $(s,k)$-clash-
free permutation with $s=\lfloor(n-1)/k\rfloor$ exists if and only if $s\leq
r$, $k=r$, or $d_{s}d_{k}$ divides $n$.

Considering the small open cases listed above, Theorem 1 shows in particular
(see Figure 1) that $\sigma(n,k)=\lfloor(n-1)/k\rfloor$ when $(n,k)=(40,6)$,
and $\sigma(n,k)=\lfloor(n-1)/k\rfloor-1$ when
$(n,k)\in\\{(34,4),(34,8),(38,6),(39,6)\\}$.

We observe that the first statement of the theorem follows from known results.
To show this, first observe that if $k=r$ then $k$ divides $n$, and so
$\sigma(n,k)=\lfloor(n-1)/k\rfloor$ by [9, Theorem 3.7] and the theorem holds
in this case. So we may assume without loss of generality that $1\leq r<k$.
Secondly, we observe that if $r>s$ then

$\lfloor(n-1)/s\rfloor=\lfloor(ks+(r-1))/s\rfloor\leq k+1$

and so $\lfloor(n-1)/s\rfloor-1\leq k$. In this case the construction from
Blackburn [3, Section 2] with the roles of $r$ and $s$ swapped gives a
$(k,s)$-clash-free permutation of $\mathbb{Z}_{n}$. Since the existence of an
$(s,k)$-clash-free permutation is equivalent to the existence of a
$(k,s)$-clash-free permutation, we find that the theorem holds in this case
also. Hence it suffices to assume that $r\leq s$. Finally, if $r=s$ then $s$
divides $r$, and the theorem follows by [9, Theorem 3.7]. Hence the first
assertion of the theorem holds.

So it suffices to prove the final two assertions of the theorem. To this end,
we will assume from now on that $n=sk+r$ where $r$ is positive, $r<s$ and
$r<k$.

In Section 2, we will provide some structural information on permutations
$\pi$ of $\mathbb{Z}_{n}$ that are $(\lfloor(n-1)/k,k)$-clash-free. In
particular we show (see Theorem 7 below) that if an $(s,k)$-clash-free
permutation exists then $d_{s}d_{k}$ must divide $n$. So if $d_{s}d_{k}$ does
not divide $n$ then no $(k,s)$-clash-free permutation exists and hence the
third statement of the Theorem 1 will follow.

In Section 3 we assume that $d_{s}d_{k}$ divides $n$ and provide an explicit
construction for an $(s,k)$-clash-free permutation; see Theorem 9 below. This
will prove the second statement of the theorem, and completes the proof of
Theorem 1.

In fact, the techniques of Sections 2 and 3 can be extended to provide a
comprehensive classification of $(s,k)$-clash-free permutations with
$s=\lfloor(n-1)/k\rfloor$ when $r<k$, $s<k$ and $d_{s}d_{k}$ divides $n$.
Section 4 sketches a proof of this classification.

### Acknowledgement

We would like to thank Sergey Kitaev, for bringing the references on non-
attacking kings to our attention.

##  2 The structure of extremal clash-free permutations

Let $n$ and $k$ be such that $k<n$. Define $s=\lfloor(n-1)/k\rfloor$ and write
$n=sk+r$ with $1\leq r$. Assume that $r<s$ and $r<k$. Let $\pi$ be an
$(s,k)$-clash-free permutation. This section explores the structure of $\pi$.
We will argue from the point-of-view of a rectangle packing for the sake of
clarity. So we represent the torus $\mathbb{Z}_{n}^{2}$ as an $n\times n$ grid
of $1\times 1$ cells, indexed in the usual cartesian fashion with the origin
at the lower left-hand corner. We place dots in the cells with coordinates
$(i,\pi(i))$. We place $n$ rectangles in the torus, all $s$ cells wide and $k$
cells high, with the $i$th rectangle $R_{i}$ having cell $(i,\pi(i))$ at its
lower left corner. The fact that $\pi$ is $(s,k)$-clash-free implies that
these rectangles do not overlap.

######  Lemma 2.

Every column of the grid contains exactly $r$ cells that are not covered by a
rectangle. Every row contains exactly $r$ cells that are not covered by a
rectangle.

###### Proof.

Let $x\in\mathbb{Z}_{n}$, and consider the column of all cells with first co-
ordinate $x$. The $i$th rectangle $R_{i}$ intersects our column if and only if
$i\in\\{x,x-1,\ldots,x-(s-1)\\}$. If the rectangle intersects our column, it
covers exactly $k$ cells. Since the $s$ rectangles that intersect our column
are disjoint, exactly $sk$ cells in our column are covered. So there are
$n-sk=r$ cells in our column not covered by a rectangle. The argument for the
row of cells with second co-ordinate $y\in\mathbb{Z}_{n}$ is essentially the
same: there are $k$ rectangles intersecting our row (the rectangles $R_{i}$
where $\pi(i)\in\\{y,y-1,\ldots,y-(k-1)\\}$) and each rectangle covers $s$
cells in the row. ∎

A cell is called _free_ if it is not contained in a rectangle, and is
otherwise _covered_. So the lemma above states that every row and every column
contains exactly $r$ free cells.

######  Lemma 3.

Let $R$ be a fixed rectangle. Then exactly one rectangle touches the top edge
of $R$. The same is true for the left, right and bottom edges of $R$.

###### Proof.

Consider the $s$ cells that lie just above $R$. All these cells lie in the
same row $y$, and this row contains $r$ free cells by Lemma 2. Since $r<s$,
not all of the $s$ cells are free. So at least one is occupied, and there is a
rectangle touching the top edge of $R$. There cannot be two rectangles
touching the top edge of $R$, since then these rectangles would both have dots
with second coordinate $y$, contradicting the fact that $\pi$ is injective. So
there is exactly one rectangle touching the top edge of $y$, and the first
statement of the theorem follows. The same argument (applied three times)
establishes the second statement of the theorem. ∎

Let $\Gamma$ be the graph with vertex set $\mathbb{Z}_{n}$, with vertices $i$
and $j$ joined by an edge if and only if the rectangles $R_{i}$ and $R_{j}$
touch on their left or right sides. Let $\Delta$ be the graph with the same
vertex set $\mathbb{Z}_{n}$, but with vertices $i$ and $j$ joined by an edge
if and only if the rectangles $R_{i}$ and $R_{j}$ touch on their top or bottom
sides. We call the connected components of $\Gamma$ _warp threads_. We call
the connected components of $\Delta$ _weft threads_. (The terminology warp and
weft comes from weaving. Parallel warp threads are set up in a loom, and the
shuttle with a weft thread attached weaves through the warp threads, thus
forming the transverse threads in the woven textile.)

######  Lemma 4.

Each warp thread $U$ is a cycle containing $n/d_{s}$ vertices. The vertices in
$U$ correspond to rectangles $R_{i}$ where $i$ lies in a fixed congruence
class modulo $d_{s}$. Each weft thread $V$ is a cycle containing $n/d_{k}$
vertices. The vertices in $V$ correspond to rectangles $R_{i}$ where $\pi(i)$
lies in a fixed congruence class modulo $d_{k}$

###### Proof.

Lemma 3 implies that warp threads are all cycles, since every vertex of the
thread has degree $2$. The first co-ordinates of rectangles in a warp thread
$U$ increases by $s$ as we move right along the cycle. So we return to the
start of the cycle after $\ell$ steps, where $\ell$ is the additive order of
$s$ modulo $n$. Since $\ell=n/d_{s}$, the first statement of the theorem
follows. The second statement follows from this observation, together with the
fact that the number of elements $i\in\mathbb{Z}_{n}$ in a congruence class
modulo $d_{s}$ is also $n/d_{s}$. The final statement of the lemma is proved
similarly, using the fact that two touching rectangles in a weft thread $V$
have second co-ordinates that differ by $k$. ∎

Let $R$ be a rectangle in our packing. There are four rectangles touching $R$,
none of which is completely aligned horizontally or vertically with $R$
(because $\pi$ is a permutation). As can be seen in Figure 2 (where the arrows
span a positive number of cells), the fact that rectangles do not overlap
shows that the rectangles touching $R$ can be arranged in one of two ways: we
call $R$ a _clockwise rectangle_ or  _anticlockwise rectangle_ respectively.
This figure also shows that touching rectangles are clockwise when $R$ is
clockwise, and anticlockwise otherwise. So all the rectangles in our packing
are either clockwise or anticlockwise: we call $\pi$ a clockwise or
anticlockwise permutation depending on which case occurs. Reflecting in a
horizontal line (or replacing $\pi$ by $-\pi$) shows that a clockwise
$(s,k)$-clash-free permutation exists if and only if an anticlockwise
$(s,k)$-clash-free permutation exists.

Figure 2: Clockwise (left) and anticlockwise (right) rectangles.

We define the _gap_ of a rectangle $R$ to be the (edge) connected region of
free cells that include free cells just above $R$.

######  Lemma 5.

Fix a warp thread $U$. The set of rectangles touching the upper edges of
rectangles in $U$ is another warp thread $U^{\prime}$. The gap of any
rectangle $R\in U$ is rectangular in shape. The width of the gap of $R\in U$
depends only on $U$ (not $R$). The set of rectangles touching the lower edges
of rectangles in $U$ form another warp thread. Fix a weft thread $V$. The set
of rectangles touching the left edges of rectangles in $V$ forms a weft
thread, as does the set of rectangles touching the right edges of rectangles
in $V$. The gap of $R\in V$ is a rectangle, and its height depends only on $V$
(not $R$).

###### Proof.

We may assume that $\pi$ is a clockwise permutation. (The proof for an
anticlockwise permutation is identical to the clockwise case.) We will prove
the statements for warp threads: the corresponding proofs for weft threads are
similar.

$R$$S$$R^{\prime}$$S^{\prime}$$u$$v$$s$ Figure 3: Can $R^{\prime}$ and
$S^{\prime}$ fail to touch?

Let $R$ and $S$ be adjacent rectangles in a warp thread $U$. Let $R^{\prime}$
and $S^{\prime}$ be the rectangles touching the upper sides of $R$ and $S$
respectively; see Figure 3. To prove the first statement of the lemma, it
suffices to prove that $R^{\prime}$ and $S^{\prime}$ lie on the same warp
thread. The first coordinates $a$ of the dot in $R$ and $b$ of the dot in $S$
satisfy the equality $b-a=s$, since $R$ and $S$ touch. The first coordinate of
the dot in $R^{\prime}$ is of the form $a^{\prime}=a+u$ where $1\leq u<s$, and
the first coordinate of the dot in $S^{\prime}$ is $b^{\prime}=b+v$ where
$1\leq v<s$. The number of columns separating $R^{\prime}$ and $S^{\prime}$ is
$b^{\prime}-a^{\prime}-s$, where

$b^{\prime}-a^{\prime}-s=(b+v)-(a+u)-s=v-u<v<s.$

So there can be no rectangle between $R^{\prime}$ and $S^{\prime}$, as $R$ and
$S$ are separated by fewer than $s$ columns. But this means that $R^{\prime}$
and $S^{\prime}$ touch, since otherwise the $k$ cells immediately to the left
of $S$ are all free. This implies that $R^{\prime}$ and $S^{\prime}$ lie on
the same warp thread, as required.

The same argument implies the fourth statement of the lemma, that the
rectangles touching the lower sides of a warp thread form another warp thread.

$R$$S$$T$$R^{\prime}$$S^{\prime}$$T^{\prime}$$x$$x$$x$ Figure 4: Gaps above a
warp thread have constant width $x$.

In Figure 4, $R$, $S$ and $T$ lie in the same warp thread. Let $R^{\prime}$,
$S^{\prime}$ and $T^{\prime}$ be the rectangles touching the upper sides of
$R$, $S$ and $T$ respectively. We note that once the position of the
rectangles $R$, $S$, $T$ and $R^{\prime}$ are known, the position of
$S^{\prime}$ is determined since $S^{\prime}$ touches $S$ and $R^{\prime}$,
and similarly the position of $T^{\prime}$ are determined since it touches $T$
and $S^{\prime}$. The figure shows that the gaps of $S$ and $T$ both
rectangular, of the same width. This suffices to establish the second and
third statements of the lemma. ∎

We may use the results of Lemma 5 to define two maps on the set of warp
threads, and two maps on the set of all weft threads, as follows. For a warp
thread $U$, define $\tau(U)$ to be the warp thread consisting of all
rectangles (not in $U$) that touch the upper edges of $U$. Define $\delta(U)$
to be the warp thread consisting of all rectangles (not in $U$) that touch the
lower edges of $U$. For a weft thread $V$, define $\rho(V)$ to be the weft
thread consisting of all rectangles (not in $V$) that touch the right edges of
rectangles in $V$. Finally, define $\lambda(V)$ to be the weft thread
consisting of all rectangles (not in $V$) that touch the left edges of
rectangles in $V$.

######  Lemma 6.

The function $\tau$ defined above is a permutation of the set of all $d_{s}$
warp threads; indeed it is a $d_{s}$-cycle. The function $\rho$ defined above
is a cyclic permutation of the set of weft threads; indeed it is an
$d_{k}$-cycle.

###### Proof.

The functions $\tau$ and $\rho$ are permutations, as they have inverses
$\delta$ and $\lambda$ respectively. Let $U$ be a fixed warp thread. Then the
region of the torus consisting of the rectangles in
$\bigcup_{i\in\mathbb{Z}}\tau^{i}(U)$ together with their gaps has no boundary
and so is the whole of the torus. Hence every warp thread lies in
$\bigcup_{i\in\mathbb{Z}}\tau^{i}(U)$, and so $\tau$ is an $n/d_{s}$-cycle.
Similarly, $\rho$ is an $n/d_{k}$-cycle. ∎

######  Theorem 7.

Let $n$ and $k$ be fixed positive integers, with $k<n$. Write
$s=\lfloor(n-1)/k\rfloor$, so $n=sk+r$ where $1\leq r\leq k$. Define
$d_{k}=\gcd(n,k)$ and $d_{s}=\gcd(n,s)$. Suppose that $r<k$ and $r<s$. If an
$(s,k)$-clash-free permutation of $\mathbb{Z}_{n}$ exists, then $d_{s}d_{k}$
divides $n$.

###### Proof.

Fix a rectangle $R$. The rectangle $R$ lies on a warp thread $U_{0}$ and a
weft thread $V$. Journeying upwards along our weft thread $V$, we obtain a
sequence $U_{0},U_{1},\ldots$ of warp threads, where the $i$th rectangle in
our journey lies in warp thread $U_{i}$. The definition of $\tau$ shows that
$\tau(U_{i})=U_{i+1}$ for $i\geq 0$. By Lemma 6, $\tau$ is a $d_{s}$-cycle and
so the sequence $U_{0},U_{1},\ldots$ has exact period $d_{s}$. But our weft
thread contains $n/d_{k}$ rectangles and so after $n/d_{k}$ steps our journey
reaches $R$ and begins to repeat. So the sequence $U_{0},U_{1},\ldots$ has
period dividing $n/d_{k}$. Hence $d_{s}$ divides $n/d_{k}$ and so $d_{s}d_{k}$
divides $n$, as required. ∎

Previously, the cases when $\sigma(n,k)=\lfloor(n-1)/k\rfloor-1$ were
established by computer search (and so only finitely many parameters were
known). Theorem 7 allows us to construct infinitely many parameters with this
property:

######  Corollary 8.

There are infinitely many choices of parameters $n$ and $k$ such that
$\sigma(n,k)=\lfloor(n-1)/k\rfloor-1$.

###### Proof.

Consider, for example, the case when $k\equiv 2\bmod 4$ with $k\geq 10$.
Define $s$ to be an integer such that $6\leq s<k$ and $s\equiv 2\bmod 4$.
Define $n=sk+s-4$. Note that $\lfloor(n-1)/k\rfloor=s$. In the notation of
Theorem 7, we observe that both $d_{k}$ and $d_{s}$ are divisible by $2$ but
$n$ is not divisible by $4$, so $n$ is not divisible by $d_{s}d_{k}$. Theorem
7 implies that no $(s,k)$-clash-free permutation exists and so
$\sigma(n,k)\not=\lfloor(n-1)/k\rfloor$. Hence
$\sigma(n,k)=\lfloor(n-1)/k\rfloor-1$, by (1). ∎

##  3 An explicit construction of $(s,k)$-clash-free permutations

######  Theorem 9.

Let $n$ and $k$ be fixed positive integers, with $k<n$. Write
$s=\lfloor(n-1)/k\rfloor$, so $n=sk+r$ where $1\leq r\leq k$. Define
$d_{k}=\gcd(n,k)$ and $d_{s}=\gcd(n,s)$. Suppose that $r<k$ and $r<s$. If
$d_{s}d_{k}$ divides $n$, then there exists an $(s,k)$-clash-free permutation.

###### Proof.

Suppose that $d_{s}d_{k}$ divides $n$. We define a function
$\pi:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ as follows. Let
$x\in\mathbb{Z}_{n}$. We claim there exist unique integers
$j\in\\{0,1,\ldots,d_{s}-1\\}$, $i\in\\{0,1,\ldots,d_{k}-1\\}$ and
$\alpha\in\\{0,1,\ldots,n/(d_{s}d_{k})-1\\}$ such that $x=(\alpha
d_{k}+i)s+j\bmod n$. To see this, we first use the quotient and remainder
theorem to write $x=qd_{s}+j\bmod n$ for unique integers
$q\in\\{0,1,\ldots,n/d_{s}-1\\}$ and $j\in\\{0,1,\ldots,d_{s}-1\\}$. Since
$\\{qd_{s}\bmod n:q\in\mathbb{Z}\\}=\\{fs\bmod n:f\in\mathbb{Z}\\}$, we see
that $qd_{s}=fs\bmod n$ for a unique integer $f\in\\{0,1,\ldots,n/d_{s}-1\\}$.
We write $f=\alpha d_{k}+i$, where $0\leq i<d_{k}$ and
$0\leq\alpha<n/(d_{s}d_{k})$. Then $x=(\alpha d_{k}+i)s+j\bmod n$, and our
claim follows. We define

$\pi(x)=\pi((\alpha d_{k}+i)s+j)=jk-i-\alpha d_{s}d_{k}\in\mathbb{Z}_{n}.$

We first show that $\pi$ is a permutation. It suffices to prove that $\pi$ is
injective. Suppose

$x=(\alpha d_{k}+i)s+j\text{ and
}x^{\prime}=(\alpha^{\prime}d_{k}+i^{\prime})s+j^{\prime}$ (3)

are elements of $\mathbb{Z}_{n}$ such that $\pi(x)=\pi(x^{\prime})$. We may
look at $\pi(x)=jk-i-\alpha d_{s}d_{k}$ and
$\pi(x^{\prime})=j^{\prime}k-i^{\prime}-\alpha^{\prime}d_{s}d_{k}$ modulo
$d_{k}$, since $d_{k}$ divides $n$. Using the fact that $d_{k}$ also divides
$k$, we see that $i=i^{\prime}$ modulo $d_{k}$ and so $i=i^{\prime}$. Hence

$j(k/d_{k})-\alpha d_{s}=j^{\prime}(k/d_{k})-\alpha^{\prime}d_{s}\bmod
n/d_{k}.$ (4)

Since $d_{s}$ divides $n/d_{k}$, we may deduce that

$j(k/d_{k})=j^{\prime}(k/d_{k})\bmod d_{s}.$ (5)

Since $d_{k}=\gcd(n,k)$, we have that $k/d_{k}$ and $n/d_{k}$ are coprime. But
$d_{s}$ divides $n/d_{k}$, and so $k/d_{k}$ and $d_{s}$ are coprime. Hence (5)
implies that $j=j^{\prime}\bmod d_{s}$ and so $j=j^{\prime}$. Now (4) implies
that $\alpha=\alpha^{\prime}\bmod{n/(d_{s}d_{k})}$ and so
$\alpha=\alpha^{\prime}$. We have shown that $i=i^{\prime}$. $j=j^{\prime}$
and $\alpha=\alpha^{\prime}$. Hence $x=x^{\prime}$ by (3). Hence $\pi$ is
injective, as required.

We now show that $\pi$ is $(s,k)$-clash-free. Define integers $a$ and $b$ by
$a=r-(d_{s}-1)$ and $b=d_{s}d_{k}-(d_{k}-1)$. We claim that $0<a<s$ and
$0<b<k$. Clearly $b$ is positive. To prove the other inequalities in our
claim, we first note that $r=n-sk$ and $d_{s}d_{k}$ divides $n$ and so $r$ is
a (positive) multiple of $d_{s}d_{k}$. In particular, we see that $a\leq r$
and $b\leq r$. Since $r<s$ and $r<k$, we see that $a<s$ and $b<k$. Finally,
since $r\geq d_{s}d_{k}$ we see that $a$ is positive, and our claim follows.

Consider the non-overlapping collection of $s\times k$ rectangles in the
infinite grid $\mathbb{Z}^{2}$, as depicted in Figure 5. This packing of
rectangles is divided into $d_{k}\times d_{s}$ _blocks_ of rectangles (with
different shadings in the figure). There are $d_{s}$ rows and $d_{k}$ columns
of rectangles in each block. The gaps above the rectangles are all of width
and height $1$, apart from the gaps above the rectangles in the top row of
each block which have width $a$, and the gaps above the the left column of
each block, which have height $b$. (This is a special case of a packing
obtained from two bi-infinite sequences $(a_{i})$ and $(b_{j})$ of positive
integers, with $a_{i}\leq s$ and $b_{i}\leq k$, by defining the gap above the
$(i,j)$th rectangle to have a gap of width $a_{i}$ and height $b_{j}$.)

Fix one of the blocks of rectangles (coloured more darkly in Figure 5), and
choose coordinates so that the lower left corner of the lower left rectangle
in the block is $(0,0)$. (This is marked as a dot in the most darkly shaded
block.) The set of lower left dots in all blocks (the dots in the figure) form
a lattice $L$, where

$\displaystyle L$ $\displaystyle=\\{\alpha u+\beta
v:\alpha,\beta\in\mathbb{Z}\\},\text{ with}$ $\displaystyle u$
$\displaystyle=(d_{k}s,-(d_{k}-1)-b)=(d_{k}s,-d_{s}d_{k})\text{ and}$
$\displaystyle v$ $\displaystyle=((d_{s}-1)+a,d_{s}k)=(r,d_{s}k).$

(If we take a tile consisting of the rectangles in a fixed block and their
associated gaps, the images of this tile under $L$ form a lattice tiling of
the plane.)

Let $\cal P$ be the set of coordinates of the lower left corners of all
rectangles (not all blocks) in the packing. So

${\cal P}=\\{w+(is+j,jk-i):0\leq i\leq d_{k}-1,0\leq j\leq d_{s}-1\text{ and
}w\in L\\}.$

Rectangles in the same block are associated with the same element $w\in L$. It
is clear that the transformation of the plane defined by $x\mapsto x+w$ are
symmetries of our packing for any $w\in L$. We note that $(n,0),(0,n)\in L$,
since

$\displaystyle(n,0)$ $\displaystyle=\left(\frac{k\,}{d_{k}}\right)u+v,\text{
and}$ $\displaystyle(0,n)$
$\displaystyle=-\left(\frac{r}{d_{s}d_{k}}\right)u+\left(\frac{s\,}{d_{s}}\right)v.$

So our rectangle packing is periodic of period dividing $n$ in both horizontal
and vertical directions, and therefore gives a well-defined packing of the
torus $\mathbb{Z}_{n}^{2}$ with $s\times k$ rectangles. But the permutation
$\pi$ gives rise to rectangles in this packing, since the $s\times k$
rectangles associated with $\pi$ are at coordinates

$(x,\pi(x))=\big{(}(\alpha d_{k}+i)s+j,jk-i-\alpha d_{s}d_{k}\big{)}=\alpha
u+(is+j,jk-i)$

modulo $n$, which all lie in $\cal P$. Since $\pi$ is a permutation, these
rectangles are distinct modulo $n$ and hence non-overlapping. Hence $\pi$ is
$(s,k)$-clash-free, as required. ∎

$b$$b$$b$$b$$a$$a$$a$$s$$k$ Figure 5: A planar rectangle packing, with some
blocks of rectangles highlighted

##  4 More structure theory

As in previous sections, we assume that $n$ and $k$ are fixed integers with
$k<n$, and we set $s=\lfloor(n-1)/k\rfloor$ with $n=sk+r$ for $1\leq r\leq k$.
We define $d_{s}$ and $d_{k}$ as before, and assume that $r<k$ and $r<s$.
Futhermore, we suppose that $d_{s}d_{k}$ divides $n$, so $(s,k)$-clash-free
permutations exist. In this section, we sketch how the structural information
in Section 2 may be extended, and the construction in Section 3 may be
generalised, to provide a tighter characterisation of $(s,k)$-clash-free
permutations.

The orbits of the map taking a permutation $\pi$ to the permutation $-\pi$
partition the set of $(s,k)$-clash-free permutations into pairs, one clockwise
and one anticlockwise. So, without loss of generality, we may assume that our
$(s,k)$-clash-free permutation is clockwise. Furthermore, replacing $\pi$ by
the permutation $\pi^{\prime}$ defined by $\pi^{\prime}(x)=\pi(x)-\pi(0)$ for
all $x\in\mathbb{Z}_{n}$, we may assume that $\pi(0)=0$. We aim to classify
clockwise $(s,k)$-clash-free permutations with $\pi(0)=0$ by bringing them
into bijection with the set of objects we call $(s,k,n)$-jumpers. It turns out
that the rectangles of these clash-free permutations may be divided up into
blocks, generalising the approach in Section 3, but the gaps associated with
the rectangles in a block have a more complicated structure that is determined
by an $(s,k,n)$-jumper. We use the term jumper to keep within our weaving
theme, and because a jumper determines how rectangles are arranged, jumping
from a completely regular lattice. We leave the reader to think of a brand
name that the jumpers might belong to.

An $(s,k,n)$-_jumper_ is a pair $\big{(}(a_{i}),(b_{i})\big{)}$ of sequences
of integers with the following properties:

  1. 1.

$(a_{i})$ has period dividing $d_{s}$, and $(b_{i})$ has period dividing
$d_{k}$.

  2. 2.

We have $1\leq a_{i}<s$ and $1\leq b_{i}<k$ for $i\geq 0$.

  3. 3.

The $d_{k}$ partial sums $\sum_{i=0}^{\ell-1}b_{i}$ where $0\leq\ell<d_{s}$
are distinct modulo $d_{k}$. Moreover, $d_{s}d_{k}$ divides $\sigma_{b}$ where
$\sigma_{b}=\sum_{i=0}^{d_{k}-1}b_{i}$.

  4. 4.

The $d_{s}$ partial sums $\sum_{i=0}^{m-1}a_{i}$ where $0\leq m<d_{s}$ are
distinct modulo $d_{s}$. Moreover, $d_{s}d_{k}$ divides $\sigma_{a}$ where
$\sigma_{a}=\sum_{i=0}^{d_{s}-1}a_{i}$.

  5. 5.

Defining $\sigma_{a}$ and $\sigma_{b}$ as above,
$\sigma_{a}\sigma_{b}=d_{s}d_{k}r$.

We define $J(s,k,n)$ to be the set of $(s,k,n)$-jumpers.

For example, suppose $n=216$, $s=10$ and $k=21$. So $n=sk+r$ with $r=6$, and
we have $d_{s}=2$ and $d_{k}=3$. We can check that
$\big{(}(a_{i}),(b_{i})\big{)}$ is a jumper, Let
$(a_{i})=(a_{0},a_{1},\ldots)$ be the sequence of period $2$ with $a_{0}=1$
and $a_{1}=5$. Let $(a^{\prime}_{i})$ be the constant sequence of period $1$
where $a^{\prime}_{i}=3$ for all $i$. Let $(b_{i})=(b_{0},b_{1},\ldots)$ be
the sequence of period $3$ where $b_{0}=b_{1}=1$ and $b_{2}=4$. Let
$(b^{\prime}_{i})=(b^{\prime}_{0},b^{\prime}_{1},\ldots)$ be the sequence of
period $3$ where $b^{\prime}_{0}=1$, $b^{\prime}_{1}=4$ and
$b^{\prime}_{2}=1$. Then is not hard to check that when
$(c_{i})\in\\{(a_{i}),(a^{\prime}_{i})\\}$ and
$(d_{i})\in\\{(b_{i}),(b^{\prime}_{i})\\}$ we have that
$\big{(}(c_{i}),(d_{i})\big{)}$ is an $(s,k,n)$-jumper.

Under our assumption that $d_{s}d_{k}$ divides $n$, $(s,k,n)$-jumpers always
exist. Indeed, a $(s,k,n)$-jumper can be constructed as follows. Since
$n=sk+r$, we see that $d_{s}d_{k}$ divides $r$. Write
$r/(d_{s}d_{k})=r_{a}r_{b}$ for some positive integers $r_{a}$ and $r_{b}$.
(This factorisation can be trivial.) Define $\sigma_{a}=d_{s}d_{k}r_{a}$ and
$\sigma_{b}=d_{s}d_{k}r_{b}$. Let $(a_{0},a_{1},\ldots)$ be the sequence of
period dividing $d_{s}$ with $a_{1}=\cdots a_{d_{s}-1}=1$ and
$a_{0}=\sigma_{a}-(d_{s}-1)$. Similarly, let $(b_{0},b_{1},\ldots)$ be the
sequence of period dividing $d_{k}$ with $b_{1}=\cdots b_{d_{k}-1}=1$ and
$b_{0}=\sigma_{b}-(d_{k}-1)$. It is easy to check (using our assumption that
$r<s$ and $r<k$) that $\big{(}(a_{i}),(b_{i})\big{)}$ is an $(s,k,n)$-jumper.

We will see below that a jumper $\big{(}(a_{i}),(b_{i})\big{)}$ determines the
size of gaps associated with rectangles in a block of a permutation: the
$(u,v)$th rectangle in a block has a gap that is rectangular of width $a_{v}$
and height $b_{u}$ to its north-east. For example, a block of a permutation
associated with the jumper $\big{(}(a^{\prime}_{i}),(b^{\prime}_{i})\big{)}$
is depicted in Figure 6.

Figure 6: A block in a permutation with jumper
$\big{(}(a^{\prime}_{i}),(b^{\prime}_{i})\big{)}$. All gaps have width $3$,
and height either $1$ or $4$.

######  Lemma 10.

Let $n$ and $k$ be fixed integers with $k<n$. Set $s=\lfloor(n-1)/k\rfloor$,
and define $r$ by $n=sk+r$ for $1\leq r\leq k$. Define $d_{s}=\gcd(n,s)$ and
$d_{k}=\gcd(n,k)$. Assume that $d_{s}d_{k}$ divides $n$. Let
$\big{(}(a_{i}),(b_{i})\big{)}$ be an $(s,k,n)$-jumper, and define
$\sigma_{a}=\sum_{i=0}^{d_{s}-1}a_{i}$ and
$\sigma_{b}=\sum_{i=0}^{d_{k}-1}b_{i}$. Then

$\gcd\big{(}n/(d_{s}d_{k}),\sigma_{b}/(d_{s}d_{k})\big{)}=1.$

###### Proof.

The third and fourth conditions for being a jumper imply that we be write
$\sigma_{a}=d_{s}d_{k}r_{a}$ and $\sigma_{b}=d_{s}d_{k}r_{b}$ for some
integers $r_{a}$ and $r_{b}$. The final condition of being a jumper implies
that $r=d_{s}d_{k}r_{a}r_{b}$ and so in particular $r/(d_{s}d_{k})$ is a
multiple of $\sigma_{b}/(d_{s}d_{k})$. Thus it suffices to show that

$\gcd\big{(}n/(d_{s}d_{k}),r/(d_{s}d_{k})\big{)}=1.$

Suppose, for a contradiction, that there exists a prime $p$ dividing both
$n/(d_{s}d_{k})$ and $r/(d_{s}d_{k})$. Then $p$ divides

$(n-r)/(d_{s}d_{k})=sk/(d_{s}d_{k})=(s/d_{s})(k/d_{k}),$

and so $p$ divides $s/d_{s}$ or $k/d_{k}$. Suppose that $p$ divides $s/d_{s}$.
Since $p$ divides $n/(d_{s}d_{k})$, we see that $p$ divides $n/d_{s}$ and so
$\gcd(n/d_{s},s/d_{s})\geq p$. But this contradicts the definition of $d_{s}$.
Similarly, if we assume that $p$ divides $k/d_{k}$ we derive a contradiction
using the definition of $d_{k}$. So
$\gcd\big{(}n/(d_{s}d_{k}),r/(d_{s}d_{k})\big{)}=1$ and the lemma follows. ∎

######  Theorem 11.

Let $n$ and $k$ be fixed integers with $k<n$. Set $s=\lfloor(n-1)/k\rfloor$,
and define $r$ by $n=sk+r$ for $1\leq r\leq k$. Define $d_{s}=\gcd(n,s)$ and
$d_{k}=\gcd(n,k)$. Assume that $r<k$ and $r<s$. Futhermore, suppose that
$d_{s}d_{k}$ divides $n$. There is a bijection between the set of clockwise
$(s,k)$-clash-free permutations with $\pi(0)=0$ and the set $J(s,k,n)$ of
$(s,k,n)$-jumpers.

###### Proof.

Let $\pi$ be a clockwise $(s,k)$-clash-free permutation with $\pi(0)=0$. We
produce an $(s,k,n)$-jumper as follows.

Consider the rectangle $R$ whose lower left cell is at $(0,0)$. As in the
proof of Theorem 7, we may define a sequence $U_{0},U_{1},\ldots$ of warp
threads, where $U_{0}$ is the warp thread containing $R$ and where
$U_{i+1}=\tau(U_{i})$ for $i>0$. The proof of Theorem 7 shows that this
sequence has period exactly $d_{s}$. Let $a_{i}$ be the width of a gap above a
rectangle in $U_{i}$. (This width does not depend on the rectangle in $U_{i}$
we choose, by Lemma 5.) The sequence $(a_{i})$ has period dividing $d_{s}$,
and $1\leq a_{i}<s$ for $i\geq 0$. Arguing similarly, by travelling along the
warp thread through $R$, we may produce a sequence $V_{0},V_{1},\ldots$ of
weft threads, where $V_{0}$ is the weft thread containing $R$ and
$V_{i+1}=\rho(V_{i})$ for $i>0$. This sequence has period exactly $d_{k}$. Let
$b_{i}$ be the height of a gap above a rectangle in $V_{i}$ (which is well-
defined by Lemma 5). The sequence $(b_{i})$ has period dividing $d_{k}$, and
$1\leq b_{i}<k$ for $i\geq 0$. We claim that the pair
$\big{(}(a_{i}),(b_{i})\big{)}$ of sequences is an $(s,k,n)$-jumper.

We have already established the first two conditions required for being a
jumper. To show the third and fourth conditions are also satisfied, we argue
as follows. Moving along the warp thread containing $R$, we find a sequence
$R=R_{(0)},R_{(1)},\ldots$ of rectangles. The lower left cell of rectangle
$R_{(\ell)}$ is at position $(\ell s,-\sum_{i=0}^{\ell-1}b_{i})$. The
rectangles $R_{(0)},R_{(1)},\ldots,R_{(d_{k}-1)}$ lie in distinct weft threads
$V_{0},V_{1},\ldots,V_{d_{k}-1}$, and so the elements
$-\sum_{i=0}^{\ell-1}b_{i}$ are distinct modulo $d_{k}$, by the last statement
of Lemma 4. Hence the $d_{k}$ partial sums $\sum_{i=0}^{x-1}b_{i}$ are
distinct modulo $d_{k}$. The sequence $R=R_{(0)},R_{(1)},\ldots$ of rectangles
has period $n/d_{s}$, again by Lemma 4. Comparing the second coordinates of
$R_{(0)}$ and $R_{(n/d_{k})}$ we find that

$0\equiv-\sum_{i=0}^{n/d_{s}-1}b_{i}\equiv-(n/(d_{s}d_{k}))\sigma_{b}\bmod n,$

and so $(n/(d_{s}d_{k}))\sigma_{b}\equiv 0\bmod d_{s}d_{k}$. Thus the third
condition holds. The fourth condition similarly holds, by arguing that the
rectangles encountered when moving along the weft thread containing $R$ have
lower left corners at positions $(\sum_{i=0}^{m-1}a_{i},mk)$ and using the
second statement of Lemma 4.

It remains to check that the final condition for being a jumper is satisfied.
Since the sequence $(b_{j})$ has period $d_{k}$, the gaps of rectangles in
warp thread $U_{i}$ have total area

$\sum_{j=0}^{n/d_{s}-1}(a_{i}b_{j})=a_{i}\left(\sum_{j=0}^{n/d_{s}-1}b_{j}\right)=a_{i}(n/d_{s}d_{k})\sigma_{b}.$

So the total area of all gaps can be written as

$(n/d_{s}d_{k})\sum_{i=0}^{d_{s}-1}a_{i}\sigma_{b}=(n/d_{s}d_{k})\sigma_{a}\sigma_{b}.$

But Lemma 2 shows that every row of our torus contains $r$ free cells, and so
there are $nr$ free cells in total. Hence
$nr=(n/d_{s}d_{k})\sigma_{a}\sigma_{b}$ and so
$\sigma_{a}\sigma_{b}=rd_{s}d_{k}$. This establishes our claim that
$((a_{i}),(b_{i}))$ is an $(s,k,n)$-jumper, as required.

Let $\big{(}(a_{i}),(b_{i})\big{)}$ be an $(s,k,n)$-jumper. We construct a
permutation $\pi:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ as follows. Let
$x\in\mathbb{Z}_{n}$. By the fourth condition of being an $(s,k,n)$-jumper,
and by considering $x$ modulo $d_{s}$, there exist unique integers
$q\in\\{0,1,\ldots,n/d_{s}-1\\}$ and $m\in\\{0,1,\ldots,d_{s}-1\\}$ such that
$x=qd_{s}+\sum_{i=0}^{m-1}a_{i}\bmod n$. As in the proof of Theorem 9, we may
write $qd_{s}=fs\bmod n$ for a unique integer $f\in\\{0,1,\ldots,n/d_{s}-1\\}$
and we may write $f=\alpha d_{k}+\ell$ where $0\leq\ell<d_{k}$ and
$0\leq\alpha<n/(d_{s}d_{k})$. We define $\pi(x)=y$ where

$\pi(x)=\pi\left((\alpha
d_{k}+\ell)s+\sum_{i=0}^{m-1}a_{i}\right)=mk-\sum_{i=0}^{\ell-1}b_{i}-\alpha\sigma_{b}.$

In order to check that $\pi$ is a permutation, it suffices to show that $\pi$
is injective. Suppose that

$mk-\sum_{i=0}^{\ell-1}b_{i}-\alpha\sigma_{b}=m^{\prime}k-\sum_{i=0}^{\ell^{\prime}-1}b_{i}-\alpha^{\prime}\sigma_{b}\bmod
n.$

Considering this equality modulo $d_{k}$, and using the third condition of
being an $(s,k,n)$-jumper, we see that $\ell=\ell^{\prime}$. So
$mk-\alpha\sigma_{b}=m^{\prime}k-\alpha^{\prime}\sigma_{b}\bmod n$ and hence
(using the fact that $d_{k}$ divides $\sigma_{b}$)

$m(k/d_{k})-\alpha(\sigma_{b}/d_{k})=m^{\prime}(k/d_{k})-\alpha^{\prime}(\sigma_{b}/d_{k})\bmod
n/d_{k}.$

Since $d_{s}$ divides both $n/d_{k}$ and $\sigma_{b}/d_{k}$, we deduce that
$m(k/d_{k})=m^{\prime}(k/d_{k})\bmod d_{s}$. But $k/d_{k}$ is coprime to
$n/d_{k}$ and so $k/d_{k}$ is coprime to $d_{s}$. Hence $m=m^{\prime}\bmod
d_{s}$ and so $m=m^{\prime}$. We deduce that
$\alpha\sigma_{b}=\alpha^{\prime}\sigma_{b}\bmod n$, and so
$\alpha\sigma_{b}/(d_{s}d_{k})=\alpha^{\prime}\sigma_{b}/(d_{s}d_{k})\bmod
n/(d_{s}d_{k})$. Now $\sigma_{b}/(d_{s}d_{k})$ is coprime to $n/(d_{s}d_{k})$,
by Lemma 10, and so $\alpha=\alpha^{\prime}$.

We have shown that $\pi$ is a permutation, it is clear that $\pi(0)=0$, and it
is not hard to see that $\pi$ is clockwise. Consider the generalisation of the
packing of $s\times k$ rectangles in the plane $\mathbb{Z}^{2}$ mentioned in
Section 3. So the $(\ell,m)$th rectangle in the packing has lower left corner
at the cell with position

$\left(\ell s+\sum_{i=0}^{m-1}a_{i},mk-\sum_{i=0}^{\ell-1}b_{i}\right).$

This rectangle packing is invariant with respect to the integer lattice $\cal
L$ generated by $u$ and $v$, where

$\displaystyle u$
$\displaystyle=(d_{k}s,-\sum_{i=0}^{d_{k}-1}b_{i})=(d_{k}s,-\sigma_{b})\text{
and}$ $\displaystyle v$
$\displaystyle=(\sum_{i=0}^{d_{s}-1}a_{i},d_{s}k)=(\sigma_{a},d_{s}k).$

We note that

$\displaystyle\frac{k}{d_{k}}u+\frac{\sigma_{b}}{d_{s}d_{k}}v$
$\displaystyle=(ks+r,0)=(n,0)\text{ and}$
$\displaystyle-\frac{\sigma_{a}}{d_{s}d_{k}}u+\frac{s}{d_{s}}v$
$\displaystyle=(0,r+ks)=(0,n).$

Now $d_{s}d_{k}$ divides $\sigma_{a}$ and $\sigma_{b}$, since we have an
$(n,s,k)$-jumper. So $(n,0)$ and $(0,n)$ are $\mathbb{Z}$-linear combinations
of $u$ and $v$, and therefore lie in $\cal L$. Thus our packing induces a
well-defined packing of the torus $\mathbb{Z}_{n}^{2}$. The argument in
Theorem 9 now shows that $\pi$ is $(s,k)$-clash-free.

The process of producing a jumper from a permutation, and the process of
producing a permutation from a jumper, are inverse to each other. So we have a
bijections between $(s,k,n)$-jumpers and clockwise $(s,k)$-clash free
permutations of $\mathbb{Z}_{n}$ with $\pi(0)=0$, as required. ∎

## References

  * [1] Brian Alspach, ‘The wonderful Walecki construction’, _Bull. Inst. Combin. Appl._ 52 (2008) 7–20.
  * [2] David Bevan, Cheyne Homberger and Bridget Eileen Tenner, ‘Prolific permutations and permuted packings: downsets containing many large patterns’, _J. Combin. Theory Ser. A_ 153 (2018) 98–121.
  * [3] Simon R. Blackburn, ‘Permutations that separate close elements’, _J. Combin. Theory Ser. A_ 196 (2023), article 105734.
  * [4] Simon R. Blackburn, Cheyne Homberger and Peter Winkler, ‘The minimum Manhattan distance and minimum jump of permutations’, _J. Combin. Theory Ser. A_ 161 (2019) 364–386.
  * [5] Richard A. Brualdi, Kathleen P. Kiernan, Seth A.Meyer and Michael W. Schroeder, ‘Cyclic matching sequencibility of graphs’, _Australas. J. Combin._ 53 (2012), 245–256.
  * [6] Severin Hertzsprung, ‘En kombinationsopgave’, _Tidsskrift for mathematik_ 5 (1887), 13–17.
  * [7] Irving Kaplansky, ‘Symbolic solution of certain problems in permutations’, _Bull. Amer. Math. Soc._ 50 (1944), 906–914.
  * [8] Donald L. Kreher, Adrián Pastine and Leah Tollefson, ‘A note on the cyclic matching sequencibility of graphs’, _Australas. J. Combin._ 61 (2015) 142–146
  * [9] Adam Mammoliti and Jamie Simpson, ‘Permutations in which pairs of numbers are not simultaneously close in position and close in size’, _Australas. J. Combin._ 78 (2020) 11–34.