total_simplicial_depth_eq_sum_powersetCard_four
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
- rectilinear_crossing_number_add_total_simplicial_depth_eq_choose_of_fourIf every 4-element subset Q of a finite point set P in the Euclidean plane satisfies cr(Q) + TSD(Q) = 1, then cr(P) + TSD(P) = (|P| choose…
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.
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.
uses
Finset.card_erase_of_memhave hcard : (Q.erase p).card = 3 := by rw [Finset.card_erase_of_mem hp, h4]
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.
uses
Finset.powersetCard_self,Finset.filter_singletonunfold simplicial_depth rw [← hcard, Finset.powersetCard_self, Finset.filter_singleton] split_ifs with h · simp · simp
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}.
uses
Finset.card_filter,Finset.sum_filterrw [simplicial_depth, Finset.card_filter] rw [← Finset.sum_filter]
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.
uses
Finset.sum_bij,Finset.mem_filter,Finset.mem_powersetCard,Finset.erase_subset_erase,Finset.card_erase_of_memrefine 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]⟩
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₂.
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]
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.
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
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.
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
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.
uses
Finset.sum_filter,Finset.filter_mem_eq_inter,Finset.inter_eq_right.mprrw [← Finset.sum_filter, Finset.filter_mem_eq_inter] rw [Finset.inter_eq_right.mpr h]
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.
uses
Finset.mem_powersetCard,total_simplicial_depth_eq_sum_powersetCard_four_sum_ite_mem,Finset.sum_congr,Finset.sum_commhave 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]
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.
uses
total_simplicial_depth_eq_sum_powersetCard_four_swapunfold total_simplicial_depth rw [total_simplicial_depth_eq_sum_powersetCard_four_swap]
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.
uses
Finset.sum_congr,total_simplicial_depth_eq_sum_powersetCard_four_sum_eraseexact 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.
- The overall proof is structured into four helper lemmas: characterizing the simplicial depth in a 4-point set as an indicator function, establishing a bijection between 4-subsets containing a point p and 3-subsets of P \ {p}, restricting sums via indicator functions, and exchanging double summations.
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 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)