AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_opt_singleton

theoremverified

For k ≥ 1 and configurations a, r : Fin k → Fin m, the offline optimum of the single request r from a is 0 if a i = r i for some i, and 1 otherwise.

Statement

theorem gen_k_server_uniform_opt_singleton {k m : ℕ} (hk : 0 < k) (a r : Fin k → Fin m) :
    gen_k_server_uniform_opt a [r] = if ∃ i, a i = r i then 0 else 1
Source
Sanity check of gen_k_server_uniform_opt (arXiv:2610.37192, Sec. 2): one request costs 0 if the start serves it and 1 otherwise
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • gen_k_server_uniform_optFor a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some…
  • gen_k_server_uniform_path_costFor a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the…

The proof, explained

The theorem is proved by a case split on whether the initial configuration a already serves the single request r (that is, whether a i = r i for some server i). If so, keeping all servers in place incurs a cost of 0, which is optimal since costs are non-negative. If not, moving server 0 to r(0) yields a configuration serving r at distance 1 from a, establishing an upper bound of 1 on the offline optimum. Conversely, any configuration serving r must differ from a, meaning any valid transition incurs a Hamming cost of at least 1; hence the optimum offline cost is exactly 1.

  1. If some server in configuration a already satisfies request r, the stationary schedule [a] serves r with cost 0.

    We branch on whether some server of a matches r (line 4). In the positive branch (hypothesis h), remaining at configuration a throughout the single step serves r via List.Forall₂.cons and List.Forall₂.nil. The transition cost from a to a is hammingDist a a = 0 by hammingDist_self, so the total cost of [a] is 0. This demonstrates that 0 belongs to the set of valid path costs.

    lines 3–10

    uses List.Forall₂.cons, List.Forall₂.nil, hammingDist_self

      open Finset in
      split_ifs with h
      · dsimp [gen_k_server_uniform_opt]
        have h0 : 0 ∈ {c | ∃ os : List (Fin k → Fin m),
            List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by
          refine ⟨[a], ?_, ?_⟩
          · exact List.Forall₂.cons h List.Forall₂.nil
          · simp [gen_k_server_uniform_path_cost, hammingDist_self]
  2. In the first case, the offline optimum cost is 0.

    Since 0 is an achievable path cost, Nat.sInf_le implies that the infimum of valid path costs is at most 0. Because path costs are non-negative integers, linear arithmetic (omega) concludes that the infimum equals 0.

    lines 11–14

    uses Nat.sInf_le

        have le : sInf {c | ∃ os : List (Fin k → Fin m),
            List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 0 :=
          Nat.sInf_le h0
        omega
  3. When no server in a satisfies r, server 0 has a(0) ≠ r(0), and moving server 0 to r(0) produces a configuration y that serves r.

    In the negative branch, no coordinate of a matches r (hypothesis h). Since k > 0, the index 0 exists as ⟨0, hk⟩. If server 0 already matched r(0), that would contradict h, so a(0) ≠ r(0). We define the configuration y by modifying a at server 0 to r(0) using Function.update. By Function.update_self, y matches r at index 0, so y serves r.

    lines 15–24

    uses Function.update_self

      · dsimp [gen_k_server_uniform_opt]
        have hne : a ⟨0, hk⟩ ≠ r ⟨0, hk⟩ := by
          intro heq
          apply h
          exact ⟨⟨0, hk⟩, heq⟩
        let y := Function.update a ⟨0, hk⟩ (r ⟨0, hk⟩)
        have hy_serves : ∃ i, y i = r i := by
          use ⟨0, hk⟩
          dsimp [y]
          rw [Function.update_self]
  4. The Hamming distance between a and y is 1.

    By definition, the Hamming distance is the number of indices where a and y differ. By extensionality and case analysis on whether an index i equals 0, the set of indices where a i ≠ y i is proved to be precisely the singleton {⟨0, hk⟩}, using mem_filter, mem_univ, true_and, mem_singleton, and Function.update_self. The cardinality of this singleton set is 1.

    lines 25–37

    uses mem_filter, mem_univ, true_and, mem_singleton, Function.update_self

        have hy_dist : hammingDist a y = 1 := by
          dsimp [hammingDist]
          have heq : (filter (fun i => a i ≠ y i) univ) = {⟨0, hk⟩} := by
            ext i
            simp only [mem_filter, mem_univ, true_and, mem_singleton]
            by_cases hi : i = ⟨0, hk⟩
            · subst hi
              dsimp [y]
              simp [Function.update_self, hne]
            · dsimp [y]
              simp [hi]
          rw [heq]
          simp
  5. The offline optimum cost is at most 1.

    The single-step schedule [y] serves r because y serves r (via List.Forall₂.cons and List.Forall₂.nil). The cost of moving from a to y is hammingDist a y = 1. Therefore, 1 is an achievable cost, and Nat.sInf_le shows that the infimum of valid path costs is at most 1.

    lines 38–45

    uses List.Forall₂.cons, List.Forall₂.nil, Nat.sInf_le

        have h1 : 1 ∈ {c | ∃ os : List (Fin k → Fin m),
            List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by
          refine ⟨[y], ?_, ?_⟩
          · exact List.Forall₂.cons hy_serves List.Forall₂.nil
          · simp [gen_k_server_uniform_path_cost, hy_dist]
        have hle : sInf {c | ∃ os : List (Fin k → Fin m),
            List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 1 :=
          Nat.sInf_le h1
  6. Any valid schedule has cost at least 1, so the offline optimum cost is 1.

    By le_csInf, to show 1 ≤ sInf, it suffices to show that every valid schedule has cost at least 1. Any schedule serving the single request [r] must be a singleton [y'] where y' serves r. Its path cost is hammingDist a y' + 0 = hammingDist a y' by add_zero. If this cost were strictly less than 1, it would be 0, which by eq_of_hammingDist_eq_zero would force a = y'. But then a would serve r, contradicting the assumption h. Thus every valid schedule has cost at least 1. Combined with the upper bound ≤ 1, linear arithmetic (omega) concludes that the optimum cost is 1.

    lines 46–61

    uses le_csInf, add_zero, eq_of_hammingDist_eq_zero

        have hge : 1 ≤ sInf {c | ∃ os : List (Fin k → Fin m),
            List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by
          apply le_csInf ⟨1, h1⟩
          rintro c ⟨os, hos, rfl⟩
          obtain ⟨y', rfl, hy⟩ : ∃ y', os = [y'] ∧ ∃ i, y' i = r i := by
            cases hos with
            | cons hy hnil =>
              cases hnil
              exact ⟨_, rfl, hy⟩
          simp only [gen_k_server_uniform_path_cost, add_zero]
          by_contra! hc
          have hc0 : hammingDist a y' = 0 := by omega
          have heq := eq_of_hammingDist_eq_zero hc0
          subst heq
          exact h hy
        omega
add_zero
adding zero on the right leaves an element unchanged (a + 0 = a)
eq_of_hammingDist_eq_zero
if two configurations have Hamming distance 0, they are identical
Function.update_self
updating a function at an input to a given value yields that value when evaluated at that input
hammingDist_self
the Hamming distance between any configuration and itself is 0
le_csInf
if a set is nonempty and a is a lower bound for the set, then a ≤ sInf s
List.Forall₂.cons
if a relation holds between heads and elementwise between tails, it holds elementwise between the prepended lists
List.Forall₂.nil
the elementwise relation holds trivially between two empty lists
mem_filter
an element belongs to a filtered sub-finset if and only if it belongs to the finset and satisfies the predicate
mem_singleton
an element belongs to a singleton set {a} if and only if it equals a
mem_univ
every element of a finite type belongs to the universal finset `univ`
Nat.sInf_le
the infimum of a set of natural numbers is at most any member of that set
true_and
the conjunction of True and p is logically equivalent to p

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

theorem gen_k_server_uniform_opt_singleton {k m : ℕ} (hk : 0 < k) (a r : Fin k → Fin m) :    gen_k_server_uniform_opt a [r] = if ∃ i, a i = r i then 0 else 1 := by  open Finset in  split_ifs with h  · dsimp [gen_k_server_uniform_opt]    have h0 : 0 ∈ {c | ∃ os : List (Fin k → Fin m),        List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by      refine ⟨[a], ?_, ?_⟩      · exact List.Forall₂.cons h List.Forall₂.nil      · simp [gen_k_server_uniform_path_cost, hammingDist_self]    have le : sInf {c | ∃ os : List (Fin k → Fin m),        List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 0 :=      Nat.sInf_le h0    omega  · dsimp [gen_k_server_uniform_opt]    have hne : a ⟨0, hk⟩ ≠ r ⟨0, hk⟩ := by      intro heq      apply h      exact ⟨⟨0, hk⟩, heq⟩    let y := Function.update a ⟨0, hk⟩ (r ⟨0, hk⟩)    have hy_serves : ∃ i, y i = r i := by      use ⟨0, hk⟩      dsimp [y]      rw [Function.update_self]    have hy_dist : hammingDist a y = 1 := by      dsimp [hammingDist]      have heq : (filter (fun i => a i ≠ y i) univ) = {⟨0, hk⟩} := by        ext i        simp only [mem_filter, mem_univ, true_and, mem_singleton]        by_cases hi : i = ⟨0, hk⟩        · subst hi          dsimp [y]          simp [Function.update_self, hne]        · dsimp [y]          simp [hi]      rw [heq]      simp    have h1 : 1 ∈ {c | ∃ os : List (Fin k → Fin m),        List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by      refine ⟨[y], ?_, ?_⟩      · exact List.Forall₂.cons hy_serves List.Forall₂.nil      · simp [gen_k_server_uniform_path_cost, hy_dist]    have hle : sInf {c | ∃ os : List (Fin k → Fin m),        List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} ≤ 1 :=      Nat.sInf_le h1    have hge : 1 ≤ sInf {c | ∃ os : List (Fin k → Fin m),        List.Forall₂ (fun o r' => ∃ i, o i = r' i) os [r] ∧ gen_k_server_uniform_path_cost a os = c} := by      apply le_csInf ⟨1, h1⟩      rintro c ⟨os, hos, rfl⟩      obtain ⟨y', rfl, hy⟩ : ∃ y', os = [y'] ∧ ∃ i, y' i = r i := by        cases hos with        | cons hy hnil =>          cases hnil          exact ⟨_, rfl, hy⟩      simp only [gen_k_server_uniform_path_cost, add_zero]      by_contra! hc      have hc0 : hammingDist a y' = 0 := by omega      have heq := eq_of_hammingDist_eq_zero hc0      subst heq      exact h hy    omega
See it in the graphDiscuss this resultChallenge it