Math 2325
Project 2 (Chapter 2) - Difference Sets

The Basics

Mod[n,m]gives the remainder on division of n by m.

Mod[5, 3]

Mod[-5, 18]

The next command gives a list of  the squares of {1,2,...,m-1}modulo m

Squares[m_] := 
      Table[Mod[k^2, m], {k, 1, m - 1}]

Squares[11]

Let us  remove multiple occurences of squares; we also want to remove 0:

Squares[m_] := 
      Select[Union[
          Table[Mod[k^2, m], {k, 1, m - 1}]], #1 ≠ 
            0 &]

Squares[11]

Given a set D and a positive integer m, the next command  computes all differences of distinct elements in D modulo m

Diff[D_, m_] := 
      Do[Do[If[k ≠ l, 
            Print[D[[k]], " - ", D[[l]], " = ", 
              Mod[D[[k]] - D[[l]], m]], ], {k, 1, Length[D]}], {l, 1, 
          Length[D]}]

Diff[Squares[11], 11]

Let's list only the results. We once again want to  remove the zeroes as well:

Diff[D_, m_] := 
      Select[Flatten[
          Table[Mod[D[[k]] - D[[l]], m], {k, 1, Length[D]}, {l, 1, 
              Length[D]}]], #1 ≠ 
            0 &]

Diff[Squares[11], 11]

Finally we want to count the frequencies of each of the elements k in  {1,2,...,m-1}.

Freq[D_, m_] := 
      Table[{i, Count[Diff[D, m], i]}, {i, 1, 
          m - 1}]

Freq[Squares[11], 11]

To make the output shorter, we can just list all distinct occurring frequencies instead - if the output below contains just one element, then the set D is a difference set modulo m.

Freq[D_, m_] := 
      Union[Table[
          Count[Diff[D, m], i], {i, 1, 
            m - 1}]]

Freq[Squares[11], 11]

Finally, we print some output.

CheckDifferenceSet[D_, m_] := 
      If[Length[
            un = Union[Table[Count[Diff[D, m], i], {i, 1, m - 1}]]] == 
          1,  Print["The set ",  
          D,  " is a difference set modulo m=", m, ". (λ=", 
          un[[1]], " , k=",  
          Length[D], ")"], 
Print["The set of \
non-zero squares is NOT a difference set modulo ", 
          m, "."]
]

CheckDifferenceSet[Squares[11], 11]

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

CheckDifferenceSet[Squares[15], 15]

CheckDifferenceSet[Squares[83], 83]

The Ready-to-Run Program

The following command tells whether the non-zero squares form a difference set for the cases  m=5 to 100.

For this to work, you must have executed all commands in the previous section first.

You can produce more examples by changing the 5 and 100 to different values. Be careful, though: For larger values of m the computation might take quite a while.

\(Do[
	
      CheckDifferenceSet[Squares[m], m]
, {m, 5, 
        100}]\)

Helmut Knaust, hknaust@utep.edu.	
September 17, 2003.