PreprintCC BY-NC-ND 4.0HAL
Proof of a conjecture of Johnston on binary matrices with low discrepancy
Abstract
A square in a matrix M = (a i, j ) is a 2 × 2 submatrix S with row and column indices {i, i + s} and { j, j + s}, respectively. A square is zero-sum if the sum of its entries equals 0. In 2021, Arévalo, Montejano and Roldán-Pensado proved that all large binary matrices M over {1, -1} of order n with absolute discrepancy | ∑ a i, j | ≤ n contain a zero-sum square, unless they are split. In 2023, Johnston showed that the same conclusion follows from the much weaker hypothesis | ∑ a i, j | ≤ n 2 /4. He further conjectured that the same conclusion would still follow from the weakest possible hypothesis, namely
-2 if n is odd.
We prove this conjecture here. We also address a related problem raised by Johnston in the rectangular case.
Related
- A proof of the interlacing conjecture for the singular values of Sylvester-Kac matrices
- On the lower bound of the refined Bessis--Moussa--Villani conjecture: proof of the cases S_{6,3} and S_{7,3} for 3x3 matrices
- Pal's permanent conjecture: proof for block uniform matrices
- The Komlós conjecture for complex discrepancy
- A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
BibTeX
@misc{eliahou2026proof,
title = {{Proof of a conjecture of Johnston on binary matrices with low discrepancy}},
author = {Shalom Eliahou},
howpublished = {HAL},
year = {2026},
month = sep,
url = {https://hal.science/hal-05753799v1},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Proof of a conjecture of Johnston on binary matrices with low discrepancy
AU - Shalom Eliahou
PY - 2026
DA - 2026/09/17
PB - HAL
UR - https://hal.science/hal-05753799v1
AB - A square in a matrix M = (a i, j ) is a 2 × 2 submatrix S with row and column indices {i, i + s} and { j, j + s}, respectively. A square is zero-sum if the sum of its entries equals 0. In 2021, Arévalo, Montejano and Roldán-Pensado proved that all large binary matrices M over {1, -1} of order n with absolute discrepancy | ∑ a i, j | ≤ n contain a zero-sum square, unless they are split. In 2023, Johnston showed that the same conclusion follows from the much weaker hypothesis | ∑ a i, j | ≤ n 2 /4. He further conjectured that the same conclusion would still follow from the weakest possible hypothesis, namely -2 if n is odd. We prove this conjecture here. We also address a related problem raised by Johnston in the rectangular case.
ER -