Feketeの補題

1. $a_n=1$（定数）は $1\le1+1$ なので劣加法的で、$a_n/n=1/n\to0=\inf_ma_m/m$ である。下限は達成されない。
2. $a_n=-n^2$ は $-(m+n)^2=-m^2-n^2-2mn\le-m^2-n^2$ なので劣加法的で、$a_n/n=-n\to-\infty$ である。極限は $-\infty$ になりうる。
3. $a_n=\sqrt n$ は $\sqrt{m+n}\le\sqrt m+\sqrt n$（両辺を 2 乗）なので劣加法的で、$a_n/n\to0$ である。
4. 誤差つきの劣加法性 $a_{m+n}\le a_m+a_n+C$（$C\ge0$ は定数）でも、$a_n/n$ の極限は存在する。$a_n+C$ が劣加法的になり、$(a_n+C)/n$ と $a_n/n$ の極限は一致するからである。ただし極限は $\inf_m(a_m+C)/m$ で、$\inf_ma_m/m$ とは一致しないことがある（$a_n=-1$、$C=1$ では極限 $0$、下限 $-1$）。

$T$ を実または複素の Banach 空間 $X$ 上の有界作用素とする。$b_n:=\|T^n\|$ は $\|T^{m+n}\|\le\|T^m\|\,\|T^n\|$ により劣乗法的なので、cor-fek-submultiplicative により
$$ r(T):=\lim_{n\to\infty}\|T^n\|^{1/n}=\inf_{m\ge1}\|T^m\|^{1/m}\le\|T\| $$
が存在する。冪零な $T$（ある $m$ で $T^m=0$）では $\log\|T^n\|$ が実数にならないが、乗法版ではその場合も含めて扱える。複素の場合、この極限がスペクトルの絶対値の最大値に等しいことが Gelfand の公式である（スペクトル半径 の命題「冪のノルムの根の極限」と定理「Gelfand のスペクトル半径公式」）。Bre11 の演習 6.23（pp. 177–178）は、実 Banach 空間の上で $a_n=\log\|T^n\|$ の劣加法性からこの極限を導き、スペクトルとの関係を調べる形になっている。
たとえば $L^p(0,1)$（$1\le p\le\infty$）上の Volterra 作用素 $(Vu)(t)=\int_0^tu(s)\,ds$ は $\|V^n\|\le1/n!$ を満たす（Volterra作用素）。$n!\ge(n/2)^{n/2}$（$n!$ の後ろ半分の因子はどれも $n/2$ 以上）から $(1/n!)^{1/n}\le(2/n)^{1/2}\to0$ なので、$r(V)=0$ である。

$d\ge1$ とする。$\mathbb Z^d$ の原点から出発し、各歩で座標の 1 つを $\pm1$ だけ動かす $n$ 歩の道 $(x_0=0,x_1,\dots,x_n)$ のうち、点 $x_0,\dots,x_n$ がすべて異なるものを 自己回避歩行 といい、その個数を $c_n$ とする。

1. $c_{m+n}\le c_mc_n$ である。$m+n$ 歩の自己回避歩行を、最初の $m$ 歩と、残りの $n$ 歩を $x_m$ が原点に来るよう平行移動したものに分けると、どちらも自己回避歩行であり、元の道はこの組から復元できる。よって写像は単射である。
2. $d^n\le c_n\le2d(2d-1)^{n-1}$ である。座標が増える向きの $d$ 通りの歩だけを使う道は、座標の和が毎歩 $1$ ずつ増えるので自己回避であり、$d^n$ 本ある。上からは、最初の歩は $2d$ 通り、その後の各歩は直前の点に戻れないので $2d-1$ 通り以下である。
   cor-fek-submultiplicative により、極限 $\mu_d:=\lim_nc_n^{1/n}=\inf_nc_n^{1/n}$ が存在し、2 から $d\le\mu_d\le2d-1$ である。この $\mu_d$ を 連結定数 という。$c_n$ の正確な式は知られていないが、指数的な増え方の率は Feketeの補題だけで確定する。

有限集合 $A$ の元を並べた有限列（語）の集合 $L$ が、語の連続した部分を取り出す操作で閉じているとする。長さ $n$ の $L$ の語の数を $N(n)$ とすると、長さ $m+n$ の語は長さ $m$ の頭と長さ $n$ の尾に一意に分かれ、どちらも $L$ に入るので $N(m+n)\le N(m)N(n)$ である。よって $\lim_nN(n)^{1/n}$ が存在する（記号力学ではその対数を位相的エントロピーと呼ぶ）。
$A=\{0,1\}$ で、$11$ を含まない語の全体を $L$ とすると、長さ $n\ge3$ の語は末尾が $0$ なら長さ $n-1$ の語に $0$ を、末尾が $1$ なら長さ $n-2$ の語に $01$ を付けたものなので、$N(n)=N(n-1)+N(n-2)$、$N(1)=2$、$N(2)=3$ である。$N(n)$ は Fibonacci数 $F_{n+2}$ で、$N(n)^{1/n}\to\frac{1+\sqrt5}2$ である。

有限集合に値をとる確率変数の列 $X_1,X_2,\dots$ が 定常 である、すなわち各 $n$ について $(X_{k+1},\dots,X_{k+n})$ の同時分布が $k\ge0$ によらないとする。$H_n:=H(X_1,\dots,X_n)$（エントロピー）とおくと、同記事の定理「連鎖律と劣加法性」により $H_{m+n}\le H(X_1,\dots,X_m)+H(X_{m+1},\dots,X_{m+n})$ で、定常性から第 2 項は $H_n$ に等しい。よって $(H_n)$ は劣加法的で、$H_n\ge0$ なので極限 $\lim_nH_n/n=\inf_nH_n/n\in[0,\infty)$ が存在する。これを列の エントロピー率 という。

$k\ge2$ とし、$X_1,X_2,\dots$ と $Y_1,Y_2,\dots$ を $\{1,\dots,k\}$ の上の一様分布に従う独立な確率変数とする。語 $X_1\cdots X_n$ と $Y_1\cdots Y_n$ の共通部分列（両方から文字を順序を保って取り出して得られる同じ語）の最大の長さを $L_n$ とし、$\ell_n:=\mathbb E[L_n]$ とおく。
$X_1\cdots X_m$ と $Y_1\cdots Y_m$ の最長共通部分列の後ろに、$X_{m+1}\cdots X_{m+n}$ と $Y_{m+1}\cdots Y_{m+n}$ の最長共通部分列をつなげると、長さ $m+n$ の 2 語の共通部分列になる。後半の 2 語の組は前半と同じ分布なので、期待値をとって $\ell_{m+n}\ge\ell_m+\ell_n$ である。$\ell_n\le n$ なので、prop-fek-superadditive により極限 $\gamma_k:=\lim_n\ell_n/n=\sup_n\ell_n/n\in(0,1]$ が存在する（$\ell_1=1/k>0$）。$\gamma_k$ の正確な値は一般には知られていないが、存在は Feketeの補題だけで分かる。

1 行目：$a_{2n}=0\le2a_n$（$a_n\ge0$）なので弱い条件は満たす。$a_3=3>a_1+a_2=1+0$ なので劣加法的ではない。$a_n/n$ は奇数番目で $1$、偶数番目で $0$ なので収束しない。
2 行目：加法的関数 $f(s+t)=f(s)+f(t)$ は劣加法的である。一次関数でない加法的関数は選択公理を使って作れ、そのグラフは $\mathbb R^2$ で稠密である（Hamel基底 の定理「一次関数でない加法的関数」）。任意の $c\in\mathbb R$ と $T>0$ について、点 $(T+1,c(T+1))$ の近くにグラフの点 $(t,f(t))$ があり、$t>T$、$\lvert f(t)/t-c\rvert<1$ とできる。よって $c$ と $c'$ が離れていれば、$f(t)/t$ は $t\to\infty$ で $c$ の近くの値と $c'$ の近くの値を何度もとり、収束しない。このような $f$ はどの区間の上でも上に有界でない（同記事の定理「一次関数になる条件」）。