外書輪講I(第15回)

[場所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$ を超えないとき、

各注文書において、実際の代金と請求金額の差を $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$
のどちらかにすることができます。

外書輪講I(第14回)

[場所1E503（月曜日5限）]

HPに行く

現在外書輪講では、Matousekの33-Miniaturesをみんなで読んでいます。

今回は、Miniature 15 18をやりました。

Miniature 15
前回の続きです。

${\mathbb R}^d$ に長さがちょうど２種類となる $n$ 個の点が存在するような
$n$ の最大を $n(d)$ とする。

前回の続きで、以下を証明してもらいました。

定理
$n(d)\le \frac{1}{2}(d^2+5d+4)$

ここでポイントとなるのは、2種類の長さが正の実数 $a,b$ であるとして、
${\mathbb R}^d$ の中の ${\bf p}_i$  $(i=1,..., n)$ 任意の２つの互いの長さが
2種類であるとき、$n$ 個の点を関数 $f_i({\bf x})=(||{\bf x}-{\bf p}_i||^2-a^2)\cdot( ||{\bf x}-{\bf p}_i||^2-b^2)$
に言い換えることです。
この関数は、${\mathbb R}^d$ から ${\mathbb R}$ への関数です。
とりわけ、連続関数となります。

${\bf p}_i\mapsto f_i$ として
点を ${\mathbb R}^d$ から ${\mathbb R}$ への関数と言い換えます。
関数をベクトル空間のベクトルとして表すことで、
線形代数の知識が使えるようになります。

このとき、この関数は、${\mathbb R}^d$ 上の関数全体の中で一次独立となります。
つまり、$n$ は、${\mathbb R}^d$ から ${\mathbb R}$ への関数 $f_i({\bf x})$ で
張られるベクトル空間 $V$ の次元となります。

$V$ がどのようなベクトル空間かについて考えます。
$f_i$  がいくつかの関数の一次結合で書けるとき、
$V$ 全体もその関数たちの一次結合で書けることになります。
つまり、その関数の集合を $G$ とすると、$V\subset \langle G\rangle$
となります。ここで、$\langle G\rangle$ は $G$ の元によってはられるベクトル
空間のこととします。
この包含関係により、$n\le \dim(\langle G\rangle)$ として不等式が得られます。

$f_i$ は、$x_1,\cdots, x_d$ の多項式関数なので、その成分がどのような
関数で書けているか？を考えます。
$f_i$ を慎重に展開を行うと、

$$(\sum_{i=1}^dx_i^2)^2,\ x_j\sum_{i=1}^dx_i^2,\ x_j^2,\ x_ix_j,\ x_j,\ 1$$
たちの一次結合でかけていることがわかります。
よって、これらの数を数えると、
$$n=\dim(V)\le \frac{1}{2}(d^2+5d+4)$$
となります。

最後に、${\mathbb R}^{d+1}$ の中の $\sum_{i=1}^{d+1}x_i=2$ となる超平面を
考えれば、この中に、$\{0,1\}^{d+1}$ の中で、ちょうど２つが $1$ となる
点が含まれます。これら $\binom{d+1}{2}$ 個の点は明らかに長さが2つもつ
点集合です。よって、上からの評価と下からの評価を合わせると、
$$\frac{1}{2}(d^2+d)\le n(d)\le \frac{1}{2}(d^2+5d+4)$$
となります。
この評価式から、$n(d)\sim \frac{1}{2}d^2$ がわかり、上からの評価はそれほど悪くない
ということがわかります。

また、$n(d)\le \binom{d+2}{2}$ も成り立つことがわかり、
上からの評価はさらに良くなるようです。

Miniature 18
では、直径縮小分割の話です。

$X\subset {\mathbb R}^d$ の分割 $X_1,X_2,\cdots, X_{k}$ で、任意の $i$ に対して
$\text{diam}(X_i)<\text{diam}(X)$ となるものを $X$ の $k$ 個への直径縮小分割
と言います。分割とは、$X=X_1\cup X_2\cup \cdots \cup X_k$ となることを意味します。

ボルスクの予想(Borsuk’s conjecture)というのは次です。

予想
$X\subset {\mathbb R}^d$ を直径有限な集合とするとき、 $X$ には
$d+1$ 個の直径縮小分割が存在する。

例として、${\mathbb R}^{d+1}$ 次元の $d$-単体の頂点を考えます。
この $d$-単体 $\sigma_d$ の直径は $1$ です。
$\sigma_d$ には $d+1$ 個の頂点が存在し、その $d$ 個の分割には、
必ず2点が含まれるので、$d$ 個への直径縮小分割は存在しない
ことになります。しかし、$d+1$ 個への直径縮小分割は、
それぞれの点を $X_i$ としてとることで、直径 $0$ の直径縮小分割が
存在することになります。

ボルスクの予想は、$\sigma_d$ の頂点集合だけでなく、
一般に、$d$ 次元球体においても $d+1$ 個の直径縮小分割が
知られています(1930 Borsuk)。
さらに、2,3次元のあらゆる集合においても、任意次元の
smooth convex setにおいてもボルスクの予想が成り立つことが知られています。

このMiniatureではこの予想が一般に成り立たないことを線形代数を使って
示しています。