Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata
Abstract
We characterize the largest admissible side length of fixed-margin square Hankel submatrices generated by probabilistic realizations on a d-point carrier and quantum linear realizations on a d-dimensional Hilbert space, when prefix and suffix word lengths are bounded by T. Using a four-symbol transition alphabet shared by all selected rows and columns, we show that, for fixed margins λ2>0 and λ1+λ2<1, the corresponding side lengths satisfy ln NQ,4=Θλ1,λ2(min{d2,T}) for completely positive trace-preserving (CPTP) quantum realizations and ln NS,4=Θλ1,λ2(min{d,T}) for probabilistic automata. Four unitary and four permutation transition maps attain the corresponding orders. At zero false-acceptance tolerance (λ2=0 with 0≤λ1<1), all four model classes satisfy ln N=Θ(min{ln d,T}). The upper bounds follow from state-space packing and word counting, while the lower bounds combine explicit transition tuples with Grassmannian and positive-rate codebooks whose existence follows from the probabilistic method. These results establish sharp dimension--word-length tradeoffs for bounded-word Hankel tables.
Related
- Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension
- Bounded VC-dimension implies the Erdős--Rado sunflower conjecture
- Finite Borel asymptotic dimension of bounded-to-one commutative monoid actions
- Largest Sperner families with bounded VC-dimension
- Intrinsic-dimension empirical Bernstein inequalities for bounded self-adjoint operators
BibTeX
@misc{zhao2026hankel,
title = {{Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata}},
author = {Yixin Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21797},
eprint = {2610.21797},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21797},
}
RIS
TY - UNPB
TI - Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata
AU - Yixin Zhao
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.21797
UR - https://arxiv.org/abs/2610.21797
AB - We characterize the largest admissible side length of fixed-margin square Hankel submatrices generated by probabilistic realizations on a d-point carrier and quantum linear realizations on a d-dimensional Hilbert space, when prefix and suffix word lengths are bounded by T. Using a four-symbol transition alphabet shared by all selected rows and columns, we show that, for fixed margins λ_2>0 and λ_1+λ_2<1, the corresponding side lengths satisfy ln N_Q,4=Θ_λ_1,λ_2(min{d^2,T}) for completely positive trace-preserving (CPTP) quantum realizations and ln N_S,4=Θ_λ_1,λ_2(min{d,T}) for probabilistic automata. Four unitary and four permutation transition maps attain the corresponding orders. At zero false-acceptance tolerance (λ_2=0 with 0≤λ_1<1), all four model classes satisfy ln N=Θ(min{ln d,T}). The upper bounds follow from state-space packing and word counting, while the lower bounds combine explicit transition tuples with Grassmannian and positive-rate codebooks whose existence follows from the probabilistic method. These results establish sharp dimension--word-length tradeoffs for bounded-word Hankel tables.
ER -