Golomb rulers


For the last page in this text we shall spend some more time on the concept that was the reason for writing these pages in the first place: Golomb rulers.

A Golomb ruler is a set of positive integers, containing zero, so that no two differences between any pair of these numbers are the same. The elements of this set are often called `marks' and the largest integer in the set is called the `length' of the ruler. For example, the following set of integers is a Golomb ruler of length 45 with 9 marks:

   0   2  10  24  25  29  36  42  45
To check whether a given set is a Golomb ruler we may use a technique very similar to checking whether a set is a CDS: we construct a difference table and check whether all elements of that table are different. For Golomb rulers we only need the top half of the table:
   0   2  10  24  25  29  36  42  45
       0   8  22  23  27  34  40  43
           0  14  15  19  26  32  35
               0   1   5  12  18  21
                   0   4  11  17  20
                       0   7  13  16
                           0   6   9
                               0   3
                                   0
In general, Golomb rulers are easily found. However, we want to find Golomb rulers where the marks are as close together as possible. More specifically, we want to find the shortest possible ruler for a given number of marks. Such a ruler is called optimal. Although a length of 45 is pretty good for a ruler with nine marks, the optimal ruler for this number of marks has length 44. More information on optimal Golomb rulers can be found on the Golomb ruler homepage.

Golomb rulers and CDSs

As you probably gathered from the definition, Golomb rulers have a lot in common with cyclic difference sets. In fact, it is easily proved that any Golomb ruler of length L is a CDS when we choose a modulus n larger than two times L - and sometimes a smaller modulus works as well.

Conversely, we may make any CDS into a Golomb ruler by just ignoring the modulus. The example above was constructed in that way: I started with a perfect difference set of modulus 73.

So, how do we construct short Golomb rulers from a given CDS? Well, we simply generate all shifts of that CDS and all `multiples' (and their shifts) - as was explained on the previous page. This gives us a lot of different Golomb rulers, of which we simply choose the shortest. As an example, take the perfect CDS {0,1,6,15,22,26,45,55} with modulus 57. Using shifts and multiplication we may generate 96 different CDSs (and hence 96 different Golomb rulers). In this list there are two rulers of length 35:

   0   4   5  17  19  25  28  35
   0   7  10  16  18  30  31  35
Again, these are not optimal: the optimal length in this case is 34.

There are other ways to construct short Golomb rulers: construct a slightly larger ruler and remove the larger marks. For example, using the CDS {0,1,3,7,15,31,36,54,63} with modulus 73 we may construct 72 different Golomb rulers with 9 marks. Amongst them are the following two:

   0   2   5   9  15  23  34  35  51
   0   1  12  20  26  30  33  35  57
If we remove the last marker from both rulers we get two pretty short rulers with 8 marks which are different from the ones we found before.

97/01/10 - Kris Coolsaet