AFTD Auto-Formalizing Theoretical Domains

straight_line_bisection_of_side_card_bounds

theoremverified

A straight line whose strictly positive and strictly negative sides each contain at most half of each color admits a consistent two-agent allocation giving each agent exactly half of each color. Points on the line fill the separate color quotas.

Statement

theorem straight_line_bisection_of_side_card_bounds
    (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (ℓ : StraightLine)
    (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card)
    (hpos : ∀ j, ((P.filter fun p => c p = j).filter fun p => 0 < ℓ.cut p).card ≤
      (P.filter fun p => c p = j).card / 2)
    (hneg : ∀ j, ((P.filter fun p => c p = j).filter fun p => ℓ.cut p < 0).card ≤
      (P.filter fun p => c p = j).card / 2) :
    ∃ α : (ℝ × ℝ) → 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
  • finite_color_cut_signingFor a finite two-colored set and a real-valued cut, if each color has even size and neither strict sign side exceeds half of that color,…
  • 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 α…
Used by 1
  • straight_line_bisection_of_cut_zeroIf every point lies on a given straight line and each of two colors has even size, that one line admits a consistent allocation bisecting…

The proof, explained

The proof applies the combinatorial lemma finite_color_cut_signing to the affine functional defining the line ℓ. Because each color class has even cardinality and at most half of its points strictly on either side of ℓ, this lemma yields a boolean signing that agrees with the geometric sides of ℓ and bisects each color class into two equal halves. We then define the allocation α by sending points signed true to agent 0 and points signed false to agent 1, which directly fulfills both the cut-consistency condition and the equal-allocation requirement for each agent and color.

  1. There exists a boolean signing s respecting the strictly positive and negative sides of ℓ that bisects both color classes, and we use it to define an allocation α.

    Applying finite_color_cut_signing to the functional p ↦ ℓ.cut p yields a signing s : ℝ × ℝ → Bool such that s(p) = true whenever ℓ.cut p > 0, s(p) = false whenever ℓ.cut p < 0, and each color class is split into two halves of size |P_j| / 2 according to whether s(p) is true or false. We define the allocation α by assigning agent 0 when s(p) is true and agent 1 when s(p) is false.

    lines 15–18

    uses finite_color_cut_signing

      classical
      obtain ⟨s, hs, hcard⟩ := finite_color_cut_signing P c (fun p => ℓ.cut p)
        heven hpos hneg
      let α := fun p => if s p then (0 : Fin 2) else 1
  2. The allocation α and signing function satisfy the sign consistency requirement for the line ℓ.

    We supply α and the constant signing (l, p) ↦ s p as witnesses for the cut-consistency definition. For any line l in the singleton {ℓ}, l must equal ℓ (by mem_singleton.mp), so the sign consistency condition holds directly from the guarantee hs on s.

    lines 19–23

    uses mem_singleton.mp

      refine ⟨α, ⟨fun _ p => s p, ?_, ?_⟩, ?_⟩
      · intro l hl p hp
        have : l = ℓ := mem_singleton.mp hl
        subst l
        exact hs p hp
  3. The allocation α is determined by the signs assigned by the lines.

    If two points p, q ∈ P have the same sign on all lines in {ℓ}, evaluating this condition on ℓ itself (using mem_singleton_self) gives s(p) = s(q). Because α is defined solely as a function of s, it immediately follows that α(p) = α(q).

    lines 24–26

    uses mem_singleton_self

      · intro p hp q hq heq
        have h := heq ℓ (mem_singleton_self _)
        simp only [α, h]
  4. Agent 0 receives exactly half of each color class.

    We consider agent i = 0 for an arbitrary color j. The set of points of color j allocated to agent 0 consists of points where α(p) = 0 and c(p) = j. Since α(p) = 0 if and only if s(p) = true, this set coincides with {p ∈ P | c(p) = j ∧ s(p) = true}. By the first part of the cardinality guarantee on s, this set has cardinality |P_j| / 2.

    lines 27–35

    uses and_left_comm, and_assoc, and_comm

      · intro i j
        fin_cases i
        · change (P.filter fun p => α p = 0 ∧ c p = j).card = _
          have hfilter : (P.filter fun p => α p = 0 ∧ c p = j) =
              (P.filter fun p => c p = j).filter (fun p => s p = true) := by
            ext p
            cases h : s p <;> simp [α, h, and_left_comm, and_assoc, and_comm]
          rw [hfilter]
          exact (hcard j).1
  5. Agent 1 receives exactly half of each color class.

    For agent i = 1, points of color j allocated to agent 1 are those with α(p) = 1 and c(p) = j. Since α(p) = 1 if and only if s(p) = false, this set coincides with {p ∈ P | c(p) = j ∧ s(p) = false}, which has cardinality |P_j| / 2 by the second part of the cardinality guarantee on s.

    lines 36–42

    uses and_left_comm, and_assoc, and_comm

        · change (P.filter fun p => α p = 1 ∧ c p = j).card = _
          have hfilter : (P.filter fun p => α p = 1 ∧ c p = j) =
              (P.filter fun p => c p = j).filter (fun p => s p = false) := by
            ext p
            cases h : s p <;> simp [α, h, and_left_comm, and_assoc, and_comm]
          rw [hfilter]
          exact (hcard j).2
finite_color_cut_signing
Given a finite set with a 2-coloring where each color class has even cardinality, and a real functional with at most half of each color class strictly positive and at most half strictly negative, there exists a boolean signing agreeing with the non-zero signs that splits each color class into two equal halves.
mem_singleton.mp
If an element belongs to a singleton set {a}, then it is equal to a.
mem_singleton_self
Every element a belongs to the singleton set {a}.
and_left_comm
Conjunction satisfies the left commutativity law: a ∧ b ∧ c ↔ b ∧ a ∧ c.
and_assoc
Conjunction is associative: (a ∧ b) ∧ c ↔ a ∧ b ∧ c.
and_comm
Conjunction is commutative: a ∧ b ↔ b ∧ a.

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_side_card_bounds    (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (ℓ : StraightLine)    (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card)    (hpos : ∀ j, ((P.filter fun p => c p = j).filter fun p => 0 < ℓ.cut p).card ≤      (P.filter fun p => c p = j).card / 2)    (hneg : ∀ j, ((P.filter fun p => c p = j).filter fun p => ℓ.cut p < 0).card ≤      (P.filter fun p => c p = j).card / 2) :    ∃ α : (ℝ × ℝ) → 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  classical  obtain ⟨s, hs, hcard⟩ := finite_color_cut_signing P c (fun p => ℓ.cut p)    heven hpos hneg  let α := fun p => if s p then (0 : Fin 2) else 1  refine ⟨α, ⟨fun _ p => s p, ?_, ?_⟩, ?_⟩  · intro l hl p hp    have : l = ℓ := mem_singleton.mp hl    subst l    exact hs p hp  · intro p hp q hq heq    have h := heq ℓ (mem_singleton_self _)    simp only [α, h]  · intro i j    fin_cases i    · change (P.filter fun p => α p = 0 ∧ c p = j).card = _      have hfilter : (P.filter fun p => α p = 0 ∧ c p = j) =          (P.filter fun p => c p = j).filter (fun p => s p = true) := by        ext p        cases h : s p <;> simp [α, h, and_left_comm, and_assoc, and_comm]      rw [hfilter]      exact (hcard j).1    · change (P.filter fun p => α p = 1 ∧ c p = j).card = _      have hfilter : (P.filter fun p => α p = 1 ∧ c p = j) =          (P.filter fun p => c p = j).filter (fun p => s p = false) := by        ext p        cases h : s p <;> simp [α, h, and_left_comm, and_assoc, and_comm]      rw [hfilter]      exact (hcard j).2
See it in the graphDiscuss this resultChallenge it