The compress-with-another threshold of the series Aₖ: an upper bound 4n/3 for every k, exact values to n = 186, and a one-letter correction

Abstract

Szykuła's recent survey of open problems on synchronising automata introduces the compress-with-another threshold of a state — the length of a shortest word sending that state and some other state to a common image — and records a conjecture, for a series Aₖ of binary automata on n = 3k+6 states credited to a 2018 master's thesis of Dżyga: Aₖ is synchronising, and the shortest word compressing q₀ with another state is (ab)ᵏ⁺²a(ab)ᵏ⁺², of length (4)/(3)n. The survey reports a computational check for n ≤ 21 only and says that even the synchronisation clause seems difficult to prove; it proves nothing about the series. We prove, for every k ≥ 1 and with no computation, that the word (ba)ᵏ⁺²(ab)ᵏ⁺², of length exactly (4)/(3)n, sends q₀ and q₂ to a common state, so the compress-with-another threshold of q₀ is at most (4)/(3)n for every k. The same identity locates a one-letter slip in the conjecture: (ab)ᵏ⁺²a(ab)ᵏ⁺² = a · (ba)ᵏ⁺²(ab)ᵏ⁺², and a fixes q₀, so the exhibited word is the shorter word with a redundant leading letter and has length (4)/(3)n + 1, one more than the value stated in the same sentence. Both halves of that sentence are true, of different quantities: we show that the merging distance of the pair {q₀,q₁} is exactly (4)/(3)n + 1 and is attained by the exhibited word, while the threshold — the minimum over all partners — is exactly (4)/(3)n, both for k = 1, …, 60, that is n = 9, …, 186. The matching lower bounds rest on a ranking-function certificate whose three checked properties imply the bound however the certificate was produced. We also exhibit reset words showing Aₖ synchronising for k ≤ 40 (n ≤ 126), and determine the pairwise merging diameter of Aₖ for k ≤ 16: it is (5k²+32k+47)/4 for odd k and (5k²+34k+44)/4 for even k, asymptotically (5)/(36)n². Every theorem below is machine-checked in Lean 4. The general lower bound cwa(q₀) ≥ (4)/(3)n, and synchronisation for every k, remain open.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   599349760f33f598d48f3fcf6cba539fe4bff422d25e445e952ad61d5587f796