Quadratic bounds for uncompletable words and matrix mortality
Abstract
Every finite nonempty incomplete uniquely decipherable code with maximum word length k has an uncompletable word of length at most 4k2−3k. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer n× n matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most 4n2−3n. A binary partial deterministic family with 2k−1 states has shortest zero product of length k2+k−1, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.
Related
- Markovian Random Words, a Gaussian Random Matrix Model and Beyond
- Quadratic Reciprocity via Vandermonde Matrix
- Uniform bounds for bubbles of neutral quadratic polynomials
- Sharp Quadratic Bounds for Anticanonical Volumes of Weak Fano Surfaces
- Matrix-Free Moment-Matching Method for Reduced-Order Modeling of Quadratic-Bilinear Descriptor Systems with Multiple Inputs
BibTeX
@misc{chandelkar2026quadratic,
title = {{Quadratic bounds for uncompletable words and matrix mortality}},
author = {Rahul Chandelkar and Samrath Singh Chadha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30817},
eprint = {2609.30817},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30817},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quadratic bounds for uncompletable words and matrix mortality
AU - Rahul Chandelkar
AU - Samrath Singh Chadha
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.30817
UR - https://arxiv.org/abs/2609.30817
AB - Every finite nonempty incomplete uniquely decipherable code with maximum word length k has an uncompletable word of length at most 4k^2−3k. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer n× n matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most 4n^2−3n. A binary partial deterministic family with 2k−1 states has shortest zero product of length k^2+k−1, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.
ER -