|
Click here for PDF version.
Background
Graceful graphs are the creation of Solomon W. Golomb, professor
of electrical engineering and mathematics at the University of
Southern California.
A graceful graph is a graph of points and connecting lines which
can be numbered in a certain way. Let us say the graph has p points and e lines (e for edges) connecting them. Each of the points is assigned
an integer. Each of the lines is labeled with the difference between
the two integers of the points which it connects. Then, if the
numbers corresponding with the lines run from 0 through e, then the graph is said to be graceful. See Figure B-1 for an
example of a graceful graph.
Let us take a special case of graphs in which every point is connected
to every other point. These graphs, some of which are shown in
Figure B-2A, are called complete graphs. These special graphs
may be viewed in a less abstract way as follows: Form a ruler
with p different divisions, each division corresponding to a number
on the graph. See Figure B-2B for examples. Such graphs where
the ruler can measure each of, but only, the distances from 0
through the length of the ruler are called perfect Golomb rulers.
There are no perfect Golomb rulers with more than 4 divisions
(proof is shown in the folder). Golomb rulers with more than 4
divisions (not perfect Golomb rulers) are those which measure
unique lengths. In other words, the ruler in Figure B-3A is a
Golomb ruler, but the one in Figure B-3B is not.
Throughout this project, a ruler is represented by a sequence
of numbers. Each number represents the length of a division on
a ruler. For example, see Figure B-4, which shows the ruler 1,
3, 5, 2.
Purpose
By selecting a long enough ruler and dividing it in the right
way, it is fairly easy to construct a Golomb ruler. The purpose
of this project, therefore, is to find a way of constructing the
shortest possible Golomb rulers.
For example, Figure 1-A shows a Golomb ruler with 6 divisions.
It is not, however, the shortest such ruler. Figure 1-B displays
the shortest possible 6-division Golomb rulers. We want to find
a way of finding the shortest possible Golomb rulers for any number
of divisions.
Hypothesis
Previous searches have revealed minimum-length Golomb rulers for
up to 12 divisions. These are shown in Figure 2.
At first glance, the lengths have no apparent pattern to them:
3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106. Upon further staring,
nothing clicks. This is not a simple problem.
To begin with, as stated before, there are no perfect Golomb rulers
with more than 4 divisions. Let us analyze these impossible Golomb
rulers. A Golomb ruler with p divisions measures a certain number of distances, as shown in
Figure 3. A pattern is easily seen: 1, 3, 6, 10, 15, etc. The
differences between these numbers is 1, 2, 3, 4, 5. So these numbers
are simply the sum of the numbers 1 through p . This is commonly-known (among mathematicians, at least) as
(p)(p+1)/2 . A proof is shown in the folder. In any case, the point is that
these (1, 3, 6, 10, 15, etc.) would be the lengths of the rulers if all Golomb rulers were perfect
Golomb rulers. A non-perfect Golomb ruler, since it must - by
definition - measure unique distances, must have a size greater
than 1, 3, 6, etc. (depending on its number of divisions).
The actual lengths 3, 6, 11, 17, 25... are very close to the perfect
series 3, 6, 10, 15, 21. In fact, the differences are 0, 0, 1,
2, 4, 6, 8, 10, 17, 19, 28. Still, however, no pattern is easily
recognizable.
People jokingly say scientists either change data to fit their
hypothesis or change their hypothesis to fit the data. Having
looked for a clue to a solution and having found none, I won't
hazard an unfounded guess.
Methods
To help in the search for a method of developing Golomb rulers,
I began to write a series of computer programs in the C programming
language for the Apple Macintosh. All of these programs are listed
separately in the folder. While I was working on these programs,
I also began looking into establishing upper and lower bounds
for the lengths of Golomb rulers. The search is documented more
completely in the folder. A few proofs for the non-existence of
certain rulers are also shown in the folder.
The main problem in writing the computer programs was that much
attention had to be given to speed. At first, the time factor
was not known. After the bugs were worked out of the program and
the program was tested, however, it was clear that the program
would be of almost no use in its present form. So the program
had to be completely revamped - one whole section of it completely
rewritten - and then debugged yet again.
Even after a speed increase of at least 10 times, the program
was still too slow to provide much useful information. So the
program was modified to skip certain sets of numbers. A different
modification let the user enter the numbers to check.
The modified program was then stripped to the bone so that it
only checked for Golombicity (whether or not it's a Golomb ruler)
for one user-entered ruler. Still another program averaged the
division lengths in certain positions of a Golomb ruler. For example,
if the program found two rulers, 1 3 5 2 and 2 5 1 3, then the
average of those two rulers would be 1.5 4 3 2.5. The purpose
of this was to hopefully provide information on the general structure
of Golomb rulers.
Results
All of the results from the computer programs are listed in the
folder. The listings were analyzed and different theories were
tested, but most failed.
The folder contains several proofs concerning Golomb rulers. There
is a proof that there are no perfect Golomb rulers with more than
4 divisions. There is a proof that there are no Golomb rulers
with more than 6 divisions which have a length of (p(p+1)/2)+1 , where p is the number of divisions. That is the highest the lower bound
was computed to.
Clearly, a ruler with divisions of lengths 1, 2, 4, 8, 16, etc.
is a Golomb ruler. A formal proof is shown in the folder. Also,
a ruler such as 1, 2, 4, 5 or 1, 2, 4, 8, 9 is Golomb (proof also
shown). So the upper bound was lowered to 2p-1 + 2p-2. This was
clearly a terrible upper bound. The best method - by far - that
I could find of constructing Golomb rulers is what I call the
Middle Number Method.
After looking at the different Golomb rulers, it seemed as if
many followed a similar pattern. The numbers are almost in numerical
order if we count in this manner: left, right, left, right, beginning
on the outside and ending up in the middle. For example, the ruler
1 3 6 5 2 would be read 1, 2, 3, 5, 6. The Middle Number Method
starts with a Golomb ruler with 3 divisions, such as 1 3 2, and
tries to find a number larger than any of the others to place
in the middle so that the ruler remains Golomb. If we start with
1 3 2, then the rulers continue 1 3 5 2, and 1 3 6 5 2 and 1 3
6 8 5 2 and so on. A proof that the Middle Number Method works
(that there always exists such a number to place in the middle)
is located in the folder. The listing of a computer program to
find these rulers is also in the folder.
All of the lower and upper bounds are shown in Figure 4, along
with the results from the Middle Number Method.
Observations
As expected, there are more Golomb rulers with longer lengths.
This isn't simply because there are more rulers (although that
is part of the reason); the greater length means that the division
lengths are more distinct. For example, if we have a ruler with
division lengths of 1, 2, 3, and 27, then the 27 portion can be
placed anywhere in the ruler and not change the Golombicity of
the ruler. On the other hand, if the ruler had lengths 1, 2, 3,
5 then the 5 portion is restrictive to the ruler because the 2
cannot be placed next to the 3.
It would seem that if we start the Middle Number Method with a
longer 3-division ruler, then all of the resulting lengths would
be longer. This is not the case. For up to about 25 divisions,
it holds true. However, using 1 3 2 as our beginning ruler the
36-division ruler is 3182 units long, whereas with the 1 4 3 beginning
ruler the 36-division ruler is 3134 units long. And the difference
gets larger for larger rulers. For 40 divisions the difference
is 4490 to 4264.
As far as the averaging data goes, it appears that smaller rulers
are more distinct, while larger rulers are very different, causing
the average ruler to look very dull - as in 2 5 5 5 5 in one case.
Figure 5 compares the different average-ruler results. Due to
a feature of the program, only rulers in which the first division
is shorter than the last will the ruler be counted as Golomb.
For example, it will count 1 3 5 2 but not 2 5 3 1. In this manner,
mirror-images are not counted as two, but it also forces the average
of the last division to be at least 2.
Conclusions
I failed to find a method of constructing the shortest possible Golomb rulers. I did, however, find an algorithm for
constructing Golomb rulers of any number of divisions - the Middle
Number Method. Also, I created a lower bound for the lengths of
Golomb rulers. This will be helpful in the search, as it will
avoid wasting time looking for non-existent Golomb rulers.
Proof_machine.c, still being programmed, should provide a quick
way of proving the non-existence of certain Golomb rulers and
possibly provide a way of raising the lower bound. A preliminary
listing is located in the folder.
Finally, further analysis of the results of the programs used
in this project, along with more running time on a faster computer
(perhaps a rented Macintosh II), and a little luck should provide
even shorter Golomb rulers than the shortest ones known at this
time.
Significance
The following is an excerpt from a Scientific American article
dealing with Golomb rulers (see folder for complete article).
Radio astronomy makes occasional use of Golomb rulers in the resolution
of distant radio sources and in the measurement of our own planet.
In the first case a number of antennas are placed along a straight
line several kilometers long. The antenna positions correspond
to the marks on a Golomb ruler. To locate a distant radio source,
it is essential to determine the angle between the antenna baseline
and the direction of the wave fronts arriving from the source.
The antennas are all observing at a given wavelength. The precise
time at which each wave in the incoming signal arrived at each
antenna can be determined by analysis of the tape that captures
the incoming signal. The total number of wavelengths between a
given pair of antennas is called the total phase difference. It
is normally composed of an integer and a fractional part called
the phase difference. If the total phase difference can be reconstructed,
the sought-for angle between the source and the baseline is easily
calculated from the observing wavelength and c , the speed of light. Each pair of antennas, however, can only
yield the phase difference itself, not the total phase difference.
In truth, it is Fourier analysis that recaptures the total phase
difference from the many pairs of antenna recordings. But if the
distance between one pair of antennas is the same or nearly the
same as the distance between another pair, the two pairs provide
the same phase-difference information. Redundancy of information
means its loss. The accuracy of the source-angle computation is
greatest if each antenna pair records a different phase difference;
this condition is achieved by in effect placing the antennas on
the marks of a Golomb ruler.
Okay, so if you didn't get all that mumbo-jumbo, in essence this
is what it says: if radio antenna are placed on the marks of a
Golomb ruler, then they get more accurate results. So the search
for Golomb rulers does have significance.
Possible Extensions
There are several possible extensions to this project.
To begin with, this project deals only with Golomb rulers. This
is only a scratch on the surface of graceful graphs. This project
could explore the properties of graceful graphs. Is it possible
to tell if a graph is graceful simply by looking at it?
A different approach to the Golomb ruler problem could be pursued.
Instead of using a constant number of divisions and searching
for the shortest length, we could start with a constant length
and see how many divisions (and of what length) we need so that
we can measure every length from 1 to the length of the ruler.
These would not be Golomb rulers, as they would measure some distances
more than once. But the problem would be of a similar nature.
Finally, Sophie Piccard, a Swiss mathematician, in 1939 propounded
a "theorem" stating that two rulers measuring the same set of
distinct distances must be the same rulers. The theorem fails
for 5 divisions. The theorem has not been disproven for longer
rulers. I have begun work on a computer program to find such a
ruler, but as yet have not completed it. A preliminary listing
of the program is located in the folder. |
