关于哥伦布尺问题的新的进展

Some New Development on the Length of Golomb's Rulers

给定一个递增的整数序列0=x_1<x_2<…<x_n,如果满足任两个元素之差的绝对值均不相等且x_n 又能保证最小,则序列x_1,x_2,…,x_n 称为哥伦布尺,x_n 的大小则被称为哥伦布尺的长度.当然,目标是对任意给定的n,找出最短的哥伦布尺.本文在[1]的基础上,给出了两个有意义的结论,首先找到了长度为O(n^3/4)的哥伦布尺;其次证明了不存在一个长度为n 的平方级的万能公式其能产生哥伦布尺。

Let x_1,x_2,…,x_n be an increasing sequence of integers,where x_1=0,whichsatisfies the following conditions:if |x_i-x_j|=|x_p-x_q|then{i,j}={p,q}.The objective isto find the order of minimum x_n for any given n.There are two interesting results in[1].They are both improved in this paper.In particular,it will be shown that thelength of Golomb's Rulers have been shortened to a half,and that the satisfying se-quence can't be generated by such a quadratic formula as x_i=ai^2+bni+ci+dn^2+en+ffor any rationals a,b,c,d,e and f.