Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8, lower half of (2.4.4) — the Ulam constant satisfies c≥(8/π)1/2c \ge (8/\pi)^{1/2}c≥(8/π)1/2

Open
KingmanSubadditive.Ulam.theorem_8_lower_bound

by tianyipeng · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

longest-increasing-subsequencerandom-permutationsulam-problem

Let ccc be the constant of (2.4.3), that is, the limit in probability of n−1/2 l(πn)n^{-1/2}\,l(\pi_n)n−1/2l(πn​) for πn\pi_nπn​ uniformly distributed over the permutation group Sn\mathcal S_nSn​, where l(πn)l(\pi_n)l(πn​) is the length of the longest ascending sequence (Theorem 7). Then

c ≥ (8π)1/2.c \ \ge\ \Big(\frac8\pi\Big)^{1/2}.c ≥ (π8​)1/2.

This is the left inequality of (2.4.4) in Theorem 8. Kingman obtains it from Hammersley's construction: in a planar Poisson process of unit rate, a greedy ascending path has i.i.d. increments whose mean is ∫0∞∫0∞xe−12(x+y)2 dx dy=(π/8)1/2\int_0^\infty\int_0^\infty x e^{-\frac12(x+y)^2}\,dx\,dy = (\pi/8)^{1/2}∫0∞​∫0∞​xe−21​(x+y)2dxdy=(π/8)1/2, which yields the lower bound on ccc.

Formalization Note As in Theorem 8, the constant enters as the hypothesis that n−1/2l(πn)n^{-1/2}l(\pi_n)n−1/2l(πn​) converges in probability to ccc (ConvergesInProbUniform c); no sign or bound on ccc is assumed. π\piπ in the bound is the circle constant.

Preamble
import Mathlib
import Definitions.Def_KingmanSubadditive_Ulam_Permutations
Formal statement
namespace KingmanSubadditive.Ulam

/-- **Lower bound of (2.4.4)** (Kingman, *Subadditive ergodic theory*, Ann. Probab. 1(6):883–899
(1973), §2.4, Theorem 8 and the first part of its proof, p. 895). The constant `c` in (2.4.3),
the limit in probability of `n^{−½} l(π_n)` for `π_n` uniform on `𝒮_n`, satisfies
`(8/π)^½ ≤ c`.

**Formalization Note** As in Theorem 8, the constant enters as the hypothesis
`ConvergesInProbUniform c`; no sign or bound on `c` is assumed. -/
theorem theorem_8_lower_bound (c : ℝ) (hc : ConvergesInProbUniform c) :
    Real.sqrt (8 / Real.pi) ≤ c := by sorry

end KingmanSubadditive.Ulam
Source
Kingman, Subadditive ergodic theory, Ann. Probab. 1(6):883–899 (1973), DOI 10.1214/aop/1176996798, §2.4, Theorem 8, left inequality of (2.4.4), proved on p. 895

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me