planar_necklace_three_agents_cuts_ge_two
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
- 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 α…
- not_is_straight_line_cut_consistent_singleton_of_three_agentsLet P be a finite set of points in ℝ², ℓ a straight line, and α : ℝ² → Fin 3 an allocation function. If every agent in Fin 3 receives at…
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.
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.
uses
Finset.card_eq_one.1,Finset.mem_filterclassical 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⟩
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.
uses
Nat.le_one_iff_eq_zero_or_eq_one.1by_contra h have hc : L.card ≤ 1 := by omega rcases Nat.le_one_iff_eq_zero_or_eq_one.1 hc with h0 | h1
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.
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)
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.
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.
- The impossibility of partitioning points consistently among three agents using only a single straight line is established in the external lemma `not_is_straight_line_cut_consistent_singleton_of_three_agents`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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