Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
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 Dq,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 Lq(j) for the number of Lyndon words of length j over an alphabet of size q, we deduce the improved upper bound Dq,k(n)=O (nEq(k)), Eq(k)=∑j=1kj Lq(j)−1 . In the case of a binary alphabet this bound satisfies D2,k(n)=O (n4· 2k−1). We then prove matching lower bounds in the first two nontrivial cases: Dq,2(n)=Θ (nq2−1) for every alphabet size q, and D2,3(n)=Θ(n9) 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.
Related
- The Expected Number of Distinct Substrings in an Alphabet String
- Improved LCL Equivalences and Curve Decoding Alphabet Sizes
- Counting almost independent sets in regular graphs
- On Counting Independent Sets in Regular Hypergraphs
- Finite Bases for Truncated Cyclic Group Flat Semirings with Two Independent Parameters
BibTeX
@misc{nilforoushan2026improved,
title = {{Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters}},
author = {Arman Nilforoushan and Farzad Parvaresh},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23106},
eprint = {2609.23106},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23106},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
AU - Arman Nilforoushan
AU - Farzad Parvaresh
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.23106
UR - https://arxiv.org/abs/2609.23106
AB - 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 (n^E_q(k)), E_q(k)=∑_j=1^kj L_q(j)−1 . In the case of a binary alphabet this bound satisfies D_2,k(n)=O (n^4· 2^k−1). We then prove matching lower bounds in the first two nontrivial cases: D_q,2(n)=Θ (n^q^2−1) 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.
ER -