AFTD Auto-Formalizing Theoretical Domains

condorcet_strict_half_separator_iff_integer_circulation

theoremverified

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
Used by 1

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.

  1. 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.

    lines 18–19

      classical
      constructor
  2. Given 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.

    lines 20–23

    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 hsep
  3. There 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$.

    line 24

    uses condorcet_integer_acyclic_separator_neighbor_mass

        obtain ⟨v,hv,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R d hd
  4. There 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.

    line 25

    uses condorcet_integer_circulation_of_neighbor_mass

        obtain ⟨f,hf,hrow,hcol⟩ := condorcet_integer_circulation_of_neighbor_mass m R v hHall
  5. The 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.

    lines 26–28

        refine ⟨f,hf,?_,?_⟩
        · intro a
          rw [hrow,hcol]
  6. 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$.

    lines 29–30

        · intro A hA
          simpa only [hrow] using hv A hA
  7. 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`.

    lines 31–32

    uses Nat.cast_nonneg

      · rintro ⟨f,_,_,hf⟩
        refine ⟨fun a => ((∑ b, f a b : ℕ) : ℝ),fun a => Nat.cast_nonneg _,?_⟩
  8. 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.

    lines 33–35

        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.

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 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
See it in the graphDiscuss this resultChallenge it