New sets for old: multipliers

If you were for instance using CDSs to construct optimal Golomb rulers - more about this later - you would not always be satisfied with finding a single CDS for a given modulus and size. For that reason, we will spend some time explaining how you can generate new CDSs from a given CDS. And as an offspin of this method we shall even discover a new method of generating CDSs which doesn't require an understanding of geometries or linear recurrences (and which consequently does not always work).

Many pages ago, we have seen that some of the shifts of a CDS yield a different CDS (with same size and modulus). For example, for the CDS {0,10,12,17,18} modulo 21, the following shifts yield a new CDS:

    0   10   12   17   18  (21)          +  0
    0    2    7    8   11  (21)          + 11
    0    5    6    9   19  (21)          +  9
    0    1    4   14   16  (21)          +  4
    0    3   13   15   20  (21)          +  3

We may reformulate this by saying that a new CDS can be generated from an old CDS by adding the same (appropriately chosen) number x to every element of the CDS, using modular arithmetic with modulus n. The `appropriate' numbers x are of the form x = -y (n), where y is any element in the original CDS. We have written these numbers in the column on the right.

A different way to generate new CDSs from old CDSs is by multiplying every element of the CDS with an appropriate number z (modulo n). In the example above, this yields

    0   10   12   17   18  (21)          *  1
    0    3   13   15   20  (21)          *  2
    0    5    6    9   19  (21)          *  4
    0    1    6    8   18  (21)          *  5
    0   10   12   17   18  (21)          *  8
    0    2   12   15   16  (21)          * 10
    0    5    6    9   19  (21)		 * 11
    0    3    4    9   11  (21)          * 13
    0    3   13   15   20  (21)          * 16
    0    2   12   15   16  (21)          * 17
    0    1    6    8   18  (21)          * 19 
    0    3    4    9   11  (21)          * 20

The `appropriate' numbers this time are all numbers z in the range 1..n-1 which have no divisor in common with n (except 1). For example, the value z=14 does not yield a correct CDS, for z=14 and n=21 are both divisible by 7.

There are some observations we can make about the CDSs generated so far:

Sometimes two different values of z yield the same CDS, as with z=10 and z=17 in the example above.
In particular, sometimes a value of z>1 yields the original CDS again. (In this case, z=8).
Two different values of z may yield two different CDSs which are shifts of each other. In our example, the CDSs for z=1,2,4,8,11 and 16 are shifts of the original CDS, while the other six results are all shifts of another CDS.

This method will not always generate a tremendous amount of new CDSs, but you may always expect at least one new CDS which is not a shift of the original one: use z=-1 (i.e., z=n-1, for we are working modulo n). In a lot of cases there will be more.

[ Note that applying this `multiplication' method to a shift of the original CDS will only yield shifts of the results you obtained with the unshifted CDS. ]

Multipliers

A value of z which transforms a CDS into itself or into one of its own shifts is called a multiplier of that CDS. For example, 1,2,4,8,11 and 16 are multipliers for the CDS {0,10,12,17,18} modulo 21. Multipliers for some other CDSs are listed below:

CDS                                          Multipliers
-----------------------------------------------------------
   0   1   8  10 (13)                        1,3,9
   0   1   9  13 (15)                        1,2,4,8 
   0  10  12  17  18 (21)                    1,2,4,8,11,16
   0   3   4  17  19 (24)                    1,5
   0   2  21  30  33  43  44 (48)            1,7
   0  24  30  32  37  49  52  53 (63)        1,2,4,8,16,32
   0   5  18  24  26  27  41  69  73 (80)    1,3,9,27  
------------------------------------------------------------

As you notice, all CDSs we have constructed so far have one or more multipliers different from 1.

Furthermore, if a CDS has a multiplier z, then it will often have a shift which is mapped to itself by the corresponding multiplication. We call this a special shift. The following table lists a special shift for each of the CDSs in the example above:

CDS                                          Multipliers
-----------------------------------------------------------
   0   2   5   6 (13)                        1,3,9
   7  11  13  14 (15)			     1,2,4,8
   0   1   4  14  16 (21)                    1,4,16
   0   2   7  10  11 (24)                    1,5
   0  10  17  19  22  23  37 (48)            1,7
  13  19  21  26  38  41  42  52 (63)        1,2,4,8,16,32
   0  14  42  46  53  58  71  77  79 (80)    1,3,9,27  
------------------------------------------------------------

Note that a special shift does not always contain the element zero. Moreover, a special shift for a given multiplier need not necessarily exist: in the third case no shift exists for the multipliers 2,8 or 11.

Special shifts have some interesting properties: if you take any element e of that shift, then the elements e*z, e*z*z, ... must also belong to that shift. Eventually, some e*z*z*...*z will again be equal to e (don't forget to use modular arithmetic) and then the sequence will repeat. We shall call such a sequence a `run' with multiplier z. Special shifts can always be split into disjoint runs, and we have done this for the special shifts above, in the table below:

   0*3= 0 | 2*3= 6   6*3= 2   5*3= 2          (13)      2 runs 
   7*2=14  14*2=13  13*2=11  11*2= 7          (14)      1 run
   0*4= 0 |14*4=14 | 1*4= 4   4*4=16  16*4= 1 (21)      3 runs
   0*5= 0 | 2*5=10  10*5= 2 | 7*5=11  11*5= 7 (24)      3 runs
   0*7= 0 |10*7=22  22*7=10 |19*7=37  37*7=19
          |17*7=23  23*7=17                   (48)      4 runs
  13*2=26  26*2=52  52*2=41  41*2=19  19*2=38
           38*2=13                            (63)      1 run
   0*3= 0 |14*3=42  42*3=46  46*3=58  58*3=14
          |53*3=79  79*3=77  77*3=71  71*3=53 (80)      3 runs

Using `runs' to construct CDSs

This property can now be used in reverse as a construction method for CDSs. Suppose we are looking for a perfect difference set of size 9 and modulus 73. This CDS will most probably have some (as yet unknown) multiplier z for which there is a special shift. This special shift then consists of runs with multiplier z. If we knew z, we could construct all possible runs of z and then try to glue them together into a CDS. For instance, let us try z=3. The possible runs with multiplier 3 are

 0*3= 3
 1*3= 3  3*3= 9  9*3=27 27*3= 8  8*3=24 24*3=72 72*3=70 70*3=64 64*3=46
  46*3=67 67*3=49 49*3=1
 2*3= 6  6*3=18 18*3=54 54*3=16 16*3=48 48*3=71 71*3=67 67*3=55 55*3=19
  19*3=57 57*3=25 25*3=2
 4*3=12 12*3=36 36*3=35 35*3=32 32*3=23 23*3=69 69*3=61 61*3=37 37*3=38
  38*3=41 41*3=50 50*3=4
 5*3=15 15*3=45 45*3=62 62*3=40 40*3=47 47*3=68 68*3=58 58*3=28 28*3=11
  11*3=33 33*3=26 26*3=5
10*3=30 30*3=17 17*3=51 51*3= 7  7*3=21 21*3=63 63*3=43 43*3=56 56*3=22
  22*3=66 66*3=52 52*3=10
20*3=60 60*3=34 34*3=29 29*3=14 14*3=42 42*3=53 53*3=13 13*3=39 39*3=44
  44*3=59 59*3=31 31*3=20

There is one run of length 1 and 6 runs of length 12. Clearly these runs are too long for a CDS of size 9, hence we must try a different z, say 2. We list only a single run in this case, for that will appear to be sufficient:

   1   2   4   8   16   32   64   55   37

This is a run of length 9, which is not only small enough to be part of a special shift, but is exactly the maximal size. This run might therefore itself be a special shift of a perfect CDS. If that is the case, the set {0,1,3,7,15,31,36,54,63} with modulus 73 could be the CDS we are looking for, and it is easily verified that this is indeed the case.

True, this set has been constructed in a somewhat slapdash manner, but the alternative - using linear recurrences of degree 9 - would certainly not have been easier.

Golomb Rulers

97/01/10 - Kris Coolsaet