16.4 数え上げへの応用

16.1 節から 16.3 節までの不等式は，系 16.3.4 が集合の関数一般へ広げたのを別にすれば，どれも確率変数の族についてのものだった．本節はその族に，有限集合の上の一様分布から作った変数を置く．そうすると全体のエントロピーが集合の要素数の対数になり，部分集合についてのエントロピーは，座標の一部だけを見た像の要素数の対数で上から押さえられる．こうして定理 16.3.1 は，確率の出てこない数え上げの不等式に化ける．得られるのは，有限集合の大きさを，座標を落として得られる影の大きさの積で上から押さえる不等式である． $3$ 次元で言えば， $X 3$ の部分集合について，三つの座標平面への影にあたる射影の要素数の積が，元の集合の要素数の $2$ 乗を上から押さえる，という形になる．

定義 16.4.1（射影）. $𝑛 \geq 1$ とし， $X$ を有限集合とする． $X 𝑛$ で ${1, \dots, 𝑛}$ から $X$ への関数の全体を表し， $𝐴$ をその部分集合とする． $𝑆 \subseteq {1, \dots, 𝑛}$ に対し， $𝐴$ の各元を $𝑆$ の座標だけに切り詰めて得られる集合

𝜋 𝑆 (𝐴) : = {𝑥 | 𝑆 : 𝑥 \in 𝐴}

を $𝐴$ の $𝑆$ への射影と呼ぶ（ $𝑥 | 𝑆$ は $𝑥$ の定義域を $𝑆$ に狭めた関数である）． $𝑆 = {1, \dots, 𝑛} ∖ {𝑖}$ のときは $𝜋 - 𝑖 (𝐴)$ とも書く．

この $𝜋$ はつねに添字 $𝑆$ と引数 $𝐴$ の両方をとる写像であり，円周率とは形が違う． $𝜋 𝑆 (𝐴)$ は $𝑆$ から $X$ への関数の全体の部分集合で， $| 𝑆 | = 1$ のときの $𝜋 {𝑖} (𝐴)$ は， $𝐴$ の元の第 $𝑖$ 座標として現れる値の全体にあたる．以下， $X 𝑛$ の元は $𝑛$ 個の値の組として書く．

形式化: projectionSubset (ソース)， $1$ 座標を落とす場合 projectionExcept (ソース)

不等式を数え上げに移す道具は二つある．一つは定義 16.1.1 の族の作り方で， $𝐴$ の上の一様分布に従う確率変数 $𝑋$ をとり，その第 $𝑖$ 座標を $𝑋 𝑖$ と置く．もう一つは，対数で書かれた不等式の両辺から $l o g$ をはずす操作である．そのために， $l o g$ が正の実数の全体から実数の全体への狭義単調な全単射であることと，正の数 $𝑢$ ， $𝑣$ と実数 $𝑚$ について $l o g (𝑢 𝑣) = l o g 𝑢 + l o g 𝑣$ および $l o g 𝑢 𝑚 = 𝑚 l o g 𝑢$ が成り立つことを既知とする．

定理 16.4.2（Loomis–Whitney の不等式）. $𝑛 \geq 1$ とし， $X$ を有限集合， $𝐴 \subseteq X 𝑛$ を空でない部分集合とすると

| 𝐴 | 𝑛 - 1 \leq 𝑛 \prod 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) |

である．

証明. $𝐴$ の上の一様分布に従う確率変数 $𝑋$ をとり， $1 \leq 𝑖 \leq 𝑛$ に対し $𝑋 𝑖$ を $𝑋$ の第 $𝑖$ 座標とする．どの $𝑋 𝑖$ も $X$ に値をとるから， $𝑋 1, \dots, 𝑋 𝑛$ は定義 16.1.1 の設定を満たす族である．定義 1.1.1 のエントロピーは分布だけで決まり，確率 $0$ の値の項は約束により和に寄与しないから，以下ではどの確率変数についても，そのアルファベットを実際にとる値の全体にとってよい．

$𝑋 {1, \dots, 𝑛}$ は $𝑋$ そのもので，とりうる値は $𝐴$ の元だから，例 1.1.3 を $𝑀 = | 𝐴 |$ で当てて $𝐻 (𝑋 {1, \dots, 𝑛}) = l o g | 𝐴 |$ である．また $𝑆 \subseteq {1, \dots, 𝑛}$ をとると $𝑋 𝑆$ のとりうる値は $𝜋 𝑆 (𝐴)$ の元に限られるから，定理 1.1.5 を当てて

𝐻 (𝑋 𝑆) \leq l o g | 𝜋 𝑆 (𝐴) |

を得る．

族を $𝑆 𝑖 : = {1, \dots, 𝑛} ∖ {𝑖}$ （ $1 \leq 𝑖 \leq 𝑛$ ）ととる．番号 $𝑗$ を含む $𝑆 𝑖$ は $𝑖 \neq 𝑗$ を満たす $𝑖$ に対応するものだから，ちょうど $𝑛 - 1$ 個ある． $𝑘 = 𝑛 - 1$ として定理 16.3.1 を当て，右辺の各項に上の評価を当てると

(𝑛 - 1) l o g | 𝐴 | \leq 𝑛 \sum 𝑖 = 1 l o g | 𝜋 - 𝑖 (𝐴) |

である． $𝐴$ は空でなく，どの $𝜋 - 𝑖 (𝐴)$ も空でないから，両辺を対数の中にまとめると左辺は $l o g | 𝐴 | 𝑛 - 1$ ，右辺は $l o g \prod 𝑛 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) |$ である． $l o g$ が狭義単調だから主張を得る． $◼$

形式化: loomis_whitney (ソース)

形式化上の注記. 宣言の指数は自然数の引き算で書かれていて， $𝑛 = 0$ では $𝑛 - 1$ が $0$ に切り捨てられる．そのとき左辺は $1$ ，右辺は空の積で $1$ だから，宣言は $𝑛 = 0$ も込みで成り立っている．本文は $𝑛 \geq 1$ を仮定するので，この差は定理 16.4.2 の範囲には出てこない．

例 16.4.3. $𝑛 = 3$ ， $X = {0, 1}$ とする．

$𝐴 = {0, 1} 3$ をとると定理 16.4.2 の両辺はどちらも $64$ で等号である．
$𝐴 = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)}$ をとると左辺は $16$ ，右辺は $27$ で狭義である．

証明. 1 を示す． $| 𝐴 | = 8$ だから左辺は $82 = 64$ である．どの $𝑖$ についても $𝜋 - 𝑖 (𝐴) = {0, 1} 2$ で要素数は $4$ だから，右辺は $43 = 64$ である．

2 を示す． $| 𝐴 | = 4$ だから左辺は $42 = 16$ である． $𝜋 - 1 (𝐴)$ は第 $2$ 座標と第 $3$ 座標だけを見た像で， $𝐴$ の四つの元はそれぞれ $(0, 0)$ ， $(0, 0)$ ， $(1, 0)$ ， $(0, 1)$ に移るから $𝜋 - 1 (𝐴) = {(0, 0), (1, 0), (0, 1)}$ で要素数は $3$ である． $𝐴$ は座標の入れ替えで自分自身に移るから $𝜋 - 2 (𝐴)$ と $𝜋 - 3 (𝐴)$ の要素数も $3$ であり，右辺は $33 = 27$ である． $◼$

定理 16.4.2 の証明で族の形が効いたのは，どの番号もちょうど $𝑛 - 1$ 回覆われることを確かめる一箇所だけだった．定理 16.3.1 が族を選ばせてくれる以上，落とす座標を $1$ 個に限る理由はない．族を一般にとった形には Brascamp–Lieb の名が付いている．この名は， $ℝ 𝑛$ の上の積分について，いくつかの線形写像で低い次元へ送った先で定めた関数の積を，それぞれの積分の積の定数倍で上から押さえる解析の不等式に由来する．次の定理はその有限集合版にあたり，解析の側は本書では扱わない．

定理 16.4.4（Brascamp–Lieb の不等式（組合せ形））. $𝑛 \geq 1$ とし， $X$ を有限集合， $𝐴 \subseteq X 𝑛$ を空でない部分集合とする． $𝑟 \geq 1$ ， $𝑆 1, \dots, 𝑆 𝑟 \subseteq {1, \dots, 𝑛}$ とし， $𝑘$ を非負整数とする．どの $𝑖 \in {1, \dots, 𝑛}$ についても $𝑖$ を含む $𝑆 𝑗$ が $𝑘$ 個以上あるならば

| 𝐴 | 𝑘 \leq 𝑟 \prod 𝑗 = 1 | 𝜋 𝑆 𝑗 (𝐴) |

である．

証明. 定理 16.4.2 の証明で，族を $𝑆 1, \dots, 𝑆 𝑟$ に，覆う回数を $𝑛 - 1$ から $𝑘$ に取り替えればよい． $𝐴$ の上の一様分布から作った族についての二つの事実，すなわち $𝐻 (𝑋 {1, \dots, 𝑛}) = l o g | 𝐴 |$ であることと，どの $𝑆 \subseteq {1, \dots, 𝑛}$ についても $𝐻 (𝑋 𝑆) \leq l o g | 𝜋 𝑆 (𝐴) |$ であることは，族の取り方に触れずに出したのでそのまま使える．仮定より定理 16.3.1 が $𝑘$ で当てられて

𝑘 l o g | 𝐴 | \leq 𝑟 \sum 𝑗 = 1 l o g | 𝜋 𝑆 𝑗 (𝐴) |

を得る． $𝐴$ もどの $𝜋 𝑆 𝑗 (𝐴)$ も空でないから，両辺を対数の中にまとめると左辺は $l o g | 𝐴 | 𝑘$ ，右辺は $l o g \prod 𝑟 𝑗 = 1 | 𝜋 𝑆 𝑗 (𝐴) |$ であり， $l o g$ が狭義単調だから主張を得る． $◼$

形式化: brascamp_lieb_finset (ソース)

形式化上の注記. 宣言は族の添字を任意の有限型でとる．本文が族を $𝑆 1, \dots, 𝑆 𝑟$ と番号で並べているのは，その添字を ${1, \dots, 𝑟}$ にとった場合にあたる．

定理 16.4.2 は，定理 16.4.4 で族を「番号 $𝑖$ を抜いた $𝑛$ 個の集合」， $𝑘 = 𝑛 - 1$ ととった場合である．族をいちばん小さい集合でとると，別の形が出る．

系 16.4.5. $𝑛 \geq 1$ とし， $X$ を有限集合， $𝐴 \subseteq X 𝑛$ を空でない部分集合とすると

| 𝐴 | \leq 𝑛 \prod 𝑖 = 1 | 𝜋 {𝑖} (𝐴) |

である．

証明. 族を $𝑛$ 個の $1$ 点集合 ${1}, \dots, {𝑛}$ ととると，どの番号もちょうど一つの集合に含まれる． $𝑘 = 1$ として定理 16.4.4 を当てると，左辺は $| 𝐴 | 1 = | 𝐴 |$ である． $◼$

形式化: hypercube_product_projection_bound (ソース)

形式化上の注記. 宣言の名前は超立方体を名乗るが，述べているのは系 16.4.5 と同じく一般の有限アルファベットについての不等式である．

系 16.4.5 は， $𝐴$ のどの元も第 $𝑖$ 座標に $𝜋 {𝑖} (𝐴)$ の値をとるから， $𝐴$ が $1$ 点集合への射影の直積に含まれることからも見える．一般の定理から導いたのは，定理 16.4.4 の族をいちばん小さくとるとこの評価に戻る，という確認のためである．

例 16.4.6. 例 16.4.3 の 2 の $𝐴$ について系 16.4.5 の両辺は $4$ と $8$ である．また $𝑛 = 4$ ， $X = {0, 1}$ とし，族を $𝑆 1 = {1, 2}$ ， $𝑆 2 = {3, 4}$ ととり $𝑘 = 1$ として， $𝐴 : = {(0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1), (1, 1, 1, 0)}$ とすると，定理 16.4.4 の両辺はどちらも $4$ で等号である．

証明. 例 16.4.3 の 2 の $𝐴$ ではどの座標にも $0$ と $1$ の両方が現れるから，どの $𝑖$ についても $𝜋 {𝑖} (𝐴) = {0, 1}$ で，系 16.4.5 の右辺は $23 = 8$ ，左辺は $| 𝐴 | = 4$ である．

後半の $𝐴$ では，番号 $1$ と $2$ が $𝑆 1$ だけに，番号 $3$ と $4$ が $𝑆 2$ だけに含まれるから，どの番号もちょうど一つの集合に覆われて $𝑘 = 1$ として定理 16.4.4 が使える． $| 𝐴 | = 4$ だから左辺は $4$ である． $𝜋 𝑆 1 (𝐴) = {(0, 0), (1, 1)}$ ， $𝜋 𝑆 2 (𝐴) = {(0, 1), (1, 0)}$ でどちらも要素数は $2$ だから，右辺も $4$ である． $◼$

等号が起きる形を見る. 例 16.4.3 の 1 と例 16.4.6 の後半では等号が起きた．どちらの $𝐴$ も，座標の組ごとに集合を選んでその直積をとった形をしている．射影が見ているのは，各座標や各座標の組に現れる値の全体だけで，値どうしの組み合わせ方は落ちる．等号が起きた二つの例では，落ちた組み合わせ方がもともと無かったのである．いっぽう例 16.4.3 の 2 の $𝐴$ では，どの座標にも $0$ と $1$ の両方が現れるので， $1$ 点集合への射影はどれも ${0, 1}$ そのもの，すなわち目一杯である．それでも元の個数は $4$ しかなく，その開きが系 16.4.5 の $4 \leq 8$ になっている． $1$ 座標を落とした射影のほうは目一杯ではない．要素数は $4$ ではなく $3$ で， $(0, 0, 0)$ と $(1, 0, 0)$ が第 $1$ 座標を落とすと同じ $(0, 0)$ に移るぶんだけ小さい．それでも組み合わせ方の落ちる余地は残っていて，定理 16.4.2 の $16 \leq 27$ の開きになっている．

$| 𝐴 |$ の上界が二つ出たので，どちらが強いかを決めておく．どちらも定理 16.4.4 から出たもので，族の選び方が違うだけである．

命題 16.4.7. $𝑛 \geq 2$ とし， $X$ を有限集合， $𝐴 \subseteq X 𝑛$ を空でない部分集合とすると

𝑛 \prod 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) | \leq (𝑛 \prod 𝑖 = 1 | 𝜋 {𝑖} (𝐴) |) 𝑛 - 1

である．すなわち定理 16.4.2 が $| 𝐴 | 𝑛 - 1$ に与える上界は，系 16.4.5 の上界を $𝑛 - 1$ 乗したものを超えない．

証明. 番号 $𝑖$ を固定する． $𝜋 - 𝑖 (𝐴)$ は ${1, \dots, 𝑛} ∖ {𝑖}$ から $X$ への関数の空でない集合だから，その番号を小さい順に $1, \dots, 𝑛 - 1$ へ読み替えて，系 16.4.5 を座標の個数 $𝑛 - 1$ の場合に当てると

| 𝜋 - 𝑖 (𝐴) | \leq \prod 𝑗 \neq 𝑖 | 𝜋 {𝑗} (𝐴) |

である（読み替えても第 $𝑗$ 座標に現れる値の全体は変わらないので，右辺の各因子は $𝐴$ の $1$ 点集合への射影の要素数である）． $𝐴$ が空でないからどの射影も空でなく，両辺はどちらも正である．よって $𝑖$ について掛け合わせてよく，右辺では各 $𝑗$ の因子が $𝑗 \neq 𝑖$ を満たす $𝑖$ の個数だけ，すなわち $𝑛 - 1$ 回ずつ現れるから，主張を得る． $◼$

形式化上の注記. 二つの上界の強弱を述べる宣言はない．射影の要素数の積を結論に含む宣言をすべて開いて確かめた．機械検証が及ぶのは定理 16.4.2 と系 16.4.5 のそれぞれまでで，二つを比べる段は本文の側にある．

命題 16.4.7 を例 16.4.3 の数で見ておく．2 の $𝐴$ では定理 16.4.2 の右辺が $27$ ，系 16.4.5 の右辺を $2$ 乗したものが $82 = 64$ である． $| 𝐴 |$ は整数で $62 = 36 > 27$ だから，前者からは $| 𝐴 | \leq 5$ が，後者からは $| 𝐴 | \leq 8$ が出る（真の値は $4$ である）．1 の $𝐴$ では $43 = 64$ と $82 = 64$ で，二つは一致する．

数え上げに移す道具はこれで揃った．次節は同じ道具を， $X = {0, 1}$ の場合に，集合の大きさではなく集合の境界の大きさへ当てる．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．