% 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|