Loading home page…
Each mission turns a result from a paper or textbook into small Lean 4 statements anyone can tackle.
Campaigns group missions around a shared mathematical goal. Each one tracks a quantity, such as an upper or lower bound. Have a good candidate in mind? Ping us on Slack, Zulip, or WeChat.
Each mission turns a result from a paper or textbook into small Lean 4 statements anyone can tackle.
Campaigns group missions around a shared mathematical goal. Each one tracks a quantity, such as an upper or lower bound. Have a good candidate in mind? Ping us on Slack, Zulip, or WeChat.
The irrationality measure of π quantifies how closely rational numbers can approximate it. This campaign seeks formal proofs of sharper upper bounds, starting with Mahler’s bound of 42.
The sharp Hlawka inequality for Schatten -norms is a cousin of the triangle inequality: it relates the norms of three matrices to the norms of their pairwise sums and their total sum. For complex diagonal matrices, an exact formula for the best possible comparison constant has been proved in Lean for every real . We conjecture that the same formula holds for all .
What is the smallest cutoff for which this formula holds for every real ?
References:
Is every odd number a sum of primes? This campaign tracks formalized proofs of the smallest that suffices.
Schnirelmann (1930) showed some finite works. Vinogradov (1937) showed that three is enough for all sufficiently large odd numbers. Tao (2012) proved unconditionally. Helfgott (2013) proved that every odd number greater than is a sum of three primes, though the proof is still unrefereed. Ideally, we can formalize this statement here. Note that three is optimal: is neither prime nor + prime.
Schoolbook matrix multiplication takes operations. The exponent is the infimum of all such that two matrices can be multiplied in arithmetic operations; trivially , and is conjectured but open.
Strassen gave the first nontrivial bound, , in 1969, and introduced the laser method in 1986 to reach . Coppersmith and Winograd's 1990 bound of stood for two decades. Every subsequent improvement comes from analyzing higher tensor powers of their construction with refined laser-method variants. That line reached in 2025, and the current record is , from August 2026. See Computational complexity of matrix multiplication for the full table. Can we formalize these results and even improve on them?
For many natural chains, convergence to stationarity is not gradual: the distance stays near its maximum for a long time and then collapses to zero in a comparatively negligible window. A deck of cards under riffle shuffles is "not at all mixed" for six shuffles and "essentially mixed" after eight. This abrupt transition is the cutoff phenomenon, discovered by Aldous and Diaconis in the 1980s, and Chapter 18 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develops its theory: precise definitions of cutoff and cutoff windows, the product criterion necessary for cutoff, and complete proofs for two model families — the biased walk on a segment and the lazy hypercube walk, the latter with the sharp location and window , in both total variation and separation. Chapter 19 complements this with lamplighter walks: chains on the wreath-product state space of lamp configurations over a moving lamplighter, whose relaxation, mixing, and separation times are governed — beautifully — by the hitting and cover times of Missions VI. Both chapters are formalized in this mission.
A family of chains is a sequence on state spaces with stationary distributions ; all single-chain quantities acquire an index . As before, , , , and . The family has a cutoff when for every
and a cutoff at with window when and the distance at time tends (in the appropriate limsup/liminf sense) to as and to as . The separation distance from is (Mission III), , and a separation cutoff is defined by the same window template with in place of . From Mission VII, is the relaxation time; from Mission VI, and are the maximal hitting and cover times, and the pairwise distance is from Mission II.
The concrete chains: the lazy biased walk on holds with probability and otherwise steps up with probability , down with probability (reflecting at the endpoints); the lazy hypercube walk is the walk of Mission IV on . The lamplighter chain over a graph has states (lamp configuration in , lamplighter position in ); one step randomizes the current lamp, moves the lamplighter one step of the lazy walk on , and randomizes the new lamp. Its stationary distribution is uniform lamps times the walk's stationary distribution.
Theorem 18.3: the lazy hypercube walk has a cutoff at with window — the family's total variation distance undergoes its full collapse in a window of size around .
The results. Cutoff is the deepest phenomenon in the quantitative theory of Markov chains: it says mixing is a phase transition in time. The hypercube is the fundamental example where everything can be computed — the eigenvalue structure of Mission VII delivers the upper bound and a refined distinguishing-statistic argument (Mission IV) the lower — and the location with window is the sharpest statement of the coupon-collector heuristic. The product condition 18.4 is the basic sanity criterion in the ongoing research program of characterizing cutoff. The lamplighter theorems tie together the entire series: hitting times (Mission VI), cover times (Mission VI), relaxation times (Mission VII), and separation (Missions III, XI) all meet in one family of chains that furnishes counterexamples — for instance, families with total-variation cutoff but no separation cutoff.
Formalizing them. Nothing about cutoff exists in any proof assistant. The definitions themselves (families of chains, windows, limsup/liminf in a real parameter) are a formalization contribution: they force precision about quantifier order that informal texts elide. The hypercube cutoff is a landmark target — a sharp two-sided asymptotic statement, not an inequality.
The upper half of the hypercube cutoff needs the full eigenvalue decomposition of the walk ( with multiplicity , via Mission VII's spectral representation) and the bound summed over binomial coefficients; the lower half needs the Hamming-weight distinguishing statistic pushed to second-order precision (mean and variance at time ). Proposition 18.4 converts an eigenfunction with eigenvalue near into a quantitative anti-concentration statement — the formal content of "a bounded ratio forbids abrupt collapse". Theorem 18.2 rests on a central-limit-flavoured estimate for the biased walk's position, done with fourth-moment bounds rather than the CLT. The lamplighter theorems are the heaviest: the upper bounds couple lamp refreshment with the cover-time of the base walk, the lower bounds run separation-distance and eigenfunction arguments, and all four inequalities must hold with universal constants over an arbitrary growing graph family — the statements quantify over the family, so the proofs must too. The asymptotic language throughout (liminf/limsup over , limits in the window parameter ) exercises the filter library in earnest.
Families are dependent functions ∀ n, Matrix (V n) (V n) ℝ over a sequence of finite state-space types. Cutoff and windows are rendered exactly by the book's Eq. (18.3) and §18.1: the window definition uses Filter.liminf/limsup over composed with limits in the real parameter (through ⌊t n + α w n⌋₊, with the natural-floor convention on negative reals). The mixing-time ratio in the cutoff definition uses real division of the natural-valued mixing times (total division: the hypotheses keep denominators eventually positive). The biased walk's stationary distribution is passed as a hypothesis rather than a closed form. In the lamplighter theorems the comparability constants and the threshold are existentially quantified, with the graph family and its connectivity as hypotheses; the lamplighter matrix and its product stationary distribution are explicit definitions. Lemma 19.3 is stated for a single reversible chain at all times .
Every mixing bound in Missions II–IX ultimately leaned on either coupling or the spectrum, and the spectral route demanded reversibility. Chapter 17 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) opens a third route: martingales — processes whose conditional expected increment vanishes — and the beautiful evolving-set process of Morris and Peres built from them. The payoff theorem of the chapter bounds the mixing time of any lazy irreducible chain by its bottleneck constant, with no reversibility hypothesis anywhere — an honest strengthening of the spectral route through the Cheeger inequality, whose proof is a martingale analysis of a random sequence of sets growing and shrinking under the chain's flow. The same chapter proves the optional stopping theorem in the exact discrete form the rest of the series consumes, and applies the machinery to sharp return-probability estimates for lazy walks.
Throughout, is a chain on a finite state space with stationary distribution ; , , and as in the earlier missions; . The chain is lazy when at every state.
A martingale adapted to the chain is a family of functions of the trajectory up to time such that the conditional expectation of , given the trajectory so far, equals — for a finite chain, a pointwise finite-sum identity. A stopping time is a -valued stopping rule in the sense of Mission III: whether to stop at time depends only on the trajectory up to .
From Mission IV: the edge measure is , with , and the bottleneck constant is the minimum over sets with of . The evolving-set process is the Markov chain on subsets of in which, from the current set , one draws uniform on and passes to the superlevel set
— states currently receiving a large share of the flow out of are likely to join, states receiving little are likely to leave.
Theorem 17.10 (Morris–Peres), the capstone of Chapter 17: for any lazy irreducible chain — reversibility not assumed —
The results. The optional stopping theorem is the workhorse identity of discrete probability — the earlier missions' gambler's-ruin and hitting-time computations are all instances, and Missions XI–XII cite it again. The Morris–Peres theorem is the strongest known elementary relation between geometry and mixing: for reversible chains it recovers the Cheeger-based bound of Mission VII, but it needs no reversibility, and its proof technique — controlling the root as a supermartingale — introduced evolving sets as a tool that has since produced heat-kernel decay, isoperimetric mixing profiles, and bounds for non-reversible and time-inhomogeneous chains well beyond the book.
Formalizing them. Mathlib's martingale library lives in measure-theoretic generality; this mission's chain-adapted martingales are self-contained finite objects (families of functions on trajectory spaces), so the optional stopping theorem here is independent of, and complementary to, the measure-theoretic one. Evolving sets exist in no proof assistant; the process is a genuinely novel formalization target — a Markov chain whose states are Finsets, defined through interval lengths of a uniform variable.
The optional stopping theorem needs the dominated-convergence step (bounded martingale, a.s. finite time) rendered as an elementary tail estimate — the series must be shown summable and equal to by an exchange of finite sums with a limit. The evolving-set transition probabilities are interval lengths: the probability of passing from to is the length of the set of whose superlevel set is exactly , which the formalization encodes by explicit upper and lower thresholds (a min over and a max over of the clipped ratios ); establishing that these lengths sum to one over , and that the process has the two martingale properties, is delicate finite-order-statistics reasoning. The goal theorem then runs a supermartingale argument on : laziness keeps the thresholds in , an expansion estimate converts the bottleneck constant into a per-step multiplicative decay of , and Lemma 17.12 converts that decay into a total-variation bound. Theorem 17.17 composes the same machinery with a Cauchy–Schwarz step. None of this exists in any library; the auxiliary supermartingale lemmas are welcome as separate contributions.
Martingales, stopping times, and stopped expectations are the trajectory-calculus objects of Missions I and III: finite sums over paths weighted by , with expectations over the stopping time as tsums in (non-summable families sum to ; the a.s.-finiteness hypothesis is the statement that the stopping mass sums to ). The evolving-set matrix is defined by the clipped-threshold formula described above — an explicit real matrix on Finset V — and the goal and lemmas assume positive and lazy exactly where the book does. Theorem 17.17 is stated for the lazy walk on a connected graph with positive degrees, with written out. Real-valued bounds on the natural-valued are direct inequalities on the cast, with no hidden rounding.
The Ising model is statistical mechanics' fruit fly: spins on the vertices of a graph, neighbours preferring to agree, a single parameter — the inverse temperature — tuning the strength of that preference. Chapter 15 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) studies the Glauber dynamics for this model and exhibits, on concrete graphs, the phenomenon that made mixing times a subject: a dynamical phase transition. At high temperature (small ) the dynamics mixes in steps on any bounded-degree graph; on the complete graph the same dynamics passes, as crosses an explicit threshold, from mixing to exponentially slow mixing. The chapter also introduces two comparison tools of independent value — the sensitivity of the spectral gap to edge removal, and the block dynamics comparison — and the Kenyon–Mossel–Peres bound for trees, all formalized in this mission.
Spin configurations on a finite graph with vertex set of size and maximum degree are functions assigning to each vertex (encoded over Booleans, ). The Ising model at inverse temperature is the Gibbs distribution
each edge counted once, the normalizing partition function. The Glauber dynamics for picks a uniform vertex and re-samples its spin from conditioned on all other spins — concretely, the new spin at is with probability where is the sum of the neighbouring spins.
The yardsticks are as in the earlier missions: is the total variation distance, , and . From Mission VII: an eigenvalue of a chain is a real with for some nonzero ; is the largest eigenvalue , the spectral gap is , the largest over eigenvalues , and the relaxation time is .
Theorem 15.1, the high-temperature fast-mixing theorem: if then the Glauber dynamics on any graph satisfies
together with its refinement for graphs with all degrees even, where the condition relaxes to .
The results. Theorem 15.1 is the standard fast-mixing criterion for Glauber dynamics, and the model application of the path-coupling technique of Mission VIII. Theorem 15.3 exhibits, in the cleanest possible setting, the correspondence between the static phase transition of the mean-field Ising model and the dynamical transition of its Glauber dynamics — the phenomenon at the heart of Markov-chain approaches to statistical physics. The tree bound of Kenyon–Mossel–Peres and the block-dynamics comparison are the standard tools for spatially structured spin systems; block dynamics in particular is the engine of recursive gap bounds on trees and lattices.
Formalizing them. Nothing about the Ising model, Gibbs distributions, or Glauber dynamics exists in Mathlib. The Gibbs-distribution layer (weights, partition functions, conditional single-site laws with their closed forms) is foundational for any future formalization of statistical mechanics; the phase-transition theorem 15.3(ii) would be, to our knowledge, the first formalized instance of exponentially slow mixing driven by an energy barrier.
The high-temperature theorem is path coupling (Mission VIII) plus the tanh lemma: the one-site coupling of two adjacent configurations contracts the Hamming metric at rate , and every analytic input is in Lemma 15.2 — which is why that elementary lemma is a milestone of its own. The slow-mixing half of Theorem 15.3 runs through the bottleneck bound of Mission IV: the magnetization performs a one-dimensional walk in a double-well free-energy landscape, and the bottleneck at zero magnetization has exponentially small stationary mass — a large-deviations estimate carried out with binomial coefficients. The cycle's lower bound needs Wilson's method (Mission VII) with an explicit eigenfunction. The tree and block theorems are exercises in the comparison technology of Mission VII (Dirichlet forms, canonical paths through block updates); their constants are crude but the inductive structure is delicate. Everything sits on the subtlety that the state space has size , so all "polynomial" bounds are polynomial in , not in the size of the state space.
The Gibbs distribution is defined by explicit finite sums (weight over partition function, total division); no positivity side conditions are needed since the weights are exponentials. The Glauber dynamics is the generic single-site heat bath of Mission II applied to the Ising distribution, so the closed form is a provable lemma, not a definition. Asymptotic statements (, "for sufficiently large ") are rendered with explicit quantifiers and a free precision parameter ; the phase-transition constants are existentially quantified. The tree is encoded as words of length over an alphabet of size ; the block dynamics re-samples a uniformly chosen block from the conditional Gibbs distribution, with the convention that a conditioning of zero mass yields a zero row (total division), which the theorems' hypotheses exclude on the support. The even-degree refinement of the goal is stated as a second conjunct with its own hypothesis.
How many shuffles does a deck of cards need? The question created the modern theory of mixing times: Diaconis and Shahshahani's analysis of random transpositions (1981) and the Bayer–Diaconis "seven shuffles suffice" analysis of the riffle shuffle (1992) are its founding results. Chapters 8 and 16 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) treat the four standard shuffles: random transpositions (pick two cards, swap them), the riffle shuffle (cut and interleave, the Gilbert–Shannon–Reeds model), random adjacent transpositions, and the -reversal chain of segment reversals — the last motivated by genome rearrangement, where a chromosome evolves by reversing segments and the mixing time measures evolutionary distance ("from shuffling cards to shuffling genes").
All four chains are random walks on a symmetric group; decks are encoded as in Mission III, an arrangement being a permutation with position on top. Random transpositions have increment distribution , . The lazy adjacent-transposition walk puts mass on the identity and on each . One inverse riffle shuffle assigns each card an independent uniform bit and moves the cards labeled to the top, preserving relative order; the (forward) riffle shuffle is its time reversal, given by transposing the inverse-shuffle matrix (the stationary distribution being uniform). The -reversal chain on circular arrangements indexed by picks a position and a length uniformly and reverses the segment .
for random transpositions on cards (Corollary 8.10), formalized as: for every there is with for all .
Proposition 8.11 (random transpositions lower bound , via fixed points); Proposition 8.13 (riffle shuffle: ); Proposition 8.14 (riffle shuffle: for large , by the counting bound of Mission IV); the random adjacent transpositions upper bound for large (§16.1.2, display (16.4)) and lower bound (§16.1.3, by following a single card); and Proposition 16.2 (the -reversal chain with satisfies , via conserved adjacencies).
The results. Random transpositions at (the constant here is not sharp; the sharp constant is part of the celebrated Diaconis–Shahshahani cutoff) and riffle at are the emblematic mixing results outside of spin systems; the riffle bound is the mathematical content of "seven shuffles suffice" for . The adjacent-transposition walk at order is the basic example where geometry (diameter ) forces polynomial mixing. The -reversal lower bound is the quantitative starting point of the biological application.
Formalizing them. Random walks on symmetric groups and their mixing are entirely absent from Mathlib; so are the combinatorial devices these proofs run on — the Broder stopping time, rising sequences and the Eulerian-number analysis of riffle shuffles, single-card projections, conserved adjacencies. The riffle shuffle formalization via bit strings and the stable-sort permutation Tuple.sort gives a clean combinatorial model reusable for the cutoff analysis of Mission XI.
Corollary 8.10's route is the Broder strong stationary time: mark cards under a card-and-position scheme and prove that, conditioned on the marked set and its positions, the marked cards are uniformly ordered — an exchangeability induction on top of Mission III's stopping-rule framework; then the coupon-collector-style tail with an extra factor. Proposition 8.11 requires the fixed-point statistic: the expected number of untouched cards after transpositions and a second-moment bound, fed into Proposition 7.8. The riffle upper bound runs through inverse shuffles: after inverse shuffles the deck is a uniform stable sort of -bit labels, and mixing reduces to the birthday problem for labels; formalizing "distinct labels imply uniform order" is the crux. The -reversal lower bound needs a second-moment argument for the number of conserved adjacencies with the exact variance bookkeeping of the book. Throughout, the walk-on-group conventions (left vs right increments, forward vs inverse shuffle) are the classic source of silent errors; the formal statements pin them.
All chains are explicit matrices on Equiv.Perm (Fin n) (or Equiv.Perm (ZMod n) for the circular -reversal chain); increments act on the left, matching Mission I's group-walk convention. The riffle shuffle is defined as the transpose-reversal of the explicit inverse-riffle matrix — the two have equal distance to uniformity by Lemma 4.13 (Mission II), which a solver may use rather than re-derive. Asymptotic statements (, "for sufficiently large ") are spelled out with explicit quantifiers; upper bounds carry a where integer rounding requires it. The -reversal family takes the length function as a hypothesis-carrying parameter with , and its lower bound is a genuine limit statement (Tendsto, distance to stationarity tending to ).
Welcome contributions: exchangeability and projection lemmas for deck chains; Eulerian/rising-sequence counting; the single-card chain projection (reused for Mission XI's cutoff examples).
Why do interior-point methods solve convex programs in Newton steps? Nesterov and Nemirovskii's answer is self-concordance: a convex function whose third derivative is controlled by its second, along every line, admits a Newton analysis with absolute constants and no condition number — and the logarithmic barrier is self-concordant. This mission formalizes §9.6 and Chapter 11 of Boyd & Vandenberghe: the self-concordance calculus, the Newton-decrement analysis, the duality gap along the central path, the per-centering work bound , and the crown result — with the aggressive schedule the barrier method reaches duality gap after
centering steps, each of uniformly bounded Newton cost.
Determine the exact second-order term in the least possible largest factor in a factorization of into distinct integers exceeding , with the proposed rational constant .
The final step from bandits to reinforcement learning: actions now change the state of the world. Chapter 38 of Lattimore–Szepesvári studies online learning in an unknown Markov decision process with states, actions and rewards in . The optimism principle of Mission II scales up: UCRL2 maintains confidence sets over transition kernels, solves an extended MDP by extended value iteration, and recomputes only when a state-action count doubles. The goal theorem: with probability , , where is the diameter of the MDP — sublinear regret with no prior knowledge of the dynamics. The matching lower bound brackets the true complexity of tabular reinforcement learning up to .
Randomness appears to enlarge efficient computation, but the Sipser–Gács–Lautemann theorem places every bounded-error probabilistic polynomial-time language at the second level of the polynomial hierarchy, giving one of complexity theory’s foundational limits on the power of randomization.
How well can any algorithm possibly do? Chapters 13–17 of Lattimore–Szepesvári answer with three matching impossibility results. The divergence decomposition identifies the information a policy collects: . Feeding it into the Bretagnolle–Huber inequality of Mission VI yields the goal theorem — the minimax lower bound over Gaussian bandits, showing MOSS (Mission III) is optimal up to a constant. The same machinery gives the instance-dependent bound of Lai–Robbins type: every consistent policy suffers , certifying the asymptotic optimality of the UCB of Mission III and KL-UCB of Mission IV, and a high-probability lower bound showing the Exp3-IX guarantees of Mission V cannot be improved.
Dantzig–Wolfe decomposition and column generation solve large integer programs by replacing a set of "easy" constraints with a description of its feasible points, and then pricing out the points one at a time. For linear programs this rests on the Minkowski–Weyl representation: every point of a polyhedron is a convex combination of its extreme points plus a nonnegative combination of its extreme rays. For integer programs that representation is not enough. Imposing integrality on the convex multipliers of the extreme points of does not give back the integer program, because an optimal integer point may lie in the interior of .
Lübbecke and Desrosiers, in their survey Selected Topics in Column Generation (Operations Research 53(6), 2005), present discretization (Johnson 1989, Vanderbeck 2000) as the true integer analogue of the decomposition principle. Its basis is their Theorem 1: the integer points of a rational polyhedron are generated by finitely many integer points and finitely many integer rays with integer multipliers. The paper states this result and refers its proof to Nemhauser and Wolsey, Integer and Combinatorial Optimization (1988). It underlies the integer master problem (25) of branch-and-price.
Let be an matrix and an -vector with rational entries. The polyhedron is
and its set of integer points is , the points of whose coordinates are all integers. Because , .
The recession cone of is . An integer ray of is a nonzero vector of in this cone. Extreme rays are not required.
In Lean these are polyhedronP D d, integerPoints D d, recessionConeP D and IsIntegerRay D w in the namespace Lubbecke2005.Discretization, with integer vectors cast to real vectors by castVec.
If , there exist a finite set of integer points and a finite set of integer rays of such that
Since the multipliers are nonnegative integers summing to one over , (24) says that is the union, over , of the translates of the monoid generated by the rays. No bound on or is part of the goal.
If , every point of is a vertex of . In this case convexification and discretization coincide.
The result. Theorem 1 converts an integer program into the integer master program (25) over the multipliers , with one column per generating point and per generating ray. When is bounded the rays disappear, exactly one equals one, and (25) is a linear integer program even for a nonlinear cost . The representation is what makes branching on master variables, and the passage between compact and extensive formulations, well defined in branch-and-price.
Formalizing it. The result is classical (Nemhauser–Wolsey 1988, going back to Giles and Pulleyblank and to Meyer's theorem that the integer hull of a rational polyhedron is a polyhedron). On Prove2Me, the real representation (8) is formalized as LinearOptimization.polyhedron_resolution (Bertsimas–Tsitsiklis Thm 4.15) and the integer hull theorem as LinearOptimization.integer_hull_is_polyhedron (Thm 11.3); both are included as reference items. The convexification counterpart of §3.2, that the Lagrangian dual equals the LP over , is LinearOptimization.lagrangean_dual_eq_lp_over_hull. No machine-checked statement of the integer representation (24), with integer multipliers and integer rays, was found on the platform. The mission produces that statement and, once solved, its proof.
The obvious attempt applies the real representation (8) and rounds. It fails twice. First, the extreme points of need not be integral, and an integer point written as a real combination of vertices and rays has no reason to have integer multipliers. Second, the extreme rays of generate the recession cone over , but the integer points of that cone are not in general nonnegative integer combinations of the (scaled) extreme rays; a generating set of the lattice points of a cone must usually contain non-extreme vectors. The finiteness of is also not automatic: itself is typically infinite, and taking trivializes the statement.
Rationality of the data is essential. For , every integer ray has slope below , so finitely many base points and rays generate only points with for some , while contains for every .
Fin n → ℝ; integer vectors are Fin n → ℤ cast coordinatewise. Both sides of (24) are sets of real vectors.ℚ-valued and cast to ℝ. This is an addition: the paper names no field, and the theorem is false for irrational data (see Difficulty). The cited source, Nemhauser–Wolsey, works with rational data.Fin k and Fin l for existentially chosen ; the finiteness is the content of the theorem. The multiplier vector is written as a pair of ℕ-valued vectors.A formalization with real multipliers would be the resolution theorem (8), already on the platform, and one with or infinite would be trivial; both are excluded by the statement.
Useful infrastructure: lattice points of rational polyhedral cones (Hilbert bases, Gordan's lemma), the integer hull theorem, and the real resolution theorem. A proof of Gordan's lemma for rational cones in this vocabulary would be reusable well beyond this mission. Contributions toward any of these are welcome.
In best arm identification with fixed confidence, a learner samples unknown distributions (arms) sequentially and must, as early as possible, name the arm with the largest mean, while being wrong with probability at most a prescribed risk . The problem models adaptive A/B/n testing, clinical and simulation-based selection among alternatives, and the "ranking and selection" problem of operations research and simulation optimization. The quantity of interest is the sample complexity , the expected number of samples a strategy takes before stopping.
Timeline of the question this mission formalizes:
A canonical one-parameter exponential family is a family of laws , , on with density with respect to a reference measure ; is twice differentiable and strictly convex, and has mean . Bernoulli, Poisson and Gaussian laws with known variance are examples. The divergence is the Kullback–Leibler divergence between the members with means and .
A bandit model assigns a member of the family to each arm. The class consists of models with a unique optimal arm . At each round the learner picks an arm as a function of past observations, observes a reward drawn from that arm's law, and at a stopping time recommends an arm. is the number of draws of arm in the first rounds and its empirical mean.
With and the probability simplex, the characteristic time is
and the maximizer are the optimal proportions of arm draws.
Track-and-Stop combines two ingredients:
For and , Chernoff's stopping rule with combined with C-Tracking or D-Tracking satisfies
for every .
Theorem 1 of the same paper shows for every -PAC strategy, and . Theorem 14 with therefore shows that the lower bound is attained: is the exact asymptotic sample complexity of best arm identification in exponential family models, and Track-and-Stop is asymptotically optimal.
The result is proved in the paper. What is not available is a machine-checked proof for exponential families. The platform already holds a Lean development of the Gaussian case following Lattimore and Szepesvári, Bandit Algorithms, Ch. 33, stated for one existentially chosen policy with a different threshold. This mission asks for the universal statement: every run of either tracking rule, for every exponential family, with the paper's thresholds. The tracking lemmas (Lemmas 15, 7, 8) are deterministic combinatorics and reusable by any tracking-based algorithm.
The obvious argument plugs the almost-sure behaviour of Proposition 13 into an expectation. That step fails: almost-sure convergence of does not control , because on the rare events where the empirical means are far from the stopping time may be very large. Theorem 14 needs a quantitative concentration of on events whose complements have summable probability, which in turn relies on the forced exploration guaranteed by the lower bounds on (the concentration step of App. D, Lemmas 19–20).
A second obstacle is the regularity of : the tracking lemmas only transfer convergence of to convergence of through the continuity of on , proved from the characterization of in §2.2 (Proposition 6). The GLR statistic also needs its closed form (7) near , which requires the empirical means to lie in the interior of the mean space.
BanditPolicy, BanditTrajectory, TrackAndStop). uses Kullback–Leibler divergences of the arm laws over the class and takes values in . Trajectory coordinate is round . An arm never drawn has empirical mean .Best arm identification with fixed confidence is the pure-exploration counterpart of the multi-armed bandit problem. A learner faces unknown reward distributions ("arms"), samples them sequentially, and must stop and name the arm with the largest mean, being wrong with probability at most a prescribed . The question is how many samples this requires. It arises in adaptive A/B testing, in the selection of the best of several simulated systems (ranking and selection in simulation optimization), and in clinical trials that must declare the best treatment with a guaranteed error rate.
Lower bounds for this problem were first stated in terms of the gaps between means (Mannor and Tsitsiklis, 2004). Kaufmann, Cappé and Garivier (2016) replaced ad hoc changes of measure by a single "transportation" lemma relating expected sample counts, Kullback–Leibler divergences and the error probability. Garivier and Kaufmann (COLT 2016, arXiv:1602.04589v2) combine this lemma over all alternative models at once, in the spirit of Graves and Lai (1997), and obtain a lower bound whose constant is exactly matched, as , by their Track-and-Stop strategy. This mission formalizes that lower bound (Theorem 1 of the paper, p. 3).
A canonical one-parameter exponential family is given by a reference measure on , an open interval and a function , twice continuously differentiable on with , such that the laws with density with respect to are probability measures for . The mean of is . Bernoulli laws and Gaussian laws of known variance are examples.
A bandit model is a vector ; arm returns i.i.d. rewards with law and mean . Arm is the unique optimal arm if for every . Let be any set of bandit models of the family each having a unique optimal arm, and put .
A strategy consists of a sampling rule (the arm drawn at round depends, possibly with extra randomization, on the first observations), a stopping time of the natural filtration , and an -measurable decision . It is -PAC on if for every , and . is the number of draws of arm among the first rounds.
Write for the divergence between two arm laws, , and for the probability simplex on the arms. The characteristic time is defined by eq. (1):
For , every -PAC strategy on and every ,
The statement fixes no constant beyond those of the paper, and it holds for every , not only in the limit.
For every with ,
This is Lemma 1 of Kaufmann et al. (2016), which the paper quotes without proof; Theorem 1 follows from it for every alternative simultaneously.
Theorem 1 identifies as the exact problem-dependent complexity of fixed-confidence best arm identification: since , it gives , and the paper's Track-and-Stop strategy attains this rate (the subject of mission IV of this series). The bound also explains which proportions of draws an optimal strategy must use: the maximizer of eq. (1) (mission II).
Both results are proved in the literature. Neither is formalized in the paper's generality. The platform holds the textbook form of Lattimore and Szepesvári (Theorem 33.5), which is stated for an arbitrary class with the weaker constant ; for , , so Theorem 1 is strictly stronger. A formal proof here yields the transportation lemma for exponential families on the platform's infinite-horizon bandit model, which later missions (II–IV, and any lower bound by change of measure) can reuse.
The obvious proof applies the finite-horizon divergence decomposition at a deterministic horizon . That fails here: is random and unbounded, the decision is -measurable, and the relevant divergence is between the laws of the stopped observations. The step from a fixed horizon to a stopping time, together with the data-processing inequality that turns the error guarantees under two models into , is the central difficulty. A second, smaller difficulty is to identify the paper's divergence and its means with the measure-theoretic KL divergence and mean of the arm laws of the exponential family.
Lean namespace OptimalBAI.LowerBound. The bandit protocol is the platform's (BanditAlgorithm.BanditPolicy, banditTrajMeasure, IsBanditStoppingTime, IsSoundBAI, baiComplexity); is the platform's bernoulliRelativeEntropy and is trajPullCount. Conventions:
Fin K, 0-based (the paper's arm is index ); trajectory coordinate is round ;A statement with in place of , or restricted to Gaussian arms, is the platform's existing textbook theorem and does not count as this mission's goal; nor does any version that drops the almost-sure stopping clause or truncates or to real numbers.
Needed infrastructure: the transportation lemma at a stopping time (data processing for KL through an -measurable event, Wald-type identity for the stopped log-likelihood ratio), the identities "mean of " and "KL of two family members ", and . All are reusable beyond this mission. Contributions of any of these lemmas, of eq. (2) alone, or of the Gaussian and Bernoulli special cases as stepping stones are welcome.
Graphs are the most basic combinatorial model of pairwise relations: road networks, frequency interference between radio stations, schedules, circuit layouts. Chapter 5 of Keller and Trotter's Applied Combinatorics (appliedcombinatorics.org, CC BY-SA 4.0) introduces the vocabulary of graph theory and proves its first structural theorems: when a graph can be traversed edge by edge (Euler, 1736), when it can be toured vertex by vertex (Dirac, 1952), when it can be colored with two colors, and how far the chromatic number can drift from the size of the largest clique.
Hamiltonicity is the vertex analogue of Euler's edge-traversal problem and behaves very differently: Euler's problem has a simple parity characterization, while deciding whether a graph has a hamiltonian cycle is NP-complete (Karp, 1972). Sufficient conditions are therefore the main tool, and the minimum-degree condition of Dirac (1952) is the first and most cited of them; Ore's condition (1960) and the Bondy–Chvátal closure (1976) refine it.
A graph consists of a finite vertex set and a set of 2-element subsets of , the edges; means and are adjacent. The degree is the number of neighbours of . The mission uses Mathlib's SimpleGraph V with [Fintype V]; "a graph on vertices" means Fintype.card V = n.
AppliedComb.Graphs.IsHamiltonian).IsEulerian).IsIntervalGraph).In the book's order:
The book's proof of Theorem 5.18 uses only the pigeonhole principle, so none of these results lies on its path. The milestones are the chapter's other theorems about the same objects (cycles, degrees, colorings), and they share the goal's definitions. Cayley's formula (Theorem 5.39, labelled trees on vertices) is already on the platform as GYGraphTheory.cayley_tree_formula and is included as a reference item.
Dirac's theorem is sharp: the complete bipartite graph has minimum degree and no hamiltonian cycle. It is the starting point for the theory of degree conditions for hamiltonicity (Ore, Pósa, Chvátal) and for its extremal and random-graph analogues. Euler's theorem gives linear-time recognition of eulerian graphs; Theorem 5.21 characterizes bipartite graphs; Proposition 5.25 shows that local sparsity (no triangles) does not bound the chromatic number; Theorem 5.28 is the first step towards perfect graphs.
All of these results have been proved for a long time. What is missing is their formalization. Mathlib provides SimpleGraph, chromaticNumber, cliqueNum, degree-sum identities, and definitions of eulerian and hamiltonian walks. It contains no Dirac theorem, no converse of the eulerian degree condition, and no interval-graph theory. On the platform, FamousTheorems.two_colorable_iff_no_odd_cycle_6b is stated with odd closed walks rather than odd cycles, and triangle_free_chromatic_number asserts only rather than with exactly.
For Dirac's theorem the obvious approach, induction on (deleting a vertex), fails: deleting a vertex lowers degrees, and the hypothesis is not inherited by the smaller graph. The degree condition is global, and so is the argument that uses it. In Lean the argument also has to reverse and splice vertex sequences while keeping distinctness and every adjacency along the way. The sufficiency half of Euler's theorem has to construct a circuit that uses every edge exactly once, not just show that one exists up to parity. In Theorem 5.21 the obstruction is a cycle with distinct vertices; producing one from a failed 2-coloring takes more work than producing an odd closed walk. Proposition 5.25 needs a concrete infinite family of graphs and exact computation of both invariants. The upper bound is easy, but the lower bound is not.
SimpleGraph V on a Fintype V. The number of vertices is always Fintype.card V, never a free parameter; in Theorem 5.18 the ceiling is (n + 1) / 2 in , with Fintype.card V = n.Walk.IsHamiltonianCycle, which needs at least three vertices: under that notion Theorem 5.18 would be false for . The goal assumes nonempty, as the book's proof does ( positive). Degenerate readings are ruled out: a predicate satisfied by a cycle through only some vertices, or a statement in which is not the number of vertices, would make the goal vacuous or false, and neither is used here.chromaticNumber (-valued) and is cliqueNum; on finite graphs both agree with the book's definitions (pp. 81, 84).Formalize , the current record from Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog (arXiv:2608.16884, August 2026).
The paper applies the combination-loss laser method of Alman et al. (arXiv:2404.16349), formalized here as the entry, to . That is level instead of 3, with an exact rational certificate of about parameters found by gradient-based optimization and AlphaEvolve. The authors state that the solution and verification code are being prepared for release.
The stochastic multi-armed bandit is the basic model of sequential decision making under uncertainty: a learner repeatedly chooses one of actions, observes a noisy reward for the chosen action only, and must balance exploring poorly known actions against exploiting the one that currently looks best. It underlies adaptive clinical trials, online advertising, recommendation, dynamic pricing and many simulation-optimization procedures in operations research.
The standard algorithm is UCB (Auer, Cesa-Bianchi and Fischer, 2002, doi:10.1023/A:1013689704352), which plays the arm with the largest upper confidence bound on its mean. Its confidence widths grow with the current time (or with a horizon fixed in advance), and its guarantee is on the expected regret, which grows like . Lai and Robbins (1985, doi:10.1016/0196-8858(85)90002-8) showed that logarithmic growth of the expected regret cannot be avoided by a consistent algorithm.
Abbasi-Yadkori, Pál and Szepesvári (NIPS 2011) proved a self-normalized concentration inequality for vector-valued martingales that holds uniformly over time. Section 6 of their paper applies it to the -armed bandit. The resulting confidence intervals depend on neither the horizon nor the current time. The UCB variant built on them, UCB(), has pseudo-regret bounded by a constant, independent of the horizon, on a single event of probability at least . This mission formalizes that section.
There are arms with unknown means . Write for the best mean and for the gap of arm .
Randomness lives on a probability space with a filtration . In round the learner plays an arm that is -measurable and receives the reward . The noise is -measurable and conditionally 1-sub-Gaussian:
The noise need not be independent or identically distributed across rounds, and the rewards need not be bounded.
After rounds, is the number of plays of arm and is the average reward received from it. For a confidence level the confidence width is
with when . UCB() plays, in round , an arm that maximizes ; in particular every arm is played once before any comparison is made. The pseudo-regret after rounds is
This is the linear bandit of the paper with the standard basis of as decision set and .
For every , with probability at least , for all simultaneously,
The right-hand side depends only on the gaps, and .
For any adapted choice of arms (not only UCB()) and every , with probability at least ,
The result. Theorem 7 shows that, once a confidence level is fixed, a UCB-type algorithm can stop paying for exploration after finitely many rounds: with probability the total regret over an infinite horizon is bounded. The paper notes that this does not contradict the Lai–Robbins lower bound, which concerns expected regret; on the failure event of probability the regret may grow linearly. Lemma 6 is the practical content behind this: anytime-valid confidence intervals for adaptively sampled means under martingale noise, usable for stopping rules, best-arm identification and any sequential procedure that inspects its estimates at data-dependent times.
Formalizing it. Both results are proved in the paper's appendices (F and G). No machine-checked proof of either is known to exist. The platform already has the self-normalized martingale bound for and unit sub-Gaussian noise (BanditAlgorithm.self_normalized_martingale_bound, listed here as a reference item), and UCB bounds with horizon-dependent widths and in-expectation or pathwise conclusions. Neither is Theorem 7. The mission produces a formal account of time-uniform confidence intervals for adaptively sampled arm means, and of a regret bound that is uniform in the horizon.
Two points separate this from textbook UCB analyses. First, the number of samples of an arm is itself random and depends on past noise, so a fixed-sample concentration inequality with a union bound over times does not give widths that are free of : a union bound over all costs a factor that diverges. The time-uniform event must come from a maximal (self-normalized) inequality applied to the martingale . Second, the regret statement is uniform in with constants depending on the gaps; converting a condition of the form "" into an explicit bound on requires solving an inequality in which appears both polynomially and inside a logarithm, and the explicit constants and must come out of that step.
The Lean development lives in the namespace ImprovedLinBandits.UCBDelta.
Fin d with 0 < d in the goal; means are μ : Fin d → ℝ, is ⨆ i, μ i (the maximum over a nonempty finite type).t + 1 for t : ℕ: the arm I (t + 1) is ℱ t-measurable, the noise η (t + 1) is ℱ (t + 1)-measurable and satisfies Mathlib's HasCondSubgaussianMGF (ℱ t) … (η (t + 1)) 1 P. Values at index are unused.A trivializing formalization is ruled out: the confidence event is not assumed as a hypothesis of Theorem 7, the i.i.d. bandit model is not substituted for the martingale noise model, and no bound on the means or rewards is imposed.
Useful infrastructure for solvers: the self-normalized bound of Theorem 1 in the scalar case (, , , ), a union bound over arms, and elementary inequalities inverting . Lemmas about pull counts and empirical means under adaptive sampling are reusable beyond this mission and are welcome as contributions.
Nonlinear programming algorithms are routinely advertised as finding a local minimum. Most of them only certify first-order conditions (a KKT point), and the natural next question is whether a given feasible point is in fact a local minimum. For smooth problems where the Hessian is nonsingular this is a second-order test, but in the degenerate case the test itself becomes a combinatorial question about a quadratic form restricted to a cone.
K. G. Murty and S. N. Kabadi (Math. Programming 39 (1987) 117–129) showed that this question is intractable already in its simplest instance: deciding whether is a local minimum of a quadratic form on the nonnegative orthant is NP-complete, and so is deciding whether a square integer matrix is copositive. The paper is the standard reference for the hardness of copositivity testing, which matters for copositive programming, for second-order optimality checks in constrained optimization, and for the complexity of local search in nonconvex optimization.
Let be a real square matrix of order and . The matrix is copositive if for every (coordinatewise). The paper considers the quadratic program
and the following questions, each phrased so that "yes" is the interesting answer:
The source problem is subset sum (Problem 5): given positive integers , is there with ? Let be the total number of digits in the data. The paper fixes an integer and a rational with , and defines functions of nonnegative variables :
, a homogeneous quadratic that agrees with on the set
and . The function is a quadratic form in ; the symmetric matrix , with entries computed explicitly from , is the output of the reduction.
For positive integer data and as above, with the matrix of , the following are equivalent:
This is the mathematical content of Theorems 1–3 and §4: a polynomially computable map from subset sum instances to matrices under which every one of these questions has the answer of the subset sum instance.
The result. The equivalence shows that checking local optimality of a feasible point, checking boundedness of a quadratic objective on a cone, and checking copositivity are all at least as hard as subset sum, hence NP-hard. Through (15) the same holds for local minimality and boundedness of a quartic polynomial with no constraints at all. These facts are the standard justification for why nonconvex solvers settle for KKT points, and the copositivity part underlies the hardness of copositive programming.
The formalization. The paper's claims are proved, and have been cited for decades, but the proof as printed is a sketch: several steps are stated as "clearly" or "it can be verified", and one step of the proof of Theorem 1 (p. 125) is false as written. The inequality for fails for slightly above , and the pointwise implication " on " has an explicit counterexample. The equivalence of Problems 6 and 7 itself survives numerical checks. A machine-checked proof of the goal settles the correctness of the reduction with the paper's own constants. No machine-checked proof of these statements exists on the platform.
The combinatorial direction (a subset sum solution gives a point with ) is a computation. The converse direction carries the content, in two places.
First, passing from to trades the linear penalty for a quadratic one. This is harmless on the box but not for , where is negative. The printed argument handles this coordinate by coordinate and is wrong there; a correct argument has to show that no point of with exists unless a point with does, which requires a global use of the size of .
Second, passing from to requires a quantitative gap: if on then with of only polynomially many bits. Lemma 2 provides such a gap for the unit box and integer matrices, but is not the box and has rational coefficients, so the lemma does not apply verbatim.
The remaining equivalences (Problems 1, 2, 3, 4, 11, 12 for a fixed matrix) follow from homogeneity of the quadratic form and the substitution , and are routine.
The data are natural numbers and is rational; all are cast to in and . The index is Fin n, and the variables of are indexed by Fin n ⊕ Fin n with Sum.elim y s. Standing hypotheses: and (the paper's "all positive integers"); in ; and in . The size counts decimal digits. Problem 1 is local minimality relative to the orthant, Problem 11 is unconstrained local minimality, both in the Euclidean topology. Lemma 2 is stated for integer symmetric (as §4 of the paper says, "as before … symmetric"), with Schrijver's encoding size, since the paper does not define "the size of "; the "optimum is or " is stated as a disjunction without an infimum. The milestones on over assume , which the paper assumes tacitly; the goal needs no such hypothesis.
Not formalized: membership in NP (Lemma 1), the polynomial-time computability of and its encoding size, the NP-completeness of subset sum (cited by the paper from Garey–Johnson), Theorem 4, and any of the words "NP-complete" or "NP-hard". The platform's complexity layer (Turing machines over bitstrings) has no subset sum problem and no encoding of rational matrices. The matrix has rational entries; a positive integer multiple of it is the integer matrix of Theorem 3, has the same answer to every question, and the rescaling is not formalized. The §3 standing assumption "D is not PSD" is not imposed; the constructed matrix can be PSD and the equivalence holds regardless.
The goal is about the explicit matrix , whose entries are given in the definitions; it is not about "some matrix whose quadratic form is ", and the constants and are the paper's explicit bounds, not "sufficiently large" or "for some ". A formalization that quantifies existentially over the matrix or the precision would be trivially true and is ruled out.
Contributions welcome: proofs of the matrix identity and the homogeneity arguments (milestones 6–9), a proof of Lemma 2 (which needs a Cramer/Hadamard bound on basic solutions of the linear complementarity system (9)), and a correct proof of the step. The copositivity definitions and milestones 7–9 are reusable for any later work on copositive programming.
Value-at-Risk (VaR) is the standard regulatory measure of downside risk of a portfolio: the loss level that is exceeded only with a prescribed small probability . Computing it requires the full distribution of asset returns, which is rarely known. In practice one estimates a mean vector and a covariance matrix and then assumes a Gaussian distribution, which understates the probability of large losses when returns are heavy-tailed or skewed.
El Ghaoui, Oks and Oustry (Oper. Res. 51(4), 2003) replace the distributional assumption by a worst case: the VaR is computed against every distribution consistent with the known moments. For known mean and covariance they obtain an exact closed form and several semidefinite (SDP) representations of this worst-case VaR. The SDP forms are what make the approach extend to moment uncertainty (moments only known to lie in a set, §2.2 of the paper) and to robust portfolio optimization. The equivalence between the probabilistic statement and the closed form is also a multivariate one-sided Chebyshev bound, related to Bertsimas and Popescu (SIAM J. Optim. 15(3), 2005; working paper 2000).
There are assets. Their returns over one period form a random vector , and a portfolio earns . The paper restricts to an admissible set that does not contain ; only is used.
The distribution of is unknown except for its mean and covariance matrix , with (positive definite). Let be the set of all probability distributions on with these two moments. For a loss level , the loss set is . The worst-case VaR at level is (Eq. (4))
Further notation: (Eq. (8)); for symmetric matrices, means is positive semidefinite and . The second-moment matrix is (Eq. (6))
For , , and , the following five propositions are equivalent:
In particular
The result. Proposition 2 turns the worst-case VaR into a second-order cone function of , so minimizing it over a polytope of portfolios is a second-order cone program (Eq. (12)). The SDP forms 3 and 5 are the basis of the paper's §2.2–§3: they extend, with the moments only known to lie in a convex set, to a single SDP whose value is the worst-case VaR over that set. Proposition 4 gives a deterministic reading: the worst-case VaR is the largest loss when the return vector is only known to lie in an ellipsoid, which connects distributional robustness to robust optimization with ellipsoidal uncertainty.
Formalizing it. The result is proved in the paper, with two imported steps: strong duality for the moment problem (Smith 1995; Bonnans and Shapiro 2000) and a Slater-type strong duality for the one-constraint quadratic condition. No machine-checked version is known. A formal proof would supply these steps with explicit hypotheses and would produce a Lean statement of the multivariate one-sided Chebyshev (Cantelli) bound with tightness over the full moment class.
The matrix equivalences (2 ⇔ 4 ⇔ 5 and 2 ⇔ 3) are Schur complements and finite-dimensional SDP duality. The difficulty is Proposition 1. The upper bound (Cantelli's inequality for ) handles one direction, but the converse requires tightness: for every below the closed form, a distribution on with exactly the prescribed mean and full covariance matrix that puts probability more than on the loss set. A scalar extremal distribution for does not by itself have the right covariance in the other directions, and a Gaussian does not reach the bound. The paper's route through the moment problem instead needs strong duality between a supremum over measures and an infimum over matrices, which is where the positive definiteness of enters.
EuclideanSpace ℝ (Fin n); is the inner product, and matrices are Matrix (Fin n) (Fin n) ℝ. Matrices of size are indexed by Fin n ⊕ Fin 1 and built with Matrix.fromBlocks (the helper bordered A v c is ). is PosSemidef, is PosDef, is (A * B).trace, and is written .HasMeanCov) contains every Borel probability measure on whose coordinates are square-integrable, with mean and centred covariance . It is not restricted to densities or to Gaussians: the Gaussian class gives a different constant, .IsLUB/IsGLB of one real number (no attainment is claimed). The maxima over , over and over the ellipsoid are IsGreatest.An algorithm for linear programming is strongly polynomial if the number of arithmetic operations it performs is bounded by a polynomial in the dimension of the problem alone (the number of variables and constraints), independently of the bit lengths of the numbers in the input. Many combinatorial optimization problems are linear programs over polyhedra of the form whose constraint matrix has entries , but whose objective vector is an arbitrary rational weight vector. Polynomial-time algorithms for such problems (for instance the ellipsoid-based algorithms of Grötschel, Lovász and Schrijver for maximum-weight cliques in perfect graphs, submodular flows, and matroid polyhedra) have running times that depend on the length of .
Frank and Tardos (Combinatorica 1987) remove this dependence once and for all: they replace by an integral objective whose entries have bits and which has exactly the same optimal solutions and the same optimal dual bases as over every such polyhedron. Any algorithm that is polynomial in and in the length of the objective then becomes strongly polynomial. The tool is simultaneous Diophantine approximation, used through the lattice-basis-reduction algorithm of Lenstra, Lenstra and Lovász (Math. Ann. 1982). The technique extends Tardos's strongly polynomial algorithm for linear programs with small constraint matrices (Oper. Res. 1986), which applies only to explicitly given programs.
For write and ; takes the values .
Decomposition. Fix a positive integer . A decomposition of is an expression
It satisfies condition (iii) if for the vector is nonzero and : the coefficients decrease so quickly that each term is negligible against the previous one.
Preprocessing. Given a rational and , the paper's preprocessing algorithm finds a decomposition with , condition (iii), and the size bound (ii)' , and outputs
Linear programs. Let be an matrix with entries in and . The primal program is and the dual program is . A point is -maximal if . A dual basis is a maximal set of row indices of whose rows are linearly independent; it determines at most one with supported on it (the basic dual solution), and it is an optimal dual basis if that exists and is optimal for the dual program.
For every , with , there is with
such that for every matrix with columns and every : (i) is -maximal if and only if it is -maximal; (ii) a set of rows of is an optimal dual basis for if and only if it is one for . The vector depends on only, not on or .
The result gives a general reduction: whenever a class of polyhedra with constraint matrices admits an optimization algorithm that is polynomial in and in the length of the objective, it admits a strongly polynomial one. The paper applies this to maximum-weight cliques in perfect graphs, optimization over submodular flow polyhedra, and matroid polyhedra membership, and its Section 5 applies the same rounding to the integer programming algorithms of Lenstra and Kannan. The subset-sum corollary (milestone 5) is independently useful: every rational weight function on a finite set can be replaced by an integral one with -bit entries that orders all subset sums identically.
All statements of this mission have been proved on paper since 1987. None is formalized on Prove2Me, and Mathlib contains only the one-dimensional Dirichlet approximation theorem. The mission produces a machine-checked version of the exact statements, with the explicit constants of the paper; the complexity claims (operation counts, strong polynomiality) are not part of it.
The goal combines two independent parts. The number-theoretic part (milestones 1–5) needs a multidimensional Dirichlet theorem, an induction producing the decomposition, and exact inequality chains with the constants and . The linear-programming part (milestones 6–7) needs bounds on the entries of inverses of nonsingular submatrices, the existence of optimal dual solutions supported on a dual basis, LP duality and complementary slackness. The obvious first idea, scaling to an integer vector by a common denominator, preserves every sign but gives no bound on in terms of ; the bound is the content of the theorem. Likewise, rounding each coordinate of separately to a fixed precision does not preserve the sign of when is tiny but nonzero.
Vectors are functions on Fin n: the input is rational (Fin n → ℚ) in the goal, in Theorem 3.3 and in the subset-sum corollary, as in the algorithm's input line; it is real in Theorem 3.1, Lemma 3.2 and Lemma 4.1, as on the page. Integral vectors are Fin n → ℤ, and is a Matrix (Fin m) (Fin n) ℤ with every entry in , cast to ; is unrestricted. Decompositions are indexed by as in the paper. is always the explicit sum , compared with in ; of an integer vector is a natural number (supNorm). Sign equality uses SignType.sign and includes the zero case. Condition (iii) is stated multiplicatively together with , which the paper's quotient presupposes; without Lemma 3.2 fails. An optimal dual basis is a maximal linearly independent set of row indices together with an optimal dual solution supported on it.
Two formalizations would make the goal trivial and are excluded: dropping the bound on (a multiple of then works), and letting depend on and (the goal states before ). The assumption on is part of every Section 4 statement.
A complete development needs a multidimensional pigeonhole argument, determinant and adjugate bounds for matrices, and basic LP duality (strong duality, complementary slackness, basic optimal dual solutions); the last two are reusable across linear-programming missions. Proofs of individual milestones, reusable lemmas on LP duality, and alternative proofs of Dirichlet's theorem are all welcome.
Paging is the problem of managing a fast memory that holds pages out of : when a requested page is not in fast memory (a page fault), some resident page must be evicted, and the cost of an algorithm is its number of faults. Practitioners have many eviction rules. Least-recently-used (LRU) performs well on real workloads but can be times worse than the optimal off-line schedule; the randomized marking algorithm of the same paper is -competitive and so has better worst-case guarantees. Fiat, Karp, Luby, McGeoch, Sleator and Young asked in 1991 whether one on-line algorithm can combine the advantages of several given ones, and answered the question exactly: the attainable combinations of ratios are characterized by one inequality (arXiv:cs/0205038, §6).
The question of combining on-line algorithms has since become a theme of its own: combining heuristics with worst-case-safe algorithms, and, more recently, combining machine-learned predictions with robust fallbacks, both ask for the same kind of guarantee against several reference algorithms at once.
A type consists of servers and a finite set of vertices with the uniform metric: two distinct vertices are at distance . This is paging: vertices are pages, the vertices covered by servers are the pages in fast memory, and a server move is a page fault.
A deterministic on-line algorithm of type has an initial configuration of its servers and, after each request , moves servers so that some server covers ; its configuration after a request sequence depends only on that sequence. Its cost on a request sequence is the total distance its servers travel, i.e. the number of server moves.
For algorithms and of the same type and a constant , is -competitive against if there is a constant such that for every request sequence
A sequence of positive reals is realizable if for every type and every deterministic on-line algorithms of that type there is a deterministic on-line algorithm of the same type that is -competitive against for every .
For and positive reals ,
In the order of the paper's proof:
The result. Theorem 6 is an exact characterization, not a bound: the region of simultaneously attainable ratios against arbitrary deterministic paging algorithms is . For example, any two paging algorithms can be combined into one that is -competitive against each, and no better symmetric pair is possible in general. Combined with Theorem 7 of the same paper (not part of this mission), the same region is attainable against randomized algorithms, which is how LRU's practical behaviour and the marking algorithm's worst-case guarantee can be obtained within constant factors by one algorithm.
Formalizing it. The theorem has been proved since 1991; no machine-checked proof is known. A formal proof produces a reusable notion of competitiveness of one on-line algorithm against another, built on the published KServer_model definitions, and a formal account of the scheduling fact at the core of the sufficiency proof.
Sufficiency looks like an averaging argument, but the combined algorithm cannot simulate the and follow one of them: switching between their configurations costs up to per switch, which no additive constant absorbs. The accounting has to charge each of 's faults to a specific move of a specific , and the charge must be injective; the paper's claim that is at least the number of punishments is where this happens, and it depends on how server intervals are matched. The allocation of faults to algorithms is then a deadline-scheduling problem whose feasibility is exactly , and the floor functions make the counting delicate at the boundary. The paper's own definition of punishment only counts intervals that start with a move, so the first faults of (servers on their initial vertices) need separate treatment; they are absorbed by the additive constant.
Necessity needs the right family of hard instances: the algorithms must never move at the same step, which pins the type to .
The Lean development works in the namespace CompetitivePaging.Combining and imports the published KServer_model definitions: KServer.OnlineAlgorithm k M (a configuration map from request prefixes to Fin k → M with a serving condition) and OnlineAlgorithm.cost. Committed conventions:
k : ℕ and any finite M : Type with a metric in which distinct points are at distance ; realizability quantifies over all of them, never over one fixed type;Trivializing encodings are ruled out: realizability is not stated for a single fixed type, the metric is not the metric of Fin n, and the competitive constant is not allowed to depend on the request sequence.
A complete proof needs the construction of the punishing algorithm as a KServer.OnlineAlgorithm (a lazy, injective algorithm whose moves depend on the prefix and on the 's configurations), the injective charging argument, the scheduling lemma, and the explicit shuttle algorithms. The scheduling lemma and the charging lemma are independent of paging and reusable. Proofs of any milestone are welcome, as are alternative statements of the sufficiency construction.
The Hitchcock transportation problem asks how to ship a commodity from supply points to demand points at minimum total cost. It was posed by Hitchcock in 1941 and is one of the founding problems of linear programming and network optimization; it is solved routinely in logistics, and its structure (a bipartite network with supplies, demands and per-unit costs) recurs in assignment, optimal transport and matching.
The classical algorithms for it, the Ford–Fulkerson primal–dual method among them, augment flow one path at a time. With integral data their number of augmentations is bounded only by the total supply , which is exponential in the number of binary digits used to write the data. Edmonds and Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems (J. ACM 19(2), 1972, doi:10.1145/321694.321699), introduced capacity scaling: solve a coarse version of the problem first, then refine one binary digit at a time. Their Theorem 9 (p. 260) bounds the total number of augmentations by a quantity proportional to times the number of bits of the data, which made the transportation problem, and through standard reductions the minimum-cost flow problem, one of the first network problems with a polynomial-time ("good") algorithm in the sense of Edmonds.
Timeline. Hitchcock (1941) posed the problem; Ford and Fulkerson (1956–1962) gave the primal–dual labeling method and the optimality conditions by node potentials; Edmonds and Karp (1972) gave the scaling method and the bound formalized here. Strongly polynomial algorithms, independent of the size of the numbers, came later (Tardos 1985; Orlin 1988).
The network of Figure 1 (p. 259) has a source , a sink , supply nodes and demand nodes , with . Its arcs are with capacity and cost ; with capacity and cost ; with capacity and cost ; and the return arc with capacity and cost . The supplies and demands are positive integers with .
A flow assigns a nonnegative number to every arc, at most the capacity, with inflow equal to outflow at every node. Write , , ; the value of is , and a maximum flow is one of largest value. Its cost is ; a flow is extreme if no flow of the same value is cheaper. A flow is pseudo-extreme if there are real with for all and whenever .
An augmenting path relative to is a sequence of distinct nodes from to in which each step either follows an arc with spare capacity or traverses backwards an arc carrying positive flow; augmenting pushes the minimum spare amount along it and raises by .
For , Problem has the same network and costs, with capacities and . Choose with every . The scaling method solves Problems in turn. Each phase performs augmentations keeping every flow pseudo-extreme, until no augmenting path is left. Problem starts from the zero flow, and Problem starts from twice the final flow of Problem .
For every run of the scaling method, the total number of flow augmentations satisfies
The bound holds for every admissible for the data and every choice of costs, and is stated with the paper's constant exactly.
The result. Theorem 9 shows that scaling reduces the number of augmentations from order to order , which is roughly the length of the binary encoding of the data. Combined with the cost of one augmentation it gives a polynomial-time algorithm for the transportation problem; through the reduction of minimum-cost flow to transportation (p. 261) it gives one for minimum-cost flow. Capacity and cost scaling became standard techniques in network optimization and in combinatorial optimization generally. Theorem 8 and the pseudo-extreme criterion are the optimality certificates for transportation, a special case of linear-programming complementary slackness.
Formalizing it. The theorem has been proved since 1972. This mission produces a machine-checked version of the bound, of the exact counting argument (eq. (6)) and of the arithmetic estimate that turns it into the stated constant, together with the potential-based optimality conditions for the transportation network. To our knowledge no machine-checked bound on the number of augmentations of a flow algorithm exists on the platform.
The obvious argument bounds the number of augmentations by the increase in flow value, since each augmentation raises the value by a positive integer. Applied to Problem 0 directly this gives only . The scaling bound needs three things that the naive count does not supply. First, doubling the final flow of Problem must give a feasible, still pseudo-extreme, starting flow for Problem (Lemma 3). Second, the gap between that start and the optimum of Problem must be small, which requires the exact maximum-flow value of each scaled problem. Third, the telescoping sum of the gaps must be estimated against with the floors handled exactly. Integrality of every intermediate flow is not assumed; it has to be carried along the run from the integral capacities and the zero start.
Everything lives in the namespace EdmondsKarp.Scaling. Nodes form an inductive type (s, t, src i, dst j). A flow is a structure with components f0, fx, fz, ret for the four arc families, real valued; the infinite capacities are encoded by the absence of an upper bound. IsMaxFlow is a predicate comparing values with every flow, not a supremum. Problem uses natural-number division for . Augmenting paths are lists of distinct nodes from s to t whose consecutive pairs have positive residual amount (resCap, valued in WithTop ℝ); they never use the return arc.
A run of the scaling method (IsScalingRun) is a family of phases for . It starts from in Problem , restarts from in Problem , and advances by one augmentation per step. Every flow is pseudo-extreme, and each phase ends with no augmenting path left. The paper's path-selection rule (minimum weight for the modified reduced costs ) is abstracted to this invariant, which the paper states for it, so every run of the paper's method is covered.
The goal compares the count, cast to , with , using Real.logb 2 and Int.floor. The constant is the printed one; neither nor a weaker constant is acceptable. Positivity of all is a hypothesis, because without it the printed bound is false (for , , , one augmentation is needed and the bound is negative). A formalization in which runs could be empty or never reach a maximum flow would trivialize the goal; the run predicate forbids this, and it is satisfiable (for instance with , , and one augmentation).
A complete development needs max-flow/min-cut for the bipartite network, integrality of flows along a run, the exact value of , the telescoping identity and floor/logarithm estimates. LP duality or complementary slackness is needed only for Theorem 8. The augmenting-path and max-flow lemmas are reusable for other bipartite flow problems. Contributions welcome: proofs of any milestone, and a formalization of the paper's exact path rule showing that it satisfies the invariant.
The economic order quantity (EOQ) is the most widely used formula in inventory management. It assumes that demand is a deterministic constant stream. Real demand is random, and the model that accounts for this, the continuous-review policy with stochastic demand, has no closed-form optimum: for decades its optimal parameters were computed numerically, one instance at a time, which gave little insight into how the stochastic system behaves. Practitioners nevertheless kept using the EOQ quantity in stochastic systems and observed that the cost penalty was small (Wagner, O'Hagan and Lundh 1965; Naddor 1975; Archibald and Silver 1978), without an analytical explanation.
Zheng (Management Science 38(1), 1992) supplied that explanation. By minimising the average cost first over the reorder point and then over the order quantity, he obtained two simple optimality equations and compared the stochastic model with the EOQ model under the same cost structure. One of the results is the goal of this mission: for every leadtime-demand distribution, using the EOQ order quantity in the stochastic system raises the average cost by at most one eighth. The paper extends Federgruen and Zheng (1988), who treated the discrete-demand version of the cost function.
A single item faces demand at rate . Orders are delivered after a fixed leadtime , and stockouts are backordered. Each order costs a fixed . Inventory is held at cost rate per unit and backorders are penalised at cost rate per unit. Let be the demand during a leadtime, with mean . The newsvendor cost
is the rate at which expected inventory costs accrue at time when the inventory position at time is . It is convex, and it is assumed, as in the paper, to attain its minimum at a unique point .
A policy orders units whenever the inventory position falls to the reorder point . Its long-run average cost is
For a fixed let be an optimal reorder point, and set
is the average cost when the reorder point is chosen optimally for ; an order quantity minimising over is the optimal order quantity, and is the optimal cost.
The EOQ model is the special case in which the leadtime demand is the constant . Its cost rate is , and its optimal order quantity is
The subscript marks every object of the EOQ model (, , ).
is the stochastic cost at the EOQ quantity with the reorder point re-optimised for it. The bound holds for every leadtime-demand distribution and every value of the parameters.
In the order the goal's proof uses them:
The theorem is a distribution-free worst-case guarantee for the most common heuristic in inventory practice. It says that the EOQ formula, which needs only the mean demand rate and three cost parameters, loses at most against the true optimum, and that the loss is smaller when is close to or to . Combined with the paper's Theorem 2 (the gap is bounded as grows), it implies that the relative loss vanishes as the fixed ordering cost grows. The milestones along the way (the optimality conditions of Theorem 1, the monotonicity of the optimal reorder point, the comparison of with its EOQ counterpart) are the standard structural facts about continuous systems and are reused throughout the inventory literature.
The result is proved in the paper. No machine-checked version of it, or of the optimality conditions for the continuous cost (1), is known to exist. The platform has related but different formalizations: the discrete cost function with integer (InventoryControl_rqDiscrete), the cost under normal demand (InventoryControl_rq), and the EOQ without backorders (InventoryControl_eoq). A complete development here provides the continuous machinery for an arbitrary leadtime-demand distribution.
The paper's proofs differentiate and twice (Eqs. (4), (5)), which presupposes a leadtime demand with a smooth density. The formalization does not assume one, so that discrete demand, such as the Poisson demand of the paper's own numerical study, is covered. Every step that the paper takes through derivatives, in particular the convexity of and the slope bound , has to be established by other means: through one-sided derivatives or chord arguments for the convex function , whose kinks are where the derivative-based argument breaks. The definition of as a minimiser also means its existence and uniqueness must be proved before any property of , or can be used.
IsQRModel: , the conditions on , and the unique minimiser of (paper, p. 90). is a separate hypothesis. No density is assumed.In stochastic optimization the law of a random return is rarely known exactly, while its mean and variance can be estimated. A robust mean-covariance decision maker therefore evaluates a utility by its worst case
Popescu (Operations Research 55(1), 2007) shows that for large classes of utilities this infinite-dimensional problem collapses to a one-dimensional one. The paper projects multivariate problems to a single dimension (the subject of the first mission of this series) and then asks for which the univariate worst case sits on laws with two support points. This mission formalizes the answer the paper gives for utilities whose marginal utility is decreasing and changes curvature once, with finite limits: log-logistic utilities used in statistics and classification, and catenary-type utilities , each plus a concave quadratic.
The result has a bounded-support precursor: Birge and Dulá (Annals of Operations Research 30, 1991, Theorem 5.1, as cited on p. 102 of Popescu 2007) proved an analogous two-point statement for functions on a bounded interval. Popescu's Proposition 5 is the unbounded version on the whole real line.
Let .
and (lemma1Quad).
partnerPoint) and (prop5Gap).If is differentiable, is inverse S-shaped, and the limits and exist and are finite, then
The result. Through the paper's Proposition 4, two-point support turns the worst-case expected utility over all laws with mean and variance into a minimization over a single parameter of . Combined with the projection property of the paper's Section 2, this gives tractable robust counterparts of multivariate stochastic programs whose objective depends on a linear combination of random returns. Proposition 5 is the paper's sufficient condition that places a concrete class of utilities in this regime; it is also closed under adding any quadratic.
Formalizing it. The result is proved on paper; no machine-checked version is known. The formalization produces a checked characterization of two-point support (Lemma 1), a reusable encoding of convex-concave and S-shaped functions, and a proof of Proposition 5. The printed final step of the paper's proof is incomplete (see Difficulty), so a complete formal proof requires an argument the paper does not spell out.
Conditions (a) and (b) of Lemma 1 come from a sign change of on : the two limits in milestone 4 need a l'Hôpital-type argument and the continuity of a monotone derivative. The central difficulty is condition (c): showing that the quadratic built from a pair lies below on the whole line. The obvious argument takes any zero of and counts the intersections of the linear with the inverse S-shaped . This fails when is affine on an interval: a zero of can then produce a quadratic that coincides with on but crosses above just left of . A proof must therefore choose the zero of , or the pair , with care, and the curvature hypotheses are not strict.
ℝ → ℝ; is deriv u, and the goal assumes Differentiable ℝ u. Finite limits are Tendsto (deriv u) atBot (𝓝 l) and Tendsto (deriv u) atTop (𝓝 l) for some real l; the one-sided limit at is along 𝓝[<] μ.StrictMono); the paper writes "nondecreasing" for the weak notion. Convexity and concavity are ConvexOn/ConcaveOn on the open half-lines Set.Iio x₀, Set.Ioi x₀, as printed.Useful infrastructure: l'Hôpital's rule at infinity (Analysis/Calculus/LHopital), Darboux's theorem for derivatives, the intermediate value theorem, and one-sided limits of monotone functions. The shape definitions of Definition 2 are reusable for S-shaped value functions elsewhere (prospect theory, sigmoidal utilities). Proofs of the milestones, of the goal, and alternative arguments for condition (c) are all welcome. Related platform work: Wasserstein Distributionally Robust Optimization II.
A linear program asks for a point minimizing subject to linear inequalities . Many problems in computational geometry and statistics are linear programs with few variables and very many constraints: separating two point sets by a line or plane, fitting a line in the Chebyshev () norm, finding the smallest disk or ball containing a point set (a related convex problem). For these problems the number of variables is a small constant, and what matters is how the running time grows with .
Nimrod Megiddo showed that for every fixed the problem can be solved in time (J. ACM 31(1), 1984).
Timeline.
Fix . An instance is a matrix and a vector , and its feasible region is the polyhedron . Here is the number of constraints and the number of variables.
The model of computation is the real RAM. A program is a finite list of instructions acting on real registers, integer pointer registers and a memory . It performs exact on reals at unit cost, tests the sign of a real, sets, copies, increments, decrements and compares pointers, and loads and stores through pointers. The input is the standard encoding of in memory: the numbers and , then row by row, then . A program decides an instance within steps with output if it halts on that output after at most steps.
Megiddo's method rests on multidimensional search. There is an unknown point and an oracle that, for any hyperplane , answers whether , or . Given hyperplanes with , the question is how many oracle calls determine the position of relative to all of them. A search strategy is a ternary decision tree: inner nodes are hyperplane queries, leaves carry outputs, and the tree is built from the data alone. For linear programming, is an optimal solution, or a minimizer of the infeasibility function when the system is infeasible. The oracle is implemented by solving problems in variables.
The program and the constant depend on only. No explicit form of is fixed.
The result. For every fixed dimension, linear programming is solvable in time linear in the number of constraints. The algorithm is also strongly polynomial in fixed dimension: its operation count does not depend on the bit size of the data. Deciding whether the optimum is at most is feasibility of together with , so the goal also covers the decision form of optimization. The prune-and-search technique of the paper, which discards a constant fraction of the constraints per round, became a standard tool of computational geometry.
Formalizing it. The result is proved and classical. The platform already has the cases (linear time) and (quadratic time, by Fourier–Motzkin elimination) on the same machine and input encoding (SmaleNinth.real_ram_decides_one_variable_lp_linear, SmaleNinth.real_ram_decides_two_variable_lp_quadratic). No machine-checked proof of the general statement is known. The work consists of the query-complexity layer (milestones 1–6), the convex-analytic correctness of the oracle (milestones 7–9), and a real-RAM implementation with a step count linear in , including linear-time median selection. Alternative proofs, for example through Clarkson's or Seidel's algorithms made deterministic, are welcome for the goal.
The obvious approach is to find the optimum by testing constraints one by one or by eliminating variables. Fourier–Motzkin elimination produces constraints after one step. Pivoting methods have no known bound linear in . The key difficulty is to discard a constant fraction of the constraints using only a constant number of recursive calls in dimension , when no single hyperplane test gives information about more than one constraint. The multidimensional search layer gives this, and it is where the pairing of hyperplanes by slope and the degenerate cases (dependent pairs, zero coefficients) have to be handled exactly. At the machine level, the step count must stay linear in for a fixed program, so every median selection and every recursive call must be implemented within the budget, with the recursion depth depending on only.
SmaleNinth.RAMProgram with RAMDecidesInTime, and the input convention is SmaleNinth.encodeLP (published definitions, reused unchanged). No instruction is added: there is no LP, median, floor or sort primitive. Time is the number of machine steps.compare (a ⬝ᵥ x) b and nothing else, leaves hold fixed values, and correctness is required for every . A tree over arbitrary tests of would make milestones 5 and 6 empty, and it is excluded by the definition.0, 1 of Fin (d + 2), and its is Fin.last d of Fin (d + 1).Online convex optimization is a repeated game between a learner and an adversary. In each round the learner commits to a point of a convex set ; only then is a convex cost function revealed, and the learner pays . The learner is judged by its regret: its total cost minus the total cost of the best fixed point chosen in hindsight. The model covers online portfolio selection, online regression, prediction with expert advice and the analysis of stochastic gradient methods, and it is the standard language of online learning theory.
Zinkevich (ICML 2003) showed that projected gradient descent with step sizes of order has regret for any convex costs with gradients bounded by on a set of diameter , and this rate cannot be improved for linear costs. Hazan, Agarwal and Kale (Machine Learning 69, 2007) asked what curvature buys. Their first result, the subject of this mission, is that the same algorithm with the faster step sizes has regret only logarithmic in once every cost function is -strongly convex. The paper's other three results (the Online Newton Step, Follow the Approximate Leader and Exponentially Weighted Online Optimization, for exp-concave costs) are the subject of the other missions of this series.
Fix and a nonempty, closed, bounded, convex set , with the Euclidean norm (§2.1, p. 171).
IsProj P y z).(IsOGDRun P η f x).
For , cost functions that are -strongly convex on with gradients bounded by on , and any run of Online Gradient Descent whose step after round is , for every and every :
This is LogRegretOCO.OGD.ogd_regret_bound. The constant is the paper's, and at the bound reads .
UnderstandingML.projection_lemma, and is reused as a reference item.The last step of the argument is the harmonic-sum bound , which Mathlib already provides (harmonic_le_one_add_log).
The result. Theorem 1 separates two regimes of online convex optimization: regret for general convex costs and for strongly convex ones, with an algorithm that costs one gradient and one projection per round. Through the online-to-batch conversion, the same step-size schedule gives the rate of stochastic gradient descent on strongly convex objectives. The theorem is also the reference point for the paper's weaker exp-concavity assumption, under which the other three algorithms obtain regret.
Formalizing it. The result is proved and well known; what this mission adds is a machine-checked proof with the paper's exact constant. The Prove2Me platform holds a statement of the textbook version of this theorem (Hazan, Introduction to Online Convex Optimization, Theorem 3.3), OnlineConvexOpt.FirstOrder.online_gradient_descent_strongly_convex_regret, but it is Disproved: its regret is written with a real infimum over the decision set, which Lean evaluates to a junk value. No proved version of the logarithmic bound is on the platform. The strong-convexity inequality, the one-step projected-gradient inequality and the telescoping argument are reusable by every later formalization of gradient methods on the platform.
The argument is short, and its difficulty lies in the bookkeeping. The telescoping sum of squared distances cancels exactly only with the right step-size indexing: the step taken after round must be . Reading Fig. 1 literally with makes the step after round equal to , and the sum then leaves an uncancelled term that the printed bound does not contain. Strong convexity is a statement about the Hessian, so the curvature inequality (1) needs a second-order Taylor expansion along a segment of ; convexity of keeps the segment inside the set where the Hessian bound holds. The projection step needs the obtuse-angle property of Euclidean projection onto a convex set.
Points are EuclideanSpace ℝ (Fin n), so is the Euclidean norm (the sup norm of Fin n → ℝ would change the gradient bound). Cost functions are functions on all of , as the paper's use of gradients and Hessians presupposes; the gradient is Mathlib's gradient, and the Hessian quadratic form is the second Fréchet derivative applied to . Rounds are 1-based: x 0, f 0 and η 1 are never read, and sums run over Finset.Icc 1 T. The run of the algorithm is a predicate on the whole trajectory, required at every round; the projection is a predicate (nearest point of ), which is unique for nonempty closed convex .
Choices and corrections relative to the printed text:
η (t + 1) = 1 / (H * t) for on the step sizes of Fig. 1.A regret bound written with a real ⨅/sInf over , or a bound for an arbitrary sequence satisfying Eq. (2) instead of a run of the paper's algorithm, would not be Theorem 1; the goal quantifies over every comparator in and carries the run predicate, the Hessian hypothesis and the gradient bound. The hypotheses are jointly satisfiable: on the closed unit ball, with meets all of them.
Contributions welcome: proofs of the two inequalities and of the goal; a general projection lemma for positive semidefinite (Lemma 8 in full, needed by the Online Newton Step mission) is reusable beyond this mission.
The iteration of a rational map of the Riemann sphere is the model problem of holomorphic dynamics. The subject was founded by Fatou and Julia around 1918–1920, who split the sphere into a region of stable behaviour and a region of chaotic behaviour, and it was revived in the 1980s by Douady, Hubbard, Sullivan and Thurston. John Milnor's textbook Dynamics in One Complex Variable (3rd ed., Princeton, 2006) is the standard graduate introduction. This mission, the first of a series on the book, formalizes the chain of results that leads from Montel's theorem on normal families to Sullivan's theorem that rational maps have no wandering domains.
Timeline of the results formalized here:
The Riemann sphere is , the one-point compactification of , with the two coordinates (near finite points) and (near ). A rational map is with coprime complex polynomials, ; it acts on in the usual way, and its degree is . Write for the -th iterate.
A family of maps from an open set to is normal if every sequence in it has a subsequence converging locally uniformly in the spherical (chordal) metric. The Fatou set is the set of points having a neighbourhood on which the iterates form a normal family; the Julia set is its complement . A Fatou component is a connected component of . A periodic point of minimal period has multiplier , computed in a local coordinate; it is repelling if and attracting if .
A Fatou component with is a Siegel disk (resp. Herman ring) if is conformally conjugate to an irrational rotation of the unit disk (resp. of a round annulus ).
For a rational map of degree and every Fatou component there are , with
The results. Montel's theorem is the engine of the Fatou–Julia theory: nonemptiness of , density of iterated preimages and density of repelling cycles all rest on it. Theorem 14.1 identifies the non-normality locus with the closure of the repelling cycles, the form in which the Julia set is usually computed and pictured. Sullivan's theorem, combined with Theorem 16.1, gives a complete qualitative picture of the dynamics on the Fatou set; it is used throughout the later theory, e.g. to show that the Julia set of a postcritically finite map without superattracting cycles is the whole sphere (Milnor, Corollary 16.5).
Formalizing them. All results here are classical theorems with published proofs; none is open. A text search of Mathlib at the platform's pinned revision (0df444a) finds no Montel theorem for families of holomorphic maps, no Fatou or Julia sets and no wandering-domain results; it does contain the Schwarz lemma and the hyperbolic metric on the upper half-plane. The remaining work is to formalize the known proofs.
The early milestones need the uniformization-type input that is covered by the disk (via the modular function or an equivalent construction) and Schwarz–Pick-type estimates on hyperbolic surfaces; Mathlib has the Schwarz lemma and the hyperbolic metric of the upper half-plane, but not the Poincaré metric of general hyperbolic domains or covering-space uniformization. Theorem 14.1 requires a quantitative use of Montel's theorem around points of that are not critical values. Theorem 16.1 needs the Denjoy–Wolff-type classification of self-maps of hyperbolic surfaces and the Snail Lemma for parabolic points. The goal is substantially harder: Sullivan's proof uses the measurable Riemann mapping theorem (Morrey–Ahlfors–Bers) to build an infinite-dimensional family of quasiconformal deformations of , contradicting the finite dimensionality of the space of rational maps of degree . The theory of quasiconformal maps and Beltrami equations is absent from Mathlib, and no elementary argument avoiding it is known.
All declarations live in the book-wide namespace MilnorDynamics and build on the published definition files MilnorDynamics_NormalFamilies, MilnorDynamics_RationalMaps and MilnorDynamics_PeriodicPoints; one new definition file, MilnorDynamics_FatouComponents, adds Fatou components, immediate basins, Siegel disks and Herman rings.
OnePoint ℂ; a rational map is a structure of coprime polynomials with , acting on OnePoint ℂ via RationalMap.toFun; the degree is .IsHolomorphicOn). Normality is locally uniform subconvergence in the chordal metric (IsNormalFamily); the Fatou set is defined through the standard charts of .Welcome contributions: the Poincaré metric and Schwarz–Pick on hyperbolic domains, the modular covering of , the degree theory of rational maps, quasiconformal maps and the measurable Riemann mapping theorem. These are reusable far beyond this mission.