The Golomb Ruler

Golomb rulers are named after the mathematician Solomon W. Golomb. In contrast to regular rulers, they do not have markings at uniform intervals. The typical ruler depicted above has 12 markings, each with a distance of one centimeter. With it, lengths between one and eleven can be measured.

A Golomb ruler, for example one of length 6 (seen above), only has 4 markings (it has order 4), yet it can still measure all lengths from 1 to 6. It is therefore called a perfect Golomb ruler.

However, there are no perfect Golomb rulers beyond that. With a Golomb ruler of order 5, which has 5 markings (0,1,4,9,11), you cannot measure all lengths, as 6 is not included. But that's not the point. The aim is to have as many different distances between the markings as possible while keeping the ruler as short as possible. It is then called optimal.

Golomb rulers are used in the design of array antennas such as radio telescopes. Antennas in a [0,1,4,6] Golomb arrangement are commonly found in mobile phone towers. They are also used in the arrangement of field sensors in MRI or X-ray crystallography and in geodesy.

In these applications, the goal is to achieve a maximal number of different distances with a minimal number of elements (antennas, sensors) and in three dimensions, a maximal number of different emission and reception angles. If the Golomb rulers used are optimal, the extent of the measuring system or array antenna is also minimized, improving handling or enabling deployment altogether.

Finding optimal Golomb rulers for a given order is a computationally intensive task. Using distributed computing, optimal Golomb rulers up to order 28 have been confirmed so far. As of 2022, the search for an optimal ruler of order 29 is not planned, as the effort involved appears to be too high.