binary_partial_word_partition_min_degree_restrict_essential
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
- binary_partial_word_cubeThe finite Boolean cube determined by fixing the coordinates of a finite support to the values of a Boolean word.
- binary_partial_word_restrict_supportRestrict the support of a partial word to the coordinate subtype excluding one specified coordinate.
- binary_partial_word_partition_both_bitsEvery mentioned coordinate of a finite partial-word cube partition occurs with both Boolean values.
- Used by 1
- binary_partial_word_partition_singular_coordinateA finite Boolean cube partition mentioning every coordinate and having exactly one more part than coordinates, with a nonempty coordinate…
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.
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.
classical intro w by_contra hn push Not at hn
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.
uses
mem_filter,mem_univ,true_andhave 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
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.
uses
mem_filter,Or.inl,mem_univhave 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⟩
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}.
uses
binary_partial_word_partition_both_bits,mem_filter,Or.inr,mem_univobtain ⟨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⟩
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.
uses
ssubset_iff_subset_nehave 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)
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.
uses
card_lt_cardhave 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
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.
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