Math 2325
(Chapter 2) - Cyclic Difference Sets

Note: Be sure to run the following series of commands first, before anything else!

Squares[m_] := 
        Drop[Union[Mod[#^2, m] &  /@  Range[m]], 
          1];

GenDiff[D_, m_] := Mod[Outer[Subtract, D, D], m];
VerticalLine[n_] := Table["|", {n}];
HorizontalLine[n_] := Table["--", {n}];
PadMatrix[corner_, top_, left_, body_] := 
        Transpose[
          Prepend[Transpose[Prepend[body, top]], 
            Prepend[left, corner]]];
GenDiffTable[D_, m_] := 
        MatrixForm[
          PadMatrix["-", Prepend[D, "|"], Prepend[D, "--"], 
            PadMatrix["+", HorizontalLine[Length[D]], 
              VerticalLine[Length[D]], GenDiff[D, m]]]];
DiffTable[m_] := 
        GenDiffTable[Squares[m], m];

RawFreq[S_, n_] := Count[S, #] &  /@  Range[n];
RawFreqTable[S_, n_] := {Range[n], RawFreq[S, n]};
FreqTable[S_, n_] := MatrixForm[RawFreqTable[S, n]];
FreqLongTable[S_, n_] := 
        MatrixForm[Transpose[RawFreqTable[S, n]]];
GenDiffFreqTable[D_, m_] := 
        FreqTable[Flatten[GenDiff[D, m]], m - 1];
GenDiffFreqLongTable[D_, m_] := 
        FreqLongTable[Flatten[GenDiff[D, m]], m - 1];
DiffFreqTable[m_] := GenDiffFreqTable[Squares[m], m];
DiffFreqLongTable[m_] := 
        GenDiffFreqLongTable[Squares[m], m];

GenDiffFreq[D_, m_] := 
        Union[RawFreq[Flatten[GenDiff[D, m]], m - 1]];
DiffFreq[m_] := GenDiffFreq[Squares[m], m];

Examples with squares

m=7 (highly annotated)

First, we find the (non-zero)squares (mod 7), to be used as the our possible cyclic difference set.  Note that (1^2)=1, (2^2) = 4,  (3^2) = 9= 2 (mod 7), (4^2) = 16  =  2 (mod 7),  
      (5^2) = 25  =  4 (mod 7),  
      and (6^2) = 36  =  1 (mod 7).

Squares[7]

Next, we compute all the possible differences among this set.  Note , for instance, that the entry in the middle row, right column is 2-4 = -2 =5 (mod 7).

DiffTable[7]

Something nice about the set {1,2,4} (mod 7) is that in the above difference table, every non-zero entry occurs the same number of times!  It's easy to see this in this small case from the above table, but as the numbers get larger, it will be nice to have a program that checks the number of occurrences of each entry.  The below program verifies that every number from 1 through 6 occurs exactly once.

DiffFreqTable[7]

When the numbers get larger, it may be handy to list this table vertically instead of horizontally:

DiffFreqLongTable[7]

Another quick check, handy as the numbers get larger, is to simply list all the frequencies in the above table.  If there is only one frequency, we have a cyclic difference set, and λ is simply equal to this unique frequency.  Below, this shows that λ=1 here.

DiffFreq[7]

Also, we can compute k, the number of elements in the cyclic difference set, as below.

Length[Squares[7]]

Exercise 11

m=5

Squares[5]

DiffTable[5]

DiffFreqTable[5]

DiffFreq[5]

m=6

Squares[6]

DiffTable[6]

DiffFreqTable[6]

DiffFreq[6]

m=15

Squares[15]

DiffTable[15]

DiffFreqTable[15]

DiffFreq[15]

Bigger examples

m=45

DiffFreq[45]

This shows very quickly that the square (mod  m=45) do not form a cyclic difference set. We still might want to run our programs to see why not:

DiffTable[45]

DiffFreqLongTable[45]

m=19

DiffFreq[19]

DiffTable[19]

DiffFreqTable[19]

Squares[19]

Length[Squares[19]]

More general difference sets

The Scientific American example

GenDiffTable[{1, 2, 3, 5, 6, 9, 11}, 15]

GenDiffFreqTable[{1, 2, 3, 5, 6, 9, 11}, 15]

Another example

This example shows that we can construct cyclic difference sets even when k does not equal (m-1)/2

GenDiffTable[{1, 2, 3, 5}, 7]

GenDiffFreqTable[{1, 2, 3, 5}, 7]

Art Duval, artduval@math.utep.edu
November 6, 2004