Tusnady's problem: canonical models and monotone-chain certificates

Definitions and mathematical statement

Let $d\ge2$ and let $P\subseteq\mathbb R^d$ be a set of $n$ distinct points. An axis-parallel box is a Cartesian product $B=\prod_{j=1}^d[a_j,b_j]$ with real $a_j\le b_j$. For a signing $\varepsilon:P\to\{-1,1\}$, its imbalance on $B$ is $|\sum_{x\in P\cap B}\varepsilon(x)|$. Define \[ \operatorname{disc}_{\mathrm{box}}(P)= \min_{\varepsilon:P\to\{-1,1\}}\ \sup_{B} \left|\sum_{x\in P\cap B}\varepsilon(x)\right|, \qquad T_d(n)=\max_{\substack{P\subseteq\mathbb R^d\\|P|=n}} \operatorname{disc}_{\mathrm{box}}(P). \] Only finitely many intersections $P\cap B$ occur, so the supremum is an ordinary maximum over a finite set system. Allowing unbounded boxes would not change it, because any relevant intersection can be obtained with finite endpoints. The outer maximum is well defined: the possible discrepancies are integers between zero and $n$.

Tusnády's problem asks for $T_2(n)$, and particularly for its sharp asymptotic growth as $n$ increases. The workshop also asks the same question for every fixed dimension $d\ge2$. In an asymptotic estimate, constants may depend on $d$, but not on $n$ or the configuration $P$. The optimization chooses one coloring that balances all boxes simultaneously, then considers the worst point configuration. This is combinatorial discrepancy on a finite set of points, with no reference measure or equidistribution normalization.

Short English statement

How large must the worst rectangle or box imbalance be when an arbitrary finite point set is optimally colored with two colors?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000918 (AIM-COMBINATORICS-0043), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Hereditary discrepancy and factorization norms, item 1.65. Original workshop question underlying AIM-COMBINATORICS-0043. http://aimpl.org/hereddiscrep/1/.