## 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...
Joseph Malkevitch
## Introduction
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 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. Figure 2
In fact, standard rulers also are "marred" by the fact that they use numbers as labels for the markings on the ruler.
Figure 3
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. ## Getting started
Let us start with a bit of combinatorics--counting. If one has
There are
Both of these expressions can be read as giving the number of ways that
Figure 4
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. ## Graceful graphs
A graph is a diagram which consists of dots known as
Figure 5
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 Figure 6
If we are able to gracefully label a complete graph with Figure 7
Again, note that a complete graph on Figure 8
Figure 9
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.
Figure 10
This in turn is a special type of tree called a
Figure 11
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.
Figure 12
Figure 13 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: 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.(a) (b) Figure 14
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). 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
(Paul Erdős and Paul Turán)
A sequence ( 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^{2} 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. a = _{j}a - _{k}a. From this is follows that _{l}a + _{i}a= _{l} a + _{k}a. However, this contradicts the defining property of a Sidon set that pairwise sums are different. Hence, S must give rise to a Golomb ruler._{j}## 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.
Joseph Malkevitch |
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 |