[場所1E503（月曜日5限）]
HPに行く
現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。
今回が春学期は最後でした。Miniature 18, 19をやりました。
Miniature 18
は、直径縮小分割の問題です。
ある集合 $X\subset {\mathbb R}^d$ の $k$ 個の直径縮小分割とは、
$X$ が $X_1,\cdots, X_k$ の部分に分割されていて、各 $i$ に対して、
$\text{diam}(X_i)<\text{diam}(X)$ となることを言います。
ボルスクの予想とは、以下のようになります。
予想(1930 Borsuk)
${\mathbb R}^d$ に対して、直径有限な集合は、必ず $d+1$ 個の直径縮小分割をもつ。
この予想を線形代数を用いて否定的に解決します。
$p$ を素数として $n=4p$ とします。$n$ 個の点集合の中の
$2p-1$ 個の部分集合全体からなる集合を $\mathcal{A}$ とします。
$A\in \mathcal{A}$ に対して、$u_A\in {\mathbb R}^n$ を、
$i\in A$ であれば、$u_A$ の第 $i$ 成分は、1であり、$i\not\in A$ であれば
$u_A$ の第 $i$ 成分は、 $-1$ として定義します。
このとき、${\mathbb R}^{n^2}$ の中に、$|\mathcal{A}|$ 個の点集合を
$A\in \mathcal{A}$ に対して、${\bf q}_A=u_A\otimes u_A$ としておきます。
こうすることで、${\mathbb R}^{n^2}$ に、$\binom{4p}{2p-1}$ 個の
点を置くことができます。
それを $Q_{\mathcal{A}}:=\{{\bf q}_A|A\in \mathcal{A}\}$ とおきます。
今、$A,B\in \mathcal{A}$ として、$||{\bf q}_A-{\bf q}_B||^2$ を計算すると、
$||{\bf q}_A-{\bf q}_B||^2=\langle {\bf q}_A,{\bf q}_A\rangle +\langle {\bf q}_B,{\bf q}_B\rangle-2\langle {\bf q}_A,{\bf q}_B\rangle$
$=\langle u_A,u_A\rangle +\langle u_B,u_B\rangle-2\langle u_A,u_B\rangle$
となります。
学生には、$|A\cap B|=s$ としたときに、
$\langle u_A,u_B\rangle=4(s-p+1)$ であることを示してもらいました。
よって、$s=p-1$ のときに、この値は $0$ となります。
$\langle u_A,u_B\rangle$ は非負の整数なので、
$||{\bf q}_A-{\bf q}_B||$ の最大はこの値が $0$ のとき、つまり、
$\langle u_A,u_A\rangle +\langle u_B,u_B\rangle$ のときが最大となります。
この値は、$A,B$ のとり方によらず $8p$ となり、$Q_{\mathcal{A}}$ の直径
は $\sqrt{8p}$ ということになります。
集合 $\mathcal{A}$ の $m$ 個の分割 を考えます。
それを、$\mathcal{F}_1,\mathcal{F}_2,\cdots, \mathcal{F}_m$ とします。
$\mathcal{F}_i$ のいずれもが、 $A,B\in \mathcal{F}_i\Rightarrow |A\cap B|\neq p-1$
を満たすとします。このとき、Miniature 17 を使うと、任意の $i$ に対して、
$|\mathcal{A}|\ge 1.1^n|\mathcal{F}_i|$
となります。よって、
$m|\mathcal{A}|\ge 1.1^n(|\mathcal{F}_1|+|\mathcal{F}_2|+\cdots+|\mathcal{F}_m|)\ge 1.1^n|\mathcal{A}|$
となり、$m\ge 1.1^n$ が成り立ちます。
対偶をとれば、$1.1^n>m$ であれば、$m$ 個の分割 $\mathcal{F}_1,\mathcal{F}_2,\cdots, \mathcal{F}_m$ の中には、$|A\cap B|=p-1$ となる、$A,B$ を含む $\mathcal{F}_i$ が
存在するということになります。
今、$Q_{\mathcal{A}}$ を $1.1^n$ より少ない個数 $m$ 個の分割を考えます。
そのような分割を $Q_i:=\{{\bf q}_A|A\in \mathcal{F}_i\}$ とすると、
ある $i$ が存在して、$A,B$ が $\mathcal{F}_i$ の中に含まれて、$|A\cap B|=2p-1$
ということになります。
つまり $Q_i$ の直径の2乗は、$||{\bf q}_A-{\bf q}_B||^2=\langle {\bf q}_A,{\bf q}_A\rangle +\langle {\bf q}_B,{\bf q}_B\rangle=8p$
となるので、$Q_{\mathcal{A}}$ の直径と等しくなります。
この $Q_i$ は $Q_{\mathcal{A}}$ の直径と同じになるので、
この分割は直径縮小分割ではないということになります。
$m$ 個の任意の分割に対してそのような成分を含んでしまうので、
結果、この集合 $Q_{\mathcal{A}}$ は $m$ 個への直径縮小分割は存在しないという
ことになります。
今、$n^2$ と $1.1^n$ を比べてみれば、$n$ を十分大きくとれば、
$n^2$ より $1.1^n$ の方がはるかに大きくなりますから、そのような
$n$ に対して、$Q_{\mathcal{A}}$ は $n^2+1$ 個の直径縮小分割が存在しなくなります。
Miniature 19
は、discrepancy理論についての問題です。
まずは問題の設定です。
[設定]
ある国(設定はヨーロッパ？)の通貨のうち、1ユーロ以下は使えなくなり、
1ユーロ未満のお金は切り上げるか、切り下げるかのどちらかを選ばなければ
ならなくなった。
このとき、以下の問題を考えよう。
[問題]
ある商店の各商品の値段の切り上げ、切り下げを決めるとき、
いくつかの注文の請求金額と実際の代金の差をできるだけ小さくすることが
できるか？
[定理]
ある商店には 、ある日 $m$ 枚の注文書が届いた。
各注文書には、各商品の注文が高々１つであり、
各商品の総注文数が $t$ を超えないとき、
つまり、この日の各商品の切り上げ、切り下げを一斉に決めることで、
これら $m$ 枚の注文書の売り上げの差を $t$ ユーロ以内にするということです。
$i=1,\cdots, n$ を全ての商品とし、$c_i$ をその値段とします。
$c_i$ は $(0,1)$ の元であることを仮定しましょう。
各注文には、高々１つの商品の注文が入っているので、
$S_j\subset \{1,2,\cdots, n\}$, $j=1,\cdots, m$ としておけば、
$j$ 番目の注文書を表すことができます。
ここで、$\sum_{j\in S_i}x_j=\sum_{j\in S_i}c_j\ \ \ (\ast)$ という
連立一次方程式を考えます。
$x_i=c_i$ をその解の初期値としておきます。
(観察)
今、$S_i$ が $t$ 個以下の集合であれば、$c_i$ をどのように丸めても、
必ず、$|\sum_{j\in S_i}z_j-\sum_{j\in S_i}c_j|\le t$ となることは
すぐわかります。ここで、$z_j$ は $z_j\in \{0,1\}$ となる任意の値。
なので、$S_i$ の元の個数が $t$ 以下の集合(注文書)はとりあえず無視して、
$S_i$ の元の個数が $t$ より大きいもののみをを考えれば十分です。
そのような $S_i$ を危険な集合(注文書)ということにします。
そうではない注文書を安全な集合(注文書)ということにします。
このとき、危険な集合の数は必ず、変数の数より小さくなります。
危険な集合に含まれる変数の総数 $N$ は、
$$tm’<N\le tn$$
となるからです。
$m’$ は危険な集合の数とします。
$F$ を危険な集合に含まれる変数の集合とします。
よって、上の方程式 $(\ast)$ は、解空間は一次元以上は存在することになり、
$\sum_{j\in S_i}x_j=\sum_{j\in S_i}c_j$ が $(0,1)^{|F|}$
の内点を通るので、その解空間はその境界の点が存在します。
つまり全体として $(\ast)$ を満たしながらも、その成分のいくつか(1つ以上)は
$\{0,1\}$ の中に値を持つことができるようになります。
そのような解は、危険な集合に含まれる変数の一つを $0$ もしくは $1$ に
選んだことになります。
選ばれた変数はその値 $0,1$ を固定することで、
危険な集合の中の変数としては定数とみなすことにします。
それ以外を変数と考えます。
そうすると、$F$ の元はひとつ以上減り、
このとき、危険な集合は危険でなくなるかもしれませんが、危険でなくなった時点
でその注文書のことは無視します。また、新しい危険な注文書だけ
考えます。
同じようにして、新しい危険な集合の数はその中に含まれる変数よりは小さくなります。
そうすると対応する連立方程式 $(\ast)$ を考えると、
その解は1次元以上存在し解を少しずらすことで、関係を保ったまま
ある変数は $0,1$ を達成させることができます。
これを続けることで、危険な集合は徐々に少なくなっていきます。
集合 $S_i$ が危険でなくなった時点でも、
$\sum_{j\in S_i}x_i=\sum_{j\in S_i}c_j$
このように危険な注文書の変数をひとつずつ少なくして行くことで、
最終的に危険な集合は全て無くなります。
そうすると、固定されていない変数は、各 $S_i$ に対して高々 $t$ なので、
$|\sum_{j\in S_i}x_j-\sum_{j\in S_i}c_j|\le t$ は守られたまま全ての変数を $0,1$
のどちらかにすることができます。
Miniature 18
は、直径縮小分割の問題です。
ある集合 $X\subset {\mathbb R}^d$ の $k$ 個の直径縮小分割とは、
$X$ が $X_1,\cdots, X_k$ の部分に分割されていて、各 $i$ に対して、
$\text{diam}(X_i)<\text{diam}(X)$ となることを言います。
ボルスクの予想とは、以下のようになります。
予想(1930 Borsuk)
${\mathbb R}^d$ に対して、直径有限な集合は、必ず $d+1$ 個の直径縮小分割をもつ。
この予想を線形代数を用いて否定的に解決します。
$p$ を素数として $n=4p$ とします。$n$ 個の点集合の中の
$2p-1$ 個の部分集合全体からなる集合を $\mathcal{A}$ とします。
$A\in \mathcal{A}$ に対して、$u_A\in {\mathbb R}^n$ を、
$i\in A$ であれば、$u_A$ の第 $i$ 成分は、1であり、$i\not\in A$ であれば
$u_A$ の第 $i$ 成分は、 $-1$ として定義します。
このとき、${\mathbb R}^{n^2}$ の中に、$|\mathcal{A}|$ 個の点集合を
$A\in \mathcal{A}$ に対して、${\bf q}_A=u_A\otimes u_A$ としておきます。
こうすることで、${\mathbb R}^{n^2}$ に、$\binom{4p}{2p-1}$ 個の
点を置くことができます。
それを $Q_{\mathcal{A}}:=\{{\bf q}_A|A\in \mathcal{A}\}$ とおきます。
今、$A,B\in \mathcal{A}$ として、$||{\bf q}_A-{\bf q}_B||^2$ を計算すると、
$||{\bf q}_A-{\bf q}_B||^2=\langle {\bf q}_A,{\bf q}_A\rangle +\langle {\bf q}_B,{\bf q}_B\rangle-2\langle {\bf q}_A,{\bf q}_B\rangle$
$=\langle u_A,u_A\rangle +\langle u_B,u_B\rangle-2\langle u_A,u_B\rangle$
となります。
学生には、$|A\cap B|=s$ としたときに、
$\langle u_A,u_B\rangle=4(s-p+1)$ であることを示してもらいました。
よって、$s=p-1$ のときに、この値は $0$ となります。
$\langle u_A,u_B\rangle$ は非負の整数なので、
$||{\bf q}_A-{\bf q}_B||$ の最大はこの値が $0$ のとき、つまり、
$\langle u_A,u_A\rangle +\langle u_B,u_B\rangle$ のときが最大となります。
この値は、$A,B$ のとり方によらず $8p$ となり、$Q_{\mathcal{A}}$ の直径
は $\sqrt{8p}$ ということになります。
集合 $\mathcal{A}$ の $m$ 個の分割 を考えます。
それを、$\mathcal{F}_1,\mathcal{F}_2,\cdots, \mathcal{F}_m$ とします。
$\mathcal{F}_i$ のいずれもが、 $A,B\in \mathcal{F}_i\Rightarrow |A\cap B|\neq p-1$
を満たすとします。このとき、Miniature 17 を使うと、任意の $i$ に対して、
$|\mathcal{A}|\ge 1.1^n|\mathcal{F}_i|$
となります。よって、
$m|\mathcal{A}|\ge 1.1^n(|\mathcal{F}_1|+|\mathcal{F}_2|+\cdots+|\mathcal{F}_m|)\ge 1.1^n|\mathcal{A}|$
となり、$m\ge 1.1^n$ が成り立ちます。
対偶をとれば、$1.1^n>m$ であれば、$m$ 個の分割 $\mathcal{F}_1,\mathcal{F}_2,\cdots, \mathcal{F}_m$ の中には、$|A\cap B|=p-1$ となる、$A,B$ を含む $\mathcal{F}_i$ が
存在するということになります。
今、$Q_{\mathcal{A}}$ を $1.1^n$ より少ない個数 $m$ 個の分割を考えます。
そのような分割を $Q_i:=\{{\bf q}_A|A\in \mathcal{F}_i\}$ とすると、
ある $i$ が存在して、$A,B$ が $\mathcal{F}_i$ の中に含まれて、$|A\cap B|=2p-1$
ということになります。
つまり $Q_i$ の直径の2乗は、$||{\bf q}_A-{\bf q}_B||^2=\langle {\bf q}_A,{\bf q}_A\rangle +\langle {\bf q}_B,{\bf q}_B\rangle=8p$
となるので、$Q_{\mathcal{A}}$ の直径と等しくなります。
この $Q_i$ は $Q_{\mathcal{A}}$ の直径と同じになるので、
この分割は直径縮小分割ではないということになります。
$m$ 個の任意の分割に対してそのような成分を含んでしまうので、
結果、この集合 $Q_{\mathcal{A}}$ は $m$ 個への直径縮小分割は存在しないという
ことになります。
今、$n^2$ と $1.1^n$ を比べてみれば、$n$ を十分大きくとれば、
$n^2$ より $1.1^n$ の方がはるかに大きくなりますから、そのような
$n$ に対して、$Q_{\mathcal{A}}$ は $n^2+1$ 個の直径縮小分割が存在しなくなります。
Miniature 19
は、discrepancy理論についての問題です。
まずは問題の設定です。
[設定]
ある国(設定はヨーロッパ？)の通貨のうち、1ユーロ以下は使えなくなり、
1ユーロ未満のお金は切り上げるか、切り下げるかのどちらかを選ばなければ
ならなくなった。
このとき、以下の問題を考えよう。
[問題]
ある商店の各商品の値段の切り上げ、切り下げを決めるとき、
いくつかの注文の請求金額と実際の代金の差をできるだけ小さくすることが
できるか？
[定理]
ある商店には 、ある日 $m$ 枚の注文書が届いた。
各注文書には、各商品の注文が高々１つであり、
各商品の総注文数が $t$ を超えないとき、
各注文書において、実際の代金と請求金額の差を $t$ ユーロ
以内にすることができる。
つまり、この日の各商品の切り上げ、切り下げを一斉に決めることで、
これら $m$ 枚の注文書の売り上げの差を $t$ ユーロ以内にするということです。
$i=1,\cdots, n$ を全ての商品とし、$c_i$ をその値段とします。
$c_i$ は $(0,1)$ の元であることを仮定しましょう。
各注文には、高々１つの商品の注文が入っているので、
$S_j\subset \{1,2,\cdots, n\}$, $j=1,\cdots, m$ としておけば、
$j$ 番目の注文書を表すことができます。
ここで、$\sum_{j\in S_i}x_j=\sum_{j\in S_i}c_j\ \ \ (\ast)$ という
連立一次方程式を考えます。
$x_i=c_i$ をその解の初期値としておきます。
(観察)
今、$S_i$ が $t$ 個以下の集合であれば、$c_i$ をどのように丸めても、
必ず、$|\sum_{j\in S_i}z_j-\sum_{j\in S_i}c_j|\le t$ となることは
すぐわかります。ここで、$z_j$ は $z_j\in \{0,1\}$ となる任意の値。
なので、$S_i$ の元の個数が $t$ 以下の集合(注文書)はとりあえず無視して、
$S_i$ の元の個数が $t$ より大きいもののみをを考えれば十分です。
そのような $S_i$ を危険な集合(注文書)ということにします。
そうではない注文書を安全な集合(注文書)ということにします。
このとき、危険な集合の数は必ず、変数の数より小さくなります。
危険な集合に含まれる変数の総数 $N$ は、
$$tm’<N\le tn$$
となるからです。
$m’$ は危険な集合の数とします。
$F$ を危険な集合に含まれる変数の集合とします。
よって、上の方程式 $(\ast)$ は、解空間は一次元以上は存在することになり、
$\sum_{j\in S_i}x_j=\sum_{j\in S_i}c_j$ が $(0,1)^{|F|}$
の内点を通るので、その解空間はその境界の点が存在します。
つまり全体として $(\ast)$ を満たしながらも、その成分のいくつか(1つ以上)は
$\{0,1\}$ の中に値を持つことができるようになります。
そのような解は、危険な集合に含まれる変数の一つを $0$ もしくは $1$ に
選んだことになります。
選ばれた変数はその値 $0,1$ を固定することで、
危険な集合の中の変数としては定数とみなすことにします。
それ以外を変数と考えます。
そうすると、$F$ の元はひとつ以上減り、
このとき、危険な集合は危険でなくなるかもしれませんが、危険でなくなった時点
でその注文書のことは無視します。また、新しい危険な注文書だけ
考えます。
同じようにして、新しい危険な集合の数はその中に含まれる変数よりは小さくなります。
そうすると対応する連立方程式 $(\ast)$ を考えると、
その解は1次元以上存在し解を少しずらすことで、関係を保ったまま
ある変数は $0,1$ を達成させることができます。
これを続けることで、危険な集合は徐々に少なくなっていきます。
集合 $S_i$ が危険でなくなった時点でも、
$\sum_{j\in S_i}x_i=\sum_{j\in S_i}c_j$
が成り立ちますが、その後、無視して、その後の危険な集合に含まれる変数が
そこに含まれていても、その中で動く変数は上記の(観察)の事実から、
高々、$|\sum_{j\in S_i}x_i-\sum_{j\in S_i}c_i|\le t$ に限られます。
最終的に危険な集合は全て無くなります。
そうすると、固定されていない変数は、各 $S_i$ に対して高々 $t$ なので、
$|\sum_{j\in S_i}x_j-\sum_{j\in S_i}c_j|\le t$ は守られたまま全ての変数を $0,1$
のどちらかにすることができます。
