Ordproblem for grupper

I matematik , mere præcist inden for kombinatorisk gruppeteori , er ordproblemet for en begrænset type gruppe G det algoritmiske problem med at afgøre, om to ord i gruppens generatorer repræsenterer det samme element.

Konkret hvis X er et endeligt sæt af generatorer til G , anser vi det formelle sprog består af ord på X og sæt formelle inverse, der sendes af den naturlige ansøgning om identiteten af gruppen G . Ordproblemet er det algoritmiske problem, der består i at afgøre, om et ord tilhører dette formelle sprog eller ej. Vi kan se, at hvis Y er et andet sæt af generatorer til G , så problemet af ordet med alle Y svarer til problemet med Ordet med al X . Vi kan derfor tale uden tvetydighed om ordproblemets beslutsomhed for en gruppe G af endelig type.

Et andet, men beslægtet problem er det ensartede ordproblem for en klasse K af grupper givet af et rekursivt sæt præsentationer; algoritmiske problem er at beslutte, givet en præsentation P af en gruppe G af klassen K , hvis to ord repræsenterer det samme element i G . Vi kan også overveje, at klassen K kun kan defineres ved et rekursivt utallige sæt præsentationer.

Ordproblemet er i det generelle tilfælde ubeslutsomt, men kan afgøres for mange grupper. For eksempel har polycykliske grupper (in) et ord, der kan defineres som problem; på samme måde giver Todd-Coxeter-algoritmen og færdiggørelsen af Knuth-Bendix effektive resultater. På den anden side betyder det faktum, at en bestemt algoritme ikke gælder i et bestemt tilfælde, ikke at ordproblemet er ubeslutsom. For eksempel giver Dehn algoritme ikke løse ordet problem for grundlæggende gruppe af torus , og alligevel er denne gruppe er det direkte produkt af to uendelige cykliske grupper, og derfor har et afgørbart ord problem.

En mere konkret beskrivelse

Vi overvejer en præsentation af et par, hvor er sæt generatorer og sæt relatorer. Ordproblemet er at bestemme, om to ord på og dets inverse repræsenterer det samme element i modulogruppens relatorer. Mere formelt, lad være en begrænset type gruppe , givet ved en præsentation med endelig X. Vi betragter alfabetet , hvor er et adskilt alfabet af og i forbindelse med ; dets elementer repræsenterer de formelle inverser af elementerne i . Vi betragter kortet som genereret , udvidet til en formodning af den frie monoid på . Det Ordet Problemet består så i at afgøre, om , hvor, hvis to ord og og hvor er den formelle inverse af i , og hvor er det neutrale element i . Tilsvarende er problemet at beslutte, om der skal være et ord af , derfor hvis det hører til det formelle sprog ${\ displaystyle (X \ mid R)}$ $x$ $R$ $x$ $G$ ${\ displaystyle G = \ langle X \ mid R \ rangle}$ ${\ displaystyle \ Sigma = X \ sqcup X ^ {- 1}}$ ${\ displaystyle X ^ {- 1}}$ $x$ $x$ $x$ ${\ displaystyle \ pi: X \ til G}$ ${\ displaystyle \ pi (X) \ subseteq G}$ $G$ $\ Sigma ^ {*}$ $G$ ${\ displaystyle \ pi (u) = \ pi (v)}$ ${\ displaystyle \ pi (uv ^ {- 1}) = e}$ $u$ $v$ ${\ displaystyle v ^ {- 1}}$ $v$ $\ Sigma ^ {*}$ $e$ $G$ ${\ displaystyle \ pi (x) = e}$ $x$ $\ Sigma ^ {*}$ $x$

{\ displaystyle W (G, X) = \ {w \ in \ Sigma ^ {*} \ mid \ pi (w) = e \}}

Ved en noget elliptisk genvej siger vi også, at det hele er ordets problem. Vi siger også, at ordproblemet kan løses, hvis sprogmedlemskabet kan afgøres. ${\ displaystyle W (G, X)}$ ${\ displaystyle W (G, X)}$

Eksempler

Grupper med et løseligt ordproblem

Følgende grupper har et problem, der kan løses:

De automatiske grupper , som inkluderer:
- de begrænsede grupper
- de hyperboliske grupper
- de euklidiske grupper
- De Coxeter grupper
- de fletning grupper
- de geometrisk endelige grupper (i)
De frie grupper er endeligt
De abelske grupper af begrænset type
De polycykliske grupper (i)
De grupper viste, absolut (i) finite typen, omfattende:
- Enkle grupper af begrænset type.
Restmæssigt begrænsede grupper (i) fint præsenteret
Grupperne i en relator (af Magnus sætning), inklusive de grundlæggende grupper af varianter, to dimensioner og justerbare lukkede.
De næsten frie grupper af begrænset type, da sprogækvivalente ord i det neutrale element er et algebraisk sprog af Muller-Schupp-sætningen .

Grupper med et ubeslutsom ordproblem

Lad X være et rekursivt talbart antal naturlige heltal, hvor medlemsproblemet er ubeslutsom. Så gruppen ${\ displaystyle \ langle a, b, c, d \ mid a ^ {n} ba ^ {n} = c ^ {n} dc ^ {n}, n \ i X \ rangle}$ er af endelig type med en rekursivt opregningsbar præsentation, og hvis ordproblem er ubeslutsom.
Enhver begrænset type gruppe med en rekursivt opregningsbar præsentation og et ubesluteligt ordproblem er en undergruppe af en begrænset type gruppe med et ubesluteligt ordproblem
Antallet af relatorer i en fint præsenteret gruppe med et ubeslutsom ordproblem kan være 14 eller endda 12.
Et eksplicit eksempel på en præsentation med et ubeslutsom ordproblem er:

generatorer :

{\ displaystyle \ {a, b, c, d, e, p, q, r, t, k \}}

relationer : (kommutationer) og meget mere

{\ displaystyle ra = ar, rb = br, rc = cr, rd = dr, re = er, pt = tp, qt = tq}

{\ displaystyle {\ begin {array} {ll} & p ^ {10} a = ap, & pacqr = rpcaq, \\ & p ^ {10} b = bp, & p ^ {2} adq ^ {2} r = rp ^ {2} daq ^ {2}, \\ & p ^ {10} c = cp, & p ^ {3} bcq ^ {3} r = rp ^ {3} cbq ^ {3}, \ \ & p ^ {10} d = dp, & p ^ {4} bdq ^ {4} r = rp ^ {4} dbq ^ {4}, \\ & p ^ {10} e = ep, & p ^ {5} ceq ^ {5} r = rp ^ {5} ecaq ^ {5}, \\ & aq ^ {10} = qa, & p ^ {6} deq ^ {6} r = rp ^ {6} edbq ^ {6}, \\ & bq ^ {10} = qb, & p ^ {7} cdcq ^ {7} r = rp ^ {7} cdceq ^ {7}, \\ & cq ^ {10} = qc, & p ^ {8} ca ^ {3} q ^ {8} r = rp ^ {8} a ^ {3} q ^ {8}, \\ & dq ^ {10} = qd, & p ^ {9} da ^ {3} q ^ {9} r = rp ^ {9} a ^ {3} q ^ {9}, \\ & eq ^ {10} = qe, & a ^ {- 3} ta ^ {3} k = ka ^ {- 3} ta ^ {3} \ end {array}}}

Generelle resultater

Boone-Rogers sætning : Der er ingen delvis algoritme, der løser ordproblemet i alle begrænsede typegrupper, der har et problem, der kan løses.

Med andre ord er det ensartede ordproblem ikke løst for klassen i alle endeligt præsenterede grupper.

Boone-Higman-sætning : En fint præsenteret gruppe har et løseligt ordproblem, hvis og kun hvis det kan kastes i en simpel gruppe, der kan kastes i en fint præsenteret gruppe.

Følgende resultat er blevet demonstreret af Bernhard Neumann og Angus Macintyre :

En endeligt præsenteret gruppe har et ordproblem, der kan løses, hvis og kun hvis den kan nedsænkes i en algebraisk lukket gruppe (i) .

For enkeltgrupper:

En enkelt gruppe præsenteret rekursivt har et løsbart ordproblem.

Ordproblemet er ensartet løst for klassen af endeligt præsenterede enkle grupper.

Historisk note

Beregninger i grupper udføres ofte ved hjælp af forskellige normale former . Eksistensen af en sådan normal form løser normalt implicit ordproblemet for de undersøgte grupper. I 1911 foreslog Max Dehn at betragte ordproblemet som et vigtigt emne i sig selv såvel som konjugationsproblemet (en) og problemet med gruppers isomorfisme (en) . I 1912 gav han en algoritme til løsning af ordproblemet og bøjningsproblemet for grundlæggende grupper af orienterbare lukkede manifolder af dimension 2 af slægten større end eller lig med 2. Andre forfattere udvidede derefter Dehns algoritme kraftigt og anvendte den på mange beslutningsproblemer .

I 1955 viser Piotr Novikov , at der er en fint præsenteret gruppe G, hvis ordproblem er ubeslutsom . Det følger straks, at det ensartede ordproblem også er uafgøreligt. Uafhængigt bevis blev afgivet af William Boone i 1958.

Ordproblemet var et af de første eksempler på et ubeslutsomt problem, der ikke opstod fra matematisk logik eller teorien om algoritmer , men fra generel algebra , den centrale gren af klassisk matematik.

Noter og referencer

Bemærkninger

JA Todd og HSM Coxeter. “En praktisk metode til at tælle coset af en begrænset abstrakt gruppe”, Proc. Edinburgh Math Soc. (2), vol. 5, side 25-34, 1936.
D. Knuth og P. Bendix. "Simple word problems in universal algebras", J. Leech (editor) Computational Problems in Abstract Algebra , side 263-297, 1970.
H. Simmons, "Ordet problem for absolutte præsentationer." J. London Math. Soc. (2) 6, 275-280 1973
Lyndon og Schupp 2001 .
Collins og Zieschang 1990 , s. 149.
Collins og Zieschang 1990 , Cor. 7.2.6.
Collins 1969 .
Borisov 1969 .
Collins 1972 .
Collins 1986 .
Den præsenterede version er en korrigeret version hentet fra A Catalog of Algebraic Systems af John Pedersen.
Dehn 1911 .
Dehn 1912 .
Martin Greendlinger , ” Dehn algoritme for ordet problem ”, meddelelser om Ren og Anvendt matematik , vol. 13, nr . 1, Juni 1959, s. 67–83 ( DOI 10.1002 / cpa.3160130108 )
Roger C. Lyndon , “ On Dehns algoritme ”, Mathematische Annalen , bind. 166, nr . 3, September 1966, s. 208–228 ( DOI 10.1007 / BF01361168 , læs online )
Paul E. Schupp , “ Om Dehns algoritme og konjugationsproblemet ”, Mathematische Annalen , bind. 178, nr . 2 Juni 1968, s. 119–130 ( DOI 10.1007 / BF01350654 , læs online )
Novikov 1955 .
Boone 1958 .

Referencer

(da) " Word problem " , på PlanetMath

Bøger

Roger C. Lyndon og Paul E. Schupp , Combinatorial Group Theory , Springer-Verlag , koll. "Klassikere i matematik",2001, xiv + 339 s. ( ISBN 3-540-41158-5 , læs online ) - Genoptryk af 1977-udgaven
William W. Boone, FB Cannonito og Roger C. Lyndon (redaktører), Word Problems: Decision Problem in Group Theory , North-Holland,1973.
Joseph Rotman , en introduktion til teorien om grupper , Berlin, New York, Springer-Verlag ,1994, 517 s. ( ISBN 978-0-387-94285-8 , læs online ).
Donald J. Collins og H. Zieschang , kombinatorisk gruppeteori og grundlæggende grupper , Berlin, New York, Springer-Verlag ,1990( Matematikanmeldelser 1099152 )

Artikler

(ru) Piotr Novikov , “ Om ordproblemets algoritmiske uløselighed i gruppeteori ” , Proceedings of the Steklov Institute of Mathematics , bind. 44,1955, s. 1-143 ( zbMATH 0068.01301 )
William W. Boone , " Ordet problem, " Proceedings of the National Academy of Sciences , bind. 44, nr . 10,1958, s. 1061–1065 ( DOI 10.1073 / pnas.44.10.1061 , zbMATH 0086.24701 , læs online [PDF] )
William W. Boone og G. Higman, " En algebraisk karakterisering af ordproblemets opløselighed ", J. Austral. Matematik. Soc. , Vol. 18,1974, s. 41-53.
William W. Boone og H. Rogers Jr., ” Om et problem med JHC Whitehead og et problem med Alonzo Church, ” Math. Scand. , Vol. 19,1966, s. 185-192.
VV Borisov , “ Enkle eksempler på grupper med uløseligt ordproblem ”, Akademiya Nauk SSSR. Matematicheskie Zametki , vol. 6,1969, s. 521–532 ( ISSN 0025-567X , matematikanmeldelser 0260851 )
Donald J. Collins , ” Ord- og konjugatproblemer i grupper med kun få definerende relationer ”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , vol. 15, n os 20-221969, s. 305–324 ( DOI 10.1002 / malq.19690152001 , matematikanmeldelser 0263903 )
Donald J. Collins , “ On a group embedding theorem of VV Borisov ”, Bulletin of the London Mathematical Society , bind. 4, n o 21972, s. 145–147 ( ISSN 0024-6093 , DOI 10.1112 / blms / 4.2.145 , matematiske anmeldelser 0314998 )
Donald J. Collins , ” En simpel præsentation af en gruppe med uløseligt ordproblem, ” Illinois Journal of Mathematics , bind. 30, nr . 21986, s. 230–234 ( ISSN 0019-2082 , matematikanmeldelser 840121 )
Max Dehn , “ Über unendliche diskontinuierliche Gruppen ”, Mathematische Annalen , vol. 71, nr . 1,1911, s. 116–144 ( ISSN 0025-5831 , DOI 10.1007 / BF01456932 , Matematikanmeldelser 1511645 , læs online )
Max Dehn , “ Transformation der Kurven auf zweiseitigen Flächen ”, Mathematische Annalen , vol. 72, n o 3,1912, s. 413–421 ( ISSN 0025-5831 , DOI 10.1007 / BF01456725 , Matematikanmeldelser 1511705 , læs online )
CF Miller, "Beslutningsproblemer for grupper - undersøgelse og refleksioner" , i algoritmer og klassificering i kombinatorisk gruppeteori , Springer,1991, s. 1-60
J. Stillwell, "Ordproblemet og isomorfismeproblemet for grupper ", AMS Bulletin , bind. 6,1982, s. 33-56.
Sam AM Jones og Richard M. Thomas , " Gruppeproblemer i grupper: formelle sprog, karakteriseringer og beslutsomhed ", Theoretical Computer Science , bind. 750,2018, s. 2–23 ( DOI 10.1016 / j.tcs.2018.05.007 ).

Relaterede artikler

Kombination af ord
Ordproblem
Indlejret batteriautomat (de blev brugt til at løse ordproblemet i grupper)