[RC5] OGRs meet D.Net, was "sexy" projects

gindrup at okway.okstate.edu gindrup at okway.okstate.edu
Mon Mar 2 10:19:19 EST 1998

     Hmm...  An off the top of my head OGR mini FAQ.
     A ruler is a collection (without repetitions) of positive integers.  
     This collection is to be interpreted as the series of positions of 
     marks on a real, wood (or metal) ruler.  For example. {0, 19,4,15} 
     represents a ruler with four marks at 0, 4, 15, and 19 (inches, 
     centimeters, parsecs, whatever unit you like) units.
     By convention, the first mark of a ruler is at 0.  This has no 
     effect on OGRs which only care about relative positions of marks.
     (There is a different way of representing rulers where you record 
     the distances between successive marks.  This representation isn't 
     any easier or harder to use than the one given.  In fact, the one 
     can be generated from the other in o(kn) time, where k is the 
     (average) time to load a register and do a subtraction.)
     A "n-mark ruler" is a ruler of n (distinct) integers.  The above 
     ruler is a 4-mark ruler.
     The set of measurements of a ruler is the (multi-)set of distances 
     between each pair of (not necessarily adjacent) marks (without 
     repetitions).  For example, using the 4-mark ruler above, the set of 
     measurements is {4, 15, 19, 11, 15, 4}.
     The set of distinct measurements is the set of measurements with 
     repetitions removed.  Using our example, the set of distinct 
     measurements is {4, 11, 15, 19}, notice that the distance between 
     the marks at 0 and 15 is the same as the distance between the marks 
     at 4 and 19, but we only count that difference (15) once.
     A Golomb ruler (GR) is any ruler whose set of measurements is the 
     same as its set of distinct measurements.  Our example is not a GR.  
     {0, 1, 3} is a GR, since its set of measurements is {1, 2, 3} (i.e., 
     contains no repetitions).
     One can make many GRs with differing numbers of marks.  In fact, the 
     ruler with marks at 0 and (2^n)+1 for n=0 to k is a k+2-mark GR.  
     (Each successive mark is farther from any other mark than any other 
     pair of marks is.)
     So, let's imagine we had a collection of all 5-mark GRs in a bag.  
     Which one is the shortest?
     An Optimal GR of n-marks (OGR-n) is the shortest n-mark GR.
     Here is a short table of OGRs:
     OGR- 1    0   {0}
     OGR- 2    1   {0,1}
     OGR- 3    3   {0,1,3}
     OGR- 4    6   {0,1,4,6}
     OGR- 5   11   {0,1,4,9,11} and {0,2,7,8,11}
     OGR- 6   17   {0,1,4,10,12,17} and 3 others
     OGR- 7   25   {0,1,4,10,18,23,25} and 4 others
     OGR- 8   34   ...
     OGR- 9   44
     OGR-10   55
     OGR-11   72
     OGR-12   85
     OGR-13  106
     OGR-14  127
     OGR-15  151
     OGR-16  177
     OGR-17  199
     OGR-18  216
     OGR-19  246
     OGR-20  283
     OGR-21    ?  (<= 332)
     OGR-22    ?  (<= 358)
     OGR-23    ?  (<= 372)
     OGR-24    ?  (<= 425)
     Notice that OGRs are not unique for 5 or more marks.  They are never 
     *actually* unique because the mirror image of an OGR is an OGR.  It 
     is a convention that of the two, the one with the smaller second 
     mark is listed.  (Thus, {0,1,3} and not {0,2,3} for OGR-3.)
     The important property of a GR for applications is that no pair of 
     marks is the same distance apart as a different pair of marks.  For 
     radio astronomy, this means that an array of telescopes ranged out 
     at the marks of a GR collect maximum interferometric data (due to 
     lack of phase correlationscaused by matched spatial separations).  
     If they're arrayed on an OGR, they do the same thing, but take up 
     the least amount of space.
     This spatial decorrelation has been used in the X-ray diffraction 
     analysis of crystal structures.
     Distribution of radio transmission bandwidth based on OGRs can 
     reduce 3rd order intermodulation interference.  A few modifications 
     can also remove 5th order interference.
     OGRs's measurement sets can be used to generate self-orthogonal 
     (error correcting) codes.
     Pulse Phase Modulation communications use OGRs to maximize signal 
     correlation (to the correct desired decoding) while minimizing pulse 
     sequence lengths.
     Open Questions:
     Except for a pair of OGR-6's are there (other) pairs of OGRs with 
     different (non-mirror image) marks but the same set of measurements? 
      Professor Golomb has offered an award for the production of a pair 
     of same-difference-set non-mirror image OGRs of $100.
     What are the best upper and lower bounds on the length of OGR-n 
     (when OGR-n is not explicitly known)?
     Do OGRs represent "fixed points" of some algebraic structure?
            -- Eric Gindrup ! gindrup at okway.okstate.edu

______________________________ Reply Separator _________________________________
Subject: Re: [RC5] OGRs meet D.Net, was "sexy" projects 
Author:  <rc5 at llamas.net > at SMTP
Date:    2/28/98 12:59 PM

At 12:32 PM 2/28/1998 -0500, you wrote: 
>Thank you for the replies!  I am so glad to see that there is a large 
>interest in OGRs.  I will attempt to reply to all of your questions in 
>this one post...
>> Jason, for those of us who are laymen (me), could you 
>> please describe what an OGR is, and its application?  You 
>> mentioned something about astronomy and astrophysics, but 
>> not much more besides how big a problem it could be.
Is OGR a project that gets helped by knowing the results of other answers 
found by other computers?  I would think that would give d.net's clients a 
problem right now.
Nathan Barber
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net 
rc5-digest subscribers replace rc5 with rc5-digest
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list