AFTD Auto-Formalizing Theoretical Domains

rectilinear_crossing_number_add_total_simplicial_depth_eq_choose_of_four

theoremverified

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

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

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

    lines 6–8

    uses rectilinear_crossing_number_eq_sum_powersetCard_four, total_simplicial_depth_eq_sum_powersetCard_four, Finset.sum_add_distrib

      rw [rectilinear_crossing_number_eq_sum_powersetCard_four,
          total_simplicial_depth_eq_sum_powersetCard_four,
          ← Finset.sum_add_distrib]
  2. 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.

    line 9

    uses Finset.sum_congr

      rw [Finset.sum_congr rfl h_four]
  3. 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.

    line 10

    uses Finset.card_powersetCard

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

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