PaperlayerView exact revision on arXiv

Source-linked AI summary

Encoding-Sensitive Nullstellensatz Certificates for Syndrome Exclusion in LDPC Codes: Sharp Local Bounds and a Linear Separation

Malihe Aliasgari, Hassan Khodaiemehr, Khadijeh Bagheri

arXiv:2610.32171v1cs.ITmath.IT

TL;DR

The paper asks how to certify that no small variable-node support leaves too few checks unsatisfied, a question tied to minimum-distance and trapping-set analysis. It compares exact polynomial encodings of the same problem and constructs local certificates alongside planted-knapsack lower bounds for the counting encoding. The local degree stays bounded in the stated settings while counting-encoding lower bounds grow linearly with block length; the planting argument is optimal among pullbacks of its kind.

  • Problem

    The problem is to certify that no nonempty support of size at most t leaves at most b checks unsatisfied, which is relevant to minimum-distance and trapping-set analysis.

    Source: §I · p. 2

  • Method

    The paper compares equivalent counting and local polynomial encodings, constructing explicit local certificates and pulling back planted-knapsack functionals for lower bounds.

    Source: §I · p. 2, §VI · p. 28, C. Why the Growth Needs Both Counters · p. 37

  • Results

    The local encoding has degree at most t + b + K + 1 independent of block length under fixed t, b, and bounded check degree, while the counting encoding has linear-in-block-length lower bounds in the stated code families.

    Source: §XI · pp. 45–46, §XII · pp. 46–47

  • Takeaways & Limitations

    The results show that encoding choice affects certificate degree, and the authors suggest local cardinality constraints when certificates are a deliverable.

    Source: §XII · p. 46

    Odd column weight at (t, b) = (1, 0) remains open for girth-six families lacking the specified induced paths, stars, or many check-disjoint short codewords.

    Source: F. Further Limitations · p. 42

Abstract

from arXiv · show

Certifying that a parity-check matrix has no nonempty set of at most t variable nodes leaving at most b checks unsatisfied arises in minimum-distance and trapping-set analysis. Such absence is the infeasibility of a polynomial system, provable by an independently checkable Nullstellensatz certificate. The degree of these certificates depends strongly on how the two cardinality constraints are encoded, although the encodings have identical solutions. For a local encoding with inclusion-exclusion and cardinality obstructions, we construct explicit certificates of degree at most t + b + K + 1, with K logarithmic in the maximum check degree; this bound is independent of the block length and cannot be improved in general. For a standard counting encoding, a generalized planted-knapsack theorem, which pulls back a knapsack functional with an arbitrary target, gives lower bounds linear in the block length for cycle codes, regular codes of girth at least six near the feasibility boundary, array-based quasi-cyclic codes and minimum-distance certificates for arrays of circulant permutation matrices, where the local degree stays bounded. On array codes and regular codes of girth at least eight, planted column pairs extend these bounds to odd column weight with no unsatisfied checks. The planting argument is optimal among such pullbacks. All computed degrees and certificates are verified in exact rational arithmetic; bounds are distinguished from exact minimum degrees. Local certificates for quasi-cyclic matrices, including a lifted fifth-generation New Radio base graph, pass two independent verifiers.

I. INTRODUCTION

Small variable-node supports with few unsatisfied checks relate to codewords and trapping sets, and their exclusion can be formulated as polynomial infeasibility. The paper studies how equivalent encodings change Nullstellensatz proof degree, rather than proposing a new search or decoding method.

A. The Conference Version

  • The journal version adds asymptotic analysis, lower bounds beyond cycle codes, and minimum-distance certification to the conference version’s encodings, local certificates, and finite cycle-code separation.The conference version also reduced counting degree on cycle codes to a compact Boolean system and generated local certificates for QC-LDPC matrices.Source: A. The Conference Version · p. 3

B. Contributions

  • The local encoding yields certificates of degree at most t + b + K + 1, uniform in block length for fixed t, b, and bounded check degree, and this bound is sharp in general.The construction has O(nt) terms; at (t, b) = (1, 0), the degree is exactly two for column-regular matrices whose checks have degree two or three.Source: B. Contributions · p. 3
  • The planting method pulls back a knapsack functional with an arbitrary rational target, and its bound is optimal among such pullbacks.The target has degree exactly M + 1, and that bound is attained for every M.Source: B. Contributions · pp. 3–4
  • The generalized planted-knapsack theorem gives counting-encoding degree lower bounds linear in block length for cycle, regular, and array-based QC-LDPC codes, yielding Θ(n)-versus-O(1) separations.The regular families have girth at least six and are near the feasibility boundary; planted 6-cycles also give bounds for column weight three at t ∈ {2, 3}.Source: B. Contributions · p. 4
  • Planting codewords gives counting-degree lower bounds for minimum-distance certification, including a Θ(n)-versus-O(1) separation for arrays of circulant permutation matrices.For H(3, 5, 47), the counting degree is at least 45 for t from 2 to 5, versus local degree at most 8.Source: B. Contributions · p. 4
  • Planted column pairs extend linear lower bounds to odd column weight with no unsatisfied checks on array codes and regular families of girth at least eight.The stated conditions are specific: girth six alone does not suffice, and the result uses induced paths or stars.Source: B. Contributions · p. 4

C. Positioning and Scope

  • The local encoding trades lower proof degree for extra generators and O(nt) certificate terms, so it is not presented as faster than enumeration or as a claim about Gröbner-basis running time.The paper frames the benefit as an independently checkable proof object; all statements are over Q, and several depend on characteristic zero.Source: C. Positioning and Scope · p. 5

D. Related Work

  • The paper studies proof degree for nonexistence certificates, distinct from prior work on searching for small trapping structures and algebraic decoding.It places the work alongside established encoding sensitivity in proof complexity and independently checkable proof objects.Source: D. Related Work · p. 5

B. The Counting and Local Encodings

The two encodings impose the same bounded-support and syndrome conditions but use different generators for the cardinality bounds. Their exactness and certificate degrees are characterized through Boolean solutions and finite linear-algebra criteria.

B. The Counting and Local Encodings

  • The counting encoding uses counters and one-hot selectors for support size and syndrome weight, while the local encoding uses truncated inclusion–exclusion and cardinality obstructions.The local obstructions do not depend on H and leave all dependence on H in the parity generators; the example with n = 48 and (t, b) = (3, 0) has 156 counting generators versus 194,749 local generators.Source: B. The Counting and Local Encodings · pp. 6–7

C. Exactness

  • Both encodings have exactly the admissible supports as their Boolean solutions: nonempty sets of size at most t with at most b odd-degree checks.Every auxiliary variable is determined by the support, and each admissible support extends uniquely to a zero.Source: C. Exactness · p. 7

D. Certificates and Their Degree

  • The dual criterion certifies degree greater than D with a normalized linear functional annihilating all generator multiples through degree D, while Boolean multilinear reduction turns degree membership into finite linear algebra.The results are over Q; the paper notes that positive-characteristic behavior can differ and that the planted lower bounds are characteristic-zero statements.Source: D. Certificates and Their Degree · pp. 8–9

E. Counter Elimination and a Generic Upper Bound

Counter elimination reduces the counting encoding to a Boolean system, enabling a generic degree bound in the number of variables. The local support-polynomial construction uses inclusion–exclusion, cardinality obstructions, and parity inverses to build low-degree certificates.

E. Counter Elimination and a Generic Upper Bound

  • Counter elimination replaces the counting system with an equivalent all-Boolean system while mapping certificates without increasing their degree.The generic Boolean-system bound then applies to the transformed instance.Source: E. Counter Elimination and a Generic… · p. 9
  • For an infeasible system with N Boolean variables and further generators of degree at most dG, the Nullstellensatz degree is at most N + dG.Applied to the counter-eliminated counting system, this gives the stated encoding-specific upper bound.Source: E. Counter Elimination and a Generic… · p. 9

A. Support Polynomials, Absorption and Parity Inverses

  • The support-polynomial construction uses inclusion–exclusion, with omitted terms represented by cardinality obstructions whose certificate products have degree at most t + 1.On Boolean points of weight at most t, the support polynomial identifies the specified support.Source: A. Support Polynomials, Absorption and… · p. 10
  • For an odd check intersection, the parity inverse interpolates the reciprocal of c − 2Qj on Boolean points; the construction uses the support obstructions, and equally low degree without them remains open.The obstructions enter the certificate only at this step.Source: A. Support Polynomials, Absorption and… · p. 10

B. The Sharper Bound

The local encoding admits certificates of degree at most t + b + K + 1, with a bound uniform in block length for fixed t, b, and bounded check degree. The bound is attained in general, while every local certificate has degree at least t.

B. The Sharper Bound

  • Infeasible local instances have an explicit certificate of degree at most t + b + K + 1.The bound combines support localization, the syndrome-count telescope, the parity inverse, and a closing generator.Source: B. The Sharper Bound · pp. 11–12

C. Tightness

  • Every certificate for the local encoding has degree at least t, while whether t + b + 1 is always a lower bound when check degrees are at least two remains open.Random-instance computations reported lower degrees in some cases involving degree-one checks.Source: B. The Sharper Bound · p. 11, C. Tightness · p. 13

B. The Sharper Bound

  • For fixed t, b, and maximum check degree, the local degree bound is uniform in block length, and the explicit construction has O(nt) terms.If t or b grows with block length, the degree bound grows as well.Source: B. The Sharper Bound · pp. 11–12

C. Tightness

  • The upper bound is attained in general, with exact computations confirming the constructed certificate degrees in the exhibited cases.The paper distinguishes these exact degrees from general upper bounds.Source: C. Tightness · p. 13

D. Exact Degree Two for Cycle and Sparse Regular Codes

The local encoding has exact degree two for the stated column-regular matrices with check degrees two or three. The counting encoding, in contrast, admits linear degree lower bounds through a degree-preserving pullback to a knapsack system with an unattainable target.

D. Exact Degree Two for Cycle and Sparse Regular Codes

  • For column-regular matrices with check degrees at most three, the local encoding has degree at most two, with equality when every check has degree at least two.This includes cycle codes and the stated sparse regular examples.Source: D. Exact Degree Two for Cycle and… · pp. 13–14

IV. A GENERALIZED PLANTED-KNAPSACK THEOREM

  • The planted-knapsack construction maps counting variables to constants or affine functions of new Boolean variables, preserving degree while turning both counts into multiples of one linear form.A knapsack functional for that form pulls back to a functional for the counting encoding.Source: §IV · p. 14

A. The Knapsack Functional with an Arbitrary Target

  • For an unattainable rational target r outside {0, . . . , M}, the knapsack functional is defined on Boolean monomials and annihilates multiples of Y − r through the stated degree range.When the target is attainable, the functional instead averages evaluations over Boolean points with Y = r.Source: A. The Knapsack Functional with an… · p. 15

B. The Knapsack Target

  • The knapsack system with an unattainable target has exact Nullstellensatz degree M + 1.The result supplies the degree lower bound used by the planted construction.Source: B. The Knapsack Target · pp. 15–16

C. The Generalized Planting Theorem

The generalized planting theorem substitutes constants and affine functions for counting variables so that the support and syndrome counts share a single knapsack target. Pulling back the corresponding functional yields a degree lower bound when the planting conditions make that target unattainable.

C. The Generalized Planting Theorem

  • The planted sets are pairwise disjoint, each check meets at most one, their syndrome-weight increments agree, and the base support and syndrome weights satisfy the stated boundary conditions.These conditions include a common increment λ and integers c and β in the specified ranges.Source: C. The Generalized Planting Theorem · p. 16
  • The substitution maps support variables and parity variables to constants or affine functions of one new Boolean variable, while keeping selectors and counters fixed at constants.Every variable maps to a polynomial of degree at most one, so monomial degrees do not increase.Source: C. The Generalized Planting Theorem · p. 17
  • When the planted target is unattainable, pulling back the knapsack functional gives the degree lower bound; no pullback of this kind proves more.Only two degree-one generators carry the target, and the functional annihilates their relevant multiples through degree M.Source: C. The Generalized Planting Theorem · pp. 17–18

D. Single Planted Columns

Single-column plantings yield counting-encoding degree lower bounds, while generalized targets and even planted sets remove two restrictions of the simplest planting. These arguments establish linear separations for cycle and regular codes, with compact-system bounds also growing linearly on cycles.

D. Single Planted Columns

  • M relaxed planted columns with a common parity change λ and 0 ≤ Φ(O) − λ ≤ b imply degNS(Ecnt) ≥ M + 1.Adding each planted column changes Φ(O) by λ; the relaxed planting removes the need for all planted columns to avoid checks in O.Source: D. Single Planted Columns · pp. 18–19

E. What the General Target and Even Planted Sets Remove

  • General targets remove the single-column restriction |O| ≤ t + 1, while even planted sets or even c remove its parity restriction.For odd planted-set size k, β ≡ wc (mod 2); at t = 1 and odd column weight, this requires b ≥ 1.Source: E. What the General Target and Even… · pp. 19–20

A. Tanner-Graph Conditions

  • For regular codes of girth at least six, t = 1 and w − 2 ≤ b ≤ w − 1 give a linear-in-n counting lower bound, versus a bounded local degree for fixed parameters.The range of b is forced by the planting parity condition; planted pairs extend the reach to b = 0 in Section VII.Source: A. Tanner-Graph Conditions · p. 21
  • On Cn, for 1 ≤ t ≤ n − 1 and b ∈ {0, 1}, the counting degree is at least ⌊(n − 1)/2⌋, while the local degree is bounded.The compact Boolean system OPPn also has degree growing linearly, although its exact degree formula remains open.Source: B. Cycle Codes and the Compact System… · pp. 22, 24

C. Quasi-Cyclic Codes

For quasi-cyclic matrices, planted columns give linear counting-encoding lower bounds when a pair of columns shares checks. Explicit array-code families meet the needed structural conditions, while local bounds remain logarithmic in check degree.

C. Quasi-Cyclic Codes

  • If two weight-w columns share s checks, then for w − 2s ≤ b ≤ w − 1 the t = 1 instance is infeasible and the counting degree is at least Z − w + s.The local degree is at most b + K + 2; when the columns share exactly one check, the counting lower bound is linear in Z.Source: C. Quasi-Cyclic Codes · pp. 24–25
  • For H(w, L, Z) with Z > (w − 1)(L − 1), the construction has n = LZ columns, check degree L, and no pair of columns sharing two checks.For w − 2 ≤ b ≤ w − 1, the planted construction gives a linear-in-n counting lower bound and a local bound at most b + K + 2.Source: C. Quasi-Cyclic Codes · p. 25
  • At Z = (w − 1)(L − 1), two columns can share two checks, so the threshold on Z cannot be lowered uniformly in w and L.The example uses columns (0, 0) and (L − 1, 0).Source: C. Quasi-Cyclic Codes · p. 26

D. Planted 6-Cycles and Larger Supports

Planted 6-cycles extend counting-degree lower bounds to weight-three codes, including the zero-unsatisfied-check setting that single-column plantings cannot reach. The results also delimit feasibility for supports of size two or three.

D. Planted 6-Cycles and Larger Supports

  • For weight-three codes of girth at least six containing the specified 6-cycle, supports of size t ∈ {2, 3} are infeasible when b ≤ 2 and feasible when b ≥ 3.A planted 6-cycle supports β = 0, unlike the odd-β single-column planting limitation for column weight three.Source: D. Planted 6-Cycles and Larger Supports · p. 26
  • M planted columns with pairwise disjoint check sets, disjoint from the 6-cycle checks, give degNS(Ecnt) ≥ M + 1 for every t ≥ 2 and b ≥ 0.The supplied result states that such columns exist with a lower bound on M, and gives M = Z − 4 for the specified H(3, L, Z) family.Source: D. Planted 6-Cycles and Larger Supports · p. 26
  • For supports of size at most three in the stated weight-three setting, Φ(S) is at least 3, 4, or 3 for sizes one, two, or three, respectively, so b ≤ 2 is infeasible.A singleton has Φ = 3, making the problem feasible for b ≥ 3.Source: D. Planted 6-Cycles and Larger Supports · p. 26

COUNTING VERSUS LOCAL ENCODINGS: BOUNDS PROVED IN SECTIONS V–VII

Across the listed infeasible instances, counting encodings require degree growing linearly with block length while local degrees stay bounded for fixed parameters and bounded check degree. The minimum-distance results use planted codeword structures, with asymptotic separation established for specified arrays of circulant permutation matrices.

E. Counting Versus Local Encodings

VI. MINIMUM-DISTANCE CERTIFICATION

  • For b = 0, certifying dmin ≥ t + 1 is the infeasibility problem of excluding nonzero codewords of weight at most t.Theorem 30 plants single columns from a codeword with columns removed, or whole codewords when O is empty.Source: §VI · p. 28, A. Single Planted Columns from a… · p. 28

A. Single Planted Columns from a Codeword

  • For a minimum-weight codeword, the b = 0 problem is infeasible exactly when t ≤ dmin − 1; Theorem 30 provides a counting lower bound in that range.The local degree is at most t + K + 1 in the same range.Source: A. Single Planted Columns from a… · pp. 28–29
  • Using s ≥ 2 removed codeword columns allows |O| to exceed t + 1 and extends the covered t range down to dmin − 2s.The general target is needed for this extension beyond the s = 1 planting.Source: A. Single Planted Columns from a… · p. 29

B. The Packing Limit and the Choice of Codeword

  • The planting bound is optimal among plantings of this kind when the planted columns cover every check outside C(C), but it need not equal the true Nullstellensatz degree.Packing capacity depends on the chosen codeword’s check neighborhood and its distribution over row blocks, not just its weight.Source: B. The Packing Limit and the Choice of… · p. 29

C. An Asymptotic Separation for Arrays of Circulants

  • For fixed w and L ≥ w + 1, the specified girth-six arrays of circulant permutation matrices have counting degree Θ(n) and local degree O(1) for minimum-distance certification.The result uses a uniform bound on dmin; no asymptotic claim is made for L ≤ w.Source: C. An Asymptotic Separation for Arrays… · pp. 29–30

D. Planted Codewords

Planted codewords give counting-encoding lower bounds across infeasible support bounds; examples compare planting strategies. Planted pairs extend linear lower bounds to odd column weight in specified settings.

D. Planted Codewords

  • M pairwise check-disjoint supports of nonzero codewords of common weight k give counting degree at least M + 1 for every t ≥1 and b ≥0.For b = 0, this applies whenever t < dmin; the construction needs no structure inside the codewords.Source: D. Planted Codewords · pp. 30–31

E. Examples

  • On H(3, 5, 47), 44 planted columns yield counting degree at least 45 for t = 2 to 5, versus local degree at most 8 at t = 5.The 44-column planting is perfect and optimal; 15 pairwise check-disjoint minimum-weight codewords give the weaker bound 16.Source: E. Examples · pp. 31–32

VII. ODD COLUMN WEIGHT: PLANTED PAIRS, PATHS AND STARS

A. Planted Pairs

  • For column weight w, disjoint planted dominoes yield counting degree at least M + 1, while local certificates have degree at most b + K + 2 when t = 1 and 0 ≤ b ≤ w −1.A domino is two weight-w columns sharing exactly one check.Source: A. Planted Pairs · p. 33

B. When Paths and Stars Exist

  • Girth six alone guarantees neither an induced path nor a star: in projective-plane incidence matrices every two columns share a check.For odd column weight, the counting degree at (t, b) = (1, 0) remains unresolved for girth-six families without these structures or other applicable plantings.Source: B. When Paths and Stars Exist · p. 34

C. Counting Dominoes

Domino plantings yield linear counting-degree lower bounds for regular codes of girth at least eight and specified array codes, while local degree remains bounded. The section also contrasts this with constant-degree behavior when one cardinality bound is local.

C. Counting Dominoes

  • For fixed (w, d), counting degree is Θ(n) and local degree O(1) for (w, d)-regular matrices of girth at least 8 and specified array codes, including odd w at b = 0.The array condition is L ≥2 and Z > (w −1)(L −1).Source: C. Counting Dominoes · pp. 34–35

A. Four Exact Encodings

  • The four exact encodings independently choose local or counted forms for the support and syndrome bounds, while retaining identical solutions.The first letter denotes support encoding and the second syndrome encoding.Source: A. Four Exact Encodings · p. 36

C. Why the Growth Needs Both Counters

On cycle codes, growth in counting-encoding degree requires both cardinality constraints to be counted. The planting lower bound is sharp among its pullbacks, but that optimality does not establish the exact degree in general.

C. Why the Growth Needs Both Counters

  • On cycle codes, either local cardinality bound supplies global information that yields a constant-degree contradiction; only counting both leaves two sums for a knapsack planting.The planted substitutions cannot be applied when either bound is local, and bounded degree for mixed encodings beyond cycle codes remains open.Source: C. Why the Growth Needs Both Counters · p. 37

IX. OPTIMALITY AND LIMITS OF THE PLANTING METHOD

A. Limits of the Knapsack Argument

  • For the knapsack functional, products through degree M vanish but not all products of degree M + 1.The theorem's optimality claim concerns this pullback method, not the Nullstellensatz degree itself.Source: A. Limits of the Knapsack Argument · p. 38

B. A Cap for Pullback Arguments

  • Under the stated substitution conditions, a pullback into N Boolean variables proves at most degree N + dG.For Theorem 14's substitution, N = M, so its bound is optimal among such pullbacks; this cap does not depend on circulant or quasi-cyclic structure.Source: B. A Cap for Pullback Arguments · pp. 38–39

C. Sharpness of the Planted Bound

The planted lower bound M + 1 is attained in a constructed family and in partner-containing examples, while cycle-code data show a gap above that bound. The paper also states scope limits on these results and its exact computational checks.

C. Sharpness of the Planted Bound

D. Partners

  • With partners in every planted check, degNS = M + 1 for every M ≥3, despite planted checks having degree two.The construction's partner has weight M, so it does not establish sharpness for bounded-degree codes.Source: D. Partners · p. 41

E. Cycle Codes

  • On cycle codes, the counting degree is exactly two above M + 1 in the reported cases.The largest single-column planting cannot reach the conjectured degree by the pullback bound; the paper reports not finding a target of maximal degree.Source: E. Cycle Codes · p. 42

F. Further Limitations

  • Odd column weight at (t, b) = (1, 0) remains open for girth-six families lacking induced paths, stars, or many check-disjoint short codewords.Other stated limits include infeasibility needing separate proof, characteristic zero, and no result for mixed encodings from the planting substitution.Source: F. Further Limitations · p. 42

X. EXACT COMPUTATIONAL VERIFICATION

  • Computed degree bounds are backed by certificates or functionals verified exactly over Q; minimum distances use exhaustive enumeration.Packing optima are proved by optimization solvers.Source: §X · p. 42

A. Exact Degree Computations

Exact computations and independent checks substantiate the paper’s degree claims and certificate examples. The discussion weighs encoding size against proof degree and identifies unresolved boundaries for both encodings.

A. Exact Degree Computations

  • Exact degree tests use rational linear algebra, reconstruct modular candidates over Q, and verify certificates or functionals exactly.Symmetries reduce candidate searches to monomial orbits; the reported computations include exact values for local systems and OPPn.Source: A. Exact Degree Computations · pp. 43–44

B. Identity and Planting Checks

  • Exact checks cover the identities and planting tests, with independent implementations agreeing on codeword weights, configurations, and packing optima.The computations also test planted functionals on full counting encodings, including counters and selectors.Source: B. Identity and Planting Checks · p. 44

C. QC-LDPC Certificates

  • Every generated QC certificate attains degree t+b+K+1; four cases improve on earlier certificates by one degree and use 23%–48% fewer terms.Two independent exact-arithmetic verifiers accept all five certificates and reject 48 corrupted files; the lifted 5G NR example tests the pipeline at a feasibility boundary, not code performance.Source: C. QC-LDPC Certificates · p. 45

XI. DISCUSSION AND OPEN PROBLEMS

  • The local encoding trades more generators for bounded degree, while the counting encoding has degree Θ(n) on several code families and minimum-distance certificates.The discussion suggests local cardinality constraints when certificates are a deliverable, while noting that proof degree is not running time and neither encoding is cheaper in every respect.Source: §XI · pp. 45–46
  • Open local-encoding questions include whether degree two persists at check degree at least four and whether low degree survives without support obstructions.The discussion also leaves open degree behavior beyond cycle codes and (t, b) = (1, 0).Source: §XI · p. 46
  • Open counting-encoding questions include growth for odd-weight families lacking specified planted configurations and exact degree beyond the planted bound.The exact values for OPPn and cycle-code cases are also left unresolved in the cited discussion.Source: §XI · p. 46

XII. CONCLUSION

  • The conclusion contrasts bounded local degree with linear counting lower bounds across cycle, regular, and array-based code settings.It states that planted-pair bounds extend to odd column weight with no unsatisfied checks and are optimal among such pullbacks, while exact counting degree beyond the planted bound remains open.Source: §XII · pp. 46–47
Loading 2610.32171v1…