A high-probability lower bound for random permutation discrepancy

Definitions and mathematical statement

Write $[n]=\{1,\ldots,n\}$. A permutation $\pi$ of $[n]$ gives the interval sets $\{\pi(a),\pi(a+1),\ldots,\pi(b)\}$ for $1\le a\le b\le n$. Given $k$ permutations $\pi=(\pi_1,\ldots,\pi_k)$, take the union of these $k$ interval systems and define \[ D(\pi)=\min_{\varepsilon:[n]\to\{-1,1\}} \max_{\substack{1\le i\le k\\1\le a\le b\le n}} \left|\sum_{j=a}^b\varepsilon(\pi_i(j))\right|. \] There is one sign for each ground-set element, used consistently in all permutations. Repeated permutations and repeated interval sets cause no change to the definition.

The first question is to determine the worst-case discrepancy $D(n,k)=\max_{\pi}D(\pi)$, with sharp dependence on both the ground-set size $n$ and the number $k$ of permutations. The second asks for the typical value of $D(\pi)$ when $\pi_1,\ldots,\pi_k$ are independent uniform random permutations, including asymptotic bounds holding with probability tending to one as $n\to\infty$ for the specified regime of $k=k(n)$. These are distinct extremal and probabilistic questions; a bad fixed family need not describe a random family. Intervals are the convention here. If one instead uses only prefixes, its discrepancy lies between one half and one times the interval discrepancy, so the asymptotic order questions are unchanged.

Short English statement

Determine the worst-case and typical discrepancy of the interval systems generated by several permutations.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000914 (AIM-COMBINATORICS-0039), 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.3. Original workshop question underlying AIM-COMBINATORICS-0039. http://aimpl.org/hereddiscrep/1/.