wild_three_uniform_fixed_support_disjoint_count
For a finite indexed family T_i of three-element sets and a fixed three-element set S, assume each vertex of S occurs in d indices and each distinct pair in S occurs in l indices. If D counts indices disjoint from S and Q counts indices equal to S, then D+Q+3d=N+3l in the integers, where N is the index-type cardinality. Repeated supports count with multiplicity; hypotheses are only needed on S.
Statement
theorem wild_three_uniform_fixed_support_disjoint_count {ι κ : Type*} [Fintype ι] [DecidableEq κ] (T : ι → Finset κ) (S : Finset κ) (d l : ℕ) (hsize : ∀ i, (T i).card = 3) (hS : S.card = 3) (hvertex : ∀ a ∈ S, (univ.filter fun i => a ∈ T i).card = d) (hpair : ∀ a ∈ S, ∀ b ∈ S, a ≠ b → (univ.filter fun i => a ∈ T i ∧ b ∈ T i).card = l) : ((univ.filter fun i => Disjoint S (T i)).card : ℤ) + ((univ.filter fun i => S = T i).card : ℤ) + 3*(d : ℤ) = (Fintype.card ι : ℤ) + 3*(l : ℤ)
- Source
- IN-364 / OP-306, continuation of the finite weighted-partition route for https://arxiv.org/html/2610.22142v1, Sections3.3 and6. Standard permutation-orbit background: Matchings and Representation Theory (2018), Section4.10, https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/9d33772f-c7dc-409f-a4ed-521da8d87890/content. The witness triple system is standard incidence data; these are route helpers or finite method diagnostics. No wild-number bound, new exact sharpness case, general sign theorem, or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- wild_three_uniform_disjoint_pair_countLet T_i be three-element subsets of a finite vertex type, indexed by a finite type of size N, with repeated subsets allowed. Suppose each…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof establishes that for any two 3-element sets S and T_i, the indicator identity 2 * [S ∩ T_i = ∅] = 2 - 2|S ∩ T_i| + |(S ∩ T_i).offDiag| - 2 * [S = T_i] holds. Summing this equation over all indices i, the sum of intersection sizes is computed as 3d by double counting elements of S, and the sum of off-diagonal sizes is computed as 6l by double counting ordered pairs from S. Substituting these counts into the summed identity gives 2D = 2N - 6d + 6l - 2Q, which immediately simplifies to D + Q + 3d = N + 3l.
For each index i, the intersection size |S ∩ T_i| equals the sum over elements of S of the indicator that the element belongs to T_i
By rewriting the intersection S ∩ T_i as a filtered sub-finset of S and expressing the cardinality of a filtered finset as a sum of indicator values, each |S ∩ T_i| is written as a sum of 0-1 indicators over S.
uses
sum_filter,filter_mem_eq_interclassical have hcard (i : ι) : ((S ∩ T i).card : ℤ) = ∑ a ∈ S, if a ∈ T i then (1 : ℤ) else 0 := by simp [← sum_filter,filter_mem_eq_inter]
The total incidence sum ∑_i |S ∩ T_i| equals the sum over a ∈ S of the frequencies |{i | a ∈ T_i}|
Substitute the indicator representation of |S ∩ T_i| into the outer sum over i, swap the order of summation using sum_comm, and simplify the inner sum over i into the cardinality of the index set of blocks containing a.
uses
sum_comm,sum_congr,sum_filtersimp_rw [hcard] rw [sum_comm] apply sum_congr rfl intro a ha simp [← sum_filter]
Assume classical logic for decidability
Enable classical logic so that all propositions, in particular set equality and disjointness, are decidable.
classical
The total intersection size ∑_i |S ∩ T_i| equals 3d
By the incidence sum identity wild_fixed_support_incidence_sum, the sum rewrites to ∑_{a ∈ S} |{i | a ∈ T_i}|. Since every vertex a ∈ S appears in d sets and |S| = 3, this sum evaluates to 3d.
uses
wild_fixed_support_incidence_sum,sum_congrhave hinter : (∑ i : ι, ((S ∩ T i).card : ℤ)) = 3*(d : ℤ) := by rw [wild_fixed_support_incidence_sum] calc _ = ∑ a ∈ S, (d : ℤ) := by apply sum_congr rfl intro a ha rw [hvertex a ha] _ = _ := by simp [hS]
The total off-diagonal size ∑_i |(S ∩ T_i).offDiag| equals 6l
The off-diagonal of S ∩ T_i is S.offDiag ∩ (T_i).offDiag. Applying wild_fixed_support_incidence_sum transforms the sum over i into a sum over all ordered pairs (a, b) ∈ S.offDiag of the number of sets containing both a and b. Each of the 3 * 2 = 6 pairs occurs in l sets, so the sum evaluates to 6l.
uses
offDiag_inter,wild_fixed_support_incidence_sum,sum_congr,mem_offDiag,offDiag_cardhave hoff : (∑ i : ι, ((S ∩ T i).offDiag.card : ℤ)) = 6*(l : ℤ) := by simp_rw [offDiag_inter] rw [wild_fixed_support_incidence_sum] calc _ = ∑ z ∈ S.offDiag, (l : ℤ) := by apply sum_congr rfl intro z hz obtain ⟨ha,hb,hne⟩ := mem_offDiag.mp hz have hf : (univ.filter fun i => z ∈ (T i).offDiag) = (univ.filter fun i => z.1 ∈ T i ∧ z.2 ∈ T i) := by ext i simp [mem_offDiag,hne] rw [hf,hpair z.1 ha z.2 hb hne] _ = _ := by simp [offDiag_card,hS]
Summing the indicator identity over all indices i links disjointness, intersection sizes, pair counts, and set equality
For each index i, both S and T_i have cardinality 3, so wild_three_set_disjoint_indicator applies. Summing this equality over all i equates the sum of twice the disjointness indicators to the sum of the RHS expressions.
uses
sum_congr,wild_three_set_disjoint_indicatorhave heq := sum_congr (s₁ := (univ : Finset ι)) rfl (fun i _ => wild_three_set_disjoint_indicator S (T i) hS (hsize i))
Express the sums of the disjointness indicators and equality indicators as set cardinalities D and Q
Summing the indicator of Disjoint S (T_i) over all i gives the size D of the set of indices disjoint from S, and summing the indicator of S = T_i gives the size Q of the set of indices equal to S.
uses
sum_filterhave hD : (∑ i : ι, if Disjoint S (T i) then (1 : ℤ) else 0) = ((univ.filter fun i => Disjoint S (T i)).card : ℤ) := by simp [← sum_filter] have hQ : (∑ i : ι, if S = T i then (1 : ℤ) else 0) = ((univ.filter fun i => S = T i).card : ℤ) := by simp [← sum_filter]
Distribute the summation and factor constants across the terms of the identity
Distribute the sum over subtractions and additions, factor out scalar multipliers, and evaluate the sum of the constant 2 over all indices as 2 * N, where N = Fintype.card ι.
uses
sum_sub_distrib,sum_add_distrib,mul_sum,sum_const,card_univ,nsmul_eq_mulsimp only [sum_sub_distrib,sum_add_distrib] at heq simp_rw [← mul_sum] at heq simp only [sum_const,card_univ,nsmul_eq_mul] at heq
Substitute the calculated aggregate sums and conclude D + Q + 3d = N + 3l automation
Substituting hinter (3d), hoff (6l), hD (D), and hQ (Q) into the identity produces 2D = 2N - 6d + 6l - 2Q. Linear integer arithmetic (linarith) rearranges and divides by 2 to conclude D + Q + 3d = N + 3l.
rw [hinter,hoff,hD,hQ] at heq linarith
filter_mem_eq_inter- Filtering a finite set by membership in another set yields their intersection.
sum_comm- Swapping the order of two finite summations preserves the sum.
sum_filter- Summing an indicator function over a finite set equals the cardinality of the filtered subset.
sum_congr- Two sums over the same finite set are equal if their summands are equal at every element.
wild_fixed_support_incidence_sum- The total intersection cardinality over all indexed sets equals the sum over elements of S of the number of sets containing each element.
offDiag_inter- The off-diagonal of an intersection of sets is the intersection of their off-diagonals.
mem_offDiag- An element belongs to the off-diagonal of a set if and only if both coordinates belong to the set and are distinct.
offDiag_card- The cardinality of the off-diagonal of a set S is |S| * |S| - |S|.
wild_three_set_disjoint_indicator- For any two 3-element sets S and T, twice the disjointness indicator equals 2 - 2|S ∩ T| + |(S ∩ T).offDiag| - 2 * [S = T].
sum_sub_distrib- The sum of differences distributes into the difference of sums.
sum_add_distrib- The sum of additions distributes into the sum of sums.
mul_sum- Multiplication by a constant distributes over a finite sum.
sum_const- The sum of a constant value over a finite set equals the cardinality of the set multiplied by the constant.
card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type.
nsmul_eq_mul- Natural scalar multiplication n • a equals the product of n and a.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 3000000theorem wild_fixed_support_incidence_sum {ι κ : Type*} [Fintype ι] [DecidableEq κ] (T : ι → Finset κ) (S : Finset κ) : (∑ i : ι, ((S ∩ T i).card : ℤ)) = ∑ a ∈ S, ((univ.filter fun i => a ∈ T i).card : ℤ) := by classical have hcard (i : ι) : ((S ∩ T i).card : ℤ) = ∑ a ∈ S, if a ∈ T i then (1 : ℤ) else 0 := by simp [← sum_filter,filter_mem_eq_inter] simp_rw [hcard] rw [sum_comm] apply sum_congr rfl intro a ha simp [← sum_filter]theorem wild_three_uniform_fixed_support_disjoint_count {ι κ : Type*} [Fintype ι] [DecidableEq κ] (T : ι → Finset κ) (S : Finset κ) (d l : ℕ) (hsize : ∀ i, (T i).card = 3) (hS : S.card = 3) (hvertex : ∀ a ∈ S, (univ.filter fun i => a ∈ T i).card = d) (hpair : ∀ a ∈ S, ∀ b ∈ S, a ≠ b → (univ.filter fun i => a ∈ T i ∧ b ∈ T i).card = l) : ((univ.filter fun i => Disjoint S (T i)).card : ℤ) + ((univ.filter fun i => S = T i).card : ℤ) + 3*(d : ℤ) = (Fintype.card ι : ℤ) + 3*(l : ℤ) := by classical have hinter : (∑ i : ι, ((S ∩ T i).card : ℤ)) = 3*(d : ℤ) := by rw [wild_fixed_support_incidence_sum] calc _ = ∑ a ∈ S, (d : ℤ) := by apply sum_congr rfl intro a ha rw [hvertex a ha] _ = _ := by simp [hS] have hoff : (∑ i : ι, ((S ∩ T i).offDiag.card : ℤ)) = 6*(l : ℤ) := by simp_rw [offDiag_inter] rw [wild_fixed_support_incidence_sum] calc _ = ∑ z ∈ S.offDiag, (l : ℤ) := by apply sum_congr rfl intro z hz obtain ⟨ha,hb,hne⟩ := mem_offDiag.mp hz have hf : (univ.filter fun i => z ∈ (T i).offDiag) = (univ.filter fun i => z.1 ∈ T i ∧ z.2 ∈ T i) := by ext i simp [mem_offDiag,hne] rw [hf,hpair z.1 ha z.2 hb hne] _ = _ := by simp [offDiag_card,hS] have heq := sum_congr (s₁ := (univ : Finset ι)) rfl (fun i _ => wild_three_set_disjoint_indicator S (T i) hS (hsize i)) have hD : (∑ i : ι, if Disjoint S (T i) then (1 : ℤ) else 0) = ((univ.filter fun i => Disjoint S (T i)).card : ℤ) := by simp [← sum_filter] have hQ : (∑ i : ι, if S = T i then (1 : ℤ) else 0) = ((univ.filter fun i => S = T i).card : ℤ) := by simp [← sum_filter] simp only [sum_sub_distrib,sum_add_distrib] at heq simp_rw [← mul_sum] at heq simp only [sum_const,card_univ,nsmul_eq_mul] at heq rw [hinter,hoff,hD,hQ] at heq linarith