op_517_zero_excess_iff_exists_walk
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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.
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`).
uses
Prod.mk.injEq,Finite.of_injective,op_517_zero_excess_iff_exists_walk_ot_injtheorem 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)
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.
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
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₀.
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)
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).
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
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.
uses
Set.ncard_le_ncard,Set.toFinite,Set.ncard_insert_lehave hcard := Set.ncard_le_ncard hsub (Set.toFinite _) have hinsert := Set.ncard_insert_le i₀ {t | v'.val t ≠ w'.val t} omega
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.
/-- 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
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.
uses
Set.ncard_eq_zero,SimpleGraph.Walk.nilby_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⟩
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.
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]
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.
uses
SimpleGraph.dist_le· rintro ⟨p, hp⟩ have hle : G.dist ⟨u, hu⟩ ⟨v, hv⟩ ≤ D := by rw [← hp] exact SimpleGraph.dist_le pThe 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.
uses
SimpleGraph.Reachable.exists_walk_length_eq_dist,op_517_zero_excess_iff_exists_walk_support_le,le_antisymmhave 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.
- The induction in the helper lemma `op_517_zero_excess_iff_exists_walk_support_le` relies on the finiteness of `OrderedTriple (Fin m)` to apply cardinality bounds on sets (`Set.ncard_le_ncard`), which is established at lines 1–11 via an injective map into $(\text{Fin } m)^3$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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