% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.64}{24(3)}{2017}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb,float}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand\lam{\lambda}
\newcommand\Q{\mathbb{Q}}
\newcommand\Z{\mathbb{Z}}
\newcommand\F{\mathbb{F}}
\newcommand\cB{\mathcal{B}}
\newcommand\cS{\mathcal{S}}
\newcommand{\comment}[1]{}

\allowdisplaybreaks
% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

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

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Relative difference sets partitioned by cosets}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Peter J.~Dukes\thanks{Supported by NSERC grant 312595--2010.}\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small University of Victoria\\[-0.8ex] 
\small Victoria, Canada\\
\small\tt dukes@uvic.ca\\
\and
Alan C.H.~Ling\\
\small Department of Computer Science\\[-0.8ex]
\small University of Vermont\\[-0.8ex]
\small Burlington, U.S.A.\\
\small\tt aling@cems.uvm.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Oct 16, 2015}{Sep 9, 2017}{Sep 22, 2017}\\
\small Mathematics Subject Classifications: 05B10; 05B15; 05B25}

\begin{document}

\maketitle


\begin{abstract}
We explore classical (relative) difference sets intersected with the cosets of a subgroup of small index. The intersection sizes are governed by quadratic Diophantine equations.  Developing the intersections in the subgroup yields an interesting class of group divisible designs.  From this and the Bose-Shrikhande-Parker construction, we obtain some new sets of mutually orthogonal latin squares.   We also briefly consider optical orthogonal codes and difference triangle systems.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} 	relative difference set; mutually orthogonal latin square; optical orthogonal code; difference triangle system
\end{abstract}

\section{Introduction}

A $k$-subset $D$ of a group $G$ of order $v$ (which we often assume is abelian and written additively) is a $(v,k,\lam)$-\emph{difference set} if every non-zero element of $G$ is realized exactly $\lam$ times as a difference of two elements in $D$.  If, for the moment, we write $G$ multiplicatively with identity $e_G$, its subsets correspond to elements of the group ring $\Z[G]$ with coefficients in $\{0,1\}$; conveniently, $D$ is a $(v,k,\lam)$-difference set if and only if $\left(\sum_{d \in D} d \right) \left( \sum_{d \in D} d^{-1} \right)  = k \cdot e_G + \lam \cdot \left( \sum_{g \in G} g - e_G\right)$.  This is naturally abbreviated as 
\begin{equation}
D \cdot D^{(-1)} =  k \cdot e_G + \lam \cdot ( G - e_G).
\end{equation}

Let $N$ be a normal subgroup of $G$, where $|N|=n$ and $|G|=mn$.  A $k$-subset $R$ of $G$ is an $(m,n,k,\lam)$-\emph{relative difference set} if 
every element of $G \setminus N$ is realized exactly $\lam$ times as a difference of elements in $R$, while no nonzero element of $N$ is ever realized as such a difference.
Back in the group ring language, this means that 
\begin{equation}
R \cdot R^{(-1)} =  k \cdot e_G + \lam \cdot (G-N).
\end{equation}
Relative difference sets were introduced over fifty years ago by Elliott and Butson in \cite{RDS-orig}.  

We review two important examples.  Let $q$ be a prime power and $\F_q$ the finite field of order $q$.  If we take $G = \F_{q^3}^\times / \F_q^\times$ and 
$D=\{\alpha \in G : \mathrm{Tr}_{3/1}(\alpha)=0\}$, then $D$ is a $(q^2+q+1,q+1,1)$-difference set.  Extracting exponents of a generator yields an additive presentation, call it $S_q$, in the cyclic group $\Z/(q^2+q+1)\Z$.   These are (a special case of) the `Singer' difference sets.
Next, a $(q+1,q-1,q,1)$-relative difference set on $\F_{q}^\times \leq \F_{q^2}^\times$ is furnished by $R=\{\alpha : \mathrm{Tr}_{2/1}(\alpha) = 1 \}$.  We again have an additive presentation, call it $R_q \subseteq \Z/(q^2-1)\Z$ relative to the subgroup $\Z/(q-1)\Z$.  These are often referred to as `Bose'  or `affine' relative difference sets.  These and other important examples of relative difference sets can be found in Alexander Pott's survey, \cite{RDS-survey}.

It is well known that $(v,k,\lam)$-difference sets, when acted on by their underlying group, develop into symmetric $(v,k,\lam)$-designs.  Indeed, the projective plane of order $q$ arises from developing the Singer difference sets above.  Similarly, relative difference sets develop into a generalized type of block design, defined next.

A \emph{group divisible design} (GDD) is a triple $(V,\Pi,\cB)$, where $V$ is a set of \emph{points}, $\Pi$ is a partition of $V$, and $\cB \subseteq 2^V$ is a family of subsets of $V$ called \emph{blocks}, such that
two elements from different parts of $\Pi$ appear together in exactly one block, while
two elements from the same part of $\Pi$ never appear together in a blocks.

If the block sizes are in $K$, it is common to abbreviate this as a $K$-GDD.  As with BIBDs, it is possible to replace `exactly one' by `exactly $\lam$' above for a nonnegative integer $\lam$; for our purposes, though, we assume $\lam=1$.  
The \emph{type} of the GDD is the list of part sizes in $\Pi$.  It is common to abbreviate this with exponential notation, so that, for instance, $n^m$ represents $m$ groups of size $n$.  

A $(v,k,1)$-BIBD is equivalent to a $\{k\}$-GDD of type $1^v$. More generally, a \emph{pairwise balanced design} PBD$(v,K)$ is a $K$-GDD of type $1^v$.  In these cases, $\Pi$ consists of $v$ singleton parts.  At the opposite extreme, a transversal design TD$(k,n)$ is a $\{k\}$-GDD of type $n^k$.  In this case the blocks are transversals of the partition $\Pi$.  Recall that a TD$(k,n)$ is equivalent to $k-2$ mutually orthogonal latin squares of order $n$, and also to $k$-factor orthogonal arrays of strength two.  Therefore, GDDs provide a common generalization of the fundamental objects of interest in design theory.  Richard Wilson was perhaps the first to consider GDDs in generality, starting in \cite[\S 6]{RMW0}; this formed a key part of his existence theory for pairwise balanced designs.

Returning to relative difference sets, the group action develops such a set with parameters $(m,n,k,1)$ into a $\{k\}$-GDD of type $n^m$.  For instance, the Bose relative difference set in $\F_{q^2}^\times$ yields a $\{q\}$-GDD of type $(q-1)^{q+1}$, which is equivalent to an affine plane of order $q$ with one point deleted.

Our primary observation is a straightforward extension of this.  Since blocks are developed as cyclic shifts, subgroups of $G$ induce smaller GDDs, potentially with a mixture of block sizes.  This is similar in spirit to constructions in \cite{Brouwer-sep,LingDTS,Pott}.

\begin{theorem}
\label{main}
Let $R$ be an $(m,n,k,1)$-relative difference set on groups $N \le G$.  Let $V$ be a subgroup of index $d$ in $G$ such that $G=NV$.
Then $R$ induces a GDD with points $V$, partition $\Pi = V/(N \cap V)$, and blocks $gR \cap V$, $g \in G$.  The type of the GDD is $[n/d]^m$ and the block sizes are $|R \cap hV|$, where $h$ ranges over a transversal of $V$ in $G$.
\end{theorem}

\begin{proof}
Let $x,y \in V$.  Suppose they are in different cosets of $\Pi$.  Then $xy^{-1} \in G \setminus N$.  By the property of $R$ being a relative difference set, it follows that $x,y \in gR$ for some (exactly one) $g \in G$.  This is the condition for $x,y$ to be covered by some (exactly one) block of the given form.  Similarly, if  $xy^{-1} \in N \setminus \{e_G\}$, then $x,y$ are covered by no such block developed from $R$.

By assumption, we have $|V|=|G|/d=nm/d$ and, by the second isomorphism theorem, we have $|\Pi|=|G/N|=m$.  This gives the GDD type.  Finally, the size of a generic block is $|gR \cap V| = |R \cap g^{-1}V|$, which can be computed over coset representatives $g$ for $V$ in $G$.
\end{proof}

We comment on some additional structure. 
In a GDD with points $V$ and blocks $\cB$, a \emph{symmetric class} of blocks is a subset $\cS \subseteq \cB$ such that each block in $\cS$ has the same size, call it $k$, and every point of $V$ is covered by exactly $k$ elements of $\cS$.  For instance, developing a (relative) difference set of size $k$ leads to one symmetric class $\cS=\cB$.  We remark that the GDD of Theorem~\ref{main} induces $d$ disjoint symmetric classes.  In more detail, the blocks $gR \cap V$, $g \in G$, partition into classes according to the coset of $g$ in $V$.  That is, let $g_1,g_2,\dots,g_d$ be a transversal of $V$ in $G$ and put $B_i = g_i R  \cap V$.  Then developing $B_i$ in $V$ gives symmetric block classes $\cS_i = \{hB_i : h \in V\}$, $i=1,\dots,d$.

In this paper, we explore such GDDs for the affine relative difference sets.

\begin{corollary}
\label{affine-gdd}
Let $R_q \subset \Z/(q^2-1)\Z$ be the affine relative difference set and suppose $d \mid q-1$.  Put $a_i =  |R_q \cap (i + d \Z)|$ for $i=0,1,\dots,d-1$.  Then there exists an $\{a_0,a_1,\dots,a_{d-1}\}$-GDD of type $[(q-1)/d]^{q+1}$.  Moreover, the blocks of this GDD partition into symmetric classes of block size $a_i$ for $i=0,1,\dots,d-1$.
\end{corollary}

We investigate some special cases of these GDDs in the next section.  As consequences, we obtain constructions of some new best-known sets of mutually orthogonal latin squares.  The method appears to be useful for other difference problems, such as optical orthogonal codes and difference triangle systems.

\section{Constraints on block sizes}

Here we investigate the structure of the block sizes $a_0,a_1,\dots,a_{d-1}$ of the GDD arising from Corollary~\ref{affine-gdd}.
Since those block sizes are formed by intersecting $R_q$ with cosets of $d \Z$, it follows that
\begin{equation}
\label{sum}
\sum_{i=0}^{d-1} a_i = q.
\end{equation}
Next, every difference which is $0 \pmod{d}$ must arise (exactly once) from a difference of elements of $R_q$ in the same coset.  Therefore,
\begin{equation}
\label{squares}
\sum_{i=0}^{d-1} a_i(a_i-1) = \frac{q(q-1)}{d}.
\end{equation}
There exist other constraints (not all independent) by examining other types of differences.  For the moment, we focus on the cases $d=3,4$. 

\begin{proposition}
Let $q=p \equiv 4n+1$, a prime.  Consider the GDD obtained by developing $R_q$ in $\Z/(q^2-1)\Z$ using a subgroup of index $d=4$.
Its block sizes are 
$$\{a_0,a_1,a_2,a_3\}=\left\{n+\frac{a}{2},n-\frac{a}{2},n+\frac{1}{2}+\frac{b}{2},n+\frac{1}{2}-\frac{b}{2} \right\},$$
where $p=a^2+b^2$ is the unique decomposition of $p$ as a sum of squares with $a$ even.
\end{proposition}

\begin{proof}[Proof outline]
From an easy counting argument, we can strengthen (\ref{sum}) in the case $d=4$ to $a_0 + a_2 = 2n$, $a_1 + a_3 = 2n+1$.
With this, (\ref{squares}) becomes $a_0 a_1+a_1 a_2 + a_2 a_3 + a_3 a_0 = 2n(2n+1)$, after simplification.
Letting $a,b$ be defined as above, this is equivalent to Fermat's Diophantine equation
$a^2 + b^2 = p$. 
\end{proof}

\begin{remark}
Various explicit or algorithmic methods for computing $a,b$ are known.  For instance, it was known to Gauss that $a \equiv \frac{1}{2} \binom{2n}{n}$ and
$b \equiv a(2k)! \pmod{p}$, where $|a|,|b|<p/2$.  See \cite{Lemmermeyer} for a proof.
\end{remark}

A similar explicit calculation of block sizes can be undertaken for $d=3$. 

\begin{proposition}
\label{block-sizes-d-3}
Let $q=p \equiv 3n+1$, a prime.   Consider the GDD obtained by developing $R_q$ in $\Z/(q^2-1)\Z$ using a subgroup of index $d=3$.
Its block sizes are 
$$\{a_0,a_1,a_2\}  = \frac{1}{3} \binom{2n}{n} \{1,\omega,\omega^2\} \mod p,$$
where $\omega$ is a primitive cube root of unity in $(\Z/p\Z)^\times$.  
\end{proposition}

\begin{proof}[Proof outline]
Since by (\ref{sum}) we have $a_0+a_1+a_2 = p \equiv 1\pmod{3}$, we may assume (after re-indexing) that $a_0 \equiv a_1 \pmod{3}$.
Put $A:=3a_0+3a_1-2p$ and $B:=(a_0-a_1)/3$.  After a calculation, we find that
\begin{equation}
\label{Dioph}
A^2 + 27B^2 = 4p.
\end{equation}
Since the Eisenstein integers $\Z[\frac{1+\sqrt{-3}}{2}]$ form a UFD, it follows that (\ref{Dioph}) has at most one solution in positive integers $A,B$.  The formula given 
comes from a result of Jacobi (see, for instance, \cite{Lemmermeyer}), which explicitly solves (\ref{Dioph}).  A few calculations are needed to switch back to variables $a_0,a_1,a_2$.
\end{proof}

In what follows, we let $d$ be general and not assume $q$ is prime.  Let $p$ be the characteristic of $\F_q$ and $\theta: x \mapsto x^p$ the Frobenius automorphism.  Our next result controls the block sizes.

\begin{proposition}
Consider the GDD obtained by developing by $R_q$ in $\Z/(q^2-1)\Z$ using a subgroup of index $d$.  Let $a_i:=(i+d\Z) \cap R_q$ be the coset intersections with $R_q$, $i=0,\dots,d-1$.  Then $a_i=a_{ip}$, where subscripts are read modulo $d$. 
\end{proposition}

\begin{proof}
The affine relative difference set in $\F_{q^2}$ is invariant under $\theta$, and hence in the additive presentation we have $p \cdot R_q = R_q$ in $\Z/(q^2-1)\Z$. It follows that 
$$a_{ip} = |(-i p+R_q) \cap d\Z| = |(-i+\overline{p}R_q) \cap d\Z| =  |(-i+R_q) \cap d\Z| = a_{i},$$
where $p\overline{p}=1$ in $\Z/(q^2-1)\Z$ and where subscripts on the block sizes are interpreted modulo $d$.
\end{proof}

\begin{remark}
A similar invariance exists for the Singer difference sets $S_q$ intersected with cosets of a subgroup of index $d$.
\end{remark}

\begin{corollary}
The number of different block sizes of the GDD arising from $R_q$ and $d$ is at most the number of orbits of multiplication by $p$ on $\Z/d\Z$.
\end{corollary}



The truth is sometimes better, since intersections from different orbits of $\theta$ might vanish or coincide.

\begin{example}
Let $q=16$, $d=5$ so that Corollary~\ref{affine-gdd} gives an $\{a_0,a_1,\dots,a_4\}$-GDD of type $3^{17}$.  Since $p=2$ is a generator for $\Z/5\Z$, we have only two different block sizes: $a_0$ and $a_1=a_2=a_3=a_4$.  Substituting into (\ref{sum}) and (\ref{squares}), these necessary equations have only the solution $a_0=0$, $a_1=4$ in nonnegative integers.  So, in fact, we obtain a $\{4\}$-GDD of type $3^{17}$.
\end{example}



Extending this example, we have a class of two-block-size GDDs that occur in certain cases.

\begin{corollary}
\label{two-block-sizes}
Suppose $q=p^{2t} \equiv 1 \pmod{d}$ is such that $p$ generates $(\Z/d\Z)^\times$. Then there exists a cyclic
$\{ \frac{q \mp \sqrt{q}}{d}, \frac{q \pm (d-1) \sqrt{q}}{d} \}$-GDD of type $[(q-1)/d]^{q+1}$, where the sign is chosen according to whether $\sqrt{q} \equiv \pm 1 \pmod{d}$.
\end{corollary}

\begin{proof}
We have only two block sizes $a_0$ and $a_1=\dots=a_{d-1}$.  Equations (\ref{sum}) and (\ref{squares}) reduce to
\begin{align*}
a_0+(d-1)a_1 &= q, \text{ and} \\
a_0^2+(d-1)a_1^2 &= \frac{q(q+d-1)}{d}.
\end{align*}
Solving the quadratic equation gives $a_0 = \frac{q \mp \sqrt{q}}{d}$ and $a_1=\frac{q \pm (d-1) \sqrt{q}}{d}$.
\end{proof}


\begin{table}[!ht]
$$
\begin{array}{c|c|l}
q=3n+1 & \text{type} & a_0,a_1,a_2 \\
\hline
4 & 1^{5} & 0, 2, 2 \\
7 & 2^{8} & 2, 4, 1 \\
13 & 4^{14} & 6, 5, 2 \\
16 & 5^{17} & 8, 4, 4 \\
19 & 6^{20} & 4, 9, 6 \\
25 & 8^{26} & 5, 10, 10 \\
31 & 10^{32} & 9, 8, 14 \\
37 & 12^{38} & 16, 9, 12 \\
43 & 14^{44} & 17, 10, 16 \\
49 & 16^{50} & 12, 17, 20 \\
61 & 20^{62} & 20, 25, 16 \\
64 & 21^{65} & 16, 24, 24 \\
67 & 22^{68} & 24, 17, 26 \\
73 & 24^{74} & 22, 30, 21 \\
79 & 26^{80} & 32, 25, 22 \\
97 & 32^{98} & 26, 37, 34 \\
103 & 34^{104} & 30, 32, 41 \\
109 & 36^{110} & 37, 42, 30 \\
121 & 40^{122} & 33, 44, 44 \\
127 & 42^{128} & 49, 36, 42 \\
139 & 46^{140} & 54, 41, 44 \\
151 & 50^{152} & 44, 49, 58 \\
157 & 52^{158} & 57, 56, 44 \\
163 & 54^{164} & 46, 57, 60 \\
169 & 56^{170} & 56, 64, 49 \\
181 & 60^{182} & 58, 69, 54 \\
193 & 64^{194} & 72, 65, 56 \\
199 & 66^{200} & 70, 57, 72 \\
\end{array}
\hspace{1cm}
\begin{array}{c|c|l}
q=4n+1 & \text{type} & a_0,a_1,a_2,a_3 \\
\hline
5 & 1^{6} & 2, 2, 1, 0 \\
9 & 2^{10} & 1, 2, 4, 2 \\
13 & 3^{14} & 2, 4, 5, 2 \\
17 & 4^{18} & 5, 2, 4, 6 \\
25 & 6^{26} & 5, 8, 8, 4 \\
29 & 7^{30} & 10, 8, 5, 6 \\
37 & 9^{38} & 10, 6, 9, 12 \\
41 & 10^{42} & 13, 8, 8, 12 \\
49 & 12^{50} & 9, 12, 16, 12 \\
53 & 13^{54} & 10, 14, 17, 12 \\
61 & 15^{62} & 18, 12, 13, 18 \\
73 & 18^{74} & 17, 14, 20, 22 \\
81 & 20^{82} & 25, 20, 16, 20 \\
89 & 22^{90} & 25, 18, 20, 26 \\
97 & 24^{98} & 29, 26, 20, 22 \\
101 & 25^{102} & 26, 30, 25, 20 \\
109 & 27^{110} & 26, 32, 29, 22 \\
113 & 28^{114} & 25, 24, 32, 32 \\
121 & 30^{122} & 25, 30, 36, 30 \\
125 & 31^{126} & 26, 30, 37, 32 \\
137 & 34^{138} & 29, 32, 40, 36 \\
149 & 37^{150} & 34, 42, 41, 32 \\
157 & 39^{158} & 34, 36, 45, 42 \\
169 & 42^{170} & 45, 36, 40, 48 \\
173 & 43^{174} & 50, 44, 37, 42 \\
181 & 45^{182} & 50, 50, 41, 40 \\
193 & 48^{194} & 45, 42, 52, 54 \\
197 & 49^{198} & 50, 42, 49, 56 \\
\end{array}
$$
\caption{Block sizes and types for $q=3n+1$ and $4n+1$}\label{1}
\end{table}


We  give a list of GDD types and block sizes for various small cases in Tables \ref{1} and \ref{2}




\begin{table}
$$
\begin{array}{c|c|l}
q=5n+1 & \text{type} & a_0,a_1,a_2,a_3,a_4 \\
\hline
11 & 2^{12} & 2, 0, 4, 3, 2 \\
16 & 3^{17} & 0, 4, 4, 4, 4 \\
31 & 6^{32} & 4, 10, 7, 4, 6 \\
41 & 8^{42} & 10, 6, 8, 5, 12 \\
61 & 12^{62} & 12, 12, 18, 9, 10 \\
71 & 14^{72} & 18, 8, 14, 15, 16 \\
81 & 16^{82} & 9, 18, 18, 18, 18 \\
101 & 20^{102} & 26, 22, 14, 21, 18 \\
121 & 24^{122} & 28, 25, 28, 16, 24 \\
131 & 26^{132} & 24, 30, 32, 19, 26 \\
151 & 30^{152} & 31, 34, 28, 22, 36 \\
181 & 36^{182} & 34, 46, 34, 37, 30 \\
191 & 38^{192} & 30, 38, 47, 36, 40 \\
211 & 42^{212} & 42, 36, 46, 51, 36 \\
241 & 48^{242} & 45, 48, 42, 46, 60 \\
\end{array}
\hspace{1cm}
\begin{array}{c|c|l}
q=6n+1 & \text{type} & a_0,a_1,a_2,a_3,a_4,a_5 \\
\hline
7 & 1^{8} & 0, 2, 1, 2, 2, 0 \\
13 & 2^{14} & 2, 2, 2, 4, 3, 0 \\
19 & 3^{20} & 2, 6, 4, 2, 3, 2 \\
25 & 4^{26} & 1, 4, 6, 4, 6, 4 \\
31 & 5^{32} & 5, 6, 8, 4, 2, 6 \\
37 & 6^{38} & 8, 6, 8, 8, 3, 4 \\
43 & 7^{44} & 7, 6, 10, 10, 4, 6 \\
49 & 8^{50} & 8, 8, 8, 4, 9, 12 \\
61 & 10^{62} & 8, 10, 8, 12, 15, 8 \\
67 & 11^{68} & 10, 6, 12, 14, 11, 14 \\
73 & 12^{74} & 14, 16, 9, 8, 14, 12 \\
79 & 13^{80} & 18, 12, 8, 14, 13, 14 \\
97 & 16^{98} & 14, 16, 14, 12, 21, 20 \\
103 & 17^{104} & 16, 14, 17, 14, 18, 24 \\
109 & 18^{110} & 19, 24, 18, 18, 18, 12 \\
\end{array}
$$
\caption{Block sizes and types for $q=5n+1$ and $6n+1$}\label{2}
\end{table}







%\normalsize

\section{Some new MOLS, IMOLS and HMOLS}

Following \cite{Brouwer-sep,Greig}, we can use the GDDs of Corollary~\ref{affine-gdd} to construct mutually orthogonal latin squares via the Bose-Shrikhande-Parker construction, \cite{BSP}. 
We cite the relevant construction below, simplified somewhat for our use.  The usual statement involves `incomplete transversal designs' TD$(k,n)- \sum_{i=1}^t \mathrm{TD}(k,m_i)$, which are equivalent to $k-2$ mutually orthogonal `holey' latin squares of size $n$ missing $t$ disjoint subsquares of size $m_i$.  In the case where all $m_i=1$ and $t=n$, this can be regarded as a family of mutually orthogonal idempotent latin squares of size $n$.  See \cite{MakingMOLS} for a formal definition. 



\begin{theorem}[see \cite{BSP,MakingMOLS}]
\label{bsp}
Let $(V,\Pi,\cB)$ be a $K$-GDD with $|V|=v$ and $\Pi=\{V_1,\dots,V_t\}$.  Suppose $\cB$ partitions into symmetric classes $\cS_1,\dots,\cS_s$, where $\cS_j$ has block size $\alpha_j$.  Let $\epsilon_j \in \{0,1\}$, and suppose there exist
$$\mathrm{TD}(k,\alpha_j+\epsilon_j) - \sum_{i=1}^{\alpha_j+\epsilon_j} \mathrm{TD}(k,1),$$  
i.e.  $k-2$ mutually orthogonal idempotent latin squares of size $\alpha_j+\epsilon_j$, for all $j =1,\dots,s$.  Let $\sigma=\sum_{j=1}^s \epsilon_j \alpha_j$.  
Then there exists a 
$$\mathrm{TD}(k,v+\sigma) - \mathrm{TD}(k,\sigma) - \sum_{i=1}^{t} \mathrm{TD}(k,|V_i|),$$
i.e. $k-2$ mutually orthogonal holey latin squares with hole sizes as indicated.  
\end{theorem}

\begin{remark}
A more general form with similar notation is \cite[Theorem 3.23]{MakingMOLS}; an even more general version of the construction appears as \cite[Theorem 3.7]{BrouwerVR}.
\end{remark}


If, in Theorem~\ref{bsp}, we also have the existence of TD$(k,\sigma)$ and TD$(k,|V_i|)$, then we can `fill holes' to get a TD$(k,v+\sigma)$.  Likewise, assuming the existence of TD$(k,\sigma+1)$ and TD$(k,|V_i|+1)$, we obtain a TD$(k,v+\sigma+1)$.  

A good set of MOLS is possible under the (strange) hypothesis that our intersection sizes $a_0,\dots,a_{d-1}$ of Section 2 be prime powers, or one less than prime powers. 
We give two examples improving known lower bounds on $N(n)$, the maximum number MOLS, in \cite[Table III.3.87]{Handbook}, which in recent years has become fairly static.

\begin{example}
Let $q=79$, $d=3$.  We compute from Corollary~\ref{affine-gdd} a $\{22,25,32\}$-GDD of type $26^{80}$ having symmetric classes of each block size.  By Theorem~\ref{bsp}, we obtain a TD$(23,2102)-$TD$(23,22)-80 \times$TD$(23,26)$, where we have incremented $22$ to $23$ using $\epsilon_1$, say.  For this, we have used the existence of $q-2$ mutually orthogonal idempotent latin squares for prime powers $q$.  Add 1 to the hole sizes and fill them, producing a TD$(23,2103)$.  It follows that $N(2103) \ge 21$; compare with $N(2103) \ge 15$ in \cite{Handbook}.
\end{example}



\begin{example}
For $q=127$, $d=3$ we similarly have a $\{36,42,49\}$-GDD of type $42^{128}$ with symmetric classes.  Taking $\epsilon_1=\epsilon_2=1$ in Theorem~\ref{bsp} (corresponding to classes of block size 36 and 42) leads to 
$N(42 \times 128 + 36+42+1) =N(5455) \ge 35$; compare with $N(5455) \ge 15$ in \cite{Handbook}.
\end{example}

Next, we have an improved set of incomplete MOLS.  Following the standard notation, let the maximum number of incomplete MOLS of size $n$ missing a common subsquare of size $m$ be denoted $N(n;m)$.

\begin{example}
With $q=41$ and $d=4$, we get a $\{8,8,12,13\}$-GDD of type $10^{42}$.  So $N(449;29) \ge 7$; compare with $N(449;29) \ge 6$ in \cite{Handbook}.
\end{example}

Finally, we have some noteworthy holey MOLS with a uniform partition into holes.  Let $N(h^m)$ denote the maximum number of holey MOLS of size $hm$ missing $m$ disjoint holes of size $h$.

\begin{example}
With $q=37$ and $d=3$, we get a $\{9,12,16\}$-GDD of type $12^{38}$.  So $N(12^{39}) \ge 7$; compare with $N(12^{39}) \ge 4$ in \cite{Handbook}
\end{example}

\begin{example}
With $q=61$ and $d=3$, we get a $\{16,20,25\}$-GDD of type $20^{62}$.  So $N(20^{63}) \ge 15$, and this is the second largest number of HMOLS known (of any type) for the challenging case of group size 20.
\end{example}

\begin{example}
With $q=49$ and $d=4$, we get a $\{9,12,12,16\}$-GDD of type $12^{50}$, with two symmetric classes of block size 12.  So $N(12^{52}) \ge 7$, and this is again a reasonable lower bound for a difficult group size.
\end{example}

This general technique can produce many interesting non-uniform HMOLS, although there is no table for comparison.  


\section{Optical orthogonal codes and difference triangle sets}

An $(n,w,\lam)$ \emph{optical orthogonal code} (OOC) is a family of cyclic binary sequences of length $n$, constant weight $w$, and such that any two sequences from different cycles has at most $\lam$ ones in common positions.  In other words, all `Hamming correlations' between different sequences are at most $\lam$.  As a cyclic binary code, the minimum distance of such an OOC is at least $2(w-\lam)$.

If we extract the supports of binary sequences in an $(n,w,1)$ OOC, the result is a family of sets of size $w$ in $\Z/n\Z$ which form a `difference packing', that is, such that any nonzero element in the group occurs as a difference in one of the sets at most once.  The converse relationship is also clear.

We propose the cyclic GDD of Corollary~\ref{two-block-sizes}, with blocks of size $a_0$ discarded, as an infinite class of (sometimes very good) difference packings.

\begin{proposition}
Suppose $q=p^{2t}$ with $\sqrt{q} \equiv 1 \pmod{d}$.  Let $d \ge 3$ be an integer such that $p$ generates $(\Z/d\Z)^\times$. Then there exists a  $(q^2-1,\frac{q + (d-1) \sqrt{q}}{d},1)$ OOC of size $d-1$.
\end{proposition}

An $(n,k)$-\emph{difference triangle set} (abbreviated D$\Delta$S) is a set $\{X_1,X_2,\dots,X_n\}$ of $(k+1)$-subsets of integers such that the $nk(k+1)/2$ (unsigned) differences between two elements in some $X_i$ are distinct and nonzero.  The case $n=1$ reduces to a `Golomb ruler' with $k+1$ marks or, equivalently, a `Sidon set' of size $k+1$.  

For example, a $(2,2)$-D$\Delta$S is given by $\{\{0,1,4\}, \{0,2,7\}\}$.  As illustrated in this example, we can assume by translation that each set $X_i$ has minimum element $0$; in this case, the difference triangle set is called \emph{normalized}.  Similar to Golomb rulers, it is of interest to find normalized $(n,k)$-D$\Delta$S such that the maximum integer in any of its sets, called the \emph{scope}, is as small as possible.  The $(2,2)$-D$\Delta$S above has scope 7, which is best possible.  A table of known upper and lower bounds on minimum scopes of $(n,k)$-D$\Delta$S for small $n,k$ can be found in \cite[\S VI.19]{Handbook}.

If we interpret a cyclic difference set over the integers (i.e. ignoring the modulus), the result is a Golomb ruler.  In a similar way, the second author in \cite{LingDTS} used relative difference sets to obtain record-breaking scopes for various $(n,k)$-D$\Delta$S.

To illustrate another application of our coset technique, we offer one example improvement on the table mentioned above. 
%This is similar in spirit to \cite{LingDTS}.

\begin{example}
Let $q=81$ and consider the Singer difference set $S_q$ of size $q+1$ in $\Z/(q^2+q+1)\Z$.  Project $S_q$ onto $d=7$ cosets, 
and compute that $|S \cap 7 \Z|=4$, while $|S \cap (i+7 \Z)| =13$ for all nonzero $i \in \Z/7\Z$.  Retain the six `full' cosets and translate each to include zero.  All internal differences are distinct multiples of 7, so we divide and normalize again, this time searching for an optimal scaling and translation to minimize the scope.  We obtain a $(6,12)$-D$\Delta$S of scope $786$, which improves on $797$ found in \cite[Table VI.19.37]{Handbook}:
\end{example}
$$\begin{array}{l}
\{\{0, 36, 57, 89, 102, 229, 293, 374, 499, 619, 702, 716, 774\}, \\
~\{0, 160, 161, 350, 356, 461, 532, 576, 587, 638, 663, 755, 786\},\\ 
~\{0, 29, 70, 178, 241, 243, 278, 320, 337, 376, 494, 618, 757\}, \\
~\{0, 43, 48, 152, 273, 303, 353, 357, 431, 439, 491, 500, 538\}, \\
~\{0, 24, 112, 180, 207, 321, 475, 565, 605, 715, 727, 734, 749\}, \\
~\{0, 132, 165, 302, 318, 393, 403, 421, 669, 736, 762, 782, 785\}\}.
\end{array}$$

We have not undertaken an exhaustive analysis of other cases.  Qualitatively, it seems that this technique for constructing difference triangle systems has too much waste unless the (relative) difference set admits a very favorable partition by cosets.

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


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

\begin{thebibliography}{99}

\bibitem{BSP}
R.C. Bose, S.S. Shrikhande and E.T. Parker, 
Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture.
\emph{Canad. J. Math.} 12 (1960), 189--203.

\bibitem{Brouwer-sep}
A.E.~Brouwer, A series of separable designs with application to pairwise orthogonal Latin squares. \emph{European J. Combin.}  1 (1980), 39--41.

\bibitem{BrouwerVR}
A.E.~Brouwer and G.H.J. van Rees, More mutually orthogonal latin squares. \emph{Discrete Math.} 39 (1982), 263--281.

\bibitem{CES}
S.~Chowla, P.~Erd\H os, and E.G.~Strauss, On the maximal number of pairwise orthogonal latin squres of a given order. 
{\em Canad. J. Math.} 12 (1960), 204--208.

\bibitem{MakingMOLS}
C.J.~Colbourn and J.H.~Dinitz, Making the MOLS table.  \emph{Computational and constructive design theory},  67--134, Math. Appl., 368, Kluwer, Dordrecht, 1996.

\bibitem{Handbook}
C.J.~Colbourn and J.H.~Dinitz, eds., The CRC Handbook of Combinatorial
Designs, 2nd edition, CRC Press, Boca Raton, 2006.

\bibitem{RDS-orig}
J.E.H. Elliott and A.T. Butson,
Relative difference sets.
\emph{Illinois J. Math.} 10 (1966), 517--531. 

\bibitem{Greig}
M. Greig, Designs from projective planes and PBD bases. 
\emph{J. Combin. Des.} 7 (1999), 341--374.

\bibitem{Lemmermeyer}
F.~Lemmermeyer, Reciprocity laws: from Euler to Eisenstein. 
Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2000.

\bibitem{LingDTS}
A.C.H.~Ling, Difference triangle sets from affine planes.
\emph{IEEE Trans. Inform. Theory} 48 (2002), 2399--2401.

\bibitem{RDS-survey}
A. Pott,
A survey on relative difference sets. \emph{Groups, difference sets, and the Monster} (Columbus, OH, 1993), 
195--232, Ohio State Univ. Math. Res. Inst. Publ., 
4, de Gruyter, Berlin, 1996.

\bibitem{Pott}
A.~Pott, Two applications of relative difference sets: Difference triangles and
negaperiodic autocorrelation functions.
\emph{Discrete Math.} 308 (2008), 2854--2861.

\bibitem{RMW0}
R.M.~Wilson, An existence theory for pairwise balanced designs I: 
Composition theorems and morphisms. \emph{J. Combin. Theory Ser. A}
13 (1972), 220--245.

\end{thebibliography}

\end{document}