AFTD Auto-Formalizing Theoretical Domains

straight_line_bisection_of_cut_zero

theoremverified

If every point lies on a given straight line and each of two colors has even size, that one line admits a consistent allocation bisecting both colors. This handles the collinear case using the permitted boundary signs.

Statement

theorem straight_line_bisection_of_cut_zero
    (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (ℓ : StraightLine)
    (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card)
    (hzero : ∀ p ∈ P, ℓ.cut p = 0) :
    ∃ α : (ℝ × ℝ) → Fin 2,
      is_straight_line_cut_consistent P {ℓ} α ∧
      ∀ i j : Fin 2,
        (P.filter fun p => α p = i ∧ c p = j).card =
          (P.filter fun p => c p = j).card / 2
Source
Boundary-assignment helper for planar_necklace_three_agents_three_cuts; arXiv:2610.27956 Proposition 9 and its bisection step. The definition permits arbitrary signs on zero cuts.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • straight_line_bisection_of_side_card_boundsA straight line whose strictly positive and strictly negative sides each contain at most half of each color admits a consistent two-agent…
  • StraightLineA straight line in the plane ℝ², given by an affine functional with nonzero linear part.
  • is_straight_line_cut_consistentGiven a finite set P of points in ℝ × ℝ, a finite set L of straight lines (StraightLine), a natural number k, and an allocation function α…

The proof, explained

The proof reduces the claim to straight_line_bisection_of_side_card_bounds, which guarantees a consistent bisecting allocation whenever each open half-plane bounded by the line contains at most half of the points of each color. Since every point of the set lies directly on the line ℓ, both the strictly positive and strictly negative half-planes contain no points at all. Their cardinalities are zero, which trivially satisfies the required upper bounds.

  1. It suffices to show that each color class has at most half its points in the positive half-plane (0 < ℓ.cut p) and at most half in the negative half-plane (ℓ.cut p < 0).

    By invoking the existing result straight_line_bisection_of_side_card_bounds with the even-cardinality hypothesis heven, the problem of finding a bisecting cut-consistent allocation reduces to verifying that both open half-planes contain at most half of the points of each color.

    line 12

    uses straight_line_bisection_of_side_card_bounds

      apply straight_line_bisection_of_side_card_bounds P c ℓ heven
  2. For each color j, the number of points of color j in the positive half-plane 0 < ℓ.cut p is at most half the total number of points of that color.

    Let j be a color. Since every point p in P lies on ℓ by assumption (ℓ.cut p = 0), any point in the filtered set would satisfy 0 < 0, which is impossible by irreflexivity of strict inequality (lt_irrefl). Thus, by filter_eq_empty_iff.mpr and mem_filter.mp, the set of points of color j in the positive half-plane is empty. Its cardinality is 0 by card_empty, which is at most half of the total size by Nat.zero_le.

    lines 13–20

    uses filter_eq_empty_iff.mpr, mem_filter.mp, lt_irrefl, card_empty, Nat.zero_le

      · intro j
        have hempty : ((P.filter fun p => c p = j).filter fun p => 0 < ℓ.cut p) = ∅ := by
          apply filter_eq_empty_iff.mpr
          intro p hp
          rw [hzero p (mem_filter.mp hp).1]
          exact lt_irrefl _
        rw [hempty, card_empty]
        exact Nat.zero_le _
  3. For each color j, the number of points of color j in the negative half-plane ℓ.cut p < 0 is at most half the total number of points of that color.

    Let j be a color. Symmetrically, any point in the negative half-plane would satisfy ℓ.cut p < 0, which contradicts ℓ.cut p = 0 via lt_irrefl. Therefore, by filter_eq_empty_iff.mpr and mem_filter.mp, the set of points of color j in the negative half-plane is empty. Its cardinality is 0 by card_empty, which is at most half the color size by Nat.zero_le.

    lines 21–28

    uses filter_eq_empty_iff.mpr, mem_filter.mp, lt_irrefl, card_empty, Nat.zero_le

      · intro j
        have hempty : ((P.filter fun p => c p = j).filter fun p => ℓ.cut p < 0) = ∅ := by
          apply filter_eq_empty_iff.mpr
          intro p hp
          rw [hzero p (mem_filter.mp hp).1]
          exact lt_irrefl _
        rw [hempty, card_empty]
        exact Nat.zero_le _
straight_line_bisection_of_side_card_bounds
If each open half-plane bounded by a line contains at most half of the points of each even-sized color class, then there exists a cut-consistent allocation that bisects both color classes.
filter_eq_empty_iff.mpr
If no element of a finite set satisfies a predicate, then the filtered set is empty.
mem_filter.mp
An element belongs to a filtered set only if it belongs to the original set and satisfies the predicate.
lt_irrefl
Strict inequality is irreflexive: no element is strictly less than itself.
card_empty
The cardinality of the empty finite set is zero.
Nat.zero_le
Zero is less than or equal to every natural number.

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 Finsettheorem straight_line_bisection_of_cut_zero    (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (ℓ : StraightLine)    (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card)    (hzero : ∀ p ∈ P, ℓ.cut p = 0) :    ∃ α : (ℝ × ℝ) → Fin 2,      is_straight_line_cut_consistent P {ℓ} α ∧      ∀ i j : Fin 2,        (P.filter fun p => α p = i ∧ c p = j).card =          (P.filter fun p => c p = j).card / 2 := by  apply straight_line_bisection_of_side_card_bounds P c ℓ heven  · intro j    have hempty : ((P.filter fun p => c p = j).filter fun p => 0 < ℓ.cut p) = ∅ := by      apply filter_eq_empty_iff.mpr      intro p hp      rw [hzero p (mem_filter.mp hp).1]      exact lt_irrefl _    rw [hempty, card_empty]    exact Nat.zero_le _  · intro j    have hempty : ((P.filter fun p => c p = j).filter fun p => ℓ.cut p < 0) = ∅ := by      apply filter_eq_empty_iff.mpr      intro p hp      rw [hzero p (mem_filter.mp hp).1]      exact lt_irrefl _    rw [hempty, card_empty]    exact Nat.zero_le _
See it in the graphDiscuss this resultChallenge it