Session S09 - Number Theory in the Americas

Thursday, July 15, 15:00 ~ 15:30 UTC-3

Zero-sum squares in bounded discrepancy $\mathbf{\{-1,1\}}$-matrices

Amanda Montejano

UNAM, Juriquilla, Mexico   -   amandamontejano@ciencias.unam.mx

A \emph{square} in a matrix ${\mathcal M}=(a_{ij})$ is a $2\times 2$ sub-matrix of ${\mathcal M}$ with entries $a_{i,j}, a_{i+s,j}, a_{i,j+s}, a_{i+s,j+s}$ for some $s\ge 1$. An \emph{Erickson matrix} is a square binary matrix that contains no squares with constant entries. In [4], Erickson asked for the maximum value of $n$ for which there exists an $n\times n$ Erickson matrix. In [2] Axenovich and Manske gave an upper bound of around $2^{2^{40}}$. This gargantuan bound was later improved by Bacher and Eliahou in [3] using computational means to the optimal value of $15$.

In this talk we present the study of a zero-sum analogue of the Erickson matrices problem where we consider binary matrices with entries in $\{-1,1\}$. For this purpose, of course, we need to take into account the discrepancy or deviation of the matrix, defined as the sum of all its entries, that is $${\rm disc}({\mathcal M})=\sum_{\substack{1\le i\le n \\ 1\le j\le m}} a_{i,j}.$$

A \emph{zero-sum square} is a square $S$ with ${\rm disc}(S)=0$. A natural question is, for example, the following: is it true that for sufficiently large $n$ every $n\times n$ $\{-1,1\}$-matrix ${\mathcal M}$ with ${\rm disc}({\mathcal M})=0$ contains a zero-sum square? We answered positive to this question. Since, our proof uses an induction argument, in order for the induction to work we prove the following stronger statement: For $n\ge 5$ and $m\in \{n,n+1\}$, every $n\times m$ $\{-1,1\}$-matrix $M$ with ${\rm abs}{\rm disc}(M)\le n$ contains a zero-sum square except for the split matrix (up to symmetries), where a split matrix is a matrix with all entries above the diagonal equal to $-1$ and all remaining entries equal to $1$.

\medskip

\par\noindent [1] \quad A. R. Ar\'evalo, A. Montejano and E. Rold\'an-Pensado, \emph{Zero-sum squares in bounded discrepancy $\{-1,1\}$-matrices}, arXiv:2005.07813 (2020). \par\noindent [2] M.~Axenovich and J.~Manske, \emph{On monochromatic subsets of a rectangular grid}, Integers \textbf{8} (2008), A21, 14. \par\noindent [3] R.~Bacher and S.~Eliahou, \emph{Extremal binary matrices without constant 2-squares}, J. Comb. \textbf{1} (2010), no.~1, 77--100. \par\noindent [4] M.~J. Erickson, \emph{Introduction to combinatorics}, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley \& Sons, Inc., New York, 1996, A Wiley-Interscience Publication.

Joint work with Alma R. Ar\'evalo (UNAM, Mexico) and Edgardo Rold\'an Pensado (UNAM, Mexico).

View abstract PDF