# A formally verified convergence theorem for the tug-of-war scheme of the normalized $p$-Laplacian

> A complete Lean 4 formalization proves p-harmonious functions converge to the viscosity solution of the normalized p-Laplacian for 2 ≤ p < ∞, with no unproved statements.

- **Source:** [arXiv](https://arxiv.org/abs/2611.20169)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/2yfvox
- **Whiteboard:** https://picx.dev/p/2yfvox/image

## Summary

## 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 $2 \leq p < \infty$, as the step size $\varepsilon \to 0$.
- **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 $1 < p < \infty$, the normalized p-Laplacian is defined as

$$
\Delta_{p}^{\mathrm{N}} u = \Delta u + (p-2)\Delta_{\infty}^{\mathrm{N}} u, \qquad \Delta_{\infty}^{\mathrm{N}} u = \left\langle D^{2}u \frac{\nabla u}{|\nabla u|}, \frac{\nabla u}{|\nabla u|} \right\rangle. \tag{1}
$$

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:

$$
u_{\varepsilon}(x) = \frac{\alpha}{2}\left(\sup_{B_{\varepsilon}(x)} u_{\varepsilon} + \inf_{B_{\varepsilon}(x)} u_{\varepsilon}\right) + \beta \int_{B_{\varepsilon}(x)} u_{\varepsilon}, \qquad \alpha = \frac{p-2}{p+d}, \quad \beta = \frac{d+2}{p+d}. \tag{2}
$$

Here $\varepsilon > 0$ is the step size, $B_{\varepsilon}(x)$ is the open ball of radius $\varepsilon$ centered at $x$, and $\int_{B} v$ denotes the average of $v$ over $B$ with respect to Lebesgue measure. For $p \geq 2$, the weights satisfy $\alpha \geq 0$, $\beta > 0$, and $\alpha + \beta = 1$.

### Main Theorem (Formalized)

Let $2 \leq p < \infty$ and $d \geq 1$. Let $\Omega \subset \mathbb{R}^{d}$ be a bounded open set satisfying the **exterior sphere condition** (for every $y \in \partial\Omega$ there is a ball $B(z,\delta)$ with $B(z,\delta) \cap \Omega = \varnothing$ and $y \in \partial B(z,\delta)$), and let $F: \mathbb{R}^{d} \to \mathbb{R}$ be bounded and continuous. Then:

1. For every $\varepsilon > 0$ there is a unique p-harmonious function $u_{\varepsilon}$ in $\Omega$ with data $F$, equal to $F$ outside $\Omega$, with $\sup |u_{\varepsilon}| \leq \sup |F|$;
2. The half-relaxed limits $\overline{u}$ and $\underline{u}$ coincide on $\Omega$ and equal $F$ on $\partial\Omega$, and $u_{\varepsilon} \to \overline{u}$ uniformly on $\Omega$.

The limit is a viscosity solution of $-\Delta_{p}^{\mathrm{N}} u = 0$ in $\Omega$.

---

## Methodology

### The Step Operator

For admissible (Borel measurable, bounded) $v$, the step operator is:

$$
T_{\varepsilon} v(x) = \frac{\alpha}{2}\left(\sup_{B_{\varepsilon}(x)} v + \inf_{B_{\varepsilon}(x)} v\right) + \beta \int_{B_{\varepsilon}(x)} v. \tag{3}
$$

**Definition 2.1**: An admissible $u$ is p-harmonious in $\Omega$ with data $F$ if $u = T_{\varepsilon} u$ on $\Omega$ and $u = F$ on the strip $\Gamma_{\varepsilon} = \{x \notin \Omega : \text{dist}(x, \Omega) \leq \varepsilon\}$.

### Viscosity Solutions with Envelopes

The equation is written as $\mathcal{F}(\nabla u, D^{2}u) = 0$ where

$$
\mathcal{F}(q, X) = -\operatorname{tr} X - (p-2)\left\langle X \frac{q}{|q|}, \frac{q}{|q|}\right\rangle, \qquad q \neq 0.
$$

At $q = 0$, the lower and upper semicontinuous envelopes are:

$$
\mathcal{F}_{*}(0, X) = -\operatorname{tr} X - (p-2)\lambda_{\max}(X), \quad \mathcal{F}^{*}(0, X) = -\operatorname{tr} X - (p-2)\lambda_{\min}(X). \tag{4}
$$

**Definition 2.2**: An upper semicontinuous $u$ is a viscosity subsolution if for any $\varphi \in C^{2}$ with $u - \varphi$ having a local maximum at $x_0$:
- $\mathcal{F}(\nabla\varphi(x_0), D^{2}\varphi(x_0)) \leq 0$ if $\nabla\varphi(x_0) \neq 0$,
- $\mathcal{F}_{*}(0, D^{2}\varphi(x_0)) \leq 0$ otherwise.

Supersolutions are defined dually.

### Proof Structure (Barles–Souganidis)

The proof reduces to three statements:

- **(A)** $\overline{u}$ is a viscosity subsolution and $\underline{u}$ is a viscosity supersolution in $\Omega$;
- **(B)** Boundary inequalities $\overline{u} \leq F \leq \underline{u}$ on $\partial\Omega$;
- **(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 $T_{\varepsilon}$ 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 $\varphi \in C^{3}$ with $\nabla\varphi(x_0) \neq 0$. There is $\rho > 0$ such that for every $y \in B_{\rho}(x_0)$ and $0 < \varepsilon \leq \rho$:

$$
T_{\varepsilon}\varphi(y) = \varphi(y) + \frac{\varepsilon^{2}}{2(p+d)} \Delta_{p}^{\mathrm{N}}\varphi(y) + E_{\varepsilon}(y), \qquad \sup_{y \in B_{\rho}(x_0)} |E_{\varepsilon}(y)| = o(\varepsilon^{2}) \quad (\varepsilon \to 0^{+}).
$$

The proof uses:
- **Second moments of Lebesgue measure**: $\int_{B_{\varepsilon}(0)} z_i z_j \, dz = \frac{\varepsilon^{2}}{d+2}\delta_{ij}$ (exact identity);
- **Averaging Taylor expansion**: $\int_{B_{\varepsilon}(x)} \varphi = \varphi(x) + \frac{\varepsilon^{2}}{2(d+2)}\Delta\varphi(x) + O(\varepsilon^{3})$;
- **Extreme values**: $\frac{1}{2}\left(\sup_{B_{\varepsilon}(x)}\varphi + \inf_{B_{\varepsilon}(x)}\varphi\right) = \varphi(x) + \frac{\varepsilon^{2}}{2}\Delta_{\infty}^{N}\varphi(x) + o(\varepsilon^{2})$;
- **Weight combination**: $\alpha\frac{\varepsilon^{2}}{2}\Delta_{\infty}^{N}\varphi + \beta\frac{\varepsilon^{2}}{2(d+2)}\Delta\varphi = \frac{\varepsilon^{2}}{2(p+d)}\Delta_{p}^{N}\varphi$.

### Viscosity Property of Relaxed Limits

**Theorem 5.1**: If $(u_{\varepsilon})$ is uniformly bounded and each $u_{\varepsilon}$ is p-harmonious in open $\Omega$, then $\overline{u}$ is a viscosity subsolution and $\underline{u}$ is a viscosity supersolution of $-\Delta_{p}^{N}u = 0$ in $\Omega$.

Key techniques:
- **Near-maximizers without extraction**: Compactness on annuli instead of subsequences;
- **Singular case handling**: Reflecting balls through centers to obtain eigenvalue inequalities;
- **From $C^{3}$ to $C^{2}$**: Adding quartic perturbation $|x-x_0|^4$ and using second-order Taylor polynomials.

### Comparison Principle

**Theorem 6.1**: For bounded open $\Omega$, with $U$ upper semicontinuous and $V$ lower semicontinuous, if $U$ is a viscosity subsolution, $V$ a viscosity supersolution, and $U(y) \leq V(y)$ on $\partial\Omega$, then $U \leq V$ in $\Omega$.

The proof strategy:
1. **Change of values**: $\psi(s) = s - \eta s^2$, $W = \psi \circ V$ gives strictness:
$$
\Delta_{p}^{N}(cq, cX - 2\eta q \otimes q) \leq -2\eta(p-1)|q|^{2}. \tag{5}
$$
2. **No maximum with nonzero gradient**: Using Jensen's lemma and Aleksandrov's theorem to obtain a contradiction via $\kappa = 2\eta(p-1)(|q|/(2C))^2 > 0$;
3. **Translated maximum**: Showing the contact set is both open and closed, hence all of $G$;
4. **Regularization**: Sup-convolution and inf-convolution for semiconvexity/semiconcavity.

### Aleksandrov's Theorem and Jensen's Lemma

**Theorem 6.3 (alexandrov)**: A convex function $f$ on $\mathbb{R}^{d}$ has a second-order expansion at almost every point:
$$
f(x+h) = f(x) + \langle q, h\rangle + \frac{1}{2}X(h,h) + o(|h|^{2}) \qquad (h \to 0).
$$

Proved via **proximal maps** $J(y) = \operatorname{argmin}_x (f(x) + \frac{1}{2}|x-y|^2)$, which are one-Lipschitz and onto, avoiding Hahn–Banach.

**Theorem 6.4 (jensen_positive_measure)**: For semiconvex $W$ with $W$ larger at some point of $\overline{B}(x_0, r)$ than $2\delta r$ plus its values on the sphere, the set of points where some $W + \langle\xi, \cdot\rangle$ with $|\xi| \leq \delta$ attains its maximum has positive measure.

### Boundary Behavior and Existence

**Theorem 7.1 (ubar_le_bdry)**: Under the Main Theorem's hypotheses, $\overline{u}(y_0) \leq F(y_0)$ at every $y_0 \in \partial\Omega$.

The proof uses a **polynomial barrier**: with $t = |x-z|^2 - \delta^2$,

$$
\psi = t - Mt^2, \qquad M = \frac{2(d+p-2)+1}{8(p-1)\delta^{2}},
$$

satisfying $\Delta_{p}^{N}\psi \leq -1$ on the shell $0 \leq t \leq 1/(4M)$, giving:

$$
T_{\varepsilon}(c + A\psi) \leq c + A\psi - \frac{A\varepsilon^{2}}{4(p+d)}.
$$

**Theorem 7.2 (exists_pharmonious)**: Iterating the restricted operator $\tilde{T}$ (equal to $T_{\varepsilon}$ on $\Omega$, identity elsewhere) from $u_0 = -C$ on $\Omega$ yields a monotone increasing, uniformly bounded sequence converging to a fixed point.

**Theorem 7.3 (pharmonious_unique)**: Propagating near-maxima of $w = v - u$ in a fixed direction with geometrically growing errors; after $N$ steps with $N\varepsilon/2$ exceeding the width of $\Omega$, 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 $2 \leq p < \infty$. 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 $1 < p < 2$ (where $\alpha < 0$ complicates monotonicity), relaxing the exterior sphere condition, and formalizing regularity results for the limit equation.

---

_Markdown view of https://picx.dev/p/2yfvox, served by PicX — AI-generated visual whiteboard summaries of research papers._
