Cyclic difference sets

And now for some mathematics:

A cyclic difference set (CDS) modulo n is a set of s positive numbers {a1=0,a2,a3,...,as} less than n, with the property that all differences ai-aj modulo n for i not equal to j, are different. The number n is called the modulus of the CDS and s is the size of the CDS. The set itself is usually written as 

    0 a1 a2 ... as (n)
where 0 < a1 < a2 < ... < as.

Sorry, could you repeat that?

OK, apart from some terminology, we have not really encountered anything new. Consider the 21-bead necklace from the previous page, written as a numerical sequence: 
    0   5   6   9  19  (21)
Here, the cyclic difference set is {0,5,6,9,19} ({a1,...,a5} in the definition), the modulus is 21 (n in the definition) and the size is 5 (s). By the difference of two numbers a and b `modulo 21' we mean a-b if a is not less than b, or else a-b+21. Hence, the requirement that no two differences `modulo 21' are the same, means that all non-diagonal elements in the difference table must be different.

Therefore, mathematically speaking, cyclic difference sets are the same as weird necklaces, whichever terminology you prefer.

Short necklaces

As you may have noticed while trying to string your own weird necklaces, it is fairly easy to construct cyclic difference sets with large modulus and small size. For example: 
    0  1  10  100  1000  10000 ... 100000000000  (1000000000000)
The trick lies in constructing large sets with small modulus. We may ask the question again: is there a weird necklace with 5 yellow beads and less than 16 black beads? Or in other words, is there a cyclic difference sets of size 5 with modulus less than 21?

To answer this question, we must have a closer look at the difference table. For size 5, this table has the following form: 

   0   *   *   *   *  (n)
   *   0   *   *   *
   *   *   0   *   *
   *   *   *   0   *
   *   *   *   *   0
where the various stars correspond to different positive numbers. Now, the picture above contains 20 stars (count them!) and each star must hold a number greater than 0 and less than the modulus. In other words the modulus must be at least one more than the number of stars, in this case 20+1=21. The total number of beads in a necklace with 5 yellow beads must therefore be at least 21.

This reasoning can be repeated for any size s. Indeed, the number of stars is s times s-1 (there are s rows of s-1 stars) and hence the modulus n is at least s^2-s+1. (We write s^2 to denote s squared.) The following table lists the various values of this number for given sizes s: 

   s    |   4   5   6   7   8   9  10  11  12  13
-------------------------------------------------
s^2-s+1 |  13  21  31  43  57  73  91 111 133 157
So you see that our 13-bead necklace is the shortest possible for size 4 as well.

A CDS of size s for which the modulus is exactly s^2-s+1 (and hence the smallest possible) is called a perfect difference set. It has the added property that every number between 0 and the modulus can be found in the corresponding difference table.

Problems

New sets for old: Shifts

96/12/30 - Kris Coolsaet