AFTD Auto-Formalizing Theoretical Domains

op1370_coordinate_block_density_bound

theoremverifiedoriginal

Let t uncomplemented mutually strongly incomparable families of subsets of Fin n be given. Fix x and, for each color, a k-element set Y of coordinates other than x. Suppose that, for each nonempty color and each y in its set Y, both {x,y} and its complement occur outside that color. Then the total size is at most t times 2^(n-(k+1)).

Statement

theorem op1370_coordinate_block_density_bound (n t k : ℕ)
    (𝒜 : Fin t → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
    (hu : ∀ i, is_uncomplemented (𝒜 i)) (x : Fin n) (Y : Fin t → Finset (Fin n))
    (hxY : ∀ i, x ∉ Y i) (hcard : ∀ i, (Y i).card = k)
    (hblock : ∀ i : Fin t, (𝒜 i).Nonempty → ∀ y ∈ Y i,
      ∃ j l : Fin t, j ≠ i ∧ l ≠ i ∧ ({x,y} : Finset (Fin n)) ∈ 𝒜 j ∧ ({x,y} : Finset (Fin n))ᶜ ∈ 𝒜 l) :
    ∑ i, (𝒜 i).card ≤ t * 2 ^ (n - (k + 1))
Related work
A coordinate-blocker density bound related to Conjecture 4.3 of arXiv:2611.12199.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • strongly_incomparableAn indexed family of finset families 𝒜 : ι → Finset (Finset α) is strongly incomparable if for all i j : ι with i ≠ j, for all…
  • is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
  • op1370_coordinate_patterns_boundIf an uncomplemented family has the opposite membership of x at every coordinate in Y, where x is outside Y, then its size is at most…
  • op1370_block_forces_coordinate_patternFor strongly incomparable families, if a two-element set {x,y} and its complement both occur outside the family of S, then x belongs to S…

Read back from the Lean

For any natural numbers n, t, and k, given: 1. a family 𝒜 of t families of subsets of Fin n (indexed by Fin t), 2. an assumption that 𝒜 is strongly incomparable (for all i ≠ j, no set in 𝒜 i is a subset of any set in 𝒜 j), 3. an assumption that each 𝒜 i is uncomplemented (for every A ∈ 𝒜 i, the complement Aᶜ ∉ 𝒜 i), 4. an element x : Fin n, 5. a family of subsets Y i ⊆ Fin n for each i : Fin t, 6. an assumption that x ∉ Y i for all i : Fin t, 7. an assumption that |Y i| = k for all i : Fin t, and 8. an assumption that for every i : Fin t, if 𝒜 i is nonempty, then for every y ∈ Y i, there exist indices j, l : Fin t such that j ≠ i, l ≠ i, the pair {x, y} ∈ 𝒜 j, and its complement {x, y}ᶜ ∈ 𝒜 l; then the sum of the cardinalities of all 𝒜 i (for i : Fin t) is at most t * 2 ^ (n - (k + 1)).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

theorem op1370_coordinate_block_density_bound (n t k : ℕ)
    (𝒜 : Fin t → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
    (hu : ∀ i, is_uncomplemented (𝒜 i)) (x : Fin n) (Y : Fin t → Finset (Fin n))
    (hxY : ∀ i, x ∉ Y i) (hcard : ∀ i, (Y i).card = k)
    (hblock : ∀ i : Fin t, (𝒜 i).Nonempty → ∀ y ∈ Y i,
      ∃ j l : Fin t, j ≠ i ∧ l ≠ i ∧ ({x,y} : Finset (Fin n)) ∈ 𝒜 j ∧ ({x,y} : Finset (Fin n))ᶜ ∈ 𝒜 l) :
    ∑ i, (𝒜 i).card ≤ t * 2 ^ (n - (k + 1)) := by
  open Finset in
  classical
  have hb : ∀ i, (𝒜 i).card ≤ 2 ^ (n - (k + 1)) := by
    intro i
    have hh := op1370_coordinate_patterns_bound n (𝒜 i) (hu i) x (Y i) (hxY i) (by
      intro S hS y hy
      obtain ⟨j, l, hji, hli, hw, hc⟩ := hblock i ⟨S, hS⟩ y hy
      exact op1370_block_forces_coordinate_pattern n t 𝒜 hinc i j l hji hli x y hw hc S hS)
    simpa [hcard i] using hh
  calc
    ∑ i, (𝒜 i).card ≤ ∑ _i : Fin t, 2 ^ (n - (k + 1)) := sum_le_sum (by intro i hi; exact hb i)
    _ = t * 2 ^ (n - (k + 1)) := by simp
See it in the graphDiscuss this resultChallenge it