\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{subcaption}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\newcommand{\suchthat}{\; : \;}
\newcommand{\CommentLine}[1]{\State $\triangleright$ #1}
\newcommand{\I}{\text{I}}
\newcommand{\II}{\text{II}}
\newcommand{\III}{\text{III}}
\newcommand{\IV}{\text{IV}}
\newcommand{\kmin}{k^\text{min}}
\newcommand{\Bcal}{\mathcal{B}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Planar Additive Bases for Rectangles
}
\vskip 1cm
\large
Jukka Kohonen\\
Department of Computer Science\\
University of Helsinki\\
P.O. Box 68, FI-00014 University of Helsinki\\
Finland\\
\href{mailto:jukka.kohonen@helsinki.fi}{\tt jukka.kohonen@helsinki.fi} \\
\ \\
Visa Koivunen and Robin Rajam\"aki\\
Department of Signal Processing and Acoustics\\
Aalto University\\
P.O. Box 15400, FI-00076 Aalto\\
Finland\\
\href{mailto:visa.koivunen@aalto.fi}{\tt visa.koivunen@aalto.fi}, \href{mailto:robin.rajamaki@aalto.fi}{\tt robin.rajamaki@aalto.fi}
\end{center}
\vskip .2 in
\begin{abstract}
We study a generalization of additive bases into a
planar setting. A planar additive basis is a set of
non-negative integer pairs whose vector sumset covers
a given rectangle. Such bases find applications in
active sensor arrays used in, for example, radar and
medical imaging.
We propose two algorithms for finding the minimal
bases of small rectangles: one in the unrestricted
case where the basis elements can be anywhere in the
rectangle, and another in the restricted case, where
the elements are confined to the lower left quadrant.
We present numerical results from such searches,
including the minimal cardinalities and number of
unique solutions for all rectangles up to
$[0,11]\times[0,11]$ in the unrestricted case, and up
to $[0,26]\times[0,26]$ in the restricted case. For
squares we list the minimal basis cardinalities up to
$[0,13]\times[0,13]$ in the unrestricted case, and up
to $[0,46]\times[0,46]$ in the restricted
case. Furthermore, we prove asymptotic upper and lower
bounds on the minimal basis cardinality for large
rectangles.
\end{abstract}
\section{Introduction}
\label{sec:intro}
An \emph{additive basis} for an interval of integers $[0, n] =
\{0,1,2,\ldots,n\}$ is a set of non-negative integers $A$ such that
$A+A \supseteq [0,n]$. By extension we define that a \emph{planar
additive basis} for a rectangle of integers $R=[0,s_x]\times[0,s_y]$
is a set of points with non-negative integer coordinates
\[
A = \{(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)\}, \quad\text{such that $A+A \supseteq R$}.
\]
The \emph{sumset} (or \emph{sum co-array}) is defined in terms of
vector addition, that is
\[
A+A' = \{(x+x', \; y+y') \suchthat (x,y) \in A, \; (x',y') \in A' \}.
\]
Additive bases for integer intervals have been widely studied since
Rohrbach~\cite{rohrbach1937}. Often one seeks to maximize~$n$ when
the basis cardinality $|A|=k$ is given. For small~$k$ this has been
approached with computations
\cite{challis1993,kohonen2014,lunnon1969,riddell1978}, and for
large~$k$ with asymptotic bounds~\cite{kohonen2017,yu2015}.
Less is known about planar additive bases. Kozick and Kassam
discussed them in an application context of signal processing, and proposed some simple
designs~\cite{kozick1991}. In a rather different line of work,
sumsets in vector spaces and abelian groups have been studied with the
interest in how \emph{small} the sumset can be
\cite{eliahou1998,eliahou2005,eliahou2003}. Boundary effects in
planar sumsets have also been studied by e.g., Han~\cite{han2004}.
We now aim to minimize the cardinality $k$ of a planar additive basis,
when the target rectangle $R=[0,s_x]\times[0,s_y]$ is given. To the
best of our knowledge, this combinatorial optimization problem has not
been addressed before.
Planar bases have an application in signal processing, when an array
of sensor elements is deployed on a plane to be used in active imaging
or radar surveillance~\cite{naidu2009}. Here ``active'' means that
the sensors both transmit a signal towards objects such as radar
targets or human tissue, and receive the reflections. In this
context, the pairwise vector sums of the sensor locations make up a
virtual sensor array, called the \emph{sum co-array}, which may be
used to improve imaging resolution, or to reduce the number of sensors
without significant performance loss~\cite{hoctor1990}.
An important special case is that of \emph{restricted} bases. A basis
$A$ for $[0,n]$ is restricted if $A \subseteq [0, n/2]$. Analogously
we define that a basis $A$ for $[0,s_x]\times[0,s_y]$ is restricted if
$A \subseteq [0,s_x/2]\times[0,s_y/2]$. Apart from practical
motivations related to the physical placing of sensors, there are
other reasons to study restricted bases. Computationally, we can
study much larger instances in the restricted case, at least with our
current algorithms. Numerically, restricted bases often attain the
same minimum cardinality as unrestricted bases. Also, the minimal
restricted bases often exhibit interesting geometric structure.
We introduce here the following results. First,~a~search algorithm is
proposed for finding all bases of a given size for a given rectangle;
and the minimum basis sizes are determined for all rectangles with
$s_x,s_y \le 11$ or $ s_x=s_y \leq 13 $.
Secondly,~a~meet-in-the-middle method is developed that constructs a
restricted planar basis by concatenating together four smaller bases, one in
each corner; and the minimum restricted basis sizes are determined for
all even $s_x,s_y \le 26$ or even $ s_x=s_y \leq 46 $. Thirdly,~some
asymptotic upper and lower bounds on the minimum basis size for large
rectangles are established.
\section{Definitions and preliminary observations}
\label{sec:preliminary}
The target rectangle is $R=[0,s_x]\times[0,s_y]$. If $R$ is square,
we call it the \emph{$s$-square}, with $s=s_x=s_y$. A basis
containing $k$ elements is a \emph{$k$-basis}. The size of the
smallest basis for $[0,s_x]\times[0,s_y]$ is denoted by $k(s_x,s_y)$.
If $s_x$ and $s_y$ are even, we set $h_x = s_x/2$ and $h_y = s_y/2$.
Then a basis $A$ is \emph{restricted} if $A \subseteq [0,h_x] \times
[0,h_y]$. Note that it follows that $A+A=R$. The size of the smallest
restricted basis is $k^*(s_x,s_y)$.
If $A$ is a basis for~$R$ such that $A \subseteq R$, we say that $A$
is \emph{admissible}. If not, then it cannot be minimal, since one
can simply drop the elements that are outside the target. So we
confine our attention to admissible bases.
We relate the basis size
$k=|A|$ to the number of target elements
$N = \left\lvert R\right\rvert =
(s_x+1)(s_y+1)$,
which may be understood as the \emph{target area} measured in grid
points. The \emph{efficiency} of a basis is defined as
\begin{equation}
c = N/k^2.
\label{eq:efficiency}
\end{equation}
The shape of the target is characterized by its \emph{aspect ratio}
$\rho = (s_y+1)/(s_x+1)$.
Two simple basis constructions were proposed by Kozick and Kassam in
the context of sensor arrays~\cite{kozick1991}. For any rectangle,
the \emph{L-shaped basis} is
\begin{equation}
([0,s_x] \times \{0\}) \;\cup\; (\{0\} \times [0,s_y]),
\label{eq:lbasis}
\end{equation}
which has $s_x+s_y+1$ elements. If $s_x,s_y\ge 2$ are even, the
\emph{boundary basis} is
\begin{equation}
([0,h_x] \!\times\! \{0,h_y\})
\; \cup \; (\{0,h_x\} \!\times\! [0, h_y]),
\label{eq:boundarybasis}
\end{equation}
which has $s_x+s_y$ elements and is restricted. These two provide a
minimal basis for most small squares (boundary basis if $s\ge 2$ is
even, L-shaped otherwise). The smallest counterexample is the
7-square, whose minimal bases have only $14$~elements, one less than
the L-shaped basis (see Figure~\ref{fig:nr_7}). However, for
non-square rectangles, \eqref{eq:lbasis} and \eqref{eq:boundarybasis}
are generally not minimal. Examples of this will be presented in
Section~\ref{sec:results}, and an asymptotic result in
Section~\ref{sec:largescale}.
The following observations about the corners and the horizontal edges
of planar additive bases will be useful. Corresponding results in the
vertical direction can be proven by transposing $x$ and~$y$.
\begin{lemma}[Origin corner]
\label{lemma:corners_nonrestr}
If $A$ is a basis for a rectangle with $s_x \geq 1$, then $(0,0),
(1,0) \in A$.
\end{lemma}
\begin{proof}
The only way to represent $(1,0)$ as a sum of two pairs of
non-negative integers is $(0,0)+(1,0)$, so those elements must be in
the basis.
\end{proof}
\begin{figure}[H]
\begin{subfigure}[b]{0.23\textwidth}
\centerline{\includegraphics[width=1\textwidth]{l_5_5}}
\caption{}
\label{fig:l_5}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.23\textwidth}
\centerline{\includegraphics[width=1\textwidth]{b_6_6}}
\caption{}
\label{fig:b_6}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.23\textwidth}
\centerline{\includegraphics[width=1\textwidth]{nr_7_7}}
\caption{}
\label{fig:nr_7}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.24\textwidth}
\centerline{\includegraphics[width=1\textwidth]{nr_13_13}}
\caption{}
\label{fig:nr_13}
\end{subfigure}
\caption{(a) The L-shaped basis for the 5-square. (b) The
boundary basis for the 6-square. (c)~A~minimal basis for the
7-square. (d) A~minimal basis for the 13-square.}
\label{fig:intro}
\end{figure}
\begin{lemma}[Restricted edges]
\label{lemma:edges_restr}
If $A$ is a restricted basis for $[0,s_x]\times[0,s_y]$, then its
bottom edge $\{x : (x,0)\in A\}$ and top edge $\{x : (x,h_y)\in A\}$
are (one-dimensional) restricted bases for $[0,s_x]$.
\end{lemma}
\begin{proof}
Consider first the bottom edge. Since the $y$ coordinates in $A$
are non-negative, for any $x\in[0,s_x]$ the point $(x,0)$ must be
the sum of some $(x',0),(x'',0) \in A$. Since $A$ is restricted, we
have $x',x'' \le h_x$.
Consider next the top edge. Since the $y$ coordinates in $A$ are at
most $h_y$, for any $x\in[0,s_x]$ the point $(x,s_y)$ must be the
sum of some $(x',h_y),(x'',h_y) \in A$. Since $A$ is restricted, we
have $x',x'' \le h_x$.
\end{proof}
\begin{lemma}[Two rows]
\label{lemma:shallow_restr}
For any even $s_x \ge 0$, we have $k^*(s_x,2) = 2k^*(s_x,0)$.
\end{lemma}
\begin{proof}
Let $A$ be a restricted basis for $[0,s_x]\times[0,2]$. By
Lemma~\ref{lemma:edges_restr} its bottom and top edges are
restricted bases for $[0,s_x]$, so each has at least $k^*(s_x,0)$
elements. Thus $|A| \ge 2k^*(s_x,0)$.
To see that $k^*(s_x,2) \le 2k^*(s_x,0)$, let $A^*$ be a restricted
basis for $[0,s_x]$. Then $A^* \times [0,1]$ is a restricted
basis for $[0,s_x]\times[0,2]$.
\end{proof}
\section{Search algorithm for admissible bases}
\label{sec:nonrestricted}
In this section we develop a method to find all admissible $k$-bases
for a given rectangle. Then we can also establish the minimum value
of~$k$. For example, the L-shaped basis suffices to show that
$k(9,9) \le 19$, but to prove that $k(9,9)=19$ we must ascertain that
there is no 18-basis for the $9$-square. Trying out the
$\binom{100}{18} \approx 3 \cdot 10^{19}$ ways of placing 18 elements
in $[0,9]\times[0,9]$ is obviously impractical.
Our Algorithm~\ref{alg:search} is a relatively straightforward
generalization of Challis's algorithm, which finds one-dimensional
bases \cite{challis1993}. Assume for simplicity that $s_x \ge 2$.
By~Lemma~\ref{lemma:corners_nonrestr} the points $(0,0)$ and $(1,0)$
must be included in the basis. Next we branch on the decision whether
$(2,0)$ is included. We proceed to the right and rowwise, branching
at each location on whether that point is included, until we have $k$
elements or reach the top right corner.
\begin{algorithm}[tb]
\caption{Find all admissible $k$-bases for $[0,s_x]\times[0,s_y]$}
\label{alg:search}
\begin{algorithmic}[1]
\Procedure{FindBases}{$k,s_x,s_y$}
\State \Call{Extend}{$k,s_x,s_y,\{(0,0),(1,0)\},1,0$}
\EndProcedure
\Procedure{Extend}{$k,s_x,s_y,A,x,y$}
\CommentLine{$(x,y)$ is the latest location considered (either filled or left empty).}
\State $j \gets \lvert A \rvert$
\Comment{Number of elements}
\State $G \gets \lvert [0,s_x]\times[0,s_y] \setminus (A+A) \rvert$
\Comment{Number of gaps}
\If{$(j = k) \wedge (G=0)$}
\Call{Print}{$A$}
\Comment{Found a basis}
\EndIf
\If{$j = k$}
\Return
\Comment{Reached full size}
\EndIf
\State $M \gets (k+j+1)(k-j)/2$
\Comment{Max.\ sums to expect}
\If{$M < G$}\label{line:gaps}
\Return
\Comment{Too many gaps}
\EndIf
\If{$xx$ or $y'>y$ (or both). Thus any such
elements will not generate the sum $(x,y)$, by the non-negativity of
coordinates. If $(x,y)$ has not already been covered, then $(x,y)$
has to be included in the basis.
The other test (line~\ref{line:gaps}) is based on a counting argument.
Suppose that after placing $j$ elements there are $G$ gaps, or target
points not covered by the current sumset. No matter where the
remaining $k-j$ elements are placed, they will generate at most
$M=(j+1)+(j+2)+\cdots+k = (k+j+1)(k-j)/2$ more sums. If $M0$ and $h_y=s_y/2>0$. First we divide $R_h$ into four
disjoint rectangles by choosing breaking points $a_x \in [0,h_x-1]$
and $a_y \in [0,h_y-1]$ arbitrarily, and defining
\begin{align*}
R_\I &= [0,a_x]\times[0,a_y], \\
R_\II &= [a_x+1,h_x]\times[0,a_y], \\
R_\III &= [a_x+1,h_x]\times[a_y+1,h_y], \\
R_\IV &= [0,a_x]\times[a_y+1,h_y].
\end{align*}
These are the colored rectangles in the left part of Figure~\ref{fig:mim}. Now
split a basis $A$ into components $ A_\I,A_\II,A_\III,A_\IV$ so that
$ A_\I = A \cap R_\I$, and similarly with the others. By the
non-negativity of all coordinates, any sumset involving $A_\II$,
$A_\III$ or $A_\IV$ is completely outside the lower left corner
~$R_\I$. So in order to have $A+A \supseteq R$ we need
$A_\I+A_\I \supseteq R_\I$. That is, $A_\I$ must be an admissible
basis for~$R_\I$. All candidates for~$A_\I$ can be listed by
Algorithm~\ref{alg:search}.
A similar argument applies in the lower right corner of the target,
with some necessary coordinate transformations. Let
$C_\II = [h_x+a_x+1, s_x] \times [0,a_y]$. Then we need
$A_\II+A_\II \supseteq C_\II$, since all the other component sumsets
are outside~$C_\II$. Consider the ``mirror image'' of $A_\II$, namely
$B_\II = \{(h_x\!-\!x,\; y) : (x,y) \in A_\II\}$. By construction, we
have $B_\II \subseteq [0,b_x]\times[0,a_y]$, where for convenience we
have written $b_x = h_x-a_x-1$. Now the condition
$A_\II+A_\II \supseteq C_\II$ implies that
$B_\II+B_\II \supseteq [0,b_x]\times[0,a_y]$. So $B_\II$ must be an
admissible basis for~$[0,b_x]\times[0,a_y]$, and again all candidates
can be found by Algorithm~\ref{alg:search}.
\begin{figure}[H]
\centerline{\includegraphics[width=6in]{MIM}}
\caption{MIM decomposition of a restricted basis $ A $. The
four components $ A_\I,\ldots, A_\IV$ are contained in the
colored rectangles (left). Consequently, $ A+A $ (right) is
the union of $A_\text{S} $, $A_\text{N} $ and $A_\text{D} $
(center), which are the self, neighboring and diagonal sums
of the components. The extreme corners of $ A+A $ (areas within dashed rectangles) are
covered only by the self sumsets, so $ A_\I,\ldots, A_\IV $
must be admissible bases for those rectangles (up to suitable
coordinate transformations).}
\label{fig:mim}
\end{figure}
Similar conditions for $A_\III$ and~$A_\IV$ apply in the remaining two
corners. Consequently, $A$ must be the union of four components,
which are (mirror images of) admissible bases of suitable rectangles.
Since we have so far only dealt with necessary conditions, we have not
lost any possible solutions. The conditions guarantee only that the
four extreme corner regions are covered; for any candidate solution
$A = A_\I \cup A_\II \cup A_\III \cup A_\IV$ we must finally check
whether in fact $A+A \supseteq R$.
Algorithm~\ref{alg:mim} gives a formal description of the MIM method.
We choose $ a_x = \lfloor h_x/2 \rfloor$ and
$a_y = \lfloor h_y/2 \rfloor$ so the components have roughly equal
dimensions. The final ingredient of the algorithm, on lines 8--14,
concerns how the overall budget of $k$ elements is allocated to the
four components. Note that $A_\I$ need not be a minimal basis
for~$R_\I$. It may have more than $k(a_x,a_y)$ elements, and indeed
this may be necessary to find any solutions for $A+A \supseteq R$.
The same goes for the other three components.
\begin{algorithm}[tb]
\caption{Find all restricted $k$-bases for $[0,s_x]\times[0,s_y]$}
\label{alg:mim}
\begin{algorithmic}[1]
\Procedure{MIM}{$k,s_x,s_y$}
\State $ h_x \gets s_x/2 $ \Comment{dimensions of rectangle containing $ A$}
\State $ h_y \gets s_y/2 $
\State $ a_x \gets \lfloor h_x/2 \rfloor $ \Comment{dimensions of rectangle containing $ A_\I $}
\State $ a_y \gets \lfloor h_y/2 \rfloor $
\State $ b_x \gets h_x-a_x-1 $ \Comment{dimensions of other rectangles}
\State $ b_y \gets h_y-a_y-1 $
\State $ \kmin_\I \gets k(a_x,a_y)$ \Comment{look up minimum sizes of the components}
\State $ \kmin_\II \gets k(b_x,a_y)$
\State $ \kmin_\III \gets k(b_x,b_y)$
\State $ \kmin_\IV \gets k(a_x,b_y)$
\CommentLine{Iterate feasible ways of allocating $k$ among the four quadrants}
\For{$(k_\I,k_\II,k_\III,k_\IV)$ such that $k_\I+k_\II+k_\III+k_\IV=k$}
\If {$k_\I\ge \kmin_\I \;\wedge\; k_\II\ge \kmin_\II \;\wedge\; k_\III\ge \kmin_\III \;\wedge\; k_\IV\ge \kmin_\IV$}
\CommentLine{Compute or look up admissible component bases}
\State $\Bcal_\I \gets$ output from \Call{FindBases}{$k_\I,a_x,a_y$}
\State $\Bcal_\II \gets$ output from \Call{FindBases}{$k_\II,b_x,a_y$}
\State $\Bcal_\III\gets$ output from \Call{FindBases}{$k_\III,b_x,b_y$}
\State $\Bcal_\IV \gets$ output from \Call{FindBases}{$k_\IV,a_x,b_y$}
\For{$ (B_\I, B_\II, B_\III, B_\IV) \in \Bcal_\I \times \Bcal_\II \times \Bcal_\III \times \Bcal_\IV $}\label{line:innerloop}
\State $A_\I \gets B_\I$
\State $A_\II \gets \{(h_x\!-\!x, \; y) : (x,y)\in B_\II\}$ \Comment{Mirror $x$ coordinates}
\State $A_\III \gets \{(h_x\!-\!x, \; h_y\!-\!y) : (x,y)\in B_\III\}$ \Comment{Mirror $x,y$ coordinates}
\State $A_\IV \gets \{(x, \; h_y\!-\!y) : (x,y)\in B_\IV\}$ \Comment{Mirror $y$ coordinates}
\State $A \gets A_\I \cup A_\II \cup A_\III \cup A_\IV$ \Comment{Concatenate components}\label{line:glue}
\If {$ A+A = R $} \Call{Print}{$A$} \Comment{Found a basis} \EndIf
\EndFor
\EndIf
\EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}
In order to determine the value of $k^*(s_x,s_y)$, just run
Algorithm~\ref{alg:mim} repeatedly, beginning with
$k=\kmin_\I+\kmin_\II+\kmin_\III+\kmin_\IV$ since certainly there are
no solutions below that size, and increase $k$ in steps of~$1$ until
some solutions are found.
\begin{example}
A restricted basis $ A $ for $ R = [0,10]\times[0,10] $ satisfies
$A\subseteq R_h=[0,5]\times[0,5]$. The first quadrant of $R_h$ is
$R_\I = [0,2]\times[0,2]$, and the other quadrants have the same
size. Since $ k(2,2) =4$, we have necessarily
$|A| \geq 4+4+4+4 = 16 $. There is only one $4$-basis for
$[0,2]\times[0,2]$, so for $k=16$ there is only one combination to
check in the innermost loop of Algorithm~\ref{alg:mim}. But this
combination does not give a basis for $[0,10]\times[0,10]$, so more
than $16$ elements are needed.
It turns out that $k=20$ is enough. After some simple pruning
conditions (not shown in Algorithm~\ref{alg:mim}) we find that the
only possible allocations of $20$ elements are
$(k_\I,k_\II,k_\III,k_\IV) = (4,6,4,6)$ and $(5,5,5,5)$. There are
nine $5$-bases and eighteen $6$-bases for $[0,2]\times[0,2]$, so the
first allocation leads to $1 \cdot 18 \cdot 1 \cdot 18 = 324$
combinations to be checked, and the second gives
$9 \cdot 9 \cdot 9 \cdot 9 = 6561$ combinations. Out of these, we
find $17$ restricted solutions. This is less than one second of
computation. In comparison, finding \emph{all} $20$-bases for the
$10$-square with our implementation of Algorithm~\ref{alg:search}
takes more than an hour.
\end{example}
There are a few ways to significantly prune the number of candidate
solutions that need to be checked. Firstly, the complete sumset of a
candidate restricted basis does not have to be calculated immediately.
A necessary condition for a restricted basis is that any two neighboring quadrants form a restricted basis along one of the coordinate axes. It therefore suffices to first check whether this
condition is satisfied for all four neighboring quadrant pairs. Only
if the condition is met does the full sumset need to be checked.
Secondly, often some of the component pieces have the same dimensions
(indeed all of them if $h_x,h_y$ are both odd). If the pieces also
have the same cardinality, then the set of candidate solutions is the
same for all of them, up to suitable coordinate transformations.
\begin{example} \label{ex:mim_same_dimensions}
Consider a restricted basis $ A $ for the square $[0,s]\times[0,s]$,
with $s/2 = 2a+1$ odd and $a \ge 0$. Each quadrant has the same
dimensions $a_x=b_x=a_y=b_y=a$. If all component sets also have
equal cardinality, then the candidates for $A_\II$, $A_\III$ and
$A_\IV$ are the same as for $A_\I$, up to suitable mirroring.
Furthermore, if the sumset $ (A_\I \cup A_\II) + (A_\I \cup A_\II)$
does not cover $[0,s]\times[0,a]$, then all candidate solutions
containing any rotation of this pair can be pruned.
\end{example}
Thirdly, when components have different cardinalities, the order in
which they are concatenated matters. One possible strategy is to first concatenate
component pairs of low cardinality, not only because they usually have
fewer component solutions to try out, but also because they are less
likely to produce feasible concatenations than pairs of higher
cardinality. Occasionally, an infeasible concatenation
rules out all potential solutions containing high cardinality components.
Then these components do not even have to be computed in the first
place.
\begin{example}
Consider the square restricted basis $ A $ in Example~\ref{ex:mim_same_dimensions}. Let the cardinality of this basis be
$4\kmin+ \tilde{k} = 4\kmin+ (\tilde{k}_\I+\tilde{k}_\II+\tilde{k}_\III+\tilde{k}_\IV) $, where $\tilde{k}_\I,\ldots, \tilde{k}_\IV $ represent the number of
extra elements in each quadrant, which are now of equal dimensions. Let $ \tilde{k}=3 $. After accounting for rotational and mirror symmetries of $ A $, it turns out that there are four unique ways to distribute the extra elements:
$(\tilde{k}_\I,\tilde{k}_\II,\tilde{k}_\III,\tilde{k}_\IV) =
(0,0,0,3)$,
$(0,0,1,2)$, $(0,1,0,2)$, or $(0,1,1,1)$. If the concatenation of pair
$(\tilde{k}_\I,\tilde{k}_\II) = (0,0) $ gives no solutions, then the
candidate solutions containing pairs
$(\tilde{k}_\III,\tilde{k}_\IV) = (0,3) $ and
$(\tilde{k}_\III,\tilde{k}_\IV) = (1,2) $ are discarded. Consequently, we avoid computing the potentially many solutions of the $ (\kmin + 3 )$-basis altogether.
\end{example}
\section{Numerical results}
\label{sec:results}
We now describe some results obtained for small rectangles with
Algorithms \ref{alg:search} and \ref{alg:mim}. Examples of minimal
bases are shown in Figures~\ref{fig:nr_bases} and \ref{fig:r_bases}.
We note that especially the restricted solutions in
Figure~\ref{fig:r_bases} exhibit regular structure that can perhaps be
generalized to larger bases.
In the result listings, $m$ is the number of all minimal bases, and
$ m_\text{u} $ is the number of ``unique'' bases after taking into
account rotation and mirror symmetries. Each basis may have up to 8
symmetric variants if the target is square, and up to 4 variants
otherwise.
\begin{figure}[H]
\centerline{\includegraphics[width=1\textwidth]{nr_bases_7}}
\caption{Some minimal bases for $s_x=7$ and varying $s_y$.}
\label{fig:nr_bases}
\end{figure}
\subsection{Results for squares}
Table~\ref{tab:results_nonrestr_square} summarizes the minimal basis
sizes for squares up to $ s=13 $. For $s \le 12$ we have generated
and counted all minimal bases. Regarding $s=13$, we deduce that
$k(13,13)=26$, because Algorithm~\ref{alg:search} finds no solutions
with $25$ elements, but we can construct a basis with $26$ elements
(see Figure~\ref{fig:nr_13}).
We also observe that in small even-sided instances $s=2,4,6,8,10,12$
one of the minimal solutions is the boundary basis. In small odd-sided
instances $s=1,3,5,9,11$ one of the minimal solutions is the L-shaped
basis. Cases $s=7, 13$ stand out as exceptions where the L-shaped
basis is not minimal (recall Figures~\ref{fig:nr_7}
and~\ref{fig:nr_13}).
\begin{figure}[H]
\centerline{\includegraphics[width=1\textwidth]{r_bases_14}}
\caption{Some minimal restricted bases for $ s_x = 14$, varying $s_y$.}
\label{fig:r_bases}
\end{figure}
Concerning the restricted case, Table~\ref{tab:results_restr_square}
summarizes the results for squares up to $s=46$. For $s\le 26$ we
generated and counted the minimal bases. For $28 \le s \le 46$ we
only determined the value of $k^*(s,s)$, but did not generate the
bases. For example, since we found that there is no restricted
$91$-basis for the $46$-square, we can deduce that $k^*(46,46)=92$ as
the boundary basis has this size. In all even-sided squares with $2
\le s \le 46$, we have $k^*(s,s)=2s$, which is attained by the
boundary basis.
Although the simple L-shaped and boundary bases provide minimal or
almost minimal solutions for small squares, having the full collection
of minimal solutions can be useful from an application perspective.
In some sensor array applications it is beneficial to avoid placing
sensor elements near each other, so as to avoid mutual coupling
effects that cause degraded performance~\cite{liu2017}. This may lead
to a secondary optimization goal or constraint, and one may search the
collection of minimal-size bases in order to satisfy this constraint.
\subsection{Results for rectangles}
The situation with rectangles is quite different from that with
squares: if the aspect ratio $\rho=(s_y+1)/(s_x+1)$ is not equal to~1,
then minimal bases may be much smaller than the L-shaped and boundary
bases.
\begin{table}[H]
\begin{center}
\begin{tabular}[t]{|r|r|r|r|}
\hline
$ s $ & $ k^* $& $ m $ & $ m_\text{u} $\\
\hline
0 & 1 & 1 & 1\\
2 & 4 & 1 & 1\\
4 & 8 & 1 & 1\\
6 &12 &1 & 1\\
8 & 16 & 9 & 5\\
10 & 20 & 17 & 4\\
12 & 24 & 58 & 16\\
14 & 28 & 163 & 28\\
16 & 32 & 451 & 72\\
18 & 36 & 2047 & 276\\
20 & 40 & 8451 & 1133\\
22 & 44 & 43807 & 5575\\
24 & 48 & 213859 & 27108\\
26 & 52 & 1273607 & 159744\\
28 & 56 & & \\
30 & 60 & & \\
32 & 64 & & \\
34 & 68 & & \\
36 & 72 & & \\
38 & 76 & & \\
40 & 80 & & \\
42 & 84 & & \\
44 & 88 & & \\
46 & 92 & & \\
\hline
\end{tabular}
\caption{Minimal restricted bases for squares.}
\label{tab:results_restr_square}
\end{center}
\end{table}
Minimal bases for rectangles are summarized in
Table~\ref{tab:results_nonrestr_rect}, and Tables
\ref{tab:results_restr_rect} and~\ref{tab:results_restr_sy2} for the
restricted case. In order to compare the minimal solutions to the
L-shaped and boundary bases, the quantity $ \Delta k = k-k_\text{t} $
is computed. Here $ k_\text{t} $ is the number of elements in the best
applicable trivial solution, which is the boundary basis when $s_x$
and $s_y$ are even, and the L-shaped basis otherwise, except when
$ s_y = 0 $ where the trivial solution is a one-dimensional basis with
$\lceil s_x/2 \rceil +1 $ elements at $ 0,1,\ldots ,\lceil s_x/2 \rceil$.
\begin{table}[H]
\centering
\input{r_solutions.tex}
\caption{Minimal restricted bases for rectangles.}
\label{tab:results_restr_rect}
\end{table}
\begin{table}[H]
\centering
\input{r_sy2_solutions.tex}
\caption{Minimal restricted bases for $ s_y=2 $.}
\label{tab:results_restr_sy2}
\end{table}
Tables~\ref{tab:results_nonrestr_rect} and
\ref{tab:results_restr_rect} show that minimal (unrestricted and
restricted) bases use increasingly fewer elements than the trivial
solutions as the aspect ratio deviates further from~$1$. This is also
apparent from Figure~\ref{fig:rho_vs_c}, which shows the efficiency
\eqref{eq:efficiency} of the minimal bases as a function of aspect
ratio, along with the asymptotical efficiencies of the L-shaped basis,
and two parametric bases that are introduced in
section~\ref{sec:lower_bounds} (Definitons~\ref{def:densesparse} and
\ref{def:shortbars}). Specifically, the L-shaped basis has efficiency
$ c \to \rho/(1+\rho)^2$, as $ s_x\to \infty$, since it requires
$s_x+s_y+1 = (1+\rho)s_x+\rho$ elements for its sumset to cover the
$ [0,s_x]\times[0,s_y] = [0,s_x]\times[0,\rho(s_x+1)-1]$
rectangle. Similarly, the asymptotical efficiency of the dense-sparse
and short-bars bases is $ c = 1/4 $, as shown later in
Corollary~\ref{cor:eff_ds} of section~\ref{sec:lower_bounds}. The
efficiency of the minimal bases in Figure~\ref{fig:rho_vs_c} seem to
approach $ 1/4 $ as $ s_x $ and $ \rho $ increase.
A peculiarity is illustrated in Figure~\ref{fig:r_sy2}, which
shows two minimal restricted bases for which the number of elements
actually decreases as the target width increases. Not only is
$k^*(62,2) = 28 > k^*(64,2) = 26$, but the number of solutions for the
two cases is also drastically different. The former has $125247$
unique solutions, whereas the latter has only~$1$. The solutions for
$s_y=2 $ listed in Table~\ref{tab:results_restr_sy2} reveal that a
similar effect also occurs for $ s_x=104 $ and $ 116 $. The same also
applies to $ s_y=0 $, since $ k^*(s_x,2) = 2k^*(s_x,0) $ by
Lemma~\ref{lemma:shallow_restr}.
An overview of currently known minimal restricted bases is shown in
Figure~\ref{fig:r_map}. The colors of the pixels correspond to the
minimal number of elements. At present, bases up to about $k=50$ are
practical to list exhaustively. For clarity of presentation,
restricted one-dimensional bases are not plotted for $ s_x>120 $.
\begin{figure}[H]
\centerline{\includegraphics[width=1\textwidth]{nr_rho_vs_c}}
\caption{Efficiency of minimal bases, and asymptotical efficiency of L-shaped basis (dotted red line) and dense-sparse/short-bars bases (dashed blue line). The L-shaped basis is suboptimal when $ \rho\neq 1 $ and $ s_x\to\infty $, whereas the dense-sparse and short-bars bases asymptotically achieve $ c=1/4 $ for any $ \rho $. The asymptotic efficiency of minimal bases is unknown.}
\label{fig:rho_vs_c}
\end{figure}
\begin{figure}[H]
\begin{subfigure}{1\textwidth}
\centerline{\includegraphics[width=1\textwidth]{r_62_2_28}}
\label{fig:r_sy2_a}
\end{subfigure}
\begin{subfigure}[b]{1\textwidth}
\centerline{\includegraphics[width=1\textwidth]{r_64_2_26}}
\label{fig:r_sy2_b}
\end{subfigure}
\caption{Two restricted bases for $ s_y=2 $, for which the minimal
number of elements decreases as the rectangle width increases.}
\label{fig:r_sy2}
\end{figure}
\begin{figure}[H]
\centerline{\includegraphics[width=1\textwidth]{r_map}}
\caption{Minimal number of elements in restricted bases.}
\label{fig:r_map}
\end{figure}
\section{Bounds for large-scale behaviour}
\label{sec:largescale}
For very large rectangles it seems difficult to determine the minimum
basis size exactly. Towards understanding the large-scale behaviour,
we establish some upper and lower bounds on the efficiency $c = N/k^2$
(recall~\eqref{eq:efficiency}) of such bases.
\subsection{Upper bounds}
A crude upper bound on efficiency is obtained by observing that from
$k$ elements at most $(k+1)k/2$ different pairwise sums can be formed,
considering that $a+b=b+a$ and that sums of the form $a+a$ are
allowed. It follows that $N \le (k+1)k/2$, so for any planar basis we
have
\begin{equation*}
c \le 0.5 + O\bigl(1/\sqrt{N}\bigr).
\label{eq:upperany}
\end{equation*}
In one dimension, upper bounds tighter than $0.5$ have been
established by analytic and combinatorial methods. For all $s_x$
large enough, by Yu's Theorem~1.1~\cite{yu2015} we have
\begin{equation}
s_x / k(s_x,0)^2 \le 0.45851 = \alpha,
\label{eq:yu_nonrestr}
\end{equation}
and by Yu's Theorem~1.2~\cite{yu2009} we have
\begin{equation}
s_x / k^*(s_x,0)^2 \le 0.41983 = \beta.
\label{eq:yu_restr}
\end{equation}
Combining Yu's theorems with simple counting, we obtain the following
bounds with rectangles of small constant height. For brevity, if $P$
is a set of points, we denote $P_y = \{x : (x,y) \in P\}$ and call
this the \emph{row $y$} of~$P$.
\begin{theorem}
For all $s_x$ large enough, any basis for $[0,s_x]\times[0,1]$ has
efficiency $c < 0.4311$.
\label{thm:upper1}
\end{theorem}
\begin{proof}
Assume that $s_x$ is large enough that \eqref{eq:yu_nonrestr} holds.
Without loss of generality let $A$ be admissible, and
let its rows $A_0,A_1$ contain $k_0,k_1$ elements, respectively.
Now $A_0+A_0$ must cover $R_0 = [0,s_x]$, and $A_0+A_1$ must cover
$R_1 = [0,s_x]$. By applying \eqref{eq:yu_nonrestr} on row~$0$, and
by counting sums on row~$1$, we obtain
\begin{align*}
s_x &\le \alpha k_0^2,\\
s_x &\le k_0 k_1.
\end{align*}
For any $k$, the minimum of these two bounds is maximized at $k_1 =
\alpha k_0$, implying that $k = (1+\alpha)k_0$ and
\[
s_x/k^2 \le \frac{\alpha}{(1+\alpha)^2} < 0.215542.
\]
Since $N = |R| = 2(s_x+1)$, we have $N/k^2 < 0.4311$ for $s_x$ large
enough.
\end{proof}
\begin{theorem}
For all $s_x$ large enough, any basis for $[0,s_x]\times[0,2]$ has
efficiency $c < 0.4190$.
\label{thm:upper2}
\end{theorem}
\begin{proof}
Assume that $s_x$ is large enough that \eqref{eq:yu_nonrestr} holds.
Without loss of generality let $A$ be admissible, and let its rows
$A_0,A_1,A_2$ contain $k_0,k_1,k_2$ elements, respectively. Now
$A_0+A_0$ must cover $R_0 = [0,s_x]$, and $A_0+A_1$ must cover $R_1
= [0,s_x]$, and finally $(A_0+A_2) \cup (A_1+A_1)$ must cover $R_2 =
[0,s_x]$. By applying \eqref{eq:yu_nonrestr} on row~$0$, and by
counting sums on rows $1$ and~$2$, we obtain
\begin{align*}
s_x &\le \alpha k_0^2,\\
s_x &\le k_0 k_1,\\
s_x &\le k_0 k_2 + k_1^2/2 + k_1/2.
\end{align*}
For any $k$, the minimum of these three bounds is maximized at their
intersection, and by routine manipulations we obtain
\[
s_x/k^2 \le \frac{\alpha}{(1+2\alpha-\alpha^2/2)^2} + o_{s_x}(1)
< 0.139663
\]
for $s_x$ large enough. Since $N = |R| = 3(s_x+1)$, we have $c = N/k^2
< 0.4190$ for $s_x$~large enough.
\end{proof}
Any improvements to the one-dimensional bound~\eqref{eq:yu_nonrestr}
will imply corresponding improvements to Theorems \ref{thm:upper1}
and~\ref{thm:upper2}. One could also apply the same proof technique
with larger constant values of $s_y$, but it then becomes more
complicated to maximize the simultaneous upper bounds of $s_x$.
Numerical maximization suggests decreasing upper bounds as $s_y$
increases, for example, around $0.4126$ with $s_y=3$, and around
$0.4087$ with $s_y=4$. This begs the question: what happens when $s_y$ goes to infinity?
Turning our attention to the restricted case we obtain the following
bounds.
\begin{theorem}
For all $s_x$ large enough, any restricted basis for $[0,s_x]\times[0,2]$
has efficiency $c < 0.3149$.
\end{theorem}
\begin{proof}
Combine Lemma~\ref{lemma:shallow_restr} with the
bound~\eqref{eq:yu_restr} and the fact that $|R|=3(s_x+1)$.
\end{proof}
\begin{theorem}
For all $s_x$ large enough, any restricted basis for $[0,s_x]\times[0,4]$
has efficiency $c < 0.3585$.
\end{theorem}
\begin{proof}
Assume that $s_x$ is large enough that \eqref{eq:yu_restr} holds. Let
$A$ be a restricted basis for~$R$, and let $k_0,k_1,k_2$ be the
cardinalities of its rows. By applying \eqref{eq:yu_restr} on rows
$0$ and~$4$ of the target, and by counting sums on rows $1$ and~$3$,
we obtain
\begin{align*}
s_x &\le \beta k_0^2,\\
s_x &\le k_0 k_1,\\
s_x &\le k_1 k_2,\\
s_x &\le \beta k_2^2.
\end{align*}
The minimum of these four bounds is maximized at their intersection,
where $k_0=k_2$ and $k_1=\beta k_0$, thus $k = (2+\beta)k_0$.
Then we obtain
\[
s_x/k^2 \le \frac{\beta}{(2+\beta)^2} < 0.071698.
\]
Since $N = |R| = 5(s_x+1)$, we have $c = N/k^2 < 0.3585$ for $s_x$ large
enough.
\end{proof}
\subsection{Lower bounds}\label{sec:lower_bounds}
As with one-dimensional bases, also in planar bases it is relatively
easy to obtain an efficiency of approximately $1/4$ for large
rectangles. For squares this is particularly easy: the L-shaped basis
for an $s$-square has $k=2s+1$, so $c = 0.25 + O(1/s)$. The boundary
basis has $k=2s$, so its efficiency has the same asymptotic form.
However, for non-square rectangles, the efficiency of the L-shaped and
boundary bases falls below $1/4$. Indeed, consider rectangles
$[0,s_x]\times[0,s_y]$ with a constant aspect ratio $\rho \ne 1$. The
L-shaped basis has $k=s_x+s_y+1 = (1+\rho)s_x+\rho$, so
\begin{equation}
c \to \rho / (1+\rho)^2 < 1/4
\label{eq:belowquarter}
\end{equation}
as~$s_x \to \infty$. The case with the boundary basis is similar.
For example, if the aspect ratio is $\rho=1/9$, then both the L-shaped
and boundary bases have only $c\to 0.09$ in the limit.
The following parametric constructions demonstrate that an asymptotic
efficiency of~$1/4$ can be achieved with rectangles of essentially any
constant aspect ratio, as both $s_x$ and $s_y$ go to infinity. The
first construction, a \emph{dense-sparse basis}, is the union of a
dense part (a filled rectangle) and a sparse part (regularly spaced
single elements). The second construction, a \emph{short-bars basis},
consists of short, regularly spaced horizontal and vertical bars.
Both constructions are illustrated in Figure~\ref{fig:quarter}. We
use here the notation
\[
[a,(t),b] = \{a,\; a+t,\; a+2t,\; \ldots,\; b\}
\]
for a finite arithmetic progression from $a$ to $b$ with step
length~$t$, with the provision that $b-a$ is divisible by~$t$.
\begin{definition}
\label{def:densesparse}
The \emph{dense-sparse basis} with parameters $t_x,t_y \ge 1$ is the
set $A = B \cup C$, where $B = [0,t_x-1] \times [0,t_y-1]$ and $C =
[0,(t_x),t_x^2-t_x] \times [0,(t_y),t_y^2-t_y]$.
\end{definition}
\begin{theorem}
\label{thm:densesparse}
The dense-sparse basis has $|A|=2t_xt_y-1$ and $A+A \supseteq
[0,t_x^2-1]\times[0,t_y^2-1]$.
\end{theorem}
\begin{proof}
Since $|B|=|C|=t_xt_y$ and $B \cap C = \{(0,0)\}$, the claim on
$|A|$ follows. For any point $(x,y) \in R$, let $x = b_x + c_x$
with $b_x \in [0,t_x-1]$ and $c_x \in [0,(t_x),t_x^2-t_x]$.
Similarly let $y = b_y + c_y$ with $b_y \in [0,t_y-1]$ and $c_y \in
[0,(t_y),t_y^2-t_y]$. Now $(x,y) = (b_x,b_y) + (c_x,c_y)$ with
$(b_x,b_y)\in B$ and $(c_x,c_y) \in C$. Thus $(x,y) \in B+C
\subseteq A+A$.
\end{proof}
\begin{figure}[H]
\begin{subfigure}[b]{0.48\textwidth}
\centerline{\includegraphics[width=1\textwidth]{quarter_ds}}
\caption{}
\label{fig:quarter_ds}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.48\textwidth}
\centerline{\includegraphics[width=1\textwidth]{quarter_sb}}
\caption{}
\label{fig:quarter_sb}
\end{subfigure}
\caption{Two bases for the rectangle $[0,24]\times[0,8]$: (a)
a dense-sparse basis (Definition~\ref{def:densesparse}), (b) a short-bars basis (Definition~\ref{def:shortbars}), both with
parameters $t_x=5$, $t_y=3$. Both bases have only $29$
elements, while an L-shaped basis for the same rectangle has
$33$ elements.}
\label{fig:quarter}
\end{figure}
\begin{definition}
\label{def:shortbars}
The \emph{short-bars basis} with parameters $t_x,t_y \ge 1$ is the
set $A = B \cup C$, where $B = [0,t_x-1] \times [0,(t_y),t_y^2-t_y]$
and $C = [0,(t_x),t_x^2-t_x] \times [0,t_y-1]$.
\end{definition}
\begin{theorem}
\label{thm:shortbars}
The short-bars basis has $|A|=2t_xt_y-1$ and $A+A \supseteq
[0,t_x^2-1]\times[0,t_y^2-1]$.
\end{theorem}
\begin{proof}
Since $|B|=|C|=t_xt_y$ and $B \cap C = \{(0,0)\}$, the claim on $|A|$
follows. For any point $(x,y) \in R$, let $x = b_x + c_x$ with
$b_x \in [0,t_x-1]$ and $c_x \in [0,(t_x),t_x^2-t_x]$. Similarly
let $y = b_y + c_y$ with $b_y \in [0,(t_y),t_y^2-t_y]$ and
$c_y \in [0,t_y-1]$. Now $(x,y) = (b_x,b_y) + (c_x,c_y)$ with
$(b_x,b_y)\in B$ and $(c_x,c_y) \in C$. Thus
$(x,y) \in B+C \subseteq A+A$.
\end{proof}
\begin{corollary} \label{cor:eff_ds}
Let $\rho = p^2/q^2$ be a fixed aspect ratio, where $p$ and $q$ are
integers, and let $h \ge 1$ be an integer. Then both the
dense-sparse basis and the short-bars basis, with parameters
$t_x = qh$ and $t_y = ph$, are bases for the rectangle
$[0,t_x^2-1] \times [0, t_y^2-1]$, which has the said aspect ratio.
The efficiency of either basis is
\[
c = \frac{t_x^2 t_y^2}{(2 t_x t_y - 1)^2} = 0.25 + O(1/h^2).
\]
\end{corollary}
\begin{corollary} \label{cor:suboptimal}
For any fixed aspect ratio $\rho = p^2/q^2 \ne 1$, with $p$ and $q$
integers, the L-shaped basis and the boundary bases are
asymptotically suboptimal as $s_x \to \infty$.
\end{corollary}
For arbitrarily wide rectangles of any \emph{constant height} we
present a basis construction whose asymptotic efficiency
\emph{exceeds} $1/4$. The construction is somewhat analogous to
Mrose's one-dimensional basis~\cite{mrose1979}, hence the name. As a
mnemonic for our symbols here, note that in $I_1,I_2,I_3$ the set of
$x$~coordinates is an interval; in $T$ it is a $t$-step arithmetic
progression; and in $S$ it is a ``sparse'' $(t+1)$-step arithmetic
progression.
\begin{definition}
\label{def:stacked}
The \emph{stacked Mrose basis} with parameters $s_y \ge 0$ and $t \ge 1$
is the set $I_1 \cup I_2 \cup I_3 \cup T \cup S$, where
\begin{align*}
I_1 &= [0,t] \times Y, \\
T &= [0, (t), at^2-t] \times \{0\}, \\
S &= [at^2, (t+1), (a+1)t^2-1] \times Y, \\
I_2 &= [2at^2, 2at^2+t] \times Y, \\
I_3 &= [(3a+1)t^2, (3a+1)t^2+t] \times Y,
\end{align*}
and $Y=[0,s_y]$ and $a=4s_y+3$.
\end{definition}
\begin{theorem}
\label{thm:stacked}
If $A$ is a stacked Mrose basis, then $|A|=(8s_y+7)t + (3s_y+1)$ and
$A+A \supseteq [0, (16s_y+14)t^2-1] \times [0,s_y]$.
\end{theorem}
\begin{proof}
Let us first determine the size of the basis. We observe that
$\lvert I_1 \rvert = \lvert I_2 \rvert = \lvert I_3 \rvert =
(t+1)(s_y+1)$, $\lvert T \rvert = at$, and $\lvert S \rvert =
t(s_y+1)$. Because the parts are otherwise disjoint except that
$I_1 \cap T = \{(0,0),(t,0)\}$, the claim on $|A|$ follows.
Let us next verify that $A+A$ covers the desired target rectangle.
We check seven consecutive subrectangles in turn.
\begin{enumerate}
\item $[0, at^2-1] \times Y$ is covered by $I_1 + T$.
\item $[at^2, (a+1)t^2-1] \times Y$ is covered by $I_1 + S$.
\item $[(a+1)t^2, 2at^2-1] \times Y$ is covered by $T + S$.
\item $[2at^2, 3at^2-1] \times Y$ is covered by $I_2 + T$.
\item $[3at^2, (3a+1)t^2-1] \times Y$ is covered by $I_2 + S$.
\item $[(3a+1)t^2, (4a+1)t^2-1] \times Y$ is covered by $I_3 + T$.
\item $[(4a+1)t^2, (4a+2)t^2-1] \times Y$ is covered by $I_3 + S$.
\end{enumerate}
Because $I_1,I_2,I_3,T,S \subseteq A$, combining observations (1)--(7)
and $4a+2 = 16s_y+14$
we have
\[
A+A \supseteq [0, (16s_y+14)t^2-1] \times Y
\]
as claimed.
\end{proof}
\begin{corollary}
The stacked Mrose basis has efficiency
\[
c = \frac{N}{k^2} = \frac{(16s_y+14)t^2 \cdot (s_y+1)}{\left( (8s_y+7)t \right)^2 + O(t)}
\xrightarrow[t \to \infty]{} \frac{2s_y+2}{8s_y+7}.
\]
\end{corollary}
\begin{example}
With $s_y=1$, Definition~\ref{def:stacked} gives a basis of size
$k=15t+4$ for the rectangle $[0, 30t^2-1]\times[0,1]$, with
efficiency tending to $4/15 > 0.2666$ as $t \to \infty$.
\end{example}
\begin{example}
With $s_y=2$, Definition~\ref{def:stacked} gives a basis of size
$k=23t+7$ for the rectangle $[0, 46t^2-1]\times[0,2]$, with
efficiency tending to $6/23 > 0.2609$ as $t \to \infty$.
Figure~\ref{fig:thm_1} illustrates this basis in the case of $t=10$.
\end{example}
Although a stacked Mrose basis can be constructed arbitrarily high,
its efficiency tends down to $1/4$ as $s_y$ goes to infinity. We do
not know whether $1/4$ can be asymptotically exceeded for rectangles
with both dimensions going to infinity (e.g., with a constant aspect
ratio).
\begin{figure}[H]
\centerline{\includegraphics[width=1\textwidth]{thm1}}
\caption{A schematic illustration of the stacked Mrose basis
(Definition~\ref{def:stacked}) with parameters $s_y=2$ and
$t=10$. In this case $a=11$ and $s_x=4599$.}
\label{fig:thm_1}
\end{figure}
\section{Conclusion and open questions}
Planar additive bases are a natural generalization of the classical
one-dimensional additive bases, and it may be slightly surprising that
they have not been studied much. In this paper, some initial results
have been provided. For small squares and rectangles, we have
determined the minimum cardinalities exactly; and for larger
instances, we have established some lower and upper bounds, although
the bounds are not very tight.
Apart from the obvious desires of extending the finite results and
improving the bounds, we would like to pose some open questions. For
squares, the ``trivial'' L-shaped and boundary bases achieve an
asymptotic efficiency of $1/4$. For non-square rectangles, the
trivial bases fall below $1/4$, but our parametric constructions still
attain $1/4$. Can this be improved at~all? We pose this question in
two forms, one for squares and one for general rectangles.
\begin{question}
Does any square $[0,s] \times [0,s]$ admit an additive basis of less
than $2s$ elements?
\end{question}
\begin{question}
Is there a constant $c > 1/4$ such that there are arbitrarily high
and wide rectangles admitting an additive basis of efficiency at
least $c$?
\end{question}
We would not be too surprised by a positive answer to our questions
above. We recall that in one-dimensional additive bases, contrary to
Rohrbach's conjecture~\cite[p.~9]{rohrbach1937}, parametric
constructions with efficiencies over $1/4$ have been
found~\cite{hammerer1976,mrose1979,kohonen2017}. Also, for
constant-height rectangles, our parametric construction (stacked Mrose
basis) exceeds $1/4$. But if both dimensions tend to infinity, the
question is open.
For other directions of future research, we note that additive bases
are conceptually closely related to \emph{difference bases}, where the
object of interest is the difference set $A-A$. One-dimensional
difference bases have been studied by, e.g., Leech~\cite{leech1956}
and Wichmann~\cite{wichmann1963anote}. Difference bases find
applications in sensor arrays for passive sensing, particularly when
second-order statistics of the element outputs are processed
\cite{hoctor1990}. Due to the use of data covariance in many
applications, such as direction-of-arrival estimation, both one- and
two-dimensional difference bases have received attention recently
\cite{linebarger1993difference,pal2010nested,liu2017}. We also point
out that non-rectangular, for example hexagonal, grids have received
some attention in array processing using difference
bases~\cite{haubrich1968array}. Additive bases for non-rectangular
targets would be another interesting direction of research.
\section{Acknowledgments}
We thank the anonymous referee for insightful suggestions to improve
the exposition.
\begin{thebibliography}{10}
\bibitem{challis1993}
M.~F. Challis, Two new techniques for computing extremal $h$-bases ${A}_k$,
{\em Comput. J.} {\bf 36} (1993), 117--126.
\bibitem{eliahou1998}
S.~Eliahou and M.~Kervaire, Sumsets in vector spaces over finite fields, {\em
J. Number Theory} {\bf 71} (1998), 12--39.
\bibitem{eliahou2005}
S.~Eliahou and M.~Kervaire, Minimal sumsets in infinite abelian groups, {\em J.
Algebra} {\bf 287} (2005), 449--457.
\bibitem{eliahou2003}
S.~Eliahou, M.~Kervaire, and A.~Plagne, Optimally small sumsets in finite
abelian groups, {\em J. Number Theory} {\bf 101} (2003), 338--3487.
\bibitem{hammerer1976}
N.~H{\"a}mmerer and G.~Hofmeister, Zu einer {V}ermutung von {R}ohrbach, {\em J.
Reine Angew. Math.} {\bf 286/287} (1976), 239--247.
\bibitem{han2004}
S.~P.~S. Han, The boundary structure of the sumset in {$\mathbf{Z}^2$}.
\newblock In D.~Chudnovsky, G.~Chudnovsky, and M.~Nathanson, editors, {\em
Number Theory}, Springer, 2004, pp.~201--218.
\bibitem{haubrich1968array}
R.~A. Haubrich, Array design, {\em Bulletin of the Seismological Society of
America} {\bf 58} (1968), 977--991.
\bibitem{hoctor1990}
R.~T. Hoctor and S.~A. Kassam, The unifying role of the coarray in aperture
synthesis for coherent and incoherent imaging, {\em Proc. IEEE}
{\bf 78} (1990), 735--752.
\bibitem{kohonen2015early}
J.~Kohonen, Early pruning in the restricted postage stamp problem.
\newblock Preprint, 2015, available at \url{https://arxiv.org/abs/1503.03416}.
\bibitem{kohonen2014meet}
J.~Kohonen, A meet-in-the-middle algorithm for finding extremal restricted
additive 2-bases, {\em J. Integer Sequences} {\bf 17} (2014),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Kohonen2/kohonen5.html}{Article 14.6.8}.
\bibitem{kohonen2017}
J.~Kohonen, An improved lower bound for finite additive 2-bases, {\em J. Number
Theory} {\bf 174} (2017), 518--524.
\bibitem{kohonen2014}
J.~Kohonen and J.~Corander, Addition chains meet postage stamps: Reducing the
number of multiplications, {\em J. Integer Sequences} {\bf 17} (2014),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Kohonen/kohonen2.html}{Article
14.3.4}.
\bibitem{kozick1991}
R.~J. Kozick and S.~A. Kassam, Linear imaging with sensor arrays on convex
polygonal boundaries, {\em IEEE Trans. Systems Man Cybernet.} {\bf 21}
(1991), 1155--1166.
\bibitem{leech1956}
J.~Leech, On the representation of 1, 2, \ldots, $n$ by differences, {\em J.
Lond. Math. Soc.} {\bf 31} (1956), 160--169.
\bibitem{linebarger1993difference}
D.~A. Linebarger, I.~H. Sudborough, and I.~G. Tollis, Difference bases and
sparse sensor arrays, {\em IEEE Trans. Inform. Theory} {\bf 39} (1993),
716--721.
\bibitem{liu2017}
C.~L. Liu and P.~P. Vaidyanathan, Hourglass arrays and other novel 2-{D} sparse
arrays with reduced mutual coupling, {\em IEEE Trans. Signal Process.} {\bf
65} (2017), 3369--3383.
\bibitem{lunnon1969}
W.~F. Lunnon, A postage stamp problem, {\em Comput. J.} {\bf 12} (1969),
377--380.
\bibitem{mrose1979}
A.~Mrose, Untere {S}chranken f{\"u}r die {R}eichweiten von {E}xtremalbasen
fester {O}rdnung, {\em Abh. Math. Semin. Univ. Hambg.} {\bf 48} (1979),
118--124.
\bibitem{naidu2009}
P.~S. Naidu, {\em Sensor Array Signal Processing}, CRC Press, 2nd edition,
2009.
\bibitem{pal2010nested}
P.~Pal and P.~P. Vaidyanathan, Nested arrays: A novel approach to array
processing with enhanced degrees of freedom, {\em IEEE Trans. Signal
Process.} {\bf 58} (2010), 4167--4181.
\bibitem{riddell1978}
J.~Riddell and C.~Chan, Some extremal 2-bases, {\em Math. Comp.} {\bf 32}
(1978), 630--634.
\bibitem{rohrbach1937}
H.~Rohrbach, Ein {B}eitrag zur additiven {Z}ahlentheorie, {\em Math. Z.} {\bf
42} (1937), 1--30.
\bibitem{wichmann1963anote}
B.~Wichmann, A note on restricted difference bases, {\em J. Lond. Math. Soc.}
{\bf s1-38} (1963), 465--466.
\bibitem{yu2009}
G.~Yu, Upper bounds for finite additive 2-bases, {\em Proc. Amer. Math. Soc.}
{\bf 137} (2009), 11--18.
\bibitem{yu2015}
G.~Yu, A new upper bound for finite additive $h$-bases, {\em J. Number Theory}
{\bf 156} (2015), 95--104.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B13.
\noindent \emph{Keywords:} additive basis, restricted basis, planar basis, rectangular sumset.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A001212},
\seqnum{A008574},
\seqnum{A295771},
\seqnum{A295774}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 15 2018;
revised version received December 17 2018.
Published in {\it Journal of Integer Sequences}, December 17 2018.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}