Non-asymptotic Upper Bounds for Deletion Correcting Codes

I. INTRODUCTION

• The bounds provide finite-length limits for assessing code constructions, addressing the gap left by asymptotic results that do not finely approximate codebook size.For unbounded code-size benchmarks, asymptotic equality does not establish whether a particular finite-length code is larger or smaller than the benchmark.Source: §I · pp. 1–2
• The paper derives explicit non-asymptotic bounds for any deletion count and alphabet size, including a closed-form single-deletion bound that implies known asymptotic bounds.The results imply Levenshtein’s asymptotic bound and Tenengolts’ asymptotic bound.Source: §I · p. 2
• The bounds also yield an improved upper bound on the asymptotic rate function when the deletion count is a constant fraction of string length.The rate function gives the asymptotic rate of the largest deletion-correcting code as a function of the deleted fraction.Source: §I · p. 2
• The method extends to constrained sources, demonstrated with non-asymptotic bounds for single-deletion codes over run-length limited strings.A constrained source is a specified set of strings, not necessarily all strings of a given length.Source: §I · p. 2
• A hypergraph matching formulation and a feasible dual solution to its linear-programming relaxation yield the upper bounds.For single deletions, this construction permits a closed-form dual objective; for larger deletion counts, the resulting expressions do not admit closed forms in the paper’s analysis.Source: §I · p. 2
• For binary single-deletion codes through length 14, the fractional-matching bound is close to VT-code size, supporting the conjecture that VT codes are optimal or nearly optimal in that range.VT codes are confirmed optimal through length 10; the paper reports their size differs from the fractional-matching bound by at most 8 through length 14.Source: §I · p. 2, A. Related work · p. 2

B. Organization

• The paper’s roadmap moves from preliminaries and single-deletion bounds to multiple deletions and rate bounds, constrained-source bounds, numerical comparisons, and discussion.The numerical section compares Levenshtein’s bound, the paper’s bound, a tighter bound from its logic, and best-known codes.Source: B. Organization · p. 3

II. PRELIMINARIES

• A subsequence preserves the order of selected symbols, and deleting n−k symbols from a string produces a subsequence of length k.Insertion reverses this relation by adding symbols to a subsequence to obtain a supersequence.Source: §II · p. 4
• A run is a maximal contiguous block of identical symbols; the number of runs is denoted r(x).For example, 120010 has five runs.Source: §II · p. 4
• The s-deletion set Ds(x) contains subsequences formed by deleting s symbols, while an s-deletion correcting code has pairwise disjoint deletion sets.Deletion of different symbols within the same run can yield the same subsequence.Source: §II · p. 4
• A code corrects s deletions exactly when distinct codewords have Levenshtein distance greater than 2s.The preliminaries also state equivalent characterizations using intersecting deletion sets or insertion sets.Source: §II · p. 4

A. Background on hypergraphs

• A hypergraph consists of vertices and nonempty vertex subsets called hyperedges; a matching is a collection of pairwise disjoint hyperedges.A transversal is a vertex subset intersecting every hyperedge.Source: A. Background on hypergraphs · p. 5
• The incidence matrix records which vertices each hyperedge covers, and integer linear programs characterize the matching and transversal numbers.Matching variables select hyperedges subject to at most one selected edge covering each vertex; transversal variables select vertices so every edge is covered.Source: A. Background on hypergraphs · p. 5
• Relaxing integrality defines fractional matchings and transversals, whose optimal values are equal by linear-programming strong duality.The fractional matching number upper-bounds the integer matching number, while the fractional transversal number lower-bounds the integer transversal number.Source: A. Background on hypergraphs · p. 6

A. Hypergraph characterization

• An s-deletion correcting code corresponds to a matching in the deletion-set hypergraph, so the largest code size equals that hypergraph’s matching number.Its hyperedges represent length-n strings and its vertices represent length-(n−s) strings.Source: A. Hypergraph characterization · pp. 6–7
• The deletion-set approach faces unequal hyperedge sizes, which complicates direct packing bounds.This reflects the unequal sizes of neighborhoods under Levenshtein distance, unlike Hamming-distance neighborhoods.Source: A. Hypergraph characterization · p. 7
• Insertion-set hyperedges have equal size, but their matching formulation leads to a weak upper bound.The paper contrasts this analytically convenient formulation with its deletion-set approach.Source: A. Hypergraph characterization · p. 7
• The deletion-set hypergraph is regular, and the paper reports that appropriately addressing it yields a better bound.The hypergraph is not in a category where matching problems appear well studied.Source: A. Hypergraph characterization · p. 7

• The single-deletion proof relies on run-count monotonicity under insertion and the equality between deletion-set size and run count.Source: B. The non-asymptotic upper bounds for… · p. 7
• The largest q-ary single-deletion code has size at most (q^n-q)/((q-1)(n-1)).Source: B. The non-asymptotic upper bounds for… · p. 8
• The codebook maximum equals a hypergraph matching number, so a fractional transversal supplies an upper bound on its size.Source: B. The non-asymptotic upper bounds for… · p. 8
• A transversal is constructed by assigning weights using the run count of each length-(n−1) string.Source: B. The non-asymptotic upper bounds for… · p. 8
• The bound implies the known asymptotic results of Levenshtein and Tenengolts.Source: B. The non-asymptotic upper bounds for… · p. 8
• For binary strings, the paper combines the bound with the size of Varshamov-Tenengolts codes to compare upper and lower bounds.Source: B. The non-asymptotic upper bounds for… · p. 8

• The multiple-deletion bound follows from a fractional transversal weighted by the reciprocal deletion-set size, with insertion monotonicity ensuring feasibility.Source: ASYMPTOTIC RATE FUNCTION · p. 9
• For s≤5, explicit deletion-set formulas yield code-size bounds, and these can be tighter than the general bound.Source: ASYMPTOTIC RATE FUNCTION · p. 9
• For general s, a lower bound on deletion-set size yields an explicit upper bound when n>2s, with strings having at most two runs handled separately.Source: ASYMPTOTIC RATE FUNCTION · p. 9
• The resulting bounds imply Levenshtein’s earlier asymptotic results for binary strings and generalize them to q-ary strings.Source: ASYMPTOTIC RATE FUNCTION · pp. 9–10
• For fixed s, the derived upper bound U_q,s,n has asymptotic order s!q^n/((q−1)^s n^s).Source: ASYMPTOTIC RATE FUNCTION · p. 10
• For s≠1, U_q,s,n is explicit but difficult to reduce to a closed form.Source: ASYMPTOTIC RATE FUNCTION · p. 11

A. The asymptotic rate function

• Theorem 4.4 gives rate-function bounds for τ < 1/2 and for 1/2 ≤ τ ≤ 1.The non-asymptotic bound used for the derivation applies directly only when τ < 1/2; for larger τ the section uses a trivial bound.Source: A. The asymptotic rate function · p. 11
• The derived rate-function bound improves on Levenshtein’s previous bound.The rate drops sharply for small deletion fractions, and for τ ≥ 1/2 the stated bound is Rq(τ) ≤ 1 − τ.Source: A. The asymptotic rate function · p. 11
• For τ < 1/2, the bound becomes non-monotone and remains positive, so it is vacuous beyond a certain deletion fraction.The true rate function must decrease monotonically with τ; the bound reaches zero only at τ = 1.Source: A. The asymptotic rate function · p. 11
• The non-asymptotic bound can yield useful asymptotics in one regime without doing so in others.The section notes that the bound’s behavior at larger τ illustrates this limitation.Source: A. The asymptotic rate function · p. 11

V. BOUNDS ON CODES FOR CONSTRAINED SOURCES

• The method extends the bounds to codebooks drawn from a constrained set of source strings, rather than all strings of a fixed length.The section notes that prior arguments based on Stirling’s approximation rely on having all strings available.Source: §V · p. 12
• For a source set S, the codebook is modeled as a matching in a partial hypergraph generated by S.The associated integer program selects strings subject to at most one selected string per deletion output.Source: §V · p. 12
• A fractional transversal of the source-specific hypergraph supplies the upper bound on the largest codebook.The construction applies the logic of Theorem 4.1 to constraints indexed by strings in S.Source: §V · p. 12
• A greedy independent-set bound on the line graph also gives a lower bound for the largest source-restricted codebook.The argument bounds the line graph’s maximum degree using deletion-set and insertion-set sizes.Source: §V · p. 12

A. Run-length limited sources

• The demonstration applies the constrained-source method to single-deletion codes for (d, ∞)-RLL strings, and the approach extends to more deletions.The source strings have unit-length 1-runs and 0-runs of length at least d, with the first and last runs also 0-runs.Source: A. Run-length limited sources · p. 12
• Deleting one symbol from an (d, ∞)-RLL string yields either an (d, ∞)-RLL string of length n−1 or one with exactly one gap of d−1 zeros between consecutive 1s.The latter output set is denoted S′ n−1(d, ∞).Source: A. Run-length limited sources · p. 13
• Theorem 5.2 gives an upper bound on the largest codebook for Sn(d, ∞).Its proof counts deletion outputs in the two sets from Lemma 5.1; the authors say simplifying the bounds into closed form is beyond the paper’s scope.Source: A. Run-length limited sources · p. 13

VI. NUMERICAL RESULTS

• The derived non-asymptotic bound is tighter than Levenshtein’s, while remaining weaker than the numerically computed fractional matching value.The gap to the fractional matching value shows that the constructed fractional transversal is not optimal.Source: §VI · p. 14, Table I · p. 14
• For binary single-deletion codes with n ≤ 14, VT0(n) closely matches LP-UB; VT0(n) is confirmed optimal for n ≤ 10 in Sloane’s compilation.The paper describes VT0(n) as conjectured optimal for all n [1].Source: §VI · p. 14
• The numerical comparison includes the largest codes in Tenengolts’ two-parameter family for larger alphabets.The authors compute each family member for the available parameter values and report the largest; these codes are smaller than LP-UB.Source: §VI · pp. 14–15
• For q = 2 and s = 2, 3, 4 over 15 ≤ n ≤ 30, the derived bound is significantly better than Levenshtein’s.The figure compares Uq,s,n as solid lines with Levenshtein’s bound as dotted lines.Source: §VI · p. 15, Figure 2 · p. 15

VII. DISCUSSION

• The single-deletion bound can be improved in principle because it does not equal the fractional matching number, but finding a smaller-weight transversal has eluded the authors.The close numerical match between their construction and the optimal fractional transversal makes improvement challenging in practice.Source: §VII · p. 15
• Figure 3 compares optimal and constructed fractional transversals for the stated hypergraphs, with the plotted lines used to show value trends rather than carrying independent meaning.The examples are q = 2, n = 8, s = 1 and q = 5, n = 4, s = 1.Source: §VII · pp. 15–16
• The constructed fractional transversal closely matches the optimal trend in the illustrated cases, and the average difference vanishes for large n in the binary case.The authors say further fine-tuning is not obvious, though a small saving could substantially improve the bound because the number of vertices grows exponentially.Source: §VII · p. 15
• The authors speculate that the binary optimum may have a number-theoretic expression, suggesting such a construction could tighten the fractional matching or transversal bound.Their speculation is motivated by the fractional matching number closely tracking the VT-code size, which has a number-theoretic formula.Source: §VII · p. 15
• The paper concludes that its bounds cover general alphabets, deletion counts, and constrained sources, and imply classical asymptotic bounds.The constrained-source analysis is demonstrated for run-length limited sources.Source: §VII · p. 15

APPENDIX PROOF OF THEOREM 4.4

• The asymptotic rate satisfies Rq(τ) ≤ max over 0 ≤ ρ ≤ 1−τ of N(ρ; τ) − D(ρ; τ).D is the larger of D1 and D2; the proof estimates the exponents after setting aside a polynomial term relative to the first sum.Source: APPENDIX PROOF OF THEOREM 4.4 · p. 16
• For τ ≤ ρ < 3τ, the proof gives D1(ρ; τ) = (ρ−τ) log2 q; when ρ ≤ τ, D1(ρ; τ) = 0.The proof separately handles τ ≥ 1/2 using a trivial bound.Source: APPENDIX PROOF OF THEOREM 4.4 · pp. 16–17
• D2(ρ; τ) dominates D1(ρ; τ) throughout the stated range, using D1 = 0 when ρ ≤ τ and a maximizing choice when ρ > τ.For ρ > τ, the proof uses μ = τ in the maximization defining D2.Source: APPENDIX PROOF OF THEOREM 4.4 · p. 17