2020-09-08

Sobolevの不等式

関数解析

前回の記事ではHardy-Littlewood-Sobolevの不等式を示しました. 今回は前回の不等式とポアソン方程式のよく知られた事実を使ってSobolevの不等式というものを証明していきたいと思います. Sobolevの不等式はSobolev空間と $L^{p}$ 空間やヘルダー空間の包含関係を把握するのに必要な不等式です.

[定義] (Newtonポテンシャル)

$n=2$ のとき

$\Phi(x) = -\frac{1}{2\pi} \log |x|$ ,

$n \ge 3$ のとき

$\Phi(x) = \frac{1}{(n-2)|\partial B_{1}(0)|}|x|^{2-n}$

とおく. $\Phi：\mathbb{R}^{n}\setminus \{0\} \rightarrow \mathbb{R}$ をNewtonポテンシャルといい, 原点以外で $\Delta \Phi =0$ を満たす ( $|\partial B_{1}(0)|$ は単位球面の面積である).

[定理] (Sobolevの不等式)

$1\le p \lt n$ とする. 実数 $p^{*}$ を $\frac{1}{p^{*}}=\frac{1}{p}-\frac{1}{n}$ で定める. このとき,

$\exists C_{p,\ n}\gt 0\ \ \text{s.t.}\ \ \forall u \in C_{0}^{1}(\mathbb{R}^{n}),\ \|u\|_{L^{p^{*}}(\mathbb{R}^{n})}\le C_{p, n}\|\nabla u\|_{L^{p}(\mathbb{R}^{n})}$

が成り立つ.

[証明]

Case1：　 $p\gt 1$ .

$w(x) = \int_{\mathbb{R}^{n}} \Phi(x-y)u(y)dy$

とおく (ただし $\Phi$ はNewtonポテンシャルである). 次の事実を使う.

[事実]：ポアソン方程式の古典解の存在

$n\ge 2$ とする. 任意の $f\in C_{0}^{1}(\mathbb{R}^{n})$ に対して,

$w(x) = \int_{\mathbb{R}^{n}} \Phi(x-y)f(y)dy$

は $C^{2}$ 級で, $-\Delta w = f$ を満たす.

この事実と積分記号下の微分定理[非線形偏微分方程式, 共立出版]により

f:id:togedemaru419:20200908014620p:plain

となる. ここでNewtonポテンシャルの評価で

$|\nabla \Phi(x)|\le \frac{C}{|x|^{n-1}}$

が成り立つので, コーシーシュワルツの不等式とRieszポテンシャル $I_{1}$ を用いて

$\displaystyle |u(x)|\le \int_{\mathbb{R}^{n}}\frac{C}{|x-y|^{n-1}}|\nabla u(y)|dy=C I_{1}[|\nabla u|]$

が成り立つ. ここでHardy-Littlewood-Sobolevの不等式を用いると,

togedemaru419.hatenablog.com

$\|u\|_{L^{p^{*}}(\mathbb{R}^{n})}\le C\|I_{1}[|\nabla u|]\|_{L^{p^{*}}(\mathbb{R}^{n})}\le C\|\nabla u\|_{L^{p}(\mathbb{R}^{n})}$

が成り立つ.　　( $p\gt 1$ の場合の証明終)

Case2：　 $p=1$ .

各 $j=1,\, \ldots ,\, n$ について

$\displaystyle u(x) = \int_{-\infty}^{x_{j}}\partial_{x_{j}}u(x_{1},\ \ldots,\ x_{j-1},\ y_{j},\ x_{j+1},\ \ldots,\ x_{n})dy_{j}$

となるので,

f:id:togedemaru419:20200908152558p:plain

最後の行で一般化ヘルダーの不等式を用いた. 次に $x_{2}$ について積分すると

f:id:togedemaru419:20200908155013p:plain

となる. 以下同様に $x_{3},\ \ldots,\ x_{n}$ について積分していくと

$\displaystyle \int_{\mathbb{R}^{n}}|u(x)|^{\frac{n}{n-1}}dx \le \prod_{j=1}^{n}\left( \int_{\mathbb{R}^{n}}|\partial_{x_{j}}u(x)|dx\right)^{\frac{1}{n-1}}$

となる. ここで両辺を $\frac{n-1}{n}$ 乗すると

f:id:togedemaru419:20200908160800p:plain

となる. 上から2行目の不等式は相加平均・相乗平均の不等式, 最後の行の不等式は和をベクトルの内積とみてコーシーシュワルツの不等式を用いた. 　(証明終)

2020-09-08

Hardy-Littlewood-Sobolevの不等式

関数解析

急にSobolev空間の記事を書きたくなりました。主な参考文献はEvansのPDEと儀我儀我非線形偏微分方程式です。

[定理](一般化ヤングの不等式)

$1\lt p,\ q,\ r\lt \infty$ が $\frac{1}{q}=\frac{1}{p}+\frac{1}{r}-1$ を満たすとする. このとき

$\|f*g\|_{L^{q}(\mathbb{R}^{n})} \le C_{p,q}|g|_{r,\ \infty}\|f\|_{L^{p}(\mathbb{R}^{n})},\ \ \ g\in L^{r,\ \infty}(\mathbb{R}^{n}),\ f\in L^{p}(\mathbb{R}^{n})$

が成り立つ.

$L^{r,\ \infty}$ は弱 $L^{r}$ 空間(またはローレンツ空間)といいます. これについての詳細は今後ブログで書きます. この一般化ヤングの不等式を示すにはMarcinkiewiczの補間定理などが必要になりますがここでは上記の不等式を認めます.

[定理](Hardy-Littlewood-Sobolevの不等式)

$0\lt \alpha \lt n$ とする. $p,\ q$ が

$1\lt p,\ q\lt \infty$ かつ $\frac{1}{q}=\frac{1}{p}-\frac{\alpha}{n}$

を満たすとする. このとき, 任意の $f\in C_{0}(\mathbb{R}^{n})$ に対して,

$\|I_{\alpha}[f] \|_{L^{q}(\mathbb{R}^{n})} \le C_{\alpha,\ p,\ n}\|f\|_{L^{p}(\mathbb{R}^{n})}$

が成り立つ.

ここで $\displaystyle I_{\alpha}[f]=\int_{\mathbb{R}^{n}}\frac{f(y)}{|x-y|^{n-\alpha}}dy$ であり, これを $f$ のRieszポテンシャルといいます. ポアソン方程式を勉強するとこいつがよく出てきます.

[証明]

$|x|^{-n+\alpha}\in L^{\frac{n}{n-\alpha},\ \infty}(\mathbb{R}^{n})$ であるので, 一般化Youngの不等式より $1\lt p,\ q\lt \infty$ かつ $\frac{1}{q}=\frac{1}{p}+\frac{n-\alpha}{n}-1=\frac{1}{p}-\frac{\alpha}{n}$ に対して

$\|I_{\alpha}[f] \|_{L^{q}(\mathbb{R}^{n})} \le C\||x|^{-n+\alpha}\|_{L^{\frac{n}{n-\alpha}, \infty}(\mathbb{R}^{n})}\|f\|_{L^{p}(\mathbb{R}^{n})}= C_{\alpha,\ p,\ n}\|f\|_{L^{p}(\mathbb{R}^{n})}$ ///

2017-10-11

Hallの定理とその応用

グラフ理論

[Def]近傍

グラフ $G$ の任意の点集合 $S$ に対して、 $S$ のどれかの点に隣接する点の全体を $G$ における $S$ の近傍と呼び、 $N_{G}(S)$ や $N(S)$ と書く。

$G$ を2部分割 $(X,Y)$ を持つ2部グラフとするとき、 $X$ の点がすべて飽和されるような $G$ のマッチングを見つけることは応用上重要である。

[Thm]Hallの定理

$G$ を2部分割 $(X,Y)$ を持つ2部グラフとする。

$G$ は $X$ の点を全て飽和するマッチングを持つ $\Leftrightarrow$ 任意の $S \subseteq X$ に対して、 $|N(S)| \geq |S|$

(証明)

( $\Rightarrow$ )

$X$ の全ての点を飽和するマッチングを $M$ とする。

任意の $S \subseteq X$ を考える。

$S$ を飽和する $M$ の辺を集めた集合を $M_{S}$ とすると、

$|S| = |M_{S}|$ .

$M_{S}$ が飽和する $Y$ の頂点は全て $N(S)$ の元である。

よって、 $|M_{S}| \leq |N(S)|$ .

つまり、 $|S| \leq |N(S)|$ . 　■

( $\Leftarrow$ )

$(X,Y)$ を部集合に持つ2部グラフで $\forall S \subseteq X,|N(S)| \geq |S|$ を満たすものを $G$ とする。

そこで $G$ は $X$ の点を全て飽和するマッチングを持たないと仮定して矛盾を導く。

$M$ を $G$ の最大マッチングとする。

仮定により、 $X$ に属する $M$ 非飽和点 $u$ が存在する。

そこで、 $Z$ を $M$ 交互道によって、 $u$ に連結するような点の全体の集合とする。

$M$ は最大マッチングだから、 $u$ は $Z$ の中で唯一の $M$ 非飽和点である。(もし、そうでないとすると $M$ 増加道が存在することになり $M$ の最大性に矛盾。)

$S = Z \cup X , T = Z \cup Y$ とおく。

明らかに $S \setminus ｛u｝$ の点は $M$ の下で $T$ の点とマッチングされているから

$|T| = |S| -1$ であり、 $T \subseteq N(S)$ が成り立つ。

$N(S)$ のどの点も $M$ 交互道により $u$ に連結されているので $N(S) \subseteq T$ .

よって $N(S) = T$ が成り立つ。

よって $|N(S)| = |T| = |S| - 1 ＜ |S|$ となって仮定に矛盾。　■

[Prob]Hallの定理を応用した面白い問題

トランプのカード52枚を4枚ずつ13個のグループへ任意に分けた時、各グループから1枚ずつカードをうまく選ぶと、A,2,3,4,5,6,7,8,9,10,J,Q,Kを1枚ずつ取り出せる。

(解答)

$A =$ グループに対応する頂点の集合

$B =$ カードのランクに対応する頂点の集合

とおく。

$A$ の各点(グループのこと)に対して、その点とその点に対応するグループに属するカードのランクに対応する $B$ の点を辺で結ぶ。そうでないとき辺を引かない。

この操作により2部グラフができる。

$\forall S \subseteq A$ を考える。

$N(S)$ は $S$ に属するグループに含まれるカードのランクに対応する。

$S$ に属するグループに含まれるカードの総数は $4|S|$

$N(S)$ に対応するランクのカードの総数は $4|N(S)|$

$|N(S)|＜ |S|$ と仮定する。

$|S|$ 個のグループを $N(S)$ に対応するランクのカードだけでつくれない。

実際 $|S|$ 個のグループをつくるには $4|S|$ 枚のカードが必要であるが、この仮定のもとでは $4|N(S)|$ 枚のカードしか用意できないためカードが足りなくなる。

よって $|S| \leq |N(S)|$ .

つまりHallの定理にある条件が成り立つので $A$ を飽和するマッチングが存在する。

そこから各グループからどのカードを選べばよいかわかる。■

2017-10-07

マッチング

グラフ理論

単純無向グラフ $G=(V,E)$ を考える。

[Def](マッチング)

$M \subseteq E$ のどの2辺も互いに隣接しないとき、 $M$ を $G$ のマッチングという。

マッチング $M$ に属する辺の両端点は $M$ でマッチングされているという。

点 $v$ がマッチング $M$ に属する辺の端点のとき、 $M$ は $v$ を飽和しているといい、 $v$ を $M$ 飽和点という。

$G$ の全ての点が $M$ 飽和点のときマッチング $M$ は完全マッチングという。

$|M^{'} |＞|M|$ となるマッチング $M^{'}$ が存在しないとき、 $M$ を最大マッチングという。

[Def](交互道)

$M$ を $G$ のマッチングとする。

$M$ に関する交互道とは $G$ における道 $v_{0}-...-v_{k}(k \geqq1)$ で $M$ の辺と $E \setminus M$ の辺が交互に現れるもの。

[Def](増加道)

$M$ に関する増加道とは、 $M$ に関する交互道 $v_{0}-...-v_{k}(k \geqq1)$ で $v_{0}$ と $v_{k}$ が $M$ 非飽和なものである。

[Thm](Berge,1957)

$M \subseteq E$ が $G$ の最大マッチング $\Leftrightarrow$ $M$ に関する増加道が存在しない。

[証明]

( $\Rightarrow$ )

対偶:

$M$ に関する増加道が存在 $\Rightarrow$ $M$ は最大マッチングでない

を示す。

$M$ に関する増加道があると仮定し、 $v_{0}-v_{1}-...-v_{2m+1}$ を増加道とする。

辺 $v_{1}v_{2},...,v_{2m-1}v_{2m}$ は $M$ の辺であり、これらを $M$ から取り除き、新たに辺 $v_{0}v_{1},...,v_{2m}v_{2m+1}$ を加えたものを $M^{'}$ とする。

このとき交互道の定義から $M^{'}$ がマッチングであることがすぐにわかる。

さらに $|M^{'}| = |M|+1$ から $M$ が最大マッチングでないことがわかる。

( $\Leftarrow$ )

対偶:

$M$ が最大マッチングでない $\Rightarrow$ $M$ に関する増加道が存在

を示す。

$M$ が $G$ の最大マッチングでないとする。

$M^{'}$ を $G$ の最大マッチングとする。

つまり $|M^{'}| ＞|M|$ が成り立つ。

グラフ $H = (V,M△M^{'})$ を考える。(△は対称差であり $M△M^{'}=(M\cup M^{'})\setminus (M \cap M^{'})$ )

このとき $H$ の各点の次数は高々2である。

よって $H$ の各連結成分は孤立点か $M$ と $M^{'}$ の辺を交互にとる偶サイクルか $M$ と $M^{'}$ の辺が交互に現れる道である。

偶サイクルにおいてそれに含まれる $M$ の辺の数と $M^{'}$ の辺の数は等しい。

$|M^{'}| ＞|M|$ より、( $M$ の辺の数)<( $M^{'}$ の辺の数)を満たす $H$ の道 $P$ が存在する。このとき $P$ の始まりも終わりも $M^{'}$ の辺になる。

つまり $P$ の始点と終点は $H$ では $M^{'}$ 飽和であるが、 $G$ では $M$ 非飽和である。

よって $P$ は $G$ の $M$ に関する増加道である。■

2017-10-04

最短距離の起こる回数

離散幾何

[Thm]

平面上に $n$ ( $n≧3$ )個の点が与えられたとき、最短距離は $3n - 6$ 個より多くは起こりえない。

(証明)

最短距離を $r$ とおく。

点の個数 $n$ のグラフGを次のように定める。

「Gの頂点集合を $P_{1},P_{2},...,P_{n}$ とする。また2点 $P_{i}$ , $P_{j}$ 間の距離が $r$ のときに限りそれら2点を結ぶ。この操作により得られた線分の集合をGの辺集合と定める。」

[Claim]

Gは平面グラフである。

(proof of Claim)

Gが平面グラフでないとする。

つまり2辺 $P_{i}P_{j}$ , $P_{k}P_{l}$ が点 $Q$ で交わっているとする。

三角不等式より

${ QP_{i} + QP_{k} ≧ P_{i}P_{k}}$

$QP_{j} + QP_{l} ≧ P_{j}P_{l}$ .

よって

${\displaystyle\ P_{i}P_{j} + P_{k}P_{l} ＞ P_{i}P_{k} + P_{j}P_{l}}$

つまり ${\displaystyle\ 2r ＞ P_{i}P_{k} +P_{j}P_{l}}$

これより $P_{i}P_{k}$ , $P_{j}P_{l}$ の少なくとも一方は $r$ 未満である。

これは $r$ の定義に矛盾する。■

Claimにより、Gが単純平面グラフであることがわかる。

よって

togedemaru419.hatenablog.com

↑により点の個数 $n$ の平面グラフGの辺の本数、つまり最短距離が起こる回数は $3n - 6$ 以下である。■

うまいことグラフを定義して特定の距離が起こる回数を、定義したグラフの辺数に帰着させてるところが面白いですよね。

2017-10-03

オイラーの公式の応用

グラフ理論

[Def]平面グラフ

グラフが平面グラフであるとは、辺が交わることなく平面(または2次元球面)上に描くことができるグラフのことである。

■オイラーの公式■

Gが連結平面グラフで、 $n$ 個の頂点、 $e$ 個の辺、 $f$ 個の面を持てば、次の関係式が成り立つ。

${\displaystyle\ n - e + f = 2}$

[離散幾何でしばしば使われる命題]

Gを空でない単純(多重辺とループがない)連結平面グラフとする。このとき以下が成り立つ。

(1) Gは高々5次の頂点を持つ。

(2)Gの辺の数は高々 $3n-6$ である。

(記号の注意)

$k$ 面とは $k$ 個の辺で囲まれた面のこととする。

$f_{k}$ を $k$ 面の数とする。

$n_{i}$ をグラフGにおける次数 $i$ の頂点の数とする。

(証明)

Gの頂点数を $n$ ,辺数を $e$ ,面数を $f$ とする。

Gは単純グラフだから、あらゆる面は少なくとも3つの辺を持つ。

$f = f_{3} + f_{4} + f_{5} +.....$

$2e = 3f_{3} + 4f_{4} + 5f_{5} + ....$

が得られ、 $2e - 3f ≧0$ となる。

ここで、もし全ての頂点の次数が少なくとも6であれば

$n = n_{6} + n_{7} + n_{8} + ...$

$2e = 6n_{6} + 7n_{7} + 8n_{8} + ...$

が得られ、 $2e - 6n ≧0$ となる。

2つの不等式をあわせると、

$6(e - n - f) = (2e - 6n) + 2(2e - 3f) ≧0$

つまり $e ≧ n +f$ が得られるが、これはオイラーの公式に矛盾する。■

(2)　(1)より $2e - 3f ≧0$ が得られていたので、オイラーの公式から

$3n - 6 = 3e - 3f ≧ e$ となる。■

2017-10-03

距離の出現回数

離散幾何

凸包の定義

点集合Pの凸包とは、Pの点を全て含む極小の凸集合のことである。

(イメージ的にはPの各点を板に打ち付けた釘とみなした時、全ての釘を含むように外側から輪ゴムを掛けてできる凸多角形がPの凸包である。)

定理:

平面上にn個の点(n≧3) ${\displaystyle\ P_{1},P_{2},...,P_{n}}$ が与えられたとき、

${\displaystyle\ {\sqrt{n-{\frac{3}{4}}}}-{\frac{1}{2}}}$ 個以上の異なる値を持つ距離が存在する。

(証明)

Case1: ${\displaystyle\ P_{1},...,P_{n}}$ が同一直線上にある

定理の成立は明らか。

Case2:Case1以外

点集合P={ ${\displaystyle\ P_{1},P_{2},...,P_{n}}$ }の凸包をとり、必要に応じて頂点の記号を交換することにより、 ${\displaystyle\ P_{1}}$ を凸包上の1点と仮定してもよい。

このとき、凸包の頂点 ${\displaystyle\ P_{1}}$ での内角は180°未満である。

${\displaystyle\ P_{1}}$ から ${\displaystyle\ P_{2},...,P_{n}}$ へのn-1個の距離を考える。これらの距離のうち ${\displaystyle\ k}$ 種類の異なる距離 ${\displaystyle\ d_{1},...,d_{k}}$ が起き、

各 ${\displaystyle\ d_{i}}$ ( ${\displaystyle\ i=1,..,k}$ )がそれぞれ ${\displaystyle\ f_{i}}$ 回起きると仮定すると、

${\displaystyle\ n-1 = \sum_{i=1}^{k} f_{i} \ }$

が成り立つ。

${\displaystyle\ f_{i}}$ のうち一番大きな値のものを ${\displaystyle\ N}$ とすると、

${\displaystyle\ \sum_{i=1}^{k} f_{i}\ ≦kN}$ となるので、

${\displaystyle\ k≧{\frac{n-1}{N}}}$ を得る。

ここでN回起きる距離をrとし、 ${\displaystyle\ P_{1}}$ を中心とする半径rの円を

${\displaystyle\ P_{1}(r)}$ で表す。

${\displaystyle\ P_{1}(r)}$ の円周上にはN個の点が存在して、それらの点を ${\displaystyle\ Q_{1},...,Q_{N}}$ とする。頂点 ${\displaystyle\ P_{1}}$ での凸包の内角が180°未満なので、N個の点 ${\displaystyle\ Q_{1},...,Q_{N}}$ は ${\displaystyle\ P_{1}(r)}$ の半円周上にある。よって、N-1個の距離 ${\displaystyle\ Q_{1}Q_{2},...,Q_{1}Q_{N}}$ はすべて異なる。

このように{ ${\displaystyle\ d_{1},...,d_{k}}$ }と{ ${\displaystyle\ Q_{1}Q_{j}}$ }( ${\displaystyle\ j=2,..,N}$ )の2つの実数の集合を考えると、それぞれちょうど ${\displaystyle\ k(≧{\frac{n-1}{N}})}$ 個とN-1個の異なる値を含む。