%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% July 23, 2003 %%% REU paper %%% A Survey of Relative Difference Sets \documentclass{article} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{latexsym} \DeclareSymbolFont{AMSb}{U}{msb}{m}{n} \DeclareMathSymbol{\C}{\mathbin}{AMSb}{"43} \topmargin -.75in \textwidth 6.5in \textheight 9.5in \oddsidemargin 0in \evensidemargin 0.1in \baselineskip 3ex \begin{document} \title{A Survey of Relative Difference Sets} \author{ Christine Berkesch \\ \\ Jeff Ginn \\ \\ Erin Haller \\ \\ Erin Militzer \\ \\} \maketitle \vskip12pt \abstract{ A $(v,k,\lambda)$ difference set $D$ in a group $G$ is a subset of $G$ such that every nonidentity element of $G$ is covered exactly $\lambda$ times by quotients $d_1d_2^{-1}, \ d_1, d_2 \in D.$ In the group ring, this means that $D$ obeys the equation $DD^{(-1)} = k \cdot 1 + \lambda(G-1)$. An $(m,n,k,\lambda)$ relative difference set $R$ is a difference set relative to a normal subgroup $N$ of $G$ satisfying the similar equation $RR^{(-1)} = k \cdot 1 + \lambda(G - N)$. Difference sets may be used to construct symmetric designs with a nice automorphism group; relative difference sets are used to construct square divisible designs with a nice automorphism group. Symmetric designs and divisible designs are important combinatorial structures. We will describe various search techniques for relative difference sets (RDS), including the exhaustive search method for small groups using the computer program GAP, as well as the multiplier theorem and group representations methods used for larger groups. We will provide a catalog of RDS found, as well as those eliminated, using these methods. A proof is presented of the non-existence of $(2m,2,2m,m)$ relative difference sets in quaternion groups of order $4m$ where $m$ is odd. In conclusion, we will state several interesting results found for specific parameters, including (12,2,12,6) and (12,3,12,4). } \tableofcontents \pagebreak \openup.5\jot %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 1 Introduction - Difference Sets and Symmetric Designs % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction - Difference Sets and Symmetric Designs} An important topic in the field of discrete mathematics is the study of block designs. A $(n,k,\lambda)$ block design is a set of $v$ points arranged into $b$ blocks of size $k$ where any 2 points are together on exactly $\lambda$ blocks. A design is called symmetric if $v = b$. Symmetric designs may be constructed using difference sets. Given a difference set $D$ in a group $G$, define the points of the design as the elements of $G$ and the blocks as the translates $gD$ for $g \in G$ of the difference set. This construction gives a symmetric design with an automorphism group acting sharply transitive on the points of the design (\cite{Pott}, p. 8-10). A group divisible design is a combinatorial structure with a slightly weaker condition than a symmetric block design (\cite{Pott}, p. 3). A group divisible design may be constructed from relative difference sets in the same way that symmetric designs are constructed from difference sets. Much of the research on RDS has focused on families of semiregular difference sets (see \cite{Pott}, p. 40). This paper will survey small parameter sets for semiregular RDS and describe several semiregular RDS which were previously unknown. In this paper, we exhausively determine the existence of RDS with certain small parameters and find new semiregular RDS. \vskip8pt \noindent {\bf Acknowledgements} \noindent This research was done during Summer 2002 at Central Michigan University under the guidance of Dr. Ken Smith and sponsorship of the National Science Foundation Research Experience for Undergraduates grant (NSF DMS-0097394). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 2 Basics of Difference Sets and Relative Difference Sets % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Basics of Difference Sets and Relative Difference Sets} Throughout this paper, we use definitions and notation based on those of Alexander Pott \cite{Pott}. \\ \noindent {\bf Definition 1.} A $(v,k,\lambda)$ {\it difference set }$D$ is a subset of a group $G$ of order $k$ such that in the list of quotients $d_1\cdot d_2^{-1}$ with distinct elements $d_1,d_2 \in D$ each nonidentity element of $G$ occurs exactly $\lambda$ times. \\ \noindent {\bf Definition 2.} An $(m,n,k,\lambda)$ {\it relative difference set }$R$ in a group $G$ of order $m\cdot n$ relative to a forbidden normal subgroup $N$ $(|N|=n)$ is a $k$-subset of $G$ with the following property: the list of quotients $r_1 \cdot r_2^{-1}$ with distinct elements $r_1,r_2^{-1}\in R$ contains each element in $G/N$ exactly $\lambda$ times and does not contain the elements of $N$. Thus, the following formula in the group ring $ZG$ must be satisfied: $$RR^{(-1)} = k\cdot 1 + \lambda(G - N).$$ Difference sets are homomorphic images of relative difference sets (RDS). One can show that the existence of an $(m,n,k,\lambda)$ relative difference set implies the existence of an $(m,k,n\lambda)$ difference set. Suppose a group $G$ contains a relative difference set $R$ relative to a normal subgroup $N$, then if a normal subgroup $H$ of $G$ is contained in $N$, there exists a relative difference set in $G/H$ relative to $N/H$. Furthermore, if $R$ has parameters $(m,n,k,\lambda)$ then the RDS in $G/H$ will have parameters $(m,\frac n h, k, \lambda h)$ where $|H| = h.$ Hence, $G/N$ will contain an $(m,k,n \lambda)$ difference set which is said to be a contraction of $R$. $R$ is said to be an extension or lifting of this difference set. The contraction of a semiregular RDS is the trivial $(m,m,m)$ difference set. The existence of a $(v,k,\lambda)$ difference set implies the existence of a $(v,k,\lambda)$ $symmetric$ $design$. Similarly, the existence of an $(m,n,k,\lambda)$ RDS implies the existence of an $(m,n,k,\lambda)$ $divisible$ $design$. (See Section 1.1 of \cite{Pott}.) \\ \noindent {\bf Definition 3.} An $(m,n,k,\lambda)$ {\it divisible design} is an incidence structure with $mn$ points and the same number of blocks such that every block has $k$ points and every point is on $k$ blocks. Also, every pair of points will be together on $\lambda$ blocks except the points corresponding to the cosets of the normal subgroup $N$ to which the $(m,n,k,\lambda)$ RDS is relative. \\ Let the elements of a group $G$ form the points of a divisible design. The translates of a relative difference set $R$ in $G$ form the set of blocks $B$ of the design, so that $B = \{gR:g \in G\}$. Divisible designs are often useful in projective geometries. If we are given a projective plane and remove one of the blocks and all those parallel to it, we are left with a divisible design \cite{Pott94}. \\ \noindent {\bf Lemma 1.} Given a group $G$ and a normal subgroup $N$ of $G$, $R$ may contain no two elements of the same coset of $N$. \vskip2pt \noindent {\bf Proof.} Let $x \in G$ and $Nx$ be a right coset of $N$. Suppose $r_1$ and $r_2$ are distinct elements of $R$ such that $r_1 = n_{1}x$ and $r_2 = n_{2}x$ where $n_1, n_2 \in N$. Then $$r_{1}r_{2}^{-1} = (n_{1}x)x^{-1}n_2^{-1} = n_{1}n_{2}^{-1} \in N,$$ but $r_1r_2^{-1}$ is not supposed to be in $N$, a contradiction. $\Box$ \\ \noindent {\bf Lemma 2.} Given a group $G$ with normal subgroup $N$ and RDS $R$, then any translate $Rg := \{rg : r \in R\}$ of $R$ is also a RDS. \vskip2pt \noindent {\bf Proof.} If $x = r_1r_2^{-1}$ for $r_1, r_2 \in R$ then $x = r_1(gg^{-1})r_2 = (r_1g)(r_2g)^{-1}$ and $r_1g, r_2g \in Rg.$ $\Box$ \\ \noindent {\bf Definition 4.} A relative difference set is said to be {\it semiregular} if $m=k=n\lambda$. \\ \noindent {\bf Theorem 1 (Prime powers in RDS)}. $(p^{a},p^{b},p^{a},p^{a-b})$ RDS exist whenever $p$ is a prime and $a \ge b$ \cite{Pott94}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 3 Search Techniques % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Search Techniques} In this section we describe the various techniques we used to search for relative difference sets in finite groups. \subsection{The Bose-Connor Theorem} {\bf Theorem 2} \cite{Pott}. Let $R$ be an $(m,n,k,\lambda)$ RDS in a group $G$ with respect to a subgroup $N$. If $k^2 \ge mn\lambda$ and $k> 0$ then \vskip4pt (1) if $m$ is even then $k^2 -mn\lambda$ is a square. Moreover, if $m \equiv 2 \mod 4$ and $n$ is even, then $k$ is the sum of two squares. \vskip4pt (2) if $m$ is odd and $n$ is even then \indent (2a) $k$ is a square and \indent (2b) the equation $$(k^2-mn\lambda) x^2 + (-1)^{m(m-1)/2}n \lambda y^2 = z^2$$ has nontrivial integer solutions $(x,y,z).$ \vskip4pt (3) if both $m$ and $n$ are odd then the equation $$k x^2 + (-1)^{n(n-1)/2}n y^2 = z^2$$ has nontrivial integer solutions. \\ The Bose-Connor theorem is useful in ruling out RDS parameters. For example, there exist no nontrivial integer solutions to the equation $$10x^2 + ((-1)^{5(5-1)/2}\cdot5)y^2 = z^2,$$ which corresponds with the $(19,5,10,1)$ parameter set, where $m$ and $n$ are both odd. This implies that no $(19,5,10,1)$ RDS exists. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 3.2 GAP % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Groups, Algorithms, and Programming (GAP)} For groups of small order, an exhaustive search can be the most effective method for finding all possible RDS. The computer program GAP \cite{GAP} provides a complete listing of groups, along with the capability to search them for RDS. By modifying a GAP program written by Dr. Ken Smith, it was possible to search for RDS with various parameters, the results of which can be found in section 4.1. The program checks all groups corresponding to a given set of parameters for a RDS. Within each group $G$, it finds each normal subgroup $N$ of the appropriate order and also generates the cosets with respect to $N.$ Each relative difference set has at most one element in a given coset of $N$, and so a RDS $R$ is a subset of a transversal (a system of coset representatives) of $N$. If the RDS is semiregular, then it is equal to a transversal. The GAP program chooses a transversal and checks to see if it provides a RDS. If not, it chooses another transversal. There are $n^m$ transversals for a given subgroup $N$, but the search can be reduced to $n^{m-2}$ possibilities by fixing two elements of $R$: the identity element and one element $x$ from another coset. This is allowed by the following argument. Assume $x \not\in N.$ Then there exists $r_1, r_2 \in R$ such that $x = r_1r_2^{-1}.$ Since $R$ is a RDS, so is $Rr_2^{-1}.$ But since $r_1, r_2 \in R$ then $x=r_1r_2^{-1}$ and $1 = r_2r_2^{-1}$ are in $Rr_2^{-1}.$ Thus the RDS $R$ can be replaced by the RDS $Rr_2^{-1},$ which contains both $1$ and $x$. If the initial transversal choice fails, the elements in the cosets are permuted until a RDS is found or all possibilities have been exhausted. The problem, however, is that as the order of the group grows and the number of groups of the orders grow, the number of possibilities for transversals increases exponentially. For this reason, the exhaustive method should only be used for small groups. For larger groups, other methods had to be implemented. Exhaustively searching a group for an $(m,n,k,\lambda)$ RDS required checking $n^{m-2}$ putative difference sets to see if they satisfied the basic equation from definifion 2. If $n^{m-2}$ was on the order of a million, this process took several hours on a Mac G3 laptop computer. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 3.3. Multipliers % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Multipliers} {\bf Lemma 3.} If $A$ is an Abelian group written in additive notation and $t$ is relatively prime to the order of $A$, then $a \mapsto ta$ for all $a \in A$ is an automorphism of $A$. \\ \noindent {\bf Definition 5.} If $tD = g+D$ for some $g \in G$, then $t$ is said to be a {\it multiplier}. \\ \noindent {\bf Conjecture.} Suppose $t$ is relatively prime to the order of $A$ and, in addition, $t | (k - \lambda)$ in a difference set or if $t | (k^2 - mn\lambda)$ in a RDS. Then, if there exists a $(v,k,\lambda)$ difference set or an $(m,n,k,\lambda)$ RDS then there is a difference set or RDS fixed by $t$ (see \cite{Pott}, pp. 29-30). \\ Suppose we are searching for a $(7,4,2)$ difference set in $Z_7$; then $t = 2$ is a multiplier. The multiplier $t=2$ generates the orbits $\{0\}, \{1,2,4\}, \{3,5,6\}$ in $\{Z_7, + \}$. We pick $\{0\}$ and one of $\{1,2,4\}$ or $\{3,5,6\}$ to be our difference set. Note that the sets $\{0,1,2,4\}$ and $\{0,3,5,6\}$ are isomorphic to one another under $a \mapsto 3a$. A multiplier may also be lifted." If we were to lift the $(7,4,2)$ difference set from the above example into a $(7,2,4,2)$ RDS, then the multiplier $t = 2$ would be lifted to $t = 9$ where $a \mapsto 9a$ is an automorphism of $Z_{14}$ and fixes a $(7,2,4,2)$ RDS. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 3.4 Representations % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Representations} A {\em representation} $\Phi$ of a group $G$ is an operation-preserving map from $(G,*)$ into $(GL_{n}(\C), \cdot)$. Representations will be used to distinguish between the elements in each coset while building a RDS. A representation $\Phi$ is said to be {\em trivial} on a subgroup $N$ of $G$ if $\Phi(x) = 1$ for all $x \in N.$ Representations of finite groups may be built from a special set of representations called irreducible representations" (see \cite{Lederman}). We extend a representation $\Phi$ on $G$ to a representation of the group ring $ZG$ by defining $\Phi(\sum a_gg):=\sum a_g \Phi(g)$. Thus, $\Phi: ZG \rightarrow$ Mat$_N(\C)$ is an algebra homomorphism. \vskip8pt {\bf Theorem 3}. Let $N$ be a normal subgroup of $G$; let $\Phi$ be an irreducible representation of $G$. Then either $\Phi$ is trivial on $N$ or $\displaystyle{\sum_{x\in G} \Phi(x)=0.}$ \vskip6pt In the case where $\Phi (N)$ is trivial on $N$, each element in a coset of $N$ is treated the same. This only reiterates the fact that one element must be chosen from each coset without providing new information to aid in the actual selection of elements. Thus for the given purposes, the cases of interest occur when $\sum_{x\in G} \Phi(x)=0.$ (For further reading and examples on this topic, see \cite{Lederman} and \cite{Thomas}.) When $\Phi$ is not trivial on $N$, it should be noted that both $\sum_{g \in G} \Phi(g)$ and $\sum_{n \in N} \Phi(n) = 0$, and so $\Phi(G-N) = 0$. \vskip8pt \noindent {\bf Example:} \\ \indent Search for an (8,2,8,4) RDS in the group $G = Q_8 =$ with respect to the unique subgroup of order two: $N = \{1,x^4\}.$ Let $\zeta$ be a primitive 8th root of unity. Here are the representations of $G$ and their action on $N$. \vskip8pt \begin{center} Representations \vskip8pt \begin{tabular}{|c|c|c|c|c|c|} \hline & $x$ & $y$ & $N$ &\\ \hline & 1 & $\pm$ 1 & 2 & trivial on $N$ \\ \hline & -1 & $\pm$ 1 & 2 & trivial on $N$ \\ \hline $\Phi_{1}$ & $\begin{pmatrix} \zeta & 0 \\ 0 & \bar{\zeta} \end{pmatrix}$ & $\begin{pmatrix} 0 & 1\\ -1 & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$ & \\ \hline \hskip15pt & $\begin{pmatrix} \zeta^2 & 0\\ 0 & \bar{\zeta}^2 \end{pmatrix}$ & $\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ & $\begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}$ & trivial on N \\ \hline $\Phi_{2}$ & $\begin{pmatrix} \zeta^3 & 0\\ 0 & \bar{\zeta}^3 \ \end{pmatrix}$ & $\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$ & \\ \hline \end{tabular} \end{center} %End Representations \vskip8pt Since $\Phi_{1}$ and $\Phi_{2}$ are the only cases which are non-trivial on N, they are the only two that need to be considered. For $\Phi_1$ and $\Phi_2$, $RR^{(-1)} \mapsto 8I_2$ + 4$[\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$ - $\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}]$ = $\begin{pmatrix} 8 & 0 \\ 0 & 8 \end{pmatrix}$ \vskip8pt First, let us consider $\Phi_1$. The cosets with respect to $N$ are: \vskip8pt \begin{center} \begin{tabular}{c|c|c|c|c|c|c|c} $1$ & $x$ & $x^2$ & $x^3$ & $y$ & $xy$ & $x^{2}y$ & $x^{3}y$ \\ $x^4$ & $x^5$ & $x^6$ & $x^7$ & $x^{4}y$ & $x^{5}y$ & $x^{6}y$ & $x^{7}y$ \\ \end{tabular} \end{center} \vskip6pt These elements map as follows under $\Phi_{1}$: \vskip6pt %Begin coset mapping \hfill{ \tiny \begin{tabular}{c|c|c|c|c|c|c|c} $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ & $\begin{pmatrix} \zeta & 0 \\ 0 & \bar{\zeta} \end{pmatrix}$ & $\begin{pmatrix} \zeta^2 & 0\\ 0 & \bar{\zeta}^2 \end{pmatrix}$ & $\begin{pmatrix} \zeta^3 & 0\\ 0 & \bar{\zeta}^3 \end{pmatrix}$ & $\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & \zeta \\ -\bar{\zeta} & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & \zeta^{2} \\ -\bar{\zeta}^{2} & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & \zeta^{3} \\ -\bar{\zeta}^{3} & 0 \end{pmatrix}$ \\ $\begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}$ & $\begin{pmatrix} -\zeta & 0 \\ 0 & -\bar{\zeta} \end{pmatrix}$ & $\begin{pmatrix} -\zeta^2 & 0\\ 0 & -\bar{\zeta}^2 \end{pmatrix}$ & $\begin{pmatrix} -\zeta^3 & 0\\ 0 & -\bar{\zeta}^3 \ \end{pmatrix}$ & $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & -\zeta \\ \bar{\zeta} & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & -\zeta^{2} \\ \bar{\zeta}^{2} & 0 \end{pmatrix}$ & $\begin{pmatrix} 0 & -\zeta^{3} \\ \bar{\zeta}^{3} & 0 \end{pmatrix}$ \\ \end{tabular} %End coset mapping } \normalsize \vskip10pt Let $R \mapsto \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ and $R^{(-1)}$ $\mapsto$ $\begin{pmatrix} \bar{a} & \bar{c} \\ \bar{b} & \bar{d} \end{pmatrix}$, where $a = \epsilon_{0} + \epsilon_{1}\zeta + \epsilon_{2}\zeta^{2} + \epsilon_{3}\zeta^{3}$ and $b = \epsilon_{4} + \epsilon_{5}\zeta + \epsilon_{6}\zeta^{2} + \epsilon_{7}\zeta^{3}.$ Here $\epsilon_{i} = \pm1,$ where 1 indicates the element from top row of a coset and -1 indicates the element from bottom row of a coset. The elements $c$ and $d$ follow from the values of $a$ and $b$. \vskip8pt Therefore, $RR^{(-1)}$ $\mapsto$ $\begin{pmatrix} a\bar{a} + b\bar{b} & a\bar{c} + b\bar{d} \\ c\bar{a} + d\bar{b} & c\bar{c} + d\bar{d} \end{pmatrix}$ = $\begin{pmatrix} 8 & 0 \\ 0 & 8 \end{pmatrix}$. \vskip8pt In other words, $||a||^2 + ||b||^2 = 8$ \hskip3pt and \hskip3pt $c\bar{a} + d\bar{b} = 0$. \vskip8pt One solution to these equations is $\epsilon_{i} = (1, 1, 1, 1, 1, 1, -1,1)$, i.e. all of the elements for the relative difference set are from the top row in the cosets except for the second to last one. \vskip8pt Using these choices, $a = 1 + (\sqrt{2} +1)i$ \ and \ $b = 1 + (\sqrt{2} -1)i$. \vskip8pt So $||a||^2 = 4 + 2\sqrt{2}$, $||b||^2 = 4 - 2\sqrt{2}$, and $||a||^{2} + ||b||^{2} = 8$, as desired. \vskip8pt By working back through the mappings, we find that $R = 1 + x + x^2 + x^3 + y + xy + x^3y + x^6y$ is an $(8,2,8,4)$ RDS in $Q_8$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 4 Results % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Results} \subsection{GAP} The following tables describe the results of an exhaustive search in GAP, grouped according to the type of relative difference set. In each table we list parameters of relative difference sets and determine the existence of a RDS with those parameters. If we found the difference sets using GAP in an exhaustive search, we included, for each group with a RDS, the number of the group in GAP's small group library. For example, 16.2,3,4,5,9,10,11,12,13'' in the GAP library number'' column in the first table indicates that of the fourteen groups of order sixteen, the groups numbered 2-5 and 9-13 have $(8,2,8,4)$ relative difference sets. \vskip14pt \begin{center} $(m,2,m,m/2)$ \vskip8pt \begin{tabular}{|c|c|c|} \hline Parameters & RDS? & GAP library number \\ \hline (6,2,6,3) & no & \\ \hline (8,2,8,4) & yes & 16.2, 3, 4, 5, 9, 10, 11, 12, 13 \\ \hline (10,2,10,5) & no & \\ \hline (12,2,12,6) & yes & 24.3, 4, 11 \\ \hline (14,2,14,7) & no & \\ \hline \end{tabular} \vskip18pt $(m,m,m,1)$ \vskip8pt \begin{tabular}{|c|c|c|} \hline Parameters & RDS? & GAP library number \\ \hline (4,4,4,1) & yes & 16.2, 6, 12 \\ \hline (5,5,5,1) & yes & 25.2\\ \hline (6,6,6,1) & no & \\ \hline (7,7,7,1) & yes* & \\ \hline (8,8,8,1) & yes* & \\ \hline \end{tabular} \vskip4pt {\scriptsize *These exist by Theorem 1. No further search was performed.} \vskip16pt Other \vskip8pt \begin{tabular}{|c|c|c|} \hline Parameters & RDS? & GAP library number \\ \hline (8,2,8,4) & yes & 16.2, 3, 4, 5, 9, 10, 11, 12, 13 \\ \hline (8,4,8,2) & yes & 32.21, 23, 25, 26, 28, 29, 32, 33, 35\\ \hline (9,3,9,3) & yes & 27.2, 3, 4, 5\\ \hline \end{tabular} \end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Quaternion groups % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Quaternion Theorem} \vskip8pt The quaternion groups, $Q_{2m} =$, are a particularly interesting case for the $(2m,2,2m,m)$ parameters. We found the following when considering these groups: \begin{center} \begin{tabular}{|c|c|c|} \hline Parameters & RDS? & Reason \\ \hline (4,2,4,2) & Yes & \\ \hline (6,2,6,3) & No & Exhaustive search (GAP) \\ \hline (8,2,8,4) & Yes & \\ \hline (10,2,10,5) & No & Exhaustive search (GAP) \\ \hline (12,2,12,6) & Yes & \\ \hline (14,2,14,7) & No & Bose-Connor Theorem \\ \hline (16,2,16,8) & Yes & \\ \hline (18,2,18,9) & No & Exhaustive search (GAP) \\ \hline (20,2,20,10) & Yes & \\ \hline (22,2,22,11) & No & Bose-Connor Theorem \\ \hline (24,2,24,12) & Yes & \\ \hline \end{tabular} \end{center} \vskip8pt There is an obvious pattern in the existence of a RDS when $m$ is even and nonexistence when $m$ is odd. With this in mind, the following theorem arose. \\ \noindent {\bf Theorem 4.} There do not exist any $(2m,2,2m,m)$ RDS in $Q_{2m}$ when $m$ is odd. \vskip4pt \noindent {\bf Proof.} For $(2s,2,2s,s)$ RDS in $Q_{2s}$ when $s$ is odd, check two representations: \vskip6pt \hskip18pt $\Phi_1: x \mapsto -1$, \ $y \mapsto i.$ \vskip6pt \hskip18pt $\Phi_2: x \mapsto$ $\begin{pmatrix} \zeta & 0 \\ 0 & \bar{\zeta} \end{pmatrix}$, \ $y \mapsto$ $\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix},$ \vskip4pt \hskip38pt where $\zeta$ is a primitive $2s^{th}$ root of unity. \vskip10pt By constructing $R$ from the cosets of $Q_{2m}$ with respect to $N$, it is obvious that $$R = \displaystyle{\sum_{i=0}^{s-1} a_i x^i} + (\displaystyle{\sum_{i=0}^{s-1} b_i x^i}) y.$$ \vskip2pt Therefore, $RR^{(-1)} = 2s \cdot 1 + \lambda (0) = 2s \cdot 1$. \vskip8pt For $\Phi_{2}$, $R \mapsto \begin{pmatrix} \displaystyle{\sum_{i=0}^{s-1} a_i \zeta^i} & 0 \\ 0 & \displaystyle{\sum_{i=0}^{s-1} a_i \bar{\zeta}^i} \end{pmatrix} + \begin{pmatrix} \displaystyle{\sum_{i=0}^{s-1} b_i \zeta^i} & 0 \\ 0 & \displaystyle{\sum_{i=0}^{s-1} b_i \bar{\zeta}^i} \end{pmatrix}y,$ \vskip4pt \hskip15pt $= \begin{pmatrix} A & 0 \\ 0 & \bar{A} \end{pmatrix} + \begin{pmatrix} B & 0 \\ 0 & \bar{B} \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix},$ \vskip4pt \hskip15pt $=\begin{pmatrix} A & B \\ -\bar{B} & \bar{A} \end{pmatrix}$. \vskip4pt So, $RR^{(-1)} \mapsto \begin{pmatrix} A\bar{A} + B\bar{B} & 0 \\ 0 & A\bar{A} + B\bar{B} \end{pmatrix}$. \vskip8pt Therefore $A\bar{A} + B\bar{B} = 2s \in (2)$ but $\notin (4)$. \vskip6pt \hangindent24pt \hskip16pt By $(2)$ and $(4)$, we mean the ideals generated by 2 and 4, respectively. While $A$ and $B$ are cyclotomic integers, the given statement still holds. For further reading on this topic, consult Ireland and Rosen \cite{Ireland}. \vskip8pt Now, $A = \displaystyle{\sum_{i=0}^{s-1} a_i \zeta^i}$, where $a_i = \pm 1$, the indicator within each coset. \vskip3pt $A+0 = \displaystyle{\sum_{i=0}^{s-1} a_i \zeta^i + \sum_{i=0}^{s-1} (-1)^i \zeta^i},$ \vskip3pt \hskip28pt $= \displaystyle{\sum_{i=0}^{s-1} (a_i + (-1)^i) \zeta^i}.$ \vskip4pt \hskip40pt $\Rightarrow A \in (2)$ and similarly, $B \in (2)$. \vskip2pt \hskip40pt $\Rightarrow$ Since $(2)(2) = (4)$, we have that $A\bar{A} + B\bar{B} \in (4)$, a contradiction. $\Box$ \vskip12pt This leaves the cases with $m$ even open. We have not yet been able to prove the existence of a $(2m,2,2m,m)$ RDS in this case, but do believe it is true. We conjecture that there exists a $(2m,2,2m,m)$ RDS in all $Q_{2m}$ when $m$ is even. After reaching this conclusion, we found Ito's conjecture, which states that there are $(4t,2,4t,2t)$ RDS in $Q_{8t}$ for all $t$ such that $2t-1$ or $4t-1$ is a prime power \cite{Ito}. This conjecture is strong and has been verified for all $t \leq 46$ \cite{Schmidt}. It is important to point out that a proof for this conjecture would also imply the Hadamard conjecture, which has remained open since posed in 1893. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Specific parameters % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Specific Parameters} \subsubsection{($12,2,12,6)$} It is worth noting that we found only three $(12,2,12,6)$ RDS, all in \underline{nonabelian} groups: $SL_2(3)$, $Q_{12}$, and $Z_3 \times Q_4$, which are all generated by three elements, $x,y,z$ such that: \vskip4pt $SL_2(3) = \$, \vskip2pt $Q_{12} = \$, and \vskip2pt $Q_{4} \times Z_3 = \$. \vskip6pt This points out that investigating RDS in only Abelian groups will not give a full analysis of all working parameters. Nonabelian groups contain RDS that are also quite interesting. \vskip4pt A $(12,2,12,6)$ relative difference set in \underline{all three} groups is: $$R = (x^2 + x + y + xy)(1 + z) + (1 + x + y + xy)(x^2 z^2).$$ \vskip3pt The idea that one magic" formula will produce a RDS in all three groups is exciting. It suggests that all other RDS should be investigated to see if this phenomenon occurs with any other parameters. \vskip12pt \subsubsection{$(12,3,12,4)$} Alexander Pott stated, $(m,2,m,m/2)$ are the \underline{only} examples of semiregular relative difference sets in groups which are not $p$-groups: All known examples with $n \neq 2$ live in $p$-groups" \cite{Pott}, p. 103. However, we found $(12,3,12,4)$ RDS in the three following groups: $Q_6 \times Z_3$, $A_4 \times Z_3$, and $(Z_6 \times Z_2)\times Z_3$. These groups provide examples outside $p$-groups which do contain RDS. This opens the door to a search for many other RDS. Notice also that all three groups are splitting, meaning that $Z_3 = N$ in each group. \vskip7pt A $(12,3,12,4)$ RDS in $Q_6 \times Z_3 = \$ is: \hskip20pt $(1+y+x^2y+x^4y+x^5+xy)+(x^3+x^3y+x^2+x^5y)z+(x^4+x)z^2$. \vskip6pt A $(12,3,12,4)$ RDS in $A_4 \times Z_3 = \times$ is: \hskip20pt $(1+x^{2}y_{1}+xy_{1}+xy_{2}+y_{2}+x^{2})+ (y_{1}+x^{2}y_{1}y_{2}+y_{1}y_{2}+x^{2}y_{2})z+ (xy_{1}y_{2}+x)z^{2}.$ \vskip6pt A $(12,3,12,4)$ RDS in $(Z_6 \times Z_2)\times Z_3 =$ is: \hskip20pt $(1+x^2y+x^3+x^5)+(x+xy)z+(y+x^2+x^3y+x^4+x^4y+x^5y)z^2.$ \subsubsection{(12,6,12,2)} The next logical step is to attempt a lift of the previous two parameters to a $(12,6,12,2)$ RDS. In order to be eligible for such a RDS, a group $G$ of order 72 must have a normal subgroup $N$ of order six where the subgroups $H_2$ and $H_3$ of $N$, of orders two and three respectively, give factor groups corresponding to those which have $(12,3,12,4)$ and $(12,2,12,6)$ RDS. Using GAP, it was determined that the possibility of such a RDS only exists in two groups: $SL_2(3) \times Z_3$ and $Q_4 \times Z_3^2$. An exhaustive search of these groups, using GAP, would require, for each normal subgroup $N$ of order six, examining $6^{10} \approx 60$ million transversals and running a relative difference set check on each transversal. Our current program would take approximately a month of computer time to exhaust one group. Therefore, at this time, the existence of a $(12,6,12,2)$ RDS is still open. \pagebreak \begin{thebibliography}{99} \bibitem{GAP} The GAP Group, GAP --- Groups, Algorithms, and Programming, Version 4.2;2002. () \bibitem{Schmidt} B. Schmidt, Williamson Matrices and a Conjecture of Ito's, Designs, Codes, and Cryptography, Vol. 17 (1999) pp. 61-68. \bibitem{Pott} A. Pott, Finite Geometry and Character Theory, Springer-Verlag, Berlin-Heidelberg 1995. %book \bibitem{Pott94} A. Pott, A Survey on Relative Difference Sets. In: "Groups, Difference sets, and the Monster" (eds. K.T. Arasu, J. Dillon, K. Harada, S.K. Sehgal, and R. Solomon), deGruyter Verlag, Berlin-New York (1994). %paper \bibitem{Ito} N. Ito, On Hadamard Groups, J. Algebra, Vol. 168 (1994) pp. 981-987. \bibitem{Ireland} K. Ireland and M. Rosen, A Classical Intorduction to Modern Number Theory, 2nd Edition, pp. 193-199, Springer-Verlag, New York 1990. \bibitem{Lederman} W. Ledermann, Introduction to Group Characters, University Press, Cambridge 1977. \bibitem{Thomas} A. D. Thomas and G. V. Wood, Group Tables, Shiva Publishing Limited, Kent, UK 1980. \end{thebibliography}\ \end{document}