Lemma 2 — Iteration bound
DisprovedCloseGaps.DPA.lemma_2dpap2o-gran-per-chapterp2o-plan-paperp2o-v1
Lemma 2. max{N^u,N^c} ≤ 3 log n for n ≥ 3.
Differences from the source:
- encoding: Stage counts in equations (17) and (21). → Existence of a complete trace and counts satisfying the minimum tests.; reason: Definedness is asserted in the conclusion at the source sizes: every printed real grid count must be an exact positive integer, each stage duration positive, and each stopping minimum attained; no rounding or restriction to executable sizes is introduced.
- reading: Stage counts appear as fixed summation limits and deterministic factors outside expectations in section 5, although the interval widths are random. → A common pair of deterministic counts satisfies the actual stopping tests almost surely on the constructed virtual traces.; reason: This is the literal fixed-count reading of the printed formulas; nominal-width equalities are not assumed, and successful construction is asserted in the conclusion.
- reading: The size parameter has no explicit integrality restriction. → n is real with n ≥ 3.; reason: This retains every stated size, including all integer sizes.
- encoding: Grid prices have indices j=1,...,κ_i. → Grid indices are j=0,...,k-1, with price lo+j(hi-lo)/k.; reason: The same left endpoints are enumerated; only the index origin changes.
- reading: The empirical argmax and argmin do not specify a tie rule. → Choose the least grid index attaining each finite optimum.; reason: This fixes an observable deterministic selection from the source argmax or argmin, without demand information.
- reading: The base-instance estimator is count/Δ and its inventory target is x/T. → For the size-n normalized instance, estimate base demand by count/(nΔ) and compare with x.; reason: Instantiating the pseudocode with inventory nx and dividing its rate estimate and target by n gives this rule; normalized time has horizon one.
Preamble
import Definitions.Def_CloseGaps_DPA_RevenueEvents open MeasureTheory Set open scoped Classical
Formal statement
namespace CloseGaps.DPA
theorem lemma_2 (c : Coefficients) (hc : c.Positive) (x : ℝ) (hx : 0 < x)
(a : Market) (ha : a.Valid) (hw : a.hi - a.lo = 1)
(lam : ℝ → ℝ) (hlam : InClass c a x 1 lam) (n : ℝ) (hn : 3 ≤ n) :
∃ N : StageCounts, (∀ᵐ E ∂clockLaw, completeTrace a lam n x N E) ∧
(max N.Nu N.Nc : ℝ) ≤ 3 * Real.log n := by sorry
end CloseGaps.DPA
Source
Wang, Deng, and Ye (2014), Operations Research 62(2), 318–331, DOI 10.1287/opre.2013.1245, Lemma 2, p. 324 (PDF 7)
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. The theorem quantifies over:
- coefficients with ;
- a real ;
- a market with and ;
- a function in the class InClass;
- a real .
It asserts that there exist natural numbers , depending on all of these, such that
is the infinite product of rate-1 exponential laws on noise sequences .
InClass means all of the following, with :
- is strictly decreasing on , with there;
- and on ;
- some satisfies:
- on ;
- is -Lipschitz on ;
- at each , and its derivative function (taken as where is not differentiable) are both differentiable, and ;
- lies in the open interval , where:
- is the supremum of the maximizers of on ;
- is the supremum of the minimizers of on ;
- each is if its set is empty.
Complete trace. This concerns stages built from .
A stage on with duration and size exists only if all hold:
- equals exactly a positive integer ;
- and ;
- at the grid points for .
It records:
- counts , the increments, truncated at , of an imported counting process along clock times ;
- the gap ;
- the least grid index maximizing , and the least index minimizing ;
- the center , the larger of the two selected points;
- the end clock .
The u-stages are:
- u-stage 1: on , with and , clock ;
- u-stage : on , with:
- ;
- ;
- starting at the previous end clock.
The c-branch after u-stage is:
- c-stage 1: on , with and , starting at u-stage 's end clock;
- c-stage : on , where is the c-selected point, with:
- ;
- .
The complete trace then means all of:
- ;
- u-stages all exist;
- at stage , and at every earlier stage;
- for every :
- ;
- c-stages of branch exist;
- at stage , and at every earlier stage.
So and must be exactly the first stopping indices, almost surely.
Degenerate cases.
- If , no satisfies InClass and the statement is vacuous.
- The width condition already implies .
- The conclusion requires u-stage 1 to exist with positive probability. Its existence does not depend on , and is a probability measure.
- So the conclusion requires, outright, that is exactly a positive integer for , and for . For example, at this needs to be an integer.
- gives .
- No noise-dependent choice of is allowed: is fixed before .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.