11
$\begingroup$

A Golomb ruler is a set of $n$ integers that determines $\binom{n}{2}$ distinct differences. Two sets are homometric if they determine the same (multiset) of differences. For example, $$\{0,1,4,10,12,17\} \;,\; \{0,1,8,11,13,17\}$$ are a homometric pair of Golomb rulers, determining 15 distinct differences (excluding only $\{14,15\}$). Although there are arbitrarily large Golomb rulers, and arbitrarily large pairs of homometric sets (allowing multipiclity), it is unclear (from my searching) if there are arbitrarily large pairs of Golomb rulers.

In the 1994 paper, "There Are No New Homometric Golomb Ruler Pairs with 12 Marks or Less," the authors say that they "are divided on whether any additional nontrivial homometric rulers are to be found." The nice paper "Reconstructing sets from interpoint distances" does not seem to attend to the special case where all distances are distinct. Nor does the Rosenblatt-Seymour paper "The structure of homometric sets" (inferring from secondary sources—I don't have that paper yet).

My question is: What is the largest pair of homometric Golomb rulers known? Is it still open whether or not there are arbitrarily large pairs? Thanks for any pointers on this topic!

Addendum. Thanks to Yota Otachi for uncovering the 2007 paper by Bekir and Golomb he cites below. As he says, it proves that there are no homometric Golomb rulers of more than six marks. The proof uses Golomb's "polynomial method."

$\endgroup$
4
  • $\begingroup$ Some information on the related 'optimal rulers' can be found on this page: luschny.de/math/rulers/optimallist.html $\endgroup$ Jul 13, 2010 at 19:12
  • $\begingroup$ @Bruce: Thanks! That link includes the homometric Golomb pair {0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68}, {0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68}, sets of cardinality 14. $\endgroup$ Jul 13, 2010 at 19:27
  • $\begingroup$ Be careful! Optimal rulers are not necessarily Golomb rulers. There are 4 homometric optimal rulers of length 123 and a homometric pair of length 138 is known. Look around at the given site. $\endgroup$ Jul 13, 2010 at 19:47
  • $\begingroup$ @Bruce: You are right, I misinterpreted his definition of optimal! I'll leave in my incorrect comment above for the record... $\endgroup$ Jul 13, 2010 at 20:16

1 Answer 1

7
$\begingroup$

I think "There are no further counterexamples to S. Piccard's theorem" by A. Bekir and S.W. Golomb is the answer. I skimmed the paper and if I understand correctly they proved that there are no homometric Golomb ruler pairs with 7 marks or more.

$\endgroup$
1
  • $\begingroup$ Thanks for this reference! I am retrieving the paper from Interlibrary Loan, as my institution's library does not carry that journal. Will report back eventually... $\endgroup$ Feb 7, 2011 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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