{"id":"41342ba9-d6f2-4b85-8f03-65eb150fa37f","arxiv_id":"2511.17236","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The expected dimension of the star product of two uniformly random linear codes asymptotically equals its maximum min{k1k2, n}.","lead":"This paper computes the expected dimension of the coordinate-wise (star) product of two random linear codes, showing it asymptotically reaches its maximum size both as the alphabet grows and, under a growth condition, as the code dimensions grow. The result calibrates what random codes can and cannot do in private information retrieval, secure distributed matrix multiplication, and code-based cryptography.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Cor 5.12's o(1) gap is not supported by the proved E|ker|→2; the n=m regime needs a concentration argument, and Theorem 5.11's puncturing step is invalid.","rationale":"I read the paper's central claim as having two parts: the q→∞ asymptotic (Corollary 4.2) and the dimension-asymptotic expected-dimension result (Corollary 5.12). The q→∞ part is well supported by the explicit kernel expectation and Markov-inequality argument. The dimension-asymptotic part is not. The reader correctly identified the puncturing argument in Theorem 5.11 as broken: the embedded dual vector only gives dim(extended)≤m+t−1, which is vacuous for full dimension m. I agree with that. However, I find an even more load-bearing issue in the n=m case: Theorem 5.7's E[|ker|]→2 is only a first-moment statement, and Corollary 5.10's Markov tail bounds yield an O(1) gap in expectation, not the o(1) claimed in Corollary 5.12. The authors appear to conflate convergence of the expected kernel size with convergence of the expected kernel dimension. The analogy to uniform random matrices—where E[|ker|]→2 but E[nullity] is bounded below by a positive constant—shows that an additional concentration argument is essential and is not supplied. This is why my agreement with the reader is only partial: the reader's identified flaw is real, but the proof gap is broader and affects the basic n=k1k2 regime as well. Since the underlying statement may still be recoverable with further estimates, and the q-asymptotic results are solid, I do not recommend changing the CONDITIONAL verdict, only strengthening the required conditions: either prove the missing concentration or restrict Corollary 5.12 to regimes where n(t)−k1(t)k2(t)→∞ or q is large.","tokens_in":26073,"tokens_out":39968,"duration_ms":360165,"concrete_test":"Monte Carlo (or exact enumeration for small parameters) with q=2, k1=k2=t, n=t^2 for t=4,5,6: sample systematic generator matrices, compute dim(C1⋆C2), and estimate E[t^2−dim]. If the gap does not tend to 0 as t grows but stabilizes at a positive constant (e.g., near the random-matrix prediction ≈1−∏_{i≥1}(1−2^{-i}) for the full-rank probability), then Corollary 5.12 is false in the n=m regime. If the gap does decay to 0, the concern reduces to a missing proof, and one should then also test the analogous puncturing implication in Theorem 5.11 by enumerating q=2,k1=k2=2,n=3 with extension length m+t to see whether dim(C1⋆C2)=3 yet the extended star product has dimension <4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main gap is that Corollary 5.12's E[dim(C1⋆C2)] = min{k1k2,n}+o(1) does not follow from the estimates actually proved. In the central regime n(t)=k1(t)k2(t)=m, Theorem 5.7 only gives E[|kerψ|]→2. Since dim(C1⋆C2)=m−log_q|kerψ|, this gives, via Corollary 5.10, the tail bound P(|kerψ|≥q^{ℓ+1})≤(2+ε)q^{-(ℓ+1)}, which yields only E[m−dim]≤(2+ε)/(q−1)=O(1), not o(1). Convergence of E[q^d] to 2 does not imply convergence of E[d] to 0. For a uniformly random m×m matrix the same first-moment statistic holds: E[|ker|]→2, yet P(rank=m)→∏_{i≥1}(1−q^{-i})<1, so E[dim]=m−O(1). The systematic rank-one matrices used here share the key first-moment property—each nonzero bilinear form kills a random coordinate with probability ≈1/q—and no second-moment or concentration argument is supplied. Thus the n=m case of Corollary 5.12 is unproven and may be false. Separately, Theorem 5.11's attempt to handle n<m is invalid: from dim(C1⋆C2)<n one gets a nonzero vector in the extended dual, which only gives dim(extended star product)≤m+t−1, a bound that does not exclude full dimension m; hence P(M)≥P(N) is unjustified. Both gaps affect the same headline dimension-asymptotic claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the expected dimension of the star product C1⋆C2 of two independent uniformly random linear codes of dimensions k1 and k2 in F_q^n. Using the correspondence between star products and evaluations of bilinear forms, the authors obtain an exact expression for E|ker ψ| (Theorem 3.9), deduce a Jensen lower bound on E[dim C1⋆C2] (Corollary 3.11), and show that as q→∞ the star product has the maximal possible dimension min{k1k2,n} with probability tending to 1 (Corollary 4.2). They then address the regime in which k1,k2 grow with t under an 'admissibility' condition, claiming in Theorem 5.7 that E|ker ψ|→2 and in Theorems 5.9/5.11 and Corollary 5.12 that E[dim C1⋆C2]=min{k1k2,n}+o(1). The final section discusses applications to PIR, SDMM, CSS-T codes, and cryptanalysis.","tokens_in":26382,"tokens_out":12583,"duration_ms":105415,"significance":"If the dimension-asymptotic results were correct, the paper would give a clean two-parameter extension of the square-of-random-code analysis of Cascudo et al. [18]. The exact enumeration in Theorem 3.9 is parameter-free, the lower bound in Corollary 3.11 is checked against Monte Carlo estimates in Table 1, and the q-asymptotic Corollary 4.2 is a solid, self-contained contribution. The manuscript is honest about the technical nature of its admissibility condition and about the overlap with [26]. However, the proofs supporting the dimension-growth claim contain serious gaps, especially in Theorem 5.11 and in the passage from Theorem 5.7 to Corollary 5.12, so the paper's headline dimension-asymptotic result is currently not established. The q-asymptotic part alone would still be a useful contribution.","major_comments":[{"comment":"The step 'M implies N' is not proved and is in fact unsupported. Let m=k1k2 and let t be as in the proof. The assumed failure dim(C1⋆C2)<n yields a nonzero v∈(C1⋆C2)⊥; embedding it as ṽ=(v,0,...,0) shows ṽ∈(C̃1⋆C̃2)⊥. But this only implies dim(C̃1⋆C̃2) ≤ m+t−1, which is vacuous because C̃1⋆C̃2 is spanned by m products and hence already has dimension at most m. It does not imply dim(C̃1⋆C̃2)<m, so M^c does not imply N^c. Consequently P(M)≥P(N) does not follow, and the entire n(t)<m(t) case of Corollary 5.12 lacks support.","section":"Theorem 5.11"},{"comment":"In the regime n(t)=m(t)=k1(t)k2(t), Theorem 5.7 gives only E|ker ψ|=2+o(1). By Corollary 5.10, P(dim≤m−ℓ−1) ≤ (2+ε)/q^{ℓ+1}; summing over ℓ yields E[m−dim] ≤ (2+ε)/(q−1), a positive constant for fixed q, not o(1). The fact that |ker| is a power of q does not close the gap: a distribution with P(|ker|=q)=1/q and P(|ker|=1)=1−1/q has expectation 2 and positive expected deficit. A second-moment or concentration argument is required. The same obstruction applies whenever n(t)−m(t) is bounded, since Theorem 5.9 then gives only a constant lower bound. Thus the claimed o(1) in Corollary 5.12 is unproven.","section":"Corollary 5.12 (n=m case)"},{"comment":"The proof as printed contains a sign / law-of-total-probability error. It derives P(N) ≤ ((2q−1)/q^2)^{n−m} (E|ker ψ'|−1), which is an upper bound on the success probability, whereas the theorem claims P(N) ≥ 1−((2q−1)/q^2)^{n−m}. The union bound should be applied to the complement: P(N^c|E_j) ≤ (j−1)((2q−1)/q^2)^{n−m}, hence P(N^c) ≤ ((2q−1)/q^2)^{n−m}(E|ker ψ'|−1). Unless this is a typographical error and the text is corrected, the proof of Theorem 5.9 is invalid.","section":"Theorem 5.9"}],"minor_comments":[{"comment":"The 'uniformly random code' model samples only codes whose first k coordinates form an identity prefix, i.e., complements of a fixed coordinate subspace. The text argues robustness across models, but a formal statement or a short proof of equivalence to the uniform subspace model would strengthen the paper.","section":"Definition 3.8"},{"comment":"The multiple summations are very hard to parse. Please define all summation ranges explicitly and consider simplifying the displayed formula, e.g., by introducing auxiliary functions for the q-binomial factors.","section":"Theorem 3.9 / Eq. (3.5)"},{"comment":"The sentence 'our bound is appears to be good' is ungrammatical. Also, report the Monte Carlo standard errors and state the number of samples in the caption (currently given only in the text).","section":"Table 1 and surrounding text"},{"comment":"The conjecture lim_{t→∞} E|ker ψ| = exp((q−1)k2(t)(k1(t)−1)/q^{k1(t)})+1 has t-dependent quantities inside the claimed limit. Please clarify the intended asymptotic notation.","section":"Remark 5.8"},{"comment":"State explicitly that o(1) is as t→∞ with q fixed, and specify which additional growth conditions on n(t)−m(t) are needed for the conclusion to follow from the proved estimates.","section":"Corollary 5.12"}],"recommendation":"major_revision","confidential_remarks":"The Section 5 issues are substantive and affect the paper's main dimension-asymptotic claim. The q-asymptotic contribution (Theorem 4.1 and Corollary 4.2) appears sound and could form the basis of a revised paper, possibly with a corrected and substantially strengthened Section 5. In its current form, the manuscript should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is a mixed bag. The q→∞ half is sound: Theorem 3.9 gives an explicit kernel-expectation formula, Corollary 3.11's lower bound matches the Monte Carlo values, and Corollary 4.2's Markov-inequality argument proving full dimension with probability tending to 1 is correct. The dimension-growth half is not. Corollary 5.12's o(1) claim is unsupported, and Theorem 5.11's puncturing argument is wrong.\n\nWhat's genuinely new: the extension from squares of one random code to star products of two codes of possibly different dimensions, the kernel formula, and the field-size asymptotic. The Monte Carlo table is a useful sanity check, not a fitted parameter.\n\nThe soft spot is Section 5. Theorem 5.11 tries to prove P(M) ≥ P(N) by showing N ⇒ M. The contrapositive runs: if dim(C1⋆C2) < n, then a nonzero vector in the punctured dual embeds as a nonzero vector in the extended dual. But that only gives dim(extended dual) ≥ 1, which is compatible with dim(extended star) = m: the extended ambient space has m+t coordinates, so the orthogonal complement can have dimension t while the star product is full. The bound dim(extended star) ≤ m+t−1 is vacuous because the star product is already spanned by m products. So ¬M does not imply ¬N, and the claimed P(M) ≥ P(N) does not follow.\n\nThere is a second, independent gap. Even in the central regime n = m, Corollary 5.12 does not follow from Theorem 5.7. E|ker|→2 only gives, via Corollary 5.10, P(|ker| ≥ q^{ℓ+1}) ≤ (2+ε)q^{-(ℓ+1)}, which yields E[log_q|ker|] = O(1), not o(1). First-moment convergence does not give concentration of the logarithm: a uniform random m×m matrix has E|ker|→2 but fails to be full rank with probability bounded away from 0. The authors need a second-moment or concentration argument, or they should restrict the claim to regimes where n(t)−k1k2 grows.\n\nThe admissibility condition in Definition 5.6 is honestly flagged as a technical limitation; that is not the issue. The overlap with [26] is acknowledged in Remark 5.13 and is handled fairly; the q→∞ result stands independent.\n\nWho this is for: anyone working with random linear codes in PIR, SDMM, or code-based crypto will want the q-asymptotic result and the kernel formula. The Section 5 claims are currently not trustworthy, so the paper needs a major revision before those asymptotic-in-dimension statements can be used. It deserves a serious referee: the q-half is publishable, and the gap in the dimension-half is specific and likely repairable with a second-moment argument or a narrower statement.","headline":"Solid q→∞ half with a clean kernel formula; Section 5's dimension-growth claim doesn't follow — the puncturing step is invalid and Corollary 5.12 needs concentration beyond E|ker|→2.","tokens_in":27001,"tokens_out":5505,"would_cite":true,"duration_ms":41871,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B65","15A69"],"pacs":[],"model":"deepseek-v4-flash","headline":"The star product of two uniformly random linear codes almost always attains the maximum possible dimension min{k1k2, n}, asymptotically as the field size grows, and under an admissibility condition also as the code dimensions grow.","keywords":["star product","Schur product","Hadamard product","random linear codes","bilinear forms","expected dimension","asymptotic maximality","code-based cryptography"],"falsifier":"Fix q=2, k1=k2=3, n=7 (so k1k2=9 > n). If Theorem 5.11 were true, P(dim(C1⋆C2)=7) would be at least 1−((2q−1)/q^2)^t = 1−(3/4)^t for large t, tending to 1. A direct computation over F_2^7, either by enumeration or by sampling many random systematic pairs and computing the star-product dimension, could check whether the probability approaches 1; a limiting value strictly below 1 would refute the claimed implication. More directly, verify whether an extended pair with appended random columns can have a full 9-dimensional star product while its 7-coordinate punctured star product has dimension 6;","tokens_in":25815,"feed_emoji":"🎲","tokens_out":11251,"duration_ms":83710,"temperature":0.7,"pith_summary":"Two random linear codes, when multiplied coordinatewise, produce a third code whose dimension is usually the largest possible: the smaller of the product of the two dimensions and the ambient length. The paper proves this asymptotic maximality in two regimes: as the field size q tends to infinity, the star-product dimension equals min{k1k2, n} with probability tending to 1; and as the code dimensions grow, the same conclusion holds provided the second dimension does not grow too quickly relative to the first. The proof converts the star product into the image of a linear map that evaluates bilinear forms on random column pairs, reducing the question to counting zero-diagonal matrices of fixed rank. The result matters because star-product dimension controls the efficiency of private information retrieval and secure distributed matrix multiplication, and because deviations from maximal dimension are exactly what code-based distinguishers look for.","feed_headline":"Random codes almost surely maximize star-product dimension","feed_subtitle":"The componentwise product of two random codes reaches min{k1k2,n} almost surely as q grows.","key_machinery":"The evaluation map ψ_{G1,G2} from the space of bilinear forms on F_q^{k1} × F_q^{k2} to F_q^n, which sends a form to its values on the column pairs of systematic generator matrices; its image is exactly C1⋆C2, so |ker ψ| determines the dimension defect. Counting |ker ψ| means counting k1×k2 matrices with zero diagonal of each rank r, via the sets S_r^{k1,k2} and q-binomial identities. Jensen's inequality converts the exact expectation of log_q |ker ψ| into a lower bound on the expected dimension; Markov's inequality converts the bounded kernel expectation into high probability of full dimension.","core_discovery":"The paper's central claim is that for independent uniformly random linear codes C1,C2 ≤ F_q^n of dimensions k1,k2, the expected star-product dimension is asymptotically maximal: lim_{q→∞} P(dim(C1⋆C2)=min{k1k2,n})=1 (Corollary 4.2), and under an admissibility condition on monotone dimension functions, E[dim(C1⋆C2)] = min{k1(t)k2(t),n(t)}+o(1) (Corollary 5.12). The identification of C1⋆C2 with the image of the evaluation map ψ on bilinear forms gives dim(C1⋆C2) = k1k2 − log_q |ker ψ|, and the expected kernel size is computed exactly by enumerating zero-diagonal k1×k2 matrices of each rank. From this expression, lower bounds on the expected dimension, and concentration through Markov's inequal","pith_inferences":["The proof of the n(t)<k1k2 case (Corollary 5.12 via Theorem 5.11) rests on the unproven implication that a full-dimensional punctured star product forces a full-dimensional extended star product; the provided argument only embeds the dual vector, which yields a vacuous bound. If this implication cannot be repaired, the dimension-growth theorem remains established only for n(t) ≥ k1k2.","The same bilinear-form counting strategy should extend to star products of three or more random codes, giving analogous maximal dimension results for iterated Schur products; the paper only treats pairs.","In code-based cryptography, the near-maximality of random star products gives a clean quantitative baseline: a candidate code pair whose star-product dimension falls noticeably below min{k1k2,n} is statistically distinguishable from random, which could sharpen existing square-based distinguishers.","The abstract promises explicit asymptotic upper bounds on the variance of the star-product dimension, but the included text does not appear to contain that analysis; pinning down the variance would let practitioners convert the Markov-based concentration into tail bounds with explicit constants."],"forward_implications":["As q→∞, for any fixed n,k1,k2, the star product of two uniformly random codes fills F_q^n when k1k2 ≥ n, and otherwise has dimension exactly k1k2, with probability approaching 1.","Under the admissibility condition (k2 not growing too fast relative to k1), the same maximality holds as the code dimensions grow: E[dim(C1⋆C2)] = min{k1k2,n} + o(1).","The explicit lower bound of Corollary 3.11 gives a certified estimate for all finite parameters, not just asymptotics, and matches Monte Carlo simulations even at small q and n.","For PIR/SDMM, random code pairs yield an upper bound on the PIR rate of 1−min{k1k2,n}/n and a lower bound on the SDMM recovery threshold of min{k1k2,N}, so random codes cannot beat structured MDS constructions in these metrics.","Random binary codes of sufficiently large dimension give no high-distance binary CSS-T quantum codes, because their star-square fills the ambient space and leaves no room for the T-gate code C2."],"fun_headline_variants":["Star product of random codes reaches max dimension as q grows","Random linear codes: star product dimension is asymptotically largest","Expected star-product dimension of random codes hits its ceiling","Star product dimension of random codes: maximal almost surely"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that in the regime where the ambient length is smaller than the product of the code dimensions, a full-dimensional star product of the punctured codes guarantees a full-dimensional star product after randomly extending the codes; the proof of Theorem 5.11 asserts this but only establishes a bound that is automatically true, so the n(t) < k1k2 part of the growth result is unsupported as written.","fun_headline_variants_meta":{"raw":{"variants":["Star product of random codes reaches max dimension as q grows","Random linear codes: star product dimension is asymptotically largest","Expected star-product dimension of random codes hits its ceiling","Star product dimension of random codes: maximal almost surely"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000636,"raw_usage":{"total_tokens":2747,"prompt_tokens":698,"completion_tokens":2049,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":442,"completion_tokens_details":{"reasoning_tokens":1984}},"tokens_in":442,"tokens_out":2049,"duration_ms":14255,"temperature":1.0,"reasoning_tokens":1984,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:58:40.393261+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix q=2, k1=k2=3, n=7 (so k1k2=9 > n). If Theorem 5.11 were true, P(dim(C1⋆C2)=7) would be at least 1−((2q−1)/q^2)^t = 1−(3/4)^t for large t, tending to 1. A direct computation over F_2^7, either by enumeration or by sampling many random systematic pairs and computing the star-product dimension, could check whether the probability approaches 1; a limiting value strictly below 1 would refute the claimed implication. More directly, verify whether an extended pair with appended random columns can have a full 9-dimensional star product while its 7-coordinate punctured star product has dimension 6;","supporting_citations":[],"review_version":1}