op1370_lower_independent_fibers
For two downward-closed families on a finite Boolean cube that attain equality in the uniform correlation inequality, at every coordinate the two slices coincide for at least one family.
Statement
theorem op1370_lower_independent_fibers (n : ℕ) (𝒜 ℬ : Finset (Finset (Fin n)))
(h𝒜 : IsLowerSet (𝒜 : Set (Finset (Fin n))))
(hℬ : IsLowerSet (ℬ : Set (Finset (Fin n))))
(hEq : 𝒜.card * ℬ.card = 2 ^ n * (𝒜 ∩ ℬ).card) (x : Fin n) :
𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x ∨
ℬ.memberSubfamily x = ℬ.nonMemberSubfamily x- Source
- A coordinate-slice equality lemma for a balanced-case route to OP-1370, arXiv:2611.12199, Conjecture 4.3.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 2
- op1370_independent_upper_difference_hubFor two upper-closed families whose complementary lower-closed families attain equality in the uniform correlation inequality, if the…
- op1370_balanced_cross_incomparable_hubIf two mutually incomparable set families each have one quarter of the Boolean cube, the second family has a member Z such that every…
The proof, explained
We decompose the Boolean cube along coordinate x into two slices, the 1-slice and the 0-slice, over an (n-1)-element subcube. Because 𝒜 and ℬ are downward-closed, their 1-slices are subsets of their 0-slices; assuming for contradiction that neither family has equal slices yields strict inequalities |𝒜₁| < |𝒜₀| and |ℬ₁| < |ℬ₀|. Expanding the strictly positive product (|𝒜₀| - |𝒜₁|)(|ℬ₀| - |ℬ₁|) > 0 and applying the correlation inequality to each pair of slices contradicts the equality |𝒜||ℬ| = 2^n |𝒜 ∩ ℬ|.
The coordinate x is removed to form the subcube domain s = univ \ {x}, which has size n - 1.
We define s as the complement of {x} in Fin n and evaluate its cardinality |s| = n - 1.
classical let s : Finset (Fin n) := Finset.univ.erase x have hs : s.card = n - 1 := by simp [s]
Every set in the 0-slice (non-member subfamily) and 1-slice (member subfamily) along coordinate x is a subset of s.
By definition of both slices, any member set t does not contain x. Therefore, every element y ∈ t satisfies y ≠ x, which places y in s = univ \ {x}.
uses
mem_nonMemberSubfamily,mem_erase,mem_univ,and_true,mem_memberSubfamilyhave h0 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.nonMemberSubfamily x, t ⊆ s := by intro t ht y hy rw [mem_nonMemberSubfamily] at ht simp only [s, mem_erase, mem_univ, and_true] intro hxy exact ht.2 (hxy ▸ hy) have h1 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.memberSubfamily x, t ⊆ s := by intro t ht y hy rw [mem_memberSubfamily] at ht simp only [s, mem_erase, mem_univ, and_true] intro hxy exact ht.2 (hxy ▸ hy)
For both downward-closed families 𝒜 and ℬ, the 1-slice is contained in the 0-slice, so |𝒜₁| ≤ |𝒜₀| and |ℬ₁| ≤ |ℬ₀|.
Because 𝒜 and ℬ are downward-closed, removing x from a set in the family leaves another set in the family, meaning 𝒜₁ ⊆ 𝒜₀ and ℬ₁ ⊆ ℬ₀. The inequalities on cardinalities follow immediately.
uses
card_le_cardhave hAsub : 𝒜.memberSubfamily x ⊆ 𝒜.nonMemberSubfamily x := h𝒜.memberSubfamily_subset_nonMemberSubfamily have hBsub : ℬ.memberSubfamily x ⊆ ℬ.nonMemberSubfamily x := hℬ.memberSubfamily_subset_nonMemberSubfamily have hA := card_le_card hAsub have hB := card_le_card hBsub
The uniform correlation inequality holds on the subcube for the 0-slices and for the 1-slices: |𝒜₀| |ℬ₀| ≤ 2^|s| |𝒜₀ ∩ ℬ₀| and |𝒜₁| |ℬ₁| ≤ 2^|s| |𝒜₁ ∩ ℬ₁|.
The slices of a downward-closed family are themselves downward-closed families consisting entirely of subsets of s, so Kleitman's correlation inequality applies to both the 0-slices and the 1-slices.
have h00 := h𝒜.nonMemberSubfamily.le_card_inter_finset' hℬ.nonMemberSubfamily (h0 𝒜) (h0 ℬ) have h11 := h𝒜.memberSubfamily.le_card_inter_finset' hℬ.memberSubfamily (h1 𝒜) (h1 ℬ)
The total cube size factors as 2^n = 2 * 2^|s|.
Since x ∈ Fin n, n is strictly positive, so 2^n = 2^(|s| + 1) = 2 * 2^|s|.
uses
Nat.lt_of_le_of_lt,Nat.zero_le,Nat.mul_comm,pow_succ,Nat.sub_add_cancelhave hn : 0 < n := Nat.lt_of_le_of_lt (Nat.zero_le x.val) x.isLt have hp : 2 ^ n = 2 * 2 ^ s.card := by rw [hs, Nat.mul_comm (2 : ℕ) (2 ^ (n - 1)), ← pow_succ, Nat.sub_add_cancel hn]
The equality condition decomposes by slices along x into (|𝒜₁| + |𝒜₀|) * (|ℬ₁| + |ℬ₀|) = 2 * 2^|s| * (|𝒜₁ ∩ ℬ₁| + |𝒜₀ ∩ ℬ₀|).
We partition 𝒜, ℬ, and 𝒜 ∩ ℬ into their respective 1-slices and 0-slices along x, and substitute 2^n = 2 * 2^|s| into the assumed equality.
uses
card_memberSubfamily_add_card_nonMemberSubfamily,memberSubfamily_inter,nonMemberSubfamily_interhave hEq' := hEq rw [← card_memberSubfamily_add_card_nonMemberSubfamily x 𝒜, ← card_memberSubfamily_add_card_nonMemberSubfamily x ℬ, ← card_memberSubfamily_add_card_nonMemberSubfamily x (𝒜 ∩ ℬ), memberSubfamily_inter, nonMemberSubfamily_inter, hp] at hEq'
Assuming for contradiction that neither family has identical slices, both 1-slices are strictly smaller than their 0-slices: |𝒜₁| < |𝒜₀| and |ℬ₁| < |ℬ₀|.
If 𝒜₁ ≠ 𝒜₀ and ℬ₁ ≠ ℬ₀, the inclusions 𝒜₁ ⊆ 𝒜₀ and ℬ₁ ⊆ ℬ₀ are proper, which implies strict inequalities between their finite cardinalities.
uses
Finset.card_lt_card,lt_of_le_of_neby_contra h push_neg at h have ha : (𝒜.memberSubfamily x).card < (𝒜.nonMemberSubfamily x).card := by exact Finset.card_lt_card (lt_of_le_of_ne hAsub h.1) have hb : (ℬ.memberSubfamily x).card < (ℬ.nonMemberSubfamily x).card := by exact Finset.card_lt_card (lt_of_le_of_ne hBsub h.2)
Contradiction: the strict inequalities force a strictly positive difference that contradicts the correlation equality. automation
The identity (|𝒜₀| - |𝒜₁|)(|ℬ₀| - |ℬ₁|) > 0 expands to (|𝒜₁| + |𝒜₀|)(|ℬ₁| + |ℬ₀|) < 2(|𝒜₀||ℬ₀| + |𝒜₁||ℬ₁|). Together with the subcube correlation bounds |𝒜₀||ℬ₀| ≤ 2^|s| |𝒜₀ ∩ ℬ₀| and |𝒜₁||ℬ₁| ≤ 2^|s| |𝒜₁ ∩ ℬ₁|, this strictly bounds the left-hand side below 2 * 2^|s| * (|𝒜₁ ∩ ℬ₁| + |𝒜₀ ∩ ℬ₀|), contradicting their equality. Nonlinear arithmetic closes the goal.
nlinarith
and_true- For any proposition p, p ∧ True is equivalent to p.
card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
card_memberSubfamily_add_card_nonMemberSubfamily- The size of a family is the sum of the sizes of its member and non-member subfamilies at coordinate a: |𝒜₁| + |𝒜₀| = |𝒜|.
Finset.card_lt_card- If s ⊂ t for finite sets s and t, then |s| < |t|.
lt_of_le_of_ne- In any partial order, if a ≤ b and a ≠ b, then a < b.
mem_erase- An element y belongs to s \ {x} if and only if y ≠ x and y ∈ s.
mem_memberSubfamily- A set s belongs to the member subfamily of 𝒜 at a if and only if s ∪ {a} ∈ 𝒜 and a ∉ s.
mem_nonMemberSubfamily- A set s belongs to the non-member subfamily of 𝒜 at a if and only if s ∈ 𝒜 and a ∉ s.
mem_univ- Every element of a finite type belongs to the universal finset univ.
memberSubfamily_inter- The member subfamily of an intersection is the intersection of the member subfamilies: (𝒜 ∩ ℬ)₁ = 𝒜₁ ∩ ℬ₁.
Nat.lt_of_le_of_lt- If a ≤ b and b < c, then a < c.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
Nat.zero_le- For any natural number n, 0 ≤ n.
nonMemberSubfamily_inter- The non-member subfamily of an intersection is the intersection of the non-member subfamilies: (𝒜 ∩ ℬ)₀ = 𝒜₀ ∩ ℬ₀.
pow_succ- For any monoid element a and natural number n, a^(n + 1) = a^n * a.
- The final contradiction is closed by `nlinarith` using the algebraic identity $2(a_0 b_0 + a_1 b_1) - (a_0 + a_1)(b_0 + b_1) = (a_0 - a_1)(b_0 - b_1) > 0$ together with the subcube correlation bounds $a_0 b_0 \le 2^{n-1} c_0$ and $a_1 b_1 \le 2^{n-1} c_1$.
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 2000000theorem op1370_lower_independent_fibers (n : ℕ) (𝒜 ℬ : Finset (Finset (Fin n))) (h𝒜 : IsLowerSet (𝒜 : Set (Finset (Fin n)))) (hℬ : IsLowerSet (ℬ : Set (Finset (Fin n)))) (hEq : 𝒜.card * ℬ.card = 2 ^ n * (𝒜 ∩ ℬ).card) (x : Fin n) : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x ∨ ℬ.memberSubfamily x = ℬ.nonMemberSubfamily x := by classical let s : Finset (Fin n) := Finset.univ.erase x have hs : s.card = n - 1 := by simp [s] have h0 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.nonMemberSubfamily x, t ⊆ s := by intro t ht y hy rw [mem_nonMemberSubfamily] at ht simp only [s, mem_erase, mem_univ, and_true] intro hxy exact ht.2 (hxy ▸ hy) have h1 (𝒞 : Finset (Finset (Fin n))) : ∀ t ∈ 𝒞.memberSubfamily x, t ⊆ s := by intro t ht y hy rw [mem_memberSubfamily] at ht simp only [s, mem_erase, mem_univ, and_true] intro hxy exact ht.2 (hxy ▸ hy) have hAsub : 𝒜.memberSubfamily x ⊆ 𝒜.nonMemberSubfamily x := h𝒜.memberSubfamily_subset_nonMemberSubfamily have hBsub : ℬ.memberSubfamily x ⊆ ℬ.nonMemberSubfamily x := hℬ.memberSubfamily_subset_nonMemberSubfamily have hA := card_le_card hAsub have hB := card_le_card hBsub have h00 := h𝒜.nonMemberSubfamily.le_card_inter_finset' hℬ.nonMemberSubfamily (h0 𝒜) (h0 ℬ) have h11 := h𝒜.memberSubfamily.le_card_inter_finset' hℬ.memberSubfamily (h1 𝒜) (h1 ℬ) have hn : 0 < n := Nat.lt_of_le_of_lt (Nat.zero_le x.val) x.isLt have hp : 2 ^ n = 2 * 2 ^ s.card := by rw [hs, Nat.mul_comm (2 : ℕ) (2 ^ (n - 1)), ← pow_succ, Nat.sub_add_cancel hn] have hEq' := hEq rw [← card_memberSubfamily_add_card_nonMemberSubfamily x 𝒜, ← card_memberSubfamily_add_card_nonMemberSubfamily x ℬ, ← card_memberSubfamily_add_card_nonMemberSubfamily x (𝒜 ∩ ℬ), memberSubfamily_inter, nonMemberSubfamily_inter, hp] at hEq' by_contra h push_neg at h have ha : (𝒜.memberSubfamily x).card < (𝒜.nonMemberSubfamily x).card := by exact Finset.card_lt_card (lt_of_le_of_ne hAsub h.1) have hb : (ℬ.memberSubfamily x).card < (ℬ.nonMemberSubfamily x).card := by exact Finset.card_lt_card (lt_of_le_of_ne hBsub h.2) nlinarith