AFTD Auto-Formalizing Theoretical Domains

exists_radio_labeling_top_span_eq

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 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.

  1. 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.

    lines 8–14

    uses Finset.card_image_of_injective, Finset.card_range, Nat.eq_of_mul_eq_mul_right, Nat.add_right_cancel

      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) h2
  2. 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.

    lines 20–23

    uses Finset.mem_image

      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
  3. 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.

    lines 24–46

    uses dist_self, Nat.cast_zero, sub_zero, abs_mul, abs_of_nonneg, lt_or_gt_of_ne, abs_of_neg, abs_of_pos

      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
  4. 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.

    lines 47–66

    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
  5. 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.

    lines 70–82

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

      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
  6. 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.

    lines 83–94

    uses Nat.mul_le_mul_right, Nat.sub_le, mul_comm

      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 h5
  7. 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.

    lines 98–104

    uses exists_radio_labeling_top_span_eq_card, exists_radio_labeling_top_span_eq_separation

      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, ?_⟩
  8. 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).

    lines 105–107

    uses exists_radio_labeling_top_span_eq_span_le, multi_label_span_ge_of_radio_labeling_top, le_antisymm

      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
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

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
See it in the graphDiscuss this resultChallenge it