AFTD Auto-Formalizing Theoretical Domains

planar_necklace_three_agents_cuts_ge_two

theoremverified

Let P be a finite set of points in ℝ × ℝ colored with two colors c : (ℝ × ℝ) → Fin 2, L a finite set of straight lines, and α an allocation function from ℝ × ℝ to Fin 3. If each of the three agents receives exactly 1 point of color 0 and 1 point of color 1 from P, and α is consistent with L on P, then L contains at least 2 straight lines.

Statement

theorem planar_necklace_three_agents_cuts_ge_two
    (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (L : Finset StraightLine)
    (α : (ℝ × ℝ) → Fin 3)
    (h_fair : ∀ i : Fin 3,
      (P.filter (fun p => α p = i ∧ c p = 0)).card = 1 ∧
      (P.filter (fun p => α p = i ∧ c p = 1)).card = 1)
    (h_cons : is_straight_line_cut_consistent P L α) :
    2 ≤ L.card
Source
arXiv:2610.27956 Proposition 1 (Splitting Planar Necklaces with Few Straight Cuts)
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

Let $P$ be a finite set of points in $\mathbb{R}^2$, $c : \mathbb{R}^2 \to \{0, 1\}$ a 2-coloring of points, $L$ a finite set of straight lines (affine maps $\mathbb{R}^2 \to \mathbb{R}$ with non-zero linear part), and $\alpha : \mathbb{R}^2 \to \{0, 1, 2\}$ an assignment of points to 3 agents. Assume: 1. (h_fair) For each agent $i \in \{0, 1, 2\}$, there is exactly one point $p \in P$ with $\alpha(p) = i$ and $c(p) = 0$, and exactly one point $p \in P$ with $\alpha(p) = i$ and $c(p) = 1$. 2. (h_cons) The assignment $\alpha$ is consistent with the cuts $L$, meaning there exists a sign choice function $s : \text{StraightLine} \to \mathbb{R}^2 \to \text{Bool}$ such that: - For all $\ell \in L$ and all $p \in P$, if $\ell.\text{cut}(p) > 0$ then $s(\ell, p) = \text{true}$, and if $\ell.\text{cut}(p) < 0$ then $s(\ell, p) = \text{false}$. - For all $p, q \in P$, if $s(\ell, p) = s(\ell, q)$ for all $\ell \in L$, then $\alpha(p) = \alpha(q)$. Then $L$ contains at least 2 lines ($2 \le |L|$).

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 theorem is proved by contradiction: assuming fewer than two straight lines suffice, the set of lines L must have cardinality 0 or 1. If |L| = 0, there are no lines to separate points, forcing all points to receive the same agent label, which contradicts fairness because at least two distinct agents must receive points. If |L| = 1, a single straight line can partition points into at most two sides, which cannot consistently divide points among three distinct agents who all receive non-empty allocations.

  1. Every agent i ∈ {0, 1, 2} receives at least one point of P under the allocation α.

    Under classical logic, we deduce surjectivity of α onto Fin 3. For any agent i, the fairness hypothesis implies that the set of points in P assigned to i with color 0 has cardinality 1. By `Finset.card_eq_one.1`, this set is a singleton {p}, and by `Finset.mem_filter`, p ∈ P with α(p) = i.

    lines 10–16

    uses Finset.card_eq_one.1, Finset.mem_filter

      classical
      have h_surj : ∀ i : Fin 3, ∃ p ∈ P, α p = i := by
        intro i
        obtain ⟨p, hp⟩ := Finset.card_eq_one.1 (h_fair i).1
        have hmem : p ∈ P.filter (fun p => α p = i ∧ c p = 0) := by rw [hp]; simp
        rw [Finset.mem_filter] at hmem
        exact ⟨p, hmem.1, hmem.2.1⟩
  2. Assuming for contradiction that |L| < 2, the number of lines |L| must be either 0 or 1.

    We assume for contradiction that ¬ (2 ≤ |L|). Linear arithmetic on ℕ (via `omega`) gives |L| ≤ 1. We then split into two cases using `Nat.le_one_iff_eq_zero_or_eq_one.1`: |L| = 0 or |L| = 1.

    lines 17–19

    uses Nat.le_one_iff_eq_zero_or_eq_one.1

      by_contra h
      have hc : L.card ≤ 1 := by omega
      rcases Nat.le_one_iff_eq_zero_or_eq_one.1 hc with h0 | h1
  3. The case |L| = 0 is impossible because an empty set of cuts forces all points to receive the same agent allocation.

    If |L| = 0, then L = ∅ by `Finset.card_eq_zero.1`. The consistency condition for L = ∅ implies that any two points in P agreeing on all lines in L must have the same agent allocation; since L is empty, this condition holds vacuously for all pairs of points. Taking points p₀ and p₁ allocated to agents 0 and 1 (from surjectivity), consistency forces α(p₀) = α(p₁), which gives 0 = 1 in Fin 3, an immediate contradiction.

    lines 20–28

    uses Finset.card_eq_zero.1

      · have hL : L = ∅ := Finset.card_eq_zero.1 h0
        rw [hL] at h_cons
        obtain ⟨s, hs_cut, hs_α⟩ := h_cons
        obtain ⟨p₀, hp₀, hα₀⟩ := h_surj 0
        obtain ⟨p₁, hp₁, hα₁⟩ := h_surj 1
        have heq : (0 : Fin 3) = 1 := by
          rw [← hα₀, ← hα₁]
          exact hs_α p₀ hp₀ p₁ hp₁ (by intro ℓ hℓ; simp at hℓ)
        exact absurd heq (by decide)
  4. The case |L| = 1 is impossible because a single straight line cannot consistently partition points among three active agents.

    If |L| = 1, then L = {ℓ} for some straight line ℓ by `Finset.card_eq_one.1`. The lemma `not_is_straight_line_cut_consistent_singleton_of_three_agents` establishes that a single straight line cannot provide a consistent allocation when every agent receives at least one point, contradicting cut consistency.

    lines 29–30

    uses Finset.card_eq_one.1, not_is_straight_line_cut_consistent_singleton_of_three_agents

      · obtain ⟨ℓ, rfl⟩ := Finset.card_eq_one.1 h1
        exact not_is_straight_line_cut_consistent_singleton_of_three_agents P ℓ α h_surj h_cons
Finset.card_eq_one.1
A finite set has cardinality 1 if and only if it is a singleton set {a} for some element a.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the filtering predicate.
Nat.le_one_iff_eq_zero_or_eq_one.1
A natural number is at most 1 if and only if it is 0 or 1.
Finset.card_eq_zero.1
A finite set has cardinality 0 if and only if it is the empty set.
not_is_straight_line_cut_consistent_singleton_of_three_agents
A cut-consistent allocation among three agents on a set of points where each agent receives at least one point cannot be formed by a singleton set of straight lines.

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

/-- Tightness of Conjecture 2: any fair allocation among three agents receiving at least one point of each color requires at least two straight lines. -/theorem planar_necklace_three_agents_cuts_ge_two    (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (L : Finset StraightLine)    (α : (ℝ × ℝ) → Fin 3)    (h_fair : ∀ i : Fin 3,      (P.filter (fun p => α p = i ∧ c p = 0)).card = 1 ∧      (P.filter (fun p => α p = i ∧ c p = 1)).card = 1)    (h_cons : is_straight_line_cut_consistent P L α) :    2 ≤ L.card := by  classical  have h_surj : ∀ i : Fin 3, ∃ p ∈ P, α p = i := by    intro i    obtain ⟨p, hp⟩ := Finset.card_eq_one.1 (h_fair i).1    have hmem : p ∈ P.filter (fun p => α p = i ∧ c p = 0) := by rw [hp]; simp    rw [Finset.mem_filter] at hmem    exact ⟨p, hmem.1, hmem.2.1⟩  by_contra h  have hc : L.card ≤ 1 := by omega  rcases Nat.le_one_iff_eq_zero_or_eq_one.1 hc with h0 | h1  · have hL : L = ∅ := Finset.card_eq_zero.1 h0    rw [hL] at h_cons    obtain ⟨s, hs_cut, hs_α⟩ := h_cons    obtain ⟨p₀, hp₀, hα₀⟩ := h_surj 0    obtain ⟨p₁, hp₁, hα₁⟩ := h_surj 1    have heq : (0 : Fin 3) = 1 := by      rw [← hα₀, ← hα₁]      exact hs_α p₀ hp₀ p₁ hp₁ (by intro ℓ hℓ; simp at hℓ)    exact absurd heq (by decide)  · obtain ⟨ℓ, rfl⟩ := Finset.card_eq_one.1 h1    exact not_is_straight_line_cut_consistent_singleton_of_three_agents P ℓ α h_surj h_cons
See it in the graphDiscuss this resultChallenge it