AFTD Auto-Formalizing Theoretical Domains

op_1291_extremal_reset_thresholds_characterization

theoremverifiedformalization

Open Problem OP-1291: For any synchronizable DFAs A₁ and A₂ over a common alphabet, the direct product attains the lower bound max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) if and only if there exists a word synchronizing both A₁ and A₂ of length at most max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂), and attains the upper bound dfa_reset_threshold A₁ + dfa_reset_threshold A₂ if and only if every word synchronizing both A₁ and A₂ has length at least dfa_reset_threshold A₁ + dfa_reset_threshold A₂.

Statement

theorem op_1291_extremal_reset_thresholds_characterization {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (h₁ : dfa_is_synchronizable A₁) (h₂ : dfa_is_synchronizable A₂) : (dfa_prod_attains_lower_bound A₁ A₂ ↔ ∃ w : List α, dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w ∧ (w.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂)) ∧ (dfa_prod_attains_upper_bound A₁ A₂ ↔ ∀ w : List α, dfa_is_synchronizing A₁ w → dfa_is_synchronizing A₂ w → dfa_reset_threshold A₁ + dfa_reset_threshold A₂ ≤ (w.length : WithTop ℕ))
Formalizes
arXiv:2611.09136 Sec. 7, open question 1
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • 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_prod_attains_upper_boundA pair of DFAs A₁ and A₂ over the same alphabet attains the upper bound of Proposition 3.4 if the reset threshold of their direct…
  • dfa_is_synchronizableA deterministic finite automaton A : DFA α σ is synchronizable if there exists a synchronizing word w : List α for A.
  • 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…
  • 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_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_prod_is_synchronizing_appendIf w₁ is a synchronizing word for A₁ and w₂ is a synchronizing word for A₂, then the concatenated word w₁ ++ w₂ is a…
  • 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…

Read back from the Lean

For all types α, σ₁, and σ₂, and all deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, assuming that A₁ is synchronizable (there exists a word synchronizing A₁) and A₂ is synchronizable (there exists a word synchronizing A₂), both of the following equivalences hold: 1. The reset threshold of the product automaton dfa_prod A₁ A₂ attains the lower bound max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) if and only if there exists a word w : List α that synchronizes both A₁ and A₂ whose length (in WithTop ℕ) is at most max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂). 2. The reset threshold of the product automaton dfa_prod A₁ A₂ attains the upper bound dfa_reset_threshold A₁ + dfa_reset_threshold A₂ if and only if for every word w : List α, if w synchronizes A₁ and w synchronizes A₂, then dfa_reset_threshold A₁ + dfa_reset_threshold A₂ ≤ (w.length : WithTop ℕ).

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 theorem characterizes when the direct product A₁ × A₂ of two synchronizable DFAs achieves the extremal reset threshold bounds established in Proposition 3.4. For the lower bound max(dfa_reset_threshold A₁, dfa_reset_threshold A₂), the forward direction uses the well-foundedness of WithTop ℕ to obtain a minimal-length synchronizing word for the product, which simultaneously synchronizes both automata; the reverse direction observes that any common synchronizing word witnesses an upper bound on the infimum. For the upper bound dfa_reset_threshold A₁ + dfa_reset_threshold A₂, both directions use the fact that synchronizing the product is equivalent to synchronizing both factors, converting the equality into the condition that the threshold sum is a lower bound for every common synchronizing word.

  1. The proof reduces to establishing the equivalence for the lower bound and the equivalence for the upper bound independently, starting with the forward implication of the lower bound.

    We split the conjunction into two subgoals for the lower and upper bounds, and then split the lower-bound biconditional into forward and backward implications.

    lines 3–4

      constructor
      · constructor
  2. If the direct product attains the lower bound, then there exists a word synchronizing both A₁ and A₂ of length at most max(dfa_reset_threshold A₁, dfa_reset_threshold A₂).

    Assuming the product attains the lower bound, we find an optimal synchronizing word for the product. Since A₁ and A₂ are synchronizable with words w₁ and w₂, the concatenation w₁ ++ w₂ synchronizes the product by `dfa_prod_is_synchronizing_append`, so the set of lengths of synchronizing words of the product is nonempty. By `csInf_mem`, the infimum of this nonempty set is attained by some word w, which synchronizes both A₁ and A₂ by `dfa_prod_is_synchronizing_iff`. Since w achieves the infimum, its length equals the product reset threshold, which by hypothesis equals max(dfa_reset_threshold A₁, dfa_reset_threshold A₂).

    lines 5–20

    uses dfa_prod_is_synchronizing_append, csInf_mem, dfa_prod_is_synchronizing_iff

        · intro h
          obtain ⟨w₁, hw₁⟩ := h₁
          obtain ⟨w₂, hw₂⟩ := h₂
          have h_prod_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) :=
            dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂
          have h_nonempty : ((fun w : List α => (w.length : WithTop ℕ)) ''
              {w | dfa_is_synchronizing (dfa_prod A₁ A₂) w}).Nonempty :=
            ⟨↑(w₁ ++ w₂).length, ⟨w₁ ++ w₂, h_prod_sync, rfl⟩⟩
          have h_mem := csInf_mem h_nonempty
          obtain ⟨w, hw, heq⟩ := h_mem
          have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w :=
            (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw
          refine ⟨w, hw'.1, hw'.2, ?_⟩
          change dfa_reset_threshold (dfa_prod A₁ A₂) = max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) at h
          change (w.length : WithTop ℕ) = dfa_reset_threshold (dfa_prod A₁ A₂) at heq
          rw [heq, h]
  3. If there exists a word synchronizing both A₁ and A₂ of length at most max(dfa_reset_threshold A₁, dfa_reset_threshold A₂), then the direct product attains the lower bound.

    Given a common synchronizing word w, it synchronizes the product by `dfa_prod_is_synchronizing_iff`. As the reset threshold is the infimum of synchronizing word lengths, dfa_reset_threshold (dfa_prod A₁ A₂) ≤ |w| by `sInf_le`. Composing this with |w| ≤ max(dfa_reset_threshold A₁, dfa_reset_threshold A₂) via `le_trans` gives dfa_reset_threshold (dfa_prod A₁ A₂) ≤ max(dfa_reset_threshold A₁, dfa_reset_threshold A₂). Since the reverse inequality max(...) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) is always valid by `dfa_prod_reset_threshold_bounds`, the two values are equal by `le_antisymm`.

    lines 21–30

    uses dfa_prod_is_synchronizing_iff, sInf_le, le_trans, dfa_prod_reset_threshold_bounds, le_antisymm

        · intro ⟨w, hw₁, hw₂, hw_le⟩
          have h_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) w :=
            (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩
          have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w.length : WithTop ℕ) := by
            dsimp [dfa_reset_threshold]
            exact sInf_le ⟨w, h_sync, rfl⟩
          have h_trans : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) :=
            le_trans h_le hw_le
          have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1
          exact le_antisymm h_trans h_bound
  4. Unfolding definitions and recording the known upper bound dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂, it suffices to establish both directions of the upper-bound equivalence.

    We unfold the definitions of attaining the upper bound and of reset threshold as an infimum. We extract the known bound dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂ from `dfa_prod_reset_threshold_bounds`, and split the equivalence into forward and backward implications.

    lines 31–34

    uses dfa_prod_reset_threshold_bounds

      · dsimp [dfa_prod_attains_upper_bound, dfa_reset_threshold]
        have h_le := (dfa_prod_reset_threshold_bounds A₁ A₂).2
        dsimp [dfa_reset_threshold] at h_le
        constructor
  5. If the direct product attains the upper bound, then every word synchronizing both A₁ and A₂ has length at least dfa_reset_threshold A₁ + dfa_reset_threshold A₂.

    Assuming the product attains the upper bound, the threshold sum equals dfa_reset_threshold (dfa_prod A₁ A₂). If w synchronizes both A₁ and A₂, it synchronizes the product by `dfa_prod_is_synchronizing_iff`. Because the reset threshold is the infimum of all product synchronizing word lengths, it is at most |w| by `sInf_le`, which yields the desired lower bound on |w|.

    lines 35–38

    uses sInf_le, dfa_prod_is_synchronizing_iff

        · intro h w hw₁ hw₂
          rw [← h]
          apply sInf_le
          exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩, rfl⟩
  6. If every word synchronizing both A₁ and A₂ has length at least dfa_reset_threshold A₁ + dfa_reset_threshold A₂, then the direct product attains the upper bound.

    Since the product reset threshold is already bounded above by the threshold sum, by `le_antisymm` it suffices to show that the sum is at most the product reset threshold. By `le_sInf_iff`, a value is less than or equal to an infimum if and only if it is bounded by every element in the set. Any element in the set is the length of some synchronizing word w for the product, which synchronizes both A₁ and A₂ by `dfa_prod_is_synchronizing_iff`. By hypothesis, the length of any such w is at least the sum of the thresholds.

    lines 39–45

    uses le_antisymm, le_sInf_iff, dfa_prod_is_synchronizing_iff

        · intro h
          apply le_antisymm h_le
          rw [le_sInf_iff]
          rintro - ⟨w, hw, rfl⟩
          have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w :=
            (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw
          exact h w hw'.1 hw'.2
dfa_prod_is_synchronizing_append
If w₁ synchronizes DFA A₁ and w₂ synchronizes DFA A₂, then the concatenation w₁ ++ w₂ synchronizes their direct product A₁ × A₂.
csInf_mem
In a conditionally complete linear order with a well-founded order relation, every nonempty set contains its infimum.
dfa_prod_is_synchronizing_iff
A word synchronizes the direct product A₁ × A₂ if and only if it synchronizes both A₁ and A₂.
sInf_le
The infimum of a set is less than or equal to every element of that set.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
dfa_prod_reset_threshold_bounds
For any two DFAs A₁ and A₂, the reset threshold of their direct product is at least max(reset threshold of A₁, reset threshold of A₂) and at most the sum of their reset thresholds.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
le_sInf_iff
An element a is less than or equal to the infimum of a set s if and only if a ≤ b for all b ∈ s.

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

/-- Characterization of when the direct product of two DFAs attains the lower and upper reset threshold bounds of Proposition 3.4. -/theorem op_1291_extremal_reset_thresholds_characterization {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (h₁ : dfa_is_synchronizable A₁) (h₂ : dfa_is_synchronizable A₂) : (dfa_prod_attains_lower_bound A₁ A₂ ↔ ∃ w : List α, dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w ∧ (w.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂)) ∧ (dfa_prod_attains_upper_bound A₁ A₂ ↔ ∀ w : List α, dfa_is_synchronizing A₁ w → dfa_is_synchronizing A₂ w → dfa_reset_threshold A₁ + dfa_reset_threshold A₂ ≤ (w.length : WithTop ℕ)) := by  constructor  · constructor    · intro h      obtain ⟨w₁, hw₁⟩ := h₁      obtain ⟨w₂, hw₂⟩ := h₂      have h_prod_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) :=        dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂      have h_nonempty : ((fun w : List α => (w.length : WithTop ℕ)) ''          {w | dfa_is_synchronizing (dfa_prod A₁ A₂) w}).Nonempty :=        ⟨↑(w₁ ++ w₂).length, ⟨w₁ ++ w₂, h_prod_sync, rfl⟩⟩      have h_mem := csInf_mem h_nonempty      obtain ⟨w, hw, heq⟩ := h_mem      have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w :=        (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw      refine ⟨w, hw'.1, hw'.2, ?_⟩      change dfa_reset_threshold (dfa_prod A₁ A₂) = max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) at h      change (w.length : WithTop ℕ) = dfa_reset_threshold (dfa_prod A₁ A₂) at heq      rw [heq, h]    · intro ⟨w, hw₁, hw₂, hw_le⟩      have h_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) w :=        (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩      have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w.length : WithTop ℕ) := by        dsimp [dfa_reset_threshold]        exact sInf_le ⟨w, h_sync, rfl⟩      have h_trans : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) :=        le_trans h_le hw_le      have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1      exact le_antisymm h_trans h_bound  · dsimp [dfa_prod_attains_upper_bound, dfa_reset_threshold]    have h_le := (dfa_prod_reset_threshold_bounds A₁ A₂).2    dsimp [dfa_reset_threshold] at h_le    constructor    · intro h w hw₁ hw₂      rw [← h]      apply sInf_le      exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩, rfl⟩    · intro h      apply le_antisymm h_le      rw [le_sInf_iff]      rintro - ⟨w, hw, rfl⟩      have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w :=        (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw      exact h w hw'.1 hw'.2
See it in the graphDiscuss this resultChallenge it