Dehn funktion

Ej att förväxla med Dehn invariant .

I det matematiska ämnet geometrisk gruppteori är en Dehn-funktion , uppkallad efter Max Dehn , en optimal funktion associerad med en finit grupppresentation som begränsar arean av en relation i den gruppen (det vill säga ett fritt reducerat ord i generatorerna som representerar identitetselement i gruppen) i termer av längden på den relationen (se s. 79–80 i ). Tillväxttypen för Dehn-funktionen är en kvasi-isometri-invariant av en ändligt presenterad grupp . Dehn-funktionen för en ändligt presenterad grupp är också nära förbunden med icke-deterministisk algoritmisk komplexitet hos ordproblemet i grupper. I synnerhet har en finit presenterad grupp lösbara ordproblem om och bara om Dehn-funktionen för en finit presentation av denna grupp är rekursiv (se sats 2.1 i ). Föreställningen om en Dehn-funktion är motiverad av isoperimetriska problem inom geometri, såsom den klassiska isoperimetriska olikheten för det euklidiska planet och, mer generellt, föreställningen om en fyllningsareafunktion som uppskattar arean av en minimal yta i ett Riemann-grenrör i termer av av längden på gränskurvan för den ytan.

Historia

Idén om en isoperimetrisk funktion för en ändligt presenterad grupp går tillbaka till Max Dehns arbete på 1910-talet. Dehn bevisade att ordproblemet för standardpresentationen av den grundläggande gruppen av en sluten orienterad yta av släktet minst två är lösbart med vad som nu kallas Dehns algoritm . En direkt konsekvens av detta faktum är att för denna presentation uppfyller Dehn-funktionen Dehn( n ) ≤ n . Detta resultat utökades på 1960-talet av Martin Greendlinger till att ändligt presenterade grupper som uppfyllde C'(1/6) small cancellation-villkoret . Den formella föreställningen om en isoperimetrisk funktion och en Dehn-funktion som den används idag dök upp i slutet av 1980-talet – början av 1990-talet tillsammans med introduktionen och utvecklingen av teorin om ordhyperboliska grupper . I sin monografi "Hyperboliska grupper" från 1987 Gromov att en ändligt presenterad grupp är ordhyperbolisk om och endast om den uppfyller en linjär isoperimetrisk olikhet, det vill säga om och endast om denna grupps Dehn-funktion är ekvivalent med funktionen f ( n ) = n . Gromovs bevis var till stor del informerat i analogi med fyllningsareafunktioner för kompakta Riemannska grenrör där arean av en minimal yta som avgränsar en noll-homotop sluten kurva är avgränsad i termer av längden på den kurvan.

Studiet av isoperimetriska och Dehn-funktioner utvecklades snabbt till ett separat huvudtema i geometrisk gruppteori , särskilt eftersom tillväxttyperna för dessa funktioner är naturliga kvasi-isometri- invarianter av finitely presenterade grupper. Ett av de viktigaste resultaten i ämnet erhölls av Sapir, Birget och Rips som visade att de flesta "rimliga" tidskomplexitetsfunktionerna hos Turing-maskiner kan realiseras, upp till naturlig ekvivalens, eftersom Dehn fungerar i ändligt presenterade grupper.

Formell definition

Låta

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

vara en finit grupppresentation där X är ett finit alfabet och där R ⊆ F ( X ) är en finit uppsättning cykliskt reducerade ord.

Area av en relation

Låt w ∈ F ( X ) vara en relation i G , det vill säga ett fritt reducerat ord så att w = 1 i G . Observera att detta motsvarar att säga att w tillhör den normala stängningen av R i F ( X ), det vill säga det finns en representation av w som

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

där m ≥ 0 och där r _i ∈ R ^{± 1} för i = 1, ..., m .

För w ∈ F ( X ) som uppfyller w = 1 i G , är arean av w med avseende på (∗), betecknad Area( w ), den minsta m ≥ 0 så att det finns en representation (♠) för w som produkt i F ( X ) av m konjugat av element av R ^{± 1} .

Ett fritt reducerat ord w ∈ F ( X ) uppfyller w = 1 i G om och endast om slingan märkt med w i presentationskomplexet för G som motsvarar (∗) är noll-homotop . Detta faktum kan användas för att visa att Area( w ) är det minsta antalet 2-celler i ett van Kampen-diagram över (∗) med gränscykel märkt med w .

Isoperimetrisk funktion

En isoperimetrisk funktion för en finit presentation (∗) är en monoton icke-minskande funktion

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

så att när w ∈ F ( X ) är ett fritt reducerat ord som uppfyller w = 1 i G , då

Area( w ) ≤ f (| w |),

där | w | är längden på ordet w .

Dehn funktion

Då definieras Dehn-funktionen för en finit presentation (∗).

${\rm {Dehn}}(n)=\max\{{\rm {Area}}(w):w=1{\text{ i }}G,|w|\leq n,w {\text{ fritt reducerad}}.\}$

På motsvarande sätt är Dehn( n ) den minsta isoperimetriska funktionen för (∗), det vill säga Dehn( n ) är en isoperimetrisk funktion för (∗) och för alla andra isoperimetriska funktioner f ( n ) vi har

Dehn( n ) ≤ f ( n )

för varje n ≥ 0.

Tillväxttyper av funktioner

Eftersom den exakta Dehn-funktionen vanligtvis beror på presentationen, studerar man vanligtvis dess asymptotiska tillväxttyp då n tenderar till oändligheten, vilket bara beror på gruppen.

För två monoton-icke-minskande funktioner

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

man säger att f domineras av g om det finns C ≥1 så att

$f(n)\leq Cg(Cn+C)+Cn+C$

för varje heltal n ≥ 0. Säg att f ≈ g om f domineras av g och g domineras av f . Då är ≈ en ekvivalensrelation och Dehn-funktioner och isoperimetriska funktioner studeras vanligtvis fram till denna ekvivalensrelation. För alla a,b > 1 har vi alltså a ⁿ ≈ b ⁿ . På liknande sätt, om f ( n ) är ett polynom av grad d (där d ≥ 1 är ett reellt tal) med icke-negativa koefficienter, då f ( n ) ≈ n ^d . Dessutom, 1 ≈ n .

Om en finit grupppresentation tillåter en isoperimetrisk funktion f ( n ) som är ekvivalent med en linjär (respektive kvadratisk, kubisk, polynom, exponentiell, etc.) funktion i n , sägs presentationen uppfylla en linjär (respektive kvadratisk, kubisk, polynom, exponentiell, etc.) isoperimetrisk olikhet .

Grundläggande egenskaper

• Om G och H är kvasi-isometriska ändligt presenterade grupper och någon ändlig presentation av G har en isoperimetrisk funktion f ( n ) så finns det för varje ändlig presentation av H en isoperimetrisk funktion ekvivalent med f ( n ). I synnerhet gäller detta faktum för G = H , där samma grupp ges av två olika finita presentationer.
• Följaktligen, för en ändligt presenterad grupp beror tillväxttypen för dess Dehn-funktion, i den mening som anges ovan, inte av valet av en ändlig presentation för den gruppen. Mer generellt, om två ändligt presenterade grupper är kvasi-isometriska så är deras Dehn-funktioner ekvivalenta.
• För en finit presenterad grupp G som ges av en finit presentation (∗) är följande villkor likvärdiga:
  • G har en rekursiv Dehn-funktion med avseende på (∗).
  • Det finns en rekursiv isoperimetrisk funktion f ( n ) för (∗).
  • Gruppen G har lösbart ordproblem .

I synnerhet innebär detta att lösbarheten av ordet problem är en kvasi-isometriinvariant för ändligt presenterade grupper .

• Att känna till arean Area( w ) av en relation w gör det möjligt att binda, i termer av | w |, inte bara antalet konjugat av de definierande relationerna i (♠) utan även längden av de konjugerande elementen u i _. Som en konsekvens är det känt att om en finit presenterad grupp G som ges av en finit presentation (∗) har en beräkningsbar Dehn-funktion Dehn( n ), så är ordproblemet för G lösbart med icke-deterministisk tidskomplexitet Dehn( n ) och deterministisk tidskomplexitet Exp(Dehn( n )). I allmänhet finns det dock ingen rimlig gräns för Dehn-funktionen för en ändligt presenterad grupp när det gäller den deterministiska tidskomplexiteten för ordproblemet och gapet mellan de två funktionerna kan vara ganska stort.

Exempel

• För varje finit presentation av en finit grupp G har vi Dehn( n ) ≈ n .
• För den slutna orienterade ytan av släkte 2, standardpresentationen av dess grundläggande grupp

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

uppfyller Dehn( n ) ≤ n och Dehn( n ) ≈ n .

• För varje heltal k ≥ 2 har den fria abelska gruppen $\mathbb {Z} ^{k}$ Dehn( n ) ≈ n ² .
• Baumslag -Solitar-gruppen

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

har Dehn( n ) ≈ 2 ⁿ ( ser ).

• Den 3-dimensionella diskreta Heisenberggruppen

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

uppfyller en kubisk men ingen kvadratisk isoperimetrisk olikhet.

• Högdimensionella Heisenberg-grupper

$_ 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 }$ ,

där k ≥ 2, uppfyller kvadratiska isoperimetriska olikheter.

• Om G är en "Novikov-Boone-grupp", det vill säga en ändligt presenterad grupp med ett olösligt ordproblem , så växer Dehn-funktionen av G snabbare än någon rekursiv funktion .
• För Thompson-gruppen F är Dehn-funktionen kvadratisk, det vill säga ekvivalent med n ² (se ).
• Den så kallade Baumslag-Gersten-gruppen

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

har en Dehn-funktion som växer snabbare än något fast itererat torn av exponentialer. Specifikt för denna grupp

Dehn( n ) ≈ exp(exp(exp(...(exp(1))...)))

där antalet exponential är lika med den integrerade delen av log ₂ ( n ) (se ).

Kända resultat

• En finit presenterad grupp är en ordhyperbolisk grupp om och endast om dess Dehn-funktion är ekvivalent med n , det vill säga om och endast om varje finit presentation av denna grupp uppfyller en linjär isoperimetrisk olikhet.
• Isoperimetriskt gap : Om en ändligt presenterad grupp uppfyller en subkvadratisk isoperimetrisk ojämlikhet så är den ordhyperbolisk. Det finns alltså inga ändligt presenterade grupper med Dehn-funktioner ekvivalenta med n ^d med d ∈ (1,2).
• Automatiska grupper och mer allmänt kambara grupper uppfyller kvadratiska isoperimetriska ojämlikheter.
• En ändligt genererad nilpotent grupp har en Dehn-funktion ekvivalent med n ^d där d ≥ 1 och alla positiva heltal d realiseras på detta sätt. Dessutom medger varje ändligt genererad nilpotent grupp G en polynom isoperimetrisk olikhet av grad c + 1, där c är nilpotensklassen för G .
• Uppsättningen av reella tal d ≥ 1, så att det finns en ändligt presenterad grupp med Dehn-funktion ekvivalent med n ^d , är tät i intervallet $[2,\infty )$ .
• Om alla asymptotiska koner i en ändligt presenterad grupp helt enkelt är anslutna , uppfyller gruppen en polynom isoperimetrisk olikhet.
• Om en ändligt presenterad grupp uppfyller en kvadratisk isoperimetrisk olikhet, är alla asymptotiska koner i denna grupp helt enkelt sammankopplade.
• Om ( M , g ) är ett slutet Riemann-grenrör och G = π ₁ ( M ) så är Dehn-funktionen för G ekvivalent med grenrörets fyllningsareafunktion.
• Om G är en grupp som agerar korrekt diskontinuerligt och kokompakt genom isometrier på ett CAT(0)-utrymme , så uppfyller G en kvadratisk isoperimetrisk olikhet. I synnerhet gäller detta fallet där G är den fundamentala gruppen i ett sluten Riemann-grenrör med icke-positiv tvärsnittskrökning (inte nödvändigtvis konstant).
• Dehn-funktionen för SL( m , Z ) är som mest exponentiell för någon m ≥ 3. För SL(3, Z ) är denna gräns skarp och det är i så fall känt att Dehn-funktionen inte tillåter en subexponentiell övre gräns. Dehn-funktionerna för SL( m , Z ), där m > 4 är kvadratiska. Dehn-funktionen för SL(4, Z ), har antagits vara kvadratisk av Thurston.
• Kartläggningsklassgrupper av ytor av ändlig typ är automatiska och uppfyller kvadratiska isoperimetriska olikheter.
• Dehn-funktionerna för grupperna Aut( F _k ) och Out( F _k ) är exponentiella för varje k ≥ 3. Exponentiella isoperimetriska olikheter för Aut( F _k ) och Out( F _k ) när k ≥ 3 hittades av Hatcher och Vogtmann . Dessa gränser är skarpa, och grupperna Aut( F _k ) och Out( F _k ) uppfyller inte subexponentiella isoperimetriska olikheter, som visas för k = 3 av Bridson och Vogtmann, och för k ≥ 4 av Handel och Mosher.
• För varje automorfism φ av en ändligt genererad fri grupp F _{k tillfredsställer} avbildningstorusgruppen $F_{k}\rtimes _{\phi }\mathbb {Z}$ av φ en kvadratisk isoperimetrisk olikhet.
• De flesta "rimliga" beräkningsbara funktioner som är ≥ n ⁴ kan realiseras, upp till ekvivalens, som Dehn-funktioner i ändligt presenterade grupper. I synnerhet om f ( n ) ≥ n ⁴ är en superadditiv funktion vars binära representation kan beräknas i tiden $O\left({\sqrt[{4}]{f(n) }}\right)$ av en Turing-maskin är f ( n ) ekvivalent med Dehn-funktionen för en ändligt presenterad grupp.
• Även om man inte på ett rimligt sätt kan binda en grupps Dehn-funktion i termer av komplexiteten i dess ordproblem, fick Birget, Olʹshanskii, Rips och Sapir följande resultat, vilket ger en långtgående generalisering av Higmans inbäddningsteorem : Ordet problem med en finitely genererad grupp är avgörbar i icke-deterministisk polynomtid om och endast om denna grupp kan bäddas in i en ändligt presenterad grupp med en polynomisk isoperimetrisk funktion. Dessutom kan varje grupp med ordet problemlösbart i tiden T( n ) bäddas in i en grupp med isoperimetrisk funktion ekvivalent med n ² T( n ² ) ⁴ .

Generaliseringar

• Det finns flera följeslagare som är nära besläktade med begreppet en isoperimetrisk funktion. Således begränsar en isodiametrisk funktion den minsta diametern (med avseende på den förenklade metriken där varje kant har längden ett) av ett van Kampen-diagram för en viss relation w i termer av längden av w . En fyllningslängdfunktion den minsta fyllningslängden av ett van Kampen-diagram för en viss relation w i termer av längden av w . Här fyllningslängden för ett diagram minimum, över alla kombinatoriska nollhomotoper i diagrammet, av den maximala längden av mellanliggande slingor som avgränsar mellanliggande diagram längs sådana nollhomotoper. Utfyllnadslängdfunktionen är nära relaterad till den icke-deterministiska rymdkomplexiteten hos ordproblemet för ändligt presenterade grupper. Det finns flera allmänna ojämlikheter som förbinder Dehn-funktionen, den optimala isodiametriska funktionen och den optimala fyllningslängdfunktionen, men det exakta förhållandet mellan dem är ännu inte förstått.
• Det finns också högre dimensionella generaliseringar av isoperimetriska och Dehn-funktioner. För k ≥ 1 begränsar den k -dimensionella isoperimetriska funktionen för en grupp den minimala kombinatoriska volymen av ( k + 1)-dimensionella kulfyllningar av k -sfärer avbildade till ett k -anslutet utrymme på vilket gruppen verkar korrekt och samkompakt; bunden ges som en funktion av k -sfärens kombinatoriska volym. Standarduppfattningen om en isoperimetrisk funktion motsvarar fallet k = 1. Till skillnad från fallet med standard Dehn-funktioner är lite känt om möjliga tillväxttyper av k -dimensionella isoperimetriska funktioner för ändligt presenterade grupper för k ≥ 2.
• I sin monografi Asymptotiska invarianter av oändliga grupper föreslog Gromov en probabilistisk eller genomsnittlig version av Dehn-funktionen och föreslog att för många gruppers genomsnittliga Dehn-funktioner borde ha strikt långsammare asymptotik än Dehn-standardfunktionerna. Mer exakta behandlingar av begreppet en genomsnittlig Dehn-funktion eller genomsnittlig Dehn-funktion gavs senare av andra forskare som också bevisade att genomsnittliga Dehn-funktioner verkligen är subasymptotiska till standard Dehn-funktioner i ett antal fall (som nilpotenta och abelska grupper).

• En relativ version av begreppet en isoperimetrisk funktion spelar en central roll i Osin' inställning till relativt hyperboliska grupper .
• Grigorchuk och Ivanov utforskade flera naturliga generaliseringar av Dehns funktion för grupppresentationer på ändligt många generatorer men med oändligt många definierande relationer.

Se även

• van Kampen diagram
• Ordhyperbolisk grupp
• Automatisk grupp
• Liten avbokningsteori
• Geometrisk gruppteori

Vidare läsning

•   Noel Brady, Tim Riley och Hamish Short. Ordets geometri för ändligt genererade grupper. Advanced Courses in Mathematics CRM Barcelona, ​​Birkhäuser, Basel, 2007. ISBN 3-7643-7949-9 .
•   Martin R. Bridson. Ordets problems geometri. Invitations to geometri and topology, s. 29–91, Oxford Graduate Texts in Mathematics, 7, Oxford University Press , Oxford, 2002. ISBN 0-19-850772-0 .

externa länkar

• Den isoperimetriska olikheten för SL(n,Z). En workshop i september 2008 vid American Institute of Mathematics .
• PDF av Bridsons artikel The geometry of the word problem.