pith. sign in

arxiv: 2605.18323 · v1 · pith:2LK6SAIPnew · submitted 2026-05-18 · 💻 cs.IT · math.IT

Existence and Counting Bounds for High-Memory Spatially-Coupled Codes via the Combinatorial Nullstellensatz

Lei Huang This is my paper

Pith reviewed 2026-05-19 23:58 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords spatially-coupled LDPCCombinatorial Nullstellensatzcycle eliminationprotographexistence boundscounting boundsgirthedge-spreading
0
0 comments X

The pith

Sufficient memory conditions derived via the Combinatorial Nullstellensatz eliminate short cycles in spatially-coupled LDPC codes for fully connected base graphs.

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

This paper establishes sufficient conditions on the memory of spatially-coupled low-density parity-check codes to eliminate harmful short-cycle configurations at the protograph level. The authors model edge-spreading assignments such that cycle activations correspond to vanishing of certain polynomials over finite grids. Applying the Combinatorial Nullstellensatz then yields explicit memory thresholds that guarantee the absence of all 4-cycles, and of all 4- and 6-cycles, for fully connected base graphs. A sympathetic reader cares because these non-constructive bounds are shown to be asymptotically tight up to a constant factor for fixed base graph parameters, and the work also supplies counting lower bounds on the number of valid assignments. This provides an algebraic characterization of the feasible high-memory design space without relying on explicit constructions.

Core claim

The paper claims that by encoding the conditions for activating 4-cycles and 6-cycles as polynomial equations over suitable finite grids, the Combinatorial Nullstellensatz can be applied to prove the existence of edge-spreading assignments with memory m large enough to make all such polynomials non-zero only outside the desired range, thereby destroying the cycles. For (γ, κ) fully connected base graphs, this gives explicit memory requirements, and for fixed γ the upper bounds match lower bounds up to a constant factor asymptotically. The Alon-Füredi theorem further gives lower bounds on how many such assignments exist, including for those achieving girth at least 6.

What carries the argument

Encoding cycle-activation conditions as polynomial vanishing constraints over finite grids, to which the Combinatorial Nullstellensatz is applied to derive memory thresholds that force the polynomials to be non-vanishing in the relevant domain.

If this is right

  • Explicit memory values suffice to destroy all 4-cycles in the protograph for given base graph parameters.
  • Similar explicit conditions apply to eliminate both 4-cycles and 6-cycles.
  • The memory bounds are asymptotically tight up to a constant factor for fixed γ compared to known lower bounds.
  • Lower bounds exist on the number of edge-spreading assignments that achieve girth at least six.
  • The feasible design space for high-memory SC-LDPC codes receives a refined algebraic-combinatorial description.

Where Pith is reading between the lines

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

  • Since no construction algorithm is given, one could investigate whether random or greedy methods find valid assignments efficiently once the memory exceeds the threshold.
  • The polynomial encoding technique might be adaptable to other cycle lengths or different harmful structures in code design.
  • These existence results suggest that the proportion of good assignments grows with memory, which could be verified through sampling experiments.

Load-bearing premise

Cycle-activation conditions for the harmful structures can be encoded as polynomial vanishing constraints over finite grids in a way that permits direct application of the Combinatorial Nullstellensatz to obtain the stated memory thresholds.

What would settle it

An explicit computation for small γ and κ showing that the minimal memory needed to eliminate all 4-cycles exceeds the paper's derived sufficient bound would falsify the result.

read the original abstract

The finite-length performance of spatially-coupled low-density parity-check (SC-LDPC) codes is strongly affected by short cycle configurations and the harmful structures induced by them. This paper studies SC-LDPC code design directly at the protograph level, where the design variables are the edge-spreading assignments specified by the partition matrix. In contrast to CLLL/Moser--Tardos based constructive frameworks for QC-SC-LDPC codes, we focus on sharper nonconstructive existence and counting bounds. By encoding cycle-activation conditions as polynomial vanishing constraints over finite grids, we apply the Combinatorial Nullstellensatz to derive sufficient memory conditions for eliminating prescribed cycle-induced harmful structures. For fully connected $(\gamma,\kappa)$ base graphs, the resulting bounds explicitly characterize the memory required to destroy all $4$-cycles as well as all $4$- and $6$-cycles, and for fixed $\gamma$, they are asymptotically tight up to a constant factor compared with known lower bounds. We further apply the Alon--F\"uredi theorem to obtain lower bounds on the number of feasible edge-spreading assignments, including an explicit counting bound for assignments that eliminate all $4$-cycles and hence yield girth at least six. These results provide a refined algebraic-combinatorial characterization of the feasible design space for high-memory SC-LDPC codes, although no corresponding construction algorithm is provided.

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

1 major / 2 minor

Summary. The paper encodes cycle-activation conditions for 4-cycles (and 4-/6-cycles) in fully-connected (γ,κ) protographs as vanishing constraints on a multivariate polynomial P over a finite grid of size m, then invokes the Combinatorial Nullstellensatz to obtain sufficient conditions on the memory m that guarantee the existence of edge-spreading assignments eliminating those cycles; it further applies the Alon–Füredi theorem to lower-bound the number of such assignments.

Significance. If the CN application holds, the work supplies non-constructive existence bounds that are asymptotically tight up to a constant factor (for fixed γ) relative to known lower bounds, together with explicit counting lower bounds on girth-6 assignments. This algebraic-combinatorial perspective on the feasible design space for high-memory SC-LDPC codes is a clear strength.

major comments (1)
  1. [§3] §3, application of Combinatorial Nullstellensatz to P = ∏_c f_c: each edge variable x_e appears in Θ(κ) distinct 4-cycles (γ fixed), so deg_{x_e}(P) = O(κ) when each f_c has bounded per-variable degree. For the claimed regime m = Θ(κ) needed to match the asymptotic tightness statement, m−1 exceeds this per-variable degree for sufficiently large implicit constants, forcing the coefficient of ∏_e x_e^{m−1} to be identically zero. This violates the CN hypothesis and prevents the theorem from guaranteeing a non-vanishing point. The derivation of the explicit memory thresholds therefore requires a corrected degree calculation or a revised range of m.
minor comments (2)
  1. [§2] Notation for the partition matrix and the precise definition of the shift variables x_e should be introduced before the polynomial construction in §2.
  2. [Theorem 1] The statement of the main existence theorem would benefit from an explicit display of the leading monomial whose coefficient is asserted to be nonzero.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and for highlighting an important consideration regarding the degree analysis in the application of the Combinatorial Nullstellensatz. We address this comment below and will make the necessary revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§3] §3, application of Combinatorial Nullstellensatz to P = ∏_c f_c: each edge variable x_e appears in Θ(κ) distinct 4-cycles (γ fixed), so deg_{x_e}(P) = O(κ) when each f_c has bounded per-variable degree. For the claimed regime m = Θ(κ) needed to match the asymptotic tightness statement, m−1 exceeds this per-variable degree for sufficiently large implicit constants, forcing the coefficient of ∏_e x_e^{m−1} to be identically zero. This violates the CN hypothesis and prevents the theorem from guaranteeing a non-vanishing point. The derivation of the explicit memory thresholds therefore requires a corrected degree calculation or a revised range of m.

    Authors: We appreciate the referee's careful analysis of the polynomial degree in Section 3. The observation that each edge variable x_e is involved in Θ(κ) cycles is correct, and with γ fixed this yields a per-variable degree that is linear in κ. In our original derivation, the sufficient condition on m was stated in a manner that could, for large implicit constants, exceed the actual degree bound, which would indeed make the coefficient of the monomial ∏_e x_e^{m-1} vanish. To address this, we will revise the manuscript by providing an explicit computation of deg_{x_e}(P). Assuming each cycle polynomial f_c contributes a degree of at most 1 in each of its variables (as is typical for difference-based cycle activation conditions), the total degree is at most (γ − 1)(κ − 1). We will adjust the memory threshold to m ≤ (γ − 1)(κ − 1) + 1, ensuring the CN hypothesis holds. This preserves the O(κ) scaling and the asymptotic tightness up to a constant factor for fixed γ. The counting bounds via Alon–Füredi remain unaffected. We will update the statements of the main theorems and the proofs in the revised version. revision: yes

Circularity Check

0 steps flagged

No circularity: external theorems applied to independently defined cycle polynomials

full rationale

The paper defines edge-spreading assignments and encodes cycle-activation conditions directly as polynomial vanishing constraints over finite grids using the structure of the (γ,κ) base graph. It then invokes the Combinatorial Nullstellensatz and Alon-Füredi theorem—standard external results—to derive sufficient memory thresholds and counting bounds. No step reduces a claimed prediction to a fitted parameter by construction, renames a known result, or relies on a load-bearing self-citation whose justification is internal to the present work. The derivation chain is self-contained against external mathematical benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the validity of the Combinatorial Nullstellensatz and Alon-Füredi theorem as standard results, plus the assumption that cycle structures admit a faithful polynomial encoding; no free parameters or new entities are introduced.

axioms (2)
  • standard math The Combinatorial Nullstellensatz holds and can be applied to polynomials over finite grids to guarantee non-vanishing or existence of points satisfying vanishing conditions.
    Invoked to convert polynomial vanishing constraints into sufficient memory conditions for cycle elimination.
  • standard math The Alon-Füredi theorem provides lower bounds on the number of points where a polynomial does not vanish.
    Used to obtain counting bounds on feasible edge-spreading assignments.

pith-pipeline@v0.9.0 · 5777 in / 1526 out tokens · 38778 ms · 2026-05-19T23:58:53.585156+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

36 extracted references · 36 canonical work pages

  1. [1]

    High performance non-binary spatially-coupled codes for flash memories,

    A. Hareedy, H. Esfahanizadeh, and L. Dolecek, “High performance non-binary spatially-coupled codes for flash memories,” in2017 IEEE Information Theory Workshop (ITW), 2017, pp. 229–233

    work page 2017

  2. [2]

    Threshold saturation for spatially coupled LDPC and LDGM codes on BMS channels,

    S. Kumar, A. J. Young, N. Macris, and H. D. Pfister, “Threshold saturation for spatially coupled LDPC and LDGM codes on BMS channels,”IEEE Transactions on Information Theory, vol. 60, no. 12, pp. 7389–7415, 2014

    work page 2014

  3. [3]

    Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC,

    S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC,”IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 803–834, 2011

    work page 2011

  4. [4]

    Spatially coupled ensembles universally achieve capacity under belief propagation,

    S. Kudekar, T. Richardson, and R. L. Urbanke, “Spatially coupled ensembles universally achieve capacity under belief propagation,”IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 7761–7813, 2013

    work page 2013

  5. [5]

    Asymptotically good LDPC convolutional codes based on protographs,

    D. G. M. Mitchell, A. E. Pusane, K. S. Zigangirov, and D. J. Costello, “Asymptotically good LDPC convolutional codes based on protographs,” in2008 IEEE International Symposium on Information Theory, 2008, pp. 1030–1034

    work page 2008

  6. [6]

    Free distance bounds for protograph-based regular LDPC convolutional codes,

    D. G. M. Mitchell, A. E. Pusane, N. Goertz, and D. J. Costello, “Free distance bounds for protograph-based regular LDPC convolutional codes,” in2008 5th International Symposium on Turbo Codes and Related Topics, 2008, pp. 408–413

    work page 2008

  7. [7]

    Asymptotic trapping set analysis of regular protograph-based LDPC convolutional code ensembles,

    D. G. M. Mitchell, A. E. Pusane, and D. J. Costello, “Asymptotic trapping set analysis of regular protograph-based LDPC convolutional code ensembles,” in2009 Information Theory and Applications Workshop, 2009, pp. 264–271

    work page 2009

  8. [8]

    New families of LDPC block codes formed by terminating irregular protograph-based LDPC convolutional codes,

    D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, “New families of LDPC block codes formed by terminating irregular protograph-based LDPC convolutional codes,” in2010 IEEE International Symposium on Information Theory, 2010, pp. 824–828

    work page 2010

  9. [9]

    Trapping set analysis of protograph-based LDPC convolutional codes,

    D. G. M. Mitchell, A. E. Pusane, and D. J. Costello, “Trapping set analysis of protograph-based LDPC convolutional codes,” in2009 IEEE International Symposium on Information Theory, 2009, pp. 561–565

    work page 2009

  10. [10]

    Asymp- totically good LDPC convolutional codes with AWGN channel thresholds close to the Shannon limit,

    M. Lentmaier, D. G. Mitchell, G. Fettweis, and D. J. Costello, “Asymp- totically good LDPC convolutional codes with AWGN channel thresholds close to the Shannon limit,” in2010 6th International Symposium on Turbo Codes & Iterative Information Processing, 2010, pp. 324–328

    work page 2010

  11. [11]

    AWGN channel analysis of terminated LDPC convolutional codes,

    D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, “AWGN channel analysis of terminated LDPC convolutional codes,” in2011 Information Theory and Applications Workshop, 2011, pp. 1–5

    work page 2011

  12. [12]

    Exact free distance and trapping set growth rates for LDPC convolutional codes,

    D. G. M. Mitchell, A. E. Pusane, M. Lentmaier, and D. J. Costello, “Exact free distance and trapping set growth rates for LDPC convolutional codes,” in2011 IEEE International Symposium on Information Theory Proceedings, 2011, pp. 1096–1100

    work page 2011

  13. [13]

    Window decoding of braided convolutional codes,

    M. Zhu, D. G. M. Mitchell, M. Lentmaier, D. J. Costello, and B. Bai, “Window decoding of braided convolutional codes,” in2015 IEEE Information Theory Workshop - Fall (ITW), 2015, pp. 143–147

    work page 2015

  14. [14]

    A strategy to detect error propagation in sliding window decoding of SC-LDPC codes,

    M. M. M. Costantino, M. Battaglioni, and D. G. M. Mitchell, “A strategy to detect error propagation in sliding window decoding of SC-LDPC codes,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

    work page 2025

  15. [15]

    Modeling a sliding window decoder for spatially coupled LDPC codes,

    M. Zhu, D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, “Modeling a sliding window decoder for spatially coupled LDPC codes,” in2021 IEEE Globecom Workshops (GC Wkshps), 2021, pp. 1–6

    work page 2021

  16. [16]

    Design considerations for spatially coupled LDPC codes under decoding latency constraints,

    D. J. Costello, M. Zhu, D. G. M. Mitchell, and M. Lentmaier, “Design considerations for spatially coupled LDPC codes under decoding latency constraints,”IEEE BITS the Information Theory Magazine, pp. 1–17, 2026

    work page 2026

  17. [17]

    High-rate spatially coupled LDPC codes based on Massey’s convolutional self- orthogonal codes,

    D. J. Costello, M. Zhu, D. G. M. Mitchell, and M. Lentmaier, “High-rate spatially coupled LDPC codes based on Massey’s convolutional self- orthogonal codes,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

    work page 2025

  18. [18]

    Fractional doping of protograph-based spatially coupled LDPC codes,

    D. J. Costello, M. Zhu, D. G. M. Mitchell, and M. Lentmaier, “Fractional doping of protograph-based spatially coupled LDPC codes,” in2025 13th International Symposium on Topics in Coding (ISTC), 2025, pp. 1–5

    work page 2025

  19. [19]

    A novel design of spatially coupled LDPC codes for sliding window decoding,

    M. Zhu, D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, “A novel design of spatially coupled LDPC codes for sliding window decoding,” in2020 IEEE International Symposium on Information Theory (ISIT), 2020, pp. 473–478

    work page 2020

  20. [20]

    Error propagation mitigation in sliding window decoding of spatially coupled LDPC codes,

    M. Zhu, D. G. M. Mitchell, M. Lentmaier, and D. J. Costello, “Error propagation mitigation in sliding window decoding of spatially coupled LDPC codes,”IEEE Journal on Selected Areas in Information Theory, vol. 4, pp. 470–486, 2023

    work page 2023

  21. [21]

    Concatenated spatially coupled LDPC codes with sliding window decoding for joint source- channel coding,

    A. Golmohammadi and D. G. M. Mitchell, “Concatenated spatially coupled LDPC codes with sliding window decoding for joint source- channel coding,”IEEE Transactions on Communications, vol. 70, no. 2, pp. 851–864, 2022

    work page 2022

  22. [22]

    Spatially coupled generalized LDPC codes: Asymptotic analysis and finite length scaling,

    D. G. M. Mitchell, P. M. Olmos, M. Lentmaier, and D. J. Costello, “Spatially coupled generalized LDPC codes: Asymptotic analysis and finite length scaling,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3708–3723, 2021

    work page 2021

  23. [23]

    Designing protograph-based quasi-cyclic spatially coupled LDPC codes with large girth,

    S. Mo, L. Chen, D. J. Costello, D. G. M. Mitchell, R. Smarandache, and J. Qiu, “Designing protograph-based quasi-cyclic spatially coupled LDPC codes with large girth,”IEEE Transactions on Communications, vol. 68, no. 9, pp. 5326–5337, 2020

    work page 2020

  24. [24]

    Code design based on connecting spatially coupled graph chains,

    D. Truhachev, D. G. M. Mitchell, M. Lentmaier, D. J. Costello, and A. Karami, “Code design based on connecting spatially coupled graph chains,”IEEE Transactions on Information Theory, vol. 65, no. 9, pp. 5604–5617, 2019

    work page 2019

  25. [25]

    Design of irregular SC-LDPC codes with non-uniform degree distributions by linear programming,

    H.-Y . Kwak, J.-S. No, and H. Park, “Design of irregular SC-LDPC codes with non-uniform degree distributions by linear programming,”IEEE Transactions on Communications, vol. 67, no. 4, pp. 2632–2646, 2019

    work page 2019

  26. [26]

    A Markov Chain Monte Carlo method for efficient finite-length LDPC code design,

    A. Tanrıkulu, M. Yıldırım, and A. Hareedy, “A Markov Chain Monte Carlo method for efficient finite-length LDPC code design,”IEEE Transactions on Communications, vol. 74, pp. 5979–5993, 2026

    work page 2026

  27. [27]

    Probabilistic design of multi-dimensional spatially-coupled codes,

    C. ˙Irima˘gzı, A. Tanrıkulu, and A. Hareedy, “Probabilistic design of multi-dimensional spatially-coupled codes,” in2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 653–658

    work page 2024

  28. [28]

    Exploiting the degrees of freedom: Multi-dimensional spatially-coupled codes based on gradient descent,

    A. Tanrıkulu, M. Yıldırım, and A. Hareedy, “Exploiting the degrees of freedom: Multi-dimensional spatially-coupled codes based on gradient descent,”arXiv preprint arXiv:2603.25824, 2026

    work page arXiv 2026

  29. [29]

    Edge-spreading Raptor-like LDPC codes for 6G wireless systems,

    Y . Ren, L. Zhang, Y . Shen, W. Song, E. Boutillon, A. Balatsoukas- Stimming, and A. Burg, “Edge-spreading Raptor-like LDPC codes for 6G wireless systems,”IEEE Transactions on Communications, 2025

    work page 2025

  30. [30]

    Neural window decoder for SC-LDPC codes,

    D.-Y . Yun, H.-Y . Kwak, Y . Kim, S.-H. Kim, and J.-S. No, “Neural window decoder for SC-LDPC codes,”arXiv preprint arXiv:2411.19092, 2024

    work page arXiv 2024

  31. [31]

    Quantum convolutional codes constructed from classical self-orthogonal convolutional codes,

    V . Nourozi and D. G. M. Mitchell, “Quantum convolutional codes constructed from classical self-orthogonal convolutional codes,” in2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 02, 2025, pp. 634–635

    work page 2025

  32. [32]

    Spatially-coupled QLDPC codes,

    S. Yang and R. Calderbank, “Spatially-coupled QLDPC codes,”Quantum, vol. 9, p. 1693, 2025

    work page 2025

  33. [33]

    Counting and entropy bounds for structure-avoiding spatially- coupled LDPC constructions,

    L. Huang, “Counting and entropy bounds for structure-avoiding spatially- coupled LDPC constructions,”arXiv preprint arXiv:2601.09674, 2026

    work page arXiv 2026

  34. [34]

    Design and analysis of time-invariant SC-LDPC convolutional codes with small constraint length,

    M. Battaglioni, A. Tasdighi, G. Cancellieri, F. Chiaraluce, and M. Baldi, “Design and analysis of time-invariant SC-LDPC convolutional codes with small constraint length,”IEEE Transactions on Communications, vol. 66, no. 3, pp. 918–931, 2017

    work page 2017

  35. [35]

    Combinatorial Nullstellensatz,

    N. Alon, “Combinatorial Nullstellensatz,”Combinatorics, Probability and Computing, vol. 8, no. 1-2, pp. 7–29, 1999

    work page 1999

  36. [36]

    Covering the cube by affine hyperplanes,

    N. Alon and Z. Füredi, “Covering the cube by affine hyperplanes,” European journal of combinatorics, vol. 14, no. 2, pp. 79–83, 1993

    work page 1993