{"id":"ffbe10fc-8624-445a-8a82-cc81678dc163","arxiv_id":"2507.00872","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A boolean matrix with gamma-2 norm at most lambda contains a blocky submatrix that covers at least a 1/2^{2^{O(lambda)}} fraction of its 1-entries.","lead":"The paper proves that every boolean matrix with small gamma-2 factorization norm contains a large blocky submatrix built from disjoint all-1 rectangles. This is a step toward resolving a conjecture on writing such matrices as sums of few blocky matrices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim depends on unverified BHT25 monochromatic-rectangle theorem; if that theorem is false or has additional hypotheses, the blocky extraction in Lemma 3.2 collapses.","rationale":"The reader's weakest assumption correctly identifies the BHT25 dependency. The proof of Theorem 1.5 uses Theorem 1.4 exactly once, in Lemma 3.2, and the entire quantitative blocky-extraction argument depends on obtaining a positive-density 1-rectangle in a dense low-γ2 submatrix. The internal typographical errors, notably in Lemma 2.7's display, are real but clearly repairable: the displayed sum should be over |R_s|, not ||u_s||^2|R_s|, and the surrounding inequalities can be fixed while preserving the lemma's statement. No other flaw in the induction appeared after checking the algebra in the two alternatives of Lemma 3.2 and the disjointness of the resulting blocks. Therefore the central claim is plausible conditional on BHT25, and the reader's CONDITIONAL verdict should stand unchanged.","tokens_in":11523,"tokens_out":25180,"duration_ms":252696,"concrete_test":"Read BHT25 (arXiv:2506.23989), Theorem 1.1, and independently re-derive the monochromatic-rectangle density bound for rectangular boolean matrices with γ2 norm at most λ and density >1/2. Then re-check Lemma 3.2: if the derived bound is at least 2^{-2^{O(λ)}} for every such matrix, the induction closes; otherwise, identify the minimal density bound needed for inequality (57) to hold and compare against what BHT25 actually proves.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.5's proof invokes Theorem 1.4 of BHT25 (a 2025 preprint) in Lemma 3.2, case (i). There the pivot-row inequality (44) forces a submatrix A_{S×R_i} with density >1/2, and BHT25 is used to extract a 1-rectangle of size e^{-O(λ^3)}|S||R_i|. This rectangle is the only source of new blocky 1-entries in the balanced case: the induction lower bound (57) adds k/e^{O(λ^3)} and requires that guarantee to overcome the 10λ^4 k loss. If BHT25's theorem required extra hypotheses (e.g., square matrices, dimension-dependent constants not stated) or if the guarantee were absent, the induction would not close and Theorem 1.5 would not follow from this argument. The manuscript contains no fallback for this case, so the correctness of the main theorem rests directly on an unverified external result. The typos in Lemma 2.7's displayed inequalities are repairable and do not change this assessment.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1.5: for every m×n boolean matrix A with γ2 norm at most λ and F ones, there exists a blocky matrix B of the same dimensions, with B(i,j)=1 only if A(i,j)=1, containing at least F / 2^{2^{O(λ)}} ones. The proof introduces a potential function Π_λ(A) and the threshold dimension TD(A), and proceeds by an induction that either deletes a set of columns with a large potential drop (Lemma 2.7) or extracts a large 1-monochromatic rectangle or a lower-threshold-dimensional submatrix (Lemma 3.2). The argument relies essentially on Theorem 1.4 of Balla–Hambardzumyan–Tomon (BHT25), a 2025 preprint guaranteeing a large monochromatic rectangle in any boolean matrix of bounded γ2 norm. The paper also derives Corollary 1.6, an explicit double-exponential bound for the existence of a large 1-rectangle.","tokens_in":11737,"tokens_out":20534,"duration_ms":199918,"significance":"If the result is correct, it provides a matrix analogue of the Green–Sanders quantitative idempotent theorem and can be viewed as a weak stability statement for Livshits' characterization of blocky matrices as those with γ2 norm at most 1. The proof is structurally clean, combining a custom potential function with threshold-dimension analysis, and it makes the quantitative dependence on λ explicit (though double-exponential). A clear strength is that the main argument is self-contained beyond the black-box use of BHT25, and the derived Corollary 1.6 gives a concrete improvement over the qualitative statement in BHT25. The main risk is the dependence on a non-peer-reviewed preprint.","major_comments":[{"comment":"Equation (37) contains an inequality that does not follow from the displayed assumptions. The lower bound (1/(2λ²)) Σ_{s∈Δ_i} ||u_s||² |R_s| ≥ 2η is not implied by assumption (32), which gives Σ_{s∈Δ_i} |R_s| ≥ 4λ² η, because the factors ||u_s||² ≤ 1 can only make the weighted sum smaller. A correct argument is: for s∈Δ_i, (36) yields ||u_s||² − ||u'_s||² ≥ 1/(2λ²), so Π_{U,V}(A) − Π_{U',V'}(A') ≥ (1/(2λ²)) Σ_{s∈Δ_i} |R_s| ≥ 2η. The printed proof should be corrected to remove the spurious ||u_s||² factor inside the sum.","section":"Section 2, Lemma 2.7"},{"comment":"The proof of case (i) of Lemma 3.2 and the subsequent induction step in (57) rely essentially on Theorem 1.4 of BHT25, a preprint whose result is not proved in this manuscript. If the bound e^{-O(λ³)} were weaker or subject to additional hypotheses, the blocky extraction step would not close the induction. The authors should either include a proof of the needed consequence of BHT25 or explicitly state that Theorem 1.5 is conditional on that preprint and confirm its current status.","section":"Lemma 3.2 / Theorem 1.5"}],"minor_comments":[{"comment":"The abstract contains the doubled article in 'there exists a a collection'; also 'm×nboolean matrixA' is missing a space.","section":"Abstract"},{"comment":"The proof claims to establish ||G||_{γ2} ≥ Ω(log² n), but the computation at the end of the proof yields only Ω(log n). The weaker bound is sufficient for the stated consequence TD(A) ≤ 2^{O(λ)}; the text should be corrected from 'log² n' to 'log n'.","section":"Proposition 3.1"},{"comment":"The displayed comparison to λ^{2O(λ)} is not accurate: since d ≤ 2^{O(λ)}, the factor (40λ^4)^d is bounded by 2^{2^{O(λ)}}, not by λ^{2O(λ)}. The final denominator should be written directly as 2^{2^{O(λ)}}.","section":"Proof of Theorem 1.5, Eq. (50)"},{"comment":"In the numerator of the lower bound, the coefficient '10λ^2 k' should be '10λ^4 k' to match the bound in (45); the subsequent inequality still holds with the corrected coefficient.","section":"Proof of Theorem 1.5, Eq. (57)"},{"comment":"The displayed chain '1 ≥ 1/2/denom ≥ (1−Π/2)/denom' has the middle inequality reversed for Π ≤ 1; the desired conclusion b ≥ (1−Π/2)/denom follows directly from 1 ≥ (1−Π/2)/denom.","section":"Proof of Theorem 1.5, base case (51)"},{"comment":"The phrase 'let 1≤i≤[m] be given' should read 'let 1≤i≤m be given'.","section":"Lemma 2.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a solid contribution, but the proof has a local, repairable gap in Lemma 2.7 and is contingent on the BHT25 preprint. If the authors fix the inequality and clarify the status of the external theorem, I would support acceptance. The novelty and methods are appropriate for the journal, and the paper is not circular: the main theorem follows from a fresh potential-threshold argument applied to the BHT25 black box."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on Goh–Hatami, arXiv:2507.00872.\n\nThe paper proves a new quantitative structure theorem: any boolean matrix with γ2 norm at most λ has a blocky submatrix containing at least 1/2^{2^{O(λ)}} of its ones. That's a real step beyond BHT25's single-rectangle result, and the proof idea—a potential function over factorizations plus a threshold-dimension descent—is fresh and worth knowing. Corollary 1.6, an explicit double-exponential density for a 1-rectangle, is a nice bonus. The writing is clear and the history is handled honestly, including the authors' own GH25 for background.\n\nWhere are the soft spots? Lemma 2.7's displayed inequality (37) doesn't follow as printed. The step Π_U,V(A)−Π_{U',V'}(A') ≥ (1/2λ²)Σ_{s∈Δ_i}||u_s||²|R_s| ≥ 2η uses the assumption on ||A_{Δ_i×[n]}||²_F, but the middle term is weighted by ||u_s||² and the assumption bounds the unweighted sum. The reader's proposed repair—use Σ|R_s| directly and accept a slightly worse constant—looks right. Proposition 3.1 says 'Ω(log² n)' but proves Ω(log n); it's a typo, and the conclusion d ≤ 2^{O(λ)} still follows. The abstract has a doubled 'a' and the introduction says 'bab-rectangle', but these are cosmetic.\n\nThe bigger caveat is external: the proof leans on Theorem 1.4 of BHT25, a 2025 preprint, for the concentrated case in Lemma 3.2. If that theorem has hidden hypotheses or is wrong, the induction in Theorem 1.5 doesn't close. This isn't a defect of the paper—you can't re-prove every dependency—but a referee should check BHT25 carefully, and ideally the authors should coordinate. I don't see circularity or fitted parameters. The main theorem is new and the argument is coherent.\n\nBottom line: this deserves a serious referee. It's not a desk reject; it's a solid, interesting contribution with a couple of repairable typos. I'd give it a conditional accept and ask for fixes. I'd cite it myself as the current best quantitative block-structure statement.","headline":"A new and credible quantitative block-structure theorem for bounded γ2 norm, held up by a few repairable typos and a heavy reliance on a recent unverified preprint.","tokens_in":12259,"tokens_out":3420,"would_cite":true,"duration_ms":36668,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15B36","47L80","94D10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every boolean matrix with $\\gamma_2$ norm at most $\\lambda$ contains a blocky submatrix that keeps at least a $1/2^{2^{O(\\lambda)}}$ fraction of its 1-entries.","keywords":["boolean matrices","γ₂ factorization norm","blocky matrices","monochromatic rectangles","threshold dimension","Schur multipliers","stability"],"falsifier":"Look for a family of boolean matrices with $\\gamma_2$ norm at most a fixed $\\lambda$ and $F$ ones, growing with the dimensions, in which every collection of row- and column-disjoint all-1 submatrices covers $o(F)$ ones; equivalently, the maximum density of a monochromatic 1-rectangle should drop below $1/2^{2^{O(\\lambda)}}$ while the matrix still has bounded $\\gamma_2$ norm. A direct computation of the largest blocky submatrix in an explicit candidate matrix would settle the matter.","tokens_in":11327,"feed_emoji":"🧱","tokens_out":9974,"duration_ms":97779,"temperature":0.7,"pith_summary":"The paper proves that every boolean matrix whose $\\gamma_2$ factorization norm is bounded by $\\lambda$ has a large blocky core: one can select row- and column-disjoint all-1 submatrices inside it that together cover at least a $1/2^{2^{O(\\lambda)}}$ fraction of all 1-entries. Blocky matrices are exactly the boolean matrices with $\\gamma_2$ norm at most 1, so the theorem is a stability statement: relaxing the norm bound from 1 to $\\lambda$ still leaves a $\\lambda$-dependent constant fraction of block structure. This is the boolean-matrix analogue of the quantitative idempotent theorem for boolean functions with small Fourier algebra norm, and it sharpens an earlier polylogarithmic dimension-dependent block-complexity bound into a dimension-free, constant-fraction form. The proof runs by induction on the number of 1s, a potential function, and the threshold dimension, using a recent monochromatic-rectangle lemma to extract the basic blocks.","feed_headline":"Every low-norm boolean matrix contains a large blocky core","feed_subtitle":"The paper proves a constant fraction of all 1-entries can be covered by disjoint all-1 rectangles.","key_machinery":"The proof is carried by two parameters. The potential function $\\Pi_\\lambda(A)=\\inf\\sum_{s=1}^{m}\\|u_s\\|_2^2|R_s|$, where the infimum runs over all $\\lambda$-factorizations $A=UV$ (rows of $U$ have norm at most 1, columns of $V$ norm at most $\\lambda$), measures how far $A$ is from being blocky; its lower bound $\\|A\\|_F^2/\\lambda^2$ is attained exactly for blocky matrices. The threshold dimension $\\mathrm{TD}(A)$ is the largest $d$ for which $A$ contains a $d\\times d$ staircase pattern $A(i_s,j_t)=1[s\\ge t]$, and $\\mathrm{TD}(A)=1$ exactly for blocky matrices; Proposition 3.1 shows $\\mathrm{TD}(A)\\le 2^{O(\\lambda)}$ when $\\|A\\|_{\\gamma_2}\\le\\lambda$. A pivotal-row lemma states that either deleting the neighbourhood $R_i$ of some row causes a substantial potential drop, allowing recursion, or the matrix is concentrated on $\\Delta_i\\times R_i$ (where $\\Delta_i$ contains rows whose factor vectors correlate strongly with row $i$), and then the monochromatic-rectangle lemma of [BHT25] yields either a large 1-rectangle or a submatrix whose threshold dimension decreased by 1. Iterating the threshold-dimension drop up to $2^{O(\\lambda)}$ levels against the $2^{-O(\\lambda^3)}$ rectangle-density loss produces the double-exponential denominator.","core_discovery":"The central claim is Theorem 1.5: if $A$ is an $m\\times n$ boolean matrix with $\\|A\\|_{\\gamma_2}\\le\\lambda$ and $F$ ones, then there is a blocky matrix $B$ of the same dimensions with $B(i,j)=1$ only where $A(i,j)=1$, and with at least $F/2^{2^{O(\\lambda)}}$ ones. In words, the 1-entries of a bounded-norm boolean matrix can be covered to a constant fraction by a collection of all-1 rectangles that are pairwise disjoint in both rows and columns. The constant depends only on $\\lambda$, not on the matrix dimensions. As a direct corollary the proof yields an explicit double-exponential version of the known non-quantitative statement that a 1-rectangle of size proportional to $F/n$ and $F/m$ exists in such a matrix.","pith_inferences":["The double-exponential denominator is not obviously forced by the norm alone; any improvement in Proposition 3.1's bound $\\mathrm{TD}(A)\\le 2^{O(\\lambda)}$ would automatically improve Theorem 1.5's exponent, so pinning the true growth of threshold dimension in terms of $\\lambda$ is a natural next step.","Specializing to circulant matrices $A(x,y)=f(x-y)$, the theorem suggests that the coset-decomposition constant from the quantitative idempotent theorem should be recoverable by purely matrix arguments; checking whether the blocky rectangles produced can always be taken to be cosets would connect the two results more tightly.","The case distinction in Lemma 2.7 and Lemma 3.2 gives an explicit recursive recipe that, given a $\\lambda$-factorization, outputs the blocky submatrix; this algorithmic reading is not spelled out in the paper.","If the constant-fraction blocky cover is essentially optimal, then any disjoint-rectangle cover of the support of a bounded-norm matrix must lose at least that fraction, providing a concrete benchmark for rectangle-based communication-complexity arguments."],"forward_implications":["Every boolean matrix with $\\gamma_2$ norm at most $\\lambda$ has a blocky core of density at least $1/2^{2^{O(\\lambda)}}$, with no dimension-dependent loss.","Writing $A=B+C$, the leftover matrix $C$ has at most $F(1-1/2^{2^{O(\\lambda)}})$ ones, so structural statements that hold for blocky matrices extend to bounded-norm matrices up to an exponentially small error in the support.","Corollary 1.6 gives a single 1-rectangle with at least $c_\\lambda F/n$ rows and $c_\\lambda F/m$ columns for $c_\\lambda\\ge 1/2^{2^{O(\\lambda)}}$, a quantitative form of the previously non-quantitative [BHT25] theorem.","In the group-translation case $A(x,y)=f(x-y)$ with $\\|f\\|_{\\mathcal A}\\le\\lambda$, the theorem gives the matrix analogue of the quantitative idempotent theorem's support statement: a constant fraction of the support of $f$ admits structured covering.","The proof's explicit bound offers a route toward the signed-sum block-complexity conjecture: a single blocky matrix already captures a constant fraction of the support, so the conjecture reduces to controlling the leftover matrix by further applications of the same induction."],"supporting_citations":[{"why":"Supplies the monochromatic rectangle of density at least $2^{-O(\\lambda^3)}$ inside any boolean matrix with $\\gamma_2$ norm at most $\\lambda$, invoked in Lemma 3.2 to extract a 1-rectangle or force the threshold dimension to drop.","marker":"[BHT25]"},{"why":"Characterizes boolean matrices with $\\gamma_2$ norm at most 1 as blocky matrices, fixing the target structure and identifying when the potential lower bound is attained.","marker":"[Liv95]"},{"why":"Provides the earlier polylogarithmic block-complexity bound that the new constant-fraction result sharpens.","marker":"[GH25]"},{"why":"Formulates the signed-sum block-complexity conjecture and connects it to idempotent Schur multipliers, framing why a constant-fraction blocky submatrix is the meaningful structural conclusion.","marker":"[HHH23]"},{"why":"Underlies the threshold dimension notion and its monotonicity properties, used in the second alternative of Lemma 3.2.","marker":"[MS14]"},{"why":"Gives the quantitative idempotent theorem for boolean functions with small Fourier algebra norm, whose coset decomposition is the group-theoretic analogue the main theorem mirrors.","marker":"[GS08]"}],"fun_headline_variants":["Low-norm boolean matrices always have a blocky core","Constant fraction of 1s in disjoint all-1 rectangles","Bounded γ2 norm implies a large blocky core","Blocky core guaranteed for low-norm boolean matrices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction leans on the 2025 preprint result that every boolean matrix with $\\gamma_2$ norm at most $\\lambda$ has a monochromatic rectangle of density at least $2^{-O(\\lambda^3)}$; if that theorem required extra hypotheses or failed at any density level, the block-extraction induction would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Low-norm boolean matrices always have a blocky core","Constant fraction of 1s in disjoint all-1 rectangles","Bounded γ2 norm implies a large blocky core","Blocky core guaranteed for low-norm boolean matrices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000761,"raw_usage":{"total_tokens":3325,"prompt_tokens":841,"completion_tokens":2484,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":457,"completion_tokens_details":{"reasoning_tokens":2417}},"tokens_in":457,"tokens_out":2484,"duration_ms":21914,"temperature":1.0,"reasoning_tokens":2417,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:05:34.502362+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look for a family of boolean matrices with $\\gamma_2$ norm at most a fixed $\\lambda$ and $F$ ones, growing with the dimensions, in which every collection of row- and column-disjoint all-1 submatrices covers $o(F)$ ones; equivalently, the maximum density of a monochromatic 1-rectangle should drop below $1/2^{2^{O(\\lambda)}}$ while the matrix still has bounded $\\gamma_2$ norm. A direct computation of the largest blocky submatrix in an explicit candidate matrix would settle the matter.","supporting_citations":[],"review_version":1}