binary_partial_word_partition_twins
If a coordinate appears in exactly two parts of a Boolean cube partition, once at each value, those parts have equal supports and agree at every other supported coordinate.
Statement
theorem binary_partial_word_partition_twins {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) (v : V) (hsing : ∀ bit : Bool, (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = 1) : ∃ i₀ i₁ : I, i₀ ≠ i₁ ∧ v ∈ s i₀ ∧ b i₀ v = false ∧ v ∈ s i₁ ∧ b i₁ v = true ∧ (∀ i, v ∈ s i → i = i₀ ∨ i = i₁) ∧ s i₀ = s i₁ ∧ (∀ w ∈ s i₀, w ≠ v → b i₀ w = b i₁ w)
- 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_cube_memMembership in a partial-word cube is exactly agreement on every supported coordinate.
- binary_partial_word_cube_cover_iffA family of partial-word cubes covers the whole Boolean cube exactly when every Boolean assignment agrees with one of the partial words on…
- Used by 1
- binary_partial_word_partition_order_convexIn a finite Boolean cube partition with one more part than mentioned coordinates, linearly order the parts so that every false occurrence…
The proof, explained
To show that two parts restricting coordinate v are twins, the proof first isolates their indices i₀ and i₁ and confirms that no other part restricts v. The pivotal move is a flipping lemma: flipping coordinate v in any word of cube i₀ must land in cube i₁ because the partition covers the full cube and pairwise conflict prevents any other part from containing the flipped word. This flipping property implies that neither cube can have a supported coordinate missing from the other, proving equal supports. Finally, flipping v on the pattern of i₀ itself forces the two parts to agree on all other supported coordinates.
There exist unique indices i₀ and i₁ whose parts restrict coordinate v to false and true, respectively.
By the assumption that exactly one part restricts v to each bit, we extract the unique witness i₀ for false and the unique witness i₁ for true from the singleton filters.
uses
card_eq_one,mem_filterclassical obtain ⟨i₀, hi₀⟩ := card_eq_one.mp (hsing false) obtain ⟨i₁, hi₁⟩ := card_eq_one.mp (hsing true) have hzero : v ∈ s i₀ ∧ b i₀ v = false := by have : i₀ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = false) := by rw [hi₀]; simp exact (mem_filter.mp this).2 have hone : v ∈ s i₁ ∧ b i₁ v = true := by have : i₁ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = true) := by rw [hi₁]; simp exact (mem_filter.mp this).2
The indices i₀ and i₁ are distinct.
If i₀ = i₁, the pattern value at coordinate v would have to be false and true simultaneously, which is impossible.
have hne : i₀ ≠ i₁ := by intro he have : b i₀ v = true := he ▸ hone.2 rw [hzero.2] at this contradiction
Any part restricting coordinate v must be either i₀ or i₁.
For any part i restricting v, its bit at v is either false or true. In either case, i belongs to the corresponding singleton filter, forcing i = i₀ or i = i₁.
uses
mem_filter,mem_univ,mem_singletonhave huniq (i : I) (hvi : v ∈ s i) : i = i₀ ∨ i = i₁ := by cases hbit : b i v · left have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = false) := mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩ simpa only [hi₀, mem_singleton] using this · right have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = true) := mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩ simpa only [hi₁, mem_singleton] using this
Flipping coordinate v in any word belonging to cube a ∈ {i₀, i₁} yields a word in the opposite cube d.
Because the subcubes cover the entire Boolean cube, the flipped word g must belong to some cube j. It cannot be cube a because its bit at v has been inverted. Furthermore, j must restrict coordinate v: if it did not, pairwise disjointness would force a conflict with a at some coordinate w ≠ v, but g agrees with cube a outside v, a contradiction. Since j restricts v and j ≠ a, uniqueness implies j = d.
uses
binary_partial_word_cube_cover_iff,binary_partial_word_cube_mem,Function.update_self,mem_inter,Function.update_of_nehave hflip (a d : I) (had : a ≠ d) (hva : v ∈ s a) (hvd : v ∈ s d) (hopp : b d v = !(b a v)) (honly : ∀ j, v ∈ s j → j = a ∨ j = d) : ∀ f, f ∈ binary_partial_word_cube (s a) (b a) → Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d) := by intro f hf let g := Function.update f v (!f v) obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover g have hfv : f v = b a v := (binary_partial_word_cube_mem _ _ _).mp hf v hva have hja : j ≠ a := by intro he subst j have heq := hj v hva have hnot : (!f v) ≠ f v := by cases f v <;> decide exact hnot (by simpa only [g, Function.update_self, ← hfv] using heq) have hvj : v ∈ s j := by by_contra hn obtain ⟨w, hw, hbits⟩ := hconflict a j hja.symm have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2 have he := hj w (mem_inter.mp hw).2 have hfa := (binary_partial_word_cube_mem _ _ _).mp hf w (mem_inter.mp hw).1 exact hbits (hfa.symm.trans (by simpa only [g, Function.update_of_ne hwv] using he)) have hjd : j = d := (honly j hvj).resolve_left hja subst j exact (binary_partial_word_cube_mem _ _ _).mpr hj
Flipping coordinate v maps cube i₀ into cube i₁ and vice versa.
We specialize the flipping lemma to the pairs (i₀, i₁) and (i₁, i₀), establishing the flipping property in both directions.
have hf₀ := hflip i₀ i₁ hne hzero.1 hone.1 (by simp [hzero.2, hone.2]) huniq have hf₁ := hflip i₁ i₀ hne.symm hone.1 hzero.1 (by simp [hzero.2, hone.2]) (fun j hj => (huniq j hj).symm)
If flipping coordinate v maps cube a into cube d, then the support of d is contained in that of a (s d ⊆ s a).
Suppose some coordinate w ∈ s d were not in s a. Since v ∈ s a, w ≠ v. We can construct a word in cube a whose value at w disagrees with cube d. Flipping v produces a word in cube d, which must match cube d at w, contradicting our construction because w ≠ v was untouched by the flip.
uses
binary_partial_word_cube_mem,Function.update_of_ne,Function.update_selfhave hsub (a d : I) (hflipad : ∀ f, f ∈ binary_partial_word_cube (s a) (b a) → Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d)) (hva : v ∈ s a) : s d ⊆ s a := by intro w hwd by_contra hwa have hwv : w ≠ v := by rintro rfl; exact hwa hva let f := Function.update (b a) w (!(b d w)) have hf : f ∈ binary_partial_word_cube (s a) (b a) := by rw [binary_partial_word_cube_mem] intro u hu have huw : u ≠ w := by rintro rfl; exact hwa hu simp only [f, Function.update_of_ne huw] have hgd := hflipad f hf have he := (binary_partial_word_cube_mem _ _ _).mp hgd w hwd have hnot : (!(b d w)) ≠ b d w := by cases b d w <;> decide exact hnot (by simpa only [Function.update_of_ne hwv, f, Function.update_self] using he)
The supports of i₀ and i₁ are equal (s i₀ = s i₁).
Mutual inclusion s i₁ ⊆ s i₀ and s i₀ ⊆ s i₁ follows from the support inclusion lemma applied to both directions, so s i₀ = s i₁ by antisymmetry.
have hsupport : s i₀ = s i₁ := (hsub i₁ i₀ hf₁ hone.1).antisymm (hsub i₀ i₁ hf₀ hzero.1)The witnesses i₀ and i₁ satisfy all required properties, and their patterns agree on all supported coordinates other than v.
Providing the witnesses and previously proved properties leaves only checking agreement at other coordinates w ≠ v in s i₀. The pattern b i₀ itself belongs to cube i₀. Flipping coordinate v yields a word in cube i₁, which must match b i₁ at w. Since w ≠ v, the flip leaves coordinate w unchanged, forcing b i₀ w = b i₁ w.
uses
binary_partial_word_cube_mem,Function.update_of_nerefine ⟨i₀, i₁, hne, hzero.1, hzero.2, hone.1, hone.2, huniq, hsupport, ?_⟩ intro w hw hwv have hbmem : b i₀ ∈ binary_partial_word_cube (s i₀) (b i₀) := (binary_partial_word_cube_mem _ _ _).mpr (fun u hu => rfl) have hgd := hf₀ (b i₀) hbmem have he := (binary_partial_word_cube_mem _ _ _).mp hgd w (hsupport ▸ hw) simpa only [Function.update_of_ne hwv] using he
card_eq_one- A finite set has cardinality 1 if and only if it is a singleton set {a} for some element a.
mem_filter- An element belongs to filter p s if and only if it belongs to s and satisfies the predicate p.
mem_univ- Every element of a finite type belongs to the universal finset univ.
mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
binary_partial_word_cube_cover_iff- A family of partial word subcubes covers the entire Boolean cube if and only if every Boolean word matches some part on its support.
binary_partial_word_cube_mem- A Boolean word f belongs to the subcube defined by support s and pattern b if and only if f agrees with b on all coordinates in s.
Function.update_self- Evaluating an updated function at the modified input yields the new value.
mem_inter- An element belongs to the intersection of two sets if and only if it belongs to both sets.
Function.update_of_ne- Evaluating an updated function at an input distinct from the updated point leaves its value unchanged.
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_twins {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) (v : V) (hsing : ∀ bit : Bool, (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = 1) : ∃ i₀ i₁ : I, i₀ ≠ i₁ ∧ v ∈ s i₀ ∧ b i₀ v = false ∧ v ∈ s i₁ ∧ b i₁ v = true ∧ (∀ i, v ∈ s i → i = i₀ ∨ i = i₁) ∧ s i₀ = s i₁ ∧ (∀ w ∈ s i₀, w ≠ v → b i₀ w = b i₁ w) := by classical obtain ⟨i₀, hi₀⟩ := card_eq_one.mp (hsing false) obtain ⟨i₁, hi₁⟩ := card_eq_one.mp (hsing true) have hzero : v ∈ s i₀ ∧ b i₀ v = false := by have : i₀ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = false) := by rw [hi₀]; simp exact (mem_filter.mp this).2 have hone : v ∈ s i₁ ∧ b i₁ v = true := by have : i₁ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = true) := by rw [hi₁]; simp exact (mem_filter.mp this).2 have hne : i₀ ≠ i₁ := by intro he have : b i₀ v = true := he ▸ hone.2 rw [hzero.2] at this contradiction have huniq (i : I) (hvi : v ∈ s i) : i = i₀ ∨ i = i₁ := by cases hbit : b i v · left have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = false) := mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩ simpa only [hi₀, mem_singleton] using this · right have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = true) := mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩ simpa only [hi₁, mem_singleton] using this have hflip (a d : I) (had : a ≠ d) (hva : v ∈ s a) (hvd : v ∈ s d) (hopp : b d v = !(b a v)) (honly : ∀ j, v ∈ s j → j = a ∨ j = d) : ∀ f, f ∈ binary_partial_word_cube (s a) (b a) → Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d) := by intro f hf let g := Function.update f v (!f v) obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover g have hfv : f v = b a v := (binary_partial_word_cube_mem _ _ _).mp hf v hva have hja : j ≠ a := by intro he subst j have heq := hj v hva have hnot : (!f v) ≠ f v := by cases f v <;> decide exact hnot (by simpa only [g, Function.update_self, ← hfv] using heq) have hvj : v ∈ s j := by by_contra hn obtain ⟨w, hw, hbits⟩ := hconflict a j hja.symm have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2 have he := hj w (mem_inter.mp hw).2 have hfa := (binary_partial_word_cube_mem _ _ _).mp hf w (mem_inter.mp hw).1 exact hbits (hfa.symm.trans (by simpa only [g, Function.update_of_ne hwv] using he)) have hjd : j = d := (honly j hvj).resolve_left hja subst j exact (binary_partial_word_cube_mem _ _ _).mpr hj have hf₀ := hflip i₀ i₁ hne hzero.1 hone.1 (by simp [hzero.2, hone.2]) huniq have hf₁ := hflip i₁ i₀ hne.symm hone.1 hzero.1 (by simp [hzero.2, hone.2]) (fun j hj => (huniq j hj).symm) have hsub (a d : I) (hflipad : ∀ f, f ∈ binary_partial_word_cube (s a) (b a) → Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d)) (hva : v ∈ s a) : s d ⊆ s a := by intro w hwd by_contra hwa have hwv : w ≠ v := by rintro rfl; exact hwa hva let f := Function.update (b a) w (!(b d w)) have hf : f ∈ binary_partial_word_cube (s a) (b a) := by rw [binary_partial_word_cube_mem] intro u hu have huw : u ≠ w := by rintro rfl; exact hwa hu simp only [f, Function.update_of_ne huw] have hgd := hflipad f hf have he := (binary_partial_word_cube_mem _ _ _).mp hgd w hwd have hnot : (!(b d w)) ≠ b d w := by cases b d w <;> decide exact hnot (by simpa only [Function.update_of_ne hwv, f, Function.update_self] using he) have hsupport : s i₀ = s i₁ := (hsub i₁ i₀ hf₁ hone.1).antisymm (hsub i₀ i₁ hf₀ hzero.1) refine ⟨i₀, i₁, hne, hzero.1, hzero.2, hone.1, hone.2, huniq, hsupport, ?_⟩ intro w hw hwv have hbmem : b i₀ ∈ binary_partial_word_cube (s i₀) (b i₀) := (binary_partial_word_cube_mem _ _ _).mpr (fun u hu => rfl) have hgd := hf₀ (b i₀) hbmem have he := (binary_partial_word_cube_mem _ _ _).mp hgd w (hsupport ▸ hw) simpa only [Function.update_of_ne hwv] using he