---
abstract: 'A classical recursive construction for mutually orthogonal latin squares (MOLS) is shown to hold more generally for a class of permutation codes of length $n$ and minimum distance $n-1$. When such codes of length $p+1$ are included as ingredients, we obtain a general lower bound $M(n,n-1) \ge n^{1.079}$ for large $n$, gaining a small improvement on the guarantee given from MOLS.'
address:
- 'Sergey Bereg: Computer Science, University of Texas at Dallas, Richardson, TX '
- 'Peter J.  Dukes: Mathematics and Statistics, University of Victoria, Victoria, BC '
author:
- Sergey Bereg
- 'Peter J. Dukes'
title: |
    A lower bound on permutation codes\
    of distance $n-1$
---

------------------------------------------------------------------------

Introduction
============

Let $n$ be a positive integer. The *Hamming distance* between two permutations $\sigma, \tau \in \mathcal{S}_n$ is the number of non-fixed points of $\sigma \tau^{-1}$, or, equivalently, the number of disagreements when $\sigma$ and $\tau$ are written as words in single-line notation. For example, $1234$ and $3241$ are at distance three.

A *permutation code* PC$(n,d)$ is a subset $\Gamma$ of $\mathcal{S}_n$ such that the distance between any two distinct elements of $\Gamma$ is at least $d$. Language of classical coding theory is often used: elements of $\Gamma$ are *words*, $n$ is the *length* of the code, and the parameter $d$ is the *minimum distance*, although for our purposes it is not important whether distance $d$ is ever achieved. Permutation codes are also called *permutation arrays* by some authors, where the words are written as rows of an $n \times |\Gamma|$ array.

The investigation of permutation codes essentially began with the articles [@DV; @FD]. After a decade or so of inactivity on the topic, permutation codes enjoyed a resurgence due to various applications. See [@CCD; @H; @SM] for surveys of construction methods and for more on the coding applications.

For positive integers $n \ge d$, we let $M(n,d)$ denote the maximum size of a PC$(n,d)$. It is easy to see that $M(n,1)=M(n,2)=n!$, and that $M(n,n)=n$. The Johnson bound $M(n,d) \le n!/(d-1)!$ holds. The alternating group $A_n$ shows that $M(n,3)=n!/2$. More generally, a sharply $k$-transitive subgroup of $\mathcal{S}_n$ furnishes a permutation code of (maximum possible) size $n!/(n-k)!$. For instance, the Mathieu groups $M_{11}$ and $M_{12}$ are maximum PC$(11,7)$ and PC$(12,7)$, respectively. On the other hand, determination of $M(n,d)$ absent any algebraic structure appears to be a difficult problem. As an example, it is only presently known that $78 \le M(7,5) \le 134$; see [@BD; @JLOS] for details. A table of bounds on $M(n,d)$ can be found in [@SM].

In [@CKL], it was shown that the existence of $r$ mutually orthogonal latin squares (MOLS) of order $n$ yields a permutation code PC$(n,n-1)$ of size $rn$. Although construction of MOLS is challenging in general, the problem is at least well studied. Lower bounds on MOLS can be applied to the permutation code setting, though it seems for small $n$ not a prime power that the code sizes can be much larger than the MOLS guarantee. For example, $M(6,5) =18$ despite the nonexistence of orthogonal latin squares of order six, and $M(10,9) \ge 49$, [@JS], when no triple of MOLS of order 10 is known. On the other hand, it is straightforward to see, [@CKL], that $M(n,n-1)=n(n-1)$ implies existence of a full set of MOLS (equivalently a projective plane) of order $n$, so any nontrivial upper bound on permutation codes would have major impact on design theory and finite geometry. This connection is explored in more detail in [@BM]. Permutation codes are used in [@JS2] for some recent MOLS constructions.

Let $N(n)$ denote the maximum number of MOLS of order $n$. Chowla, Erdős and Strauss showed in [@CES] that $N(n)$ goes to infinity. Wilson, [@WilsonMOLS], found a construction strong enough to prove $N(n) \ge n^{1/17}$ for sufficiently large $n$. Subsequently, Beth, [@Beth] tightened some number theory in the argument to lift the exponent to $1/14.8$. In terms of permutation codes, then, one has $M(n,n-1) \ge n^{1+1/14.8}$ for sufficiently large $n$.

Our main result in this note gives a small improvement to the exponent.

\[main\] $M(n,n-1) \ge n^{1+1/12.533}$ for sufficiently large $n$.

The proof is essentially constructive, although it requires, as does [@Beth; @WilsonMOLS], the selection of a ‘small’ integer avoiding several arithmetic progressions. This is guaranteed by the Buchstab sieve; see [@Ivt]. Apart from this number theory, our construction method generalizes a standard design-theoretic construction for MOLS to permutation codes posessing a small amount of additional structure. Some set up for our methodology is given in the next two sections, and the proof of Theorem \[main\] is given in Section \[proof\] as a consequence of the somewhat stronger Theorem \[idem-bound\]. We conclude with a discussion of some possible next directions for this work.

Idempotent permutation codes and latin squares
==============================================

Let $[n]:=\{1,2,\dots,n\}$. Recall that a *fixed point* of a permutation $\pi:[n]\rightarrow [n]$ is an element $i \in [n]$ such that $\pi(i)=i$. In single-line notation, this says symbol $i$ is in position $i$. Of course, for the identity permutation $\iota$, every element is a fixed point.

Let us say that a permutation code is *idempotent* if each of its words has exactly one fixed point. As some justification for the definition, recall that a latin square $L$ of order $n$ is idempotent if the $(i,i)$-entry of $L$ equals $i$ for each $i \in [n]$. So, a maximum PC$(n,n)$ is idempotent if and only if the ‘corresponding’ latin square is idempotent.

We are particularly interested in idempotent PC$(n,n-1)$ in which every symbol is a fixed point of the same number, say $r$, words; these we call $r$-*regular* and denote by $r$-IPC$(n,n-1)$. Permutation codes with extra ‘distributional’ properties have been investigated before. For example, ‘$k$-uniform’ permutation arrays are introduced in [@DV], while ‘$r$-balanced’ and ‘$r$-separable’ permutation arrays are considered in [@DFKW]. However, our definition is seemingly new, or at least not obviously related to these other conditions.

If there exists an $r$-IPC$(n,n-1)$, say $\Delta$, then $\Delta \cup \{\iota\}$ is also a PC$(n,n-1)$. Consequently, $M(n,n-1) \ge rn+1$. It follows that $r \le n-2$ is an upper bound on $r$.

On the other hand, if $\Gamma$ is a PC$(n,n-1)$ containing $\iota$, then the words of $\Delta$ at distance exactly $n-1$ from $\iota$ form an idempotent IPC$(n,n-1)$. Concerning the $r$-regular condition, whether $\iota \in \Gamma$ or not, we may find an $r$-IPC$(n,n-1)$ with $$\label{r-formula}
r=\max_{\sigma \in \Gamma} \min_{i \in [n]} |\{\tau \in \Gamma \setminus \{\sigma\}: \tau(i)=\sigma(i)\}|.$$ In more detail, if $\sigma$ achieves the maximum in (\[r-formula\]), then for each $i=1,\dots,n$ we choose exactly $r$ elements $\tau \in \Gamma$ which agree with $\sigma$ in position $i$. After relabelling each occurrence of $\sigma(i)$ to $i$, we have the desired $r$-idempotent PC$(n,n-1)$.

A question in its own right is whether there exists an $r$-IPC$(n,n-1)$ for $r = \lfloor \frac{1}{n}(M(n,n-1)-1) \rfloor$. However, relatively little is known about maximum permutation code sizes. Indeed, the exact value of $M(n,n-1)$ is known only for $n=q$, a prime power, ($M(q,q-1) = q(q-1)$, [@FD]) and for $n=6$ ($M(6,5)=18$, [@K6]).

\[ipc6\] A 2-IPC$(6,5)$: $$\begin{array}{cc}
1\  3\  5\  6\  2\  4\ &   1\  4\  6\  2\  3\  5 \\
6\  2\  4\  5\  3\  1\ &   5\  2\  1\  3\  6\  4\\
5\  6\  3\  1\  4\  2\ &   4\  5\  3\  2\  6\  1\\
2\  5\  6\  4\  1\  3\ &   3\  6\  1\  4\  2\  5\\
3\  1\  4\  6\  5\  2\ &   6\  4\  2\  1\  5\  3\\
4\  3\  2\  5\  1\  6\  &  2\  1\  5\  3\  4\  6\\
\end{array}$$

A 3-IPC$(10,9)$ (symbol ‘0’ is used for ‘10’): $$\begin{array}{ccc}
\ 1\ 8\ 6\ 2\ 9\ 5\ 4\ 0\ 3\ 7& \ 1\ 5\ 0\ 9\ 7\ 4\ 3\ 6\ 2\ 8& \ 1\ 3\ 8\ 0\ 6\ 9\ 5\ 2\ 7\ 4\\
\ 8\ 2\ 1\ 9\ 6\ 7\ 0\ 4\ 5\ 3& \ 3\ 2\ 5\ 6\ 9\ 8\ 1\ 7\ 0\ 4& \ 9\ 2\ 8\ 7\ 4\ 1\ 3\ 0\ 6\ 5\\
\ 5\ 9\ 3\ 2\ 7\ 8\ 0\ 1\ 4\ 6& \ 8\ 7\ 3\ 5\ 2\ 0\ 4\ 9\ 6\ 1& \ 9\ 4\ 3\ 1\ 6\ 2\ 8\ 5\ 0\ 7\\
\ 9\ 7\ 1\ 4\ 0\ 3\ 5\ 6\ 8\ 2& \ 6\ 3\ 2\ 4\ 1\ 0\ 9\ 7\ 5\ 8& \ 0\ 8\ 9\ 4\ 3\ 1\ 2\ 5\ 7\ 6\\
\ 0\ 3\ 6\ 7\ 5\ 2\ 1\ 4\ 8\ 9& \ 3\ 8\ 4\ 0\ 5\ 7\ 9\ 1\ 6\ 2& \ 7\ 9\ 2\ 8\ 5\ 4\ 6\ 3\ 0\ 1\\
\ 9\ 8\ 7\ 5\ 1\ 6\ 0\ 3\ 2\ 4& \ 8\ 9\ 4\ 1\ 0\ 6\ 2\ 7\ 3\ 5& \ 5\ 1\ 0\ 3\ 9\ 6\ 8\ 4\ 7\ 2\\
\ 3\ 0\ 9\ 8\ 1\ 2\ 7\ 6\ 4\ 5& \ 5\ 4\ 6\ 0\ 8\ 1\ 7\ 9\ 2\ 3& \ 8\ 6\ 0\ 2\ 4\ 3\ 7\ 5\ 1\ 9\\
\ 2\ 6\ 7\ 1\ 9\ 0\ 5\ 8\ 4\ 3& \ 4\ 1\ 9\ 0\ 2\ 3\ 6\ 8\ 5\ 7& \ 7\ 0\ 1\ 3\ 4\ 5\ 9\ 8\ 2\ 6\\
\ 0\ 7\ 4\ 6\ 1\ 5\ 8\ 2\ 9\ 3& \ 2\ 1\ 6\ 8\ 0\ 7\ 3\ 5\ 9\ 4& \ 4\ 5\ 7\ 3\ 6\ 8\ 2\ 0\ 9\ 1\\
\ 6\ 5\ 1\ 7\ 2\ 9\ 8\ 3\ 4\ 0& \ 4\ 6\ 5\ 8\ 7\ 1\ 9\ 2\ 3\ 0& \ 2\ 4\ 8\ 9\ 3\ 5\ 6\ 7\ 1\ 0\\
\end{array}$$

The connection with MOLS is important in the sequel. The following result is essentially the construction from MOLS to PC$(n,n-1)$ in [@CKL], except that here we track the idempotent condition.

\[idemp-MOLS\] If there exist $r$ mutually orthogonal idempotent latin squares of order $n$, then there exists an $r$-IPC$(n,n-1)$.

Suppose $L_1,\dots,L_r$ are the hypothesized latin squares, each on the set of symbols $[n]$. For each $i \in [n]$ and $j \in [r]$, define the permutation $\pi_{i,j} \in \mathcal{S}_n$ by $\pi_{i,j}(x) = y$ if and only if the $(x,y)$-entry of $L_j$ is $i$. Let $\Gamma = \{\pi_{i,j} : i \in [n], j \in [r]\}$. Consider distinct permutations $\pi_{i,j}$ and $\pi_{h,k}$ in $\Gamma$. They have no agreements if $j=k$, by the latin property, and they have exactly one agreement if $j \neq k$ by the orthogonality of squares $L_j$ and $L_k$. So $\Gamma$ is a PC$(n,n-1)$. Moreover, since each $L_j$ is an idempotent latin square, the permutation $\pi_{i,j}$ has only the fixed point $i$. It follows that $\Gamma$ is in fact an $r$-IPC$(n,n-1)$.

We remark that the maximum number of mutually orthogonal idempotent latin squares of order $n$ is either $N(n)$ or $N(n)-1$, since we may permute rows and columns of one square so that its main diagonal is a constant, and then permute symbols of the other squares. That is, our idempotent condition is negligible as far as the rate of growth of $r$ in terms of $n$ is concerned.

\[prime-powers\] For prime powers $q$, there exists a $(q-2)$-IPC$(q,q-1)$.

More generally, MacNeish’s lower bound on MOLS leads to a similar bound for idempotent permutation codes.

\[product\] If $n=q_1\dots q_t$ is factored as a product of powers of distinct primes, then there exists a $(q-2)$-IPC$(n,n-1)$ where $q=\min\{q_i : i=1,\dots,t\}$.

Finally, it is worth briefly considering a ‘reverse’ of the MOLS construction for PC$(n,n-1)$. Suppose a PC$(n,n-1)$, say $\Gamma$, is partitioned into PC$(n,n)$, say $\Gamma_1,\dots,\Gamma_r$. We define $r$ partial latin squares as linear combinations of permutation matrices for $\Gamma_i$ with symbolic coefficients. Since two distinct words of the code have at most one agreement, overlaying any two of the $r$ partial latin squares leads to distinct ordered pairs of symbols over the common non-blank cells. We merely offer an example, but remark that this viewpoint is helpful for our recursive construction to follow.

The $2$-IPC$(6,5)$ of Example \[ipc6\] admits a partition into three disjoint PC$(6,6)$; this can be seen by reading the array four rows at a time. Each of these sub-arrays is converted into a partial latin square of order six, where a permutation $\pi$ having fixed point $i$ fills all cells of the form $(x,\pi(x))$ in its square with symbol $i$. $$\begin{array}{|c|c|c|c|c|c|}
\hline
1&4&&&3&2\\
\hline
&2&1&&4&3\\
\hline
&&3&2&1&4\\
\hline
3&&&4&2&1\\
\hline
4&1&2&3&&\\
\hline
2&3&4&1&&\\
\hline
\end{array}
\hspace{1cm}
\begin{array}{|c|c|c|c|c|c|}
\hline
1&&5&6&2&\\
\hline
5&2&6&1&&\\
\hline
2&6&&5&&1\\
\hline
&1&2&&6&5\\
\hline
6&&1&&5&2\\
\hline
&5&&2&1&6\\
\hline
\end{array}
\hspace{1cm}
\begin{array}{|c|c|c|c|c|c|}
\hline
&6&4&3&&5\\
\hline
6&&&5&3&4\\
\hline
4&5&3&&6&\\
\hline
5&3&6&4&&\\
\hline
&4&&6&5&3\\
\hline
3&&5&&4&6\\
\hline
\end{array}$$

A recursive construction using block designs
============================================

In this section, we observe that idempotent permutation codes can be combined to produce larger such codes. Since the resultant code must preserve at most one agreement between different words, we are naturally led to consider block designs to align the ingredient codes.

A *pairwise balanced design* PBD$(n,K)$ is a pair $(V,\mathcal{B})$, where $V$ is a set of size $n$, $\mathcal{B}$ is a family of subsets of $V$ with sizes in $K$, and such that every pair of distinct elements of $V$ belongs to exactly one set in $\mathcal{B}$. The sets in $\mathcal{B}$ are called *blocks*. Thinking of a PBD as a special type of hypergraph, we refer the elements of $V$ as *vertices* or *points*.

The following construction is inspired from a similar one for MOLS; see [@CD Theorem 3.1].

\[pbd-construction\] If there exists a PBD$(n,K)$ and, for every $k \in K$, there exists an $r$-IPC$(k,k-1)$, then there exists an $r$-IPC$(n,n-1)$.

Let $([n],\mathcal{B})$ be a PBD$(n,K)$. For each block $B \in \mathcal{B}$, take a copy of an $r$-IPC$(|B|,|B|-1)$ on the symbols of $B$. Its permutations are, say, $\pi_{i,j}^B:B \rightarrow B$, for $i \in B$, $j =1,\dots,r$, where $\pi_{i,j}^B(i)=i$ is the unique fixed point for $\pi_{i,j}^B$.

Let $i \in [n]$ and put $\mathcal{B}_i:=\{B \in \mathcal{B}: i \in B\}$, the set of blocks containing symbol $i$. Since $\mathcal{B}$ is the block set of a PBD, we have that $\mathcal{B}_i$ is a partition of $[n] \setminus \{i\}$. For $j=1,\dots,r$, define a permutation $\pi_{i,j}:[n] \rightarrow [n]$ by $$\pi_{i,j}(x) = \begin{cases}
i & \text{if~} x =i, \\
\pi^B_{i,j}(x) & \text{if~} x\neq i, \text{~where~} x \in B \in \mathcal{B}_i.
\end{cases}$$ We claim that $\{\pi_{i,j}:i \in [n], j \in [r]\}$ is an $r$-IPC$(n,n-1)$ such that, for each $i$, the subset $\{\pi_{i,j}: j \in [r]\}$ has precisely the fixed point $i$. First, each $\pi_{i,j}$ is a permutation. That $([n],\mathcal{B})$ is a PBD ensures that $\pi_{i,j}$ is well-defined and bijective. In particular, if $a \in [n]$, $a \neq i$, we have $\{i,a\}$ contained in a unique block, say $A \in \mathcal{B}$.

It remains to check the minimum distance. Consider $\pi_{i,j}$ and $\pi_{i,j'}$ for $j \neq j'$. They agree on $i$, but suppose for contradiction that they agree also on $h \neq i$. Let $B$ be the unique block of $\mathcal{B}_i$ containing $h$. By construction, we must have $\pi^B_{i,j}$ agreeing with $\pi^B_{i,j'}$ at $h$, and this is a contradiction to the minimum distance being $|B|-1$ within this component code.

Now, consider $\pi_{i,j}$ and $\pi_{i',j'}$ for $i \neq i'$. Suppose they agree at distinct positions $h$ and $l$. Say $\pi_{i,j}(h)=\pi_{i',j'}(h)=a$ and $\pi_{i,j}(l) = \pi_{i',j'}(l) = b$. Then $\{i,i',h,a\}$ and $\{i,i',l,b\}$ are in the same block. It follows that $h,l$ are in the same block and we get a contradiction again.

We illustrate the construction of Theorem \[pbd-construction\].

Figure \[idpc10\] shows a PBD$(10,\{3,4\})$ at left. The design is built from an affine plane of order three (on vertex set $\{1,\dots,9\}$) with one parallel class extended (to vertex $0$). In the center, template idempotent permutation codes of lengths 3 and 4 are shown. The code of length three is simply an idempotent latin square, but note that the code of length four achieves minimum distance three. On the right is shown the resultant $1$-IPC$(10,9)$, an unimpressive code for illustration only. It can be checked that two rows agree in at most one position (which if it exists is found within the unique block containing the chosen row labels).

$$\begin{array}{cccc}
\{0,1,2,3\} & \{1,4,7\} & \{1,5,9\} & \{1,6,8\} \\
\{0,4,5,6\} & \{2,5,8\} & \{2,6,7\}  & \{2,4,9\}  \\
\{0,7,8,9\} & \{3,6,9\}  & \{3,4,8\}  & \{3,5,7\}  \\
\end{array}$$

(-2.5,0)–(1,0); (-2.5,0) to \[out=45,in=180\] (-1,1); (-2.5,0) to \[out=-45,in=180\] (-1,-1);

(-1,1)–(1,1); (-1,-1)–(1,-1); (0,-1)–(0,1); (1,-1)–(1,1); (-1,-1)–(-1,1); (1,1)–(-1,-1); (1,-1)–(-1,1);

(0,1)–(-1,0); (-1,0) to \[out=225,in=90\] (-1.5,-1); (1,-1) to \[out=225,in=270\] (-1.5,-1);

(0,-1)–(1,0); (1,0) to \[out=45,in=270\] (1.5,1); (-1,1) to \[out=45,in=90\] (1.5,1);

(0,1)–(1,0); (1,0) to \[out=315,in=90\] (1.5,-1); (-1,-1) to \[out=315,in=270\] (1.5,-1);

(0,-1)–(-1,0); (-1,0) to \[out=135,in=270\] (-1.5,1); (1,1) to \[out=135,in=90\] (-1.5,1);

at (-2.5,0.3) [$0$]{}; at (-0.3,0) [$5$]{}; at (0,1.3) [$2$]{}; at (0,-1.3) [$8$]{}; at (.7,0) [$6$]{}; at (1,1.3) [$3$]{}; at (1,-1.3) [$9$]{}; at (-1.3,0) [$4$]{}; at (-1,1.3) [$1$]{}; at (-1,-1.3) [$7$]{};

(-2.5,0) circle \[radius=.1\]; (0,0) circle \[radius=.1\]; (0,1) circle \[radius=.1\]; (0,-1) circle \[radius=.1\]; (1,0) circle \[radius=.1\]; (1,1) circle \[radius=.1\]; (1,-1) circle \[radius=.1\]; (-1,0) circle \[radius=.1\]; (-1,1) circle \[radius=.1\]; (-1,-1) circle \[radius=.1\];

 

  -------
   a c b
   c b a
   b a c
  -------

  ---------
   a c d b
   c b d a
   d a c b
   b c a d
  ---------

 

$$\begin{array}{c}
0\ 2\ 3\ 1\ 5\ 6\ 4\ 8\ 9\ 7\\
2\ 1\ 3\ 0\ 7\ 9\ 8\ 4\ 6\ 5\\
3\ 0\ 2\ 1\ 9\ 8\ 7\ 6\ 5\ 4\\
1\ 2\ 0\ 3\ 8\ 7\ 9\ 5\ 4\ 6\\
5\ 7\ 9\ 8\ 4\ 6\ 0\ 1\ 3\ 2\\
6\ 9\ 8\ 7\ 0\ 5\ 4\ 3\ 2\ 1\\
4\ 8\ 7\ 9\ 5\ 0\ 6\ 2\ 1\ 3\\
8\ 4\ 6\ 5\ 1\ 3\ 2\ 7\ 9\ 0\\
9\ 6\ 5\ 4\ 3\ 2\ 1\ 0\ 8\ 7\\
7\ 5\ 4\ 6\ 2\ 1\ 3\ 8\ 0\ 9\\
\end{array}$$

We conclude this section with an existence result for pairwise balanced designs. This is implicit in early constructions of mutually orthogonal latin squares, [@CES; @WilsonMOLS]. We extend the use to permutation codes later.

\[pbd-existence\] Suppose $m,t,u$ are integers satisfying $N(t) \ge m-1$ and $0 \le u \le t$. Then there exists a PBD$(mt+u,\{m,m+1,t,u\})$.

We use some design theory terminology from [@WilsonMOLS]. First, the existence of $m-1$ MOLS of order $t$ gives a transversal design TD$(m+1,t)$. Delete all but $u$ points from one group of this TD, and turn groups into blocks. We claim that the resulting system is a PBD of the required parameters. The total number of points is $mt+u$ and block sizes are in $\{m,m+1,t,u\}$, as needed. And, every pair of points, whether in the same or different groups of the original TD, appear together in a unique block.

An improved exponent {#proof}
====================

We apply the partition and extension technique from [@BMS] to construct an idempotent permutation code. Consider AGL$(1,p)$, the affine general linear group of permutations on ${\mathbb{Z}}_p$, i.e. $$\text{AGL}(1,p)=\{x \mapsto ax+b : a,b\in {\mathbb{Z}}_p, a\neq 0\}.$$ First, we pick the largest $k<n$ such that $2k\le\lceil p/k\rceil+1$. Note that $2x\le\lceil p/x\rceil+1$ holds if $x=\sqrt{p/2}$ and fails if $x=\sqrt{p/2}+1$. Therefore $k=\lfloor \sqrt{p/2}\rfloor$ or $k=\lceil \sqrt{p/2}\rceil$. Put $s=\lceil p/k\rceil$. Write $n=p$ as a sum $n=n_1+n_2+\dots +n_k$ where $n_i\ge s$ for all $i$. Take an ordered partition ${\mathcal{P}}=(P_1,\dots,P_k)$ of ${\mathbb{Z}}_p$ into $k$ blocks of consecutive elements with $|P_i|=n_i$ for all $i$. Let us say that a permutation $\pi : {\mathbb{Z}}_p \rightarrow {\mathbb{Z}}_p$ is [*covered by*]{} $P_i$ for some $i=1,\dots,k$ if there exists $x\in P_i$ such that $\pi(x)\in P_i$.

\[lemma-prime-plusone\] Let $p$ be a prime with $p\ge 5$. For any integer $j$ with $k \le j\le s$, and any $i=1,\dots,k$, all permutations in $B_j:=\{ jx+b : b\in{\mathbb{Z}}_p\}$ are covered by $P_i$.

Take a permutation $\pi(x)=jx+b$ from $B_j$. Suppose that $P_i=\{m+1,m+2,\dots,m+n_i\}$. Then $\pi(P_i)=\{\pi(m+1),\pi(m+2),\dots,\pi(m+n_i)\}$ is an arithmetic sequence over ${\mathbb{Z}}_p$ with common difference $j$. We show that $\pi(P_i)\cap P_i\ne\emptyset$. Suppose to the contrary that $\pi(P_i)\cap P_i =\emptyset$. Since $j\le s$, $P_i$ does not have any element in $\{\pi(m')+1,\pi(m')+2,\dots, \pi(m')+n_i-1\}$ for any $m',m+1\le m'<m+n_i$. Let $S$ be the set $\{t \in {\mathbb{Z}}: j(m+1)+b\le t\le j(m+n_i)+b\}$ and let $S_p=\{t \pmod{p} : t\in S\}$. Since $\pi(P_i)\cap P_i =\emptyset$, $P_i$ does not have any element in set $S_p$. If $|S|\ge p$ then $|S_p|=p$ and $S_p={\mathbb{Z}}_p$ contradicting $S_p\cap P_i =\emptyset$. Thus $|S|=j(n_i-1)+1<p$ and $|S_p|=|S|$. Now, in view of $$jn_i\ge ks=k\cdot \lceil p/k\rceil\ge p,$$ we have $|{\mathbb{Z}}_p \setminus S_p|\le j-1$. This contradicts the fact that $|P_i|=n_i>j-1$.

\[prime-plusone\] For primes $p\ge 5$, there exists an $r$-IPC$(p+1,p)$ where $r=k-1 = O(\sqrt{p})$ as above.

Following [@BMS], create the distance-$p$ partition system $\Pi=({\mathcal{M}},{\mathcal{P}},{\mathcal{Q}})$ on ${\mathbb{Z}}_p$ such that:

1.  ${\mathcal{M}}=(M_1,M_2,\dots,M_{k+1})$, where $M_1,M_2,\dots,M_k$ are selected as cosets $B_k,B_{k+1},\dots,B_{2k-1}$ from Lemma \[lemma-prime-plusone\], and $M_{k+1}=B_1$ is an additional coset, noting that $p \ge 5$ implies $k \ge 2$;

2.  ${\mathcal{P}}={\mathcal{Q}}=(P_1,P_2,\dots,P_{k})$.

First, we show that there are enough cosets to choose from Lemma \[lemma-prime-plusone\], i.e. that $k\le s-k+1$. This follows by the choice of $k$ and $s$ above.

The extension $ext(\Pi)$ of $\Pi$ is a PC$(p+1,p)$ by [@BMS Theorem 1]. A $(k-1)$-IPC$(p+1,p)$ can be obtained from it as follows. Every permutation in $M_j, j=1,\dots,k$, has a unique fixed point. A fixed point of a permutation may disappear due to the extension. We remove permutations without fixed points. There are at most $n_j$ permutations removed from $ext(M_j)$. The sets $P_1,\dots,P_k$ are disjoint, and so every symbol $0,1,\dots,p-1$ is a fixed point in at least $k-1$ of the remaining permutations. By removing some permutations if necessary we can make every symbol $0,1,\dots,p-1$ a fixed point exactly $k-1$ times.

Finally, we carefully choose $M_{k+1}$. Pick any $k-1$ permutations from coset $B_1$ except the identity permutation $0,1,2, \dots, p-1$. Adjoin $p$ at the end of every permutation. Then symbol $p$ will be the only fixed point and the entire permutation code is a $(k-1)$-IPC$(p+1,p)$.

Next we cite an important number-theoretic result used in [@Beth] for MOLS.

Let $2=p_0,p_1,\dots,p_k$ be the primes less than or equal to $y$, and let $\omega=\{a_0,a_1,\dots,a_k,b_1,\dots,b_k\}$ be a set of $2k+1$ integers. Let $B_\omega (x,y)$ denote the number of positive integers $z \le x$ which do not lie in any of the arithmetic progressions $z  \equiv a_i \pmod{p_i}$, $i=0,1,\dots,k$ or $z \equiv b_j \pmod{p_j}$, $j=1,\dots,k$. Then $B_\omega(x,x^{4.2665})$ tends to infinity with $x$, independent of the selections $\omega$.

The tools are now in place for our asymptotic lower bound on $M(n,n-1)$.

\[idem-bound\] For sufficiently large $n$, there exists an $r$-IPC$(n,n-1)$ with $r \ge n^{1/12.533}$.

We follow a similar strategy as in [@Beth; @WilsonMOLS], applying the Buchstab sieve.

Put $\gamma=1/12.533$ and $r=\lceil n^\gamma \rceil$. Choose a prime $m$ with $2(r+2)^2 \le m \le 4(r+2)^2$. Then in view of Theorems \[product\] and \[prime-plusone\], there exist both $r$-IPC$(m,m-1)$ and $r$-IPC$(m+1,m)$. Use the Buchstab sieve to select an integer $t'$, $0 \le t' \le n^{4.2665 \times 2 \gamma} < n^{0.681}$, so that, with $t:=t'+\lfloor \frac{n}{m+1} \rfloor$, we have $t \not\equiv 0 \pmod{p}$ and $mt \not\equiv n \pmod{p}$ for each prime $p \le m$. Put $u=n-mt$ so that $n=mt+u$. By choice of $t$, and Theorem \[product\] again, there exist $r$-IPC$(t,t-1)$ and $r$-IPC$(u,u-1)$. In addition, we have $N(t) >m$ from MacNeish’s bound.

Since $t \ge \frac{n}{m+1}$, we have $u \le t$. And, for large $n$, $$t \le n^{0.681} + n/(m+1) \le n/m + \left( n^{0.681} - \frac{n}{m(m+1)} \right) \le n/m,$$ from which it follows that $u \ge 0$. By Lemma \[pbd-existence\], there exists a PBD$(mt+u,\{m,m+1,t,u\})$. Hence, by Theorem \[pbd-construction\], there exists an $r$-IPC$(n,n-1)$.

Our main result, Theorem \[main\], stating that $M(n,n-1) \ge n^{1+1/12.533}$ is now an immediate consequence of Theorem \[idem-bound\].

Discussion
==========

Our exponent $1/12.533$ is only slightly better than the $1/14.8$ already known for MOLS. However, in certain cases it may be possible to construct a PBD whose block sizes are large primes or primes plus one. For example, a projective plane of order $p$ is a PBD$(p^2+p+1,\{p+1\})$. If $p'$ is another prime, say with $\sqrt{2p} < p' < p$, then, by deleting all but $p'$ points from one line of this plane we obtain a PBD$(p^2+p',\{p',p,p+1\})$. Our construction gives an $r$-IPC$(n,n-1)$ with $r$ on the order of $n^{1/4}$, and this is not in general subsumed by existing MOLS bounds nor existing permutation code constructions. A little more generally, an exponent approaching 1/4 can be achieved when $n$ has a representation $n=p_1+p_2 p_3$ for primes $p_i$ satisfying $n^{1/2-\epsilon} < p_1 < \max\{p_2,p_3\} <n^{1/2-\epsilon}$.

The exponent could also be improved if a better construction for designs with large block sizes could be used in place of Lemma \[pbd-existence\]. Even with our family of designs from Lemma \[pbd-existence\], the hypothesis $N(t) \ge m-1$ significantly harms our exponent. Wilson’s construction for MOLS in [@WilsonMOLS] drops this strong requirement on $t$. However, a preliminary look at the construction suggests that a suitable relaxation for permutation codes PC$(n,n-1)$ likely demands a partition into codes of full distance, so that some latin square structure is maintained. This is an idea worth exploring in future work.

In another effort to work around the hypothesis $N(t) \ge m-1$, we explored letting $t=s^2$ for an integer $s$ with no prime factors up to about $\sqrt{m}$. Our remainder $u=n-ms^2$ is then a quadratic in $s$ and one must avoid an extra arithmetic progression. The allowed range for $s$ is too small for the trade-off to be worthwhile.

Applying equation (\[r-formula\]) to a known permutation code with $n=60$, we can report the existence of a $6$-IPC$(60,59)$. By comparison, it is only known that $N(60) \ge 5$; see [@Abel]. As a next step in researching $r$-IPC$(n,n-1)$, it would be interesting to accumulate some additional good examples, primarily in the case when neither $n$ nor $n-1$ is a prime power.

Finding a maximum idempotent code (with the assumption on $r$-regularity dropped) is closely related to finding a smallest maximal set of permutations at distance $n$ in a PC$(n,n-1)$. Some preliminary experiments on known codes suggests that it is sometimes possible to have one permutation at distance exactly $n-1$ to all others. As one example, the current lower bound in the case $n=54$ is $408$ (see [@BMS]), yet there is an idempotent code of size $407$.

Finally, we remark that using designs to join permutation codes may be a fruitful approach not only for smaller Hamming distances, but also perhaps for other measures of discrepancy, such as the Lee metric.

[99]{}

R.J.R. Abel, Existence of five MOLS of orders 18 and 60. *J. Combin. Des.* 23 (2015), 135–139.

S. Bereg, L. Morales and I.H. Sudborough, Extending permutation arrays: improving MOLS bounds. *Des. Codes Cryptogr.* 83 (2017), 661–683.

T. Beth, Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren. *Abh. Math. Sem. Univ. Hamburg* 53 (1983), 284–288.

J. Bierbrauer and K. Metsch, A bound on permutation codes. *Electron. J. Combin.* 20 (2013), P6, 12 pp.

M. Bogaerts and P. Dukes, Semidefinite programming for permutation codes. *Discrete Math.* 326 (2014), 34–43.

S. Chowla, P. Erdős, and E.G. Strauss, On the maximal number of pairwise orthogonal latin squres of a given order. [*Canad. J. Math.*]{} 12 (1960), 204–208.

W. Chu, C.J. Colbourn, and P.J. Dukes, Permutation codes for powerline communication. [*Des. Codes Cryptography*]{} 32 (2004), 51–64.

C.J. Colbourn and J.H. Dinitz, Making the MOLS table. *Computational and constructive design theory*, 67–134, Math. Appl., 368, Kluwer Acad. Publ., Dordrecht, 1996.

C.J. Colbourn, T. Kløve, and A.C.H. Ling, Permutation arrays for powerline communication and mutually orthogonal Latin squares. [*IEEE Trans. Inform. Theory*]{} 50 (2004), 1289–1291.

M. Deza and S.A. Vanstone, Bounds for permutation arrays. [*J. Statist. Plann. Inference*]{} 2 (1978), 197–209.

C. Ding, F.-W. Fu, T. Kløve and V.K.-W.Wei, Constructions of permutation arrays. *IEEE Trans. Inform. Theory* 48 (2002), 977–980.

P. Frankl and M. Deza, On the maximum number of permutations with given maximal or minimal distance. [*J. Combin. Theory Ser. A*]{} 22 (1977), 352–360.

S. Huczynska, Powerline communication and the 36 officers problem. *Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci.* 364 (2006), 3199–3214.

H. Iwaniec, J. van de Lune and H.J.J.  te Riele, The limits of Buchstab’s iteration sieve. *Nederl. Akad. Wetensch. Indag. Math.* 42 (1980), 409–417.

I. Janiszczak, W. Lempken, P.R.J. Östergård and R. Staszewski, Permutation codes invariant under isometries, *Des. Codes Cryptogr.* 75 (2015), 497–507.

I. Janiszczak and R. Staszewski, An improved bound for permutation arrays of length 10. Preprint 4, Institute for Experimental Mathematics, University Duisburg-Essen, 2008.

I. Janiszczak and R. Staszewski, Isometry invariant permutation codes and mutually orthogonal Latin squares, <https://arxiv.org/abs/1812.06886>.

T. Kløve, Classification of permutation codes of length 6 and minimum distance 5. [*Proc. Int. Symp. Information Theory Appl.*]{}, 2000, 465–468.

D.H. Smith and R. Montemanni, A new table of permutation codes. *Des. Codes Cryptogr.* 63 (2012), 241–253.

R.M. Wilson, Concerning the number of mutually orthogonal Latin squares. *Discrete Math.* 9 (1974), 181-198.
