OAI.MetricKMedian.RationalPhysicalKernel.step_drift: intermediate lemma from OpenAI, The approximation threshold for metric k-median (result family 125)
ProvedOAI.MetricKMedian.RationalPhysicalKernel.step_driftAn intermediate lemma of the split of OpenAI's proof of OAI.MetricKMedian.main_finite_work, carved from OpenAI's openai/math development for this platform. The statement and its proof are OpenAI's (OpenAI, The approximation threshold for metric k-median (result family 125), OpenAI Math Release, September 24, 2026, result family 125, github.com/openai/math, Apache License 2.0), ported to Lean 4.33.1 and Mathlib 0df444a.
The statement, as published (namespace OAI.MetricKMedian.RationalPhysicalKernel, with open Finset PhysicalPotential FixedBatch Analytic CopyState):
theorem step_drift (d₀ : F → F → ℚ) (location : F → X) (client : X)
(hd₀ : ∀ i j, dist (location i) (location j)=(d₀ i j:ℝ))
(g β p φ P : ℚ) (hp : 0 ≤ p) (hφ : 0 ≤ φ) (hupper : (1+φ)*p ≤ 1)
(s : State F Δ g β) (S S₀ : Finset (Copy (F := F) Δ))
{x h R ζ : ℝ} (hprob : (p:ℝ)=2*h*(g:ℝ))
(hg : 0 < (g:ℝ)) (hg1 : (g:ℝ) ≤ 1) (hunit : (g:ℝ)*(Δ:ℝ)=1)
(hP : 0 < (P:ℝ)) (hP1 : (P:ℝ) ≤ 1/2) (hA : 1 ≤ mass (g:ℝ) s.1)
(hx0 : 0 ≤ x) (hx1 : x ≤ 1) (hh0 : 0 ≤ h) (hh1 : h ≤ 1) (hφ1 : (φ:ℝ) ≤ 1)
(hsmall : (16*((Δ^2+Δ:ℕ):ℝ)+10)*h ≤ savingsFraction (g:ℝ))
(hζ0 : 0 ≤ ζ) (hζ1 : ζ < 1/4) (he : |(P:ℝ)-Analytic.P x| ≤ ζ)
(hactive : S ⊆ s.1) (hS : S ⊆ S₀) (hm₀ : mass (g:ℝ) S₀=1)
(hR0 : 0 ≤ R) (hdR : ∀ i ∈ S₀, dist client (location i.1) ≤ R)
(hR : ∃ i ∈ S₀, R=dist client (location i.1)) :
(step d₀ g β p φ P hp hφ hupper s).expectation (fun t =>
potential (x*Real.exp (-h)) (g:ℝ) (fun i => dist client (location i.1))
(labels g β x (fun (_ : Unit) f => dist client (location f)) t (fun _ => S) ())
(GroupCap.cap R (fun f => dist client (location f)) (integral Δ t.1))) ≤
potential x (g:ℝ) (fun i => dist client (location i.1)) S
(GroupCap.cap R (fun f => dist client (location f)) (integral Δ s.1))+
h*((g:ℝ)+12*ζ)*PhysicalPotential.cost (g:ℝ) (fun i => dist client (location i.1)) S+
batchConstant Δ*h*((φ:ℝ)+h)*R
Definitions. The statement is written with OAI.MetricKMedian.Analytic.P (definitions bundle OAIQ035K000 of this split); OAI.MetricKMedian.CopyState.Copy, OAI.MetricKMedian.CopyState.integral and OAI.MetricKMedian.PhysicalPotential.mass (definitions bundle OAIQ035K003 of this split); OAI.MetricKMedian.FixedBatch.batchConstant (definitions bundle OAIQ035K005 of this split); OAI.MetricKMedian.PhysicalPotential.cost (definitions bundle OAIQ035K007 of this split); OAI.MetricKMedian.GroupCap.cap (definitions bundle OAIQ035K008 of this split); OAI.MetricKMedian.PhysicalPotential.savingsFraction (definitions bundle OAIQ035K016 of this split); OAI.MetricKMedian.RationalPhysicalKernel.Payload and OAI.MetricKMedian.RationalPhysicalKernel.State (definitions bundle OAIQ035K017 of this split); OAI.MetricKMedian.PhysicalPotential.potential (definitions bundle OAIQ035K021 of this split); OAI.MetricKMedian.RationalPhysicalKernel.labels (definitions bundle OAIQ035K044 of this split); OAI.MetricKMedian.SparseIntegerLaw.expectation (definitions bundle OAIQ035K045 of this split); OAI.MetricKMedian.RationalPhysicalKernel.step (definitions bundle OAIQ035K047 of this split).
Used by. The proof of OAI.MetricKMedian.RationalPhysicalKernel.histories_drift of this split imports it.
import Mathlib import Definitions.Def_OAIQ035K044 import Definitions.Def_OAIQ035K045 import Definitions.Def_OAIQ035K047
section
set_option linter.all false
set_option linter.unusedVariables false
set_option linter.unusedTactic false
set_option linter.unreachableTactic false
namespace OAI
section
section
namespace MetricKMedian.RationalPhysicalKernel
open Finset PhysicalPotential FixedBatch Analytic CopyState
variable {F X : Type} [LinearOrder F] [Fintype F] [PseudoMetricSpace X] {Δ : ℕ}
theorem step_drift (d₀ : F → F → ℚ) (location : F → X) (client : X)
(hd₀ : ∀ i j, dist (location i) (location j)=(d₀ i j:ℝ))
(g β p φ P : ℚ) (hp : 0 ≤ p) (hφ : 0 ≤ φ) (hupper : (1+φ)*p ≤ 1)
(s : State F Δ g β) (S S₀ : Finset (Copy (F := F) Δ))
{x h R ζ : ℝ} (hprob : (p:ℝ)=2*h*(g:ℝ))
(hg : 0 < (g:ℝ)) (hg1 : (g:ℝ) ≤ 1) (hunit : (g:ℝ)*(Δ:ℝ)=1)
(hP : 0 < (P:ℝ)) (hP1 : (P:ℝ) ≤ 1/2) (hA : 1 ≤ mass (g:ℝ) s.1)
(hx0 : 0 ≤ x) (hx1 : x ≤ 1) (hh0 : 0 ≤ h) (hh1 : h ≤ 1) (hφ1 : (φ:ℝ) ≤ 1)
(hsmall : (16*((Δ^2+Δ:ℕ):ℝ)+10)*h ≤ savingsFraction (g:ℝ))
(hζ0 : 0 ≤ ζ) (hζ1 : ζ < 1/4) (he : |(P:ℝ)-Analytic.P x| ≤ ζ)
(hactive : S ⊆ s.1) (hS : S ⊆ S₀) (hm₀ : mass (g:ℝ) S₀=1)
(hR0 : 0 ≤ R) (hdR : ∀ i ∈ S₀, dist client (location i.1) ≤ R)
(hR : ∃ i ∈ S₀, R=dist client (location i.1)) :
(step d₀ g β p φ P hp hφ hupper s).expectation (fun t =>
potential (x*Real.exp (-h)) (g:ℝ) (fun i => dist client (location i.1))
(labels g β x (fun (_ : Unit) f => dist client (location f)) t (fun _ => S) ())
(GroupCap.cap R (fun f => dist client (location f)) (integral Δ t.1))) ≤
potential x (g:ℝ) (fun i => dist client (location i.1)) S
(GroupCap.cap R (fun f => dist client (location f)) (integral Δ s.1))+
h*((g:ℝ)+12*ζ)*PhysicalPotential.cost (g:ℝ) (fun i => dist client (location i.1)) S+
batchConstant Δ*h*((φ:ℝ)+h)*R := by
sorry
end MetricKMedian.RationalPhysicalKernel
end
end
end OAI
end