Exact Collision Multiplicities in Periodic Deletion Reconstruction: Quadratic Laws for Three and Four Deletions

For the periodic source word (P=(0,1,2,4,7,3,2,6,0,7,8,7)), repeated (m) times, this preprint investigates the multiplicities of output words obtained by exactly three or four indexed deletions. For three deletions, we prove that the number of ambiguous output words is exactly (A_3(m)=12m^2-3m), and that every such word has precisely two deletion histories. For four deletions, we establish that every ambiguous output word has either two or four deletion histories, and that the number of outputs with exactly four histories is (Q_4(m)=m(m-1)/2). The proofs combine an exact local exchange criterion, connectivity of deletion-mask fibers, finite periodic residue classification, and a structural isolation theorem for exceptional exchange edges. These arguments provide an explicit classification of the collision graph for the specified periodic source. The manuscript includes a reproducible, standard-library-only Python verification program and computational certificates supporting the theoretical results. The work contributes to the combinatorics of subsequence embeddings, deletion channels, and exact reconstruction multiplicities. Its relationship to existing reconstruction and deletion-channel literature is discussed without asserting exhaustive novelty or priority. This manuscript is an author-approved preprint release candidate and has not undergone external peer review. AI Assistance Statement OpenAI ChatGPT was used substantially in mathematical exploration, programming, computational certificate design, literature discovery, proof organization, and manuscript drafting. The named author, Ivo Vajc, is responsible for reviewing the mathematical arguments, checking the released source files and computational results, verifying bibliographic references and originality claims, and making the final decision regarding submission and publication. AI assistance does not constitute independent peer review or formal verification. Author Approval — Granted for Release-Candidate Preparation Author: Ivo Vajc Affiliation: Independent Researcher ORCID: 0009-0005-5145-6491 Manuscript version: 1.0 Date: 2026-11-02 Status: Author-approved release candidate. The author has authorized preparation of the manuscript and supporting research package for potential public deposition on Zenodo. Final inspection of the released files and the decision to publish remain the responsibility of the author. This declaration does not represent external peer review, journal acceptance, or a cryptographic signature.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-02
DOI
https://doi.org/10.5281/zenodo.23889268
Primary Topic
semigroups and automata theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Exact Collision Multiplicities in Periodic Deletion Reconstruction: Quadratic Laws for Three and Four Deletions

Ivo Vajc
1 links
Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
preprint

Exact Collision Multiplicities in Periodic Deletion Reconstruction: Quadratic Laws for Three and Four Deletions

Ivo Vajc
preprint en

Abstract

For the periodic source word (P=(0,1,2,4,7,3,2,6,0,7,8,7)), repeated (m) times, this preprint investigates the multiplicities of output words obtained by exactly three or four indexed deletions. For three deletions, we prove that the number of ambiguous output words is exactly (A_3(m)=12m^2-3m), and that every such word has precisely two deletion histories. For four deletions, we establish that every ambiguous output word has either two or four deletion histories, and that the number of outputs with exactly four histories is (Q_4(m)=m(m-1)/2). The proofs combine an exact local exchange criterion, connectivity of deletion-mask fibers, finite periodic residue classification, and a structural isolation theorem for exceptional exchange edges. These arguments provide an explicit classification of the collision graph for the specified periodic source. The manuscript includes a reproducible, standard-library-only Python verification program and computational certificates supporting the theoretical results. The work contributes to the combinatorics of subsequence embeddings, deletion channels, and exact reconstruction multiplicities. Its relationship to existing reconstruction and deletion-channel literature is discussed without asserting exhaustive novelty or priority. This manuscript is an author-approved preprint release candidate and has not undergone external peer review. AI Assistance Statement OpenAI ChatGPT was used substantially in mathematical exploration, programming, computational certificate design, literature discovery, proof organization, and manuscript drafting. The named author, Ivo Vajc, is responsible for reviewing the mathematical arguments, checking the released source files and computational results, verifying bibliographic references and originality claims, and making the final decision regarding submission and publication. AI assistance does not constitute independent peer review or formal verification. Author Approval — Granted for Release-Candidate Preparation Author: Ivo Vajc Affiliation: Independent Researcher ORCID: 0009-0005-5145-6491 Manuscript version: 1.0 Date: 2026-11-02 Status: Author-approved release candidate. The author has authorized preparation of the manuscript and supporting research package for potential public deposition on Zenodo. Final inspection of the released files and the decision to publish remain the responsibility of the author. This declaration does not represent external peer review, journal acceptance, or a cryptographic signature.

Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon