simple_graph_multi_radio_number_path_le_eight_mul
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
- simple_graph_multi_radio_numberThe (m,k)-radio number lambda_k^m(G): the least span of an (m,k)-radio labeling of G.
- 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).
- path_radio_label_eight_mul_sepThe labels 8a + (3x mod 8) and 8b + (3y mod 8) (with x ≠ y or a ≠ b) differ by at least 4 - |x - y|.
- simple_graph_path_graph_dist_geIn the path graph P_n the distance between u and v is at least |u - v|.
- 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 2
- simple_graph_multi_radio_number_path_three_of_le_of_forallReduction of the thread goal to one finite statement per m: if no (m,3)-radio labeling of P_{4m+4} has all labels at most 8m - 2, then the…
- simple_graph_multi_radio_number_path_three_one_of_leFor every n >= 8 the (1,3)-radio number of the path P_n is exactly 7: the case m = 1 of the thread's goal (8m - 1 for n >= 4m + 4).
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.
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`.
uses
Finset.card_image_of_injective,Finset.card_rangehave 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
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|`.
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
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`).
uses
Finset.sup_le,Finset.mem_image,Finset.mem_rangehave 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
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.
uses
le_trans,Nat.sInf_leexact 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`
- The key modular arithmetic inequality that ensures the radio separation condition holds on the path is encapsulated in the helper lemma `path_radio_label_eight_mul_sep`, which is proved separately in the knowledge base.
- In line 25, the `omega` tactic silently uses the fact that `(3 * y.val) % 8 ≤ 7` along with `b' < m` to establish the upper bound `8 * b' + 3 * y.val % 8 - a ≤ 8 * m - 1`.
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_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