On Effective Convergence in Fekete's Lemma and Related Combinatorial Problems in Information Theory

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 \emph{\citeauthor{ZhWe01}} 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 \(\Sigma_1\) and \(\Pi_1\). Using methods from the theory established by \emph{\citeauthor{ZhWe01}}, we then show that the limit value emerging from Fekete's lemma is, in general, not a computable number. Furthermore, we characterize under which conditions the limit value can be computed and investigate the corresponding modulus of convergence. We close the paper by a discussion on how our findings affect common problems from information theory.