AFTD Auto-Formalizing Theoretical Domains

finite_binary_line_free_independent_support_criterion

theoremverified

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.

  1. 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.

    lines 7–28

    uses Finset.mem_insert, Finset.mem_singleton, Finset.card_sdiff_of_subset, Finset.card_eq_one.mp, Finset.mem_sdiff.mp

      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])
  2. 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.

    lines 29–49

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_sdiff.mpr

      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
  3. 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.

    lines 50–65

    uses Finset.sum_insert, Finset.sum_singleton, id_eq, add_assoc, neg_eq_of_add_eq_zero_right, CharTwo.neg_eq

      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⟩
  4. |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.

    lines 78–80

    uses Finset.card_sdiff_of_subset

      constructor
      · rw [Finset.card_sdiff_of_subset hIU, hcardU]
        omega
  5. 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.

    lines 81–85

      · 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
  6. 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.

    lines 86–95

    uses Finset.mem_inter.mp, Finset.mem_sdiff.mpr, Finset.mem_inter.mpr, Finset.disjoint_iff_inter_eq_empty.mp

        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
  7. 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.

    lines 96–104

    uses Finset.not_disjoint_iff.mp, Finset.mem_inter.mpr, Finset.card_pos.mpr, Finset.card_le_card, Finset.inter_subset_left

        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
  8. 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.

    lines 105–111

    uses Finset.mem_inter.mpr, Finset.disjoint_iff_inter_eq_empty.mp

        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
  9. 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.

    lines 112–130

    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
  10. 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.

    lines 131–139

    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

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
See it in the graphDiscuss this resultChallenge it