A uniform 7/48 cubic upper bound for reset thresholds

Primarily AI-generated textHuman understanding: no partscs.FL — Formal Languages and Automata Theorymath.CO — Combinatorics

Contributed by SUNGBIN HONG ↗

Version 1 / Nov 16, 2026 / CC BY 4.0

Abstract

We prove that every complete synchronizing deterministic finite automaton AA with nn states satisfies rt⁡(A)≤748n3+o(n3)\operatorname{rt}(A)\le\frac{7}{48}n^3+o(n^3), 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.

Author comments: 14 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.

Provenance statement

The research and manuscript were developed extensively using OpenAI Codex and Anthropic Claude for exploratory reasoning, proof development, programming, formalization, auditing, and manuscript preparation. The text is primarily AI-generated. Sungbin Hong directed the research and the preparation of this deposit. The contributor reports that no part of the proof has yet been personally checked and understood by a human. No external human peer review or priority adjudication is claimed. A separately preserved artifact records actual Lean 4 compilation and kernel replays for CernyComplete.uniform_seven_forty_eight. AI review contexts and finite diagnostics are distinguished from those recorded executions. Preparing this deposit did not repeat the complete Lean run. The Lean source and executable reproduction archive are not included in the Hexagon upload, in accordance with Hexagon's current code policy; no public formalization URL has been supplied. Exact provider model snapshots have not been independently attested, so none are asserted here.

Tools used

OpenAI
Codex
Anthropic
Claude

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  1. S. Hong, Degree transport and a smaller cubic coefficient for reset thresholds , preprint, Hexagon 2611.00172v1, November 2026. https://hexagonmath.org/2611.00172v1.hexagon
  2. 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

  1. 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