Rovný program - Straight-line program

v matematika, konkrétněji v výpočetní algebra, a přímočarý program (SLP) pro konečnou skupinu G = ⟨S⟩ Je konečná posloupnost L prvků G tak, že každý prvek L buď patří S, je inverzní k předchozímu prvku nebo součin dvou předchozích prvků. SLP L říká se vypočítat skupinový prvek G ∈ G -li G ∈ L, kde G je kódován slovem v S a jeho inverze.

Intuitivně některé SLP počítají G ∈ G je účinný způsob skladování G jako skupinové slovo S; pozorujte, že pokud G je postaven v i kroky, délka slova G může být exponenciální v i, ale délka odpovídajícího SLP je lineárníi. To má důležité aplikace v teorie výpočetních grup pomocí SLP k efektivnímu kódování prvků skupiny jako slov v dané generující sadě.

Přímé programy zavedly Babai a Szemerédi v roce 1984^[1] jako nástroj pro studium výpočetní složitosti určitých vlastností skupiny matic. Babai a Szemerédi dokazují, že každý prvek konečné skupiny G má délku SLP Ó(log²|G|) v každé generující sadě.

Efektivní řešení konstruktivní problém členství je zásadní pro mnoho skupinově teoretických algoritmů. Lze jej uvést z hlediska SLP následujícím způsobem. Vzhledem k omezené skupině G = ⟨S⟩ a G ∈ G, najděte lineární výpočetní program G přesS. Konstruktivní problém členství je často studován v prostředí skupiny černé skříňky. Prvky jsou kódovány bitovými řetězci pevné délky. Tři věštci jsou poskytovány pro skupinové teoretické funkce násobení, inverze a kontroly rovnosti s identitou. A algoritmus černé skříňky je ten, který používá pouze tyto věštce. Přímé programy pro skupiny černé skříňky jsou tedy algoritmy černé skříňky.

Explicitní přímé programy jsou uvedeny pro řadu konečných jednoduchých skupin online ATLAS konečných skupin.

Definice

Neformální definice

Nechat G být konečnou skupinou a nechat S být podmnožinou G. Sekvence L = (G₁,…,G_m) prvků z G je přímočarý program přes S pokud každý G_i lze získat jedním z následujících tří pravidel:

1. G_i ∈ S
2. G_i = G_j ${ displaystyle cdot}$ G_k pro některé j,k < i
3. G_i = G⁻¹
   _j pro některé j < i.

Přímka náklady C(G|S) prvku G ∈ G je délka nejkratšího přímého programu S výpočetní G. Cena je nekonečná, pokud G není v podskupině generované uživatelem S.

Přímý program je podobný derivaci v predikátové logice. Prvky S odpovídají axiomům a operace skupiny odpovídají pravidlům odvození.

Formální definice

Nechat G být konečnou skupinou a nechat S být podmnožinou G. A přímočarý program délky m přes S výpočet některé G ∈ G je posloupnost výrazů (w₁,…,w_m) takové, že pro každého i, w_i je symbol pro nějaký prvek Snebo w_i = (w_j, -1) pro některé j < inebo w_i = (w_j,w_k) pro některé j,k < i, takový, že w_m přebírá hodnotu G při hodnocení v G zjevným způsobem.

Původní definice uvedená v ^[2] to vyžaduje G =⟨S⟩. Definice uvedená výše je běžným zobecněním.

Z výpočetního hlediska má formální definice přímého programu některé výhody. Za prvé, sekvence abstraktních výrazů vyžaduje v generující sadě méně paměti než termíny. Zadruhé umožňuje přímé programy postavit v jedné reprezentaci G a hodnoceno v jiném. Toto je důležitá vlastnost některých algoritmů.^[2]

Příklady

The dihedrální skupina D₁₂ je skupina symetrií šestiúhelníku. Lze jej generovat 60stupňovou rotací ρ a jedním odrazem λ. V následujícím levém sloupci je přímkový program pro λρ³:

V S.₆, skupina permutací na šesti písmenech, můžeme jako generátory vzít α = (1 2 3 4 5 6) a β = (1 2). Sloupec zcela vlevo je příkladem přímého programu pro výpočet (1 2 3) (4 5 6):

Aplikace

Krátký popis konečných skupin. Přímé programy lze použít ke studiu komprese konečných skupin pomocí logika prvního řádu. Poskytují nástroj pro konstrukci „krátkých“ vět popisujících popis G (tj. mnohem kratší než |G|). Podrobněji se SLP používají k prokázání, že každá konečná jednoduchá skupina má popis délky prvního řádu Ó(log |G|) a každá konečná skupina G má popis délky prvního řádu Ó(log³|G|).^[3]

Přímočaré programy počítající generující množiny pro maximální podskupiny konečných jednoduchých skupin. Online ATLAS zastoupení konečných skupin^[4] poskytuje abstraktní lineární programy pro výpočet generování sad maximálních podskupin pro mnoho konečných jednoduchých skupin.

Příklad: Skupina Sz (32) patřící do nekonečné rodiny Suzuki skupiny, má 2. pozici prostřednictvím generátorů A a b, kde A má objednávku 2, b má objednávku 4, ab má objednávku 5, ab² má objednávku 25 a abab²ab³ má pořadí 25. Následuje lineární program, který počítá generující množinu pro maximální podskupinu E.₃₂${ displaystyle cdot}$E₃₂${ displaystyle rtimes}$C₃₁. Tento přímý program lze nalézt v online ATLASu zastoupení konečných skupin.

Věta o dosažitelnosti

Věta o dosažitelnosti uvádí, že vzhledem k konečné skupině G generováno uživatelem S, každý G ∈ G má maximální náklady (1 + lg |G|)². To lze chápat jako vazbu na to, jak těžké je generovat prvek skupiny z generátorů.

Zde funkce lg (X) je celočíselná verze funkce logaritmu: pro k≥1 nechat lg (k) = max {r : 2^r ≤ k}.

Myšlenkou důkazu je konstrukce sady Z = {z₁,…,z_s}, který bude fungovat jako nová generující sada (s budou definovány během procesu). Obvykle je větší než S, ale jakýkoli prvek G lze vyjádřit maximálně jako slovo délky 2|Z| přes Z. Sada Z je konstruováno indukčním definováním rostoucí posloupnosti množin K.(i).

Nechat K.(i) = {z₁^α₁·z₂^α₂·…·z_i^α_i : α_j 0,1 {0,1}}, kde z_i je prvek skupiny přidaný do Z na i-tý krok. Nechat C(i) označuje délku nejkratšího přímého programu, který obsahuje Z(i) = {z₁,…,z_i}. Nechat K.(0) = {1_G} a C(0) = 0. Definujeme množinu Z rekurzivně:

• Li K.(i)⁻¹K.(i) = G, prohlásit s převzít hodnotu i a přestaň.
• Jinak si některé vyberte z_i+1 ∈ G\K.(i)⁻¹K.(i) (který není prázdný), který minimalizuje „zvýšení nákladů“ C(i+1) − C(i).

Tímto procesem Z je definován tak, že jakýkoli G ∈ G lze napsat jako prvek K.(i)⁻¹K.(i), což účinně usnadňuje generování z Z.

Nyní musíme ověřit následující deklaraci, abychom zajistili, že proces skončí do lg (|G|) mnoho kroků:

Následující deklarace slouží k prokázání, že cena každého prvku skupiny je v rámci požadované hranice.

Trvá to maximálně 2i kroky k vygenerování G₁ ∈ K.(i)⁻¹K.(i). Nemá smysl generovat prvek maximální délky, protože se jedná o identitu. Proto 2i −1 kroky postačují. Vygenerovat G₁·G₂ ∈ G\K.(i)⁻¹K.(i), 2i kroky jsou dostatečné.

Teď dokončujeme teorém. Od té doby K.(s)⁻¹K.(s) = G, jakýkoli G ∈ G lze napsat ve formě k⁻¹
₁·k₂ s k⁻¹
₁,k₂ ∈ K.(s). Od Corollary 2 potřebujeme nanejvýš s² − s kroky k vygenerování Z(s) = Z, a ne více než 2s − 1 kroky k vygenerování G z Z(s).

Proto C(G|S) ≤ s² +  s - 1 ≤ lg²|G| + lg |G| - 1 ≤ (1 + lg |G|)².

Reference