rectilinear_crossing_number_add_total_simplicial_depth_eq_choose_of_four
If 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 4).
Statement
theorem rectilinear_crossing_number_add_total_simplicial_depth_eq_choose_of_four
(P : Finset (ℝ × ℝ))
(h_four : ∀ Q ∈ P.powersetCard 4, rectilinear_crossing_number Q + total_simplicial_depth Q = 1) :
rectilinear_crossing_number P + total_simplicial_depth P = Nat.choose P.card 4- Source
- arXiv:2610.38658 Lemma 20 -- Larger Crossing Families
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- rectilinear_crossing_number_eq_sum_powersetCard_fourThe rectilinear crossing number 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_eq_sum_powersetCard_fourThe 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…
- 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…
- rectilinear_crossing_numberFor a finite set P of points in the plane ℝ × ℝ, the rectilinear crossing number of P is the number of unordered pairs of disjoint…
Read back from the Lean
Let $P$ be a finite set of points in the plane $\mathbb{R}^2$. Suppose that for every 4-element subset $Q \subseteq P$, the sum of the rectilinear crossing number of $Q$ and the total simplicial depth of $Q$ equals $1$. Then the sum of the rectilinear crossing number of $P$ and the total simplicial depth of $P$ equals $\binom{|P|}{4}$.
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 proof double-counts the quantity cr(P) + TSD(P) over all 4-element subsets of P. Because both the rectilinear crossing number and total simplicial depth decompose as sums over 4-element subsets, their total is the sum of cr(Q) + TSD(Q) over all Q ⊆ P with |Q| = 4. Since each such subset contributes 1 by hypothesis, the total is simply the count of 4-element subsets, which is (|P| choose 4).
The sum cr(P) + TSD(P) is expressed as a single sum of (cr(Q) + TSD(Q)) over all 4-element subsets Q of P.
By `rectilinear_crossing_number_eq_sum_powersetCard_four` and `total_simplicial_depth_eq_sum_powersetCard_four`, both the crossing number and total simplicial depth of P decompose as sums over all 4-element subsets Q ⊆ P. Applying `Finset.sum_add_distrib` in reverse merges these two separate sums into a single summation of cr(Q) + TSD(Q) over all Q in the collection of 4-element subsets of P.
uses
rectilinear_crossing_number_eq_sum_powersetCard_four,total_simplicial_depth_eq_sum_powersetCard_four,Finset.sum_add_distribrw [rectilinear_crossing_number_eq_sum_powersetCard_four, total_simplicial_depth_eq_sum_powersetCard_four, ← Finset.sum_add_distrib]The sum reduces to summing the constant 1 over all 4-element subsets of P.
By congruence of sums (`Finset.sum_congr`), each summand cr(Q) + TSD(Q) is replaced by 1 using the hypothesis `h_four`, which asserts that cr(Q) + TSD(Q) = 1 for every 4-element subset Q of P.
uses
Finset.sum_congrrw [Finset.sum_congr rfl h_four]
Summing 1 over all 4-element subsets of P yields (|P| choose 4).
Summing 1 over a finite set equals its cardinality. By `Finset.card_powersetCard`, the number of 4-element subsets of P is (|P| choose 4), which matches the right-hand side and completes the proof.
uses
Finset.card_powersetCardsimp [Finset.card_powersetCard]
rectilinear_crossing_number_eq_sum_powersetCard_four- The rectilinear crossing number of a finite planar point set P equals the sum of the rectilinear crossing numbers of all its 4-element subsets.
total_simplicial_depth_eq_sum_powersetCard_four- The total simplicial depth of a finite planar point set P equals the sum of the total simplicial depths of all its 4-element subsets.
Finset.sum_add_distrib- The sum of a sum of two functions over a finite set equals the sum of the individual sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_congr- Two sums over finite sets are equal if their index sets are equal and their summands are equal on every element of the index set.
Finset.card_powersetCard- The number of n-element subsets of a finite set s is (|s| choose n).
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.
/-- Double-counting reduction: if every 4-element subset contributes 1 to cr + TSD, the total sum is (|P| choose 4). -/theorem rectilinear_crossing_number_add_total_simplicial_depth_eq_choose_of_four (P : Finset (ℝ × ℝ)) (h_four : ∀ Q ∈ P.powersetCard 4, rectilinear_crossing_number Q + total_simplicial_depth Q = 1) : rectilinear_crossing_number P + total_simplicial_depth P = Nat.choose P.card 4 := by rw [rectilinear_crossing_number_eq_sum_powersetCard_four, total_simplicial_depth_eq_sum_powersetCard_four, ← Finset.sum_add_distrib] rw [Finset.sum_congr rfl h_four] simp [Finset.card_powersetCard]