Theorem 8, lower half of (2.4.4) — the Ulam constant satisfies
OpenKingmanSubadditive.Ulam.theorem_8_lower_boundlongest-increasing-subsequencerandom-permutationsulam-problem
Let be the constant of (2.4.3), that is, the limit in probability of for uniformly distributed over the permutation group , where is the length of the longest ascending sequence (Theorem 7). Then
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 , which yields the lower bound on .
Formalization Note As in Theorem 8, the constant enters as the hypothesis that converges in probability to (ConvergesInProbUniform c); no sign or bound on is assumed. 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