AFTD Auto-Formalizing Theoretical Domains

rectilinear_crossing_number

def

For a finite set P of points in the plane ℝ × ℝ, the rectilinear crossing number of P is the number of unordered pairs of disjoint 2-element subsets {e₁, e₂} of P whose open line segments have nonempty intersection.

Statement

noncomputable def rectilinear_crossing_number (P : Finset (ℝ × ℝ)) : ℕ
Defined in
arXiv:2610.38658, Section 4
Verified
08 Nov 2026
Axioms
none listed
Used by 3

Read back from the Lean

Given a finite set of points $P \subset \mathbb{R} \times \mathbb{R}$, rectilinear_crossing_number P is the number of pairs $\{e_1, e_2\}$ of distinct 2-element subsets of $P$ (edges of the complete graph on $P$) such that: 1. $e_1$ and $e_2$ are disjoint (they share no vertices in $P$), and 2. there exist distinct vertices $u_1, v_1 \in e_1$ and distinct vertices $u_2, v_2 \in e_2$ such that the open line segment between $u_1$ and $v_1$ has a nonempty intersection with the open line segment between $u_2$ and $v_2$.

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

Lean source view module on GitHub

/-- Rectilinear crossing number of a finite point set P in ℝ × ℝ. -/
noncomputable def rectilinear_crossing_number (P : Finset (ℝ × ℝ)) : ℕ := open Classical in (((P.powersetCard 2).powersetCard 2).filter (fun (pair : Finset (Finset (ℝ × ℝ))) => ∃ 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₂).Nonempty)).card
See it in the graphDiscuss this resultChallenge it