High-dimensional permutation discrepancy conjecture

Let dd be a positive integer. A dd-dimensional permutation is an [n]d+1[n]^{d+1} array of zeros and ones with exactly one 11 on every line parallel to any coordinate axis. For a box T=T1××Td+1[n]d+1\mathcal T=T_1\times\cdots\times T_{d+1}\subseteq[n]^{d+1}, define its volume and the number of permutation entries it contains by

vol(T)=iTi,A(T)={αT:A(α)=1}.\operatorname{vol}(\mathcal T)=\prod_i|T_i|,\qquad A(\mathcal T)=|\{\alpha\in\mathcal T:A(\alpha)=1\}|.

High-dimensional permutation discrepancy conjecture. For every d2d\geq2 there exist arbitrarily large dd-dimensional permutations AA such that, for every box T\mathcal T,

A(T)vol(T)n=O(vol(T)).\left|A(\mathcal T)-\frac{\operatorname{vol}(\mathcal T)}{n}\right|=O(\sqrt{\operatorname{vol}(\mathcal T)}).

This is a high-dimensional analogue of the expander mixing lemma and predicts optimal square-root discrepancy for all boxes. The paper gives heuristic motivation but no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Nathan Linial and Zur Luria, “Discrepancy of High-Dimensional Permutations”, arXiv:1512.04123 (2016).

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.