{"id":"8793a024-0f79-4a15-b82a-6691c272c13c","arxiv_id":"2502.06730","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"The fractional binary rank is not multiplicative under Kronecker products: the Domino matrix gives bpf(D⊗D) ≤ 6 < 6.25, and its asymptotic fractional rank lies between 2 and 2.373.","lead":"The paper shows that the fractional binary rank, a measure of how efficiently a binary matrix can be decomposed into complete bipartite blocks, is not multiplicative when matrices are combined with the Kronecker product. This resolves a natural conjecture in the fractional setting and leaves a concrete open interval for the asymptotic value of the small Domino example.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's upper bound 2.372713 rests on an unaudited Gurobi column-generation run for k=5; no certificate or pinned code is provided, so the interval is not independently verifiable from the paper.","rationale":"The paper has two contributions: (1) a rigorous disproof of multiplicativity of fractional binary rank via explicit decomposition of D⊗D, and (2) an engineered interval [2,2.372713] for the asymptotic fractional binary rank of the Domino. Contribution (1) is fully proven: the displayed 12 matrices weighted by 0.5 form a feasible fractional biclique partition of D⊗D with objective 6, and since bpf(D)=2.5 is certified by the displayed dual solution, 6 < 6.25 disproves multiplicativity. Lemma 3's proof is sound; the projection argument correctly produces a fractional cover of G_A from a fractional partition of G_{A⊗A'}, and the multiplicativity of bcf gives the asymptotic lower bound 2. Thus the central structural claim does not depend on any computation. The computational upper bound is the sole weak point: the value 75.201302 for k=5 is not accompanied by a certificate, and the column-generation implementation involves heuristics (solution-pool pricing, pruning counter, ε=1e-6) and a commercial solver, so an independent reader cannot verify the reported optimum from the paper alone. This is a verifiability gap rather than a demonstrated error; the code is open source, so the gap can be closed. If the k=5 value fails verification, the correct theorem would still hold with the weaker upper bound sqrt(6) from the explicit decomposition, preserving the main claim. Hence the CONDITIONAL verdict is appropriate, and no adjustment is needed.","tokens_in":13361,"tokens_out":13853,"duration_ms":116310,"concrete_test":"Pin the repository commit and Gurobi version, re-run the k=5 instance with deterministic settings, and verify that the final master LP solution satisfies Mx=1 to 1e-8 and has objective ≤ 75.201302; additionally generate a machine-checkable certificate (explicit weighted biclique list or dual LP) for bpf(D^⊗5). If no certificate can be produced, recompute the rigorous upper bound using only the explicit decomposition, giving [2, sqrt(6)].","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's core non-multiplicativity result is rigorously established by the explicit 12-biclique decomposition in Section 3, which shows bpf(D⊗D) ≤ 6 < 6.25 = bpf(D)^2, and Lemma 3's lower bound bcf(A) ≤ bp∞_f(A) is proven correctly. The only load-bearing gap is the reported upper endpoint of Theorem 2, bpf(D^⊗5)=75.201302, used to claim bp∞_f(D) ≤ 2.372713. This value comes from a column-generation LP solved with Gurobi 10.0.0, but the paper ships no dual certificate, no LP/log files, and no commit hash for the public repository. The algorithm's pricing stage uses a heuristic solution pool and pruning, and Gurobi's floating-point tolerances could make the final 'feasible' partition violate Mx=1 at the 1e-6 level. If the true value of bpf(D^⊗5) is larger than 75.201302, the interval's upper bound is not established. However, even in that case the rigorous bound sqrt(6)≈2.449 from the explicit decomposition suffices to show the asymptotic fractional binary rank is strictly below the fractional binary rank 2.5; only the sharper interval in Theorem 2 would be affected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the fractional binary rank (equivalently, the fractional biclique partition number bp_f) of Kronecker powers of binary matrices, motivated by the open question whether binary rank is multiplicative under Kronecker products. The central mathematical contribution is an explicit fractional biclique decomposition of D⊗D, where D is the 3×3 Domino matrix, using twelve bicliques each with weight 1/2, which yields bp_f(D⊗D) ≤ 6 < 6.25 = bp_f(D)^2 and thereby disproves multiplicativity of the fractional binary rank. The authors prove Lemma 3, a lower bound bp_f(A⊗A') ≥ max{bcf(A) bp_f(A'), bp_f(A) bcf(A')}, which implies bcf(A) ≤ bp∞_f(A) and gives the lower bound 2 for the Domino. On the computational side, the paper engineers a column-generation method with inductive initialization, ILP-based pricing over maximal bicliques, and pruning, and reports bp_f(D^{⊗k}) values for k=1,...,5, leading to the interval bp∞_f(D) ∈ [2, 2.372713]. The paper also discusses the relation between biclique cover/partition numbers and the isolating-set bound.","tokens_in":13554,"tokens_out":12791,"duration_ms":116648,"significance":"The explicit disproof of multiplicativity is a clean and checkable result: it settles a natural conjecture for the fractional relaxation of binary rank in the negative, and it is the kind of counterexample that can be verified by direct inspection. Lemma 3 is a useful strengthening of the standard isolating-set lower bound and is proved with a projection argument that, once the details are spelled out, is sound. The computational engineering is thoughtful and the reported upper bounds are plausible, but the exactness of the k=5 optimum is not independently auditable from the manuscript. Even without the computed upper bound, the elementary bound bp∞_f(D) ≤ sqrt(6) ≈ 2.449 obtained from the explicit decomposition already implies the qualitative phenomenon that the asymptotic fractional binary rank can be strictly below the fractional binary rank. The paper therefore contains a solid core result plus a potentially interesting but less fully certified computational upper bound.","major_comments":[{"comment":"The exactness of the reported values in the table of Section 5.4, in particular bp_f(D^{⊗5}) = 75.201302, is not verifiable from the manuscript. The column-generation loop stops when no column in the current pool has reduced cost above 1+ε, but the paper does not report the final maximum pricing objective α, the implied dual lower bound, or any certificate that the final primal solution satisfies Mx=1. Pruning in Section 5.3 can delete columns permanently, and although pricing over all maximal bicliques should in principle regenerate useful columns, the completeness of the search and the final duality gap are asserted rather than documented. Please provide the final dual bound for each k, a machine-checkable certificate (e.g., the list of bicliques and weights for k=5), and the repository commit hash; alternatively, state explicitly that the table gives upper bounds obtained from feasible fractional partitions and adjust the wording of Theorem 2 and the abstract.","section":"5.3–5.4"}],"minor_comments":[{"comment":"The sentence 'this decomposition is also optimal because there is a dual feasible solution certifying bp_f(D⊗D) ≥ 6' is not supported by an explicit certificate in the text; no dual vector is shown, in contrast to the certificate Y* provided for D. While the upper bound 6 alone is enough for the non-multiplicativity claim, the table in Section 5.4 reports 6.0 as an exact value, so the claimed optimality of the 12-biclique decomposition should be backed by the dual vector or a file reference.","section":"Section 3"},{"comment":"Please expand the sentence 'The intersection ... yields a feasible fractional biclique partition of G_A′' in the proof of Lemma 3 to explain that restricting each intersecting biclique to the block gives a biclique in the block and that the edge-cover weights sum to one for every edge in the block.","section":"Section 4"},{"comment":"The dual variables in Eq. (5) are unrestricted in sign because the primal problem has equality constraints; please state this explicitly when introducing the dual.","section":"Section 5.2"},{"comment":"The sentence beginning 'To ensure that the number of bicliques does not blow up too fast when we It is possible...' is grammatically broken and should be rewritten.","section":"Section 5.3"},{"comment":"The speculation that bp_f(D^{⊗3}) could equal 2059/149 is unsupported; either verify this identity or remove the sentence.","section":"Section 5.4"},{"comment":"Please include the repository commit hash and the exact Gurobi parameter settings (e.g., MIP gap for the pricing ILPs, barrier crossover tolerances) to make the computational claims reproducible.","section":"Section 5.4"}],"recommendation":"major_revision","confidential_remarks":"The paper's strongest and cleanest contribution is the explicit non-multiplicativity example, which is rigorous and independently verifiable; the computational upper bound is secondary. I recommend requesting the missing certificates and a clearer separation of 'computed optimum' from 'upper bound obtained from a feasible solution' before publication. The paper fits the journal's scope, and I see no novelty concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one for the counterexample. The authors give an explicit 12-biclique decomposition of D⊗D, each with weight 1/2, showing bpf(D⊗D) ≤ 6 < 6.25 = bpf(D)^2. That rigorously kills multiplicativity of fractional binary rank under Kronecker products, and it is the real contribution. The fractional boolean (cover) rank is multiplicative, so this distinction is meaningful.\n\nThe rest is a clean lower-bound lemma plus an engineered column-generation pipeline. Lemma 3 proves bcf(A) ≤ bp∞_f(A) via a projection argument, and it is at least as strong as the isolating-set bound. The proof is correct as far as I can see, aside from one typo: the sentence after the first half says 'bcf(A⊗A′)≤bpf(A)·bcf(A′)' which is not the bound you need; swapping roles gives bpf(A⊗A') ≥ bpf(A) bcf(A'), and since bpf is invariant under swapping factors, that works.\n\nThe computational part is clever and fragile. The column-generation scheme—inductive initialization from Kronecker products, pricing via QUBOs over maximal bicliques, pruning by a slack counter—is sensible and the reported running times are plausible. But the upper bound in Theorem 2, bpf(D^⊗5)=75.201302, comes from a Gurobi run with no solver certificate, no log files, and no pinned repository revision. Pricing uses heuristic thresholds (ε=1e-6, pruning after 3 slacks), and floating-point tolerances could mean the final solution is not exactly feasible. As written, an independent group cannot audit that number. If it is off, the interval [2,2.372713] is not established. However, the rigorous decomposition for k=2 already gives bp∞_f(D) ≤ sqrt(6) ≈ 2.449, so the qualitative conclusion—asymptotic fractional binary rank strictly below 2.5—does not depend on the computational result.\n\nThere is also a small verifiability gap in Section 3: the paper claims a dual certificate for bpf(D⊗D) ≥ 6 but does not display it. This is minor and easily fixed; the disproof only needs the upper bound.\n\nBottom line: the core result is new, correct, and worth a serious referee. Citations are appropriate, and the distinction from Watts' multiplicativity result is clearly drawn. The authors should be asked to supply the missing dual certificate and to make the computational run reproducible with certificates, logs, and a commit hash. This is for people working on combinatorial matrix ranks, communication complexity, or exponential-size LPs.","headline":"Rigorous counterexample to multiplicativity of fractional binary rank, with a fragile computational upper bound that needs verification.","tokens_in":14155,"tokens_out":5224,"would_cite":true,"duration_ms":42381,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","15A23","90C05","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The 3×3 Domino matrix shows the fractional binary rank is not multiplicative under the Kronecker product, and its asymptotic rank lies in [2, 2.373].","keywords":["fractional binary rank","biclique partition","Kronecker product","asymptotic rank","column generation","Domino graph","biclique cover","linear programming"],"falsifier":"Independently solve the fractional biclique partition LP for $D^{\\otimes 5}$ with a different solver or an exact rational LP algorithm: if the optimum is below 75.201302, the reported optimality claim is wrong, and if it is above, the upper bound is false. For the non-multiplicativity result, check the twelve 0-1 matrices and the dual certificate in Section 3 by hand to confirm $\\mathrm{bp}_f(D\\otimes D)=6$.","tokens_in":13075,"feed_emoji":"🧩","tokens_out":8135,"duration_ms":63137,"temperature":0.7,"pith_summary":"The paper tries to settle whether the fractional binary rank—the least total weight of bicliques needed to cover a matrix's 1-entries exactly—is multiplicative under Kronecker products. It answers no: the Domino matrix $D$ satisfies $\\mathrm{bp}_f(D\\otimes D)=6$, strictly below $\\mathrm{bp}_f(D)^2=6.25$, so the asymptotic fractional binary rank of the Domino is strictly smaller than its fractional binary rank. The paper also proves that the fractional biclique cover number lower-bounds the asymptotic fractional binary rank, and it engineers a column-generation algorithm that computes $\\mathrm{bp}_f(D^{\\otimes k})$ for $k$ up to 5, giving the interval $[2, 2.372713]$ for the Domino. If correct, this establishes the fractional binary rank as another rank function—alongside nonnegative and boolean rank—whose asymptotic value can be strictly less than its finite value.","feed_headline":"Domino graph breaks multiplicativity of fractional binary rank","feed_subtitle":"Explicit 12-biclique decomposition gives 6 < 6.25 and pins asymptotic rank between 2 and 2.373.","key_machinery":"The central objects are the fractional biclique partition number $\\mathrm{bp}_f(A)$ (equivalently the fractional binary rank), the Domino matrix $D$, and its Kronecker powers $D^{\\otimes k}$. The argument is carried by two mechanisms: (1) an explicit 12-biclique fractional decomposition of $D\\otimes D$ with uniform weight $1/2$, accompanied by a dual certificate proving optimality at value 6, which shows the rank function is not multiplicative; and (2) a projection lemma that maps bicliques of $A\\otimes A'$ to bicliques of $A$ by intersecting with blocks of the form $a_{ij}A'$, normalizing by $\\mathrm{bp}_f(A')$, to convert an optimal fractional partition of the product into a fractional cover of $A$. The computational upper bound rests on a column-generation scheme whose pricing problem is a maximum-weight submatrix ILP posed per maximal biclique, with maximal bicliques computed by the MBEA algorithm, initialized inductively from Kronecker products of optimal biclique sets, and pruned by counting slack iterations.","core_discovery":"The central discovery is a counterexample to multiplicativity of the fractional binary rank: for the Domino adjacency matrix $D$, $\\mathrm{bp}_f(D\\otimes D) = 6 < 6.25 = \\mathrm{bp}_f(D)^2$. The 12-biclique fractional decomposition with weight $1/2$ on each biclique, together with an explicit dual feasible solution, certifies this value. Consequently, by Fekete's lemma the asymptotic fractional binary rank $\\mathrm{bp}^\\infty_f(D)$ is well defined and strictly less than $\\mathrm{bp}_f(D)$. The paper additionally proves that $\\mathrm{bp}_f(A\\otimes A') \\ge \\max\\{ \\mathrm{bc}_f(A)\\cdot\\mathrm{bp}_f(A'),\\ \\mathrm{bp}_f(A)\\cdot\\mathrm{bc}_f(A') \\}$, which implies that the fractional biclique cover number $\\mathrm{bc}_f(A)$ is a lower bound on the asymptotic fractional binary rank; for the Domino this yields the lower bound $2$. Finally, the engineered column-generation algorithm computes $\\mathrm{bp}_f(D^{\\otimes 5}) = 75.201302$, giving $\\mathrm{bp}^\\infty_f(D) \\le 2.372713$.","pith_inferences":["If further Kronecker powers keep pushing the $k$-th root toward 2, the asymptotic fractional binary rank of the Domino would equal its fractional biclique cover number, which would match the value predicted by the fractional boolean rank—an equality the paper does not itself claim.","The projection lemma gives a general template for lower-bounding fractional binary rank of products: project an optimal fractional partition of $A\\otimes A'$ onto one factor and compare with a fractional cover; applying this to graphs other than the Domino could reveal whether non-multiplicativity is rare or common.","Since the fractional relaxation already fails multiplicativity at the second power, the integer binary rank question likely requires a genuinely different approach; a fractional counterexample does not transfer to the integer case, but it rules out simple fractional-based proofs of multiplicativity.","The suggested rational value $2059/149$ for $\\mathrm{bp}_f(D^{\\otimes 3})$ invites a combinatorial construction that would make the upper-bound sequence exactly computable for small $k$ without rerunning the optimizer."],"forward_implications":["The Domino graph is a concrete witness that the fractional binary rank is not multiplicative, placing it alongside nonnegative and boolean rank as rank functions whose asymptotic value can be strictly smaller than the finite value.","The interval $2 \\le \\mathrm{bp}^\\infty_f(D) \\le 2.372713$ is now the best-known bound, and solving $k=6$ would tighten the upper endpoint since Fekete's lemma identifies the infimum over all $k$.","The proven chain $i(A) \\le \\mathrm{bc}_f(A) \\le \\mathrm{bp}^\\infty_f(A) \\le \\mathrm{bp}_f(A) \\le \\mathrm{bp}(A)$ gives a new general lower bound for the asymptotic fractional binary rank in terms of the fractional biclique cover number, which is at least as strong as the fooling-set bound.","The column-generation machinery with inductive initialization and slack-based pruning handles problems with double-exponentially many bicliques, so the same pipeline can be retargeted at other small graphs and their Kronecker powers."],"supporting_citations":[{"why":"Supplies the fractional biclique cover/partition framework and the multiplicativity of fractional boolean rank, against which the new non-multiplicativity of fractional binary rank is contrasted; also the source of the fooling-set lower bound.","marker":"[12]"},{"why":"States the open question whether binary rank is multiplicative, the target of the paper's fractional counterexample.","marker":"[10]"},{"why":"Fekete's lemma justifies the definition of asymptotic rank and the characterization as the infimum of $k$-th roots of $\\mathrm{bp}_f(A^{\\otimes k})$.","marker":"[5]"},{"why":"Provides the MBEA algorithm used to enumerate inclusion-wise maximal bicliques for the pricing step.","marker":"[13]"},{"why":"Supplies the projection strategy that Lemma 3 adapts to prove the lower bound $\\mathrm{bc}_f(A) \\le \\mathrm{bp}^\\infty_f(A)$.","marker":"[8]"},{"why":"The maximum-sum submatrix technique that the pricing ILP is modeled on.","marker":"[4]"},{"why":"The column-generation reference underpinning the master-pricing loop.","marker":"[9]"}],"fun_headline_variants":["Domino graph defies fractional binary rank multiplicativity","6 < 6.25: Domino breaks multiplicativity of fractional binary rank","Domino disproves multiplicativity of fractional binary rank","Fractional binary rank: Domino gives counterexample to multiplicativity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed upper bound 2.372713 depends on the correctness of the engineered column-generation solver with Gurobi 10.0.0 on the $k=5$ instance, whose reported value 75.201302 is not accompanied by a solver certificate or versioned code, so it cannot be independently verified from the paper alone.","fun_headline_variants_meta":{"raw":{"variants":["Domino graph defies fractional binary rank multiplicativity","6 < 6.25: Domino breaks multiplicativity of fractional binary rank","Domino disproves multiplicativity of fractional binary rank","Fractional binary rank: Domino gives counterexample to multiplicativity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001501,"raw_usage":{"total_tokens":6115,"prompt_tokens":1133,"completion_tokens":4982,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":749,"completion_tokens_details":{"reasoning_tokens":4910}},"tokens_in":749,"tokens_out":4982,"duration_ms":29678,"temperature":1.0,"reasoning_tokens":4910,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:31:52.818187+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Independently solve the fractional biclique partition LP for $D^{\\otimes 5}$ with a different solver or an exact rational LP algorithm: if the optimum is below 75.201302, the reported optimality claim is wrong, and if it is above, the upper bound is false. For the non-multiplicativity result, check the twelve 0-1 matrices and the dual certificate in Section 3 by hand to confirm $\\mathrm{bp}_f(D\\otimes D)=6$.","supporting_citations":[{"cited_title":"Fractional biclique covers and partitions of graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the fractional biclique cover/partition framework and the multiplicativity of fractional boolean rank, against which the new non-multiplicativity of fractional binary rank is contrasted; also the source of the fooling-set lower bound."},{"cited_title":"Nonnegative rank vs","cited_arxiv_id":null,"evidence_quote":"States the open question whether binary rank is multiplicative, the target of the paper's fractional counterexample."},{"cited_title":"\\\"U ber die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten","cited_arxiv_id":null,"evidence_quote":"Fekete's lemma justifies the definition of asymptotic rank and the characterization as the infimum of $k$-th roots of $\\mathrm{bp}_f(A^{\\otimes k})$."},{"cited_title":"Phillips, Gary L","cited_arxiv_id":null,"evidence_quote":"Provides the MBEA algorithm used to enumerate inclusion-wise maximal bicliques for the pricing step."},{"cited_title":"On biclique cover and partition problems","cited_arxiv_id":null,"evidence_quote":"Supplies the projection strategy that Lemma 3 adapts to prove the lower bound $\\mathrm{bc}_f(A) \\le \\mathrm{bp}^\\infty_f(A)$."},{"cited_title":"Maximal-sum submatrix search using a hybrid contraint programming/linear programming approach","cited_arxiv_id":null,"evidence_quote":"The maximum-sum submatrix technique that the pricing ILP is modeled on."}],"review_version":1}