Random nilpotent groups, polycyclic presentations, and Diophantine problems. Garreta, A., Miasnikov, A., & Ovchinnikov, D. Groups Complexity Cryptology, 9(2):99–115, November, 2017. Publisher: De Gruyter Section: Groups Complexity Cryptology![Random nilpotent groups, polycyclic presentations, and Diophantine problems [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex We introduce a model of random finitely generated, torsion-free, 2-step nilpotent groups (in short, τ2\\textbackslashtau_\2\\-groups). To do so, we show that these are precisely the groups with presentation of the form 〈A,C∣[ai,aj]=∏t=1mctλt,i,j(1≤i<j≤n),[A,C]=[C,C]=1〉\\textbackslashlangle A,C\textbackslashmid[a_\i\,a_\j\]=\textbackslashprod_\t=1\\textasciicircum\m\c_\t\\textasciicircum\\textbackslashlambda_\t,i,j\\(1\textbackslashleq i<j% \textbackslashleq n),\textbackslash,[A,C]=[C,C]=1\textbackslashrangle\, where A=\a1,…,an\\A=\textbackslash\a_\1\,\textbackslashdots,a_\n\\textbackslash\\ and C=\c1,…,cm\\C=\textbackslash\c_\1\,\textbackslashdots,c_\m\\textbackslash\\. Hence, a random G can be selected by fixing A and C , and then randomly choosing integers λt,i,j\\textbackslashlambda_\t,i,j\\, with \textbarλt,i,j\textbar≤ℓ\\textbar\textbackslashlambda_\t,i,j\\textbar\textbackslashleq\textbackslashell\ for some ℓ\\textbackslashell\. We prove that if m≥n-1≥1\m\textbackslashgeq n-1\textbackslashgeq 1\, then the following hold asymptotically almost surely as ℓ→∞\\textbackslashell\textbackslashto\textbackslashinfty\: the ring ℤ\\textbackslashmathbb\Z\\ is e-definable in G , the Diophantine problem over G is undecidable, the maximal ring of scalars of G is ℤ\\textbackslashmathbb\Z\\, G is indecomposable as a direct product of non-abelian groups, and Z(G)=〈C〉\Z(G)=\textbackslashlangle C\textbackslashrangle\. We further study when Z(G)≤Is(G′)\Z(G)\textbackslashleq\textbackslashoperatorname\Is\(G\textasciicircum\\textbackslashprime\)\. Finally, 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.
@article{garreta_random_2017,
title = {Random nilpotent groups, polycyclic presentations, and {Diophantine} problems},
volume = {9},
issn = {1869-6104},
url = {https://www.degruyter.com/document/doi/10.1515/gcc-2017-0007/html},
doi = {10.1515/gcc-2017-0007},
abstract = {We introduce a model of random finitely generated, torsion-free, 2-step nilpotent groups (in short, τ2\{{\textbackslash}tau\_\{2\}\}-groups). To do so, we show that these are precisely the groups with presentation of the form 〈A,C∣[ai,aj]=∏t=1mctλt,i,j(1≤i\<j≤n),[A,C]=[C,C]=1〉\{{\textbackslash}langle A,C{\textbackslash}mid[a\_\{i\},a\_\{j\}]={\textbackslash}prod\_\{t=1\}{\textasciicircum}\{m\}c\_\{t\}{\textasciicircum}\{{\textbackslash}lambda\_\{t,i,j\}\}(1{\textbackslash}leq i\<j\% {\textbackslash}leq n),{\textbackslash},[A,C]=[C,C]=1{\textbackslash}rangle\}, where A=\{a1,…,an\}\{A={\textbackslash}\{a\_\{1\},{\textbackslash}dots,a\_\{n\}{\textbackslash}\}\} and C=\{c1,…,cm\}\{C={\textbackslash}\{c\_\{1\},{\textbackslash}dots,c\_\{m\}{\textbackslash}\}\}. Hence, a random G can be selected by fixing A and C , and then randomly choosing integers λt,i,j\{{\textbackslash}lambda\_\{t,i,j\}\}, with {\textbar}λt,i,j{\textbar}≤ℓ\{{\textbar}{\textbackslash}lambda\_\{t,i,j\}{\textbar}{\textbackslash}leq{\textbackslash}ell\} for some ℓ\{{\textbackslash}ell\}. We prove that if m≥n-1≥1\{m{\textbackslash}geq n-1{\textbackslash}geq 1\}, then the following hold asymptotically almost surely as ℓ→∞\{{\textbackslash}ell{\textbackslash}to{\textbackslash}infty\}: the ring ℤ\{{\textbackslash}mathbb\{Z\}\} is e-definable in G , the Diophantine problem over G is undecidable, the maximal ring of scalars of G is ℤ\{{\textbackslash}mathbb\{Z\}\}, G is indecomposable as a direct product of non-abelian groups, and Z(G)=〈C〉\{Z(G)={\textbackslash}langle C{\textbackslash}rangle\}. We further study when Z(G)≤Is(G′)\{Z(G){\textbackslash}leq{\textbackslash}operatorname\{Is\}(G{\textasciicircum}\{{\textbackslash}prime\})\}. Finally, 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.},
language = {en},
number = {2},
urldate = {2021-04-21},
journal = {Groups Complexity Cryptology},
author = {Garreta, Albert and Miasnikov, Alexei and Ovchinnikov, Denis},
month = nov,
year = {2017},
note = {Publisher: De Gruyter
Section: Groups Complexity Cryptology},
pages = {99--115},
}
Downloads: 0
{"_id":"mJzwbS5Za7gEgezaY","bibbaseid":"garreta-miasnikov-ovchinnikov-randomnilpotentgroupspolycyclicpresentationsanddiophantineproblems-2017","author_short":["Garreta, A.","Miasnikov, A.","Ovchinnikov, D."],"bibdata":{"bibtype":"article","type":"article","title":"Random nilpotent groups, polycyclic presentations, and Diophantine problems","volume":"9","issn":"1869-6104","url":"https://www.degruyter.com/document/doi/10.1515/gcc-2017-0007/html","doi":"10.1515/gcc-2017-0007","abstract":"We introduce a model of random finitely generated, torsion-free, 2-step nilpotent groups (in short, τ2\\\\textbackslashtau_\\2\\\\-groups). To do so, we show that these are precisely the groups with presentation of the form 〈A,C∣[ai,aj]=∏t=1mctλt,i,j(1≤i<j≤n),[A,C]=[C,C]=1〉\\\\textbackslashlangle A,C\\textbackslashmid[a_\\i\\,a_\\j\\]=\\textbackslashprod_\\t=1\\\\textasciicircum\\m\\c_\\t\\\\textasciicircum\\\\textbackslashlambda_\\t,i,j\\\\(1\\textbackslashleq i<j% \\textbackslashleq n),\\textbackslash,[A,C]=[C,C]=1\\textbackslashrangle\\, where A=\\a1,…,an\\\\A=\\textbackslash\\a_\\1\\,\\textbackslashdots,a_\\n\\\\textbackslash\\\\ and C=\\c1,…,cm\\\\C=\\textbackslash\\c_\\1\\,\\textbackslashdots,c_\\m\\\\textbackslash\\\\. Hence, a random G can be selected by fixing A and C , and then randomly choosing integers λt,i,j\\\\textbackslashlambda_\\t,i,j\\\\, with \\textbarλt,i,j\\textbar≤ℓ\\\\textbar\\textbackslashlambda_\\t,i,j\\\\textbar\\textbackslashleq\\textbackslashell\\ for some ℓ\\\\textbackslashell\\. We prove that if m≥n-1≥1\\m\\textbackslashgeq n-1\\textbackslashgeq 1\\, then the following hold asymptotically almost surely as ℓ→∞\\\\textbackslashell\\textbackslashto\\textbackslashinfty\\: the ring ℤ\\\\textbackslashmathbb\\Z\\\\ is e-definable in G , the Diophantine problem over G is undecidable, the maximal ring of scalars of G is ℤ\\\\textbackslashmathbb\\Z\\\\, G is indecomposable as a direct product of non-abelian groups, and Z(G)=〈C〉\\Z(G)=\\textbackslashlangle C\\textbackslashrangle\\. We further study when Z(G)≤Is(G′)\\Z(G)\\textbackslashleq\\textbackslashoperatorname\\Is\\(G\\textasciicircum\\\\textbackslashprime\\)\\. Finally, 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.","language":"en","number":"2","urldate":"2021-04-21","journal":"Groups Complexity Cryptology","author":[{"propositions":[],"lastnames":["Garreta"],"firstnames":["Albert"],"suffixes":[]},{"propositions":[],"lastnames":["Miasnikov"],"firstnames":["Alexei"],"suffixes":[]},{"propositions":[],"lastnames":["Ovchinnikov"],"firstnames":["Denis"],"suffixes":[]}],"month":"November","year":"2017","note":"Publisher: De Gruyter Section: Groups Complexity Cryptology","pages":"99–115","bibtex":"@article{garreta_random_2017,\n\ttitle = {Random nilpotent groups, polycyclic presentations, and {Diophantine} problems},\n\tvolume = {9},\n\tissn = {1869-6104},\n\turl = {https://www.degruyter.com/document/doi/10.1515/gcc-2017-0007/html},\n\tdoi = {10.1515/gcc-2017-0007},\n\tabstract = {We introduce a model of random finitely generated, torsion-free, 2-step nilpotent groups (in short, τ2\\{{\\textbackslash}tau\\_\\{2\\}\\}-groups). To do so, we show that these are precisely the groups with presentation of the form 〈A,C∣[ai,aj]=∏t=1mctλt,i,j(1≤i\\<j≤n),[A,C]=[C,C]=1〉\\{{\\textbackslash}langle A,C{\\textbackslash}mid[a\\_\\{i\\},a\\_\\{j\\}]={\\textbackslash}prod\\_\\{t=1\\}{\\textasciicircum}\\{m\\}c\\_\\{t\\}{\\textasciicircum}\\{{\\textbackslash}lambda\\_\\{t,i,j\\}\\}(1{\\textbackslash}leq i\\<j\\% {\\textbackslash}leq n),{\\textbackslash},[A,C]=[C,C]=1{\\textbackslash}rangle\\}, where A=\\{a1,…,an\\}\\{A={\\textbackslash}\\{a\\_\\{1\\},{\\textbackslash}dots,a\\_\\{n\\}{\\textbackslash}\\}\\} and C=\\{c1,…,cm\\}\\{C={\\textbackslash}\\{c\\_\\{1\\},{\\textbackslash}dots,c\\_\\{m\\}{\\textbackslash}\\}\\}. Hence, a random G can be selected by fixing A and C , and then randomly choosing integers λt,i,j\\{{\\textbackslash}lambda\\_\\{t,i,j\\}\\}, with {\\textbar}λt,i,j{\\textbar}≤ℓ\\{{\\textbar}{\\textbackslash}lambda\\_\\{t,i,j\\}{\\textbar}{\\textbackslash}leq{\\textbackslash}ell\\} for some ℓ\\{{\\textbackslash}ell\\}. We prove that if m≥n-1≥1\\{m{\\textbackslash}geq n-1{\\textbackslash}geq 1\\}, then the following hold asymptotically almost surely as ℓ→∞\\{{\\textbackslash}ell{\\textbackslash}to{\\textbackslash}infty\\}: the ring ℤ\\{{\\textbackslash}mathbb\\{Z\\}\\} is e-definable in G , the Diophantine problem over G is undecidable, the maximal ring of scalars of G is ℤ\\{{\\textbackslash}mathbb\\{Z\\}\\}, G is indecomposable as a direct product of non-abelian groups, and Z(G)=〈C〉\\{Z(G)={\\textbackslash}langle C{\\textbackslash}rangle\\}. We further study when Z(G)≤Is(G′)\\{Z(G){\\textbackslash}leq{\\textbackslash}operatorname\\{Is\\}(G{\\textasciicircum}\\{{\\textbackslash}prime\\})\\}. Finally, 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.},\n\tlanguage = {en},\n\tnumber = {2},\n\turldate = {2021-04-21},\n\tjournal = {Groups Complexity Cryptology},\n\tauthor = {Garreta, Albert and Miasnikov, Alexei and Ovchinnikov, Denis},\n\tmonth = nov,\n\tyear = {2017},\n\tnote = {Publisher: De Gruyter\nSection: Groups Complexity Cryptology},\n\tpages = {99--115},\n}\n\n","author_short":["Garreta, A.","Miasnikov, A.","Ovchinnikov, D."],"key":"garreta_random_2017","id":"garreta_random_2017","bibbaseid":"garreta-miasnikov-ovchinnikov-randomnilpotentgroupspolycyclicpresentationsanddiophantineproblems-2017","role":"author","urls":{"Paper":"https://www.degruyter.com/document/doi/10.1515/gcc-2017-0007/html"},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://bibbase.org/zotero/valeosupero","dataSources":["EnqvB6K2MYgNdp7Kd"],"keywords":[],"search_terms":["random","nilpotent","groups","polycyclic","presentations","diophantine","problems","garreta","miasnikov","ovchinnikov"],"title":"Random nilpotent groups, polycyclic presentations, and Diophantine problems","year":2017}