Weird RulersHopefully 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...
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 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.
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?
(Photograph courtesy of Solomon Golomb)
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.
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.
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.
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.
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.
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.
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.
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:
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.
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.
(Paul Erdős and Paul Turán)
A sequence (a0, a1,...) is a Sidon sequence if none of the pairwise sums ai + aj (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 k2 is divided by p).
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.
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.
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.
The AMS encourages your comments, and hopes you will join the discussions. We review comments before they're posted, and those that are offensive, abusive, off-topic or promoting a commercial product, person or website will not be posted. Expressing disagreement is fine, but mutual respect is required.
ReferencesAtkinson, 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.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance