11
$\begingroup$

A Golomb ruler of order $n$ is a straight line with $n$ marks (at integer locations) such that no two pairs of marks are the same distance apart.

We can extend the concept to circles. Place $n$ marks on a circle (at integer locations) such that no two pairs of marks are the same distance apart going clockwise or counter-clockwise. I will call this a Golomb circle of order $n$. A Golomb circle of order $n$ is perfect if it can measure all distances from 1 to $n(n-1)$, inclusive. Here is a perfect Golomb circle of order 3 as it can measure all distances from 1 to 6:

enter image description here

Here are all its pairwise distances going in a clockwise direction:

$A \rightarrow B = 1$
$A \rightarrow C = 3$
$B \rightarrow A = 6$
$B \rightarrow C = 2$
$C \rightarrow A = 4$
$C \rightarrow B = 5$

Questions:

  1. Can you find a perfect Golomb circle of order 5?
  2. What is the largest $n$ such that there exists a perfect Golomb circle of order $n$?
  3. What is the largest non-prime $n$ such that there exists a perfect Golomb circle of order $n$?
$\endgroup$
  • $\begingroup$ How does measuring work? Can [2,3] be used to measure a distance of 1? $\endgroup$ – daw May 7 at 7:16
  • $\begingroup$ I.e., two points on the circle with distance 2,3. Distance 1 can be measured by subtracting $\endgroup$ – daw May 7 at 7:21
  • 2
    $\begingroup$ From what I read on this site there probably is no largest $n$ for a perfect modular Golomb ruler. $\endgroup$ – Jaap Scherphuis May 7 at 8:23
  • 2
    $\begingroup$ The site I linked used a method for generating perfect modular Golomb rulers for $n=p^k+1$, i.e. a prime power plus 1. Apart from $3$, these are never prime. $\endgroup$ – Jaap Scherphuis May 7 at 8:43
  • 1
    $\begingroup$ @DmitryKamenetsky I have added a concrete answer if you would like to check it out. $\endgroup$ – Yuzuriha Inori May 7 at 10:37
24
+100
$\begingroup$

Complete first answer:

Yes there exists one for order 5. Consider the combination $1,3,10,2,5$.

Partial second answer:

A perfect circle of order 98 :

$$1, 2, 34, 15, 139, 117, 24, 101, 481, 5, 65, 109, 62, 76, 7, 362, 78, 45, 9, 23, 18, 53, 104, 8, 161, 17, 25, 316, 255, 147, 199, 129, 279, 58, 131, 20, 73, 391, 6, 38, 114, 4, 217, 10, 72, 120, 57, 187, 79, 11, 122, 92, 61, 27, 140, 30, 75, 16, 234, 300, 22, 318, 48, 220, 19, 14, 86, 143, 142, 63, 64, 200, 160, 97, 113, 81, 87, 28, 98, 150, 35, 31, 68, 12, 55, 29, 40, 223, 208, 43, 46, 13, 26, 21, 116, 56, 74, 107$$

Complete second and third answer :

Projective geometry, specifically, semi-affine planes worked! There is no upper bound for either prime or non prime orders.

I have no non-technical reason why it is so as it did require a bit of combinatorial geometry, but let's see:

Once you have a Golomb circle, you can "shift" the elements modulo something and get more Golomb circles. These shifts form what is known as a semi-linear space, which is basically a part of finite geometry. It can be shown that to every cyclic semi-linear space there corresponds a Golomb circle and conversely, with every Golomb circle we may associate a cyclic semi-linear space.

Adding another axiom, we construct an affine plane from a semi-linear space. It is a known fact that an affine plane of order $q$ has $q$ points on every line, $q+1$ lines through every point, $q^2$ points in total and $q^2+q$ lines, but it is not cyclic (obviously we need cyclic spaces), and so we create a semi-affine plane from this.

This has $q^2-1$ points and $q^2-1$ lines, $q$ points on every line and $q$ lines through every point, $q+1$ parallel classes of $q-1$ lines each and similarly $q+1$ parallel classes of $q-1$ points each. And semi affine planes are what will aid us.

First we construct a semi-linear space to show what it's all about.

Take a prime number (this construction does not work if it's not a prime, and the other constructions are fairly involved) $q$, say $3$. Genrate $3^2-1=8$ points and $3^2-1=8$ lines. Label them $a,b,c,d,e,f,g,h$ and $A,B,C,D,E,F,G,H$ respectively. Each point is basically a set of coordinates $(x,y),\ 0\le x,y\le 3-1=2$. Oh, and $(0,0)$ is not allowed. This gives a possible labelling:

$$a: (0,1) \\b: (0,2) \\c: (1,0) \\d: (2,0) \\e: (1,1) \\f: (1,2) \\g: (2,1) \\h: (2,2)$$

A similar labelling to the lines is also done. To construct the labelling, just replace the lower-case letters with it's upper case letters.

Now we say that a point $(x,y)$ lies on a point $(u,v)$ if $$xu + yv = 1 \mod 3$$How does this help us? Another observation!

Consider the Fibonacci sequence $0,1,1,2,3,5,8,13,21,34,55,89,144,233,\ldots$. Take this sequence modulo $3$, which gives us $0,1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,\ldots$. Note that the sequence repeats after $8$ elements, thus the sequence has period $8$. $8$ is also $3^2-1$ which is the number of points and lines in the semi-affine plane of order $3$. Also, taking pairs of corresponding elements of the sequence, we get:

$$(0,1), (1,1), (1,2), (2,0), (0,2), (2,2), (2,1), (1,0), (0,1), (1,1), \ldots$$

which are exactly the points of our semi-affine plane shown above. This sequence gives the point sequence $a,e,f,d,b,h,g,c$ which gives us a numbering $$a=0,e=1,f=2,d=3,b=4,h=5,g=6,c=7$$Now if you had calculated which points lie on which line, you would have seen that $a,e,g$ lie on $A$ and thus $0,1,6$ in the affine plane notation and $1,5,2$ in our notation is a Golomb circle, but not perfect.

A word on the notation. To convert from affine plane to our notation, take consecutive pairwise differences (which should give you one number less than the available numbers, for example, the above gives $1-0=1,\ 6-1=5$)and the last number will be the sum of the differences subtracted from the modulus , which here in the affine plane is $q^2-1$ (in the above, it's $3^2-1-(5+1)=8-6=2$).

Unfortunately, we can't even construct more Golomb circles with this construction. The period falls short (mostly) of the required number. But this does provide us something that might work.

Enters linear recurrences of degree 2. Basically you consider a pair of numbers $(A,B)$. Start the sequence with $0,1$. and then always compute $A$ times the last number plus $B$ times the second last number. Append it to the sequence and repeat. Fibonacci is just $A=1=B$.

Consider the sequence with $A=1, B=-2$. It is $$0,1,1,-2,-3,-1,5,7,-3, -17, -11, 23, 45, -1, -91, \ldots $$Modulo $5$, the sequence is $$0, 1, 1, 4, 2, 4, 0, 2, 2, 3, 4, 3, 0, 4, 4, 1, 3, 1, 0, 3, 3, 2, 1, 2, 0, 1, 1, ...$$This sequence has period $24$ which is the correct size for a semi-affine plane of order $5$. Consecutive elements do form pairs of the affine plane and hence we are ready to construct a Golomb circle from this.

To do so, choose any line on the plane, let's say $(1,0)$. Now we see which points $(x,y)$ lie on the line, which is equivalent to checking $x+0=1\Rightarrow x=1\mod 5$. When you do the numbering (pair numbering starts from $0$), you will observe that the the pairs numbered $1,2,15,17,22$ satisfy the requirement. And thus this forms a Golomb circle, which in our notation reads, $1,13,2,5,3$.

But... these are not perfect.

Here's how we generate perfect Golomb circles!

Enter linear recurrences of degree three. You now consider a triple of numbers $(A,B,C)$. Start the sequence with $0,0,1$. and then always compute $A$ times the last number plus $B$ times the second last number plus $C$ times the third last number. Append it to the sequence and repeat.

Choose a prime $q$ and generate such a $(A,B,C)$ sequence (not all sequences work with all primes, this is where we would require a computer). Take the sequence modulo $q$. Then take a part of the sequence such that it starts from the first pair of $0$'s and ends before another pair of $0$'s. Mark all the positions of the $0$'s (I repeat, positions, not pair positions. Numbering of sequence starts with $0$). The numbers of the markings forms our perfect Golomb circle. This also guarantees that we will generate a perfect Golomb circle of size $q+1$ and modulus $q^2+q+1$.

The reason the modulus changed is because perfect Golomb circles are more restrictive and hence the change of construction plans.

For example, take $q=2$. The sequence $(1,0,1)$ works here. The sequence is:

$$0, 0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, \ldots$$

modulo $2$ is:

$$0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, \ldots$$

Taking the required part of the sequence:

$$0,0,1,1,1,0,1$$

The positions of the $0$'s are $0,1,5$. Thus this is the required perfect Golomb circle. In our notation, this reads $1,4,2$ which is the example given by the OP.

Since the number of primes are infinite, this construction proves that there is no upper bound on the size of a perfect Golomb circle. This answers question 2.

Since $q+1$ is always even for a prime $q>2$, thus the answer for question number 3 is also that there is no upper bound.

P.S. This can be generalized to finite fields and thus prime constructions can also be done (which I haven't mentioned here), but they are again pretty involved and thus is left out of here.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you. There seems to be a solution for the second question as well, but I think I would need a bit more time. $\endgroup$ – Yuzuriha Inori May 7 at 8:41
  • 3
    $\begingroup$ Wow! Just wow! This answer is incredible!!! You deserve many votes for this. $\endgroup$ – Dmitry Kamenetsky May 7 at 10:55
  • 1
    $\begingroup$ I am glad I could be of help! Thanks for the appreciation. I am honoured. $\endgroup$ – Yuzuriha Inori May 7 at 10:57
  • 2
    $\begingroup$ Stay tuned for a bounty in a few days. It will be well deserved :) $\endgroup$ – Dmitry Kamenetsky May 7 at 11:05
  • 1
    $\begingroup$ Fine. I shall add the required details tomorrow. It's locally late here. $\endgroup$ – Yuzuriha Inori May 7 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.