Аннотация:
Доказано, что всякая вычислимая функция G→N={0,1,…} на группе G (с некоторыми необходимыми ограничениями) может быть с точностью до эквивалентности реализована как функция длины элементов
посредством вложения группы G в подходящую конечно-определенную
группу. Например, длина степени gn элемента g
конечно-определенной группы может расти, как nθ, для любого
вычислимого числа θ∈(0,1]. Тем самым дается ответ на вопрос М. Громова.
Основным инструментом является доказанный в статье усиленный вариант
вложения Хигмэна, при котором сохраняются длины элементов.
Библиография: 10 названий.
Birget, JC, “One-way permutations, computational asymmetry and distortion”, Journal of Algebra, 320:11 (2008), 4030
Sean Cleary, “Distortion of wreath products in some finitely presented groups”, Pacific J Math, 228:1 (2006), 53
Birget, JC, “Circuits, the groups of Richard Thompson, and coNP-completeness”, International Journal of Algebra and Computation, 16:1 (2006), 35
Olshanskii, AY, “Subgroups of finitely presented groups with solvable conjugacy problem”, International Journal of Algebra and Computation, 15:5–6 (2005), 1075
Birget, JC, “The groups of Richard Thompson and complexity”, International Journal of Algebra and Computation, 14:5–6 (2004), 569
Ol'Shanskii, AY, “The conjugacy problem and Higman embeddings - Introduction”, Memoirs of the American Mathematical Society, 170:804 (2004), 1