exists_multi_radio_labeling_path
For all n, m, k there is an (m,k)-radio labeling of the path P_n: on vertex v put the m labels (k+1)*(m*v + a) for a < m.
Statement
theorem exists_multi_radio_labeling_path (n m k : ℕ) :
∃ f : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k f- Source
- step towards simple_graph_multi_radio_number_path_three_of_le
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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_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
An $(m,k)$-radio labeling of the path $P_n$ requires assigning each vertex $v$ a set of $m$ labels such that distinct vertex-label pairs satisfy $|a - b| \ge (k+1) - \mathrm{dist}(x, y)$. The proof constructs an explicit labeling by setting $f(v) = \{(k+1)(mv + a) : a \in \{0, \dots, m-1\}\}$, where $mv + a$ uniquely identifies each vertex and label index by uniqueness of quotient and remainder. Because each label is a distinct multiple of $k+1$, any two distinct labels differ by at least $k+1$. Since graph distance is non-negative, $(k+1) - \mathrm{dist}(x, y) \le k+1 \le |a - b|$, satisfying the radio condition everywhere without needing to calculate path distances.
If remainders satisfy $a' < m$ and $b' < m$, and $(x, a') \ne (y, b')$, then $m x + a' \ne m y + b'$.
We split by trichotomy on $x$ and $y$. If $x < y$, then $x + 1 \le y$, so $m(x + 1) \le m y$; since $a' < m$, we have $m x + a' < m(x + 1) \le m y \le m y + b'$, preventing equality. The case $y < x$ is symmetric. If $x = y$, the assumed inequality $(x, a') \ne (x, b')$ means $a' \ne b'$, so $m x + a' \ne m x + b'$.
uses
lt_trichotomy,Nat.mul_le_mul_leftrcases lt_trichotomy x y with hlt | heq | hgt · have : m * (x + 1) ≤ m * y := Nat.mul_le_mul_left m hlt nlinarith · subst heq intro h have : a' = b' := by omega exact hne (by rw [this]) · have : m * (y + 1) ≤ m * x := Nat.mul_le_mul_left m hgt nlinarith
For natural numbers $k$ and distinct $u \ne v$, the integer absolute difference satisfies $|(k+1)u - (k+1)v| \ge k + 1$.
After pushing casts from $\mathbb{N}$ to $\mathbb{Z}$, we split by trichotomy on $u$ and $v$. The case $u = v$ is ruled out by the hypothesis $u \ne v$. If $u < v$, then $u + 1 \le v$, so $(k+1)u < (k+1)v$; the absolute value simplifies to $(k+1)v - (k+1)u = (k+1)(v - u) \ge k + 1$. The case $v < u$ is symmetric.
uses
lt_trichotomy,abs_of_neg,abs_of_pospush_cast rcases lt_trichotomy u v with hlt | heq | hgt · have : (u : ℤ) < (v : ℤ) := by exact_mod_cast hlt have : (k + 1 : ℤ) * (u : ℤ) < (k + 1 : ℤ) * (v : ℤ) := by nlinarith rw [abs_of_neg (by linarith)] have : (u : ℤ) + 1 ≤ (v : ℤ) := by omega nlinarith · exact (h heq).elim · have : (v : ℤ) < (u : ℤ) := by exact_mod_cast hgt have : (k + 1 : ℤ) * (v : ℤ) < (k + 1 : ℤ) * (u : ℤ) := by nlinarith rw [abs_of_pos (by linarith)] have : (v : ℤ) + 1 ≤ (u : ℤ) := by omega nlinarith
It suffices to verify the cardinality and distance conditions for the candidate labeling $f(v) = \{(k+1)(mv + a) : a < m\}$.
We instantiate the existential quantifier with the labeling assigning to each vertex $v$ the image of $\{0, \dots, m-1\}$ under $a \mapsto (k+1)(mv + a)$. Unfolding the definition of a multi-radio labeling splits the goal into two parts: checking that each label set has size $m$, and verifying the radio inequality for any distinct vertex-label pairs.
use fun v => (Finset.range m).image (fun a => (k + 1) * (m * v.val + a)) dsimp [simple_graph_is_multi_radio_labeling] constructor
For each vertex $v$, the label set $f(v)$ has cardinality $m$.
The set $f(v)$ is the image of $\{0, \dots, m-1\}$ under $a \mapsto (k+1)(mv + a)$. Since $k+1 > 0$, multiplying by $k+1$ is injective, and adding $mv$ preserves injectivity. Because the function is injective, the cardinality of the image equals the cardinality of $\{0, \dots, m-1\}$, which is $m$.
uses
Finset.card_image_of_injective,Finset.card_range,Nat.eq_of_mul_eq_mul_left,Nat.succ_pos· intro v rw [Finset.card_image_of_injective, Finset.card_range] intro a b h have h2 := Nat.eq_of_mul_eq_mul_left (Nat.succ_pos k) h omega
Any labels $a \in f(x)$ and $b \in f(y)$ can be expressed as $a = (k+1)(mx + a')$ and $b = (k+1)(my + b')$ with $a', b' < m$.
Unpacking the definition of $f$ as the image of the range $\{0, \dots, m-1\}$, every element $a \in f(x)$ arises from some remainder $a' < m$ as $a = (k+1)(mx + a')$, and similarly $b = (k+1)(my + b')$ for some $b' < m$.
uses
Finset.mem_image,Finset.mem_range· intro x y a ha b hb hne rw [Finset.mem_image] at ha hb rcases ha with ⟨a', ha', rfl⟩ rcases hb with ⟨b', hb', rfl⟩ rw [Finset.mem_range] at ha' hb'
If $(x, a) \ne (y, b)$, then the indices $mx + a'$ and $my + b'$ are distinct.
By the first helper lemma, $mx + a' \ne my + b'$ provided $(x, a') \ne (y, b')$. If instead $(x, a') = (y, b')$, then $x = y$ and $a' = b'$, which would force $a = b$ and hence $(x, a) = (y, b)$, contradicting the hypothesis.
uses
exists_multi_radio_labeling_path_helper,Fin.ext,Prod.mk.injhave hdiff : m * x.val + a' ≠ m * y.val + b' := by apply exists_multi_radio_labeling_path_helper x.val y.val a' b' m ha' hb' intro h_eq have hxy : x = y := Fin.ext (Prod.mk.inj h_eq).1 have hab : a' = b' := (Prod.mk.inj h_eq).2 subst hxy hab exact hne rfl
The radio condition $(k+1) - \mathrm{dist}(x, y) \le |a - b|$ holds for all distinct pairs $(x, a) \ne (y, b)$.
Applying the second helper lemma to the distinct indices $mx + a'$ and $my + b'$ yields $|a - b| \ge k + 1$. Since graph distance is always non-negative ($\mathrm{dist}(x, y) \ge 0$), linear arithmetic gives $(k+1) - \mathrm{dist}(x, y) \le k + 1 \le |a - b|$, concluding the proof.
uses
exists_multi_radio_labeling_path_diff_gehave hge := exists_multi_radio_labeling_path_diff_ge k (m * x.val + a') (m * y.val + b') hdiff have hdist : 0 ≤ ((SimpleGraph.pathGraph n).dist x y : ℤ) := by positivity linarith
lt_trichotomy- Every pair of elements in a linear order satisfies $a < b$, $a = b$, or $b < a$.
Nat.mul_le_mul_left- Multiplication on the left by a natural number preserves the $\le$ relation: if $a \le b$, then $c \cdot a \le c \cdot b$.
abs_of_neg- The absolute value of a strictly negative number is its negation: if $a < 0$, then $|a| = -a$.
abs_of_pos- The absolute value of a strictly positive number is itself: if $a > 0$, then $|a| = a$.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_range- The range $\{0, \dots, n-1\}$ has cardinality $n$.
Nat.eq_of_mul_eq_mul_left- If $n > 0$ and $n \cdot a = n \cdot b$ for natural numbers, then $a = b$.
Nat.succ_pos- For every natural number $n$, $n + 1 > 0$.
Finset.mem_image- An element belongs to the image $f(s)$ if and only if it equals $f(a)$ for some $a \in s$.
Finset.mem_range- A natural number $m$ belongs to the range $\{0, \dots, n-1\}$ if and only if $m < n$.
exists_multi_radio_labeling_path_helper- If remainders satisfy $a' < m$ and $b' < m$, then $(x, a') \ne (y, b')$ implies $m \cdot x + a' \ne m \cdot y + b'$.
Fin.ext- Two elements of $\mathrm{Fin}(n)$ are equal if and only if their underlying natural numbers are equal.
Prod.mk.inj- An equality of pairs $(a, b) = (c, d)$ implies both $a = c$ and $b = d$.
exists_multi_radio_labeling_path_diff_ge- For natural numbers $u \ne v$, the difference between $(k+1)u$ and $(k+1)v$ as integers satisfies $|(k+1)u - (k+1)v| \ge k + 1$.
- The proof bounds $|a - b| \ge k + 1$ uniformly for all distinct pairs of labels, which is stronger than the required $(k + 1) - \mathrm{dist}(x, y) \le |a - b|$ because graph distances are non-negative. Consequently, no calculation of the actual path distance between vertices is needed.
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.
lemma exists_multi_radio_labeling_path_helper (x y a' b' m : ℕ) (ha : a' < m) (hb : b' < m) (hne : (x, a') ≠ (y, b')) : m * x + a' ≠ m * y + b' := by rcases lt_trichotomy x y with hlt | heq | hgt · have : m * (x + 1) ≤ m * y := Nat.mul_le_mul_left m hlt nlinarith · subst heq intro h have : a' = b' := by omega exact hne (by rw [this]) · have : m * (y + 1) ≤ m * x := Nat.mul_le_mul_left m hgt nlinarithlemma exists_multi_radio_labeling_path_diff_ge (k u v : ℕ) (h : u ≠ v) : (k + 1 : ℤ) ≤ |(((k + 1) * u : ℕ) : ℤ) - (((k + 1) * v : ℕ) : ℤ)| := by push_cast rcases lt_trichotomy u v with hlt | heq | hgt · have : (u : ℤ) < (v : ℤ) := by exact_mod_cast hlt have : (k + 1 : ℤ) * (u : ℤ) < (k + 1 : ℤ) * (v : ℤ) := by nlinarith rw [abs_of_neg (by linarith)] have : (u : ℤ) + 1 ≤ (v : ℤ) := by omega nlinarith · exact (h heq).elim · have : (v : ℤ) < (u : ℤ) := by exact_mod_cast hgt have : (k + 1 : ℤ) * (v : ℤ) < (k + 1 : ℤ) * (u : ℤ) := by nlinarith rw [abs_of_pos (by linarith)] have : (v : ℤ) + 1 ≤ (u : ℤ) := by omega nlinarith/-- Existence witness for the (m,k)-radio labeling predicate on paths; supplies nonemptiness of the set whose infimum is the (m,k)-radio number. -/theorem exists_multi_radio_labeling_path (n m k : ℕ) : ∃ f : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k f := by use fun v => (Finset.range m).image (fun a => (k + 1) * (m * v.val + a)) dsimp [simple_graph_is_multi_radio_labeling] constructor · intro v rw [Finset.card_image_of_injective, Finset.card_range] intro a b h have h2 := Nat.eq_of_mul_eq_mul_left (Nat.succ_pos k) h omega · intro x y a ha b hb hne rw [Finset.mem_image] at ha hb rcases ha with ⟨a', ha', rfl⟩ rcases hb with ⟨b', hb', rfl⟩ rw [Finset.mem_range] at ha' hb' have hdiff : m * x.val + a' ≠ m * y.val + b' := by apply exists_multi_radio_labeling_path_helper x.val y.val a' b' m ha' hb' intro h_eq have hxy : x = y := Fin.ext (Prod.mk.inj h_eq).1 have hab : a' = b' := (Prod.mk.inj h_eq).2 subst hxy hab exact hne rfl have hge := exists_multi_radio_labeling_path_diff_ge k (m * x.val + a') (m * y.val + b') hdiff have hdist : 0 ≤ ((SimpleGraph.pathGraph n).dist x y : ℤ) := by positivity linarith