REVIEW 3 major objections 5 minor 22 references
The Structure of Extremal Bad Science Matrices
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper establishes a sharp two-term asymptotic formula for the worst-case 'bad science matrix' value, and shows the extremizers are rigid Voronoi partitions of the hypercube.
desk verdict A genuine advance on the bad science matrix problem, with one repairable but real bug in the deterministic half of the main theorem. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the family of positive Voronoi cells $S_i=\{x\in\{\pm1\}^n:|\langle a_i,x\rangle|=\max_j|\langle a_j,x\rangle|,\ \langle a_i,x\rangle\ge0\}$. The key identity is the Fourier bound $\beta(A)\le 2\sum_{i=1}^n\sqrt{W_1[\mathbf{1}_{S_i}]}$, where $W_1[f]=\sum_{k=1}^n(\mathbb{E}[f(x)x_k])^2$ is the Level-1 Fourier weight. This converts the matrix problem into a problem about how $2n$ disjoint cells can split the hypercube while keeping each cell's Level-1 Fourier weight large; tightness forces near-equal volumes and near-isoperimetric cells. To compute the rate, the same rows are fed through a high-dimensional central limit theorem, replacing the Rademacher maximum by the maximum of a Gaussian with the same covariance; the Gaussian correlation inequality then shows the identity covariance gives the largest expected Gaussian maximum, and classical extreme-value asymptotics supply the second-order term.
What would settle it
Take the normalized random sign matrix $S$ for increasing $n$ (it satisfies the bounded-entry and non-degeneracy hypotheses) and compute or accurately simulate $\beta(S)$ for large $n$. If the difference $\beta(S)-(\sqrt{2\log(2n)}-\frac{\log\log(2n)}{2\sqrt{2\log(2n)}})$ does not stay within $O(1/\sqrt{\log n})$, Theorem 2.2's error rate is wrong; if some such matrix family exceeds the two-term upper bound by a fixed fraction of the $\log\log(2n)$ term, the asserted optimality of the second-order correction fails. This can be checked by direct enumeration up to $n\approx20$ and by Monte Carlo for larger $n$.
Extended reading notes
Core claim
The central discovery is a two-term expansion for the maximal value of $\beta(A)$: for a normalized random sign matrix (with high probability) and for any orthonormal almost-Hadamard matrix $Q$ (assuming Hadamard's conjecture), $\beta(\cdot)=\sqrt{2\log(2n)}-\frac{\log\log(2n)}{2\sqrt{2\log(2n)}}+O(1/\sqrt{\log n})$. The proof shows further that, under mild boundedness and non-degeneracy assumptions on the entries and the covariance, this expansion is universal for every near-optimal sequence, so no such matrix can improve the first two terms. Structurally, any sequence attaining the optimum induces a Voronoi partition $\{S_i,-S_i\}$ of the hypercube whose cell volumes converge in $\ell^2$ to $1/(2n)$, whose rows coincide with normalized cell centroids up to vanishing error, and whose cells are, for all but $o(n)$ indices, asymptotically optimal for Level-1 Fourier weight. The extremal problem is thereby reduced to an isoperimetric tiling problem on the Boolean cube.
Load-bearing premise
The deterministic all-$n$ construction loads on Hadamard's conjecture: the proof needs the nearest Hadamard order $m$ to have $m-n\le3$, and without that bound the flatness of the entries and the CLT error control for the QR-normalized truncation are not established.
Editorial extensions
If this is right
- Asymptotically, the worst-case value is strictly smaller than $\sqrt{2\log(2n)}$ by a $\frac{\log\log(2n)}{2\sqrt{2\log(2n)}}$ correction, so the rate of convergence to the leading order is now known.
- Randomness is not essential for optimality: whenever enough Hadamard matrices are available, the explicit orthonormal almost-Hadamard construction attains the same expansion, and it does so for every $n$ if Hadamard's conjecture is true.
- Any sequence that is asymptotically optimal must induce a constrained centroidal Voronoi tessellation of the hypercube with cell volumes close to $1/(2n)$; finding the exact optimum is therefore equivalent to an isoperimetric tiling problem on the cube.
- The balanced binary-tree constructions of earlier work are suboptimal because subcubes carry only about $\sqrt{\log_2 n+1}/n$ Level-1 weight, far below the isoperimetrically optimal logarithmic profile.
- Under the stated boundedness and non-degeneracy hypotheses, no sequence of matrices can improve the first two terms of the expansion, so the computed formula describes the true maximum up to $O(1/\sqrt{\log n})$.
Reading between the lines
- One natural extension, not proved in the paper, is a converse: any partition of the hypercube into $2n$ near-equal, near-Level-1-extremal cells should yield a near-optimal bad science matrix by taking each row to be the normalized centroid of its cell.
- Because the second-order term comes entirely from Gaussian extreme-value theory, the same expansion is likely to hold for other symmetric input distributions such as Gaussian or spherical vectors; this is a testable extension.
- The numerical gap between Hadamard-based and random-sign matrices is predicted by the covariance-deficit bound to be at most about $(\log n)^{3/4}/\sqrt{n}$; a matching lower bound, which the author notes is not known, would prove the deterministic construction is strictly better as $n$ grows.
- If Hadamard's conjecture turned out to fail infinitely often with growing gaps to the nearest Hadamard order, the deterministic construction would still work for the infinitely many $n$ near Hadamard orders, but the all-$n$ claim would need a different source of flat orthonormal matrices.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the max over unit-row matrices A of β(A) = E_x ||Ax||_∞ on Rademacher inputs. It claims a Fourier-analytic upper bound (Lemma 2.1), a structural rigidity theorem for extremizers (Theorem 2.1: near-equal Voronoi cells, near-extremal Level-1 Fourier weight), and a sharp two-term asymptotic expansion for two constructions: normalized random sign matrices and deterministic orthonormal almost-Hadamard matrices built from Hadamard blocks (Theorem 2.2). The proof strategy is to transfer the β-computation to a Gaussian maximum via a high-dimensional CLT, bound the loss by Gaussian correlation/Chatterjee-type inequalities, and then use classical extreme-value asymptotics. A final section interprets earlier subcube constructions and explains why they are suboptimal.
Significance. If the proof issues are repaired, the paper would be a genuine advance: it determines the second-order term for the worst-case average sup-norm of unit-row matrices, gives explicit deterministic constructions matching the random construction at this precision under Hadamard's conjecture, and ties extremality to isoperimetric tilings of the hypercube. The main chain of ideas is sound, and the paper usefully connects the problem to high-dimensional CLT results and Gaussian correlation inequalities. The code and numerical experiments are a positive feature. The issues found below are normalization and presentation errors rather than flaws in the overall conceptual framework.
major comments (3)
- [§3.1, proof of Theorem 2.1] The deterministic half of Theorem 2.2 is not proved as written. The proof fixes a "constant M = max_{i,j} Q_{ij}" after quoting Lemma 3.4, but Lemma 3.4 only gives |Q_{ij}| = O(n^{-1/2}), so M is not a constant and tends to 0. The subsequent choice q = sqrt(2M log n) therefore tends to 0, not to infinity. In the decomposition (15)-(16), the Gaussian tail integral ∫_q^∞ P(||Z||_∞ > t)dt is then comparable to the quantity being computed, so the claimed error E||S_n||_∞ = E||Z||_∞ + O(n^{-1/2}(log n)^7) does not follow. The argument is repairable: since each row of Q has unit ℓ_2-norm, Hoeffding gives P(|(S_n)_j| > t) ≤ 2 exp(-t^2/2), and choosing a fixed q = sqrt(8 log n) makes both the Gaussian tail and the matrix tail O(n^{-c}), so all displayed bounds go through. This should be stated explicitly in the revision.
- [§4, Lemma 4.1] The proof of Theorem 2.1 defines α_i = |S_i|/2^{n-1}, but the Level-1 inequality in Lemma 3.1 applies to f = 1_{S_i} on the full cube, whose mean is |S_i|/2^n. With the displayed definition, the α_i average 1/n, and Jensen's inequality would give F(α) ≤ n f(1/n), not the stated n f(1/(2n)). The subsequent volume bound with target 1/(2n) only works after replacing 2^{n-1} by 2^n throughout the proof. The theorem statement already uses the correct normalization, so this is a fixable proof error, but as written the derivation is internally inconsistent.
- [§3.1, Proposition 3.1] Lemma 4.1 states that for a subcube T_i of codimension ⌊log_2 n⌋ + 1, one has sqrt(W_1[1_{T_i}]) = sqrt(⌊log_2 n⌋ + 1)/n. This is off by a factor of 2. For a subcube of codimension k, the singleton Fourier coefficients have magnitude |T_i|/2^n = 2^{-k}, so sqrt(W_1[1_{T_i}]) = sqrt(k)/2^k. With k = ⌊log_2 n⌋ + 1 and n a power of 2, this equals sqrt(k)/(2n), not sqrt(k)/n. The paragraph's conclusion that the subcube decomposition yields β(A) = sqrt(log_2 n + 1) is consistent with the corrected formula, so the interpretive message survives, but the lemma as stated is false.
minor comments (5)
- [§3.1, Proposition 3.1] The reduction to tie-free matrices is described as "without loss of generality," but the proof only shows that optimizers can be approximated by tie-free matrices. Please clarify how the structural conclusions of Theorem 2.1 are transferred from the approximating tie-free sequence to an arbitrary optimizer that may have ties; if the theorem is intended only for generic tie-free maximizers, the statement should say so.
- [§3.3, case 1] In the tail computation for the random sign matrix, the displayed expression "S_{n,i} = 1/sqrt(n) Σ_j ξ_{ij}" omits the Rademacher vector ε_j; the correct coordinate involves the sum Σ_j ξ_{ij} ε_j. The Hoeffding bound used is correct, but the missing ε_j makes the notation confusing.
- [§3.3, case 2] The covariance computation for the almost-Hadamard matrix is inconsistent with the earlier normalization. The paper first fixes A with rows of norm √n so that Σ = (1/n)AA^T has unit diagonal, then writes Σ = (1/n)QQ^T = (1/n)I_n for an orthogonal Q. Either set A = √n Q, giving Σ = I_n, or keep A = Q and rescale the CLT normalization. As written, the two normalizations are mixed.
- [§3.3, case 2] The notation "M = max_{i,j} Q_{ij}" should use |Q_{ij}|, and the phrase "fix a constant M" is misleading given Lemma 3.4; the revision should either define M on the rescaled matrix A = √n Q or avoid M entirely and use the row-normalization property.
- [§3.3, proof of Theorem 2.2] In the deterministic case, the proof ends by saying the result holds "if we are a constant independent of n away from the closest Hadamard matrix of order ≥ n." This condition is not stated in Theorem 2.2 and is not equivalent to the Hadamard-conjecture assumption; please reconcile the theorem statement with this remark.
Circularity Check
No significant circularity: the paper's derivations rely on external CLT and classical inequalities, not on its own conclusions.
full rationale
I walked the derivation chain. Lemma 2.1 gives a Fourier upper bound for beta(A) in terms of Level-1 weights of the induced cells; Theorem 2.1 combines that bound with the lower bound obtained from the explicit constructions in Theorem 2.2. Theorem 2.2 is proved independently from the Fang-Koike-Liu-Zhao high-dimensional CLT, the Gaussian correlation inequality, and classical extreme-value asymptotics, none of which are supplied by the present paper or assumed to contain the target result. The orthonormal almost-Hadamard construction is analyzed through an external CLT, and the flatness bound in Lemma 3.4 is proved by direct QR/Cholesky estimates rather than by postulating the final expansion. Lemma 3.5 states a conditional universal expansion under boundedness and non-degeneracy hypotheses, and it is checked against the explicit constructions, not derived from the extremal characterization. There are no fitted parameters renamed as predictions, no self-citation chain carrying the argument, and no equation whose input is equivalent to its output by definition. The skeptical concern about setting M = max_{i,j} Q_{ij} as a constant when Lemma 3.4 only gives |Q_{ij}| = O(n^{-1/2}) is a genuine technical issue in the tail-bound estimate for the deterministic construction, and it affects correctness of the proof as written; however, it is not circular reasoning, because it does not reintroduce the claimed beta expansion or the matrix's optimum as an assumption.
Assumptions & free parameters
assumptions (5)
- domain assumption Hadamard's conjecture: Hadamard matrices exist for all orders divisible by 4.
- domain assumption Tie-free genericity and continuity extension (Proposition 3.1).
- standard math Fang-Koike-Liu-Zhao high-dimensional CLT with the stated non-degeneracy and exponential moment conditions.
- standard math Talagrand Level-1 inequality W1[f] <= 2 alpha^2 log(1/alpha).
- standard math Gaussian correlation inequality and Gaussian extreme-value expansion.
Cite this review
Pith. "Pith review of The Structure of Extremal Bad Science Matrices." pith.science (2026). https://pith.science/paper/C6NXLVRY
@misc{pith2026250910580,
author = {Pith},
title = {Pith review of: The Structure of Extremal Bad Science Matrices},
year = {2026},
howpublished = {\url{https://pith.science/paper/C6NXLVRY}},
note = {Machine review of arXiv:2509.10580}
}
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 $\beta(A)=\frac{1}{2^n}\sum_{x\in\{\pm1\}^n}\|Ax\|_\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. $\pm1$ entries after normalization. More recent explicit constructions [2] (arXiv:2408.00933) achieve $\beta(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 $\beta(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 $\beta(A_n)\ge\bigl(1 - \frac{\log\log(2n)}{4\log(2n)}\bigr)\sqrt{2\log(2n)}.$
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
S. Steinerberger, Bad science matrices, arXiv:2402.03205
-
[2]
Alex Albors, Hisham Bhatti, Lukshya Ganjoo, Raymond Guo, Dmitriy Kunisky, Ro- han Mukherjee, Alicia Stepin, Tony Zeng, On the Structure of Bad Science matrices, arXiv:2408.00933
-
[3]
How much are increasing sets positively correlated?Combinatorica, 16(2):243–258, 1996
Michel Talagrand. How much are increasing sets positively correlated?Combinatorica, 16(2):243–258, 1996. 27
work page 1996
-
[4]
O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014
R. O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014
2014
-
[5]
Hadamard,R´ esolution d’une question relative aux d´ eterminants, Bull
J. Hadamard,R´ esolution d’une question relative aux d´ eterminants, Bull. Sci. Math. (2)17, 240–246 (1893)
-
[6]
A Hadamard matrix of order 428,
H. Kharaghani and B. Tayfeh-Rezaie, “A Hadamard matrix of order 428,”Journal of Com- binatorial Designs, vol. 13, no. 6, pp. 435–440, 2005
work page 2005
-
[7]
Optimal numberings and isoperimetric problems on graphs,
L. H. Harper, “Optimal numberings and isoperimetric problems on graphs,”J. Combin. Theory, 1964
work page 1964
-
[8]
F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes, North- Holland, 1977
work page 1977
Show all 22 references
-
[9]
A partition of the hypercube into maximally nonparallel 1-perfect codes,
D. Krotov, “A partition of the hypercube into maximally nonparallel 1-perfect codes,”arXiv preprint arXiv:1210.0010, 2012
2012 arXiv
-
[10]
Perfect 2-colorings of Hamming graphs,
E. A. Bespalov, D. S. Krotov, A. A. Matiushev, A. A. Taranenko, and K. V. Vorob’ev, “Perfect 2-colorings of Hamming graphs,”arXiv preprint arXiv:1911.13151, 2019
1911 arXiv
-
[11]
A stability result for the cube edge isoperimetric inequality,
P. Keevash and E. Long, “A stability result for the cube edge isoperimetric inequality,” 2017. Available online
2017
-
[12]
Vertex-isoperimetric stability in the hypercube,
M. Przykucki, “Vertex-isoperimetric stability in the hypercube,”J. Combin. Theory Ser. A, 2020
2020
-
[13]
NP-hardness of Euclidean sum-of-squares clustering,
D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,”Machine Learning, vol. 75, no. 2, pp. 245–248, 2009
2009
-
[14]
Centroidal Voronoi tessellations: applications and algorithms,
Q. Du, V. Faber, and M. Gunzburger, “Centroidal Voronoi tessellations: applications and algorithms,”SIAM Review, vol. 41, no. 4, pp. 637–676, 1999
1999
-
[15]
Constrained Centroidal Voronoi Tessella- tions for Surfaces,
Q. Du, M. D. Gunzburger, and L. Ju, “Constrained Centroidal Voronoi Tessella- tions for Surfaces,”SIAM J. Sci. Comput., vol. 24, no. 5, pp. 1488–1506, 2003. doi:10.1137/S1064827501391576
2003 doi
-
[16]
High-dimensional central limit theorems by Stein’s method in the degenerate case.arXiv preprint arXiv:2305.17365, May 2023
Xiao Fang, Yuta Koike, Song-Hao Liu, and Yi-Kun Zhao. High-dimensional central limit theorems by Stein’s method in the degenerate case.arXiv preprint arXiv:2305.17365, May 2023
2023 arXiv
-
[17]
L. D. Pitt, A Gaussian correlation inequality for symmetric convex sets,Ann. Probab., 10(4):629–637, 1982
1982
-
[18]
M. R. Leadbetter, G. Lindgren, and H. Rootz´ en.Extremes and Related Properties of Random Sequences and Processes. Springer, 1983
1983
-
[19]
P. Hall. On the rate of convergence of normal extremes.J. Appl. Probab., 16(2):433–439, 1979
1979
-
[20]
Chatterjee,An error bound in the Sudakov–Fernique inequality, arXiv:math/0510424 (2005)
S. Chatterjee,An error bound in the Sudakov–Fernique inequality, arXiv:math/0510424 (2005)
2005 arXiv
-
[21]
V. N. Sudakov,Gaussian random processes and measures of solid angles in Hilbert space, Soviet Math. Dokl.12(1971), 412–415
1971
-
[22]
Fernique,R´ egularit´ e des trajectoires des fonctions al´ eatoires gaussiennes, Lecture Notes in Mathematics, vol
X. Fernique,R´ egularit´ e des trajectoires des fonctions al´ eatoires gaussiennes, Lecture Notes in Mathematics, vol. 480, Springer, 1975, pp. 1–96. Email address:ssinha19@uw.edu University of W ashington, Seattle, W A 98195, USA
1975
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.