AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_singular_coordinate

theoremverified

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
Used by 1

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.

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

    lines 14–18

    uses exists_min_image, univ_nonempty, mem_univ

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

    lines 19–24

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

    lines 25–29

    uses binary_partial_word_partition_restrict, binary_partial_word_partition_min_degree_restrict_essential, binary_partial_word_partition_dimension_bound

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

    lines 30–33

    uses Fintype.card_subtype_eq, Fintype.card_subtype_compl, Fintype.card_pos

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

    lines 34–45

    uses Fintype.card_subtype, card_filter_add_card_filter_not, card_univ

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

    lines 46–49

    uses binary_partial_word_partition_both_bits, card_pos, mem_filter, mem_univ

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

    line 50

      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.

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