AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_min_degree_restrict_essential

theoremverified

Fixing a coordinate with minimum occurrence count in a finite cube partition that mentions every coordinate leaves every other coordinate mentioned.

Statement

theorem binary_partial_word_partition_min_degree_restrict_essential
    {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V]
    (s : I → Finset V) (b : I → V → Bool)
    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)
    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)
    (hessential : ∀ v, ∃ i, v ∈ s i) (v : V)
    (hmin : ∀ w, (univ.filter (fun i => v ∈ s i)).card ≤
      (univ.filter (fun i => w ∈ s i)).card) (bit : Bool) :
    ∀ w : {w : V // w ≠ v},
      ∃ i : {i : I // v ∉ s i ∨ b i v = bit},
        w ∈ binary_partial_word_restrict_support (s i.val) v
Source
Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

We argue by contradiction: suppose some coordinate w ≠ v is not mentioned by any cube in the restricted partition. This implies that every cube mentioning w must also mention v and assign it the opposite bit value, so {i | w ∈ s i} ⊆ {i | v ∈ s i}. Furthermore, because v is essential in the partition, there exists a cube that fixes v to the specified bit value; this cube mentions v but cannot mention w, making the inclusion strict. Thus strictly fewer cubes mention w than v, contradicting the minimality of v's occurrence count.

  1. Assume for contradiction that some coordinate w ≠ v is not mentioned in any cube of the restricted partition.

    We introduce an arbitrary coordinate w with w ≠ v and assume the negation of the goal. Pushing the negation inward yields the hypothesis that for every retained cube index i (where v ∉ s i or b i v = bit), the coordinate w does not belong to the restricted support of s i.

    lines 16–19

      classical
      intro w
      by_contra hn
      push Not at hn
  2. Any cube mentioning w cannot satisfy the retention condition: it must mention v and set v to the opposite bit.

    Suppose w ∈ s i. If i satisfied the retention condition (v ∉ s i ∨ b i v = bit), it would be an allowed index in the restricted partition. Then w ∈ restrict_support (s i) v simplifies to w ∈ s i, contradicting our assumption that no retained cube mentions w.

    lines 20–24

    uses mem_filter, mem_univ, true_and

      have hnot (i : I) (hwi : w.val ∈ s i) : ¬(v ∉ s i ∨ b i v = bit) := by
        intro hs
        apply hn ⟨i, hs⟩
        simp only [binary_partial_word_restrict_support, mem_filter, mem_univ, true_and]
        exact hwi
  3. Every cube mentioning w also mentions v, so {i | w ∈ s i} ⊆ {i | v ∈ s i}.

    For any index i with w ∈ s i, if v ∉ s i, then the retention condition would hold via its left disjunct (Or.inl), contradicting the previous step. Hence v ∈ s i, giving the subset inclusion.

    lines 25–32

    uses mem_filter, Or.inl, mem_univ

      have hsub : univ.filter (fun i => w.val ∈ s i) ⊆
          univ.filter (fun i => v ∈ s i) := by
        intro i hi
        have hwi := (mem_filter.mp hi).2
        have hvi : v ∈ s i := by
          by_contra hv
          exact hnot i hwi (Or.inl hv)
        exact mem_filter.mpr ⟨mem_univ _, hvi⟩
  4. There exists a cube j that mentions v with value bit, and j does not mention w.

    Because v is essential, binary_partial_word_partition_both_bits provides a cube j such that v ∈ s j and b j v = bit. If w were in s j, then j would satisfy the retention condition via its right disjunct (Or.inr), which was ruled out. Thus j belongs to {i | v ∈ s i} but not to {i | w ∈ s i}.

    lines 33–38

    uses binary_partial_word_partition_both_bits, mem_filter, Or.inr, mem_univ

      obtain ⟨j, hjv, hjb⟩ := binary_partial_word_partition_both_bits s b hconflict hcover v
        (hessential v) bit
      have hjnot : j ∉ univ.filter (fun i => w.val ∈ s i) := by
        intro hj
        exact hnot j (mem_filter.mp hj).2 (Or.inr hjb)
      have hjmem : j ∈ univ.filter (fun i => v ∈ s i) := mem_filter.mpr ⟨mem_univ _, hjv⟩
  5. The set of cubes mentioning w is a strict subset of the set of cubes mentioning v.

    We have {i | w ∈ s i} ⊆ {i | v ∈ s i}, and the two sets cannot be equal because the index j belongs to the latter but not the former. By ssubset_iff_subset_ne, this gives strict subset inclusion.

    lines 39–43

    uses ssubset_iff_subset_ne

      have hss : univ.filter (fun i => w.val ∈ s i) ⊂
          univ.filter (fun i => v ∈ s i) := by
        refine (ssubset_iff_subset_ne).mpr ⟨hsub, ?_⟩
        intro he
        exact hjnot (he.symm ▸ hjmem)
  6. The strict inclusion contradicts the minimality of v's occurrence count.

    By card_lt_card, the strict inclusion implies |{i | w ∈ s i}| < |{i | v ∈ s i}|. However, v was assumed to have minimal degree among all coordinates, so |{i | v ∈ s i}| ≤ |{i | w ∈ s i}|. Linear arithmetic (omega) derives a contradiction from these two inequalities.

    lines 44–46

    uses card_lt_card

      have hlt := card_lt_card hss
      have hle := hmin w.val
      omega
mem_filter
An element x is in s.filter p if and only if x ∈ s and p x holds.
mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The proposition (True ∧ p) is equivalent to p.
Or.inl
Constructs a proof of a ∨ b from a proof of the left disjunct a.
Or.inr
Constructs a proof of a ∨ b from a proof of the right disjunct b.
binary_partial_word_partition_both_bits
In a cube partition of the Boolean hypercube, if coordinate v is essential (mentioned in at least one cube), then for each boolean value bit there exists a cube in the partition fixing v to bit.
ssubset_iff_subset_ne
A set s is a strict subset of t if and only if s ⊆ t and s ≠ t.
card_lt_card
If a finite set s is a strict subset of t, then |s| < |t|.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem binary_partial_word_partition_min_degree_restrict_essential    {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V]    (s : I → Finset V) (b : I → V → Bool)    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)    (hessential : ∀ v, ∃ i, v ∈ s i) (v : V)    (hmin : ∀ w, (univ.filter (fun i => v ∈ s i)).card ≤      (univ.filter (fun i => w ∈ s i)).card) (bit : Bool) :    ∀ w : {w : V // w ≠ v},      ∃ i : {i : I // v ∉ s i ∨ b i v = bit},        w ∈ binary_partial_word_restrict_support (s i.val) v := by  classical  intro w  by_contra hn  push Not at hn  have hnot (i : I) (hwi : w.val ∈ s i) : ¬(v ∉ s i ∨ b i v = bit) := by    intro hs    apply hn ⟨i, hs⟩    simp only [binary_partial_word_restrict_support, mem_filter, mem_univ, true_and]    exact hwi  have hsub : univ.filter (fun i => w.val ∈ s i) ⊆      univ.filter (fun i => v ∈ s i) := by    intro i hi    have hwi := (mem_filter.mp hi).2    have hvi : v ∈ s i := by      by_contra hv      exact hnot i hwi (Or.inl hv)    exact mem_filter.mpr ⟨mem_univ _, hvi⟩  obtain ⟨j, hjv, hjb⟩ := binary_partial_word_partition_both_bits s b hconflict hcover v    (hessential v) bit  have hjnot : j ∉ univ.filter (fun i => w.val ∈ s i) := by    intro hj    exact hnot j (mem_filter.mp hj).2 (Or.inr hjb)  have hjmem : j ∈ univ.filter (fun i => v ∈ s i) := mem_filter.mpr ⟨mem_univ _, hjv⟩  have hss : univ.filter (fun i => w.val ∈ s i) ⊂      univ.filter (fun i => v ∈ s i) := by    refine (ssubset_iff_subset_ne).mpr ⟨hsub, ?_⟩    intro he    exact hjnot (he.symm ▸ hjmem)  have hlt := card_lt_card hss  have hle := hmin w.val  omega
See it in the graphDiscuss this resultChallenge it