Linial–Luria discrepancy conjecture for Latin squares

About 10 years old · traced to

Let LL be an n×nn\times n Latin square, viewed as the n×n×nn\times n\times n zero-one array A(L)A(L) with Ai,x,q=1A_{i,x,q}=1 if and only if Li,x=qL_{i,x}=q. A box is a set T=I×X×QT=I\times X\times Q with I,X,Q⊆{1,…,n}I,X,Q\subseteq\{1,\ldots,n\}, and its volume is

vol⁡T=∣I∣∣X∣∣Q∣.\operatorname{vol} T=|I||X||Q|.

Let NT(L)N_T(L) be the number of ones of A(L)A(L) in TT.

Linial–Luria's conjecture. There exist arbitrarily large Latin squares LL such that, for every box T=I×X×QT=I\times X\times Q,

\originalleft∣NT(L)−vol⁡Tn\aftergroup\originalright∣=O\originalleft(vol⁡T\aftergroup\originalright).\mathopen{}\mathclose\bgroup\originalleft|N_T(L)-\frac{\operatorname{vol} T}{n}\aftergroup\egroup\originalright|=O\mathopen{}\mathclose\bgroup\originalleft(\sqrt{\operatorname{vol} T}\aftergroup\egroup\originalright).

This asks for Latin squares whose associated zero-one arrays have uniformly low discrepancy in every box, with the expected density 1/n1/n. The source presents it as a conjecture related to the quasirandomness of Latin squares; the paper proves that random Latin squares typically have relatively low discrepancy, but does not establish the asserted existence result.

References

Primary source

Matthew Kwan and Benny Sudakov, “Intercalates and Discrepancy in Random Latin Squares”, arXiv:1607.04981 (2017).

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.