Summary (Overview)
- Complete formalization in Lean 4: The paper presents a fully verified proof of the convergence of p-harmonious functions to the viscosity solution of the Dirichlet problem for the normalized p-Laplacian, for , as the step size .
- Barles–Souganidis framework: The proof follows the classical half-relaxed limits approach, requiring consistency (asymptotic expansion), stability (viscosity properties of limits), and comparison principle.
- Key components formalized: Aleksandrov's theorem, Jensen's lemma, existence/uniqueness for the discrete problem, comparison principle for the limit equation, and boundary behavior via exterior sphere condition.
- Scale of development: Approximately 29,400 lines of Lean code across 225 files, built on Mathlib, with no unproved statements and depending only on standard classical axioms.
- Novel analytic simplifications: The proof of Aleksandrov's theorem avoids Hahn–Banach (uses proximal maps), Jensen's lemma avoids mollification and area formula, and uniqueness propagates near-maxima instead of using compactness.
Introduction and Theoretical Foundation
The Normalized p-Laplacian
For , the normalized p-Laplacian is defined as
The operator is homogeneous of degree one and not in divergence form, making viscosity solutions the natural notion.
The Tug-of-War Scheme
The discrete dynamic programming principle (DPP) defining p-harmonious functions is:
Here is the step size, is the open ball of radius centered at , and denotes the average of over with respect to Lebesgue measure. For , the weights satisfy , , and .
Main Theorem (Formalized)
Let and . Let be a bounded open set satisfying the exterior sphere condition (for every there is a ball with and ), and let be bounded and continuous. Then:
- For every there is a unique p-harmonious function in with data , equal to outside , with ;
- The half-relaxed limits and coincide on and equal on , and uniformly on .
The limit is a viscosity solution of in .
Methodology
The Step Operator
For admissible (Borel measurable, bounded) , the step operator is:
Definition 2.1: An admissible is p-harmonious in with data if on and on the strip .
Viscosity Solutions with Envelopes
The equation is written as where
At , the lower and upper semicontinuous envelopes are:
Definition 2.2: An upper semicontinuous is a viscosity subsolution if for any with having a local maximum at :
- if ,
- otherwise.
Supersolutions are defined dually.
Proof Structure (Barles–Souganidis)
The proof reduces to three statements:
- (A) is a viscosity subsolution and is a viscosity supersolution in ;
- (B) Boundary inequalities on ;
- (C) Comparison principle for the limit equation.
Development Layers
| Layer | Content | Lines (approx.) |
|---|---|---|
| 1 | The scheme: operator, measurability, existence, uniqueness, comparison | 3,300 |
| 2 | Viscosity framework: generator, predicates, consistency, stability | 1,100 |
| 3 | Asymptotic expansion of with explicit error rate | 5,500 |
| 4 | Relaxed limits, comparison principle, boundary, convergence | 19,100 |
| Total | 225 files | 29,400 |
Empirical Validation / Results
Consistency: The Asymptotic Expansion
Theorem 4.1: Let with . There is such that for every and :
The proof uses:
- Second moments of Lebesgue measure: (exact identity);
- Averaging Taylor expansion: ;
- Extreme values: ;
- Weight combination: .
Viscosity Property of Relaxed Limits
Theorem 5.1: If is uniformly bounded and each is p-harmonious in open , then is a viscosity subsolution and is a viscosity supersolution of in .
Key techniques:
- Near-maximizers without extraction: Compactness on annuli instead of subsequences;
- Singular case handling: Reflecting balls through centers to obtain eigenvalue inequalities;
- From to : Adding quartic perturbation and using second-order Taylor polynomials.
Comparison Principle
Theorem 6.1: For bounded open , with upper semicontinuous and lower semicontinuous, if is a viscosity subsolution, a viscosity supersolution, and on , then in .
The proof strategy:
- Change of values: , gives strictness:
- No maximum with nonzero gradient: Using Jensen's lemma and Aleksandrov's theorem to obtain a contradiction via ;
- Translated maximum: Showing the contact set is both open and closed, hence all of ;
- Regularization: Sup-convolution and inf-convolution for semiconvexity/semiconcavity.
Aleksandrov's Theorem and Jensen's Lemma
Theorem 6.3 (alexandrov): A convex function on has a second-order expansion at almost every point:
Proved via proximal maps , which are one-Lipschitz and onto, avoiding Hahn–Banach.
Theorem 6.4 (jensen_positive_measure): For semiconvex with larger at some point of than plus its values on the sphere, the set of points where some with attains its maximum has positive measure.
Boundary Behavior and Existence
Theorem 7.1 (ubar_le_bdry): Under the Main Theorem's hypotheses, at every .
The proof uses a polynomial barrier: with ,
satisfying on the shell , giving:
Theorem 7.2 (exists_pharmonious): Iterating the restricted operator (equal to on , identity elsewhere) from on yields a monotone increasing, uniformly bounded sequence converging to a fixed point.
Theorem 7.3 (pharmonious_unique): Propagating near-maxima of in a fixed direction with geometrically growing errors; after steps with exceeding the width of , a contradiction is reached.
Theoretical and Practical Implications
- Formal verification of PDE theory: This is among the first complete formalizations of a nonlinear viscosity solution convergence theorem, demonstrating that complex analytic arguments (Aleksandrov's theorem, Jensen's lemma, comparison principles) can be fully mechanized.
- Methodological innovations: The proximal-map proof of Aleksandrov's theorem and the near-maxima propagation for uniqueness simplify the informal proofs, potentially offering new analytic insights.
- Foundation for future work: The formalized infrastructure (viscosity framework, jets, relaxed limits) can be reused for other non-divergence form equations and numerical schemes.
- AI-assisted formalization: The development used large language models for drafting, with the mathematical route fixed by the authors—demonstrating a viable workflow for large-scale formalization projects.
- Precision requirements: The formalization forced precise statements of several informal notions (open vs. closed balls for measurability, restricted operators, boundary strips), clarifying subtle points in the theory.
Conclusion
The paper reports a complete formalization in Lean 4 of the convergence of p-harmonious functions to the viscosity solution of the normalized p-Laplacian Dirichlet problem for . The approximately 29,400 lines of Lean code cover:
- The discrete dynamic programming scheme with existence and uniqueness;
- The asymptotic expansion (consistency);
- Viscosity properties of half-relaxed limits (stability);
- The comparison principle including Aleksandrov's theorem and Jensen's lemma;
- Boundary behavior via exterior sphere condition and polynomial barriers;
- Uniform convergence of the family.
The development contains no unproved statements and depends only on standard classical axioms (propext, Classical.choice, Quot.sound). Future directions include extending to (where complicates monotonicity), relaxing the exterior sphere condition, and formalizing regularity results for the limit equation.
Related papers
- Grokking Can Be Steered: Selecting Desirable Solutions By Choice Of Learning Rule
The learning rule, not the task, determines neural circuit size in grokked networks, enabling deliberate trade-offs between robustness, compressibility, and transfer speed.
- OpenGNS: An Open Dataset of the Gradient Noise Scale across Vision, Language, and Diffusion Models
OpenGNS, the first open dataset of gradient noise scale measurements, reveals that GNS underestimates critical batch size for generative models but overestimates it for classification.
- Inside the Loop: A Mechanistic Study of Looped Transformers on Permutation Traversal
Looped transformers solve sequential algorithmic tasks untied models of equal effective depth cannot, by executing one algorithm step per iteration without intermediate supervision.