Discrepancy of High-Dimensional Permutations

Let $L$ be an order-$n$ Latin square. For $X,Y,Z\subseteq \{1,\mathrm{.}\mathrm{.}\mathrm{.},n\}$, let $L(X,Y\mathrm{.}Z)$ be the number of triples $i\in X,j\in Y,k\in Z$ such that $L(i,j)=k$. We conjecture that asymptotically almost every Latin square satisfies $\mathrm{\mid }L(X,Y,Z)-\frac{1}{n}\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }\mathrm{\mid }Z\mathrm{\mid }\mathrm{\mid }\le O(\sqrt{\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }\mathrm{\mid }Z\mathrm{\mid }})$ for every $X,Y$ and $Z$. Let $\epsilon (L):=\max \mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }\mathrm{\mid }Z\mathrm{\mid }$ when $L(X,Y,Z)=0$. The above conjecture implies that $\epsilon (L)\le O(n^2)$ holds asymptotically almost surely (this bound is obviously tight). We show that there exist Latin squares with $\epsilon (L)\le O(n^2)$, and that $\varepsilon(L) \le O(n^2 \log^2 n)$foralmosteveryorder-$n$ Latin square. On the other hand, we recall that $\epsilon (L)\ge \mathrm{\Omega }(n^{33\mathrm{/}14})$ if $L$ is the multiplication table of an order-$n$ group. Some of these results extend to higher dimensions. Many open problems remain.