finite_color_cut_signing
For 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, boundary points can be signed to give exactly half of each color to each Boolean sign.
Statement
theorem finite_color_cut_signing {X : Type*} [DecidableEq X] (P : Finset X) (c : X → Fin 2) (f : X → ℝ) (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card) (hpos : ∀ j, ((P.filter fun p => c p = j).filter fun p => 0 < f p).card ≤ (P.filter fun p => c p = j).card / 2) (hneg : ∀ j, ((P.filter fun p => c p = j).filter fun p => f p < 0).card ≤ (P.filter fun p => c p = j).card / 2) : ∃ s : X → Bool, (∀ p ∈ P, (0 < f p → s p = true) ∧ (f p < 0 → s p = false)) ∧ ∀ j, ((P.filter fun p => c p = j).filter fun p => s p = true).card = (P.filter fun p => c p = j).card / 2 ∧ ((P.filter fun p => c p = j).filter fun p => s p = false).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- Used by 1
- 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…
The proof, explained
For each of the two color classes, the strictly positive points number at most half the class, while the non-negative points number at least half because the strictly negative points also do not exceed half and the total class size is even. An intermediate set selection lemma (`exists_subsuperset_card_eq`) guarantees a subset U of size exactly half the color class that contains all strictly positive points and only non-negative points. Choosing such a subset U(j) for each color and setting s(p) = true if and only if p ∈ U(c(p)) yields a signing that agrees with the strict signs of f and divides each color class into two equal halves.
We work classically and define R(j) to be the subset of points in P of color j.
Using classical logic, we introduce the shorthand R(j) = {p ∈ P | c(p) = j} for each color j ∈ Fin 2.
classical let R := fun j => P.filter fun p => c p = j
For each color j, there exists a subset U of size |R(j)| / 2 containing all strictly positive points of R(j) and contained in the non-negative points of R(j).
Fix a color j. Any point with 0 < f(p) also satisfies 0 ≤ f(p) by `le_of_lt`, giving the inclusion of positive points into non-negative points. By `card_filter_add_card_filter_not` and `not_lt`, the negative and non-negative points partition R(j), so their sizes sum to |R(j)|. Since |R(j)| is even (`Nat.mod_eq_zero_of_dvd`) and strictly negative points number at most |R(j)| / 2 (by hypothesis `hneg`), the non-negative points must number at least |R(j)| / 2. Since strictly positive points number at most |R(j)| / 2 (by hypothesis `hpos`), `exists_subsuperset_card_eq` guarantees an intermediate set U of cardinality exactly |R(j)| / 2.
uses
le_of_lt,not_lt,card_filter_add_card_filter_not,Nat.mod_eq_zero_of_dvd,exists_subsuperset_card_eqhave hchoose : ∀ j, ∃ U : Finset X, (R j).filter (fun p => 0 < f p) ⊆ U ∧ U ⊆ (R j).filter (fun p => 0 ≤ f p) ∧ U.card = (R j).card / 2 := by intro j have hsub : (R j).filter (fun p => 0 < f p) ⊆ (R j).filter (fun p => 0 ≤ f p) := by intro p hp exact mem_filter.mpr ⟨(mem_filter.mp hp).1, le_of_lt (mem_filter.mp hp).2⟩ have hsum : ((R j).filter fun p => f p < 0).card + ((R j).filter fun p => 0 ≤ f p).card = (R j).card := by simpa only [not_lt] using card_filter_add_card_filter_not (s := R j) (fun p => f p < 0) have hdiv := Nat.mod_eq_zero_of_dvd (heven j) have hnegj := hneg j change ((R j).filter fun p => f p < 0).card ≤ (R j).card / 2 at hnegj obtain ⟨U, hU, hU', hcard⟩ := exists_subsuperset_card_eq hsub (hpos j) (show (R j).card / 2 ≤ ((R j).filter fun p => 0 ≤ f p).card by omega) exact ⟨U, hU, hU', hcard⟩
We choose a balanced set U(j) for each color, define the signing function s, and reduce the theorem to two obligations.
Using the axiom of choice (`choose`), we extract a family U(j) for each color. We define s(p) to be true when p ∈ U(c(p)) and false otherwise. We note that any point in U(j) belongs to P and has color j (`hmem`), since U(j) ⊆ R(j). Providing s as the witness reduces the goal to checking that s respects strict signs on P and that both sign fibers have size |R(j)| / 2 for each color.
choose U hUpos hUnonneg hUcard using hchoose let s := fun p => decide (p ∈ U (c p)) have hmem : ∀ j p, p ∈ U j → p ∈ P ∧ c p = j := by intro j p hp exact mem_filter.mp (mem_filter.mp (hUnonneg j hp)).1 refine ⟨s, ?_, ?_⟩
The signing function s assigns true to strictly positive points and false to strictly negative points in P.
Let p ∈ P. If 0 < f(p), then p belongs to the strictly positive points of color c(p), which are contained in U(c(p)) by construction, so s(p) = true. If f(p) < 0, then p cannot belong to U(c(p)), because all points in U(c(p)) satisfy 0 ≤ f(p), contradicting f(p) < 0. Thus p ∉ U(c(p)) and s(p) = false.
· intro p hp constructor · intro hf have hpU : p ∈ U (c p) := hUpos (c p) (by simp [R, hp, hf]) simp [s, hpU] · intro hf have hpU : p ∉ U (c p) := by intro hu have := (mem_filter.mp (hUnonneg (c p) hu)).2 linarith simp [s, hpU]
For each color j, the points in R(j) where s is true form precisely the set U(j).
We prove {p ∈ R(j) | s(p) = true} = U(j) by double inclusion. If p ∈ R(j) and s(p) = true, then c(p) = j, so s(p) = true means p ∈ U(j). Conversely, if p ∈ U(j), then p ∈ P and c(p) = j by `hmem`, so p ∈ R(j) and s(p) = true by definition.
· intro j have htrue : (R j).filter (fun p => s p = true) = U j := by ext p constructor · intro hp obtain ⟨hpR, hs⟩ := mem_filter.mp hp have hc := (mem_filter.mp hpR).2 simpa [s, hc] using hs · intro hp obtain ⟨hpP, hpc⟩ := hmem j p hp simp [R, s, hpP, hpc, hp]
For each color j, exactly |R(j)| / 2 points are signed true and |R(j)| / 2 points are signed false.
By `card_filter_add_card_filter_not`, the true and false points in R(j) sum to |R(j)|. The true points are U(j), which has size |R(j)| / 2. Since |R(j)| is even, (|R(j)| / 2) * 2 = |R(j)| (`Nat.div_mul_cancel`), which means |R(j)| / 2 + |R(j)| / 2 = |R(j)|. Canceling |R(j)| / 2 using `Nat.add_left_cancel` shows that the false points also number |R(j)| / 2.
uses
card_filter_add_card_filter_not,Nat.div_mul_cancel,Nat.add_left_cancelhave hsum := card_filter_add_card_filter_not (s := R j) (fun p => s p = true) have hfalse : ((R j).filter fun p => ¬ s p = true) = ((R j).filter fun p => s p = false) := by ext p simp rw [htrue, hfalse, hUcard j] at hsum have hdouble : (R j).card / 2 + (R j).card / 2 = (R j).card := by have h := Nat.div_mul_cancel (heven j) change (R j).card / 2 * 2 = (R j).card at h omega exact ⟨by change ((R j).filter _).card = _; rw [htrue, hUcard], by change ((R j).filter _).card = _ exact Nat.add_left_cancel (hsum.trans hdouble.symm)⟩
le_of_lt- If a < b in a preorder, then a ≤ b.
not_lt- In a linear order, ¬(a < b) is equivalent to b ≤ a.
card_filter_add_card_filter_not- For any finite set s and predicate p, the number of elements satisfying p plus the number of elements satisfying ¬p equals |s|.
Nat.mod_eq_zero_of_dvd- If m divides n, then n % m = 0.
exists_subsuperset_card_eq- If s ⊆ t are finite sets and n satisfies |s| ≤ n ≤ |t|, then there exists a set u with s ⊆ u ⊆ t and |u| = n.
Nat.div_mul_cancel- If n divides m, then (m / n) * n = m.
Nat.add_left_cancel- If n + m = n + k, then m = k.
- On paper, the balanced subsets U(0) and U(1) are chosen individually for the two colors; in Lean, this simultaneous selection is handled via the `choose` tactic over the finite type `Fin 2`.
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.
open Finsettheorem finite_color_cut_signing {X : Type*} [DecidableEq X] (P : Finset X) (c : X → Fin 2) (f : X → ℝ) (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card) (hpos : ∀ j, ((P.filter fun p => c p = j).filter fun p => 0 < f p).card ≤ (P.filter fun p => c p = j).card / 2) (hneg : ∀ j, ((P.filter fun p => c p = j).filter fun p => f p < 0).card ≤ (P.filter fun p => c p = j).card / 2) : ∃ s : X → Bool, (∀ p ∈ P, (0 < f p → s p = true) ∧ (f p < 0 → s p = false)) ∧ ∀ j, ((P.filter fun p => c p = j).filter fun p => s p = true).card = (P.filter fun p => c p = j).card / 2 ∧ ((P.filter fun p => c p = j).filter fun p => s p = false).card = (P.filter fun p => c p = j).card / 2 := by classical let R := fun j => P.filter fun p => c p = j have hchoose : ∀ j, ∃ U : Finset X, (R j).filter (fun p => 0 < f p) ⊆ U ∧ U ⊆ (R j).filter (fun p => 0 ≤ f p) ∧ U.card = (R j).card / 2 := by intro j have hsub : (R j).filter (fun p => 0 < f p) ⊆ (R j).filter (fun p => 0 ≤ f p) := by intro p hp exact mem_filter.mpr ⟨(mem_filter.mp hp).1, le_of_lt (mem_filter.mp hp).2⟩ have hsum : ((R j).filter fun p => f p < 0).card + ((R j).filter fun p => 0 ≤ f p).card = (R j).card := by simpa only [not_lt] using card_filter_add_card_filter_not (s := R j) (fun p => f p < 0) have hdiv := Nat.mod_eq_zero_of_dvd (heven j) have hnegj := hneg j change ((R j).filter fun p => f p < 0).card ≤ (R j).card / 2 at hnegj obtain ⟨U, hU, hU', hcard⟩ := exists_subsuperset_card_eq hsub (hpos j) (show (R j).card / 2 ≤ ((R j).filter fun p => 0 ≤ f p).card by omega) exact ⟨U, hU, hU', hcard⟩ choose U hUpos hUnonneg hUcard using hchoose let s := fun p => decide (p ∈ U (c p)) have hmem : ∀ j p, p ∈ U j → p ∈ P ∧ c p = j := by intro j p hp exact mem_filter.mp (mem_filter.mp (hUnonneg j hp)).1 refine ⟨s, ?_, ?_⟩ · intro p hp constructor · intro hf have hpU : p ∈ U (c p) := hUpos (c p) (by simp [R, hp, hf]) simp [s, hpU] · intro hf have hpU : p ∉ U (c p) := by intro hu have := (mem_filter.mp (hUnonneg (c p) hu)).2 linarith simp [s, hpU] · intro j have htrue : (R j).filter (fun p => s p = true) = U j := by ext p constructor · intro hp obtain ⟨hpR, hs⟩ := mem_filter.mp hp have hc := (mem_filter.mp hpR).2 simpa [s, hc] using hs · intro hp obtain ⟨hpP, hpc⟩ := hmem j p hp simp [R, s, hpP, hpc, hp] have hsum := card_filter_add_card_filter_not (s := R j) (fun p => s p = true) have hfalse : ((R j).filter fun p => ¬ s p = true) = ((R j).filter fun p => s p = false) := by ext p simp rw [htrue, hfalse, hUcard j] at hsum have hdouble : (R j).card / 2 + (R j).card / 2 = (R j).card := by have h := Nat.div_mul_cancel (heven j) change (R j).card / 2 * 2 = (R j).card at h omega exact ⟨by change ((R j).filter _).card = _; rw [htrue, hUcard], by change ((R j).filter _).card = _ exact Nat.add_left_cancel (hsum.trans hdouble.symm)⟩