Função Dehn - Dehn function

Na disciplina matemática da teoria geométrica dos grupos , uma função de Dehn , nomeada em homenagem a Max Dehn , é uma função ótima associada a uma apresentação de grupo finito que delimita a área de uma relação naquele grupo (que é uma palavra livremente reduzida nos geradores que representam o elemento de identidade do grupo) em termos da duração dessa relação (ver pp. 79–80 em). O tipo de crescimento da função de Dehn é uma quase isometria invariante de um grupo finitamente apresentado . A função Dehn de um grupo finitamente apresentado também está intimamente ligada à complexidade algorítmica não determinística do problema de palavras em grupos. Em particular, um grupo finitamente apresentado tem problemas de palavras solucionáveis se e somente se a função de Dehn para uma apresentação finita desse grupo for recursiva (ver Teorema 2.1 em). A noção de uma função de Dehn é motivada por problemas isoperimétricos em geometria, como a clássica desigualdade isoperimétrica para o plano euclidiano e, de forma mais geral, a noção de uma função de área de preenchimento que estima a área de uma superfície mínima em uma variedade Riemanniana em termos do comprimento da curva limite dessa superfície.

História

A ideia de uma função isoperimétrica para um grupo finitamente apresentado remonta ao trabalho de Max Dehn na década de 1910. Dehn provou que o problema da palavra para a apresentação padrão do grupo fundamental de uma superfície orientada fechada do gênero pelo menos dois pode ser resolvido pelo que agora é chamado de algoritmo de Dehn . Uma conseqüência direta desse fato é que para esta apresentação a função de Dehn satisfaz Dehn ( n ) ≤ n . Este resultado foi estendido na década de 1960 por Martin Greendlinger para grupos finitamente apresentados que satisfazem a condição de cancelamento pequeno C '(1/6) . A noção formal de uma função isoperimétrica e uma função de Dehn como é usada hoje apareceu no final dos anos 1980 - início dos anos 1990, juntamente com a introdução e o desenvolvimento da teoria dos grupos hiperbólicos de palavras . Em sua monografia de 1987 "Grupos hiperbólicos" Gromov provou que um grupo finitamente apresentado é palavra-hiperbólico se e somente se satisfizer uma desigualdade isoperimétrica linear, isto é, se e somente se a função de Dehn deste grupo for equivalente à função f ( n ) = n . A prova de Gromov foi em grande parte informada por analogia com funções de área de preenchimento para variedades Riemannianas compactas , onde a área de uma superfície mínima que delimita uma curva fechada homotópica nula é limitada em termos do comprimento dessa curva.

O estudo das funções isoperimétricas e de Dehn rapidamente se desenvolveu em um tema principal separado na teoria dos grupos geométricos , especialmente porque os tipos de crescimento dessas funções são invariantes quase isométricos naturais de grupos finitamente apresentados. Um dos principais resultados no assunto foi obtido por Sapir, Birget e Rips que mostraram que a maioria das funções de complexidade de tempo "razoável" das máquinas de Turing podem ser realizadas, até a equivalência natural, como funções de Dehn de grupos finitamente apresentados.

Definição formal

Deixar

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

ser uma apresentação de grupo finito onde o X é um alfabeto finito e onde R  ⊆  F ( X ) é um conjunto finito de palavras ciclicamente reduzidas.

Área de uma relação

Deixe w  ∈  F ( X ) ser uma relação em L , isto é, uma palavra livremente reduzida de tal modo que w  = 1 em L . Observe que isso é equivalente a dizer que w pertence ao fechamento normal de R em F ( X ), ou seja, existe uma representação de w como

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

onde m  ≥ 0 e onde r _i  ∈  R ^{± 1} para i  = 1, ...,  m .

Para w  ∈  F ( X ) satisfazendo w  = 1 em G , a área de w em relação a (∗), denotada Área ( w ), é o menor m  ≥ 0 tal que existe uma representação (♠) para w como o produto em F ( X ) de m conjugados de elementos de R ^{± 1} .

Uma palavra livremente reduzida w  ∈  F ( X ) satisfaz w  = 1 em G se e somente se o laço rotulado por w no complexo de apresentação para G correspondente a (∗) é nulo-homotópico . Esse fato pode ser usado para mostrar que a Área ( w ) é o menor número de 2 células em um diagrama de van Kampen sobre (∗) com o ciclo de fronteira marcado por w .

Função isoperimétrica

Uma função isoperimétrica para uma apresentação finita (∗) é uma função monótona não decrescente

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

tal que sempre que w  ∈  F ( X ) é uma palavra livremente reduzida satisfazendo w  = 1 em G , então

Área ( w ) ≤  f (| w |),

onde | w | é o comprimento da palavra w .

Função Dehn

Então a função Dehn de uma apresentação finita (∗) é definida como

${\ displaystyle {\ rm {Dehn}} (n) = \ max \ {{\ rm {Area}} (w): w = 1 {\ text {in}} G, | w | \ leq n, w { \ text {reduzido livremente}}. \}}$

Equivalentemente, Dehn ( n ) é a menor função isoperimétrica para (∗), ou seja, Dehn ( n ) é uma função isoperimétrica para (∗) e para qualquer outra função isoperimétrica f ( n ) que temos

Dehn ( n ) ≤  f ( n )

para cada n  ≥ 0.

Tipos de funções de crescimento

Como as funções de Dehn são geralmente difíceis de calcular com precisão, geralmente estudamos seus tipos de crescimento assintótico, pois n tende ao infinito.

Para duas funções monótonas e não decrescentes

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

diz-se que f é dominado por g se existe C  ≥1 tal que

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

para cada inteiro n  ≥ 0. Say que f  ≈  g se f é dominada por g e g é dominado por f . Então ≈ é uma relação de equivalência e funções de Dehn e funções isoperimétricas são geralmente estudadas até esta relação de equivalência. Assim, para qualquer a, b> 1 , temos a ⁿ  ≈  b ⁿ . Da mesma forma, se f ( n ) é um polinômio de grau d (onde d  ≥ 1 é um número real) com coeficientes não negativos, então f ( n ) ≈  n ^d . Além disso, 1 ≈  n .

Se uma apresentação de grupo finito admite uma função isoperimétrica f ( n ) que é equivalente a uma função linear (respectivamente, quadrática, cúbica, polinomial, exponencial, etc.) em n , diz-se que a apresentação satisfaz uma função linear (respectivamente, quadrática, cúbica, polinomial, exponencial, etc.) desigualdade isoperimétrica .

Propriedades básicas

• Se G e H são grupos quase isométricos finitamente apresentados e alguma apresentação finita de G tem uma função isoperimétrica f ( n ), então para qualquer apresentação finita de H existe uma função isoperimétrica equivalente af ( n ). Em particular, esse fato é válido para G  =  H , onde o mesmo grupo é dado por duas apresentações finitas diferentes.
• Consequentemente, para um grupo finitamente apresentado, o tipo de crescimento de sua função Dehn, no sentido da definição acima, não depende da escolha de uma apresentação finita para aquele grupo. De maneira mais geral, se dois grupos finitamente apresentados são quase isométricos, então suas funções de Dehn são equivalentes.
• Para um grupo G finitamente apresentado dado por uma apresentação finita (∗), as seguintes condições são equivalentes:
  • G tem uma função de Dehn recursiva em relação a (∗).
  • Existe uma função isoperimétrica recursiva f ( n ) para (∗).
  • O grupo G tem problema de palavra solucionável .

Em particular, isso implica que a capacidade de resolução do problema da palavra é uma quase isometria invariante para grupos apresentados finitamente .

• Conhecer a área Área ( w ) de uma relação w permite limitar, em termos de | w |, não apenas o número de conjugados das relações definidoras em (♠), mas também os comprimentos dos elementos conjugantes u _i . Como consequência, sabe-se que se um grupo G finitamente apresentado dado por uma apresentação finita (∗) tem função Dehn computável Dehn ( n ), então o problema de palavra para G é solucionável com complexidade de tempo não determinística Dehn ( n ) e complexidade de tempo determinística Exp (Dehn ( n )). No entanto, em geral não existe um limite razoável na função de Dehn de um grupo finitamente apresentado em termos da complexidade determinística do tempo do problema da palavra e a lacuna entre as duas funções pode ser muito grande.

Exemplos

• Para qualquer apresentação finita de um grupo finito G , temos Dehn ( n ) ≈  n .
• Para a superfície orientada fechada do gênero 2, a apresentação padrão de seu grupo fundamental

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

satisfaz Dehn ( n ) ≤  n e Dehn ( n ) ≈  n .

• Para cada inteiro k  ≥ 2, o grupo abeliano livre tem Dehn ( n ) ≈  n ² . ${\ displaystyle \ mathbb {Z} ^ {k}}$
• O grupo Baumslag-Solitar

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

tem Dehn ( n ) ≈ 2 ⁿ (consulte).

• O grupo de Heisenberg discreto tridimensional

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

satisfaz uma desigualdade isoperimétrica cúbica, mas não quadrática.

• Grupos de Heisenberg de dimensão superior

${\ 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, \ pontos, k, [a_ {i}, b_ {j}] = 1, i \ neq j \ rangle }$ ,

onde k  ≥ 2, satisfaz as desigualdades isoperimétricas quadráticas.

• Se G é um "grupo Novikov-Boone", isto é, um grupo finitamente apresentado com problema de palavras insolúvel , então a função Dehn de G cresce mais rápido do que qualquer função recursiva .
• Para o grupo F de Thompson, a função Dehn é quadrática, ou seja, equivalente an ² (ver).
• O chamado grupo Baumslag-Gersten

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

tem uma função Dehn crescendo mais rápido do que qualquer torre iterada fixa de exponenciais. Especificamente, para este grupo

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

onde o número de exponenciais é igual à parte integral de log ₂ ( n ) (consulte).

Resultados conhecidos

• Um grupo finitamente apresentado é um grupo palavra-hiperbólico se e somente se sua função Dehn for equivalente an , isto é, se e somente se toda apresentação finita desse grupo satisfizer uma desigualdade isoperimétrica linear.
• Lacuna isoperimétrica : se um grupo finitamente apresentado satisfaz uma desigualdade isoperimétrica subquadrática, é uma palavra hiperbólica. Assim, não há grupos são apresentados um número finito com funções equivalentes Dehn a n ^d com d  ∈ (1,2).
• Os grupos automáticos e, mais geralmente, os grupos combináveis satisfazem as desigualdades isoperimétricas quadráticas.
• Um número finito gerado grupo nilpotentes tem uma função Dehn equivalente a n ^d em que d  ≥ 1 e todos os inteiros positivos d são realizados desta maneira. Além disso, cada grupo nilpotentes finitos gerado L admite uma desigualdade isoperimétrica polinomial de grau c  + 1, onde c é a classe de nilpotency L .
• O conjunto de números reais de d  ≥ 1, tal que existe uma quantidade finita grupo apresentados com Dehn função equivalente a n ^d , é denso no intervalo . ${\ displaystyle [2, \ infty)}$
• Se todos os cones assintóticos de um grupo finitamente apresentado são simplesmente conectados , então o grupo satisfaz uma desigualdade isoperimétrica polinomial.
• Se um grupo finitamente apresentado satisfaz uma desigualdade isoperimétrica quadrática, então todos os cones assintóticos deste grupo são simplesmente conectados.
• Se ( M , g ) é uma variedade Riemanniana fechada e G  =  π ₁ ( M ), então a função Dehn de G é equivalente à função de área de enchimento da variedade.
• Se G é um grupo agindo de forma descontinuada e co-compactamente adequada por isometrias em um espaço CAT (0) , então G satisfaz uma desigualdade isoperimétrica quadrática. Em particular, isso se aplica ao caso em que G é o grupo fundamental de uma variedade Riemanniana fechada de curvatura seccional não positiva (não necessariamente constante).
• A função Dehn de SL ( m , Z ) é no máximo exponencial para qualquer m  ≥ 3. Para SL (3, Z ) este limite é agudo e é conhecido nesse caso que a função Dehn não admite um limite superior subexponencial. As funções de Dehn para SL ( m , Z ), onde m  > 4 são quadráticos. A função Dehn de SL (4, Z ), foi conjecturada como quadrática, por Thurston.
• Os grupos de classes de mapeamento de superfícies de tipo finito são automáticos e satisfazem as desigualdades isoperimétricas quadráticas.
• As funções de Dehn para os grupos Aut ( F _k ) e Out ( F _k ) são exponenciais para todo k ≥ 3. Desigualdades isoperimétricas exponenciais para Aut ( F _k ) e Out ( F _k ) quando k ≥ 3 foram encontradas por Hatcher e Vogtmann . Esses limites são agudos, e os grupos Aut ( F _k ) e Out ( F _k ) não satisfazem as desigualdades isoperimétricas subexponenciais, como mostrado para k  = 3 por Bridson e Vogtmann, e para k ≥ 4 por Handel e Mosher.
• Para cada automorfismo φ de um grupo livre finitamente gerado F _k, o grupo de toro de mapeamento de φ satisfaz uma desigualdade isoperimétrica quadrática. ${\ displaystyle F_ {k} \ rtimes _ {\ phi} \ mathbb {Z}}$
• A maioria das funções computáveis ​​"razoáveis" que são ≥ n ⁴ podem ser realizadas, até a equivalência, como funções de Dehn de grupos finitamente apresentados. Em particular, se f ( n ) ≥  n ⁴ é uma função superaditiva cuja representação binária é computável no tempo por uma máquina de Turing, então f ( n ) é equivalente à função de Dehn de um grupo finitamente apresentado. ${\ displaystyle O \ left ({\ sqrt [{4}] {f (n)}} \ right)}$
• Embora não se possa limitar razoavelmente a função de Dehn de um grupo em termos da complexidade de seu problema de palavras, Birget, Olʹshanskii, Rips e Sapir obtiveram o seguinte resultado, fornecendo uma generalização de longo alcance do teorema de incorporação de Higman : O problema da palavra de um finitamente grupo gerado é decidível em tempo polinomial não determinístico se e somente se este grupo pode ser embutido em um grupo finitamente apresentado com uma função isoperimétrica polinomial. Além disso, todo grupo com a palavra problema solucionável no tempo T ( n ) pode ser incorporado em um grupo com função isoperimétrica equivalente a n ² T ( n ² ) ⁴ .

Generalizações

• Existem várias noções associadas intimamente relacionadas à noção de uma função isoperimétrica. Assim, uma função isodiamétrica limita o menor diâmetro (em relação à métrica simplicial onde cada aresta tem comprimento um) de um diagrama de van Kampen para uma relação particular w em termos do comprimento de w . Uma função de comprimento de enchimento é o menor comprimento de enchimento de um diagrama de van Kampen para uma relação particular w em termos do comprimento de w . Aqui, o comprimento de preenchimento de um diagrama é o mínimo, sobre todas as homotopias nulas combinatórias do diagrama, do comprimento máximo de loops intermediários que delimitam os diagramas intermediários ao longo de tais homotopias nulas. A função de comprimento de preenchimento está intimamente relacionada à complexidade não determinística do espaço do problema de palavras para grupos finitamente apresentados. Existem várias desigualdades gerais conectando a função de Dehn, a função isodiamétrica ótima e a função de comprimento de enchimento ideal, mas a relação precisa entre elas ainda não é compreendida.
• Existem também generalizações dimensionais superiores de funções isoperimétricas e de Dehn. Para k  ≥ 1, a função isoperimétrica k -dimensional de um grupo limita o volume combinatório mínimo de ( k  + 1) -dimensional preenchimento de bolas de k -esferas mapeadas em um espaço k- conectado no qual o grupo atua de forma adequada e co-compacta; o limite é dado em função do volume combinatório da esfera k . A noção padrão de uma função isoperimétrica corresponde ao caso k  = 1. Ao contrário do caso das funções de Dehn padrão, pouco se sabe sobre os possíveis tipos de crescimento de funções isoperimétricas k -dimensionais de grupos finitamente apresentados para k  ≥ 2.
• Em sua monografia, invariantes assintóticos de grupos infinitos, Gromov propôs uma versão probabilística ou média da função de Dehn e sugeriu que para muitos grupos as funções de Dehn médias deveriam ter assintóticas estritamente mais lentas do que as funções de Dehn padrão. Tratamentos mais precisos da noção de uma função de Dehn média ou função de Dehn média foram dados posteriormente por outros pesquisadores que também provaram que de fato as funções de Dehn médias são subassintóticas às funções de Dehn padrão em vários casos (como grupos nilpotentes e abelianos).

• Uma versão relativa da noção de uma função isoperimétrica desempenha um papel central na abordagem de Osin para grupos relativamente hiperbólicos .
• Grigorchuk e Ivanov exploraram várias generalizações naturais da função de Dehn para apresentações de grupo em geradores finitos, mas com um número infinito de relações definidoras.

Veja também

• diagrama de van Kampen
• Grupo palavra-hiperbólico
• Grupo automático
• Teoria de pequeno cancelamento
• Teoria geométrica do grupo

Notas

Leitura adicional

• Noel Brady, Tim Riley e Hamish Short. A geometria do problema da palavra para grupos finitamente gerados. Advanced Courses in Mathematics CRM Barcelona, ​​Birkhäuser, Basel, 2007. ISBN   3-7643-7949-9 .
• Martin R. Bridson. A geometria do problema da palavra. Invitations to geometry and topology, pp. 29-91, Oxford Graduate Texts in Mathematics, 7, Oxford University Press , Oxford, 2002. ISBN   0-19-850772-0 .

links externos

• A Desigualdade Isoperimétrica para SL (n, Z). Um workshop de setembro de 2008 no American Institute of Mathematics .
• PDF do artigo de Bridson A geometria do problema da palavra.