论文标题
字符串中周期集数量的收敛
Convergence of the number of period sets in strings
论文作者
论文摘要
考虑长度$ n $的单词。长度$ n $的所有周期的集合是$ \ {0,1,2，\ ldots，n-1 \} $的子集。但是，$ \ {0,1,2，\ ldots，n-1 \} $的任何子集不一定是有效的周期集。在1981年的一份开创性论文中，吉巴斯和奥德利佐（Guibas and Odlyzko）提议将单词的一组时期编码成一个$ n $ n $ long的二进制字符串，称为自相关，其中一个位置$ i $ $ $ $ $表示$ i $。他们考虑了识别有效期集的问题，还研究了长度$ n $的有效期间的数量，表示为$κ_n$。他们推测$ \ ln（κ_n）$渐近地收敛到恒定时间$ \ ln^2（n）$。如果在2001年提出了$ \ ln（κ_n）/\ ln^2（n）$的改进的下限，则自Guibas和Odlyzko的纸上以来，紧密上限的问题一直在开放。在这里，我们在这一部分展示了上限，这意味着它的收敛并关闭了这一长期的猜想。此外，我们扩展了结果，以找到相关次数的相似界限：自相关的概括，该相关编码两个字符串之间的重叠。
Consider words of length $n$. The set of all periods of a word of length $n$ is a subset of $\{0,1,2,\ldots,n-1\}$. However, any subset of $\{0,1,2,\ldots,n-1\}$ is not necessarily a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko have proposed to encode the set of periods of a word into an $n$ long binary string, called an autocorrelation, where a one at position $i$ denotes the period $i$. They considered the question of recognizing a valid period set, and also studied the number of valid period sets for length $n$, denoted $κ_n$. They conjectured that $\ln(κ_n)$ asymptotically converges to a constant times $\ln^2(n)$. If improved lower bounds for $\ln(κ_n)/\ln^2(n)$ were proposed in 2001, the question of a tight upper bound has remained opened since Guibas and Odlyzko's paper. Here, we exhibit an upper bound for this fraction, which implies its convergence and closes this long standing conjecture. Moreover, we extend our result to find similar bounds for the number of correlations: a generalization of autocorrelations which encodes the overlaps between two strings.
