Random equations in free groups

DOI10.1515/gcc.2011.010zbMath1278.20088OpenAlexW1998474638MaRDI QIDQ2884689

Robert H. Gilman, Alexei G. Myasnikov, Vitaliĭ Roman'kov

Publication date: 18 May 2012

Published in: Groups – Complexity – Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc.2011.010

zbMATH Keywords

free groupsasymptotic densitiesendomorphism problemautomorphic orbitsfree Abelian groupsrandom equationssubsets of intermediate density

Mathematics Subject Classification ID

Asymptotic properties of groups (20F69) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Probabilistic methods in group theory (20P05) Algebraic geometry over groups; equations over groups (20F70)

Related Items

On the asymptotics of visible elements and homogeneous equations in surface groups., Random systems of equations in free abelian groups., Random equations in nilpotent groups., RANDOM EQUATIONS OVER FREE SEMILATTICES

Cites Work

• Average-case complexity and decision problems in group theory.
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• A random tunnel number one 3-manifold does not fiber over the circle
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Random subgroups of Thompson's group \(F\).
• Cogrowth of groups and simple random walks
• Algebraic geometry over groups. I: Algebraic sets and ideal theory
• The class of groups all of whose subgroups with lesser number of generators are free is generic
• Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz
• Generic-case complexity, decision problems in group theory, and random walks.
• Random walk in random groups.
• Automorphic orbits in free groups.
• The space of finitely generated groups
• Cogrowth and spectral gap of generic groups.
• Algebraic geometry over groups. II: Logical foundations
• Counting primitive elements in free groups
• Sharp phase transition theorems for hyperbolicity of random groups.
• Statistical properties of finitely presented groups
• Implicit function theorem over free groups.
• Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphisms
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• Delzant's \(T\)-invariant, Kolmogorov complexity and one-relator groups.
• The probability of generating a finite classical group
• Random van Kampen diagrams and algorithmic problems in groups
• The Asymptotic Density of Some k-Dimensional Sets
• Commutators in Free Products
• Generic complexity of undecidable problems
• The mean Dehn functions of abelian groups
• Equidistribution of geodesics on homology classes and analogues for free groups
• Asymptotic growth of averaged Dehn functions for nilpotent groups
• Generic Subgroups of Group Amalgams
• Solving one-variable equations in free groups
• Equations in Free Groups
• Groups With Parametric Exponents
• ALMOST EVERY GROUP IS HYPERBOLIC
• Generic properties of finitely presented groups and howson's theorem
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• A property of subgroups of infinite index in a free group
• Equations in free groups with one variable. I
• POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
• One-Variable Equations in Free Groups
• On the Substitution Problem for Free Groups
• Local limit theorems for free groups