path_radio_label_eight_mul_sep
The labels 8a + (3x mod 8) and 8b + (3y mod 8) (with x ≠ y or a ≠ b) differ by at least 4 - |x - y|.
Statement
set_option maxHeartbeats 2000000 in theorem path_radio_label_eight_mul_sep (x y a b : ℕ) (hne : x ≠ y ∨ a ≠ b) : (4 : ℤ) - |(x : ℤ) - y| ≤ |(((8 * a + 3 * x % 8 : ℕ)) : ℤ) - ((8 * b + 3 * y % 8 : ℕ) : ℤ)|
- Source
- for simple_graph_multi_radio_number_path_le_eight_mul (arXiv:2610.25863 Proposition 4.4)
- 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_multi_radio_number_path_le_eight_mulFor n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.
The proof, explained
The proof establishes the distance separation by case analysis on the integer difference $x - y$, splitting into nine exhaustive cases: $x - y \le -4$, the seven individual values from $-3$ to $3$, and $x - y \ge 4$. In every branch, the lemma `int_four_sub_abs_le_abs` eliminates the absolute values by reducing the inequality to signed bounds. The resulting eighteen subgoals, which involve linear combinations of $a, b$ and the modulo-8 terms under the distinctness assumption $x \ne y \lor a \ne b$, are all verified automatically by integer arithmetic (`omega`).
The integer difference $x - y$ satisfies one of nine exhaustive cases: $x - y \le -4$, $x - y \in \{-3, -2, -1, 0, 1, 2, 3\}$, or $x - y \ge 4$.
Every integer belongs to one of these nine intervals or points. Linear integer arithmetic (`omega`) establishes this disjunction, and `rcases` splits the goal into nine corresponding cases.
rcases (show (x : ℤ) - y ≤ -4 ∨ (x : ℤ) - y = -3 ∨ (x : ℤ) - y = -2 ∨ (x : ℤ) - y = -1 ∨ (x : ℤ) - y = 0 ∨ (x : ℤ) - y = 1 ∨ (x : ℤ) - y = 2 ∨ (x : ℤ) - y = 3 ∨ 4 ≤ (x : ℤ) - y by omega) with h | h | h | h | h | h | h | h | h <;>
In each of the nine cases, the inequality $4 - |x - y| \le |(8a + (3x \bmod 8)) - (8b + (3y \bmod 8))|$ holds. automation
For each case, `int_four_sub_abs_le_abs` eliminates the outer absolute values, reducing the goal to showing that the label difference is bounded below or above by $\pm(4 - |x - y|)$ depending on the sign of $x - y$. The tactic `intro hs` assumes the sign condition ($0 \le x - y$ or $x - y < 0$), `push_cast` distributes the integer casts into the modular expressions, and `omega` finishes all eighteen subgoals using linear arithmetic together with the distinctness assumption $x \ne y \lor a \ne b$.
uses
int_four_sub_abs_le_absapply int_four_sub_abs_le_abs <;> intro hs <;> push_cast <;> omega
int_four_sub_abs_le_abs- For any integers $d$ and $e$, to establish $4 - |d| \le |e|$, it suffices to show that if $d \ge 0$, then $4 - d \le e$ or $e \le d - 4$, and if $d < 0$, then $4 + d \le e$ or $e \le -4 - d$.
- The modular arithmetic involved in evaluating $(3x \bmod 8) - (3y \bmod 8)$ across the nine cases for $x - y$ is discharged entirely by Lean's linear integer arithmetic tactic `omega`, which natively handles modulo and division by constant integers.
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 2000000 intheorem path_radio_label_eight_mul_sep (x y a b : ℕ) (hne : x ≠ y ∨ a ≠ b) : (4 : ℤ) - |(x : ℤ) - y| ≤ |(((8 * a + 3 * x % 8 : ℕ)) : ℤ) - ((8 * b + 3 * y % 8 : ℕ) : ℤ)| := by rcases (show (x : ℤ) - y ≤ -4 ∨ (x : ℤ) - y = -3 ∨ (x : ℤ) - y = -2 ∨ (x : ℤ) - y = -1 ∨ (x : ℤ) - y = 0 ∨ (x : ℤ) - y = 1 ∨ (x : ℤ) - y = 2 ∨ (x : ℤ) - y = 3 ∨ 4 ≤ (x : ℤ) - y by omega) with h | h | h | h | h | h | h | h | h <;> apply int_four_sub_abs_le_abs <;> intro hs <;> push_cast <;> omega