Theorem 2 proof — the chosen k is O(log(1/α)/α)
ProvedCycleLengthsExp.ManyLengths.k_boundasymptotic-boundsexpander-graphsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Set . There is one absolute constant such that, for every ,
This uniform estimate converts the explicit integer chosen in the proof into the dependence on stated by Theorem 2.
Formalization Note The paper writes . The shifted logarithm supplies the positive endpoint value at ; for it differs only by an absolute factor. The constant is quantified before .
Preamble
import Mathlib import Definitions.Def_CycleLengthsExp_ManyLengths_Setting
Formal statement
namespace CycleLengthsExp.ManyLengths
/-- The `O(log(1/α)/α)` bound following the displayed definition of `k`, p. 13. -/
theorem k_bound :
∃ K : ℝ, 0 < K ∧ ∀ α : ℝ, 0 < α → α ≤ 1 →
(kNum α : ℝ) ≤ K * Real.logb 2 (2 / α) / α := by sorry
end CycleLengthsExp.ManyLengths
Source
Friedman and Krivelevich, Cycle lengths in expanding graphs, arXiv:1912.11011v2, p. 13, proof of Theorem 2, displayed definition of k
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.