On the Effectiveness of Fekete's Lemma
share
Fekete's lemma is a well known combinatorial result pertaining to number sequences and shows the existence of limits of superadditive sequences. In this paper we analyze Fekete's lemma with respect to effective convergence and computability. We show that Fekete's lemma exhibits no constructive derivation. That is, a form of the axiom of choice is needed for the proof. We characterize when the limit value in Fekete's lemma can be computed and when it is not possible. We also investigate the speed of convergence. Given certain conditions, we can show effective convergence. In general, there is no effective convergence when applying Fekete's lemma.
READ FULL TEXT