From Surf Wiki (app.surf) — the open knowledge base
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.
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.
In this article,
N
{\displaystyle \mathbb {N} }
denotes the natural numbers. This set does not include the number 0.
A sequence of real numbers
{
a
n
}
n
=
1
∞
{\displaystyle \{a_{n}\}_{n=1}^{\infty }}
is called a subadditive sequence if and only if for all
m
,
n
∈
N
{\displaystyle m,n\in \mathbb {N} }
one has
a
n
+
m
≤
a
n
+
a
m
.
{\displaystyle a_{n+m}\leq a_{n}+a_{m}.}
Fekete’s lemma states that for every subadditive sequence,
lim
n
→
∞
a
n
n
=
inf
n
∈
N
a
n
n
.
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.}
That is, the sequence
a
n
n
{\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
inf
n
∈
N
a
n
n
≤
lim inf
n
→
∞
a
n
n
≤
lim sup
n
→
∞
a
n
n
≤
inf
n
∈
N
a
n
n
,
{\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
lim inf
{\displaystyle \liminf }
and
lim sup
{\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
lim sup
n
→
∞
a
n
n
≤
inf
n
∈
N
a
n
n
.
{\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
m
,
n
,
l
,
k
∈
N
{\displaystyle m,n,l,k\in \mathbb {N} }
,
a
n
l
+
m
k
≤
n
a
l
+
m
a
k
.
{\displaystyle a_{nl+mk}\leq na_{l}+ma_{k}.}
Define
a
0
=
0
{\displaystyle a_{0}=0}
. Then this inequality also holds when one of the indices
m
,
n
,
l
,
k
{\displaystyle m,n,l,k}
is 0.
Now fix some
q
∈
N
{\displaystyle q\in \mathbb {N} }
. For every
n
∈
N
{\displaystyle n\in \mathbb {N} }
there exist
m
∈
N
{\displaystyle m\in \mathbb {N} }
and
0
≤
r
≤
q
−
1
{\displaystyle 0\leq r\leq q-1}
such that
n
=
m
q
+
r
{\displaystyle n=mq+r}
. Hence, by the inequality above,
a
n
≤
m
a
q
+
a
r
.
{\displaystyle a_{n}\leq ma_{q}+a_{r}.}
Define
C
q
=
max
(
a
0
,
a
1
,
…
,
a
q
−
1
)
{\displaystyle C_{q}=\max(a_{0},a_{1},\dots ,a_{q-1})}
. Dividing the inequality above by
n
{\displaystyle n}
yields
a
n
n
≤
m
a
q
+
a
r
n
=
m
a
q
n
+
a
r
n
≤
m
a
q
m
q
+
C
q
n
=
a
q
q
+
C
q
n
.
{\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
n
→
∞
{\displaystyle n\to \infty }
, we obtain
lim sup
n
→
∞
a
n
n
≤
a
q
q
.
{\displaystyle \limsup _{n\to \infty }{\frac {a_{n}}{n}}\leq {\frac {a_{q}}{q}}.}
Since
q
{\displaystyle q}
was arbitrary, this holds for all
q
{\displaystyle q}
, and therefore
lim sup
n
→
∞
a
n
n
≤
inf
n
∈
N
a
n
n
.
{\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
lim
n
→
∞
a
n
n
=
inf
n
∈
N
a
n
n
.
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.}
∎
Define a sequence
{
a
n
}
n
=
1
∞
{\displaystyle \{a_{n}\}_{n=1}^{\infty }}
by, for all
n
∈
N
{\displaystyle n\in \mathbb {N} }
,
a
n
:=
n
+
n
.
{\displaystyle a_{n}:=n+{\sqrt {n}}.}
One can show that this sequence is subadditive, since for all
n
,
m
∈
N
{\displaystyle n,m\in \mathbb {N} }
,
a
n
+
m
=
n
+
m
+
n
+
m
≤
n
+
m
+
n
+
m
=
a
n
+
a
m
.
{\displaystyle a_{n+m}=n+m+{\sqrt {n+m}}\leq n+m+{\sqrt {n}}+{\sqrt {m}}=a_{n}+a_{m}.}
Indeed,
lim
n
→
∞
a
n
n
=
inf
n
∈
N
a
n
n
=
inf
n
∈
N
n
+
n
n
=
1.
{\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
0
<
c
∈
R
{\displaystyle 0
. Define a sequence
{
a
n
}
n
=
1
∞
{\displaystyle \{a_{n}\}_{n=1}^{\infty }}
by, for all
n
∈
N
{\displaystyle n\in \mathbb {N} }
,
a
n
:=
⌈
c
n
⌉
,
{\displaystyle a_{n}:=\lceil cn\rceil ,}
where
⌈
⋅
⌉
{\displaystyle \lceil \cdot \rceil }
denotes the ceiling function. The sequence is subadditive, since for all
n
,
m
∈
N
{\displaystyle n,m\in \mathbb {N} }
,
a
n
+
m
=
⌈
c
(
n
+
m
)
⌉
=
⌈
c
n
+
c
m
⌉
≤
⌈
c
n
⌉
+
⌈
c
m
⌉
=
a
n
+
a
m
.
{\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,
lim
n
→
∞
a
n
n
=
inf
n
∈
N
a
n
n
=
inf
n
∈
N
⌈
c
n
⌉
n
=
c
.
{\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
{
a
n
}
n
=
1
∞
{\displaystyle \{a_{n}\}_{n=1}^{\infty }}
is called superadditive if and only if for all
m
,
n
∈
N
{\displaystyle m,n\in \mathbb {N} }
,
a
n
+
m
≥
a
n
+
a
m
.
{\displaystyle a_{n+m}\geq a_{n}+a_{m}.}
Using Fekete’s lemma, one can show that for every superadditive sequence,
lim
n
→
∞
a
n
n
=
sup
n
∈
N
a
n
n
.
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=\sup _{n\in \mathbb {N} }{\frac {a_{n}}{n}}.}
That is, the sequence
a
n
n
{\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
b
n
:=
−
a
n
{\displaystyle b_{n}:=-a_{n}}
.
A sequence of real numbers
{
a
n
}
n
=
1
∞
{\displaystyle \{a_{n}\}_{n=1}^{\infty }}
is called submultiplicative if and only if for all
m
,
n
∈
N
{\displaystyle m,n\in \mathbb {N} }
,
a
n
+
m
≤
a
n
a
m
.
{\displaystyle 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
→
∞
a
n
n
=
inf
n
∈
N
a
n
n
.
{\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
b
n
:=
ln
a
n
{\displaystyle b_{n}:=\ln a_{n}}
, where
ln
{\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
{
a
n
}
n
=
1
∞
{\displaystyle \{a_{n}\}_{n=1}^{\infty }}
be a sequence of real numbers for which there exists
C
∈
R
{\displaystyle C\in \mathbb {R} }
such that for all
m
,
n
∈
N
{\displaystyle m,n\in \mathbb {N} }
,
a
n
+
m
≤
a
n
+
a
m
+
C
.
{\displaystyle a_{n+m}\leq a_{n}+a_{m}+C.}
Such a sequence is called almost subadditive. Then,
lim
n
→
∞
a
n
n
=
inf
n
∈
N
a
n
+
C
n
.
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}+C}{n}}.}
Define a new sequence
b
n
:=
a
n
+
C
{\displaystyle b_{n}:=a_{n}+C}
. It is subadditive, since
b
n
+
m
=
a
n
+
m
+
C
≤
a
n
+
a
m
+
C
+
C
=
b
n
+
b
m
.
{\displaystyle b_{n+m}=a_{n+m}+C\leq a_{n}+a_{m}+C+C=b_{n}+b_{m}.}
Therefore,
lim
n
→
∞
b
n
n
=
inf
n
∈
N
b
n
n
=
inf
n
∈
N
a
n
+
C
n
.
{\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,
|
b
n
n
−
a
n
n
|
=
C
n
→
0
,
{\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,
lim
n
→
∞
a
n
n
=
inf
n
∈
N
a
n
+
C
n
.
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf _{n\in \mathbb {N} }{\frac {a_{n}+C}{n}}.}
∎
- Kingman's subadditive ergodic theorem
Ask Mako anything about Fekete's lemma — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report