The Structure of Extremal Bad Science Matrices

Abstract

We study the 'bad science matrix problem': among all matrices $A\in {\mathbb{R}}^{n\times n}$ whose rows have unit ${\ell }_2$-norm, determine the maximum of ${\hat{I}}^2(A)=\frac{1}{2^n}{\sum }_{x\in \{\pm 1{\}}^n}\Vert Ax{\Vert }_{\infty }$. Steinerberger [1] (arXiv:2402.03205) showed that the optimal asymptotic rate is $(1+o(1))\sqrt{2\log n}$, and that this rate is attained with high probability by matrices with i.i.d. $\pm 1$ entries after normalization. More recent explicit constructions [2] (arXiv:2408.00933) achieve ${\hat{I}}^2(A)\ge \sqrt{{\log }_2(n)+1}$, which lies within a constant factor of the asymptotic optimum. In this paper we bridge the gap between the probabilistic and explicit approaches. We give a geometric description of extremizers as (nearly) isoperimetrically extremal partitions of the $n$-dimensional hypercube induced by the rows of $A$. We obtain precise rates for heuristic constructions by recasting the maximization of ${\hat{I}}^2(A)$ in the language of high-dimensional central-limit theorems as in Fang, Koike, Liu and Zhao [16] (arXiv:2305.17365). Using these connections, we present a family of explicit deterministic matrices $A_n$ that exist for all $n$ under the assumption of Hadamard's conjecture, and for infinitely many $n$ unconditionally, such that for all $n$ sufficiently large ${\hat{I}}^2(A_n)\ge (1-\frac{\log \log (2n)}{4\log (2n)})\sqrt{2\log (2n)}.$

27 pages, 6 figures