A uniform 7/48 cubic upper bound for reset thresholds
Version 1 / Nov 16, 2026 / CC BY 4.0
Abstract
We prove that every complete synchronizing deterministic finite
automaton with states satisfies
,
uniformly over the automaton and its finite alphabet.
The coefficient is the milestone proposed in Trahtman's 2011 half-rank
approach.
The argument fixes a short word whose kernel is stable over a dyadic
length interval. Degree transport in the graphs of pairs mergeable by
short words, combined with a simultaneous selection of times of small
degree growth, gives a compression bound for every sufficiently large
subset of states. The bound remains available after replacing the current
word. We combine it with the cheap-gap construction and the Pin--Frankl
rank upgrade: the cost of reaching half rank is paid by a saving in the
subsequent rank reductions. The required scalar comparison has an
elementary analytic proof over its entire parameter domain.
An explicit two-parameter estimate proves uniformity and extends the
result from strongly connected automata to arbitrary complete
synchronizing automata. The full theorem, including the word constructions used as classical
inputs, has also been formalized in Lean 4.
Provenance statement
Tools used
- OpenAI
- Codex
- Anthropic
- Claude
References
- J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi , Matematicko-fyzikálny časopis 14 (3) (1964), 208--216. In Slovak. https://dml.cz/dmlcz/126647.link
- P. Frankl, An extremal problem for two families of sets , European Journal of Combinatorics 3 (1982), 125--127. doi:10.1016/S0195-6698(82)80025-5 (https://doi.org/10.1016/S0195-6698(82)80025-5).DOI
- J.-E. Pin, On two combinatorial problems arising from automata theory , in Combinatorial Mathematics, North-Holland Mathematics Studies 75 (1983), 535--548. doi:10.1016/S0304-0208(08)73432-7 (https://doi.org/10.1016/S0304-0208(08)73432-7).DOI
- M. Szykuł a, Improving the upper bound on the length of the shortest reset words , 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs 96 , 56:1--56:13. doi:10.4230/LIPIcs.STACS.2018.56 (https://doi.org/10.4230/LIPIcs.STACS.2018.56). arXiv:1702.05455 (https://arxiv.org/abs/1702.05455).arXivDOI
- Y. Shitov, An improvement to a recent upper bound for synchronizing words of finite automata , Journal of Automata, Languages and Combinatorics 24 (2019), 367--373. doi:10.25596/jalc-2019-367 (https://doi.org/10.25596/jalc-2019-367). arXiv:1901.06542 (https://arxiv.org/abs/1901.06542).arXivDOI
- F. Gonze, R. M. Jungers, and A. N. Trahtman, A note on a recent attempt to improve the Pin--Frankl bound , Discrete Mathematics & Theoretical Computer Science 17 (1) (2015), 307--308. doi:10.46298/dmtcs.2101 (https://doi.org/10.46298/dmtcs.2101). arXiv:1412.0975 (https://arxiv.org/abs/1412.0975).arXivDOI
- A. N. Trahtman, Modifying the upper bound on the length of minimal synchronizing word , in Fundamentals of Computation Theory (FCT 2011), Lecture Notes in Computer Science 6914 (2011), 173--180. doi:10.1007/978-3-642-22953-4_15 (https://doi.org/10.1007/978-3-642-22953-4_15). Published-version preprint: arXiv:1104.2409v4 (https://arxiv.org/abs/1104.2409v4). The claimed upper bound was not established; see Correction,TrahtmanWithdrawal .arXivDOI
- A. N. Trahtman, Withdrawal notice for arXiv:1104.2409 , version 7, March 21, 2014; the first withdrawn version is version 5, December 10, 2012. https://arxiv.org/abs/1104.2409v7.arXiv
- M. V. Volkov, Synchronizing automata and the Černý conjecture , in Language and Automata Theory and Applications (LATA 2008), Lecture Notes in Computer Science 5196 (2008), 11--27. doi:10.1007/978-3-540-88282-4_4 (https://doi.org/10.1007/978-3-540-88282-4_4).DOI
- M. Szykuł a, Synchronizing automata: Open problems , Electronic Proceedings in Theoretical Computer Science 451 (2026), 33--47. doi:10.4204/EPTCS.451.3 (https://doi.org/10.4204/EPTCS.451.3). arXiv:2608.24245 (https://arxiv.org/abs/2608.24245).arXivDOI
Show all 12 referencesShow fewer references
- S. Hong, Degree transport and a smaller cubic coefficient for reset thresholds , preprint, Hexagon 2611.00172v1, November 2026. https://hexagonmath.org/2611.00172v1.hexagon
- B. Zhang, Lean formalization of the Pin--Frankl bound and Kari's theorem , software contribution, 2026. Source submission and preserved provenance: https://github.com/TheJustinSunPrize/awards/pull/605.link
Version history
- v1 · 14 pagesSubmitted by SUNGBIN HONG14 pages, including two appendices. Uniform asymptotic bound over all complete synchronizing DFAs and finite alphabets. A separate Lean 4 development and recorded verification artifact are described in the paper; code is not included in this Hexagon deposit.CurrentNov 16, 2026