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.

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.

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.

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.

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 ]