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

1 Introduction

• Node erasures delete every edge and loop incident with a failed vertex, and their distance is the vertex-cover number of the support difference; this work targets fixed failures rather than linearly growing distance.The model retains self-loops, unlike the binary simple-graph model discussed in the related asymptotic work.Source: §1 · p. 2

1.1 Contributions

• At infinitely many prime lengths, choosing λ from {2, −3, −15} yields binary triple-erasure codes with redundancy 3n−2, one above Singleton; this infinitude is unconditional.For 2 primitive modulo an odd prime n, the multi-slope construction corrects every ρ-node erasure for 2 ≤ ρ < n, with redundancy ρn−(ρ−1) when ρ ≤ (n+1)/2; unconditional infinitude is not established for ρ > 3.Source: §1 · p. 3, §1.1 · pp. 3–4
• At n = 6, 8, 10, and 12, explicit binary triple-node codes attain Singleton redundancy 3n−3, while a general ordinary-edge skeleton reduces optimal completion to a common-quotient problem.An infinite optimal four-erasure family would imply optimal triple-erasure codes at immediately smaller lengths.Source: §1.1 · pp. 3–4, §1 · p. 3
• For prime-power q, the paper derives exact node-ball transforms and inclusion–exclusion formulas, plus packing, Gilbert, random-linear existence, and covering bounds; random-linear redundancy is at most ρ log_q n + O_q,ρ(1) above Singleton for fixed ρ.The ball formulas include second-order Bonferroni bounds.Source: §1.1 · p. 4
• For the complementary clique-erasure metric, an exact weight enumerator and erasure-pattern duality show that Singleton-optimal ρ-node codes correspond to Singleton-optimal (n−ρ)-clique codes.The published optimal double-node codes therefore give an infinite family of optimal binary (n−2)-clique-erasure codes.Source: §1.1 · p. 4

2 Definitions and Preliminaries

• A q-ary graph word labels every unordered vertex pair, including self-loops, over Fq and can be represented as a symmetric labeling matrix; q is a prime power.The coordinate set consists of all self-loops and ordinary edges of the complete graph.Source: §2 · p. 5
• Node weight is the minimum size of a vertex cover of the support graph, with a nonzero loop requiring its vertex; node distance is translation-invariant.The support graph has all vertices, including isolated ones, and edges exactly at nonzero coordinates.Source: §2 · p. 5
• For a vertex set S, star coordinates describe its node-erasure pattern, while complementary induced-clique coordinates include the loops and support puncturing arguments.The node-erasure pattern generated by S includes each failed vertex’s loop coordinate.Source: §2 · p. 6
• An erased coordinate set is correctable exactly when its parity-check columns are linearly independent; for node failures, the erased columns are those in the failed vertices’ stars.Each ordinary edge and loop indexes a parity-check column.Source: §2 · pp. 6–7
• Puncturing to the surviving looped clique gives the graph Singleton bound because distinct codewords must have distinct restrictions there after any rho node erasures.If restrictions coincide, their difference is supported on erased stars, so unique correction forces that difference to be zero.Source: §2 · p. 7
• A Singleton-optimal linear rho-node-erasure code on n vertices yields a Singleton-optimal (rho−1)-node-erasure code on n−1 vertices over the same field, for 2≤rho≤n.The construction quotients out the span of columns incident with a fixed vertex.Source: §2 · pp. 7–8

3 Cyclic Slope Constructions

• The section frames both constructions as solving the erased-column rank test: checks on every failed vertex set must be independent on the erased coordinates.For triples, it varies cyclic slope checks while retaining the neighborhood and diagonal checks; for more failures, it adds Frobenius slopes.Source: §3 · p. 8

3.1 A primitive-slope triple-node construction

• For primitive λ, a failed triple is recoverable exactly when its local determinants are all nonzero, equivalently when the cyclic projective orbit Γn,λ is an n-arc.The determinants are the 3-by-3 minors on the corresponding orbit columns.Source: §3.1 · p. 10
• Infinitely many prime lengths admit one of three fixed primitive slopes yielding triple-node correction with redundancy 3n-2, one above the graph Singleton value.At n = 17, the new slope −3 applies where the published fixed-slope hypothesis does not.Source: §3.1 · p. 14

3.2 The multi-slope construction

• For odd prime n with 2 primitive, the multi-slope code corrects every set of at most ρ node erasures for 2≤ρ<n; for ρ≤(n+1)/2, redundancy is ρn-(ρ-1).The neighborhood and diagonal checks leave an ordinary-edge ambiguity with ρ−1 field parameters; ρ−2 added Frobenius slope families force it to zero.Source: §3.2 · pp. 14–15
• The local correction condition holds because the slope-family equations force w = 0, which implies the ordinary-edge labels and then all loop symbols vanish.The ordinary-edge support is Eulerian, and the cycle-space map is injective; together with diagonal checks, this yields X = 0.Source: §3.2 · pp. 16–17
• For odd prime n with 2 primitive modulo n, the Schmidt benchmark has redundancy ρn for 2 ≤ ρ < (n+1)/2 and is the zero code with redundancy N = ρn at ρ = (n+1)/2.For graph words supported on ρ coordinate stars, the associated symmetric matrix has rank at most 2ρ, so a code of rank distance 2ρ + 1 corrects these node erasures.Source: §3.2 · p. 17
• For ρ = 2, the construction recovers the published optimal code with redundancy 2n − 1; for ρ = 3, it gives redundancy 3n − 2, one bit above Singleton.The correction assertion also holds for (n+1)/2 < ρ < n, but no competitive redundancy claim is made there because selected powers of two may include inverse slopes, causing Fourier-support overlap and additional row dependencies.Source: §3.2 · p. 17

Uniform edge skeleton

• Every failed set Q of size ρ has an erased ordinary-edge block of full column rank.In the proof, the first block makes a putative relation graph Eulerian, and the remaining Frobenius blocks eliminate it.Source: §4 · pp. 20, 23

Quotient and loop completion

• For 3≤ρ≤n, Singleton-optimal completion requires a common quotient kernel disjoint from every erased-edge span and loop images forming a basis of the residual quotient.The criterion separates preserving edge rank under projection from completing each erased set with its ρ loop columns.Source: §4 · p. 24

Finite triple completions

• At n=6, 8, 10, and 12, exact loop completions yield Singleton-optimal binary triple-node codes with redundancy 3n−3; a uniform completion remains open.The verification checks all 416 failed triples across the four lengths.Source: §4 · pp. 25–26

Contribution and prior work

• The Frobenius alternating layers are established; the graph-code contribution realizes them on affine-frame edges and proves simultaneous rank for every failed set.The section identifies the finite-field layers with prior alternating rank-metric constructions, while distinguishing the edge realization and its node-erasure rank guarantee as its contribution.Source: §4 · pp. 18, 26

5 Node-Weight Enumerators

• Translation invariance makes ordered-pair distance counts reducible to the ambient node-weight distribution.Every radius-t ball is a translate of the ball around zero and has the same cardinality.Source: §5 · pp. 26–27

5.1 A loop-conditioning generating transform

• Conditioning on nonzero loops uniquely reduces the looped-graph enumerator to a residual simple-graph vertex-cover distribution.Nonzero-loop vertices are forced cover vertices; incident non-loop labels are arbitrary, leaving the support graph on the remaining vertices as the enumerative kernel.Source: §5.1 · pp. 27–28

5.2 Balls as a subspace arrangement

• Representing a ball as a union of t-star subspaces yields exact inclusion–exclusion via Venn-profile intersection dimensions and a fixed-order reduction to 2j profile variables.For each fixed inclusion–exclusion order j, the profile method avoids enumerating families of labeled cover sets.Source: §5.2 · pp. 28–30

5.3 Second-order formula and asymptotics

• Pair-intersection counts give second-order Bonferroni bounds and fixed-radius asymptotics; cross edges between the two covers’ exclusive vertices contribute to their intersection.For fixed q and t, the first-order term determines the leading asymptotic, and the same leading asymptotic holds for ambient node-weight counts.Source: §5.3 · pp. 30–31

Packing and Gilbert bounds

• Translation invariance gives sphere-packing and Gilbert bounds by substituting the exact node-ball volumes, without requiring distance regularity.The upper bound follows from disjoint radius-t balls, and the lower bound from radius-(d −1) balls around a maximal distance-d code.Source: §6 · p. 32

Asymptotic bounds

• For fixed radius, the binomial-coefficient estimate yields the asymptotic form, with the logarithmic loss beyond the graph Singleton bound reflecting the choice among possible failed-node sets.Geometrically, this is the cost of selecting which maximal coordinate subspace contains the error, a feature absent from a single star union and distinguishing node balls from Hamming balls.Source: §6 · pp. 33–34

Projective ball-volume linear bound

• For every n, prime power q, and 1 ≤ d ≤ n + 1, a linear code exists; for d ≥ 2 its redundancy is bounded using the number of projective lines in the radius-(d −1) ball.Projectivizing is valid because each node ball is invariant under nonzero scalar multiplication; for q = 3, n = 2, d = 2, the bound gives redundancy at most 2 rather than 3 from the unprojectivized bound.Source: §6 · pp. 33–34

Covering bounds

• If v = q^N and b = |B_R|, the minimum number of radius-R centers needed to cover the space is at least v/b and at most H_b v/b ≤ (1 + ln b)v/b.Uniform fractional-cover weights give the lower bound, while the greedy set-cover bound gives the harmonic-factor upper bound.Source: §6 · p. 34

7 The Complementary Clique Metric

• Clique weight defines a translation-invariant metric, and correcting every induced-clique erasure on at most µ vertices is equivalent to minimum clique distance at least µ + 1.A nonzero loop activates one vertex, while a nonzero ordinary edge activates both; thus one edge has node weight one but clique weight two.Source: §7 · pp. 34–35

7.1 Exact enumerator and generating function

• The section gives exact clique-weight polynomial and ball-volume formulas, plus an exponential generating-function identity that is formal for q > 1 because its series has zero analytic radius.The count specializes inclusion–exclusion over vertices absent from the support to q-ary looped graphs.Source: §7.1 · pp. 35–36

7.2 Optimal node–clique duality

• For ρ + µ = n, C is Singleton-optimal for ρ-node erasures if and only if C⊥ is Singleton-optimal for induced µ-vertex clique erasures, under the theorem’s dimension hypothesis.The dimension hypothesis is essential; the equivalence is a dual reformulation of the full-rank clique-minor criterion in [1, Lem. 17].Source: §7.2 · p. 37
• The duals of optimal double-node codes yield optimal binary (n −2)-clique-erasure codes of dimension 2n −1 at covered odd prime lengths; triple-node completions yield optimal (n −3)-clique codes at n = 6, 8, 10, 12.Source: §7.2 · p. 37

Open construction problem

• An infinite family of triple-node codes with redundancy 3n −3 remains the central Singleton-optimal construction problem.The exact codes at n = 6, 8, 10, 12 do not yet resolve the infinite-family question.Source: §8 · pp. 37–38

Multi-slope family

• For 2 ≤ρ ≤(n + 1)/2, the uniform multi-slope family improves the Schmidt benchmark, but its n-independent redundancy gap grows quadratically with ρ.Within the parity-check template, closing the gap requires dependencies coupling different slope families, not merely another independent family of n cyclic checks.Source: §8 · pp. 37–38

Moore edge skeleton

• For every 2 ≤ρ ≤n, the Moore theorem gives the Moore edge skeleton maximum local rank on every failed set.For ρ ≥ 3, completion requires a common quotient of dimension ρ(ρ −3)/2 followed by ρ-loop completion; at ρ = 3 the quotient is trivial, and each triple's loop images must form a basis of its three-dimensional quotient. The exact codes at n = 6, 8, 10, 12 show that the published cyclic parity-check obstruction does not preclude optimal triple-node codes; an algebraic completion for infinitely many m would settle the central problem.Source: §8 · p. 38

Four-failure codes

• An optimal four-failure family would imply an optimal triple-failure family, while an alternative four-star edge quotient still requires simultaneous loop completion.For even m = n −1, maximal alternating rank-metric spaces of Delsarte–Goethals type suggest a possible route; bilinear forms provide a structural reduction, not a finished construction.Source: §8 · p. 38

Metric-ball enumeration

• Node-metric ball volumes require accounting for overlaps among maximal subspaces, which dimension-only arguments miss by a polynomial factor.The Venn-profile formula records overlaps exactly, and the pair formula determines fixed-radius asymptotics; open tasks include recurrences for Sm,q(z), efficient profile-sum computation for growing t, and a multivariate transform recovering a dual weight distribution.Source: §8 · p. 38

Vertex-cover metric

• The vertex-cover metric's constant-relative-distance regime and this paper's fixed-distance regime are complementary, motivating explicit families that interpolate between them.The cited asymptotic work is by Kopparty, Potukuchi, and Sha.Source: §8 · p. 38

• All computer-assisted verifications reported in the paper used exact arithmetic.Source: Computational Reproducibility · p. 38
• The Zenodo archive includes source code, certificate data, execution instructions, and recorded outputs.Source: Computational Reproducibility · p. 38
• Cryptographic checksums are provided for every reported finite check in the public verification package.Source: Computational Reproducibility · p. 38

Appendix A Proof of the Local Determinant Criterion

• For prime n ≥ 5 and primitive λ, a failed triple is locally recoverable exactly when Dk(a, b) ≠ 0 for every nonzero k.If a determinant vanishes, a nonzero codeword is supported on the triple’s incident coordinates.Source: Appendix A · pp. 38, 42
• Neighborhood checks leave an Eulerian ordinary-edge pattern, while diagonal checks use loop variables to normalize its two edge parameters to δ1β1 + δ2β2 = 0.The cycle-space coordinate represents the edge pattern, and its normalized parameters reduce to a single coset y + F2.Source: Appendix A · pp. 39–41
• When all Dk(a, b) are nonzero, the determinant-tested middle factor is a unit, forcing the remaining edge pattern and every loop symbol to vanish.Primitivity of λ makes its exponent orbits {0} and all nonzero residues, so the fixed-point condition forces y ∈ F2.Source: Appendix A · p. 41
• If some Dk(a, b) vanishes, reversing the reductions constructs a nonzero locally supported codeword that passes the neighborhood, diagonal, and slope checks.The reconstructed ordinary-edge pattern is Eulerian, and the chosen loop labels make the diagonal checks vanish.Source: Appendix A · pp. 41–42
• Distinct elements of J ∩ im Lλ give distinct local codewords; fixing a linear section of Lλ on its image makes the construction linear and injective, hence local nullity is at least d2 − 1.Source: Appendix A · p. 42

Appendix B Rank of the Primitive-Slope Check Matrix

• The primitive-slope check matrix has row rank 3n − 2: Fourier analysis shows its only dependencies are the sums of all neighborhood rows and all slope rows.The argument uses odd n and primitive λ with n ≥ 5.Source: Appendix B · p. 43

Appendix C Proof of the Multi-Slope Theorem

• The correction argument reduces to showing that product and Frobenius–Moore equations force the exterior element w to vanish.The proof invokes an alternating-form mechanism and an affine product equation tailored to the multi-slope argument.Source: Appendix C · p. 43
• Frobenius descent normalizes the final independent element to 1, then uses induction and exterior-coefficient comparisons to constrain the paired elements.The proof establishes independence of the transformed elements and represents the paired elements in their span.Source: Appendix C · pp. 44–45
• Under the primitive-root hypothesis, the reduced algebra is the field K, and the failed-set elements δ1, . . . , δs are linearly independent.A relation on the proper failed subset would contradict the fact that the only relation among all n indices is the all-one relation.Source: Appendix C · p. 45
• The neighborhood, slope, and diagonal syndromes supply the descent lemma’s hypotheses for the erased graph word.The proof specializes the alternating map to K, uses distinct exponents for non-loop edges, and derives the product equation from the loopless labeling construction and diagonal checks.Source: Appendix C · pp. 45–46
• The descent conclusion gives w = 0 and B = 0, after which the diagonal checks force every remaining loop to vanish.Each remaining loop occurs in exactly one diagonal check, and multiplication by two permutes Zn.Source: Appendix C · p. 47
• ρn − (ρ − 1) is the redundancy obtained after Fourier analysis shows that every row dependence is constant on each check family.The dependency space consists of one constant for the neighborhood rows and one for each higher-slope family; these constant families are also dependencies.Source: Appendix C · pp. 47–48

Appendix D

• The obstruction applies only to the published slope-two check space and does not rule out other optimal constructions, including those supplied by Proposition 20 at four lengths.It is not an obstruction theorem for all primitive slopes in Theorem 13.Source: A One-Bit Extension Criterion and… · p. 48
• A correcting one-dimensional extension exists exactly when the stated affine system is solvable; an odd-cardinality dependency certifies that no such extension exists.The proof uses a hyperplane normal whose inner product with each failed-triple left-null vector must equal 1; summing over an odd dependency yields 0 = 1.Source: A One-Bit Extension Criterion and… · p. 49
• At n = 5, 11, 13, and 19, odd-dependency certificates show that removing one independent check from the published check space cannot solve the missing-bit problem.At n = 13, eleven triples already form such a certificate.Source: A One-Bit Extension Criterion and… · p. 50

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

• The node-star cover is irredundant but not a partition, so the univariate node-weight enumerator of a linear code cannot determine that of its dual [11, Thm. 1].Each star uniquely contains its vertex loop, while distinct stars overlap on ordinary edges.Source: Appendix E · p. 50

A two-vertex witness

• The displayed node-weight enumerator 1 + 2z + z^2 further records the two-vertex dual comparison.Source: A two-vertex witness · p. 50
• Both two-vertex codes have node-weight enumerator 1 + z, yet their dual node-weight enumerators differ.The duals are specified by edge-coordinate constraints, including y_00 = 0 and y_01 = 0.Source: A two-vertex witness · p. 50
• Character orthogonality gives an exact Fourier identity for every linear code, but the witness shows K_w(y) is not determined by wt_N(y) alone.A refined dual theory must include additional support-intersection data, such as support orbit type under vertex relabeling.Source: A two-vertex witness · p. 51