AFTD Auto-Formalizing Theoretical Domains

simple_graph_path_radio_labeling_four_mul_add_three

theoremverified

For 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 2((v/2) mod 2) + 4a for a < v/4 and 2((v/2) mod 2) + 4a + 4m for v/4 <= a < m is an (m,3)-radio labeling of span at most 8m - 2. So the threshold 4m + 4 for the value 8m - 1 is sharp.

Statement

theorem simple_graph_path_radio_labeling_four_mul_add_three (m : ℕ) (hm : 1 ≤ m) :
    simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (4 * m + 3)) m 3
        (fun v => if v.val % 2 = 1 then (Finset.range m).image (fun a => v.val + 4 * a)
          else (Finset.range m).image
            (fun a => 2 * (v.val / 2 % 2) + 4 * a + if a < v.val / 4 then 0 else 4 * m)) ∧
      multi_label_span (fun v : Fin (4 * m + 3) =>
        if v.val % 2 = 1 then (Finset.range m).image (fun a => v.val + 4 * a)
          else (Finset.range m).image
            (fun a => 2 * (v.val / 2 % 2) + 4 * a + if a < v.val / 4 then 0 else 4 * m)) ≤ 8 * m - 2
Source
for simple_graph_multi_radio_number_path_three_lt (RT-4, OP-384); pattern read off CP-SAT solutions (exp 1952), checked for m <= 40 (exp 1953)
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • simple_graph_is_multi_radio_labelingAn (m,k)-radio labeling of G: each vertex gets a set of m nonnegative integer labels, and for any (possibly equal) vertices x, y and…
  • multi_label_spanThe span of a multi-labeling: the largest label used minus the smallest (written as the largest difference b - a over all pairs of labels).
  • simple_graph_path_graph_dist_geIn the path graph P_n the distance between u and v is at least |u - v|.
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The proof establishes that the prescribed multi-labeling of the path P_{4m+3} is an (m,3)-radio labeling of span at most 8m - 2 by splitting into three tasks: label cardinality, the radio distance separation condition, and the span bound. Each vertex is assigned the image of {0, ..., m-1} under an injective map, ensuring it receives exactly m labels. The radio condition (3 + 1) - dist(x, y) ≤ |a - b| is reduced via the path distance bound dist(x, y) ≥ |x - y| to 4 - |x - y| ≤ |a - b|, which is verified for all parity cases of x and y by the technical separation lemma path_radio_label_four_mul_add_three_sep. Finally, every label b is shown to be at most 8m - 2 by linear arithmetic, bounding the overall span b - a by 8m - 2.

  1. The proof obligation decomposes into three parts: each vertex receives m labels, the radio separation condition holds for all pairs of distinct vertex labels, and the span is at most 8m - 2.

    By definition, an (m, 3)-multi-radio labeling requires each vertex to receive a set of m labels such that any distinct pairs (x, a) ≠ (y, b) with a ∈ f(x) and b ∈ f(y) satisfy (3 + 1) - dist(x, y) ≤ |a - b|. The refinement step splits the conjunction of these requirements and the span bound multi_label_span(f) ≤ 8m - 2 into separate goals.

    line 10

      refine ⟨⟨fun v => ?_, fun x y a ha b hb hne => ?_⟩, ?_⟩
  2. For every vertex v, the assigned label set contains exactly m elements.

    We split into cases on whether the vertex index v is odd or even. In both cases, the label set is defined as the image of range m = {0, ..., m-1} under an affine map. For odd v, a ↦ v + 4a is strictly increasing, hence injective. For even v, a ↦ 2((v/2) mod 2) + 4a + (if a < v/4 then 0 else 4m) is also strictly increasing, which linear arithmetic confirms by testing the cases of a < v/4. By Finset.card_image_of_injective, an injective image preserves cardinality, and Finset.card_range gives |range m| = m.

    lines 11–17

    uses Finset.card_image_of_injective, Finset.card_range

      · dsimp only
        split_ifs with hv
        · rw [Finset.card_image_of_injective _ (fun a b h => by omega)]
          exact Finset.card_range m
        · rw [Finset.card_image_of_injective _ (fun a b h => by
            split_ifs at h <;> omega)]
          exact Finset.card_range m
  3. To verify the radio separation condition for distinct pairs (x, a) ≠ (y, b), it suffices to show 4 - |x - y| ≤ |a - b|.

    By simple_graph_path_graph_dist_ge, the graph distance between vertices x and y in a path graph satisfies dist(x, y) ≥ |x - y|. Therefore, 4 - dist(x, y) ≤ 4 - |x - y|, so the radio condition 4 - dist(x, y) ≤ |a - b| follows from 4 - |x - y| ≤ |a - b|. Moreover, since (x, a) ≠ (y, b), we have x ≠ y ∨ a ≠ b via Fin.ext, Or.inl, and Or.inr.

    lines 18–29

    uses simple_graph_path_graph_dist_ge, Fin.ext, Or.inr, Or.inl

      · have hd := simple_graph_path_graph_dist_ge x y
        have hx := x.isLt
        have hy := y.isLt
        have hne' : x = y → a ≠ b := fun h1 h2 => hne (by rw [h1, h2])
        have hne'' : (x : ℕ) ≠ (y : ℕ) ∨ a ≠ b := by
          by_cases h : (x : ℕ) = (y : ℕ)
          · exact Or.inr (hne' (Fin.ext h))
          · exact Or.inl h
        clear hne' hne
        suffices h : (4 : ℤ) - |((x : ℕ) : ℤ) - ((y : ℕ) : ℤ)| ≤ |(a : ℤ) - b| by
          push_cast; linarith
        clear hd
  4. The inequality 4 - |x - y| ≤ |a - b| holds for all a ∈ f(x) and b ∈ f(y).

    We split into four cases on the parities of x and y using split_ifs. In each case, a and b are expressed via Finset.mem_image and Finset.mem_range as the labels corresponding to indices a', b' < m. If x = y, then a ≠ b implies a' ≠ b', so in all cases x ≠ y ∨ a' ≠ b' (using Or.inl). The separation inequality then follows directly from the lemma path_radio_label_four_mul_add_three_sep, and simplifying with the parity hypotheses closes each case.

    lines 30–42

    uses Finset.mem_image, Finset.mem_range, Or.inl, path_radio_label_four_mul_add_three_sep

        dsimp only at ha hb
        split_ifs at ha hb with h1 h2 h2 <;>
        · 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
            rcases hne'' with h | h
            · exact Or.inl h
            · by_cases hxy : (x : ℕ) = (y : ℕ)
              · right; rintro rfl; apply h; (try split_ifs) <;> omega
              · exact Or.inl hxy
          have := path_radio_label_four_mul_add_three_sep m x y a' b' hx hy ha' hb' hne3
          simpa [h1, h2] using this
  5. The span of the multi-labeling is at most 8m - 2. automation

    The span is defined as the supremum of b - a over all vertices x, y and labels a ∈ f(x), b ∈ f(y). Applying Finset.sup_le repeatedly reduces the bound to showing b - a ≤ 8m - 2 for all choices of x, y, a, b. Unfolding b ∈ f(y) via Finset.mem_image and Finset.mem_range gives b' < m. Since a ≥ 0, it suffices to bound b ≤ 8m - 2, which linear integer arithmetic (omega) verifies across all parity and threshold branches using y < 4m + 3 and b' ≤ m - 1.

    lines 43–48

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

      · 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
        have hy := y.isLt
        dsimp only at hb
        split_ifs at hb with h2 <;> simp only [Finset.mem_image, Finset.mem_range] at hb <;>
          obtain ⟨b', hb', rfl⟩ := hb <;> (try split_ifs) <;> omega
Finset.card_image_of_injective
The cardinality of the image of a finite set under an injective function equals the cardinality of the original set.
Finset.card_range
The finite set range n = {0, 1, ..., n-1} has cardinality n.
simple_graph_path_graph_dist_ge
In a path graph, the graph distance between two vertices is at least the absolute difference of their integer indices.
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
Or.inr
A disjunction A ∨ B holds if its right disjunct B holds.
Or.inl
A disjunction A ∨ B holds if its left disjunct A holds.
Finset.mem_image
An element b belongs to the image f(s) of a finite set s if and only if b = f(a) for some a ∈ s.
Finset.mem_range
A natural number m belongs to range n if and only if m < n.
path_radio_label_four_mul_add_three_sep
For distinct pairs (x, a) ≠ (y, b) with vertices x, y < 4m + 3 and indices a, b < m, the difference between their assigned labels is at least 4 - |x - y|.
Finset.sup_le
The supremum of a function over a finite set is at most a if every function value on the set is at most a.

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_path_radio_labeling_four_mul_add_three (m : ℕ) (hm : 1 ≤ m) :    simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (4 * m + 3)) m 3        (fun v => if v.val % 2 = 1 then (Finset.range m).image (fun a => v.val + 4 * a)          else (Finset.range m).image            (fun a => 2 * (v.val / 2 % 2) + 4 * a + if a < v.val / 4 then 0 else 4 * m)) ∧      multi_label_span (fun v : Fin (4 * m + 3) =>        if v.val % 2 = 1 then (Finset.range m).image (fun a => v.val + 4 * a)          else (Finset.range m).image            (fun a => 2 * (v.val / 2 % 2) + 4 * a + if a < v.val / 4 then 0 else 4 * m)) ≤ 8 * m - 2 := by  refine ⟨⟨fun v => ?_, fun x y a ha b hb hne => ?_⟩, ?_⟩  · dsimp only    split_ifs with hv    · rw [Finset.card_image_of_injective _ (fun a b h => by omega)]      exact Finset.card_range m    · rw [Finset.card_image_of_injective _ (fun a b h => by        split_ifs at h <;> omega)]      exact Finset.card_range m  · have hd := simple_graph_path_graph_dist_ge x y    have hx := x.isLt    have hy := y.isLt    have hne' : x = y → a ≠ b := fun h1 h2 => hne (by rw [h1, h2])    have hne'' : (x : ℕ) ≠ (y : ℕ) ∨ a ≠ b := by      by_cases h : (x : ℕ) = (y : ℕ)      · exact Or.inr (hne' (Fin.ext h))      · exact Or.inl h    clear hne' hne    suffices h : (4 : ℤ) - |((x : ℕ) : ℤ) - ((y : ℕ) : ℤ)| ≤ |(a : ℤ) - b| by      push_cast; linarith    clear hd    dsimp only at ha hb    split_ifs at ha hb with h1 h2 h2 <;>    · 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        rcases hne'' with h | h        · exact Or.inl h        · by_cases hxy : (x : ℕ) = (y : ℕ)          · right; rintro rfl; apply h; (try split_ifs) <;> omega          · exact Or.inl hxy      have := path_radio_label_four_mul_add_three_sep m x y a' b' hx hy ha' hb' hne3      simpa [h1, h2] using this  · 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    have hy := y.isLt    dsimp only at hb    split_ifs at hb with h2 <;> simp only [Finset.mem_image, Finset.mem_range] at hb <;>      obtain ⟨b', hb', rfl⟩ := hb <;> (try split_ifs) <;> omega
See it in the graphDiscuss this resultChallenge it