Linial–Luria discrepancy conjecture for Latin squares

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

volT=IXQ.\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,

\originalleftNT(L)volTn\aftergroup\originalright=O\originalleft(volT\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.

Sources & referencesView supporting material

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.