Tomas Rokicki (rokicki@gmail.com) and Gil Dogon (gil.dogon@mobileye.com)
A Golomb ruler is a set of nonnegative integer values (marks) that includes zero and whose pairwise differences are all unique. That is, for every pair of distinct numbers (a,b) in the set, there is no other pair (c,d) such that a-b=c-d (unless a=c and b=d). The values in the set are called "marks", like marks on a ruler. The length of the ruler is equal to the maximum value in the set.
Finding the shortest Golomb ruler with a given number of marks (n) may be a difficult task. Indeed, a massive distributed project is under way to prove that the known 28-mark ruler (with a length of 585) is the shortest possible; it has been running for nearly two years and is about 12% complete.
Finding good (near-optimal) Golomb rulers using normal search techniques is difficult; we are not aware of any effective approach at this point in time. But a little bit of mathematics originated by James Singer in 1938 (with some follow-up help from R. C. Bose and S. Chowla) gives construction techniques for rulers that appear to be optimal (and are guaranteed to be near-optimal). Indeed, with the exception of six small sizes, no better Golomb rulers have been found than those generated by these construction methods. All the computational effort expended over the past two decades to prove the optimality of rulers with 18 through 27 marks has supported the assertion that rulers generated by these 75-year-old ideas are the best we can do.
But we are not certain this will continue for the larger sizes.
James B. Shearer implemented the construction methods in a set of Fortran programs around 1986, and generated the best set of Golomb rulers through 160 marks possible with these methods; his information is published on IBM's research site. He also implemented a brute-force search program that verified or found the optimal ruler lengths through 16 marks.
We have reimplemented Singer, Bose, and Chowla's ideas and run their constructions on modern machines, extending the set of possibly optimal rulers up through 40,000 marks. This has required some new ideas and improvements to the existing algorithms, which we describe below.
We believe these rulers are probably optimal, and are offering a $250 reward if anyone can beat any of these ruler lengths (for 36 through 40,000 marks) using any technique.
Every proper subset of a Golomb ruler is also a Golomb ruler (but one with fewer marks). (If the zero value is omitted you can subtract the smallest value from each value in the set to obtain a valid ruler.) Also, every Golomb ruler can be "flipped"---take the maximum value in the set, and subtract from this every value in the set to generate a new set that measures the same distances.
All of the constructions we use generate "modular" rulers. A modular ruler is one such that the marks can be placed on the circumference of a circle (of a specific size, the modulus), and all the distances measured are unique. While a standard Golomb ruler measures n(n-1)/2 distinct distances, a modular ruler measures n(n-1) distinct distances. Every subset of a modular ruler is also a modular ruler (with the same modulus). Every modular ruler is also a Golomb ruler.
Thus, every ruler we claim to be optimal, actually satisfies more constraints than strictly required; in addition to satisfying the normal Golomb requirements, it also is a modular ruler. While any Golomb ruler is also a modular ruler if you make the modulus large enough, it turns out the modulus for our rulers is typically only a little more than the total length of the ruler itself.
A perfect Golomb ruler with n marks measures exactly the distances 1 through n(n-1)/2. This is only possible through 4 marks (can you prove it is not possible for 5 or more marks?) A perfect modular ruler with n marks measures exactly the distances 1 through n(n-1) (and it is easy to show that its modulus must be n(n-1)+1). The 1938 Singer construction, which generates most of the rulers we suggest are optimal, generates perfect modular rulers, every time (but only for a number of marks that is one more than a prime power). Not only that but it generates many, many different perfect modular rulers. For instance, the Singer construction generates the following perfect modular ruler with 12 marks (and with modulus 133):
0 1 12 14 22 29 54 60 63 90 110 129
Pick any number from 1 to 133, and you can find two values that differ by that number (modulo 133) from the above set. For instance, for a difference of 65, you can pick 90 and 22; (22-90) mod 133 is 65. The best length 11 ruler that we can extract from directly this ruler is of length 94 (from the 129 wrapping around to the 90). But we can generate a new modular ruler from this one by multiplying each value by 20 (which is relatively prime to 133) and sorting the result, giving us
0 3 14 16 20 41 48 53 63 71 72 107
From this modular Golomb ruler we can extract a length-11 Golomb ruler of length only 72 (from the 0 on the left to the 72 towards the end); this is one of only two optimal length-11 Golomb rulers.
The other two constructions we consider, the Bose-Chowla construction and the Ruzsa construction, generate near-optimal modular rulers.
All the methods take a single input g, which is a prime power (or for Ruzsa's construction, just a prime) and require roughly the following steps:
PrimPoly: Find a primitive polynomial for a specific field generated by that prime. This provides a numbering of the elements of the field.
Select: From that field, select members that satisfy a specific criteria specific to the construction. This will generate the modular ruler.
Multiply: From the original modular ruler, generate a lot of additional modular rulers by multiplying that ruler by numbers relatively prime to the modulus.
Sort: Since the values of the multiplied modular ruler are not generated in numerical order, sort the modular ruler.
Scan: For each of these modular rulers, try all contiguous sub-rulers as candidate Golomb rulers.
The Fortran programs written by James B. Shearer include all of these steps in a clear and straightforward manner. In order to extend the results as far as we did, the algorithms for each step needed improvement.
There have been a number of papers written on finding primitive polynomials in Galois fields, and implementations of these ideas are available on the web. The ideas in these papers are nontrivial but critical in order to generate primitive polynomials of Galois fields with millions or billions of elements. Both of us independently authored primitive polynomial generation code.
The selection criteria for each of the distinct constructions is fairly non-trivial (especially for the Singer construction). One of us essentially copied Shearer's code into C for this; the other reimplemented everything from scratch. The performance of the Shearer code here was adequate for our purposes.
There were a number of improvements to the multiply step. Both the Singer and the Bose-Chowla construction generated O(g2) distinct modular rulers (where g is the prime power used for generation). Since we will be sorting and scanning for every multiplicand we consider, it is important to eliminate redundant multiplicands. All of the constructions exhibited symmetry based on a particular subgroup, so we were able to exclude 5/6ths of the multiplicands for the Singer construction and 3/4ths of the multiplicands for the Bose-Chowla construction. The Ruzsa construction required consideration of many fewer multicands (O(g)) so symmetry reduction was not needed here.
In addition, the actual multiply step itself could be slow, with a 64-bit multiply and remainder calculated for each value. We improved this by maintaining a cache of small multiples of the input ruler modulo the modulus. When evaluating a new modulus m, if that was small compared to the previous modulus considered, we would just add-and-test the relevant multiple from the cache. The compiler turned this into efficient SSE instructions.
Most of the time in our program was spent in the sort phase. We tried numerous variations of radix sort and finally adopted one that was able to sort more than 100 million elements per second.
In the scan phase, we want to consider every possible sub-ruler from the current modular ruler for every possible Golomb ruler length. A straightforward implementation (as Shearer used) would take time O(n2) for every modular ruler. We were able to improve this as follows. First, since optimal rulers with 27 marks and fewer are already known, we did not scan for shorter rulers; we started our set of scans at 27. (We only did this optimization for values of g of 1000 or more, so we could pick up the known values as well, all of which are generated with small values of g.) So let us say the shortest ruler found for 27 marks for the current modular ruler turned out to be 950. For each mark count, we decided we did not care about rulers of lengths greater than n2. Further, we have a lower bound on the lengths of a Golomb ruler (n2-2n1.5+sqrt(n)-2). When considering whether to scan at length 27+x, we would add our best at 27 (950) to the lower bound on the length of a ruler with x marks, and if that was greater than either (27+x)2 or our best found ruler at length 27+x, we would skip that scan since it could never improve or match our best. This simple idea let us skip almost all scans with little effort. For instance, for 14,533 marks, we considered 22,680,000 moduli. Without this optimization we would have had to do roughly 14,000 scans per moduli; with it, we ended up doing only an average of 14.7 scans per moduli, a reduction by nearly a factor of 1000.
With these ideas we were able to complete the constructions for all prime powers less than 40,000 and find what are likely to be the shortest Golomb rulers possible for all sizes through 40,000.
The data is given by the following files. All files are packed in the zip format except the C++ source for getrules. All files have a two-digit suffix indicating the range of values included; thus, the file golomb-all-13 contains information on Golomb rulers for sizes 13000 through 13999. Files named golomb-all-## contain the metadata for the best rulers constructed, with space-separated fields containing in order the number of marks, the total length, the type of construction used (pp for projective plane, and ap for affine plane), the prime power used to construct the modular ruler, and the multiplier to apply to that modular ruler. Files named modrules-pp-## and modrules-ap-## contain the actual modular rulers calculated, one per line. The line starts with the prime power, followed by a colon, and then space-separated integers giving the size of the gaps between the rulers. There are also four files called rulers-all-## containing the best Golomb rulers themselves (for sizes 5 through 3999), one per line. The line starts with the number of marks, followed by a colon, followed by space-separated locations of the marks themselves.
In addition, a C++ program called getruler.cpp is supplied that can be used to extract the probably optimal Golomb ruler for any size, given the above data files (after unzipping). Compile this program and give the desired size on the command line.
This work was inspired by the most recent of Al Zimmermann's programming contests. Thank you, Al!
See Part 2 here.
James Singer, A Theorem in Finite Projective Geometry and Some Applications to Number Theory
Konstantinos Drakakis, A Review of the Available Construction Methods for Golomb Rulers
James Shearer, Golomb Rulers
Apostolos Dimitromanolakis, Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers