The Structure of Extremal Bad Science Matrices

We study the 'bad science matrix problem': among all matrices An× n whose rows have unit ₂-norm, determine the maximum of β(A)=1/2ⁿ∑_x∈\±1\ⁿ\|Ax\|_∞. Steinerberger [1] (arXiv:2402.03205) showed that the optimal asymptotic rate is (1+o(1))√2log n, and that this rate is attained with high probability by matrices with i.i.d. ±1 entries after normalization. More recent explicit constructions [2] (arXiv:2408.00933) achieve β(A)≥√log₂(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 $β(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ₙ 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 β(Aₙ)≥(1 - loglog(2n)/4log(2n))√2log(2n).