2018-01-22

鞄とその和集合の比較ー１

定理解説

Cauchy-Davenportの定理

$p$ を素数とし、 $A, B$ を巡回群 $\mathbb{Z}/p\mathbb{Z}$ の空でない部分集合とする。 $A+B \subset \mathbb{Z}/p\mathbb{Z}$ を

$\displaystyle A+B := \{a+b \mid a \in A, b \in B\}$

と定義する。このとき、次が成り立つ：

Cauchy-Davenportの定理 $\#(A+B) \geq \min\{p, \#A+\#B-1\}.$

これより、 $\#A+\#B \geq p+1$ であれば $\mathbb{Z}/p\mathbb{Z}$ の任意の元は $A$ の元と $B$ の元の和として表すことができることがわかる。

証明. $A=\{a_1, \dots, a_m\}, \ B=\{b_1, \dots, b_n\}, \ A+B=\{c_1, \dots, c_l\}$ とする。

主張 $m+n-1 \leq p \Longrightarrow l \geq m+n-1$ が成り立つ。

主張が証明されたとする。 $m+n-1 > p$ のとき、 $B':=\{b_1, \dots, b_{p+1-m}\} \subset B$ とすると

$m+(p+1-m)-1 = p$

なので、 $A, B'$ に対して主張を適用することができ、

$l \geq \#(A+B') \geq p$

となって定理の証明が完了する。以下、主張を $n$ に関する帰納法で証明する。

$n=1$ のときは

$l=m=m+(n-1)$

と成立している。

$n=2, \ m+1\leq p$ とする。 $l \leq m$ と仮定して背理法で証明する。このとき、二つの $m$ 元集合 $\{a_1+b_1, a_2+b_1, \dots, a_m+b_1\}$ と $\{a_1+b_2, a_2+b_2, \dots, a_m+b_2\}$ は一致する必要があるため、 $b:=b_1-b_2 \neq 0$ とすると、任意の $1 \leq i \leq m$ と任意の整数 $u$ に対して $a_i+ub \in A$ が成り立つことがわかる。

理由: $i$ に対して $j$ が存在して $a_i+b_1=a_i+b_2$ が成り立つので、 $a_i+b \in A$ であり、同様に $i$ に対して $j$ が存在して $a_i+b_2=a_j+b_1$ が成り立つので、 $a_i-b \in A$ である。あとは、 $a_i+b \in A$ であることから $a_i+2b=(a_i+b)+b \in A$ のようにして、帰納的に $a_i+ub \in A$ がわかる。

従って、 $\mathbb{Z}b:=\{Nb \in \mathbb{Z}/p\mathbb{Z} \mid N \in \mathbb{Z}\}$ とすると $A=A+\mathbb{Z}b$ がわかり、 $p$ が素数で $b \neq 0$ であることから $\mathbb{Z}b=\mathbb{Z}/p\mathbb{Z}$ なので、 $A=A+\mathbb{Z}b=A+\mathbb{Z}/p\mathbb{Z}=\mathbb{Z}/p\mathbb{Z}$ となって $m=p$ が従い、矛盾に到達する。

$n > 2$ とし、 $n$ 未満では主張が成立すると仮定する。 $m+n-1 \leq p$ とする。 $l \geq m+n-1$ を示したいので、 $l < p$ と仮定してよい。

$A+B$ と $B'':=\{b_1, b_n\}$ に対して帰納法の仮定を適用すると( $l+2-1 \leq p$ より適用可能)、

$\#( (A+B)+B'') \geq l+1$

が得られる。これより、或る $d \in \mathbb{Z}/p\mathbb{Z}$ が存在して

$d-b_1 \in A+B, \quad d-b_n \not \in A+B$

が成り立つ。理由: $\{c_1+b_n, \dots, c_l+b_n\}$ は $l$ 元集合なので、この集合には族さないような $d:=c_i+b_1$ が存在する。

従って、 $b_2, \dots, b_{n-1}$ と $c_1, \dots, c_l$ を適当に並べ替えることによって

$\begin{align} &d-b_1=c_1, \dots, d-b_r=c_r \\ &d-b_{r+1} \not \in A+B, \dots, d-b_n \not \in A+B\end{align}$

が成り立つようにできる( $1 \leq {}^{\exists}r \leq n-1$ )。このとき、 $1 \leq s \leq r, r < t \leq n$ に対して $c_s-b_t \not \in A$ である。理由: $c_s-b_t=a_i \in A$ であれば $a_i+b_t=c_s=d-b_s$ であり、 $d-b_t=a_i+b_s \in A+B$ となって矛盾。

よって、 $B''':=\{b_{r+1}, \dots, b_n\}$ とすれば $A+B''' \subset (A+B) \setminus \{c_1, \dots, c_r\}$ であり

$\#(A+B''') \leq l-r.$

一方、 $A, B'''$ に帰納法の仮定を適用すると、

$\#(A+B''') \geq m+(n-r)-1$

なので、合わせると $m+(n-r)-1 \leq l-r$ , すなわち $l \geq m+n-1$ が得られる。 Q.E.D.

鞄とその和集合

$G$ を有限Abel群とし、 $A$ を $G$ の元からなる鞄(多重集合)とする。 $A=\{a_1, \dots, a_n\}$ と書いたとき、 $A$ の和集合 $\Sigma A$ を

$\displaystyle \Sigma A:= \Bigl\{ \sum_{i \in I}a_i \ \Big| \ I \subset \{1, \dots, n\}\Bigr\}$

で定義する。鞄 $A$ の重複度込みの元の個数を $\left|A\right|$ で表し、 $A$ の元からなる集合の元の個数を $\#A$ と表すことにする。

問題 $\#\Sigma A$ と $\left|A\right|$ を比較せよ。

次の定理はこの一般的問題に対する一つの簡単な結果である：

定理 $A$ を $\mathbb{Z}/p\mathbb{Z}$ の非零元からなる(有限)鞄とする。このとき、 $\#\Sigma A \geq \min\{p, \left|A\right|+1\}$ が成り立つ。

証明. $A=\{a_1, \dots, a_n\}$ とする。このとき、

$\Sigma A= \{0, a_1\}+\cdots +\{0, a_n\}$

と書ける*1。 $n=1$ のときは $\#\Sigma A=2$ なので明らか。 $n > 1$ として $n$ 未満では成立すると仮定する。このとき、Cauchy-Davenportの定理より

$\begin{align} \#\Sigma A &= \#( (\{0, a_1\}+\cdots +\{0, a_{n-1}\})+\{0, a_n\}) \\ &\geq \min\{p, \#(\{0, a_1\}+\cdots +\{0, a_{n-1}\})+\#\{0, a_n\}-1\} \\ &\geq \min\{p, \min\{p, n\}+1\}=\min\{p, n+1\}\end{align}$

と証明される。 Q.E.D.

この定理はbest possibleである。 $A=\{\underbrace{a, \dots, a}_n\}$ とすれば、 $\Sigma A = \{0, a, 2a, \dots, na\}$ なので $\#\Sigma A=n+1=\left|A\right|+1$ となる。

*1:一般に $(A+B)+C=A+(B+C)=A+B+C=\{a+b+c \mid a \in A, b \in B, c \in C\}$ である。

2018-01-17

ハイパーグラフ除去補題ー３

等間隔に並ぶ素数を追い求めて

前正則化補題 $m > 0$ , $\varepsilon > 0$ とし、関数 $F\colon \mathbb{R}_{>0} \to \mathbb{R}_{>0}$ は任意の $x \in \mathbb{R}_{>0}$ に対して $F(x) \geq 1+x$ を満たすとする( $\varepsilon$ に依存してもよい)。各 $e \in H$ に対して $\sigma$ 加法族 $\mathcal{B}_e \subset \mathcal{A}_e$ は $\mathrm{cpx}(\mathcal{B}_e) \leq m$ を満たすとする。このとき、 $M > 0$ および各 $f \in \partial H$ 毎に $\sigma$ 加法族の組 $(\mathcal{B}_f, \mathcal{B}_f')$ であって $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ を満たすものが存在して、次が成り立つ:

$F(m) \leq M \leq O_{\#J, m, \varepsilon, F}(1)$ −①
$\mathrm{cpx}(\mathcal{B}_f) \leq M \ ({}^{\forall}f \in \partial H)$ −②
$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \leq \varepsilon^2 \ ({}^{\forall}e \in H, E_e \in \mathcal{B}_e)$ −③
$\displaystyle \Delta_e\Bigl(E_e \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f' \Bigr) \leq \frac{1}{F(M)} \ ({}^{\forall}e \in H, E_e \in \mathcal{B}_e)$ −④

前正則化補題 $\Longrightarrow$ Szemerédiの正則化補題 $\Longrightarrow$ 弱正則化補題

という流れについては別途記事を書く予定。

証明. 次のアルゴリズムを考える:
0. 初期化 $\mathcal{B}_f:=\{\emptyset, V_J\} \ ({}^{\forall}f \in \partial H)$ . ( $\mathrm{cpx}(\mathcal{B}_f)=0$ .)
1. 代入 $\displaystyle M:=\max\{F(m), \max_{f \in \partial H}\mathrm{cpx}(\mathcal{B}_f)\}, \ \delta := \frac{1}{F(M)}.$ このとき、データ $(m, \varepsilon, M, \delta, \{\mathcal{B}_e\}, \{\mathcal{B}_f\})$ に対して記事２の補題２を適用。その結果、ダイコトミーのどちらであっても任意の $f \in \partial H$ に対して $\mathcal{B}_f'$ が定まる。
2. If Randomness then 停止
3. If Structure then 代入 $\mathcal{B}_f:=\mathcal{B}_f'$ 1.へ

3. から1. へ移行する度に補題２の③より

$\displaystyle \sum_{e \in H}\sum_{E_e \in \mathcal{B}_e}\mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr)$

は少なくとも $\varepsilon^2$ だけ増加する。一方、この量は $\#H\cdot 2^{2^m}=O_{\#J, m}(1)$ で押さえられるため、 $O_{\#J, m, \varepsilon}(1)$ 回の移行の後アルゴリズムは必ず停止する。すると、 $M$ の初期値が $F(m)$ であることに注意して、補題２の④より①の成立が従う。②は構成から従い、③、④は補題２の①、②から従う。 Q.E.D.

正則化補題 $0 \leq j \leq d$ に対して $j$ 一様ハイパーグラフ $H_j$ を $H_d:=H$ および $H_j:=\partial H_{j+1} \ (0 \leq j < d)$ によって定義する。 $M_d > 0$ および任意の $e \in H_d$ に対して $\mathrm{cpx}(\mathcal{B}_e) \leq M_d$ が成り立つような $\sigma$ 加法族 $\mathcal{B}_e \subset \mathcal{A}_e$ をとる。 $F$ を前正則化補題と同じ条件の関数とする。このとき、

$M_d \leq F(M_d) \leq M_{d-1} \leq F(M_{d-1}) \leq \cdots \leq M_0 \leq F(M_0) \leq O_{\#J, M_d, F}(1)$

が成り立つような $M_j > 0 \ (0 \leq j < d)$ および任意の $0 \leq j < d, \ f \in H_j$ に対して $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ なる $\sigma$ 加法族の組 $(\mathcal{B}_f, \mathcal{B}_f')$ が存在して、次が成り立つ:

$\mathrm{cpx}(\mathcal{B}_f) \leq M_j \ ({}^{\forall}0 \leq j < d, \ f \in H_j)$
$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \leq \frac{1}{F(M_j)^2} \ ({}^{\forall}1 \leq j \leq d, \ e \in H_j, \ E_e \in \mathcal{B}_e)$
$\displaystyle \Delta_e\Bigl(E_e \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \leq \frac{1}{F(M_0)} \ ({}^{\forall}1 \leq j \leq d, \ e \in H_j, \ E_e \in \mathcal{B}_e)$

証明. $J$ を固定して $d$ に関する帰納法で証明する*1。帰納法が進行する上で $O_{\#J, M_d, F}(1)$ の定数部分は変わるが、高々 $\#J$ 回なので問題ない。 $d=0$ のときは自明に成立している(と主張を読む)。 $d \geq 1$ とし、 $d-1$ では主張が成立していると仮定する。 $F$ と同じ条件を満たす関数 $F'$ を後で選択する(少なくとも各点で $F'(x) \geq F(x)$ は成り立つようなもの)。 $m=M_d, \varepsilon = 1/F(M_d), F \mapsto F'$ として前正則化補題を適用すると、 $M_{d-1} > 0$ および任意の $f \in H_{d-1}$ に対して $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ なる $\sigma$ 加法族の組 $(\mathcal{B}_f, \mathcal{B}_f')$ が存在して、

$\displaystyle F(M_d) \leq F'(M_d) \leq M_{d-1} \leq O_{\#J, \frac{1}{F(M_d)}, F'}(1) = O_{\#J, M_d, F, F'}(1)$

$\displaystyle \mathrm{cpx}(\mathcal{B}_f) \leq M_{d-1} \ ({}^{\forall}f \in H_{d-1})$

$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \leq \frac{1}{F(M_d)^2} \ ({}^{\forall}e \in H_d, \ E_e \in \mathcal{B}_e)$

$\displaystyle \Delta_e\Bigl(E_e \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \leq \frac{1}{F'(M_{d-1})} \ ({}^{\forall}e \in H_d, \ E_e \in \mathcal{B}_e)$

が成り立つ。これらを用いて帰納法の仮定( $d-1$ の場合)を適用すると、

$M_{d-1} \leq F(M_{d-1}) \leq \cdots \leq M_0 \leq F(M_0) \leq O_{\#J, M_{d-1}, F}(1)$

が成り立つような $M_j > 0 \ (0 \leq j < d-1)$ および任意の $0 \leq j < d-1, \ f \in H_j$ に対して $\mathcal{B}_f \subset \mathcal{B}_f' \subset \mathcal{A}_f$ なる $\sigma$ 加法族の組 $(\mathcal{B}_f, \mathcal{B}_f')$ が存在して、

$\mathrm{cpx}(\mathcal{B}_f) \leq M_j \ ({}^{\forall}0 \leq j < d-1, \ f \in H_j)$

$\displaystyle \mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathcal{E}_{E_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \leq \frac{1}{F(M_j)^2} \ ({}^{\forall}1 \leq j \leq d-1, \ e \in H_j, \ E_e \in \mathcal{B}_e)$

$\displaystyle \Delta_e\Bigl(E_e \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) \leq \frac{1}{F(M_0)} \ ({}^{\forall}1 \leq j \leq d-1, \ e \in H_j, \ E_e \in \mathcal{B}_e)$