Documentation

LeanPool.Erdos1196.PrimitiveWeight

Rewriting the primitive weight using visit probabilities #

This file records the exact algebraic bridge from the explicit visit-probability formula v_x(n) = 1 / (B_x n log n) to the weighted series identity f(A) = B_x * ∑_{n ∈ A} v_x(n), and packages the final deterministic reduction from a summable hit series to the logarithmic-series bound.

Main statements #

theorem PrimitiveSetsAboveX.summable_indicatorLogSeries_and_tsum_le_of_hitMass {x Y : } (chain : MarkovLayer x Y) (hx : 2 x) {A : Set } (hA : A Set.Ici x) (hB : 0 < normalizationConstant x Y) (hHitSummable : Summable (A.indicator chain.visitProbability)) (hHit : ∑' (n : ), A.indicator chain.visitProbability n 1) {C : } (hNorm : |normalizationConstant x Y - 1| C / Real.log x) :
Summable (A.indicator fun (m : ) => 1 / (m * Real.log m)) ∑' (m : ), A.indicator (fun (k : ) => 1 / (k * Real.log k)) m 1 + C / Real.log x

If the visit-probability series on A is summable and has total mass at most 1, then the logarithmic series on A is summable as well, and the normalization estimate converts this into the final upper bound for ∑_{n ∈ A} 1 / (n log n).