自己回避歩行(self-avoiding walk)とは、グラフの上の歩行で同じ頂点を二度通らないもののことである。頂点推移的なグラフでは $n$ 歩の自己回避歩行の個数 $c_n$ が $c_{m+n}\le c_mc_n$ をみたし、極限 $\mu=\lim c_n^{1/n}$(連結定数)が存在する。六角格子では $\mu=\sqrt{2+\sqrt2}$ であることが、回転角で重みをつけた観測量の局所的な打ち消しから証明される。2 次元の尺度極限が SLE$_{8/3}$ であることは予想として残っている。
自己回避歩行(self-avoiding walk)とは、グラフの上の歩行で、同じ頂点を二度通らないもののことである。高分子の鎖が自分自身と重ならないことを表す模型として化学者 Flory が考え(DCS12 §1)、ランダムウォーク と違って過去の道筋をすべて覚えている点で、扱いの難しい組合せ論と確率論の対象になった。
基本の量は、決めた頂点から出る $n$ 歩の自己回避歩行の個数 $c_n$ である。$c_n$ は劣乗法的な不等式 $c_{m+n}\le c_mc_n$ をみたすので、Feketeの補題 から極限
$$
\mu:=\lim_{n\to\infty}c_n^{1/n}
$$
が存在する。これを 連結定数(connective constant)という。$\mu$ の正確な値は、正方格子 $\mathbb Z^2$ を含む $\mathbb Z^d$($d\ge2$)では知られていない(2018 年の Gri18 p. 43 の時点)が、六角格子(蜂の巣格子)では
$$
\mu=\sqrt{2+\sqrt2}=2\cos\frac{\pi}{8}=1.84775\ldots
$$
であることが Duminil-Copin と Smirnov によって証明された(DCS12)。この記事はこの定理を完全に証明し、2 次元の尺度極限についての予想を述べる。
| 主張 | 内容 | この記事で |
|---|---|---|
| prop-saw-mu | 連結定数の存在と $c_n\ge\mu^n$ | 証明する |
| prop-saw-gf | 母関数の収束半径は $1/\mu$ で、そこで発散する | 証明する |
| lem-saw-obs | パラフェルミオン観測量の局所関係式 | 証明する |
| lem-saw-strip | 帯の上の恒等式 | 証明する |
| lem-saw-hw | ブリッジへの分解による上からの評価 | 証明する |
| thm-saw-hex | 六角格子の連結定数は $\sqrt{2+\sqrt2}$ | 証明する |
| conj-saw-2d | 2 次元の臨界指数と SLE$_{8/3}$ | 予想(未解決) |
$G=(V,E)$ を無限の連結なグラフで、各頂点の次数が有限なものとする。
$o\in V$ とする。頂点の列 $\gamma=(\gamma_0,\gamma_1,\dots,\gamma_n)$ が $o$ から出る $n$ 歩の自己回避歩行 であるとは、$\gamma_0=o$、$\gamma_{i-1}$ と $\gamma_i$ が隣接し、$\gamma_0,\dots,\gamma_n$ が互いに異なることをいう。その個数を $c_n=c_n(o)$ と書く($c_0=1$)。極限 $\mu(G):=\lim_{n\to\infty}c_n^{1/n}$ が存在するとき、これを $G$ の 連結定数 という。
$G$ が 頂点推移的、すなわち任意の 2 頂点 $x,y$ に $x$ を $y$ に移すグラフの自己同型があるとき、$c_n(o)$ は $o$ によらない。$\mathbb Z^d$(隣り合う格子点を結ぶ)と六角格子はこの場合である。次数が $\Delta$ なら、1 歩目は $\Delta$ 通り、2 歩目以降は来た頂点に戻れないので $\Delta-1$ 通り以下であり、
$$
c_n\le\Delta(\Delta-1)^{n-1}
$$
である。
$G$ を頂点推移的で次数 $\Delta$ のグラフとする。
連結定数は、自己回避歩行の母関数の収束半径として現れる。
prop-saw-mu の状況で $\chi(x):=\sum_{n\ge0}c_nx^n$($x>0$)とおく。$\chi$ の収束半径は $1/\mu$ であり、$\chi(1/\mu)=\infty$ である。
Cauchy–Hadamardの定理 から収束半径は $1/\limsup c_n^{1/n}=1/\mu$ である。$x=1/\mu$ では prop-saw-mu の 2 から各項 $c_n\mu^{-n}\ge1$ なので級数は発散する。$\square$
劣乗法性から得られるのは $c_n=\mu^{n+o(n)}$ までで、$c_n/\mu^n$ の振る舞い(多項式の補正)は別の問題である。
深さ優先探索で数えると次のとおりである。
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 10 | 12 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|
| $\mathbb Z^2$ の $c_n$ | 4 | 12 | 36 | 100 | 284 | 780 | 5916 | 44100 | 324932 | 2374444 |
| 六角格子の $c_n$ | 3 | 6 | 12 | 24 | 48 | 90 | 336 | 1218 | 4416 | 15780 |
六角格子では $c_{26}=30526374$ で、$c_{26}^{1/26}=1.9403$、$(c_{26}/c_{24})^{1/2}=1.8721$ である。prop-saw-mu の 2 から $c_n^{1/n}$ は上から $\mu$ に近づくが、その近づき方は遅い。比 $(c_n/c_{n-2})^{1/2}$ のほうが $\sqrt{2+\sqrt2}=1.8478$ に早く近づく。$\mathbb Z^2$ の $n=14$ の比は $2.703$ で、こちらの $\mu$ の正確な値は知られていない。
六角格子 $\mathbb H$ の連結定数は $\mu(\mathbb H)=\sqrt{2+\sqrt2}$ である。
歩行を回転角で複素数の重みをつけて数えると、臨界の $x=x_c$ で局所的な打ち消しが起きる(lem-saw-obs)。これを帯の中で足すと、正の重みだけの恒等式(lem-saw-strip)が得られ、下からの評価が出る。上からの評価は、歩行をブリッジに分ける組合せ論(lem-saw-hw)による。証明は prf-saw-hex に置く。
この節を通して $x_c:=1/\sqrt{2+\sqrt2}$、$\sigma:=5/8$、$j:=e^{2\pi i/3}$ とおく。$\sqrt{2+\sqrt2}=2\cos(\pi/8)$ である。
中点の間の歩行。 $\mathbb H$ を複素平面に、辺の長さが $1$ で辺の向きが $\pi/2$、$7\pi/6$、$-\pi/6$ になるように置く。各頂点から出る 3 本の辺は向きが $2\pi/3$ ずつ違うので、頂点を通るたびに歩行の向きは $\pm\pi/3$ だけ変わる。辺の中点を単に 中点 という。中点 $a$ から出る歩行 $\gamma\colon a\to z$ とは、$a$ から半辺を進んで頂点に入り、互いに異なる頂点を辿って、最後にある辺の中点 $z$ で止まるものとする(何も進まない $a\to a$ も含める)。$\gamma$ が通る頂点の数を $\ell(\gamma)$、$a$ から $z$ までに曲がった角の和を 回転角 $W(\gamma)$ と書く。
$$
Z(x):=\sum_{\gamma\colon a\to\,\cdot}x^{\ell(\gamma)}
$$
とおく(和は $a$ から出るすべての歩行にわたる)。$\ell$ 個の頂点を通る歩行の個数 $N_\ell$ は $c_{\ell-1}\le N_\ell\le4c_{\ell-1}$ をみたす。上からは、最初の頂点が 2 通り、そこから $\ell-1$ 歩の自己回避歩行、最後の中点が 2 通りだからである。下からは、最初の頂点 $v_1$ を固定すると、$v_1$ から出る $\ell-1$ 歩の自己回避歩行は、終点の辺のうち来た辺でも $a$ の辺でもないものを選んで止まれば、$a$ からの歩行になるからである。よって $Z$ の収束半径は $\chi$ と同じ $1/\mu(\mathbb H)$ であり(prop-saw-gf)、thm-saw-hex は次の 2 つと同値である。
$$
Z(x_c)=\infty,\qquad Z(x)< \infty\quad(0< x< x_c).
$$
領域と観測量。 頂点の有限集合 $S$ について、少なくとも一方の端点が $S$ にある辺の中点の集合を $M$、ちょうど一方の端点が $S$ にある中点を 境界の中点 という。$S$ を内部にもつ六角形の和集合の補集合が連結なとき、領域は 単連結 であるという。$a$ を境界の中点とし、頂点を $S$ の中にとる歩行 $\gamma\colon a\to z$($z\in M$)だけを考えて
$$
F(z):=\sum_{\gamma\colon a\to z}e^{-i\sigma W(\gamma)}x^{\ell(\gamma)}
$$
とおく。これを パラフェルミオン観測量 という(DCS12 Definition 1)。
領域は単連結で $a$ は境界の中点、$x=x_c$、$\sigma=5/8$ とする。$v\in S$ の 3 本の辺の中点を $p,q,r$ とすると
$$
(p-v)F(p)+(q-v)F(q)+(r-v)F(r)=0
$$
である。
$p,q,r$ を $v$ のまわりの反時計回りの順に名づけると $q-v=j(p-v)$、$r-v=\bar j(p-v)$ である。左辺は、$p,q,r$ のどれかで終わる歩行 $\gamma$ の寄与 $(z-v)e^{-i\sigma W(\gamma)}x^{\ell(\gamma)}$($z$ は $\gamma$ の終点)の和である。$\gamma$ が途中と終点で通る $\{p,q,r\}$ の中点の個数で分ける。
3 つすべてを通る歩行は対になる。 最初に通るものを(名前を巡回させて)$p$ とする。$\gamma$ は、$a$ から $p$ までの道 $\pi$、$p$ から $v$ を通って $q$ か $r$ へ出る 1 歩、そこから $\pi$ と交わらずに回って残りの中点で止まる道 $\rho$ からなる。$\rho$ を逆向きに辿り $v$ から出る向きを替えた歩行を対にする。通る頂点の集合は同じで $\ell$ も等しい。$p$ までの回転角を $W_0$ とする。$v$ と $\rho$ がつくる閉路は $p$ を外側に残す($\pi$ は境界の $a$ から閉路に交わらずに来る)ので、閉路の内側は、$v$ のところでは $q$ の辺と $r$ の辺の間の、$p$ の辺を含まない側にある。$r$ へ出る向きに進むと $p$ の辺は左手にあるので内側は右手にあり、閉路は $r$ から出て $q$ から戻る向きなら時計回りである。時計回りの閉路を一周する回転角は $-2\pi$ で、$v$ で $q$ から入って $r$ へ出る曲がりは $-\frac\pi3$ なので、$r$ を出てから $q$ に着くまでの回転角は $-2\pi+\frac\pi3$ である。逆向きの閉路では符号が逆になる。$v$ で曲がる角と合わせて回転角を数えると、$q$ で終わる方は $W_0-\frac{4\pi}3$、$r$ で終わる方は $W_0+\frac{4\pi}3$ になる。2 つの寄与の和は
$$
(p-v)e^{-i\sigma W_0}x^{\ell}\Bigl(je^{i\frac{5\pi}{6}}+\bar je^{-i\frac{5\pi}{6}}\Bigr)=(p-v)e^{-i\sigma W_0}x^{\ell}\cdot2\cos\frac{3\pi}{2}=0
$$
である。
1 つか 2 つを通る歩行は 3 つ組になる。 ちょうど 1 つを通る歩行 $\gamma_1$ は、その中点($p$ とする)で外から来て止まり、$v$ を通っていない。$\gamma_1$ を $v$ まで延ばし、$q$ か $r$ へ 1 歩出て止まる 2 本の歩行 $\gamma_2,\gamma_3$ は、ちょうど 2 つを通る。逆に、ちょうど 2 つを通る歩行の最後の 1 歩を消すとちょうど 1 つを通る歩行になる。$v$ で $q$ へは $-\pi/3$、$r$ へは $+\pi/3$ 曲がるので、3 本の寄与の和は
$$
(p-v)e^{-i\sigma W(\gamma_1)}x^{\ell(\gamma_1)}\Bigl(1+x\,je^{i\frac{5\pi}{24}}+x\,\bar je^{-i\frac{5\pi}{24}}\Bigr)=(p-v)e^{-i\sigma W(\gamma_1)}x^{\ell(\gamma_1)}\Bigl(1+2x\cos\frac{7\pi}{8}\Bigr)
$$
である。$2\cos(7\pi/8)=-2\cos(\pi/8)=-1/x_c$ なので、$x=x_c$ でこれは $0$ である。
すべての歩行はちょうど一つの対か 3 つ組に入るので、和は $0$ である。$\square$
この補題で $x=x_c$ を使うのは 3 つ組の打ち消しだけで、$\sigma=5/8$ は対の打ち消しで決まる。左辺は、$v$ のまわりの小さな閉路に沿った $F$ の離散的な線積分とみることができ、関係式は離散的な Cauchy–Riemannの方程式 の半分にあたる(DCS12 Remark 1)。
帯。 $n\ge1$、$m\ge0$ とし、$a$ を下の辺の中央の中点とする、高さ $n$ の六角形の帯を左右で斜めに切った単連結な領域 $S_{m,n}$ をとる(Gri18 Figure 3.4、p. 47。下の辺に $2m+1$ 個の中点がある)。境界の中点を、$a$ 以外の下の辺 $\mathcal L$、上の辺 $\mathcal U$、左右の辺 $\mathcal T$ に分け、
$$
A_{m,n}:=\sum_{\gamma\colon a\to\mathcal L}x^{\ell(\gamma)},\qquad B_{m,n}:=\sum_{\gamma\colon a\to\mathcal U}x^{\ell(\gamma)},\qquad E_{m,n}:=\sum_{\gamma\colon a\to\mathcal T}x^{\ell(\gamma)}
$$
とおく(歩行は $S_{m,n}$ の中にとる)。
$x=x_c$ のとき $c_\alpha A_{m,n}+B_{m,n}+c_\varepsilon E_{m,n}=1$ である。ここで $c_\alpha=\cos(3\pi/8)$、$c_\varepsilon=\cos(\pi/4)$ である。
要点:lem-saw-obs を $S_{m,n}$ のすべての頂点で足すと境界の中点だけが残り、回転角が境界の辺ごとに決まることと左右の対称性から恒等式になる。
両端が $S_{m,n}$ にある中点 $z$ は 2 つの頂点 $v,v'$ の和に現れ、$z$ は $v,v'$ の中点なので係数は $(z-v)+(z-v')=0$ である。境界の中点 $z$ は 1 回だけ現れ、$2(z-v)$ は外へ向かう単位ベクトルで、下の辺では $-i$、上の辺では $i$、右の辺では $e^{-i\pi/6}$、左の辺では $e^{7i\pi/6}$ である。領域は単連結で $a$ は境界にあるので、$a$ から境界の中点への歩行の回転角は出発と到着の向きだけで決まり、$\mathcal L$ へは $\pm\pi$、$\mathcal U$ へは $0$、右の辺へは $-2\pi/3$、左の辺へは $2\pi/3$ である。$a$ を通る縦の直線についての鏡映は領域を保ち、回転角の符号を変えるので、$\mathcal L$ の左右の半分と左右の辺はそれぞれ同じ重みの和をもつ。$a\to a$ の歩行は何も進まないものだけで $F(a)=1$ である。以上から、足した式の 2 倍は $-i\bigl(1+\cos\frac{5\pi}8A_{m,n}\bigr)+iB_{m,n}+\frac{E_{m,n}}2\bigl(e^{-i\pi/6}e^{5i\pi/12}+e^{7i\pi/6}e^{-5i\pi/12}\bigr)$ である。最後の括弧は $e^{i\pi/4}+e^{3i\pi/4}=i\sqrt2$ で、$\cos\frac{5\pi}8=-\cos\frac{3\pi}8$ だから、全体は $i\bigl(-1+c_\alpha A_{m,n}+B_{m,n}+c_\varepsilon E_{m,n}\bigr)=0$ である。$\square$
$A_{m,n}$ と $B_{m,n}$ は $m$ について増加し、恒等式から $A_{m,n}\le1/c_\alpha$、$B_{m,n}\le1$ なので、極限 $A_n$、$B_n$ が存在する。$B_n$ は無限の帯 $S_n$ の中で $a$ から上の辺へ行く歩行(高さ $n$ の ブリッジ)の重みの和である。恒等式から $E_{m,n}$ は $m$ について減少し、極限 $E_n$ があって $c_\alpha A_n+B_n+c_\varepsilon E_n=1$ である。$x$ を明示するときは $B_n^x$ と書く。
すべての $x>0$ について $Z(x)\le2\prod_{n\ge1}\bigl(1+B_n^x\bigr)^2$ である。
要点:歩行を最初の最も高い頂点で 2 つに切り、それぞれを最も高い頂点で切り続けると、高さが狭義単調な列のブリッジに分かれ、もとの歩行はその列から一つに決まる。
出発点が最も低い歩行(半平面の歩行)$\gamma$ を考える。最も高い頂点のうち最後に通るものまでで切って半辺を足すと、高さ $T_0$ のブリッジ $\gamma_1$ が得られる。残りを上下に反転すると、高さが $T_0$ より真に小さい半平面の歩行になる。これを繰り返すと $\gamma$ は高さ $T_0>T_1>\dots>T_k$ のブリッジに分かれる。一般の歩行は、最初の向きを決めたうえで、最初の最も高い頂点で切る。前半を逆に辿ったものと後半はともに半平面の歩行なので、高さ $T_{-i}< \dots< T_{-1}$ と $T_0>\dots>T_k$ のブリッジに分かれる。切り口に足すのは半辺と中点だけなので頂点の数は増えず、歩行は最初の向きとブリッジの列から復元できる(Gri18 pp. 51–52)。各ブリッジを平行移動して $a$ から出るようにすれば、高さの集合ごとの重みの和は $\prod B_{T}^x$ 以下で、高さが真に増える列と真に減る列の和はそれぞれ $\prod_n(1+B_n^x)$ 以下である。最初の向きの 2 通りで 2 倍する。$\square$
$Z(x_c)=\infty$。 $x=x_c$ とする。ある $n$ で $E_n>0$ なら、$E_{m,n}\ge E_n$ がすべての $m$ で成り立つ。$m$ が違うと左右の辺の位置が違うので、$E_{m,n}$ に数えられる歩行は $m$ ごとに異なり、$Z(x_c)\ge\sum_mE_{m,n}=\infty$ である。
すべての $n$ で $E_n=0$ なら $c_\alpha A_n+B_n=1$ である。$S_{n+1}$ の中で下の辺へ行く歩行のうち $S_n$ に収まらないものは、高さ $n+1$ の行の頂点を通る。その最初の最も高い頂点で切り、両側に上向きの半辺を足すと、上の辺の同じ中点から下の辺へ行く 2 本の歩行になり、逆に辿れば高さ $n+1$ のブリッジ 2 本である。切った頂点は両方に数えられるので頂点の数の和は $\ell+1$ で、
$$
A_{n+1}-A_n\le x_c^{-1}B_{n+1}^2
$$
である。$c_\alpha A_n+B_n=1$ を $n$ と $n+1$ で引くと $0\le c_\alpha x_c^{-1}B_{n+1}^2+B_{n+1}-B_n$ を得る。$C:=\min(B_1,x_c/c_\alpha)$ とし $B_n\ge C/n$ を帰納法で示す。$f(y):=c_\alpha x_c^{-1}y^2+y$ は $y\ge0$ で増加し、$c_\alpha x_c^{-1}C\le1$ なので
$$
f\Bigl(\frac{C}{n+1}\Bigr)\le\frac{C}{(n+1)^2}+\frac{C}{n+1}=\frac{C(n+2)}{(n+1)^2}< \frac Cn\le B_n\le f(B_{n+1})
$$
であり、$B_{n+1}>C/(n+1)$ である。高さの違うブリッジは異なる歩行なので $Z(x_c)\ge\sum_nB_n=\infty$ である。
$Z(x)< \infty$($x< x_c$)。 高さ $n$ のブリッジは $n$ 個以上の頂点を通るので、$B_n^x\le(x/x_c)^nB_n^{x_c}\le(x/x_c)^n$ である($B_n^{x_c}\le1$ は恒等式から)。よって $\sum_nB_n^x< \infty$ で、無限積 $\prod_n(1+B_n^x)$ は収束し、lem-saw-hw から $Z(x)< \infty$ である。
最初に述べた同値性から $\mu(\mathbb H)=1/x_c=\sqrt{2+\sqrt2}$ である。$\square$
証明は DCS12 §3 と Gri18 Theorem 3.14(pp. 45–53)にそっている。$A_{n+1}-A_n$ の評価の係数は Gri18 p. 50 の $x^{-1}$ に合わせた。帰納法はどの正の係数でも同じに進む。
$\mathbb Z^2$ や $\mathbb H$ のような 2 次元の格子で、次が予想されている。
1 と 2 は Nienhuis の物理の議論による予想で、DCS12 §4 の (7)・(8) と Conjecture 1 に述べられている。$\mathbb Z^2$ の上の一様な自己回避歩行が SLE$_{8/3}$ に収束することは、2018 年の Gri18 pp. 42–44 で未解決の問題として述べられている。尺度極限が共形不変なら $\gamma$ と $\nu$ が計算できることが Lawler–Schramm–Werner によって示されている(DCS12 §4)。lem-saw-obs は観測量 $F$ の離散的な正則性の半分にあたり、残りの半分の極限での成立が示されれば 3 が従うと考えられている(DCS12 の要旨と §4)。
一方、高い次元では、立方格子 $\mathbb Z^d$($d\ge5$)で多項式の補正のない漸近 $c_n\sim A\mu^n$ が知られている(Gri18 p. 44)。この記事ではこれらを証明しない。
prop-saw-mu・prop-saw-gf・lem-saw-obs の仮定を一つずつ外した反例を表にする。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 頂点推移的(prop-saw-mu) | 根 $o$ をもつ木で、深さ $k$ の頂点の子の数を、$(2r)!\le k< (2r+1)!$($r\ge1$)なら $2$、それ以外は $1$ とする | $o$ から出る歩行は根から離れる一方なので $c_n=\prod_{k< n}b_k$。$c_n^{1/n}$ は $n=(2r+1)!$ で $2$ に、$n=(2r+2)!$ で $1$ に近づき、極限がない |
| 劣乗法性(prop-saw-gf) | $a_n=\mu^n/n^2$($a_6=\mu^6/36>a_3^2=\mu^6/81$) | 収束半径は $1/\mu$ だが $\sum a_n\mu^{-n}=\pi^2/6< \infty$ で、収束半径の上で発散しない |
| $x=x_c$(lem-saw-obs) | 頂点 1 つの領域 $S=\{v\}$、$a=p$、$x\ne x_c$、$\sigma=5/8$ | 左辺は $(p-v)\bigl(1-2x\cos\frac\pi8\bigr)\ne0$ |
| $\sigma=5/8$(lem-saw-obs) | 同じ領域で $x=x_c$、$\sigma=1/2$ | 左辺は $(p-v)\bigl(1-\sqrt3\,x_c\bigr)\ne0$($\sqrt3x_c=0.937$) |
第 1 行の木の次数は $3$ 以下で有界なので、極限がないのは頂点ごとに歩行の数え方が違うことによる。第 3 行・第 4 行では、$a=p$ から出る歩行は何も進まないものと $v$ を通って $q$、$r$ で止まる 2 本だけで、3 つ組の打ち消しの式がそのまま左辺になる。頂点 13 個と 19 個の領域(六角形を丸ごと含み、対の場合が現れる)で $F$ を全数で計算すると、$x=x_c$、$\sigma=5/8$ では関係式が浮動小数点の誤差の範囲で成り立った。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する