FPRD LabShare an approach

← Claims

Theorem, exact delay, and DFA construction

FPRD-T86

Exact saturation delay for bounded periods

Exact statement

Let Γ\Gamma be finite and nonempty and B≥2B\ge2. At every length at least 2B−22B-2, each nonempty profile of periods through BB consists exactly of the positive multiples through BB of its least period. One next letter preserves the entire profile and every other letter destroys it. Hence SmallPer⁡B\operatorname{SmallPer}_B and its complement share a complete DFA transition graph with at most 1+∑i=02B−3∣Γ∣i+∑d=1B∣Γ∣d1+\sum_{i=0}^{2B-3}|\Gamma|^i+\sum_{d=1}^B|\Gamma|^d states. Over a non-unary alphabet the delay 2B−22B-2 is exact.

StatusProved and internally audited
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Fine–Wilf collapses all surviving bounded periods to one least-period branch after an exact finite horizon.

Hypotheses and scope

  • Periods use the ordinary positive-period convention, including vacuous periods of short words.
  • The unique-delay theorem is for B at least two; B=1 has a separate constant-word automaton.

Proof or evidence

Fine–Wilf forces every surviving period to be a multiple of the least one. All multiples require the same next letter, yielding a short-word trie followed by a rotating delay window and a sink. Explicit binary witnesses show the horizon cannot be shortened.

Principal period saturation →

Verification notes

The proof, all edge regimes, transition graph, complement polarity, binary and ternary finite regimes, and exact-delay witnesses were independently rederived and mutation-tested.

Limitations

  • The DFA recognizes only the Boolean existence of a bounded period on an already exposed word; it does not replace the two-sided quotient M_B.
  • The bound is not asserted to be minimal and gives no NFA-specific improvement.
  • It does not locate runs, anchors, or inversion output, nor improve the source decision bounds.

Open work

Determine whether the exposed-word normal form yields any useful bound after run and inversion exposure are incorporated.

Notes

Fine--Wilf is standard machinery; FPRD-T86 is a proved, independently audited instantiation for the Boolean bounded-period predicate of an already exposed word. B=1 is a separate degenerate constant-word regime, not evidence for the B >= 2 theorem. Since every DFA is an NFA, the displayed DFA upper bound is tautologically an exposed-word NFA upper bound, but no NFA-specific improvement or NFA lower bound is claimed. This does not transfer FPRD-T85's promise-NFA bounds, bound Lemma 9.1's successful-run/inversion-guessing input language, replace M_B, project through runs or inversions, improve the source paper's space bounds, or support a novelty claim.