Random nilpotent groups, polycyclic presentations, and Diophantine problems

DOI10.1515/GCC-2017-0007MaRDI QIDQ1676247zbMATH OpenOpenAlexFDO

Authors Albert Garreta, Denis Ovchinnikov, Alexei Myasnikov

Publication date 6 November 2017

Published in Groups - Complexity - Cryptology (Search for Journal in Brave)

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

zbMATH Keywords

Diophantine problemnilpotent groupspolycyclic groupsrandom groups

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Nilpotent groups (20F18) Probabilistic methods in group theory (20P05) Stochastic processes (60G99)

Abstract: We introduce a model of random f.g., torsion-free, $2$-step nilpotent groups (in short, $a{u}_2$-groups). To do so, we show that these are precisely the groups that admit a presentation of the form $labeltau2pre{s}_{0}langleA,Cmid[a_i,a_j]=pro{d}_{t}scriptstyle{c}_t^{scriptscriptstylelambd{a}_{t,i,j}}(i<j),[A,C]=[C,C]=1angle,$ where $A=a_1,dots,a_n$, and $C=c_1,dots,c_m$. Hence, one may select a random $a{u}_2$-group $G$ by fixing $A$ and $C$, and then randomly choosing exponents $lambd{a}_{t,i,j}$ with $|lambd{a}_{t,i,j}|leqell$, for some $ell$. We prove that, if $mgeqn-1geq1$, then the following holds asymptotically almost surely, as $elloinfty$: The ring of integers $mathbbZ$ is e-definable in $G$, systems of equations over $mathbbZ$ are reducible to systems over $G$ (and hence they are undecidable), the maximal ring of scalars of $G$ is $mathbbZ$, $G$ is indecomposable as a direct product of non-abelian factors, and $Z(G)=langleCangle$. If, additionally, $mleqn(n-1)/2$, then $G$ is regular (i.e. $Z(G)leqitIs(G^{\prime })$). This is not the case if $m>n(n-1)/2$. In the last section of the paper we introduce similar models of random polycyclic groups and random f.g. nilpotent groups of any nilpotency step, possibly with torsion. We quickly see, however, that the latter yields finite groups a.a.s.

Recommendations

• Full rank presentations and nilpotent groups: structure, Diophantine problem, and genericity
• A matrix model for random nilpotent groups
• Random nilpotent groups. I
• Diophantine questions in the class of finitely generated nilpotent groups
• Metabelian groups: full-rank presentations, randomness and Diophantine problems

Cites work

• A matrix model for random nilpotent groups
• Equations in nilpotent groups.
• scientific article; zbMATH DE number 5012619 (Why is no real title available?)
• scientific article; zbMATH DE number 3815938 (Why is no real title available?)
• scientific article; zbMATH DE number 3652594 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Random nilpotent groups. I
• Random walk in random groups.

Cited in

(20)

• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Deciding isomorphy using Dehn fillings, the splitting case
• Random nilpotent groups of maximal step
• Full rank presentations and nilpotent groups: structure, Diophantine problem, and genericity
• \(C^\ast\)-stability of discrete groups
• Two general schemes of algebraic cryptography
• A proof of van der Waerden's conjecture on random Galois groups of polynomials
• Random equations in nilpotent groups.
• Random nilpotent groups. I
• Low-complexity computations for nilpotent subgroup problems
• Diophantine problems in solvable groups
• Parallel complexity for nilpotent groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• The Diophantine problem in some metabelian groups
• A matrix model for random nilpotent groups
• Post's correspondence problem: from computer science to algebra
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• Quadratic Diophantine equations, the Heisenberg group and formal languages
• The Diophantine problem in Thompson's group F
• Metabelian groups: full-rank presentations, randomness and Diophantine problems

This page was built for publication: Random nilpotent groups, polycyclic presentations, and Diophantine problems

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