Fekete's lemma

In mathematics, and in particular in calculus, Fekete's lemma (also called Fekete's subadditive lemma) is a lemma concerning the limit of subadditive sequences. The lemma provides an estimate for the linear growth rate of such sequences.

The lemma is named after the Hungarian-Israeli mathematician Michael Fekete, who proved it in 1923.

Statement of the theorem

In this article, $\mathbb {N}$ denotes the natural numbers. This set does not include the number 0.

A sequence of real numbers $\{a_{n}\}_{n=1}^{\infty }$ is called a subadditive sequence if and only if for all $m,n\in \mathbb {N}$ one has

$a_{n+m}\leq a_{n}+a_{m}.$

Fekete's lemma states that for every subadditive sequence,

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.$

That is, the sequence ${\frac {a_{n}}{n}}$ converges to its infimum. Note that this infimum may be $-\infty$.

Proof

To prove that the limit exists and equals the infimum, it suffices to show that

$\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}\leq \liminf _{n\to \infty }{\frac {a_{n}}{n}}\leq \limsup _{n\to \infty }{\frac {a_{n}}{n}}\leq \inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}},$

where $\liminf$ and $\limsup$ denote the limit inferior and limit superior, respectively. The two left inequalities always hold, so it is enough to prove the rightmost inequality

$\limsup _{n\to \infty }{\frac {a_{n}}{n}}\leq \inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.$

Since the sequence is subadditive, one can prove by induction that for all $m,n,l,k\in \mathbb {N}$,

$a_{nl+mk}\leq na_{l}+ma_{k}.$

Define $a_{0}=0$. Then this inequality also holds when one of the indices $m,n,l,k$ is 0.

Now fix some $q\in \mathbb {N}$. For every $n\in \mathbb {N}$ there exist $m\in \mathbb {N}$ and $0\leq r\leq q-1$ such that $n=mq+r$. Hence, by the inequality above,

$a_{n}\leq ma_{q}+a_{r}.$

Define $C_{q}=\max(a_{0},a_{1},\dots ,a_{q-1})$. Dividing the inequality above by $n$ yields

${\frac {a_{n}}{n}}\leq {\frac {ma_{q}+a_{r}}{n}}={\frac {ma_{q}}{n}}+{\frac {a_{r}}{n}}\leq {\frac {ma_{q}}{mq}}+{\frac {C_{q}}{n}}={\frac {a_{q}}{q}}+{\frac {C_{q}}{n}}.$

Taking the limit superior as $n\to \infty$, we obtain $\limsup _{n\to \infty }{\frac {a_{n}}{n}}\leq {\frac {a_{q}}{q}}.$

Since $q$ was arbitrary, this holds for all $q$, and therefore

$\limsup _{n\to \infty }{\frac {a_{n}}{n}}\leq \inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.$

Combining the inequalities, we conclude that

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.$

∎

Examples

Square root

Define a sequence $\{a_{n}\}_{n=1}^{\infty }$ by, for all $n\in \mathbb {N}$,

$a_{n}:=n+{\sqrt {n}}.$

One can show that this sequence is subadditive, since for all $n,m\in \mathbb {N}$,

$a_{n+m}=n+m+{\sqrt {n+m}}\leq n+m+{\sqrt {n}}+{\sqrt {m}}=a_{n}+a_{m}.$

Indeed,

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {n+{\sqrt {n}}}{n}}=1.$

Integer value

Let $0<c\in \mathbb {R}$. Define a sequence $\{a_{n}\}_{n=1}^{\infty }$ by, for all $n\in \mathbb {N}$,

$a_{n}:=\lceil cn\rceil ,$

where $\lceil \cdot \rceil$ denotes the ceiling function. The sequence is subadditive, since for all $n,m\in \mathbb {N}$,

$a_{n+m}=\lceil c(n+m)\rceil =\lceil cn+cm\rceil \leq \lceil cn\rceil +\lceil cm\rceil =a_{n}+a_{m}.$

Indeed,

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {\lceil cn\rceil }{n}}=c.$

Corollaries

Superadditive sequences

A sequence of real numbers $\{a_{n}\}_{n=1}^{\infty }$ is called superadditive if and only if for all $m,n\in \mathbb {N}$,

$a_{n+m}\geq a_{n}+a_{m}.$

Using Fekete's lemma, one can show that for every superadditive sequence,

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\sup _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.$

That is, the sequence ${\frac {a_{n}}{n}}$ converges to its supremum. As in the subadditive case, this supremum may be $\infty$.

The proof follows by applying Fekete's lemma to the sequence $b_{n}:=-a_{n}$.

Submultiplicative sequences

A sequence of real numbers $\{a_{n}\}_{n=1}^{\infty }$ is called submultiplicative if and only if for all $m,n\in \mathbb {N}$,

$a_{n+m}\leq a_{n}a_{m}.$

Using Fekete's lemma, one can show that for every submultiplicative sequence with positive terms,

$\lim _{n\to \infty }{\sqrt[{n}]{a_{n}}}=\inf _{n\in \mathbb {N} }{\sqrt[{n}]{a_{n}}}.$

The proof follows by applying Fekete's lemma to the sequence $b_{n}:=\ln a_{n}$, where $\ln$ denotes the natural logarithm.

Note that since Fekete's lemma for submultiplicative sequences applies only to positive sequences, the infimum is necessarily finite and nonnegative. This fact has important applications, for example:

• Any power series whose coefficients have absolute values forming a submultiplicative sequence has a positive radius of convergence (the Cauchy–Hadamard theorem).

• Every lattice admits a connective constant describing the growth rate of the number of possible self-avoiding walks.

Almost subadditive sequence

Let $\{a_{n}\}_{n=1}^{\infty }$ be a sequence of real numbers for which there exists $C\in \mathbb {R}$ such that for all $m,n\in \mathbb {N}$,

$a_{n+m}\leq a_{n}+a_{m}+C.$

Such a sequence is called almost subadditive. Then,

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}+C}{n}}.$

Proof

Define a new sequence $b_{n}:=a_{n}+C$. It is subadditive, since

$b_{n+m}=a_{n+m}+C\leq a_{n}+a_{m}+C+C=b_{n}+b_{m}.$

Therefore,

$\lim _{n\to \infty }{\frac {b_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {b_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}+C}{n}}.$

On the other hand,

$\left|{\frac {b_{n}}{n}}-{\frac {a_{n}}{n}}\right|={\frac {C}{n}}\to 0,$

so the two sequences have the same limit. Hence,

$\lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}+C}{n}}.$

∎

See also

• Kingman's subadditive ergodic theorem