[場所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 件のコメント:
コメントを投稿