Proof of Theorem 1.1 — (log log n)^2 = o((log n)^{β−δ}) for the positive constant β − δ
ProvedExactDFTRefine.Main.loglog_absorptionarithmetic-complexityfourier-transformp2o-gran-per-chapterp2o-plan-paperp2o-v1
With and , the constant is positive and
Logarithms are natural. This absorbs the overhead of the Fourier reduction into the gap , turning the bound into .
Differences from the source:
- encoding: f = o(g) → Asymptotics.IsLittleO atTop on functions ℕ → ℝ; reason: standard little-o along n → ∞
Preamble
import Mathlib import Definitions.Def_ExactDFTRefine_Main_Moments open Asymptotics Filter
Formal statement
namespace ExactDFTRefine.Main
/-- **Proof of Theorem 1.1, absorption of `(log log n)^2`**, p. 6. `β - δ` is positive and
`(log log n)^2 = o((log n)^{β-δ})` as `n → ∞`. -/
theorem loglog_absorption :
0 < beta - delta ∧
(fun n : ℕ => Real.log (Real.log (n : ℝ)) ^ 2) =o[atTop]
(fun n : ℕ => Real.log (n : ℝ) ^ (beta - delta)) := by sorry
end ExactDFTRefine.Main
Source
Yao, Liu, A Numerical Refinement of an Exact Discrete Fourier Transform Bound, arXiv:2611.01257v1, p. 6, proof of Theorem 1.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.