path_radio_label_four_mul_add_three_sep
The 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 indices a, b (distinct if x = y) differ by at least 4 - |x - y|.
Statement
set_option maxHeartbeats 4000000 in theorem path_radio_label_four_mul_add_three_sep (m x y a b : ℕ) (hx : x < 4 * m + 3) (hy : y < 4 * m + 3) (ha : a < m) (hb : b < m) (hne : x ≠ y ∨ a ≠ b) : (4 : ℤ) - |(x : ℤ) - y| ≤ |(((if x % 2 = 1 then x + 4 * a else 2 * (x / 2 % 2) + 4 * a + if a < x / 4 then 0 else 4 * m) : ℕ) : ℤ) - (((if y % 2 = 1 then y + 4 * b else 2 * (y / 2 % 2) + 4 * b + if b < y / 4 then 0 else 4 * m) : ℕ) : ℤ)|
- Source
- for simple_graph_path_radio_labeling_four_mul_add_three (RT-4, OP-384)
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- int_four_sub_abs_le_absFor 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|.
- Used by 1
- simple_graph_path_radio_labeling_four_mul_add_threeFor m >= 1, the labeling of the path P_{4m+3} that gives an odd vertex v the labels v, v+4, ..., v+4(m-1) and an even vertex v the labels…
The proof, explained
The proof reduces the absolute value separation condition 4 - |x - y| ≤ |f(x, a) - f(y, b)| to linear inequalities using the lemma `int_four_sub_abs_le_abs`, branching on the sign of x - y. It then expands all conditional branches in the piecewise definition of the label—the parities of x and y, and whether a < x / 4 or b < y / 4—into 18 separate cases. Finally, casts from natural numbers to integers are pushed through, and the Presburger arithmetic solver `omega` closes every case using the given bounds on x, y, a, and b.
The difference between the labels at (x, a) and (y, b) is at least 4 - |x - y|. automation
We reduce the absolute value inequality 4 - |x - y| ≤ |f(x, a) - f(y, b)| using `int_four_sub_abs_le_abs`, which splits the problem into two cases based on the sign of x - y: when x - y ≥ 0, we must show that the difference of labels is at least 4 - (x - y) or at most (x - y) - 4; when x - y < 0, an analogous condition holds. In each case, introducing the sign assumption (`hs`) and splitting all if-then-else conditions (`split_ifs`) based on the parity of x and y and the cutoff inequalities a < x / 4 and b < y / 4 produces 18 subgoals. After pushing the integer casts into the arithmetic expressions (`push_cast`), linear integer arithmetic (`omega`) closes all 18 goals using the bounds x, y < 4m + 3, a, b < m, and the distinctness hypothesis x ≠ y ∨ a ≠ b.
uses
int_four_sub_abs_le_absapply int_four_sub_abs_le_abs <;> intro hs <;> split_ifs <;> push_cast <;> omega
int_four_sub_abs_le_abs- For any integers d and e, to prove 4 - |d| ≤ |e|, it suffices to show that 4 - d ≤ e ∨ e ≤ d - 4 when d ≥ 0, and 4 + d ≤ e ∨ e ≤ -4 - d when d < 0.
- The proof consists of a single tactic pipeline on line 9 that delegates all 18 resulting case branches to the `omega` Presburger arithmetic tactic. The arithmetic reasoning involves division and modulo by 2 and 4, bounded variables, and disjunctions, all handled internally by automation.
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.
set_option maxHeartbeats 4000000 intheorem path_radio_label_four_mul_add_three_sep (m x y a b : ℕ) (hx : x < 4 * m + 3) (hy : y < 4 * m + 3) (ha : a < m) (hb : b < m) (hne : x ≠ y ∨ a ≠ b) : (4 : ℤ) - |(x : ℤ) - y| ≤ |(((if x % 2 = 1 then x + 4 * a else 2 * (x / 2 % 2) + 4 * a + if a < x / 4 then 0 else 4 * m) : ℕ) : ℤ) - (((if y % 2 = 1 then y + 4 * b else 2 * (y / 2 % 2) + 4 * b + if b < y / 4 then 0 else 4 * m) : ℕ) : ℤ)| := by apply int_four_sub_abs_le_abs <;> intro hs <;> split_ifs <;> push_cast <;> omega