AFTD Auto-Formalizing Theoretical Domains

forest_greedy_step_neg

theoremverified

Negating both input discrepancies and flipping the tie coin negates the output of one greedy step.

Statement

theorem forest_greedy_step_neg (x y : ℤ) (b : Bool) :
    forest_greedy_signed_step (-x) (-y) (!b) = -forest_greedy_signed_step x y b
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_symmetric_mergeThe greedy update of two independent finite uniform symmetric integer laws with a fair tie coin has symmetric value counts.

The proof, explained

The proof proceeds by case analysis on the tie-breaking coin b and the relative order of the discrepancies x and y. Unfolding the definition of `forest_greedy_signed_step`, negating the inputs reverses their inequality (-x < -y ↔ y < x), while inverting the coin flips the choice made when x = y. In every case, linear integer arithmetic confirms that the greedy step on the negated inputs is the exact arithmetic negation of the original step.

  1. The signed greedy step is an odd function under simultaneously negating both discrepancies and flipping the tie-breaking coin, across all trichotomy cases (x < y, x > y, and x = y).

    We split into cases on the boolean tie-breaking coin b (`cases b`). In each branch, unfolding the definition of `forest_greedy_signed_step` (`simp [forest_greedy_signed_step]`) simplifies the inequality -x < -y to y < x and evaluates the flipped coin !b. Case-splitting on the if-then-else conditions (`split_ifs`) separates the relative orderings of x and y. Each resulting branch either contains contradictory order assumptions (such as x < y and y < x simultaneously) or simplifies to an elementary identity such as -x + 1 = -(x - 1) or -x - 1 = -(x + 1), all of which are resolved by linear integer arithmetic (`omega`).

    line 3

    uses forest_greedy_signed_step

      cases b <;> simp [forest_greedy_signed_step] <;> split_ifs <;> omega
forest_greedy_signed_step
The signed greedy step function: given discrepancies x and y and a boolean coin, returns x + 1 if x < y, x - 1 if y < x, and if x = y breaks the tie using coin (returning x + 1 if true and x - 1 if false).

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_step_neg (x y : ℤ) (b : Bool) :    forest_greedy_signed_step (-x) (-y) (!b) = -forest_greedy_signed_step x y b := by  cases b <;> simp [forest_greedy_signed_step] <;> split_ifs <;> omega
See it in the graphDiscuss this resultChallenge it