\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P6}{20(3)}{2013}
\usepackage{amsthm,amsmath,amssymb}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{result}[theorem]{Result}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\title{\bf A bound on permutation codes}

\author{J\"urgen Bierbrauer\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Michigan Technological University\\[-0.8ex]
\small Houghton, Michigan 49931, USA\\
\small\tt jbierbra@mtu.edu\\
\and
Klaus Metsch\\
\small Universit\"at Gie\ss en\\[-0.8ex]
\small Mathematisches Institut\\[-0.8ex]
\small Arndtstr. 2, D-35392 Gie\ss en, Germany\\
\small\tt klaus.metsch@math.uni-giessen.de
}

\date{\dateline{Nov 28, 2012}{July 18, 2013}{July 26, 2013}\\
\small Mathematics Subject Classifications: 05A05, 05B40, 51E26, 94B60}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\e{\epsilon}
\def\d{\delta}
\def\s{\sigma}
\def\sm{\setminus}

\begin{document}

\maketitle

\begin{abstract}
Consider the symmetric group $S_n$ with the Hamming metric.
A {\bf permutation code} on $n$ symbols is a subset $C\subseteq S_n.$
If $C$ has minimum distance $\geq n-1,$ then $\vert C\vert\leq n^2-n.$
Equality can be reached if and only if a projective plane of order $n$ exists.
Call $C$ {\bf embeddable} if it is contained in a permutation code of minimum
distance $n-1$ and cardinality $n^2-n.$ Let $\delta =\delta (C)=n^2-n-\vert C\vert$ be the {\bf deficiency} of the permutation code $C\subseteq S_n$ of minimum distance $\geq n-1.$
\par
We prove that $C$ is embeddable if either $\delta\leq 2$ or if
$(\delta^2-1)(\delta +1)^2<27(n+2)/16.$ The main part of the proof is an adaptation
of the method used to obtain the famous Bruck completion theorem for mutually orthogonal
latin squares.
\end{abstract}


\section{Introduction}
\label{introsection}

\begin{definition}
\label{permcodedef}
Consider the symmetric group $S_n$ equipped with the Hamming distance. A {\bf permutation code} is a subset
$C\subseteq S_n$ and the {\bf minimum distance} $d=d(C)$ is the
minimum distance between two members of $C.$
\end{definition}

Permutation codes are also known as permutation arrays and as
permutation sets.
There is a vast literature on the subject. Motivation comes
from data transmission
over power lines, see~\cite{Huczynska,Vinck,FV,CCD}, and the design of block ciphers~\cite{TCL}.
A related and in some sense dual notion are uniformly $t$-homogeneous sets of permutations where the defining property is
that there is a constant $\mu >0$ such that for any two not necessarily different unordered $t$-subsets
$A$ and $B$ of letters the number of permutations $\pi\in C$
mapping $\pi :A\mapsto B$ equals $\mu .$ Those sets have been studied in the framework of perpendicular arrays, see for example
~\cite{BBE,BE,MS}.
\par
Clearly a permutation code $C\subseteq S_n$ of distance $n$ has at most $n$ codewords, with equality if and only if $C$ is a Latin square of order $n.$ The case of minimum distance $n-1$ leads to the following notion:

\begin{definition}
\label{2transdef}
A permutation code $C\subseteq S_n$ is {\bf sharply 2-transitive}
if for any two pairs $(a,b), (c,d)$ of symbols such that $a\not=b, c\not=d$ there is precisely one $\pi\in C$ such that
$\pi (a)=b$ and $\pi (c)=d.$
\end{definition}

\begin{proposition}
\label{firsttrivprop}
A permutation code $C\subseteq S_n$ of minimum distance $\geq n-1$ has size at most $n(n-1),$
with equality if and only if $C$ is sharply 2-transitive.
A 2-transitive set of permutations on $n$ letters exists if and only if a projective plane of order $n$ exists. This is the case
if $n$ is a prime-power.
\end{proposition}
\begin{proof}
Most of the claims are well-known and easy to see. For the sake of completeness we sketch the proof of equivalence between projective planes and sharply 2-transitive permutation sets.
Given a projective plane of order $n,$ choose a point $\infty$ and two lines $l_1,l_2$
on $\infty .$ Label the points $\not=\infty$ on $l_1,l_2$ as
$P_1,\dots ,P_n$ and $Q_1,\dots ,Q_n,$ respectively.
To each point $R\notin l_1\cup l_2$ associate a permutation $\pi_R$ such that $\pi_R(i)=j$ if $R,P_i,Q_j$ are collinear.
The axioms of a projective plane show that this defines a sharply
2-transitive set of permutations.
This proves one of the claims.
\par
Let $C$ be a permutation code of distance $\geq n-1.$ Associate to $C$ a geometry $\Pi (C)$
with $1+2n+\vert C\vert$ points and $n^2+2$ lines where $l_1=\lbrace\infty ,P_1,\dots ,P_n\rbrace$ and
$l_2=\lbrace\infty ,Q_1,\dots ,Q_n\rbrace$ are two of the lines,
each $\pi\in C$ defines a point and for each pair $(i,j)$
where $1\leq i,j\leq n$ the line
$L_{ij}$ contains $P_i,Q_j$ and those $\pi\in C$ which map
$\pi :i\mapsto j.$ If $C$ is sharply 2-transitive, then
$\Pi (C)$ has $n^2+n+1$ points and $n^2+2$ lines and it is easy to see that it can be completed to a projective plane of order $n.$
\end{proof}

In the sequel we will restrict attention to permutation codes $C\subset S_n$ of minimum distance $\geq n-1.$

\begin{definition}
\label{embeddabledef}
A permutation code $C\subseteq S_n$ of minimum distance $\geq n-1$
is {\bf embeddable} if it is contained in a sharply 2-transitive set. Let $M_n$ be the largest size of a permutation code
$C\subseteq S_n$ of distance $\geq n-1,$ and $m_n$ the largest size of a non-embeddable such code.
\end{definition}

Observe that $M_q=q^2-q$ if $q$ is a prime-power, and
$M_n=m_n<n^2-n$ provided $n$ is not the order of a projective plane. In those cases $m_n$ can be seen as a measure for the best
possible approximation to the non-existing plane.
The values of $m_n$ are known only for $n\leq 6.$

\begin{result}
\label{mnsmalltheorem}
$m_4=7, m_5=15, m_6=18.$
\end{result}

In fact in cases $n=2$ and $n=3$ the symmetric group is sharply
2-transitive itself, so $m_n$ is not defined in those cases. For $n=4$ it is easy to see that $m_4=7.$
One such maximal non-embeddable code consists of the identity
permutation and the elements of order $4.$
The value of $m_5$ is found in Bogaerts~\cite{Bogaerts},
the determination of $m_6$ is due to Kl\o ve~\cite{Klove00,Klove}.
\par
Assume a set of $t$ mutually orthogonal Latin squares of order
$n$ exists. The representation as a dual net shows immediately
that this allows the construction of a permutation code
$C\subseteq S_n$ of minimum distance $\geq n-1$ and size $tn.$
This generalizes a statement from Proposition~\ref{firsttrivprop}
which corresponds to case $t=n-1.$ In particular the existence
of $5$ mutually orthogonal Latin squares of order $12$ shows
$M_{12}\geq 60.$ It is a recent result by I. Janiszczak and R. Staszewski (personal communication) that $M_{12}\geq 112.$
\par
Our main results are the following:

\begin{theorem}
\label{mainembedtheorem}
Let $C\subseteq S_n$ be a permutation code of minimum distance
$\geq n-1,$ where $\vert C\vert =n^2-n-\d .$
\begin{itemize}
\item If $\d\leq 2,$ then $C$ is embeddable.
\item If $(\d^2-1)(\d+1)^2<27(n+2)/16,$ then $C$ is embeddable.
\end{itemize}
\end{theorem}

The embeddability of a permutation code of size $n^2-n-1$
(case $\d =1$ of Theorem~\ref{mainembedtheorem}) had been shown by Quistorff~\cite{Quistorff06}. Of particular interest is case $n=10,$ the smallest integer $n>6$ for which no projective plane of order $n$ exists.
The lower bound $M_{10}\geq 49$ has been shown in~\cite{JS}.
Theorem~\ref{mainembedtheorem} shows $M_{10}\leq 87.$
\par
Our proof is an adaptation of the celebrated Bruck embedding theorem for mutually orthogonal Latin squares, see~\cite{Bruck,Metsch}. In Section~\ref{geometricsection}
we define a geometric representation of permutation sets.
Some basic properties are proved in Section~\ref{basicPISsection}.
The last two sections contain the proofs of the embeddability theorems.






\section{A geometric setting}
\label{geometricsection}

\begin{definition}
\label{Pincstrdef}
A {\bf permutation incidence structure}
of order $n$ consists of points and lines such that
\begin{itemize}
\item There are $n^2$ points.
\item Each line has precisely $n$ points.
\item Each point is on at least $2$ lines.
\item Two different lines meet in at most one point.
\end{itemize}
\end{definition}

\begin{definition}
\label{defdef}
Let the total number of lines of a permutation incidence structure be $n^2+n-\d .$ Then $\d$ is the
{\bf deficiency} and we write $P(n,\d ).$
\end{definition}

Observe that as a consequence of the last axiom, each point
of a $P(n,\d )$ is on at most $n+1$ lines.
Permutation incidence structures are essentially geometric
representations of permutation codes $C\subseteq S_n.$
This geometry is obtained by dualizing the geometry $\Pi (C)$ used in the proof of
Proposition~\ref{firsttrivprop}. More precisely the following holds:

\begin{proposition}
The following are equivalent:
\item A permutation code $C\subseteq S_n$ of minimum distance$\geq n-1,$ where $\vert C\vert =n(n-1)-\d .$
\item A $P(n,\d )$ which possesses two parallel classes of lines
each of which partitions the points.
\end{proposition}
\begin{proof}
Let $C$ be a permutation code of distance $\geq n-1$ and size $n(n-1)-\d .$ The corresponding $P(n,\d )$ is obtained from $\Pi (C)$ by omitting the point $\infty$ and dualization: the points of the $P(n,\d )$ are the lines $L_{ij},$ the lines
of the $P(n,\d )$ are the permutations and the $2n$ points $P_i,Q_j$ on the lines $l_1,l_2.$
\par
Conversely let a $P(n,\d )$ be given. The dual structure has
$n^2$ lines. Each point is on $n$ lines, each line has at least
$2$ points and two different points are on at most one line.
The additional property shows that this dual structure possesses
two sets $\lbrace P_1,\dots ,P_n\rbrace$ and $\lbrace Q_1,\dots ,Q_n\rbrace$ of points with the property that each line contains exactly one of the $P_i$ and one of the $Q_j.$ It follows that the lines are precisely the lines $L_{ij}$ through $P_i$ and $Q_j.$ Let $X$ be one of the $n^2-n-\d$ remaining points. Then
$X$ determines a permutation on $n$ objects in the obvious way
(the permutation maps $i\mapsto j$ if and only if $X\in L_{ij}$),
The resulting permutation code $C$ has $n^2-n-\d$ elements and
minimum distance $\geq n-1.$
\end{proof}

To sum up: each permutation code $C$ of minimum distance $\geq n-1$
and size $n^2-n-\d$ defines a $P(n,\d ).$ On the other hand it is obvious that a $P(n,\d )$ results if we remove some $\d$ lines
from an affine plane of order $n.$ We want to prove that for small values of $\d$ each $P(n,\d )$ is embeddable in an affine plane. We are going to prove this if either $\d\leq 2$
(Corollary~\ref{delta1embedcor} and Theorem~\ref{delta2embedtheorem})
or $(\d^2-1)(\d+1)^2<27(n+2)/16$ (Theorem~\ref{deltagenembedtheorem}). This will complete the proof of Theorem~\ref{mainembedtheorem}.





\section{Basic properties of permutation incidence structures}
\label{basicPISsection}

In the sequel let $({\cal P}, {\cal L})$ be a $P(n,\d ).$

\begin{definition}
\label{defPldef}
Let $r_P$ (the {\bf degree} of $P$) be the number of lines on the point $P$ and $\d_P=n+1-r_P\geq 0$ the {\bf deficiency} of $P.$
For a line $l$ define $\d_l=\sum_{P\in l}\d_P,$
the {\bf deficiency} of $l.$
A point $P$ is {\bf exceptional} if $\d_P>0.$
Let $E$ be the set of exceptional points.
Lines $l,g$ are {\bf parallel} if either $l=g$ or $l\cap g=\emptyset .$
Let $i(l_1,l_2,\dots )$ be the number of lines which are parallel to $l_1,l_2,\dots$ and different from $l_1,l_2,\dots .$
\end{definition}

\begin{lemma}
\label{firstPllemma}
Let $P$ be a point and $l$ a line. The following hold:
\begin{itemize}
\item We have $r_P\le n+1$ with equality if and only if $P$ is joined to
all remaining points.
\item If $P\notin l$ and $P$ non-exceptional, then $P$ is on
precisely one line which is parallel to $l.$
\item $\d_l\geq 0$ with equality if and only if each
$P\in l$ is non-exceptional.
\item
$i(l)=n-\d -1+\d_l$ for each line $l.$
\end{itemize}
\end{lemma}
\begin{proof} The first statement is obvious
(as $1+(n+1)(n-1)=n^2$). For the second statement observe that by the first $P$ is on precisely
$n$ lines that are not parallel to $l.$ It follows that
precisely one line through $P$ must be parallel to $l.$
The third claim follows from the first. As for the last claim, it is easier to count the lines which are not
parallel to $l.$ This number is
$1+\sum_{P\in l}(r_P-1)=1+\sum_{P\in l}(n-\d_P)=1+n^2-\d_l.$ Subtracting this from the total number $n^2+n-\d$ of lines yields the result.
\end{proof}

\begin{lemma}
\label{secondPllemma}
We have $\vert E\vert\leq\sum_{P\in {\cal P}}\d_P=\d n,$
with equality on the left if and only if all points have deficiency $\leq 1.$
\end{lemma}
\begin{proof}
Double counting of point-line incidences shows
$$n(n^2+n-\d )=n\vert {\cal L}\vert =
\sum_{P\in {\cal P}} r_P=\sum_{P\in {\cal P}}(n+1-\d_P)=n^2(n+1)-\sum_{P\in {\cal P}}\d_P.$$
The equality follows by comparison, the inequality is an obvious consequence.
\end{proof}

In particular $\d\geq 0$ and $P(n,0)$ is an affine plane.
We can assume $\d>0$ in the sequel. Here is a refinement of the
preceding lemma:

\begin{lemma}
\label{secondfinerPllemma}
For each line $l$ the following hold:
\begin{itemize}
\item $\vert E\cap l\vert\leq\d_l,$
with equality if all points on $l$ have deficiency $\leq 1.$
\item
$\vert E\sm l\vert\leq\sum_{Q\in E\sm l}\d_Q=\d n-\d_l$
with equality if all points off $l$ have deficiency $\leq 1.$
\end{itemize}
\end{lemma}
\begin{proof}
Let $e_l=\vert E\cap l\vert .$
The number of lines meeting $l$ in a point equals
$\sum_{P\in l}(n-\d_P)=n^2-\d_l.$ On the other hand this number
is $\leq (n-e_l)n+e_l(n-1)=n^2-e_l.$ It follows $e_l\leq\d_l$ with equality if every exceptional point of $l$ has deficiency one.
The remaining statements are implied by
Lemma~\ref{secondPllemma}.
\end{proof}

\begin{lemma}
\label{rPdeltalemma}
We have $\d_P\leq\d$ for all $P.$
Equality holds if and only if all points collinear with $P$ are non-exceptional and all remaining points except $P$ have deficiency $1.$
\end{lemma}
\begin{proof}
Let $P$ be an exceptional point. It is not collinear with
$\d_P(n-1)$ points and those points are exceptional.
Let $l$ be a line on $P.$ By Lemma~\ref{secondfinerPllemma} we have
$$\d_P(n-1)\leq\vert E\sm l\vert\leq \d n-\d_l\leq \d n-\d_P.$$
Comparison shows $\d_P\leq\d .$ Equality holds if and only if
all three inequalities above are met with equality.
\end{proof}

\begin{corollary}
\label{delta1embedcor}
Each $P(n,1)$ can be embedded in an affine plane.
\end{corollary}
\begin{proof} There is an exceptional point $P.$
By Lemma~\ref{rPdeltalemma} there are precisely $1+n-1=n$
exceptional points and those are pairwise not collinear.
Their union can be used as an additional line which
completes the $P(n,1)$ to an affine plane.
\end{proof}

In the sequel we may assume $\d\geq 2.$

\begin{lemma}
\label{lhschnittcountlemma}
Let lines $l,h$ meet in an exceptional point.
Then
$i(l,h)\leq\d_l+\d_h-(1+\d ).$
\end{lemma}
\begin{proof}
We know $i(l).$ As $h$ contains at least $n-\d_h$
non-exceptional points and each of those is on a line parallel to $l,$ the number in question is bounded by
the difference $i(l)-(n-\d_h)=\d_l+\d_h-1-\d .$
\end{proof}

\begin{lemma}
Let lines $l\not=h$ be parallel, $\d_l,\d_h>0.$ Then
$i(l,h)\geq n-1-\d-(\d_l-1)(\d_h-1).$
\end{lemma}
\begin{proof}
Start from the $i(l)$ lines parallel to $l$ and different from $l.$ How many of those intersect $h?$ Each of the $\geq n-\d_h$ non-exceptional points on $h$ contributes only
$h$ itself, and each of the $\leq\d_h$ exceptional points, being
collinear with the non-exceptional points on $l,$ contributes at most $\d_l$ such lines one of which is $h.$ It follows that the number in question is $\geq i(l)-1-\d_h(\d_l-1).$
\end{proof}

\begin{lemma}
\label{lhh'abslemma}
If $h$ and $h'$ meet, are both parallel to $l$
and $\d_l,\d_h,\d_{h'}>0,$ then
$n+1\leq\d_l(\d_h+\d_{h'}-1).$
\end{lemma}
\begin{proof} $h\cap h'$ is an exceptional point as it is on two lines parallel to $l.$ We have
$$i(l)\geq 2+i(l,h)+i(l,h')-i(l,h,h').$$
We know $i(l),$ have lower bounds on $i(l,h),i(l,h')$
and an upper bound on $i(l,h,h')\leq i(h,h')-1.$ Comparing the extremes of these inequalities yields the claim.
\end{proof}



\begin{definition}
For each line $l,$ let $\Pi (l)$ the set of lines parallel to $l.$
\end{definition}

We know from Lemma~\ref{firstPllemma} that $\Pi (l)$ is
a family of $n+\d_l -\d$ lines.

\begin{lemma}
\label{Xlemma}
Suppose $l$ is a line with at least $n-1$ non-exceptional points.
Then $\Pi (l)$ consists of mutually parallel lines, and
$\d_g\geq\d_l$ for all $g\in\Pi (l).$
\end{lemma}
\begin{proof} Let $l\not=g\in\Pi (l).$ We know that each non-exceptional point of $g$ is on precisely one line which is parallel to $l.$ The presence of $n-1$ non-exceptional points on
$l$ shows that the same is true for each exceptional point of $g.$ It follows that the lines in $\Pi (l)$ are mutually parallel
and therefore $\Pi (l)\subseteq\Pi (g).$ This implies $\d_l\leq\d_g.$
\end{proof}


\section{Special cases}
\label{specialsection}

\begin{proposition}
\label{linedef0prop}
Each $P(n,\d )$ containing a line of deficiency $0$ and such that
$n\geq \d (2\d-1)$ is embeddable.
\end{proposition}
\begin{proof}
Let $\d_l=0.$ Then $\vert\Pi (l)\vert =n-\d .$ Each point covered
by a line from $\Pi (l)$ is on $n+1$ lines and therefore non-exceptional. It follows that those points are precisely the non-exceptional points. Each point outside is exceptional.
Lemma~\ref{secondPllemma} implies that the points
not covered by $\Pi (l)$ form the set $E$ of exceptional points, each of deficiency $\d_Q=1.$
This implies that every line $l'\in\Pi (l)$ satisfies
$\d_{l'}=0$ and hence $\Pi (l')=\Pi (l).$
Let $g\notin\Pi (l).$ Then $g$ has precisely $n-\d$ non-exceptional points, and therefore $\d_g=\d .$
Hence, every line has deficiency $0$ or $\d .$
\par
Let $Q\in E$ and $U\subset E$ the $n$-set consisting of $Q$ and all points not collinear with $Q.$ Assume some two points of
$U$ are collinear on a line $h.$ Then $Q$ is on some two different lines both of which are parallel to $h.$ As all lines involved have deficiency $\d ,$ then Lemma~\ref{lhh'abslemma} yields a contradiction. This shows that $U$ can be added to the list of lines resulting in a $P(n,\d-1)$ which still contains a line of deficiency $0.$ We are done by induction.
\end{proof}


\begin{proposition}
\label{dPdeltaprop}
If $\d>0$ and $n\geq (\d -1)(2\d-3),$ then each $P(n,\d)$ containing a point of deficiency $\d$ is embeddable.
\end{proposition}
\begin{proof}
Let $\d_{P_0}=\d .$ We are in the situation of Lemma~\ref{rPdeltalemma} when equality holds. The bundle of lines $l_1,\dots ,l_{n+1-\d}$ on $P_0$
covers $P_0$ and the $(n+1-\d)(n-1)$ non-exceptional points.
The complement is the set $N$ of $\d (n-1)$ points of deficiency $1.$ We have $E=\lbrace P_0\rbrace\cup N.$
\par
As $\vert\Pi (l_i)\vert =n$ it follows from Lemma~\ref{Xlemma}
that the lines of $\Pi (l_i)$ partition the point set into $n$ lines.
As each $g\in\Pi (l_i)$ satisfies $\d_g\geq\d$ (Lemma~\ref{Xlemma}) and $\sum_{g\in\Pi (l_i)}\d_g=\sum_{P\in {\cal P}}\d_P=\d n$ it follows that
$\d_g=\d$ and therefore $\Pi (g)=\Pi (l_i).$
Each of the remaining lines meets each of the $l_i,$ each line parallel to $l_i$ and has deficiency $\d -1.$
\par
Let $X\in N$
and $U$ the set consisting of $X$ and the points not collinear with $X.$ Clearly $P_0\in U.$ As $\d_X=1$ we have $\vert U\vert =n.$ Assume a line $h$ contains two points from $U.$
As $X$ has degree $n,$ it is on at least two lines parallel to $h.$ The first part of the proof shows that $h$ and the two lines on $X$ parallel to $h$ have deficiency $\d -1.$
Lemma~\ref{lhh'abslemma} yields a contradiction. It follows that
$U$ can be added as a line to produce a $P(n,\d -1),$ in which
$P_0$ is a point of deficiency $\d -1.$ We are done by induction.
\end{proof}

\begin{theorem}
\label{delta2embedtheorem}
Each $P(n,2)$ is embeddable.
\end{theorem}
\begin{proof}
For $n\leq 6$ this is known. Assume therefore $n>6.$
Because of Proposition~\ref{linedef0prop} and
Proposition~\ref{dPdeltaprop} it can be assumed that all lines
have positive deficiency (equivalently: contain at least one exceptional point) and $\d_P\leq 1$ for all $P.$ The latter implies $\vert E\vert =\sum_{P\in {\cal P}}\d_P=2n.$
As the removal of two lines from an affine plane of order $n$
produces a $P(n,2)$ which either has a line of deficiency $0$ or has a point of deficiency $2,$ we expect a contradiction.
\par
Considering the distribution of the $2n$ exceptional points on the bundle of
lines on a non-exceptional point $P,$ we see that $P$ is on a line $l$ of deficiency $1.$
We have $\vert\Pi (l)\vert =n-1.$ Lemma~\ref{Xlemma}
shows that the lines of $\Pi (l)$
are parallel. They cover $n(n-1)$ points. As the $n$ exceptional points covered by $\Pi (l)$ distribute on the $n-1$ lines of this partial parallel class, there is precisely one line $g\in\Pi (l)$
of deficiency $2.$ We have $\Pi (l')=\Pi (l)$ for each line
$l'$ parallel to $l$ which is different from $g.$
As $\vert\Pi (g)\vert =n,$ it follows that there is precisely one line $h$ parallel to $g$ which is not
in $\Pi (l).$ Let $l'\in\Pi (l), l'\not=g,l.$
Then $h$ meets $l'$ and $Q=h\cap l'$ is exceptional as $Q$ is on two different parallels to $g.$ It follows that $Q$ is the unique exceptional point on $l'.$ Similarly $h\cap l$ is the unique exceptional point of $l$. This is impossible as it implies that $Q$ is on $n+1$ lines, namely the line $h$ and $l'$ and the $n-1$ lines that join $Q$ to the non-exceptional points of $l$.
\end{proof}






\section{Continuing with the general case}
\label{lastsection}

In this final section we complete the proof of Theorem~\ref{mainembedtheorem}. It follows from Theorem~\ref{delta2embedtheorem} and Propositions~\ref{linedef0prop},\ref{dPdeltaprop} that the following assumptions can be made: $\d\geq 3, \d_l>0$ for each line $l$ and
$\d_P<\d$ for each point $P.$ We start from the following:

\begin{theorem}
\label{maincounttheorem}
Assume $l$ is a line such that $\d_l\leq\d$ and
$(\d^2-1)(\d +1)^2<27(n+2)/16.$
Then the following hold:
\begin{itemize}
\item The lines of $\Pi (l)$ are pairwise parallel.
They all have the same deficiency $\e =\d_l$ and $\Pi (l)=\Pi (h)$ for all $h\in\Pi (l).$
\end{itemize}
\end{theorem}
\begin{proof}
Observe $\vert\Pi (l)\vert =n-(\d -\e )\leq n.$
Use induction on $\e =\d_l\geq 0.$ Case $\e =0$ follows from Proposition~\ref{linedef0prop} and its proof. Assume $\e >0$ in the sequel.
Consider the partition $\Pi (l)=\Pi_1\cup\Pi_2$
where $\Pi_1$ consists of $l$ and the lines $h\not=l$ parallel
to $l$ which satisfy $\d_h<(n+1+\e )/(2\e ).$ Lemma~\ref{lhh'abslemma}
implies that the lines of $\Pi_1$ are pairwise parallel. The induction hypothesis implies
$\d_h\geq\d_l$ for all $h\in\Pi_1.$ The next major claim is that $\Pi_2$ is empty.
\par
In order to prove this, let
$M$ be the set of points covered by
lines of $\Pi (l)$ and $N$ the complement of $M.$
Then $\vert N\vert\geq n(\d -\e )$ and
Lemma~\ref{firstPllemma} shows that $N$ consists of
exceptional points. Let $D\subset M$ be the set of points which are on more than one line of $\Pi (l).$ Clearly points of $D$ are exceptional. For $X\in D,$ let $d_X\geq 2$ be the number
of lines of $\Pi (l)$ on $X,$ and $d=\sum_{h\in\Pi_2}\vert h\cap D\vert .$
We have
\begin{equation}
\label{equeins}
n\vert\Pi (l)\vert -\vert M\vert =\sum_{X\in D}(d_X-1)\geq\frac{1}{2}\sum_{X\in D}d_X=\frac{1}{2}\sum_{h\in\Pi}\vert h\cap D\vert\geq d/2
\end{equation}
and

\begin{eqnarray}
\label{equzwei}
\sum_{h\in\Pi_2}\sum_{P\in h\sm D}\d_P&=&
\sum_{h\in\Pi_2}(\d_h-\sum_{P\in h\cap D}\d_P)\nonumber
\\
&\geq&
\sum_{h\in\Pi_2}(\d_h-\vert h\cap D\vert(\d-1))\\
&\geq&
\vert\Pi_2\vert (n+1+\e )/(2\e )-d(\d-1).\nonumber
\end{eqnarray}
We want to lower bound $\sum_{X\in {\cal P}}\d_X.$
As points of $N$ are exceptional and therefore have
deficiency $\geq 1$ and because of Equation~(\ref{equeins}) we have
$$\sum_{X\in N}\d_X\geq n^2-\vert M\vert\geq(n(n-\vert\Pi\vert )+d/2=n(\d -\e )+d/2.$$
Together with the points covered by $\Pi_1$ this yields the a priori lower bound
$$\d n=\sum_{X\in {\cal P}}\d_X\geq\vert\Pi_1\vert\e+n(\d -\e )+d/2.$$
which we use to obtain a weak upper bound on $d:$

\begin{equation}
\label{weakdequ}
d/2\leq\e (n-\vert\Pi_1\vert )=\e (\d -\e +\vert\Pi_2\vert )
\end{equation}

Collect now the three contributions to $\sum\d_X$ that we have to obtain a lower bound:

$$\d n=\sum_{X\in {\cal P}}\d_X\geq\e\vert\Pi_1\vert +\underbrace{(n(\d -\e )+d/2)}_{contribution~ of~N}+\underbrace{\vert\Pi_2\vert (n+1+\e )/(2\e )-d(\d-1)}_{from ~(2)}.$$
Equivalently
$$\d n\geq\vert\Pi_2\vert ((n+1+\e )/(2\e )-\e )
+\e (n-\d+\e )+n(\d -\e )-(d/2)(2\d -3).$$
Substitute inequality~(\ref{weakdequ}) for $d/2.$
After simplification this yields
$$\d n\geq\vert\Pi_2\vert ((n+1+\e )/(2\e )-2\e (\d -1))+\d n-2\e (\d -1)(\d -\e ).$$
Because of the hypothesis in Theorem~\ref{maincounttheorem} the coefficient of $\vert\Pi_2\vert$
is positive. Assume $\vert\Pi_2\vert\geq 1.$  Then
$$n+1+\e\leq 4(\d -1)\e^2(\d -\e +1).$$
The left is $\geq n+2,$ the right side is maximized by $\e =2(\d +1)/3$ as a function of $\e .$ This yields
$n+2\leq (16/27)(\d^2-1)(\d +1)^2$ contradicting the hypothesis.
\par
Now $\Pi =\Pi_1$ consists of
$n-\d+\e$ parallel lines, each of deficiency $\geq\e .$
\par
Finally we prove that $\Pi (l)=\Pi (h)$ for all
$h\in\Pi (l),$ equivalently: each line in $\Pi (l)$
has deficiency $\e .$ The situation is: $\Pi (l)$ has
$n-\d +\e$ lines. They are pairwise parallel, have deficiency $\geq\e .$ Since the $n(\delta-\e)$ points not covered by the lines of $\Pi(l)$ have positive deficiency, then global counting shows
$$\d n=\sum_{P\in{\cal P}}\d_P\geq\e (n-\d+\e )+n(\d -\e )$$
which shows that at most $z=\e (\d -\e )\leq\d^2/4$ lines of
$\Pi (l)$ have deficiency $>\e .$
Clearly $\Pi (l)=\Pi (h)$ for all $h\in\Pi (l)$ of deficiency $\e .$
\par
Assume there is some $g\in\Pi (l)$ of deficiency $>\e$. Then $g$ is parallel to some line $h$ which is not in $\Pi (l).$ Let $l=l_1,\dots ,l_c$ be the lines of
$\Pi (l)$ of deficiency $\e .$ We saw above that
$$c\geq\vert\Pi\vert -z=n-(\d-\e)(\e+1)\geq n-(\d+1)^2/4.$$
Then $h$ meets each of the $l_j$.

Each point of $h$ is exceptional. Indeed, if point $X$ of $h$ lies on no line of $\Pi(l)$ it is exceptional for this reason, and if $X$ is on a line of $\Pi (l)$, then it lies on two parallels to $g$ and is therefore exceptional.

It follows in particular $\d_h\geq n.$ Line $h$ is parallel to $n-1-\d +\d_h\geq 2n-1-\d$ other lines. At most $z$ of those are in
$\Pi (l).$ Let $s=2n-1-\d -z\geq 2n-(\d+2)^2/4$ and $h_1,\dots ,h_s$ lines parallel
to $h$ which are not in $\Pi (l).$ Count the ordered pairs of different $h_i.$ There are $s(s-1)$ such ordered pairs.
Consider the lines $l_j\in\Pi (l), j=1,\dots c.$ Each $l_j$
contains $m_j\leq\e-1\leq\d-1$ exceptional points not on $h$ and $n-1-m_j$ non-exceptional points.
The non-exceptional points of $l_j$ lie on at most one line parallel to $h$ and thus on at most one line $h_i$; thus at least $s-(n-1-m_j)$ lines $h_i$ must meet $l_j$ in one of the $m_j$ exceptional points not on $h$.
The Cauchy-Schwartz inequality shows that the number of pairs of
different $h_i$ meeting in a point of $l_j$ is at least
$$m_j\frac{s-n+1+m_j}{m_j}(\frac{s-n+1+m_j}{m_j}-1)\geq
\frac{(s-n+1)^2}{\d -1}.
$$
We obtain the inequality
$$c(s-n+1)^2\leq(\d-1)s(s-1).$$
Let us create a factor of $s$ on the left side:
as $s\leq 2(n-1)$ we obtain $(n-1)^2\geq (n-1)s/2$ and
$(s-(n-1))^2=s^2-2(n-1)s+(n-1)^2\geq s(s-2(n-1)+(n-1)/2).$
The major inequality simplifies after factoring $s:$
$$c(s-3(n-1)/2)\leq (\d-1)(s-1)<(\d -1)2n.$$
Using the lower bounds:
$$(\d -1)2n>(n-(\d+1)^2/4)((n+3)/2-(\d+2)^2/4),$$
after multiplying out on the right, forgetting the terms
not dependent on $n$ and canceling the factor $n:$
$2(\d +2)^2+(\d +1)^2+16(\d -1)>4n$ which clearly contradicts the
hypothesis.
\end{proof}

\begin{theorem}
\label{line_def_is_at_most_delta}
Let $(\d^2-1)(\d+1)^2<27(n+2)/16.$
Then every line has deficiency $\leq\d .$
\end{theorem}
\begin{proof}
Pick a non-exceptional point $P_0$ and its bundle of $n+1$ lines
$l_1,\dots ,l_{n+1}.$ Let $\d_i=\d_{l_i}$ and $\e_i=\d-\d_i.$
We want to show that $\e_i\geq 0$ for all $i.$ As every line is parallel to one of the lines $l_i$, the preceding theorem then implies the statement.
\par
Assume therefore that some of the $\e_i$ are negative.
As $\sum\e_i=\d$ and at least one negative $\e_i$ is present,
we can find some positive $\e_i$ that sum to at least $\d+1.$
As $\e_i\leq\d$ for all $i$ we can choose them such that the sum is at most $2\d.$ Choose therefore the lines $l_1,\dots ,l_s$
such that $\e_i\geq 0$ for $i\le s$ and $z=\sum_{i=1}^s\e_i$ satisfies
$\d+1\leq z\leq 2\d .$
Use the result of the preceding theorem: let $\Pi_i=\Pi (l_i)$ for $i\leq s$ and recall that $\Pi_i$ consists of $n-\e_i$
parallel lines each of which has deficiency $\d_i.$
Let $M_i$ be the set of points covered by the lines of $\Pi_i$
and $N_i$ its complement. We have $\vert M_i\vert =n(n-\e_i)$ and
$\vert N_i\vert =n\e_i.$ Also, let $N=\cup_{i=1}^sN_i.$
Observe that $N$ consists of exceptional points. Recall also from Theorem \ref{maincounttheorem} that lines $l\in\Pi_i,g\in\Pi_j$ for $i<j\le s$ must meet. This has the following evident consequences:
if $l\in\Pi_i$ and $i\not=j,$ then $\vert l\cap M_j\vert =n-\e_j$
and $\vert l\cap N_j\vert=\e_j.$ It follows $\vert N_i\cap N_j\vert =\e_i\e_j.$
\par
Here is a first lower bound on $\vert N\vert :$ observe at first that $\vert N\vert\geq\sum_{i=1}^s\vert N_i\vert -\sum_{i<j\leq s}\vert N_i\cap N_j\vert .$ In fact, the right side does count elements of $N.$ If $P\in N$ occurs in precisely
$t\geq 1$ of the $N_i,$ then the contribution of $P$ to the right side is $t-\binom{t}{2}\leq 1.$ The inequality follows. Continuing on the right side we obtain
\begin{equation}
\label{Naprioriequ}
\vert N\vert\geq\sum_{i=1}^s\e_in-\frac{1}{2}\sum_{i,j=1}^s\e_i\e_j=zn-(1/2)z^2
\end{equation}
Consider again a point $X\in N.$ It is exceptional and therefore on at most $n$ lines. Let $X$ be in $N_i$ for $i\leq t$ and in
$M_i$ for $t<i\leq s.$ The number of
points of $N$ which are collinear with $X$ is bounded by
$$\sum_{i=1}^tn(\e_i-1)+\sum_{i=t+1}^sn\e_i=nz-nt.$$
Together with Equation~(\ref{Naprioriequ}) this shows that the
number of points of $N$ which are not collinear with $X$ is
$\geq\vert N\vert -1-nz+nt\geq nt-1-z^2/2.$ As $z\leq 2\d$ it follows that the number of points in $N$ not collinear with $X$
is $\geq tn-1-2\d^2$ and therefore $>(t-1)n.$ We conclude
$\d_X\geq t.$ Finally $\sum_{X\in N}\d_X$ is lower bounded by
the number of pairs $(i,X)$ where $i\leq s$ and $X\in N_i.$
This number is $\sum_{i=1}^s\vert N_i\vert =\sum\e_in>\d n.$
As $\sum_{X\in N}\d_X\leq\d n$ by Lemma~\ref{secondPllemma}, this
is a contradiction.
\end{proof}

We are ready for the final step.

\begin{theorem}
\label{deltagenembedtheorem}
Each $P(n,\d )$ is embeddable provided
$(\d^2-1)(\d+1)^2<27(n+2)/16.$
\end{theorem}
\begin{proof}
Assume $(\d^2-1)(\d+1)^2<27(n+2)/16.$
We need to show that $P(n,\d)$ can be embedded in a $P(n,\d-1).$
As before start from a non-exceptional point $P$ and its bundle
of lines. As $\sum\d_i=\d n$ it follows that there is some line
$l_1$ on $P$ whose deficiency is $d<\d .$ Let $\Pi =\Pi (l_1),$
a parallel class of $n-\d+d$ lines, each of deficiency $d.$
Let $M$ be the set of points covered by $\Pi ,$ and $N$ the complement of $M.$ Assume all $X\in N$ satisfy $\d_X\geq 2.$
An obvious count yields the contradiction
$\d n=\sum_Q\d_Q\geq d(n-\d+d)+2n(\d-d),$ equivalently
$(n-d)(\d -d)\leq 0.$ It follows that there is some $X\in N$
such that $\d_X=1.$ Let $U$ be the union of $X$ and the $n-1$
points not collinear with $X.$ Assume some line $l$ contains
at least two points of $U.$ Let $t=\vert l\cap U\vert\geq 2.$
Then there are some two lines on $X$ which are both parallel to $l.$ We are in the situation of Lemma~\ref{lhh'abslemma} which, in conjunction with Theorem \ref{line_def_is_at_most_delta}, implies $n+1\leq\d (2\d-1).$
This contradiction shows that $U$ can be used as a new line which
together with the lines of the $P(n,\d)$ forms a $P(n,\d-1).$
This completes the proof.
\end{proof}






\begin{thebibliography}{99}
\bibitem{BBE} J. Bierbrauer, S. Black and Y. Edel:
Some $t$-homogeneous sets of permutations,
  {\sl Designs, Codes and Cryptography~\bf9} (1996), 29-38.
\bibitem{BE} J. Bierbrauer and Y. Edel:
Theory of perpendicular arrays, 
  {\sl Journal of Combinatorial Designs~\bf6 } (1994), 375-406.
%\bibitem{BCD79} I.F. Blake, G. Cohen, M.Deza:
%  {\it Coding with permutations,}
%  {\sl Inform. Control~\bf43} (1979), 1-19.
\bibitem{Bogaerts} M. Bogaerts:
Isometries and construction of permutation arrays,
  {\sl IEEE IT Transactions~\bf56} (2010), 3177-3179.
\bibitem{Bruck} R. H. Bruck:
 Finite nets II. Uniqueness and embedding, 
  {\sl Pacific J. Math.~\bf13} (1963), 421-457.
%\bibitem{CKL} C.J. Colbourn, T. Klove, A.C.H. Ling:
%  {\it Permutation arrays for powerline communication and
%    mutually orthogonal latin squares,}
%  {\sl IEEE IT Transactions~\bf50} (2004), 1289-1291.
\bibitem{CCD} W. Chu, C. Colbourn, P. Dukes:
Constructions for permutation codes in powerline communications, 
  {\sl Designs, Codes and Cryptography~\bf32} (2004), 51-64.
%\bibitem{Dukes} P.J. Dukes:
%  {\it Permutation codes and arrays,}
%  {\sl Handbook of Combinatorial designs,} 2nd edition, 568-571.
\bibitem{FV} H.C. Ferreira, A.J.H. Vinck:
Inference cancellation with permutation trellis arrays,
  {\sl Proc. IEEE Vehtcular Technology Conf.} 2000, 2401-2407.
%\bibitem{Frankl} P. Frankl, M. Deza:
%  {\it On the maximum number of permutations with given maximal %or
%  minimal distance,}
%  {\sl J. Comb. Theory A~\bf22} (1977), 352-360.
\bibitem{Huczynska} S. Huczynska:
Powerline communication and the 36 officers problem,
 {\sl Phil. Trans.R. Soc.A~\bf364} (2006), 3199-3214.
\bibitem{JS} I. Janiszczak, R. Staszewski:
An improved bound for permutation arrays of length 10,
  manuscript.
\bibitem{Klove00} T. Kl\o ve,
Classification of permutation codes of length 6 and minimum distance 5,
  {\sl Internat. Symposium on Info. Theory and its Applications,}
  Honolulu 2000, 465-468.
\bibitem{Klove} T. Kl\o ve:
A combinatorial problem motivated by a data transmission application,
  Chapman and Hall/ CRC Press 2004.
\bibitem{MS} Bill Martin and B.E. Sagan:
A new notion of transitivity for groups and sets of permutations,
  {\sl Journal of the London Mathematical Society~\bf73} (2006), 1-13.
\bibitem{Metsch} K. Metsch:
Improvement of Bruck's completion theorem,
  {\sl Designs, Codes and Cryptography~\bf1} (1991), 99-116.
\bibitem{Quistorff06} J. Quistorff:
A survey on packing and covering problems in the
  Hamming permutation space,
  {\sl Electron. J. Comb.} (2006), A1.
\bibitem{TCL} D.R. de la Torre, C.J. Colbourn, A.C.H. Ling:
An application of permutation arrays to block ciphers,
  {\sl Congr. Numer.~\bf145} (2000), 5-7.
\bibitem{Vinck} A.J. Han Vinck:
Codes modulation for powerline communications, 
  {\sl AE Internat. Journal of Electronics and Commun.~\bf54} (2000), 45-49.
\end{thebibliography}



\end{document}