CS Paper Radar

Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters

Arman Nilforoushan, Farzad Parvaresh

cs.IT math.CO ·submitted 2026-09-19 16:19 UTC · v2
theory

Abstract

Data stored in synthetic DNA is retrieved by shotgun sequencing, which returns short subsequences rather than the stored word itself. A natural abstraction of this readout is the $k$-deck of a word: the vector recording how often each word of length $k$ occurs as a subsequence. Two stored words are distinguishable from their readouts exactly when their $k$-decks differ, so the number $D_{q,k}(n)$ of distinct $k$-decks of words of length $n$ over an alphabet of size $q$ measures what a length-$k$ readout retains. We analyse the degrees of freedom remaining in a $k$-deck once all shorter decks are fixed. Within each class of words having prescribed letter multiplicities, the length-$k$ entries are confined to an affine subspace whose dimension is exactly the number of Lyndon words with the same multiplicities, which we give in closed form as a Möbius sum. Writing $L_q(j)$ for the number of Lyndon words of length $j$ over an alphabet of size $q$, we deduce the improved upper bound \[ D_{q,k}(n)=O\!\left(n^{E_q(k)}\right),\qquad E_q(k)=\sum_{j=1}^{k}j\,L_q(j)-1 . \] In the case of a binary alphabet this bound satisfies $D_{2,k}(n)=O\!\left(n^{4\cdot 2^{k-1}}\right)$. We then prove matching lower bounds in the first two nontrivial cases: $D_{q,2}(n)=Θ\!\left(n^{q^2-1}\right)$ for every alphabet size $q$, and $D_{2,3}(n)=Θ(n^{9})$ for the binary alphabet. The latter confirms, for $q=2$ and $k=3$, our conjecture that the upper bound has the correct degree for every $q$ and $k$.

Comment
Submitted to IEEE Transactions on Information Theory

Closest papers

Nearest neighbours by meaning across the whole index.

Substring Complexity in BWT-Runs Bounded Space

cs.DS ·2026-10-29 ·Johannes Fischer
similarity 0.62
Abstract

Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$. We show how to compute it in $O(n+r\log r)$ time, using only $O(r)$ words of space, where $r$ denotes the number of runs in the Burrows-Wheeler transform.

0.30

A Hyperbolic Bound for File Retrieval in DNA-Based Data Storage

cs.IT math.CO ·2026-09-28 ·Constantinos Vasilios Argyris Vlachos, Daniella Bar-Lev
theory similarity 0.59
Abstract

In DNA-based storage systems, data are retrieved by sequencing molecules sampled from a DNA pool. We study how the way coding redundancy is shared between files affects their expected retrieval times. Our focus lies on the case of two files that are encoded by a systematic linear code over an arbitrary finite field. We consider the conjecture that the sum obtained by dividing each file dimension by its expected retrieval time is at most one whenever the dimension of at least one file is more than one. For this, we develop a geometric view of the retrieval process. As molecules are sampled, we follow the growing span of the corresponding columns of the generator matrix and track how much of this span comes from each file. Among the samples that enlarge the overall span, this lets us compare those that make progress toward recovering both files with those that make progress toward neither. We call a column mixed if the corresponding encoded symbol combines information from both files. In this work, we sharpen a projection bound and use it to control the effect of mixed columns. We prove the conjecture whenever the total information dimension is at least twice the number of mixed columns plus two. For equal-sized files, this allows up to one fewer mixed column than the dimension of either file and extends the previous result for codes with no mixed columns.

0.40

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.59
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

Revisiting (Bijective) Burrows-Wheeler Transform Space-Time Trade-Off Constructions

cs.DS ·2026-11-02 ·Dominik Köppl, Tomohiro I
similarity 0.58
Abstract

The bijective Burrows-Wheeler transform (BBWT) replaces the delimiter of the ordinary BWT by a Lyndon factorization and sorts factor conjugates in $ω$-order. It admits quadratic-time constant-workspace algorithms and linear-time linear-space algorithms. We extend the small-space BWT trade-off of Crochemore et al. [JDA,'15] to the BBWT and accelerate both constructions. For $τ\in [3..n]$, let $σ_τ\le\min(σ,τ+1)$ be the maximum construction-batch alphabet size. We construct either transform in $ O\!\left( \frac{n^2}τ \frac{\logτ}{\log\logτ} \right) $ time and $O(τσ_τ)$ additional space, assuming $τσ_τ=O(n)$. This improves the transferred $O((n^2/τ)\logτ)$ bound by a $\log\logτ$ factor. If $σ_τ\in w^{O(1)}$, where $w\inΩ(\log n)$ is the word size, the time improves to $ O\!\left( \frac{n^2}τ + \frac{n\logτ}{\log\logτ} \right). $ For inversion, the same bounds hold with the global alphabet size $σ$ in place of $σ_τ$.

0.21

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.57
Abstract

We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

0.53

Polynomially larger deletion codes by linear hashing of substring counts

cs.IT math.CO ·2026-09-16 ·Eyal En Gad
highly cited similarity 0.57
Abstract · Extended to arbitrary fixed alphabets, mixed edits, and bounded substring edits; simplified proof using binary linear hashing

We reduce the leading redundancy coefficient for binary codes correcting any fixed number $t\ge2$ of deletions from $2t$ to $2t-1$. This is the first improvement to that coefficient since Levenshtein's 1965 bound. More generally, over every fixed alphabet of size $q\ge2$, codes of length $n$ correcting any combination of at most $t$ insertions, deletions and substitutions exist with redundancy $(2t-1)\log_q n+O_t(\log_q\log_q n)$. For two deletions, the upper-bound coefficient drops from $4$ to $3$, halving the gap to the lower-bound coefficient $2$. The leading coefficient $2t-1$ also holds for $t$ bounded substring edits, where both the removed and inserted strings have bounded length. The proof combines random binary linear hashing of substring counts with a two-colouring argument. A linear dependence among differences of substring-count vectors forces their local changes to overlap, and this overlap lowers the redundancy coefficient from $2t$ to $2t-1$. The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.

0.52

The Generalized Random Access Problem for Linear Codes

cs.IT math.CO ·2026-08-20 ·Anina Gruica, Antonio Petrillo, Ferdinando Zullo
hot direction similarity 0.56
Abstract

Random access is a central requirement in DNA-based storage systems: one would like to recover selected information symbols without sequencing the whole encoded object. A recent combinatorial model associates to a generator matrix $G\in F_q^{k\times n}$ the random variable $τ_i(G)$, measuring the number of sampled columns needed to recover the information vector $e_i$. We study the cardinality-based extremal and finite-geometric aspects of simultaneous multi-symbol recovery. For a nonempty set $I\subseteq[k]$, let $τ_I(G)$ denote the number of random column samples needed until all vectors $e_i$, $i\in I$, lie in the span of the observed columns. This variable interpolates between the singleton random access problem and the full-recovery problem underlying coverage depth. For each $m$, we introduce uniform worst-case and average parameters over all requested sets $I$ with $|I|=m$. Using the known subset-counting formula for $E[τ_I(G)]$, we establish general upper and lower bounds for these parameters. In particular, the lower bounds are expressed through order statistics of the singleton recovery variables and specialize to the known singleton bounds when $m=1$. For systematic MDS encoders, we record an equivalent form of the known multi-symbol expectation formula and derive monotonicity and asymptotic consequences. For simplex encoders in arbitrary dimension, we obtain closed formulae in terms of Gaussian binomial coefficients; the full-recovery endpoint agrees with the known coverage-depth formula for simplex codes. Finally, in dimension three we study balanced quasi-arcs and compare their values with the simplex and MDS benchmarks.

0.49

Quadratic reset bounds for finite maximal prefix codes

cs.FL ·2026-11-03 ·Samrath Singh Chadha
theory similarity 0.55
Abstract

Let $C$ be a finite maximal prefix code of maximum codeword length $k\ge2$. We prove that, whenever the literal decoder of $C$ is synchronizing, it has a reset word of length at most $(k-1)(4k-5)$. The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth $k-1$, is either identically zero or nonzero on a word of length at most $2k-3$. The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are $k-1$ and $k$, we prove the sharper bound $2(k-1)^2-1$ and characterize equality. The binary code with the single short word $a^{k-1}$ attains this bound for every $k\ge2$; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.

0.12