# Generalizations and relative applications of Fekete's subadditive lemma

Fekete's (subadditive) lemma takes its name from a 1923 paper by the Hungarian mathematician Michael Fekete . A historical overview and references to (a couple of) generalizations and applications of the result are found in Steele's book on probability and combinatorial optimization [2, Section 1.10], where a special mention is made to the work of Pólya and Szegő on the structure of real sequences and series [3, Ch. 3, Sect. 1] and that of Hammersley , motivated by percolation theory, on subadditive functions, the continuous analogue of subadditive sequences, whose systematic study was initiated, as far as I know, by Hille and Phillips in the 1957 edition of their beautiful monograph on functional analysis and semigroups [5, Ch. VII]. The same Steele acknowledges that his own 1989 proof of Kingman's subadditive ergodic theorem , of which Birkoff's celebrated theorem is a corollary, was eventually inspired by Fekete's lemma. Now, my question is:

Can you point out further generalizations (and corresponding (interesting) applications) of Fekete's lemma?

Added later. Fekete's lemma can be used to prove that the limit occurring in the spectral radius formula does actually exist. And this counts (to me) as an (interesting) application.

Bibliography.

 M. Fekete (1923), Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten, Math. Zeit., Vol. 17, pp. 228-249.

 M.J. Steele, Probability theory and combinatorial optimization, SIAM, Philadelphia, 1997.

 G. Pólya and G. Szegő, Problems and Theorems in Analysis, Vol. I, Springer-Verlag, Berlin, 1998 (reprint of the 1978 Edition).

 J.M. Hammersley (1962), Generalization of the fundamental theorem of subadditive functions, Proc. Cambridge Philos. Soc., Vol. 58, pp. 235-238.

 E. Hille and R.S. Phillips, Functional analysis and semi-groups, American Math. Soc., 1996 (revised edition).

 J.M. Steele (1989), Kingman's subadditive ergodic theorem, Annales de l'I.H.P., Section B, Vol. 25, No. 1, pp. 93-98.

• I did not know that it bear the name of Fekete. This reminds me the following: one of my best reknowned colleague once submitted a paper where he used the lemma. The referee suggested rejection because it was stated without proof! Jun 8, 2012 at 16:18
• Another crucial application is the definition of the rotation number for a diffeomorphism of the circle. Jun 8, 2012 at 16:19
• Thank you, Denis, this definitely fills the bill. Yet, unless I'm misunderstanding your thoughts, I can't figure out by myself how to use Fekete's result to prove the existence of the relevant limit in the definition of the rotation number. How do you show that, given $f: \mathbb{S}^1 \to \mathbb{S}^1$ an orientation-preserving homeomorphism of the circle, $F: \mathbb{R} \to \mathbb{R}$ a continuous lift of $f$ and $x$ an arbitrary point in $\mathbb{S}^1$, it is $F^{m+n}(x) \bmod 1 \le F^{m}(x) \bmod 1 + F^{n}(x) \bmod 1$ for all $m, n \in \mathbb{N}$? Jun 8, 2012 at 17:57
• Perhaps this could count as a generalization: Fekete's lemma for real functions (math.SE). Aug 30, 2016 at 3:50

Since you mentioned Kingman's subadditive ergodic theorem, you may find interesting the following semi-uniform subadditive ergodic theorem:

Let $T \colon X \to X$ be a continuous map of a compact metric space $X$. If $f_n \colon X \to [-\infty,+\infty)$ is a subadditive sequence ($f_{n+m} \le f_n + f_m \circ T^n$) of upper semicontinuous functions then: $$\sup_{\mu} \lim_{n \to \infty} \frac{1}{n} \int_X f_n d\mu = \lim_{n \to \infty} \frac{1}{n} \sup_{x \in X} f_n(x) ,$$ where the first $\sup$ is taken over all $T$-invariant probability measures.

References:

• Schreiber. J. Diff. Eq. 148 (1998), 334--350.
• Sturman, Stark. Nonlinearity 13 (2000), 113--143.
• Morris. Proc. London Math. Soc. (3) 107 (2013) 121–150. See Appendix A.

Here is the proof that an orientation preserving homeomorphism $f$ of $\mathbb T$ has a well-defined rotation number. Let $F:{\mathbb R}\rightarrow\mathbb R$ be its lift. It is an increasing function verifying $F(x+\ell)=F(x)+\ell$ for every integer $\ell$. Let $x\in\mathbb R$ be given and $u_n=F^{(n)}(x)$. We have to prove that $\frac1nu_n$ has a finite limit. To do so, fix $n$ and define $N$ so that $u_n\in[x+N,x+N+1)$. Then $$u_{n+m}=F^{(m)}(u_n)\in[F^{(m)}(x+N),F^{(m)}(x+N+1))=[F^{(m)}(x)+N,F^{(m)}(x)+N+1).$$ This gives $u_{n+m}\in[u_m+N,u_m+N+1)$. Consequently, we obtain $$u_m+u_n-1-x\le u_{n+m}\le u_m+u_n+1-x.$$ Applying Fekete's Lemma to $v_n=u_n+1-x$, we see that $\frac1nv_n$, hence $\frac1nu_n$, has a limit $\rho<+\infty$. Applying it to $w_n=u_n-1-x$, we see that this limit is finite.

Finally, the limit does not depend upon the starting point $x$, because if $x\le y\le x+1$, then $F^{(m)}(x)\le F^{(m)}(y)\le F^{(m)}(x)+1$. An other use of the monotonicity shows that the limit is the same as $n\rightarrow-\infty$.

• Cool! Can you provide any conventional reference where it is actually possible to find the same kind of proof? That of Herman (M.R. Herman (1979), Sur la conjugaison différentiable des difféomorphismes du cercle à des rotations, Publ. Math. IHES, Vol. 49, pp. 5–234) looks different. Jun 8, 2012 at 22:45
• @Salvo. V. Arnold discusses the rotation number in his book "Mathematical methods of classical mechanics". Jun 9, 2012 at 7:17

This lemma is simple, but it is very useful in rigorous proofs of Statistical Mechanics.

For example the existence of the thermondynamic limit of the free energy per particule $\frac{f_N}{N}$ of an Ising spin model can be proven in many cases by proving the free energy $f_N$ is sub/super-additive. If interested you can see:

F. Guerra, F. Toninelli - The Thermodynamic Limit in Mean Field Spin Glass Models .

If someone know any generalisation of this lemma, I'm very interested too.