次可加性
次可加性这个工具，虽然只是技术性的，但是经常用到，比如我们经常用BK不等式导出一个满足次可加性的序列来。这个工具妙就妙在，看起来很弱的条件却能够得到很强的结论。这篇笔记总结一下序列/函数次可加性的一些推论。
一个次可加的函数定义为
比如说，\sqrt{x}就是次可加的。
一个次可加的序列定义为
需要注意的是，superadditivity和subadditivity可以通过取负号相互转化，所以下面的一系列性质都是共享的，只不过要把正负颠倒一下罢了。
关于次可加性，最重要和标准的结论就是：
【Fekete引理】对于次可加序列{a_n}，a_n/n的极限存在且等于\inf a_n/n \in [-\infty,infty)。
（Fekete, a Hungarian-Israeli mathematician）证明略去。下面仔细理解一下这个引理说的是什么。首先对于这个极限c做一下分类讨论。
如果c=-\infty。也就是说a_n非常快地下降到负无穷，当然也满足次可加性。
如果c在负无穷和0之间，也就述说a_n类似于一个负线性序列cn，二者的差距只有一个o(n)。
如果c=0，也就述说a_n=o(n)，比如说a_n=\sqrt{n}。
如果c>0，则也是a_n=cn+o(n)，接近于一个线性序列。
总的来说，如果一个序列次可加的话，要么它往下掉地飞快；如果不是（比较“平缓”），它一定是cn+o(n)的“近似线性”的形式。
Feteke引理里面还包含着更多的信息。因为极限是inf，所以a_n\geqslant cn。直观上来说，如果一个次可加序列下降地比较平稳，那么它一定是cn+o(n)的形式，并且这个o(n)项一定是一个非负数。（如果下降很快，相当于c=-\infty）【这样的表述比原定理的表述更加清晰，而且是等价的】
这也就是我一开始说的，看起来很弱的条件却能够得到很强的结论。这句话可以这样理解：
1.明明只是一个不等式，却能给出等式a_n=cn+o(n)来。（这样一个相当「精确」的等式放在平时只能做做指数估计的地方，比如关联长度，简直求之不得）
2.明明只是一个upper bound的不等式，却能给出lower bound（o(n)项非负）来。
Fekete引理对于次可加函数也成立：
【次可加函数的Fekete引理】
另外还有一些次可加性的推广，比如
其中的非递减的g_n增长不是很快，即
则类似Fekete引理的结论也成立：
还有更多类似的定理。
题图2:05 沈んだ街角を抜けて（79748144）by フワン(15150508)。
