{"id":"fd1d94b9-a586-4352-9db0-e3a04744b5da","arxiv_id":"2509.10580","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For unit-row matrices, the maximal average sup-norm over Rademacher vectors is sqrt(2 log(2n)) - log log(2n)/(2 sqrt(2 log(2n))) + o(1/sqrt(log n)) for explicit Hadamard-based matrices and random sign matrices, with extremizers shown to induce nearly equal-volume, isoperimetrically optimal Voronoi…","lead":"This paper studies how much a matrix can amplify random sign vectors: it characterizes the optimal matrices geometrically and gives explicit matrices that reach the best possible growth rate, up to a doubly logarithmic correction. The result sharpens earlier probabilistic bounds and provides a deterministic construction that works for every dimension if a classical conjecture about Hadamard matrices is true.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Deterministic half of Theorem 2.2 fails as written: the proof treats the entry bound M of Q as a constant, but Lemma 3.4 only gives |Q_ij|=O(n^{-1/2}), so q=sqrt(2M log n) tends to 0 and the Gaussian tail integral is not negligible.","rationale":"The reader's verdict is conditional and I agree with that. The most load-bearing defect is in the proof of the explicit Hadamard construction, not in the conceptual framework: the proof contains a concrete normalization slip that, read literally, destroys the tail-integral argument. Other weak points (Hadamard conjecture, CLT non-degeneracy, tie-free genericity) are explicitly acknowledged or are standard assumptions; the M slip is an internal inconsistency in a central proof. A fixed constant M repairs the proof; hence no change to the conditional verdict. Agreement partial because the reader flagged a different normalization issue (Lemma 4.1) and the CLT conditions, but not this one.","tokens_in":19058,"tokens_out":34626,"duration_ms":227526,"concrete_test":"Recompute the deterministic case of Theorem 2.2 with a fixed constant bound: keep Lemma 3.4 as |Q_{ij}| ≤ C n^{-1/2}, define A=sqrt(n)Q, and use Hoeffding with the exact variance sum_i Q_{ji}^2 = 1 to get P(|(S_n)_j|>t) ≤ 2 exp(-t^2/2). Set q = sqrt(8 log n) in (15) and evaluate the three terms: qδ = O(n^{-1/2}(log n)^7), Gaussian tail ≤ C n^{-1}(log n)^{-1/2}, and matrix tail ≤ C n^{-3}(log n)^{-1/2}. If these combine to o((log n)^{-1/2}), the expansion (18) for Q follows; if any tail term is instead of order (log n)^{1/2}, the current proof's transfer step fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 2.2, case 2 (orthonormal almost-Hadamard matrix), the proof invokes Lemma 3.4 to get |Q_{ji}|=O(n^{-1/2}) and then 'fixes a constant M = max_{i,j} Q_{ij}'. This M is not a constant; it is O(n^{-1/2}) and tends to 0. The subsequent choice q = sqrt(2M log n) therefore tends to 0, not to infinity. In the integral decomposition (15)/(16) used to transfer the CLT rectangle error to expectations, the Gaussian tail term -∫_q^∞ P(||Z||_∞ > t)dt is then of order sqrt(2 log n), i.e. the same size as the quantity being computed, so the claimed E||S_n||_∞ = E||Z||_∞ + O(n^{-1/2}(log n)^7) does not follow. Thus the deterministic construction's expansion (18) is not proved as written. This is a normalization error, not a conceptual one: since ||row of Q||_2=1, Hoeffding gives P(|(S_n)_j|>t) ≤ 2 exp(-t^2/2), so choosing a fixed q=sqrt(8 log n) makes both tails O(n^{-c}) and the proof goes through.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19365,"tokens_out":19625,"duration_ms":140711,"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":[{"comment":"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.","section":"§3.1, proof of Theorem 2.1"},{"comment":"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.","section":"§4, Lemma 4.1"},{"comment":"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.","section":"§3.1, Proposition 3.1"}],"minor_comments":[{"comment":"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.","section":"§3.1, Proposition 3.1"},{"comment":"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.","section":"§3.3, case 1"},{"comment":"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.","section":"§3.3, case 2"},{"comment":"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.","section":"§3.3, case 2"},{"comment":"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.","section":"§3.3, proof of Theorem 2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a promising contribution that fits the journal's scope. The main theorem's deterministic half has a genuine normalization gap, but it is local and repairable by the argument indicated in my major comment. The proof of Theorem 2.1 also contains a normalization typo, and Lemma 4.1 is false as stated. I do not see a circularity problem or an unacknowledged reliance on fitted parameters. Given the paper's useful ideas and the fact that the central claims are plausibly correct after straightforward fixes, I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nHere is my read of arXiv:2509.10580. The paper deserves attention: it gives a Fourier characterization of asymptotically extremal bad science matrices and proves a second-order expansion for normalized random sign matrices and for an explicit Hadamard-based family. The random sign half of Theorem 2.2 is genuinely new and, as far as I can tell, correct. The covariance bound, the CLT transfer, and the tail-integral argument line up. The structural Theorem 2.1 is also solid: the Level-1 inequality plus Jensen gives the volume equidistribution and near-isoperimetric statements, and the proof is coherent.\n\nThe soft spot is the deterministic half of Theorem 2.2, and the stress-test note is right. In the almost-Hadamard case the proof fixes an entry bound M = max |Q_ij| right after establishing |Q_ij| = O(n^{-1/2}). So M is not a constant; it goes to zero. Then q = sqrt(2M log n) tends to zero, and the Gaussian tail integral the proof discards is of order sqrt(2 log n) — the same size as the term being computed. The claimed bound E||S_n||infinity = E||Z||infinity + O(n^{-1/2}(log n)^7) does not follow as written. The same issue infects Lemma 3.5.\n\nThe saving grace is that the fix is local and easy. The rows of Q have unit norm, so the correct Hoeffding bound is P(|(S_n)_j| > t) <= 2 exp(-t^2/2). Choosing a fixed q = sqrt(8 log n) makes both the Gaussian and matrix tail integrals O(n^{-3}(log n)^{-1/2}), well inside the claimed error. This is a normalization error, not a flawed strategy.\n\nSmaller items: Lemma 4.1's formula only holds for n a power of two; for general n the denominator should be 2^k. The qualitative centroid-alignment claim in Theorem 2.1 is stated but not actually proved; the author should prove it or soften it. Section 4 references 'the explicit matrices in [1]' where it means [2]. The tie-handling in Proposition 3.1 is hand-wavy but does not affect the main bounds.\n\nBottom line: this deserves a serious referee. The main ideas are sound, the random-sign result and the structural theorem are new and correct, and the gap in the deterministic case is repairable. I would send it to review with a request that the proof of the almost-Hadamard case be rewritten with a fixed q and the correct Hoeffding bound before acceptance.","headline":"A genuine advance on the bad science matrix problem, with one repairable but real bug in the deterministic half of the main theorem.","tokens_in":19849,"tokens_out":8293,"would_cite":true,"duration_ms":236368,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["46B09","60F05","05B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["bad science matrices","Rademacher average","supremum norm","Level-1 Fourier weight","Voronoi tessellation","Hadamard matrices","high-dimensional central limit theorem","Gaussian extreme value theory"],"falsifier":"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$.","tokens_in":18863,"feed_emoji":"🎲","tokens_out":14395,"duration_ms":109234,"temperature":0.7,"pith_summary":"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.","feed_headline":"Bad-science matrices get a sharp two-term formula","feed_subtitle":"A Fourier-partition argument plus high-dimensional CLT fixes the correction term and gives explicit near-optimal matrices.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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})$."],"supporting_citations":[{"why":"Sets up the bad science matrix problem and proves the leading-order rate $(1+o(1))\\sqrt{2\\log n}$, along with the random-sign matrix heuristic.","marker":"[1]"},{"why":"Supplies the high-dimensional central limit theorem with explicit error bound used to replace the Rademacher maximum by a Gaussian maximum.","marker":"[16]"},{"why":"Hadamard's conjecture is assumed in Lemma 3.4 to force the nearest Hadamard order to satisfy $m-n\\le3$, giving flat entries for the QR-normalized truncation.","marker":"[5]"},{"why":"Talagrand's Level-1 inequality bounds the Fourier weight of each cell and yields the universal upper bound used in Theorem 2.1.","marker":"[3]"},{"why":"The Gaussian correlation inequality pins down the identity covariance as the maximizer of the expected Gaussian supremum.","marker":"[17]"},{"why":"Provides the quantitative Sudakov-Fernique type bound that controls the loss caused by non-identity covariance.","marker":"[20]"},{"why":"Gives the asymptotic expansion for the expected absolute maximum of standard Gaussians, producing the second-order term.","marker":"[19]"},{"why":"Earlier explicit constructions and small-dimension solutions; its tree/subcube matrices are compared and diagnosed in Section 4.","marker":"[2]"}],"fun_headline_variants":["Bad-science matrices get exact second-order term","Explicit near-optimal bad-science matrices found","Universal two-term limit for bad-science matrices","Isoperimetric tiling answers matrix extremum","Correcting the bad-science matrix rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Bad-science matrices get exact second-order term","Explicit near-optimal bad-science matrices found","Universal two-term limit for bad-science matrices","Isoperimetric tiling answers matrix extremum","Correcting the bad-science matrix rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1528,"prompt_tokens":1100,"completion_tokens":428,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":716,"completion_tokens_details":{"reasoning_tokens":357}},"tokens_in":716,"tokens_out":428,"duration_ms":3707,"temperature":1.0,"reasoning_tokens":357,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:59:59.759849+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"Bad Science Matrices","cited_arxiv_id":"2402.03205","evidence_quote":"Sets up the bad science matrix problem and proves the leading-order rate $(1+o(1))\\sqrt{2\\log n}$, along with the random-sign matrix heuristic."},{"cited_title":"High-dimensional Central Limit Theorems by Stein's Method in the Degenerate Case","cited_arxiv_id":"2305.17365","evidence_quote":"Supplies the high-dimensional central limit theorem with explicit error bound used to replace the Rademacher maximum by a Gaussian maximum."},{"cited_title":"Hadamard,R´ esolution d’une question relative aux d´ eterminants, Bull","cited_arxiv_id":null,"evidence_quote":"Hadamard's conjecture is assumed in Lemma 3.4 to force the nearest Hadamard order to satisfy $m-n\\le3$, giving flat entries for the QR-normalized truncation."},{"cited_title":"How much are increasing sets positively correlated?Combinatorica, 16(2):243–258, 1996","cited_arxiv_id":null,"evidence_quote":"Talagrand's Level-1 inequality bounds the Fourier weight of each cell and yields the universal upper bound used in Theorem 2.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Gaussian correlation inequality pins down the identity covariance as the maximizer of the expected Gaussian supremum."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the asymptotic expansion for the expected absolute maximum of standard Gaussians, producing the second-order term."},{"cited_title":"On the Structure of Bad Science Matrices","cited_arxiv_id":"2408.00933","evidence_quote":"Earlier explicit constructions and small-dimension solutions; its tree/subcube matrices are compared and diagnosed in Section 4."}],"review_version":2}