弱正則化補題 (Frieze, Kannan) 
を有限集合とし、
および
をとる。このとき、
, ![a \in [A], b \in [B]](http://chart.apis.google.com/chart?cht=tx&chl=a%20%5Cin%20%5BA%5D%2C%20b%20%5Cin%20%5BB%5D)
毎に
, 分割
が存在して、任意の
に対して![\displaystyle \left| \#\{(\mathbf{F}\times \mathbf{G}) \cap \mathbf{E}\} - \sum_{a \in [A]}\sum_{b \in [B]}d_{a, b}\#\{\mathbf{F} \cap \mathbf{V}_a\}\cdot \#\{\mathbf{G} \cap \mathbf{W}_b\}\right| \leq \varepsilon \#\mathbf{V}\cdot \#\mathbf{W}](http://chart.apis.google.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5Cleft%7C%20%5C%23%5C%7B%28%5Cmathbf%7BF%7D%5Ctimes%20%5Cmathbf%7BG%7D%29%20%5Ccap%20%5Cmathbf%7BE%7D%5C%7D%20-%20%5Csum_%7Ba%20%5Cin%20%5BA%5D%7D%5Csum_%7Bb%20%5Cin%20%5BB%5D%7Dd_%7Ba%2C%20b%7D%5C%23%5C%7B%5Cmathbf%7BF%7D%20%5Ccap%20%5Cmathbf%7BV%7D_a%5C%7D%5Ccdot%20%5C%23%5C%7B%5Cmathbf%7BG%7D%20%5Ccap%20%5Cmathbf%7BW%7D_b%5C%7D%5Cright%7C%20%5Cleq%20%5Cvarepsilon%20%5C%23%5Cmathbf%7BV%7D%5Ccdot%20%5C%23%5Cmathbf%7BW%7D)
が成り立つ。
これは次の記事で証明する。ここでは、後で使う系を導出する。
系 を有限集合とし、および
毎に
をとる。このとき、
, ![a \in [A], w \in \mathbf{W}](http://chart.apis.google.com/chart?cht=tx&chl=a%20%5Cin%20%5BA%5D%2C%20w%20%5Cin%20%5Cmathbf%7BW%7D)
毎に
, 分割
が存在して、任意の
に対して![\displaystyle \left| \#\{\mathbf{F} \cap \mathbf{E}_w\} - \sum_{a \in [A]}c_{a, w}\#\{\mathbf{F}\cap \mathbf{V}_a\}\right| \leq \varepsilon \#\mathbf{V}](http://chart.apis.google.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5Cleft%7C%20%5C%23%5C%7B%5Cmathbf%7BF%7D%20%5Ccap%20%5Cmathbf%7BE%7D_w%5C%7D%20-%20%5Csum_%7Ba%20%5Cin%20%5BA%5D%7Dc_%7Ba%2C%20w%7D%5C%23%5C%7B%5Cmathbf%7BF%7D%5Ccap%20%5Cmathbf%7BV%7D_a%5C%7D%5Cright%7C%20%5Cleq%20%5Cvarepsilon%20%5C%23%5Cmathbf%7BV%7D)
が高々
個のを除いて成立する。
証明. とし、
として弱正則化補題を適用する。すると、
,
毎に
, 分割
が存在して、任意のに対して
が成り立つ。のとき
と定義する。
の定義から
が成り立ち、に対して
が成り立つので、
と書き直すことができる。これを、として
のそれぞれに適用して足し合わせると
を得る。
と不等式評価できるので
が得られ、これが主張していたことであった。 Q.E.D.
最後の不等式評価はMarkovの不等式およびその証明そのものである。今後は同じ変形は省略する。