AFTD Auto-Formalizing Theoretical Domains

condorcet_strict_half_separator_acyclic_cover_closed_walk

theoremverified

If a finite relation has a nonnegative real strict-half acyclic separator, then every positive finite family of induced acyclic sets admits a nonempty closed directed walk whose total membership count in the family, doubled, is strictly less than walk length times family size. Vertices may repeat. No S3 assumption is used.

Statement

theorem condorcet_strict_half_separator_acyclic_cover_closed_walk
    (m n : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop)
    (U : Fin n → Finset (Fin m))
    (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val))
    (hsep : ∃ 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) :
    ∃ l : ℕ, 0 < l ∧ ∃ v : ℕ → Fin m,
      v l = v 0 ∧ (∀ i < l, R (v i) (v (i+1))) ∧
      2 * (∑ i ∈ range l, (univ.filter fun j => v i ∈ U j).card) < l*n
Source
IN-380, OP-19 campaign session8, 2026-10-30. Supporting reduction from the proved strict-half circulation bridge. Scratch ClosedWalk.lean passed trusted-axiom checking. Standard finite matching and orbit averaging; no research novelty or new election bound is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

The proof uses a vertex-cloning technique combined with Hall's marriage theorem and cycle decomposition of permutations. First, the real strict-half separator is discretized to integer weights satisfying Hall's condition on out-neighborhoods, yielding a permutation e on a cloned vertex set V whose steps follow edges of the relation R. Summing the strict separator inequality across the family of acyclic sets shows that the average cost c(x) = 2*z(x.1) - n across all cloned vertices is strictly negative. By permutation cycle decomposition, e must have a cycle with strictly negative total cost, and projecting this cycle back to the original graph gives the desired closed directed walk.

  1. There exist integer weights w satisfying both the strict-half acyclic separator condition and Hall's neighborhood condition, yielding a permutation e on the cloned vertices that follows directed edges of R.

    We unpack the given nonnegative real strict-half separator w₀. By condorcet_finite_strict_separator_integer_weights, there exist integer weights w₁ satisfying the same strict-half property for all acyclic induced subgraphs. Applying condorcet_integer_acyclic_separator_neighbor_mass, we obtain integer weights w that maintain the strict-half property for acyclic sets while satisfying Hall's condition that any set's total weight is bounded by that of its out-neighborhood. Then condorcet_integer_neighbor_mass_clone_permutation produces a permutation e of the cloned vertex set V = Σ a, Fin (w a) such that for every clone x, R x.1 (e x).1 holds.

    lines 17–22

    uses condorcet_finite_strict_separator_integer_weights, condorcet_integer_acyclic_separator_neighbor_mass, condorcet_integer_neighbor_mass_clone_permutation

      classical
      obtain ⟨w₀,hw₀,hsep₀⟩ := hsep
      obtain ⟨w₁,hw₁⟩ := 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 ⟨w,hw,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R w₁ hw₁
      obtain ⟨e,he⟩ := condorcet_integer_neighbor_mass_clone_permutation m R w hHall
  2. Define the cloned vertex type V, the family membership counts z, and the vertex cost function c.

    We define V as the type of pairs (a, k) where a is an original vertex and k < w(a), effectively duplicating each vertex a by its integer weight w(a). For each vertex a, z(a) is defined as the number of acyclic sets U_j containing a. Each cloned vertex x in V is assigned cost c(x) = 2*z(x.1) - n.

    lines 23–25

      let V := Σ a : Fin m, Fin (w a)
      let z : Fin m → ℝ := fun a => ((univ.filter fun j => a ∈ U j).card : ℝ)
      let c : V → ℝ := fun x => 2*z x.1 - n
  3. The sum over j of the doubled weights of U_j is strictly less than the total weight summed n times: ∑ j, 2 * ∑ a ∈ U j, w a < ∑ j, ∑ a, w a.

    By hypothesis, each set U_j induces an acyclic subgraph under R. Since w is a strict-half separator, 2 * ∑ a ∈ U_j, w a < ∑ a, w a holds for each j. Since n > 0, the family is nonempty (witnessed by index 0). Summing these strict inequalities over all j in Fin n using sum_lt_sum yields a strict inequality between the sums.

    lines 26–32

    uses sum_lt_sum, mem_univ

      have hstrict : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) <
          ∑ _j : Fin n, ∑ a, (w a : ℝ) := by
        apply sum_lt_sum
        · intro j hj
          exact_mod_cast (hw (U j) (hU j)).le
        · refine ⟨⟨0,hn⟩,mem_univ _,?_⟩
          exact_mod_cast hw (U ⟨0,hn⟩) (hU ⟨0,hn⟩)
  4. The weighted sum of membership counts satisfies ∑ a, w a * (2 * z a) < n * ∑ a, w a.

    We interchange the order of summation. Each sum over U_j is rewritten via Fintype.sum_ite_mem using an indicator function. Commuting the sums with sum_comm and factoring out w(a), the inner sum over j counts the number of sets U_j containing a, which is by definition z(a). Substituting this equality into the previous step and simplifying the constant outer sum over Fin n yields ∑ a, w a * (2 * z a) < n * ∑ a, w a.

    lines 33–46

    uses sum_congr, Fintype.sum_ite_mem, mul_sum, sum_comm, sum_filter, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul

      have hswap : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) =
          ∑ a, (w a : ℝ) * (2*z a) := by
        have hconvert : (∑ j : Fin n, ∑ a ∈ U j, (w a : ℝ)) =
            ∑ j : Fin n, ∑ a : Fin m, if a ∈ U j then (w a : ℝ) else 0 := by
          apply sum_congr rfl
          intro j hj
          exact (Fintype.sum_ite_mem (U j) (fun a => (w a : ℝ))).symm
        rw [← mul_sum,hconvert,sum_comm,mul_sum]
        apply sum_congr rfl
        intro a ha
        simp [z,← sum_filter]
        ring
      rw [hswap] at hstrict
      simp only [sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul] at hstrict
  5. The total cost over all cloned vertices is strictly negative: ∑ x ∈ V, c x < 0.

    Using Fintype.sum_sigma, the sum over V splits into an outer sum over vertices a and an inner sum over the w(a) copies of a. Since c(x) = 2*z(x.1) - n depends only on the original vertex, summing over the fiber multiplies the cost by w(a). Distributing and regrouping shows ∑ x ∈ V, c x = ∑ a, w a * (2 * z a) - n * ∑ a, w a. Since the first term is strictly smaller than the second, linear arithmetic concludes that the total sum is strictly negative.

    lines 47–55

    uses Fintype.sum_sigma, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul, mul_sub, sum_sub_distrib, sum_mul

      have hc : (∑ x : V, c x) < 0 := by
        have heq : (∑ x : V, c x) =
            (∑ a, (w a : ℝ) * (2*z a)) - (n : ℝ) * ∑ a, (w a : ℝ) := by
          rw [Fintype.sum_sigma]
          simp only [c,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul,mul_sub]
          rw [sum_sub_distrib,← sum_mul]
          ring
        rw [heq]
        linarith
  6. There exists a cycle of the permutation e of positive length l starting at some x ∈ V with strictly negative total cost: (e^l) x = x and ∑ i ∈ range l, c ((e^i) x) < 0.

    By condorcet_permutation_negative_closed_walk, whenever a cost function on a finite domain has a strictly negative sum, any permutation on that domain must contain a cycle whose orbit has strictly negative total cost.

    line 56

    uses condorcet_permutation_negative_closed_walk

      obtain ⟨l,hl,x,hclose,hneg⟩ := condorcet_permutation_negative_closed_walk e c hc
  7. The vertex projection of the cycle v(i) = ((e^i) x).1 forms a closed walk of length l > 0 with v(l) = v(0).

    We define the walk v : ℕ → Fin m by projecting each cloned vertex (e^i) x to its original vertex in Fin m. Since (e^l) x = x and (e^0) x = x, projecting with Sigma.fst gives v(l) = v(0).

    lines 57–59

    uses pow_zero, Equiv.Perm.one_apply, congrArg, Sigma.fst

      let v : ℕ → Fin m := fun i => ((e^i) x).1
      refine ⟨l,hl,v,?_,?_,?_⟩
      · simpa only [v,pow_zero,Equiv.Perm.one_apply] using congrArg Sigma.fst hclose
  8. For every step i < l, R (v i) (v (i+1)) holds.

    For any step i, (e^(i+1)) x = e ((e^i) x). The clone permutation e satisfies R y.1 (e y).1 for every cloned vertex y. Applying this to y = (e^i) x shows that R (v i) (v (i+1)) holds along every step of the walk.

    lines 60–62

    uses pow_succ', Equiv.Perm.mul_apply

      · intro i hi
        have h := he ((e^i) x)
        simpa only [v,pow_succ',Equiv.Perm.mul_apply] using h
  9. The walk satisfies the strict count bound: 2 * (∑ i ∈ range l, card {j | v i ∈ U j}) < l * n.

    The negative-cost condition along the cycle states that ∑ i ∈ range l, (2 * z(v i) - n) < 0. Distributing the sum gives 2 * (∑ i ∈ range l, z(v i)) - l * n < 0, so 2 * (∑ i ∈ range l, z(v i)) < l * n. Unfolding the definition of z and casting from ℝ to ℕ establishes the desired inequality.

    lines 63–68

    uses sum_sub_distrib, mul_sum, sum_const, card_range, nsmul_eq_mul

      · have hlt : 2 * (∑ i ∈ range l, (z (v i))) < (l : ℝ)*n := by
          change (∑ i ∈ range l, (2*z (v i) - n)) < 0 at hneg
          simp only [sum_sub_distrib,← mul_sum,sum_const,card_range,nsmul_eq_mul] at hneg
          linarith
        dsimp only [z] at hlt
        exact_mod_cast hlt
condorcet_finite_strict_separator_integer_weights
A finite system with a nonnegative real strict-half separator also admits an integer-valued strict-half separator.
condorcet_integer_acyclic_separator_neighbor_mass
An integer strict-half acyclic separator can be modified to another integer acyclic separator whose weights satisfy Hall's neighborhood condition: the total weight of any subset is at most that of its out-neighborhood.
condorcet_integer_neighbor_mass_clone_permutation
If integer weights satisfy Hall's neighborhood condition, there is a permutation of the cloned vertex set where each copy maps to a copy of an out-neighbor.
sum_lt_sum
A sum of terms that are each bounded by another, with at least one strict inequality, is strictly less than the other sum.
mem_univ
Every element of a finite type belongs to the universal finset univ.
sum_congr
Two sums over equal finsets with pointwise equal summands are equal.
Fintype.sum_ite_mem
Summing over the whole universe with an indicator function for a subset equals the sum over that subset.
mul_sum
A constant factor outside a finite sum distributes over all terms.
sum_comm
The order of summation in a double finite sum can be interchanged.
sum_filter
Summing over elements filtered by a predicate equals summing with an if-then-else indicator over the original set.
sum_const
Summing a constant over a finset yields the cardinality of the finset times the constant.
card_univ
The cardinality of univ for a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
nsmul_eq_mul
Natural number scalar multiplication equals algebraic multiplication by the integer or real cast.
Fintype.sum_sigma
A sum over a dependent sum (sigma type) can be evaluated as an iterated sum over base and fiber.
mul_sub
Multiplication distributes over subtraction from the left.
sum_sub_distrib
The sum of termwise differences is the difference of the sums.
sum_mul
A constant factor after a finite sum distributes over all terms.
condorcet_permutation_negative_closed_walk
If the sum of a cost function over a finite set is strictly negative, any permutation of that set contains a cycle whose total cost along the orbit is strictly negative.
pow_zero
The zeroth power of an element in a group or monoid is the identity.
Equiv.Perm.one_apply
The identity permutation maps every element to itself.
congrArg
Applying a function to equal arguments produces equal results.
Sigma.fst
The projection function extracting the first component of a dependent pair.
pow_succ'
The (n+1)-th power of a monoid element is the element multiplied by its n-th power.
Equiv.Perm.mul_apply
The composition of permutations evaluated at an element is the application of the first to the result of the second.
card_range
The cardinality of the range {0, ..., n - 1} is n.

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_acyclic_cover_closed_walk    (m n : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop)    (U : Fin n → Finset (Fin m))    (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val))    (hsep : ∃ 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) :    ∃ l : ℕ, 0 < l ∧ ∃ v : ℕ → Fin m,      v l = v 0 ∧ (∀ i < l, R (v i) (v (i+1))) ∧      2 * (∑ i ∈ range l, (univ.filter fun j => v i ∈ U j).card) < l*n := by  classical  obtain ⟨w₀,hw₀,hsep₀⟩ := hsep  obtain ⟨w₁,hw₁⟩ := 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 ⟨w,hw,hHall⟩ := condorcet_integer_acyclic_separator_neighbor_mass m R w₁ hw₁  obtain ⟨e,he⟩ := condorcet_integer_neighbor_mass_clone_permutation m R w hHall  let V := Σ a : Fin m, Fin (w a)  let z : Fin m → ℝ := fun a => ((univ.filter fun j => a ∈ U j).card : ℝ)  let c : V → ℝ := fun x => 2*z x.1 - n  have hstrict : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) <      ∑ _j : Fin n, ∑ a, (w a : ℝ) := by    apply sum_lt_sum    · intro j hj      exact_mod_cast (hw (U j) (hU j)).le    · refine ⟨⟨0,hn⟩,mem_univ _,?_⟩      exact_mod_cast hw (U ⟨0,hn⟩) (hU ⟨0,hn⟩)  have hswap : (∑ j : Fin n, 2 * (∑ a ∈ U j, (w a : ℝ))) =      ∑ a, (w a : ℝ) * (2*z a) := by    have hconvert : (∑ j : Fin n, ∑ a ∈ U j, (w a : ℝ)) =        ∑ j : Fin n, ∑ a : Fin m, if a ∈ U j then (w a : ℝ) else 0 := by      apply sum_congr rfl      intro j hj      exact (Fintype.sum_ite_mem (U j) (fun a => (w a : ℝ))).symm    rw [← mul_sum,hconvert,sum_comm,mul_sum]    apply sum_congr rfl    intro a ha    simp [z,← sum_filter]    ring  rw [hswap] at hstrict  simp only [sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul] at hstrict  have hc : (∑ x : V, c x) < 0 := by    have heq : (∑ x : V, c x) =        (∑ a, (w a : ℝ) * (2*z a)) - (n : ℝ) * ∑ a, (w a : ℝ) := by      rw [Fintype.sum_sigma]      simp only [c,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mul,mul_sub]      rw [sum_sub_distrib,← sum_mul]      ring    rw [heq]    linarith  obtain ⟨l,hl,x,hclose,hneg⟩ := condorcet_permutation_negative_closed_walk e c hc  let v : ℕ → Fin m := fun i => ((e^i) x).1  refine ⟨l,hl,v,?_,?_,?_⟩  · simpa only [v,pow_zero,Equiv.Perm.one_apply] using congrArg Sigma.fst hclose  · intro i hi    have h := he ((e^i) x)    simpa only [v,pow_succ',Equiv.Perm.mul_apply] using h  · have hlt : 2 * (∑ i ∈ range l, (z (v i))) < (l : ℝ)*n := by      change (∑ i ∈ range l, (2*z (v i) - n)) < 0 at hneg      simp only [sum_sub_distrib,← mul_sum,sum_const,card_range,nsmul_eq_mul] at hneg      linarith    dsimp only [z] at hlt    exact_mod_cast hlt
See it in the graphDiscuss this resultChallenge it