Dehn関数(Dehn function)とは、有限表示群で長さ $\ell$ 以下の語が単位元を表すことを示すのに必要な関係子の共役の個数の最大値である。表示の取り方によらず定数倍の違いを除いて定まり、準等長で変わらない群の不変量になる。双曲群では一次以下、$\mathbb Z^2$ では二次、Baumslag–Solitar 群 $\mathrm{BS}(1,2)$ では指数関数であり、二次より遅く増えるなら双曲群である。
有限表示 $\langle S\mid R\rangle$ をもつ群で、語 $w$ が単位元を表すことを確かめるには、$w$ を関係子の共役の積に書けばよい。Dehn関数(Dehn function)は、長さ $\ell$ 以下の語についてそのために必要な関係子の個数の最大値である。表示を取り替えても、Dehn関数は定数倍と変数の定数倍の違いを除いて変わらない(thm-dehn-invariance)ので、群の不変量になる。
Dehn関数は、群の幾何(Cayley グラフの中で閉じた道を埋める円板の面積)と、語の問題(群論)の難しさの両方を測る。たとえば 双曲群 では一次関数で抑えられ、逆に二次関数より真に遅く増える Dehn関数をもつ群は双曲群に限られる。
| 結果 | 内容 | この記事での扱い |
|---|---|---|
| thm-dehn-invariance | 表示によらないこと | 証明する |
| lem-dehn-fox | Fox 微分による下からの評価 | 証明する |
| prop-dehn-z2 | $\mathbb Z^2$ の Dehn関数は二次 | 証明する |
| thm-dehn-bs | $\mathrm{BS}(1,2)$ の Dehn関数は指数関数 | 証明する |
| prop-dehn-hyperbolic | 双曲群の Dehn関数は一次以下 | 証明する |
| thm-dehn-gap | 二次より遅ければ双曲群 | 主張と所在 |
| thm-dehn-qi・thm-dehn-gersten | 準等長不変性・語の問題との関係 | 主張と所在 |
$S$ を有限集合、$F=F(S)$ を $S$ 上の自由群とし、$S^{\pm1}$ の文字の有限列を 語 という。語は $F$ の元を表し、自由簡約($ss^{-1}$ や $s^{-1}s$ を消すこと)で移り合う語は同じ元を表す。$R\subset F$ を有限集合、$N$ を $R$ の $F$ での正規閉包とし、$G=F/N$ を表示 $\langle S\mid R\rangle$ の群とする。語 $w$ が $G$ の単位元を表すことと $w\in N$ は同値で、そのとき $w$ は $F$ の中で
$$
w=\prod_{i=1}^k u_i\,r_i^{\varepsilon_i}\,u_i^{-1}\qquad(u_i\in F,\ r_i\in R,\ \varepsilon_i=\pm1)
$$
の形に書ける。
$w\in N$ について、上の形の表し方での $k$ の最小値を $w$ の 面積 といい、$\operatorname{Area}(w)$ と書く($w=1$ なら $0$)。自然数 $\ell$ について
$$
\operatorname{Dehn}(\ell):=\max\{\operatorname{Area}(w): w \text{ は長さ } \ell \text{ 以下の語で、} G \text{ の単位元を表す}\}
$$
とおき、表示 $\langle S\mid R\rangle$ の Dehn関数 という。
長さ $\ell$ 以下の語は有限個なので、$\operatorname{Dehn}(\ell)$ は有限の値で、$\ell$ について単調増加である。面積は $F$ の元に対して定まるので、自由簡約で変わらない。これは DK17 Definitions 7.94・7.95(p. 240)の定義である。
$u,v\in N$、$g\in F$ について次が成り立つ。
Dehn関数を比べるときは、次の順序を使う(DK17 Definition 1.3, p. 2)。
$f,g\colon\mathbb N\to\mathbb R$ について、正の定数 $A,B,C,D,E$ があって十分大きいすべての $\ell$ で
$$
f(\ell)\le A\,g(B\ell+C)+D\ell+E
$$
となるとき $f\preccurlyeq g$ と書く。$f\preccurlyeq g$ かつ $g\preccurlyeq f$ のとき $f\asymp g$ と書き、同値 という。
$\ell\preccurlyeq0$(定数関数 $0$)なので、一次以下の関数はすべて $0$ と同値である。また $3^\ell\le2^{2\ell}$ から $2^\ell\asymp3^\ell$ である。
$\langle S\mid R\rangle$ と $\langle S'\mid R'\rangle$ が同じ群 $G$ の有限表示なら、それぞれの Dehn関数 $\operatorname{Dehn}$、$\operatorname{Dehn}'$ は $\operatorname{Dehn}\asymp\operatorname{Dehn}'$ を満たす。
対称なので $\operatorname{Dehn}'\preccurlyeq\operatorname{Dehn}$ を示す。$F=F(S)$、$F'=F(S')$ とし、$s\in S$ ごとに $G$ で同じ元を表す $S'$ の語 $\varphi(s)$、$s'\in S'$ ごとに同じ元を表す $S$ の語 $\psi(s')$ を選ぶ。これらは準同型 $\varphi\colon F\to F'$、$\psi\colon F'\to F$ に延び、$G$ への像を保つ。$K:=\max_{s'}\lvert\psi(s')\rvert$、$A_0:=\max_{r\in R}\operatorname{Area}'(\varphi(r))$、$A_1:=\max_{s'\in S'}\operatorname{Area}'(s'\,\varphi\psi(s')^{-1})$ とおく($\varphi(r)$ と $s'\varphi\psi(s')^{-1}$ は単位元を表すので面積が定まる)。
$w'=x_1\cdots x_m$($x_i\in S'^{\pm1}$、$m\le\ell$)が単位元を表すとする。$\psi(w')$ は長さ $K\ell$ 以下で単位元を表す $S$ の語なので、$\operatorname{Dehn}(K\ell)$ 個以下の $u_ir_i^{\pm1}u_i^{-1}$ の積である。$\varphi$ を施すと、$\varphi\psi(w')$ は $\varphi(u_i)\varphi(r_i)^{\pm1}\varphi(u_i)^{-1}$ の積になり、lem-dehn-basic の 1 から $\operatorname{Area}'(\varphi\psi(w'))\le A_0\operatorname{Dehn}(K\ell)$ である。次に $y_i:=\varphi\psi(x_i)$、$P_i:=x_1\cdots x_i$ とおくと、$m$ についての帰納法で
$$
w'\,\bigl(\varphi\psi(w')\bigr)^{-1}=x_1\cdots x_m\,y_m^{-1}\cdots y_1^{-1}=\prod_{i=m}^{1}P_{i-1}\,(x_iy_i^{-1})\,P_{i-1}^{-1}
$$
(積は $i=m$ から $i=1$ の順)であり、$x_iy_i^{-1}$ は $s'\varphi\psi(s')^{-1}$ か、その逆元の共役($x_i=s'^{-1}$ のとき $s'^{-1}\varphi\psi(s')=s'^{-1}(s'\varphi\psi(s')^{-1})^{-1}s'$)なので、面積は $A_1$ 以下である。よって
$$
\operatorname{Dehn}'(\ell)\le A_0\operatorname{Dehn}(K\ell)+A_1\ell
$$
となり、$\operatorname{Dehn}'\preccurlyeq\operatorname{Dehn}$ である。$\square$
これは DK17 Exercise 7.96(p. 241)である。以下、有限表示群 $G$ の Dehn関数 $\operatorname{Dehn}_G$ を、$\asymp$ の同値類として扱う。
自由群 $F(S)=\langle S\mid\ \rangle$ では、単位元を表す語は自由簡約で空になるので $\operatorname{Dehn}=0$ である。同じ自由群 $\mathbb Z$ の表示 $\langle a,b\mid b\rangle$ では、語 $b^\ell$ の面積は $\ell$ である($b$ の指数和は、$b^{\pm1}$ の共役 1 個ごとに $\pm1$ しか変わらない)。どちらの Dehn関数も $0$ と同値で、thm-dehn-invariance と矛盾しない。
面積を下から評価するには、$w$ のどんな表し方にも共通して現れる量を見つければよい。そのための道具が Fox 微分である。$\mathbb ZG$ を $G$ の群環とし、$c=\sum_g c_gg\in\mathbb ZG$ に $\|c\|_1:=\sum_g\lvert c_g\rvert$ とおく。語 $u$ の $G$ での像を $\bar u$ と書く。
$x\in S$ と語 $w=y_1\cdots y_m$($y_j\in S^{\pm1}$)に対し、$\partial_xw\in\mathbb ZG$ を次の和で定める。$y_j=x$ なら $+\overline{y_1\cdots y_{j-1}}$、$y_j=x^{-1}$ なら $-\overline{y_1\cdots y_j}$ を加え、それ以外の文字は何も加えない。
定義から $\partial_x(pq)=\partial_xp+\bar p\,\partial_xq$ である。$w$ の途中に $xx^{-1}$ を挟むと、挟んだ位置の接頭辞を $\bar p$ として $+\bar p-\bar p\,\bar x\bar x^{-1}=0$ が加わるだけであり、$x^{-1}x$ でも $-\bar p\bar x^{-1}+\bar p\bar x^{-1}=0$ である。$x$ 以外の文字の組についても何も加わらないので、$\partial_xw$ は自由簡約で変わらず、$F$ の元に対して定まる。
$G=\langle S\mid r\rangle$ を関係子が 1 個の表示とし、$x\in S$ とする。$w\in N$ を $w=\prod_{i=1}^ku_ir^{\varepsilon_i}u_i^{-1}$ と表すと、$c:=\sum_i\varepsilon_i\bar u_i$ について
$$
\partial_xw=c\cdot\partial_xr,\qquad\|c\|_1\le k
$$
が成り立つ。とくに、$c\cdot\partial_xr=\partial_xw$ を満たす $c\in\mathbb ZG$ がただ 1 つなら、$\operatorname{Area}(w)\ge\|c\|_1$ である。
$\bar r=1$ なので $0=\partial_x(rr^{-1})=\partial_xr+\partial_x(r^{-1})$、同様に $0=\partial_x(uu^{-1})=\partial_xu+\bar u\,\partial_x(u^{-1})$ である。よって
$$
\partial_x(ur^{\varepsilon}u^{-1})=\partial_xu+\bar u\,\partial_x(r^{\varepsilon})+\bar u\,\partial_x(u^{-1})=\varepsilon\,\bar u\,\partial_xr
$$
となる。各 $u_ir^{\varepsilon_i}u_i^{-1}$ の像は $1$ なので、積の公式から $\partial_xw=\sum_i\varepsilon_i\bar u_i\,\partial_xr$ である。$\|c\|_1\le k$ は三角不等式による。最後の主張は、最短の表し方に前半を当てはめればよい。$\square$
Fox 微分の考え方は、$w$ を埋める円板の 2 胞体を、Cayley グラフの頂点 $\bar u_i$ に置かれた関係子として数えることである。$c$ がただ 1 つに決まれば、どの円板もその個数以上の 2 胞体をもつ。
$\mathbb Z^2=\langle a,b\mid aba^{-1}b^{-1}\rangle$ の Dehn関数は、$\operatorname{Dehn}(\ell)\le\ell^2/4$ と $\operatorname{Dehn}(4n)\ge n^2$ を満たす。とくに $\operatorname{Dehn}_{\mathbb Z^2}(\ell)\asymp\ell^2$ である。
上から. $x\in\{a^{\pm1}\}$、$y\in\{b^{\pm1}\}$ について $yx(xy)^{-1}=yxy^{-1}x^{-1}$ は、関係子 $r=aba^{-1}b^{-1}$ の巡回置換か、その逆元の共役であり、面積 $1$ である。単位元を表す長さ $\ell$ の語 $w$ が $a^{\pm1}$ を $\alpha$ 個、$b^{\pm1}$ を $\beta$ 個含むとする。$b^{\pm1}$ の直後に $a^{\pm1}$ がある箇所を入れ替えることをくり返す。1 回ごとに「$b^{\pm1}$ が $a^{\pm1}$ より前にある文字の組」が 1 つ減るので、$\alpha\beta$ 回以下で $a^{\pm1}$ だけの語のあとに $b^{\pm1}$ だけの語が続く形になる。$w$ は単位元を表し、入れ替えで $a$ と $b$ の指数和は変わらないので、どちらの部分も指数和が $0$ で、自由簡約で空になる。lem-dehn-basic の 2 から $\operatorname{Area}(w)\le\alpha\beta\le\ell^2/4$ である。
下から. $w_n:=a^nb^na^{-n}b^{-n}$ は長さ $4n$ で単位元を表す。定義から $\partial_ar=1-b$ である。$w_n$ の $a$ は接頭辞 $1,a,\dots,a^{n-1}$ の後にあり、$a^{-1}$ を含む接頭辞の像は $a^{n-j}b^n$($1\le j\le n$)なので、$T:=\sum_{i=0}^{n-1}a^i$ として
$$
\partial_aw_n=(1-b^n)\,T=c\,(1-b),\qquad c:=(1+b+\dots+b^{n-1})\,T
$$
である。$\mathbb Z[\mathbb Z^2]$ は Laurent 多項式環 $\mathbb Z[a^{\pm1},b^{\pm1}]$ で整域なので、$c(1-b)=\partial_aw_n$ を満たす $c$ はただ 1 つであり、lem-dehn-fox から $\operatorname{Area}(w_n)\ge\|c\|_1=n^2$ である。
$\ell\ge1$ について $n=\lceil\ell/4\rceil$ とおくと $4n\le\ell+3$ なので、$\ell^2\le16n^2\le16\operatorname{Dehn}(\ell+3)$ である。$\square$
$w_n$ を Cayley グラフ(平面の格子)の上の閉じた道とみると、辺の長さ $n$ の正方形の周であり、面積 $n^2$ はその中の単位正方形の個数である。
$\mathrm{BS}(1,2)=\langle t,b\mid tbt^{-1}b^{-2}\rangle$ は、$\mathbb Z[1/2]\rtimes\mathbb Z$(積 $(r,k)(s,l)=(r+2^ks,\,k+l)$)と $t\mapsto(0,1)$、$b\mapsto(1,0)$ で同型である(群の表示複体 の例「Baumslag–Solitar 群 BS(1,2)」)。とくに $b$ は無限位数で、$t^nbt^{-n}=b^{2^n}$ である。
$G=\mathrm{BS}(1,2)$ の上の表示の Dehn関数は、$\operatorname{Dehn}(\ell)\le\ell\,2^\ell$ と $\operatorname{Dehn}(4n+4)\ge2^{n+1}-2$ を満たす。とくに $\operatorname{Dehn}_G(\ell)\asymp2^\ell$ である。
$r=tbt^{-1}b^{-2}$ とする。
下から. $w_n:=[t^nbt^{-n},b]=t^nbt^{-n}\,b\,t^nb^{-1}t^{-n}\,b^{-1}$ は長さ $4n+4$ で、$t^nbt^{-n}=b^{2^n}$ と $b$ は可換なので単位元を表す。$\partial_tr=1-tbt^{-1}$ の像は $1-b^2$ である。$w_n$ の 4 つの $t^{\pm n}$ の塊からの寄与を順に足すと、$T:=\sum_{j=0}^{n-1}t^j$ として
$$
\partial_tw_n=T-b^{2^n}T+b^{2^n+1}T-bT=(1-b)(1-b^{2^n})\,T
$$
である。$b^{2^n}t^j=t^jb^{2^{n-j}}$ と $1-b^{2m}=\bigl(\sum_{k=0}^{m-1}b^{2k}\bigr)(1-b^2)$ から、
$$
\partial_tw_n=c\,(1-b^2),\qquad c:=\sum_{j=0}^{n-1}(1-b)\,t^j\sum_{k=0}^{2^{n-j-1}-1}b^{2k}
$$
である。$t^jb^{2k}=b^{2^{j+1}k}t^j$ なので、$c$ に現れる元 $b^{2^{j+1}k}t^j$ と $-b^{2^{j+1}k+1}t^j$ はすべて異なり、$\|c\|_1=\sum_{j=0}^{n-1}2\cdot2^{n-j-1}=2^{n+1}-2$ である。$c'(1-b^2)=0$ なら $c'=c'b^2$ で、$c'$ の係数は各剰余類 $g\langle b^2\rangle$ の上で一定である。$b$ は無限位数なので剰余類は無限集合であり、係数が有限個の $c'$ は $0$ である。よって $c$ はただ 1 つで、lem-dehn-fox から $\operatorname{Area}(w_n)\ge2^{n+1}-2$ である。
上から. 次の置き換えを考える($\varepsilon=\pm1$)。
$$
tb^{\varepsilon}\to b^{2\varepsilon}t,\qquad b^{\varepsilon}t^{-1}\to t^{-1}b^{2\varepsilon}.
$$
置き換え前後の語 $x,y$ について $xy^{-1}$ は、$tbt^{-1}b^{-2}=r$、$tb^{-1}t^{-1}b^2=b^{-2}r^{-1}b^2$、$bt^{-1}b^{-2}t=t^{-1}rt$、$b^{-1}t^{-1}b^2t=t^{-1}b^{-2}r^{-1}b^2t$ であり、面積 $1$ である。単位元を表す長さ $\ell$ の語 $w$ に、置き換えと自由簡約をできる限りくり返す。$t$ の文字は右へ、$t^{-1}$ の文字は左へだけ動き、$t^{\pm1}$ の文字どうしは追い越さない。$b^{\pm1}$ の文字は、$t^{\pm1}$ の文字に追い越されるたびに同じ側の 2 文字に置き換わる。同じ $t^{\pm1}$ の文字は、ある $b^{\pm1}$ の文字から生じた文字を 2 度追い越さない(追い越した後に生じる 2 文字は、その $t^{\pm1}$ の文字の後ろ側にあり、その文字は前にしか進まない)。よって $w$ の各 $b^{\pm1}$ の文字から生じる文字の系図は、深さが $t^{\pm1}$ の文字の個数以下の二分木で、置き換えられる文字は $2^\ell$ 個未満である。置き換えの回数はこれらの合計で、$\ell\,2^\ell$ 以下である。とくに手続きは止まる。
止まった語には $tb^{\pm1}$、$b^{\pm1}t^{-1}$、$tt^{-1}$、$t^{-1}t$ が現れないので、$t^{-1}$ の文字は先頭に、$t$ の文字は末尾に集まり、語は $t^{-p}ut^q$($u$ は $b^{\pm1}$ だけの語で、指数和を $M$ とする)の形である。この像は $(2^{-p}M,\ q-p)$ で、単位元なので $p=q$、$M=0$ となり、語は自由簡約で空になる。lem-dehn-basic の 2 から $\operatorname{Area}(w)\le\ell\,2^\ell$ である。
最後に、$2^\ell\le\operatorname{Dehn}(4\ell+4)+2$ かつ $\ell\,2^\ell\le2^{2\ell}$ なので、$\operatorname{Dehn}_G\asymp2^\ell$ である。$\square$
$w_n$ は、$t^nbt^{-n}$ が長さ $2n+1$ の語で長さ $2^n$ の語 $b^{2^n}$ と同じ元を表すことを使って、$b^{2^n}$ と $b$ の交換子を短く書いたものである。短い語の中に、平面の正方形では起こらない「指数関数的に大きな面積」が隠れている。
有限生成群 $G$ が双曲群なら、$G$ は有限表示をもち、$\operatorname{Dehn}_G(\ell)\preccurlyeq\ell$、すなわち $\operatorname{Dehn}_G\asymp0$ である。
双曲群 の系「語の問題・有限表示・線形の等周不等式」の 2 により有限表示 $\langle S\mid R\rangle$ があり、同 3 によりその表示で単位元を表す語 $w$ は $R$ の元の共役 $\lvert w\rvert$ 個以下の積である。よってこの表示で $\operatorname{Dehn}(\ell)\le\ell$ であり、thm-dehn-invariance からどの有限表示でも同じ結論になる。$\square$
逆も成り立ち、さらに一次と二次の間には Dehn関数が存在しない。
有限表示群 $G$ の Dehn関数が $\operatorname{Dehn}_G(\ell)/\ell^2\to0$($\ell\to\infty$)を満たすなら、$G$ は双曲群である。とくに $\operatorname{Dehn}_G$ は一次以下である。
Gromov による。DK17 Theorem 11.181(p. 432)は、粗く単連結な測地的距離空間で埋める面積の関数が $o(\ell^2)$ なら双曲的であることを述べ、同 Theorem 9.80(p. 324)は、有限表示群の Cayley グラフで埋める面積の関数が Dehn関数と同値であることを述べる。2 つを合わせると thm-dehn-gap になる。
prop-dehn-z2・thm-dehn-bs と prop-dehn-hyperbolic から、$\mathbb Z^2$ と $\mathrm{BS}(1,2)$ はどちらも双曲群でない。$\ell^2\preccurlyeq\ell$ は成り立たないからである($\mathbb Z^2$ については 双曲群 でも別の方法で確かめている)。
有限表示群 $G,H$ が準等長(準等長写像)なら $\operatorname{Dehn}_G\asymp\operatorname{Dehn}_H$ である。とくに有限表示群とその指数有限の部分群の Dehn関数は同値である。
たとえば $\mathbb Z^2$ を指数有限の部分群にもつ群の Dehn関数は二次、$\mathrm{BS}(1,2)$ と準等長な有限表示群の Dehn関数は指数関数であり、$\mathbb Z^2$ と $\mathrm{BS}(1,2)$ は準等長でない。
$\operatorname{Dehn}(\ell)$ は、長さ $\ell$ の語が単位元を表すことの「証明」の長さの上限である。
有限表示群 $G$ について、次は同値である。(1) $G$ の語の問題が解ける。(2) $G$ の Dehn関数は計算可能関数である。(3) $G$ の Dehn関数は、ある計算可能関数で上から抑えられる。
語の問題(群論) の定理「Novikov–Boone の定理」と合わせると、計算可能などの関数でも上から抑えられない Dehn関数をもつ有限表示群が存在する。一方、ex-dehn-free・prop-dehn-z2・thm-dehn-bs の群の Dehn関数は計算可能である。
| 主張 | 外す条件 | 例 | 成り立たない結論 |
|---|---|---|---|
| thm-dehn-invariance | 表示が有限 | $\mathbb Z^2$ の表示 $\langle a,b\mid N\rangle$($N$ は単位元を表す語の全体) | 面積は $1$ 以下で、Dehn関数が二次でなくなる |
| thm-dehn-gap | $o(\ell^2)$($O(\ell^2)$ に弱める) | $\mathbb Z^2$ | 双曲群でない |
| def-dehn-order の同値 | 一次の項 $D\ell+E$ | $\mathbb Z$ の 2 つの表示(ex-dehn-free) | $\ell\le A\cdot0$ は成り立たず、表示によらなくなる |
| lem-dehn-fox の最後の主張 | $c$ がただ 1 つ | $\mathbb Z/2=\langle a\mid a^2\rangle$、$w=a^4$ | $c=3-a$ も条件を満たすが、係数の絶対値の和 $4$ は面積($2$ 以下)より大きい |
1 行目:単位元を表す語 $w$ は $N$ の元なので $w=w^{1}$ と書け、面積は $1$ 以下である。prop-dehn-z2 の有限表示では二次なので、有限でない表示を許すと Dehn関数は群で決まらない。
2 行目:prop-dehn-z2 により $\operatorname{Dehn}_{\mathbb Z^2}\asymp\ell^2$ で $O(\ell^2)$ だが、$\mathbb Z^2$ は双曲群でない(prop-dehn-hyperbolic と、$\ell^2\preccurlyeq\ell$ が成り立たないこと)。
3 行目:$\langle a\mid\ \rangle$ の Dehn関数は $0$、$\langle a,b\mid b\rangle$ の Dehn関数は $\ell$ で、一次の項がなければ $\ell\le A\cdot0$ が必要になる。
4 行目:$\partial_a(a^2)=1+a$、$\partial_aw=1+a+a^2+a^3=2+2a$ である。$c=1+a$ と $c=3-a$ はどちらも $c(1+a)=2+2a$ を満たす($(1-a)(1+a)=0$)。$w=a^2\cdot a^2$ なので面積は $2$ 以下である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する