The triple rendezvous time of a synchronizing automaton can be floor(4n/3)

Abstract

For every n >= 9 we construct a strongly connected synchronizing automaton with two letters and n states whose shortest word merging some three distinct states has length floor(4n/3). One letter is a permutation, and the other has rank n-1. Complete transition maps and three parameterized diagrams define the construction. Integer labels on state pairs prove the lower bound, and an explicit word attains it. For n not divisible by 3, the same construction contains a state whose shortest word merging it with some other state has length floor(4n/3)-1. The main article includes every part of the construction proof, including the three small synchronization cases. Additional results and computational data give the separate finite enumerations and upper bounds for restricted classes. Preprint. Not externally peer reviewed. The main construction proof is self-contained. Additional results and computational data accompany the article. Reproduction note: Extract the archive under an additional parent directory, for example C:\Research\t3-publication-artifact. Run circular_replay/circular_gpu.py with --reference pointing to the corresponding original histogram in history/circular_before_sync_filter. Direct extraction at the drive root may cause an import-time IndexError. This compatibility issue does not change the manuscript or numerical results.