Discrepancy of High-Dimensional Permutations

Abstract

Let $L$ be an order-$n$ Latin square. For $X,Y,Z\subseteq \{1,...,n\}$, let $L(X,Y.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 $|L(X,Y,Z)-\frac{1}{n}|X||Y||Z||\le O(\sqrt{|X||Y||Z|})$ for every $X,Y$ and $Z$. Let $\epsilon (L):=\max |X||Y||Z|$ 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 $\epsilon (L)\le O(n^2{\log }^{2}n)$ for almost every order-$n$ Latin square. On the other hand, we recall that $\epsilon (L)\ge \hat{I}\text{c◯}(n^{33/14})$ if $L$ is the multiplication table of an order-$n$ group. Some of these results extend to higher dimensions. Many open problems remain.