# The Enigmatic Golomb Ruler: A Marvel in Measurement

Written on

## Chapter 1: Introduction to Golomb Rulers

The Golomb ruler stands as a captivating and sophisticated combinatorial structure, boasting numerous practical applications in various domains.

“Measure what is measurable, and make measurable what is not so.”

— Galileo Galilei (1564–1642)

Upon first encountering the concept of the Golomb ruler, I was reminded of the golem, a legendary figure from Jewish folklore, imbued with the enigmatic power of life. Similarly, the Golomb ruler possesses its own intriguing features and capabilities.

### The Ruler

Take, for instance, a conventional 12-inch ruler. While it serves its purpose, it lacks mathematical efficiency. To illustrate, there are 12 distinct methods to measure a distance of one inch, and 11 for two inches, and so forth.

Now, imagine if you needed to purchase a ruler, with the cost determined by the number of markings it has—each mark priced at a staggering 15 million dollars. This scenario would lead you to seek the fewest number of markings possible.

In the early 1950s, Wallace C. Babcock was addressing intermodulation interference (IMI) at Bell Labs. This phenomenon arises when multiple signals merge, unintentionally generating additional frequencies that can compromise communication system performance. Babcock discovered that positioning signals at distinct intervals could mitigate this interference.

In 1956, mathematician Solomon Golomb joined the Jet Propulsion Laboratory and engaged in advanced communications research. His significant contributions included pioneering work on shift register sequences, crucial for error detection and correction in digital communication.

Golomb became aware of Babcock’s approach to reducing intermodulation interference and recognized it could be conceptualized as a ruler with minimal markings. Specifically, a Golomb ruler is marked using a set of integers

A = {a₀, a₁, ..., aₖ}, where a₀ < a₁ < ... < aₖ,

and it maintains the property that the distance between any two marks is unique.

For example, a 4-mark Golomb ruler would illustrate this concept.

Typically, the initial mark of a Golomb ruler is designated as zero, although this is not a strict requirement—Golomb rulers retain their essential structure even when translated. A horizontal reflection of a Golomb ruler is also considered a trivial variation.

Terminology includes:

- The number of marks is referred to as the size (or “order”) of the ruler.
- The furthest mark indicates the ruler's length.
- An optimal Golomb ruler (OGR) is one for which no shorter ruler of the same size exists.

The example above has a length of 6 and, with only 4 marks, can measure every distance from 1 to 6, qualifying it as a perfect ruler. Only four distinct perfect rulers exist: {0}, {0, 1}, {0, 1, 3}, and {0, 1, 4, 6}, with {0} generally included for completeness.

### The Mystery

While constructing a Golomb ruler can be straightforward, identifying optimal rulers is a complex task. Optimal rulers have only been discovered and verified for sizes up to 28. Below are the first ten:

The intricacies involved in locating optimal Golomb rulers remain largely unknown and are generally considered NP-hard. The computational challenge is immense; for a given algorithm, finding a ruler of size n+1 can take approximately ten times longer than for size n. A distributed computation effort by Distributed.net confirmed OGR-28 over 8.5 years, resulting in a length of 528.

Numerous methods exist for constructing Golomb rulers. Paul Erdős and Pál Turán provided a formula utilizing odd primes p:

2pk + (k² mod p), k ∈ [0, p - 1].

For instance, with p = 7, the result is {0, 15, 32, 44, 58, 74, 85}, which generates ordered pairwise differences.

However, the growth rate of lengths for OGRs remains poorly understood. A ruler of size s can measure C(s, 2) lengths, where C(n, k) denotes the binomial coefficient. Given that all distances are unique, the length must be at least s(s - 1)/2. Various efforts have sought to improve this lower boundary, while Erdős conjectured an upper limit of s², confirmed thus far up to s = 150.

For size s and length G(s), the following graph illustrates the length function for the first 28 values:

### The 15 Million Dollar Markings

Regarding those 15 million dollar markings, Golomb rulers play a critical role in radio astronomy. Radio telescopes are often arranged in a linear formation, termed a “one-dimensional synthesis array,” to simulate a larger antenna. When astronomical signals are collected, Fourier transforms analyze their frequency components. By positioning telescopes at Golomb markers, the unique differences in antenna positions ensure that each pair yields distinct information about the frequency components of the signals, thereby optimizing the array's efficiency.

Golomb rulers also find diverse applications in engineering and computer science. They help mitigate interference in radio and television broadcasts and cellular systems, enhance resolution in X-ray crystallography, and aid in constructing self-orthogonal codes for error detection and correction in communications. Furthermore, they assist in identifying DNA sequences by ensuring that each probe binds to a unique location. Due to their simplicity and compactness, Golomb rulers are valuable in computational testing.

Essentially, Golomb rulers represent a foundational construct for both physical and abstract designs that necessitate a pattern-free structure. Interestingly, they have counterparts in higher dimensions, such as Costas arrays, which were first utilized to enhance sonar technology in the 1960s.

The alluring simplicity of Golomb rulers, coupled with their enigmatic nature, establishes Solomon Golomb’s creation as one of the remarkable mysteries within mathematics.

The $15 million estimate reflects the approximate modern cost for one of the 27 telescopes in the VLA.

Thank you for reading! If you found this article engaging, please consider following me and tapping the “Applause” icon as many times as you’d like. You can also subscribe for my latest content delivered directly to your inbox. I publish weekly on intriguing topics spanning math, music, and science.

### Further Resources

The National Medal of Science 50th Anniversary | National Science Foundation

Technical treatment of computational methods for finding OGRs

Paper: “A review of the available construction methods for Golomb rulers”

## Chapter 2: The Legacy of Solomon Golomb

The first video titled "King Among Kings" delves into the legacy of Solomon Golomb and the significance of his contributions to mathematics.

The second video, "What is the difference between Emperor and King? The Different Ranks of Monarchs," explores the hierarchy of monarchs, providing a contextual backdrop for understanding Golomb's impact on the realm of mathematics.