Conference rusure::math

Did you use the procedure given the Dewdney's column, or did you enhance
it in some way?  Also, Dewdney states the search can be started with a mark
at distance one or two from the beginning.  All I can figure out is that
perhaps this is because a shortest Golomb ruler must have a one at one end
and a two at the other end.  Do you understand why Dewdney says that?


				-- edp

No, I dont understand exactly what was said, or why he said it.
Also, the search for a 14-mark ruler of length 127 (or less) is
now searching for rulers with a first mark at 3.  Because of the
search order of the algorithm, this implies I've got a bug, or
the upper bound on Gl(14) was misreported, or a Golomb ruler of
length 14 must have a first mark at 3 (or beyond).  By symmetry,
this applies to either end of the ruler.

Here is the reason the search may begin with two:  Starting with one checks
for each possible ruler with a first mark at one or greater (since the procedure
may eventually back up and increase the one).  Clearly, every possible ruler
as a first mark at one or greater.  But if the search begins with two, every
possible ruler with a first mark at two or greater is checked.  But every
ruler with a first mark at one could be reversed to have a first mark at
two or greater, so this latter search gets such rulers.


				-- edp

There may be a better way to speed up the process than starting with a
separation of two.  Consider rulers with 14 marks.  Count the number of marks on
each side if the middle of the ruler.  One side of the ruler must have a number
of marks not greater than the other side.  Thus, if we consider only rulers
with seven or more marks by the time we reach the midpoint, we will get all
rulers (since any ruler with less than seven marks by the midpoint could
be reversed to get one of the rulers we would consider).  The only problem
is not knowing where the midpoint is.  However, there is, according to the
_Scientific American_ article, a ruler of length 127.  So any midpoint must
be at or before 63.5.  The number of marks from the actual midpoint can only
increase by 63.5, so we need only consider rulers for which the first seven
or more marks add up to less than 64.


				-- edp

Another approach is a 'meet in the middle approach'.  That is, generate
all rulers of seven marks, and all with eight marks, sort them (somehow),
and look for two sub-rulers that combine to form a short 14 mark ruler.

Here's the best guess so far for 14 marks:

	127   0 4 2 14 15 17 7 18 1 8 3 10 23 5

If Gl(14) < 127, then the first mark is at 5 or beyond (on either/both ends).

Newsgroups: net.math,net.puzzle
Path: decwrl!decvax!wanginst!apollo!johnf
Subject: Golomb Rulers
Posted: 18 Jan 86 04:54:01 GMT
Organization: Apollo Computer, Chelmsford, Mass.
Xref: decwrl net.math:2446 net.puzzle:1318
 
Has anyone else out there done any investigation of Golomb Rulers ?
(Briefly, a Golomb Ruler is a ruler of integral length, with marks
at integral intervals such that the distances between any pair of
marks are all different. See the computer recreations section of
the December issue of Scientific American for more details).
I can add the following information to that which is given there:
    The lower bound for rulers with 14 marks is 127.
    The lower bound for rulers with 15 marks is at least 137.
Both of these values come from an exhaustive search program I wrote
(which is still running). It took twenty hours (on an Apollo DSP160,
which is about a VAX11/780 equivalent) to verify the results given
for rulers of up to 13 marks. I am quite proud of this program, as
the Scientific American article mentioned that the program that was
run to verify that 106 was the lower bound for rulers with 13 marks
took a MONTH of CPU time!  However, I would still like to improve
the running time of the program, as the search time gets longer and
longer as the rulers increase in length (for example, it took 41
hours to verify that there were no rulers of length 136 with 15 marks).
In the article mention is made of a formula that gives a lower bound
for the length of a ruler with M marks, but the formula is not given.
[The values quoted for the lower bound for rulers with 14 to 24 marks
are 114,133,154,177,201,227,254,283,314,346 and 380]. If anyone out
there knows what the formula is (and how it is derived) I would like
to hear from them, as a good lower bound formula would enable me to
reduce the running time of the program considerably!
 
Another snippet of information:  If I have a ruler of length L that
has M marks, I can obviously get rulers of length L with any number
of marks less tham M (just delete some of the marks). It is usually
true that if I can find a ruler of length L with M marks then I can
also find rulers of length L+n with M marks for all positive values
of n. So far I have found the following exceptions to this rule:
 
   Marks   Minimum L   Exceptions
   0 - 9                NONE
    10        55         56  57
    11        72         73
    12        85         86  87  88  89
    13       106        107 108
    14       127        NONE
 
Hypothesis 1:   There exists some value of M, above which there will be
                no exception cases.
 
Hypothesis 2:   For arbitrary M there is some function of M which gives
                a minimum value of n above which there are no exceptions,
                and which is of magnitude o(M). [Little-O, for those of
                you reading this on upper-case-only terminals].
 
Can anybody prove (or disprove) these hypotheses?

"apollo!johnf" in the last note is probably ex-DECie, John Francis.

Newsgroups: net.math,net.puzzle
Path: decwrl!decvax!genrad!panda!talcott!harvard!bbnccv!bbncc5!jr
Subject: Re: Golomb Rulers
Posted: 27 Jan 86 17:01:35 GMT
Organization: Bolt Beranek and Newman, Cambridge, MA
Xref: decwrl net.math:2518 net.puzzle:1327
 
  Date:     Mon, 27 Jan 86 9:52:18 EST
  From:     Ken Sedgwick <[email protected]>
  To:       [email protected], [email protected], [email protected], [email protected], 
	    [email protected], [email protected], [email protected], 
	    [email protected]
  Subject:  Length 14 Exhausted!
 
	  The shortest ruler with 14 marks has been found by titan.
	  The run lasted 30 hours on 79 processors.
	  -> 5 28 38 41 49 50 68 75 92 107 121 123 127
 
					  Ken Sedgwick
 
Titan is a BBN Butterfly multiprocessor, with 128 MC68000 processors.
I don't know why Ken used only 79.  I believe it found the 13-mark
solution in about 20 minutes.
 
/jr

Newsgroups: net.math
Path: decwrl!decvax!genrad!panda!talcott!harvard!seismo!rochester!pt.cs.cmu.edu!a.sei.cmu.edu!tgl
Subject: New Golomb ruler data point
Posted: 19 Feb 86 18:09:48 GMT
Organization: Carnegie-Mellon University, CS/RI
 
I have found a 15-mark Golomb ruler which is shorter than the
best previously known according to the December Sci. Am. article.
It is
 
spaces:    3   1  18  32  10   6  11  13  15   8  21   5   7   2
marks:   0   3   4  22  54  64  70  81  94 109 117 138 143 150 152
 
This is of length 152, whereas the best previously known was 155.
 
This was found by an exhaustive search program running on a 68020.
It's still cranking along, and will be for quite a while yet.
I can state that there are no shorter 15-mark rulers having a space
of length 2 at either end...
 
				tom lane
-----
ARPA: lane@{CMU-CS-A.ARPA|A.CS.CMU.EDU}
UUCP: ...!seismo!cmu-cs-a!lane

Newsgroups: net.math
Path: decwrl!decvax!minow
Subject: Re: New Golomb ruler data point
Posted: 22 Feb 86 00:02:37 GMT
Organization: DEC - ULTRIX Engineering Group
 
From March '86 Scientific American:
 
  "... during the Christmas Holidays, James B. Shearer of the IBM
  Thomas J. Watson Research Center programmed an idle computer to
  search exhaustively for rulers, and the computer has now turned
  up Golomb rulesr with 14 and 15 marks.  The 14-mark Golumb ruler
  is 127 units long and has marks at 0, 5, 28, 38, 41, 49, 50, 68,
  75, 92, 107, 121, 123, and 127.  The 15-mark ruler is 151 units
  long and has marks at 0, 6, 7, 15, 28, 40, 51, 75, 89, 92, 94,
  121, 131, 147, and 151.  Shearer writes that he saved much computing
  time by assuming the middle mark on the ruler is to the left of
  the geometric middle."
 
Quoted by
Martin Minow
decvax!minow

I've some thoughts on how to exhaustively search for a counter-example
of the 7-mark problem described at the end of .0.  Stop by if you're
interested.

    As Gilbert and I described in a talk after one of the math noters
    dinners, we have a program that searches for pairs of rulers that are
    not identical or reflections of each other yet measure the same
    distances.  These are called homometric Golomb rulers.  When we gave
    the talk, our program had exhausted the possibilities for 7-, 8-, 9-,
    and 10-mark homometric rulers without finding any.  The 11-mark case
    finished in 10 days of CPU-time on a DECstation 3100, without finding
    any.  I altered the program so it could be interrupted and pursue
    different branches of the search, so it is now running on nine
    processors.
    
    The search has examined 1.6 billion states without finding any 12-mark
    homometric rulers.  It's consumed about 20 million CPU-seconds and
    executed about one-fifth of a quadrillion instructions.  I'm hoping its
    close to half done.
    
    
    				-- edp

    .13
    
    I assume you'll show that the method you are using to "search" for
    that ruler is not "missing" some states? i.e. that you actually 
    looked at all the possibilities. you got'a prove that, iam assuming..
    
    /nasser
    who_have_no_idea_what_a_homoetric_Golomb_ruler_is_but_it_sound_interesting
    

    Re .14:
    
    The measurements of each Golomb ruler are the distances between pairs
    of marks.  For a pair of Golomb rulers, there is a total, 1-1, onto
    function that maps each pair of marks from one ruler to the pair of
    marks on the other ruler that measures the same distance.  So to search
    every Golomb ruler, regardless of size, we only have to search the
    total, 1-1, onto functions from the C(n,2) pairs of one ruler to the
    C(n,2) pairs to the other ruler.  So there's a finite number of things
    to search.  Our program tries various assignments for the function and
    rejects them if it can prove they won't work.  Basically, potential
    assignments yield sets of linear equations, which we can reduce and try
    to solve.
    
    
    				-- edp

    Gilbert and I are about the send the final version of our paper to the
    publisher.  Could somebody double-check some calculations for me:
    
    	Take the points (2,0), (-2,0), (0,2*sqrt(3)), (-2,2*sqrt(3)),
    	(3,sqrt(3)), (-1,-sqrt(3)).
    
    	Multiply them by -sqrt(3)*sqrt(a^2+b^2-ab)/3 and project them
    	onto the line y=sqrt(3)*(2a-b)*x/3b.
    
    	Where do those points fall on the line, measured as a signed
    	distance from the origin?
    
    	If you negate the x coordinates and then multiply the points
    	and project them onto the line, where do they fall on the line
    	then?
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To get PGP, FTP /pub/unix/security/crypt/pgp23A.zip from ftp.funet.fi.
For FTP access, mail "help" message to DECWRL::FTPmail or open Upsar::Gateways.

    I get, with Maple's help:

	(2,0) ->	-b
	(-2,0) ->	b
	(0,2*s3) ->	2a - b
	(-2, 2*s3) ->	2a
	(2, 2*s3) ->	2a - 2b
	(3, s3) ->	a - 2b
	(-3, s3) ->	a + b
	(-1, -s3) ->	-a + b
	(1, -s3) ->	-a
	(x, y) ->	a(y*s3/3) - b((3x + s3*y)/6)

    where s3 = sqrt(3)

				Topher

    Re .17: 
    
    Well, you gave me a brief scare, but it was only a different choice of
    sign.  Looks like I still can project points onto lines.  Thanks.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To get PGP, FTP /pub/unix/security/crypt/pgp23A.zip from ftp.funet.fi.
For FTP access, mail "help" message to DECWRL::FTPmail or open Upsar::Gateways.