クラフトの不等式
すると F ( X ) {\displaystyle F(X)} の定義より、多項式 ( F ( X ) ) m = ∑ l q l X − l {\displaystyle \left(F(X)\right)^{m}=\sum _{\ell }q_{\ell }\,X^{-\ell }} の最低次の項の次数はm minであり、最高次の項の次数はm maxである。
以上の議論より、
( F ( r ) ) m = ∑ l q l r − l ≤ ∑ l r l r − l = ∑ l 1 ≤ m ( m a x − m i n + 1 ) {\displaystyle \left(F(r)\right)^{m}=\sum _{\ell }q_{\ell }\,r^{-\ell }\leq \sum _{\ell }r^{\ell }\,r^{-\ell }=\sum _{\ell }1\leq m(max-min+1)}
が成立する。
mは任意だったので上の不等式は任意のmに対して成立する。mを無限大に飛ばしたとき、左辺は指数関数的に変化するのに対し、右辺は線形にしか増加しない。従って任意のmに対して上の不等式が成立する事から
F ( r ) ≤ 1 {\displaystyle F(r)\leq 1}
が成立する。 l i = | φ ( s i ) | {\displaystyle \ell _{i}=|\phi (s_{i})|} とすれば、 F ( X ) {\displaystyle F(X)} の定義より、
1 ≥ F ( r ) = ∑ i = 1 n r − l i {\displaystyle 1\geq F(r)=\sum _{i=1}^{n}r^{-\ell _{i}}}
が成立する。すなわち、クラフトの不等式が証明された。