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.

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.

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 * * * * * 0where 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 157So 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.

- Can you construct a perfect difference set of size 6?
- And of size 7? (You might need a computer here!)
- Is there a perfect difference set for every possible size?

New sets for old: Shifts

*96/12/30 -
Kris Coolsaet
*