\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand*\HyPL@Entry[1]{}
\HyPL@Entry{0<</S/D>>}
\citation{rohrbach1937}
\citation{challis1993}
\citation{kohonen2014}
\citation{lunnon1969}
\citation{riddell1978}
\citation{kohonen2017}
\citation{yu2015}
\citation{kozick1991}
\citation{eliahou1998}
\citation{eliahou2005}
\citation{eliahou2003}
\citation{han2004}
\citation{naidu2009}
\citation{hoctor1990}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{2}{section.1}}
\newlabel{sec:intro}{{1}{2}{Introduction}{section.1}{}}
\citation{kozick1991}
\@writefile{toc}{\contentsline {section}{\numberline {2}Definitions and preliminary observations}{3}{section.2}}
\newlabel{sec:preliminary}{{2}{3}{Definitions and preliminary observations}{section.2}{}}
\newlabel{eq:efficiency}{{1}{3}{Definitions and preliminary observations}{equation.2.1}{}}
\newlabel{eq:lbasis}{{2}{3}{Definitions and preliminary observations}{equation.2.2}{}}
\newlabel{eq:boundarybasis}{{3}{3}{Definitions and preliminary observations}{equation.2.3}{}}
\newlabel{lemma:corners_nonrestr}{{1}{3}{Origin corner}{theorem.1}{}}
\citation{challis1993}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{fig:l_5}{{1a}{4}{\relax }{figure.caption.1}{}}
\newlabel{sub@fig:l_5}{{a}{4}{\relax }{figure.caption.1}{}}
\newlabel{fig:b_6}{{1b}{4}{\relax }{figure.caption.1}{}}
\newlabel{sub@fig:b_6}{{b}{4}{\relax }{figure.caption.1}{}}
\newlabel{fig:nr_7}{{1c}{4}{\relax }{figure.caption.1}{}}
\newlabel{sub@fig:nr_7}{{c}{4}{\relax }{figure.caption.1}{}}
\newlabel{fig:nr_13}{{1d}{4}{\relax }{figure.caption.1}{}}
\newlabel{sub@fig:nr_13}{{d}{4}{\relax }{figure.caption.1}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces (a) The L-shaped basis for the 5-square. (b) The boundary basis for the 6-square. (c)\nobreakspace  {}A\nobreakspace  {}minimal basis for the 7-square. (d) A\nobreakspace  {}minimal basis for the 13-square.\relax }}{4}{figure.caption.1}}
\newlabel{fig:intro}{{1}{4}{(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.\relax }{figure.caption.1}{}}
\newlabel{lemma:edges_restr}{{2}{4}{Restricted edges}{theorem.2}{}}
\newlabel{lemma:shallow_restr}{{3}{4}{Two rows}{theorem.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Search algorithm for admissible bases}{4}{section.3}}
\newlabel{sec:nonrestricted}{{3}{4}{Search algorithm for admissible bases}{section.3}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Find all admissible $k$-bases for $[0,s_x]\times [0,s_y]$\relax }}{5}{algorithm.1}}
\newlabel{alg:search}{{1}{5}{Find all admissible $k$-bases for $[0,s_x]\times [0,s_y]$\relax }{algorithm.1}{}}
\newlabel{line:gaps}{{10}{5}{Find all admissible $k$-bases for $[0,s_x]\times [0,s_y]$\relax }{algorithm.1}{}}
\newlabel{line:admissibility}{{18}{5}{Find all admissible $k$-bases for $[0,s_x]\times [0,s_y]$\relax }{algorithm.1}{}}
\citation{kohonen2014meet}
\citation{kohonen2015early}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Minimal bases for squares.\relax }}{6}{table.caption.2}}
\newlabel{tab:results_nonrestr_square}{{1}{6}{Minimal bases for squares.\relax }{table.caption.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Meet-in-the-middle method for restricted bases}{6}{section.4}}
\newlabel{sec:restricted}{{4}{6}{Meet-in-the-middle method for restricted bases}{section.4}{}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Minimal bases for rectangles.\relax }}{7}{table.caption.3}}
\newlabel{tab:results_nonrestr_rect}{{2}{7}{Minimal bases for rectangles.\relax }{table.caption.3}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces MIM decomposition of a restricted basis $ A $. The four components $ A_\text  {I},\ldots  , A_\text  {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_\text  {I},\ldots  , A_\text  {IV}$ must be admissible bases for those rectangles (up to suitable coordinate transformations).\relax }}{8}{figure.caption.4}}
\newlabel{fig:mim}{{2}{8}{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).\relax }{figure.caption.4}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Find all restricted $k$-bases for $[0,s_x]\times [0,s_y]$\relax }}{9}{algorithm.2}}
\newlabel{alg:mim}{{2}{9}{Find all restricted $k$-bases for $[0,s_x]\times [0,s_y]$\relax }{algorithm.2}{}}
\newlabel{line:innerloop}{{20}{9}{Find all restricted $k$-bases for $[0,s_x]\times [0,s_y]$\relax }{algorithm.2}{}}
\newlabel{line:glue}{{25}{9}{Find all restricted $k$-bases for $[0,s_x]\times [0,s_y]$\relax }{algorithm.2}{}}
\newlabel{ex:mim_same_dimensions}{{5}{10}{}{theorem.5}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Numerical results}{11}{section.5}}
\newlabel{sec:results}{{5}{11}{Numerical results}{section.5}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Some minimal bases for $s_x=7$ and varying $s_y$.\relax }}{11}{figure.caption.5}}
\newlabel{fig:nr_bases}{{3}{11}{Some minimal bases for $s_x=7$ and varying $s_y$.\relax }{figure.caption.5}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Results for squares}{11}{subsection.5.1}}
\citation{liu2017}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Some minimal restricted bases for $ s_x = 14$, varying $s_y$.\relax }}{12}{figure.caption.6}}
\newlabel{fig:r_bases}{{4}{12}{Some minimal restricted bases for $ s_x = 14$, varying $s_y$.\relax }{figure.caption.6}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Results for rectangles}{12}{subsection.5.2}}
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces Minimal restricted bases for squares.\relax }}{13}{table.caption.7}}
\newlabel{tab:results_restr_square}{{3}{13}{Minimal restricted bases for squares.\relax }{table.caption.7}{}}
\@writefile{lot}{\contentsline {table}{\numberline {4}{\ignorespaces Minimal restricted bases for rectangles.\relax }}{14}{table.caption.8}}
\newlabel{tab:results_restr_rect}{{4}{14}{Minimal restricted bases for rectangles.\relax }{table.caption.8}{}}
\@writefile{lot}{\contentsline {table}{\numberline {5}{\ignorespaces Minimal restricted bases for $ s_y=2 $.\relax }}{15}{table.caption.9}}
\newlabel{tab:results_restr_sy2}{{5}{15}{Minimal restricted bases for $ s_y=2 $.\relax }{table.caption.9}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces 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 \not =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.\relax }}{16}{figure.caption.10}}
\newlabel{fig:rho_vs_c}{{5}{16}{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.\relax }{figure.caption.10}{}}
\newlabel{fig:r_sy2_a}{{\caption@xref {fig:r_sy2_a}{ on input line 853}}{16}{Results for rectangles}{figure.caption.11}{}}
\newlabel{sub@fig:r_sy2_a}{{}{16}{Results for rectangles}{figure.caption.11}{}}
\newlabel{fig:r_sy2_b}{{\caption@xref {fig:r_sy2_b}{ on input line 857}}{16}{Results for rectangles}{figure.caption.11}{}}
\newlabel{sub@fig:r_sy2_b}{{}{16}{Results for rectangles}{figure.caption.11}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Two restricted bases for $ s_y=2 $, for which the minimal number of elements decreases as the rectangle width increases.\relax }}{16}{figure.caption.11}}
\newlabel{fig:r_sy2}{{6}{16}{Two restricted bases for $ s_y=2 $, for which the minimal number of elements decreases as the rectangle width increases.\relax }{figure.caption.11}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Minimal number of elements in restricted bases.\relax }}{16}{figure.caption.12}}
\newlabel{fig:r_map}{{7}{16}{Minimal number of elements in restricted bases.\relax }{figure.caption.12}{}}
\citation{yu2015}
\citation{yu2009}
\@writefile{toc}{\contentsline {section}{\numberline {6}Bounds for large-scale behaviour}{17}{section.6}}
\newlabel{sec:largescale}{{6}{17}{Bounds for large-scale behaviour}{section.6}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Upper bounds}{17}{subsection.6.1}}
\newlabel{eq:upperany}{{6.1}{17}{Upper bounds}{subsection.6.1}{}}
\newlabel{eq:yu_nonrestr}{{4}{17}{Upper bounds}{equation.6.4}{}}
\newlabel{eq:yu_restr}{{5}{17}{Upper bounds}{equation.6.5}{}}
\newlabel{thm:upper1}{{7}{17}{}{theorem.7}{}}
\newlabel{thm:upper2}{{8}{17}{}{theorem.8}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Lower bounds}{19}{subsection.6.2}}
\newlabel{sec:lower_bounds}{{6.2}{19}{Lower bounds}{subsection.6.2}{}}
\newlabel{eq:belowquarter}{{6}{19}{Lower bounds}{equation.6.6}{}}
\newlabel{def:densesparse}{{11}{19}{}{theorem.11}{}}
\newlabel{thm:densesparse}{{12}{19}{}{theorem.12}{}}
\citation{mrose1979}
\newlabel{fig:quarter_ds}{{8a}{20}{\relax }{figure.caption.13}{}}
\newlabel{sub@fig:quarter_ds}{{a}{20}{\relax }{figure.caption.13}{}}
\newlabel{fig:quarter_sb}{{8b}{20}{\relax }{figure.caption.13}{}}
\newlabel{sub@fig:quarter_sb}{{b}{20}{\relax }{figure.caption.13}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Two bases for the rectangle $[0,24]\times [0,8]$: (a) a dense-sparse basis (Definition\nobreakspace  {}\ref  {def:densesparse}), (b) a short-bars basis (Definition\nobreakspace  {}\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.\relax }}{20}{figure.caption.13}}
\newlabel{fig:quarter}{{8}{20}{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.\relax }{figure.caption.13}{}}
\newlabel{def:shortbars}{{13}{20}{}{theorem.13}{}}
\newlabel{thm:shortbars}{{14}{20}{}{theorem.14}{}}
\newlabel{cor:eff_ds}{{15}{20}{}{theorem.15}{}}
\newlabel{cor:suboptimal}{{16}{20}{}{theorem.16}{}}
\newlabel{def:stacked}{{17}{20}{}{theorem.17}{}}
\newlabel{thm:stacked}{{18}{21}{}{theorem.18}{}}
\citation{rohrbach1937}
\citation{hammerer1976}
\citation{mrose1979}
\citation{kohonen2017}
\citation{leech1956}
\citation{wichmann1963anote}
\citation{hoctor1990}
\citation{linebarger1993difference}
\citation{pal2010nested}
\citation{liu2017}
\citation{haubrich1968array}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces A schematic illustration of the stacked Mrose basis (Definition\nobreakspace  {}\ref  {def:stacked}) with parameters $s_y=2$ and $t=10$. In this case $a=11$ and $s_x=4599$.\relax }}{22}{figure.caption.14}}
\newlabel{fig:thm_1}{{9}{22}{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$.\relax }{figure.caption.14}{}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Conclusion and open questions}{22}{section.7}}
\bibcite{challis1993}{1}
\bibcite{eliahou1998}{2}
\bibcite{eliahou2005}{3}
\bibcite{eliahou2003}{4}
\bibcite{hammerer1976}{5}
\bibcite{han2004}{6}
\bibcite{haubrich1968array}{7}
\bibcite{hoctor1990}{8}
\bibcite{kohonen2015early}{9}
\bibcite{kohonen2014meet}{10}
\@writefile{toc}{\contentsline {section}{\numberline {8}Acknowledgments}{23}{section.8}}
\bibcite{kohonen2017}{11}
\bibcite{kohonen2014}{12}
\bibcite{kozick1991}{13}
\bibcite{leech1956}{14}
\bibcite{linebarger1993difference}{15}
\bibcite{liu2017}{16}
\bibcite{lunnon1969}{17}
\bibcite{mrose1979}{18}
\bibcite{naidu2009}{19}
\bibcite{pal2010nested}{20}
\bibcite{riddell1978}{21}
\bibcite{rohrbach1937}{22}
\bibcite{wichmann1963anote}{23}
\bibcite{yu2009}{24}
\bibcite{yu2015}{25}