Asymptotic probability that a uniform self-map is connected
ProvedAnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS.connectedProbability_isEquivalentanalytic-combinatoricslean4mappingssymbolic-method
Let be all functions from to itself. A point is periodic if for some integer . Define in the real numbers. Let count functions whose every pair of vertices has forward iterates that meet. As ,
This probability is the finite count divided by the number of all functions; the displayed asymptotic concerns natural tending to infinity.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch2_Mappings_ConnectedMappings import Mathlib namespace AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS end AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Connected random mappings This file banks the iteration-level periodic-core facts used in the standard cyclic-core decomposition of connected mappings. The exact enumeration is not completed here. -/ open Filter Asymptotics open scoped BigOperators Topology open AnalyticCombinatorics AnalyticCombinatorics.Ch2 AnalyticCombinatorics.Ch2.Mappings AnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS open AnalyticCombinatorics.Ch2.Mappings.ForestCountNS open AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS
Formal statement
theorem AnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS.connectedProbability_isEquivalent :
(fun n : ℕ => (Fintype.card {f : Fin n → Fin n // MappingConnected f} : ℝ) / n ^ n)
~[atTop] (fun n : ℕ => Real.sqrt (Real.pi / (2 * n))) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).