# 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$.

Case 2, $\lambda=+\infty$. Left as an exercise. Mimick the argument above.

QED

As an exercise, try to prove the following by applying the Lemma above.

Exercise: Let $f(k)=R(3,..,3)$=k-color Ramsey number of triangles. Prove that $f(k)^{1/k}$ tends to a limit.

Advertisements