论文标题
关于信息理论中Fekete引理和相关组合问题的有效收敛
On Effective Convergence in Fekete's Lemma and Related Combinatorial Problems in Information Theory
论文作者
论文摘要
Fekete的引理是组合数学的众所周知的结果，该数学显示了与实数的超级和亚基序列有关的限制值。在本文中，我们分析了Zheng和Weihrauch实数的算术层次结构，并将结果拟合到信息理论环境中。我们介绍了与超级和亚基序列相关的特殊集，并证明了它们与\（σ_1\）和\（π_1\）的有效等效性。利用Zheng和Weihrauch建立的理论的方法，我们表明，从Fekete的引理中出现的极限值通常不是可计算的数字。考虑到另外满足非负性的序列，我们表明可以有效地计算关联的限制值并研究收敛的相应模量。辅以鉴定，我们证明了一个关于可计算数字的可计算序列与有理数的可计算序列之间的结构差异的定理。我们通过讨论我们的发现如何影响信息理论的常见问题来结束论文。
Fekete's lemma is a well known result from combinatorial mathematics that shows the existence of a limit value related to super- and subadditive sequences of real numbers. In this paper, we analyze Fekete's lemma in view of the arithmetical hierarchy of real numbers by Zheng and Weihrauch and fit the results into an information-theoretic context. We introduce special sets associated to super- and subadditive sequences and prove their effective equivalence to \(Σ_1\) and \(Π_1\). Using methods from the theory established by Zheng and Weihrauch, we then show that the limit value emerging from Fekete's lemma is, in general, not a computable number. Given a sequence that additionally satisfies non-negativity, we characterize under which conditions the associated limit value can be computed effectively and investigate the corresponding modulus of convergence. Subsidiarily, we prove a theorem concerning the structural differences between computable sequences of computable numbers and computable sequences of rational numbers. We close the paper by a discussion on how our findings affect common problems from information theory.
