Weird Rulers

Suppose you have something you want to measure. Easy enough--you grab a ruler or a tape measure and carry out the measurement. Today, many rulers come with scales along each of the edges of the rectangular shape--inches along one edge and centimeters along the other. Inches are what is still standardly used in the U.S. although nearly all the rest of the world (except Liberia and Myanmar) uses the metric system. But in a sense the way rulers are designed involves a redundancy--they have markings at 0, 1, 2, 3, ...., 12 on a typical foot-long ruler, and one does not necessarily need all of these markings. Let me be more specific.

Figure 1 shows a portion of a typical ruler with equally-spaced segments labeled with the numbers from 1 to 8. If one wants to measure 4 inches, this can be done from 0 to 4, from 1 to 5, from 2 to 6 or from 3 to 7.
 

Figure 2 shows a ruler which does not have marks at all of the integers from 0 to 6. For convenience we have shown labels at 0, 1, 4, and 6 but these could be omitted.

In fact, standard rulers also are "marred" by the fact that they use numbers as labels for the markings on the ruler.

Imagine we had to measure positive integer length numbers from 1 to k, and we wanted to do this by putting marks along a straightedge in such a way that each length from 1 to k could be measured in exactly one way using two of the marks on the ruler. There will be no names (numbers) necessarily assigned to these marks (though sometimes we use them for convenience). We just want marks where the differences between the marks can measure the numbers from 1 to k. Can this always be done?

The ruler in Figure 2 shows that for k=6 there is such a ruler with 4 marks on the ruler: This ruler with its 4 marks can measure segments of length 1, 2, 3, 4, 5, and 6. It turns out the requirements just described are very demanding and there are not very many rules of this kind. They only exist for k equal to 1, 3, 6 and have marks at:

0 and 1
0, 1, and 3
0, 1, 4, and 6

More about this a bit later. Since being able to get all the distances from 1 to k is such a stringent condition perhaps it is more reasonable to require the following: A ruler with n marks, the first mark by tradition corresponding to 0, is called a Golomb Ruler if each of the pairs of marks on the ruler measures a different length. While a Golomb Ruler whose first and last marks are at 0 and m may not measure all the lengths 1, 2, ...., m, no length that it does measure is repeated. The number of marks on a Golomb ruler is often referred to as the order of the ruler, while the largest mark is called the length of the rule.

An example of a Golomb ruler with 5 marks is shown in Figure 3. It is an order 5 ruler of length 11
 

and it measures the lengths 1,2,3,4,5,7,8,9,10, and 11. Only length 6 is missing. Can you find another Golomb ruler with 5 marks which misses only the number 10?

In fact there is another Golomb ruler with 5 marks. It has marks at 0, 2, 7, 8, and 11. This ruler will measure all the distances from 1 to 11 except 10. Thus, we see that these two rulers cannot be "isomorphic" (the last word meaning that they are in essence the same ruler), since they miss a single different number in the set of numbers they are able to measure. (This second ruler has a second version which has marks at 0, 3, 4, 9, and 11 which is "equivalent" to the first.) It is conceivable that there are two inequivalent rulers which omit the same set of distances. Note that if we want a ruler which measures the lengths 1, 2, ...6, we can get away with a ruler of 4 marks. However, to measure the lengths from 1 to 10 we cannot use a ruler with as few as 5 marks because the rulers with 5 marks miss either the values 6 or 10. Here are the inequivalent rulers with 6 marks:

0 1 4 10 12 17

0 1 4 10 15 17

0 1 8 11 13 17

0 1 8 12 14 17

Note that all of these rulers measure the numbers 1 to 7. Any of these rulers of order 6 (6 marks) will measure integers from 1 to 7, but not all of them measure the integers from 1 to 8. Also, the first and third rulers in this list measure all the integers from 1 to 17 while missing the lengths 14 and 15 showing that inequivalent rulers can, in fact, miss the same set of lengths.

Golomb Rulers are named for Solomon Golomb. Golomb studied mathematics at Johns Hopkins and Harvard University; his Harvard doctorate dealt with prime numbers. He has made important contributions to coding theory and information theory. For his important work in these areas he won the IEEE Hamming Medal in 2000. His research has centered on issues related to communications theory but shows a remarkable range of applicable and "pure" mathematics.
 

Golomb is also known for coining the word polyomino for the geometrical diagrams which arise from pasting together 1x1 squares along edges. One of the 12 possible pentominoes is shown below:
 

My goal here is not merely to explore the world of Golomb rulers, which is a fascinating mathematical environment, but also to show how when mathematicians investigate a topic they bring to bear on it a rich association of tools and ideas that are part of the training that mathematicians get. One thing leads to another, and hopefully this tour of ideas on the periphery of studying Golomb rulers will give you a flavor of the fun and excitement of what mathematics is about.

Getting started

Let us start with a bit of combinatorics--counting. If one has k marks on a ruler then what is the largest number of distinct distances one can measure with that ruler? This largest number will occur when for any pair of marks one gets a different distance. How many ways are there for picking two marks from k? This is known as the number of ways that two objects (without regard to order) can be selected from k things, and is typically denoted and counted as shown.
 

There are k ways to pick the first mark and k-1 ways to pick the second, so there are (k)(k-1) ways to pick two marks one after the other. We divide by 2 because the order of the selections will not matter for our count.

Another notation for this uses binomial coefficients:
 

Both of these expressions can be read as giving the number of ways that k things can be chosen two at a time without taking order into account. For example, with 5 marks one could measure at most 10 distinct distances while 6 marks can measure at most 15 different distances.

Above I asked if you can find another example of a Golomb ruler with 5 marks. This raises the question of when two Golomb rulers are "equivalent" or the "same." We saw that putting marks at 0, 1, 4, 9 11 gives rise to a Golomb ruler with 5 marks. We could also put marks at 0, 2, 7, 10, 11. This would measure lengths 1, 2, 3, 4, 5, 7, 8, 9, 10, and 11. This set of marks can be obtained from the first set of marks by reading off the marks in the "reverse" direction. Thus, label the far right mark as 0, the next to the last mark as 1, etc. Thus, though the labels are different I will consider this as the same ruler as the first one. Both rulers omit the number 6. Since with 6 marks one can measure at most 15 distinct numbers (6 x 5/2 = 15), the fact that the shortest Golomb rulers with 6 marks have their last mark at 17 shows that these rulers each omit two lengths, as can be verified from the complete set of shortest rulers with 6 marks shown above.

Given a Golomb Ruler with n marks we can form a table of the distances that it gives rise to, which by definition must be distinct, as follows. The first row of the table is obtained by taking the difference (larger mark minus smaller mark) of marks one unit from each other; the second row of the table is obtained by taking the difference of marks two units from one another.
 

Using difference sets of various kinds has a long history in combinatorics and geometry. It has ties to the construction of various kinds of block designs and affine and projective planes.

One way to think about a Golomb ruler is to represent each of the marks on the ruler as a vertex of a graph, with that vertex labeled with a number which corresponds to the distance from 0 to the mark on the ruler. Thus, a vertex labeled 4 would mean that there is a mark on the ruler at 4. We can then take two vertices of the graph we produce and join them with an edge which is labeled with the (absolute value) of the difference between the two vertices' labels. Thus, given vertices with labels 4 and 6 we label the edge 2.

The example above (Figure 2) is a dramatic Golomb ruler. With 4 marks we are able to measure all the consecutive integer values, 1, 2, 3, 4, 5, 6. When a Golomb ruler has this property it will be referred to as a perfect Golomb ruler. It turns out there are very few perfect Golomb rulers--in fact, the largest such ruler has 4 marks.

The key idea with regard to Golomb rulers is that they represent distinct distances. However, this means that for 5 or more marks (since there are no perfect Golomb rulers with 5 or more marks) some distances cannot be measured with a Golomb ruler. This has led to the study of other kinds of rulers which trade off various properties of rulers with one another. Rulers with "few" marks will either have to repeat some of the distances they measure or they will have to omit being able to measure lengths from 1 to the length of the ruler.

By a ruler we will mean an increasing sequence of integer marks (no repeats allowed) with the first mark taken as 0. The last mark on a ruler will be its length L. The distances between adjacent marks is usually referred to as a segment. Thus, if there are m marks the ruler will have (m-1) segments.

A ruler is known as complete if it can measure all distances between 1 and the length L of the ruler. Usually, to be complete the ruler will have to repeat some of the distances it measures. Thus, a ruler is called perfect if it is complete and there is no ruler of the same length which has fewer marks. A ruler is called optimal if there exists no perfect ruler with the same number of marks but greater length. A sparse ruler has distance marks missing, yet it can measure distances up to its full length. Wichmann rulers are a special class of rulers which are not always optimal but there are no known optimal rulers with length more than 68 which are not Wichmann rulers. Other kinds of rulers involve putting the marks on a circle rather than along a straight line.

It turns out that finding optimal Golomb rulers is a computationally hard problem. One important recent trend is that there have been some collaborative online efforts to find additional optimal rulers. One of the tantalizing aspects of looking at lists of Golomb rulers is the issue of when there are many optimal rulers with the same number of marks. For example, with 7 marks there are five inequivalent optimal rulers. At the current time the longest Golomb ruler which has been determined to be optimal is one with 26 marks:

0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492

Graceful graphs

A graph is a diagram which consists of dots known as vertices and line segments known as edges, A complete graph is one in which every pair of vertices is joined by an edge. Figure 5 shows a complete graph having 5 vertices.
 

The degree of a vertex in a graph is the number of edges at that vertex. In the graph in Figure 5 all the vertices have degree 4. In a complete graph with n vertices, each vertex has degree (n-1). Since there are n vertices and each edge has exactly two endpoints, the number of edges in a complete graph is n(n-1)/2. This expression should remind you of the one we found for measuring distinct distances for a ruler with k marks.

Suppose we assign non-negative integer numbers to the vertices of a complete graph starting with 0. Now suppose we assign to an edge of the graph the absolute value of the difference between the labels on the edge. If we are able to have the edges now display the labels from one to the number of edges in the graph, we will say that the complete graph has been gracefully labeled. More generally, we will be interested in cases in which G is any connected graph (one for which one can travel between any pair of vertices by moving along edges of the graph). We will say that G has a graceful labeling if its vertices can be assigned labels from 0 to m in such a way that 1. distinct vertices are labeled differently, 2. for each edge of the graph the edges get labeled with the absolute value of the difference of the labels assigned to their endpoints and 3. the numbers from 1 to m each gets used exactly once in the edge-labeling. Figure 6 shows a graceful labeling of a "4-cycle."
 

If we are able to gracefully label a complete graph with n vertices, we have a way to construct a perfect Golomb ruler with n marks! Figure 7 shows such a labeling of the complete graph with 4 vertices.

 

Again, note that a complete graph on k vertices has exactly k(k-1)/2 edges, which is the right number of edges to represent a Golomb ruler with k marks.

Can this graph theory approach help us find Golomb rulers? Let us go back and look at the complete graphs with 2 and 3 vertices.

The Golomb ruler with two marks, 0, 1 would correspond to the complete graph with 2 vertices shown in Figure 8.

 

The Golomb ruler with three marks 0, 1, 3 would correspond to the complete graph with 3 vertices shown in Figure 9. It turns out that by using a graph-labeling point of view (or other combinatorial approaches), it can be seen there are no perfect Golomb rulers with more than 4 marks.

A tree is a special type of graph which is in one piece (one can move between any pair of vertices along edges of the graph) but there are no circuits (no routes of different edges that begin and end at the same vertex). A special type of tree known as a path is shown in Figure 10.

 

This in turn is a special type of tree called a caterpillar. A caterpillar arises from a path by picking vertices along the path and attaching edges at the vertices of the path. Here is an example where we have a path of length 6:
 

Note that in any tree, the number of edges is always exactly one less than the number of vertices, (This is a special case of Euler's famous result, which when applied to graphs that have been drawn in the plane where edges meet at vertices, states that Vertices + Faces - Edges = 2.) It is a rather nice fact that all caterpillars (and hence all paths) have graceful labelings.
 

 

Using the labeling shown in Figures 12 and 13, perhaps you can figure out an algorithm (mechanical procedure) for labeling the vertices of a caterpillar in a graceful way.

Mathematics has many conjectures that are easy to state but have eluded solution for many years. In 1964 Gerhard Ringel raised this question:

Given a fixed tree T with s edges, one can decompose the complete graph on 2s+1 vertices into 2s+1 isomorphic copies of T.

In the same year this conjecture due to Ringel and Anton Kötzig appeared:

Every tree has a graceful labeling.

A rather amazing and simple-to-state connection between the ideas here is a theorem due to Alexander Rosa, dating to 1969.

Theorem (Rosa)

If T is a tree with s edges which can be gracefully labeled then the complete graph with 2s+1 edges can be decomposed into 2s+1 copies of T.

Graceful labelings of graphs is a topic of interest in its own right. Important classes of graphs which are known to admit graceful colorings are n-cubes, wheels, and grid graphs.

There are many variant problems that suggest themselves which are related to the ideas we have introduced. Instead of using one marked ruler to generate nearly all distinct distances, what about using several rulers? In this spirit Figure 14 shows two labeled complete graphs with 4 vertices. Each of these separately can be thought of as giving rise to a ruler which measures distinct distances. One of these rulers would have marks at 0, 8, 9, 12 and would measure distances, 1, 3, 4, 8, 9, 12, while the second of the rulers would have marks at 0, 6, 11, 13 and measure distances 2, 5, 6, 7, 11, 13. Collectively, the rulers measure 12 distances while missing the single distance 10. Note that we cannot have two different rulers which end at the same mark t because then they would both measure t, which would be a repeat for the pair of rulers.
 

Since it is not possible to gracefully label a complete graph with 5 or more vertices another natural question is what is the smallest number of edges that must be removed from a complete graph with 5 or more vertices so that it admits a graceful labeling? It turns out for example, that for the complete graph on 5 vertices this can be accomplished with a single edge being removed (Figure 15).
 

It is easy to check that this vertex labeling generates the labels 1 to 9 on the edges. However, though it may be tempting to think that putting marks at 0, 1, 4, 7 and 9 on a ruler is a Golomb ruler, this is not the case because the difference between 4 and 1 gives the same value as the difference between the vertices labeled 4 and 7. You might try for yourself to find a labeling of the complete graph with 6 vertices with two edges deleted that admits a graceful labeling.

Many other graph-labeling questions have been posed and investigated, and there are many unsolved problems related to them.

From left field

In 1944 two prominent Hungarian mathematicians wrote a paper dealing with number theory that involved an idea due to another Hungarian mathematician, Simon Sidon. The paper by Paul Erdős and Paul Turán discussed sequences now known as Sidon sequences.
 

A sequence (a₀, a₁,...) is a Sidon sequence if none of the pairwise sums a_i + a_j (i ≤ j) are ever the same. Sidon had been led to study this kind of sequence in conjunction with work he was doing about Fourier Series. Interest in Sidon sets concerned for the most part how many elements there could be in a Sidon sequence less than a given number x. Questions of this kind proved complex; progress on the questions in the 1944 paper have been slow in coming. In this paper Erdős and Turán give a method of constructing a Golomb ruler. The construction works for every odd prime p. It works as follows. For each integer k between 0 and p-1 compute the following quantity: 2(p)(k) + (the remainder when k² is divided by p).

Example: p = 5;

k=0; 2(5)(0) + 0 = 0.

k=1; 2(5)1 + 1 = 11.

k=2; 2(5)2 + 4 = 24.

k=3; 2(5)3 + 4 = 34.

k=4; 2(5)4 + 1 = 41.

The claim is that 0, 11, 24, 34, 41 is a Golomb ruler. This is easily checked by computing the differences 11, 24, 34, 41, 13, 23, 30, 10, 17, and 7 and noting that they are all different. This ruler, however, is not optimal for one with 5 marks.

It is intriguing that only quite recently was it observed by Dimitromanolakis Apostolos that there are interesting connections between Sidon sets and Golomb rulers. In fact finite Sidon sets can be used to construct Golomb rulers and vica versa. Here is the easy proof in one direction.

If S is a finite Sidon set, S gives rise to a Golomb ruler. Suppose S is a finite Sidon set but does not give rise to a Golomb ruler. This means that there must be 4 elements of S such that a_i - a_j = a_k - a_l. From this is follows that a_i + a_l = a_k + a_j. However, this contradicts the defining property of a Sidon set that pairwise sums are different. Hence, S must give rise to a Golomb ruler.

Are weird rulers good for anything?

So far I have treated Golomb rulers and graceful number problems as if they were just mathematical curiosities which might entertain mathematics aficionados because of their charm and quick-starting nature. However, in fact, these ideas have found a remarkably rich collection of applications.

Without pursuing these issues in detail other than to point the interested party towards where he/she can find out more information, here are some examples:

* Insight into diffraction patterns that arise in X-ray crystallography

* Convolutional codes

* Radar and sonar

* Costas arrays

These arrays have proved useful in problems dealing with designing radar and sonar systems. They can be regarded as a 2-dimensional generalization of Golomb rulers. The basic idea is to construct n x n matrices whose entries are zeroes and ones where there is a 1 in each row and each column and where all the pairs of vectors between coordinates of the locations (rows, columns) of the ones in the matrix are distinct. These matrices constitute a special subcollection of the permutation matrices which are already an interesting collection of matrices. Here is a Costas array:

0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0

where the coordinates of the cells of interest are (rows numbered from the bottom up, columns from left to right): (1,2), (2,1), (3,3), and (4,4).

* pattern matching and information retrieval

A growing literature is devoted to how to use "seeds" in trying to find efficient ways of extracting patterns from strings. Pattern matching finds many applications in data mining and genomics, in which attempts are made to find important stretches of DNA in different species. One idea is to look in species for strings that are known to code genes in another species.

* codes to synchronize photodetectors

* radar pulse codes

* missile guidance codes

* radio frequency assignment

* radio astronomy

This application involves the placement of antennae for radio telescopes.

The charm of the mathematics of Golomb rulers as well as the many ways that they can be put to practical use suggests that there will be continued interest in this tantalizing area for the foreseeable future.

 

--------------------------------------------------------------------------

This article is dedicated to the memory of my friend Gary Bloom (1940-2009), a doctoral student of Solomon Golomb, who made contributions to Golomb rulers and related graph-coloring problems.
 

References

Atkinson, M. and A. Hassenklover, Sets of integers with distinct difference, School of Computer Science, Carlton University, Report SCS-TR-63, 1984.

Atkinson, M. and N. Santoro, J. Urrutia, Integer Sets with Distinct Sums and Differences and Carrier Frequency Assignments for Nonlinear Repeaters, IEEE Trans. Comm. 34 (1986) 614-617.

Babcock, W., Intermodulation interference in radio systems, Bell System Technical Journal, 1953, p. 63-73.
Bloom, G. and S. Golomb, Applications of numbered undirected graphs, Proceedings of IEEE, 65 (1977) 562-570.

Bloom, G. A counterexample to a theorem of S. Piccard, Journal of Combinatorial Theory, 22 (1977) 378-379.

Bloom, G. and S. Golomb, Numbered complete graphs, unusual rulers, and assorted applications, Theory and Applications of Graphs, Vol. 642, Lecture Notes in Mathematics, Springer-Verlag, 1978, pp. 53-65.

Chen, W. and T. Klove, Lower bounds on multiple difference sets, Discrete Mathematics, 98 (1991) 9-21.

Chen, Z., Further results on difference triangle sets, IEEE Transactions on Information Theory, It-40 (1994) 1268-1270.

Christophe, M. and J. Brigitte, "Equivalence of some LP-based lower bounds for the Golomb ruler problem, Discrete Applied Mathematics 154 (2006) 120--144.

Colbourn, C. and J. Dinitz, (Eds.). CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL, 1996.

Dewdney, A. K. "Computer Recreations." Sci. Amer. 85 (253) 16.

Dewdney, A. K. "Computer Recreations." Sci. Amer. 254, 20, Mar. 1986.

Dollas, A. and W. 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) 379-382.

Fang, R. and W. Sandrin, Carrier frequency assignment for non-linear repeaters, Comsat Technical Review, 7(1977) 227-245.

Gardner, M., Mathematical games, Scientific American, March 1972, p. 108-112, and June 1972, p. 116-118.

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

Golomb, S., There are no further counterexamples to S. Piccard's Theorem, IEEE Transactions in Information Theory, 53 (2007) 2864-2867.

Guy, R., Modular Difference Sets and Error Correcting Codes, §C10 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, 1994, pp. 118-121.

Hansen P. and J. Brigitte and M.Christophe, On Lower Bounds for Numbered Complete Graphs, Discrete Applied Mathematics 94 (1999) 205-225.

Klieber, E., Some difference triangles for constructing self-orthogonal codes, IEEE Transactions on Information Theory, It-16 (1970) 237-238.

Klove, T., Bounds on the size of optimal difference triangle sets, IEEE Transactions on Information Theory, It-34 (1988) 355-361.

Klove, T., Bounds and constructions for difference triangle sets, IEEE Transactions on Information Theory, It-35 (1989) 879-886.

Kotzig, A. and P. Laufer, Sum Triangles of Natural Numbers Having Minimum Top, Ars. Combin., 1986 (21) 5-13,.

Lam, A. and D.Sarwate, On optimal time-hopping patterns, IEEE Transactions on Communications, COM-36 (1988), 380-382.

Lorentzen, R. and R. Nilsen, Application of linear programming to the optimal difference triangle set problem, IEEE Transactions on Information Theory, It-37 (1991) 1486-1488.

Martin, G., Optimal convolutional self-orthogonal codes with an application to digital radio, Proc. IEEE International Conference on Communications, (1985) 1249-1253.

Robinson, A. and A. Bernstein, A class of binary recurrent codes with limited error propagation, IEEE Transactions on Information Theory, It-13(1967) 106-113.

Robinson, J, Optimum Golomb rulers, IEEE Transactions on Computers, C-28 (1979), 943-944.

Robinson, J., Addendum to "Optimum Golomb rulers, IEEE Transactions on Computers, C-32( 1983) 201.

Robinson, J., Golomb rectangles, IEEE Transactions on Information Theory, It-31 (1985), 781-787.

Robinson, J., Golomb rectangles as folded rulers, IEEE Transactions on Information Theory, It-43 (1997) 290-293.

Rodgers, D., Addition theorems for perfect systems of difference sets, Journal London Mathematical Society, 23 (1981) 385-395.

Shearer, J., Some new optimum Golomb rulers, IEEE Transactions on Information Theory, It-36 (1990) 183-184.

Shearer, J., Some new optimum Golomb rectangles, Electronic Journal of Combinatorics, 2( 1995) #R12.

Shearer, J., Some New Difference Triangle Sets, Journal of Combinatorial Mathematics and Combinatorial Computing, 27(1998), p. 65-76.

Shearer, J., Improved LP Lower Bounds for Difference Triangle Sets, The Electronic Journal of Combinatorics, 6 (1999) #R31.

Wichmann, B., A note on restricted difference bases, J. London Math. Soc., 38 (1962) 465-466

Zhi, Z, and F. Pingzhi and J. Fan, Disjoint difference sets, difference triangle sets, and related codes, IEEE Transactions on Information Theory, It-38 (1992) 518-522.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be found via the ACM Portal, which also provides bibliographic services.