AFTD Auto-Formalizing Theoretical Domains

wild_three_uniform_fixed_support_disjoint_count

theoremverified

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

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.

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

    lines 10–13

    uses sum_filter, filter_mem_eq_inter

      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]
  2. 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.

    lines 14–18

    uses sum_comm, sum_congr, sum_filter

      simp_rw [hcard]
      rw [sum_comm]
      apply sum_congr rfl
      intro a ha
      simp [← sum_filter]
  3. Assume classical logic for decidability

    Enable classical logic so that all propositions, in particular set equality and disjointness, are decidable.

    line 30

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

    lines 31–38

    uses wild_fixed_support_incidence_sum, sum_congr

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

    lines 39–52

    uses offDiag_inter, wild_fixed_support_incidence_sum, sum_congr, mem_offDiag, offDiag_card

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

    lines 53–54

    uses sum_congr, wild_three_set_disjoint_indicator

      have heq := sum_congr (s₁ := (univ : Finset ι)) rfl
        (fun i _ => wild_three_set_disjoint_indicator S (T i) hS (hsize i))
  7. 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.

    lines 55–58

    uses sum_filter

      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]
  8. 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 ι.

    lines 59–61

    uses sum_sub_distrib, sum_add_distrib, mul_sum, sum_const, card_univ, nsmul_eq_mul

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

    lines 62–63

      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

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