Linear discrepancy conjecture for non-diagonal zero-sum-square-free matrices

Let M=(ai,j)M=(a_{i,j}) be an n×nn\times n matrix with entries in {1,1}\{-1,1\}. Define its discrepancy by

disc(M)=1i,jnai,j.\operatorname{disc}(M)=\sum_{1\leq i,j\leq n}a_{i,j}.

A matrix is zero-sum-square-free if it contains no square submatrix whose four entries sum to 00, and it is diagonal if, after vertical and horizontal reflections, it becomes a tt-diagonal matrix for some tt.

Linear discrepancy conjecture. For every C>0C>0, there is an integer NN such that, whenever nNn\geq N, every non-diagonal n×nn\times n matrix MM with entries in {1,1}\{-1,1\} and

disc(M)Cn|\operatorname{disc}(M)|\leq Cn

contains a zero-sum square.

Arévalo, Montejano and Roldán-Pensado proved this with the bound nn (apart from n4n\leq4), and remarked that their proof might yield 2n2n. The conjecture asserts that every fixed linear bound CnCn eventually forces a zero-sum square in a non-diagonal matrix.

Sources & referencesView supporting material

Primary source

Tom Johnston, “Zero-sum squares in \-1, 1\-matrices with low discrepancy”, arXiv:2010.10310 (2023).

Additional references

2 papers in this index state this conjecture (2020). The statement above is taken from the most recent of them; the others are arXiv:2005.07813.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.