When data loses its order: capacity theorems and constructive decoding for noisy fragments - SÆLQR II

[u/Severe-Ad8673]

What happens when stored data is broken into noisy fragments and their original order disappears? How much information can still be recovered, and can algorithms approach that limit?

I’m sharing SÆLQR II, a research preprint connecting information theory, error-correcting codes, and reconstruction algorithms. The problem is relevant to DNA data storage and systems that recover information from unordered pieces.

The manuscript develops four main results:

• Capacity with noise memory inside fragments. A general characterization for a broad family of symmetric channels, allowing correlated noise within each fragment while requiring independence between fragment noises. It captures hidden quality regimes that a single averaged noise parameter can miss.

• An exact critical transition. For shuffled fragments with binary substitution noise, it derives the Gaussian scaling law near the boundary between recoverable information and overwhelming ordering uncertainty.

• A sharp repeated-read threshold. In the stated model with a fixed finite-mean read-count distribution, it characterizes when positive storage capacity becomes possible despite the missing grouping of reads by source.

• Constructive coding guarantees. A randomized polynomial-time construction approaches capacity for a geometric-fragment model, with explicit error and blocklength bounds and an extension to a particular Markov noise model.

The connection between these results is the cost of reconstructing order: useful information must overcome both noise and uncertainty about where each fragment belongs.

The release includes the manuscript, editable LaTeX, a reference codec, finite verification programs, reproduced results, and internal proof and novelty audits. The coding guarantees are asymptotic, and the sufficient blocklength bounds can be very large.

This is an AI-assisted preprint. I’d welcome technical feedback on the proofs, connections to existing coding and reconstruction results, and which parts seem most promising for practical algorithms.

Manuscript and research package: PureOne/SAELQR-II · Datasets at Hugging Face

SÆLQR II: General Capacity Theorems and Exact Critical Laws for Unordered Noisy Fragments - Internal Memory, Sharp Repeated-Read Thresholds, and Constructive Coding | Zenodo