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.
96/12/30 - Kris Coolsaet