AFTD Auto-Formalizing Theoretical Domains

op_517_zero_excess_iff_exists_walk

theoremverifiedformalization

Two rank-3 signotopes on Fin m have braid-move excess 0 if and only if there exists a walk in the higher Bruhat order B(m, 2) between them whose length equals their Hamming distance.

Statement

theorem op_517_zero_excess_iff_exists_walk (m : ℕ) (u v : OrderedTriple (Fin m) → ℤˣ)
    (hu : is_rank_three_signotope u) (hv : is_rank_three_signotope v) :
    (bruhat_order_three_graph (Fin m)).dist ⟨u, hu⟩ ⟨v, hv⟩ = {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard ↔
      ∃ p : (bruhat_order_three_graph (Fin m)).Walk ⟨u, hu⟩ ⟨v, hv⟩,
        p.length = {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard
Formalizes
arXiv:2610.03808 Lemma 2.8
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • bruhat_order_three_graphThe higher Bruhat order B(α, 2) is the simple graph whose vertices are rank-3 signotopes u : OrderedTriple α → ℤˣ (subtypes of functions…
  • OrderedTripleAn ordered triple in a preordered type is a triple of elements (a, b, c) with a < b and b < c.
  • is_rank_three_signotopeA function u : OrderedTriple α → ℤˣ assigning units of ℤ ({+1, -1}) to ordered triples in a linearly ordered type α is a rank-3 signotope…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

For every natural number $m$ and any two functions $u, v : \text{OrderedTriple}(\text{Fin } m) \to \mathbb{Z}^\times$ satisfying the rank-three signotope conditions $hu$ and $hv$ respectively: The graph distance between $\langle u, hu \rangle$ and $\langle v, hv \rangle$ in the rank-3 Bruhat order graph on $\text{Fin } m$ equals the number of ordered triples $t$ where $u(t) \neq v(t)$ if and only if there exists a walk in this graph from $\langle u, hu \rangle$ to $\langle v, hv \rangle$ whose length equals the number of ordered triples $t$ where $u(t) \neq v(t)$.

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

Two rank-3 signotopes have braid-move excess zero precisely when their graph distance in the higher Bruhat order B(m, 2) equals their Hamming distance D (the number of ordered triples on which they differ). In the forward direction, if the distance equals D, a shortest distance-realizing walk (or an empty walk if D = 0) witnesses the existence of a walk of length D. In the reverse direction, any walk of length D gives dist ≤ D, while an induction on walks proves that every walk must have length at least the Hamming distance between its endpoints, forcing dist = D by antisymmetry.

  1. The type of ordered triples on Fin m is finite.

    The map sending an ordered triple (a, b, c) to its coordinates in (Fin m)³ is injective (`op_517_zero_excess_iff_exists_walk_ot_inj`), since equality of the coordinate pairs implies equality of each component (`Prod.mk.injEq`) and thus equality of the triples. Because (Fin m)³ is finite, this injection proves that `OrderedTriple (Fin m)` is finite (`Finite.of_injective`).

    lines 1–11

    uses Prod.mk.injEq, Finite.of_injective, op_517_zero_excess_iff_exists_walk_ot_inj

    theorem op_517_zero_excess_iff_exists_walk_ot_inj (m : ℕ) :
        Function.Injective (fun t : OrderedTriple (Fin m) => (t.a, t.b, t.c)) := by
      intro ⟨xa, xb, xc, xab, xbc⟩ ⟨ya, yb, yc, yab, ybc⟩ h
      simp only [Prod.mk.injEq] at h
      rcases h with ⟨rfl, rfl, rfl⟩
      rfl
    
    instance op_517_zero_excess_iff_exists_walk_ot_finite (m : ℕ) : Finite (OrderedTriple (Fin m)) :=
      Finite.of_injective (fun t : OrderedTriple (Fin m) => (t.a, t.b, t.c))
        (op_517_zero_excess_iff_exists_walk_ot_inj m)
    
  2. For the empty walk, the number of differing triples between its endpoints is at most its length.

    We proceed by induction on the walk p. In the base case where p is the empty walk from u' to u', its length is 0 and the set of triples where u' differs from itself is empty, whose cardinality is 0 ≤ 0.

    lines 12–17

    theorem op_517_zero_excess_iff_exists_walk_support_le (m : ℕ)
        {u v : { w : OrderedTriple (Fin m) → ℤˣ // is_rank_three_signotope w }}
        (p : (bruhat_order_three_graph (Fin m)).Walk u v) :
        {t : OrderedTriple (Fin m) | u.val t ≠ v.val t}.ncard ≤ p.length := by
      induction' p with u' u' v' w' hadj p_rest ih
      · simp
  3. In the inductive step, the first edge of the walk flips the signotope at a unique triple i₀.

    Decomposing the walk as an initial edge from u' to v' followed by p_rest from v' to w', its length is 1 + length(p_rest) by `SimpleGraph.Walk.length_cons`. The edge hypothesis means u' and v' differ at exactly one triple i₀, so u'(t) = v'(t) for all t ≠ i₀.

    lines 18–23

    uses SimpleGraph.Walk.length_cons

      · rw [SimpleGraph.Walk.length_cons]
        obtain ⟨i₀, hi₀, huniq⟩ := hadj
        have heq : ∀ t, t ≠ i₀ → u'.val t = v'.val t := by
          intro t ht
          by_contra hne
          exact ht (huniq t hne)
  4. The triples on which u' and w' differ are contained in {i₀} ∪ {t | v'(t) ≠ w'(t)}.

    For any triple t, if t = i₀, it belongs to the inserted singleton {i₀}. If t ≠ i₀, then u'(t) = v'(t), so u'(t) ≠ w'(t) implies v'(t) ≠ w'(t).

    lines 24–32

        have hsub : {t | u'.val t ≠ w'.val t} ⊆ insert i₀ {t | v'.val t ≠ w'.val t} := by
          intro t ht
          by_cases hti : t = i₀
          · simp [hti]
          · right
            change v'.val t ≠ w'.val t
            have : u'.val t = v'.val t := heq t hti
            rw [← this]
            exact ht
  5. The number of triples where u' and w' differ is at most the length of the walk. automation

    Because the set of ordered triples is finite (`Set.toFinite`), taking cardinalities preserves subset inclusion (`Set.ncard_le_ncard`), and inserting i₀ increases cardinality by at most 1 (`Set.ncard_insert_le`). Combining these bounds with the induction hypothesis on p_rest via linear integer arithmetic (`omega`) completes the inductive step.

    lines 33–36

    uses Set.ncard_le_ncard, Set.toFinite, Set.ncard_insert_le

        have hcard := Set.ncard_le_ncard hsub (Set.toFinite _)
        have hinsert := Set.ncard_insert_le i₀ {t | v'.val t ≠ w'.val t}
        omega
    
  6. Set up the if-and-only-if statement between graph distance and Hamming distance.

    We abbreviate G as the graph and D as the Hamming distance (the cardinality of differing triples). We then split the equivalence into the forward and reverse directions, beginning with the forward implication assuming G.dist(u, v) = D.

    lines 37–46

    /-- Zero excess is equivalent to the existence of a walk of length equal to the Hamming distance. -/
    theorem op_517_zero_excess_iff_exists_walk (m : ℕ) (u v : OrderedTriple (Fin m) → ℤˣ)
        (hu : is_rank_three_signotope u) (hv : is_rank_three_signotope v) :
        (bruhat_order_three_graph (Fin m)).dist ⟨u, hu⟩ ⟨v, hv⟩ = {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard ↔
          ∃ p : (bruhat_order_three_graph (Fin m)).Walk ⟨u, hu⟩ ⟨v, hv⟩,
            p.length = {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard := by
      set G := bruhat_order_three_graph (Fin m)
      set D := {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard
      constructor
      · intro h
  7. In the forward direction, if D = 0, the trivial walk witnesses the claim.

    If D = 0, the set of differing triples has cardinality 0 and is thus empty (`Set.ncard_eq_zero`). Hence u = v, and the zero-step walk `SimpleGraph.Walk.nil` has length 0 = D.

    lines 47–57

    uses Set.ncard_eq_zero, SimpleGraph.Walk.nil

        by_cases hD : D = 0
        · have h_empty : {t : OrderedTriple (Fin m) | u t ≠ v t} = ∅ := by
            rwa [Set.ncard_eq_zero] at hD
          have huv : u = v := by
            funext t
            by_contra hc
            have ht : t ∈ {t : OrderedTriple (Fin m) | u t ≠ v t} := hc
            rw [h_empty] at ht
            exact ht
          subst huv
          refine ⟨SimpleGraph.Walk.nil, hD.symm⟩
  8. In the forward direction, if D ≠ 0, a shortest walk witnesses the claim.

    Because G.dist(u, v) = D ≠ 0, the vertices are reachable (`SimpleGraph.Reachable.of_dist_ne_zero`). Reachability guarantees the existence of a walk p whose length equals the graph distance (`SimpleGraph.Reachable.exists_walk_length_eq_dist`), which is D.

    lines 58–62

    uses SimpleGraph.Reachable.of_dist_ne_zero, SimpleGraph.Reachable.exists_walk_length_eq_dist

        · have hdist_ne : G.dist ⟨u, hu⟩ ⟨v, hv⟩ ≠ 0 := by rw [h]; exact hD
          have hr : G.Reachable ⟨u, hu⟩ ⟨v, hv⟩ := SimpleGraph.Reachable.of_dist_ne_zero hdist_ne
          obtain ⟨p, hp⟩ := SimpleGraph.Reachable.exists_walk_length_eq_dist hr
          use p
          rw [hp, h]
  9. In the reverse direction, a walk of length D implies G.dist(u, v) ≤ D.

    Assuming there is a walk p of length D, the graph distance between u and v is bounded above by the length of any walk connecting them (`SimpleGraph.dist_le`), yielding G.dist(u, v) ≤ D.

    lines 63–66

    uses SimpleGraph.dist_le

      · rintro ⟨p, hp⟩
        have hle : G.dist ⟨u, hu⟩ ⟨v, hv⟩ ≤ D := by
          rw [← hp]
          exact SimpleGraph.dist_le p
  10. The reverse inequality D ≤ G.dist(u, v) also holds, completing the equivalence.

    The existence of p ensures that u and v are reachable, so there exists a distance-realizing walk q with length(q) = G.dist(u, v) (`SimpleGraph.Reachable.exists_walk_length_eq_dist`). By our helper lemma `op_517_zero_excess_iff_exists_walk_support_le`, D is bounded by the length of q, so D ≤ G.dist(u, v). By antisymmetry (`le_antisymm`), G.dist(u, v) = D.

    lines 67–72

    uses SimpleGraph.Reachable.exists_walk_length_eq_dist, op_517_zero_excess_iff_exists_walk_support_le, le_antisymm

        have hr : G.Reachable ⟨u, hu⟩ ⟨v, hv⟩ := ⟨p⟩
        obtain ⟨q, hq⟩ := SimpleGraph.Reachable.exists_walk_length_eq_dist hr
        have hge : D ≤ G.dist ⟨u, hu⟩ ⟨v, hv⟩ := by
          rw [← hq]
          exact op_517_zero_excess_iff_exists_walk_support_le m q
        exact le_antisymm hle hge
Prod.mk.injEq
Two ordered pairs are equal if and only if their first and second components are respectively equal.
Finite.of_injective
A type is finite if there exists an injection from it into a finite type.
op_517_zero_excess_iff_exists_walk_ot_inj
The mapping sending an ordered triple to the triple of its components is injective.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increments its length by one.
Set.ncard_le_ncard
If s is a subset of a finite set t, then the cardinality of s is at most that of t.
Set.toFinite
A set whose corresponding subtype is finite is finite.
Set.ncard_insert_le
Inserting an element into a set increases its cardinality by at most one.
Set.ncard_eq_zero
A finite set has cardinality zero if and only if it is empty.
SimpleGraph.Walk.nil
The empty (zero-step) walk from a vertex to itself.
SimpleGraph.Reachable.of_dist_ne_zero
If the graph distance between two vertices is non-zero, then they are reachable from each other.
SimpleGraph.Reachable.exists_walk_length_eq_dist
If two vertices are reachable, there exists a walk between them whose length equals their graph distance.
SimpleGraph.dist_le
The graph distance between two vertices is less than or equal to the length of any walk connecting them.
op_517_zero_excess_iff_exists_walk_support_le
For any walk between two rank-3 signotopes in the higher Bruhat graph, the number of ordered triples where they differ is at most the length of the walk.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.

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

theorem op_517_zero_excess_iff_exists_walk_ot_inj (m : ℕ) :    Function.Injective (fun t : OrderedTriple (Fin m) => (t.a, t.b, t.c)) := by  intro ⟨xa, xb, xc, xab, xbc⟩ ⟨ya, yb, yc, yab, ybc⟩ h  simp only [Prod.mk.injEq] at h  rcases h with ⟨rfl, rfl, rfl⟩  rflinstance op_517_zero_excess_iff_exists_walk_ot_finite (m : ℕ) : Finite (OrderedTriple (Fin m)) :=  Finite.of_injective (fun t : OrderedTriple (Fin m) => (t.a, t.b, t.c))    (op_517_zero_excess_iff_exists_walk_ot_inj m)theorem op_517_zero_excess_iff_exists_walk_support_le (m : ℕ)    {u v : { w : OrderedTriple (Fin m) → ℤˣ // is_rank_three_signotope w }}    (p : (bruhat_order_three_graph (Fin m)).Walk u v) :    {t : OrderedTriple (Fin m) | u.val t ≠ v.val t}.ncard ≤ p.length := by  induction' p with u' u' v' w' hadj p_rest ih  · simp  · rw [SimpleGraph.Walk.length_cons]    obtain ⟨i₀, hi₀, huniq⟩ := hadj    have heq : ∀ t, t ≠ i₀ → u'.val t = v'.val t := by      intro t ht      by_contra hne      exact ht (huniq t hne)    have hsub : {t | u'.val t ≠ w'.val t} ⊆ insert i₀ {t | v'.val t ≠ w'.val t} := by      intro t ht      by_cases hti : t = i₀      · simp [hti]      · right        change v'.val t ≠ w'.val t        have : u'.val t = v'.val t := heq t hti        rw [← this]        exact ht    have hcard := Set.ncard_le_ncard hsub (Set.toFinite _)    have hinsert := Set.ncard_insert_le i₀ {t | v'.val t ≠ w'.val t}    omega/-- Zero excess is equivalent to the existence of a walk of length equal to the Hamming distance. -/theorem op_517_zero_excess_iff_exists_walk (m : ℕ) (u v : OrderedTriple (Fin m) → ℤˣ)    (hu : is_rank_three_signotope u) (hv : is_rank_three_signotope v) :    (bruhat_order_three_graph (Fin m)).dist ⟨u, hu⟩ ⟨v, hv⟩ = {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard ↔      ∃ p : (bruhat_order_three_graph (Fin m)).Walk ⟨u, hu⟩ ⟨v, hv⟩,        p.length = {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard := by  set G := bruhat_order_three_graph (Fin m)  set D := {t : OrderedTriple (Fin m) | u t ≠ v t}.ncard  constructor  · intro h    by_cases hD : D = 0    · have h_empty : {t : OrderedTriple (Fin m) | u t ≠ v t} = ∅ := by        rwa [Set.ncard_eq_zero] at hD      have huv : u = v := by        funext t        by_contra hc        have ht : t ∈ {t : OrderedTriple (Fin m) | u t ≠ v t} := hc        rw [h_empty] at ht        exact ht      subst huv      refine ⟨SimpleGraph.Walk.nil, hD.symm⟩    · have hdist_ne : G.dist ⟨u, hu⟩ ⟨v, hv⟩ ≠ 0 := by rw [h]; exact hD      have hr : G.Reachable ⟨u, hu⟩ ⟨v, hv⟩ := SimpleGraph.Reachable.of_dist_ne_zero hdist_ne      obtain ⟨p, hp⟩ := SimpleGraph.Reachable.exists_walk_length_eq_dist hr      use p      rw [hp, h]  · rintro ⟨p, hp⟩    have hle : G.dist ⟨u, hu⟩ ⟨v, hv⟩ ≤ D := by      rw [← hp]      exact SimpleGraph.dist_le p    have hr : G.Reachable ⟨u, hu⟩ ⟨v, hv⟩ := ⟨p⟩    obtain ⟨q, hq⟩ := SimpleGraph.Reachable.exists_walk_length_eq_dist hr    have hge : D ≤ G.dist ⟨u, hu⟩ ⟨v, hv⟩ := by      rw [← hq]      exact op_517_zero_excess_iff_exists_walk_support_le m q    exact le_antisymm hle hge
See it in the graphDiscuss this resultChallenge it