int_four_sub_abs_le_abs
For integers d, e: if e >= 4 - d or e <= d - 4 when d >= 0, and e >= 4 + d or e <= -4 - d when d < 0, then 4 - |d| <= |e|.
Statement
theorem int_four_sub_abs_le_abs {d e : ℤ} (h1 : 0 ≤ d → (4 - d ≤ e ∨ e ≤ d - 4))
(h2 : d < 0 → (4 + d ≤ e ∨ e ≤ -4 - d)) : 4 - |d| ≤ |e|- Source
- for simple_graph_path_radio_labeling_four_mul_add_three (RT-4, OP-384)
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- path_radio_label_four_mul_add_three_sepThe labels of the explicit labeling of P_{4m+3} (odd x: x + 4a; even x: 2((x/2) mod 2) + 4a, plus 4m when a >= x/4) at vertices x, y with…
- path_radio_label_eight_mul_sepThe labels 8a + (3x mod 8) and 8b + (3y mod 8) (with x ≠ y or a ≠ b) differ by at least 4 - |x - y|.
The proof, explained
The proof proceeds by case analysis on the signs of $d$ and $e$, eliminating the absolute values $|d|$ and $|e|$. Depending on whether $d \ge 0$ or $d < 0$, the corresponding hypothesis ($h_1$ or $h_2$) yields a disjunction bounding $e$. Finally, linear integer arithmetic confirms that the desired inequality $4 - |d| \le |e|$ holds in all four cases.
The inequality reduces to four cases depending on the signs of $d$ and $e$, expressing $|d|$ and $|e|$ without absolute values.
Applying `abs_cases` to $d$ splits into the cases $0 \le d$ (where $|d| = d$) and $d < 0$ (where $|d| = -d$). Applying it again to $e$ splits each branch into $0 \le e$ (where $|e| = e$) and $e < 0$ (where $|e| = -e$), yielding four cases in total.
uses
abs_casesrcases abs_cases d with ⟨e1, hd⟩ | ⟨e1, hd⟩ <;> rcases abs_cases e with ⟨e2, he⟩ | ⟨e2, he⟩ <;>
In all four cases, the inequality $4 - |d| \le |e|$ holds. automation
In each case, rewriting $|d|$ and $|e|$ by their signed expressions removes all absolute values from the goal. When $0 \le d$, hypothesis $h_1$ provides $4 - d \le e \lor e \le d - 4$; when $d < 0$, hypothesis $h_2$ provides $4 + d \le e \lor e \le -4 - d$. In each branch, the disjunction together with the sign conditions linearly implies the goal, which is closed by linear integer arithmetic (`omega`).
rw [e1, e2] <;> [have := h1 hd; have := h1 hd; have := h2 hd; have := h2 hd] <;> omega
abs_cases- An element $a$ of a linearly ordered additive commutative group satisfies either $|a| = a$ and $0 \le a$, or $|a| = -a$ and $a < 0$.
- The proof delegates the final verification of the inequalities in all four branches to the `omega` decision procedure for Presburger arithmetic.
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 int_four_sub_abs_le_abs {d e : ℤ} (h1 : 0 ≤ d → (4 - d ≤ e ∨ e ≤ d - 4)) (h2 : d < 0 → (4 + d ≤ e ∨ e ≤ -4 - d)) : 4 - |d| ≤ |e| := by rcases abs_cases d with ⟨e1, hd⟩ | ⟨e1, hd⟩ <;> rcases abs_cases e with ⟨e2, he⟩ | ⟨e2, he⟩ <;> rw [e1, e2] <;> [have := h1 hd; have := h1 hd; have := h2 hd; have := h2 hd] <;> omega