This web page is devoted to modular Golomb rulers and the related functions defined by Graham and Sloane ( GS ).
A modular Golomb ruler with n marks mod k is a set of n residues a1, ..., ak such that the differences ai-aj (i != j) are all distinct mod k. Generally we are interested in dense modular Golomb rulers, ie for a fixed number of marks n we want k to be as small as possible. Simple counting shows k > = n*n-n+1.
There are several good constructions known for modular Golomb rulers:
For large p these constructions appear to be much better than typical rulers not based on some algebraic property. For example for n=13 marks there are rulers mod k=168 (Bose construction with p=13) and mod k=183 (Singer construction with p=13 and a mark deleted), but no examples for any other value of k < 193. However if k is large enough for fixed n there will always be rulers. For example for n=13 there are rulers for all k > = 193. The table below lists for small n the values of k for which rulers exist.
|marks(n)||n*n-n+1||lengths for which rulers exist|
Graham and Sloane ( GS ) defined a function v[delta](n) which is equivalent to asking for any n what is the smallest value of k for which a modular Golomb ruler exists. For small n these values can be read off from table 1 above.
Graham and Sloane ( GS ) also define a function v[gamma](n) which is based on a variant of the modular Golomb ruler problem which is equivalent to allowing ai-aj=aj-ak but otherwise requiring the differences to be distinct. Again we want the ruler to be as dense as possible. A somewhat more complicated counting argument shows k >= n*(n-3). I know of no algebraic constructions which take advantage of the weaker requirement to improve the three constructions above. I suspect for large n these constructions will still be best. However for small n this is not the case, the best rulers don't appear to have any nice structure. The equivalent of tables 1 and 1a appear below.
|marks(n)||n*(n-3)||lengths for which rulers exist|
Graham and Sloane ( GS ) also defined a function v[gamma](n) which is equivalent to asking for any n what is the smallest value of k for which a modified modular Golomb ruler exists. For small n these values can be read off from table 2 above.
References mentioned above.
IBM Research home page |
James B. Shearer's home page |
[ IBM home page | Order | Search | Contact IBM | Legal ]