% A Latex file for a 9 page document
\documentstyle[12pt]{article}
\oddsidemargin 0.25in
\topmargin -0.25in
\headheight 0.25in
\textwidth 6in
\headsep .25in
\textheight 8.25in
%\font\smcp=cmcsc8
%\headline={\ifnum\pageno>1 {\smcp the electronic journal of
%combinatorics 2 (1995), \#R12\hfill\folio} \fi}

\begin{document}

\pagestyle{myheadings}

\markboth{\sc the electronic journal of combinatorics 2 (1995) \#R12}{\sc the electronic
 journal of combinatorics 2 (1995) \#R12}
\markright{\sc the electronic journal of combinatorics 2 (1995) \#R12}



\begin{center}
\Large

{\bf Some New Optimum Golomb Rectangles}


\bigskip

\normalsize

James B. Shearer\\
IBM Research Division\\
T.J. Watson Research Center\\
P.O. Box 218\\
Yorktown Heights, N.Y.  10598\\
{\tt jbs@watson.ibm.com} \\
\medskip
Submitted: April 3, 1995; Accepted: June 1, 1995
\end{center}


%\maketitle

\bigskip


\noindent
{\bf Abstract:}  We give some new optimum Golomb rectangles found
by computer search.

\bigskip

\noindent
{\bf AMS Subject Classification.} 05B99

\bigskip


%\newpage

%\tableofcontents

%\newpage

\pagestyle{myheadings}
%\nopagenumbers
%\markright{\sc the electronic journal of combinatorics 2 (1995),
%\#Xnn\hfill}
\thispagestyle{empty}

\medskip


\noindent

In [2] Robinson defined a Golomb rectangle as an
$N \times 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 \times 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 \times 18$ rectangle with 9 ones.
The rectangle in Robinson's table V is $2 \times 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
$ a_1 < a_2 < \cdots < a_k$ for which the
$\left( \begin{array}{c} k \\ 2 \end{array} \right)$ differences
$\{ a_j - a_i | 1 \leq i < j \leq k \}$ are distinct.
We will use the following easy lemma.

\bigskip

\noindent
{\bf Lemma 1:}
{\it $N \times 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) | 1 \leq i \leq N, 1 \leq j \leq M\}$.}

\bigskip

\noindent
{\bf Proof:}  Let $\{( b_i , c_i ) | 1 \leq b_i \leq N, 1 \leq c_i \leq
M, 1 \leq i \leq K \}$ be a set of $K$ positions in a $N \times M$
rectangle.  We claim this set consists of the positions of the ones
in a $N \times M$ Golomb rectangle
with $K$ ones iff the set $\{ a_i = b_i + (2N-1)(c_i -1) |
1 \leq i \leq K\}$, is a Golomb ruler with elements
chosen from the set $\{ i + (2N -1) (j-1) | 1 \leq i \leq N, 1 \leq
j \leq M \}$.  For suppose $(b_{i_1}, c_{i_1} ) - (b_{i_2} , c_{i_2} )
= (b_{i_3} , c_{i_3}) - (b_{i_4} , c_{i_4} )$.  Then
\begin{eqnarray*}
a_{i_1} - a_{i_2} & = & ( b_{i_1} + (2N -1) (c_{i_1} - 1))- (b_{i_2}
+ (2N -1) ( c_{i_2} - 1 )) \\
& = & (b_{i_1} - b_{i_2} ) + (2N -1) (c_{i_1} - c_{i_2} ) \\
& = & (b_{i_3} - b_{i_4} ) + (2N - 1) ( c_{i_3} - c_{i_4}) \\
& = & (b_{i_3} + (2N -1)
(c_{i_3} -1)) - (b_{i_4} + (2N-1) ( c_{i_4} - 1)) \\
& = & a_{i_3} - a_{i_4} .
\end{eqnarray*}
Conversely suppose $(a_{i_1} - a_{i_2} ) = (a_{i_3} - a_{i_4} )$.
Then
\begin{eqnarray*}
(b_{i_1} & + & (2N -1)(c_{i_1} - 1)) - (b_{i_2} + (2N -1) (c_{i_2}
-1)) \\
& = & (b_{i_3} + (2N-1) (c_{i_3} -1))- (b_{i_4} + (2N -1) (c_{i_4}-1)) .
\end{eqnarray*}
It follows that
$$
(b_{i_1} - b_{i_2} ) - (b_{i_3} - b_{i_4} ) + (2N-1)
(( c_{i_1} - c_{i_2} ) - ( c_{i_3} - c_{i_4} )) = 0 .
$$
Now $1 \leq b_{i_1}, b_{i_2}, b_{i_3}, b_{i_4} \leq N$.  It follows that
$$
-(2N-1) < ( b_{i_1} - b_{i_2} ) + (b_{i_3} - b_{i_4}) < (2N-1) .
$$
Therefore we must have $(b_{i_1} - b_{i_2} ) - ( b_{i_3} - b_{i_4})
= 0$ and $(c_{i_1} - c_{i_2} ) - (c_{i_3} - c_{i_4} ) = 0$.
Hence $(b_{i_1} , c_{i_1} ) - (b_{i_2} , c_{i_2} ) = (b_{i_3} , c_{i_3})
- (b_{i_4} , c_{i_4} )$.  This suffices to prove the claim and the
lemma. \hfill$\Box$

Lemma 1 means that searches for
Golomb rectangles can be performed with a modified version of the
author's Golomb ruler search program (see [3]).
This program performs a straightforward depth first backtrack search.
It builds up a Golomb ruler by picking $a_1 , a_2 ,
\ldots , a_k$ in order ($a_j$ being picked at
level $j$ of the search tree).  At each node of the search tree
the program keeps track of which differences have been used (i.e. are
formed by pairs of the elements which have already been picked) and
of which integers can be adjoined to the current ruler without
violating the distinct difference condition.  The sons of a node at
level $j$ are formed by setting $a_{j+1}$ to each of
the elements in the level $j$ eligibility list in turn.
The search tree is pruned (i.e. the program backtracks) when too
few  integers remain eligible to allow completion of the ruler,
when not enough small differences remain unused to allow completion
of the ruler or when allowed by symmetry conditions.  (Symmetry
conditions allow search trees to be pruned because we need only
generate one member of each symmetry class of solutions.
Clever use of symmetry can produce dramatic improvements in running
times.)  The following symmetry conditions were used in the Golomb
rectangle program.  Assume at least half the ones are in the left
half of the rectangle (flip left and right if necessary).  Assume the
top half of the first column contains a one (clearly
in an optimum rectangle the first column must contain a one, flip
top and bottom if necessary).  These conditions are probably not
the best (in particular the second condition could assume the
top half of the first column contains at least half the ones in the
first column) but they were simple to implement.  One can choose
to search for $N \times M$ rectangles or for $M \times N$
rectangles.  The main runs were done with $N \leq M$ although
that is not always the best choice.

The entire program amounts to about 100 lines of VS Fortran code.
As is often the case for this sort of program running times (on a
3090 IBM mainframe) increased rapidly with the problem size.
For example showing $G (7,11) < 14$ required 640 seconds
of cpu time but showing $G (9, 12) < 16$ required 44000
seconds of cpu time.  On average each node visited in the search
tree required about 6 microseconds of cpu time.

A skeptical reader might ask why he should believe the program is
correct.  Checking that the rectangles found are in fact Golomb
rectangles is fairly simple.  An independent program checked this
for the rectangles in table 1.  It is possible (although tedious)
to do these checks by hand.  The validity of the assertion that
the rectangles in table 1 are optimum (i.e. that Golomb rectangles
with better parameters do not exist) is more problematic.
However, the following factors give the author confidence that his
search program has not missed any superior rectangles.
The program successfully reproduced (with the exception noted above)
the results Robinson obtained with a completely different program.
The program is reasonably small (100 lines of code).
Additionally, the basic algorithm and much of the code is the same
as for the author's Golomb ruler program.  The results obtained by
the Golomb ruler program are in agreement with those obtained by
other researchers using independent programs.  Of course, additional
checking is always possible.  For example, it would be nice to do
searches on $N \times M$ rectangles and on $M \times N$
rectangles as the search trees will be completely different (when
$N \neq M$).  However, as noted above this was not done for the
large cases.

\medskip

\begin{center}
Table 1
\end{center}


\begin{tabbing}
G(2,18)=9 \qquad \=  110000010000000010\\
\> 100101000000010001 \\
\\
G(2,29)=11 \> 11000000100000000000010100010 \\
\> 10010000000010000100000000001 \\
\\
G(2,35)=12 \> 10100000000000110000000010000000100 \\
\> 10010001000000000000000100001000001 \\
\\
G(2,43)=13 \> 1100000000000010100000000000000000100010010 \\
\> 1000001000010000000000010000000010000000001 \\
\\
G(2,52)=14
\> 1100000001000000000000001000000100000000000001000101 \\
\> 1001000000000100000000000000010000000000010000100000 \\
\\
G(2,59)=15
\> 11000000001000000100000000000000000000001000001000000010001 \\
\> 10010000000000000000001010000000000100000000000000100001000 \\
\\
G(3,18)=11 \> 100100000000010100 \\
\> 100000000100000001 \\
\> 010000011000100000 \\
\\
G(3,21)=12 \> 100001000001000000011 \\
\> 100000000000000010100 \\
\> 001000100100000000010 \\
\\
G(3,26)=13 \> 10001000000010000000001101 \\
\> 01000000100000000000000001 \\
\> 10000010000000010000100000 \\
\\
G(3,31)=14 \> 1000010001000000010000001000001 \\
\> 1000000000000000000010010000000 \\
\> 0110000000001000000000000000101 \\
\\
G(3,37)=15 \> 1000010000000010000000000000000000101 \\
\> 1001000000000000000000000010001000000 \\
\> 0010000000100000010000010000000000110 \\
\\
G(4,13)=11 \> 1001000000011 \\
\> 1000000000000 \\
\> 0100001010000 \\
\> 1000100000100 \\
\\
G(4,16)=12 \> 1001000000001010 \\
\> 1000000000000001 \\
\> 0000000100010000 \\
\> 1000011000000100 \\
\\
G(4,19)=13 \> 1010000100000000100 \\
\> 1000000000100000001 \\
\> 0000000001000001000 \\
\> 0100110000000000100 \\
\\
G(4,23)=14 \> 11000001000100001000000 \\
\> 10000000000000000010010 \\
\> 00000010000000000001000 \\
\> 10100000000000100000001 \\
\\
G(4,27)=15 \> 100000000100010100000001000 \\
\> 100100000000000000000000100 \\
\> 000000011000000000010000001 \\
\> 100001000000000000000000010 \\
\\
G(5,11)=11 \> 11000000001 \\
\> 10000000000 \\
\> 00000010010 \\
\> 10100001000 \\
\> 00001000001 \\
\\
G(5,12)=12 \> 110001000001 \\
\> 100000000000 \\
\> 000000010010 \\
\> 100000001000 \\
\> 001010000001 \\
\\
G(5,15)=13 \> 100001000001001 \\
\> 100000000000010 \\
\> 000000000010001 \\
\> 001010000000000 \\
\> 100000011000000 \\
\\
G(5,18)=14 \> 100000001000100001 \\
\> 100000010010000000 \\
\> 000010000000000100 \\
\> 100000000000000000 \\
\> 010100000000000011 \\
\\
G(5,20)=15 \> 10000000010000000100 \\
\> 00001000100000000011 \\
\> 10100000000000000000 \\
\> 00000000000001001000 \\
\> 01000010000001000001 \\
\\
G(6,8)=11 \> 11000100 \\
\> 00000001 \\
\> 00000001 \\
\> 01010000 \\
\> 10000010 \\
\> 01001000 \\
\\
G(6,10)=12 \> 1100000001 \\
\> 1000000100 \\
\> 0001000001 \\
\> 0000100000 \\
\> 0000000010 \\
\> 1010010000 \\
\\
G(6,12)=13 \> 100010000110 \\
\> 000010000001 \\
\> 100000000000 \\
\> 000101000000 \\
\> 001000000000 \\
\> 100000001001 \\
\\
G(6,14)=14 \> 10010000000101 \\
\> 00000110000010 \\
\> 00100000000000 \\
\> 10000000000010 \\
\> 10000000000000 \\
\> 00001000100001 \\
\\
G(6,17)=15 \> 11000000000000101 \\
\> 10000001000000000 \\
\> 00000000010000010 \\
\> 00010000000001000 \\
\> 10000000000000000 \\
\> 01000100001001000 \\
\\
G(7,7)=11 \> 1000100 \\
\> 0100001 \\
\> 1000001 \\
\> 0000000 \\
\> 0001000 \\
\> 0000001 \\
\> 0110100 \\
\\
G(7,9)=12 \> 110000101 \\
\> 100000000 \\
\> 000100000 \\
\> 100000000 \\
\> 000000001 \\
\> 010010000 \\
\> 001000100 \\
\\
G(7,10)=13 \> 1100000010 \\
\> 0000010000 \\
\> 0000100100 \\
\> 1000000000 \\
\> 0000000001 \\
\> 1000000001 \\
\> 0101000100 \\
\\
G(7,12)=14 \> 001010000001 \\
\> 000000001000 \\
\> 100000000001 \\
\> 110000000000 \\
\> 000000000010 \\
\> 000100100000 \\
\> 010001000001 \\
\\
G(7,15)=15 \> 100000001000011 \\
\> 100000010001000 \\
\> 000000000000000 \\
\> 101000000000000 \\
\> 000010000000001 \\
\> 000001000000000 \\
\> 010000000010010 \\
\\
G(8,8)=12 \> 11001010 \\
\> 10000000 \\
\> 00000001 \\
\> 10000000 \\
\> 00010000 \\
\> 00000100 \\
\> 00100000 \\
\> 10000001 \\
\\
G(8,11)=14 \> 10000001001 \\
\> 10001000010 \\
\> 00000000000 \\
\> 00001000000 \\
\> 00000000010 \\
\> 11000000000 \\
\> 00000001000 \\
\> 00100000101 \\
\\
G(8,13)=15 \> 1000010001001 \\
\> 1000000000000 \\
\> 0000000001000 \\
\> 0100000000000 \\
\> 1000000000010 \\
\> 0000000000001 \\
\> 0000011000000 \\
\> 0010000010100 \\
\\
G(9,9)=13 \> 110000001 \\
\> 100000000 \\
\> 000010000 \\
\> 100000000 \\
\> 000000100 \\
\> 010000010 \\
\> 000000000 \\
\> 100000000 \\
\> 000101001 \\
\\
G(9,10)=14 \> 1000001000 \\
\> 1010000001 \\
\> 0000000000 \\
\> 1001000000 \\
\> 0000000100 \\
\> 0000000000 \\
\> 0000000001 \\
\> 1000000010 \\
\> 0100011000 \\
\\
G(9,12)=15 \> 110000010001 \\
\> 100000000000 \\
\> 000000001010 \\
\> 100000000000 \\
\> 000010000000 \\
\> 000001000000 \\
\> 000000000000 \\
\> 100000000100 \\
\> 000100100001 \\
\\
G(10,10)=15 \> 1000010010 \\
\> 0100000000 \\
\> 0000000001 \\
\> 1000100000 \\
\> 0010000000 \\
\> 0000000000 \\
\> 0000000001 \\
\> 0000000001 \\
\> 0101000000 \\
\> 1000001100
\end{tabbing}


\bigskip


\begin{thebibliography}{99}
\bibitem{1} Golomb, S.W. and Taylor, M.,
{\em Two-dimensional synchronization patterns for minimal ambiguity},
IEEE Transactions Information Theory, It-28, pp. 600-604, 1982.
\bibitem{2} Robinson, J.P.,
{\em Golomb Rectangles},
IEEE Transactions on Information
Theory, It-31, pp. 781-787, 1985.
\bibitem{3} Shearer, J.B.,
{\em Some New Optimum Golomb Rulers},
IEEE Transactions on Information
Theory, It-36, pp. 183-184, 1990.

\end{thebibliography}
\end{document}
