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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: