A Golomb ruler is a set of Nonnegative integers such that all pairwise Positive differences are distinct. The optimum Golomb ruler with marks is the Golomb ruler having the smallest possible maximum element (``length''). The set (0, 1, 3, 7) is an order four Golomb ruler since its differences are (, , , , , ), all of which are distinct. However, the optimum 4-mark Golomb ruler is (0, 1, 4, 6), which measures the distances (1, 2, 3, 4, 5, 6) (and is therefore also a Perfect Ruler).
The lengths of the optimal -mark Golomb rulers for , 3, 4, ... are 1, 3, 6, 11, 17, 25, 34, ... (Sloane's A003022, Vanderschel and Garry). The lengths of the optimal -mark Golomb rulers are not known for .
See also Perfect Difference Set, Perfect Ruler, Ruler, Taylor's Condition, Weighings
References
Atkinson, M. D.; Santoro, N.; and Urrutia, J. ``Integer Sets with Distinct Sums and Differences and Carrier Frequency Assignments for
Nonlinear Repeaters.'' IEEE Trans. Comm. 34, 614-617, 1986.
Colbourn, C. J. and Dinitz, J. H. (Eds.) CRC Handbook of Combinatorial Designs.
Boca Raton, FL: CRC Press, p. 315, 1996.
Guy, R. K. ``Modular Difference Sets and Error Correcting Codes.'' §C10 in
Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 118-121, 1994.
Lam, A. W. and D. V. Sarwate, D. V. ``On Optimum Time Hopping Patterns.'' IEEE Trans. Comm. 36, 380-382, 1988.
Robinson, J. P. and Bernstein, A. J. ``A Class of Binary Recurrent Codes with Limited Error Propagation.'' IEEE Trans. Inform. Th.
13, 106-113, 1967.
Sloane, N. J. A. Sequence
A003022/M2540
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.
Vanderschel, D. and Garry, M. ``In Search of the Optimal 20 & 21 Mark Golomb Rulers.''
http://members.aol.com/golomb20/.
© 1996-9 Eric W. Weisstein