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:

• A construction due to Singer ( S ) shows for every prime power p there exists a modular Golomb ruler with p+1 marks mod p**2+p+1. These are better known as perfect difference sets. It is an open problem whether they can exist when p is not a prime power.
• A construction due to Bose ( B ) shows for every prime power p there exists a modular Golomb ruler with p marks mod p**2-1.
• A third construction ( R ) shows for every prime p there exists a modular Golomb ruler with p-1 marks mod p**2 - p.

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 ]