Zero-sum squares in $\{-1, 1\}$-matrices with low discrepancy.

2020 
Given a matrix $M = \left(a_{i,j}\right)$ a square is a $2 \times 2$ submatrix with entries $a_{i,j}$, $a_{i, j+s}$, $a_{i+s, j}$, $a_{i+s, j +s}$ for some $s \geq 0$, and a zero-sum square is a square where the entries sum to $0$. Recently, Ar\'evalo, Montejano and Rold\'an-Pensado proved that all large $n \times n$ $\{-1,1\}$-matrices $M$ with $|\operatorname{disc}(M)| = |\sum a_{i,j}| \leq n$ contain a zero-sum square unless they are diagonal. We improve this bound by showing that all large $n \times n$ $\{-1,1\}$-matrices $M$ with $|\operatorname{disc}(M)| \leq n^2/4$ are either diagonal or contain a zero-sum square.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    10
    References
    0
    Citations
    NaN
    KQI
    []