[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.

Definitions:
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

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:
>D.Netters-
>
>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.

Jason,

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

```