PaperlayerView exact revision on arXiv

Source-linked AI summary

Coding for Multiple Reverse-Complement and Palindromic Duplications

Aryeh Lev Zabokritskiy

arXiv:2609.00779v1cs.IT

TL;DR

The paper addresses finite-error coding for sequential PAL and RC duplications, including the even-length gap in prior RC-specific constructions. It proves common converse bounds and an even-length channel conjugacy, then obtains exact-two sphere characterizations and existential codes, while leaving a binary factor-two existence gap and explicit-construction limitations.

  • Problem

    The paper studies q-ary codes correcting sequential PAL and RC duplications, including multiple errors and the prior RC-specific construction gap at even k.

  • Method

    It combines endpoint-multiplicity counting, an even-length coordinate-wise alternating-complement conjugacy, exact-two sphere analysis, and greedy coloring of a confusability graph.

  • Results

    For even k, PAL and RC channels are bijectively conjugate; exact-two spheres yield existential codes with redundancy 4 log_q n + O_{q,k}(1), while binary converse bounds begin at 2 log_2 n − O_k(1).

  • Takeaways & Limitations

    The conjugacy transfers correcting codes, encoders, and decoders between PAL and RC at even duplication lengths without changing code size.

  • Takeaways & Limitations

    The existence theorem does not itself provide structured encoding or decoding, and the stronger-channel benchmark lacks efficient syndrome-tuple selection and message encoding.

Abstract

from arXiv · show

Reverse-complement (RC) and palindromic (PAL) duplications copy a length-$k$ block, reverse the copy, and insert it next to the original block; an RC duplication also complements the copied symbols. We study $q$-ary codes correcting $t$ such operations performed sequentially, so a later operation may copy symbols created by an earlier one. For fixed $q,k,t$, every length-$n$ code $C$ for either channel satisfies $n-\log_q|C|\geq t\log_q n-O_{q,k,t}(1)$; for fixed $q,k$ and $t=o(n)$ the lower bound is $t\log_q(n/t)-O_{q,k}(t)$. For a single RC error over an even alphabet with a fixed-point-free complement, the previously known RC-specific lift applies at odd $k$ and does not cover even $k$. For every even $k$, we give a coordinate-wise bijection that turns each RC duplication into a PAL duplication. Applying this bijection to every codeword therefore converts any $t$-error-correcting RC code into a PAL code of the same size, and conversely; encoders and decoders transfer by adding linear-time coordinate passes. We also determine the maximum number of distinct descendants produced by exactly two errors from one source word. Words alternating between any two distinct alphabet symbols attain this maximum for PAL, and the bijection gives the RC maximizers. For both PAL and RC at even $k$, form a graph whose vertices are all $q$-ary words of length $n$, joining two distinct vertices exactly when they have a common exact-two descendant. Bounding the degree and greedily coloring this graph yields existential codes of redundancy $4\log_q n+O_{q,k}(1)$. In the binary two-error problem, the converse gives $2\log_2 n-O_k(1)$, leaving a factor-two gap in the best existence bounds.

1 Introduction

The paper studies sequential PAL and RC duplication channels, establishes common finite-error bounds, and resolves their even-length relationship through a bijective conjugacy. It also characterizes exact-two spheres and derives existential two-error codes, while identifying remaining construction gaps.

  • Channel and scope: Sequential duplications may copy symbols inserted by earlier operations, so the channel permits arbitrary overlap and reuse across operations.The source block for each operation is selected from the current word.
  • Converse bounds: For fixed q, k, and t, every correcting code obeys a finite-error redundancy lower bound of t log_q n − O_{q,k,t}(1).For t=o(n), the bound becomes t log_q(n/t) − O_{q,k}(t).
  • Even-length equivalence: At every even k, an alternating-complement bijection conjugates the complete sequential PAL and RC channels, preserving code length and size.Encoders and decoders transfer with at most two linear-time coordinate passes.
  • Two-error geometry: For every even k, alternating words over any two distinct symbols attain the maximum exact-two PAL descendant sphere, with RC maximizers obtained by conjugacy.The supplied passage introduces the exact maximum, while the following results identify its PAL and RC maximizers.
  • Existence bounds: Greedy coloring of the two-error confusability graph yields PAL and RC codes with redundancy 4 log_q n + O_{q,k}(1).In the binary case, the converse and existence bounds are 2 log_2 n − O_k(1) and 4 log_2 n + O_k(1), respectively.
  • Benchmarks and open directions: A stronger two-burst benchmark has leading redundancy coefficient five and does not improve the coefficient-four existence bound.Its separate contribution is a nonuniform polynomial-time decoder after suitable syndrome parameters are supplied.

2 Channel model and code parameters

This section defines q-ary PAL and RC duplication channels, their descendant spheres, and code correction through disjoint descendant sets. Exact-t and at-most-t correction coincide because common descendants can be extended to the same number of operations.

  • Alphabet and words: The alphabet is a finite q-symbol set with an involutive complement, and words are indexed from zero for coordinate-wise operations.Fixed points of the involution are allowed in the abstract model.
  • Duplication operations: A duplication decomposes x as uvw with |v|=k, then inserts a transformed reverse of v immediately after the source factor.The PAL transformation reverses v, while the RC transformation additionally applies the complement map.
  • Insertion notation: The insertion operator InsAfter_h inserts a word immediately after coordinate h of the current word.This formalizes the location of each duplication insertion.
  • Descendant spheres: A descendant sphere is the set of words reachable by exactly t or at most t length-k operations of the selected channel.The channel label χ distinguishes PAL from RC operations.
  • Correction criterion: A code corrects when distinct codewords have disjoint corresponding descendant sets, equivalently forming an independent set in the confusability graph.The graph joins words whose descendant sets intersect.
  • Correction conventions: Exact-t and at-most-t correction are equivalent because any common descendant after fewer operations can be extended by applying identical legal duplications.Different operation counts also produce different output lengths.

3 An endpoint-multiplicity packing bound

The paper embeds many distinct exact-t descendants by assigning duplication multiplicities to eligible endpoints, then packs these families to obtain finite-error redundancy lower bounds for both channels.

  • Endpoint-multiplicity embedding: Endpoint multiplicities encode t duplications by repeatedly duplicating eligible source blocks in decreasing endpoint order.The construction remains injective because eligible endpoints provide separating symbols, including overlapping source blocks.
  • Endpoint statistics: G_k,pal(x) ≥ r_(≥k)(x), and alternating words can have G_k,pal(x)=n−k+1 despite having no long constant runs.Thus eligible-endpoint families can be substantially larger than constant-run families while preserving the same leading packing order.
  • Fixed-error converse: For fixed q, k, and t, every correcting code has redundancy at least t log_q n + t log_q(q−1) − log_q(t!) − (k+1)t − o(1).The bound applies to either PAL or RC channels and to exact-t or at-most-t correction.
  • Sublinear errors: For t=o(n), the lower bound sharpens to t log_q(n/t)−O_q,k(t).Here q and k are fixed, and the constants are not uniform when q or k grows with n.
  • Scope: The converse applies to reverse-complement duplication at every length k, without requiring a PAL–RC channel relation.The even-length channel equivalence is developed separately.

4 Even-length equivalence of the two channels

For even duplication length, complementing exactly the odd coordinates gives a bijective conjugacy between PAL and RC channels. It preserves correction properties, sphere sizes, optimal redundancies, and decoder transfer up to linear-time coordinate passes.

  • Conjugacy: For even k, the alternating-complement map is an involutive coordinate bijection that conjugates each reverse-complement duplication to a palindromic duplication.The identity holds step by step because the inserted block transforms into the reversed source factor and even-length shifts preserve suffix parity.
  • Sequential transfer: The conjugacy extends layerwise to sequential histories and variable even duplication lengths.Applying the appropriate map to each output length transfers endpoint sets, confusability, and decoder behavior.
  • Code equivalence: PAL and RC codes related by the map have identical sphere sizes, optimal cardinalities, and redundancies.Their exact-s and at-most-t confusability graphs are isomorphic.
  • Algorithms: Encoder and decoder transfer requires only coordinate-wise passes, adding O(n) encoder time and O(|y|) decoder time.The transforms can use O(1) extra memory in a mutable random-access representation.
  • Parity boundary: The construction is specific to even k because odd-length duplications change suffix-coordinate parity and are not conjugated by the same map.This limitation is structural, although one-error burst codes still cover both channels at every fixed length.

5 Two-error sphere geometry at even lengths

The paper determines the maximum exact-two descendant sphere for every even duplication length and identifies alternating sources as extremizers. The PAL result transfers to RC through the even-length conjugacy, while sphere nonuniformity limits direct converse arguments.

  • Exact-two maximum: For every even k, alternating words over any two distinct alphabet symbols attain the maximum exact-two PAL descendant sphere.The proof classifies two-step history collisions and shows alternating sources have only the forced doubleton fibers.
  • Sphere formula: Every exact-two descendant sphere has size at most H−P, with alternating sources achieving equality.The upper bound comes from collisions forced for every source; attainability requires ruling out additional alternating-source collisions.
  • RC transfer: The same exact-two and at-most-two maxima hold for RC at even k; in the binary case, constant sources attain them.The PAL maximizers transfer through the channel conjugacy, while binary RC maximizers are 0^n and 1^n.
  • Length-two refinement: For k=2, the edge-tree normal form has the sharp number of structural shapes, although different shapes can merge on nonalternating sources.The edge-tree retains ancestry information that sphere cardinality alone does not reveal.
  • Converse limitation: Maximum spheres grow as Θ(n^2), but their high nonuniformity prevents the maximum-sphere formula alone from proving a 2 log_2 n−O(1) converse.The paper instead obtains the binary converse by constructing quadratic descendant subfamilies for almost all sources.

6 Inverse lists and an elementary even-length existence bound

The paper bounds inverse PAL parent lists and combines these bounds with maximum forward spheres to control confusability-graph degree. Greedy coloring then yields existential two-error codes for both even-length PAL and RC channels.

  • Inverse lists: A length-(n+k) word has at most n−k+1 distinct one-error PAL-k parents.Each inverse step selects a length-2k window of the form vv^R and deletes its final k symbols.
  • Inverse lists: A length-(n+2k) word has at most (n+1)(n−k+1) distinct two-error PAL-k ancestors.Reverse-chronological enumeration remains valid for overlapping and nested duplications.
  • Graph construction: Multiplying forward descendant and inverse-parent bounds controls confusability-graph degree, and a greedy coloring produces an independent correcting code.An independent set in the exact-two graph also corrects at most two duplications.
  • RC and algorithmic scope: The same existence bound holds for at most two even-length RC duplications by channel transfer.This is an existence statement and does not itself provide a structured encoder or decoder.

7 Benchmarks and the dedicated construction problem

The section compares a syndrome-parameterized stronger-channel benchmark with duplication-specific existential bounds and identifies the remaining explicit-construction problems. Correcting two arbitrary insertion bursts gives a coefficient-5 benchmark, while greedy coloring gives coefficient 4 but nonconstructively.

  • Benchmarks: Table 1 compares neighboring coding regimes row by row because differing channels, parities, alphabets, and error counts are not directly ordered.Redundancy is measured in q-ary symbols unless bits are stated explicitly.
  • Stronger-channel benchmark: Two sequential arbitrary insertions can be simultaneously deleted as two disjoint final length-k bursts, even when later insertions overlap or nest in earlier material.This containment makes the stronger burst channel applicable to sequential PAL and RC duplications.
  • Stronger-channel benchmark: 5 log2 n + 14k log2 log2 n + Ok(1) bounds the redundancy of the syndrome-parameterized binary benchmark for at most two PAL-k or RC-k duplications.The code corrects a stronger arbitrary-burst channel rather than exploiting duplication-specific structure.
  • Algorithmic status: Once a suitable syndrome tuple is supplied, the benchmark has a nonuniform polynomial-time codeword decoder, but no efficient tuple-selection procedure or polynomial-time message encoder is asserted.The tuple is guaranteed to exist by a nonconstructive ensemble argument.
  • Dedicated construction problem: 4 log2 n + Ok(1) is the greedy existential upper bound, while the binary converse is 2 log2 n −(2k + 3) −o(1), leaving open whether the converse coefficient can be attained.The section separately asks for explicit uniform binary families with polynomial-time parameter selection, encoding, and decoding.
  • Dedicated construction problem: An explicit family should correct two unrestricted sequential PAL-k duplications with all parameters selected in polynomial time and a leading coefficient below five.A possible route is to exploit PAL sphere structure directly rather than correct every pair of arbitrary bursts.

8 Conclusion

The paper establishes common finite-error converses for PAL and RC duplications, extends the analysis to even-length channel conjugacy and exact two-error geometry, and obtains coefficient-4 existential codes. The binary two-error setting remains between a coefficient-2 converse and coefficient-4 existence bound, with explicit efficient constructions still open.

  • Conclusion: The endpoint-multiplicity method gives finite-length code-size bounds and fixed- and sublinear-error asymptotics for both channels without a parity restriction.The proof handles sequential operations whose later source blocks include symbols inserted earlier.
  • Conclusion: For every even k, exact two-error spheres and greedy coloring yield PAL and RC codes with redundancy 4 logq n + Oq,k(1).In the binary case, the converse is 2 log2 n −Ok(1), leaving a factor-two gap in best existence bounds.

A Cyclic factorization of the even-length interleaving action

For even k, the interleaving action decomposes source–insertion couplings into a cyclic 1-factorization of Km,m. The matching phase is determined by a coupled residue pair, but recovering the full duplication start additionally requires row-location information and a lift choice.

  • PAL–RC relation: The cyclic factorization describes the same source–target column coupling in PAL and RC channels; RC changes only the inserted symbol value by complementing it.The conjugacy identifies the channels at word level, while this appendix supplies the finer interleaving description.
  • Cyclic factorization: The map πb is a fixed-point-free involution exchanging even and odd residues, and its factors form a 1-factorization of Km,m.Every edge belongs to exactly one factor.
  • Cyclic factorization: For k = 2m, each source–insertion column coupling is a factor in the standard cyclic 1-factorization of Km,m.The bipartition consists of even and odd residue classes.
  • Phase identification: An identified source–insertion column pair determines the matching phase b modulo m through 2b ≡ r + s + 1 (mod 2m).Because the paired residues have opposite parity, division by two determines b uniquely modulo m.
  • Start recovery: The two lifts b and b + m generally have different row-cut profiles, so the matching phase alone does not recover the complete duplication start.The row location and lift choice are additionally required.

B Obstructions for separated-row and raw-history constructions

The appendix rules out several separated-row and raw-history construction architectures without proving lower bounds for unrestricted PAL2 or RC2 codes. Joint constraints on the two rows and endpoint invariants on history equivalence classes remain open.

  • Construction obstructions: Separated-row analysis finds architecture-specific obstructions, including a linear clique under constant regularity and failure of a raw B2 history sum as an endpoint syndrome.These results do not preclude constructions using joint row constraints or endpoint invariants on history-equivalence classes.

B.1 Row dynamics and trace-conditioned reconstruction

The row-update rules track how each PAL2 duplication changes the even and odd subsequences. Given a complete even-row trace and the final odd row, the initial odd row is uniquely reconstructible, while the original even row alone is insufficient.

  • Row update rules: Each PAL2 update transforms the even and odd rows according to the insertion coordinate parity.The formulas are applied to the updated rows after every subsequent error.
  • Insufficient side information: The original even row and full received word cannot always identify the source uniquely after one PAL2 error.Two instances can share the same original even row and received word while having distinct odd rows; the same obstruction transfers to RC2.
  • Trace-conditioned reconstruction: A complete ordered even-row trace together with the final odd row determines at most one compatible initial odd row.Reverse reconstruction deletes a forced symbol at one of two adjacent coordinates; equal adjacent symbols make the alternatives equivalent.
  • Trace-conditioned reconstruction: Reverse induction establishes uniqueness because boundary and inserted-value checks can reject candidates but cannot create additional predecessors.The argument proceeds one reversed duplication at a time.

B.2 Pointwise list bounds and linear fixed-row ambiguity

For a fixed even row and received word, two PAL2 errors admit a bounded list of compatible odd-row sources, but the bound grows with the row length. A construction shows linear ambiguity and a logarithmic side-syndrome cost even when the even row has run length one.

  • Pointwise list bound: (m + 2)(L + 1) bounds the number of compatible initial odd rows for fixed E and received y after two PAL2 errors.The factor m + 2 counts the first reverse deletion coordinate, while L + 1 bounds the second deletion multiplicity.
  • Pointwise list bound: The dependence on m cannot be removed, even under the strongest nonconstant run-length constraint.Thus a pointwise list bound need not become constant when repeated-symbol runs are tightly controlled.
  • Linear fixed-row ambiguity: (n + 2)/4 distinct initial odd rows can share one fixed even row and received word for infinitely many source lengths.The fixed even row has maximum run length one, so the ambiguity is linear despite the strongest possible nonconstant run constraint.
  • Conditional syndrome cost: log2 n −O(1) bits are required from a side syndrome correcting the two-error family within the fixed-even-row fiber.A syndrome class cannot contain two sources with the same exact-two descendant.

B.3 Regularity localization

Weak regularity localizes two-insertion traces and yields quadratic pointwise source-list bounds, but these local bounds do not control a universal syndrome across all received words. Regular fixed-even-row cliques demonstrate the resulting ambiguity for PAL2 and RC2.

  • Regularity after insertion: Two insertions into a weakly ℓ-regular row produce constant runs of length at most ℓ+2 and alternating substrings of length at most 3ℓ+2.The bounds follow by removing the two inserted symbols and partitioning surviving alternating substrings.
  • Trace localization: The pair (E, Ey) either identifies two runs containing one deletion each or an interval containing both deletion coordinates.This dichotomy localizes every compatible reverse trace.
  • Pointwise source lists: For fixed E, Ey, and final odd row, the number of compatible initial odd rows is bounded by the corresponding ordered-trace count.Each ordered even-row trace permits at most one initial odd row by conditional trace uniqueness.
  • Limits of localization: For ℓ=O(log n), the pointwise list is O(ℓ^2), but this does not bound the number of syndrome values needed over the union of all lists.The local list estimate therefore does not by itself yield a universal side syndrome.
  • Regular fixed-row cliques: A fixed even row can support r+1 sources forming an exact-two PAL2 confusability clique, and the construction transfers to RC2.These are conditional fixed-E fiber results, not redundancy lower bounds for unrestricted codes; joint constraints on both rows may exclude the gadgets.
  • History-label obstruction: Raw structural two-history sums cannot serve as endpoint syndrome differences for all two-step PAL2 histories.Two histories from 0^n reach the same 0^(n+4) endpoint but have different raw shape sums.
  • Scope of obstruction: The raw-history obstruction leaves open endpoint-class labels and state-dependent invariants that telescope along the updated word.It concerns the unquotiented history tree rather than all additive constructions.
Loading 2609.00779v1…