THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY

DOI10.1142/S0218196704001980zbMATH Open1088.20016arXivmath/0204292OpenAlexW2071283394MaRDI QIDQ4658702FDOQ4658702

Authors: J.-C. Birget 

Publication date: 18 March 2005

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Abstract: We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We define the groups as partial transformation groups and we give a faithful representation in the Cuntz C*-algebra. For the finitely presented simple group T_fin (also known as V) we show that the word-length and the table size satisfy an n log n relation, just like the symmetric groups. We show that the word problem of T_fin belongs to the parallel complexity class AC^1 (a subclass of plynomial time). We show that the generalized word problem of T_fin is undecidable. We study the distortion functions of T_fin and we show that T_fin contains all finite direct products of finitely generated free groups as subgroups with linear distortion. As a consequence, up to polynomial equivalence of functions, the following three sets are the same: the set of distortions of T_fin, the set of all Dehn functions of finitely presented groups, and the set of time complexity functions of nondeterministic Turing machines.

Full work available at URL: https://arxiv.org/abs/math/0204292

Recommendations

• Introductory notes on Richard Thompson's groups
• Presentations of higher dimensional Thompson groups.
• Monoid generalizations of the Richard Thompson groups.
• Free products in R. Thompson's group \(V\).
• Higher dimensional Thompson groups.

zbMATH Keywords

Dehn functionsword problemThompson groupsdistortionsCuntz algebrascomplexitiesfinitely presented simple groupsinfinite simple groupsword-lengths

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Selfadjoint operator algebras ((C^*)-algebras, von Neumann ((W^*)-) algebras, etc.) (46L99) Simple groups (20E32)

Cites Work

• Simple \(C^*\)-algebras generated by isometries
• Title not available (Why is that?)
• Word Problems Solvable in Logspace
• Title not available (Why is that?)
• Constructing inverse semigroups from category actions
• Title not available (Why is that?)
• Constructing finitely presented simple groups that contain Grigorchuk groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Isoperimetric and isodiametric functions of groups
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• A finitely presented simple group with unsolvable conjugacy problem
• An application of polycyclic monoids to rings
• The complexity of Grigorchuk groups with application to cryptography
• A construction which can be used to produce finitely presented infinite simple groups
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS

Cited In (39)

• UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS
• Orthogonal Completions of the Polycyclic Monoids
• Recent developments around partial actions
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• Higher dimensional generalizations of the Thompson groups
• Irreducible Pythagorean representations of R. Thompson's groups and of the Cuntz algebra
• The Polycyclic MonoidsP_nand the Thompson GroupsV_n,1
• Generalizations of free monoids
• Polynomial-time right-ideal morphisms and congruences
• Introductory notes on Richard Thompson's groups
• A CORRESPONDENCE BETWEEN BALANCED VARIETIES AND INVERSE MONOIDS
• New embeddings between the Higman-Thompson groups
• The universal Boolean inverse semigroup presented by the abstract Cuntz-Krieger relations
• Pseudogroups and their étale groupoids.
• Subgroups of the group of homeomorphisms of the Cantor space and a duality between a class of inverse monoids and a class of Hausdorff étale groupoids
• A dynamical definition of f.g. virtually free groups
• Conjugator length in Thompson's groups
• Partial category actions on sets and topological spaces
• The word problem of the Brin-Thompson group is \textsf{coNP}-complete
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Compression techniques in group theory
• The Polycyclic Inverse Monoids and the Thompson Groups Revisited
• Non-commutative Stone duality: inverse semigroups, topological groupoids and \(C^*\)-algebras
• Bernoulli measure on strings, and Thompson-Higman monoids.
• Monoids that map onto the Thompson-Higman groups
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.
• The Booleanization of an inverse semigroup
• The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• Divergence functions of Thompson groups
• Compact presentability of tree almost automorphism groups
• Representations of Higman-Thompson groups from Cuntz algebras
• Metric spaces with complexity of the smallest infinite ordinal number
• Semigroups and one-way functions
• The action of the Thompson group \(F\) on infinite trees
• Infinitely generated semigroups and polynomial complexity
• Embeddings into Thompson's groups from quasi-median geometry
• Complexity among the finitely generated subgroups of Thompson's group

This page was built for publication: THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4658702)