finite_binary_maximal_packing_conflict_triangle_free
In a finite binary line family covered by a set U, the graph joining two points when their sum lies outside U in the geometry is triangle-free.
Statement
theorem finite_binary_maximal_packing_conflict_triangle_free
(n : ℕ) (S U : Finset (Fin n → ZMod 2))
(F : Finset (Finset (Fin n → ZMod 2)))
(hF : ∀ t : Finset (Fin n → ZMod 2),
t ∈ F ↔ t ⊆ S ∧ t.card = 3 ∧ t.sum id = 0)
(hcover : ∀ t ∈ F, ¬ Disjoint U t)
(x y z : Fin n → ZMod 2) (hxy : x ≠ y) (hyz : y ≠ z) (hzx : z ≠ x)
(hxyS : x + y ∈ S \ U) (hyzS : y + z ∈ S \ U) (hzxS : z + x ∈ S \ U) :
False- Source
- Elementary characteristic-two exchange in the three-packing support argument.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
Suppose for contradiction that three distinct vertices x, y, and z form a triangle in the conflict graph, meaning their edge sums x + y, y + z, and z + x all lie in S \ U. Because the vertices are pairwise distinct, these three sums are pairwise distinct and form a 3-element subset T = {x + y, y + z, z + x} ⊆ S. In characteristic 2, the sum of these three vectors is (x + x) + (y + y) + (z + z) = 0, which makes T a line in F. However, every element of T belongs to S \ U and hence is disjoint from U, contradicting the assumption that U covers every line in F.
The sums x + y, y + z, and z + x are pairwise distinct, defining the 3-element set T = {x + y, y + z, z + x}.
Suppose x + y = y + z. By commutativity (add_comm), y + x = y + z, and cancelling y on the left (add_left_cancel) yields x = z, contradicting z ≠ x. By the same cancellation argument, x + y = z + x would imply y = z (contradicting y ≠ z), and y + z = z + x would imply y = x (contradicting x ≠ y). Thus, all three vectors are distinct, and we define the finite set T = {x + y, y + z, z + x}.
uses
add_comm,add_left_cancelclassical have hab : x + y ≠ y + z := by intro h have h' : y + x = y + z := by simpa [add_comm] using h exact hzx (add_left_cancel h').symm have hac : x + y ≠ z + x := by intro h have h' : x + y = x + z := by simpa [add_comm] using h exact hyz (add_left_cancel h') have hbc : y + z ≠ z + x := by intro h have h' : z + y = z + x := by simpa [add_comm] using h exact hxy (add_left_cancel h').symm let T : Finset (Fin n → ZMod 2) := {x+y, y+z, z+x}
T ⊆ S
Every element of T is equal to x + y, y + z, or z + x (unfolded by Finset.mem_insert and Finset.mem_singleton). By hypothesis, each of these three vectors belongs to S \ U, so in particular each belongs to S by Finset.mem_sdiff.mp.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_sdiff.mphave hsub : T ⊆ S := by intro a ha simp only [T, Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact (Finset.mem_sdiff.mp hxyS).1 · exact (Finset.mem_sdiff.mp hyzS).1 · exact (Finset.mem_sdiff.mp hzxS).1
|T| = 3
Since T consists of the three elements x + y, y + z, and z + x and they are pairwise distinct, the cardinality of T is 3.
have hcard : T.card = 3 := by simp [T, hab, hac, hbc]
The sum of the elements in T is 0.
In ℤ/2ℤ, a + a = 0 holds for all elements by finite exhaustion (decide). Because vector addition in (ℤ/2ℤ)ⁿ is pointwise, every vector satisfies v + v = 0. Rearranging terms using abelian group associativity and commutativity gives (x + y) + (y + z) + (z + x) = (x + x) + (y + y) + (z + z) = 0 + 0 + 0 = 0. Since the elements of T are distinct, the finset sum of T equals this expression, so ∑_{v ∈ T} v = 0.
uses
add_assochave hadd0 : ∀ v : Fin n → ZMod 2, v + v = 0 := by intro v have hh : ∀ a : ZMod 2, a + a = 0 := by decide ext i exact hh (v i) have hsum : T.sum id = 0 := by have hval : (x+y)+(y+z)+(z+x) = 0 := by calc (x+y)+(y+z)+(z+x) = (x+x)+(y+y)+(z+z) := by abel _ = 0 := by simp [hadd0] simpa [T, hab, hac, hbc, add_assoc] using hval
T ∈ F
By the defining condition hF, a set belongs to the line family F if and only if it is a subset of S, has cardinality 3, and its elements sum to 0. Since T satisfies all three properties, T belongs to F.
have htF : T ∈ F := (hF T).2 ⟨hsub, hcard, hsum⟩U and T are disjoint.
By Finset.disjoint_left.mpr, it suffices to show that no element of U belongs to T. Any element of T must be x + y, y + z, or z + x, all of which are assumed to belong to S \ U. By Finset.mem_sdiff.mp, none of these vectors can belong to U.
uses
Finset.disjoint_left.mpr,Finset.mem_insert,Finset.mem_singleton,Finset.mem_sdiff.mphave hdis : Disjoint U T := by apply Finset.disjoint_left.mpr intro a haU haT simp only [T, Finset.mem_insert, Finset.mem_singleton] at haT rcases haT with rfl | rfl | rfl · exact (Finset.mem_sdiff.mp hxyS).2 haU · exact (Finset.mem_sdiff.mp hyzS).2 haU · exact (Finset.mem_sdiff.mp hzxS).2 haU
Falsehood (contradiction).
The covering hypothesis hcover states that every line in F intersects U, so ¬ Disjoint U T. This directly contradicts the fact that U and T are disjoint.
exact hcover T htF hdis
add_comm- Addition is commutative: a + b = b + a.
add_left_cancel- Addition allows left cancellation: a + b = a + c implies b = c.
add_assoc- Addition is associative: (a + b) + c = a + (b + c).
Finset.mem_insert- An element belongs to an inserted set insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to a singleton {a} if and only if it equals a.
Finset.mem_sdiff.mp- If an element belongs to the set difference A \ B, then it belongs to A and does not belong to B.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first set belongs to the second set.
- In the binary affine space (ℤ/2ℤ)ⁿ, lines are formalized as 3-element sets whose elements sum to zero (corresponding to triples of the form {u, v, u + v}). The identity v + v = 0 in characteristic 2 is checked coordinatewise by finite case analysis (decide) on the two elements of ℤ/2ℤ.
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 finite_binary_maximal_packing_conflict_triangle_free (n : ℕ) (S U : Finset (Fin n → ZMod 2)) (F : Finset (Finset (Fin n → ZMod 2))) (hF : ∀ t : Finset (Fin n → ZMod 2), t ∈ F ↔ t ⊆ S ∧ t.card = 3 ∧ t.sum id = 0) (hcover : ∀ t ∈ F, ¬ Disjoint U t) (x y z : Fin n → ZMod 2) (hxy : x ≠ y) (hyz : y ≠ z) (hzx : z ≠ x) (hxyS : x + y ∈ S \ U) (hyzS : y + z ∈ S \ U) (hzxS : z + x ∈ S \ U) : False := by classical have hab : x + y ≠ y + z := by intro h have h' : y + x = y + z := by simpa [add_comm] using h exact hzx (add_left_cancel h').symm have hac : x + y ≠ z + x := by intro h have h' : x + y = x + z := by simpa [add_comm] using h exact hyz (add_left_cancel h') have hbc : y + z ≠ z + x := by intro h have h' : z + y = z + x := by simpa [add_comm] using h exact hxy (add_left_cancel h').symm let T : Finset (Fin n → ZMod 2) := {x+y, y+z, z+x} have hsub : T ⊆ S := by intro a ha simp only [T, Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact (Finset.mem_sdiff.mp hxyS).1 · exact (Finset.mem_sdiff.mp hyzS).1 · exact (Finset.mem_sdiff.mp hzxS).1 have hcard : T.card = 3 := by simp [T, hab, hac, hbc] have hadd0 : ∀ v : Fin n → ZMod 2, v + v = 0 := by intro v have hh : ∀ a : ZMod 2, a + a = 0 := by decide ext i exact hh (v i) have hsum : T.sum id = 0 := by have hval : (x+y)+(y+z)+(z+x) = 0 := by calc (x+y)+(y+z)+(z+x) = (x+x)+(y+y)+(z+z) := by abel _ = 0 := by simp [hadd0] simpa [T, hab, hac, hbc, add_assoc] using hval have htF : T ∈ F := (hF T).2 ⟨hsub, hcard, hsum⟩ have hdis : Disjoint U T := by apply Finset.disjoint_left.mpr intro a haU haT simp only [T, Finset.mem_insert, Finset.mem_singleton] at haT rcases haT with rfl | rfl | rfl · exact (Finset.mem_sdiff.mp hxyS).2 haU · exact (Finset.mem_sdiff.mp hyzS).2 haU · exact (Finset.mem_sdiff.mp hzxS).2 haU exact hcover T htF hdis