## Rulers, Arrays, and Gracefulness

Ed Pegg Jr., November 15, 2004

In 1952, seemed to solve distortion problems in consecutive radio bands. Wallace C. Babcock found that the optimal way to set up radio signals involved placing them at fixed points so that all distances between signals were distinct. From that basis, he optimized signals within a minimum bandwidth - completely eliminating third order distortion while reducing fifth order distortion. His optimal array placed channels within the frequency spectrum at positions {0, 1, 4, 9, 15, 22, 32, 34}. No two distances are repeated. From 1 to 34, all distances except {16, 20, 24, 26, 27, 29}appear.

Solomon Golomb became interested in this intermodulation-avoidance array, and changed the problem to a ruler with minimal markings. He noted was perfect -- each distance from 1 to 6 appeared exactly once -- and wondered if more perfect rulers were possible. Unfortunately, he proved that this was the largest perfect ruler. Golomb rulers were named as a result of his investigations.

Consider the following curious triangle (Figure 1). Note that CH=1, BF=2, AD=3, BE=4, ..., BD=16, AH=17, AC=18, AB=19. There are a total of 18 different possible distances along the edges, with none repeated. All distances from 1 to 19 can be measured, except 14.

Figure 1. DΔS M(3,3) gives 18 distinct distances in a scope of 19. (See J B Shearer's page.)

The triangle can be represented as {{0,3,15,19}, {0,6,11,13}, {0,8,17,18}}, and gives an optimal difference triangle set, or DΔS. The maximal distance, or scope, must be as small as possible. For M(3,3), the scope is 19. A triangle with 6 marks on each side, M(3,7) = {{0,12,15,31,55,87,88,93}, {0,7,30,41,51,77,90,99}, {0,2,29,37,54,82,96,100}}, measures 84 distinct distances with scope 100. M(3,8) is currently unknown.

Triangles seem interesting -- how about a 2 sided object? The largest known DΔS of this type is M(2,9), shown below.

Figure 2. DΔS M(2,9) gives 90 distinct distance in a scope of 121. (See J B Shearer's page.)

The above use marks on two or three lines. If the marks are placed on just a single line, and no shorter ruler is possible, it's a Golomb ruler. All Golomb rulers up to 8 marks were originally discovered by Wallace C. Babcock. The rest have been discovered through both combinatorial analysis and impressive computer power. The following table contains examples of all known rulers up to 24 marks. The years given are the verification dates, and not necessarily the year a particular ruler was originally discovered.

 0, 1 (Babcock 1952) 0, 1, 3 (Babcock 1952) 0, 1, 4, 6 (Babcock 1952) 0, 1, 4, 9,11 (Babcock 1952) 0, 1, 4,10,12,17 (Babcock 1952) 0, 1, 4,10,18,23, 25 (Babcock 1952) 0, 1, 4, 9,15,22, 32, 34 (Babcock 1952) 0, 3, 9,17,19,32, 39, 43, 44 (Mixon 1972) 0, 1, 6,10,23,26, 34, 41, 53, 55 (Robinson&Bernstein 1967) 0, 1, 4,13,28,33, 47, 54, 64, 70, 72 (Robinson&Bernstein 1967) 0, 2, 6,24,29,40, 43, 55, 68, 75, 76, 85 (Robinson 1983) 0, 7, 8,17,21,36, 47, 63, 69, 81,101,104,106 (Robinson&Bernstein 1967) 0, 5,28,38,41,49, 50, 68, 75, 92,107,121,123,127 (Shearer 1990) 0, 6, 7,15,28,40, 51, 75, 89, 92, 94,121,131,147,151 (Shearer 1990) 0, 1, 4,11,26,32, 56, 68, 76,115,117,134,150,163,168,177 (Shearer 1990) 0, 5, 7,17,52,56, 67, 80, 81,100,122,138,159,165,168,191,199 (Silbert 1993) 0, 2,10,22,53,56, 82, 83, 89, 98,130,148,153,167,188,192,205,216 (Silbert 1993) 0, 4,13,15,42,56, 59, 77, 93,116,126,138,146,174,214,221,240,245,246 (Rankin 1995) 0,24,30,43,55,71, 75, 89,104,125,127,162,167,189,206,215,272,275,282,283 (G&V 1997) 0, 4,23,37,40,48, 68, 78,138,147,154,189,204,238,250,251,256,277,309,331,333 (G&V 1998) 0, 1, 9,14,43,70,106,122,124,128,159,179,204,223,253,263,270,291,330,341,353,356 (d.n 1999) 0, 6,22,24,43,56, 95,126,137,146,172,173,201,213,258,273,281,306,311,355,365,369,372 0, 9,33,37,38,97,122,129,140,142,152,191,205,208,252,278,286,326,332,353,368,384,403,425

Rulers with 20 to 22 marks were found with an intense computer search by Mark Garry and David Vanderschel. For rulers with 23 and 24 marks, work got started at distributed.net. They sent out a press release on 1 November 2004:

 distributed.net is proud to announce the completion of OGR-24! Four years ago, distributed.net users undertook the search for the optimal 24 mark Golomb Ruler. This year sees the successful conclusion of that effort. We have proven conclusively by the exhaustive search of all possible rulers that the currently best known ruler is indeed the Optimal one. More precisely it is: 24/9-24-4-1-59-25-7-11-2-10-39-14-3-44-26-8-40-6-21-15-16-19-22 This shortest ruler was found by two independent computers. The initial report was received on May 24th, 2004 and a second, matching result was returned on July 3rd, 2004. However it was not until the final stub was returned and verified that could we rule out the possibility of a still-shorter ruler. This final stub was returned October 13th, 2004 drawing to a close the complete search of all possible stubs. Due to the nature of an exhaustive search, distributed.net users have also proven that the above solution is unique (the ruler's mirror notwithstanding). This project was first announced in 1998, started in February 2000, and is now concluded in 2004. Although 4 years may seem like a long time, the search was no trivial task. No fewer than 555,529,785,505,835,800 rulers were checked during that time. Moreover, a second pass of all rulers was done to rule out (heh) any errors. Additionally a small oversight in the beginning of the project caused several rulers to be excluded from the initial search. These were the subject of the much discussed Phase 2 (rulers with initial marks > 70). Incidentally the optimal ruler was amongst these. ("9+24+4+1+59 > 70") The double phase, phase 2 and their verification each required additional structural changes which also contributed to the overall 4 year duration. Note that distributed.net users continue to pursue the solution to the OGR-25 project which began in parallel with OGR-24. We have currently completed 10-15% of OGR-25 phase 2 which is about 65% overall. To celebrate the successful end of yet another distributed.net project all our contributors are invited for a drink...when we find a place large enough to host the 41,805 people that participated in this particular distributed effort. :)

A picture of OGR-24 can be seen at hewgill.com. I don't think they are serious about that last comment -- can you imagine how big the party would be? Let me turn that question around: can you figure out how big a Golomb ruler will be? For n marks, we know that G(n) gives the sequence 0, 1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425. (A003022). Above 4 marks, we know that (n-1)(n-2)<G(n)<n2. Can a better bound be found? To answer that question, one must delve farther back into history.

As earlier mentioned, they are named Golomb rulers, but were actually discovered by Babcock. Before that, in 1932, Simon Sidon looked at subsets of the natural numbers up to n such that no two pairs of numbers had a common sum. (In a Golomb ruler, no two pairs of numbers have a common difference.) Paul Erdos called them Sidon sets, and published papers about them in 1934. Apostolos Dimitromanolakis proved the equivalence of the two in 2002. It was very easy: Sidon <=> NOT(ar+as= am+an) <=> NOT(ar-an = am-as) <=> Golomb. Dimitromanolakis used this connection to find the lower bound G(n)>n^2-2n*sqrt(n)+sqrt(n)-2.

So, we have some sequence of marks, {0, 1, 4, 9, 15, 22, 32, 34}, and we demand that the differences on every level be different: {{1, 3, 5, 6, 7, 10, 2}, {4, 8, 11, 13, 17, 12}, {9, 14, 18, 23, 19}, {15, 21, 28, 25}, {22, 31, 30}, {32, 33}, {34}}. What if the restriction is lessened, so that the distances must be distinct within each level? These are called Costas arrays. They are used in the fields of radar, sonar, and communications -- and it turns out the best introduction about them was written by Solomon W. Golomb and Herbert Taylor.

Currently, the only way to determine all Costas arrays of a given order is through exhaustive search, although many may be produced through algebraic constructions. As a simple example, consider the prime number 19, and compute the values of (2^k) mod 19, k = 0:17. The result is the following sequence: 1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10.

This sequence is not only a permutation of the integers from 1 to 18, but also has the property that each row of its triangular difference table contains unique differences. This property is similar to Golomb rulers, except the differences are allowed to be negative or positive, and uniqueness is only enforced within a given row.

For some time, only the Costas arrays up to order 23 were known, giving sequence A008404. In April 2004, it was announced at the IEEE Radar Conference that 200 distinct Costas arrays exist for n=24, and 88 exist for n=25.

Sparse rulers are more practical as actual rulers. , for example, will measure all distances up to 29. It has an excess of seven extra distances {1, 2, 3, 3, 6, 13, 27}. One obvious problem is to minimize excess for n marks. Sparse rulers don't seem to be well studied -- the best source I found for them was David Fowler's article at the Mathematica Information Center, of all places.

A similar problem involves labeling the vertices of graphs such that the n edges represent the difference between the vertices. If the edges contain the values 1 to n, it is considered to be a graceful graph. A famous unsolved problem: Characterize the graceful graphs (S. Golomb, 1972). As an example, the Petersen graph is graceful. Joseph Gallian maintains a survey of what is known on graceful graphs.

Figure 4. The graceful Petersen graph.

Thousands of computers are working to extend the results mentioned above. Curiously, these massive computer searches have been verifying what is already known: the OGR-24 result was verified 1 November 2004, but it was originally discovered in 1967 (!) by John P. Robinson and Arthur J. Bernstein. The rulers to beat are maintained by James Shearer, and consist mainly of constructions via affine and projective planes. The last 8 proven rulers have used thousands of years of computer time to verify the results of a few clever combinatorialists from over 30 years ago. The OGR-25 project will try to top the 1984 result of Atkinson and Hassenklover. In this battle between two combinatorialists and one of the world's largest distributed computer systems, I'll side with the two math guys.

References:

W. C. Babcock, "Intermodulation Interference in Radio Systems", Bell System Technical Journal, 1953, p. 63-73.

James Beard, Jon Russo, Keith Erickson, Michael Monteleone, and Mike Wright, "Combinatoric Collaboration on Costas Arrays and Radar Applications," IEEE Radar Conference, Philadelphia, PA, April 2004. http://www.radar04.org/program/index.cgi?paper=144.

Justin Colannino, " Circular and Modular Golomb Rulers," http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/JustinColannino/.

distributed.net, "Project OGR," http://www.distributed.net/ogr/.

Apostolos Dimitromanolakis, "Analysis Of The Golomb Ruler And The Sidon Set Problems And Determination Of Large Near-Optimal Golomb Rulers," http://citeseer.ist.psu.edu/dimitromanolakis02analysis.html.

Apostolos Dollas, William T. Rankin, David McCracken, "New Algorithms for Golomb Ruler Derivation and Proof of the 19 Mark Ruler," http://www.ee.duke.edu/~wrankin/golomb/golomb.html.

Paul Erdos and P. Turan. "On a problem of Sidon in additive number theory, and on some related problems," J. London Math. Soc, 16:212--215, 1941.

Frans Faase, "Sparse rulers," http://home.planet.nl/~faase009/Ha_sparse_rulers.html.

David Fowler, "Genetically Seeking Sparse Rulers," Mathematica in Education and Research, V9:2, 2000, p 33-40. http://library.wolfram.com/infocenter/Articles/3820/.

Joseph A. Gallian, "Graph Labeling," http://www.combinatorics.org/Surveys/.

Mark Garry, David Vanderschel, "In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers," http://members.aol.com/golomb20/.

Martin Gardner, "Mathematical Games", Scientific American, March 1972, p. 108-112.

Solomon W. Golomb, Herbert Taylor, "Construction and Properties of Costas Arrays", Proceedings of the IEEE, Vol. 72, No. 9, September 1984.

Solomon W. Golomb, "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.

Bill Rankin, "Golomb Ruler Calculations," http://www.ee.duke.edu/~wrankin/golomb/golomb.html.

Walter Schneider, "Golomb Rulers," http://www.wschnei.de/number-theory/golomb-rulers.html.

James B. Shearer, "Difference Triangle Sets," http://www.research.ibm.com/people/s/shearer/dts.html.

James B. Shearer, "Smallest Known Golomb Rulers," http://www.research.ibm.com/people/s/shearer/grtab.html.

N. J. A. Sloane, Sequences A000217, A003022, A036501, and A039953 in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.

Eric W. Weisstein. "B2-Sequence, Graceful Graph, Golomb Ruler" From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/.

Math Games archives.