Pith. sign in

REVIEW 4 minor 29 references

For a broad family of sticky-insertion channels, Shannon capacity equals zero-error capacity and both equal log₂ λ.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 12:21 UTC pith:M5FH54S3

load-bearing objection First exact Shannon capacities for a nontrivial infinite family of sticky channels, with clean matching duals and constructive codes.

arxiv 2607.28281 v1 pith:M5FH54S3 submitted 2026-07-30 cs.IT math.IT

The Capacity of a Family of Sticky Channels

Mladen Kova\v{c}evi\'{c} This is my paper
classification cs.IT math.IT MSC 94A2494A40
keywords sticky-insertion channelrepeat channelShannon capacityzero-error capacityFuss–Catalan numberssynchronization errorscapacity per unit costduplication channel
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Sticky channels replace every input symbol by a random positive number of identical copies, scrambling run lengths while preserving the sequence of run symbols. Exact Shannon capacities for nontrivial repeat channels have been unknown. This paper isolates a family of q-ary laws whose repetition counts live on the arithmetic progression 1, 1+d, 1+2d, … and whose run-length distributions obey a coefficientwise domination inequality. For every such law the Shannon capacity collapses to the zero-error capacity and equals log₂ λ bits per input symbol, where λ is the unique positive root of a simple algebraic equation fixed by the alphabet size and the span d. Explicit members of the family are exhibited, including weighted Fuss–Catalan laws, giving the first exact capacity formulas for nontrivial sticky channels.

Core claim

Fix q≥2 and d≥1, and let λ>0 solve λ^d=(q−1)(λ^{d−1}+⋯+1). Every repetition law supported on 1+dℤ≥0 that satisfies the coefficientwise domination W_m(y)≥γ W_{m+d}(y) for all m,y with some γ≥λ^{−d} has Shannon capacity equal to zero-error capacity, both equal to log₂ λ. For the primitive weighted Fuss–Catalan family the equality holds if and only if the weight β meets or exceeds λ^{−d}.

What carries the argument

Coefficientwise domination of successive run-length distributions, which forces an explicit mixture Q_0 of the first d run laws to be a tight KL dual: the resulting upper bound exactly matches the rate of the modular zero-error construction that uses only run lengths 1 through d.

Load-bearing premise

Lengthening any input run by exactly d symbols never multiplies any single output-length probability by more than the fixed factor 1/γ.

What would settle it

Take a primitive weighted Fuss–Catalan law with parameter β strictly below λ^{−d} and check whether its Shannon capacity still equals log₂ λ; the paper asserts it must strictly exceed that value via a one-point run-length perturbation.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Maximum-cardinality modular zero-error codes achieve Shannon capacity for every law meeting the hypotheses, and admit efficient enumerative encoding and decoding.
  • Weighted Fuss–Catalan and certain power-law repetition laws have capacity exactly log₂ λ once their parameters clear the algebraic threshold.
  • An exact KL test decides whether the modular input distribution remains capacity-achieving even when uniform domination fails.
  • All capacity statements remain operationally valid at the critical Fuss–Catalan endpoint where the mean repetition count is infinite.

Where Pith is reading between the lines

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

  • The same domination-plus-modular dual may apply directly to tandem-duplication channels already known to share the same zero-error capacity.
  • Binary Fuss–Catalan channels with d=2 lie entirely below the equality threshold and form a concrete test case for tighter duals beyond uniform domination.
  • Compound laws whose intrinsic domination constant sits below λ^{−d} yet still pass the exact KL test would separate coefficientwise domination from capacity equality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper determines the Shannon and zero-error capacities of a family of q-ary sticky-insertion (repeat) channels. For fixed q≥2 and d≥1, λ is the unique positive root of λ^d=(q-1)(λ^{d-1}+⋯+1). Under the hypotheses that the repetition law K is supported on 1+dZ≥0 and that the induced run-length distributions satisfy the coefficientwise domination W_m(y)≥γ W_{m+d}(y) for some γ≥λ^{-d}, both capacities equal log2 λ. The zero-error rate is obtained from an explicit modular construction whose confusability classes are completely classified; the matching Shannon upper bound is obtained from an explicit mixture dual Q0 via the KL-duality method. An algebraic characterization identifies all laws obeying domination as compound weighted Fuss–Catalan PGFs, and for the primitive family the threshold β≥λ^{-d} is shown to be necessary as well as sufficient. Explicit power-law and Fuss–Catalan examples are given, including finite-mean cases.

Significance. Exact capacity formulas for nontrivial repeat/sticky channels have been essentially nonexistent; the literature consists of numerical bounds, asymptotic regimes, and zero-error results. The present work supplies the first infinite parametric family in which Shannon capacity is known exactly and coincides with zero-error capacity. The proofs are self-contained, free of moment assumptions (covering even the infinite-mean critical law), and constructive: maximum-cardinality zero-error codes with efficient enumerative encoding/decoding are exhibited. The exact KL criterion (Proposition 4) and the complete algebraic characterization of the domination class (Proposition 6) are additional structural contributions that clarify when soft run-length information can or cannot raise capacity above the modular rate. These results directly answer an open question of Cheraghchi–Ribeiro and supply a clean benchmark for future work on synchronization channels.

minor comments (4)
  1. [Section II, Theorem 1] In the statement of Theorem 1 the supremum is written over finitely supported PL; the subsequent continuity argument that rational finite-support laws are dense is correct, but a one-sentence forward reference to the total-variation continuity of conditional entropy (Csiszár–Körner) would make the passage fully self-contained for readers who skip the proof.
  2. [Section III, eq. (29)] Display (29) rewrites the defining equation for λ in reciprocal form; while equivalent, a brief remark that it is identical to (1) would prevent a momentary notational pause.
  3. [Section VI, Table I] Table I is useful but the caption could explicitly note that the upper endpoint β=1/(d+1) is the infinite-mean critical law, already discussed in Remark 4.
  4. [Introduction and passim] A few typographical inconsistencies appear (e.g., “asticky-insertion” missing a space in the Introduction; occasional missing thin spaces before dZ). None affect readability.

Circularity Check

0 steps flagged

No significant circularity: capacity equals log2 λ by matching an independent combinatorial zero-error code to a dual upper bound built from the channel law.

full rationale

The derivation is self-contained and non-circular. λ is fixed by the algebraic equation (1)/(29), which is also the growth rate of the modular signature count derived in the Appendix; it is not fitted to capacity data. The zero-error lower bound C0,q = log2 λ follows from support restriction (2) plus support nesting from domination (31), with the counting argument written out in full (Thm 3 + Appendix), so the citation to the author’s prior zero-error work [20] is not load-bearing. The Shannon upper bound is obtained from an explicit mixture dual Q0 (or the uniform-domination dual) via Lemma 2; when γ ≥ λ^{-d} the KL bound matches log2 λ pointwise (48)–(49). For the primitive Fuss–Catalan family the same threshold is necessary by the exact KL test (Prop. 4) and the elementary identity D(Wd+1∥W1)=log2(1/β). No quantity is defined in terms of the capacity it is used to prove, no parameter is fitted and then re-predicted, and no uniqueness theorem is imported as an external force. The paper is an ordinary matching of combinatorial lower and information-theoretic upper bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 2 invented entities

The argument rests on standard Shannon theory (mutual information, Fano, relative-entropy identities), the classical run-length reduction for sticky channels, and elementary branching-process/generating-function facts. No parameters are fitted to data; λ and the domination threshold are fixed by algebra. The only modeling choices are the sticky-insertion channel itself and the two hypotheses (arithmetic support and coefficientwise domination) that define the family under study.

axioms (5)
  • domain assumption Shannon capacity and zero-error capacity are defined via the usual asymptotic rate limits for vanishing-error and zero-error codes on the sticky channel (Sec. II).
    Standard operational definitions; no moment assumptions are imposed on K.
  • standard math Relative-entropy decomposition and non-negativity of KL divergence yield the dual capacity upper bound once a reference output Q satisfying D(Wℓ∥Q)≤cℓ−log2(q−1) is exhibited (Lemma 2).
    Classical information-theoretic identity used throughout Cheraghchi-style duality arguments.
  • standard math Galton–Watson extinction criterion and Dwass’s formula identify the coefficients of the functional equation G=(1−β)z+βG^{d+1} with weighted Fuss–Catalan / Jain–Consul probabilities (Prop. 5).
    Standard branching-process facts; cited to Athreya–Ney, Dwass, Consul et al.
  • domain assumption Repetition counts are i.i.d. and strictly positive, so the channel preserves run symbols and acts independently on run lengths (model (6)).
    Defines the sticky-insertion channel under study; excludes deletions.
  • ad hoc to paper Coefficientwise domination Wm≥γ Wm+d together with arithmetic support on 1+dZ is assumed as the hypothesis that forces the dual bound to meet the zero-error rate (Thm 3).
    This is the paper’s sufficient condition, not a universal channel property; necessity is proved only for the primitive subfamily.
invented entities (2)
  • Coefficientwise-domination criterion (31) and its intrinsic constant γ⋆d(G) independent evidence
    purpose: Supplies a checkable pointwise condition that makes the modular dual exactly tight and characterizes the compound Fuss–Catalan class.
    Introduced as the central technical hypothesis; equivalent algebraic forms are proved, but the criterion itself is native to the paper.
  • Compound weighted Fuss–Catalan repetition laws G=Fd,γ∘R independent evidence
    purpose: Complete algebraic description of all PGFs satisfying the domination inequality for a fixed γ.
    Defined and characterized in Prop. 6; they are ordinary probability laws, not physical postulates, and come with explicit pmfs and branching representations.

pith-pipeline@v1.2.0-daily-grok45 · 22286 in / 2931 out tokens · 50319 ms · 2026-07-31T12:21:04.858116+00:00 · methodology

0 comments
read the original abstract

We determine the capacity of a family of $q$-ary sticky-insertion channels. Fix $q\geq2$ and $d\geq1$, and let $\lambda$ be the unique positive solution of $\lambda^d = (q-1) (\lambda^{d-1} + \cdots + \lambda + 1 )$. We prove that, for every repetition law supported on $1+d\mathbb{Z}_{\geq0}$ and satisfying a coefficientwise-domination criterion with domination constant $\gamma\geq\lambda^{-d}$, the Shannon capacity equals the zero-error capacity, both being $\log_2\lambda$ bits per symbol. We also exhibit explicit repetition laws satisfying these conditions, one of which is given by the weighted Fuss--Catalan numbers. To the best of our knowledge, these are the first known cases of nontrivial repeat channels whose Shannon capacity has been determined exactly.

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 · 11 canonical work pages

  1. [1]

    Capacity per unit cost of a discrete memoryless channel,

    K. A. S. Abdel-Ghaffar, “Capacity per unit cost of a discrete memoryless channel,”Electron. Lett., vol. 29, no. 2, pp. 142–144, 1993, doi: 10.1049/el:19930096

    work page doi:10.1049/el:19930096 1993

  2. [2]

    K. B. Athreya and P. E. Ney,Branching Processes, ser. Grundlehren der mathematischen Wissenschaften, vol. 196. Berlin, Germany: Springer- Verlag, 1972, doi: 10.1007/978-3-642-65371-1

    doi:10.1007/978-3-642-65371-1 1972

  3. [3]

    Capacity upper bounds for deletion-type channels,

    M. Cheraghchi, “Capacity upper bounds for deletion-type channels,”J. ACM, vol. 66, no. 2, art. no. 9, 79 p., 2019, doi: 10.1145/3281275

    work page doi:10.1145/3281275 2019

  4. [4]

    Sharp analytical capacity upper bounds for sticky and related channels,

    M. Cheraghchi and J. Ribeiro, “Sharp analytical capacity upper bounds for sticky and related channels,”IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 6950–6974, 2019, doi: 10.1109/TIT.2019.2920375

    arXiv 2019

  5. [5]

    An overview of capacity results for synchronization channels,

    M. Cheraghchi and J. Ribeiro, “An overview of capacity results for synchronization channels,”IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 3207–3232, 2021, doi: 10.1109/TIT.2020.2997329

    arXiv 2021

  6. [6]

    P. C. Consul and F. Famoye,Lagrangian Probability Distributions. Boston, MA, USA: Birkhäuser, 2006, doi: 10.1007/0-8176-4477-6

    work page doi:10.1007/0-8176-4477-6 2006

  7. [7]

    The generalized negative binomial distribution and its characterization by zero regression,

    P. C. Consul and H. C. Gupta, “The generalized negative binomial distribution and its characterization by zero regression,”SIAM J. Appl. Math., vol. 39, no. 2, pp. 231–237, 1980, doi: 10.1137/0139020

    work page doi:10.1137/0139020 1980

  8. [8]

    Use of Lagrange expansion for generating discrete generalized probability distributions,

    P. C. Consul and L. R. Shenton, “Use of Lagrange expansion for generating discrete generalized probability distributions,”SIAM J. Appl. Math., vol. 23, no. 2, pp. 239–248, 1972, doi: 10.1137/0123026

    work page doi:10.1137/0123026 1972

  9. [9]

    Csiszár and J

    I. Csiszár and J. Körner,Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 2011, doi: 10.1017/CBO9780511921889

    doi:10.1017/cbo9780511921889 2011

  10. [10]

    Shannon’s theorems for channels with synchronization errors,

    R. L. Dobrushin, “Shannon’s theorems for channels with synchronization errors,”Probl. Inf. Transm., vol. 3, no. 4, pp. 11–26, 1967

    1967

  11. [11]

    Improved lower bounds for the capacity of i.i.d. deletion and duplication channels,

    E. Drinea and M. Mitzenmacher, “Improved lower bounds for the capacity of i.i.d. deletion and duplication channels,”IEEE Trans. Inf. Theory, vol. 53, no. 8, pp. 2693–2714, 2007, doi: 10.1109/TIT.2007.901221

    arXiv 2007

  12. [12]

    The total progeny in a branching process and a related random walk,

    M. Dwass, “The total progeny in a branching process and a related random walk,”J. Appl. Probab., vol. 6, no. 3, pp. 682–686, 1969, doi: 10.2307/3212112

    work page doi:10.2307/3212112 1969

  13. [13]

    Flajolet and R

    P. Flajolet and R. Sedgewick,Analytic Combinatorics. Cambridge, U.K.: Cambridge Univ. Press, 2009, doi: 10.1017/CBO9780511801655

    doi:10.1017/cbo9780511801655 2009

  14. [14]

    The Lagrange distributions and branching processes,

    I. J. Good, “The Lagrange distributions and branching processes,”SIAM J. Appl. Math., vol. 28, no. 2, pp. 270–275, 1975, doi: 10.1137/0128022

    work page doi:10.1137/0128022 1975

  15. [15]

    On the capacity of channels with timing synchronization errors,

    A. R. Iyengar, P. H. Siegel, and J. K. Wolf, “On the capacity of channels with timing synchronization errors,”IEEE Trans. Inf. Theory, vol. 62, no. 2, pp. 793–810, 2016, doi: 10.1109/TIT.2015.2504358

    arXiv 2016

  16. [16]

    A generalized negative binomial distri- bution,

    G. C. Jain and P. C. Consul, “A generalized negative binomial distri- bution,”SIAM J. Appl. Math., vol. 21, no. 4, pp. 501–513, 1971, doi: 10.1137/0121056

    work page doi:10.1137/0121056 1971

  17. [17]

    Duplication-correcting codes for data storage in the DNA of living organisms,

    S. Jain, F. Farnoud (Hassanzadeh), M. Schwartz, and J. Bruck, “Duplication-correcting codes for data storage in the DNA of living organisms,”IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4996–5010, 2017, doi: 10.1109/TIT.2017.2688361

    arXiv 2017

  18. [18]

    Capacity bounds for the Poisson-repeat channel,

    M. Kazemi and T. M. Duman, “Capacity bounds for the Poisson-repeat channel,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Taipei, Taiwan, June 2023, pp. 1196–1201, doi: 10.1109/ISIT54713.2023.10206866

    arXiv 2023

  19. [19]

    Directly lower bounding the information capac- ity for channels with i.i.d. deletions and duplications,

    A. Kirsch and E. Drinea, “Directly lower bounding the information capac- ity for channels with i.i.d. deletions and duplications,”IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 86–102, 2010, doi: 10.1109/TIT.2009.2034883

    arXiv 2010

  20. [20]

    Zero-error capacity of duplication channels,

    M. Kova ˇcevi´c, “Zero-error capacity of duplication channels,”IEEE Trans. Commun., vol. 67, no. 10, pp. 6735–6742, 2019, doi: 10.1109/TCOMM.2019.2931342

    arXiv 2019

  21. [21]

    On the maximum number of non-confusable strings evolving under short tandem duplications,

    M. Kova ˇcevi´c, “On the maximum number of non-confusable strings evolving under short tandem duplications,”Probl. Inf. Transm., vol. 58, no. 2, pp. 111–121, 2022, doi: 10.1134/S0032946022020028

    work page doi:10.1134/s0032946022020028 2022

  22. [22]

    Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors,

    H. Mercier, V . Tarokh, and F. Labeau, “Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors,”IEEE Trans. Inf. Theory, vol. 58, no. 7, pp. 4306–4330, 2012, doi: 10.1109/TIT.2012.2191682

    arXiv 2012

  23. [23]

    Capacity bounds for sticky channels,

    M. Mitzenmacher, “Capacity bounds for sticky channels,”IEEE Trans. Inf. Theory, vol. 54, no. 1, pp. 72–77, 2008, doi: 10.1109/TIT.2007.911291

    arXiv 2008

  24. [24]

    A survey of results for deletion channels and related synchronization channels,

    M. Mitzenmacher, “A survey of results for deletion channels and related synchronization channels,”Probability Surveys, vol. 6, pp. 1–33, 2009, doi: 10.1214/08-PS141

    work page doi:10.1214/08-ps141 2009

  25. [25]

    Efficient capacity-achieving codes for general repeat channels,

    F. Pernice, R. Li, and M. Wootters, “Efficient capacity-achieving codes for general repeat channels,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Espoo, Finland, June–July 2022, pp. 3097–3102, doi: 10.1109/ISIT50566.2022.9834386

    arXiv 2022

  26. [26]

    On the capacity of duplication channels,

    M. Ramezani and M. Ardakani, “On the capacity of duplication channels,” IEEE Trans. Commun., vol. 61, no. 3, pp. 1020–1027, 2013, doi: 10.1109/TCOMM.2013.020413.120070

    arXiv 2013

  27. [27]

    Functional composition patterns and power series reversion,

    G. N. Raney, “Functional composition patterns and power series reversion,” Trans. Amer. Math. Soc., vol. 94, no. 3, pp. 441–451, 1960, doi: 10.1090/S0002-9947-1960-0114765-9

    doi:10.1090/s0002-9947-1960-0114765-9 1960

  28. [28]

    The zero error capacity of a noisy channel,

    C. E. Shannon, “The zero error capacity of a noisy channel,” IRE Trans. Inf. Theory, vol. IT-2, no. 3, pp. 8–19, 1956, doi: 10.1109/TIT.1956.1056798

    arXiv 1956

  29. [29]

    On channel capacity per unit cost,

    S. Verdú, “On channel capacity per unit cost,”IEEE Trans. Inf. Theory, vol. 36, no. 5, pp. 1019–1030, 1990, doi: 10.1109/18.57201

    work page doi:10.1109/18.57201 1990