Fekete's lemma - tokoharuの落書き帳

一つ前の記事と似てるような似てないような、なので書いておく

$x$ を数列とする。任意の $k,l \geq 1$ に対して
$x_{k+l} \geq x_k + x_l$ (優加法性) を満たすならば、
$\lim_{k \to \infty} x_k / k = \sup_{k} x_k / k$ を満たす

直感的には、とりあえず $x_k / k$ が(どこかから)非減少列であることを示せてしまえればよさそうに見える。
しかし、この方針では厳しい。たとえば、
$x = (1,2,11,12,21,22,...)$ のように $x_{2a+1} = 10a+1, x_{2a+2} = 10a+2$ ととれば優加法性を満たし、かつ
$a$ を大きくとることによって $x_{2a+1}/(2a+1)>x_{2a+2}/(2a+2)$ となる。

ということで、別の方針で示す必要がある。証明はCombinatorial Optimization (Schrijver)の2章の証明に説明を少し追加したものである。

$i,j,k \geq 1$ とする
優加法性から $x_{jk+i} \geq j x_k + x_i$
$i,k$ を固定して
$\liminf_{j \to \infty} x_{jk+i}/(jk+i) \geq \liminf_{j \to \infty} \frac{jx_k + x_i}{jk+i}$
$= \liminf_{j \to \infty} \frac{x_k}{k} \frac{jk}{jk+i} + \frac{x_i}{jk+i}$
$= \frac{x_k}{k}$
最後の式はlimを飛ばして(無限大にもなりうるが)収束するのでliminfでも大丈夫。
また、この変形の最後で $i$ を含まなかったので次のようにできる
$\liminf_{n \to \infty} \frac{x_n}{n} = \inf_i \liminf_{j \to \infty} \frac{x_{jk+i}}{jk+i} \geq \frac{x_k}{k}$
よって、
$\liminf_{n \to \infty} \frac{x_n}{n} \geq \sup_k \frac{x_k}{k}$ とできる。

liminfとlimsupの定義から、
$\liminf_{n \to \infty} \frac{x_n}{n} \leq \limsup_{n \to \infty} \frac{x_n}{n} \leq \sup_n \frac{x_n}{n}$ なので、先ほどの式とあわせることで、これらには等式が成り立つことがわかる。

結局、liminfとlimsupが一致したので、limが存在することがわかり、 $\lim_{n \to \infty} \frac{x_n}{n} = \sup_n \frac{x_n}{n}$