Rätt linje program

Inom matematiken , mer specifikt i beräkningsalgebra , är ett rätlinjeprogram ( SLP ) för en finit grupp G = ⟨ S ⟩ en ändlig sekvens L av element i G så att varje element i L antingen tillhör S , är inversen av ett föregående element, eller produkten av två föregående element. En SLP L sägs beräkna ett gruppelement g ∈ G om g ∈ L , där g kodas av ett ord i S och dess inverser.

Intuitivt är en SLP som beräknar några g ∈ G ett effektivt sätt att lagra g som ett gruppord över S ; observera att om g är konstruerad i i -steg kan ordlängden för g vara exponentiell i i , men längden på motsvarande SLP är linjär i i . Detta har viktiga tillämpningar inom beräkningsgruppteori , genom att använda SLP:er för att effektivt koda gruppelement som ord över en given genereringsuppsättning.

Raklinjeprogram introducerades av Babai och Szemerédi 1984 som ett verktyg för att studera beräkningskomplexiteten hos vissa matrisgruppegenskaper. Babai och Szemerédi bevisar att varje element i en finit grupp G har en SLP med längden O (log ² | G |) i varje genereringsmängd.

En effektiv lösning på det konstruktiva medlemsproblemet är avgörande för många gruppteoretiska algoritmer. Det kan anges i termer av SLPs enligt följande. Givet en finit grupp G = ⟨ S ⟩ och g ∈ G , hitta ett rätlinjigt program som beräknar g över S . Det konstruktiva medlemskapsproblemet studeras ofta i grupper med svarta lådan . Elementen kodas av bitsträngar med en fast längd. Tre orakel tillhandahålls för de gruppteoretiska funktionerna multiplikation, inversion och kontroll av likhet med identiteten. En svart låda-algoritm är en som bara använder dessa orakel. Följaktligen är rätlinjeprogram för svarta låda-grupper algoritmer för svarta lådan.

Explicita linjära program ges för en mängd finita enkla grupper i online- ATLAS of Finite Groups .

Definition

Informell definition

Låt G vara en finit grupp och låt S vara en delmängd av G . En sekvens L = ( g _{1 ,} ..., g _m ) av element i G är ett rätlinjigt program över S om varje gi kan erhållas genom en av följande tre regler:

1. g _i ∈ S
2. g _i = g _j $\cdot$ g _k för vissa j , k < i
3. g _i = g
   ⁻¹ _j för vissa j < i .

Den linjära kostnaden c ( g | S ) för ett element g ∈ G är längden av ett kortaste linjärt program över S beräkning g . Kostnaden är oändlig om g inte är i undergruppen som genereras av S .

Ett linjärt program liknar en härledning i predikatlogik. Elementen i S motsvarar axiom och gruppoperationerna motsvarar inferensreglerna.

Formell definition

Låt G vara en finit grupp och låt S vara en delmängd av G . Ett rätlinjeprogram med längden m över S som beräknar något g ∈ G är en sekvens av uttryck ( w ₁ ,…, w _m ) så att för varje i är w _i en symbol för något element i S , eller w _i = ( w _j ,-1) för vissa j < i , eller w _i = ( w _j , w _k ) för vissa j , k < i , så att wm _antar värdet g när den utvärderas i G på det uppenbara sättet.

Den ursprungliga definitionen som förekommer i kräver att G =⟨ S ⟩. Definitionen som presenteras ovan är en vanlig generalisering av detta.

Ur ett beräkningsperspektiv har den formella definitionen av ett linjärt program vissa fördelar. För det första kräver en sekvens av abstrakta uttryck mindre minne än termer över genereringsuppsättningen. För det andra tillåter det rätlinjeprogram att konstrueras i en representation av G och utvärderas i en annan. Detta är en viktig egenskap hos vissa algoritmer.

Exempel

Den dihedriska gruppen D ₁₂ är gruppen av symmetrier för en hexagon. Den kan genereras av en 60 graders rotation ρ och en reflektion λ. Kolumnen längst till vänster i följande är ett rätlinjeprogram för λρ ³ :

1. λ
2. ρ
3. ρ ²
4. ρ ³
5. λρ ³

1. λ är en generator.
2. ρ är en generator.
3. Andra regeln: (2).(2)
4. Andra regeln: (3).(2)
5. Andra regeln: (1).(4)

I S ₆ , gruppen av permutationer på sex bokstäver, kan vi ta α=(1 2 3 4 5 6) och β=(1 2) som generatorer. Kolumnen längst till vänster här är ett exempel på ett rätlinjeprogram att beräkna (1 2 3)(4 5 6):

1. α
2. β
3. α ²
4. a2p ^_ _
5. α2βα ^_ _
6. α2βαβ ^_ _
7. α2βαβα2βαβ ^_ _ ^_ _

1. (1 2 3 4 5 6)
2. (1 2)
3. (1 3 5)(2 4 6)
4. (1 3 5 2 4 6)
5. (1 4)(2 5 3 6)
6. (1 4 2 5 3 6)
7. (1 2 3) (4 5 6)

1. α är en generator
2. β är en generator
3. Andra regeln: (1).(1)
4. Andra regeln: (3).(2)
5. Andra regeln: (4).(1)
6. Andra regeln: (5).(2)
7. Andra regeln: (6).(6)

Ansökningar

Korta beskrivningar av ändliga grupper . Raklinjeprogram kan användas för att studera komprimering av ändliga grupper via första ordningens logik . De tillhandahåller ett verktyg för att konstruera "korta" meningar som beskriver G (dvs. mycket kortare än | G |). Mer detaljerat används SLP för att bevisa att varje finit enkel grupp har en första ordningens beskrivning av längden O (log| G |), och varje finit grupp G har en första ordningens beskrivning av längden O (log ³ | G | ).

Raklinjeprogram som beräknar genereringsuppsättningar för maximala undergrupper av ändliga enkla grupper . Online-ATLAS of Finite Group Representations tillhandahåller abstrakta rätlinjiga program för att beräkna genererande uppsättningar av maximala undergrupper för många finita enkla grupper.

Exempel : Gruppen Sz(32), som tillhör den oändliga familjen av Suzuki-grupper , har rang 2 via generatorerna a och b , där a har ordning 2, b har ordning 4, ab har ordning 5, ab ² har ordning 25 och abab ² ab ³ har ordning 25. Följande är ett linjärt program som beräknar en genereringsmängd för en maximal undergrupp E ₃₂ ·E ₃₂ ⋊C ₃₁ . Detta raka program finns i online-ATLAS of Finite Group Representations.

1. a
2. b
3. ab
4. abb
5. ababb
6. ababbb
7. ( abb ) ¹⁸
8. ( abb ) ⁻¹⁸
9. ( abb ) ⁻¹⁸ b
10. ( abb ) ⁻¹⁸ b ( abb ) ¹⁸
11. ( ababb ) ¹⁴
12. ( ababb ) ⁻¹⁴
13. ( ababb ) ⁻¹⁴ ababbb
14. ( ababb ) ⁻¹⁴ ababbb ( ababb ) ¹⁴

1. a är en generator.
2. b är en generator.
3. Andra regeln: (1).(2)
4. Andra regeln: (3).(2)
5. Andra regeln: (3).(4)
6. Andra regeln: (5).(2)
7. Andra regeln upprepad: (4) multiplicerat 18 gånger
8. Tredje regeln: (7) invers
9. Andra regeln: (8).(2)
10. Andra regeln: (9).(7)
11. Andra regeln upprepad: (5) multiplicerat 14 gånger
12. Tredje regeln: (11) invers
13. Andra regeln: (12).(6)
14. Andra regeln: (13).(11)

Nåbarhetsteorem

Nåbarhetssatsen säger att, givet en ändlig grupp G genererad av S , har varje g ∈ G en maximal kostnad på (1 + lg| G |) ² . Detta kan förstås som en begränsning av hur svårt det är att generera ett gruppelement från generatorerna.

Här är funktionen lg( x ) en heltalsvärderad version av logaritmfunktionen: för k ≥1 låt lg( k ) = max{ r : 2 ^r ≤ k }.

Tanken med beviset är att konstruera en mängd Z = { z ₁ ,…, z _s } som kommer att fungera som en ny genereringsmängd ( s kommer att definieras under processen). Det är vanligtvis större än S , men vilket element som helst i G kan uttryckas som ett ord med längden högst 2| Z | över Z. _ Mängden Z är konstruerad genom att induktivt definiera en ökande sekvens av mängder K ( i ).

Låt K ( i ) = { z ₁ ^{α ₁} · z ₂ ^{α ₂} ·…· z _i ^{α _i} : α _j ∈ {0,1}}, där z _i är gruppelementet adderat till Z i det i -te steget . Låt c ( i ) beteckna längden av ett kortaste rätlinjeprogram som innehåller Z ( i ) = { z ₁ ,…, z _i }. Låt K (0) = {1 _G } och c (0)=0. Vi definierar mängden Z rekursivt:

• Om K ( i ) ⁻¹ K ( i ) = G , förklara att s tar på sig värdet i och slutar.
• Annars, välj några z _{i +1} ∈ G \ K ( i ) ⁻¹ K ( i ) (som inte är tomma) som minimerar "kostnadsökningen" c ( i +1) − c ( i ).

Genom denna process definieras Z på ett sätt så att valfri g ∈ G kan skrivas som ett element av K ( i ) ⁻¹ K ( i ), vilket effektivt gör det lättare att generera från Z .

Vi måste nu verifiera följande påstående för att säkerställa att processen avslutas inom lg(| G |) många steg:

Krav 1 — Om i < s då | K ( i +1) | = 2| K ( i ) | .

Bevis

Det är omedelbart att | K ( i +1) | ≤ 2| K ( i ) | . Antag nu för en motsägelse att | K ( i +1) | < 2| K ( i ) | . Enligt duvhålsprincipen finns k ₁ , k ₂ ∈ K ( i +1) med k ₁ = z ₁ ^{α ₁} · z ₂ ^{α ₂} ·…· z _{i +1} ^{α _{i +1}} = z ₁ ^{β ₁} · z ₂ ^{β ₂} ·…· z _{i +1} ^{β _{i +1}} = k ₂ för vissa α _j , β _j ∈ {0,1}. Låt r vara det största heltal så att α _r ≠ β _r . Antag WLOG att α _r = 1. Det följer att z _r = z _p ^{− α _p} · z _{p -1} ^{− α _{p -1}} ·…· z ₁ ^{− α ₁} · z ₁ ^{β ₁} · z ₂ ^{β ₂} ·…· z _q ^{β _q} , med p , q < r . Därav z _r ∈ K ( r −1) ⁻¹ K ( r − 1), en motsägelse.

Nästa anspråk används för att visa att kostnaden för varje gruppelement ligger inom den erforderliga gränsen.

Krav 2 — c ( i ) ≤ i ² − i .

Bevis

Eftersom c (0)=0 räcker det att visa att c ( i +1) - c ( i ) ≤ 2 i . Cayley- grafen för G är sammankopplad och om i < s , K ( i ) ⁻¹ K ( i ) ≠ G , så finns det ett element av formen g ₁ · g ₂ ∈ G \ K ( i ) ⁻¹ K ( i ) med g ₁ ∈ K ( i ) ⁻¹ K ( i ) och g ₂ ∈ S .

Det krävs högst 2 i steg för att generera g ₁ ∈ K ( i ) ⁻¹ K ( i ). Det är ingen mening att generera elementet med maximal längd, eftersom det är identiteten. Därför 2 i −1 steg. För att generera g ₁ · g ₂ ∈ G \ K ( i ) ⁻¹ K ( i ), räcker det med 2 i -steg.

Vi avslutar nu satsen. Eftersom K ( s ) ⁻¹ K ( s ) = G , kan valfri g ∈ G skrivas på formen k
⁻¹ ₁ · k ₂ med k
⁻¹ ₁ , k ₂ ∈ K ( s ). Enligt konsekvens 2 behöver vi som mest s ² − s steg för att generera Z ( s ) = Z , och inte mer än 2 s − 1 steg för att generera g från Z ( s ).

Därför c ( g | S ) ≤ s ² + s − 1 ≤ lg ² | G | + lg| G | − 1 ≤ (1 + lg| G |) ² .