New sets for old: Shifts

Write down any CDS. (In our example we use the previously encountered set {0,3,5,12} modulo 13.) On the line underneath it, write the same set but increase each number by 1. Instead of 13 just write 0. Do the same again with that new line and continue until you end up with the same line as you started with.

This is what you should get:

   0   3   5  12
   1   4   6   0
   2   5   7   1
   3   6   8   2
   4   7   9   3
   5   8  10   4
   6   9  11   5
   7  10  12   6
   8  11   0   7
   9  12   1   8
  10   0   2   9
  11   1   3  10
  12   2   4  11
(  0   3   5  12 )

If we leave out the (repeated) last line we find 13 different sets. They are called shifts of the original CDS. In general, for every CDS of size s and modulus n we may construct n different shifts.

Shifts have remarkable properties

You may use the example above to check the following properties which hold for shifts of any CDS:

Every number from 0 up to n-1 occurs in exactly s shifts.
Each of the s shifts that contain the number 0 is again a CDS.
In fact, these shifts all occur as lines in the difference table of the CDS (in reverse order).
Two different shifts may have either 0 or 1 element in common. (In the example above you will not find a disjoint pair, but this is a consequence of the fact that the CDS is perfect.)
Any pair of different numbers (in the range 0..n-1) occurs in at most one shift. (Again, when the CDS is perfect, you will not find a pair that does not occur in any shift.)

We shall not prove these properties here.

Apart from providing us new CDSs for old ones, the notion of `shifts' is also useful in providing a geometrical interpretation of cyclic difference sets as will be explained in the following pages.

Problems

Try to prove the general properties of shifts.
Construct all shifts for the CDS {0,1,3} modulo 7. Do you see any relation with the picture below?
(This is a picture of the so-called `Fano'-plane.)
Construct all shifts for the CDS {0,1,3} but now modulo 8. (By the way, to prove that this is indeed a CDS you only need to verify the shift properties. Note that this CDS is not perfect.)
Can you make a corresponding picture for that last example?

Is this geometry?

96/12/30 - Kris Coolsaet