pith. sign in

arxiv: 2604.02994 · v1 · submitted 2026-04-03 · 💻 cs.IT · math.IT

Weight distribution bounds to relate minimum distance, list decoding, and symmetric channel performance

Donald Kougang-Yombi , Jan H\k{a}z{\l}a This is my paper

Pith reviewed 2026-05-13 18:50 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords error correcting codeslist decodingsymmetric channelweight distributionJohnson radiusminimum distanceerasure channel
0
0 comments X

The pith

Any q-ary code of relative distance delta achieves vanishing error probability on the symmetric channel up to the Johnson radius.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper links minimum distance to symmetric channel performance by showing that codes with relative distance delta have vanishing block error rates below the Johnson radius. It extends the known connection from list decoding radius to channel performance to cover general, non-linear codes through direct weight distribution bounds. For linear codes with alphabet size at least 4, this threshold improves for some values of delta by applying Samorodnitsky inequalities to weight distributions informed by erasure channel properties. These results indicate that combinatorial distance properties suffice to guarantee good random-noise performance without separate list-decoding analysis.

Core claim

A q-ary code of relative distance delta has vanishing error probability on the symmetric channel up to the Johnson radius J_q(delta). This holds for general codes by bounding the weight distribution directly. For linear codes and q at least 4, the bound improves over a range of delta by using erasure properties to constrain the weight distribution via Samorodnitsky inequalities.

What carries the argument

Bounds on the code's weight distribution obtained from its erasure-channel performance and Samorodnitsky inequalities, which control the transition to good symmetric-channel behavior.

If this is right

  • General codes, not just linear ones, connect their list-decoding radius to symmetric channel performance.
  • Linear codes can exceed the Johnson radius for symmetric channel performance when q is at least 4.
  • The erasure performance of a linear code implies tighter control over its weight distribution.
  • Weight distribution serves as the key link between minimum distance and channel error probability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Code constructions could prioritize erasure resilience to gain better noise tolerance beyond distance guarantees.
  • The approach may apply to other channel models where weight distributions determine performance.
  • Binary and ternary codes might not see the same improvement, highlighting the role of larger alphabets.

Load-bearing premise

The derived weight distribution bounds from erasure properties and Samorodnitsky inequalities are sufficiently accurate to push the performance threshold past the Johnson radius for linear codes with q at least 4.

What would settle it

Observe whether the block error probability of a linear code over an alphabet of size 4 with suitable relative distance goes to zero on the symmetric channel at noise rates exceeding the Johnson radius but within the improved range.

Figures

Figures reproduced from arXiv: 2604.02994 by Donald Kougang-Yombi, Jan H\k{a}z{\l}a.

Figure 1
Figure 1. Figure 1: Our lower bound p (q) ∗ ( qδ q−1 , δ) from Theorem 7 plotted against the Johnson bound for q = 9 and q = 17. Our bound is larger for larger values of δ. Also the upper bound of δ and the lower bound of δ/2 are plotted for illustration. Outline of the paper. Section 2 recaps our notation and preliminaries. Section 3 contains the proof of Theorem 1. In Section 4 we prove and discuss Theorem 6, and Section 4.… view at source ↗
Figure 2
Figure 2. Figure 2: Binary case q = 2, plot of Fλ(γ, p) := F(γ, p) + γ log 2 λ − 1  as a function of γ, for λ = 0.5 and some values of p. Our results imply vanishing error probability on BSCp whenever Fλ(δ, p) > 0, assuming relative distance δ and vanishing error probability on BECλ. 12 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Binary case q = 2, plot of p∗(λ, δ) as a function of the BEC erasure probability λ, for fixed relative distances δ ∈ {0.05, 0.1, 0.2, 0.4}. For comparison, we plot the threshold p(λ) = 1 2 − p 2 λ−1(1 − 2 λ−1) from [HSS21] which does not require the assumption of δ > 0. In the intervals where the graphs are constant, our bound matches the trivial bound p∗(λ, δ) ≥ δ/2. Theorem 6 establishes that linear code… view at source ↗
Figure 4
Figure 4. Figure 4: Binary case q = 2, p∗(λ, δ) as a function of the relative distance δ, for fixed erasure probabilities λ ∈ {0.25, 0.5, 0.7, 0.8}. Since a code family with relative distance δ has list decoding radius J2(δ), by Theorem 1 it also has vanishing symmetric channel error probability for p < J2(δ). Our bounds improve upon this result under the additional BEC assumption whenever p∗(λ, δ) > J2(δ). If W(δ0, p1) ≤ 0, … view at source ↗
Figure 5
Figure 5. Figure 5: The threshold p (q) ∗ (λ, δ) as a function of the relative distance δ, for fixed erasure probability λ = 0.6 and q ∈ {3, 5, 7, 16}. We also provide the trivial bound δ/2. (As in [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: p∗(0.6, δ) and p ⊥ ∗ (0.4, R, δ), as a function of the relative distance δ, for fixed rates R ∈ {0.4, 0.41, , 0.42, 0.43}. 5 Proof of Theorem 7 To establish Theorem 7, we need two preliminary claims. Claim 29 (Exercise 7.17 in [GRS25]). Let C ⊆ F n q be a code with relative distance at least 0 ≤ δ ≤ 1 − 1/q. Then, for every ε > 0, C is  q q−1 − ε  δ, q (q−1)ε  -erasure list decodable. Proof. For δ = 0 … view at source ↗
Figure 7
Figure 7. Figure 7: p0(15, δ) as a function of δ and compared to Jq(δ) and δ/2. See Appendix A.1. 0.6658 0.6660 0.6662 0.6664 0.6666 0.640 0.645 0.650 0.655 0.660 0.665 q=3 p (q) * ( q q 1 , ) Jq( ) 0.7490 0.7492 0.7494 0.7496 0.7498 0.7500 0.725 0.730 0.735 0.740 0.745 0.750 q=4 p (q) * ( q q 1 , ) Jq( ) 0.8880 0.8882 0.8884 0.8886 0.8888 0.860 0.865 0.870 0.875 0.880 0.885 0.890 q=9 p (q) * ( q q 1 , ) Jq( ) 0.9402 0.9404 0… view at source ↗
Figure 8
Figure 8. Figure 8: Our lower bound p (q) ∗ ( qδ q−1 , δ) from Theorem 7 plotted against the Johnson bound for q ∈ {3, 4, 9, 17} for δ ∈ [1 − 1 q − 2 −10 , 1 − 1 q ]. For q ≥ 4, our bound is larger than Jq(δ) for larger values of δ. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Upper and lower bounds for psym(q, δ) discussed in the paper, for large q = 220. Note that the bound p (q) ∗ ( δq q−1 , δ) is only for linear codes. Let t ′ := pn−n θ . Consider the error vector Z distributed according to Pr[Z = z] = ( p q−1 ) wt(z) (1−p) n−wt(z) . Assume that x ∈ C is the original message, and note that ∆(x + Z, x) = wt(Z). By the union bound, PB(C, qSCp , x) ≤ Pr[wt(Z) ∈/ (t ′ , t)] + Pr… view at source ↗
read the original abstract

We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a $q$-ary code of relative distance $\delta$ has vanishing error probability on the symmetric channel up to the Johnson radius $J_q(\delta)$. We improve upon this bound in the case of linear codes, for a range $\delta$, for $q\ge 4$. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript studies relationships between minimum distance, list decoding radius, and block error probability on symmetric channels for q-ary error-correcting codes. It extends the tight connection between list decoding and symmetric channel performance (previously shown for linear codes by Pernice, Sprumont, and Wootters) to general codes via direct weight-distribution bounds rather than sharp-threshold arguments. This yields that any q-ary code of relative distance δ has vanishing error probability on the symmetric channel up to the Johnson radius J_q(δ). For linear codes with q ≥ 4 the authors improve the threshold for a range of δ by using the code's erasure-channel performance together with Samorodnitsky inequalities to bound the weight distribution; they also present a general technique for linear codes that possess both constant relative distance and good erasure performance.

Significance. If the weight-distribution bounds and their application to the symmetric channel are tight as stated, the work provides a direct combinatorial route from minimum distance to average-case performance that applies to both linear and nonlinear codes. The extension beyond the Johnson radius for linear codes with q ≥ 4, obtained without parameter fitting, and the reusable technique linking erasure and symmetric-channel behavior constitute a concrete advance in relating worst-case and probabilistic properties of codes.

major comments (2)
  1. [section deriving the improved bound for linear codes] The central claim that the Johnson-radius threshold is improved for linear codes when q ≥ 4 rests on the tightness of the weight-distribution bounds obtained from erasure properties via Samorodnitsky inequalities. The manuscript should supply the explicit inequality chain, the resulting error term, and at least one concrete numerical comparison (for a specific δ and q) demonstrating that the new threshold strictly exceeds J_q(δ).
  2. [section extending the result to general codes] The extension of the list-decoding-to-symmetric-channel equivalence from linear to general codes is achieved by directly bounding the weight distribution. The manuscript must exhibit the precise bounding argument (including any auxiliary lemmas) that replaces the sharp-threshold technique used in the linear case, so that the vanishing-error claim up to J_q(δ) can be verified without circular appeal to prior linear-code results.
minor comments (1)
  1. [Introduction / preliminaries] Notation for the Johnson radius J_q(δ) and the symmetric-channel crossover probability should be introduced once with a self-contained definition before being used in the main statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address the two major comments below and will revise the manuscript to supply the requested explicit details and arguments.

read point-by-point responses

  1. Referee: [section deriving the improved bound for linear codes] The central claim that the Johnson-radius threshold is improved for linear codes when q ≥ 4 rests on the tightness of the weight-distribution bounds obtained from erasure properties via Samorodnitsky inequalities. The manuscript should supply the explicit inequality chain, the resulting error term, and at least one concrete numerical comparison (for a specific δ and q) demonstrating that the new threshold strictly exceeds J_q(δ).

    Authors: We agree that the presentation would benefit from greater explicitness. In the revised version we will insert the full inequality chain obtained by applying the Samorodnitsky inequalities to the erasure-channel performance, state the resulting additive error term in the weight-distribution bound, and add a concrete numerical example (q=4, δ=0.15) that shows the new threshold strictly larger than J_4(δ). revision: yes

  2. Referee: [section extending the result to general codes] The extension of the list-decoding-to-symmetric-channel equivalence from linear to general codes is achieved by directly bounding the weight distribution. The manuscript must exhibit the precise bounding argument (including any auxiliary lemmas) that replaces the sharp-threshold technique used in the linear case, so that the vanishing-error claim up to J_q(δ) can be verified without circular appeal to prior linear-code results.

    Authors: We will expand the relevant section to display the direct combinatorial bounding argument for the weight distribution of arbitrary (possibly nonlinear) codes, together with the auxiliary lemmas that control the number of codewords of each weight. The argument is self-contained and does not invoke the linear-code sharp-threshold result, thereby establishing vanishing block error up to the Johnson radius for general codes. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivation extends the Pernice-Sprumont-Wootters result to general codes by directly bounding weight distributions (a standard combinatorial technique) and improves the linear-code case via erasure-channel properties combined with external Samorodnitsky inequalities. Neither step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the cited prior work is by different authors and the inequalities are independent mathematical tools. The argument therefore remains self-contained against external benchmarks with no circular reduction of the claimed thresholds to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the ledger is populated from standard coding-theory background rather than explicit statements in the manuscript.

axioms (2)
  • domain assumption Standard properties of q-ary codes and symmetric channels hold (alphabet size q, uniform symbol error probability).
    Invoked implicitly when relating minimum distance, list-decoding radius, and block error probability.
  • domain assumption Samorodnitsky inequalities apply to the weight distribution of linear codes with given erasure performance.
    Used to bound weight distributions in the linear-code improvement.

pith-pipeline@v0.9.0 · 5510 in / 1348 out tokens · 35556 ms · 2026-05-13T18:50:36.179568+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Generalized S amorodnitsky noisy function inequalities, with applications to error-correcting codes

    Olakunle Abawonse, Jan Hązła, and Ryan O'Donnell. Generalized S amorodnitsky noisy function inequalities, with applications to error-correcting codes. arXiv:2508.06940, 2025

    work page arXiv 2025

  2. [2]

    A proof that R eed-- M uller codes achieve S hannon capacity on symmetric channels

    Emmanuel Abbe and Colin Sandon. A proof that R eed-- M uller codes achieve S hannon capacity on symmetric channels. In Symposium on Foundations of Computer Science (FOCS) , pages 177--193. IEEE, 2023

    work page 2023

  3. [3]

    Reed-- M uller codes have vanishing bit-error probability below capacity: a simple tighter proof via camellia boosting

    Emmanuel Abbe and Colin Sandon. Reed-- M uller codes have vanishing bit-error probability below capacity: a simple tighter proof via camellia boosting. arXiv:2312.04329, 2023

    work page arXiv 2023

  4. [4]

    Reed-- M uller codes

    Emmanuel Abbe, Ori Sberlo, Amir Shpilka, and Min Ye. Reed-- M uller codes. Foundations and Trends in Communications and Information Theory , 20(1--2):1--156, 01 2023

    work page 2023

  5. [5]

    Convex Optimization

    Stephen Boyd and Lieven Vandenberghe. Convex Optimization . Cambridge University Press, 2004

    work page 2004

  6. [6]

    Algebraic geometry codes and some applications

    Alain Couvreur and Hugues Randriambololona. Algebraic geometry codes and some applications. In Concise Encyclopedia of Coding Theory , pages 307--362. Chapman and Hall/CRC, 2021

    work page 2021

  7. [7]

    On the number of error correcting codes

    Dingding Dong, Nitya Mani, and Yufei Zhao. On the number of error correcting codes. Combinatorics, Probability and Computing , 32(5):819--832, 2023

    work page 2023

  8. [8]

    Error-correcting codes for list decoding

    Peter Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory , 37(1):5--12, 1991

    work page 1991

  9. [9]

    On the list-decodability of random linear codes

    Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty. On the list-decodability of random linear codes. In Symposium on Theory of Computing (STOC) , pages 409--416, 2010

    work page 2010

  10. [10]

    Essential coding theory

    Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. Draft available at http://www. cse.buffalo.edu/faculty/atri/courses/coding-theory/book/ , 2025

    work page 2025

  11. [11]

    Techniques of bounding the probability of decoding error for block coded modulation structures

    Hanan Herzberg and Gregory Poltyrev. Techniques of bounding the probability of decoding error for block coded modulation structures. IEEE Transactions on Information Theory , 40(3):903--911, 1994

    work page 1994

  12. [12]

    On codes decoding a constant fraction of errors on the BSC

    Jan H a z a, Alex Samorodnitsky, and Ori Sberlo. On codes decoding a constant fraction of errors on the BSC . In Symposium on Theory of Computing (STOC) , pages 1479--1488, 2021

    work page 2021

  13. [13]

    Some remarks on the number of rational points of algebraic curves over finite fields

    Yasutaka Ihara. Some remarks on the number of rational points of algebraic curves over finite fields. Journal of the Faculty of Science, University of Tokyo , 28(3):721--724, 1981

    work page 1981

  14. [14]

    A new upper bound for error-correcting codes

    Selmer Johnson. A new upper bound for error-correcting codes. IRE Transactions on Information Theory , 8(3):203--207, 1962

    work page 1962

  15. [15]

    Reed- M uller codes achieve capacity on erasure channels

    Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D Pfister, Eren S a s o g lu, and R \"u diger Urbanke. Reed- M uller codes achieve capacity on erasure channels. In Symposium on Theory of Computing (STOC) , pages 658--669, 2016

    work page 2016

  16. [16]

    Adaptive estimation of a quadratic functional by model selection

    Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics , pages 1302--1338, 2000

    work page 2000

  17. [17]

    Smoothing of binary codes, uniform distributions, and applications

    Madhura Pathegama and Alexander Barg. Smoothing of binary codes, uniform distributions, and applications. Entropy , 25(11):1515, 2023

    work page 2023

  18. [18]

    Binary codes with specified minimum distance

    Morris Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory , 6(4):445--450, 1960

    work page 1960

  19. [19]

    Bounds on the decoding error probability of binary linear codes via their spectra

    Gregory Poltyrev. Bounds on the decoding error probability of binary linear codes via their spectra. IEEE Transactions on Information Theory , 40(4):1284--1292, 1994

    work page 1994

  20. [20]

    List-decoding capacity implies capacity on the q-ary symmetric channel

    Francisco Pernice, Oscar Sprumont, and Mary Wootters. List-decoding capacity implies capacity on the q-ary symmetric channel. In Symposium on Theory of Computing (STOC) , pages 855--866, 2025

    work page 2025

  21. [21]

    From bit to block: D ecoding on erasure channels

    Henry D Pfister, Oscar Sprumont, and Gilles Zémor. From bit to block: D ecoding on erasure channels. In International Symposium on Information Theory (ISIT) , pages 1--6, 2025

    work page 2025

  22. [22]

    Reed-- M uller codes on BMS channels achieve vanishing bit-error probability for all rates below capacity

    Galen Reeves and Henry D Pfister. Reed-- M uller codes on BMS channels achieve vanishing bit-error probability for all rates below capacity. IEEE Transactions on Information Theory , 70(2):920--949, 2023

    work page 2023

  23. [23]

    Modern Coding Theory

    Tom Richardson and Rüdiger Urbanke. Modern Coding Theory . Cambridge University Press, 2008

    work page 2008

  24. [24]

    Two theorems on list decoding

    Atri Rudra and Steve Uurtamo. Two theorems on list decoding. In Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM) , pages 696--709, 2010

    work page 2010

  25. [25]

    An upper bound on _q norms of noisy functions

    Alex Samorodnitsky. An upper bound on _q norms of noisy functions. IEEE Transactions on Information Theory , 66(2):742--748, 2019

    work page 2019

  26. [26]

    An improved bound on _q norms of noisy functions

    Alex Samorodnitsky. An improved bound on _q norms of noisy functions. arXiv:2010.02721, 2020

    work page arXiv 2010

  27. [27]

    Performance analysis of linear codes under maximum-likelihood decoding: A tutorial

    Igal Sason and Shlomo Shamai. Performance analysis of linear codes under maximum-likelihood decoding: A tutorial. Foundations and Trends in Communications and Information Theory , 3(1--2):1--222, 2006

    work page 2006

  28. [28]

    Modular curves, S himura curves, and G oppa codes, better than V arshamov-- G ilbert bound

    MA Tsfasman, SG Vl a duţ, and Th Zink. Modular curves, S himura curves, and G oppa codes, better than V arshamov-- G ilbert bound. Mathematische Nachrichten , 109(1):21--28, 1982

    work page 1982

  29. [29]

    Discrete isoperimetric inequalities and the probability of a decoding error

    Jean-Pierre Tillich and Gilles Z \'e mor. Discrete isoperimetric inequalities and the probability of a decoding error. Combinatorics, Probability and Computing , 9(5):465--479, 2000

    work page 2000