Golomb Rulers are an interesting class of math problem. For one thing, they can consume all available “computes” for all foreseeable future time. For another, they are useful.

Useful for what? Well, for siting radio telescopes for optimal performance with minimum number on the least land, and for some kinds of data compression and in radio, spectrum use. Among other things (including optimal position of sensor for things like x-ray fingerprints of diamonds).

So what’s a Golomb Ruler? Pretty simple, really. It is a set of marks on a stick where the distance between e two marks is unique.

A lot more is here:

https://en.wikipedia.org/wiki/Golomb_ruler

But I’m just going to give one simple example and I think that’s enough to “get it”.

A Golomb Ruler with 5 elements (called ‘order 5’) and largest element of 11 (called ‘length 11’) is:

0 1 4 9 11

And if you look at the distance between the different numbers you get:

1 3 5 2 4 8 7 9 10 11

No 2 numbers the same.

Now this ‘ruler’ is also an “optimal ruler” as the 11 is as small as you can get and still make 5 marks. This matters since, for example, if you were making a radio telescope with 5 antennas, you get the maximum information with the least land if you space them at 0 (start), 1, 4, 9, and 11. If those were km spacings, you would really rather not put one out at 23 km beyond what you needed and buy a lot more land…

There’s also some interesting bits on Golomb Rulers here:

http://mathworld.wolfram.com/GolombRuler.html

And here:

http://www.research.ibm.com/people/s/shearer/grule.html

### Nostalgia

I first started looking at this about a dozen (or maybe 14 now..) years ago when I first had a long duration contract in Florida. I was in a Motel and using my Compaq laptop (that I still have…) with some God Awful slow processor by today’s standards. It’s something like 64 MB of memory, Red Hat 5.2 or so, and some small Pentium. But I had a Golomb Ruler code I’d written running on it. (“someday” I need to find that in the archives and compare it to modern versions for speed and accuracy).

While doodling around looking at these lengths, I decided to just “plot them and look at it.” This was done by hand on graph paper. By Inspection, it sure looked like a parabola. Smith’s Hypothesis Of Golomb Rulers was formed: “Optimal Golomb Rulers lie *near* a parabola”.

I doodled around some more and did a crude curve fitting. It sure seemed to hold and have some predictive power. I even managed to find one of the next likely Optimal Golomb Rulers, but at that time it was not easy to find out if it was new (or tell anyone) unless you were a math professor.

Then the contract “suddenly ended” when the client decided to outsource their data center. Golomb went on the shelf as I packed up and headed home, looking for a new job and no longer spending evenings bored silly looking for a ‘hobby’ to keep me interested.

### Time Passes

Well, time passes, and Moore’s Law makes computers a LOT faster. The Raspberry Pi I’m using now is roughly the same performance in total computes as the Cray XMP I managed in the 1980’s. The Web makes all sorts of things nearly trivial to find, or do. Distributed Computing has moved Golomb Rulers forward quite fast (and hit a new exponential wall at an optimal length of 28), and my “solution” can now be checked against reality (IFF I can find it in one of the old boxes…)

Furthermore, since blogging has evolved into existence, I can now “publish” without all the pain and suffering of the past.

So with that, I’m going to “toss the idea at the world” and see if it grows…

### The Fitting Of The Curve

Where before I did this with pencil and paper over nights in the hotel, now it is a quick visit to a web page:

Now this shows that the errors are to each side of the ‘fit’. You really want a parabola that sits to one side, so that a search does not run forever to find nothing.

I went back by hand and did a trial of a few simpler equations, looking for one or two that seemed to just skirt the edges of the fit for the more recent data points. In the very early data points, you get an exact fit with

y= 1/2 x^2 -1/2 X

but that rapidly doesn’t fit so well. (Implying that the actual curve isn’t quite a parabola, or that the integer nature of the rulers makes them have significant ‘jitter’ in the errors as things grow).

Some of the other ‘fits’ as you add items are:

0.64 X^2 -1.15 X +0.6 0.70 X^2 -1.51 X +0.7 0.74 X^2 -1.89 X +1.66 0.81 X^2 -2.70 X +3.3

And so it goes. Clearly a better “fit” and perhaps even solving for the vertex of the implied parabola would be very helpful.

But I just want a good enough ‘rule of thumb’ for the next few numbers in the Golomb series. So I did a hand fit / fudge with some simplifications. First off, this basic formula is of the form y=aX^2+bX+c and I dumped the “c”. Then adjusted to keep the fit close.

There are four formulas that look to have some ‘merit’ as starting point finder for a search for any given ruler.

0.8 X^2 0.8 X^2 -X 0.8 X^2 -1/2X 0.81 X^2 -X

There is certainly a better choice with a bit more tuning.

I computed the predicted value of each, and compared that to the known Optimal Golomb Rulers for the 27 known lengths.

0.8 X^2 gives a value that never fails to be just outside the actual value, but the distance is a bit further than I’d like.

0.8 X^2 – X gives a nice close value, but sometimes is just a hair too short. Take the ruler of n=21 for example. The optimum known is length 333. If you do 0.8 x 21^2 = 352.8 and that’s about 20 away from the optimal. It would take a while to iterate that distance. Now look at 0.8 X^2 -X and you get 331.8 and a miss by 1.2 so you search forever and find nothing. That’s not good.

Yet in the first 27, there are only 4 misses, and two of them are the n=1 and n=2 cases at the start. Clearly it’s a very tight fit. (The other big one is n=25 and length 480 where it predicts 475 for a miss by 5).

Which brings us to the two other formulas. Instead of taking out a full X, take out 1/2 X, or have the X^2 grow a bit faster.

The 0.8 X^2 and 0.81 X^2- X formulas have “cross over” at n=100 with both giving a prediction of 8000 length, while the best known is length 8831 and 0.8 X^2 – X predicts 7900 length. This fairly strongly implies, IMHO, a more optimal ruler than the known length at between 7900 and 8000 with the potential of one just a bit shorter than 7900 not ruled out. 0.8 X^2 – 1/2X gives 7950 and I’d expect the actual value is more probably between 7900 and 7950 if I had to bet.

IMHO, the optimal thing to do from this point would be to fit 3 parabolas. One just outside the known optimal values, one just inside, and one ‘best fit’. Then search from both edges toward the middle and from the middle toward both edges. As soon as any ruler if found, it sets a new bounds and the searches outside that bounds can be discarded.

It is my belief that this ‘fitting’ method using parabolas (or any better fit) would significantly reduce the search area from the present methods for proving an Optimal Golomb Ruler (which is exhaustive search). While exhaustive search is still the only way to prove a ruler is optimal, this ought to more rapidly get you to good candidates.

For a list of the known rulers, optimal or not, see:

http://www.research.ibm.com/people/s/shearer/grtab.html

This web page contains a table giving the lengths of the shortest known Golomb rulers for up to 150 marks. The values for 23 marks or less are known to be optimal. For the actual rulers see known optimal rulers best rulers from projective plane construction best rulers from affine plane construction Table of lengths of shortest known Golomb rulers marks length found by proved by comments 1 0 trivial 2 1 trivial 3 3 trivial 4 6 trivial 5 11 1952 WB 1967? RB hand search 6 17 1952 WB 1967? RB hand search 7 25 1952 WB 1967? RB hand search 8 34 1952 WB 1972 WM hand search 9 44 1972 WM 1972 WM computer search 10 55 1967 RB 1972 WM projective plane construction p=9 11 72 1967 RB 1972 WM projective plane construction p=11 12 85 1967 RB 1979 JR1 projective plane construction p=11 13 106 1981 JR2 1981 JR2 computer search 14 127 1967 RB 1985 JS1 projective plane construction p=13 15 151 1985 JS1 1985 JS1 computer search 16 177 1986 JS1 1986 JS1 computer search 17 199 1984? AH 1993 OS affine plane construction p=17 18 216 1967 RB 1993 OS projective plane construction p=17 19 246 1967 RB 1994 DRM projective plane construction p=19 20 283 1967 RB 1997? GV projective plane construction p=19 21 333 1967 RB 1998 GV projective plane construction p=23 22 356 1984? AH 1999 GV affine plane construction p=23 23 372 1967 RB 1999 GV projective plane construction p=23 24 425 1967 RB projective plane construction p=23 25 480 1984 AH projective plane construction p=25 26 492 1984 AH projective plane construction p=25 27 553 1984 AH projective plane construction p=27 28 585 1984 AH projective plane construction p=27 29 623 1984 AH projective plane construction p=29 30 680 1984 AH projective plane construction p=29 31 747 1984 AH projective plane construction p=31 32 784 1984 AH projective plane construction p=31 33 859 1984 AH projective plane construction p=32 34 938 1984 AH projective plane construction p=37 35 987 1984 AH affine plane construction p=37 36 1005 1984 AH affine plane construction p=37 37 1099 1984 AH projective plane construction p=37 38 1146 1984 AH projective plane construction p=37 39 1252 1984 AH projective plane construction p=41 40 1282 1984 AH affine plane construction p=41 41 1305 1984 AH projective plane construction p=41 42 1397 1984 AH projective plane construction p=41 43 1507 1984 AH affine plane construction p=43 44 1596 1984 AH projective plane construction p=43 45 1687 1984 AH projective plane construction p=47 46 1703 1984 AH projective plane construction p=47 47 1804 1984 AH affine plane construction p=47 48 1887 1986 LS projective plane construction p=49 49 1958 1984 AH projective plane construction p=49 50 2094 1984 AH projective plane construction p=49 51 2190 1984 AH projective plane construction p=53 52 2270 1984 AH projective plane construction p=53 53 2347 1984 AH projective plane construction p=53 54 2373 1984 AH projective plane construction p=53 55 2598 1984 AH projective plane construction p=59 56 2725 1984 AH projective plane construction p=59 57 2773 1984 AH projective plane construction p=59 58 2851 1984 AH projective plane construction p=59 59 2911 1984 AH projective plane construction p=59 60 3019 1984 AH projective plane construction p=59 61 3134 1984 AH affine plane construction p=61 62 3215 1984 AH projective plane construction p=61 63 3391 1984 AH projective plane construction p=64 64 3527 1984 AH projective plane construction p=64 65 3593 1984 AH projective plane construction p=64 66 3757 1984 AH projective plane construction p=67 67 3819 1984 AH projective plane construction p=67 68 3956 1984 AH projective plane construction p=67 69 4145 1984 AH projective plane construction p=71 70 4217 1984 AH projective plane construction p=71 71 4330 1984 AH projective plane construction p=71 72 4473 1986 LS projective plane construction p=73 73 4513 1984 AH projective plane construction p=73 74 4753 1984 AH projective plane construction p=73 75 4982 1984 AH projective plane construction p=79 76 5089 1984 AH projective plane construction p=79 77 5204 1984 AH projective plane construction p=79 78 5299 1984 AH projective plane construction p=79 79 5408 1984 AH projective plane construction p=79 80 5563 1984 AH projective plane construction p=79 81 5717 1984 AH projective plane construction p=83 82 5814 1984 AH projective plane construction p=83 83 6020 1984 AH projective plane construction p=83 84 6159 1984 AH projective plane construction p=83 85 6410 1984 AH affine plane construction p=89 86 6537 1984 AH affine plane construction p=89 87 6708 1984 AH projective plane construction p=89 88 6745 1984 AH projective plane construction p=89 89 6778 1984 AH projective plane construction p=89 90 6967 1984 AH projective plane construction p=89 91 7542 1984 AH affine plane construction p=97 92 7617 1984 AH projective plane construction p=97 93 7726 1984 AH projective plane construction p=97 94 7884 1984 AH projective plane construction p=97 95 7967 1984 AH projective plane construction p=97 96 8121 1984 AH affine plane construction p=97 97 8357 1984 AH projective plane construction p=97 98 8462 1986 LS projective plane construction p=101 99 8540 1984 AH projective plane construction p=101 100 8831 1984 AH projective plane construction p=101 101 8897 1986 AH projective plane construction p=101 102 9218 1986 AH projective plane construction p=101 103 9408 1986 LS projective plane construction p=103 104 9581 1986 LS projective plane construction p=103 105 9884 1997 LM affine plane construction p=107 106 10135 1986 LS projective plane construction p=107 107 10241 1997 LM projective plane construction p=109 108 10415 1986 LS projective plane construction p=109 109 10583 1986 LS projective plane construction p=109 110 10767 1997 LM projective plane construction p=109 111 11108 1986 LS projective plane construction p=113 112 11292 1986 LS projective plane construction p=113 113 11423 1986 LS projective plane construction p=113 114 11764 1986 LS projective plane construction p=113 115 12212 1986 LS projective plane construction p=121 116 12412 1986 LS projective plane construction p=121 117 12517 1986 LS projective plane construction p=121 118 12741 1998 JS2 projective plane construction p=125 119 12911 1986 LS projective plane construction p=121 120 13089 1986 LS projective plane construction p=121 121 13280 1986 LS projective plane construction p=121 122 13521 1986 LS projective plane construction p=125 123 13761 1997 LM affine plane construction p=127 124 13948 1998 JS2 affine plane construction p=125 125 14055 1986 LS projective plane construction p=125 126 14348 1986 LS projective plane construction p=127 127 14460 1998 JS2 projective plane construction p=128 128 14821 1986 LS projective plane construction p=128 129 15075 1986 LS projective plane construction p=128 130 15275 1986 LS projective plane construction p=131 131 15548 1986 LS projective plane construction p=131 132 15893 1986 LS projective plane construction p=131 133 16192 1986 LS projective plane construction p=137 134 16296 1986 LS projective plane construction p=137 135 16622 1997 LM projective plane construction p=139 136 16766 1986 LS projective plane construction p=137 137 17031 1997 LM projective plane construction p=139 138 17124 1986 LS projective plane construction p=139 139 17579 1997 LM affine plane construction p=139 140 17938 1986 LS projective plane construction p=139 141 18601 1986 LS projective plane construction p=149 142 18751 1986 LS projective plane construction p=149 143 18941 1997 LM affine plane construction p=149 144 19123 1997 LM projective plane construction p=151 145 19325 1986 LS projective plane construction p=149 146 19628 1986 LS projective plane construction p=149 147 19757 1986 LS projective plane construction p=149 148 20037 1986 LS projective plane construction p=149 149 20265 1997 LM projective plane construction p=151 150 20521 1986 LS projective plane construction p=149 References for above table. WB - Wallace C. Babcock W. C. Babcock, "Intermodulation Interference in Radio Systems", Bell System Technical Journal, 1953, p. 63-73. RB - John P. Robinson and Arthur J. Bernstein J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation", IEEE Transactions on Information Theory, IT-13(1967), p. 106-113. WM - William Mixon (unpublished, cited in) M. Gardner, "Mathematical games", Scientific American, June 1972, p. 116-118. JR1 - John P. Robinson J. P. Robinson "Optimal golomb rulers" IEEE Transactions on Computers, C-28(1979), p. 943-944. JR2 - John P. Robinson J. P. Robinson "Addendum to "Optimal golomb rulers"" IEEE Transactions on Computers, C-32(1983), p. 201. AH - M. D. Atkinson and A. Hassenklover M. D. Atkinson and A. Hassenklover, "Sets of Integers with Distinct Differences", School of Computer Science, Carlton University, Ottawa Ontario, Canada, Report SCS-TR-63, August 1984. see also M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions on Communications, COM-34(1986), p. 614-617. LS - Alex W. Lam and Dilip V. Sarwate A. W. Lam and D. V. Sarwate, "On optimum time-hopping patterns", IEEE Transactions on Communications, COM-36(1988), p. 380-382. JS1 - James B. Shearer J. B. Shearer, "Some New Optimum Golomb Rulers", IEEE Transactions on Information Theory, 36(1990), p. 183-184. OS - W. Olin Sibert (unpublished, cited in) A. Dollas, W. T. Rankin and D. McCracken, "A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler", IEEE Transactions on Information Theory, It-44(1998), p. 379-382. DRM - Apostolos Dollas, William T. Rankin and David McCracken A. Dollas, W. T. Rankin and D. McCracken, "A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler", IEEE Transactions on Information Theory, It-44(1998), p. 379-382. GV - Mark Garry, David Vanderschel and others (web project) Golomb ruler search site LM - Lloyd Miller (web page dated Oct. 12, 1997) Table of shortest known Golomb rulers (was Table of shortest known Golomb rulers ). JS2 - James B. Shearer (unpublished) Computations done Feb. 19, 1998 in preparing this table.

The known Optimal Rulers are given in the wiki. I also compiled the Golomb Ruler Searcdh probrams from:

http://researchweb.watson.ibm.com/people/s/shearer/grprog.html

on my Raspberry Pi just to see if I can keep it busy testing this hypothesis. At first, I was surprised that the results did not match those of the wiki table. Looking a bit further, I realized these are ‘distance reflections’ of each other. A ruler can be specified as the positions, or as the distance between elements. Using n=5 as the example, the wiki lists:

0 1 4 9 11 0 2 7 8 11

while the grs1.f program gives:

pi@RPiM2 ~ $ ./grs1 00005 11 0 1 4 9 11 0 3 4 9 11 n= 5 k= 11 solutions= 2 time= 0.00000000000 nodes= 40.

Note the second ruler of each is different. But state them as length segments instead:

2 5 1 3 7 6 4 8 9 11 and 3 1 5 2 4 6 7 9 8 11

Each row is just a reflection of the other. Typically reflected rulers are considered the same, so if you do run the programs, don’t let that throw you.

And, finally, there’s the distributed.net effort to find ever larger optimal rulers using a gaggle of home machines.

http://www.distributed.net/OGR

Just to give an idea where folks have gotten to, this problem grows exponentially at each step, but so does Moore’s Law (for now).

http://blogs.distributed.net/2014/02/

The OGR-27 project has been completed.

Filed under: project status — Mike Reed @ 16:09 UTCDear friends,

distributed.net is proud to announce the completion of OGR-27!

It is almost five years ago to the day that we began on this exciting journey. Almost 20,000 of you joined us.. without whom, it would have been impossible.

We have proven conclusively by the exhaustive search of all possible rulers that the previously predicted 27-mark ruler is indeed the most optimal one. We were confident that we would find a more optimal ruler during this search, but it was not to be.

We expected it to take us seven years to complete this awesome task but thanks to your efforts recruiting your friends and co-workers to our effort and a little help from Moore’s Law, we did it in five.The best known ruler is 27/3-12-26-25-29-2-9-36-10-68-1-4-17-53-35-8-16-28-6-14-13-71-18-19-23-7 (length 553). Represented the other way, this is marks at positions 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553.

In total, we verified 302,621,586 unique stubs (2,526 with 3-diffs, 179,120 with 4-diffs, 6,457,815 with 5-diffs and 295,982,125 with 6-diffs), requiring each to have been completed at least two times independently and with an identical node count. Additionally, due to a client implementation bug in some early clients, we required all stubs to have been verified at least once by a client greater than v2.9109.518. This delayed us by a few weeks towards the end of the project but was necessary to ensure that no work was skipped.

The shortest ruler was sent to us 11 times, with one user completing it twice. I will be writing to this user directly for some help picking lottery numbers!

We will be sending some distributed.net swag to the lucky winners and hope that you will join us as we move on to our next challenge!Moo!

One presumes the Moo! greeting is a reference to COW – a Cluster Of Workstations, which is how Distributed Net computing works.

At any rate, in about 2019 we ought to have a length 28 solution, using about 100,000 “computer-years” of computing…

And that points out why I’m hopeful someone will find a way to make use of a ‘near parabolic’ fit to the Optimal Golomb Ruler length.

It would be very nice if “Smith’s Hypothesis of Parabolic Optimal Golomb Ruler Length” could help to cut off a year or three of that compute burden. Unfortunately, at the present size of things, there is no way for me to test this significantly on my own.

So there you have it. Cast to the winds of Mathematical Fortune. May it find favor somewhere.

Small quibble: the length is the largest DISTANCE not largest element.

@Bobalooga:

Um, when talking about the last element (11 in the above example) the length from start to end is 11 and the distance from 0 to 11 is 11, so I’m not seeing the subtlety you are working at.

Are you speaking of non-optimal rulers where the final element, the distance from it to the start, and the length might all be different? For all known optimal Golomb Rulers the largest element size, the distance from start to it, and the length are all the same… (and they all start at zero).

Just off the top of my head, going back to my engineering days where we had to learn how to plot those conic section curves graphically rather than mathematically perhaps you should look at similar curves which are not quite parabolas.

A parabola is plotted using a fixed relationship between a point and a line, where an ellipse is plotted by using a fixed relationship between the two foci. At the special case where they foci of the ellipse are an infinite distance apart the curve plotted is identical to a parabola with the same distance to its focus. (the line “directrix” mimics a distant foci at infinite distance in the ellipse) and in that case an ellipse and a parabola are identical when the foci of the ellipse are infinite distance apart.

http://www.engineerintrainingexam.com/eit-review/mathematics-for-engineering/straight-lines-and-conics/

Therefore an ellipse is always “inside” the parabola it mimics. Any ellipse with a major axis shorter than infinity would plot inside the parabola, If that is the case the ellipse might be the inner bound of the jitter and a hyperbola might be the outer bound of the jitter.

Defining the characteristics of the ellipse and hyperbolas which would bound the jitter I leave as an exercise for those with more math background than I, but it would be a logical starting place in my view for analyzing your rule. Perhaps some relationship with the key characteristics of the ellipse and hyperbola and the parabola’s characteristic dimensions, like the bounding value would be some relationship with the largest known number of the ruler you are working on and trying to find the next number in the series.

If true you would trim the values to test by several orders of magnitude.

@Larry:

Interesting idea…

Oh, and since we’re at 1/2 decade to compute a proof… it would be very practical to recompute bounding ellipse, parabola, and hyperbola for each run / length target.

And yes, that “trim by a couple of orders of magnetude” is the whole idea. You trade some occasional failures (like picking a starting point inside the actual optimum) for a potential very fast hit most of the time on a ‘near optimal’, then adjust strategy. IFF the one bound run wanders off an dies, the other run ought to succeed and much sooner than otherwise.

Since we’re in the land of using multiple processors anyway, it would be reasonable to “bound the space” and assign parts of the cluster to search parts of the space. This just (hopefully) starts them off such that at least one of them is much much closer to the final solution…

Yes, since you didn’t specify non-optimal, I had to be a pedant.

Ok. Pedantry welcome ;-)

I’ve been an olympic class nit harvester sometimes too :-)