Primitive normalisers in quasipolynomial time View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2021-10-26

AUTHORS

Mun See Chang, Colva M. Roney-Dougal

ABSTRACT

The normaliser problem has as input two subgroups H and K of the symmetric group Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {S}_n$$\end{document}, and asks for a generating set for NK(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_K(H)$$\end{document}: it is not known to have a subexponential time solution. It is proved in Roney-Dougal and Siccha (Bull Lond Math Soc 52(2):358–366, 2020) that if H is primitive, then the normaliser problem can be solved in quasipolynomial time. We show that for all subgroups H and K of Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {S}_n$$\end{document}, in quasipolynomial time, we can decide whether NSn(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_{\mathrm {S}_n}(H)$$\end{document} is primitive, and if so, compute NK(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_K(H)$$\end{document}. Hence we reduce the question of whether one can solve the normaliser problem in quasipolynomial time to the case where the normaliser in Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {S}_n$$\end{document} is known not to be primitive. More... »

PAGES

19-25

References to SciGraph publications

  • 2021-08-05. Base sizes of primitive permutation groups in MONATSHEFTE FÜR MATHEMATIK
  • 1996. Permutation Groups in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00013-021-01670-5

    DOI

    http://dx.doi.org/10.1007/s00013-021-01670-5

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1142200732


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "School of Computer Science, University of St Andrews, St Andrews, UK", 
              "id": "http://www.grid.ac/institutes/grid.11914.3c", 
              "name": [
                "School of Computer Science, University of St Andrews, St Andrews, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "Mun See", 
            "id": "sg:person.07611665501.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07611665501.15"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Mathematics and Statistics, University of St Andrews, St Andrews, UK", 
              "id": "http://www.grid.ac/institutes/grid.11914.3c", 
              "name": [
                "School of Mathematics and Statistics, University of St Andrews, St Andrews, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Roney-Dougal", 
            "givenName": "Colva M.", 
            "id": "sg:person.013462403417.99", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013462403417.99"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-1-4612-0731-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016935242", 
              "https://doi.org/10.1007/978-1-4612-0731-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00605-021-01599-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1140215368", 
              "https://doi.org/10.1007/s00605-021-01599-5"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-10-26", 
        "datePublishedReg": "2021-10-26", 
        "description": "The normaliser problem has as input two subgroups H and K of the symmetric group Sn\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathrm {S}_n$$\\end{document}, and asks for a generating set for NK(H)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$N_K(H)$$\\end{document}: it is not known to have a subexponential time solution. It is proved in Roney-Dougal and Siccha (Bull Lond Math Soc 52(2):358\u2013366, 2020) that if H is primitive, then the normaliser problem can be solved in quasipolynomial time. We show that for all subgroups H and K of Sn\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathrm {S}_n$$\\end{document}, in quasipolynomial time, we can decide whether NSn(H)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$N_{\\mathrm {S}_n}(H)$$\\end{document} is primitive, and if so, compute NK(H)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$N_K(H)$$\\end{document}. Hence we reduce the question of whether one can solve the normaliser problem in quasipolynomial time to the case where the normaliser in Sn\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathrm {S}_n$$\\end{document} is known not to be primitive.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00013-021-01670-5", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052783", 
            "issn": [
              "0003-889X", 
              "1420-8938"
            ], 
            "name": "Archiv der Mathematik", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "118"
          }
        ], 
        "keywords": [
          "group", 
          "time", 
          "cases", 
          "problem", 
          "generating set", 
          "time solution", 
          "solution", 
          "questions", 
          "set", 
          "normaliser", 
          "subgroup H", 
          "symmetric group", 
          "subexponential time solutions", 
          "quasipolynomial time"
        ], 
        "name": "Primitive normalisers in quasipolynomial time", 
        "pagination": "19-25", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1142200732"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00013-021-01670-5"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00013-021-01670-5", 
          "https://app.dimensions.ai/details/publication/pub.1142200732"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:39", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_908.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00013-021-01670-5"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00013-021-01670-5'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00013-021-01670-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00013-021-01670-5'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00013-021-01670-5'


     

    This table displays all metadata directly associated to this object as RDF triples.

    89 TRIPLES      22 PREDICATES      41 URIs      31 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00013-021-01670-5 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N385373fb4b8d4563aab2fc10f4ddbce3
    4 schema:citation sg:pub.10.1007/978-1-4612-0731-3
    5 sg:pub.10.1007/s00605-021-01599-5
    6 schema:datePublished 2021-10-26
    7 schema:datePublishedReg 2021-10-26
    8 schema:description The normaliser problem has as input two subgroups H and K of the symmetric group Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {S}_n$$\end{document}, and asks for a generating set for NK(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_K(H)$$\end{document}: it is not known to have a subexponential time solution. It is proved in Roney-Dougal and Siccha (Bull Lond Math Soc 52(2):358–366, 2020) that if H is primitive, then the normaliser problem can be solved in quasipolynomial time. We show that for all subgroups H and K of Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {S}_n$$\end{document}, in quasipolynomial time, we can decide whether NSn(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_{\mathrm {S}_n}(H)$$\end{document} is primitive, and if so, compute NK(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_K(H)$$\end{document}. Hence we reduce the question of whether one can solve the normaliser problem in quasipolynomial time to the case where the normaliser in Sn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {S}_n$$\end{document} is known not to be primitive.
    9 schema:genre article
    10 schema:inLanguage en
    11 schema:isAccessibleForFree true
    12 schema:isPartOf N45042630908b4b0db29db103d5975cf4
    13 N9c9a241d03f7430e842d3a36f9a50794
    14 sg:journal.1052783
    15 schema:keywords cases
    16 generating set
    17 group
    18 normaliser
    19 problem
    20 quasipolynomial time
    21 questions
    22 set
    23 solution
    24 subexponential time solutions
    25 subgroup H
    26 symmetric group
    27 time
    28 time solution
    29 schema:name Primitive normalisers in quasipolynomial time
    30 schema:pagination 19-25
    31 schema:productId N0e3e5eaa75444801bf1c75b7cdc92d32
    32 N81f5c78e36174af5b55c457d61135e98
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1142200732
    34 https://doi.org/10.1007/s00013-021-01670-5
    35 schema:sdDatePublished 2022-05-20T07:39
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher N9ce4f9bfed5843a69198614d49e28dc1
    38 schema:url https://doi.org/10.1007/s00013-021-01670-5
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset articles
    41 rdf:type schema:ScholarlyArticle
    42 N0e3e5eaa75444801bf1c75b7cdc92d32 schema:name doi
    43 schema:value 10.1007/s00013-021-01670-5
    44 rdf:type schema:PropertyValue
    45 N385373fb4b8d4563aab2fc10f4ddbce3 rdf:first sg:person.07611665501.15
    46 rdf:rest N7a904223d49a4447afc0a43787a2a6f3
    47 N45042630908b4b0db29db103d5975cf4 schema:volumeNumber 118
    48 rdf:type schema:PublicationVolume
    49 N7a904223d49a4447afc0a43787a2a6f3 rdf:first sg:person.013462403417.99
    50 rdf:rest rdf:nil
    51 N81f5c78e36174af5b55c457d61135e98 schema:name dimensions_id
    52 schema:value pub.1142200732
    53 rdf:type schema:PropertyValue
    54 N9c9a241d03f7430e842d3a36f9a50794 schema:issueNumber 1
    55 rdf:type schema:PublicationIssue
    56 N9ce4f9bfed5843a69198614d49e28dc1 schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Mathematical Sciences
    60 rdf:type schema:DefinedTerm
    61 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Pure Mathematics
    63 rdf:type schema:DefinedTerm
    64 sg:journal.1052783 schema:issn 0003-889X
    65 1420-8938
    66 schema:name Archiv der Mathematik
    67 schema:publisher Springer Nature
    68 rdf:type schema:Periodical
    69 sg:person.013462403417.99 schema:affiliation grid-institutes:grid.11914.3c
    70 schema:familyName Roney-Dougal
    71 schema:givenName Colva M.
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013462403417.99
    73 rdf:type schema:Person
    74 sg:person.07611665501.15 schema:affiliation grid-institutes:grid.11914.3c
    75 schema:familyName Chang
    76 schema:givenName Mun See
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07611665501.15
    78 rdf:type schema:Person
    79 sg:pub.10.1007/978-1-4612-0731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016935242
    80 https://doi.org/10.1007/978-1-4612-0731-3
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/s00605-021-01599-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140215368
    83 https://doi.org/10.1007/s00605-021-01599-5
    84 rdf:type schema:CreativeWork
    85 grid-institutes:grid.11914.3c schema:alternateName School of Computer Science, University of St Andrews, St Andrews, UK
    86 School of Mathematics and Statistics, University of St Andrews, St Andrews, UK
    87 schema:name School of Computer Science, University of St Andrews, St Andrews, UK
    88 School of Mathematics and Statistics, University of St Andrews, St Andrews, UK
    89 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...