New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences
New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences
复制标题
非正线性递归引起的法律分解的新行为
DOI：
10.1177/0143034308090060
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Huanzhong Xu
中科院分区：
文献类型：
--
作者：
M. Catral;Pari L. Ford;P. Harris;Steven J. Miller;Dawn Nelson;Zhao Pan;Huanzhong Xu
Zeckendorf定理指出，每个正整数都有一个唯一的分解为不相邻的Fibonacci数之和。这一结果已被推广到许多序列$\{a_n\}$所产生的一个整数正线性递归，其中每一个有一个相应的概念，一个法律的分解。已有的工作证明了当递归式中的首项系数为正时，$m \in [a_n，a_{n+1}）$的分解中的被和项的个数服从n\to\infty$的正态分布，并且与每个m$相关的间隙测度收敛于几何随机变量.我们将探讨在两个特殊的序列中删除这个假设时会发生什么。在一个算法中，我们恢复了所有以前的结果，包括唯一的分解;在另一个算法中，法律的分解的数量呈指数增长，法律的分解的自然选择（贪婪算法）只在大约92.6%的时间内有效（尽管稍微修改总是有效）。我们发现这两个序列之间的联系，这就解释了为什么在这两个例子中，被加数和被加数之间的间隔的分布是相同的。在我们的调查过程中，我们发现了一个新的角度来处理与特征多项式相关的多项式的根。这使我们能够消除需要的详细的技术分析，其属性大大复杂的证明许多早期的结果在这个问题上，以及处理新的情况下，超出了现有的技术。
Zeckendorf's theorem states every positive integer has a unique decomposition as a sum of non-adjacent Fibonacci numbers. This result has been generalized to many sequences $\{a_n\}$ arising from an integer positive linear recurrence, each of which has a corresponding notion of a legal decomposition. Previous work proved the number of summands in decompositions of $m \in [a_n, a_{n+1})$ becomes normally distributed as $n\to\infty$, and the individual gap measures associated to each $m$ converge to geometric random variables, when the leading coefficient in the recurrence is positive. We explore what happens when this assumption is removed in two special sequences. In one we regain all previous results, including unique decomposition; in the other the number of legal decompositions exponentially grows and the natural choice for the legal decomposition (the greedy algorithm) only works approximately 92.6\% of the time (though a slight modification always works). We find a connection between the two sequences, which explains why the distribution of the number of summands and gaps between summands behave the same in the two examples. In the course of our investigations we found a new perspective on dealing with roots of polynomials associated to the characteristic polynomials. This allows us to remove the need for the detailed technical analysis of their properties which greatly complicated the proofs of many earlier results in the subject, as well as handle new cases beyond the reach of existing techniques.
广义 Zeckendorf 分解间隙的中心极限定理
DOI：
--
发表时间：
2019
期刊：
The Fibonacci quarterly
影响因子：
--
作者：
Li, Ray;Miller, Steven J.
通讯作者：
Miller, Steven J.