IBM - Personal communication

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.

Table 1 - lengths for which modular Golomb rulers exist
marks(n) n*n-n+1 lengths for which rulers exist
2 3 3+
3 7 7+
4 13 13+
5 21 21 23+
6 31 31 35+
7 43 48+
8 57 57 63+
9 73 73 80 85+
10 91 91 107+
11 111 120 133 135+
12 133 133 156 158 159 161+
13 157 168 183 193+
14 183 183 225+
15 211 255 261? 262? 264? 265? 266? 267+

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.

Table 1a - Graham-Sloane function v[delta](n)
n 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
v[delta] 3 7 13 21 31 48 57 73 91 120 133 168 183 255 255 273 307

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.

Table 2 - lengths for which modified modular Golomb rulers exist
marks(n) n*(n-3) lengths for which rulers exist
2 -2 2+
3 0 3+
4 4 6+
5 10 11+
6 18 19+
7 28 28+
8 40 40 42+
9 54 56+
10 70 72+
11 88 96+
12 108 114 120+
13 130 147+
14 154 178 180 182+
15 180 ?

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.

Table 2a - Graham-Sloane function v[gamma](n)
n 2 3 4 5 6 7 8 9 10 11 12 13 14 15
v[gamma] 2 3 6 11 19 28 40 56 72 96 114 147 178 ?

References mentioned above.

GS - Ronald L. Graham and Neil J. A. Sloane
R. L. Graham and N. J. A. Sloane, "On additive bases and Harmonious Graphs", Siam J. Algebraic and Discrete Methods, 1(1980), p. 382-404.
S - James Singer
J. Singer, "A theorem in finite projective geometry and some applications to number theory", Transactions American Mathematical Society, 43(1938), p. 377-385.
B - R. C. Bose
R. C. Bose, "An affine analogue of Singer's Theorem", J. Ind. Math. Society, 6(1942), p. 1-15.
R - Imre Z. Ruzca
I. Z. Ruzsa, "Solving a linear equation in a set of intgers I", Acta Arithmetica, 65(1993), p. 259-282.

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Legal ]