16.5 超立方体の辺等周

面積を決めておいて周の長さをいちばん短くする図形は何か，と問うのが等周問題である．同じ問いを超立方体の頂点の上で立てるのが本節である． ${0, 1} 𝑛$ の二つの点は，ちょうど $1$ 座標だけ違うときに辺で結ばれているとみる．頂点の集合 $𝐴$ を選ぶと，端点の一方だけが $𝐴$ に入っている辺が決まり，その本数が $𝐴$ の周にあたる．要素数を決めておいて，この本数がどこまで小さくなりうるかを問う．本節は下からの評価を二つ与えて二つを比べ，要素数が $2$ のべきであるときには最小値を決める．以下 $X = {0, 1}$ に固定し， ${0, 1} 𝑛$ の元はビットの列として書く．

定義 16.5.1（辺境界）. $𝑛 \geq 0$ とし， $𝐴 \subseteq {0, 1} 𝑛$ とする． $𝑥 \in {0, 1} 𝑛$ と $𝑖 \in {1, \dots, 𝑛}$ に対し， $𝑥$ の第 $𝑖$ 座標だけを反転して他の座標を変えない点を $𝑥 (𝑖)$ と書く． $𝑥 \in 𝐴$ かつ $𝑥 (𝑖) \notin 𝐴$ を満たす対 $(𝑥, 𝑖)$ の全体を $𝜕 e 𝐴$ と書き， $𝐴$ の 辺境界 と呼ぶ．

$𝜕 e$ は辺境界を表す記号であって，第10章 10.4 節の偏微分とは別である（偏微分はつねに分数の形で関数に当たり，こちらはつねに添字 $e$ を伴って集合に当たる）．対 $(𝑥, 𝑖)$ と，端点の一方だけが $𝐴$ に入る辺とは一対一に対応する．そのような辺について， $𝐴$ に入っているほうの端点を $𝑥$ ，二つの端点が食い違う座標の番号を $𝑖$ とすればよい．だから $| 𝜕 e 𝐴 |$ は「 $𝐴$ から外へ出ていく辺の本数」である．

形式化: edgeBoundaryCount (ソース)

注記

形式化は辺境界を集合としてではなく，その要素数として直に定めている（本文が $| 𝜕 e 𝐴 |$ と書く数がそれである）．座標の反転にも flipCoord (InformationTheory/Shannon/HypercubeEdge/Boundary.lean) という名前が与えられている．

命題 16.5.2. $𝑛 \geq 0$ とし， $𝐴 \subseteq {0, 1} 𝑛$ とする． $𝑥 \in 𝐴$ と $𝑖 \in {1, \dots, 𝑛}$ の対 $(𝑥, 𝑖)$ のうち $𝑥 (𝑖) \in 𝐴$ を満たすものの個数と $| 𝜕 e 𝐴 |$ との和は $𝑛 | 𝐴 |$ に等しい．

証明. $𝑥 \in 𝐴$ と $𝑖 \in {1, \dots, 𝑛}$ の対は， $𝑥$ の選び方が $| 𝐴 |$ 通り， $𝑖$ の選び方が $𝑛$ 通りで，全部で $𝑛 | 𝐴 |$ 個ある．その各々について $𝑥 (𝑖)$ は $𝐴$ に入るか入らないかのどちらか一方だから，全体は $𝑥 (𝑖) \in 𝐴$ を満たす対と $𝑥 (𝑖) \notin 𝐴$ を満たす対とに分かれる．後者の個数は定義 16.5.1 より $| 𝜕 e 𝐴 |$ である． $◼$

形式化: edge_total_count (ソース)

注記

形式化は $𝑥 (𝑖) \in 𝐴$ を満たす対の個数にも internalEdgePairCount (InformationTheory/Shannon/HypercubeEdge/Boundary.lean) という名前を与えていて，宣言はその数と辺境界の要素数との和が $𝑛 | 𝐴 |$ に等しい，という形で述べられている．

以下，本節の主張ブロックでは $l o g$ の底を $2$ にとる．立方体の次元 $𝑛$ と $l o g 2 | 𝐴 |$ を同じ物差しで比べるためである．

定理 16.5.3（辺等周不等式）. $𝑛 \geq 0$ とし， $𝐴 \subseteq {0, 1} 𝑛$ を空でない集合とすると

| 𝐴 | (𝑛 - l o g 2 | 𝐴 |) \leq | 𝜕 e 𝐴 |

である．

証明. $𝑛 = 0$ のときは ${0, 1} 0$ の元がただ一つで $𝐴$ はその一点だから， $| 𝐴 | = 1$ と $l o g 2 | 𝐴 | = 0$ より左辺は $0$ であり，対 $(𝑥, 𝑖)$ をとる $𝑖$ がないので右辺も $0$ である．以下 $𝑛 \geq 1$ とする．

$𝐴$ の上の一様分布に従う確率変数 $𝑋$ をとり， $𝑋 𝑖$ を $𝑋$ の第 $𝑖$ 座標とする． $𝑋 1, \dots, 𝑋 𝑛$ は定義 16.1.1 の設定を満たす族である． $𝑋 {1, \dots, 𝑛}$ は $𝑋$ そのもので，とりうる値は $𝐴$ の元だから，そのアルファベットを $𝐴$ にとって例 1.1.3 を $𝑀 = | 𝐴 |$ で当てると $𝐻 (𝑋 {1, \dots, 𝑛}) = l o g 2 | 𝐴 |$ である．

まず上から押さえる．定理 16.1.4 を $𝑆 = {1, \dots, 𝑛}$ に当てると $\sum 𝑛 𝑖 = 1 𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑖 - 1}) = l o g 2 | 𝐴 |$ である． ${1, \dots, 𝑖 - 1}$ は ${1, \dots, 𝑛} ∖ {𝑖}$ に含まれるから，補題 16.1.2 に注意して定理 1.2.4 を当てると，各 $𝑖$ について $𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑛} ∖ {𝑖}) \leq 𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑖 - 1})$ である．足し合わせると

𝑛 \sum 𝑖 = 1 𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑛} ∖ {𝑖}) \leq l o g 2 | 𝐴 |

である．

次に左辺を数え直す．番号 $𝑖$ を固定し， $𝑋 {1, \dots, 𝑛} ∖ {𝑖}$ のとる値 $𝑦$ を一つとる． $𝐴$ の元で第 $𝑖$ 座標以外が $𝑦$ に一致するものは $1$ 個か $2$ 個で， $2$ 個ならその二つは互いに第 $𝑖$ 座標を反転した関係にある． $𝑦$ のもとでの条件付きエントロピーを，この二つの場合に分けて見る．

$2$ 個のとき． $𝑋$ は $𝐴$ の上で一様だから， $𝑦$ のもとでの $𝑋 𝑖$ の条件付き分布は ${0, 1}$ の上の一様分布である．例 1.1.3 を $𝑀 = 2$ で当てて $𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑛} ∖ {𝑖} = 𝑦) = 1$ であり，この $𝑦$ の確率は $2 / | 𝐴 |$ である．
$1$ 個のとき．条件付き分布は一点に集中するから，定義 1.1.1 の和は $- 1 l o g 2 1$ の一項だけになり，値は $0$ である．

定義 1.2.2 は各 $𝑦$ のもとでの値をその確率で平均したものだから，寄与するのは $2$ 個の場合の $𝑦$ だけで，その寄与は $𝑦$ ひとつにつき $2 / | 𝐴 |$ である．そのような $𝑦$ ひとつには $𝐴$ の元が $2$ 個対応し，それらはちょうど，第 $𝑖$ 座標を反転しても $𝐴$ に留まる $𝐴$ の元だから，そのような $𝑦$ の個数を $2$ 倍したものが，そのような元の個数に等しい．したがって

𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑛} ∖ {𝑖}) = | {𝑥 \in 𝐴 : 𝑥 (𝑖) \in 𝐴} | | 𝐴 |

である． $𝑖$ について足すと，分子の和は $𝑥 (𝑖) \in 𝐴$ を満たす対 $(𝑥, 𝑖)$ の個数だから，命題 16.5.2 よりそれは $𝑛 | 𝐴 | - | 𝜕 e 𝐴 |$ である．前段の不等式と合わせて

𝑛 | 𝐴 | - | 𝜕 e 𝐴 | | 𝐴 | \leq l o g 2 | 𝐴 |

を得る． $| 𝐴 | > 0$ を両辺に掛けて整理すれば主張である． $◼$

形式化: edgeBoundary_entropy_sharp (ソース)

例 16.5.4（部分立方体）. $𝑛 \geq 0$ ， $0 \leq 𝑘 \leq 𝑛$ とする． $𝐹 \subseteq {1, \dots, 𝑛}$ を要素数 $𝑛 - 𝑘$ の座標の集合， $𝑐$ を $𝐹$ から ${0, 1}$ への関数とし，

𝐴 : = {𝑥 \in {0, 1} 𝑛 : 𝑥 𝑖 = 𝑐 (𝑖) (𝑖 \in 𝐹)}

とおく．このとき $| 𝐴 | = 2 𝑘$ かつ $| 𝜕 e 𝐴 | = 2 𝑘 (𝑛 - 𝑘)$ であり，定理 16.5.3 は等号で成り立つ（図 16.5.1）．

証明. $𝐴$ の元は $𝐹$ の外の $𝑘$ 個の座標を自由に選んで得られるから $| 𝐴 | = 2 𝑘$ である． $𝑥 \in 𝐴$ と座標 $𝑖$ をとる． $𝑖 \notin 𝐹$ ならば $𝑥 (𝑖)$ も $𝐹$ の上で $𝑐$ に一致するので $𝐴$ に属し， $𝑖 \in 𝐹$ ならば $𝑥 (𝑖)$ の第 $𝑖$ 座標は $𝑐 (𝑖)$ と違うので $𝐴$ に属さない．したがって外に出る対は $𝑖 \in 𝐹$ のものに限り，その個数は $| 𝐴 | | 𝐹 | = 2 𝑘 (𝑛 - 𝑘)$ である．一方 $l o g 2 2 𝑘 = 𝑘$ だから定理 16.5.3 の左辺は $2 𝑘 (𝑛 - 𝑘)$ であり，両辺が一致する． $◼$

図 16.5.1. $𝑛 = 3$ ， $𝑘 = 2$ ， $𝐹 = {1}$ ， $𝑐 (1) = 0$ のときの部分立方体 $𝐴$ （塗った $4$ 点，第 $1$ 座標が $0$ の点）． $𝐴$ から外へ出る辺は太線の $4$ 本で， $2 𝑘 (𝑛 - 𝑘) = 4$ に等しい．

これで，節の冒頭の問いのうち要素数が $2$ のべきである場合には答えが出る．節の終わりに系 16.5.9 としてまとめる．要素数が $2$ のべきでないときの最小値を，本書は与えない．

下界をもう一つ作っておく．前節の定理 16.4.2 は，集合の要素数を射影の要素数で上から押さえる不等式だった．辺境界も射影の要素数で書けるので（命題 16.5.6），同じ不等式をこの節に持ち込める．そうして出る下界を定理 16.5.3 と比べれば，二つの道の差が数で見える．持ち込むには， $𝑛$ 個の非負の数の積の $𝑛$ 乗根が相加平均を超えないという古典的な不等式が要る．本書はこれを補題 1.1.9 から証明するので，借用ではない．

補題 16.5.5（相加相乗平均の不等式）. $𝑛 \geq 1$ とし， $𝑡 1, \dots, 𝑡 𝑛$ を非負の実数とすると

(𝑛 \prod 𝑖 = 1 𝑡 𝑖) 1 / 𝑛 \leq 1 𝑛 𝑛 \sum 𝑖 = 1 𝑡 𝑖

である．

証明. どれかの $𝑡 𝑖$ が $0$ ならば左辺は $0$ であり，右辺は非負だから成り立つ．以下すべての $𝑡 𝑖$ が正であるとする．補題 1.1.6 のとおり $l o g$ は $(0, \infty)$ の上で狭義凹だから，補題 1.1.9 を，重み $𝑤 𝑖 = 1 / 𝑛$ ，点 $𝑡 𝑖$ ととって当てると

1 𝑛 𝑛 \sum 𝑖 = 1 l o g 𝑡 𝑖 \leq l o g (1 𝑛 𝑛 \sum 𝑖 = 1 𝑡 𝑖)

である．左辺は $l o g (\prod 𝑛 𝑖 = 1 𝑡 𝑖) 1 / 𝑛$ に等しい． $l o g$ が狭義単調だから主張を得る． $◻$

形式化上の注記

この補題だけを述べる宣言はない．積の $𝑛$ 乗根を相加平均で押さえる形で InformationTheory/ の全体を探しても見つからず，形式化は同じ内容を重みつきの一般形として Mathlib から直に引いている．定理 16.5.7 と定理 16.6.1 に紐付けた宣言が，それぞれその中でこれを使っている．

命題 16.5.6. $𝑛 \geq 0$ とし， $𝐴 \subseteq {0, 1} 𝑛$ とすると

| 𝜕 e 𝐴 | + 𝑛 | 𝐴 | = 2 𝑛 \sum 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) |

である（ $𝜋 - 𝑖 (𝐴)$ は定義 16.4.1 の射影である）．

証明. 番号 $𝑖$ を固定する． $𝑦 \in 𝜋 - 𝑖 (𝐴)$ に対し， $𝐴$ の元で第 $𝑖$ 座標以外が $𝑦$ に一致するものは $1$ 個か $2$ 個である． $1$ 個であるような $𝑦$ の個数を $𝑎 𝑖$ ， $2$ 個であるような $𝑦$ の個数を $𝑏 𝑖$ と書くと， $𝜋 - 𝑖 (𝐴)$ の元はこの二種類に分かれるから $| 𝜋 - 𝑖 (𝐴) | = 𝑎 𝑖 + 𝑏 𝑖$ であり， $𝐴$ の元をこの分け方で数えて $| 𝐴 | = 𝑎 𝑖 + 2 𝑏 𝑖$ である．また $𝑥 \in 𝐴$ の第 $𝑖$ 座標以外を切り詰めたものを $𝑦$ と書くと， $𝑥 (𝑖) \notin 𝐴$ であることと $𝑦$ が $1$ 個のほうであることとは同じことだから，第 $𝑖$ 座標の向きに外へ出る対の個数は $𝑎 𝑖$ である．よって

𝑎 𝑖 + | 𝐴 | = 𝑎 𝑖 + (𝑎 𝑖 + 2 𝑏 𝑖) = 2 | 𝜋 - 𝑖 (𝐴) |

である． $𝑖$ について足すと，左辺の第 $1$ 項の和は $| 𝜕 e 𝐴 |$ ，第 $2$ 項の和は $𝑛 | 𝐴 |$ だから主張を得る． $◼$

形式化: edgeBoundary_count_eq (ソース)

命題 16.5.6 は，辺境界を射影の要素数の言葉に書き換える．そこに定理 16.4.2 を当てれば，もう一つの下界が出る．正の整数 $𝑚$ に対し $𝑢 \mapsto 𝑢 1 / 𝑚$ が $[0, \infty)$ の上で単調非減少であること（ $𝑢 \mapsto 𝑢 𝑚$ の逆写像である）と，正の実数のべき乗の規則，すなわち正の実数 $𝑢$ ， $𝑣$ と実数 $𝜅$ ， $𝜏$ について $(𝑢 𝑣) 𝜅 = 𝑢 𝜅 𝑣 𝜅$ ， $𝑢 𝜅 + 𝜏 = 𝑢 𝜅 𝑢 𝜏$ ， $(𝑢 𝜅) 𝜏 = 𝑢 𝜅 𝜏$ が成り立つことを既知とする．単調性を使うのは定理 16.5.7 の証明と例 16.6.2 の二箇所で，べき乗の規則を使うのは，本節と次節が $1 / 𝑚$ 乗を積や積のべきに通すところである．

定理 16.5.7. $𝑛 \geq 1$ とし， $𝐴 \subseteq {0, 1} 𝑛$ を空でない集合とすると

2 𝑛 | 𝐴 | (𝑛 - 1) / 𝑛 - 𝑛 | 𝐴 | \leq | 𝜕 e 𝐴 |

である．

証明. 補題 16.5.5 を $𝑡 𝑖 = | 𝜋 - 𝑖 (𝐴) |$ ととって当てると

𝑛 \sum 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) | \geq 𝑛 (𝑛 \prod 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) |) 1 / 𝑛

である． $X = {0, 1}$ として定理 16.4.2 を当てると $\prod 𝑛 𝑖 = 1 | 𝜋 - 𝑖 (𝐴) | \geq | 𝐴 | 𝑛 - 1$ であり， $1 / 𝑛$ 乗が単調非減少だから右辺は $𝑛 | 𝐴 | (𝑛 - 1) / 𝑛$ 以上である．命題 16.5.6 と合わせると $| 𝜕 e 𝐴 | + 𝑛 | 𝐴 | \geq 2 𝑛 | 𝐴 | (𝑛 - 1) / 𝑛$ であり，移項すれば主張を得る． $◼$

形式化: edgeBoundary_ge_AMGM (ソース)

注記

宣言は移項する前の形（ $2 𝑛 | 𝐴 | (𝑛 - 1) / 𝑛 \leq | 𝜕 e 𝐴 | + 𝑛 | 𝐴 |$ ）で述べられている．指数は定理 16.4.2 の宣言と同じく自然数の引き算で書かれていて $𝑛 = 0$ でも両辺が定まる．本文が $𝑛 \geq 1$ を仮定するのは， $(𝑛 - 1) / 𝑛$ を分数として読むためである．

下界が二つ出たので，どちらが強いかを決めておく．

命題 16.5.8. $𝑛 \geq 1$ とし， $𝐴 \subseteq {0, 1} 𝑛$ を空でない集合とすると

2 𝑛 | 𝐴 | (𝑛 - 1) / 𝑛 - 𝑛 | 𝐴 | \leq | 𝐴 | (𝑛 - l o g 2 | 𝐴 |)

である．すなわち定理 16.5.3 の下界は定理 16.5.7 の下界以上である．等号が成り立つのは $| 𝐴 | = 1$ のときと $| 𝐴 | = 2 𝑛$ のときに限る．

証明. $𝐴$ は空でなく ${0, 1} 𝑛$ に含まれるから $1 \leq | 𝐴 | \leq 2 𝑛$ であり， $𝑠 : = 1 - l o g 2 | 𝐴 | / 𝑛$ とおくと $0 \leq 𝑠 \leq 1$ である． $l o g 2 | 𝐴 | = 𝑛 (1 - 𝑠)$ だから $| 𝐴 | - 1 / 𝑛 = 2 - (1 - 𝑠)$ であり，

2 𝑛 | 𝐴 | (𝑛 - 1) / 𝑛 - 𝑛 | 𝐴 | = 2 𝑛 | 𝐴 | | 𝐴 | - 1 / 𝑛 - 𝑛 | 𝐴 | = 𝑛 | 𝐴 | (2 𝑠 - 1), | 𝐴 | (𝑛 - l o g 2 | 𝐴 |) = 𝑛 | 𝐴 | 𝑠

である． $𝑛 | 𝐴 | > 0$ だから，示すべきは $0 \leq 𝑠 \leq 1$ に対する $2 𝑠 \leq 1 + 𝑠$ である．補題 1.1.6 のとおり $l o g 2$ は狭義凹だから，補題 1.1.9 を， $2$ 点 $1$ と $2$ ，重み $1 - 𝑠$ と $𝑠$ ととって当てると

l o g 2 (1 + 𝑠) = l o g 2 ((1 - 𝑠) \cdot 1 + 𝑠 \cdot 2) \geq (1 - 𝑠) l o g 2 1 + 𝑠 l o g 2 2 = 𝑠

である． $𝑠 = l o g 2 2 𝑠$ であり $l o g 2$ は狭義単調だから， $1 + 𝑠 \geq 2 𝑠$ を得る．等号については， $0 < 𝑠 < 1$ のときは補題 1.1.9 の重みが二つとも正で点 $1$ と $2$ が違うから狭義であり， $𝑠 = 0$ と $𝑠 = 1$ のときは重みの一方が $0$ で等号である． $𝑠 = 0$ は $| 𝐴 | = 2 𝑛$ ， $𝑠 = 1$ は $| 𝐴 | = 1$ にあたる． $◼$

形式化上の注記

二つの下界の強弱を述べる宣言はない．辺境界の要素数を結論に含む宣言をすべて開いて確かめた．機械検証が及ぶのは定理 16.5.3 と定理 16.5.7 のそれぞれまでで，二つを比べる段は本文の側にある．

二つの下界を数で比べる. $𝑛 = 10$ とし， $𝐴$ を $5$ 個の座標を固定して得られる $32$ 点の部分立方体にとる．例 16.5.4 より $| 𝜕 e 𝐴 | = 32 \times 5 = 160$ である．定理 16.5.3 の下界は $32 (10 - 5) = 160$ で真の値に一致し，定理 16.5.7 の下界は $2 \times 10 \times 32 9 / 10 - 10 \times 32 = 452.548 \dots - 320 = 132.548 \dots$ で， $27$ ほど届かない．両端では二つは一致する． $| 𝐴 | = 1$ ではどちらも $𝑛$ ， $| 𝐴 | = 2 𝑛$ ではどちらも $0$ である．

二つの下界は道が違う．弱いほうの定理 16.5.7 は，命題 16.5.6 で辺境界を射影の要素数に書き換えてから定理 16.4.2 と補題 16.5.5 に渡すので，本節の側で見ているのは要素数だけである（定理 16.4.2 自身の証明は定理 16.3.1 を通るので，エントロピーを使わずに済むわけではない）．強いほうの定理 16.5.3 は，射影を経由せずに定理 16.1.4 の分解を立方体の上でそのまま使い， $1$ 座標だけを残したときの条件付きエントロピーが，条件の値ごとに $0$ か $1$ しかとらないことを数え上げに直す．射影を経由しないほうが弱くならない下界を出し，両端の $| 𝐴 | = 1$ と $| 𝐴 | = 2 𝑛$ を除けば真に強い，というのが二つを比べた結果である．

強いほうの下界は，要素数が $2$ のべきであるときにはとられる．節の冒頭の問いの答えは，そこから出る．

系 16.5.9（辺境界の最小値）. $𝑛 \geq 0$ とし， $𝑘$ を $0 \leq 𝑘 \leq 𝑛$ を満たす整数とする． $| 𝐴 | = 2 𝑘$ を満たす $𝐴 \subseteq {0, 1} 𝑛$ を動かすとき， $| 𝜕 e 𝐴 |$ の最小値は $2 𝑘 (𝑛 - 𝑘)$ である．

証明. $| 𝐴 | = 2 𝑘$ は正だから $𝐴$ は空でなく， $l o g 2 2 𝑘 = 𝑘$ だから，そのような $𝐴$ のどれについても定理 16.5.3 は $| 𝜕 e 𝐴 | \geq 2 𝑘 (𝑛 - 𝑘)$ を与える．いっぽう $0 \leq 𝑘 \leq 𝑛$ だから，要素数 $𝑛 - 𝑘$ の座標の集合と，そこから ${0, 1}$ への関数を一つずつとって例 16.5.4 を当てることができ，そこで作った部分立方体は要素数が $2 𝑘$ で，その辺境界の要素数はちょうど $2 𝑘 (𝑛 - 𝑘)$ である．よって $2 𝑘 (𝑛 - 𝑘)$ は下界であり，かつとられる． $◼$

形式化上の注記

要素数を固定したときの辺境界の最小値を述べる宣言はない．結論の形で探しても，最小値を述べるものも，例 16.5.4 の部分立方体を作る宣言も見つからない．機械検証が及ぶのは定理 16.5.3 の下界までで，その値がとられることを言う段は本文の側にある．

次節は補題 16.5.5 のほうをもう一度使う．当てる相手は集合の要素数ではなく，行列の行列式である．

情報理論入門（Lean による形式証明つき）・GitHub