OAI.MetricKMedian.FixedBatch.charge_bound: intermediate lemma from OpenAI, The approximation threshold for metric k-median (result family 125)

Open

OAI.MetricKMedian.FixedBatch.charge_bound

by dbenbenn · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

openai-math

An 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); in Lean it is the declaration OAI.MetricKMedian.FixedBatch.charge_bound of lean/OAI/Combinatorics/KMedian/KMedian/Process/FrozenBatchBound.lean at commit adc7f12, ported to Lean 4.33.1 and Mathlib 0df444a.

The statement, as published (namespace OAI.MetricKMedian.FixedBatch, with open Finset PhysicalPotential Analytic):

 theorem charge_bound (D : Actions I E) {x g R b : ℝ} (d : I → ℝ) (S : Finset I)
    (hx0 : 0 ≤ x) (hx1 : x ≤ 1) (hg : 0 ≤ g) (hR : 0 ≤ R)
    (hd0 : ∀ i, 0 ≤ d i) (hdR : ∀ i ∈ S, d i ≤ R)
    (hy : mass g S ≤ 1) (hb0 : 0 ≤ b) (hbR : b ≤ 5*R) (e : E) :
    |charge D x g b d S e| ≤ 8*R

Definitions. The statement is written with OAI.MetricKMedian.PhysicalPotential.mass (definitions bundle OAIQ037K003 of this split); OAI.MetricKMedian.FixedBatch.Actions (definitions bundle OAIQ037K004 of this split); OAI.MetricKMedian.FixedBatch.charge (definitions bundle OAIQ037K021 of this split).

Used by. The proofs of OAI.MetricKMedian.FixedBatch.ideal_local_lower and OAI.MetricKMedian.SparseEnumeratedFixedBatch.expected_frozen_bound of this split import it.

Preamble

import Mathlib
import Definitions.Def_OAIQ037K021

Formal statement

section

attribute [-instance] _root_.OAI.MetricKMedian.FixedBatch.instDecidableEqHeavyAction _root_.OAI.MetricKMedian.FixedBatch.instFintypeHeavyAction
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.FixedBatch
open Finset PhysicalPotential Analytic
variable {I E : Type*} [DecidableEq I] [DecidableEq E] [Fintype E]

omit [Fintype E] in
 theorem charge_bound (D : Actions I E) {x g R b : ℝ} (d : I → ℝ) (S : Finset I)
    (hx0 : 0 ≤ x) (hx1 : x ≤ 1) (hg : 0 ≤ g) (hR : 0 ≤ R)
    (hd0 : ∀ i, 0 ≤ d i) (hdR : ∀ i ∈ S, d i ≤ R)
    (hy : mass g S ≤ 1) (hb0 : 0 ≤ b) (hbR : b ≤ 5*R) (e : E) :
    |charge D x g b d S e| ≤ 8*R := by
  sorry

end MetricKMedian.FixedBatch
end
end

end OAI
end

Source

OpenAI, The approximation threshold for metric k-median (result family 125), OpenAI Math Release, September 24, 2026, https://github.com/openai/math (result family 125; paper: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026/main.pdf; Apache License 2.0); Lean: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Combinatorics/KMedian/KMedian/Process/FrozenBatchBound.lean (declaration OAI.MetricKMedian.FixedBatch.charge_bound)

View graph