Proof of Theorem 1, p. 4 — τ resets X iff δ′(τ, ·) sends one of the minimal intervals [s_{i_j}, s_{i_{j−1}}] containing X to a singleton
ProvedMonoReset.IntervalBFS.minimal_interval_reductionLet be monotonic and , listed in cyclic order. The minimal intervals containing are the intervals (indices of taken cyclically), i.e. the intervals with both endpoints in that contain . For every word ,
In particular the minimum length of a reset sequence of equals the minimum length of a path in the interval automaton from a minimal interval containing to a singleton interval, which is what the breadth-first search computes. For both sides are false.
Formalization Note States are Fin n, with the element and the cyclic order ; letters are Fin k; a word is a list read left to right. An interval is its pair of endpoints, and ∞ is none. Monotonicity is read cyclically (see the definition item).
Differences from the source:
- generalization: a minimum reset sequence is a minimum length path from some interval containing X to a singleton interval, and vice versa; only the minimal intervals [s_{i_j}, s_{i_{j−1}}] need be considered → for every word τ: IsResetSeq δ X τ ↔ ∃ I ∈ minIntervals X, ∃ s, dPrime δ τ (some I) = some (s, s); reason: the per-word equivalence implies the source's equality of minimum lengths (and its 'vice versa') by taking minima on both sides
- encoding: minimal intervals [s_{i_j}, s_{i_{j−1}}] for X = {s_{i_1}, s_{i_2}, …} → minIntervals X = pairs (x, y) ∈ X × X with X ⊆ ivSet (x, y); reason: for x ∈ X the only y ∈ X with X ⊆ [x, y] is the cyclic predecessor of x in X, so the two sets coincide; for X = {x} both are {[x, x]}
- reading: δ monotonic: δ(σ, s1), …, δ(σ, sn), after removal of adjacent duplicate states, is a subsequence of a cyclic permutation of s1, …, sn → IsMonotonic (δ a) for every letter a: n = 0, or for some start m the cyclic offsets (δ a (m + i) − δ a m) mod n are nondecreasing in i; reason: 'adjacent' is read cyclically, as 'preserves the cyclic order' requires; this reading admits more automata than the linear one (s1→s1, s2→s2, s3→s1), so the statement is the stronger one; checked equal to the cyclic de-duplication reading for every map with n ≤ 6
- encoding: states s1, …, sn in cyclic order, letters σ1, …, σk, words in Σ∗ with δ(τ1τ2, s) = δ(τ2, δ(τ1, s)) → states Fin n with s_i = i − 1 and the cyclic order of Fin n, letters Fin k, words List (Fin k) read left to right (run = left fold); reason: relabelling; same instances
- encoding: interval [s_i, s_j] and the symbol ∞ → endpoint pair (i, j) : Fin n × Fin n with state set ivSet (i, j); ∞ is none in Option (Fin n × Fin n); reason: same objects; the n representations of S stay distinct pairs, as in the source
import Mathlib import Definitions.Def_MonoReset_IntervalBFS_Model import Definitions.Def_MonoReset_IntervalBFS_Algorithm
namespace MonoReset.IntervalBFS
theorem minimal_interval_reduction {n k : ℕ} (δ : Fin k → Fin n → Fin n)
(hδ : ∀ a, IsMonotonic (δ a)) (X : Finset (Fin n)) (τ : List (Fin k)) :
IsResetSeq δ X τ ↔ ∃ I ∈ minIntervals X, ∃ s : Fin n, dPrime δ τ (some I) = some (s, s) := by sorry
end MonoReset.IntervalBFS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.