Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
type: Item
instance of: scholarly article
title: Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
zbMATH Open document ID: 0952.20005
author: Sergey Bratus
author: Igor Pak
published in: Journal of Symbolic Computation
publication date: 2000-08-28T00:00:00Z
review text: This paper deals with the following question: Suppose you have a finitely generated group \(G\) for which you know that there exists a group isomorphism \(\phi\colon G\to S_n\), where \(S_n\) is the symmetric group. Can you construct \(\phi\) ``quickly'' and, if so, how? The authors provide a ``randomized'' algorithm which computes \(a,b\in G\) such that \(\phi(a)=(1,2)\) and \(\phi(b)=(1,2,\dots,n)\). Moreover, they provide an algorithm which, for each \(x\in G\), computes \(\phi(x)\in S_n\). These algorithms, and their complexity estimates, involve several assumptions -- all of which are laid out clearly by the authors. For example, they assume \(n\geq 20\) and, for the complexity estimates, a rather explicit version of the Goldbach 2-primes conjecture. Under these assumptions, their algorithms are sub-quadratic in \(n\). The authors give a modification of their algorithm where \(S_n\) is replaced by \(A_n\). They also address the harder question: what if one knows only that there exists a group isomorphism \(\phi\colon G\to S_n\), for some unknown \(n\)? The authors show that, under the Goldbach conjecture, there is a subquadratic (randomized) algorithm to do that, too.
Mathematics Subject Classification ID: 20B40
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 11P32
zbMATH DE Number: 1422746
zbMATH Keywords: finitely generated groups
zbMATH Keywords: group isomorphisms
zbMATH Keywords: symmetric groups
zbMATH Keywords: alternating groups
zbMATH Keywords: randomized algorithms
zbMATH Keywords: complexity estimates
zbMATH Keywords: Goldbach conjecture
reviewed by: David Joyner
describes a project that uses: GAP
MaRDI profile type: Publication
full work available at URL: jsco.1999.0295
OpenAlex ID: W1979045682
Wikidata QID: Q123226193
cites work: Q4335288
cites work: Fast recognition of doubly transitive groups
cites work: Q4335292
cites work: Q4335291
cites work: Generating random elements of a finite group
cites work: Q5556574
cites work: Q4333102
cites work: Q4335294
cites work: Q5650865
cites work: A complete Vinogradov 3-primes theorem under the Riemann hypothesis
cites work: Walks on generating sets of groups
cites work: Q3259107
cites work: A.D. Alexandrov spaces with curvature bounded below
cites work: The exceptional set of Goldbach's problem
cites work: A Recognition Algorithm for Special Linear Groups
cites work: Q4335304
cites work: A Recognition Algorithm For Classical Groups Over Finite Fields
cites work: Q4224933
cites work: Q4875069
cites work: Approximate formulas for some functions of prime numbers
cites work: Checking the odd Goldbach conjecture up to 10²⁰
cites work: Q4272975
cites work: Q5827024
cites work: Q3317167
cites work: On Vinogradov's constant in Goldbach's ternary problem
DOI: 10.1006/JSCO.1999.0295
description: scientific article; zbMATH DE number 1422746