op_517_zero_excess_of_adj
If two wiring diagrams (represented as rank-3 signotopes u and v on Fin m) are adjacent in the higher Bruhat graph bruhat_order_three_graph (Fin m), then they have braid-move excess 0: their graph distance is 1, which equals the number of triples on which they differ.
Statement
theorem op_517_zero_excess_of_adj (inst : WiringDiagramPair) (h : (bruhat_order_three_graph (Fin inst.m)).Adj ⟨inst.u, inst.hu⟩ ⟨inst.v, inst.hv⟩) : wiring_diagram_zero_excess inst- Source
- arXiv:2610.03808
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- OrderedTripleAn ordered triple in a preordered type is a triple of elements (a, b, c) with a < b and b < c.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - wiring_diagram_zero_excessA pair of wiring diagrams (represented as rank-3 signotopes) has braid-move excess 0 if their distance in the higher Bruhat graph B(m, 2)…
- 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…
- WiringDiagramPairAn instance of the zero excess problem consisting of a wire count m and two rank-3 signotopes u and v on Fin m representing wiring…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - differs_at_oneTwo functions f and g of type ι → ℤˣ (taking values in the units of ℤ, {+1, -1}) differ at exactly one index if there is a unique index i…
- bruhat_order_three_graphThe higher Bruhat order B(α, 2) is the simple graph whose vertices are rank-3 signotopes u : OrderedTriple α → ℤˣ (subtypes of functions…
Read back from the Lean
For any inst : WiringDiagramPair (consisting of $m \in \mathbb{N}$ and two rank-3 signotopes $u, v : \text{OrderedTriple}(\mathrm{Fin}\ m) \to \mathbb{Z}^\times$), if $u$ and $v$ are adjacent in the graph bruhat_order_three_graph (Fin inst.m) (that is, they differ at exactly one ordered triple), then their graph distance in bruhat_order_three_graph (Fin inst.m) equals the cardinality of the set of ordered triples $t$ where $u(t) \neq v(t)$ (i.e., wiring_diagram_zero_excess inst holds).
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
By definition, two wiring diagrams (rank-3 signotopes) are adjacent in the higher Bruhat graph if and only if they differ at exactly one triple. In any simple graph, adjacent vertices have graph distance 1. Because the set of triples on which the diagrams differ is a singleton, its cardinality is also 1, so the graph distance equals the number of differing triples and the excess is 0.
The graph distance between u and v is 1, reducing zero excess to showing that the set of triples where u and v differ has cardinality 1.
Zero excess is defined as the equality between the graph distance and the cardinality of the difference set {t | u(t) ≠ v(t)}. Because u and v are adjacent by hypothesis h, their distance in the higher Bruhat graph is 1 by SimpleGraph.dist_eq_one_iff_adj.mpr.
uses
SimpleGraph.dist_eq_one_iff_adj.mprdsimp [wiring_diagram_zero_excess] rw [SimpleGraph.dist_eq_one_iff_adj.mpr h]
There exists a unique triple t at which u and v differ.
In the higher Bruhat graph, adjacency is defined as differs_at_one, meaning there is a unique triple at which the signotopes disagree. Unpacking this gives a triple t with u(t) ≠ v(t), such that any triple y with u(y) ≠ v(y) satisfies y = t.
have hdiff : differs_at_one inst.u inst.v := h obtain ⟨t, ht, hunique⟩ := hdiff
The set of triples on which u and v differ is the singleton {t}.
By set extensionality, a triple y belongs to the difference set if and only if u(y) ≠ v(y). If u(y) ≠ v(y), uniqueness implies y = t, hence y ∈ {t} by Set.mem_singleton_iff.mpr. Conversely, if y ∈ {t}, then y = t by Set.mem_singleton_iff.mp, so u(y) ≠ v(y) since u(t) ≠ v(t).
uses
Set.mem_singleton_iff.mpr,Set.mem_singleton_iff.mphave heq : {t' : OrderedTriple (Fin inst.m) | inst.u t' ≠ inst.v t'} = {t} := by ext y exact ⟨fun hy => Set.mem_singleton_iff.mpr (hunique y hy), fun hy => (Set.mem_singleton_iff.mp hy).symm ▸ ht⟩
The cardinality of the set of differing triples is 1, establishing zero excess.
Rewriting the difference set to the singleton {t}, its cardinality is 1 by Set.ncard_singleton. Both sides of the equation now equal 1, completing the proof.
uses
Set.ncard_singletonrw [heq, Set.ncard_singleton]
SimpleGraph.dist_eq_one_iff_adj.mpr- If two vertices in a simple graph are adjacent, the graph distance between them is 1.
Set.mem_singleton_iff.mpr- If x = a, then x belongs to the singleton set {a}.
Set.mem_singleton_iff.mp- If x belongs to the singleton set {a}, then x = a.
Set.ncard_singleton- The cardinality of a singleton set {a} is 1.
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.
/-- Two wiring diagrams that are adjacent in the higher Bruhat graph differ at exactly one triple, hence have excess 0. -/theorem op_517_zero_excess_of_adj (inst : WiringDiagramPair) (h : (bruhat_order_three_graph (Fin inst.m)).Adj ⟨inst.u, inst.hu⟩ ⟨inst.v, inst.hv⟩) : wiring_diagram_zero_excess inst := by dsimp [wiring_diagram_zero_excess] rw [SimpleGraph.dist_eq_one_iff_adj.mpr h] have hdiff : differs_at_one inst.u inst.v := h obtain ⟨t, ht, hunique⟩ := hdiff have heq : {t' : OrderedTriple (Fin inst.m) | inst.u t' ≠ inst.v t'} = {t} := by ext y exact ⟨fun hy => Set.mem_singleton_iff.mpr (hunique y hy), fun hy => (Set.mem_singleton_iff.mp hy).symm ▸ ht⟩ rw [heq, Set.ncard_singleton]