PaperlayerView exact revision on arXiv

Source-linked AI summary

The list size of random linear codes at capacity

Shashwat Silas

arXiv:2609.06570v1cs.ITcs.DMmath.COmath.IT

TL;DR

The list size of random linear codes near capacity was known to scale as Θ(1/ε), but for q≥3 the matching-constant upper bound was missing. This paper combines the random-code threshold framework with sparse-vector entropy bounds, determining the list size for every prime power and typically identifying it exactly.

  • Problem

    Although random linear-code list size was known to be Θ_{q,ρ}(1/ε), a matching-constant upper bound was missing for q≥3.

    Source: §1 · p. 2

  • Method

    The authors use the threshold framework to reduce list-size bounds to estimating V(q,L,ρ), with an entropy inequality for sparse random vectors and an exact analysis of a previously introduced distribution.

    Source: §1 · p. 2, §1.1 · p. 4

  • Results

    L*(C,ρ)=⌈ζ⌉ with probability 1-o(1), except when the fractional part of ζ is at most an explicit exponentially small cutoff, when L* is ⌊ζ⌋ or ⌊ζ⌋+1.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The matching-constant upper-bound result previously available only for q=2 is extended to every prime power q.

    Source: §1 · p. 2

    The arguments do not immediately extend to average-radius list decoding, because they require each codeword individually to lie within radius ρ of the center.

    Source: §8 · p. 28

Abstract

from arXiv · show

Let $C \le \mathbb{F}_q^n$ be a uniformly random $\mathbb{F}_q$-linear code of rate $1 - h_q(\rho) - \varepsilon$, and let $L^*(C,\rho)$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^* = \Theta_{q,\rho}(1/\varepsilon)$ has been known since work of Guruswami, H{\aa}stad and Kopparty and of Guruswami and Narayanan. Guruswami, Li, Mosheiff, Resch, Silas and Wootters proved that the constant in front of $1/\varepsilon$ is at least $h_q(\rho)$ for all $q$, along with an upper bound special to $q = 2$ which narrowed $L^*$ to within three consecutive integers in that case. But for $q \ge 3$ no upper bound with the correct constant was known. We determine $L^*$ for every prime power $q$. Let $\zeta := h_q(\rho)/\varepsilon$. For every sufficiently small $\varepsilon$, with probability $1-o(1)$ over the choice of $C$, $$L^*(C,\rho) = \lceil \zeta \rceil,$$ unless the fractional part of $\zeta$ is at most $q^{-\Omega_{q,\rho}(\zeta)}$, in which case $L^*(C,\rho)$ is $\lfloor \zeta \rfloor$ or $\lfloor \zeta \rfloor + 1$. By the threshold characterization of random linear codes due to Mosheiff, Resch, Ron-Zewi, Silas and Wootters, both bounds reduce to a two-sided estimate of a single quantity $V(q,L,\rho)$, where $1-V(q,L,\rho)$ is the threshold rate for $(\rho,L)$-list-decodability. We prove for all large $L$: $$h_q(\rho)(1 + 1/L) - q^{-\Omega_{q,\rho}(L)} \le V(q,L,\rho) \le h_q(\rho)(1 + 1/L).$$ The upper bound rests on a new entropy inequality for sparse random vectors under pairwise non-proportional linear constraints, proved with the Erd\H{o}s-Rado sunflower lemma. The lower bound is an exact analysis of the distribution introduced by Guruswami, Li, Mosheiff, Resch, Silas and Wootters.

1 Introduction

The paper resolves the list size of random linear codes near capacity for every prime power, typically identifying it exactly. It uses the random-linear-code threshold framework and new entropy bounds to close the remaining gap.

1 Introduction

  • Earlier work established Θ_{q,ρ}(1/ε) list size and the matching h_q(ρ) lower-bound constant; the matching-constant upper bound was known only for q=2, tightened in.The prior upper-bound result applied to the stronger average-radius notion in.Source: §1 · p. 2

1.1 Our contributions

  • The threshold framework reduces list-size determination to estimating V(q,L,ρ), which the paper determines within an exponentially small additive error.The threshold rate for (ρ,L)-list-decodability is 1−V(q,L,ρ).Source: §1 · p. 2, §1.1 · p. 3
  • With probability 1-o(1), L*(C,ρ)=⌈ζ⌉ unless the fractional part of ζ is at most an explicit exponentially small cutoff, when L* is either ⌊ζ⌋ or ⌊ζ⌋+1.Here ζ=h_q(ρ)/ε, for sufficiently small ε.Source: §1.1 · p. 3
  • For the upper bound, a sparse-vector entropy inequality uses the Erdős-Rado sunflower lemma; for q≥3, examples show its residual η cannot generally be removed.The entropy theorem gives a fixed saving when N≥1.Source: §1.1 · pp. 3–4
  • The lower bound exactly analyzes an i.i.d. ρ-sparse vector plus a uniform multiple of the all-ones vector.This is the distribution introduced in [GLM+22, Definition 4.2].Source: §1.1 · p. 4

1.2 Organization

  • The paper introduces the threshold framework and proof roadmap, reduces types to configurations, proves the upper and lower bounds on V, and collects further directions and deferred proofs.The sections also include formal theorem statements and track proof constants in the appendices.Source: §1.2 · p. 5

2 Preliminaries

These preliminaries set the entropy and sparsity measures, encode clustered codeword families as types, and connect implied distributions to random-code list-decoding thresholds.

2.1 Entropy and divergence

  • The section defines base-q entropy, q-ary and binary entropy, fixes h=hq(ρ), and records that base-q Bernoulli divergence is nonnegative and increases in its second argument above its first.Source: §2.1 · p. 5

2.2 Sparsity

  • A ρ-sparse scalar is nonzero with probability at most ρ; vectors require this coordinatewise without independence, and scalar entropy is at most hq(ρ), with equality at sparsity ρ and uniform nonzero values.Source: §2.2 · p. 6

2.3 Types

  • A type pairs spanning linear forms with a distribution on their input, representing jointly distributed distinct columns; absolute ρ-clustering means a coupled center is within ρ of each coordinate.Source: §2.3 · pp. 6–7

2.4 Implied distributions and the threshold framework

  • The threshold framework gives list-decodability below rate 1−V; implied linear images are compared by least entropy per dimension to set the threshold.Source: §2.4 · pp. 7–8

3 Overview of the proof of Theorem 1.2

The proof reduces list-size bounds to entropy estimates for configurations obtained from absolutely ρ-clustered types. A sunflower-based entropy bound controls every configuration, while a single explicit type supplies a near-matching lower bound.

Overview of the proof

  • For all sufficiently large L, every absolutely ρ-clustered type has rat bounded by h_q(ρ)(1 + 1/L), and one type comes within q^-Ω(L) of that value.This two-sided estimate is the target of the proof overview.Source: §3 · p. 9

Reduction to configurations

  • The reduction turns each type into a configuration: a ρ-sparse random vector whose linear-form evaluations are also ρ-sparse, with pairwise non-proportional forms.The construction shifts codewords by the coupled center and restricts to information-set coordinates.Source: §3 · p. 9

Upper bound

  • For the upper bound, a normalized tilt makes each additional sparse-form constraint lower entropy; support reduction and a sunflower make the savings add.The sunflower argument handles singleton petals, which yield no savings individually.Source: §3 · p. 9

Lower bound

  • For the lower bound, the proof analyzes one type, σ_m, formed from an i.i.d. ρ-sparse vector plus a uniform multiple of 1, and computes its rat exactly.Its entropy spreads evenly across quotients by symmetry and submodularity.Source: §3 · p. 10

4 From codes to configurations

The proof first adjusts the code so that adjoining the all-ones vector creates a direct sum and makes the shifted codeword sparse. It then represents the type through an information set and sparse evaluations of pairwise non-proportional linear forms.

4.1 Reduction to 1 /∈C and augmentation by 1

  • If 1 already belongs to the column code, passing to a reduced type lowers its rank by one; adjoining 1 then gives dimension k = r◦ + 1 and makes the shifted codeword ρ-sparse.The shift is Y = x − α1, with each coordinate nonzero with probability at most ρ.Source: §4.1 · pp. 10–11
  • The augmented code's coordinate functionals are nonzero, pairwise non-proportional, and span its dual, so an information set of k coordinates determines Y.The functionals are pairwise non-proportional because each shares the last coordinate −1.Source: §4.1 · pp. 10–11

4.2 Reduction to configurations

  • Restricting to an information set yields a configuration: k ρ-sparse coordinates and additional ρ-sparse linear-form evaluations with nonzero, pairwise non-proportional forms.Each discarded coordinate is expressed as a linear form in X, the retained coordinates.Source: §4.2 · pp. 11–12
  • The entropy of X splits into the entropy of X modulo F_q1 and a conditional term between 0 and 1, since each quotient value has q preimages.This relates the information-set representation to its quotient by the all-ones line.Source: §4.2 · p. 12

5 Entropy bounds for configurations

Section 5 develops entropy bounds for sparse linear-constraint configurations, using sparse product measures and reductions to small-support families to analyze how savings from multiple linear forms interact. Sunflower extraction controls interactions in general-position families with exponentially small error, while common-core families require separate treatment for singleton forms; the section also identifies a limitation for q ≥ 3.

5.1 Calibration and the divergence of a single form

  • Tilting the k coordinate constraints gives the bound k h_q(ρ), with equality at ν0; an additional form of support w lowers it by D_q(ρ ∥ π_w), at least γ* when w ≥ 2.The probabilities π_w increase with w, and the local translate coefficient λ is less than 1.Source: §5.1 · pp. 13–14

5.2 Families with a common core

  • For forms with a common core and disjoint petals, conditioning on the core preserves the single-form savings for support sizes w ≥ 2; singleton forms instead exploit a shared core coordinate.The singleton argument pins down that coordinate and incurs a λ-power error.Source: §5.2 · pp. 14–15
  • A single support-2 form saves less than a full coordinate: γ* < h_q(ρ), so the single-form bound does not imply the theorem’s separate multi-form conclusion.The text establishes strict inequality by considering two dependent sparse coordinates and a support-2 difference form.Source: §5.2 · p. 17

5.3 Divergences add in general position

  • For multiple forms, entropy is bounded by k h_q(ρ) minus their single-form divergences, plus Ψ ln q, where Ψ measures interactions from linear combinations of at least two forms.Each interaction is weighted according to how much the combination’s support falls below the union of the supports involved.Source: §5.3 · pp. 17–19
  • When every combination of at least two forms has support at least W, the forms are in W-general position, and the interaction error is exponentially small as W grows.The section defines general position by this support condition; its bound controls Ψ using the decay of κ^W.Source: §5.3 · pp. 17, 19

5.4 General position, or confinement to a subspace

  • A family either contains T vectors in W-general position or lies in a subspace of dimension at most T − 1 plus vectors of support less than W.This dichotomy addresses the fact that a configuration need not contain the forms required by Proposition 5.12.Source: §5.4 · pp. 19–20

5.5 Reducing the supports by a change of basis

  • Changing basis along a form preserves entropy and the configuration while reducing the supports of a subfamily to at most 2W − 1.When forms lie in a bounded-dimensional subspace plus low-support vectors, a positive fraction share a common subspace component, enabling the change of basis.Source: §5.5 · pp. 20–21

5.6 Extracting a sunflower

  • Support reduction yields small supports from which the sunflower lemma [ER60] extracts a family with a common core and disjoint petals, enabling entropy bounds.When at least half the petals have size at least 2, the resulting bound is H_q(X) ≤ (k − 1)h.Source: §5.6 · p. 21
  • For q ≥ 3, configurations can have H_q(X) > (k − 1)h; the exponentially small residual for singleton petals therefore cannot be removed.The passage contrasts this with q = 2, where the displayed construction does not exist.Source: §5.6 · p. 22

5.7 Proof of Theorem 1.3

  • For N ≥ 1, Hq(X) ≤ k hq(ρ) − γ∗ with γ∗ > 0; for every η > 0, explicit N0(q,ρ,η), polynomial in log(1/η) with degree depending on (q,ρ), ensures N ≥ N0 gives Hq(X) ≤ (k − 1)hq(ρ) + η.For q ≥ 3, instances with arbitrarily large k and N can have Hq(X) > (k − 1)hq(ρ).Source: §5.7 · p. 23

5.8 Proof of the upper bound on V

  • For L ≥ max{q, L_low(q,ρ)}, the upper-bound proof applies Proposition 5.20 to types with 1 ≤ r° ≤ L − 1.The proof first restricts the reduced rank to 1 ≤ r° ≤ L, then treats the interior range using Proposition 5.20.Source: §5.8 · p. 24

6 Proof of the lower bound on V

The lower bound on V comes from exactly analyzing the projection entropies of a single explicit type. Symmetry and submodularity control those entropies across quotients, with the minimum attained at F_q1.

6 Proof of the lower bound on V

  • The explicit type’s entropy per dimension is computed exactly and lies within q^-Ω(m) of h_q(ρ).The type is an i.i.d. ρ-sparse vector plus a uniform multiple of the all-ones vector.Source: §6 · p. 24

6.1 The type σ_m

  • σ_m uses an i.i.d. ρ-sparse vector plus a uniform scalar shift, giving distinct columns and a type whose upper bound needs no forms.For this type, Proposition 4.3 alone gives rat(σ_m) ≤ h_q(ρ).Source: §6 · p. 24, §6.1 · p. 24

6.3 Equidistribution of entropy across quotients

  • Permutation symmetry and submodularity bound the entropy deficit on a quotient by its dimension times Q_m.The orbit of each nonzero subspace contains either Y or W, which supports the quotient-entropy bound.Source: §6.3 · pp. 25–26

6.4 The minimum is attained at Fq1

  • Among proper subspaces, the minimum projected entropy per codimension is attained at F_q1.The proof compares quotients containing F_q1 with those that do not, using Q_m ≤ 1 to establish the same lower bound.Source: §6.4 · pp. 26–27

7 Formal statements of Theorems 1.1 and 1.2

The formal statements give explicit cutoffs for the two-sided estimate of V and apply the threshold framework to random linear codes. They also provide a list-size bound at every rate below capacity.

7 Formal statements of Theorems 1.1 and 1.2

  • The lower and upper bounds on V together prove Theorems 1.1 and 1.2 through the threshold framework.The formal statements use explicit cutoffs for the bounds.Source: §7 · p. 27
  • For every integer L ≥ L_V(q,ρ), Corollary 7.1 gives the stated explicit upper bound on V.The cutoff L_V is defined using the list-size cutoff L_low and length cutoff m_lb.Source: §7 · p. 27
  • At rate R = 1 − h_q(ρ) − ε, the construction L = max{⌊ζ⌋ + 1, L_V(q,ρ)} yields list-decodability with probability 1 − o(1).The corollary applies the bound at every rate below capacity.Source: §7 · pp. 27–28

8 Further directions

The paper identifies a boundary for extending its argument to average-radius list decoding and discusses the range where its bounds apply. It proposes a quotient-entropy conjecture aimed at extending the upper bound’s range.

8 Further directions

  • The argument does not immediately extend to average-radius list decoding because it requires every codeword to lie individually within radius ρ.Average-radius decoding requires only that the list lie at average relative distance ρ from the center.Source: §8 · p. 28
  • The lower bound applies over a broader ε range than the exact upper bound, which requires ε below e^-Θ_q(κ^-2).Near 1 − 1/q, the lower-bound range includes ε ≤ (1 − h_q(ρ))/c for an absolute constant c.Source: §8 · p. 28
  • Between those ranges, Corollary 7.3 gives only L* ≤ L_V, which is exponentially larger than ζ.At rates Ω_q(κ^2), [Woo13] gives list size O(κ^-2) with constants independent of ρ.Source: §8 · p. 28
  • The upper-bound route loses up to one q-ary unit when it replaces H_q(X mod F_q1) by H_q(X), restricting the ε range.The paper suggests bounding the quotient entropy directly instead.Source: §8 · pp. 28–29
  • Conjecture 8.1 bounds quotient entropy by (k − 1)h_q(ρ)m/(m − 1), and would determine V within q^-Ω(L).It is meaningful when m(1 − h_q(ρ)) > 1; the paper states that the bound is tight up to q^-Ω(L).Source: §8 · p. 29

AI Disclosure

The manuscript discloses that Claude Opus 5 was used for proof checking, numerical verifications, and editing.

AI Disclosure

  • Claude Opus 5 was used for proof checking, numerical verifications, and editing; the author takes responsibility for correctness and originality.Source: AI Disclosure · p. 29

A Deferred proofs

The deferred proofs justify the threshold estimates through quotient and entropy arguments, then combine them to pin down the random code’s list size. In particular, they bracket it by consecutive integers and identify when the upper integer is attained.

Quotient reduction

  • A coordinate quotient preserves absolute ρ-clustering and pairwise-distinct columns, while relating the rates by rat(τ)≤rat(τ′).The quotient removes one dimension, and the associated code decomposes as C=C(τ′)+F_q1.Source: A Deferred proofs · p. 31

Sparse-form reduction

  • A pigeonhole argument extracts a large subfamily of forms with controlled support, using a basis change when their common component has support at least W.The selected subfamily has size at least N/q^(σ+W)−1 in the basis-change case.Source: A Deferred proofs · p. 33

Proposition 5.20

  • The proof of Proposition 5.20 splits at hN=γ*L and bounds H_q(X) in each regime to establish its target inequality.For hN≤γ*L it uses Corollary 5.7; for hN>γ*L it applies Theorem 1.3(2).Source: A Deferred proofs · p. 33

Entropy estimates

  • The entropy of u modulo the all-ones span is m h_q(ρ)−Δ_m, with Δ_m bounded by summing coset entropy contributions using the λ^m estimate.The proof uses the i.i.d. coordinate distribution ν₀ and bounds the summed terms by (q−1)λ^m.Source: A Deferred proofs · pp. 33–34
  • For two quotient variables, H_q(X mod V₁,X mod V₂)≤H_q(X mod V₁)+H_q(X mod V₂)−H_q(X mod (V₁+V₂)).The proof identifies the joint quotient with reduction modulo V₁∩V₂.Source: A Deferred proofs · p. 34

Final list-size bounds

  • With probability 1−o(1), the proof gives ⌊ζ⌋ ≤ L* ≤ ⌊ζ⌋+1, and yields L*=⌊ζ⌋+1 when {ζ}>t(ζ).The probability statement is for n→∞ with q, ρ, and ε fixed.Source: A Deferred proofs · p. 35

B Constants

All constants in this section depend only on q and ρ.

Constants

B.1 The tilting constants

The tilting constants are restricted to the parameter range ρ<1−1/q, and the sequence π_w increases from its initial values toward 1−1/q.

Tilting constants

  • The constants κ and β lie in (0,1), and θ₀ is positive.Source: §B.1 · p. 35

Parameter range

  • The parameter range ρ<1−1/q is precisely where θ₀>0 and β<1 hold.Source: §B.1 · p. 35

Tilting constants

  • The sequence satisfies π₀=0 and π₁=ρ, then increases toward 1−1/q; also λ<1.Source: §B.1 · p. 35

B.2 The derived constants

The derived constants include a positive divergence parameter and cutoffs used to control the proof’s error terms and apply its propositions.

Derived constants

  • γ*=D_q(ρ∥π₂)=D_q(ρ∥ρ(1+κ)) is positive.Source: §B.2 · p. 36
  • T_gp is chosen with T_gpγ*≥h_q(ρ), while W_gp is the least integer at least 2 making the stated error term at most γ*/2.At W=W_gp, Proposition 5.16 leaves a subfamily with supports of size at most ω.Source: §B.2 · p. 36
  • The cutoffs m_lb, L_low, L_V, and L_list are defined where they are first needed.Source: §B.2 · p. 36

C Limits of Theorem 1.3

The appendix constructs configurations whose entropy exceeds the bounds considered in Theorem 1.3, including under conditions where they satisfy Conjecture 8.1. It also gives a lower bound on the theorem’s parameter N0 and a weaker entropy conclusion without a restriction on κ.

C Limits of Theorem 1.3

  • For k + 1 ≤ m ≤ q^(k−1), a dimension-k configuration has Hq(X) > (k−1)hq(ρ), except that this range is empty when q = k = 2.These examples show the stated entropy bound can fail; the range is empty only in that case.Source: C Limits of Theorem 1.3 · p. 36
  • The construction uses a distribution with an atom at 0 and q^(k−1) pairwise non-proportional constraint vectors to form configurations.The constraint vectors include e1, …, ek.Source: C Limits of Theorem 1.3 · p. 36
  • For η below the configurations’ entropy excess, N0(q,ρ,η) is at least q^Ωq(1/κ).The excess depends only on q, κ, and k.Source: C Limits of Theorem 1.3 · p. 36
  • The weaker conclusion Hq(X) > k−1 holds without any restriction on κ.In this regime, the bound of Lemma 4.5 exceeds the trivial bound rat(τ) ≤ 1.Source: C Limits of Theorem 1.3 · p. 36
  • Under condition (24), m(1−hq(ρ)) ≥ Cq, and sufficiently large Cq, a configuration violates Hq(X) ≤ (k−1)hq(ρ) while satisfying Conjecture 8.1’s bound.For each m in the stated range, such a dimension-k configuration exists.Source: C Limits of Theorem 1.3 · pp. 36–37
Loading 2609.06570v1…