TOPICS
Search

Golomb Ruler


GolombRulers

A Golomb ruler with n marks is a set of n distinct nonnegative integers (a_1,a_2,...,a_n), called "marks," such that the positive differences |a_i-a_j|, computed over all pairs of indices 1<=i<j<=n, are distinct.

Up to a translation, finite Sidon sets are exactly Golomb rulers.

No perfect Golomb ruler, i.e., a Golomb ruler that uniquely measures all distances up to its length, exists for five or more marks (Golomb 1972; Gardner 1983, p. 154).

Normalize an n-mark Golomb ruler by writing its marks in increasing order as 0=a_1<a_2<...<a_n. Its length is a_n. Optimality and the convention for choosing a canonical form are specified as follows.

1. The ruler is optimal if there is no other n-mark Golomb ruler with a smaller largest mark a_n.

2. The canonical form is the "smaller" of the equivalent rulers (0,a_2,...,a_n) and (0,...,a_n-a_2,a_n), where "smaller" means the first differing entry is less than the corresponding entry in the other ruler.

Thus, (0, 1, 3) is the unique optimal 3-mark Golomb ruler modulo reversal (i.e., (0, 2, 3) is considered the same ruler).

For example, the set (0, 1, 3, 7) is a 4-mark Golomb ruler since its differences are (1=1-0, 2=3-1, 3=3-0, 4=7-3, 6=7-1, 7=7-0), all of which are distinct. However, the unique optimal Golomb 4-mark ruler is (0, 1, 4, 6), which measures the distances (1, 2, 3, 4, 5, 6). As a further example, it turns out that the length of an optimal 6-mark Golomb ruler is 17. In fact, there are four optimal 6-mark Golomb rulers up to reversal, all of length 17, one of which is given by (0, 1, 4, 10, 12, 17).

Rulers may be indicated either by giving the distances at which the marks occur, e.g., (0, 1, 3, 7) in the above example, or by the differences between successive marks, which in this case would be [1,2,4].

The lengths of the optimal n-mark Golomb rulers for n=2, 3, 4, ... are 1, 3, 6, 11, 17, 25, 34, ... (OEIS A003022, Vanderschel and Garry). Although the lengths of the optimal n-mark Golomb rulers are not known for n>28, the known 21- through 28-mark rulers were proved optimal by the Golomb ruler search project between 1998 and 2022.

Proving optimality of Golomb rulers is notoriously difficult. For example, in 1967, J. P. Robinson and A. J. Bernstein found the 24-mark ruler (0, 9, 33, 37, 38, 97, 122, 129, 140, 142, 152, 191, 205, 208, 252, 278, 286, 326, 332, 353, 368, 384, 403, 425), which was verified to be optimal on Nov. 1, 2004 by a 4-year computation on distributed.net that performed an exhaustive search through 555529785505835800 rulers (distributed.net 2004). In 1984, M. D. Atkinson and A. Hassenklover found the 25-mark ruler (0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207, 214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480). A follow-up eight-year distributed.net project for the 25-mark ruler, assisted by 124387 people, announced on Oct. 25, 2008 that the 25-mark ruler was optimal.

The OGR-28 search took approximately 8.5 years and involved more than 65,000 volunteers from over 80 countries. It verified 524,091,443 search stubs at least twice independently and established that the previously known 28-mark ruler of length 585 is optimal (distributed.net 2022).

Reviews of construction methods for Golomb rulers are given by Dimitromanolakis (2002), Drakakis (2009), and Rokicki and Dogon. As noted by Rokicki and Dogon, the construction developed by Singer (1938), together with subsequent constructions of Bose (1942) and Bose and Chowla (1962-63), produces rulers that are guaranteed to be near-optimal and often appear to be optimal. With the exception of orders 7, 8, 9, 13, 15, and 16, these finite field constructions have produced all known optimal rulers (cf. Pegg 2016).

The numbers N(n) of inequivalent optimal n-mark Golomb rulers for n=2, 3, ... are 1, 1, 1, 2, 4, 5, 1, 1, 1, ... (OEIS A036501), and the number of distances in an n-mark ruler is given by the triangular number T_(n-1)=n(n-1)/2, so for n=1, 2, ..., the first few are 0, 1, 3, 6, 10, 15, ... (OEIS A000217).

The following table gives a complete list of optimal Golomb rulers for small n. A more complete table is maintained by J. B. Shearer.

nN(n)optimal rulers
21(0, 1)
31(0, 1, 3)
41(0, 1, 4, 6)
52(0, 1, 4, 9, 11), (0, 2, 7, 8, 11)
64(0, 1, 4, 10, 12, 17), (0, 1, 4, 10, 15, 17), (0, 1, 8, 12, 14, 17),
(0, 1, 8, 11, 13, 17)
75(0, 1, 4, 10, 18, 23, 25), (0, 2, 3, 10, 16, 21, 25), (0, 1, 11, 16, 19, 23, 25),
(0, 1, 7, 11, 20, 23, 25), (0, 2, 7, 13, 21, 22, 25)
81(0, 1, 4, 9, 15, 22, 32, 34)

Carter et al. (2026) proved the lower bound k^2-1.89k^(3/2) for the length of a k-mark Golomb ruler, improving the coefficient to 1.88607 when k>=483.


See also

Perfect Difference Set, Perfect Ruler, Ruler, Sidon Set, Sparse Ruler, Taylor's Condition, Weighing

Explore with Wolfram|Alpha

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.Bose, R. C. "An Affine Analogue of Singer's Theorem." J. Indian Math. Soc. 6, 1-15, 1942.Bose, R. C. and Chowla, S. "Theorems in the Additive Theory of Numbers." Comment. Math. Helvet. 37, 141-147, 1962-63.Carter, D.; O'Bryant, K.; and Tao, T. "On the Diameter and Distribution of Sidon Sets." 26 Oct 2026. https://arxiv.org/abs/2610.36207.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 315, 1996.Dewdney, A. K. "Computer Recreations." Sci. Amer. 253, 16, Dec. 1985. https://doi.org/10.1038/scientificamerican1285-16.Dewdney, A. K. "Computer Recreations." Sci. Amer. 254, 20, Mar. 1986.Dimitromanolakis, A. "Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers." Technical University of Crete. Department of Electronic and Computer Engineering. June 2002.distributed.net. "distributed.net Is Proud to Announce the Completion of OGR-24." Nov. 1, 2004. https://blogs.distributed.net/2004/11/01/10/24/nugget/.distributed.net. "Completion of OGR-28 Project." Nov. 23, 2022. https://blogs.distributed.net/2022/11/23/03/28/bovine/.distributed.net. "Project OGR." https://www.distributed.net/OGR.Drakakis, K. "A Review of the Available Construction Methods for Golomb Rulers." Adv. Math. Commun. 3, 235-250, 2009.Gardner, M. Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 153-155, 1983.Gardner, M. The Magic Numbers of Dr Matrix. Buffalo, NY: Prometheus, p. 230, 1985.Golomb, S. W. "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.Guy, R. K. "Modular Difference Sets and Error Correcting Codes." §C10 in Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, pp. 181-183, 2004.Hewgill, G. "distributed.net OGR Project." https://hewgill.com/ogr/.Kotzig, A. and Laufer, P. J. "Sum Triangles of Natural Numbers Having Minimum Top." Ars. Combin. 21, 5-13, 1986.Lam, A. W. and Sarwate, D. V. "On Optimum Time Hopping Patterns." IEEE Trans. Comm. 36, 380-382, 1988.Miller, L. "Golomb Rulers." http://www.cuug.ab.ca/~millerl/g3-records.html.Pegg, E. Jr. "Math Games: Rulers, Arrays, and Gracefulness." Nov. 15, 2004. https://www.mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html. Pegg, E. Jr. "Golomb Rulers and Fibonacci Sequences." Wolfram Demonstrations Project. 2016. https://demonstrations.wolfram.com/GolombRulersAndFibonacciSequences/. Pegg, E. Jr. "Golomb Rulers." Wolfram Demonstrations Project. 2023. https://demonstrations.wolfram.com/GolombRulers/.Pegg, E. Jr. Mathematical Games. Episode 6: "Sparse Rulers, Golomb Rulers & Difference Sets." Jul. 13, 2023. https://www.youtube.com/watch?v=6FxfRnQUVfQ.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.Rokicki, T. and Dogon, G. "Possibly Optimal Golomb Rulers Calculated for 160 to 40,000 Marks." https://cube20.org/golomb/.Shearer, J. B. "Golomb Rulers." https://web.archive.org/web/20060110160821/http://www.research.ibm.com:80/people/s/shearer/grule.html.Singer, J. "A Theorem in Finite Projective Geometry and Some Applications to Number Theory." Trans. Amer. Math. Soc. 43, 377-385, 1938.Sloane, N. J. A. and Plouffe, S. Figure M2540 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Vanderschel, D. and Garry, M. "In Search of the Optimal 20, 21, & 22 Mark Golomb Rulers." https://web.archive.org/web/20081030015301/http://members.aol.com/golomb20/.Sloane, N. J. A. Sequences A000217/M2535, A003022/M2540, A036501, and A039953 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Golomb Ruler

Cite this as:

Weisstein, Eric W. "Golomb Ruler." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GolombRuler.html

Subject classifications