AFTD Auto-Formalizing Theoretical Domains

total_simplicial_depth_eq_sum_powersetCard_four

theoremverified

The total simplicial depth of a finite point set P in the Euclidean plane is the sum over all 4-element subsets Q of P of the total simplicial depth of Q.

Statement

theorem total_simplicial_depth_eq_sum_powersetCard_four
    (P : Finset (ℝ × ℝ)) :
    total_simplicial_depth P =
      ∑ Q ∈ P.powersetCard 4, total_simplicial_depth Q
Source
arXiv:2610.38658 Lemma 20 -- Larger Crossing Families
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • total_simplicial_depthThe total simplicial depth TSD(P) of a finite point set P in the Euclidean plane is the sum over all points p in P of the simplicial depth…
  • simplicial_depthThe simplicial depth SD(p, P) of a point p with respect to a finite set P in the Euclidean plane is the number of 3-element subsets of P \…
Used by 1

Read back from the Lean

For any finite set of points $P \subseteq \mathbb{R}^2$, the total simplicial depth of $P$ is equal to the sum over all 4-element subsets $Q \subseteq P$ of the total simplicial depth of $Q$.

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

The proof, explained

The total simplicial depth of a finite point set P in the Euclidean plane is defined as the sum over all points p in P of their simplicial depth in P. For any point p, removing p provides a bijection between 4-element subsets Q containing p and 3-element subsets of P \ {p}, and the simplicial depth of p in Q is simply the indicator that p lies in the convex hull interior of Q \ {p}. Summing this indicator over all 4-subsets containing p reconstructs the simplicial depth of p in P. Finally, rewriting the sum of total depths of all 4-subsets by swapping the double summation over Q and p in Q yields the total simplicial depth of P.

  1. Removing p from a 4-element set Q leaves a 3-element set Q \ {p}.

    Because p is in Q and |Q| = 4, removing p from Q reduces the cardinality by 1, leaving exactly 3 elements.

    lines 7–8

    uses Finset.card_erase_of_mem

      have hcard : (Q.erase p).card = 3 := by
        rw [Finset.card_erase_of_mem hp, h4]
  2. For a 4-element set Q and p in Q, the simplicial depth of p in Q is 1 if p lies in the interior of the convex hull of Q \ {p}, and 0 otherwise. automation

    By definition, the simplicial depth of p in Q counts the 3-element subsets of Q \ {p} whose convex hull contains p in its interior. Since |Q \ {p}| = 3, the only 3-element subset is Q \ {p} itself. Filtering this singleton set yields {Q \ {p}} if p is in the interior of the convex hull and the empty set otherwise, whose cardinalities are 1 and 0 respectively.

    lines 9–13

    uses Finset.powersetCard_self, Finset.filter_singleton

      unfold simplicial_depth
      rw [← hcard, Finset.powersetCard_self, Finset.filter_singleton]
      split_ifs with h
      · simp
      · simp
  3. The simplicial depth of p in P can be written as an indicator sum over all 3-element subsets of P \ {p}.

    Unfolding the definition of simplicial depth gives the cardinality of the filtered collection of 3-element subsets of P \ {p}. Converting this cardinality into a sum of 1s over the filtered collection, and then rewriting the filter as an indicator function, expresses the depth as a sum of indicators over all 3-subsets of P \ {p}.

    lines 19–20

    uses Finset.card_filter, Finset.sum_filter

      rw [simplicial_depth, Finset.card_filter]
      rw [← Finset.sum_filter]
  4. The mapping Q ↦ Q \ {p} sends 4-element subsets of P containing p to 3-element subsets of P \ {p}.

    To equate the sum over 4-element subsets containing p with the sum over 3-element subsets of P \ {p}, we set up a bijection via Finset.sum_bij. For any Q ⊆ P with |Q| = 4 and p ∈ Q, the erased set Q \ {p} is a subset of P \ {p} and has cardinality 4 - 1 = 3.

    lines 21–27

    uses Finset.sum_bij, Finset.mem_filter, Finset.mem_powersetCard, Finset.erase_subset_erase, Finset.card_erase_of_mem

      refine Finset.sum_bij (fun Q _ => Q.erase p) ?_ ?_ ?_ ?_
      · intro Q hQ
        rw [Finset.mem_filter] at hQ
        obtain ⟨hQ4, hpQ⟩ := hQ
        rw [Finset.mem_powersetCard] at hQ4 ⊢
        obtain ⟨hsub, hcard⟩ := hQ4
        exact ⟨Finset.erase_subset_erase p hsub, by rw [Finset.card_erase_of_mem hpQ, hcard]⟩
  5. The mapping Q ↦ Q \ {p} is injective on sets containing p.

    If Q₁ \ {p} = Q₂ \ {p} and p belongs to both Q₁ and Q₂, reinserting p into both sets recovers Q₁ = Q₂.

    lines 28–30

    uses Finset.mem_filter, Finset.insert_erase

      · intro Q1 hQ1 Q2 hQ2 heq
        rw [Finset.mem_filter] at hQ1 hQ2
        rw [← Finset.insert_erase hQ1.2, ← Finset.insert_erase hQ2.2, heq]
  6. The mapping Q ↦ Q \ {p} is surjective onto the 3-element subsets of P \ {p}.

    Given any 3-element subset T of P \ {p}, the point p does not belong to T. The set Q = insert p T is a subset of P containing p, has cardinality 3 + 1 = 4, and satisfies Q \ {p} = T.

    lines 31–40

    uses Finset.mem_powersetCard, Finset.subset_erase.mp, Finset.mem_filter, Finset.insert_subset, Finset.Subset.trans, Finset.erase_subset, Finset.mem_insert_self, Finset.card_insert_of_notMem, Finset.erase_insert

      · intro T hT
        rw [Finset.mem_powersetCard] at hT
        obtain ⟨hTsub, hTcard⟩ := hT
        have hpT : p ∉ T := (Finset.subset_erase.mp hTsub).2
        refine ⟨insert p T, ?_, ?_⟩
        · rw [Finset.mem_filter, Finset.mem_powersetCard]
          refine ⟨⟨Finset.insert_subset hp (Finset.Subset.trans hTsub (Finset.erase_subset p P)),
            ?_⟩, Finset.mem_insert_self p T⟩
          rw [Finset.card_insert_of_notMem hpT, hTcard]
        · exact Finset.erase_insert hpT
  7. The summands agree under the bijection, so the sum over 4-subsets containing p equals the simplicial depth of p in P.

    For each 4-element subset Q containing p, total_simplicial_depth_eq_sum_powersetCard_four_sd_eq_indicator equates its simplicial depth to the indicator that p lies in the interior of the convex hull of Q \ {p}. Since the bijection preserves summands, the two sums are equal.

    lines 41–45

    uses Finset.mem_filter, Finset.mem_powersetCard, total_simplicial_depth_eq_sum_powersetCard_four_sd_eq_indicator

      · intro Q hQ
        rw [Finset.mem_filter] at hQ
        obtain ⟨hQ4, hpQ⟩ := hQ
        rw [Finset.mem_powersetCard] at hQ4
        exact total_simplicial_depth_eq_sum_powersetCard_four_sd_eq_indicator p Q hpQ hQ4.2
  8. Summing an indicator-weighted function over P restricts to a sum over the subset Q.

    Rewriting the indicator sum as a sum over the filtered set {x ∈ P | x ∈ Q} produces the intersection P ∩ Q. Since Q ⊆ P, this intersection is simply Q.

    lines 50–51

    uses Finset.sum_filter, Finset.filter_mem_eq_inter, Finset.inter_eq_right.mpr

      rw [← Finset.sum_filter, Finset.filter_mem_eq_inter]
      rw [Finset.inter_eq_right.mpr h]
  9. The double sum of simplicial depths over 4-subsets Q and points p in Q equals the double sum over p in P and 4-subsets containing p.

    Using total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem, each inner sum over p in Q is extended to a sum over all p in P weighted by the indicator that p is in Q. Swapping the order of summation with Finset.sum_comm yields the desired double sum.

    lines 56–62

    uses Finset.mem_powersetCard, total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem, Finset.sum_congr, Finset.sum_comm

      have h1 : ∀ Q ∈ P.powersetCard 4, ∑ p ∈ Q, simplicial_depth p Q =
          ∑ p ∈ P, (if p ∈ Q then simplicial_depth p Q else 0) := by
        intro Q hQ
        rw [Finset.mem_powersetCard] at hQ
        exact (total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem P Q hQ.1
          (fun p => simplicial_depth p Q)).symm
      rw [Finset.sum_congr rfl h1, Finset.sum_comm]
  10. Unfolding total simplicial depth reduces the theorem to evaluating the swapped double sum.

    Unfolding total_simplicial_depth on both sides of the theorem and applying total_simplicial_depth_eq_sum_powersetCard_four_swap converts the sum of total depths over all 4-element subsets into a double sum over p in P and 4-element subsets Q containing p.

    lines 69–70

    uses total_simplicial_depth_eq_sum_powersetCard_four_swap

      unfold total_simplicial_depth
      rw [total_simplicial_depth_eq_sum_powersetCard_four_swap]
  11. Evaluating the inner sum for each point p in P completes the proof of the theorem.

    For each point p in P, total_simplicial_depth_eq_sum_powersetCard_four_sum_erase shows that the inner sum over 4-subsets containing p evaluates to the simplicial depth of p in P. Summing over all p in P completes the proof.

    lines 71–72

    uses Finset.sum_congr, total_simplicial_depth_eq_sum_powersetCard_four_sum_erase

      exact Finset.sum_congr rfl
        (fun p hp => (total_simplicial_depth_eq_sum_powersetCard_four_sum_erase p P hp).symm)
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1.
Finset.powersetCard_self
The only subset of a finite set with size equal to the set's cardinality is the set itself.
Finset.filter_singleton
Filtering a singleton set by a predicate yields the singleton if the element satisfies the predicate, and the empty set otherwise.
Finset.card_filter
The size of a filtered subset equals the sum over the original set of the indicator of the filtering predicate.
Finset.sum_filter
Summing a function over elements satisfying a predicate equals summing the function multiplied by the predicate's indicator over the whole set.
Finset.sum_bij
If a map between two finite sets is a bijection and preserves summands, then the sums of the functions over the respective sets are equal.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_powersetCard
A set is an element of the k-subsets of a set if and only if it is a subset and has cardinality k.
Finset.erase_subset_erase
If one set is a subset of another, removing an element from both preserves the subset inclusion.
Finset.insert_erase
Re-inserting an element into a set from which it was removed recovers the original set, provided the element was originally in the set.
Finset.subset_erase.mp
If a set is a subset of another set with an element removed, it is a subset of the original set and does not contain that element.
Finset.insert_subset
Inserting an element into a subset of a set produces another subset, provided the element belongs to the ambient set.
Finset.Subset.trans
The subset relation on finite sets is transitive.
Finset.erase_subset
Removing an element from a set produces a subset of the original set.
Finset.mem_insert_self
An element always belongs to the set obtained by inserting that element.
Finset.card_insert_of_notMem
Inserting an element not already present into a finite set increases its cardinality by 1.
Finset.erase_insert
Removing an element immediately after inserting it returns the original set, provided the element was not originally in the set.
total_simplicial_depth_eq_sum_powersetCard_four_sd_eq_indicator
For any 4-element set Q and point p in Q, the simplicial depth of p in Q is 1 if p lies in the interior of the convex hull of the other 3 points, and 0 otherwise.
Finset.filter_mem_eq_inter
Filtering a finite set by membership in another set yields their intersection.
Finset.inter_eq_right.mpr
If Q is a subset of P, their intersection is Q.
total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem
Summing an indicator-weighted function over a superset equals summing the function directly over the subset.
Finset.sum_congr
Two sums over finite sets are equal if the index sets are equal and the summands agree on all elements.
Finset.sum_comm
The order of summation in a finite double sum can be interchanged.
total_simplicial_depth_eq_sum_powersetCard_four_swap
The double sum over 4-element subsets Q of P and points p in Q equals the double sum over p in P and 4-element subsets Q containing p.
total_simplicial_depth_eq_sum_powersetCard_four_sum_erase
For any point p in P, summing the simplicial depth of p in Q over all 4-element subsets Q containing p recovers the simplicial depth of p in P.

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 scoped Classicallemma total_simplicial_depth_eq_sum_powersetCard_four_sd_eq_indicator    (p : ℝ × ℝ) (Q : Finset (ℝ × ℝ)) (hp : p ∈ Q) (h4 : Q.card = 4) :    simplicial_depth p Q =      if p ∈ interior (convexHull ℝ (↑(Q.erase p) : Set (ℝ × ℝ))) then 1 else 0 := by  have hcard : (Q.erase p).card = 3 := by    rw [Finset.card_erase_of_mem hp, h4]  unfold simplicial_depth  rw [← hcard, Finset.powersetCard_self, Finset.filter_singleton]  split_ifs with h  · simp  · simplemma total_simplicial_depth_eq_sum_powersetCard_four_sum_erase    (p : ℝ × ℝ) (P : Finset (ℝ × ℝ)) (hp : p ∈ P) :    ∑ Q ∈ P.powersetCard 4, (if p ∈ Q then simplicial_depth p Q else 0) =      simplicial_depth p P := by  rw [simplicial_depth, Finset.card_filter]  rw [← Finset.sum_filter]  refine Finset.sum_bij (fun Q _ => Q.erase p) ?_ ?_ ?_ ?_  · intro Q hQ    rw [Finset.mem_filter] at hQ    obtain ⟨hQ4, hpQ⟩ := hQ    rw [Finset.mem_powersetCard] at hQ4 ⊢    obtain ⟨hsub, hcard⟩ := hQ4    exact ⟨Finset.erase_subset_erase p hsub, by rw [Finset.card_erase_of_mem hpQ, hcard]⟩  · intro Q1 hQ1 Q2 hQ2 heq    rw [Finset.mem_filter] at hQ1 hQ2    rw [← Finset.insert_erase hQ1.2, ← Finset.insert_erase hQ2.2, heq]  · intro T hT    rw [Finset.mem_powersetCard] at hT    obtain ⟨hTsub, hTcard⟩ := hT    have hpT : p ∉ T := (Finset.subset_erase.mp hTsub).2    refine ⟨insert p T, ?_, ?_⟩    · rw [Finset.mem_filter, Finset.mem_powersetCard]      refine ⟨⟨Finset.insert_subset hp (Finset.Subset.trans hTsub (Finset.erase_subset p P)),        ?_⟩, Finset.mem_insert_self p T⟩      rw [Finset.card_insert_of_notMem hpT, hTcard]    · exact Finset.erase_insert hpT  · intro Q hQ    rw [Finset.mem_filter] at hQ    obtain ⟨hQ4, hpQ⟩ := hQ    rw [Finset.mem_powersetCard] at hQ4    exact total_simplicial_depth_eq_sum_powersetCard_four_sd_eq_indicator p Q hpQ hQ4.2lemma total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem    (P Q : Finset (ℝ × ℝ)) (h : Q ⊆ P) (f : ℝ × ℝ → ℕ) :    ∑ x ∈ P, (if x ∈ Q then f x else 0) = ∑ x ∈ Q, f x := by  rw [← Finset.sum_filter, Finset.filter_mem_eq_inter]  rw [Finset.inter_eq_right.mpr h]lemma total_simplicial_depth_eq_sum_powersetCard_four_swap (P : Finset (ℝ × ℝ)) :    ∑ Q ∈ P.powersetCard 4, ∑ p ∈ Q, simplicial_depth p Q =      ∑ p ∈ P, ∑ Q ∈ P.powersetCard 4, (if p ∈ Q then simplicial_depth p Q else 0) := by  have h1 : ∀ Q ∈ P.powersetCard 4, ∑ p ∈ Q, simplicial_depth p Q =      ∑ p ∈ P, (if p ∈ Q then simplicial_depth p Q else 0) := by    intro Q hQ    rw [Finset.mem_powersetCard] at hQ    exact (total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem P Q hQ.1      (fun p => simplicial_depth p Q)).symm  rw [Finset.sum_congr rfl h1, Finset.sum_comm]/-- The total simplicial depth of P decomposes as the sum of total simplicial depths over all 4-element subsets of P. -/theorem total_simplicial_depth_eq_sum_powersetCard_four    (P : Finset (ℝ × ℝ)) :    total_simplicial_depth P =      ∑ Q ∈ P.powersetCard 4, total_simplicial_depth Q := by  unfold total_simplicial_depth  rw [total_simplicial_depth_eq_sum_powersetCard_four_swap]  exact Finset.sum_congr rfl    (fun p hp => (total_simplicial_depth_eq_sum_powersetCard_four_sum_erase p P hp).symm)
See it in the graphDiscuss this resultChallenge it