読者です 読者をやめる 読者になる 読者になる

tokoharuの落書き帳

らくがきですよ

Fekete's lemma

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

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}