{"id":"b8cbc726-558b-4853-a95e-2035f0951680","arxiv_id":"2505.05935","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random linear codes over small fields achieve list-recovery list size O(1/ε) at rate ε below capacity, improving the Zyablov-Pinsker q^{O(ℓ/ε)} bound for erasures over prime fields and for errors over all fields.","lead":"This paper proves that random linear codes over small fields can be list-recovered from errors and erasures with output list size only O(1/ε) when the code rate is ε below capacity, improving the classic Zyablov-Pinsker bound. It shows linearity costs little in these regimes for constant alphabet size, a question of active interest in coding theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.5 is stated for all ℓ≤q−1 but its δ-mixing input, Corollary 3.3, covers only 2≤ℓ≤q−1; singleton subsets are not δ-mixing for any δ>0, so the erasures result is unproved for ℓ=1.","rationale":"The reader's weakest-assumption identification is accurate and it is the cleanest load-bearing gap: Corollary 3.3 genuinely excludes ℓ=1, and Theorem 3.5 genuinely includes ℓ=1 in its statement. This is not a manufactured edge case, because ℓ=1 is the standard erasure list-decoding regime and the abstract's first bullet ('input list size ℓ') makes no exclusion. The gap does not threaten the core O(1/ε) dependence for fixed ℓ≥2, q, ρ, since for those parameters Corollary 3.3 supplies a positive δ. The reader also noted a second issue in Corollary 4.6, where the displayed combination of two exponential bounds into a single q^{-δn} bound is not justified by the preceding inequalities; that issue is real and should be fixed, but it is less cleanly load-bearing because a valid δ can be obtained by taking δ=min(A,B)/2 with the two exponents from Equations (23)–(24), so the qualitative errors result likely survives with a modified constant. Similarly, Lemma 3.4's statement for arbitrary b is false (e.g., q=5, T={0,1}^n, b=n gives constant probability that the span is all of F_q^n), but in the theorem applications b is at most O(ℓ/ε), which is constant for fixed ε, so choosing n sufficiently large restores the argument; this should be stated explicitly. Therefore the verdict remains CONDITIONAL: the ℓ=1 gap requires either a separate proof or a restriction in the theorem statement, while the main asymptotic contribution for ℓ≥2 is credible.","tokens_in":26697,"tokens_out":38041,"duration_ms":390516,"concrete_test":"Verify Definition 2.17 with T={0}⊆F_q, q prime, α=β=1, γ=0: the event αX+βX′∈T+γ always holds, so sup over shifts equals 1 and T is not δ-mixing for any δ>0. Then check whether Theorem 3.5's ℓ=1 case can be recovered directly: for a random linear code of rate R=1−α−ε, show that for every set S of (1−α)n fixed coordinates the projection C→F_q^S is injective with high probability, giving list size 1, or alternatively exclude ℓ=1 from the theorem statement and adjust the abstract's 'input list size ℓ' accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The erasures theorem (Theorem 3.5) claims the list-size bound L=O(1/ε) for every integer 1≤ℓ≤q−1. Its proof, however, obtains δ-mixing of the relevant sets exclusively from Corollary 3.3, whose first bullet begins 'If 2≤ℓ≤2q/3' and whose second bullet handles the remaining range of ℓ but still with ℓ≥2. For ℓ=1 no δ-mixing is possible: if T={0}⊆F_q and X,X′∼T, then for nonzero α=β=1 and shift γ=0, Pr[αX+βX′∈T+γ]=Pr[0∈{0}]=1, so Definition 2.17 cannot hold for any δ>0. Thus the proof of Theorem 3.5 has no mechanism to cover ℓ=1, despite the theorem statement. The ℓ=1 case is not merely cosmetic: it corresponds to ordinary list decoding from erasures, a standard and practically relevant setting. The claim for ℓ=1 may well be true and provable by a separate linear-algebra argument, but that argument is not in the paper. A secondary, related gap is that the same theorem's proof of Lemma 3.4 is stated for all b∈N, while the union-bound step requires n to be large relative to b; this does not affect the asymptotic ε→0 claim once n is chosen sufficiently large, but it should be stated precisely in a revision.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies list-recovery of random linear codes over small fields at rates epsilon below capacity, and proves upper bounds of the form L = O(1/epsilon) on the output list size. For list-recovery from erasures over prime fields, Theorem 3.5 claims L <= C/epsilon for every 1 <= l <= q-1, improving the Zyablov-Pinsker q^{O(l/epsilon)} bound. For list-recovery from errors over arbitrary fields, Theorem 4.7 claims a similar L <= C/epsilon bound. The technical approach adapts the Guruswami-Hastad-Kopparty mixing method: it establishes a weak 'delta-mixing' property for the relevant sets (combinatorial rectangles for erasures, list-recovery balls for errors) and then applies an increasing-chain argument to bound the intersection of a random linear code with those sets. The paper also provides explicit constants and compares its results with lower bounds for low-characteristic fields and large alphabets.","tokens_in":27009,"tokens_out":15209,"duration_ms":160966,"significance":"If the stated results hold, they settle the dependence of the output list size on the gap-to-capacity epsilon for two natural regimes of list-recovery, showing that random linear codes achieve the Elias-type bound L = O(1/epsilon) for constant alphabet size. This is a meaningful step beyond the classical Zyablov-Pinsker bound, and the erasures result over prime fields is a clean application of Lev's theorem on additive structure. The paper is largely self-contained, gives explicit constants, and correctly distinguishes the regimes where linearity is or is not costly. However, the proof of Theorem 3.5 does not cover the case l=1, which is explicitly included in the statement, and the proof of Corollary 4.6 claims a mixing rate that is not justified by the derived exponential bounds. Both issues are local and appear repairable, but they currently affect the validity of two central stated results.","major_comments":[{"comment":"Theorem 3.5 is stated for every integer 1 <= l <= q-1, but its proof relies on Corollary 3.3, which establishes delta-mixing only for subsets of size at least 2. For l=1, a singleton T={0} subset of F_q is not delta-mixing for any delta>0: with alpha=beta=1 and gamma=0, Pr[alpha X + beta X' in T+gamma] = 1, contradicting Definition 2.17. Since the proof of Theorem 3.5 sets delta >= (1-alpha) delta_0 using Corollary 3.3, it has no mechanism to handle l=1. This is load-bearing because the abstract and introduction explicitly claim the erasures result for all l, and l=1 corresponds to ordinary list-decoding from erasures. The theorem should either be restricted to l >= 2 or supplemented with a separate argument for l=1.","section":"Theorem 3.5 / §3.2"},{"comment":"The stated value of delta in Corollary 4.6 is not justified by the preceding inequalities. Equation (23) proves a bound of the form exp_q(-rho^4 (1-l/q-rho)^2/(16 log q) * n), with no factor of log_q((q-l)(1-rho)/(rho l)). The proof's concluding sentence inserts this log_q factor into the exponent of the final bound, effectively multiplying the decay rate from (23) by a factor that can be large when rho is small. Since the sum of the two exponential bounds decays at the minimum of the two rates, the claimed delta exceeds the true rate supplied by (23). The proof should either drop the log_q factor from delta or strengthen the bound on (21). This is load-bearing for the explicit constant in Theorem 4.7, although the asymptotic L = O(1/epsilon) claim is very likely repairable by taking the smaller delta.","section":"Corollary 4.6 / §4.1"}],"minor_comments":[{"comment":"The hypothesis 'n >= q^{8a/delta}' does not by itself suffice for the proof step where b(A+1) <= (delta d - 1)/2 n; the proof silently requires n to be large relative to b. Since in the application b is at most L+1 and n is chosen large, this does not affect the asymptotic conclusion, but the condition should be stated precisely.","section":"Lemma 3.4 / §3.2"},{"comment":"The bound on the number of input configurations replaces (e q/l)^{(1-alpha) n l} by q^{(1-alpha) n l}. This is not valid for l=2, since e q/2 > q. The error can be absorbed into the constants by increasing a and c, but the displayed inequality is false as written.","section":"Theorem 3.5 proof"},{"comment":"There is a small notational confusion in the proof: the scalars are called alpha_1, alpha_2 but the sets are written alpha_i T_i. The intended meaning is that the first sample is scaled by alpha_1 and the second by alpha_2; the notation should be made consistent.","section":"Lemma 4.4 / §4.1"},{"comment":"The opening paragraph refers to 'Theorem 3.2' when invoking the erasures argument; the intended reference is Lemma 3.4 (and Theorem 3.5). This is a harmless citation slip but should be corrected.","section":"Section 4 intro"},{"comment":"Both theorems state simple largeness conditions on n (e.g., n >= L, or n >= (log q/(rho(1-l/q-rho)))^c), but their proofs use additional largeness conditions such as h_2(alpha)/log q + 2 log b*/n <= 1. These auxiliary conditions should be included in the theorem statements or shown to follow from the stated conditions.","section":"Theorems 3.5 and 4.7"},{"comment":"The introduction states the erasures result for 1 <= l <= q, while Theorem 3.5 requires l <= q-1. For l = q the capacity is zero, so the range in the introduction appears to be a typo; it should be aligned with the theorem statement.","section":"Theorem 1.2 vs Theorem 3.5"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe headline: this is the first real improvement over Zyablov–Pinsker for list-recovery over small alphabets. The authors show random linear codes with rate ε below capacity have output list size O(1/ε), both for erasures over prime fields and for errors over any field. The dependence on ℓ and q is poor, but the dependence on ε is right, and the qualitative result is new.\n\nWhat is actually good: the conceptual move is adapting the GHK11 mixing framework to list-recovery sets. The erasures side uses Lev's theorem to show worst-case subsets of prime fields mix with a constant δ, including the subtle centered-interval extremal analysis. The errors side has a genuinely new convolution argument (Lemma 4.2) that bounds the probability a coordinate sum lands in the list; the observation that this works iff ρ<1−ℓ/q is clean. The structure is honest, with explicit constants and no fitted parameters. I believe the main theorems are correct for fixed ℓ≥2.\n\nSoft spots, in order of severity. First, Corollary 4.6 states a decay rate δ that does not follow from the proof. The proof combines two exponential bounds with exponents roughly A n and B n, then claims a bound with δ = R·B, where R = log_q((q−ℓ)(1−ρ)/(ρℓ)) > 1. Since the second term alone is q^{−Bn}, a rate larger than B is impossible. The fix is routine: take δ to be a constant fraction of min(A,B). This is a real flaw in a stated constant but not in the asymptotic claim. Second, Theorem 3.5 is stated for all 1≤ℓ≤q−1, but its proof uses Corollary 3.3, which only gives δ>0 for ℓ≥2. A singleton is not δ-mixing for any δ>0, so the ℓ=1 case is unproved. It is probably true and likely follows from a separate linear-algebra argument, but that argument is not here. Third, Lemma 3.4 claims a bound for every b, but the union-bound step needs n large relative to b; the statement should include that condition. This is minor in the regime ε→0 with n large.\n\nWho this is for: coding theorists working on list-recovery and on the price of linearity. The paper deserves referee time. I would send it out, with a request that the authors fix the Corollary 4.6 constant and either prove or explicitly exclude the ℓ=1 erasures case.","headline":"First real improvement over Zyablov–Pinsker for small-alphabet list-recovery: random linear codes get O(1/ε) list size near capacity, with two fixable gaps in stated constants and the ℓ=1 erasures case.","tokens_in":27571,"tokens_out":7392,"would_cite":true,"duration_ms":73608,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B05","11T71","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random linear codes over constant-size fields are shown to be list-recoverable with output list size only $O(1/\\varepsilon)$ when their rate is $\\varepsilon$ below capacity, improving the classical exponential bound.","keywords":["list-recovery","random linear codes","list-decoding","erasures","errors","delta-mixing","small-alphabet regime","Zyablov-Pinsker bound"],"falsifier":"Take $T=\\{0\\}\\subseteq \\mathbb{F}_q$, $\\alpha=\\beta=1$, and $\\gamma=0$. Since the two samples always equal $0$, $\\Pr[\\alpha X+\\beta X'\\in T+\\gamma]=1>q^{-\\delta}$ for every $\\delta>0$, so $T$ is not $\\delta$-mixing. Because the erasures proof's only path to list-size bounds goes through $\\delta$-mixing of the rectangles $T_1\\times\\cdots\\times T_n$, this calculation shows the proof as written does not cover $\\ell=1$, and any repair must either handle $\\ell=1$ separately or change the mixing definition.","tokens_in":26497,"feed_emoji":"📡","tokens_out":10211,"duration_ms":100559,"temperature":0.7,"pith_summary":"The paper claims that random linear codes over small fields can be list-recovered with output list size only linear in the gap to capacity, rather than exponential. For list-recovery from erasures over prime fields, a random linear code of rate $\\varepsilon$ below the erasure capacity is shown to be $(\\alpha,\\ell,C_1/\\varepsilon)$-list-recoverable; for list-recovery from errors over arbitrary prime-power fields, rate $\\varepsilon$ below the error capacity gives $(\\rho,\\ell,C_2/\\varepsilon)$-list-recoverability. The constants $C_1$ and $C_2$ depend only on the decoding radius, input list size, and alphabet size. This is the first improvement over the Zyablov–Pinsker bound $q^{O(\\ell/\\varepsilon)}$ in the small-alphabet regime, and it shows that in these regimes linearity does not force an exponential price in $1/\\varepsilon$.","feed_headline":"Near-capacity random linear codes list-recover with O(1/ε)-size lists","feed_subtitle":"First advance past the exponential Zyablov–Pinsker bound in the small-alphabet regime.","key_machinery":"The load-bearing object is the $\\delta$-mixing property: for a set $T\\subseteq \\mathbb{F}_q^n$, two independent uniform samples $X,X'$ satisfy $\\Pr[\\alpha X+\\beta X'\\in T+z]\\leq q^{-\\delta n}$ for all nonzero $\\alpha,\\beta\\in\\mathbb{F}_q$ and all shifts $z\\in\\mathbb{F}_q^n$. This is the property that random linear subspaces cannot correlate with the sets that threaten list-recovery. The paper establishes it separately for the two relevant set families: combinatorial rectangles $T_1\\times\\cdots\\times T_n$ over prime fields, using a centered-interval extremal bound for sums of subsets of $\\mathbb{F}_q$, and list-recovery balls $B_\\rho(T_1\\times\\cdots\\times T_n)$ over arbitrary fields, using a convolution identity. An increasing-chain lemma then converts a set that is $\\delta$-mixing into one that meets any random linear code of rate $\\varepsilon$ below capacity in at most $C/\\varepsilon$ points.","core_discovery":"The central discovery is that the sets a list-recovery decoder must avoid---combinatorial rectangles for erasures and puffed-up list-recovery balls for errors---are $\\delta$-mixing for a constant $\\delta>0$, and that this mixing property directly controls the output list size. For erasures over prime fields, the worst-case size-$\\ell$ subset of $\\mathbb{F}_q$ is a centered interval; two independent samples from such an interval sum back into it with probability at most $3/4+O(1/\\ell^2)$, giving $\\delta\\geq \\log_q(16/13)$ for $\\ell\\leq 2q/3$. For errors over any field, the paper proves the coordinate-wise collision probability with a list-recovery ball satisfies $\\Pr[E_i=1]\\leq (1-\\rho)^2+\\rho^2 \\ell/(q-\\ell)$, which is less than $1-\\rho$ exactly when $\\rho<1-\\ell/q$, the regime in which positive-rate list-recovery is possible. Feeding these mixing bounds into the increasing-chain argument of [GHK11] gives the list-size bound $L=C/\\varepsilon$ for both models, with explicit constants.","pith_inferences":["Because the errors-side collision calculation never uses primality of $q$, the same $O(1/\\varepsilon)$ list-size bound should extend to random linear codes over any finite field (or any group alphabet) with the same condition $\\rho<1-\\ell/q$.","The paper's coordinate-wise mixing bound is strong enough that the method plausibly yields average-radius list-recovery, a stronger guarantee the paper itself raises as a natural next step.","The constant $C_1$ in the erasures theorem inherits the crude $3/4$ bound for centered intervals; a tighter additive-combinatorics estimate would directly improve the explicit constants without changing the argument."],"forward_implications":["For any fixed alphabet size $q$, input list size $\\ell$, and decoding radius, the output list size is $O(1/\\varepsilon)$, matching the Elias-bound dependence that plain random codes achieve.","The bounds improve on the Zyablov–Pinsker bound $q^{O(\\ell/\\varepsilon)}$ whenever $q\\leq 2^{(1/\\varepsilon)^c}$ for some small universal constant $c>0$, i.e., throughout the small-alphabet regime.","Over prime fields, the erasures result is essentially optimal in its $\\varepsilon$-dependence, since a previous lower bound shows exponential list size is necessary for low-characteristic fields.","Over arbitrary fields, the errors result shows no price for linearity in the $\\varepsilon$-dependence, in contrast to the large-alphabet regime where an exponential lower bound applies."],"supporting_citations":[{"why":"Supplies the baseline $q^{O(\\ell/\\varepsilon)}$ list-size bound for random linear codes that the paper improves.","marker":"[ZP81]"},{"why":"Provides the mixing-plus-increasing-chains framework for list-decodability that the paper adapts to list-recovery.","marker":"[GHK11]"},{"why":"Gives the worst-case additive-combinatorics bound for sums of subsets of prime fields used in the erasures mixing argument.","marker":"[Lev01]"},{"why":"Shows the lower bound $\\ell^{\\Omega(1/\\varepsilon)}$ for erasures over low-characteristic fields, motivating the prime-field restriction.","marker":"[GLM+22]"},{"why":"Gives an exponential list-size lower bound for large alphabets, showing the errors regime here is genuinely different.","marker":"[LS25]"},{"why":"Provides the $(q,\\ell)$-entropy capacity formula and list-recovery ball-size estimates used in the errors argument.","marker":"[Res20]"},{"why":"Formalizes the Zyablov–Pinsker bound for list-recovery and gives the $\\mathbb{F}_2$ erasure lower bound context.","marker":"[Gur03]"},{"why":"Supplies the binomial central-probability bound used in the convolution and mixture analysis for list-recovery balls.","marker":"[WR61]"}],"fun_headline_variants":["Small-field linear codes list-recover with O(1/ε) lists","Random linear codes: O(1/ε) list-recovery for small fields","Linear codes beat Zyablov–Pinsker in small-alphabet regime","First improvement over Zyablov–Pinsker for list-recovery","O(1/ε) list-size for near-capacity random linear codes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The erasures theorem is stated for every input list size $\\ell\\leq q-1$, but its proof relies on a $\\delta$-mixing lemma established only for $2\\leq\\ell\\leq q-1$; for $\\ell=1$ a singleton input set is not $\\delta$-mixing at all, so the stated proof does not cover the case $\\ell=1$.","fun_headline_variants_meta":{"raw":{"variants":["Small-field linear codes list-recover with O(1/ε) lists","Random linear codes: O(1/ε) list-recovery for small fields","Linear codes beat Zyablov–Pinsker in small-alphabet regime","First improvement over Zyablov–Pinsker for list-recovery","O(1/ε) list-size for near-capacity random linear codes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1473,"prompt_tokens":1168,"completion_tokens":305,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":784,"completion_tokens_details":{"reasoning_tokens":202}},"tokens_in":784,"tokens_out":305,"duration_ms":3242,"temperature":1.0,"reasoning_tokens":202,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:53:38.851423+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $T=\\{0\\}\\subseteq \\mathbb{F}_q$, $\\alpha=\\beta=1$, and $\\gamma=0$. Since the two samples always equal $0$, $\\Pr[\\alpha X+\\beta X'\\in T+\\gamma]=1>q^{-\\delta}$ for every $\\delta>0$, so $T$ is not $\\delta$-mixing. Because the erasures proof's only path to list-size bounds goes through $\\delta$-mixing of the rectangles $T_1\\times\\cdots\\times T_n$, this calculation shows the proof as written does not cover $\\ell=1$, and any repair must either handle $\\ell=1$ separately or change the mixing definition.","supporting_citations":[],"review_version":1}