SINGER DIFFERENCE SETS



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin and Jennifer Seberry, 7.11.2014


Definition 1. Let D = {d1, d2, ... , dk} be a subset of the integers 0, 1, 2, Е , ν Ц 1. If the collection Δ = {di Ц dj: i, j, 1 ... k, i not equal to j} contains each element 1, 2, ... , ν Ц 1 exactly λ times D will be called a (ν, k, λ) difference set.

This is said to be additive notation. Equivalently, (ν, k, λ) difference set in a multiplicative group G of order ν is kЦsubset D of G such, that every element g≠1 of G has exactly λ representations g=d1d2Ц1 with d1, d2 from G.

ν is called the order of the difference set.

We note that for every (ν, k, λ) difference set there is a complementary (ν, νЦk, νЦ2k+ λ) difference set made by choosing the subset of 1, 2, ... , ν not in D.

Difference sets due to James Singer (1938, [1]) appeared first. Marshall Hall [2] wrote an extensive survey in 1956.

The incidence system with points the elements of G and blocks the translates of D in G; constitutes a symmetric balanced incomplete block design which is equivalent to the classical geometric design.

Definition 2. Let D = {d1, d2, ... , dk} be a difference set on the integers 1, 2, ... , ν. Then the ν×ν, matrix B = (bij) is said to be the incidence matrix of D if bij = 1 for j Ц i in D and 0 is j Ц i is not in D.

Example 1. Let D be the subset {1, 3, 4, 5, 9} of the integers 0, 1, 2, ... , 10. Hence we take all the differences modulo 11. Then Δ contains 1 Ц 3 = Ц2 = 9 ; 1 Ц 4 = Ц3 = 8; 1 Ц 5 = Ц4 = 7; 1 Ц 9 = Ц8 = 3; 3 Ц 1 = 2; 3 Ц 4 = Ц1 = 10; 3 Ц 5 = Ц2 = 9; 3 Ц 9 = Ц6 = 5; 4 Ц 1 = 3; 4 Ц 3 =1; 4 Ц 5 = Ц1 = 10; 4 Ц 9 = Ц5 = 6; 5 Ц 1 = 4; 5 Ц 3 = 2; 5 Ц 4 = 1; 9 Ц 1 = 8; 9 Ц 3 = 6 = 5; 9 Ц 4 = 5; 9 Ц 5 = 4; which is each non-zero integer 0, 1, 2, ..., 10 exactly twice.

The incidence matrix of D is B = circ(0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0).


Definition 3. Singer-type difference sets have parameters

(ν, k, λ) = ((qm+1Ц1)/(qЦ1), (qmЦ1)/(qЦ1), (qmЦ1Ц1)/(qЦ1))


These parameters are now usually called Singer parameters, especially in the context of difference sets.

Definition 4. A difference set with parameters (ν, k, λ) = (4tЦ1, 2tЦ1, tЦ1) will be called an Hadamard difference set.

It is interesting to note that the Reverend Thomas P. Kirkman had found many of these difference sets by 1857 [3] (see [4] for a wonderful testament to this man whose mathematical prowess is often underrated); and it seems likely that Galois would have observed these sequence and difference set properties while constructing his finite fields as extensions of GF(p) in the early 1830s (J.F. Dillon and Hans Dobbertin [5]).

Equivalently, for any prime power q = ps the collineation group of the classical design of points and hyperplanes in PG(m; q) contains a (regular) cyclic subgroup G acting sharply transitively on its points (and hyperplanes) and that the subset D of G indexing the points of any particular hyperplane is a difference set in the sense that (using additive notation for the group operation) the equation xy = g has (qmЦ1Ц1)/(qЦ1) solutions in D for all non-identity elements g in G.


CM(57;0.2297) for PG(7,2) (57,8,1) and CM(156;0.3) for PG(5,3) (156,31,6)


Coloured


1. J. Singer, A theorem in finite projectiνe geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938) 377Ц385.
2. M. Hall, Jr, A survey of difference sets, Proc Amer. Math. Soc. 7 (1956) 975-986.
3. T.P. Kirkman, On the perfect r-partitions of r2Цr+1, Trans. Hist. Soc. Lancashire Cheshire 9. (1856Ц7) 127Ц142.
4. B.C. Berndt, R.J. Eνans, K.S. Williams, Gauss and Jacobi Sums, Wiley, New York, 1988.
5. J.F. Dillon, and Hans Dobbertinb. New cyclic difference sets with Singer parameters. Finite Fields and Their Applications 10 (2004) 342Ц389.

Rambler's Top100