AFTD Auto-Formalizing Theoretical Domains

forest_greedy_merge_fixed_parity

theoremverified

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

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.

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

    lines 6–7

      obtain ⟨t, ht⟩ := h
      refine ⟨(t + 1) % 2, ?_⟩
  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.

    lines 8–10

      intro p
      specialize ht p.1
      unfold forest_greedy_signed_step
  3. 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.

    line 11

      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

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