Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Xie–Ma–Xin Theorem 4.9: normalized inventory fat-shattering bound

Proved
XMX.nonstationary_inventory_fat_bound

by visuddhi · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

inventorylearning-theoryprobability

For every positive T,U, nonnegative integer lead time L, period k<T, and margin 0<gamma<=1, every gamma-shattered sample for the normalized inventory class has size m<=2/gamma+1. Shattering uses >tau+gamma for high labels and <=tau-gamma for low labels. This concerns the inventory class, not its loss pseudodimension.

Preamble
import Definitions.Def_XMX_NonstationaryInventory
import Definitions.Def_XMX_CyclicPartition

set_option autoImplicit false
open MeasureTheory
Formal statement
namespace XMX

theorem nonstationary_inventory_fat_bound
    (T L : ℕ) (hT : 0 < T) (U γ : ℝ) (hU : 0 < U)
    (hγ : 0 < γ) (hγ1 : γ ≤ 1) (k : ℕ) (hk : k < T)
    (m : ℕ) (x : Fin m → Demand T L U) (τ : Fin m → ℝ)
    (hshatter : Shatters (normalizedInventory T L U k) γ m x τ) :
    (m : ℝ) ≤ 2 / γ + 1 := by sorry

end XMX
Source
Yaqi Xie, Will Ma, Linwei Xin, VC Theory for Inventory Policies, arXiv:2404.11509v3 (2026-02-01), Theorem 4.9 and Section 8.5
Read-back

What the Lean code literally says, in plain math · gpt-6

For every positive natural number TTT, every natural number LLL (including zero), every real U>0U>0U>0, every real γ\gammaγ with 0<γ≤10<\gamma\le10<γ≤1, every natural k<Tk<Tk<T, every natural mmm, every indexed collection x0,…,xm−1x_0,\ldots,x_{m-1}x0​,…,xm−1​ of functions {0,…,T+L−1}→[0,U]\{0,\ldots,T+L-1\}\to[0,U]{0,…,T+L−1}→[0,U], and every collection of real thresholds τ0,…,τm−1\tau_0,\ldots,\tau_{m-1}τ0​,…,τm−1​, suppose the following holds: for every Boolean labeling AAA of {0,…,m−1}\{0,\ldots,m-1\}{0,…,m−1}, there exists a level vector S:{0,…,T+L−1}→[0,(L+1)U]S:\{0,\ldots,T+L-1\}\to[0,(L+1)U]S:{0,…,T+L−1}→[0,(L+1)U] such that, for every iii, the quantity qS(xi)=(max⁡0≤j≤k[Sj−∑j≤r<k+L(xi)r])/((L+1)U)q_S(x_i)=\bigl(\max_{0\le j\le k}[S_j-\sum_{j\le r<k+L}(x_i)_r]\bigr)/((L+1)U)qS​(xi​)=(max0≤j≤k​[Sj​−∑j≤r<k+L​(xi​)r​])/((L+1)U) satisfies τi+γ<qS(xi)\tau_i+\gamma<q_S(x_i)τi​+γ<qS​(xi​) when Ai=trueA_i=\mathrm{true}Ai​=true and qS(xi)≤τi−γq_S(x_i)\le\tau_i-\gammaqS​(xi​)≤τi​−γ when Ai=falseA_i=\mathrm{false}Ai​=false. Then m≤2/γ+1m\le 2/\gamma+1m≤2/γ+1, with mmm interpreted as a real number in this inequality. The level vector may depend on the entire labeling, and the indexed trajectories need not be distinct. All coordinates are zero-based; the sum excludes its upper endpoint and is zero when empty, including the term j=kj=kj=k when L=0L=0L=0. The maximum has k+1k+1k+1 entries, all indices used are in the stated trajectory and level domains because k<Tk<Tk<T, and the normalization denominator is positive. The case m=0m=0m=0 is included.

Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by visuddhi · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me