Square-Root Box Discrepancy for Multidimensional Permutations

Definitions and mathematical statement

Let $d\geq 2$ and $n\geq 1$ be integers, and write $[n]=\{1,\ldots,n\}$. Under the standard array convention, a $d$-dimensional permutation of order $n$ is a function \[ A:[n]^{d+1}\longrightarrow\{0,1\} \] such that every coordinate line contains exactly one entry equal to $1$: for every $j\in\{1,\ldots,d+1\}$ and every fixed choice of the other coordinates, \[ \sum_{t=1}^{n}A(x_1,\ldots,x_{j-1},t,x_{j+1},\ldots,x_{d+1})=1. \] For $T\subseteq[n]^{d+1}$, put \[ A(T)=\sum_{x\in T}A(x),\qquad \operatorname{vol}(T)=|T|. \] For a Cartesian product $T=T_1\times\cdots\times T_{d+1}$, this gives $\operatorname{vol}(T)=\prod_{i=1}^{d+1}|T_i|$. These definitions make explicit standard conventions that the supplied record does not itself define.

Let $\mathcal B_{d,n}$ denote the intended family of boxes. The requested assertion, with the big-$O$ bound interpreted uniformly in the order and the box, is \[ \begin{gathered} \forall d\in{\mathbb{Z}},\ d\geq2,\quad \exists C_d>0\quad \forall N\in{\mathbb{Z}},\ N\geq1,\quad \exists n\in{\mathbb{Z}},\ n\geq N,\quad \exists A\text{ a }d\text{-dimensional permutation of order }n,\\ \forall T\in\mathcal B_{d,n},\qquad \left|A(T)-\frac{\operatorname{vol}(T)}{n}\right| \leq C_d\sqrt{\operatorname{vol}(T)}. \end{gathered} \] Thus the question asks for unboundedly many admissible orders, with a constant allowed to depend on $d$ but independent of $n$, $A$, and $T$. Empty boxes, if included, satisfy the inequality with both sides zero.

Unresolved qualification. The supplied record does not specify whether boxes are all products of arbitrary coordinate subsets, \[ \mathcal B_{d,n}^{\mathrm{cart}}= \{T_1\times\cdots\times T_{d+1}:T_i\subseteq[n]\}, \] or only products of consecutive integer intervals. The assertion above therefore retains $\mathcal B_{d,n}$ as an unresolved parameter; these two readings are not identified. The array convention and uniform interpretation of the big-$O$ constant also require confirmation against the cited source.

Short English statement

For each integer $d\geq2$, the question asks whether permutations of unbounded order can have box counts within $C_d\sqrt{\operatorname{vol}(T)}$ of $\operatorname{vol}(T)/n$, simultaneously for every box. The meaning of box is unspecified in the supplied record. The registry labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, supplied complete record for permanent ID $30003127$, titled "Square-Root Box Discrepancy for Multidimensional Permutations," in the Oberwolfach Reports Open Problems collection; exact source code catalogue entry. No individual proposer is identified. The proposed year is recorded as 2016.
• Supplied source citation: Combinatorics and Probability (2017), Oberwolfach Reports, DOI 10.4171/owr/2016/22, pp. 1189--1257. https://doi.org/10.4171/owr/2016/22. The background describes Oberwolfach Reports as documenting workshops and their open-problem discussions. The citation year 2017 is retained as supplied, alongside the DOI containing 2016 and the recorded proposed year 2016.
• Supplied literature reference: Linial and Luria, Discrepancy of High-Dimensional Permutations. https://arxiv.org/abs/1512.04123.
• Supplied literature reference: Linial and Luria, "Published Version." https://doi.org/10.19086/da.845.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that the high-dimensional box discrepancy conjecture remains unresolved, that later work proves only special dimensions or weaker bounds, and that the conjectural square-root discrepancy is not established. This is supplied dated curation derived from the OWR record, not an independently verified assessment; its time-sensitive status and cited claims require independent verification.
• The registry assigns the statement status corrected_verified and reports a manual semantic, typographic, and LaTeX review asserting that the clean statement is self-contained and preserves the target without unsupported additions. This is supplied review metadata, not verification performed for this draft.