Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 Golumb's "polynomial model."

share|improve this question
    
Some information on the related 'optimal rulers' can be found on this page: luschny.de/math/rulers/optimallist.html –  Bruce Arnold Jul 13 '10 at 19:12
    
@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. –  Joseph O'Rourke Jul 13 '10 at 19:27
    
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. –  Bruce Arnold Jul 13 '10 at 19:47
    
@Bruce: You are right, I misinterpreted his definition of optimal! I'll leave in my incorrect comment above for the record... –  Joseph O'Rourke Jul 13 '10 at 20:16
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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... –  Joseph O'Rourke Feb 7 '11 at 17:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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