AFTD Auto-Formalizing Theoretical Domains

exists_unit_hamming_triangle_free_card_eq

theoremverified

For every integer q ≥ 2 and every integer n ≥ 1, there exists a finite set A : Finset (Fin n → Fin q) satisfying unit_hamming_triangle_free A with A.card = 2 * q ^ (n - 1).

Statement

theorem exists_unit_hamming_triangle_free_card_eq (n q : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n) :
    ∃ A : Finset (Fin n → Fin q), unit_hamming_triangle_free A ∧ A.card = 2 * q ^ (n - 1)
Source
arXiv:2610.32789 Section 3.1
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • unit_hamming_triangle_freeA finite set A : Finset (Fin n → Fin q) is unit_hamming_triangle_free if for all x, y, z : Fin n → Fin q, if x ∈ A, y ∈ A, z ∈ A, and x ≠…
Used by 1
  • unit_hamming_max_triangle_free_eqFor every fixed integer q ≥ 2 and every integer n ≥ 1, the maximum size unit_hamming_max_triangle_free n q of a triangle-free vertex…

Read back from the Lean

For all natural numbers $n$ and $q$ satisfying $q \ge 2$ and $n \ge 1$, there exists a finite subset $A$ of $(\mathrm{Fin}\ n \to \mathrm{Fin}\ q)$ (i.e., words of length $n$ over an alphabet of size $q$) such that: 1. $A$ is unit Hamming triangle-free (contains no three distinct elements whose pairwise Hamming distances are all equal to $1$), and 2. the cardinality of $A$ is $2 \cdot q^{n - 1}$.

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

To construct a triangle-free subset of size 2 * q^(n-1) in the unit Hamming graph on (Fin q)^n, we write n = m + 1 and select all words whose coordinate sum modulo q lies in {0, 1}. Because changing any single coordinate strictly alters the checksum, words at Hamming distance 1 must have different checksums, which precludes triangles since no three pairwise distinct values can lie in {0, 1}. Finally, fixing the last m coordinates leaves exactly two valid choices for the first coordinate, proving by fiberwise summation that the set has size 2 * q^m.

  1. Two words at Hamming distance 1 differ at a unique coordinate and agree everywhere else.

    The Hamming distance between x and y is the size of the set of indices where they differ. When this distance is 1, the set of differing indices is a singleton {i} by Finset.card_eq_one.mp. Thus x i ≠ y i, and for all j ≠ i, x j = y j.

    lines 7–17

    uses Finset.card_eq_one.mp

      have hc : ({i | x i ≠ y i} : Finset ι).card = 1 := h
      obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hc
      have hmem : ∀ j, j ∈ ({i | x i ≠ y i} : Finset ι) ↔ j = i := by
        intro j
        rw [hi]; simp
      refine ⟨i, ?_, ?_⟩
      · intro j hj
        by_contra hne
        exact hj ((hmem j).mp (by simpa using hne))
      · have := (hmem i).mpr rfl
        simpa using this
  2. Set n = m + 1 and define the code A ⊆ (Fin q)^(m+1) of words whose checksum modulo q lies in {0, 1}.

    Because n ≥ 1, we can write n = m + 1. Since q ≥ 2, q is non-zero and 0 ≠ 1 in ℤ/qℤ (by ZMod.one_eq_zero_iff.mp), so S = {0, 1} has cardinality 2. Identifying Fin q with ℤ/qℤ via ZMod.finEquiv, we define the checksum σ(x) = ∑ x_i and the set A as all words x with σ(x) ∈ S.

    lines 22–36

    uses Nat.add_sub_cancel, ZMod.finEquiv, ZMod.one_eq_zero_iff.mp

      obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩
      simp only [Nat.add_sub_cancel]
      haveI : NeZero q := ⟨by omega⟩
      -- the abelian group ZMod q, and the code {0,1} ⊆ ZMod q
      let e : Fin q ≃ ZMod q := (ZMod.finEquiv q).toEquiv
      let S : Finset (ZMod q) := {0, 1}
      have h01 : (0 : ZMod q) ≠ 1 := by
        intro h
        have : q = 1 := ZMod.one_eq_zero_iff.mp h.symm
        omega
      have hS : S.card = 2 := by simp [S, h01]
      -- the checksum of a word
      let sigma : (Fin (m+1) → Fin q) → ZMod q := fun x => ∑ i, e (x i)
      -- the code: all words whose checksum is in {0,1}
      let A : Finset (Fin (m+1) → Fin q) := Finset.univ.filter (fun x => sigma x ∈ S)
  3. Replacing coordinate i of word x with value t updates the checksum by subtracting e(x i) and adding e(t).

    Splitting the sum over all coordinates into the i-th term and the remaining terms using Fin.sum_univ_succAbove, the update changes only index i (by Function.update_self and Fin.succAbove_ne). Recombining terms in ℤ/qℤ gives σ(x[i ↦ t]) = σ(x) - e(x i) + e(t).

    lines 37–43

    uses Fin.sum_univ_succAbove, Function.update_self, Fin.succAbove_ne

      have sigma_update (x : Fin (m+1) → Fin q) (i : Fin (m+1)) (t : Fin q) :
          sigma (Function.update x i t) = sigma x - e (x i) + e t := by
        simp only [sigma]
        rw [Fin.sum_univ_succAbove (fun j => e (Function.update x i t j)) i]
        rw [Fin.sum_univ_succAbove (fun j => e (x j)) i]
        simp [Function.update_self, Fin.succAbove_ne]
        abel
  4. For any word x and coordinate i, exactly |S| = 2 replacement values keep the updated word in A.

    Let C = σ(x) - e(x i) be the sum of the remaining coordinates. Then x[i ↦ t] ∈ A if and only if e(t) + C ∈ S. The translation t ↦ e(t) + C is a bijection between the set of valid replacement values and S: it is injective by add_right_cancel and the injectivity of e, and surjective because every s ∈ S has preimage e⁻¹(s - C). By Finset.card_bij, the fiber has size |S| = 2.

    lines 45–67

    uses Finset.card_bij, add_right_cancel

      have fiber_card (x : Fin (m+1) → Fin q) (i : Fin (m+1)) :
          (Finset.univ.filter (fun t : Fin q => Function.update x i t ∈ A)).card = S.card := by
        let C : ZMod q := sigma x - e (x i)
        have hmem : ∀ t : Fin q, Function.update x i t ∈ A ↔ e t + C ∈ S := by
          intro t
          simp only [A, Finset.mem_filter, Finset.mem_univ, true_and]
          rw [sigma_update]
          constructor
          · intro h; simpa [C, add_comm, add_left_comm, add_assoc] using h
          · intro h; simpa [C, add_comm, add_left_comm, add_assoc] using h
        refine Finset.card_bij (fun t _ => e t + C) ?_ ?_ ?_
        · intro t ht
          exact (hmem t).mp (by simpa using ht)
        · intro t1 _ t2 _ h
          exact e.injective (add_right_cancel h)
        · intro s hs
          refine ⟨e.symm (s - C), ?_, ?_⟩
          · simp only [Finset.mem_filter, Finset.mem_univ, true_and]
            apply (hmem _).mpr
            rw [e.apply_symm_apply]
            have : (s - C) + C = s := by abel
            rw [this]; exact hs
          · rw [e.apply_symm_apply]; abel
  5. For every suffix y : Fin m → Fin q, exactly 2 words in A have tail y.

    Let x = cons(c₀, y) be an arbitrary extension of y. By the fiber cardinality result, exactly 2 values of t satisfy x[0 ↦ t] ∈ A. The projection mapping a word x' ∈ A with tail y to its first coordinate x'(0) is a bijection onto this set of choices (using Fin.cons_self_tail, Fin.cases, Fin.cons_succ, and Fin.tail_cons), so by Finset.card_bij each tail fiber has cardinality 2.

    lines 69–104

    uses Classical.arbitrary, Finset.card_bij, Finset.mem_filter.mp, Fin.cons_self_tail, Fin.cons_zero, Fin.cases, Fin.cons_succ, Fin.tail_cons, Function.update_self

      have tail_fiber_card (y : Fin m → Fin q) :
          (A.filter (fun x => Fin.tail x = y)).card = 2 := by
        haveI : Nonempty (Fin q) := ⟨⟨0, by omega⟩⟩
        let c0 : Fin q := Classical.arbitrary (Fin q)
        let x : Fin (m+1) → Fin q := Fin.cons c0 y
        have hright : (Finset.univ.filter (fun t : Fin q => Function.update x 0 t ∈ A)).card = 2 := by
          calc (Finset.univ.filter (fun t : Fin q => Function.update x 0 t ∈ A)).card = S.card :=
                fiber_card x 0
            _ = 2 := hS
        refine (Finset.card_bij (fun x' _ => x' 0) ?_ ?_ ?_).trans hright
        · intro x' hx'
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          have hxmem : x' ∈ A := (Finset.mem_filter.mp hx').1
          have hxtail : Fin.tail x' = y := (Finset.mem_filter.mp hx').2
          have hx'eq : x' = Fin.cons (x' 0) y := by
            rw [← hxtail]; exact (Fin.cons_self_tail x').symm
          rw [hx'eq]
          simp only [Fin.cons_zero]
          have hupd : Function.update x 0 (x' 0) = Fin.cons (x' 0) y := by
            funext j
            refine Fin.cases ?_ ?_ j
            · simp [x]
            · intro j; simp [x, Fin.cons_succ]
          rw [hupd]
          exact hx'eq ▸ hxmem
        · intro x1 hx1 x2 hx2 h
          have hx1tail : Fin.tail x1 = y := (Finset.mem_filter.mp hx1).2
          have hx2tail : Fin.tail x2 = y := (Finset.mem_filter.mp hx2).2
          calc x1 = Fin.cons (x1 0) (Fin.tail x1) := (Fin.cons_self_tail x1).symm
            _ = Fin.cons (x2 0) (Fin.tail x2) := by rw [h, hx1tail, hx2tail]
            _ = x2 := Fin.cons_self_tail x2
        · intro t ht
          refine ⟨Function.update x 0 t, ?_, ?_⟩
          · simp only [Finset.mem_filter, Finset.mem_univ, true_and]
            exact ⟨by simpa using ht, by simp [x, Fin.tail_cons]⟩
          · simp [Function.update_self]
  6. The cardinality of A is 2 * q^m, which equals 2 * q^(n - 1).

    Summing the sizes of the fibers of A over all possible tails y : Fin m → Fin q partitions A using Finset.card_eq_sum_card_fiberwise. Since each fiber has size 2, the sum reduces via Finset.sum_congr and Finset.sum_const to 2 times the total number of tails. By Fintype.card_fun and Fintype.card_fin, the number of tails is q^m, yielding |A| = 2 * q^m.

    lines 105–118

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_congr, Finset.sum_const, Finset.card_univ, Fintype.card_fun, Fintype.card_fin, smul_eq_mul

      have hA_card : A.card = 2 * q ^ m := by
        have step1 : A.card = ∑ y ∈ (Finset.univ : Finset (Fin m → Fin q)),
            (A.filter (fun x => Fin.tail x = y)).card := by
          apply Finset.card_eq_sum_card_fiberwise
          intro x hx; simp
        rw [step1]
        have step2 : ∑ y ∈ (Finset.univ : Finset (Fin m → Fin q)),
            (A.filter (fun x => Fin.tail x = y)).card = ∑ _y : Fin m → Fin q, 2 := by
          apply Finset.sum_congr rfl
          intro y _
          exact tail_fiber_card y
        rw [step2, Finset.sum_const, Finset.card_univ, Fintype.card_fun, Fintype.card_fin,
          Fintype.card_fin, smul_eq_mul]
        ring
  7. Any two distinct words in A at Hamming distance 1 have different checksums.

    If distinct words a, b ∈ A satisfy hammingDist a b = 1, pp_hd_one gives a unique index i where they differ, so b = a[i ↦ b i]. If σ(a) = σ(b), the update formula and add_left_cancel force e(a i) = e(b i), hence a i = b i by injectivity of e, contradicting a ≠ b.

    lines 119–142

    uses pp_hd_one, add_left_cancel

      refine ⟨A, ?_, hA_card⟩
      intro x y z hx hy hz hxy hyz hxz htri
      obtain ⟨h1, h2, h3⟩ := htri
      -- words at Hamming distance one inside `A` have different checksums
      have key : ∀ a b : Fin (m+1) → Fin q, a ∈ A → b ∈ A → a ≠ b →
          hammingDist a b = 1 → sigma a ≠ sigma b := by
        intro a b _ _ hab hd hsigma
        obtain ⟨i, hagree, hdiff⟩ := pp_hd_one hd
        have hai : a i = b i := by
          by_contra hne
          have hb : b = Function.update a i (b i) := by
            funext k
            by_cases hk : k = i
            · rw [hk]; simp
            · simp [hk, hagree k hk]
          rw [hb, sigma_update a i (b i)] at hsigma
          have h2' : sigma a - e (a i) + e (b i) = sigma a - e (a i) + e (a i) := by
            rw [← hsigma]; abel
          exact hne (e.injective (add_left_cancel h2').symm)
        apply hab
        funext j
        by_cases hj : j = i
        · rw [hj]; exact hai
        · exact hagree j hj
  8. The set A contains no unit Hamming triangles. automation

    Every word in A has checksum 0 or 1. If three words x, y, z in A formed a unit Hamming triangle, their pairwise Hamming distances would all be 1, forcing their checksums σ(x), σ(y), σ(z) to be pairwise distinct. By the pigeonhole principle, three elements cannot be pairwise distinct in a two-element set {0, 1}; an exhaustive case analysis closes every branch with a contradiction.

    lines 143–154

      have hS3 : ∀ v ∈ A, sigma v = 0 ∨ sigma v = 1 := by
        intro v hv
        have hmem : sigma v ∈ S := (Finset.mem_filter.mp hv).2
        simpa [S] using hmem
      have hne1 : sigma x ≠ sigma y := key x y hx hy hxy h1
      have hne2 : sigma y ≠ sigma z := key y z hy hz hyz h2
      have hne3 : sigma x ≠ sigma z := key x z hx hz hxz h3
      have hx' := hS3 x hx
      have hy' := hS3 y hy
      have hz' := hS3 z hz
      rcases hx' with hx' | hx' <;> rcases hy' with hy' | hy' <;> rcases hz' with hz' | hz' <;>
        simp_all
add_left_cancel
In an additive structure with left-cancellation, a + b = a + c implies b = c.
add_right_cancel
In an additive structure with right-cancellation, a + b = c + b implies a = c.
Classical.arbitrary
Chooses an arbitrary element from any non-empty type.
Fin.cases
Proof by cases on Fin (n + 1), distinguishing index 0 from successor indices.
Fin.cons_succ
Evaluating cons(x, p) at a successor index i.succ yields p(i).
Fin.cons_zero
The first coordinate of cons(x, p) is x.
Fin.cons_self_tail
Reconstructing a tuple from its initial element and its tail yields the original tuple.
Fin.succAbove_ne
The embedding succAbove p omits p, so its value at any index is never equal to p.
Fin.sum_univ_succAbove
A sum over Fin (n + 1) can be decomposed into the term at index x and the sum over all other indices.
Fin.tail_cons
The tail of cons(x, p) is p.
Finset.card_bij
If there is a well-defined, injective, and surjective map between two finite sets, then they have the same cardinality.
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is a singleton.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of its fibers under any map into a finite codomain.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.mem_filter.mp
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every index.
Finset.sum_const
Summing a constant value b over a finite set s equals the cardinality of s times b.
Fintype.card_fin
The cardinality of Fin n is n.
Fintype.card_fun
The number of functions between two finite types α and β is |β|^|α|.
Function.update_self
Evaluating a function updated at a with value v at the input a yields v.
Nat.add_sub_cancel
For any natural numbers n and m, (n + m) - m = n.
pp_hd_one
Two words at Hamming distance 1 differ at exactly one index and agree at all other indices.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.
ZMod.finEquiv
For any non-zero natural number n, Fin n is canonically isomorphic to the ring ℤ/nℤ.
ZMod.one_eq_zero_iff.mp
In the ring ℤ/nℤ, 1 = 0 implies n = 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

open Finset/-- A word at Hamming distance one from another differs in exactly one coordinate. -/private lemma pp_hd_one {ι β : Type} [Fintype ι] [DecidableEq ι] [DecidableEq β]    {x y : ι → β} (h : hammingDist x y = 1) :    ∃ i, (∀ j, j ≠ i → x j = y j) ∧ x i ≠ y i := by  have hc : ({i | x i ≠ y i} : Finset ι).card = 1 := h  obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hc  have hmem : ∀ j, j ∈ ({i | x i ≠ y i} : Finset ι) ↔ j = i := by    intro j    rw [hi]; simp  refine ⟨i, ?_, ?_⟩  · intro j hj    by_contra hne    exact hj ((hmem j).mp (by simpa using hne))  · have := (hmem i).mpr rfl    simpa using this/-- Lower bound construction: there exists a triangle-free subset of (Fin n → Fin q) of size 2 * q^(n-1). -/theorem exists_unit_hamming_triangle_free_card_eq (n q : ℕ) (hq : 2 ≤ q) (hn : 1 ≤ n) :    ∃ A : Finset (Fin n → Fin q), unit_hamming_triangle_free A ∧ A.card = 2 * q ^ (n - 1) := by  obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩  simp only [Nat.add_sub_cancel]  haveI : NeZero q := ⟨by omega⟩  -- the abelian group ZMod q, and the code {0,1} ⊆ ZMod q  let e : Fin q ≃ ZMod q := (ZMod.finEquiv q).toEquiv  let S : Finset (ZMod q) := {0, 1}  have h01 : (0 : ZMod q) ≠ 1 := by    intro h    have : q = 1 := ZMod.one_eq_zero_iff.mp h.symm    omega  have hS : S.card = 2 := by simp [S, h01]  -- the checksum of a word  let sigma : (Fin (m+1) → Fin q) → ZMod q := fun x => ∑ i, e (x i)  -- the code: all words whose checksum is in {0,1}  let A : Finset (Fin (m+1) → Fin q) := Finset.univ.filter (fun x => sigma x ∈ S)  have sigma_update (x : Fin (m+1) → Fin q) (i : Fin (m+1)) (t : Fin q) :      sigma (Function.update x i t) = sigma x - e (x i) + e t := by    simp only [sigma]    rw [Fin.sum_univ_succAbove (fun j => e (Function.update x i t j)) i]    rw [Fin.sum_univ_succAbove (fun j => e (x j)) i]    simp [Function.update_self, Fin.succAbove_ne]    abel  -- changing one coordinate always allows exactly two values inside `A`  have fiber_card (x : Fin (m+1) → Fin q) (i : Fin (m+1)) :      (Finset.univ.filter (fun t : Fin q => Function.update x i t ∈ A)).card = S.card := by    let C : ZMod q := sigma x - e (x i)    have hmem : ∀ t : Fin q, Function.update x i t ∈ A ↔ e t + C ∈ S := by      intro t      simp only [A, Finset.mem_filter, Finset.mem_univ, true_and]      rw [sigma_update]      constructor      · intro h; simpa [C, add_comm, add_left_comm, add_assoc] using h      · intro h; simpa [C, add_comm, add_left_comm, add_assoc] using h    refine Finset.card_bij (fun t _ => e t + C) ?_ ?_ ?_    · intro t ht      exact (hmem t).mp (by simpa using ht)    · intro t1 _ t2 _ h      exact e.injective (add_right_cancel h)    · intro s hs      refine ⟨e.symm (s - C), ?_, ?_⟩      · simp only [Finset.mem_filter, Finset.mem_univ, true_and]        apply (hmem _).mpr        rw [e.apply_symm_apply]        have : (s - C) + C = s := by abel        rw [this]; exact hs      · rw [e.apply_symm_apply]; abel  -- every fiber over the tail map has exactly two elements  have tail_fiber_card (y : Fin m → Fin q) :      (A.filter (fun x => Fin.tail x = y)).card = 2 := by    haveI : Nonempty (Fin q) := ⟨⟨0, by omega⟩⟩    let c0 : Fin q := Classical.arbitrary (Fin q)    let x : Fin (m+1) → Fin q := Fin.cons c0 y    have hright : (Finset.univ.filter (fun t : Fin q => Function.update x 0 t ∈ A)).card = 2 := by      calc (Finset.univ.filter (fun t : Fin q => Function.update x 0 t ∈ A)).card = S.card :=            fiber_card x 0        _ = 2 := hS    refine (Finset.card_bij (fun x' _ => x' 0) ?_ ?_ ?_).trans hright    · intro x' hx'      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      have hxmem : x' ∈ A := (Finset.mem_filter.mp hx').1      have hxtail : Fin.tail x' = y := (Finset.mem_filter.mp hx').2      have hx'eq : x' = Fin.cons (x' 0) y := by        rw [← hxtail]; exact (Fin.cons_self_tail x').symm      rw [hx'eq]      simp only [Fin.cons_zero]      have hupd : Function.update x 0 (x' 0) = Fin.cons (x' 0) y := by        funext j        refine Fin.cases ?_ ?_ j        · simp [x]        · intro j; simp [x, Fin.cons_succ]      rw [hupd]      exact hx'eq ▸ hxmem    · intro x1 hx1 x2 hx2 h      have hx1tail : Fin.tail x1 = y := (Finset.mem_filter.mp hx1).2      have hx2tail : Fin.tail x2 = y := (Finset.mem_filter.mp hx2).2      calc x1 = Fin.cons (x1 0) (Fin.tail x1) := (Fin.cons_self_tail x1).symm        _ = Fin.cons (x2 0) (Fin.tail x2) := by rw [h, hx1tail, hx2tail]        _ = x2 := Fin.cons_self_tail x2    · intro t ht      refine ⟨Function.update x 0 t, ?_, ?_⟩      · simp only [Finset.mem_filter, Finset.mem_univ, true_and]        exact ⟨by simpa using ht, by simp [x, Fin.tail_cons]⟩      · simp [Function.update_self]  have hA_card : A.card = 2 * q ^ m := by    have step1 : A.card = ∑ y ∈ (Finset.univ : Finset (Fin m → Fin q)),        (A.filter (fun x => Fin.tail x = y)).card := by      apply Finset.card_eq_sum_card_fiberwise      intro x hx; simp    rw [step1]    have step2 : ∑ y ∈ (Finset.univ : Finset (Fin m → Fin q)),        (A.filter (fun x => Fin.tail x = y)).card = ∑ _y : Fin m → Fin q, 2 := by      apply Finset.sum_congr rfl      intro y _      exact tail_fiber_card y    rw [step2, Finset.sum_const, Finset.card_univ, Fintype.card_fun, Fintype.card_fin,      Fintype.card_fin, smul_eq_mul]    ring  refine ⟨A, ?_, hA_card⟩  intro x y z hx hy hz hxy hyz hxz htri  obtain ⟨h1, h2, h3⟩ := htri  -- words at Hamming distance one inside `A` have different checksums  have key : ∀ a b : Fin (m+1) → Fin q, a ∈ A → b ∈ A → a ≠ b →      hammingDist a b = 1 → sigma a ≠ sigma b := by    intro a b _ _ hab hd hsigma    obtain ⟨i, hagree, hdiff⟩ := pp_hd_one hd    have hai : a i = b i := by      by_contra hne      have hb : b = Function.update a i (b i) := by        funext k        by_cases hk : k = i        · rw [hk]; simp        · simp [hk, hagree k hk]      rw [hb, sigma_update a i (b i)] at hsigma      have h2' : sigma a - e (a i) + e (b i) = sigma a - e (a i) + e (a i) := by        rw [← hsigma]; abel      exact hne (e.injective (add_left_cancel h2').symm)    apply hab    funext j    by_cases hj : j = i    · rw [hj]; exact hai    · exact hagree j hj  have hS3 : ∀ v ∈ A, sigma v = 0 ∨ sigma v = 1 := by    intro v hv    have hmem : sigma v ∈ S := (Finset.mem_filter.mp hv).2    simpa [S] using hmem  have hne1 : sigma x ≠ sigma y := key x y hx hy hxy h1  have hne2 : sigma y ≠ sigma z := key y z hy hz hyz h2  have hne3 : sigma x ≠ sigma z := key x z hx hz hxz h3  have hx' := hS3 x hx  have hy' := hS3 y hy  have hz' := hS3 z hz  rcases hx' with hx' | hx' <;> rcases hy' with hy' | hy' <;> rcases hz' with hz' | hz' <;>    simp_all
See it in the graphDiscuss this resultChallenge it