exists_radio_labeling_top_span_eq
Upper bound: the labeling f(v_i) = {ik, (n+i)k, ..., ((m-1)n+i)k} is an (m,k)-radio labeling of K_n of span k(mn - 1).
Statement
theorem exists_radio_labeling_top_span_eq (n m k : ℕ) (hn : 2 ≤ n) (hk : 1 ≤ k) :
∃ f : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f ∧ multi_label_span f = k * (m * n - 1)- Source
- arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Proposition 2.3, construction
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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).
- multi_label_span_ge_of_radio_labeling_topLower bound: every (m,k)-radio labeling of the complete graph K_n has span at least k(mn - 1).
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- simple_graph_multi_radio_number_topFor n >= 2, k >= 1 and m >= 1, the (m,k)-radio number of the complete graph K_n is k(mn - 1).
The proof, explained
The proof constructs an explicit (m, k)-radio labeling f on the complete graph Kn = ⊤ by assigning to each vertex v the set of m labels {(a * n + v) * k | 0 ≤ a < m}. It verifies that each set has cardinality m by injectivity of the affine mapping, and that the separation condition holds by splitting into the cases x = y (where distance is 0 and the gap is at least 2k ≥ k + 1) and x ≠ y (where distance is 1, non-congruence modulo n ensures distinct prefactors, and the gap is at least k). Finally, since every label is at most ((m - 1)n + (n - 1))k = k(mn - 1), the span is at most k(mn - 1), which matches the known lower bound for Kn to achieve exact equality.
Each vertex label set f(v) contains exactly m elements.
By definition, f(v) is the image of {0, ..., m - 1} under the map a ↦ (a * n + v) * k. By Finset.card_image_of_injective, its size is m provided the map is injective. If (a * n + v) * k = (b * n + v) * k, then since k ≥ 1 we cancel k by Nat.eq_of_mul_eq_mul_right. Cancelling v by Nat.add_right_cancel gives a * n = b * n, and cancelling n ≥ 2 > 0 yields a = b. Thus the image has size m by Finset.card_range.
uses
Finset.card_image_of_injective,Finset.card_range,Nat.eq_of_mul_eq_mul_right,Nat.add_right_canceldsimp [exists_radio_labeling_top_span_eq_f] rw [Finset.card_image_of_injective] · exact Finset.card_range m · intro a b hab have h1 : a * n + (v : ℕ) = b * n + (v : ℕ) := Nat.eq_of_mul_eq_mul_right (by omega) hab have h2 : a * n = b * n := Nat.add_right_cancel h1 exact Nat.eq_of_mul_eq_mul_right (by omega) h2
Two arbitrary distinct labels (x, a) ≠ (y, b) are represented by index witnesses ia, ib < m.
Given vertices x, y and labels a ∈ f(x), b ∈ f(y) with (x, a) ≠ (y, b), unfolding the definition of f and applying Finset.mem_image yields indices ia, ib ∈ {0, ..., m - 1} such that a = (ia * n + x) * k and b = (ib * n + y) * k.
uses
Finset.mem_imageintro x y a ha b hb hne rw [exists_radio_labeling_top_span_eq_f, Finset.mem_image] at ha hb obtain ⟨ia, hia, rfl⟩ := ha obtain ⟨ib, hib, rfl⟩ := hb
The radio separation condition holds when x = y.
When x = y, the distance in the graph is dist(x, x) = 0 by dist_self, so the required lower bound is (k + 1) - 0 = k + 1. Since (x, a) ≠ (x, b), we must have ia ≠ ib. Factoring the difference gives a - b = (ia - ib) * n * k, whose absolute value factors as |ia - ib| * |n| * |k| by abs_mul. The absolute values of n and k are themselves by abs_of_nonneg. Because ia ≠ ib, trichotomy lt_or_gt_of_ne together with abs_of_neg or abs_of_pos implies |ia - ib| ≥ 1. Since n ≥ 2, we have |ia - ib| * n ≥ 2, and since k ≥ 1, multiplying by k yields |a - b| ≥ 2k ≥ k + 1, satisfying the bound.
uses
dist_self,Nat.cast_zero,sub_zero,abs_mul,abs_of_nonneg,lt_or_gt_of_ne,abs_of_neg,abs_of_posby_cases hxy : x = y · subst hxy rw [dist_self, Nat.cast_zero, sub_zero] have hab : ia ≠ ib := by rintro rfl exact hne rfl have h_eq : (↑((ia * n + (x : ℕ)) * k) : ℤ) - ↑((ib * n + (x : ℕ)) * k) = ((ia : ℤ) - (ib : ℤ)) * (n : ℤ) * (k : ℤ) := by push_cast; ring rw [h_eq, abs_mul, abs_mul] have h_n : |(n : ℤ)| = (n : ℤ) := abs_of_nonneg (by omega) have h_k : |(k : ℤ)| = (k : ℤ) := abs_of_nonneg (by omega) rw [h_n, h_k] have h_diff : 1 ≤ |(ia : ℤ) - (ib : ℤ)| := by rcases lt_or_gt_of_ne hab with hlt | hgt · have : (ia : ℤ) - (ib : ℤ) < 0 := by omega rw [abs_of_neg this]; omega · have : 0 < (ia : ℤ) - (ib : ℤ) := by omega rw [abs_of_pos this]; omega have hn' : 2 ≤ (n : ℤ) := by omega have hk' : 1 ≤ (k : ℤ) := by omega have h1 : 2 ≤ |(ia : ℤ) - (ib : ℤ)| * (n : ℤ) := by nlinarith have h2 : 2 * (k : ℤ) ≤ (|(ia : ℤ) - (ib : ℤ)| * (n : ℤ)) * (k : ℤ) := by nlinarith linarith
The radio separation condition holds when x ≠ y.
When x ≠ y, the distance in Kn is 1 by dist_top_of_ne, so the required lower bound is (k + 1) - 1 = k. The integers ia * n + x and ib * n + y cannot be equal, because reducing modulo n via Nat.add_mul_mod_self_right and Nat.mod_eq_of_lt (using x, y < n) would imply x = y by Fin.ext, contradicting x ≠ y. Factoring out k via abs_mul and abs_of_nonneg gives |a - b| = |(ia * n + x) - (ib * n + y)| * k. Since the two integers are distinct, their difference has absolute value at least 1 by lt_or_gt_of_ne, abs_of_neg, and abs_of_pos. Multiplying by k ≥ 1 yields |a - b| ≥ k.
uses
dist_top_of_ne,Nat.cast_one,add_sub_cancel_right,add_comm,Nat.add_mul_mod_self_right,Nat.mod_eq_of_lt,Fin.ext,abs_mul,abs_of_nonneg,lt_or_gt_of_ne,abs_of_neg,abs_of_pos· rw [dist_top_of_ne hxy, Nat.cast_one, add_sub_cancel_right] have h_ne : ia * n + (x : ℕ) ≠ ib * n + (y : ℕ) := by intro h have h_mod : (ia * n + (x : ℕ)) % n = (ib * n + (y : ℕ)) % n := by rw [h] rw [add_comm (ia * n), Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt x.is_lt] at h_mod rw [add_comm (ib * n), Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt y.is_lt] at h_mod exact hxy (Fin.ext h_mod) have h_eq : (↑((ia * n + (x : ℕ)) * k) : ℤ) - ↑((ib * n + (y : ℕ)) * k) = ((ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ)) * (k : ℤ) := by push_cast; ring rw [h_eq, abs_mul] have h_k : |(k : ℤ)| = (k : ℤ) := abs_of_nonneg (by omega) rw [h_k] have h_diff : 1 ≤ |(ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ)| := by rcases lt_or_gt_of_ne h_ne with hlt | hgt · have : (ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ) < 0 := by omega rw [abs_of_neg this]; omega · have : 0 < (ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ) := by omega rw [abs_of_pos this]; omega have hk' : 1 ≤ (k : ℤ) := by omega nlinarith
Reduce the span upper bound to checking the difference between arbitrary labels.
The span is defined by multi_label_span as the nested supremum of b - a over all x, y and a ∈ f(x), b ∈ f(y). Four applications of Finset.sup_le reduce the upper bound multi_label_span f ≤ k(mn - 1) to showing b - a ≤ k(mn - 1) for arbitrary choices. By Finset.mem_image and Finset.mem_range, a = (ia * n + x) * k and b = (ib * n + y) * k with ia, ib < m.
uses
Finset.sup_le,Finset.mem_image,Finset.mem_rangedsimp [multi_label_span] 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 rw [exists_radio_labeling_top_span_eq_f, Finset.mem_image] at ha hb obtain ⟨ia, hia, rfl⟩ := ha obtain ⟨ib, hib, rfl⟩ := hb rw [Finset.mem_range] at hia hib
The difference between any two labels is at most k(mn - 1).
Since y < n and ib < m, we have ib * n + y < ib * n + n = (ib + 1) * n ≤ mn, so ib * n + y ≤ mn - 1. Multiplying by k with Nat.mul_le_mul_right gives (ib * n + y) * k ≤ (mn - 1) * k. Subtracting (ia * n + x) * k ≥ 0 only decreases the value by Nat.sub_le, so the label difference is at most (mn - 1) * k = k * (mn - 1) by mul_comm.
uses
Nat.mul_le_mul_right,Nat.sub_le,mul_commhave hy : (y : ℕ) < n := y.is_lt have h1 : ib * n + (y : ℕ) < m * n := by have : (ib + 1) * n ≤ m * n := Nat.mul_le_mul_right n hib calc ib * n + (y : ℕ) < ib * n + n := by omega _ = (ib + 1) * n := by ring _ ≤ m * n := this have h2 : ib * n + (y : ℕ) ≤ m * n - 1 := by omega have h3 : (ib * n + (y : ℕ)) * k ≤ (m * n - 1) * k := Nat.mul_le_mul_right k h2 have h4 : (ib * n + (y : ℕ)) * k - (ia * n + (x : ℕ)) * k ≤ (ib * n + (y : ℕ)) * k := Nat.sub_le _ _ have h5 : (ib * n + (y : ℕ)) * k - (ia * n + (x : ℕ)) * k ≤ (m * n - 1) * k := h4.trans h3 rw [mul_comm (m * n - 1) k] at h5 exact h5
The candidate labeling f is an (m, k)-radio labeling of Kn.
Using f as the witness, we verify the two requirements of simple_graph_is_multi_radio_labeling: every vertex has exactly m labels by exists_radio_labeling_top_span_eq_card, and the distance-dependent separation condition holds for every pair of distinct labels by exists_radio_labeling_top_span_eq_separation.
uses
exists_radio_labeling_top_span_eq_card,exists_radio_labeling_top_span_eq_separationuse exists_radio_labeling_top_span_eq_f n m k have h_rl : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k (exists_radio_labeling_top_span_eq_f n m k) := by constructor · intro v exact exists_radio_labeling_top_span_eq_card n m k hn hk v · exact exists_radio_labeling_top_span_eq_separation n m k hn hk refine ⟨h_rl, ?_⟩
The span of f is exactly k(mn - 1).
Combining the upper bound span(f) ≤ k(mn - 1) from exists_radio_labeling_top_span_eq_span_le with the general lower bound span(f) ≥ k(mn - 1) for any (m, k)-radio labeling on Kn from multi_label_span_ge_of_radio_labeling_top, antisymmetry of partial orders via le_antisymm shows that the span is exactly k(mn - 1).
uses
exists_radio_labeling_top_span_eq_span_le,multi_label_span_ge_of_radio_labeling_top,le_antisymmhave h_le := exists_radio_labeling_top_span_eq_span_le n m k have h_ge := multi_label_span_ge_of_radio_labeling_top n m k (exists_radio_labeling_top_span_eq_f n m k) h_rl exact le_antisymm h_le h_ge
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 finite set of natural numbers strictly less than n has cardinality n.
Nat.eq_of_mul_eq_mul_right- In natural numbers, if n * m = k * m and m > 0, then n = k.
Nat.add_right_cancel- In natural numbers, if n + m = k + m, then n = k.
Finset.mem_image- An element b belongs to the image of s under f if and only if b = f(a) for some a in s.
dist_self- The distance from any vertex to itself is 0.
Nat.cast_zero- The cast of the natural number 0 into an additive monoid with one is 0.
sub_zero- Subtracting zero from an element leaves it unchanged.
abs_mul- The absolute value of a product is the product of the absolute values.
abs_of_nonneg- If a ≥ 0, then |a| = a.
lt_or_gt_of_ne- In a linear order, if two elements are not equal, then one is strictly less than the other.
abs_of_neg- If a < 0, then |a| = -a.
abs_of_pos- If a > 0, then |a| = a.
dist_top_of_ne- In the complete graph ⊤, the distance between any two distinct vertices is 1.
Nat.cast_one- The cast of the natural number 1 into an additive monoid with one is 1.
add_sub_cancel_right- Adding and then subtracting an element b yields the original element a.
add_comm- Addition is commutative: a + b = b + a.
Nat.add_mul_mod_self_right- Adding a multiple of z does not change the remainder modulo z: (x + y * z) % z = x % z.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Finset.sup_le- The supremum of a function over a finite set is bounded by a if each value is at most a.
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
Nat.mul_le_mul_right- Multiplication by a natural number preserves the ≤ ordering.
Nat.sub_le- Subtracting a natural number from n yields at most n: n - m ≤ n.
mul_comm- Multiplication is commutative: a * b = b * a.
exists_radio_labeling_top_span_eq_card- For each vertex v, the labeling set f(v) has cardinality m.
exists_radio_labeling_top_span_eq_separation- The labeling f satisfies the radio separation condition (k + 1) - dist(x, y) ≤ |a - b| for all distinct pairs of labeled vertices.
exists_radio_labeling_top_span_eq_span_le- The span of the candidate multi-labeling f on Kn is at most k(mn - 1).
multi_label_span_ge_of_radio_labeling_top- Any (m, k)-radio labeling of the complete graph Kn has span at least k(mn - 1).
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
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.
open SimpleGraphdef exists_radio_labeling_top_span_eq_f (n m k : ℕ) (v : Fin n) : Finset ℕ := (Finset.range m).image (fun a => (a * n + (v : ℕ)) * k)lemma exists_radio_labeling_top_span_eq_card (n m k : ℕ) (hn : 2 ≤ n) (hk : 1 ≤ k) (v : Fin n) : (exists_radio_labeling_top_span_eq_f n m k v).card = m := by dsimp [exists_radio_labeling_top_span_eq_f] rw [Finset.card_image_of_injective] · exact Finset.card_range m · intro a b hab have h1 : a * n + (v : ℕ) = b * n + (v : ℕ) := Nat.eq_of_mul_eq_mul_right (by omega) hab have h2 : a * n = b * n := Nat.add_right_cancel h1 exact Nat.eq_of_mul_eq_mul_right (by omega) h2lemma exists_radio_labeling_top_span_eq_separation (n m k : ℕ) (hn : 2 ≤ n) (hk : 1 ≤ k) : ∀ (x y : Fin n), ∀ a ∈ exists_radio_labeling_top_span_eq_f n m k x, ∀ b ∈ exists_radio_labeling_top_span_eq_f n m k y, (x, a) ≠ (y, b) → (k : ℤ) + 1 - ((⊤ : SimpleGraph (Fin n)).dist x y : ℤ) ≤ |(a : ℤ) - (b : ℤ)| := by intro x y a ha b hb hne rw [exists_radio_labeling_top_span_eq_f, Finset.mem_image] at ha hb obtain ⟨ia, hia, rfl⟩ := ha obtain ⟨ib, hib, rfl⟩ := hb by_cases hxy : x = y · subst hxy rw [dist_self, Nat.cast_zero, sub_zero] have hab : ia ≠ ib := by rintro rfl exact hne rfl have h_eq : (↑((ia * n + (x : ℕ)) * k) : ℤ) - ↑((ib * n + (x : ℕ)) * k) = ((ia : ℤ) - (ib : ℤ)) * (n : ℤ) * (k : ℤ) := by push_cast; ring rw [h_eq, abs_mul, abs_mul] have h_n : |(n : ℤ)| = (n : ℤ) := abs_of_nonneg (by omega) have h_k : |(k : ℤ)| = (k : ℤ) := abs_of_nonneg (by omega) rw [h_n, h_k] have h_diff : 1 ≤ |(ia : ℤ) - (ib : ℤ)| := by rcases lt_or_gt_of_ne hab with hlt | hgt · have : (ia : ℤ) - (ib : ℤ) < 0 := by omega rw [abs_of_neg this]; omega · have : 0 < (ia : ℤ) - (ib : ℤ) := by omega rw [abs_of_pos this]; omega have hn' : 2 ≤ (n : ℤ) := by omega have hk' : 1 ≤ (k : ℤ) := by omega have h1 : 2 ≤ |(ia : ℤ) - (ib : ℤ)| * (n : ℤ) := by nlinarith have h2 : 2 * (k : ℤ) ≤ (|(ia : ℤ) - (ib : ℤ)| * (n : ℤ)) * (k : ℤ) := by nlinarith linarith · rw [dist_top_of_ne hxy, Nat.cast_one, add_sub_cancel_right] have h_ne : ia * n + (x : ℕ) ≠ ib * n + (y : ℕ) := by intro h have h_mod : (ia * n + (x : ℕ)) % n = (ib * n + (y : ℕ)) % n := by rw [h] rw [add_comm (ia * n), Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt x.is_lt] at h_mod rw [add_comm (ib * n), Nat.add_mul_mod_self_right, Nat.mod_eq_of_lt y.is_lt] at h_mod exact hxy (Fin.ext h_mod) have h_eq : (↑((ia * n + (x : ℕ)) * k) : ℤ) - ↑((ib * n + (y : ℕ)) * k) = ((ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ)) * (k : ℤ) := by push_cast; ring rw [h_eq, abs_mul] have h_k : |(k : ℤ)| = (k : ℤ) := abs_of_nonneg (by omega) rw [h_k] have h_diff : 1 ≤ |(ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ)| := by rcases lt_or_gt_of_ne h_ne with hlt | hgt · have : (ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ) < 0 := by omega rw [abs_of_neg this]; omega · have : 0 < (ia * n + (x : ℕ) : ℤ) - (ib * n + (y : ℕ) : ℤ) := by omega rw [abs_of_pos this]; omega have hk' : 1 ≤ (k : ℤ) := by omega nlinarithlemma exists_radio_labeling_top_span_eq_span_le (n m k : ℕ) : multi_label_span (exists_radio_labeling_top_span_eq_f n m k) ≤ k * (m * n - 1) := by dsimp [multi_label_span] 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 rw [exists_radio_labeling_top_span_eq_f, Finset.mem_image] at ha hb obtain ⟨ia, hia, rfl⟩ := ha obtain ⟨ib, hib, rfl⟩ := hb rw [Finset.mem_range] at hia hib have hy : (y : ℕ) < n := y.is_lt have h1 : ib * n + (y : ℕ) < m * n := by have : (ib + 1) * n ≤ m * n := Nat.mul_le_mul_right n hib calc ib * n + (y : ℕ) < ib * n + n := by omega _ = (ib + 1) * n := by ring _ ≤ m * n := this have h2 : ib * n + (y : ℕ) ≤ m * n - 1 := by omega have h3 : (ib * n + (y : ℕ)) * k ≤ (m * n - 1) * k := Nat.mul_le_mul_right k h2 have h4 : (ib * n + (y : ℕ)) * k - (ia * n + (x : ℕ)) * k ≤ (ib * n + (y : ℕ)) * k := Nat.sub_le _ _ have h5 : (ib * n + (y : ℕ)) * k - (ia * n + (x : ℕ)) * k ≤ (m * n - 1) * k := h4.trans h3 rw [mul_comm (m * n - 1) k] at h5 exact h5theorem exists_radio_labeling_top_span_eq (n m k : ℕ) (hn : 2 ≤ n) (hk : 1 ≤ k) : ∃ f : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f ∧ multi_label_span f = k * (m * n - 1) := by use exists_radio_labeling_top_span_eq_f n m k have h_rl : simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k (exists_radio_labeling_top_span_eq_f n m k) := by constructor · intro v exact exists_radio_labeling_top_span_eq_card n m k hn hk v · exact exists_radio_labeling_top_span_eq_separation n m k hn hk refine ⟨h_rl, ?_⟩ have h_le := exists_radio_labeling_top_span_eq_span_le n m k have h_ge := multi_label_span_ge_of_radio_labeling_top n m k (exists_radio_labeling_top_span_eq_f n m k) h_rl exact le_antisymm h_le h_ge