AFTD Auto-Formalizing Theoretical Domains

op_517_zero_excess_of_eq_pair

theoremverified

For any instance inst of WiringDiagramPair, if the two signotopes inst.u and inst.v are equal, then inst has braid-move excess 0 (wiring_diagram_zero_excess inst): the distance is 0 and the number of differing triples is 0.

Statement

theorem op_517_zero_excess_of_eq_pair (inst : WiringDiagramPair) (h : inst.u = inst.v) : wiring_diagram_zero_excess inst
Source
arXiv:2610.03808
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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…
  • 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…
  • OrderedTripleAn ordered triple in a preordered type is a triple of elements (a, b, c) with a < b and b < c.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • 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)…
  • bruhat_order_three_graphThe higher Bruhat order B(α, 2) is the simple graph whose vertices are rank-3 signotopes u : OrderedTriple α → ℤˣ (subtypes of functions…
Used by 1
  • op_517_zero_excess_of_le_twoFor any instance inst of WiringDiagramPair on m pseudolines with m ≤ 2, there are no ordered triples in Fin m, so inst.u = inst.v holds…

Read back from the Lean

For every WiringDiagramPair inst, if its two signotopes inst.u and inst.v are equal, then inst satisfies wiring_diagram_zero_excess, which asserts that the graph distance between inst.u and inst.v in the rank-3 Bruhat graph on Fin inst.m equals the number of triples on which inst.u and inst.v differ.

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 asserts that if two wiring diagrams in a pair are identical ($u = v$), their braid-move excess is 0. Unfolding the definition reduces this to showing that their distance in the rank-3 Bruhat graph equals the number of triples on which they disagree. Because the signotopes are equal, they represent the same vertex in the graph (giving distance 0), and the set of differing triples is empty (giving cardinality 0).

  1. The graph distance between the two signotopes is 0.

    Unfolding the definition of `wiring_diagram_zero_excess`, the goal is to show that the distance between the two signotopes in `bruhat_order_three_graph` equals the number of triples on which they differ. Since the two signotopes are assumed equal (`h : inst.u = inst.v`), their corresponding subtype elements in the graph are identical by `Subtype.ext`. By `SimpleGraph.dist_self`, the distance from a vertex to itself is 0, so the left-hand side reduces to 0.

    lines 3–5

    uses Subtype.ext, SimpleGraph.dist_self

      unfold wiring_diagram_zero_excess
      have h_eq : (⟨inst.u, inst.hu⟩ : { u // is_rank_three_signotope u }) = ⟨inst.v, inst.hv⟩ := Subtype.ext h
      rw [h_eq, SimpleGraph.dist_self]
  2. The set of triples on which the two signotopes differ is empty.

    By set extensionality (`ext`), a triple $t$ belongs to this set if and only if `inst.u t ≠ inst.v t`. Since `inst.u = inst.v`, this condition simplifies to `inst.v t ≠ inst.v t`, which is false, meaning no triple satisfies it.

    lines 6–8

      have h_set : {t | inst.u t ≠ inst.v t} = ∅ := by
        ext t
        simp [h]
  3. Both sides equal 0, establishing braid-move excess 0.

    Replacing the set of differing triples with the empty set, `Set.ncard_empty` evaluates its cardinality to 0. Both sides of the equation are now 0, which completes the proof.

    line 9

    uses Set.ncard_empty

      rw [h_set, Set.ncard_empty]
Subtype.ext
Two terms of a subtype are equal if their underlying values are equal.
SimpleGraph.dist_self
The distance between any vertex and itself in a simple graph is 0.
Set.ncard_empty
The cardinality of the empty set is 0.

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

/-- Any pair of identical wiring diagrams has braid-move excess 0. -/theorem op_517_zero_excess_of_eq_pair (inst : WiringDiagramPair) (h : inst.u = inst.v) : wiring_diagram_zero_excess inst := by  unfold wiring_diagram_zero_excess  have h_eq : (⟨inst.u, inst.hu⟩ : { u // is_rank_three_signotope u }) = ⟨inst.v, inst.hv⟩ := Subtype.ext h  rw [h_eq, SimpleGraph.dist_self]  have h_set : {t | inst.u t ≠ inst.v t} = ∅ := by    ext t    simp [h]  rw [h_set, Set.ncard_empty]
See it in the graphDiscuss this resultChallenge it