The unary multiple-concatenation bound is not tight, and fails only in its cycle length
Abstract
Jirásek and Jirásková (arXiv:2511.03814) close their study of the state complexity of the concatenation L₁L₂… Lₖ of k regular languages with the unary case, and give an upper bound for unary automata that may carry final states in their tails: if Aᵢ has size (λᵢ,μᵢ) then L(A₁)… L(Aₖ) is recognised by a unary automaton of size (Λ, M) with Λ = lcm(λ₁,…,λₖ) and M a maximum, over subsets I of the indices, of Σᵢμᵢ - k + 1 + d_I f(I), where d_I is the greatest common divisor of the λᵢ with i ∈ I and f is the modified Frobenius number. They exhibit one instance in which the bound is met — sizes (12,2), (20,2), (30,2), minimal size (60,124), 184 states — and write that "the tightness of this upper bound in a general case remains open". We settle it: the bound is not tight. At k = 3 with cycle lengths (3,2,2) and tails (2,2,2) the bound is (6,12), that is 18 states, and yet for every one of the 8192 choices of final-state sets the concatenation is recognised by a unary automaton with at most 15 states, because the cycle length lcm(3,2,2) = 6 is never attained. The failure is confined to the cycle: at those same sizes the preperiod half M = 12 of the bound is exactly right, forced by a single witness. We also exhibit two size tuples at which the whole bound is met, both far smaller than the published example: (2,4,4) with tails (2,2,2) gives minimal size exactly (4,12), 16 states, and (1,4,6) gives exactly (12,16), 28 states — the latter with globally coprime cycle lengths and with the maximum defining M attained on a proper pair of indices. An exhaustive census over all 216 cycle-length triples with λᵢ ≤ 6 and μᵢ = 2 finds no violation of the bound, finds its preperiod half attained every time, and singles out a candidate closed form for the true cycle length, which we state as a conjecture. Finally we settle, in the unary case and for every k, a second remark the same paper leaves open: the concatenation of k-1 unary languages of at most two states each with a one-state language is recognised by a k-state automaton, and k states are necessary. All theorems below are machine-checked in Lean 4.
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
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
1db2ec2e717eb5bf28bc91504239b197bb94c2c94c71aa62718d1a9ba6235f5a
Claim ledger
Stated results
um-01known data2026-09-03
The source's own unary example is reproduced from the definitions: for unary DFAs of sizes (12,2), (20,2), (30,2) with final sets 0,13, 0,21, 0,31, the minimal DFA of L(A₁)L(A₂)L(A₃) has size exactly (60,124) – every eventual period is a multiple of 60 and no preperiod below 124 works
um-02candidate2026-09-03
The source's unary upper bound (Theorem thm:unary_finalₜails) is NOT tight: at cycle lengths (3,2,2) and tails (2,2,2) the bound is (6,12) = 18 states, but for EVERY one of the 8192 choices of final-state sets the concatenation is recognised by a unary DFA with at most 15 states, because the cycle length lcm(3,2,2) = 6 is never attained
um-03candidate2026-09-03
At the same parameters the PREPERIOD half of the source's bound is exactly right: the witness with final sets 4, 3, 3 needs a tail of at least 12 = the bound's mu in every unary DFA that recognises it. So the bound fails only in its cycle length
um-04candidate2026-09-03
The source's bound IS met at cycle lengths (2,4,4) with tails (2,2,2) and final sets 0,3, 5, 5: the minimal DFA has size exactly (4,12), 16 states – the smallest instance of the source's open question with unequal cycle lengths and final states in the tails, against its own 184-state example
um-05candidate2026-09-03
The bound is also met at cycle lengths (1,4,6) with tails (2,2,2) and final sets 1, 0,5, 0,7: minimal size exactly (12,16), 28 states – here gcd(1,4,6) = 1, so the bound can be met even when the cycle lengths are globally coprime, and the maximising subset in max_I d_I f(I) is a proper PAIR, not the whole index set
um-06routine2026-09-03
The source's k-state remark, unary case, for EVERY k: if A₁,...,Aₖ₋₁ are unary DFAs with at most two states each and Aₖ is a one-state DFA, then L(A₁)...L(Aₖ) is recognised by a unary DFA of size (1, k-1), i.e. by a k-state DFA; and k-1 copies of the odd numbers show that k states are necessary
um-07measurement2026-09-03
Exhaustive census of the tightness question at k = 3: over all 216 cycle-length triples with lambdaᵢ <= 6 and tails muᵢ = 2, and every choice of final-state sets (about 1.1e8 instances), (a) the source's bound is never violated, (b) its preperiod half is attained at every one of the 216, (c) the pair is attained at exactly 12 cycle-length multisets, and (d) the largest attainable cycle length equals max lcm_(i in I) lambdaᵢ: I nonempty, gcd_(i in I) lambdaᵢ >= 2 in all 216 cases (the same formula holds in all 1,024 k = 2 size pairs with lambdaᵢ <= 8 and muᵢ in [1,4]; it needs muᵢ >= 1, since a size-(1,0) automaton collapses the cycle to 1)
This ledger entry is reported in prose and is not bound to a Lean theorem.um-08measurement2026-09-03
The source's k-state remark holds over EVERY alphabet for k <= 6, and is tight: for r = k-1 two-state DFAs and one one-state DFA, max sc(L₁...LᵣSigma*) = r+1 exactly, attained only when every Aᵢ has its initial state non-final
This ledger entry is reported in prose and is not bound to a Lean theorem.um-09measurement2026-09-03
k-letter optimality at all nᵢ = 2: at k = 3 the binary maximum is 13 < 15 = #tau₃ and the ternary maximum is exactly 15 (reproducing the source's ternary-optimality theorem at that instance); at k = 4 the binary maximum is 18 and the TERNARY maximum is 35, strictly below #tau₄ = 37, while the source's own 4-letter all-two-state construction reaches exactly 37 – so k symbols are necessary at k = 4, nᵢ = 2, a case the source's conjecture (:1741) leaves open. That construction meets #tauₖ at k = 4, 5, 6 (37, 90, 218) but degenerates at k = 3, where its index range 2..k-2 is empty
This ledger entry is reported in prose and is not bound to a Lean theorem.Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Source. Jozef Jirásek, Galina Jirásková, *State Complexity of Multiple Concatenation*, arXiv:2511.03814 v2 (26 Nov 2025, cs.FL). Read live from arxiv.org/e-print/2511.03814v2; the single LaTeX file is MCⱼalcₐrxiv₀2.tex and every:NNN line citation in the Lean docstrings and in family.json points into it.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7