All missions

Motivation

Part II of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) turns from the theory of learnability to hypothesis classes that can actually be learned by algorithms, and it starts with the family that almost every practical method is built on: linear predictors. Chapter 9 introduces the affine functions $L_d$ and the three classes obtained by composing them with a link: halfspaces for classification, linear regression for real-valued prediction, and logistic regression in between. For each class it gives an ERM algorithm and the guarantee that goes with it. For halfspaces in the separable case the algorithm is Rosenblatt's Perceptron, and the guarantee is the classical mistake bound (Theorem 9.1): the number of updates is at most $(RB)^2$, where $R$ bounds the data and $B$ is the norm of the smallest vector separating it with margin one. The chapter then computes the VC-dimension of halfspaces (Theorems 9.2 and 9.3), which by the fundamental theorem of Mission IV makes them learnable, derives the Least Squares normal equations for regression, and observes that the logistic loss is convex, the property later chapters exploit.

Setting

Vectors live in $\mathbb{R}^d$ with its Euclidean inner product and norm. The affine functions are $h_{w,b}(x) = \langle w, x\rangle + b$, homogenous when $b = 0$; a halfspace hypothesis is $x \mapsto \operatorname{sign}(\langle w, x\rangle + b)$, formalized as a Boolean predictor that is true exactly when $\langle w, x\rangle + b > 0$ (the book leaves $\operatorname{sign}(0)$ unspecified; the VC computations do not depend on the convention). A sample $(x_1, y_1), \dots, (x_m, y_m)$ with labels $y_i \in \{\pm 1\}$ is separable if some $w$ has $y_i\langle w, x_i\rangle > 0$ for all $i$; the constants of Theorem 9.1 are $B = \inf\{\|w\| : \forall i,\ y_i\langle w, x_i\rangle \ge 1\}$ and $R = \max_i \|x_i\|$. The Batch Perceptron starts at $w^{(0)} = 0$ and, while some example has $y_i\langle w^{(t)}, x_i\rangle \le 0$, adds $y_i x_i$; since the algorithm may pick any mistaken example, a run is any sequence of updates obeying this rule, and the theorem is stated for all runs. For regression the loss is $(h(x) - y)^2$ and the Least Squares system is $Aw = b$ with $A = \sum_i x_i x_i^\top$, written as the linear map $w \mapsto \sum_i \langle x_i, w\rangle x_i$, and $b = \sum_i y_i x_i$. The logistic function is $\varphi_{sig}(z) = 1/(1 + e^{-z})$ and the logistic loss is $\log(1 + \exp(-y\langle w, x\rangle))$. The learning-theoretic notions (ERM, PAC and agnostic PAC learnability, VC-dimension) are those of Missions I and IV.

Formalization targets

Goal: Theorem 9.1 (Perceptron convergence)

For a separable sample with labels in $\{\pm 1\}$, every run of the Batch Perceptron of $T$ iterations satisfies $T \le (RB)^2$, and some run of at most $(RB)^2$ iterations ends with $y_i\langle w^{(T)}, x_i\rangle > 0$ for every $i$.

Milestones

Equation (9.1). A sample is separable if and only if some $w$ satisfies $y_i\langle w, x_i\rangle \ge 1$ for all $i$.

Theorem 9.2. The VC-dimension of the homogenous halfspaces in $\mathbb{R}^d$ is $d$.

Theorem 9.3. The VC-dimension of the halfspaces in $\mathbb{R}^d$ is $d+1$.

Least Squares (9.6). The system $Aw = b$ always has a solution, and $w$ solves it if and only if $h_w$ is an ERM hypothesis for the squared loss over the homogenous linear predictors.

Further items: Exercise 9.3, the tightness of Theorem 9.1 (for every $m$ a sample with $R \le 1$, $(BR)^2 \le m$ and a run of exactly $m$ updates); the learnability of halfspaces by ERM, a consequence of Theorem 9.3 and the fundamental theorem; Exercise 9.2, $A$ is invertible iff the $x_i$ span $\mathbb{R}^d$; and the convexity of the logistic loss in $w$.

Significance

The Perceptron bound is one of the oldest results of learning theory (Novikoff 1962) and the model for every mistake bound in the online-learning chapters: it is independent of the dimension and of the number of examples, depending only on the geometry of the data through $R$ and $B$. Theorems 9.2 and 9.3 are the first VC-dimension computations of a class used in practice and give, through Theorem 6.8, the sample complexity $\Theta((d + \log(1/\delta))/\epsilon)$ of learning halfspaces. The normal equations are the algorithmic content of linear regression, and the convexity of the logistic loss is why logistic regression is tractable in the nonseparable case, where ERM for halfspaces with the 0–1 loss is hard.

Nothing here is machine-checked in this form. Mathlib has the inner-product geometry, the Cauchy–Schwarz inequality, linear algebra of finite-dimensional spaces and convexity of compositions, but neither the Perceptron nor the VC-dimension of halfspaces.

Difficulty

Equation (9.1) is a rescaling and the intended entry point. The convexity of the logistic loss is the composition of the convex function $\log(1 + e^{-t})$ with the linear map $w \mapsto y\langle w, x\rangle$. Exercise 9.2 is the identification of the kernel of $\sum_i \langle x_i, \cdot\rangle x_i$ with the orthogonal complement of the span. The normal equations require showing that a convex quadratic is minimized exactly where its gradient vanishes, and that $b$ lies in the range of $A$, which is the span of the $x_i$. Theorem 9.1 is the book's proof: by induction on the run, $\langle w^*, w^{(T)}\rangle \ge T$ and $\|w^{(T)}\|^2 \le TR^2$ for any feasible $w^*$, then Cauchy–Schwarz, and finally the passage from a feasible $w^*$ to the infimum $B$; the existence clause follows because a run can be extended as long as the stopping condition fails and all runs are bounded. Theorem 9.2 is the linear-dependence argument of the book, with a case analysis on the signs of the coefficients and on which side is nonempty, and the shattering of the standard basis; Theorem 9.3 lifts it to $\mathbb{R}^{d+1}$ by appending a constant coordinate. The learnability of halfspaces is Theorem 6.7 applied to a class that must be shown measurable, nonempty, of finite VC-dimension and pointwise separable; the last needs rational approximations $(w_n, b_n)$ in which the offset moves below $b$ more slowly than $w_n$ approaches $w$, so that boundary points keep their label.

Formalization scope

Halfspaces are Boolean predictors with $\operatorname{sign}(0)$ negative; the classes are sets of functions, so the VC-dimension is that of Mission IV. The Perceptron is a relation on sequences, not a program: this captures the algorithm's freedom to choose any mistaken example and makes the bound apply to all implementations. $B$ is an infimum, which is attained (the feasible set is closed and the norm is coercive), but the theorem does not need attainment. $R$ is a real supremum over the finite index set, equal to $0$ for the empty sample, where every run has length $0$. The Least Squares statement is about the homogenous class and the sample $i \mapsto (x_i, y_i)$, with ERM in the sense of Mission I; the bias term is handled by the book's reduction, appending a constant coordinate, and is not formalized separately. The learnability item states qualitative learnability and the ERM guarantee with an unspecified sample-complexity function; the quantitative rate is Theorem 6.8 of Mission IV. Linear programming (§9.1.1), the pseudo-inverse (§9.2.1), polynomial regression (§9.2.2), Exercises 9.1 and 9.4–9.6 are not stated.

Trivializing readings are excluded: labels are constrained to $\pm 1$, runs must start at $0$ and update only on mistakes, the VC equalities are in $\mathbb{N} \cup \{\infty\}$, and the ERM equivalence is a biconditional. Welcome contributions: the two Perceptron invariants as separate lemmas, the shattering of the standard basis, and the pointwise separability of halfspaces.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 9. doi:10.1017/CBO9781107298019
• F. Rosenblatt, The perceptron: a probabilistic model for information storage and organization in the brain, Psychological Review 65(6), 1958. doi:10.1037/h0042519
• A. B. J. Novikoff, On convergence proofs on perceptrons, Proceedings of the Symposium on the Mathematical Theory of Automata 12, 1962.
• S. Agmon, The relaxation method for linear inequalities, Canadian Journal of Mathematics 6, 1954. doi:10.4153/CJM-1954-037-2
• S. Ben-David, H. U. Simon, Efficient learning of linear perceptrons, Advances in Neural Information Processing Systems 13, 2001.

Motivation

The fundamental theorem of Mission IV says that a class of binary classifiers is PAC learnable exactly when its VC-dimension is finite. That leaves out classes one would like to learn, such as all polynomial classifiers over the line, whose VC-dimension is infinite although each degree separately is learnable. Chapter 7 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) relaxes the definition. In nonuniform learnability (Definition 7.1) the sample size may depend on the hypothesis the learner is competing with: the learner must, for every $h \in H$, eventually do as well as $h$ up to $\epsilon$, but how soon may depend on $h$. The chapter's main result (Theorem 7.2) characterizes the nonuniformly learnable classes of binary classifiers as the countable unions of agnostic PAC learnable classes. The learning rule behind it is Structural Risk Minimization (SRM): write $H = \bigcup_n H_n$, weight the pieces, and minimize the empirical risk plus a confidence term that grows with the index (Theorems 7.3–7.5). Applied to a countable class described by a prefix-free code, SRM becomes the Minimum Description Length rule and yields a quantitative form of Occam's razor (Lemma 7.6, Theorem 7.7). The chapter closes the circle with a No-Free-Lunch result for the relaxed notion (Remark 7.2, Exercise 7.5).

Setting

The framework is that of Missions I, II and IV: examples in a domain $Z$, a hypothesis type with a class $H$, a loss $\ell$, risk $L_D$ and empirical risk $L_S$, learners as functions of the sample, the uniform convergence property with an explicit rate $m^{UC}_H$, agnostic PAC learnability, and for binary classification the 0–1 loss, the VC-dimension and pointwise separability. The new module adds Definition 7.1 with an explicit rate $m^{NUL}$ and, as in Definition 3.4, learners whose outputs lie in $H$; the same notion for a family of learners indexed by the confidence $\delta$, since the SRM and MDL rules take $\delta$ as an input; the rate $\epsilon_n(m,\delta) = \inf\{\epsilon \in (0,1) : m^{UC}_{H_n}(\epsilon,\delta) \le m\}$ of Equation (7.1), which is meaningful only when that set is nonempty; the index $n(h) = \min\{n : h \in H_n\}$ of Equation (7.4); the SRM rule as a minimizer of $L_S(h) + \epsilon_{n(h)}(m, w(n(h))\delta)$ over the admissible hypotheses, those whose index has positive weight and a defined rate; prefix-free description languages $d : H \to \{0,1\}^*$ and the MDL rule; and shattering of an infinite set.

Formalization targets

Goal: Theorem 7.2

For a class $H$ of measurable binary classifiers over a domain with measurable singletons, every subclass of which is pointwise separable, $H$ is nonuniformly learnable if and only if there are classes $H_n$ with $\bigcup_n H_n = H$, each agnostic PAC learnable.

Milestones

Theorem 7.3. If $H = \bigcup_n H_n$ is nonempty and each $H_n$ has the uniform convergence property, then $H$ is nonuniformly learnable (general loss).

Theorem 7.4. For weights $w(n) \in [0,1]$ with partial sums at most $1$, uniformly convergent pieces $H_n$ with rates $m^{UC}_{H_n}$, $\delta \in (0,1)$, any $D$ and any $m$: with probability at least $1-\delta$, for every $n$ with $w(n) > 0$ at which $\epsilon_n(m, w(n)\delta)$ is defined and every $h \in H_n$, $|L_D(h) - L_S(h)| \le \epsilon_n(m, w(n)\delta)$.

Theorem 7.5. With $w(n) = 6/(\pi^2 n^2)$ and $H_0 = \emptyset$, every family of learners implementing the SRM rule satisfies the nonuniform guarantee with rate $m^{NUL}(\epsilon,\delta,h) = m^{UC}_{H_{n(h)}}(\epsilon/2,\ 6\delta/(\pi n(h))^2)$.

Lemma 7.6 (Kraft). For a prefix-free set $S$ of binary strings, every finite subfamily satisfies $\sum_{\sigma} 2^{-|\sigma|} \le 1$.

Theorem 7.7. For a prefix-free description language on a class with a $[0,1]$-valued loss, $m \ge 1$ and $\delta > 0$: with probability at least $1-\delta$, every $h \in H$ satisfies $L_D(h) \le L_S(h) + \sqrt{(|h| + \ln(2/\delta))/(2m)}$.

Further items: nonuniform learnability is implied by agnostic PAC learnability (§7.1); a nonuniformly learnable class of binary classifiers is a countable union of classes of finite VC-dimension (Exercise 7.5 (1)–(2)); a class shattering an infinite set admits no countable cover by classes of finite VC-dimension (Exercise 7.5 (3)) and is not nonuniformly learnable; over an infinite domain the class of all measurable classifiers is not nonuniformly learnable (Remark 7.2).

Significance

Theorem 7.2 is the second characterization theorem of the book's Part I and the one that explains why model selection works: any class that can be stratified into learnable pieces is learnable in the nonuniform sense, with the price of not knowing the index paid in sample size rather than in principle. SRM is the abstract form of every penalized learning rule, and the MDL bound of Theorem 7.7 is the cleanest instance, a bound in which the only property of the hypothesis that matters is the length of its description. Remark 7.2 shows the relaxation is not free: even nonuniformly, no learner handles all classifiers over an infinite domain.

Nothing here is machine-checked. The chapter's arguments are short but they combine everything before them: Hoeffding, the union bound with weights, the VC lower bound of Corollary 6.4 and the fundamental theorem. Three places where the book's statements need care are recorded in the formalization: the rate $\epsilon_n$ is an infimum that may be undefined for small $m$; the SRM rule takes $\delta$ as an input and so is a family of learners; and the fundamental theorem's uniform-convergence direction needs a measurability condition, which appears in Theorem 7.2 as hereditary pointwise separability.

Difficulty

The relaxation remark is a direct comparison of two definitions. Kraft's inequality is the coin-tossing argument of the book or an induction on the maximal length: it is the intended entry point. Theorem 7.4 is Theorem 7.3's engine: for each index and each $\epsilon$ in the set of Equation (7.1), the uniform convergence property bounds the failure by $w(n)\delta$; the passage from "every $\epsilon$ in the set" to the infimum uses continuity of the outer measure along an increasing union; the union over $n$ uses countable subadditivity and the partial-sum condition. Theorem 7.5 is Theorem 7.4 on the good event together with the two inequalities of the book's proof, using that the target is admissible when $m \ge m^{UC}_{H_{n(h)}}(\epsilon/2, w(n(h))\delta)$ and that admissibility of the SRM output gives the bound for it. Theorem 7.3 asks for a single learner: SRM with a confidence schedule $\delta_m \to 0$ chosen so that, for each fixed index, the rate at level $\delta_m$ eventually falls below any $\epsilon$, together with an approximate minimizer within $1/m$; the target hypothesis is admissible for $m$ large. Theorem 7.7 is Theorem 7.4 with singleton pieces and the weights $2^{-|h|}$, a one-sided Hoeffding bound for each $h$, and Kraft's inequality. Exercise 7.5 (3) is the combinatorial construction of the book's hint, disjoint finite subsets $K_n$ of the shattered set with $|K_n| > \mathrm{VCdim}(H_n)$ and a labeling that no $H_n$ realizes. The first half of Theorem 7.2 is Corollary 6.4 applied to the nonuniform learner at fixed $\epsilon_0, \delta_0$, with constants chosen so that the two probability bounds actually contradict; the second half is the fundamental theorem on each piece followed by Theorem 7.3.

Formalization scope

Learners output hypotheses in $H$, in Definition 7.1 as in Definition 3.4. The rate $\epsilon_n$ is an infimum over the set of Equation (7.1), and every statement that uses it is guarded by the nonemptiness of that set; the weight $w(n)$ may be $0$, and $H_0 = \emptyset$ encodes the book's indices $1, 2, \dots$. The SRM rule minimizes over admissible hypotheses, and an SRM family is one that returns an admissible minimizer whenever some hypothesis is admissible, which is the book's assumption that the argmin is attained (automatic for the 0–1 loss). Theorem 7.4's sum condition is on partial sums, and Kraft's inequality is on finite subfamilies, so no divergent series is silently zero. Theorem 7.7 assumes a $[0,1]$-valued loss and $m \ge 1$. The binary-classification results assume measurable singletons and measurable hypotheses; Theorem 7.2 also assumes every subclass pointwise separable, which every class over a countable domain satisfies. Definition 7.8 (consistency) and the Memorize algorithm of §7.4 are not stated.

Trivializing readings are excluded: outputs in $H$ keep the risk an honest integral, the rate is never a junk infimum of the empty set, and the failure events are bounded in outer measure. Welcome contributions: a reusable weighted union bound over a countable family of uniform-convergence events, the continuity argument for the infimum rate, and the shattered-set combinatorics of Exercise 7.5.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 7. doi:10.1017/CBO9781107298019
• V. N. Vapnik, The Nature of Statistical Learning Theory, Springer, 1995. doi:10.1007/978-1-4757-2440-0
• J. Rissanen, Modeling by shortest data description, Automatica 14(5), 1978. doi:10.1016/0005-1098(78)90005-5
• A. Blumer, A. Ehrenfeucht, D. Haussler, M. K. Warmuth, Occam's razor, Information Processing Letters 24(6), 1987. doi:10.1016/0020-0190(87)90114-1
• L. G. Kraft, A device for quantizing, grouping, and coding amplitude modulated pulses, MSc thesis, MIT, 1949.

Motivation

Two different numbers describe the output of a lamp. Radiant flux $\Phi_e$ is the power it radiates, in watts. Luminous flux $\Phi_v$ is how much of that radiation the standard human eye registers, in lumens — a weighted integral of the radiated power in which each wavelength is counted according to the sensitivity of the eye at that wavelength. Their ratio

$$K \;=\; \frac{\Phi_v}{\Phi_e}$$

is the luminous efficacy of radiation, measured in lumens per watt: it says what fraction of the radiated power is usable for illumination. Photometry is built on this pair of quantities. The lumen and the candela are defined from the watt through exactly such a weighting, with the SI defining constant $K_{\mathrm{cd}} = 683$ lm/W fixing the scale at the frequency $540 \times 10^{12}$ Hz, and every efficiency figure quoted for a lamp — a tungsten filament at $15$ lm/W, a white LED above $100$ lm/W — is a statement about this ratio or its wall-plug variant.

The basic structural fact of the subject is that this ratio is bounded. Since the eye's sensitivity curve is normalized to a maximum of $1$, no source, however designed, can exceed the maximum spectral luminous efficacy: $683.002$ lm/W under photopic (daylight, cone) vision, and about $1700$ lm/W under scotopic (dark-adapted, rod) vision. Those two numbers are the ceilings against which every lighting technology is measured, and they are what this mission formalizes.

Setting

Wavelengths are real numbers (nanometres). A spectral radiant flux distribution of a source is modelled as a finite Borel measure $\mu$ on the wavelength axis: $\mu(A)$ is the power, in watts, that the source radiates at wavelengths in $A$. Its radiant flux is the total mass

$$\Phi_e \;=\; \mu(\mathbb{R}).$$

A luminosity function (luminous efficiency function) with peak at $\lambda_0$ is a measurable $V : \mathbb{R} \to \mathbb{R}$ with

$$0 \le V(\lambda) \le 1 \quad \text{for all } \lambda, \qquad V(\lambda_0) = 1 .$$

For photopic vision the CIE 1924 curve $V$ peaks at $\lambda_0 = 555$ nm; the scotopic curve $V'$ peaks at $\lambda_0 = 507$ nm. The development assumes only the normalization above, never a specific tabulated curve, so every statement holds for the photopic curve, the scotopic curve, and any other normalized weighting.

Given a maximum spectral luminous efficacy $K_{\max}$ — the value $K_m = 683.002$ lm/W for photopic vision, $1700$ lm/W for scotopic vision — the spectral luminous efficacy is $K(\lambda) = K_{\max} V(\lambda)$ and the luminous flux is

$$\Phi_v \;=\; \int_{\mathbb{R}} K(\lambda) \, \mathrm{d}\mu(\lambda) \;=\; K_{\max} \int_{\mathbb{R}} V \,\mathrm{d}\mu .$$

The luminous efficacy of radiation is $K = \Phi_v / \Phi_e$, the dimensionless luminous efficiency is $K / K_{\max}$, and the luminous efficacy of a source (overall, or wall-plug, efficacy) is $\Phi_v / P$, where $P$ is the total input power the source consumes — electrical, chemical or other — of which the radiated part is $\Phi_e \le P$.

Modelling the spectrum as a measure rather than as a density is what makes the two halves of the target statement expressible at once. A spectrum with a spectral radiant flux density $\Phi_{e,\lambda}$ is the measure $\mathrm{d}\mu = \Phi_{e,\lambda} \, \mathrm{d}\lambda$, for which the formulas above reduce to the usual integrals

$$\Phi_v = K_{\max}\int V(\lambda)\, \Phi_{e,\lambda} \,\mathrm{d}\lambda, \qquad \Phi_e = \int \Phi_{e,\lambda} \,\mathrm{d}\lambda ;$$

an ideal monochromatic source at $\lambda_0$, which has no density with respect to wavelength, is the point mass $\delta_{\lambda_0}$.

Formalization targets

Goal — the photopic ceiling is attained at $683.002$ lm/W

$$683.002 \;=\; \max\left\{\, \frac{K_m \int V \,\mathrm{d}\mu}{\mu(\mathbb{R})} \;:\; \mu \text{ finite}, \ \mu(\mathbb{R}) > 0 \,\right\}, \qquad K_m = 683.002 \text{ lm/W}.$$

This is a maximum, not a supremum: the assertion is both that no spectral radiant flux distribution exceeds $683.002$ lm/W and that some distribution — the monochromatic source at $555$ nm — attains it exactly.

Scotopic counterpart

$$1700 \;=\; \max\left\{\, \frac{1700 \int V' \,\mathrm{d}\mu}{\mu(\mathbb{R})} \;:\; \mu \text{ finite}, \ \mu(\mathbb{R}) > 0 \,\right\}$$

for a scotopic luminosity function $V'$ with $V'(507) = 1$.

Supporting statements

$\Phi_v \ge 0$; $\Phi_v \le K_{\max}\Phi_e$; $0 \le K \le K_{\max}$; luminous efficiency in $[0,1]$; the point mass at the peak realizes $K = K_{\max}$; the reduction of $K$ to the integral formula for a spectrum with a density; invariance of $K$ under rescaling the spectrum; $\Phi_v / P \le K$ when $\Phi_e \le P$; and $K = 0$ for a source radiating only where $V$ vanishes.

Significance

The ceiling is the reference point for the whole of lighting efficiency: quoted luminous efficiencies are efficacies divided by $683.002$ lm/W, so "$37\%$" for a truncated $5800$ K black body and "$2\%$" for a tungsten filament are statements about the distance to this bound. The supporting statements are the facts that make such comparisons well posed — that the efficacy depends only on the shape of the spectrum and not on the wattage, that the wall-plug efficacy of a device is never better than the efficacy of its radiation, and that power radiated outside the response band is pure loss.

Formalizing the material produces a small, reusable measure-theoretic layer for photometric and, more generally, for weighted-average quantities: a bounded weight integrated against a finite measure, normalized by the total mass, with the extreme value attained at a point mass. Nothing here is open mathematics; the value of the mission is a machine-checked model in which the definitions of the International Electrotechnical Vocabulary are stated once and the standard consequences are derived from them, rather than each being asserted in prose.

Difficulty

The mathematical content is elementary — the ceiling is the inequality $\int V \,\mathrm{d}\mu \le \mu(\mathbb{R})$ for $0 \le V \le 1$ — and the work is in the modelling. Three points need care.

First, attainment. On the space of $L^1$ densities the value $683.002$ lm/W is a supremum that is never attained: for the actual CIE curve the set $\{V = 1\}$ is a single point, hence Lebesgue-null, so a density supported there is zero almost everywhere and has no radiant flux at all. A formalization restricted to densities would either have to weaken the goal to a supremum or state an attainment claim that is vacuously true. Measures avoid this: the monochromatic source is the point mass $\delta_{555}$.

Second, division. Efficacy is a quotient, and the quotient of a real by zero is a junk value; every statement about $K$ therefore carries the hypothesis $\Phi_e > 0$, which is also the physically meaningful one.

Third, integrability. The luminous flux is a Bochner integral, which returns $0$ for a non-integrable integrand; the mission's hypotheses ($V$ measurable and bounded, $\mu$ finite) are what rule this degeneracy out.

Formalization scope

The wavelength axis is all of $\mathbb{R}$, with Lebesgue measure where a density is used; no restriction to positive wavelengths or to a visible band is imposed, since the luminosity function already performs the restriction. A spectral radiant flux distribution is a finite Borel measure; the finiteness hypothesis is carried as a typeclass assumption and the positivity of the radiant flux as an explicit one. The luminosity function is assumed measurable with values in $[0,1]$ and equal to $1$ at its peak, and nothing more: no continuity, no unimodality, no tabulated values. The maximum spectral luminous efficacy appears as an explicit parameter $K_{\max}$, so that the photopic constant $683.002$ and the scotopic constant $1700$ are instances of the same statements rather than separate developments. Units are not represented in the types: all quantities are plain real numbers, and lumens per watt appears only in the prose.

The goal is stated as "$683.002$ is the greatest element of the set of achievable efficacies", which rules out the two trivializing readings: a bare upper bound (true of any number above the ceiling) and an attainment claim over a class of spectra that is empty or null.

A complete development needs Mathlib's measure theory and Bochner integration only: finite measures, withDensity, Dirac measures, and monotonicity of the integral. The resulting definitions are reusable for any normalized weighted average of a finite measure, and contributions extending the model — mesopic weighting, black-body spectra and the efficacy figures computed from them, or the CIE curve as tabulated data — are welcome.

Selected references

• International Electrotechnical Commission, International Electrotechnical Vocabulary, entries 845-21-089 (luminous efficacy of a source) and 845-21-090 (luminous efficacy of radiation), electropedia.org.
• Bureau International des Poids et Mesures, Principles Governing Photometry, 2nd edition, 2019, p. 10, bipm.org — the value $683.002$ lm/W.
• ISO/CIE, ISO 23539:2005 Photometry — The CIE system of physical photometry, iso.org.
• T. W. Murphy, "Maximum spectral luminous efficacy of white light", Journal of Applied Physics 111 (2012) 104909, arXiv:1309.7039.
• Wikipedia, Luminous efficacy, en.wikipedia.org/wiki/Luminous_efficacy — the source material for this mission.

Motivation

The Avogadro constant $N_A$ is the conversion factor between an amount of substance and a number of elementary entities (atoms, molecules, ions, ion pairs). Since the 2019 revision of the SI it is a defining constant with the exact value $N_A = 6.02214076\times10^{23}\ \mathrm{mol}^{-1}$; the pure number $N_0 = 6.02214076\times10^{23}$ is called the Avogadro number. Before 2019 the mole was instead defined as the amount of substance in 12 grams of carbon-12, so $N_0$ was a measured quantity: the number of carbon-12 atoms in 12 g, equivalently the number of daltons in a gram, $N_0 = \mathrm{g}/\mathrm{Da}$. The two definitions agree to within the experimental uncertainty of the dalton, but no longer by fiat.

The relations that carry this content — $n(X) = N(X)/N_A$, $M(X) = m(X)\,N_A$, $V_m = v\,N_A$, $n_a = 1/N_A$, and the crystal/unit-cell count used by the Avogadro Project's X-ray crystal density measurements on silicon-28 spheres — are stated in every chemistry course and used without further comment. They are elementary, but they are also exactly the kind of unit-bookkeeping that is easy to state loosely and easy to get wrong by a factor, and they have no machine-checked formulation.

Setting

Fix a common positive scale for masses, volumes and amounts, and record on it three units: a mass unit $\mathrm{g}$ (gram), a second mass unit $\mathrm{Da}$ (dalton), and an amount unit $\mathrm{mol}$ (mole), each a strictly positive real number. Write

$$N_0 = 6.02214076\times10^{23}, \qquad N_A = \frac{N_0}{\mathrm{mol}} .$$

For a sample containing $N$ entities, its amount of substance is $n = N/N_A$; for an entity of mass $m$, the molar mass is $M = m\,N_A$; for an entity occupying volume $v$, the molar volume is $V_m = v\,N_A$; the elementary amount is $n_a = 1/N_A$. For a crystal of volume $V$ whose unit cell has volume $v_{\text{cell}} > 0$ and contains $k$ entities, the number of entities in the crystal is $k\,V/v_{\text{cell}}$.

All of these are modelled as real numbers; units appear as positive real parameters rather than as a dimension system, so every statement below is an identity between real numbers that holds for every admissible choice of $\mathrm{g}$, $\mathrm{Da}$, $\mathrm{mol}$.

Formalization targets

Goal — the gram-to-dalton ratio

Under the pre-2019 definition of the mole, let $m_{\mathrm{C}} > 0$ be the mass of one carbon-12 atom, let $N$ satisfy $N\,m_{\mathrm{C}} = 12\,\mathrm{g}$ (a mole of carbon-12 weighs 12 grams), and let the dalton be one twelfth of the mass of a carbon-12 atom, $\mathrm{Da} = m_{\mathrm{C}}/12$. Then

$$N = \frac{\mathrm{g}}{\mathrm{Da}} .$$

That is: the Avogadro number under the old definition is exactly the number of daltons in a gram. The goal fixes no numerical value — it asserts the shape of the relation, and so survives any revision of the measured value of the dalton.

Milestones

The six milestone lemmas are the remaining relations the source states: the inversion $n(X)\,N_A = N(X)$; the 2019 statement $M(X)\cdot\mathrm{mol} = N_0\,m(X)$; the elementary-amount identity $1\,\mathrm{mol} = N_0\,n_a$; the pre-2019 numerical coincidence that a particle of mass $12\,\mathrm{Da}$ has molar mass exactly $12\,\mathrm{g}/\mathrm{mol}$ when $N_A = (\mathrm{g}/\mathrm{Da})\,\mathrm{mol}^{-1}$; the worked numerical example that a water molecule occupies about $0.030\ \mathrm{nm}^3$ when the molar volume of water is $18\ \mathrm{mL}/\mathrm{mol}$; and the crystal/unit-cell amount relation.

Significance

The result itself is not new mathematics: each identity is one line of algebra once the model is fixed. What the mission produces is the model — a single, audited Lean formulation of amount of substance, molar mass, molar volume, the elementary amount, and the crystal count, in which the pre-2019 and post-2019 definitions of the mole can both be stated and compared, and in which the one place where the two definitions differ (the dalton is measured, the Avogadro number is fixed) is visible rather than hidden in a convention. That layer is reusable by any later formalization that needs to convert between microscopic and molar quantities, including the X-ray crystal density determination of $N_A$ from silicon-28 lattice measurements.

Status honesty: everything stated here is standard, textbook-level content, and all seven statements have been checked to be provable in the model as formalized. The mission's value is the faithful encoding and the audited definition layer, not the difficulty of the proofs.

Difficulty

The proofs are elementary real algebra; the difficulty is entirely in the statements. Two traps recur. First, division in Lean is total, so an identity such as $n = N/N_A$ carries no information at $N_A = 0$ and can be satisfied vacuously; every statement here therefore either derives positivity from the unit data or takes the nondegeneracy hypothesis explicitly. Second, it is easy to write a unit relation that is true only for one choice of units — for instance, conflating the numerical value $N_0$ with the dimensional constant $N_A = N_0/\mathrm{mol}$ — and such a statement still compiles. Readers auditing this proposal should check each statement against both failure modes.

Formalization scope

Units are positive real parameters bundled in a structure carrying $\mathrm{g}, \mathrm{Da}, \mathrm{mol}$ together with proofs of their positivity; there is no dimension-tracking type system. Amounts, masses, volumes and entity counts are real numbers (the crystal's entities-per-cell count is a natural number). The Avogadro number is the exact rational $602214076\times10^{15}$, so the numerical milestone is a genuine rational-arithmetic bound, not a floating-point approximation. The water example is stated as a strict two-sided bound, $0.0298\ \mathrm{nm}^3 < v < 0.0300\ \mathrm{nm}^3$, so that it cannot be satisfied by a rounded value.

A trivializing formalization is ruled out as follows: no statement is of the form "some quantity exists", every statement quantifies over an arbitrary admissible unit system, and the goal's hypotheses are simultaneously satisfiable (take $\mathrm{g} = 1$, $m_{\mathrm{C}} = 12/N$ for any $N > 0$), so the goal is not vacuous.

Contributions welcome: a dimension-typed refinement of the unit layer, and the X-ray crystal density relation $N_A = n M/(\rho a^3)$ for a cubic lattice, which the source describes only qualitatively and which is deliberately not claimed here.

Selected references

• Wikipedia, Avogadro constant. https://en.wikipedia.org/wiki/Avogadro_constant (the uploaded snapshot is the source of record for this mission).
• Bureau International des Poids et Mesures, The International System of Units (SI), 9th edition, 2019. https://www.bipm.org/en/publications/si-brochure

Motivation

A black body is an idealized body that absorbs all radiation falling on it and, when held at a fixed absolute temperature $T$, re-emits radiation whose spectrum depends on $T$ alone. At the end of the nineteenth century two incompatible descriptions of that spectrum were on the table. Wien's distribution law (1896) fitted the measurements at short wavelengths and high temperatures but failed at long wavelengths. The formula Rayleigh obtained from classical equipartition, later the Rayleigh-Jeans law, reproduced the long-wavelength data and grew without bound at short wavelengths - the failure Ehrenfest named the ultraviolet catastrophe in 1911.

Planck's 1900 formula fits at every frequency. He reached it by refusing to treat the vibrational energy of the oscillators as a continuous quantity, writing it instead as an integer multiple of an energy element $\varepsilon = h\nu$; the constant $h$ entered physics as the proportionality factor in that hypothesis. Fitting black-body data, Planck obtained $h \approx 6.55\times10^{-34}\ \mathrm{J\,s}$, within about $1.2\%$ of the value $h = 6.626\,070\,15\times10^{-34}\ \mathrm{J\,s}$ that today defines the SI.

What makes Planck's formula the successful one is not only that it fits the data. It contains both classical laws: it degenerates to Rayleigh-Jeans at low frequency and to Wien's law at high frequency, and unlike Rayleigh-Jeans it has a finite total emission. This mission formalizes those four statements - two limits and two integrability claims - about the spectral radiance function itself.

Setting

Fix three positive real parameters: the Planck constant $h$, the speed of light $c$, and the Boltzmann constant $k_B$. They are kept as variables rather than numerical constants, so every statement is a theorem about the functional form, valid in any system of units. Let $T > 0$ be an absolute temperature.

Per unit frequency $\nu$, Planck's law gives the spectral radiance

$$B_\nu(\nu, T) \;=\; \frac{2h\nu^3/c^2}{\exp\!\left(\dfrac{h\nu}{k_B T}\right) - 1},$$

which is the function planckFreq of the already-published definition bundle BlackbodyRadiation_planck. That bundle also provides the dimensionless shape function

$$g_n(x) \;=\; \frac{x^n}{e^x - 1}, \qquad n \in \mathbb{N},$$

in terms of which $B_\nu(\nu,T) = \dfrac{2k_B^3T^3}{h^2c^2}\, g_3\!\left(\dfrac{h\nu}{k_BT}\right)$.

Two further functions are introduced by this mission. The Rayleigh-Jeans spectral radiance, the classical equipartition prediction,

$$B^{\mathrm{RJ}}_\nu(\nu, T) \;=\; \frac{2\nu^2 k_B T}{c^2},$$

and Wien's distribution law, the short-wavelength approximation,

$$B^{\mathrm{W}}_\nu(\nu, T) \;=\; \frac{2h\nu^3}{c^2}\,\exp\!\left(-\frac{h\nu}{k_B T}\right).$$

Write $x = h\nu/(k_B T)$ for the dimensionless frequency. All three radiances are positive on $\nu > 0$; the two comparisons below are stated as ratios, which is the precise form of "agrees with, in this regime".

Formalization targets

Goal

For all $h, c, k_B, T > 0$, all four of the following hold simultaneously:

$$\lim_{\nu \to 0^+} \frac{B_\nu(\nu,T)}{B^{\mathrm{RJ}}_\nu(\nu,T)} = 1, \qquad \lim_{\nu \to \infty} \frac{B_\nu(\nu,T)}{B^{\mathrm{W}}_\nu(\nu,T)} = 1,$$ $$B_\nu(\cdot,T) \in L^1\big((0,\infty)\big), \qquad B^{\mathrm{RJ}}_\nu(\cdot,T) \notin L^1\big((0,\infty)\big).$$

The goal asserts only the shape of the truth - ratios tending to $1$ and membership or non-membership in $L^1$ - and fixes no constant, so it is not invalidated by any sharper rate or by the exact value of the total emission.

Milestones

The four conjuncts are milestones in their own right, together with the two shape-function limits that drive them:

$$\lim_{x \to 0^+} \frac{x}{e^x - 1} = 1, \qquad \lim_{x \to \infty} \frac{e^x}{e^x - 1} = 1 .$$

Significance

The result itself. The two limits are the sense in which Planck's law reproduces Wien's law for short wavelengths and the empirical long-wavelength formula, which is the criterion Planck was working to when he introduced $h$; the non-integrability of $B^{\mathrm{RJ}}_\nu$ is the ultraviolet catastrophe, stated exactly rather than as an asymptotic remark; and the integrability of $B_\nu$ is what makes the total emitted power

• the Stefan-Boltzmann law - a well-defined finite number in the first place. In Lean this last point is not cosmetic: the Bochner integral of a non-integrable function is defined and equal to $0$, so an integral identity such as $\int_0^\infty \pi B_\nu \, d\nu = \sigma T^4$ carries no information until integrability is known separately. This mission supplies that missing side condition for the Stefan-Boltzmann statements already on the platform (CODATA2022.blackbody_exitance_eq_stefanBoltzmann, CODATA2022.bose_einstein_integral_cube), both of which are Open.

Formalizing it. The physics has been settled for over a century; none of it is open mathematics. What is missing is machine-checked statements: the platform's existing black-body development (BlackbodyRadiation_planck, and the mission Planck's Law and Wien's Displacement Law) covers the peak of the spectrum and the exact radiation constants, but not the two classical regimes, and not integrability. The limit and integrability lemmas about $x^n/(e^x-1)$ produced here are reusable for any later work on Bose-Einstein integrals, the Debye model, or the Stefan-Boltzmann constant.

Difficulty

The obvious argument for each limit is a one-line asymptotic expansion, and the obvious argument for integrability is "the integrand decays exponentially". Neither survives contact with a formal proof as stated. The ratio $B_\nu/B^{\mathrm{RJ}}_\nu$ equals $x/(e^x-1)$ only after cancelling $\nu^2$, $c^2$ and $2$, which requires those factors to be nonzero - so the algebraic reduction is valid on a punctured neighbourhood, and must be transported to the limit through a congruence-along-a-filter step rather than by rewriting the function globally. At $\nu = 0$ the ratio is a $0/0$ junk value, which is exactly why the limit is taken within $(0,\infty)$.

For integrability the difficulty is at the two ends at once: near $0$ the integrand is $O(\nu^2)$ but the defining expression is a quotient whose denominator vanishes, and near $\infty$ the exponential decay has to be turned into a dominating integrable function rather than a limit statement. Non-integrability of $B^{\mathrm{RJ}}_\nu$ must be derived from unboundedness of $\int_0^R \nu^2 d\nu$, not asserted from the divergence of the integral, since an unproved-integrability integral in Lean silently evaluates to $0$.

Formalization scope

Everything is over $\mathbb{R}$ with the Lebesgue (volume) measure; $L^1$ membership is MeasureTheory.IntegrableOn ... (Set.Ioi 0) volume, which includes measurability. One-sided limits are filters: $\nu \to 0^+$ is the neighbourhood filter of $0$ restricted to $(0,\infty)$, and $\nu\to\infty$ is Filter.atTop. The three physical parameters and the temperature are explicit real arguments, each carrying its own strict positivity hypothesis; no statement is quantified over a possibly empty set of parameters, and every hypothesis $h,c,k_B,T>0$ is satisfiable, so nothing here is vacuous.

The radiance functions are total: division by zero yields $0$ in Lean, so $B_\nu(0,T) = 0$ and the comparison ratios are $0/0 = 0$ at $\nu = 0$. That is harmless for the limits, which are taken strictly inside $(0,\infty)$, and it is why the integrability statements are on $(0,\infty)$ rather than on $[0,\infty)$. The comparisons are deliberately stated as ratios tending to $1$ rather than as differences tending to $0$: the latter would be a weaker claim, and near $\nu=0$ it would be satisfied by functions that are not asymptotically equal.

Contributions welcome beyond the milestones: the corresponding statements in the wavelength parameterization, quantitative error bounds on the two approximations, and the integrability of $g_n$ on $(0,\infty)$ for general $n$, which would close the remaining gap in the Stefan-Boltzmann chain.

Selected references

• Max Planck, Ueber das Gesetz der Energieverteilung im Normalspectrum, Annalen der Physik 4 (1901) 553-563. https://doi.org/10.1002/andp.19013090310
• Planck constant, Wikipedia. https://en.wikipedia.org/wiki/Planck_constant
• Planck's law, Wikipedia. https://en.wikipedia.org/wiki/Planck%27s_law

Motivation

The gravitational constant $G$ is the proportionality constant in Newton's law of universal gravitation and, through the Einstein gravitational constant $\kappa = 8\pi G/c^4$, in the Einstein field equations. It is the least precisely known of the fundamental constants: the CODATA-recommended value is $G = 6.674\,30(15)\times 10^{-11}\ \mathrm{m^3\,kg^{-1}\,s^{-2}}$, a relative standard uncertainty of $2.2\times 10^{-5}$, and published high-precision measurements since the 1980s have at times been mutually exclusive. Everything that is known about $G$ is known through a small number of algebraic identities that convert a measurable quantity - a surface acceleration, a mean density, an orbital period - into a value of $G$. Those identities, not the measurements, are what can be formalized, and they are what this mission collects.

The identities themselves are classical: the inverse-square law dates to Newton's Principia (1687), the notation $G$ to C. V. Boys in the 1890s, and the first laboratory determination to the Cavendish experiment of 1798, which reported a mean Earth density of $5.448(33)\ \mathrm{g\,cm^{-3}}$ - equivalent to $G = 6.74(4)\times 10^{-11}$ in modern units, about $1\%$ above the modern value. The route from "mean density of the Earth" to "value of $G$" is exactly one of the identities below.

Setting

All quantities are real numbers; no dimensional type discipline is imposed, and units are handled explicitly where they matter (see Formalization scope).

For a gravitational constant $G$, point masses $m_1, m_2$ and a centre-to-centre distance $r$, the Newtonian force is

$$F(G, m_1, m_2, r) = \frac{G\,m_1 m_2}{r^2}.$$

For a spherically symmetric body of mass $M$ and radius $R$, the surface gravity ("small $g$", as opposed to "big $G$") is

$$g(G, M, R) = \frac{G M}{R^2},$$

the ball volume is $V(r) = \tfrac{4}{3}\pi r^3$, and the mean density is $\rho(M,R) = M / V(R)$.

A circular orbit of radius $r$ and period $P$ about a mass $M$ is the condition that the centripetal acceleration equals the gravitational acceleration:

$$r > 0,\qquad P > 0,\qquad \left(\frac{2\pi}{P}\right)^2 r = \frac{G M}{r^2}.$$

The Einstein gravitational constant is $\kappa(G,c) = 8\pi G/c^4$.

Formalization targets

Goal - $G$ from an orbit

For $G > 0$, $M > 0$ and a circular orbit of radius $r$ and period $P$ about $M$,

$$G \;=\; \frac{3\pi\,V(r)}{P^2 M},\qquad V(r) = \tfrac{4}{3}\pi r^3.$$

This is the article's statement that $G$ is fixed by the period of an orbit and the volume it encloses. It is the weakest stable form of the orbital identity: no numerical value of $G$, no unit system, and no choice of body are hard-coded into it.

Supporting levels

The milestone list refines the goal into the chain the source uses: the "big $G$ / small $g$" relation, its mean-density form (the Schiehallion-Cavendish route), $P^2 = 4\pi^2 r^3/(GM)$, Kepler's third law for circular orbits, the grazing-satellite form $P^2 = 3\pi/(G\rho)$, the relation to $\kappa$, and the SI $\leftrightarrow$ cgs conversion of the recommended numerical value.

Significance

The result itself. The identities in this mission are the bridge between what an experiment measures and the number reported for $G$: the mean-density form is what turns the Schiehallion and Cavendish results into values of $G$; the orbital form is what makes the product $GM$ (the standard gravitational parameter, known far more accurately than either factor) the quantity celestial mechanics actually uses; the $\kappa$ relation is what carries the Newtonian constant into general relativity.

Formalizing it. No claim here is open mathematics - each target is a consequence of real-field algebra, and the mission's contribution is a single, faithful, reusable Lean vocabulary for elementary Newtonian gravitation (force, surface gravity, mean density, circular orbits) together with machine-checked statements of the identities the literature quotes informally. The mission is a formalization task, not a research task, and it is presented as such.

Difficulty

The mathematical content is elementary; the difficulty is entirely in faithfulness, and it has two specific sources.

First, division in Lean's real numbers is total: $x/0 = 0$. Several of these identities are therefore true but empty at degenerate arguments unless positivity hypotheses are stated, and conversely it is easy to over-hypothesize and end up proving a weaker claim than the source states. Each statement below fixes a particular choice, and that choice is the thing to audit.

Second, the SI/cgs target is a claim about units, which have no primitive representation here. It is stated in a model where each unit symbol is a real scale factor constrained by the relations between the systems; the honest reading of that target is "the two printed numerical values denote the same quantity given $1\ \mathrm{m} = 100\ \mathrm{cm}$, $1\ \mathrm{kg} = 1000\ \mathrm{g}$ and $1\ \mathrm{dyn} = 1\ \mathrm{g\,cm\,s^{-2}}$", and nothing stronger.

Formalization scope

Everything is over $\mathbb{R}$. The definition layer is a single definition item providing newtonForce, surfaceGravity, ballVolume, meanDensity, einsteinConstant, the predicate IsCircularOrbit, and the numerical constant gravitationalConstantSI $= 6.674\,30\times 10^{-11}$; every theorem in the mission is phrased through those, so the definition layer is the part that must be audited first.

The orbit condition is stated as a predicate on $(G, M, r, P)$ carrying $r>0$ and $P>0$, rather than as a derived function, so that no target is vacuous: for every $G>0$, $M>0$ and $r>0$ there is a $P$ satisfying it, so the hypotheses of the orbital targets are satisfiable, and the targets are not true merely for want of instances. No target is stated as an existence claim that a witness construction could trivialize.

Units are modelled as real scale factors rather than by a dimensional type system; a solver who wants a genuinely dimension-typed treatment is welcome to contribute it as a separate development, but the target here is the scale-factor statement.

A complete development needs nothing beyond Mathlib's ordered-field and Real.pi API. The definition layer is intended to be reusable by any later mission on Newtonian gravitation, orbital mechanics, or unit conversion.

Selected references

• Wikipedia, Gravitational constant, https://en.wikipedia.org/wiki/Gravitational_constant (the mission's source text).
• E. Tiesinga, P. J. Mohr, D. B. Newell, B. N. Taylor, CODATA recommended values of the fundamental physical constants: 2018, Rev. Mod. Phys. 93, 025010 (2021), https://doi.org/10.1103/RevModPhys.93.025010.
• H. Cavendish, Experiments to determine the density of the Earth, Phil. Trans. R. Soc. London 88, 469-526 (1798), https://doi.org/10.1098/rstl.1798.0022.

Motivation

The encyclopedic account of the speed of light makes two claims that look physical but whose content is mathematical. First, invariance: "the speed of light in vacuum is the same for all observers, no matter their relative velocity", so that light travels at $c$ "regardless of the motion of the source or the inertial reference frame of the observer". Second, unattainability: $c$ "is the upper limit for the speed at which information, matter, or energy can travel through space", and "particles with nonzero rest mass can be accelerated to approach $c$ but can never reach it". The supporting apparatus quoted in the same source is likewise mathematical: the Lorentz factor $\gamma$, which "diverges to infinity as $v$ approaches $c$"; the Lorentz interval, in which spatial and temporal differences "are combined with a negative sign"; and the kinetic energy $(\gamma-1)mc^2$, from which the source concludes that "it would take an infinite amount of energy to accelerate an object with mass to the speed of light".

This mission isolates that mathematical core, in one spatial dimension, over the real numbers, and asks for machine-checked proofs of it. Nothing here depends on the numerical value $c = 299\,792\,458\ \mathrm{m\,s^{-1}}$: every statement is proved for an arbitrary parameter $c > 0$, which is the sense in which the source's claims are structural rather than metrological.

Setting

Fix a real constant $c > 0$, the invariant speed. Work in one spatial dimension, with a spatial coordinate $x \in \mathbb{R}$ and a time coordinate $t \in \mathbb{R}$; speeds are real numbers, and a speed $v$ is called subluminal when $|v| < c$.

Four objects are used throughout, written in the prose exactly as in the mission's Lean development.

Relativistic velocity addition. For speeds $u, v$,

$$u \oplus_c v \;=\; \frac{u+v}{1 + \dfrac{uv}{c^{2}}}.$$

Lorentz factor. For a speed $v$,

$$\gamma_c(v) \;=\; \frac{1}{\sqrt{1 - \dfrac{v^{2}}{c^{2}}}}.$$

Lorentz interval and Lorentz boost. The interval of an event $(x,t)$ is

$$I_c(x,t) \;=\; c^{2}t^{2} - x^{2},$$

and the boost of velocity $v$ sends the event $(x,t)$ to

$$B_c^{\,v}(x,t) \;=\; \Bigl(\gamma_c(v)\,(x - vt),\ \gamma_c(v)\,\bigl(t - \tfrac{vx}{c^{2}}\bigr)\Bigr).$$

Relativistic kinetic energy. For rest mass $m$ and speed $v$,

$$K_c(m,v) \;=\; \bigl(\gamma_c(v) - 1\bigr)\,m\,c^{2}.$$

Formalization targets

Goal

For every $c > 0$ and every rest mass $m > 0$, all three of the following hold:

$$\forall v,\ |v| < c \ \Longrightarrow\ c \oplus_c v = c;$$ $$\forall u, v,\ |u| < c \ \text{and}\ |v| < c \ \Longrightarrow\ |u \oplus_c v| < c;$$ $$\forall E \in \mathbb{R},\ \exists v,\ 0 < v < c \ \text{and}\ E < K_c(m,v).$$

The three conjuncts are, in order, the invariance of light speed under a change of inertial frame, the fact that composing subluminal speeds never reaches $c$, and the unboundedness of the energy required to approach $c$. The goal deliberately asserts only the shape of the claims — no rate of divergence, no numerical constant — so it is not invalidated by any sharper quantitative statement a solver may prove separately.

Milestones

The milestone list decomposes the goal along the four notions above: interval preservation under a boost, invariance of $c$ under composition, closure of the subluminal range under composition, divergence of $\gamma_c$ at $c$, and unboundedness of kinetic energy below $c$.

Significance

The three conjuncts of the goal are what make $c$ a limit rather than merely a large speed. Closure of $\{|v| < c\}$ under $\oplus_c$ says that no finite chain of subluminal boosts produces a luminal speed; invariance says that the boundary of that range is fixed by every boost; the energy statement says that the boundary is not approached at finite cost. Interval preservation is the geometric statement behind them: a boost is an isometry of the quadratic form $c^2t^2 - x^2$, so the light cone $c^2t^2 = x^2$ is frame-independent.

These results are classical and have been standard since the 1905 formulation of special relativity; nothing in this mission is mathematically open. What the mission produces is the machine-checked version and a small reusable layer of one-dimensional relativistic kinematics: a search for declarations mentioning "Lorentz" in the Mathlib revision used for the drafting check returned none, so the definitions here are contributed rather than reused. The statements are stated for an arbitrary $c > 0$, so they can be reused at $c = 1$ (natural units) without restatement.

Difficulty

The algebraic milestones are short once the right nonvanishing facts are in hand, and the obvious first attempt — clear denominators and call a ring normalizer — fails on all of them for the same reason: the denominators $1 + uv/c^2$, $c$, and $1 - v^2/c^2$ must first be shown nonzero, and each of those facts needs the hypothesis $|v| < c$, not merely $c \neq 0$. For velocity addition the usable identities are

$$c\Bigl(1 + \tfrac{uv}{c^{2}}\Bigr) \pm (u+v) = \frac{(c \pm u)(c \pm v)}{c},$$

whose positivity is where the strict inequality comes from.

The analytic milestone is the one that is not formal manipulation: $\gamma_c$ must be shown to tend to $+\infty$ along the punctured left neighbourhood of $c$, which requires the inner expression to be shown positive, not merely convergent to $0$, on a neighbourhood — the one-sided filter is essential, since $\gamma_c$ takes a junk value beyond $c$ (see below).

Formalization scope

All quantities are real; there is no vector or manifold structure, and spacetime is $\mathbb{R}^2$ presented as a pair of coordinates $(x,t)$. The invariant speed $c$ is a parameter with hypothesis $c > 0$; the numerical SI value is never used. The definitions are total functions, so two junk-value conventions are fixed and must be respected when reading the statements:

• $\gamma_c(v)$ uses the real square root, which is $0$ on negative arguments; hence $\gamma_c(v) = 0$ whenever $|v| \ge c$, rather than being undefined or infinite. Every statement about $\gamma_c$ therefore carries an explicit subluminality or one-sided-limit hypothesis.
• $u \oplus_c v$ is a quotient, and division by zero yields $0$; the hypotheses $|u| < c$, $|v| < c$ are what exclude the vanishing denominator.

No statement in the mission is vacuous: each hypothesis set is satisfiable, e.g. by $c = 1$, $u = v = 1/2$, $m = 1$, and the goal quantifies over all $c > 0$ and all $m > 0$.

A complete development needs only Mathlib's real analysis: Real.sqrt, field-simplification and positivity reasoning, and one-sided neighbourhood filters for the divergence milestone. The definition layer (velocity addition, Lorentz factor, interval, boost, kinetic energy) is reusable beyond this mission — natural follow-ups, welcome as contributions, are the associativity and group structure of $\oplus_c$, the rapidity parametrization $v = c\tanh\theta$, time dilation and length contraction, and the composition law for boosts.

Note on the read-backs attached to this proposal

The read-backs attached to the draft items of this proposal are not blind and not independent: they were written by the same agent that drafted the Lean statements, at the explicit instruction of the proposal owner, with full sight of the source material and of the intended meaning. They should be read as an author's restatement, not as independent testimony, and they do not provide the error-catching value of an independent audit.

Selected references

• Speed of light, Wikipedia (source material supplied for this mission), sections "Invariance of $c$ and the Lorentz factor", "Synthesis of space and time", and "Mass and massless particles". https://en.wikipedia.org/wiki/Speed_of_light
• A. Einstein, Zur Elektrodynamik bewegter Körper, Annalen der Physik 17 (1905), 891–921. https://doi.org/10.1002/andp.19053221004

Motivation

Missions I and II of this series showed that finite hypothesis classes are learnable, with and without the realizability assumption, by empirical risk minimization. Chapter 5 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) asks the converse question: is prior knowledge, in the form of a restricted hypothesis class, really necessary? Could there be a universal learner, an algorithm that, given enough examples from any distribution, outputs a predictor of low risk? The No-Free-Lunch theorem (Theorem 5.1) answers no: for binary classification with the 0–1 loss over a domain $X$, for every learning algorithm and every training-set size $m$ smaller than $|X|/2$ there is a distribution on which the learner fails with probability at least $1/7$, even though that distribution is perfectly predictable by some function $f$, so that another learner (ERM over $\{f\}$) succeeds. The consequence for the framework is Corollary 5.2: over an infinite domain, the class of all functions is not PAC learnable. This is the first lower bound of the book and the reason the rest of it is about the complexity of hypothesis classes rather than about universal algorithms.

Setting

The framework is the UnderstandingML_Framework module of Mission I, cited as a reference. Binary classification over a domain $X$ uses examples in $X \times \{0,1\}$, hypotheses $h : X \to \{0,1\}$ and the 0–1 loss, so the risk of $h$ under a distribution $D$ over $X \times \{0,1\}$ is $L_D(h) = D(\{(x,y) : h(x) \ne y\})$, computed as the integral of the 0–1 loss. A learner is a function from samples of each size to hypotheses, and a sample of size $m$ has the law $D^m$. PAC learnability of a class $H$ (Definition 3.1) requires a sample-complexity function $m_H$ and a learner $A$ such that for every $\epsilon, \delta \in (0,1)$, every distribution $D$ over $X$ and every measurable labeling function $f$ realizable by $H$, samples of size $m \ge m_H(\epsilon,\delta)$ yield $L_{(D,f)}(A(S)) \le \epsilon$ with probability at least $1-\delta$.

Two conventions specific to this mission. The domain $X$ is assumed to have measurable singletons (the book's Remark 3.1 assumes away measurability issues); this makes the finitely supported distributions of the proof honest probability measures and makes every $L_D(h)$ under them a genuine integral. And "$m$ smaller than $|X|/2$" is written $2m < |X|$ in the extended natural numbers, so that an infinite domain satisfies it for every $m$.

Formalization targets

Goal: Theorem 5.1 (No-Free-Lunch)

Let $A$ be any learning algorithm for binary classification with respect to the 0–1 loss over a domain $X$ with measurable singletons, and let $m$ be a training-set size with $2m < |X|$. Then there exists a probability distribution $D$ over $X \times \{0,1\}$ such that

1. there is a measurable $f : X \to \{0,1\}$ with $L_D(f) = 0$;
2. there is a measurable set $E$ of samples of size $m$ with $D^m(E) \ge 1/7$ on which $L_D(A(S)) \ge 1/8$.

Milestones

Lemma B.1 (Appendix B). If $Z$ takes values in $[0,1]$ and $E[Z] = \mu$, then for every $a \in (0,1)$, $P[Z > 1-a] \ge (\mu - (1-a))/a$, and consequently $P[Z > a] \ge (\mu - a)/(1-a) \ge \mu - a$.

Equation (5.2). Under the hypotheses of Theorem 5.1 there are $D$ and a measurable $f$ with $L_D(f) = 0$ and $\mathbb{E}_{S \sim D^m}[L_D(A(S))] \ge 1/4$.

Corollary 5.2. For an infinite domain $X$ with measurable singletons, the class of all functions $X \to \{0,1\}$ is not PAC learnable.

Two further items: Exercise 5.1, the passage from an expectation of at least $1/4$ to a probability of at least $1/7$ of exceeding $1/8$ for a $[0,1]$-valued variable; and Exercise 5.3, the $k$-fold version of Equation (5.2), with bound $1/2 - 1/(2k)$ when $km \le |X|$, $k \ge 2$ and $X$ is nonempty.

Significance

The No-Free-Lunch theorem is the book's first impossibility result and the conceptual pivot of Part I: it shows that learnability is a property of the pair (hypothesis class, learner) and not of the learner alone, and it motivates the bias–complexity tradeoff of §5.2 and the VC-dimension of Chapter 6, whose lower bound (Theorem 6.7, the "only if" direction of the fundamental theorem) is proved by the same symmetrization argument. Corollary 5.2 is the statement that the class of all functions has infinite sample complexity, the negative half of the characterization of learnable classes.

Nothing here is machine-checked. The proof is combinatorial and elementary but has real content for a formalization: a finite subset $C$ of the domain, the $2^{2m}$ labelings of $C$, the uniform distribution on $C$ labeled by each of them, an exchange of a maximum, an average and a minimum over labelings and sample sequences, and a pairing argument on labelings that differ at exactly one unseen point. Lemma B.1 is a reverse Markov inequality for bounded variables that later chapters also use.

Difficulty

Lemma B.1 is Markov's inequality applied to $1 - Z$ and is the entry point; Exercise 5.1 is its instance with $a = 1/8$ and $\mu \ge 1/4$, giving $(1/4 - 1/8)/(7/8) = 1/7$, together with the inclusion of $\{\theta > 1/8\}$ in $\{\theta \ge 1/8\}$. Theorem 5.1 follows from Equation (5.2) and Exercise 5.1 once one knows that $S \mapsto L_D(A(S))$ is, under the finitely supported $D^m$, almost everywhere equal to a measurable function with values in $[0,1]$; the set $E$ is the intersection of the event with the finite support of $D^m$, which is measurable because singletons are. Equation (5.2) is the heart of the mission. One picks $C \subseteq X$ of size $2m$ (available because $2m < |X|$), lets $D_i$ be uniform on $C$ labeled by the $i$-th function $f_i : C \to \{0,1\}$ extended by $0$ off $C$, and computes $\mathbb{E}_{S \sim D_i^m}[L_{D_i}(A(S))]$ as an average over the $(2m)^m$ sequences of instances, which requires identifying $D_i^m$ as a finitely supported measure on sequences, that is, the product of finitely supported measures. The inequalities (5.4)–(5.6) exchange max, average and min and restrict to the unseen points, and the pairing argument shows that for each unseen point the average over $i$ of the indicator that $A$ errs on it is exactly $1/2$. Exercise 5.3 is the same argument with $|C| = km$, where at least $(k-1)m$ points are unseen. Corollary 5.2 takes $\epsilon < 1/8$, $\delta < 1/7$, $m = m_H(\epsilon,\delta)$ and a set $C$ of size $2m$ in the infinite domain, and derives the contradiction from Theorem 5.1 via the identification of $L_D$ for $D$ uniform on $C$ labeled by $f$ with the true error $L_{(D_X, f)}$ of Definition 3.1, where $D_X$ is uniform on $C$; the case $m = 0$ is handled separately with a single point.

Formalization scope

The items are stated in the joint-distribution form of the book's Chapter 5, with $D$ over $X \times \{0,1\}$ and $L_D$ the risk under the 0–1 loss, rather than in the $(D, f)$ form of Definition 3.1; Corollary 5.2 is the bridge and is stated with the framework's PACLearnable. Witness labeling functions are required to be measurable, because a non-measurable $f$ would make $L_D(f) = 0$ true by Lean's convention for non-integrable functions rather than by content. Clause (2) of Theorem 5.1 is stated in the inner form (a measurable set of probability at least $1/7$ inside the event) rather than as a lower bound on the outer measure of the event, which for a non-measurable event would be the weaker statement. The size condition uses ENat.card, so infinite domains satisfy it. Learners are deterministic functions of the sample; the book's argument goes through for randomized learners by averaging, but the framework does not model them.

Trivializing readings are excluded: the distribution must be a probability measure, the failing set must be measurable with an honest lower bound, and the witness $f$ must be measurable. Welcome contributions: the finitely supported product law on sequences, the averaging identity (5.3), and the pairing argument on labelings of $C$.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 5 and Appendix B. doi:10.1017/CBO9781107298019
• D. H. Wolpert, W. G. Macready, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1), 1997. doi:10.1109/4235.585893
• A. Ehrenfeucht, D. Haussler, M. Kearns, L. Valiant, A general lower bound on the number of examples needed for learning, Information and Computation 82(3), 1989. doi:10.1016/0890-5401(89)90002-3
• V. N. Vapnik, Statistical Learning Theory, Wiley, 1998.