The finite Ramanujan sum and Gaussian comparison kernel
DefinitionAnalyticCombinatorics_Ch2_Mappings_RamanujanQanalytic-combinatoricsasymptoticsfinite-sumslean4
For natural numbers , define over the real numbers, with empty product one, and define . The empty sum gives . The comparison kernel is for real . Division is totalized at zero in these definitions; bounds involving decay are stated separately with their positivity hypotheses.
Definition code
import Mathlib set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Ramanujan's Q-function for random mappings This file defines the finite Ramanujan Q-function from Flajolet--Sedgewick, Chapter II.3. The intended asymptotic is `Q(n) ~ sqrt (pi * n / 2)`. The full Laplace-method asymptotic is not yet present in Mathlib. This file records the faithful finite definition and elementary verified bounds that are used by that proof. -/ open Filter Asymptotics open scoped BigOperators Topology namespace AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS noncomputable section /-- The `k`-th summand in Ramanujan's Q-function. The empty product is `1`. -/ def ramanujanQTerm (n k : ℕ) : ℝ := ∏ j ∈ Finset.range k, (1 - (((j + 1 : ℕ) : ℝ) / (n : ℝ))) /-- Ramanujan's Q-function: `Q(n) = 1 + (1 - 1/n) + (1 - 1/n)(1 - 2/n) + ...`. For `n = 0` the finite sum is empty, which is harmless for asymptotic uses. -/ def ramanujanQ (n : ℕ) : ℝ := ∑ k ∈ Finset.range n, ramanujanQTerm n k /-- The Gaussian kernel that dominates the summands of `ramanujanQ`. -/ def gaussianKernel (n : ℕ) (x : ℝ) : ℝ := Real.exp (-((n : ℝ)⁻¹ * 2⁻¹ * x ^ 2)) end end AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS
Source