finite_binary_line_free_independent_support_criterion
For a finite binary line family covered by a 3k-point set U, if U contains at least k points avoiding singleton-forced points, pair-sum conflicts and full lines, then their complement in U is a cover of size at most 2k.
Statement
theorem finite_binary_line_free_independent_support_criterion
(n k : ℕ) (S U I : 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)
(hcardU : U.card = 3 * k) (hIU : I ⊆ U) (hcardI : k ≤ I.card)
(hsingle : ∀ t ∈ F, (t ∩ U).card = 1 → Disjoint I t)
(hpair : ∀ x ∈ I, ∀ y ∈ I, x ≠ y → x + y ∉ S \ U)
(hlinefree : ∀ t ∈ F, ¬ t ⊆ I) :
(U \ I).card ≤ 2 * k ∧ ∀ t ∈ F, ¬ Disjoint (U \ I) t- Source
- Conflict-graph support reduction in the triangle packing-cover campaign.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem shows that removing an independent support I of size at least k from a 3k-point cover U leaves a cover U \ I of size at most 2k. The size bound |U \ I| ≤ 2k is immediate from |U| = 3k and |I| ≥ k. To show that U \ I covers every line t, the proof proceeds by contradiction: if t is disjoint from U \ I, then t ∩ U ⊆ I. A case analysis on |t ∩ U| ∈ {1, 2, 3} then derives a contradiction in each case: size 1 violates the singleton-forced condition, size 2 violates the pair-sum condition via the third point x + y, and size 3 violates the line-free condition.
There exists a unique third point z ∈ t distinct from x and y such that t \ {x, y} = {z}.
Since x, y ∈ t and x ≠ y, the pair {x, y} is a subset of t of cardinality 2. Subtracting {x, y} from the 3-element set t leaves a set of cardinality 3 - 2 = 1 by Finset.card_sdiff_of_subset. Thus t \ {x, y} is a singleton {z} by Finset.card_eq_one.mp, so z ∈ t and z ∉ {x, y}, which means z is distinct from both x and y.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_sdiff_of_subset,Finset.card_eq_one.mp,Finset.mem_sdiff.mphave hsub : ({x, y} : Finset (Fin n → ZMod 2)) ⊆ t := by intro a ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl · exact hx · exact hy have hcardpair : ({x, y} : Finset (Fin n → ZMod 2)).card = 2 := by simp [hxy] have hcarddiff : (t \ ({x, y} : Finset (Fin n → ZMod 2))).card = 1 := by rw [Finset.card_sdiff_of_subset hsub, hcard, hcardpair] obtain ⟨z, hz⟩ := Finset.card_eq_one.mp hcarddiff have hzmem : z ∈ t \ ({x, y} : Finset (Fin n → ZMod 2)) := by rw [hz] simp have hzt : z ∈ t := (Finset.mem_sdiff.mp hzmem).1 have hznot : z ∉ ({x, y} : Finset (Fin n → ZMod 2)) := (Finset.mem_sdiff.mp hzmem).2 have hxz : x ≠ z := by intro h exact hznot (by simp [h]) have hyz : y ≠ z := by intro h exact hznot (by simp [h])
t = {x, y, z}.
By set extensionality, any element a ∈ t either belongs to {x, y} or belongs to t \ {x, y} = {z}, so a ∈ {x, y, z}. Conversely, each of x, y, z is an element of t.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_sdiff.mprhave ht_eq : t = ({x, y, z} : Finset (Fin n → ZMod 2)) := by ext a constructor · intro ha by_cases h : a ∈ ({x, y} : Finset (Fin n → ZMod 2)) · simp only [Finset.mem_insert, Finset.mem_singleton] at h ⊢ rcases h with rfl | rfl · simp · simp · have hmem : a ∈ t \ ({x, y} : Finset (Fin n → ZMod 2)) := Finset.mem_sdiff.mpr ⟨ha, h⟩ rw [hz] at hmem simp only [Finset.mem_singleton] at hmem subst a simp · intro ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact hx · exact hy · exact hzt
z = x + y, completing the lemma that any two distinct points of t determine the third point as their sum.
Rewriting t = {x, y, z} in the zero-sum condition ∑ v ∈ t, v = 0 gives x + y + z = 0. In characteristic 2, negation is the identity (CharTwo.neg_eq), so z = -(x + y) = x + y by neg_eq_of_add_eq_zero_right. Combining this with the previous steps yields the desired witness z.
uses
Finset.sum_insert,Finset.sum_singleton,id_eq,add_assoc,neg_eq_of_add_eq_zero_right,CharTwo.neg_eqhave hxnot : x ∉ ({y, z} : Finset (Fin n → ZMod 2)) := by simp [hxy, hxz] have hynot : y ∉ ({z} : Finset (Fin n → ZMod 2)) := by simp [hyz] have hsum3 : x + y + z = 0 := by rw [ht_eq] at hsum rw [Finset.sum_insert hxnot, Finset.sum_insert hynot, Finset.sum_singleton] at hsum simpa only [id_eq, add_assoc] using hsum have hz_eq : z = x + y := by have h := neg_eq_of_add_eq_zero_right hsum3 have hneg : -(x + y) = x + y := by funext i exact CharTwo.neg_eq ((x + y) i) rw [hneg] at h exact h.symm exact ⟨z, hzt, hznot, ht_eq, hz_eq⟩
|U \ I| ≤ 2 * k.
Since I ⊆ U, the size of the complement is |U \ I| = |U| - |I| = 3 * k - |I| by Finset.card_sdiff_of_subset. Because |I| ≥ k, this difference is at most 3 * k - k = 2 * k.
uses
Finset.card_sdiff_of_subsetconstructor · rw [Finset.card_sdiff_of_subset hIU, hcardU] omega
To show that U \ I covers every line t ∈ F, assume for contradiction that U \ I is disjoint from t, where t ⊆ S, |t| = 3, and ∑ x ∈ t, x = 0.
We fix a line t ∈ F and suppose, for contradiction, that U \ I and t are disjoint. By the definition of F, the line t satisfies t ⊆ S, |t| = 3, and ∑ x ∈ t, x = 0.
· intro t ht intro hdisj have htS : t ⊆ S := ((hF t).mp ht).1 have htcard : t.card = 3 := ((hF t).mp ht).2.1 have htsum : t.sum id = 0 := ((hF t).mp ht).2.2
t ∩ U ⊆ I.
If there were an element a ∈ t ∩ U not in I, then a ∈ U \ I and a ∈ t, meaning a ∈ (U \ I) ∩ t. But U \ I and t are assumed disjoint, so their intersection is empty, which is a contradiction.
uses
Finset.mem_inter.mp,Finset.mem_sdiff.mpr,Finset.mem_inter.mpr,Finset.disjoint_iff_inter_eq_empty.mphave hsubI : t ∩ U ⊆ I := by intro a ha have hat : a ∈ t := (Finset.mem_inter.mp ha).1 have hau : a ∈ U := (Finset.mem_inter.mp ha).2 by_contra haI have haUS : a ∈ U \ I := Finset.mem_sdiff.mpr ⟨hau, haI⟩ have hamem : a ∈ (U \ I) ∩ t := Finset.mem_inter.mpr ⟨haUS, hat⟩ have hdisj_eq : (U \ I) ∩ t = ∅ := Finset.disjoint_iff_inter_eq_empty.mp hdisj rw [hdisj_eq] at hamem simpa using hamem
The intersection cardinality |t ∩ U| is 1, 2, or 3.
Since U covers t, the two sets are not disjoint, so they share at least one point, meaning |t ∩ U| ≥ 1. Furthermore, t ∩ U ⊆ t implies |t ∩ U| ≤ |t| = 3. Hence |t ∩ U| must be 1, 2, or 3.
uses
Finset.not_disjoint_iff.mp,Finset.mem_inter.mpr,Finset.card_pos.mpr,Finset.card_le_card,Finset.inter_subset_leftobtain ⟨a, haU, hat⟩ := Finset.not_disjoint_iff.mp (hcover t ht) have haInter : a ∈ t ∩ U := Finset.mem_inter.mpr ⟨hat, haU⟩ have hpos : 0 < (t ∩ U).card := Finset.card_pos.mpr ⟨a, haInter⟩ have hle : (t ∩ U).card ≤ 3 := by calc (t ∩ U).card ≤ t.card := Finset.card_le_card Finset.inter_subset_left _ = 3 := htcard have hcases : (t ∩ U).card = 1 ∨ (t ∩ U).card = 2 ∨ (t ∩ U).card = 3 := by omega
The case |t ∩ U| = 1 is impossible.
The hypothesis hsingle asserts that if |t ∩ U| = 1, then I and t are disjoint. However, the unique point a ∈ t ∩ U must belong to I because t ∩ U ⊆ I, placing a ∈ I ∩ t and contradicting disjointness.
uses
Finset.mem_inter.mpr,Finset.disjoint_iff_inter_eq_empty.mprcases hcases with hcard1 | hcard2 | hcard3 · have hdisjIt : Disjoint I t := hsingle t ht hcard1 have haI : a ∈ I := hsubI haInter have hamem : a ∈ I ∩ t := Finset.mem_inter.mpr ⟨haI, hat⟩ have hdisj_eq : I ∩ t = ∅ := Finset.disjoint_iff_inter_eq_empty.mp hdisjIt rw [hdisj_eq] at hamem simpa using hamem
The case |t ∩ U| = 2 is impossible.
If |t ∩ U| = 2, let t ∩ U = {x, y} with x ≠ y. Since t ∩ U ⊆ I, both x and y belong to I. Applying the helper lemma finite_binary_line_free_independent_support_criterion_third_point to t and x, y ∈ t yields the third point z = x + y ∈ t \ {x, y}. Because z ∉ {x, y} = t ∩ U while z ∈ t, we have z ∉ U. Since z ∈ t ⊆ S, we have x + y = z ∈ S \ U, contradicting the pair-sum hypothesis hpair.
uses
Finset.card_eq_two.mp,Finset.mem_inter.mp,finite_binary_line_free_independent_support_criterion_third_point,Finset.mem_inter.mpr,Finset.mem_sdiff.mpr· obtain ⟨x, y, hxy, h_inter⟩ := Finset.card_eq_two.mp hcard2 have hxInter : x ∈ t ∩ U := by rw [h_inter]; simp have hyInter : y ∈ t ∩ U := by rw [h_inter]; simp have hxt : x ∈ t := (Finset.mem_inter.mp hxInter).1 have hyt : y ∈ t := (Finset.mem_inter.mp hyInter).1 have hxI : x ∈ I := hsubI hxInter have hyI : y ∈ I := hsubI hyInter obtain ⟨z, hzt, hznotpair, ht_eq, hz_eq⟩ := finite_binary_line_free_independent_support_criterion_third_point htcard htsum hxt hyt hxy have hznotU : z ∉ U := by intro hzU have hzInter : z ∈ t ∩ U := Finset.mem_inter.mpr ⟨hzt, hzU⟩ rw [h_inter] at hzInter exact hznotpair hzInter have hzS : z ∈ S := htS hzt have hzSdiff : z ∈ S \ U := Finset.mem_sdiff.mpr ⟨hzS, hznotU⟩ have hpair' : x + y ∉ S \ U := hpair x hxI y hyI hxy rw [hz_eq] at hzSdiff exact hpair' hzSdiff
The case |t ∩ U| = 3 is impossible, concluding the proof.
If |t ∩ U| = 3, then since t ∩ U ⊆ t and both sets have cardinality 3, we have t ∩ U = t by Finset.eq_of_subset_of_card_le. Then t = t ∩ U ⊆ I, meaning the full line t is contained in I, which contradicts the line-free hypothesis hlinefree.
uses
Finset.eq_of_subset_of_card_le,Finset.inter_subset_left· have ht_eq_inter : t ∩ U = t := by apply Finset.eq_of_subset_of_card_le Finset.inter_subset_left rw [htcard, hcard3] have htI : t ⊆ I := by intro x hx apply hsubI rw [ht_eq_inter] exact hx exact hlinefree t ht htI
add_assoc- Addition is associative: `a + b + c = a + (b + c)`.
CharTwo.neg_eq- In characteristic 2, the negation of an element equals the element itself: `-x = x`.
finite_binary_line_free_independent_support_criterion_third_point- Given a 3-element line `t` in `Fin n → ZMod 2` summing to zero, any two distinct points `x, y ∈ t` determine the third point `z ∈ t \ {x, y}` such that `t = {x, y, z}` and `z = x + y`.
Finset.card_eq_one.mp- If a finite set has cardinality 1, it is a singleton `{a}` for some element `a`.
Finset.card_eq_two.mp- If a finite set has cardinality 2, it consists of two distinct elements `{x, y}`.
Finset.card_le_card- If `s ⊆ t`, then `|s| ≤ |t|`.
Finset.card_pos.mpr- A nonempty finite set has cardinality strictly greater than 0.
Finset.card_sdiff_of_subset- If `s ⊆ t`, the cardinality of the difference `t \ s` is `|t| - |s|`.
Finset.disjoint_iff_inter_eq_empty.mp- If two sets are disjoint, their intersection is empty.
Finset.eq_of_subset_of_card_le- If `s ⊆ t` and `|t| ≤ |s|`, then `s = t`.
Finset.inter_subset_left- The intersection `s ∩ t` is a subset of `s`.
Finset.mem_insert- An element belongs to `insert b s` if and only if it is equal to `b` or belongs to `s`.
Finset.mem_inter.mp- If an element belongs to `s ∩ t`, then it belongs to both `s` and `t`.
Finset.mem_inter.mpr- If an element belongs to both `s` and `t`, then it belongs to `s ∩ t`.
Finset.mem_sdiff.mp- If an element belongs to `s \ t`, then it belongs to `s` and does not belong to `t`.
Finset.mem_sdiff.mpr- If an element belongs to `s` and does not belong to `t`, then it belongs to `s \ t`.
Finset.mem_singleton- An element belongs to the singleton set `{a}` if and only if it equals `a`.
Finset.not_disjoint_iff.mp- If two sets are not disjoint, they share at least one common element.
Finset.sum_insert- For a finite set `s` and an element `a ∉ s`, the sum of `f` over `insert a s` is `f a + ∑ x ∈ s, f x`.
Finset.sum_singleton- The sum of a function over a singleton set `{a}` is `f a`.
id_eq- The identity function satisfies `id a = a`.
neg_eq_of_add_eq_zero_right- If `a + b = 0`, then `-a = b`.
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.
private lemma finite_binary_line_free_independent_support_criterion_third_point {n : ℕ} {t : Finset (Fin n → ZMod 2)} (hcard : t.card = 3) (hsum : t.sum id = 0) {x y : Fin n → ZMod 2} (hx : x ∈ t) (hy : y ∈ t) (hxy : x ≠ y) : ∃ z, z ∈ t ∧ z ∉ ({x, y} : Finset (Fin n → ZMod 2)) ∧ t = ({x, y, z} : Finset (Fin n → ZMod 2)) ∧ z = x + y := by have hsub : ({x, y} : Finset (Fin n → ZMod 2)) ⊆ t := by intro a ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl · exact hx · exact hy have hcardpair : ({x, y} : Finset (Fin n → ZMod 2)).card = 2 := by simp [hxy] have hcarddiff : (t \ ({x, y} : Finset (Fin n → ZMod 2))).card = 1 := by rw [Finset.card_sdiff_of_subset hsub, hcard, hcardpair] obtain ⟨z, hz⟩ := Finset.card_eq_one.mp hcarddiff have hzmem : z ∈ t \ ({x, y} : Finset (Fin n → ZMod 2)) := by rw [hz] simp have hzt : z ∈ t := (Finset.mem_sdiff.mp hzmem).1 have hznot : z ∉ ({x, y} : Finset (Fin n → ZMod 2)) := (Finset.mem_sdiff.mp hzmem).2 have hxz : x ≠ z := by intro h exact hznot (by simp [h]) have hyz : y ≠ z := by intro h exact hznot (by simp [h]) have ht_eq : t = ({x, y, z} : Finset (Fin n → ZMod 2)) := by ext a constructor · intro ha by_cases h : a ∈ ({x, y} : Finset (Fin n → ZMod 2)) · simp only [Finset.mem_insert, Finset.mem_singleton] at h ⊢ rcases h with rfl | rfl · simp · simp · have hmem : a ∈ t \ ({x, y} : Finset (Fin n → ZMod 2)) := Finset.mem_sdiff.mpr ⟨ha, h⟩ rw [hz] at hmem simp only [Finset.mem_singleton] at hmem subst a simp · intro ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact hx · exact hy · exact hzt have hxnot : x ∉ ({y, z} : Finset (Fin n → ZMod 2)) := by simp [hxy, hxz] have hynot : y ∉ ({z} : Finset (Fin n → ZMod 2)) := by simp [hyz] have hsum3 : x + y + z = 0 := by rw [ht_eq] at hsum rw [Finset.sum_insert hxnot, Finset.sum_insert hynot, Finset.sum_singleton] at hsum simpa only [id_eq, add_assoc] using hsum have hz_eq : z = x + y := by have h := neg_eq_of_add_eq_zero_right hsum3 have hneg : -(x + y) = x + y := by funext i exact CharTwo.neg_eq ((x + y) i) rw [hneg] at h exact h.symm exact ⟨z, hzt, hznot, ht_eq, hz_eq⟩theorem finite_binary_line_free_independent_support_criterion (n k : ℕ) (S U I : 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) (hcardU : U.card = 3 * k) (hIU : I ⊆ U) (hcardI : k ≤ I.card) (hsingle : ∀ t ∈ F, (t ∩ U).card = 1 → Disjoint I t) (hpair : ∀ x ∈ I, ∀ y ∈ I, x ≠ y → x + y ∉ S \ U) (hlinefree : ∀ t ∈ F, ¬ t ⊆ I) : (U \ I).card ≤ 2 * k ∧ ∀ t ∈ F, ¬ Disjoint (U \ I) t := by constructor · rw [Finset.card_sdiff_of_subset hIU, hcardU] omega · intro t ht intro hdisj have htS : t ⊆ S := ((hF t).mp ht).1 have htcard : t.card = 3 := ((hF t).mp ht).2.1 have htsum : t.sum id = 0 := ((hF t).mp ht).2.2 have hsubI : t ∩ U ⊆ I := by intro a ha have hat : a ∈ t := (Finset.mem_inter.mp ha).1 have hau : a ∈ U := (Finset.mem_inter.mp ha).2 by_contra haI have haUS : a ∈ U \ I := Finset.mem_sdiff.mpr ⟨hau, haI⟩ have hamem : a ∈ (U \ I) ∩ t := Finset.mem_inter.mpr ⟨haUS, hat⟩ have hdisj_eq : (U \ I) ∩ t = ∅ := Finset.disjoint_iff_inter_eq_empty.mp hdisj rw [hdisj_eq] at hamem simpa using hamem obtain ⟨a, haU, hat⟩ := Finset.not_disjoint_iff.mp (hcover t ht) have haInter : a ∈ t ∩ U := Finset.mem_inter.mpr ⟨hat, haU⟩ have hpos : 0 < (t ∩ U).card := Finset.card_pos.mpr ⟨a, haInter⟩ have hle : (t ∩ U).card ≤ 3 := by calc (t ∩ U).card ≤ t.card := Finset.card_le_card Finset.inter_subset_left _ = 3 := htcard have hcases : (t ∩ U).card = 1 ∨ (t ∩ U).card = 2 ∨ (t ∩ U).card = 3 := by omega rcases hcases with hcard1 | hcard2 | hcard3 · have hdisjIt : Disjoint I t := hsingle t ht hcard1 have haI : a ∈ I := hsubI haInter have hamem : a ∈ I ∩ t := Finset.mem_inter.mpr ⟨haI, hat⟩ have hdisj_eq : I ∩ t = ∅ := Finset.disjoint_iff_inter_eq_empty.mp hdisjIt rw [hdisj_eq] at hamem simpa using hamem · obtain ⟨x, y, hxy, h_inter⟩ := Finset.card_eq_two.mp hcard2 have hxInter : x ∈ t ∩ U := by rw [h_inter]; simp have hyInter : y ∈ t ∩ U := by rw [h_inter]; simp have hxt : x ∈ t := (Finset.mem_inter.mp hxInter).1 have hyt : y ∈ t := (Finset.mem_inter.mp hyInter).1 have hxI : x ∈ I := hsubI hxInter have hyI : y ∈ I := hsubI hyInter obtain ⟨z, hzt, hznotpair, ht_eq, hz_eq⟩ := finite_binary_line_free_independent_support_criterion_third_point htcard htsum hxt hyt hxy have hznotU : z ∉ U := by intro hzU have hzInter : z ∈ t ∩ U := Finset.mem_inter.mpr ⟨hzt, hzU⟩ rw [h_inter] at hzInter exact hznotpair hzInter have hzS : z ∈ S := htS hzt have hzSdiff : z ∈ S \ U := Finset.mem_sdiff.mpr ⟨hzS, hznotU⟩ have hpair' : x + y ∉ S \ U := hpair x hxI y hyI hxy rw [hz_eq] at hzSdiff exact hpair' hzSdiff · have ht_eq_inter : t ∩ U = t := by apply Finset.eq_of_subset_of_card_le Finset.inter_subset_left rw [htcard, hcard3] have htI : t ⊆ I := by intro x hx apply hsubI rw [ht_eq_inter] exact hx exact hlinefree t ht htI