AFTD Auto-Formalizing Theoretical Domains

dfa_prod_attains_lower_bound_of_subsingleton

theoremverifiedformalization

Proposition 3.13 of arXiv:2611.09136: For any two DFAs A₁ and A₂ over a subsingleton (unary) alphabet, their direct product always attains the lower bound max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) on its reset threshold.

Statement

theorem dfa_prod_attains_lower_bound_of_subsingleton {α σ₁ σ₂ : Type*} [Subsingleton α] (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : dfa_prod_attains_lower_bound A₁ A₂
Formalizes
arXiv:2611.09136 Proposition 3.13
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • dfa_prod_attains_lower_boundA pair of DFAs A₁ and A₂ over the same alphabet attains the lower bound of Proposition 3.4 if the reset threshold of their direct…
  • dfa_reset_thresholdThe reset threshold dfa_reset_threshold A of a deterministic finite automaton A : DFA α σ is the infimum in WithTop ℕ of the lengths…
  • dfa_prod_reset_threshold_boundsFor any two deterministic finite automata A₁ and A₂ over the same alphabet, the reset threshold of their direct product satisfies…
  • dfa_prodThe direct product dfa_prod A₁ A₂ of two deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over alphabet α is the DFA…
  • dfa_prod_is_synchronizing_iffA word w is synchronizing for the direct product dfa_prod A₁ A₂ of two deterministic finite automata if and only if w is…
  • dfa_is_synchronizingA word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for all…

Read back from the Lean

For any types α, σ₁, and σ₂ where α is a subsingleton (i.e. an alphabet with at most one symbol), and for any DFAs A₁ (with state type σ₁ over alphabet α) and A₂ (with state type σ₂ over alphabet α), the reset threshold of their product DFA dfa_prod A₁ A₂ equals the maximum of the reset threshold of A₁ and the reset threshold of A₂.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The lower bound max(threshold(A₁), threshold(A₂)) ≤ threshold(A₁ × A₂) holds in general for direct products of DFAs. Over a subsingleton (unary) alphabet, any word at least as long as a synchronizing word is also synchronizing, because any longer word is formed simply by appending a suffix. If either automaton cannot be synchronized, both sides equal ∞. Otherwise, choosing minimal synchronizing words w₁ for A₁ and w₂ for A₂, the longer of the two synchronizes both automata simultaneously, yielding a synchronizing word for the product automaton of length max(|w₁|, |w₂|) and matching the lower bound.

  1. Appending any suffix to a synchronizing word yields another synchronizing word.

    For any two states q₁ and q₂, evaluating the DFA on w ++ v decomposes by `DFA.evalFrom_of_append` into evaluating w to reach intermediate states, followed by v. Since w synchronizes the DFA, the two intermediate states are identical, and running v from the same state produces the same final state.

    lines 3–5

    uses DFA.evalFrom_of_append

      intro q₁ q₂
      simp only [DFA.evalFrom_of_append]
      rw [hw q₁ q₂]
  2. Over a subsingleton alphabet, any word l₂ with |l₁| ≤ |l₂| equals l₁ concatenated with the suffix of l₂ after the first |l₁| elements.

    The prefix of l₂ of length |l₁| has length |l₁| by `List.length_take` and matches l₁ elementwise by `Subsingleton.elim` because the alphabet has at most one element, so `List.ext_get` identifies this prefix with l₁. Substituting this into the list partition identity `List.take_append_drop` proves the equality.

    lines 9–13

    uses List.ext_get, Subsingleton.elim, List.length_take, List.take_append_drop

      have htake : l₂.take l₁.length = l₁ := by
        refine List.ext_get ?_ (fun n h₁ h₂ => Subsingleton.elim _ _)
        simp [List.length_take, h]
      conv_lhs => rw [← List.take_append_drop l₁.length l₂]
      rw [htake]
  3. Over a subsingleton alphabet, if l₁ is synchronizing and |l₁| ≤ |l₂|, then l₂ is also synchronizing.

    By `dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop`, l₂ decomposes as l₁ followed by a suffix. Since l₁ synchronizes the DFA, appending this suffix also yields a synchronizing word by `dfa_prod_attains_lower_bound_of_subsingleton_append_right`.

    lines 18–19

    uses dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop, dfa_prod_attains_lower_bound_of_subsingleton_append_right

      rw [dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop l₁ l₂ h]
      exact dfa_prod_attains_lower_bound_of_subsingleton_append_right A l₁ (l₂.drop l₁.length) hw
  4. Unfolding definitions, it suffices to prove equality of thresholds, and the lower bound max(threshold(A₁), threshold(A₂)) ≤ threshold(A₁ × A₂) already holds.

    The definition `dfa_prod_attains_lower_bound` is simplified to equality between the product threshold and the maximum of the component thresholds. The general lower bound on the direct product reset threshold is provided by `dfa_prod_reset_threshold_bounds`.

    lines 23–24

    uses dfa_prod_reset_threshold_bounds

      dsimp [dfa_prod_attains_lower_bound]
      have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1
  5. If threshold(A₁) = ⊤, the product DFA also has reset threshold ⊤, satisfying the equality.

    When threshold(A₁) = ⊤, the lower bound max(threshold(A₁), threshold(A₂)) simplifies to ⊤ by `max_top_left`. Since ⊤ ≤ threshold(A₁ × A₂), `top_le_iff.mp` forces the product threshold to be ⊤.

    lines 25–27

    uses max_top_left, top_le_iff.mp

      by_cases h₁ : dfa_reset_threshold A₁ = ⊤
      · rw [h₁, max_top_left] at h_bound ⊢
        exact top_le_iff.mp h_bound
  6. If threshold(A₂) = ⊤, the product DFA also has reset threshold ⊤, satisfying the equality.

    Similarly, if threshold(A₂) = ⊤, the lower bound simplifies to ⊤ by `max_top_right`, which implies threshold(A₁ × A₂) = ⊤ by `top_le_iff.mp`.

    lines 28–30

    uses max_top_right, top_le_iff.mp

      by_cases h₂ : dfa_reset_threshold A₂ = ⊤
      · rw [h₂, max_top_right] at h_bound ⊢
        exact top_le_iff.mp h_bound
  7. The set of lengths of synchronizing words for A₁ is nonempty.

    If this set were empty, its infimum in WithTop ℕ would be ⊤ by `WithTop.sInf_empty` (via `Set.not_nonempty_iff_eq_empty`), contradicting the assumption that threshold(A₁) ≠ ⊤.

    lines 31–36

    uses Set.not_nonempty_iff_eq_empty, WithTop.sInf_empty

      have h_ne₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty := by
        dsimp [dfa_reset_threshold] at h₁
        by_contra he
        rw [Set.not_nonempty_iff_eq_empty] at he
        rw [he, WithTop.sInf_empty] at h₁
        exact h₁ rfl
  8. The set of lengths of synchronizing words for A₂ is nonempty.

    Identically, if the set of lengths of synchronizing words for A₂ were empty, its infimum would be ⊤, contradicting threshold(A₂) ≠ ⊤.

    lines 37–42

    uses Set.not_nonempty_iff_eq_empty, WithTop.sInf_empty

      have h_ne₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty := by
        dsimp [dfa_reset_threshold] at h₂
        by_contra he
        rw [Set.not_nonempty_iff_eq_empty] at he
        rw [he, WithTop.sInf_empty] at h₂
        exact h₂ rfl
  9. There exist minimal synchronizing words w₁ for A₁ and w₂ for A₂ realizing the respective thresholds, and it suffices to show threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|).

    By `csInf_mem`, nonempty sets in ℕ attain their infimum, yielding synchronizing words w₁ and w₂ of lengths equal to threshold(A₁) and threshold(A₂). Combined with the existing lower bound, antisymmetry (`le_antisymm`) reduces the problem to establishing the upper bound threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|).

    lines 43–46

    uses csInf_mem, le_antisymm

      obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h_ne₁
      obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h_ne₂
      dsimp only at heq₁ heq₂
      apply le_antisymm _ h_bound
  10. In the case |w₁| ≤ |w₂|, threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|).

    Comparing lengths using `le_total`, assume |w₁| ≤ |w₂|. Since w₁ synchronizes A₁, the longer word w₂ also synchronizes A₁ by `dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le`. Since w₂ synchronizes both A₁ and A₂, it synchronizes the product A₁ × A₂ by `dfa_prod_is_synchronizing_iff`. By `sInf_le`, the product threshold is at most |w₂|, which is at most max(threshold(A₁), threshold(A₂)) by `le_max_right`, completing this branch via `le_trans`.

    lines 47–58

    uses dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le, dfa_prod_is_synchronizing_iff, le_max_right, le_total, le_trans, sInf_le

      rcases le_total w₁.length w₂.length with hle | hle
      · have hsync₁ : dfa_is_synchronizing A₁ w₂ :=
          dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₁ w₁ w₂ hw₁ hle
        have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₂ :=
          (dfa_prod_is_synchronizing_iff A₁ A₂ w₂).mpr ⟨hsync₁, hw₂⟩
        have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₂.length : WithTop ℕ) := by
          dsimp [dfa_reset_threshold]
          exact sInf_le ⟨w₂, hprod, rfl⟩
        have hmax : (w₂.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by
          rw [heq₂]
          exact le_max_right _ _
        exact le_trans h_le hmax
  11. In the case |w₂| ≤ |w₁|, threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|), completing the proof.

    Symmetrically, when |w₂| ≤ |w₁|, w₁ synchronizes A₂ by `dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le`, so w₁ synchronizes A₁ × A₂ by `dfa_prod_is_synchronizing_iff`. Then threshold(A₁ × A₂) ≤ |w₁| by `sInf_le`, and |w₁| ≤ max(threshold(A₁), threshold(A₂)) by `le_max_left`, completing the proof via `le_trans`.

    lines 59–69

    uses dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le, dfa_prod_is_synchronizing_iff, le_max_left, le_trans, sInf_le

      · have hsync₂ : dfa_is_synchronizing A₂ w₁ :=
          dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₂ w₂ w₁ hw₂ hle
        have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₁ :=
          (dfa_prod_is_synchronizing_iff A₁ A₂ w₁).mpr ⟨hw₁, hsync₂⟩
        have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₁.length : WithTop ℕ) := by
          dsimp [dfa_reset_threshold]
          exact sInf_le ⟨w₁, hprod, rfl⟩
        have hmax : (w₁.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by
          rw [heq₁]
          exact le_max_left _ _
        exact le_trans h_le hmax
DFA.evalFrom_of_append
Evaluating a DFA from a state on the concatenation w ++ v is equal to evaluating on v from the state reached after w.
List.ext_get
Two lists are equal if they have the same length and their elements at each position are equal.
List.length_take
Taking i elements from a list yields a prefix of length min(i, length of list).
List.take_append_drop
A list is equal to its prefix of length i concatenated with its suffix after index i.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
WithTop.sInf_empty
In ℕ ∪ {∞}, the infimum of the empty set is ⊤.
csInf_mem
Any nonempty set of natural numbers contains its infimum (the infimum is attained).
dfa_prod_attains_lower_bound_of_subsingleton_append_right
Appending any suffix to a synchronizing word for a DFA yields another synchronizing word.
dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop
Over a subsingleton alphabet, if |l₁| ≤ |l₂|, then l₂ equals l₁ concatenated with the suffix of l₂ after the first |l₁| elements.
dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le
Over a subsingleton alphabet, if l₁ is synchronizing and |l₁| ≤ |l₂|, then l₂ is also synchronizing.
dfa_prod_is_synchronizing_iff
A word synchronizes a direct product DFA if and only if it synchronizes both factor DFAs.
dfa_prod_reset_threshold_bounds
The reset threshold of a direct product DFA is at least the maximum of the thresholds of its factors and at most their sum.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
le_max_left
In a linear order, a ≤ max(a, b).
le_max_right
In a linear order, b ≤ max(a, b).
le_total
In a linear order, any two elements are comparable: a ≤ b or b ≤ a.
le_trans
If a ≤ b and b ≤ c, then a ≤ c.
max_top_left
The maximum of ⊤ and any element a is ⊤.
max_top_right
The maximum of any element a and ⊤ is ⊤.
sInf_le
The infimum of a set is less than or equal to any element in the set.
Set.not_nonempty_iff_eq_empty
A set is not nonempty if and only if it is empty.
top_le_iff.mp
In an order with a greatest element ⊤, if ⊤ ≤ x then x = ⊤.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma dfa_prod_attains_lower_bound_of_subsingleton_append_right {α σ : Type*} (A : DFA α σ) (w v : List α)    (hw : dfa_is_synchronizing A w) : dfa_is_synchronizing A (w ++ v) := by  intro q₁ q₂  simp only [DFA.evalFrom_of_append]  rw [hw q₁ q₂]lemma dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop {α : Type*} [Subsingleton α] (l₁ l₂ : List α)    (h : l₁.length ≤ l₂.length) : l₂ = l₁ ++ l₂.drop l₁.length := by  have htake : l₂.take l₁.length = l₁ := by    refine List.ext_get ?_ (fun n h₁ h₂ => Subsingleton.elim _ _)    simp [List.length_take, h]  conv_lhs => rw [← List.take_append_drop l₁.length l₂]  rw [htake]lemma dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le {α σ : Type*} [Subsingleton α] (A : DFA α σ)    (l₁ l₂ : List α) (hw : dfa_is_synchronizing A l₁) (h : l₁.length ≤ l₂.length) :    dfa_is_synchronizing A l₂ := by  rw [dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop l₁ l₂ h]  exact dfa_prod_attains_lower_bound_of_subsingleton_append_right A l₁ (l₂.drop l₁.length) hw/-- Direct products of DFAs over a subsingleton alphabet always attain the lower bound on the reset threshold. -/theorem dfa_prod_attains_lower_bound_of_subsingleton {α σ₁ σ₂ : Type*} [Subsingleton α] (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : dfa_prod_attains_lower_bound A₁ A₂ := by  dsimp [dfa_prod_attains_lower_bound]  have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1  by_cases h₁ : dfa_reset_threshold A₁ = ⊤  · rw [h₁, max_top_left] at h_bound ⊢    exact top_le_iff.mp h_bound  by_cases h₂ : dfa_reset_threshold A₂ = ⊤  · rw [h₂, max_top_right] at h_bound ⊢    exact top_le_iff.mp h_bound  have h_ne₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty := by    dsimp [dfa_reset_threshold] at h₁    by_contra he    rw [Set.not_nonempty_iff_eq_empty] at he    rw [he, WithTop.sInf_empty] at h₁    exact h₁ rfl  have h_ne₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty := by    dsimp [dfa_reset_threshold] at h₂    by_contra he    rw [Set.not_nonempty_iff_eq_empty] at he    rw [he, WithTop.sInf_empty] at h₂    exact h₂ rfl  obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h_ne₁  obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h_ne₂  dsimp only at heq₁ heq₂  apply le_antisymm _ h_bound  rcases le_total w₁.length w₂.length with hle | hle  · have hsync₁ : dfa_is_synchronizing A₁ w₂ :=      dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₁ w₁ w₂ hw₁ hle    have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₂ :=      (dfa_prod_is_synchronizing_iff A₁ A₂ w₂).mpr ⟨hsync₁, hw₂⟩    have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₂.length : WithTop ℕ) := by      dsimp [dfa_reset_threshold]      exact sInf_le ⟨w₂, hprod, rfl⟩    have hmax : (w₂.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by      rw [heq₂]      exact le_max_right _ _    exact le_trans h_le hmax  · have hsync₂ : dfa_is_synchronizing A₂ w₁ :=      dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₂ w₂ w₁ hw₂ hle    have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₁ :=      (dfa_prod_is_synchronizing_iff A₁ A₂ w₁).mpr ⟨hw₁, hsync₂⟩    have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₁.length : WithTop ℕ) := by      dsimp [dfa_reset_threshold]      exact sInf_le ⟨w₁, hprod, rfl⟩    have hmax : (w₁.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by      rw [heq₁]      exact le_max_left _ _    exact le_trans h_le hmax
See it in the graphDiscuss this resultChallenge it