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.^[1]

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

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

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

Fekete’s lemma states that for every subadditive sequence,

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

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

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

${\displaystyle \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 ${\displaystyle \liminf }$ and ${\displaystyle \limsup }$ denote the limit inferior and limit superior, respectively. The two left inequalities always hold, so it is enough to prove the rightmost inequality ${\displaystyle \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 ${\displaystyle m,n,l,k\in \mathbb {N} }$,

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

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

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

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

Define ${\displaystyle C_{q}=\max(a_{0},a_{1},\dots ,a_{q-1})}$. This value is always well defined, since it is the maximum of a finite set. Dividing the inequality above by ${\displaystyle n}$ yields

${\displaystyle {\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 ${\displaystyle n\to \infty }$, we obtain ${\displaystyle \limsup _{n\to \infty }{\frac {a_{n}}{n}}\leq {\frac {a_{q}}{q}}.}$ Since ${\displaystyle q}$ was arbitrary, this holds for all ${\displaystyle q}$, and therefore

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

Combining the inequalities, we conclude that

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

∎

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

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

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

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

Indeed,

${\displaystyle \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.}$

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

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

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

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

Indeed,

${\displaystyle \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.}$

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

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

Using Fekete’s lemma, one can show that for every superadditive sequence,^[2]

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

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

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

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

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

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

${\displaystyle \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 ${\displaystyle b_{n}:=\ln a_{n}}$, where ${\displaystyle \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.

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

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

Such a sequence is called almost subadditive. Then,

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

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

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

Therefore,

${\displaystyle \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, ${\displaystyle \left|{\frac {b_{n}}{n}}-{\frac {a_{n}}{n}}\right|={\frac {C}{n}}\to 0,}$ so the two sequences have the same limit. Hence,

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

∎