FPRD LabShare an approach

← Claims

Theorem · exact witness family

FPRD-LT-T03

Binary J-trivial actions can require shortest words of length n

Exact statement

For every n ≥ 5, there is a minimal binary n-state DFA with J-trivial transition monoid and a target transformation whose shortest representative has length exactly n. Thus the conjectured n − 1 bound for binary L-trivial inputs is false already inside the J-trivial subclass.

StatusSelf-contained construction and proof; no external review
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The five-state extremal extends uniformly. Its order and confluence put the family in the smaller J-trivial class, so the counterexample does not depend on the full freedom of L-trivial actions.

Definitions

  • On Q_n={0,1,…,n−1}, a maps 0 to 2 and n−1 to 1 and fixes every other state; b maps i to i+1 for 2≤i<n−1 and fixes 0,1,n−1.
  • The target is f_n=(n−1,1,…,1), represented by w_n=b a b^(n−4) a b.

Hypotheses and scope

  • The alphabet is exactly binary and n is at least five.

Proof or evidence

The DFA is ordered by 0<2<...<n-1<1, is confluent, reachable from 0, and minimal with final set {1}; hence its syntactic and transition monoid is J-trivial. The displayed word has length n and realizes the target. Any target word needs a b before its first a, at least n-3 later b's, and either a second a or at least 2n-6 b's around its sole a, giving the matching lower bound n.

Binary family and exact lower bound →

Verification notes

Preserved scripts checked order, confluence, reachability, minimality, and the displayed target through n=64; full monoid closure, both Green-trivialities, exact diameter, and the closed monoid-size formula were checked through n=12. A separate implementation reconfirmed target distances for n=5 through 18, both Green trivialities through n=12, and the hostile n=4 boundary where bab has length three.

Limitations

  • The lower bound is linear and therefore does not refute polynomial certificates or NP membership.
  • No novelty or priority claim is made, and no external specialist review is recorded.

Open work

Seek a polynomial upper bound for fixed binary alphabets or a family with superpolynomial shortest representatives; the linear lower bound alone does not settle complexity.