デーン関数

数学の分野である幾何群論において、マックス・デーンにちなんで名付けられたデーン関数は、有限群の表現に関連付けられた最適関数であり、その群内の関係（群の単位元を表す生成元内の自由に簡約された語）の面積を、その関係の長さで囲みます（ ^[1]の79～80ページを参照）。デーン関数の成長型は、有限に提示された群の準等長不変量です。有限に提示された群のデーン関数は、群の文章問題の非決定論的アルゴリズムの複雑性とも密接に関連しています。特に、有限に提示された群が文章問題を解けるのは、この群の有限表現に対するデーン関数が再帰的である場合のみです（ ^[1]の定理2.1を参照）。デーン関数の概念は、ユークリッド平面の古典的な等周不等式などの幾何学における等周問題や、より一般的には、リーマン多様体の極小面の面積をその面の境界曲線の長さで推定する充填面積関数の概念に由来しています。

有限に提示された群の等周関数のアイデアは、1910年代のマックス・デーンの研究に遡ります。デーンは、種数が少なくとも2である閉じた向き付けられた曲面の基本群の標準的な表現に関する単語問題が、現在デーンのアルゴリズムと呼ばれているものによって解けることを証明しました。この事実の直接的な帰結は、この表現ではデーン関数がDehn( n ) ≤nを満たすことです。この結果は、1960年代にマーティン・グリーンドリンガーによって、C'(1/6)の小さな相殺条件を満たす有限に提示された群に拡張されました。^{[2]今日使用されている等周関数とデーン関数の正式な概念は、}単語双曲群の理論の導入と発展とともに、1980年代後半から1990年代前半に登場しました。 1987 年のモノグラフ「双曲群」^[3]で、グロモフは有限生成群が語双曲的であるためには、それが線型等周不等式を満たす必要がある、つまり、この群のデーン関数が関数f ( n ) = nと同値である必要があることを証明しました。グロモフの証明は、主に、ヌルホモトピック閉曲線を囲む極小面の面積がその曲線の長さで制限されるコンパクトリーマン多様体の充填面積関数との類推に基づいています。

等周関数とデーン関数の研究は、特にこれらの関数の成長型が有限に提示された群の自然な準等長不変量であるため、幾何学的群論における別の主要テーマに急速に発展しました。この主題における主要な結果の1つは、サピア、ビルゲット、リップスによって得られ、彼らは^[4]チューリングマシンのほとんどの「合理的な」時間計算量関数は、自然な同値性まで、有限に提示された群のデーン関数として実現できることを 示しました。

させて

${\displaystyle G=\langle X|R\rangle \qquad (*)}$

有限群表現であり、Xは有限のアルファベットであり、R⊆F ( X ) は 循環的に縮小された単語の有限集合である。

w  ∈  F ( X ) をGの関係、つまりGでw  = 1となるような自由に簡約された語とします。これはw がF ( X )におけるRの正規閉包に属する、つまり wの表現が存在するということと同等であることに注意してください。

${\displaystyle w=u_{1}r_{1}u_{1}^{-1}\cdots u_{m}r_{m}u_{m}^{-1}{\text{ in }}F(X),}$   （♠）

ただし、m  ≥ 0であり、i  = 1, ...,  mに対してr _i  ∈  R ^{± 1}です。

Gにおいてw  = 1 を満たすw  ∈  F ( X )に対して、(∗) に関するwの面積(Area( w ) と表記) は、 w をR ^{± 1の元の}m個の共役のF ( X )における積として表す 表現 (♠) が存在するような最小のm ≥ 0 です。

自由に簡約された単語w  ∈  F ( X )がGでw  = 1を満たすのは、 (∗) に対応するGの表示複体でwでラベル付けされたループがヌルホモトピックである場合に限ります。この事実は、Area( w ) が、 wでラベル付けされた境界サイクルを持つ (∗) 上のファン・カンペン図の 2 セルの最小の数であることを示すために使用できます。

有限表現（∗）の等周関数は単調な非減少関数である。

${\displaystyle f:\mathbb {N} \to [0,\infty )}$

w  ∈  F ( X ) がGにおいてw  = 1 を満たす自由簡約語であるときはいつでも、

面積( w )  ≤f (| w |)、

ここで、 | w | は単語wの長さです。

すると有限表現(∗)の デーン関数は次のように定義される。

${\displaystyle {\rm {Dehn}}(n)=\max\{{\rm {Area}}(w):w=1{\text{ in }}G,|w|\leq n,w{\text{ 自由に縮小}}.\}}$

同様に、Dehn( n )は(∗)の最小の等周関数である。つまり、Dehn( n )は(∗)の等周関数であり、他の任意の等周関数f ( n ) に対しては、

デーン( n )  ≤f ( n )

すべてのn≥0に対して 。

正確なデーン関数は通常は表現に依存するため、通常はn が無限大に近づくにつれて漸近的に増加するタイプを研究しますが、これはグループにのみ依存します。

2つの単調非減少関数について

${\displaystyle f,g:\mathbb {N} \to [0,\infty )}$

fがgに支配されるとは、 C  ≥1 が 存在し、

${\displaystyle f(n)\leq Cg(Cn+C)+Cn+C}$

あらゆる整数n  ≥ 0 について成り立ちます。fがgによって支配され、g がfによって支配される場合、 f  ≈  gとします。この場合、 ≈ は同値関係であり、デーン関数と等周関数は通常、この同値関係まで研究されます。したがって、任意のa,b > 1について、 a ⁿ  ≈  b ⁿが成り立ちます。同様に、 f ( n ) がd次( d  ≥ 1 は実数) で係数が負でない多項式である場合、 f ( n ) ≈  n ^{d が成り立ち}ます。また、 1 ≈  n でもあります。

有限群の表現がnの線形（それぞれ、二次、三次、多項式、指数など）関数と同値な等周関数f ( n ) を許容する場合、その表現は線形（それぞれ、二次、三次、多項式、指数など）等周不等式を満たすと言われます。

• GとH が準等長有限 表示群であり、 Gの有限表示が等周関数f ( n ) を持つ場合、Hの任意の有限表示に対してf ( n )と同等の等周関数が存在する。 特に、この事実はG  =  Hに対して成り立ち、同じ群が 2 つの異なる有限表示によって与えられる。
• その結果、有限に提示された群の場合、上記の定義の意味でのデーン関数の成長タイプは、その群の有限の提示の選択に依存しません。より一般的には、2 つの有限に提示された群が準等長である場合、それらのデーン関数は同等です。
• 有限表現(∗)によって与えられた 有限表現群Gに対して、以下の条件は同値である。
  • Gは(∗)に関して再帰的なデーン関数を持つ。
  • (∗)に対して再帰的等周関数f ( n )が存在する。
  • グループGには解ける文章問題があります。

特に、これは、単語問題の解法が有限に提示された群に対する準等長不変量であることを意味します。

• 関係wの面積 Area( w ) がわかれば、(♠) の定義関係の共役の数だけでなく、共役元u _iの長さも | w |に関して制限することができます。結果として、^{[1] [5]}から、有限表現 (∗) によって与えられた有限提示群G が計算可能なデーン関数 Dehn( n ) を持つ場合、 Gの文章問題は非決定論的時間計算量Dehn( n ) と決定論的時間計算量Exp(Dehn( n ))で解けることがわかっています。しかし、一般に、文章問題の決定論的時間計算量に関して有限提示群のデーン関数に適切な制限はなく、2 つの関数間のギャップはかなり大きくなる可能性があります。

• 有限群Gの任意の有限表現に対して、Dehn( n )  ≈nが成り立つ。^[6]
• 種数2の閉曲面の場合、その基本群の標準的な表現は

${\displaystyle G=\langle a_{1},a_{2},b_{1},b_{2}|[a_{1},b_{1}][a_{2},b_{2}]= 1\rangle }$

Dehn( n ) ≤  nおよび Dehn( n ) ≈  n を満たします。

• 任意の整数k  ≥ 2に対して自由アーベル群は Dehn( n ) ≈  n ^2を満たす。^[6]${\displaystyle \mathbb {Z} ^{k}}$
• バウムスラッグ＝ソリタールグループ

${\displaystyle B(1,2)=\langle a,b|b^{-1}ab=a^{2}\rangle }$

Dehn( n )≈2nと^なる（^[7]を参照）。

• 3次元離散ハイゼンベルク群

${\displaystyle H_{3}=\langle a,b,t|[a,t]=[b,t]=1,[a,b]=t^{2}\rangle }$

3次等周不等式は満たすが、2次等周不等式は満たさない。^[8]

• 高次元ハイゼンベルク群

${\displaystyle H_{2k+1}=\langle a_{1},b_{1},\dots ,a_{k},b_{k},t|[a_{i},b_{i}]=t,[a_{i},t]=[b_{i},t]=1,i=1,\dots ,k,[a_{i},b_{j}]=1,i\neq j\rangle }$、

ここでk  ≥ 2は二次等周不等式を満たす。^[9]

• Gが「ノビコフ-ブーン群」、つまり解けない単語問題を持つ有限に提示された群である場合、 Gのデーン関数はどの再帰関数よりも速く増加します。
• トンプソン群 Fの場合、デーン関数は2次関数、つまりn ²に等しい（^[10]を参照）。
• いわゆるバウムスラッグ・ゲルステングループ

${\displaystyle G=\langle a,t|(t^{-1}a^{-1}t)a(t^{-1}at)=a^{2}\rangle }$

デーン関数は、指数関数の固定反復タワーよりも速く成長します。具体的には、このグループでは

デーン( n ) ≈ exp(exp(exp(...(exp(1))...)))

ここで指数関数の数はlog2(n)の整数部に等しい_（ [ 1 ] ^{[ 11]}を参照）。

• 有限表示群が語双曲群となるのは、そのデーン関数がnに等しい場合、つまり、この群のすべての有限表示が線型等周不等式を満たす場合のみです。^[3]
• 等周ギャップ：有限生成群が二次等周不等式を満たす場合、それは語双曲的である。^{[3] [12] [13]したがって、} d∈ (1,2)のn・^dと同値なデーン関数を持つ有限生成群は存在しない 。
• 自動群、そしてより一般的には、組み合わせ群は二次等周不等式を満たす。^[8]
• 有限生成冪零群は、d  ≥ 1 の n d と同値なデーン関数を持ち、すべての正の整数dは^このように実現される。さらに、すべての有限生成冪零群Gは、次数c  + 1の多項式等周不等式を許容する。ここでc はGの冪零類である。^[14]
• 実数全体の集合d ≥ 1は、 n ^d に等しいデーン関数を持つ有限生成群が存在する場合、区間内で稠密である。^[15]${\displaystyle [2,\infty )}$
• 有限生成群のすべての漸近錐が単連結である場合、その群は多項式等周不等式を満たす。^[16]
• 有限生成群が二次等周不等式を満たす場合、この群のすべての漸近錐は単連結である。^[17]
• ( M , g )が閉じたリーマン多様体でG  =  π ₁ ( M )のとき、 Gのデーン関数は多様体の充填面積関数と同値である。^[18]
• GがCAT(0)空間上の等長写像によって適切に不連続かつココンパクトに作用する群である場合、Gは二次等周不等式を満たす。^{[19]特に、これは}Gが非正断面曲率（必ずしも定数ではない）の閉じたリーマン多様体の基本群である場合に当てはまる。
• SL( m , Z )のデーン関数は、任意のm≥3に対してせいぜい指数関数的である。 [ ^20] SL(3, Z )の場合、この境界は鋭く、その場合、デーン関数は指数関数以下の上限を許さないことが知られている。^{[8] SL(} m , Z )のデーン関数（ m  >4）は2次関数である。^{[21] SL(4,} Z ) のデーン関数は、サーストンによって2次関数であると予想されている。これと、より一般的には、高階リー群の格子は2次デーン関数を持つというグロモフの予想は、ロイジンガーとヤングによって証明されている。^[22]
• 有限型曲面の写像類群は自動的に生成され、二次等周不等式を満たす。^[23]
• Aut( F _k ) および Out( F _k ) 群のデーン関数は、k ≥ 3 のいずれに対しても指数関数的である。k ≥ 3 の場合の Aut( F _k ) および Out( F _k )の指数等周不等式は、Hatcherと Vogtmann によって発見された。^{[24]これらの境界は明確であり、Aut(} F _k ) および Out( F _k )群は、 k  = 3 の場合に Bridson と Vogtmann によって示されたように、指数以下の等周不等式を満たさない。^[25]また、k ≥ 4 の場合に Handel と Mosher によって示されたように。^[26]
• 有限生成自由群Fk_の任意の自己同型 φに対して、φの写像トーラス群は二次等周不等式を満たす。^[27] ${\displaystyle F_{k}\rtimes _{\phi }\mathbb {Z} }$
• n ⁴以上の「合理的な」計算可能関数のほとんどは、同値性まで有限に提示された群のデーン関数として実現できます。特に、f ( n ) ≥  n ^{4が、そのバイナリ表現が}チューリングマシンによって時間内に計算可能な超加法関数である場合、f ( n ) は有限に提示された群のデーン関数と同値です。${\displaystyle O\left({\sqrt[{4}]{f(n)}}\right)}$
• グループのデーン関数をその単語問題の複雑さの観点から合理的に制限することはできませんが、Birget、Olʹshanskii、Rips、Sapirは次の結果を得て、^[28] Higmanの埋め込み定理の広範囲な一般化を提供しました。有限生成グループの単語問題は、このグループが多項式等周関数を持つ有限に提示されたグループに埋め込むことができる場合のみ、非決定性多項式時間で決定可能です。さらに、時間T( n )で解ける単語問題を持つすべてのグループは、 n ² T( n ² ) ⁴に等しい等周関数を持つグループに埋め込むことができます。

• 等周関数の概念に密接に関連する概念がいくつかあります。例えば、等直径関数^{[29] は、}特定の関係wに対するファン・カンペン図の最小直径(すべての辺の長さが 1 である単体的計量に関して) をwの長さに関して制限します。充填長関数は、特定の関係wに対するファン・カンペン図の最小充填長をwの長さに関して制限します。ここで、図の充填長は、図のすべての組み合わせヌルホモトピーにわたって、そのようなヌルホモトピーに沿って中間図を制限している中間ループの最大長の最小値です。^[30]充填長関数は、有限に提示された群の単語問題の非決定論的空間計算量と密接に関連しています。デーン関数、最適等直径関数、最適充填長関数を結び付ける一般的な不等式がいくつかありますが、それらの正確な関係はまだわかっていません。
• 等周関数とデーン関数の高次元一般化もある。^[31] k  ≥ 1の場合、群のk次元等周関数は、群が適切かつコンパクトに作用するk連結空間に写像された k 球の( k  + 1) 次元球充填の最小組合せ体積を境界とする。この境界は、 k球の組合せ体積の関数として与えられる。等周関数の標準的な概念は、k  = 1 の場合に対応する。古典的な場合と比較すると、これらの高次元充填関数についてはほとんど知られていない。主な結果の 1 つは、高階半単純リー群の格子は、階数以下の次元では歪みがない、つまり、関連する対称空間と同じ充填関数を満たすということである。^[22]
• グロモフは著書『無限群の漸近的不変量』^[32] で、デーン関数の確率的あるいは平均的バージョンを提案し、多くの群において平均デーン関数は標準デーン関数よりも厳密に遅い漸近性を持つはずだと示唆した。平均デーン関数あるいは平均デーン関数の概念のより正確な扱いは、後に他の研究者によってなされ、彼らはまた、平均デーン関数がいくつかのケース（冪零群やアーベル群など）において標準デーン関数に対して確かに部分漸近的であることを証明した。^{[33] [34] [35]}

• 等周関数の概念の相対バージョンは、オシンの相対双曲群へのアプローチにおいて中心的な役割を果たしている。^[36]
• グリゴルチュクとイワノフは、有限個の生成元を持つが定義関係が無限個ある場合の群表現に対するデーン関数のいくつかの自然な一般化を検討した。^[37]

• ファン・カンペン図
• 単語双曲群
• 自動グループ
• 小さな相殺理論
• 幾何群論

• Noel Brady、Tim Riley、Hamish Short。有限生成群の単語問題の幾何学。数学上級コース CRM Barcelona、Birkhäuser、バーゼル、2007 年。ISBN 3-7643-7949-9。 
• マーティン・R・ブリッドソン。「言葉の問題の幾何学」。幾何学と位相幾何学への招待、pp. 29-91、オックスフォード大学院数学テキスト、7、オックスフォード大学出版局、オックスフォード、2002年。ISBN 0-19-850772-0。 

• SL(n,Z) の等周不等式。2008 年 9 月のアメリカ数学研究所でのワークショップ。
• Bridson の論文「単語問題の幾何学」の PDF。