Mapping component counts have mean asymptotic to half log n
ProvedAnalyticCombinatorics.Ch2.Mappings.MappingComponentsNS.Sharp.expected_components_isEquivalentanalytic-combinatoricslean4mappingssymbolic-method
Let be all functions from to itself. A point is periodic if for some integer . Define in the real numbers. For , let be the number of cyclic restrictions of the permutation induced by on its periodic points: a restriction is a nonempty subset of periodic points with a permutation whose iterates have one orbit, agreeing with on that subset. Thus is the source functional-graph component count. As natural ,
The logarithm is the real natural logarithm; this is an asymptotic for the finite mean, not a distributional convergence assertion.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch2_Mappings_MappingComponents import Mathlib set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Sharp logarithmic asymptotic for mapping components The expected number of connected components in a uniform random mapping on `n` labels is asymptotic to `(1 / 2) log n`. -/ open Filter Asymptotics MeasureTheory open scoped BigOperators Topology open AnalyticCombinatorics AnalyticCombinatorics.Ch2 AnalyticCombinatorics.Ch2.Mappings AnalyticCombinatorics.Ch2.Mappings.MappingComponentsNS open AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS -- The finite-sum comparisons below combine several imported analytic bounds; -- a larger heartbeat budget avoids brittleness in the final asymptotic squeeze. set_option maxHeartbeats 800000
Formal statement
theorem AnalyticCombinatorics.Ch2.Mappings.MappingComponentsNS.Sharp.expected_components_isEquivalent :
(fun n : ℕ => (∑ f : Fin n → Fin n, (componentCount f : ℝ)) / (n : ℝ)^n)
~[atTop] (fun n : ℕ => Real.log (n : ℝ) / 2) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).