次可加性
次可加性這個(gè)工具，雖然只是技術(shù)性的，但是經(jīng)常用到，比如我們經(jīng)常用BK不等式導(dǎo)出一個(gè)滿足次可加性的序列來。這個(gè)工具妙就妙在，看起來很弱的條件卻能夠得到很強(qiáng)的結(jié)論。這篇筆記總結(jié)一下序列/函數(shù)次可加性的一些推論。
一個(gè)次可加的函數(shù)定義為
比如說，\sqrt{x}就是次可加的。
一個(gè)次可加的序列定義為
需要注意的是，superadditivity和subadditivity可以通過取負(fù)號相互轉(zhuǎn)化，所以下面的一系列性質(zhì)都是共享的，只不過要把正負(fù)顛倒一下罷了。
關(guān)于次可加性，最重要和標(biāo)準(zhǔn)的結(jié)論就是：
【Fekete引理】對于次可加序列{a_n}，a_n/n的極限存在且等于\inf a_n/n \in [-\infty,infty)。
（Fekete, a?Hungarian-Israeli?mathematician）證明略去。下面仔細(xì)理解一下這個(gè)引理說的是什么。首先對于這個(gè)極限c做一下分類討論。
如果c=-\infty。也就是說a_n非?？斓叵陆档截?fù)無窮，當(dāng)然也滿足次可加性。
如果c在負(fù)無窮和0之間，也就述說a_n類似于一個(gè)負(fù)線性序列cn，二者的差距只有一個(gè)o(n)。
如果c=0，也就述說a_n=o(n)，比如說a_n=\sqrt{n}。
如果c>0，則也是a_n=cn+o(n)，接近于一個(gè)線性序列。
總的來說，如果一個(gè)序列次可加的話，要么它往下掉地飛快；如果不是（比較“平緩”），它一定是cn+o(n)的“近似線性”的形式。
Feteke引理里面還包含著更多的信息。因?yàn)闃O限是inf，所以a_n\geqslant cn。直觀上來說，如果一個(gè)次可加序列下降地比較平穩(wěn)，那么它一定是cn+o(n)的形式，并且這個(gè)o(n)項(xiàng)一定是一個(gè)非負(fù)數(shù)。（如果下降很快，相當(dāng)于c=-\infty）【這樣的表述比原定理的表述更加清晰，而且是等價(jià)的】
這也就是我一開始說的，看起來很弱的條件卻能夠得到很強(qiáng)的結(jié)論。這句話可以這樣理解：
1.明明只是一個(gè)不等式，卻能給出等式a_n=cn+o(n)來。（這樣一個(gè)相當(dāng)「精確」的等式放在平時(shí)只能做做指數(shù)估計(jì)的地方，比如關(guān)聯(lián)長度，簡直求之不得）
2.明明只是一個(gè)upper bound的不等式，卻能給出lower bound（o(n)項(xiàng)非負(fù)）來。
Fekete引理對于次可加函數(shù)也成立：
【次可加函數(shù)的Fekete引理】
另外還有一些次可加性的推廣，比如
其中的非遞減的g_n增長不是很快，即
則類似Fekete引理的結(jié)論也成立：
還有更多類似的定理。
題圖2:05 沈んだ街角を抜けて（79748144）by?フワン(15150508)。
