Difference-set(2)

(update)

Let $G$ be a group of order $v$, and let $D$ be a $k$-subset of $G$, such that the list of quotients $d e ^ { - 1 }$ with $d , e \in D$ contains each element $g \neq 1$ exactly $\lambda$ times. Then $D$ is called a $( v , k , \lambda )$-difference set of order $n = k - \lambda$ in $G$. Up to now (1998), only the case of Abelian difference sets (i.e., $G$ is Abelian, cf. also Abelian difference set) has led to a satisfactory theory. The special case of cyclic difference sets is the one considered in Difference set (Vol. 3). For an extensive discussion of the theory of Abelian difference sets, see also [a1], Chap. VI.

The known families of difference sets can be subdivided into three classes:

difference sets with Singer parameters;

cyclotomic difference sets; and

difference sets with $( v , n ) > 1$.

The difference sets with Singer parameters

\begin{equation*} ( v , k , \lambda , n ) = \left( \frac { q ^ { d + 1 } - 1 } { q - 1 } , \frac { q ^ { d } - 1 } { q - 1 } , \frac { q ^ { d - 1 } - 1 } { q - 1 } , q ^ { d - 1 } \right) , \end{equation*}

where $q$ is a prime power and $d$ a positive integer, include the classical Singer difference sets associated with the symmetric design formed by the points and hyperplanes of the projective space $P G ( d , q )$, the Gordon–Mills–Welch series and several infinite series for $q = 2$, among them certain examples constructed from hyper-ovals (cf. also Oval) in Desarguesian projective planes of even order; see [a1], Sect. VI.17, and [a2]. The cyclotomic difference sets comprise the Paley difference sets, the families using higher-order residues and also the twin prime power series, see [a1], Sect. VI.8. The families of difference sets with $( v , n ) > 1$ are the Hadamard difference sets, the McFarland difference sets, the Spence difference sets with parameters

\begin{equation*} ( v , k , \lambda , n ) = \end{equation*}

\begin{equation*} = \left( 3 ^ { d + 1} \frac { 3 ^ { d + 1 } - 1 } { 2 } , 3 ^ { d } \frac { 3 ^ { d + 1 } + 1 } { 2 } , 3 ^ { d } \frac { 3 ^ { d } + 1 } { 2 } , 3 ^ { 2 d } \right), \end{equation*}

where $d$ is any positive integer, the Davis–Jedwab difference sets, with parameters

\begin{equation*} ( v , k , \lambda , n ) = \end{equation*}

\begin{equation*} = \left( 2 ^ { 2 t + 2 } \frac { 2 ^ { 2 t } - 1 } { 3 } , 2 ^ { 2 t - 1 } \frac { 2 ^ { 2 t + 1 } + 1 } { 3 } , 2 ^ { 2 t - 1 } \frac { 2 ^ { 2 t - 1 } + 1 } { 3 } , 2 ^ { 4 t - 2 } \right), \end{equation*}

where $t > 1$ is a positive integer, and the Chen difference sets, with parameters

\begin{equation*} ( v , k , \lambda , n ) = \end{equation*}

\begin{equation*} = \left( 4 q ^ { 2 t } \frac { q ^ { 2 t } - 1 } { q ^ { 2 } - 1 } , q ^ { 2 t - 1 } \left[ \frac { 2 ( q ^ { 2 t } - 1 ) } { q + 1 } + 1 \right] , q ^ { 2 t - 1 } ( q - 1 ) \frac { q ^ { 2 t - 1 } + 1 } { q + 1 } , q ^ { 4 t - 2 } \right), \end{equation*}

where $q = p ^ { t }$, $p$ is a prime number and $t$ is a positive integer; these were previously called generalized Hadamard difference sets and are known to exist whenever $q$ is a power of $2$ or $3$ or the square of an odd prime power; see [a1], Sect. VI.9–12, for the construction of all these series.

The construction methods for the three general classes of difference sets are completely different: The Singer difference sets are cyclic and can be obtained from the action of a cyclic group of linear transformations on the one-dimensional subspaces of a finite field (viewed as a vector space over a suitable subfield), while the Gordon–Mills–Welch series is a "twisted" version of the Singer series and many of the remaining families with Singer parameters can be obtained from certain polynomials. Cyclotomic difference sets live in elementary Abelian groups (or the direct product of two such groups) and are unions of cosets of multiplicative subgroups of finite fields. The class of difference sets with $( v , n ) > 1$ is by far the richest; [a4] shows that all these difference sets are in fact very similar. [a4] also contains a recursive construction which covers all Abelian groups known to contain a difference set with $( v , n ) > 1$ (a modification is needed to include Chen's series, see [a1]). The best way to describe their construction is in terms of characters (cf. also Character of a group). The difference set is constructed from building blocks, smaller pieces which are in some sense orthogonal to each other with respect to the character group. This is based on the fact that the difference set condition can be translated into an equation in the integral group ring ${\bf Z} G$; applying complex characters to the group ring element associated with $D$, this translates into the condition that every non-trivial character yields a character sum of absolute value $\sqrt { n }$; see [a1], Sect. VI.3. These character sums actually lie in the ring $\mathbf{Z} [ \zeta _ { e } ]$ of algebraic integers in the cyclotomic field ${\bf Q} [ \zeta _ { { e } } ]$ (cf. also Cyclotomic polynomials), where $e$ denotes the exponent of $G$ (cf. Exponent of a group) and $\zeta_{e}$ is a primitive $e$th root of unity. This fact also allows the application of algebraic number theory (cf. also Algebraic number), which leads to strong non-existence results. Important progress with this approach was recently obtained by B. Schmidt [a8], see also [a1], Sect. VI.15–16. In particular, Schmidt obtained strong evidence for the validity of the long-standing circulant Hadamard matrix conjecture, which states the non-existence of a circulant Hadamard matrix of order $> 4$ and is equivalent to the perfect sequence conjecture; this also implies very strong evidence for the Barker sequence conjecture, which states the non-existence of a Barker sequence of length $> 13$.

Cyclic difference sets are equivalent to binary periodic sequences with a $2$-level autocorrelation function; that is, the periodic autocorrelation coefficients take on only one non-trivial value $\gamma$. Examples with particularly nice correlation properties (for instance, $\gamma$ should be small in absolute value) have important applications in the engineering sciences, see [a6], [a7]. Some generalizations, e.g. Abelian relative difference sets, also yield interesting sequences, see [a6]. Similarly, difference sets in Abelian groups of rank $d$ (cf. also Rank of a group) correspond to periodic $d$-dimensional arrays, which are likewise important in the engineering sciences, see [a7].

In recent years (1998), some progress regarding non-Abelian difference sets was obtained. Non-existence results follow from applying group representations, see e.g. [a5]. There are also some interesting constructions, see e.g. [a3].

References

[a1]	T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1999) (Edition: Second)
[a2]	J.F. Dillon, H. Dobbertin, "Cyclic difference sets with Singer parameters" To appear
[a3]	J.A. Davis, J.E. Iiams, "Hadamard difference sets in nonabelian $2$-groups with high exponent" J. Algebra , 199 (1998) pp. 62–87
[a4]	J.A. Davis, J. Jedwab, "A unifying construction of difference sets" J. Combin. Th. A , 80 (1997) pp. 13–78
[a5]	J.E. Iiams, "On difference sets in groups of order $4 p ^ { 2 }$" J. Combin. Th. A , 72 (1995) pp. 256–276
[a6]	D. Jungnickel, A. Pott, "Perfect and almost perfect sequences" Discr. Appl. Math. (to appear)
[a7]	H.D. Lüke, "Korrelationssignale" , Springer (1992)
[a8]	B. Schmidt, "Cyclotomic integers and finite geometry" J. Amer. Math. Soc. (to appear)