rectilinear_crossing_number_eq_sum_powersetCard_four
The 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 rectilinear crossing number of Q.
Statement
theorem rectilinear_crossing_number_eq_sum_powersetCard_four
(P : Finset (ℝ × ℝ)) :
rectilinear_crossing_number P =
∑ Q ∈ P.powersetCard 4, rectilinear_crossing_number Q- Source
- arXiv:2610.38658 Lemma 20 -- Larger Crossing Families
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- 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 every finite set of points $P \subseteq \mathbb{R}^2$, the rectilinear crossing number of $P$ is equal to the sum, over all 4-element subsets $Q \subseteq P$, of the rectilinear crossing number 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 rectilinear crossing number of a point set P counts the pairs of disjoint line segments between points of P that intersect. Every crossing pair involves exactly four distinct points, so taking the union of the two edges maps each crossing pair to a 4-element subset of P. Summing fiberwise over all 4-element subsets Q partitions the crossings of P into the crossings within each Q.
The rectilinear crossing number of P is the number of crossing pairs of edges in P.
Unfold the definition of the rectilinear crossing number and express it by filtering pairs of 2-element subsets of P that satisfy the crossing predicate.
uses
congr_arg,rectilinear_crossing_number_eq_sum_powersetCard_four_predunfold rectilinear_crossing_number apply congr_arg Finset.card ext x simp [rectilinear_crossing_number_eq_sum_powersetCard_four_pred]
The union of the vertices in any pair of edges in P is a subset of P.
Each edge in the pair has cardinality 2 and is contained in P, so the union of the two edges is a subset of P.
uses
Finset.mem_powersetCard,Finset.biUnion_subsetrw [Finset.mem_powersetCard] at hpair ⊢ rcases hpair with ⟨hpair_sub, hpair_card⟩ have h_edges : ∀ e ∈ pair, e.card = 2 := by intro e he have := hpair_sub he rw [Finset.mem_powersetCard] at this exact this.2 have h_edges_sub : ∀ e ∈ pair, e ⊆ P := by intro e he have := hpair_sub he rw [Finset.mem_powersetCard] at this exact this.1 constructor · rw [Finset.biUnion_subset] exact h_edges_sub
The union of vertices in a crossing pair of edges has cardinality 4.
Since the pair has size 2 and contains two distinct crossing edges, the pair consists exactly of these two edges. Because the crossing edges are disjoint and each has size 2, their union has 2 + 2 = 4 elements.
uses
Finset.insert_subset_iff,Finset.singleton_subset_iff,Finset.card_pair,Finset.eq_of_subset_of_card_le,Finset.biUnion_insert,Finset.singleton_biUnion,id_eq,Finset.card_union_of_disjoint· rcases h_cross with ⟨e₁, he₁, e₂, he₂, hne, hdisj, _⟩ have hpair_eq : pair = {e₁, e₂} := by have : {e₁, e₂} ⊆ pair := by rw [Finset.insert_subset_iff, Finset.singleton_subset_iff] exact ⟨he₁, he₂⟩ have hle : pair.card ≤ ({e₁, e₂} : Finset _).card := by rw [Finset.card_pair hne, hpair_card] exact (Finset.eq_of_subset_of_card_le this hle).symm rw [hpair_eq] rw [Finset.biUnion_insert, Finset.singleton_biUnion, id_eq, id_eq] rw [Finset.card_union_of_disjoint hdisj] have he1_card : e₁.card = 2 := h_edges e₁ he₁ have he2_card : e₂.card = 2 := h_edges e₂ he₂ rw [he1_card, he2_card]
The crossing pairs in P with union Q are contained in the crossing pairs of Q.
If a crossing pair of edges in P has union Q, each edge is a 2-element subset contained in Q, hence it is a crossing pair in Q.
uses
Finset.mem_powersetCard,Finset.mem_filter,Finset.mem_biUnion.mprrw [Finset.mem_powersetCard] at hQ ext pair rw [Finset.mem_filter, Finset.mem_filter, Finset.mem_filter] constructor · rintro ⟨⟨hpairP, hcross⟩, h_union⟩ refine ⟨?_, hcross⟩ rw [Finset.mem_powersetCard] at hpairP ⊢ refine ⟨?_, hpairP.2⟩ intro e he rw [Finset.mem_powersetCard] have heP := hpairP.1 he rw [Finset.mem_powersetCard] at heP refine ⟨?_, heP.2⟩ intro x hx rw [← h_union] exact Finset.mem_biUnion.mpr ⟨e, he, hx⟩
The crossing pairs in Q are contained in the fiber of crossing pairs in P with union Q.
Any crossing pair of edges in Q spans 4 points of Q, which must be all of Q since |Q| = 4. Since Q is a subset of P, these edges are also edges of P.
uses
Finset.mem_powersetCard,rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem,Finset.eq_of_subset_of_card_le· rintro ⟨hpairQ, hcross⟩ have h_union : pair.biUnion id = Q := by have h_mem := rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem hpairQ hcross rw [Finset.mem_powersetCard] at h_mem apply Finset.eq_of_subset_of_card_le · exact h_mem.1 · rw [h_mem.2, hQ.2] refine ⟨⟨?_, hcross⟩, h_union⟩ rw [Finset.mem_powersetCard] at hpairQ ⊢ refine ⟨?_, hpairQ.2⟩ intro e he have heQ := hpairQ.1 he rw [Finset.mem_powersetCard] at heQ ⊢ exact ⟨heQ.1.trans hQ.1, heQ.2⟩Taking the union of edges maps crossing pairs in P to 4-element subsets of P.
For any crossing pair of edges in P, their union is a 4-element subset of P by the previous lemma.
uses
rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card,Finset.mem_coe,Finset.mem_filter,rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_memrw [rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card] have hmaps : Set.MapsTo (fun pair : Finset (Finset (ℝ × ℝ)) => pair.biUnion id) ↑(((P.powersetCard 2).powersetCard 2).filter rectilinear_crossing_number_eq_sum_powersetCard_four_pred) ↑(P.powersetCard 4) := by intro pair hpair rw [Finset.mem_coe, Finset.mem_filter] at hpair rw [Finset.mem_coe] exact rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem hpair.1 hpair.2
The rectilinear crossing number of P is the sum over all 4-element subsets Q of P of the crossing number of Q.
We partition the crossing pairs in P according to their underlying 4-element subset via fiberwise summation, and identify each fiber with the crossing pairs of Q.
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_congr,rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card,rectilinear_crossing_number_eq_sum_powersetCard_four_fiber_eqrw [Finset.card_eq_sum_card_fiberwise hmaps] apply Finset.sum_congr rfl intro Q hQ rw [rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card] congr 1 exact rectilinear_crossing_number_eq_sum_powersetCard_four_fiber_eq P Q hQ
congr_arg- Equality of arguments implies equality of function values.
rectilinear_crossing_number_eq_sum_powersetCard_four_pred- The predicate that a pair of edges has disjoint edges with intersecting open segments.
Finset.mem_powersetCard- Membership in a powerset of fixed cardinality.
Finset.biUnion_subset- A union over a finite set is a subset if and only if each term is a subset.
Finset.insert_subset_iff- Inserting an element into a set is a subset if and only if the element and the set are subsets.
Finset.singleton_subset_iff- A singleton is a subset if and only if its element is in the set.
Finset.card_pair- A pair of distinct elements has cardinality 2.
Finset.eq_of_subset_of_card_le- A subset with at least the cardinality of the ambient finite set is equal to it.
Finset.biUnion_insert- The union of a family over an inserted element is the term union the remaining union.
Finset.singleton_biUnion- The union of a family over a singleton is that family member.
id_eq- The identity function applied to an element is that element.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.mem_filter- Membership in a filtered finite set.
Finset.mem_biUnion.mpr- An element is in a union over a family if it belongs to one of the family members.
rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem- A crossing pair of edges spans 4 points.
Finset.mem_coe- Coercion of membership from a Finset to a Set.
rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card- The crossing number of P is the cardinality of the filtered set of crossing edge pairs.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set is the sum of cardinalities of the fibers of any map.
Finset.sum_congr- Congruence rule for sums over identical domains with pointwise equal summands.
rectilinear_crossing_number_eq_sum_powersetCard_four_fiber_eq- The fiber of crossing pairs spanning Q is equal to the crossing pairs within Q.
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 Classicaldef rectilinear_crossing_number_eq_sum_powersetCard_four_pred (pair : Finset (Finset (ℝ × ℝ))) : Prop := ∃ e₁ ∈ pair, ∃ e₂ ∈ pair, e₁ ≠ e₂ ∧ Disjoint e₁ e₂ ∧ ∃ u₁ ∈ e₁, ∃ v₁ ∈ e₁, ∃ u₂ ∈ e₂, ∃ v₂ ∈ e₂, u₁ ≠ v₁ ∧ u₂ ≠ v₂ ∧ (openSegment ℝ u₁ v₁ ∩ openSegment ℝ u₂ v₂).Nonemptylemma rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card (P : Finset (ℝ × ℝ)) : rectilinear_crossing_number P = (((P.powersetCard 2).powersetCard 2).filter rectilinear_crossing_number_eq_sum_powersetCard_four_pred).card := by unfold rectilinear_crossing_number apply congr_arg Finset.card ext x simp [rectilinear_crossing_number_eq_sum_powersetCard_four_pred]lemma rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem {P : Finset (ℝ × ℝ)} {pair : Finset (Finset (ℝ × ℝ))} (hpair : pair ∈ (P.powersetCard 2).powersetCard 2) (h_cross : rectilinear_crossing_number_eq_sum_powersetCard_four_pred pair) : pair.biUnion id ∈ P.powersetCard 4 := by rw [Finset.mem_powersetCard] at hpair ⊢ rcases hpair with ⟨hpair_sub, hpair_card⟩ have h_edges : ∀ e ∈ pair, e.card = 2 := by intro e he have := hpair_sub he rw [Finset.mem_powersetCard] at this exact this.2 have h_edges_sub : ∀ e ∈ pair, e ⊆ P := by intro e he have := hpair_sub he rw [Finset.mem_powersetCard] at this exact this.1 constructor · rw [Finset.biUnion_subset] exact h_edges_sub · rcases h_cross with ⟨e₁, he₁, e₂, he₂, hne, hdisj, _⟩ have hpair_eq : pair = {e₁, e₂} := by have : {e₁, e₂} ⊆ pair := by rw [Finset.insert_subset_iff, Finset.singleton_subset_iff] exact ⟨he₁, he₂⟩ have hle : pair.card ≤ ({e₁, e₂} : Finset _).card := by rw [Finset.card_pair hne, hpair_card] exact (Finset.eq_of_subset_of_card_le this hle).symm rw [hpair_eq] rw [Finset.biUnion_insert, Finset.singleton_biUnion, id_eq, id_eq] rw [Finset.card_union_of_disjoint hdisj] have he1_card : e₁.card = 2 := h_edges e₁ he₁ have he2_card : e₂.card = 2 := h_edges e₂ he₂ rw [he1_card, he2_card]lemma rectilinear_crossing_number_eq_sum_powersetCard_four_fiber_eq (P : Finset (ℝ × ℝ)) (Q : Finset (ℝ × ℝ)) (hQ : Q ∈ P.powersetCard 4) : {pair ∈ ((P.powersetCard 2).powersetCard 2).filter rectilinear_crossing_number_eq_sum_powersetCard_four_pred | pair.biUnion id = Q} = ((Q.powersetCard 2).powersetCard 2).filter rectilinear_crossing_number_eq_sum_powersetCard_four_pred := by rw [Finset.mem_powersetCard] at hQ ext pair rw [Finset.mem_filter, Finset.mem_filter, Finset.mem_filter] constructor · rintro ⟨⟨hpairP, hcross⟩, h_union⟩ refine ⟨?_, hcross⟩ rw [Finset.mem_powersetCard] at hpairP ⊢ refine ⟨?_, hpairP.2⟩ intro e he rw [Finset.mem_powersetCard] have heP := hpairP.1 he rw [Finset.mem_powersetCard] at heP refine ⟨?_, heP.2⟩ intro x hx rw [← h_union] exact Finset.mem_biUnion.mpr ⟨e, he, hx⟩ · rintro ⟨hpairQ, hcross⟩ have h_union : pair.biUnion id = Q := by have h_mem := rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem hpairQ hcross rw [Finset.mem_powersetCard] at h_mem apply Finset.eq_of_subset_of_card_le · exact h_mem.1 · rw [h_mem.2, hQ.2] refine ⟨⟨?_, hcross⟩, h_union⟩ rw [Finset.mem_powersetCard] at hpairQ ⊢ refine ⟨?_, hpairQ.2⟩ intro e he have heQ := hpairQ.1 he rw [Finset.mem_powersetCard] at heQ ⊢ exact ⟨heQ.1.trans hQ.1, heQ.2⟩/-- The rectilinear crossing number of P decomposes as the sum of rectilinear crossing numbers over all 4-element subsets of P. -/theorem rectilinear_crossing_number_eq_sum_powersetCard_four (P : Finset (ℝ × ℝ)) : rectilinear_crossing_number P = ∑ Q ∈ P.powersetCard 4, rectilinear_crossing_number Q := by rw [rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card] have hmaps : Set.MapsTo (fun pair : Finset (Finset (ℝ × ℝ)) => pair.biUnion id) ↑(((P.powersetCard 2).powersetCard 2).filter rectilinear_crossing_number_eq_sum_powersetCard_four_pred) ↑(P.powersetCard 4) := by intro pair hpair rw [Finset.mem_coe, Finset.mem_filter] at hpair rw [Finset.mem_coe] exact rectilinear_crossing_number_eq_sum_powersetCard_four_biUnion_mem hpair.1 hpair.2 rw [Finset.card_eq_sum_card_fiberwise hmaps] apply Finset.sum_congr rfl intro Q hQ rw [rectilinear_crossing_number_eq_sum_powersetCard_four_eq_filter_card] congr 1 exact rectilinear_crossing_number_eq_sum_powersetCard_four_fiber_eq P Q hQ