AFTD Auto-Formalizing Theoretical Domains

rectilinear_crossing_number_eq_sum_powersetCard_four

theoremverified

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

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.

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

    lines 13–16

    uses congr_arg, rectilinear_crossing_number_eq_sum_powersetCard_four_pred

      unfold rectilinear_crossing_number
      apply congr_arg Finset.card
      ext x
      simp [rectilinear_crossing_number_eq_sum_powersetCard_four_pred]
  2. 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.

    lines 23–37

    uses Finset.mem_powersetCard, Finset.biUnion_subset

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

    lines 38–51

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

    lines 59–74

    uses Finset.mem_powersetCard, Finset.mem_filter, Finset.mem_biUnion.mpr

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

    lines 75–88

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

    lines 95–103

    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_mem

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

    lines 104–109

    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_eq

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

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