Fekete’s Lemma and an application on Ramsey theory |

George Polya

Fekete’s lemma was proved by Pólya and Szegő. A historical note, not related to Fekete’s lemma thought, which I did not know myself before reading the biography of Szegő and I find it for some reason interesting to know:

At the age of 15, the young John von Neumann, recognised as a mathematical prodigy, was sent to study advanced calculus under Szegő. On their first meeting, Szegő was so astounded by von Neumann’s mathematical talent and speed that he was brought to tears. Szegő subsequently visited the von Neumann house twice a week to tutor the child prodigy. Some of von Neumann’s instant solutions to the problems in calculus posed by Szegő, sketched out with his father’s stationary, are now on display at the von Neumann archive at Budapest.

Fekete’s lemma is a very important lemma, which is used to prove that a certain limit exists. The only thing to be checked is the super-additivity property of the function of interest. Let’s be more exact. Let $N$ be the set of natural numbers and $R_{\geq 0}$ the set of non-negative reals. We shall call a function f super-additive if $f(m)+f(n) \leq f(m+n)$ for every $m,n \in N$ .

Fekete’s lemma: For every super-additive function $f$ the ratio $f(n)/n$ tends to a limit as $n\rightarrow +\infty$ .

Proof Sketch: Let $\lambda=\lim \sup_{n \rightarrow +\infty} f(n)/n$ . We distinguish two cases, $\lambda < +\infty, \lambda=+\infty$ .

Case 1, $\lambda < +\infty$ : Fix $\epsilon>0$ . We pick an $m$ (clearly there exists such one) such that that $f(m)/m>\lambda-\epsilon$ . Let $n_0$ be a sufficiently large constant (depending on $\lambda,\epsilon,m,f(1),..,f(m)$ and $n \geq n_0$. Then $n = qm+r$ and by the super-additivity property we obtain that $(\lambda+\epsilon)n \geq f(n) \geq \frac{n-r}{m} m(\lambda -\epsilon) + f(r) \geq n(\lambda-2\epsilon)$ . Letting latex $\epsilon \rightarrow 0$ we see that $\lim_{n \rightarrow +\infty} \frac{f(n)}{n} \rightarrow \lambda$ .