condorcet_strict_half_separator_iff_integer_circulation
For every finite directed relation, existence of nonnegative real weights putting every induced acyclic subset strictly below half their total is equivalent to existence of nonnegative integer edge multiplicities, zero off the relation and balanced at every vertex, whose outgoing vertex marginals put every induced acyclic subset strictly below half their total. This is a strict-half equivalence, not equality of unrestricted and circulation optima at arbitrary thresholds; it does not construct a separator on S3 relations.
Statement
theorem condorcet_strict_half_separator_iff_integer_circulation (m : ℕ) (R : Fin m → Fin m → Prop) : (∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) ↔ (∃ f : Fin m → Fin m → ℕ, (∀ a b, ¬ R a b → f a b = 0) ∧ (∀ a, ∑ b, f a b = ∑ b, f b a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, ∑ b, f a b) < ∑ a, ∑ b, f a b)
- Source
- IN-380, OP-19 campaign session 8, 2026-10-30. Self-contained helper for the strict-half acyclic-separation route. The general unrestricted one-child equality was refuted in IN-372; this work repairs only the strict-half existence reduction. Standard finite matching, rational density, and circulation weak duality are used. No new election bound or research novelty is claimed. See lean/AFTD/Scratch/In380Oct30/HalfThresholdDerivation.txt.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- condorcet_finite_strict_separator_integer_weightsFor any family C of subsets of a finite vertex set, if nonnegative real weights put every member of C strictly below half the total…
- condorcet_integer_acyclic_separator_neighbor_massIf a finite directed relation has a nonnegative integer strict-half separator of its induced acyclic sets, it has such a separator w for…
- condorcet_integer_circulation_of_neighbor_massFor any finite directed relation and natural-number vertex weights w, assume every vertex set S has weight at most its outgoing…
- Used by 1
- condorcet_strict_half_separator_excludes_cover_potentialLet a finite directed relation have a nonnegative real strict-half separator. For every positive number n of induced acyclic vertex…
The proof, explained
The theorem establishes equivalence between the existence of a real strict-half separator and an integer circulation on a finite directed relation. In the forward direction, real separator weights are first converted to integer weights, then modified to satisfy Hall's out-neighborhood condition while preserving the strict-half separation of acyclic subsets; network flow theory then constructs an integer circulation whose marginals equal these weights. In the reverse direction, the outgoing vertex marginals of an integer circulation are cast from natural numbers to real numbers, directly preserving nonnegativity and the strict-half separation.
The equivalence reduces to two implications: showing that real strict-half separator weights imply an integer circulation, and conversely that an integer circulation yields real separator weights.
We invoke classical logic (making arbitrary relations decidable) and split the logical equivalence into forward and reverse implications.
classical constructorGiven nonnegative real weights strictly separating acyclic subsets below half the total, there exist integer weights with the same separation property.
We assume nonnegative real weights $w$ separating acyclic subsets. Applying `condorcet_finite_strict_separator_integer_weights` with the condition that $A$ induces an acyclic relation produces integer weights $d : \mathrm{Fin}\,m \to \mathbb{N}$ satisfying the strict-half condition for all acyclic subsets.
uses
condorcet_finite_strict_separator_integer_weights· rintro ⟨w,hw,hsep⟩ obtain ⟨d,hd⟩ := condorcet_finite_strict_separator_integer_weights m (fun A => WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) w hw hsepThere exist integer weights that still strictly separate acyclic subsets and additionally satisfy Hall's marriage condition on out-neighborhoods.
Applying `condorcet_integer_acyclic_separator_neighbor_mass` to $d$ yields integer weights $v$ that continue to separate acyclic subsets below half the total, while satisfying $\sum_{a \in S} v(a) \le \sum_{b \in N(S)} v(b)$ for every subset $S$.
uses
condorcet_integer_acyclic_separator_neighbor_massobtain ⟨v,hv,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R d hdThere exists a nonnegative integer edge flow supported on $R$ whose row and column sums at each vertex equal $v$.
By `condorcet_integer_circulation_of_neighbor_mass`, Hall's neighborhood condition guarantees the existence of an edge flow $f$ supported on $R$ with $\sum_b f(a,b) = v(a)$ and $\sum_a f(a,b) = v(b)$ for every vertex.
uses
condorcet_integer_circulation_of_neighbor_massobtain ⟨f,hf,hrow,hcol⟩ := condorcet_integer_circulation_of_neighbor_mass m R v hHallThe flow $f$ is balanced at every vertex, forming an integer circulation.
We propose $f$ as the witness. At every vertex $a$, both the total outgoing flow $\sum_b f(a,b)$ and the total incoming flow $\sum_b f(b,a)$ equal $v(a)$, so they are equal.
refine ⟨f,hf,?_,?_⟩ · intro a rw [hrow,hcol]
The outgoing vertex marginals of $f$ strictly separate every induced acyclic subset below half the total flow.
For any acyclic subset $A$, since the outgoing sum $\sum_b f(a,b)$ is identical to $v(a)$, the strict-half inequality for $f$ reduces to that already established for $v$.
· intro A hA simpa only [hrow] using hv A hA
Conversely, given an integer circulation, its outgoing vertex marginals cast to real numbers define nonnegative real weights.
Given an integer circulation $f$, we set $w(a) = \sum_b f(a,b)$ embedded into $\mathbb{R}$. Nonnegativity follows from `Nat.cast_nonneg`.
uses
Nat.cast_nonneg· rintro ⟨f,_,_,hf⟩ refine ⟨fun a => ((∑ b, f a b : ℕ) : ℝ),fun a => Nat.cast_nonneg _,?_⟩The cast real weights strictly separate every induced acyclic subset below half the total weight.
Given an acyclic subset $A$, the circulation hypothesis gives the strict-half inequality $2 \sum_{a \in A} \sum_b f(a,b) < \sum_a \sum_b f(a,b)$ in $\mathbb{N}$. Casting this inequality from $\mathbb{N}$ to $\mathbb{R}$ completes the proof.
intro A hA dsimp only exact_mod_cast hf A hA
condorcet_finite_strict_separator_integer_weights- If a finite family of subsets is strictly separated below half the total weight by a nonnegative real vector, then it is also strictly separated below half the total weight by an integer vector.
condorcet_integer_acyclic_separator_neighbor_mass- Given integer weights strictly separating acyclic subsets below half the total weight, there exist integer weights preserving this separation that additionally satisfy Hall's marriage condition on out-neighborhoods.
condorcet_integer_circulation_of_neighbor_mass- If integer vertex weights satisfy Hall's marriage condition for out-neighborhoods of a directed relation, there exists a nonnegative integer circulation supported on the relation whose incoming and outgoing vertex sums equal those weights.
Nat.cast_nonneg- The canonical embedding of any natural number into an ordered semiring is nonnegative.
- The proof invokes `classical` at the start to supply decidability instances for the relation $R$, which are required by `condorcet_integer_acyclic_separator_neighbor_mass` and `condorcet_integer_circulation_of_neighbor_mass`.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_strict_half_separator_iff_integer_circulation (m : ℕ) (R : Fin m → Fin m → Prop) : (∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) ↔ (∃ f : Fin m → Fin m → ℕ, (∀ a b, ¬ R a b → f a b = 0) ∧ (∀ a, ∑ b, f a b = ∑ b, f b a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, ∑ b, f a b) < ∑ a, ∑ b, f a b) := by classical constructor · rintro ⟨w,hw,hsep⟩ obtain ⟨d,hd⟩ := condorcet_finite_strict_separator_integer_weights m (fun A => WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) w hw hsep obtain ⟨v,hv,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R d hd obtain ⟨f,hf,hrow,hcol⟩ := condorcet_integer_circulation_of_neighbor_mass m R v hHall refine ⟨f,hf,?_,?_⟩ · intro a rw [hrow,hcol] · intro A hA simpa only [hrow] using hv A hA · rintro ⟨f,_,_,hf⟩ refine ⟨fun a => ((∑ b, f a b : ℕ) : ℝ),fun a => Nat.cast_nonneg _,?_⟩ intro A hA dsimp only exact_mod_cast hf A hA