binary_partial_word_partition_singular_coordinate
A finite Boolean cube partition mentioning every coordinate and having exactly one more part than coordinates, with a nonempty coordinate type, has a coordinate appearing exactly once with each Boolean value.
Statement
theorem binary_partial_word_partition_singular_coordinate {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] [Nonempty 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) (hcard : Fintype.card I = Fintype.card V + 1) : ∃ v, ∀ bit : Bool, (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = 1
- 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 6
- 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_partition_dimension_boundA finite partition of a Boolean cube by pairwise conflicting partial words, mentioning every coordinate, has at least one more part than…
- binary_partial_word_restrict_supportRestrict the support of a partial word to the coordinate subtype excluding one specified coordinate.
- binary_partial_word_partition_restrictFixing one coordinate of a finite partial-word cube partition and retaining the compatible words gives a partition with the same…
- binary_partial_word_partition_both_bitsEvery mentioned coordinate of a finite partial-word cube partition occurs with both Boolean values.
- binary_partial_word_partition_min_degree_restrict_essentialFixing a coordinate with minimum occurrence count in a finite cube partition that mentions every coordinate leaves every other coordinate…
- 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
We select a coordinate v ∈ V that minimizes degree, meaning the number of subcubes in which v is specified. For each Boolean value bit, restricting the partition to the facet where v ≠ bit produces a partition of the (|V| - 1)-dimensional subcube in which all remaining coordinates are still essential. By the dimension lower bound, this restricted partition must contain at least |V| subcubes, which leaves at most one subcube in the original partition where v is specified as bit. Since every essential coordinate must take each Boolean value at least once, that subcube exists and is unique.
There exists a coordinate v ∈ V that minimizes the number of cubes specifying it.
Since V is finite and nonempty, the degree function w ↦ |{i ∈ I | w ∈ s i}| attains a minimum at some coordinate v ∈ V. We record that the number of cubes mentioning v is less than or equal to the number of cubes mentioning any other coordinate w.
uses
exists_min_image,univ_nonempty,mem_univclassical obtain ⟨v, hv, hmin⟩ := exists_min_image (univ : Finset V) (fun w => (univ.filter (fun i => w ∈ s i)).card) univ_nonempty have hmin' (w : V) : (univ.filter (fun i => v ∈ s i)).card ≤ (univ.filter (fun i => w ∈ s i)).card := hmin w (mem_univ _)
Fix the minimum-degree coordinate v; for an arbitrary Boolean value bit, set up the restricted partition away from v.
We provide v as the existential witness and fix an arbitrary bit ∈ Bool. We then define the remaining coordinate type W = {w : V // w ≠ v}, the index set J of cubes that do not fix v to bit (i.e., either v ∉ s i or b i v = !bit), and the corresponding restricted cube supports t and assignments c.
refine ⟨v, ?_⟩ intro bit let J := {i : I // v ∉ s i ∨ b i v = !bit} let W := {w : V // w ≠ v} let t : J → Finset W := fun i => binary_partial_word_restrict_support (s i.val) v let c : J → W → Bool := fun i w => b i.val w.val
The restricted family (t, c) partitions the subcube {0, 1}^W with all coordinates in W remaining essential, which implies |W| + 1 ≤ |J|.
Restricting the partition to the facet where coordinate v is set to !bit yields a valid partition of the subcube on W. Because v was chosen to have minimum degree, all coordinates in W remain essential after this restriction. Thus, the dimension bound for essential partitions applies, giving |W| + 1 ≤ |J|.
uses
binary_partial_word_partition_restrict,binary_partial_word_partition_min_degree_restrict_essential,binary_partial_word_partition_dimension_boundhave hr := binary_partial_word_partition_restrict s b hconflict hcover v (!bit) have hess := binary_partial_word_partition_min_degree_restrict_essential s b hconflict hcover hessential v hmin' (!bit) have hbound : Fintype.card W + 1 ≤ Fintype.card J := binary_partial_word_partition_dimension_bound t c hr.1 hr.2 hess
The dimension of the restricted subcube is |W| = |V| - 1, and |V| > 0.
Since W is the complement of the singleton {v} in V, its cardinality is |V| - 1. Because V is nonempty, |V| is strictly positive.
uses
Fintype.card_subtype_eq,Fintype.card_subtype_compl,Fintype.card_poshave hW : Fintype.card W = Fintype.card V - 1 := by simpa only [W, Fintype.card_subtype_eq] using Fintype.card_subtype_compl (fun w : V => w = v) have hVpos : 0 < Fintype.card V := Fintype.card_pos
The number of cubes |J| in the restricted partition plus the number of cubes fixing v to bit equals the total number of cubes |I|.
Every cube index i ∈ I either belongs to J (meaning v ∉ s i or b i v = !bit) or satisfies the negation (meaning v ∈ s i and b i v = bit). Counting elements in I according to this dichotomy gives |J| + |{i | v ∈ s i ∧ b i v = bit}| = |I|.
uses
Fintype.card_subtype,card_filter_add_card_filter_not,card_univhave hbalance : Fintype.card J + (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = Fintype.card I := by rw [Fintype.card_subtype] have he : (univ.filter (fun i : I => ¬(v ∉ s i ∨ b i v = !bit))) = univ.filter (fun i => v ∈ s i ∧ b i v = bit) := by ext i by_cases hv : v ∈ s i · cases hb : b i v <;> cases bit <;> simp [hv, hb] · simp [hv] have hcount := card_filter_add_card_filter_not (s := univ) (fun i : I => v ∉ s i ∨ b i v = !bit) simpa only [he, card_univ] using hcount
There is at least one cube in the partition specifying coordinate v with value bit.
Because v is an essential coordinate in the cube partition, it must appear with both Boolean values true and false among the cubes. In particular, there exists an index i with v ∈ s i and b i v = bit, which shows that the set of such indices is nonempty and has positive cardinality.
uses
binary_partial_word_partition_both_bits,card_pos,mem_filter,mem_univobtain ⟨i, hi, hbi⟩ := binary_partial_word_partition_both_bits s b hconflict hcover v (hessential v) bit have hpos : 0 < (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card := by exact card_pos.mpr ⟨i, mem_filter.mpr ⟨mem_univ _, hi, hbi⟩⟩
The number of cubes specifying coordinate v with value bit is exactly 1. automation
From |W| = |V| - 1 and |V| > 0, we have |J| ≥ |W| + 1 = |V|. Since |J| + |{i | v ∈ s i ∧ b i v = bit}| = |I| = |V| + 1, we must have |{i | v ∈ s i ∧ b i v = bit}| ≤ 1. Together with |{i | v ∈ s i ∧ b i v = bit}| > 0, linear integer arithmetic forces this count to be exactly 1.
omega
exists_min_image- In any nonempty finite set, a function to a linearly ordered type attains its minimum value.
univ_nonempty- The universal finset of a nonempty finite type is nonempty.
mem_univ- Every element of a finite type belongs to its universal finset.
binary_partial_word_partition_restrict- Restricting a subcube partition to the facet where coordinate v is fixed to a value yields a valid subcube partition of that facet.
binary_partial_word_partition_min_degree_restrict_essential- Restricting a subcube partition along a coordinate of minimum degree preserves the condition that all remaining coordinates are essential.
binary_partial_word_partition_dimension_bound- Any partition of a Boolean cube where every coordinate is essential requires at least one more part than the dimension of the cube.
Fintype.card_subtype_eq- The cardinality of a singleton subtype {x // x = y} is 1.
Fintype.card_subtype_compl- The cardinality of the complement subtype {x // ¬p x} is |α| - |{x // p x}|.
Fintype.card_pos- A nonempty finite type has strictly positive cardinality.
Fintype.card_subtype- The cardinality of a subtype {x // p x} equals the size of the finset of elements satisfying p.
card_filter_add_card_filter_not- The number of elements of a finset satisfying a predicate plus the number not satisfying it equals the cardinality of the finset.
card_univ- The size of the universal finset univ equals the cardinality of the underlying finite type.
binary_partial_word_partition_both_bits- If a coordinate appears in some cube of a partition, it must appear with both Boolean values across the cubes.
card_pos- A finset has strictly positive cardinality if and only if it is nonempty.
mem_filter- An element belongs to filter p s if and only if it belongs to s and satisfies predicate p.
- The final conclusion that the count equals 1 is closed by the `omega` tactic using linear arithmetic on the inequalities $|J| \ge |V|$, $|J| + k = |V| + 1$, and $k > 0$, where $k$ is the number of cubes specifying coordinate $v$ with value `bit`.
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_singular_coordinate {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] [Nonempty 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) (hcard : Fintype.card I = Fintype.card V + 1) : ∃ v, ∀ bit : Bool, (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = 1 := by classical obtain ⟨v, hv, hmin⟩ := exists_min_image (univ : Finset V) (fun w => (univ.filter (fun i => w ∈ s i)).card) univ_nonempty have hmin' (w : V) : (univ.filter (fun i => v ∈ s i)).card ≤ (univ.filter (fun i => w ∈ s i)).card := hmin w (mem_univ _) refine ⟨v, ?_⟩ intro bit let J := {i : I // v ∉ s i ∨ b i v = !bit} let W := {w : V // w ≠ v} let t : J → Finset W := fun i => binary_partial_word_restrict_support (s i.val) v let c : J → W → Bool := fun i w => b i.val w.val have hr := binary_partial_word_partition_restrict s b hconflict hcover v (!bit) have hess := binary_partial_word_partition_min_degree_restrict_essential s b hconflict hcover hessential v hmin' (!bit) have hbound : Fintype.card W + 1 ≤ Fintype.card J := binary_partial_word_partition_dimension_bound t c hr.1 hr.2 hess have hW : Fintype.card W = Fintype.card V - 1 := by simpa only [W, Fintype.card_subtype_eq] using Fintype.card_subtype_compl (fun w : V => w = v) have hVpos : 0 < Fintype.card V := Fintype.card_pos have hbalance : Fintype.card J + (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = Fintype.card I := by rw [Fintype.card_subtype] have he : (univ.filter (fun i : I => ¬(v ∉ s i ∨ b i v = !bit))) = univ.filter (fun i => v ∈ s i ∧ b i v = bit) := by ext i by_cases hv : v ∈ s i · cases hb : b i v <;> cases bit <;> simp [hv, hb] · simp [hv] have hcount := card_filter_add_card_filter_not (s := univ) (fun i : I => v ∉ s i ∨ b i v = !bit) simpa only [he, card_univ] using hcount obtain ⟨i, hi, hbi⟩ := binary_partial_word_partition_both_bits s b hconflict hcover v (hessential v) bit have hpos : 0 < (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card := by exact card_pos.mpr ⟨i, mem_filter.mpr ⟨mem_univ _, hi, hbi⟩⟩ omega