op1370_independent_upper_difference_hub
For two upper-closed families whose complementary lower-closed families attain equality in the uniform correlation inequality, if the first upper family is proper and the second is nonempty, the difference of the second from the first has a member Z such that every member of the difference has a common superset with Z in the difference.
Statement
theorem op1370_independent_upper_difference_hub (n : ℕ) (U V : Finset (Finset (Fin n)))
(hU : IsUpperSet (U : Set (Finset (Fin n))))
(hV : IsUpperSet (V : Set (Finset (Fin n))))
(hUproper : ∃ X, X ∉ U) (hVne : V.Nonempty)
(hEq : (Uᶜ).card * (Vᶜ).card = 2 ^ n * ((Uᶜ) ∩ (Vᶜ)).card) :
∃ Z ∈ V, Z ∉ U ∧ ∀ X ∈ V, X ∉ U →
∃ W ∈ V, W ∉ U ∧ X ⊆ W ∧ Z ⊆ W- Source
- Equality-structure lemma for the balanced-case route to OP-1370, arXiv:2611.12199, Conjecture 4.3.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op1370_lower_independent_fibersFor two downward-closed families on a finite Boolean cube that attain equality in the uniform correlation inequality, at every coordinate…
- Used by 1
- 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
The proof establishes that the set P of coordinates where the complement family Vᶜ is sensitive serves as the hub Z ∈ V \ U. Since Uᶜ and Vᶜ are lower sets achieving equality in the uniform correlation inequality, any coordinate where Vᶜ is sensitive must be a coordinate of invariance for Uᶜ, and vice versa. As U is a proper upper set and V is nonempty, the empty set is outside U and the full universe is in V; using the invariance lemma (op1370_fiber_union), the empty set shifts along P to show P ∉ U, while the universe shifts along Pᶜ to show P ∈ V. Finally, for any X ∈ V \ U, the union X ∪ P remains in V by upward closure and stays outside U because Uᶜ is invariant under adding P.
For any family 𝒜 and element x, if the member subfamily and non-member subfamily at x coincide, then S ∈ 𝒜 if and only if S ∪ {x} ∈ 𝒜.
We split into cases depending on whether x ∈ S. If x ∈ S, inserting x does not change S. If x ∉ S, the assumption that the member subfamily equals the non-member subfamily means S belongs to the member subfamily if and only if it belongs to the non-member subfamily, which translates directly to S ∪ {x} ∈ 𝒜 ↔ S ∈ 𝒜.
uses
mem_memberSubfamily,mem_nonMemberSubfamily,not_false_eq_true,and_trueby_cases hx : x ∈ S · simp [hx] · have hf : S ∈ 𝒜.memberSubfamily x ↔ S ∈ 𝒜.nonMemberSubfamily x := by rw [h] simpa only [mem_memberSubfamily, mem_nonMemberSubfamily, hx, not_false_eq_true, and_true] using hf.symm
If 𝒜 has identical member and non-member subfamilies at every element of T, then S ∈ 𝒜 if and only if S ∪ T ∈ 𝒜.
By induction on the finite set T. The base case T = ∅ is trivial. In the inductive step T = {x} ∪ T', the induction hypothesis gives S ∈ 𝒜 ↔ S ∪ T' ∈ 𝒜, and op1370_fiber_toggle at x gives S ∪ T' ∈ 𝒜 ↔ S ∪ ({x} ∪ T') ∈ 𝒜.
uses
Finset.induction_on,Finset.mem_insert_of_mem,Finset.mem_insert_self,op1370_fiber_toggle,Finset.union_insertinduction T using Finset.induction_on with | empty => simp | @insert x T hx ih => have hT : ∀ y ∈ T, 𝒜.memberSubfamily y = 𝒜.nonMemberSubfamily y := by intro y hy exact h y (Finset.mem_insert_of_mem hy) have hx' : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x := h x (Finset.mem_insert_self x T) calc S ∈ 𝒜 ↔ S ∪ T ∈ 𝒜 := ih hT _ ↔ insert x (S ∪ T) ∈ 𝒜 := op1370_fiber_toggle 𝒜 x hx' (S ∪ T) _ ↔ S ∪ insert x T ∈ 𝒜 := by rw [Finset.union_insert]
The complements Uᶜ and Vᶜ are lower sets.
Since U and V are upper sets, their complements in the boolean lattice are lower sets, established via isLowerSet_compl.mpr.
uses
coe_compl,isLowerSet_compl.mprclassical have hL : IsLowerSet ((Uᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by simpa only [coe_compl] using (isLowerSet_compl.mpr hU) have hM : IsLowerSet ((Vᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by simpa only [coe_compl] using (isLowerSet_compl.mpr hV)
Letting P be the set of coordinates where Vᶜ depends on the coordinate, Uᶜ is independent of every coordinate in P, and Vᶜ is independent of every coordinate outside P.
We define P as the set of coordinates x where the member and non-member subfamilies of Vᶜ differ. For x ∈ P, equality in the correlation inequality forces Uᶜ to have equal member and non-member subfamilies at x by op1370_lower_independent_fibers. For x ∉ P, Vᶜ has equal member and non-member subfamilies at x by definition of P.
uses
op1370_lower_independent_fibers,mem_univlet P : Finset (Fin n) := univ.filter fun x => (Vᶜ).memberSubfamily x ≠ (Vᶜ).nonMemberSubfamily x have hLfixed : ∀ x ∈ P, (Uᶜ).memberSubfamily x = (Uᶜ).nonMemberSubfamily x := by intro x hx have hx' := (mem_filter.mp hx).2 exact (op1370_lower_independent_fibers n (Uᶜ) (Vᶜ) hL hM hEq x).resolve_right hx' have hMfixed : ∀ x ∈ Pᶜ, (Vᶜ).memberSubfamily x = (Vᶜ).nonMemberSubfamily x := by intro x hx have hnot : x ∉ P := mem_compl.mp hx by_contra hne exact hnot (mem_filter.mpr ⟨mem_univ x, hne⟩)
The empty set is not in U, and the universal set is in V.
Since U is a proper upper set, any set X ∉ U would contain ∅, so ∅ cannot be in U (otherwise all supersets would be in U). Since V is nonempty, any member Y ∈ V is a subset of the universal set, so the universal set belongs to V because V is an upper set.
uses
Finset.empty_subset,subset_univobtain ⟨X, hX⟩ := hUproper have hUempty : (∅ : Finset (Fin n)) ∉ U := by intro h exact hX (hU (Finset.empty_subset X) h) obtain ⟨Y, hY⟩ := hVne have hVtop : (univ : Finset (Fin n)) ∈ V := hV (subset_univ Y) hY
P does not belong to U.
Since ∅ ∉ U, the empty set belongs to Uᶜ. Because Uᶜ is independent of all coordinates in P, op1370_fiber_union implies ∅ ∈ Uᶜ ↔ ∅ ∪ P ∈ Uᶜ. Hence P ∈ Uᶜ, meaning P ∉ U.
uses
op1370_fiber_unionhave hPnotU : P ∉ U := by have h := op1370_fiber_union (Uᶜ) P hLfixed (∅ : Finset (Fin n)) have he : (∅ : Finset (Fin n)) ∈ Uᶜ := by simpa using hUempty have : P ∈ Uᶜ := by simpa using h.mp he simpa using this
P belongs to V.
Since the universal set belongs to V, univ ∉ Vᶜ. Because Vᶜ is independent of all coordinates in Pᶜ, op1370_fiber_union gives P ∈ Vᶜ ↔ P ∪ Pᶜ ∈ Vᶜ. Since P ∪ Pᶜ = univ ∉ Vᶜ, we conclude P ∉ Vᶜ, meaning P ∈ V.
uses
op1370_fiber_unionhave hPinV : P ∈ V := by have h := op1370_fiber_union (Vᶜ) Pᶜ hMfixed P have ht : (univ : Finset (Fin n)) ∉ Vᶜ := by simpa using hVtop have hp : P ∉ Vᶜ := by intro hp apply ht simpa using h.mp hp simpa using hp
Z = P is the desired set in V \ U, and for any X ∈ V \ U, W = X ∪ P is a common superset belonging to V \ U.
We have already shown P ∈ V and P ∉ U. Given any X ∈ V with X ∉ U, the union W = X ∪ P is an upper set extension of X, so W ∈ V. Since X ∉ U, we have X ∈ Uᶜ; since Uᶜ is independent of coordinates in P, op1370_fiber_union implies X ∪ P ∈ Uᶜ, so W ∉ U. Both X and P are subsets of W by definition of the union.
uses
subset_union_left,subset_union_right,op1370_fiber_unionrefine ⟨P, hPinV, hPnotU, ?_⟩ intro X hXV hXU refine ⟨X ∪ P, hV (subset_union_left) hXV, ?_, subset_union_left, subset_union_right⟩ have h := op1370_fiber_union (Uᶜ) P hLfixed X have hX' : X ∈ Uᶜ := by simpa using hXU have : X ∪ P ∈ Uᶜ := h.mp hX' simpa using this
not_false_eq_true- An element is not in false proposition is True.
and_true- Conjunction with True simplifies to the proposition itself.
mem_memberSubfamily- A set S belongs to the member subfamily of A at x if and only if x ∉ S and insert x S ∈ A.
mem_nonMemberSubfamily- A set S belongs to the non-member subfamily of A at x if and only if x ∉ S and S ∈ A.
Finset.induction_on- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
Finset.mem_insert_of_mem- An element of a set s remains an element when another element is inserted into s.
Finset.mem_insert_self- An element is a member of the set formed by inserting it into s.
op1370_fiber_toggle- If a family's member and non-member subfamilies at x coincide, membership in the family is invariant under inserting x.
Finset.union_insert- The union of s with insert a t equals insert a (s ∪ t).
coe_compl- The set coercion of the complement of a finset equals the set complement of the coerced finset.
isLowerSet_compl.mpr- The complement of an upper set is a lower set.
op1370_lower_independent_fibers- For two lower families attaining equality in the correlation inequality, at every coordinate at least one family has equal member and non-member subfamilies.
mem_univ- Every element of a finite type belongs to the universal finset.
Finset.empty_subset- The empty set is a subset of every finite set.
subset_univ- Every finite set of elements of a finite type is a subset of the universal finset.
op1370_fiber_union- If a family has equal member and non-member subfamilies for all elements of T, membership in the family is invariant under taking the union with T.
subset_union_left- A finite set is a subset of its union with another set.
subset_union_right- A finite set is a subset of the union of another set with it.
- The proof relies on op1370_lower_independent_fibers, which characterizes equality in the Harris-Kleitman correlation inequality for lower sets as requiring coordinate-wise independence for at least one of the two families.
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 Finsetlemma op1370_fiber_toggle {α : Type*} [DecidableEq α] (𝒜 : Finset (Finset α)) (x : α) (h : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x) (S : Finset α) : S ∈ 𝒜 ↔ insert x S ∈ 𝒜 := by by_cases hx : x ∈ S · simp [hx] · have hf : S ∈ 𝒜.memberSubfamily x ↔ S ∈ 𝒜.nonMemberSubfamily x := by rw [h] simpa only [mem_memberSubfamily, mem_nonMemberSubfamily, hx, not_false_eq_true, and_true] using hf.symmlemma op1370_fiber_union {α : Type*} [DecidableEq α] (𝒜 : Finset (Finset α)) (T : Finset α) (h : ∀ x ∈ T, 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x) (S : Finset α) : S ∈ 𝒜 ↔ S ∪ T ∈ 𝒜 := by induction T using Finset.induction_on with | empty => simp | @insert x T hx ih => have hT : ∀ y ∈ T, 𝒜.memberSubfamily y = 𝒜.nonMemberSubfamily y := by intro y hy exact h y (Finset.mem_insert_of_mem hy) have hx' : 𝒜.memberSubfamily x = 𝒜.nonMemberSubfamily x := h x (Finset.mem_insert_self x T) calc S ∈ 𝒜 ↔ S ∪ T ∈ 𝒜 := ih hT _ ↔ insert x (S ∪ T) ∈ 𝒜 := op1370_fiber_toggle 𝒜 x hx' (S ∪ T) _ ↔ S ∪ insert x T ∈ 𝒜 := by rw [Finset.union_insert]theorem op1370_independent_upper_difference_hub (n : ℕ) (U V : Finset (Finset (Fin n))) (hU : IsUpperSet (U : Set (Finset (Fin n)))) (hV : IsUpperSet (V : Set (Finset (Fin n)))) (hUproper : ∃ X, X ∉ U) (hVne : V.Nonempty) (hEq : (Uᶜ).card * (Vᶜ).card = 2 ^ n * ((Uᶜ) ∩ (Vᶜ)).card) : ∃ Z ∈ V, Z ∉ U ∧ ∀ X ∈ V, X ∉ U → ∃ W ∈ V, W ∉ U ∧ X ⊆ W ∧ Z ⊆ W := by classical have hL : IsLowerSet ((Uᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by simpa only [coe_compl] using (isLowerSet_compl.mpr hU) have hM : IsLowerSet ((Vᶜ : Finset (Finset (Fin n))) : Set (Finset (Fin n))) := by simpa only [coe_compl] using (isLowerSet_compl.mpr hV) let P : Finset (Fin n) := univ.filter fun x => (Vᶜ).memberSubfamily x ≠ (Vᶜ).nonMemberSubfamily x have hLfixed : ∀ x ∈ P, (Uᶜ).memberSubfamily x = (Uᶜ).nonMemberSubfamily x := by intro x hx have hx' := (mem_filter.mp hx).2 exact (op1370_lower_independent_fibers n (Uᶜ) (Vᶜ) hL hM hEq x).resolve_right hx' have hMfixed : ∀ x ∈ Pᶜ, (Vᶜ).memberSubfamily x = (Vᶜ).nonMemberSubfamily x := by intro x hx have hnot : x ∉ P := mem_compl.mp hx by_contra hne exact hnot (mem_filter.mpr ⟨mem_univ x, hne⟩) obtain ⟨X, hX⟩ := hUproper have hUempty : (∅ : Finset (Fin n)) ∉ U := by intro h exact hX (hU (Finset.empty_subset X) h) obtain ⟨Y, hY⟩ := hVne have hVtop : (univ : Finset (Fin n)) ∈ V := hV (subset_univ Y) hY have hPnotU : P ∉ U := by have h := op1370_fiber_union (Uᶜ) P hLfixed (∅ : Finset (Fin n)) have he : (∅ : Finset (Fin n)) ∈ Uᶜ := by simpa using hUempty have : P ∈ Uᶜ := by simpa using h.mp he simpa using this have hPinV : P ∈ V := by have h := op1370_fiber_union (Vᶜ) Pᶜ hMfixed P have ht : (univ : Finset (Fin n)) ∉ Vᶜ := by simpa using hVtop have hp : P ∉ Vᶜ := by intro hp apply ht simpa using h.mp hp simpa using hp refine ⟨P, hPinV, hPnotU, ?_⟩ intro X hXV hXU refine ⟨X ∪ P, hV (subset_union_left) hXV, ?_, subset_union_left, subset_union_right⟩ have h := op1370_fiber_union (Uᶜ) P hLfixed X have hX' : X ∈ Uᶜ := by simpa using hXU have : X ∪ P ∈ Uᶜ := h.mp hX' simpa using this