Appears in collection : Additive Combinatorics / Combinatoire additive

A square in a matrix $\mathcal M =(a_{ij})$ is a 2X2 sub-matrix of $\mathcal M$ with entries $a_{ij}, a_{i+s,j}, ai,j+s, a_{i+s,j+s}$s for some $s\geq 1$. An Erickson matrix is a square binary matrix that contains no squares with constant entries. In [Eri96], Erickson asked for the maximum value of $n$ for which there exists an n x n Erickson matrix. In [AM08] Axenovich and Manske gave an upper bound of around $2^{2^{40}}$. This gargantuan bound was later improved by Bacher and Eliahou in [BE10] 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 $disc(\mathcal M)= \sum_{1\leq i\leq n \; \; 1\leq j\leq m}a_{i,j}$. A zero-sum square is a square $\mathcal S$ with $disc(\mathcal 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 $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 \geq 5$ and $m \in {n,n+1}$, every $ n \times m {-1, 1}$ -matrix $M$ with $\left | disc(M) \right |\leq n$ contains a zero-sum square except for the triangular matrix (up to symmetries), where a triangular matrix is a matrix with all entries above the diagonal equal to -1 and all remaining entries equal to 1.This is a joint work with Edgardo Roldn-Pensado and Alma R. Arvalo.