Quadratic limits found for uncompletable words and zero matrix products

Quadratic bounds for uncompletable words and matrix mortality

Formal Languages and Automata Theory

Summary

Some sets of code words can’t be completed to represent all possible messages, and finding a short example of such uncompletable words helps understand this limitation. The authors found a mathematical rule that the shortest uncompletable word in such cases is at most about four times the square of the maximum word length, which doesn’t depend on how many code words there are. They also extended this idea to certain collections of matrices, showing that you can multiply some of these matrices a limited number of times to get a zero result, with rigorous size limits. They made their proofs and algorithms fully precise and checked in a formal verification system called Lean.

What this means in practice

  • For software verification teams: Decide whether a set of code words can represent all messages using a verified polynomial-time algorithm to find uncompletable words or confirm completeness.
  • For control systems engineers: Detect zero products in families of matrices efficiently, which relates to stability analysis in control systems with constrained cycles.

A theory result. No direct application yet.

Authors

Rahul Chandelkar, Samrath Chadha

Abstract

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\times 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.
View PDFOpen arXiv