Fekete's lemma

1. The lemma

We give a very elegant (and useful) application of the idea of supremum and infimum. This result is attributed to Michael Fekete, and gets applied in many places, including number theory, combinatorics, and analysis. First, a definition.

Definition.

A sequence ( a n ) of nonnegative terms is subadditive if a n + m a n + a m for all n , m .

Fekete's lemma.

Let ( a n ) be a subadditive sequence of nonnegative terms a n . Then ( a n n ) is bounded below and converges to inf { a n n : n } .

Proof.

To see that the sequence is bounded below, just note that a n 0 so a n n 0 for each n .

Now let l = inf { a n n : n } . We must prove that a n n l .

Subproof.

Let ε > 0 be arbitrary.

Subproof.

Let K such that | a K K - l | < ε / 2 . There is some such K , since if not l + ε / 2 would also be a lower bound, contradicting the fact that l is the greatest lower bound.

Let M be such that a r K M < ε / 2 for all r = 0 , 1 , 2 , , K - 1 . To find such an M just find R = max { a r K : r < K } and choose M so that R / M < ε / 2 .

Let N = K M .

Subproof.

Let n N be arbitrary.

Let r , s such that n = s K + r with r < K . So s M .

Then a n n s a K s K + r + a r s K + r s a K s K + a r K M a K K + a r K M < ( l + ε / 2 ) + ε / 2 since a K K < l + ε / 2 . This means that | a n n - l | < ε since a n n l by the definition of l .

Therefore n N   | a n n - l | < ε .

Therefore N   n N   | a n n - l | < ε .

Therefore ε > 0   N   n N   | a n n - l | < ε .

For an example of a subadditive sequences, consider a n = n . It is easy to check a n + m = n + m n + m . Fekete's lemma says that ( a n n ) converges. So it does: to 0 ; this isn't terribly difficult and left as an exercise. Other easy examples of subadditive sequences include b n = n , for which ( b n n ) is a constant sequence converging to 1 .