Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Some New Optimum Golomb Rectangles"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Some New Optimum Golomb Rectangles. | Some New Optimum Golomb Rectangles James B. Shearer IBM Research Division T.J. Watson Research Center P.O. Box 218 Yorktown Heights N.Y. 10598 jbs@watson.ibm.com Submitted April 3 1995 Accepted June 1 1995 Abstract We give some new optimum Golomb rectangles found by computer search. AMS Subject Classification. 05B99 In 2 Robinson defined a Golomb rectangle as an N X M array of ones and zeros such that the two-dimensional autocorrelation has three values 0 1 and K where K is the number of ones in the array. This means that the positions of the ones in any nonzero integral translation of the rectangle will overlap with the positions of the ones in the original position of the rectangle in at most one place. Equivalently the differences between the positions of every pair of ones in the rectangle considered as vectors are distinct. See also 1 . Let G N M be the maximum number of ones that can be present in an N X M Golomb rectangle. For example G 2 2 3. Robinson defined an optimum Golomb rectangle to be one containing G N M ones. We prefer to add the conditions G N M G N 1 M and G N M G N M 1 . In table 1 we give a number of new optimum Golomb rectangles found by computer search. In most cases they are far from unique. Note there exists a 2 X 18 rectangle with 9 ones. The rectangle in Robinson s table V is 2 X 20 an apparent misprint. A brief description of the computer program used to find these rectangles follows. Recall that a Golomb ruler is a set of integers a1 a2 ak for which the differences aj ai 1 i j kg are distinct. We will use the following easy lemma. Lemma 1 N X M Golomb rectangles with K ones correspond 1 1 with K element Golomb rulers with elements chosen from the set i 2N 1 j 1 11 i N 1 j M . Proof Let bi ci 11 bi N 1 ci M 1 i K be a set of K positions in a N X M rectangle. We claim this set consists of the positions of the ones in a N X M Golomb rectangle with K ones iff the set ai bi 2N 1 ci 1 11 i K is a THE ELECTRONIC .JOURNAL OF COMBINATORICS 2 .