PaperlayerView exact revision on arXiv

Source-linked AI summary

Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality

Aryeh Lev Zabokritskiy

arXiv:2609.01474v1cs.ITmath.CO

TL;DR

The paper asks how to construct and analyze low-redundancy codes for vertex-induced erasures on looped complete graphs, especially over binary fields. It combines cyclic, multi-slope, and completion constructions with exact metric-ball analysis and complementary clique duality. The results include unconditional infinite triple-node families, finite Singleton-optimal examples, general fixed-radius bounds, and an optimal node–clique correspondence, subject to stated arithmetic and completion limitations.

  • Problem

    Binary graph codes for a fixed number of node erasures require constructions and metric analysis beyond existing large-alphabet or asymptotic results.

  • Method

    The paper uses local parity-check rank criteria, cyclic slopes and Frobenius-based edge skeletons, subspace-arrangement inclusion–exclusion, and complementary coordinate duality.

  • Results

    The paper obtains an unconditional infinite triple-node family with redundancy 3n−2, Singleton-optimal triple-node codes at n=6,8,10,12, multi-slope constructions, exact ball formulas, and node–clique duality.

  • Takeaways & Limitations

    The results separate binary construction questions from prime-power metric enumeration and connect optimal node-erasure codes to complementary clique-erasure codes.

Abstract

from arXiv · show

We study linear codes whose coordinates are the ordinary edges and self-loops of complete undirected graphs; a node erasure removes all coordinates incident with a failed vertex. The construction results are binary. For triple-node erasures, we extend the published cyclic construction by allowing a suitable cyclic check slope to depend on the prime graph length. An explicit determinant test proves that one of three fixed slope choices works at infinitely many prime lengths, unconditionally, and gives redundancy $3n-2$, one bit above the graph Singleton bound. We also give Singleton-optimal triple-node codes at $n=6,8,10,12$, together with a general ordinary-edge framework that isolates the remaining loop-completion problem. When $2$ is primitive modulo an odd prime $n$, a binary multi-slope construction corrects every $ρ$-node erasure for $2\leqρ<n$, with redundancy $ρn-(ρ-1)$ in the range $2\leqρ\leq(n+1)/2$. Returning to arbitrary prime powers, we derive exact generating transforms and inclusion--exclusion formulas for node-metric ball volumes, fixed-radius asymptotics, and packing, existence, and covering bounds. Finally, for the complementary clique-erasure metric, we obtain an exact weight enumerator and a Singleton-optimal node--clique duality.

1 Introduction

The paper targets binary graph codes in the low-redundancy, fixed-node-failure regime, where exact constructions remain difficult despite broader graph-code progress. It develops cyclic and multi-slope constructions, finite optimal completions, metric-ball formulas, bounds, and node–clique duality.

  • Motivation: Binary graph codes place symbols on complete-graph edges and loops, while a failed vertex erases its entire incident neighborhood.The node distance is the minimum number of vertex neighborhoods covering the support difference.
  • Scope: The paper organizes constructions, metric balls, and duality around the coordinate sets erased by fixed failed-vertex sets.These sets become local parity-check rank conditions, subspace arrangements, and complementary clique coordinates.
  • Cyclic constructions: 3n−2 redundancy extends the cyclic triple-node construction to length-dependent slopes chosen from {2, −3, −15}, with infinitely many admissible prime lengths unconditionally.The determinant test separates local cyclic-minor conditions from primitive-root conditions and uses Heath-Brown’s theorem.
  • Metrics and duality: For arbitrary prime powers, the paper derives node-metric enumerators, ball-volume formulas, asymptotics, packing and covering bounds, and a complementary clique-erasure duality.Singleton-optimal ρ-node codes are dual to Singleton-optimal (n−ρ)-clique-erasure codes.
  • Scope boundaries: The cyclic arithmetic results have different scopes: triple-node infinitude is unconditional, whereas the fixed-slope and general multi-slope infinitude remains tied to Artin’s conjecture.The unconditional theorem does not identify one slope that works infinitely often and does not extend to ρ > 3.

2 Definitions and Preliminaries

The preliminaries define looped complete-graph words, node weight and distance, star and clique coordinate sets, and parity-check criteria for correcting node erasures. They also establish the graph Singleton bound and a vertex-descent property for optimal codes.

  • Graph model: Graph words assign q-ary labels to all self-loops and unordered edges of a complete graph on n vertices.The ambient alphabet is a prime-power field, and graph words can be represented by symmetric labeling matrices.
  • Node metric: Node weight is the minimum vertex-cover size of the support graph, with every nonzero loop requiring its own vertex in the cover.The induced node distance is translation-invariant and measures support differences through vertex covers.
  • Erasure coordinates: Failed vertices generate star-coordinate sets containing their incident edges and loops, while complementary coordinates form induced cliques.These two coordinate families support the node-erasure and complementary clique-erasure metrics.
  • Correction criterion: A linear code corrects every set of at most ρ node erasures exactly when every corresponding erased-column submatrix of a parity-check matrix has independent columns.Unique correction of any erased coordinate set is equivalent to column independence.
  • Singleton bound: Puncturing to the surviving clique yields the graph Singleton bound, and equality defines a Singleton-optimal node-erasure code.The bound follows because the puncturing map must be injective for every failed ρ-set.
  • Vertex descent: An optimal ρ-node-erasure code on n vertices descends to an optimal (ρ−1)-node-erasure code on n−1 vertices over the same field.The construction quotients the parity-check image by the span of a chosen vertex’s incident columns.

3 Cyclic Slope Constructions

The section develops cyclic parity-check constructions by reducing triple-node recovery to explicit local determinants and an arc condition. It then extends the approach to multiple erasures, proving unconditional infinitely many triple-node lengths while identifying the redundancy limits of the broader construction.

  • Construction framework: The erased-column criterion requires parity-check columns on every failed-vertex neighborhood to be independent.For triples, neighborhood and diagonal checks are retained while cyclic slope checks are varied; for larger erasure sets, additional Frobenius slopes address successive local ambiguities.
  • Triple-node determinant test: A primitive cyclic slope corrects every triple-node erasure exactly when the associated projective orbit is an n-arc.The local determinant test is equivalent to full rank on each erased triple, and the orbit is an n-arc precisely when all relevant three-column minors are nonzero.
  • Triple-node determinant test: The resulting infinite triple-node family has redundancy 3n−2, one bit above the graph Singleton value 3n−3.Its redundancy is also two below the Schmidt benchmark 3n; n = 17 is covered by slope −3 but not by the published fixed-slope hypothesis.
  • Multi-slope construction: The multi-slope code corrects every set of at most ρ node erasures when 2 is primitive modulo an odd prime n and 2 ≤ρ<n.The construction claims its competitive redundancy comparison only through ρ ≤(n+1)/2; beyond that range, overlapping Fourier supports can create additional dependencies.

4 A Uniform Frobenius–Moore Edge Skeleton and Finite Triple Completions

The section constructs a binary ordinary-edge skeleton with full local rank for every failed vertex set, then reduces optimal completion to a loop-basis condition. For triple failures, exact completions achieve the Singleton bound at four lengths, while uniform completion remains open.

  • Uniform edge skeleton: The construction assigns Frobenius-layered binary columns to ordinary edges so every failed ρ-set has a full-rank erased-edge block.The edge skeleton is built before loops are added and is designed to work simultaneously for every failed set.
  • Uniform edge skeleton: The local rank proof converts a column relation into an Eulerian auxiliary graph and eliminates it through exterior-square and shifted-Frobenius descent.The first block forces Eulerian structure; the remaining Frobenius blocks force the exterior encoding, and hence the relation, to vanish.
  • Loop completion: For ρ failures, Singleton-optimal completion requires a common quotient whose ρ loop images form a basis for every failed set.For triples, the common quotient is trivial, so the three loop columns must span the remaining three dimensions directly.
  • Finite triple completions: Binary Singleton-optimal triple-node codes exist at n = 6, 8, 10, 12 through explicit finite-field loop assignments.The certificates use normal elements, field elements, and binary parameters to complete the uniform edge skeleton.
  • Finite triple completions: A uniform solution to the triple-node loop-completion criterion remains the remaining optimal-triple problem beyond the four exact lengths.The edge skeleton and exact three-dimensional criterion apply more broadly, but no general completion is supplied.

5 Node-Weight Enumerators

This section develops two complementary descriptions of node-weight enumerators: loop conditioning reduces the problem to simple-graph vertex-cover enumeration, while star-subspace unions yield exact inclusion–exclusion formulas and fixed-radius asymptotics.

  • Loop-conditioning transform: Conditioning on the vertices with nonzero loops transforms the q-ary looped enumerator into a sum over residual simple graphs weighted by vertex-cover number.Loops and incident labels are counted first; the remaining support graph contributes through its vertex-cover enumerator.
  • Loop-conditioning transform: The residual simple-graph polynomial is the hard enumerative core because it counts graphs by vertex-cover number, equivalently by independence number.The transform is exact, but computing this residual family remains difficult in full generality.
  • Star-subspace representation: A node ball of radius t is the finite union of linear subspaces supported on the coordinate stars of t-vertex sets.This representation follows because node weight at most t means that the support is contained in some erased star coordinate set.
  • Inclusion–exclusion: Venn profiles encode every intersection of star subspaces using only membership-signature counts, enabling exact finite inclusion–exclusion formulas.For fixed inclusion–exclusion order j, the profile uses 2^j signature variables rather than labeled cover families.
  • Asymptotics: The exact profile sum is finite-dimensional at each fixed inclusion–exclusion order, while the first two orders determine fixed-radius leading asymptotics through pair intersections.The resulting profile reduction avoids enumerating families of labeled cover sets.
  • Finite verification: The binary ambient node-weight distributions and cumulative ball volumes were also verified by exhaustive enumeration.These values are reported in Table 2.

6 Bounds from Ball Volumes

The exact node-ball volumes feed directly into packing, existence, and covering bounds for graph codes. Their asymptotics expose an additional logarithmic cost for selecting failed-node sets beyond the graph Singleton scale.

  • Packing and Gilbert bounds: Packing and Gilbert bounds specialize the classical radius-ball arguments to the translation-invariant node metric using the computed ball volumes.The upper bound uses disjoint radius-t balls, while the lower bound uses balls around a maximal distance-d code.
  • Random-linear existence: A projective random-linear argument constructs linear codes of prescribed node distance with a sharper finite-length redundancy bound than unprojectivized counting can provide.The refinement counts forbidden projective lines rather than individual nonzero words.
  • Covering bounds: Covering numbers are bounded between the ambient-space-to-ball-volume ratio and its harmonic-factor enlargement.Translation invariance makes the fractional cover number exactly the volume ratio, and greedy set cover supplies the harmonic upper bound.
  • Geometric interpretation: The extra logarithmic term measures the cost of selecting which maximal coordinate subspace contains the error, distinguishing node balls from Hamming balls.This geometric selection cost is invisible from the dimension of a single star union.

7 The Complementary Clique Metric

The complementary clique metric treats induced cliques as erasure patterns, enabling exact enumeration and a dual characterization of Singleton-optimal codes. The node–clique correspondence depends on the star–clique partition and the specified edge-coordinate dual.

  • Clique metric: The clique metric is translation-invariant, and correcting every induced clique on at most µ vertices is equivalent to minimum clique distance at least µ + 1.A nonzero loop contributes one active vertex, while a nonzero ordinary edge contributes two.
  • Clique metric: The clique Singleton bound follows from linear independence of parity-check columns indexed by each erased induced clique.Equality defines Singleton-optimality for µ-clique erasures.
  • Exact enumerator and generating function: Theorem 31 gives an exact clique-weight enumerator, ball-volume formula, and formal exponential generating function obtained by counting graph words with prescribed active vertex support.The generating-function identity is formal because, for q > 1, the final series has zero analytic radius.
  • Node–clique duality: The star–clique coordinate partition converts the node-erasure criterion for a code into the clique-erasure criterion for its dual.The argument uses the edge-coordinate inner product; in characteristic two, the Frobenius pairing on full symmetric matrices is not the relevant pairing.
  • Node–clique duality: Singleton-optimal ρ-node codes are dual to Singleton-optimal (n −ρ)-clique-erasure codes, with the converse also holding.Optimal double-node codes yield an unconditional infinite family of optimal binary (n −2)-clique-erasure codes, and optimal triple-node completions yield such codes at n = 6, 8, 10, 12.
  • Node–clique duality: The duality theorem requires its dimension hypothesis, since the zero code and ambient-space dual provide a counterexample without it.The result is a dual reformulation of the full-rank clique-minor criterion.

8 Discussion and Open Problems

The discussion isolates unresolved construction and enumeration problems while clarifying how the paper’s fixed-failure regime relates to broader asymptotic graph-code results. The main bottlenecks are optimal triple-node families, simultaneous loop completion, and efficient metric-ball enumeration.

  • Open constructions: 3n −3 remains the target redundancy for an infinite Singleton-optimal triple-node family.The paper’s explicit triple-node construction has redundancy 3n −2, so the optimal constructive problem remains open.
  • Open constructions: The multi-slope family improves the Schmidt benchmark for 2 ≤ρ ≤(n + 1)/2, with an n-independent redundancy gap that grows quadratically in ρ.Within the template, closing the gap requires dependencies coupling different slope families, not merely another independent family of n cyclic checks.
  • Open constructions: For 3 ≤ρ ≤n, optimal completion requires a common quotient of dimension ρ(ρ−3)/2 and a simultaneous ρ-loop completion.At ρ = 3 the common quotient is trivial, and exact completions are known at n = 6, 8, 10, 12.
  • Open constructions: An optimal four-failure family would imply an optimal triple-failure family at smaller lengths, while the alternative four-star edge-quotient route still has an unresolved loop-completion step.Thus bilinear-form constructions provide a structural reduction rather than a finished construction.
  • Metric enumeration: The Venn-profile formula captures overlaps among maximal subspaces in node-metric balls, while the pair formula determines fixed-radius asymptotics.Open questions include recurrences for simple-graph polynomials, efficient profile computation, and a finer multivariate transform.
  • Asymptotic perspective: The fixed-distance regime studied here complements constant-relative-distance asymptotic constructions, motivating explicit families that interpolate between them.The comparison is with the asymptotic work of Kopparty, Potukuchi, and Sha.

Computational Reproducibility

The paper reports exact-arithmetic computer-assisted checks and archives the materials needed to reproduce every finite verification.

  • Computational Reproducibility: All reported computer-assisted verifications use exact arithmetic and are accompanied by a versioned Zenodo package.The archive includes source code, certificate data, execution instructions, recorded outputs, and cryptographic checksums.

Appendix A Proof of the Local Determinant Criterion

The appendix proves the local determinant criterion by reducing failed-triple syndromes to cyclic algebra, Eulerian edge structure, and slope-factorization conditions. Nonzero determinants force the local word to vanish, while a zero determinant constructs a nonzero erased-supported codeword.

  • Criterion and reduction: The failed-triple recovery target is exact: all determinants Dk(a, b) must be nonzero to exclude nonzero words supported on the three failed stars.The proof tracks the kernel of the parity-check matrix on one failed triple.
  • Algebraic setting: The cyclic-algebra argument uses the nontrivial Chinese-remainder component Rn, with the x = 1 component checked separately to recover the full group-algebra syndrome.Rn is reduced for odd n but need not be a field.
  • Eulerian edge reduction: Neighborhood checks reduce the ordinary-edge part to an Eulerian matrix whose cycle-space coordinates lie in the span of δ1 ∧Rn and δ2 ∧Rn.The edge matrix is represented as B = C(u1, w1) + C(u2, w2).
  • Diagonal and slope checks: Diagonal checks normalize the edge parameters so that δ1β1 + δ2β2 = 0, leaving a constrained coset for the remaining cyclic-algebra variable.The proof describes this as reducing the coordinate to one coset y + F2 before applying slope checks.
  • Diagonal and slope checks: The slope checks become a polynomial factorization whose middle factor is tested by evaluating at nontrivial n-th roots of unity.Its coefficients correspond to the slope checks after exponents are reduced modulo n.
  • Nonvanishing direction: When λ is primitive and every Dk(a, b) is nonzero, the relevant cyclic-algebra factor is a unit, forcing the Eulerian edge pattern and all loops to vanish.Primitivity leaves only the exponent orbits {0} and Zn \ {0}, which forces the remaining variable into F2.
  • Vanishing direction: If some Dk0(a, b) vanishes, the construction produces a nonzero erased-supported word whose neighborhood and slope checks all vanish.Distinct elements of the relevant ideal intersection yield distinct local codewords, giving local nullity at least d2 −1.
  • Rank consequence: Fourier invertibility shows that the primitive-slope check matrix has rank 3n −2, with the two dependencies given by sums of neighborhood rows and slope rows.The argument uses odd n and separability of xn−1.

Appendix C Proof of the Multi-Slope Theorem

The appendix proves the multi-slope construction by reducing correction to algebraic identities and rank to Fourier analysis. It establishes correction and computes the complete row-dependency space, yielding the stated redundancy.

  • Proof strategy: The proof separates correction from rank: Frobenius–Moore and product equations force the exterior element to vanish, while Fourier coordinates handle row dependencies.The correction argument then eliminates the remaining edge and loop components.
  • Correction proof: Frobenius descent inductively converts the product and Frobenius–Moore equations into vanishing exterior-square relations.The induction normalizes one vector, proves intermediate relations vanish, and concludes the remaining vectors lie in the preceding span.
  • Correction proof: The neighborhood, slope, diagonal, and internal-edge syndromes instantiate the lemma’s hypotheses, after which injectivity eliminates the edge component and characteristic-two cancellation removes the loops.A pattern on fewer than ρ failed stars is embedded into a ρ-star support for the argument.
  • Algebraic setup: Under the primitive-root hypothesis, the reduced algebra becomes a field, and the cyclic elements used in the proof are linearly independent on every proper failed set.This supplies the independence assumptions needed by the Frobenius-descent lemma.
  • Rank proof: Fourier analysis shows that every row dependence is constant within the neighborhood family and within each higher-slope family.The absence of equal, inverse, and self-inverse slopes isolates each Fourier coefficient.
  • Rank proof: The resulting dependency space has one constant for the neighborhood family and one for each higher-slope family, producing redundancy ρn −(ρ −1).Each constant family is a dependence because every non-loop edge occurs twice.

Appendix D

Appendix D studies whether the published triple-node code can be extended by one dimension while preserving correction. It gives an affine extension criterion and exact odd-dependency certificates ruling out that route at several admissible lengths.

  • Scope: The appendix limits only the one-dimensional extension route for the published slope-two check space, not all primitive-slope constructions or all optimal codes.Optimal constructions nevertheless exist at four finite lengths.
  • Extension criterion: A one-dimensional extension is a correcting supercode whose parity-check space is a codimension-one subspace of the published check space.For each failed triple, the extension condition is expressed through the associated left-null vector.
  • Extension criterion: The extension exists exactly when a hyperplane avoids every failed-triple null vector, equivalently when the affine system in Proposition 36 is solvable.The restriction map on each failed triple has kernel spanned by its null vector.
  • Obstruction: An odd-cardinality dependency satisfying the stated system certifies that no correcting one-dimensional extension exists.Taking the inner product with the dependency yields the contradiction 0 = 1.
  • Obstruction: Exact certificates at n = 5, 11, 13, 19 show that deleting one independent check cannot solve the missing-bit problem at those lengths.At n = 13, eleven triples already satisfy the obstruction system.

Appendix E Dual Weight Data and the Failure of a Univariate MacWilliams Transform

Appendix E explains that the node metric does not support a univariate MacWilliams transform because its irredundant star cover is not partitioned into equal-sized blocks.

  • Structural obstruction: For n ≥2, the node-star cover is irredundant: each star uniquely contains its self-loop, while distinct stars overlap on ordinary edges.The cited criterion therefore rules out determining the dual node-weight enumerator from the primal univariate enumerator.

A two-vertex witness.

The two-vertex witness demonstrates concretely that equal primal node-weight enumerators can produce unequal dual enumerators. It motivates refining dual analysis with support-intersection data rather than node weight alone.

  • Witness: The witness compares two two-vertex codes with the same node-weight enumerator D2(z) = 1 + z.Their edge-coordinate duals are specified by different constraints.
  • Witness: Their dual node-weight enumerators differ: one is 1 + z, while the other is 1 + 2z + z2.Thus equal primal enumerators can have unequal dual enumerators.
  • Consequence: The exact Fourier identity remains available, but a useful dual theory must refine node weight with intersection data such as support orbit type.The witness shows that the dual character sum is not determined by wtN(y) alone.
Loading 2609.01474v1…