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

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}$