Pith. sign in

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 →

arxiv 2509.10580 v1 pith:C6NXLVRY submitted 2025-09-11 math.FA math.PR

classification math.FAmath.PR MSC 46B0960F0505B20
keywords badsciencematricesRademacheraveragesupremumnormLevel-1FourierweightVoronoitessellationHadamardhigh-dimensionalcentrallimittheoremGaussianextremevaluetheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the 'bad science matrix' problem: how large can the expected maximum absolute inner product $\mathbb{E}\max_i |\langle a_i,x\rangle|$ be, over a uniform random sign vector $x\in\{\pm1\}^n$, when the $n$ rows of $A$ have unit Euclidean norm? Its aim is to show that the asymptotic answer is not just $(1+o(1))\sqrt{2\log n}$ but carries a definite second-order term, and that the extremizers are geometrically rigid: their induced Voronoi cells in the hypercube must have near-equal volumes and, except for $o(n)$ exceptions, near-extremal Level-1 Fourier weight. It also claims an explicit deterministic family, obtained by truncating and orthonormalizing Hadamard matrices, attains the same rate for every $n$ if Hadamard's conjecture holds and unconditionally for infinitely many $n$. If correct, the paper identifies the exact asymptotic profile of the worst case and explains why the algebraically structured optimizers seen in small dimensions cannot survive in high dimensions.

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$.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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)
  1. [§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.
  2. [§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. [§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)
  1. [§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.
  2. [§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.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.
  4. [§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.
  5. [§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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

No numerical parameters are fitted; all constants are derived. The central construction depends on an external conjecture, Hadamard's conjecture, for the all-n statement, and on external CLT and extreme-value theorems for the expansion. No new hidden entities are introduced.

assumptions (5)
  • domain assumption Hadamard's conjecture: Hadamard matrices exist for all orders divisible by 4.
    Invoked in Definition 1 and Lemma 3.4 so that for every n the nearest Hadamard order m satisfies m-n < 4, giving flat entries for the orthonormal almost-Hadamard matrix; the unconditional results only use n for which such matrices are known, such as powers of 2.
  • domain assumption Tie-free genericity and continuity extension (Proposition 3.1).
    The proof partitions the hypercube into S_i assuming a unique row attains the max for every x; the paper asserts tied matrices can be handled by perturbation but does not fully prove the structural conclusions transfer.
  • standard math Fang-Koike-Liu-Zhao high-dimensional CLT with the stated non-degeneracy and exponential moment conditions.
    Used to replace Rademacher sup-norm tails by Gaussian tails with error O(n^{-1/2}(log n)^{6.5}); the conditions are checked for the two constructions.
  • standard math Talagrand Level-1 inequality W1[f] <= 2 alpha^2 log(1/alpha).
    Basis of the Fourier upper bound in Lemma 2.1 and the cell-optimality statements.
  • standard math Gaussian correlation inequality and Gaussian extreme-value expansion.
    Give the value E||Z||_inf approximately sqrt(2 log(2n)) - log log(2n)/(2 sqrt(2 log(2n))) for the independent Gaussian comparison.

how reviews work

0 comments
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 reproduced from arXiv: 2509.10580 by the authors.

Figure 1
Figure 1. Left: exact closed form of the 3×3 orthonormal matrix. Right: exact closed form of the 5 × 5 orthonormal matrix. S1 −S1 S2 S2 −S2 −S2 S3 −S3 S1 S1 S1 −S1 S2 −S2 −S2 −S2 S3 −S3 −S3 −S3 S4 S4 S4 −S4 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Left: induced partitions of {±1} 3 for the 3 × 3 ma￾trix used above. Right: induced partitions of {±1} 4 for a 4 × 4 Orthonormal Almost–Hadamard matrix(which is just a Hadamard matrix of order 4). Conjecture 2.1 (Hadamard’s conjecture [5]). For every positive integer n divisible by 4 there a matrix H ∈ {±1} n×n with HHT = nIn. Under the assumption that Hadamard’s famous conjecture holds, which is a nu￾merically vali… view at source ↗
Figure 3
Figure 3. Running exact simulations of the expectation, which is computationally infeasible for n>20, shows a strict gap between the deterministic and random constructions [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Running Monte-Carlo simulations of the expectation, for larger values of n, shows a gap visually matching the asymptotic bound in the proof of Theorem 2.2. 2. The seemingly easier direction is relaxing the heuristic conditions under which the optimality of the first or…
Figure 5
Figure 5. Figure 5: An unsatisfiable tree and the corresponding matrix. It is easy to see then that the root to leaf paths specify the fixed co-ordinates of a n-way subcube partition of the half of the hypercube {−1, 1} n with first coordinate +1, by subcubes of co-dimension ⌊log2 (n)⌋ an…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

  1. [1]

    Bad Science Matrices

    S. Steinerberger, Bad science matrices, arXiv:2402.03205

  2. [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. [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

  4. [4]

    O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014

    R. O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014

  5. [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. [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

  7. [7]

    Optimal numberings and isoperimetric problems on graphs,

    L. H. Harper, “Optimal numberings and isoperimetric problems on graphs,”J. Combin. Theory, 1964

  8. [8]

    F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes, North- Holland, 1977

Show all 22 references
  1. [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

  2. [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

  3. [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

  4. [12]

    Vertex-isoperimetric stability in the hypercube,

    M. Przykucki, “Vertex-isoperimetric stability in the hypercube,”J. Combin. Theory Ser. A, 2020

  5. [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

  6. [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

  7. [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

  8. [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

  9. [17]

    L. D. Pitt, A Gaussian correlation inequality for symmetric convex sets,Ann. Probab., 10(4):629–637, 1982

  10. [18]

    M. R. Leadbetter, G. Lindgren, and H. Rootz´ en.Extremes and Related Properties of Random Sequences and Processes. Springer, 1983

  11. [19]

    P. Hall. On the rate of convergence of normal extremes.J. Appl. Probab., 16(2):433–439, 1979

  12. [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)

  13. [21]

    V. N. Sudakov,Gaussian random processes and measures of solid angles in Hilbert space, Soviet Math. Dokl.12(1971), 412–415

  14. [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

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.