AFTD Auto-Formalizing Theoretical Domains

forest_greedy_symmetric_merge

theoremverified

The greedy update of two independent finite uniform symmetric integer laws with a fair tie coin has symmetric value counts.

Statement

theorem forest_greedy_symmetric_merge
    (α β : Type) [Fintype α] [Fintype β] (X : α → ℤ) (Y : β → ℤ)
    (hx : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =
      (Finset.univ.filter (fun a => X a = -z)).card)
    (hy : ∀ z : ℤ, (Finset.univ.filter (fun b => Y b = z)).card =
      (Finset.univ.filter (fun b => Y b = -z)).card) :
    ∀ z : ℤ, (Finset.univ.filter (fun p : α × β × Bool =>
      forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 = z)).card =
      (Finset.univ.filter (fun p : α × β × Bool =>
      forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 = -z)).card
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • forest_greedy_signed_stepThe new discrepancy of the first endpoint of a greedy edge is x+1 when x<y, x-1 when x>y, and uses the fair coin to choose between these…
  • forest_symmetric_fiber_equivAny finite uniform integer law with symmetric value counts admits a permutation that negates every value.
  • forest_greedy_step_negNegating both input discrepancies and flipping the tie coin negates the output of one greedy step.
Used by 1

The proof, explained

To show that the greedy step produces a symmetric distribution, the proof constructs an explicit bijection on the joint sample space $\alpha \times \beta \times \mathrm{Bool}$ that negates the resulting value. Because the marginal distributions of $X$ and $Y$ are symmetric, each admits a sign-reversing bijection; combining these with boolean negation on the tie-breaking coin yields a product bijection on the full state space. Since negating both inputs and flipping the coin negates the greedy step, this bijection pairs each outcome yielding $z$ with an outcome yielding $-z$, proving that the two values have equal counts.

  1. Construct a sign-reversing product bijection on the sample space and define the greedy step function.

    By the symmetry hypotheses on $X$ and $Y$, `forest_symmetric_fiber_equiv` provides bijections $e_X : \alpha \simeq \alpha$ and $e_Y : \beta \simeq \beta$ such that $X(e_X(a)) = -X(a)$ and $Y(e_Y(b)) = -Y(b)$. Taking their product along with boolean negation on the coin (`Equiv.boolNot`) yields a bijection $ee$ on the product domain $\alpha \times \beta \times \mathrm{Bool}$. We define $f$ as the greedy step function on this space.

    lines 11–15

    uses forest_symmetric_fiber_equiv, Equiv.boolNot

      classical
      obtain ⟨ex, hex⟩ := forest_symmetric_fiber_equiv α X hx
      obtain ⟨ey, hey⟩ := forest_symmetric_fiber_equiv β Y hy
      let ee : α × β × Bool ≃ α × β × Bool := ex.prodCongr (ey.prodCongr Equiv.boolNot)
      let f : α × β × Bool → ℤ := fun p => forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2
  2. The greedy step function satisfies $f(ee(p)) = -f(p)$ for every outcome $p$.

    Applying $f$ to $ee(p) = (e_X(a), e_Y(b), \neg c)$ evaluates the greedy signed step at $(-X(a), -Y(b), \neg c)$ by the definition of $e_X$ and $e_Y$. By `forest_greedy_step_neg`, negating both integer arguments and inverting the coin negates the resulting step value, which equals $-f(p)$.

    lines 16–19

    uses forest_greedy_step_neg

      have hstep (p : α × β × Bool) : f (ee p) = -f p := by
        change forest_greedy_signed_step (X (ex p.1)) (Y (ey p.2.1)) (!p.2.2) = _
        rw [hex, hey]
        exact forest_greedy_step_neg _ _ _
  3. For every integer $z$, the fiber of the greedy step at $z$ has the same cardinality as the fiber at $-z$.

    Fix an integer $z$. Since $f(ee(p)) = -f(p)$, an outcome $p$ satisfies $f(p) = z$ if and only if $ee(p)$ satisfies $f(ee(p)) = -z$ by linear integer arithmetic. Thus the bijection $ee$ restricts to a bijection between the subtypes $\{p \mid f(p) = z\}$ and $\{p \mid f(p) = -z\}$. Applying `Fintype.card_congr` shows these subtypes have equal cardinality, and `Fintype.card_subtype` converts their subtype cardinalities into the cardinalities of the filtered finsets in the goal.

    lines 20–25

    uses Fintype.card_congr, Fintype.card_subtype

      intro z
      let ez : {p // f p = z} ≃ {p // f p = -z} := ee.subtypeEquiv (by
        intro p
        rw [hstep]
        omega)
      simpa only [Fintype.card_subtype] using Fintype.card_congr ez
forest_symmetric_fiber_equiv
A finite integer-valued function with symmetric fiber sizes admits a domain permutation that negates the function's values at every point.
Equiv.boolNot
The permutation of `Bool` that swaps `true` and `false` (boolean negation).
forest_greedy_step_neg
Negating both integer inputs and inverting the tie-breaking coin negates the result of the greedy signed step.
Fintype.card_congr
Equivalent finite types have the same cardinality.
Fintype.card_subtype
The cardinality of a subtype equals the cardinality of the finset obtained by filtering the universal set with the subtype predicate.

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

theorem forest_greedy_symmetric_merge    (α β : Type) [Fintype α] [Fintype β] (X : α → ℤ) (Y : β → ℤ)    (hx : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =      (Finset.univ.filter (fun a => X a = -z)).card)    (hy : ∀ z : ℤ, (Finset.univ.filter (fun b => Y b = z)).card =      (Finset.univ.filter (fun b => Y b = -z)).card) :    ∀ z : ℤ, (Finset.univ.filter (fun p : α × β × Bool =>      forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 = z)).card =      (Finset.univ.filter (fun p : α × β × Bool =>      forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 = -z)).card := by  classical  obtain ⟨ex, hex⟩ := forest_symmetric_fiber_equiv α X hx  obtain ⟨ey, hey⟩ := forest_symmetric_fiber_equiv β Y hy  let ee : α × β × Bool ≃ α × β × Bool := ex.prodCongr (ey.prodCongr Equiv.boolNot)  let f : α × β × Bool → ℤ := fun p => forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2  have hstep (p : α × β × Bool) : f (ee p) = -f p := by    change forest_greedy_signed_step (X (ex p.1)) (Y (ey p.2.1)) (!p.2.2) = _    rw [hex, hey]    exact forest_greedy_step_neg _ _ _  intro z  let ez : {p // f p = z} ≃ {p // f p = -z} := ee.subtypeEquiv (by    intro p    rw [hstep]    omega)  simpa only [Fintype.card_subtype] using Fintype.card_congr ez
See it in the graphDiscuss this resultChallenge it