AFTD Auto-Formalizing Theoretical Domains

simple_graph_multi_radio_number_path_le_eight_mul

theoremverifiedformalization

For n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.

Statement

theorem simple_graph_multi_radio_number_path_le_eight_mul (n m : ℕ) (hn : 1 ≤ n) (hm : 1 ≤ m) :
    simple_graph_multi_radio_number (SimpleGraph.pathGraph n) m 3 ≤ 8 * m - 1
Formalizes
arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Proposition 4.4
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 2

The proof, explained

The theorem is proved by constructing an explicit (m, 3)-radio labeling of the path graph P_n and showing its span is at most 8m - 1. Each vertex v is assigned the m labels {8a + (3v mod 8) | 0 ≤ a < m}, which are distinct because the assignment is strictly monotonic in a. The radio separation condition (3 + 1) - dist(x, y) ≤ |a - b| follows from a modular arithmetic separation lemma and the fact that path distance is at least the difference of vertex indices. Since the maximum label is 8(m - 1) + 7 = 8m - 1, the span is at most 8m - 1, which bounds the infimum definition of the radio number.

  1. The candidate labeling assigns each vertex `v` a set of exactly `m` labels.

    We define the multi-labeling `f` on each vertex `v` as the image of `{0, ..., m - 1}` under `a ↦ 8a + (3v mod 8)`. Because this linear map is strictly increasing and therefore injective, `Finset.card_image_of_injective` implies that the size of `f(v)` equals the size of `{0, ..., m - 1}`, which is `m` by `Finset.card_range`.

    lines 3–7

    uses Finset.card_image_of_injective, Finset.card_range

      have hf : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m 3
          (fun v => (Finset.range m).image (fun a => 8 * a + 3 * v.val % 8)) := by
        refine ⟨fun v => ?_, fun x y a ha b hb hne => ?_⟩
        · rw [Finset.card_image_of_injective _ (fun a b h => by omega)]
          exact Finset.card_range m
  2. The candidate labeling satisfies the (m, 3)-radio condition: distinct vertex-label pairs satisfy `(3 + 1) - dist(x, y) ≤ |a - b|`.

    Given labels `a ∈ f(x)` and `b ∈ f(y)` with `(x, a) ≠ (y, b)`, we extract indices `a', b' < m` such that `a = 8a' + (3x mod 8)` and `b = 8b' + (3y mod 8)`. If `x = y`, then `a ≠ b` forces `a' ≠ b'`, so either `x ≠ y` or `a' ≠ b'`. The lemma `path_radio_label_eight_mul_sep` then guarantees `4 - |x - y| ≤ |a - b|`. Since the path graph distance satisfies `|x - y| ≤ dist(x, y)` by `simple_graph_path_graph_dist_ge`, linear arithmetic (`linarith`) combines these to yield `4 - dist(x, y) ≤ |a - b|`.

    lines 8–18

    uses simple_graph_path_graph_dist_ge, Finset.mem_image, Finset.mem_range, Fin.ext, Or.inl, path_radio_label_eight_mul_sep

        · have hd := simple_graph_path_graph_dist_ge x y
          simp only [Finset.mem_image, Finset.mem_range] at ha hb
          obtain ⟨a', ha', rfl⟩ := ha
          obtain ⟨b', hb', rfl⟩ := hb
          have hne3 : (x : ℕ) ≠ (y : ℕ) ∨ a' ≠ b' := by
            by_cases hxy : (x : ℕ) = (y : ℕ)
            · right; rintro rfl; exact hne (by rw [Fin.ext hxy])
            · exact Or.inl hxy
          have := path_radio_label_eight_mul_sep x y a' b' hne3
          push_cast at this ⊢
          linarith
  3. The span of the candidate multi-labeling is at most `8m - 1`.

    The span is defined as the supremum of `b - a` over all vertices `x, y` and labels `a ∈ f(x), b ∈ f(y)`. Using `Finset.sup_le` to unpack the four suprema, it suffices to bound `b - a` for arbitrary labels. Any label `b ∈ f(y)` satisfies `b = 8b' + (3y mod 8)` for some `b' < m`. Since `b' ≤ m - 1` and `(3y mod 8) ≤ 7`, we have `b ≤ 8(m - 1) + 7 = 8m - 1`. Since `a ≥ 0`, `b - a ≤ 8m - 1`, which is verified by linear arithmetic (`omega`).

    lines 19–25

    uses Finset.sup_le, Finset.mem_image, Finset.mem_range

      have hs : multi_label_span (fun v : Fin n => (Finset.range m).image (fun a => 8 * a + 3 * v.val % 8))
          ≤ 8 * m - 1 := by
        apply Finset.sup_le; intro x _; apply Finset.sup_le; intro y _
        apply Finset.sup_le; intro a ha; apply Finset.sup_le; intro b hb
        simp only [Finset.mem_image, Finset.mem_range] at hb
        obtain ⟨b', hb', rfl⟩ := hb
        omega
  4. The (m, 3)-radio number of the path graph P_n is at most `8m - 1`.

    The radio number is defined as the infimum of spans of all valid (m, 3)-radio labelings. Since our explicit candidate is a valid labeling, its span belongs to this set, so the infimum is bounded above by the candidate's span by `Nat.sInf_le`. Applying `le_trans` with the span upper bound of `8m - 1` completes the proof.

    line 26

    uses le_trans, Nat.sInf_le

      exact le_trans (Nat.sInf_le ⟨_, hf, rfl⟩) hs
Finset.card_image_of_injective
an injective function maps a finite set to an image with the same number of elements
Finset.card_range
the cardinality of the range `{0, ..., n - 1}` is `n`
Fin.ext
two elements of `Fin n` are equal if their underlying natural numbers are equal
Or.inl
if a proposition holds, then its disjunction with any other proposition also holds
simple_graph_path_graph_dist_ge
in a path graph, the distance between vertices `u` and `v` is at least `|u - v|`
Finset.mem_image
an element belongs to the image of a set under `f` if and only if it is `f a` for some element `a` of the set
Finset.mem_range
a natural number `m` is in `Finset.range n` if and only if `m < n`
path_radio_label_eight_mul_sep
distinct label pairs `(x, a) ≠ (y, b)` satisfy `4 - |x - y| ≤ |(8a + 3x % 8) - (8b + 3y % 8)|`
Finset.sup_le
the supremum of a function over a finite set is at most `c` if every value in the set is at most `c`
Nat.sInf_le
the infimum of a set of natural numbers is at most any element of that set
le_trans
inequality is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`

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 simple_graph_multi_radio_number_path_le_eight_mul (n m : ℕ) (hn : 1 ≤ n) (hm : 1 ≤ m) :    simple_graph_multi_radio_number (SimpleGraph.pathGraph n) m 3 ≤ 8 * m - 1 := by  have hf : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m 3      (fun v => (Finset.range m).image (fun a => 8 * a + 3 * v.val % 8)) := by    refine ⟨fun v => ?_, fun x y a ha b hb hne => ?_⟩    · rw [Finset.card_image_of_injective _ (fun a b h => by omega)]      exact Finset.card_range m    · have hd := simple_graph_path_graph_dist_ge x y      simp only [Finset.mem_image, Finset.mem_range] at ha hb      obtain ⟨a', ha', rfl⟩ := ha      obtain ⟨b', hb', rfl⟩ := hb      have hne3 : (x : ℕ) ≠ (y : ℕ) ∨ a' ≠ b' := by        by_cases hxy : (x : ℕ) = (y : ℕ)        · right; rintro rfl; exact hne (by rw [Fin.ext hxy])        · exact Or.inl hxy      have := path_radio_label_eight_mul_sep x y a' b' hne3      push_cast at this ⊢      linarith  have hs : multi_label_span (fun v : Fin n => (Finset.range m).image (fun a => 8 * a + 3 * v.val % 8))      ≤ 8 * m - 1 := by    apply Finset.sup_le; intro x _; apply Finset.sup_le; intro y _    apply Finset.sup_le; intro a ha; apply Finset.sup_le; intro b hb    simp only [Finset.mem_image, Finset.mem_range] at hb    obtain ⟨b', hb', rfl⟩ := hb    omega  exact le_trans (Nat.sInf_le ⟨_, hf, rfl⟩) hs
See it in the graphDiscuss this resultChallenge it