{"id":"666bbe51-239b-4515-8a29-d98651406583","arxiv_id":"2504.17947","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"For generic planted rank-one matrices in an R-dimensional subspace of m by n matrices, the JLV algorithm is proven to recover them when R is about half of mn, and proven to fail above about 0.71 times mn.","lead":"This paper tightens the proven range of an existing algorithm for finding rank-one matrices planted in a random subspace, roughly doubling the subspace dimension where success is guaranteed. It adds a provable failure threshold near 0.71 times the ambient dimension and conjectures that this is the exact breaking point, which improves tensor decomposition guarantees by a factor of two.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The central algebraic claim does not depend on any unproved or questionable step that I can find. I checked the reduction in Lemma 3.1, the squareness of M′, and the block-upper-triangular structure required for Lemma 4.9. The determinant of each 1x1 and 2x2 diagonal block is nonzero because the monomials involved are distinct formal variables or distinct products of variables after the zeroing rules. The negative result is a valid dimension count once the linear independence of the E_abcd tensors is noted. The reader’s weakest assumption (imported Propositions 2.3 and 2.4) is a legitimate caveat, but these are standard cited results with clearly satisfied hypotheses in the present setting, so it does not lower confidence in Theorem 2.5 or Corollary 2.6. I note one minor editorial issue: Corollary 7.2’s second bound appears to be a typo, since flattening along the first two modes of an order-4 tensor should require R ≤ n3*n4 rather than n2*n3; this does not affect the main rank-1 threshold results.","tokens_in":29273,"tokens_out":33619,"duration_ms":328960,"concrete_test":"Independently verify the determinant core for a small non-trivial case, e.g., m=5, n=6, k=2, s=1, R=8: construct M′ and M′′ exactly, check that M′ has one row per column, and verify that det(M′′) is a nonzero polynomial, either symbolically or over F_997, while confirming the zero pattern asserted in Lemmas 4.4–4.9. If the determinant vanishes, the block-argument has a hidden flaw; if it is nonzero, the central claim is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing concern with the central claim. The proof of Theorem 2.5 is self-contained: Lemma 3.1 correctly reduces (Goal) to full column rank of M, the construction of the square submatrix M′ is compatible with the column partition (including the Bin 4 pairing, where two columns share the same Class IV/V rows by design), and the block-upper-triangular determinant argument in Lemma 4.9 checks out block by block, with each diagonal entry or 2x2 determinant non-vanishing because the relevant monomials are distinct after the zeroing rules. The negative-result dimension count in Theorem 2.7 is also valid; the implicit linear independence of the E_abcd tensors holds because their associated 2x2-minor monomials are disjoint. The only caveats are the standard reliance on cited extraction results (Propositions 2.3 and 2.4) and a likely typo in Corollary 7.2’s second bound (flattening the order-4 tensor along the first two modes would give n3*n4, not n2*n3); neither affects the rank-1 threshold theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of recovering s planted rank-one m×n matrices from an R-dimensional linear subspace U that is generated generically by those planted matrices together with R−s generic matrices. Its main object is the key identity (Goal), which identifies the intersection S2(U) ∩ span{E_abcd}⊥ with the span of the squared planted matrices. Theorem 2.5 proves that (Goal) holds for generic planted subspaces when R ≤ 1/2 (m−1)(n−2), and Corollary 2.6 turns this into polynomial-time recovery via the cited extraction result Proposition 2.3. Theorem 2.7 gives a dimension-counting negative result: (Goal) fails when C(m,2)C(n,2) < C(R+1,2) − s, in particular when R > mn/√2 + 1. Sections 6 and 7 add a precise conjecture on the threshold, finite-field certificates and floating-point experiments for finitely many small parameter ranges, and corollaries for order-3, order-4, and symmetric tensor decomposition.","tokens_in":29449,"tokens_out":16590,"duration_ms":159605,"significance":"If correct, the paper improves the known algorithmic threshold for the JLV procedure from roughly mn/4 to roughly mn/2 and establishes an upper bound near mn/√2, essentially locating the first-order threshold up to the stated conjecture. The proof of Theorem 2.5 is a self-contained symbolic-determinant argument: a square submatrix M′′ is constructed with a block-upper-triangular structure, and Lemma 4.9 verifies that every diagonal block has nonzero determinant by checking that relevant monomials are distinct. The negative theorem is a clean dimension count. Strengths include the parameter-free nature of the threshold, the reproducible code and finite-field certificates for the computer-assisted claims, and the clear labeling of floating-point experiments as non-rigorous.","major_comments":[],"minor_comments":[{"comment":"The second term in the bound should be n3 n4 rather than n2 n3: after flattening along the first two modes, the columns c_i ⊗ d_i live in R^{n3 n4}, so the linear-independence condition is R ≤ n3 n4. This is also consistent with the final paragraph of §7, which states Rmax(n1,n2) and n3 n4.","section":"§7, Corollary 7.2"},{"comment":"The determinant formula in Eq. (3) appears to have an incorrect scalar factor: the entries of the 2×2 block already contain the factor 1/2 from Lemma 4.8, so the determinant should carry a factor 1/4 rather than 1/2. The nonvanishing conclusion is unaffected because only the zero/nonzero status matters.","section":"§4.4, Eq. (3)"},{"comment":"The abstract says the algorithm fails when R > (1+o(1))mn/√2, but Theorem 2.7 formally proves only that the identity (Goal) fails. The paper defines this as failure of a key step of the JLV algorithm, and the numerical experiments support the stronger statement, but the abstract should carry the same qualification to avoid overstating the formal result.","section":"Abstract and §2, Theorem 2.7"},{"comment":"In the Class IV zero-entry part of Lemma 4.8, the condition is written as {b,d} ≠ {g(i),g(i)}; it should be {b,d} ≠ {g(i),g(j)}.","section":"§4.3, Lemma 4.8"},{"comment":"Several typographical issues should be cleaned up: the Section 6.1 heading reads “Conjecure”; “neary” appears in §1.3; and the definition of f(v) just before E_abcd says vab vcd − vad vcd and should say vab vcd − vad vcb.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"I concur with the positive assessment of the paper. The main algebraic proof appears sound, and the remaining issues are local presentation and typographical problems rather than defects in the central derivation. The most important fix is the n3 n4 correction in Corollary 7.2, since that result is part of the advertised tensor-decomposition improvements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper doubles the proven success regime of the JLV first-level Nullstellensatz algorithm for finding planted rank-1 matrices: from R ≤ (1-o(1))mn/4 to R ≤ (1-o(1))mn/2, and proves failure (of the key intersection identity) when R ≥ (1+o(1))mn/√2. The main theorem is Theorem 2.5, and the proof is genuinely different from JLV's: a concrete block-upper-triangular submatrix of the symbolic matrix M, with each 1×1 or 2×2 diagonal block shown to have non-vanishing determinant. That argument is the heart of the paper and it checks out. The negative result is a clean dimension count. The paper is honest about what it proves: the algorithmic conclusions depend on the JLV extraction proposition (2.3), which is imported; the tensor-decomposition corollaries are straightforward applications. I agree with the reader: no load-bearing flaw. The minor issues are all minor: the unstated linear independence of the E_abcd tensors in Theorem 2.7 (true but should be one sentence); a likely typo in Corollary 7.2's flattening bound (should be n3*n4, not n2*n3); and the usual caveat that \"failure\" in Theorem 2.7 is failure of (Goal), not a formal statement that every recovery method fails—though the numerical evidence supports the conjectured sharp threshold. The finite-field certificates (3703 exact cases, p=997) and the floating-point experiments are real credit; they both support Conjecture 6.1 and demonstrate that the JLV algorithm's actual behavior tracks the proven bound. One point of caution: the conjecture's exact form (5) has no dependence on s to first order, and the paper's evidence for that is the certificates; that is a computational conjecture, not a fitted prediction, so it is fine. This is a within-subfield advance, not a field-changing one, but it is a solid, well-written paper. Who is it for: people working on algebraic algorithms for tensor decomposition, sum-of-squares/Nullstellensatz hierarchies, and the JLV line of work. Deserves a serious referee. I would accept it for review and expect it to be accepted after minor revisions.","headline":"A clean, self-contained improvement of the JLV threshold from mn/4 to mn/2, with a matching upper-bound conjecture and strong computational evidence; worth serious refereeing.","tokens_in":30034,"tokens_out":1166,"would_cite":true,"duration_ms":10995,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves the JLV algorithm's central identity holds for generic planted subspaces up to $R \\le \\frac12(m-1)(n-2)$, doubling the threshold, and that the identity fails once $R>mn/\\sqrt{2}+1$, pinning the plausible ceiling near…","keywords":["rank-1 matrix recovery","planted subspace","JLV algorithm","Nullstellensatz hierarchy","tensor decomposition","generic identifiability","threshold","symmetric square"],"falsifier":"Choose $m=n=6$, $s=0$, $R=10$, exactly the claimed threshold $R=\\frac{1}{2}(5)(4)$. For a random integer-valued subspace, compute the rank of the matrix $M$ over $\\mathbb{Q}$ or a large finite field: Theorem 2.5 predicts full column rank for every generic instance, so a single instance with rank below the column count refutes it. Equivalently, verify symbolically that some maximal minor of $M$ is a nonzero polynomial.","tokens_in":29069,"feed_emoji":"🧮","tokens_out":16259,"duration_ms":122872,"temperature":0.7,"pith_summary":"This paper asks how large a random matrix subspace can be before a polynomial-time algorithm can no longer find planted rank-1 matrices inside it. For the JLV algorithm, based on the first level of the Nullstellensatz hierarchy, the previous guarantee was $R \\le (1-o(1))mn/4$. The paper proves the algorithm's central identity holds up to $R \\le \\frac{1}{2}(m-1)(n-2)$, roughly doubling the guarantee, and proves that the identity must fail when $R > mn/\\sqrt{2}+1$. Numerical experiments suggest the true boundary is $R = (1+o(1))mn/\\sqrt{2}$. The proven bound already gives order-4 tensor decompositions with roughly twice as many components as before, and the conjectured boundary would make the threshold exactly $mn/\\sqrt{2}$.","feed_headline":"Rank-1 matrix recovery threshold doubled to mn/2","feed_subtitle":"The JLV algorithm now provably succeeds at twice the previous subspace dimension, with failure proven past mn/√2.","key_machinery":"The machinery is the symbolic matrix $M$ whose rows are indexed by the $2\\times2$-minor constraints $(a,b,c,d)$ and whose columns are indexed by pairs $(i,j)\\in\\Omega=\\{i<j\\}\\cup\\{i=j>s\\}$, with entries $M_{abcd,ij}=\\langle v_i\\vee v_j, E_{abcd}\\rangle$; full column rank of $M$ is equivalent to the identity (Goal). The proof constructs a square submatrix $M''$ with the help of a combinatorial injection $\\varphi:[R]\\to[m-1]\\times[k]$ (where $2k+1\\le n$) and by zeroing many variables, then shows $M''$ is block upper triangular with $1\\times1$ and $2\\times2$ diagonal blocks whose determinants are explicit polynomials with distinct monomials; a Zero Lemma forces every off-diagonal block to vanish. That block structure converts a high-dimensional genericity statement into a finite check on polynomial determinants.","core_discovery":"The central claim is the identity $S_2(\\mathcal{U}) \\cap \\mathrm{span}\\{E_{abcd}\\}^{\\perp} = \\mathrm{span}\\{(v_1)^{\\otimes 2},\\dots,(v_s)^{\\otimes 2}\\}$ for generically chosen planted subspaces: intersecting the symmetric square of the given subspace with the orthocomplement of the $2\\times2$ minor constraints leaves exactly the squared planted matrices. Theorem 2.5 establishes this identity whenever $R \\le \\frac{1}{2}(m-1)(n-2)$, and Theorem 2.7 shows it fails when $\\binom{m}{2}\\binom{n}{2} < \\binom{R+1}{2}-s$, in particular when $R>mn/\\sqrt{2}+1$. Because the left-hand side is computable from an arbitrary basis of $\\mathcal{U}$, the positive identity is what lets the JLV algorithm output the planted matrices (after an extraction step), and the negative result shows the first Nullstellensatz level cannot be pushed beyond about $1/\\sqrt{2}$ of the ambient dimension.","pith_inferences":["The block-triangular witness construction suggests that a deterministic family of subspaces achieving full column rank at the conjectured threshold should exist for every $m,n$, which would turn the computer-verified cases into a general proof.","If Conjecture 6.1 is true, the first level of the Nullstellensatz hierarchy is exactly as strong as its dimension count allows: the obstruction is purely linear-algebraic (rows versus columns of $M$) and no degree-2 method can do better.","The observed failure mode just above the threshold, with spurious kernel vectors of dimension exactly $\\binom{R+1}{2}-\\binom{m}{2}\\binom{n}{2}$, suggests the breakdown is abrupt rather than gradual, so a smoothed or noise-robust version of the JLV analysis would need a different mechanism.","The symmetric analogue, if Conjecture 6.10 holds, would raise the symmetric order-4 decomposition bound from $\\frac{1}{6}n(n-1)$ to $\\sim n^2/\\sqrt{6}$, a larger relative gain than the nonsymmetric factor of two; the paper's proofs for $m\\le 14$ (all $s$) and $m\\le 21$ ($s\\in\\{0,R\\}$) are consistent with that degree count."],"forward_implications":["For any $0\\le s\\le R$ with $R\\le \\frac{1}{2}(m-1)(n-2)$, the JLV algorithm recovers all $s$ planted rank-1 matrices from an arbitrary basis of $\\mathcal{U}$, up to permutation and scalar multiple (Corollary 2.6).","For $R> mn/\\sqrt{2}+1$, the identity (Goal) fails on generic inputs, so the degree-2 Nullstellensatz analysis of the algorithm cannot certify recovery or rank-1-freeness beyond that point (Theorem 2.7).","Generic order-4 $n\\times n\\times n\\times n$ tensors decompose in polynomial time up to rank $R\\le \\frac{1}{2}(n-2)^2$, roughly twice the previous $R\\le \\frac{1}{4}(n-1)^2$ (Corollary 7.2).","Generic unbalanced order-3 tensors of shape $n_1\\times n_2\\times n_3$ with $n_3\\ge n_1n_2/2$ decompose up to $R\\le \\frac{1}{2}(n_1-1)(n_2-2)$ (Corollary 7.1).","If Conjecture 6.1 holds, the threshold is exactly the dimension-count boundary $R\\sim mn/\\sqrt{2}$, and the tensor-decomposition bounds become $R\\le \\min\\{R_{\\max}(n_1,n_2), n_3n_4\\}$."],"supporting_citations":[{"why":"Defines the algorithm and supplies Proposition 2.3 (extraction by simultaneous diagonalization) and Proposition 2.4 (s=0 certificate), which turn the identity (Goal) into the recovery guarantee; also gives the previous R ≤ (m−1)(n−1)/4 bound this paper improves.","marker":"[JLV23]"},{"why":"Gives the previously known s=0 threshold c ≥ 1−1/√2 and proves Conjecture 6.1 in the special case min{m,n}=2, the anchor case for the conjecture.","marker":"[DJL24]"},{"why":"Supplies the identifiability threshold R = (m−1)(n−1) and the statement that higher Nullstellensatz levels recover planted matrices, framing the gap this paper closes for the first level.","marker":"[FOV99]"},{"why":"Provides the fact that subspaces of dimension at least (m−1)(n−1)+2 contain infinitely many rank-1 matrices, justifying the regime where the algorithm is expected to fail.","marker":"[Har92]"},{"why":"FOOBI algorithm's claimed order-4 decomposition bound R ≤ n(n+1)/2, whose proof was corrected downward by JLV23 and whose first-order claim is recovered by this paper's improvement.","marker":"[DLCC07]"},{"why":"Uses the JLV algorithm as a subroutine in overcomplete tensor decomposition, showing where the improved threshold can matter algorithmically.","marker":"[KMW24]"}],"fun_headline_variants":["Rank-1 subspace search threshold doubled to mn/2","Recovery threshold doubled and failure proven at √2","Planted rank-1 matrices found at twice the subspace","Subspace dimension for rank-1 recovery doubled, limit proven"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's own positive theorem is the algebraic identity (Goal); the headline claim that the JLV algorithm 'succeeds' additionally assumes the cited extraction step from the earlier JLV paper — that from the span of the squared planted matrices the vectors are recoverable by simultaneous diagonalization — and the negative result shows only that the identity (Goal) fails, not that no algorithm could recover the planted matrices.","fun_headline_variants_meta":{"raw":{"variants":["Rank-1 subspace search threshold doubled to mn/2","Recovery threshold doubled and failure proven at √2","Planted rank-1 matrices found at twice the subspace","Subspace dimension for rank-1 recovery doubled, limit proven"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001485,"raw_usage":{"total_tokens":5975,"prompt_tokens":966,"completion_tokens":5009,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":4941}},"tokens_in":582,"tokens_out":5009,"duration_ms":33837,"temperature":1.0,"reasoning_tokens":4941,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:29:15.939916+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose $m=n=6$, $s=0$, $R=10$, exactly the claimed threshold $R=\\frac{1}{2}(5)(4)$. For a random integer-valued subspace, compute the rank of the matrix $M$ over $\\mathbb{Q}$ or a large finite field: Theorem 2.5 predicts full column rank for every generic instance, so a single instance with rank below the column count refutes it. Equivalently, verify symbolically that some maximal minor of $M$ is a nonzero polynomial.","supporting_citations":[],"review_version":1}