Mathematicians Still Can’t Solve an Uneven Ruler That Defies Regularity
- Oops!Something went wrong.Please try again later.
A Golomb ruler is very different from your run-of-the-mill tape measure.
These strange rulers are defined in terms of constraints, and are “optimized” when they are the shortest they can be.
While not familiar to most, Golomb rulers have applications ranging from radio astronomy to DNA analysis.
A standard ruler is a straight-edge marked at equal distances of a unit length (a mark for every inch, for example). This may seem like a surprising object to need to define, but there’s a reason for it. Wooden rulers used in school, tape measures, slide rulers—all of these typically have equidistant intervals with hash marks (often numbered), used to measure both metric and customized units.
A Golomb ruler, by contrast, is something else entirely. It is a set of uneven marks at non-negative integer positions such that no two pair of marks are the same distance apart, and they sum to the distance of the ruler. The number of marks on a ruler is its ‘order,’ and the largest distance between two of its marks is its ‘length.’ A Golomb ruler might start at 0 (though this is by no means a requirement), then have 1 as its next mark. The following mark could be 4 (three units away from 1) and the final mark could be 6 (two units away from 4, and five away from the origin of zero). Each mark on one of these unfamiliar rulers is necessarily a discrete integer, and each length is also unique—and designed to be as short as possible.
They’re odd, a little complicated, and enormously complex computationally—no algorithm or formal proof exists in the world to “solve” them. In fact, mathematicians have constructed only the first 28 so-called optimal Golomb rulers—rulers of order m with minimal length n for the specific value of m. To translate that mathematics speak into plain English: a Golomb ruler is said to be optimal if no shorter Golomb ruler with the same number of marks can be formed. Any whole number length measured by a Golomb ruler can be found in only one way, and so far, mathematicians have discovered only 28 of these.
You might now be wondering what on Earth a measuring tool like this might be used for. Named for mathematician Solomon W. Golomb, the Golomb ruler is freed from regular intervals we typically associate with rulers. It therefore has a multitude of practical applications in areas that require non-repeating patterns.
For example, suppose an astronomer wants to locate a faraway radio source in space using a series of large (and, most likely, very expensive) telescopes. To maximize accuracy, the distances between telescopes need to be distinct, because more information can be harnessed with multiple datapoints from various apertures. NASA science missions often involve sky observations that require high angular resolution imagery at wavelengths spanning the ultraviolet, visible and infrared spectra.
Using a Golomb ruler, our astronomer can find the optimal number of telescopes that provide non-redundant information with the best sky coverage, then place each telescope at the marks of the ruler and measure the phase difference between them. [See graphic]. Using as few detectors as possible also significantly reduces cost of these missions, making the application of a Golomb ruler quite helpful.
But the usefulness of Golomb rulers isn’t limited to space observation. These strange rulers allow us to explore combinatorial problems as wide ranging and complex as DNA pattern matching, circuit layout, and sonar signal work. Golomb rulers are also used to generate sequences, reduce ambiguities in X-ray crystallography, and create unique labels for paths in communications networks.
Essentially, they have the potential to enable the solving of hard optimization problems more efficiently. And these sorts of problems emerge in many industries: biosciences, transport, finance, and communications alike. “I use the optimal Golomb ruler problem as a test for my computational methods,” Willem-Jan van Hoeve, professor of operations research at Carnegie Mellon University, told Popular Mechanics. “I build optimization solvers—someone can give me their constraints, their decisions, and I can figure out the optimal solution.”
Indeed, many logistics challenges have a unique assignment at their core. “If I develop a new computational technique that can solve the Golomb ruler problem more efficiently, it likely can be generalized to many other scenarios. Because Golomb rulers are easy to state and relatively small, they are great for computational testing,” van Hoeve explained.
One easy-to-visualize example is the traveling salesman problem—a common routing conundrum with many applications. Take an Amazon truck’s delivery schedule, for example. Assigning a route (a length) and a sequence of stops (marks) to various vehicles—in which the distances between stops are as small as possible to maximize efficiency and minimize gas mileage—could be enhanced with a Golomb ruler application.
“Many issues in the business world are actually very difficult combinatorial optimization problems: financial portfolio optimization (the trading of stocks gets to market equilibrium faster), DNA pattern matching, military operations, airline crew scheduling and take-off slotting… these all are a bit like a Golomb ruler,” van Hoeve said.
Golomb rulers are elegant in their simplicity, yet they remain enigmatic in their un-solvability. Currently, the only known way to show a ruler fits the Golomb definition is to exhaustively search all possible rulers with shorter lengths and n marks and prove that none has the Golomb property—a brute force exercise that would take eons. Perhaps that’s why mathematicians remain so fascinated by these measurement mysteries. “The more abstract a problem becomes, the more relevant it is to a huge number of problems,” van Hoeve said. “If you crack them, you open up a wealth of applications.”
You Might Also Like
