forest_greedy_merge_fixed_parity
If the first endpoint has fixed discrepancy parity, one greedy step has fixed output parity for all partner values and tie coins.
Statement
theorem forest_greedy_merge_fixed_parity (α β : Type) [Fintype α] [Fintype β] (X : α → ℤ) (Y : β → ℤ) (h : ∃ t : ℤ, ∀ a, X a % 2 = t) : ∃ t : ℤ, ∀ p : α × β × Bool, forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 % 2 = t
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- 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
The proof shows that if all entries of $X$ share a constant parity $t$, executing one greedy merge step always yields a value with parity $(t + 1) \pmod 2$. The witness for the existential quantifier is chosen to be $(t + 1) \pmod 2$. Expanding the definition of the greedy step shows that every outcome is either $X(a) + 1$ or $X(a) - 1$, both of which have parity congruent to $t + 1$ modulo 2.
It suffices to show that every greedy step produces a value with parity $(t + 1) \pmod 2$, where $t$ is the constant parity of $X$.
From the hypothesis $h$, we extract the constant parity $t \in \mathbb{Z}$ such that $X(a) \equiv t \pmod 2$ for all $a \in \alpha$. Because any greedy step either increments or decrements a value of $X$, the parity must flip; we therefore provide $(t + 1) \pmod 2$ as the candidate witness for the constant parity of the output.
obtain ⟨t, ht⟩ := h refine ⟨(t + 1) % 2, ?_⟩
For an arbitrary input triple $p = (a, b, \text{coin})$, the goal reduces to evaluating the piecewise definition of the greedy step on $X(a)$ modulo 2.
We introduce an arbitrary triple $p = (a, b, \text{coin}) \in \alpha \times \beta \times \text{Bool}$ and specialize the assumption on $X$ to $a = p.1$, obtaining $X(a) \equiv t \pmod 2$. Unfolding `forest_greedy_signed_step` exposes the conditional branching based on the comparison of $X(a)$ with $Y(b)$ and the tie-breaking coin.
intro p specialize ht p.1 unfold forest_greedy_signed_step
In every branch of the greedy step, the resulting value modulo 2 equals $(t + 1) \pmod 2$.
The `split_ifs` tactic splits into the four possible branches: $X(a) < Y(b)$, $Y(b) < X(a)$, and the coin flip cases when $X(a) = Y(b)$. Each branch evaluates to either $X(a) + 1$ or $X(a) - 1$. Since $X(a) \equiv t \pmod 2$, we have $(X(a) + 1) \equiv (t + 1) \pmod 2$ and $(X(a) - 1) \equiv t - 1 \equiv (t + 1) \pmod 2$. The linear integer arithmetic tactic `omega` confirms this equality in every case.
split_ifs <;> omega
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_merge_fixed_parity (α β : Type) [Fintype α] [Fintype β] (X : α → ℤ) (Y : β → ℤ) (h : ∃ t : ℤ, ∀ a, X a % 2 = t) : ∃ t : ℤ, ∀ p : α × β × Bool, forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 % 2 = t := by obtain ⟨t, ht⟩ := h refine ⟨(t + 1) % 2, ?_⟩ intro p specialize ht p.1 unfold forest_greedy_signed_step split_ifs <;> omega