simple_graph_path_radio_labeling_four_mul_add_three
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- simple_graph_multi_radio_number_path_three_ltThe threshold 4m + 4 is sharp: the (m,3)-radio number of P_{4m+3} is less than 8m - 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.
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.
refine ⟨⟨fun v => ?_, fun x y a ha b hb hne => ?_⟩, ?_⟩
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.
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
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.
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
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.
uses
Finset.mem_image,Finset.mem_range,Or.inl,path_radio_label_four_mul_add_three_sepdsimp 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
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.
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.
- The technical core of the radio separation condition, showing that 4 - |x - y| ≤ |a - b| for distinct pairs, is proved by exhaustive case analysis in the auxiliary lemma path_radio_label_four_mul_add_three_sep.
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.
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