AFTD Auto-Formalizing Theoretical Domains

path_radio_label_eight_mul_sep

theoremverified

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

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`).

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

    lines 4–6

      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 <;>
  2. 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$.

    line 7

    uses int_four_sub_abs_le_abs

        apply 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$.

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

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