论文标题
量化离散动态系统中的非可逆性
Quantifying Noninvertibility in Discrete Dynamical Systems
论文作者
论文摘要
给定有限的集合$ x $和a函数$ f：x \ to x $，我们将$ f $的不可逆转程度定义为$ \ displaystyle \ text {deg}（f）= \ frac {1} {| x | x |} \ sum_} \ sum_}这是自然衡量功能$ f $距离被射入的距离的自然衡量标准。我们计算某些特定离散动力学系统的非可逆性程度，包括Carolina Solitaire Map，迭代作用于排列的气泡排序图，作用于多静脉排列的气泡排序以及我们称为“ Nibble Sort”的地图。我们还获得了West堆栈分类地图和保加利亚纸牌地图的非可逆性程度的估计值。然后，我们将注意力转向任意功能及其迭代。为了比较任意函数的非可逆性$ f：x \ to x $与其迭代$ f^k $的度量| x | = n}} \ frac {\ text {deg}（f^k）} {\ text {deg}（f）^γ} =θ（n^{1-1/2^{k-1}}}} \]对于每个实数$γ\ geq geq 2-1/2^^k-1} $。我们以几个猜想和开放问题结尾。
Given a finite set $X$ and a function $f:X\to X$, we define the degree of noninvertibility of $f$ to be $\displaystyle\text{deg}(f)=\frac{1}{|X|}\sum_{x\in X}|f^{-1}(f(x))|$. This is a natural measure of how far the function $f$ is from being bijective. We compute the degrees of noninvertibility of some specific discrete dynamical systems, including the Carolina solitaire map, iterates of the bubble sort map acting on permutations, bubble sort acting on multiset permutations, and a map that we call "nibble sort." We also obtain estimates for the degrees of noninvertibility of West's stack-sorting map and the Bulgarian solitaire map. We then turn our attention to arbitrary functions and their iterates. In order to compare the degree of noninvertibility of an arbitrary function $f:X\to X$ with that of its iterate $f^k$, we prove that \[\max_{\substack{f:X\to X\\ |X|=n}}\frac{\text{deg}(f^k)}{\text{deg}(f)^γ}=Θ(n^{1-1/2^{k-1}})\] for every real number $γ\geq 2-1/2^{k-1}$. We end with several conjectures and open problems.
