[場所1E503（月曜日5限）]
現在外書輪講では、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ではこの予想が一般に成り立たないことを線形代数を使って
示しています。
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ではこの予想が一般に成り立たないことを線形代数を使って
示しています。
0 件のコメント:
コメントを投稿