forest_greedy_symmetric_merge
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
- forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
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.
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.
uses
forest_symmetric_fiber_equiv,Equiv.boolNotclassical 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
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)$.
uses
forest_greedy_step_neghave 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 _ _ _
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.
uses
Fintype.card_congr,Fintype.card_subtypeintro 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.
- The final step uses `Fintype.card_subtype` to translate between the type-theoretic subtypes `{p // f p = z}` and the filtered finsets appearing in the theorem statement, a formal detail with no counterpart in paper mathematics.
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.
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