Лінійна програма

Не плутати з лінійним програмуванням.

В інформатиці лінійна програма — неформально, програма, яка не містить жодного циклу чи будь-яких перевірок та складається з послідовності кроків, на яких кожна операція виконується над попередньо обчисленими значеннями.

У цій статті розглянуто випадок, коли дозволеними операціями є операції групи, тобто множення та інверсія. Конкретніше, лінійна програма (ЛП) для скінченної групи ${\displaystyle G=\langle S\rangle }$ — це скінченна послідовність ${\displaystyle L}$ елементів ${\displaystyle G}$, така що кожен елемент ${\displaystyle L}$ або належить ${\displaystyle S}$, є оберненим до попереднього елемента або є добутком двох попередніх елементів. Кажуть, що ЛП ${\displaystyle L}$ обчислює груповий елемент ${\displaystyle g\in G}$ якщо ${\displaystyle g\in L}$, де ${\displaystyle g}$ закодовано словом із ${\displaystyle S}$ та оберненими до нього.

Інтуїтивно зрозуміло, що лінійне обчислення деякого ${\displaystyle g\in G}$ — ефективний спосіб збереження ${\displaystyle g}$ як слова групи над ${\displaystyle S}$; зауважте, що якщо ${\displaystyle g}$ побудовано за ${\displaystyle i}$ кроків, довжина слова ${\displaystyle g}$ може бути експоненційною за ${\displaystyle i}$, але довжина відповідної ЛП є лінійною за ${\displaystyle i}$. Це має важливе застосування в теорії обчислювальних груп, у вигляді використання ЛП для ефективного кодування елементів групи як слів над даною твірною множиною.

Лінійні програми представили 1984 року Бабай та Семереді як засіб для вивчення обчислювальної складності певних властивостей матричних груп. Вони довели, що кожен елемент скінченної групи ${\displaystyle G}$ має ЛП довжини ${\displaystyle O(log^{2}|G|)}$ в кожній твірній множині.

Ефективне розв'язання конструктивної задачі належності має вирішальне значення для багатьох теоретико-групових алгоритмів. З погляду ЛП це можна викласти так. Дано скінченну групу ${\displaystyle G=\langle S\rangle }$ і ${\displaystyle g\in G}$, потрібно знайти ЛП, що обчислює ${\displaystyle g}$ над ${\displaystyle S}$. Конструктивну задачу належності часто вивчають у групі чорної скриньки. Елементи кодують бітовими рядками фіксованої довжини. Для теоретико-групових функцій множення, інверсії та перевірки рівності з тотожністю надаються три оракули. Алгоритм чорної скриньки використовує лише ці оракули. Отже, лінійні програми для груп чорної скриньки є алгоритмами чорної скриньки.

Явні лінійні програми для багатьох скінченних простих груп подано в онлайновому ^[en] .

Визначення

Неформальне визначення

Нехай ${\displaystyle G}$ — скінченна група і ${\displaystyle S}$ — підмножина ${\displaystyle G}$. Послідовність ${\displaystyle L=(g_{1},...,g_{m})}$ елементів ${\displaystyle G}$ є лінійною програмою над ${\displaystyle S}$, якщо кожне ${\displaystyle g_{i}}$ можна отримати за одним із таких трьох правил:

1. ${\displaystyle g_{i}\in S}$
2. ${\displaystyle g_{i}=g_{j}\cdot g_{k}}$ для деяких ${\displaystyle j,k<i}$
3. ${\displaystyle g_{i}=g_{j}^{-1}}$ для деякого ${\displaystyle j<i}$.

Лінійна вартість ${\displaystyle c(g|S)}$ елемента ${\displaystyle g\in G}$ — це довжина найкоротшої лінійної програми над ${\displaystyle S}$, що обчислює ${\displaystyle g}$. Вартість нескінченна, якщо ${\displaystyle g}$ не входить до підгрупи, породженої ${\displaystyle S}$.

Лінійна програма схожа на виведення в логіці предикатів. Елементи ${\displaystyle S}$ відповідають аксіомам, а групові операції — правилам виведення.

Формальне визначення

Нехай ${\displaystyle G}$ — скінченна група і ${\displaystyle S}$ — підмножина ${\displaystyle G}$. Лінійна програма довжини ${\displaystyle m}$ над ${\displaystyle S}$, яка обчислює деяке ${\displaystyle g\in G}$, це послідовність виразів ${\displaystyle (w_{1},...,w_{m})}$, де для кожного ${\displaystyle i}$ ${\displaystyle w_{i}}$ є символом деякого елемента ${\displaystyle S}$, або ${\displaystyle w_{i}=(w_{j},-1)}$ для деякого ${\displaystyle j<i}$, або ${\displaystyle w_{i}=(w_{j},w_{k})}$ для деякого ${\displaystyle j,k<i}$, така, що ${\displaystyle w_{m}}$ набуває значення ${\displaystyle g}$ при оціненні в ${\displaystyle G}$ в очевидний спосіб.

Оригінальне визначення, наведене в, вимагає, щоб ${\displaystyle G=\langle S\rangle }$. Наведене вище визначення є його узагальненням.

З погляду обчислень, формальне визначення лінійної програми має деякі переваги. По-перше, послідовність абстрактних виразів потребує менше пам'яті, ніж терми твірної множини^{[: ком.]}. По-друге, це дозволяє будувати лінійні програми в одному представленні ${\displaystyle G}$ і обчислювати в іншому. Це важлива особливість деяких алгоритмів.

Приклади

Діедрична група ${\displaystyle D_{12}}$ є групою симетрій шестикутника. Її можна створити поворотом ρ на 60 градусів і одним відбиттям λ. Крайній лівий стовпець наведеного нижче є лінійною програмою для λρ³:  

λ ρ ρ^2 ρ^3 λρ^3

λ — твірна. ρ — твірна. Друге правило: (2).(2) Друге правило: (3).(2) Друге правило: (1).(4)

У групі перестановок із шести літер ${\displaystyle S_{6}}$твірними можна взяти α=(1 2 3 4 5 6) і β=(1 2). Крайній лівий стовпець тут є прикладом лінійної програми для обчислень (1 2 3)(4 5 6):

a b ab abb ababb ababbb (abb)^18 (abb)^−18 (abb)^−18b (abb)^−18b(abb)^18 (ababb)^14 (ababb)^−14 (ababb)^−14ababbb (ababb)^−14ababbb(ababb)^14

a — твірна. b — твірна. Друге правило: (1).(2) Друге правило: (3).(2) Друге правило: (3).(4) Друге правило: (5).(2) Друге правило ітеровано: (4) повторено 18 разів Третє правило: (7) обернення Друге правило: (8).(2) Друге правило: (9).(7) Друге правило ітеровано: (5) повторено 14 разів Третє правило: (11) обернення Друге правило: (12).(6) Друге правило: (13).(11)

Застосування

Короткі описи скінченних груп. Лінійні програми можна використовувати для вивчення стиснення скінченних груп за допомогою логіки першого порядку. Вони надають засіб для побудови «коротких» речень, що описують ${\displaystyle G}$ (тобто значно коротших, ніж ${\displaystyle |G|}$). Детальніш, ЛП використовують, щоб довести, що кожна скінченна проста група має опис першого порядку довжини ${\displaystyle O(log|G|)}$, а кожна скінченна група ${\displaystyle G}$ має опис першого порядку довжини ${\displaystyle O(log^{3}|G|)}$.

Лінійні програми обчислення твірних для максимальних підгруп скінченних простих груп. Онлайновий АТЛАС представлень скінченних груп містить абстрактні лінійні програми для обчислення твірних наборів максимальних підгруп для багатьох скінченних простих груп.

Приклад: група ${\displaystyle Sz(32)}$, що належить до нескінченної сім'ї ^[en], має ранг 2 через твірні ${\displaystyle a}$ і ${\displaystyle b}$, де ${\displaystyle a}$ має порядок 2, ${\displaystyle b}$ має порядок 4, ${\displaystyle ab}$ має порядок 5, ${\displaystyle ab^{2}}$ має порядок 25 і ${\displaystyle abab^{2}ab^{3}}$ має порядок 25. Нижче наведено лінійну програму, яка обчислює твірний набір для максимальної підгрупи ${\displaystyle E32\cdot E32\rtimes C31}$. Цю лінійну програму можна знайти в онлайновому АТЛАСІ представлень скінченних груп.

α β α^2 α^2β α^2βα α^2βαβ α^2βαβα^2βαβ

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

α — твірна β — твірна Друге правило: (1).(1) Друге правило: (3).(2) Друге правило: (4).(1) Друге правило: (5).(2) Друге правило: (6).(6)

Теорема про досяжність

Теорема про досяжність стверджує, що для скінченної групи ${\displaystyle G}$, породженої ${\displaystyle S}$, кожна ${\displaystyle g\in G}$ має максимальну вартість ${\displaystyle (1+lg|G|)^{2}}$. Це можна розуміти як обмеження того, наскільки складно згенерувати елемент групи з генераторів.

Тут функція ${\displaystyle lg(x)}$ — це цілочисельна версія функції логарифма: нехай для ${\displaystyle k\geq 1}$ ${\displaystyle lg(k)=max\{r:2^{r}\leq k\}}$.

Ідея доведення полягає в тому, щоб побудувати множину ${\displaystyle Z=\{z_{1},...,z_{s}\}}$, яка працюватиме як нова твірна множина (${\displaystyle s}$ буде визначено в процесі). Зазвичай вона більша за ${\displaystyle S}$, але будь-який елемент ${\displaystyle G}$ можна виразити як слово довжини щонайбільше ${\displaystyle 2|Z|}$ над ${\displaystyle Z}$. Множина ${\displaystyle Z}$ будується індуктивним визначенням зростальної послідовності множин ${\displaystyle K(i)}$.

Нехай ${\displaystyle K(i)=\{z_{1}^{\alpha _{1}}\cdot z_{2}^{\alpha _{2}}\cdot ...\cdot z_{j}^{\alpha _{j}}:{\alpha _{i}}\in \{0,1\}\}}$, де ${\displaystyle z_{i}}$ — елемент групи, доданий до ${\displaystyle Z}$ на ${\displaystyle i}$-му кроці. Нехай ${\displaystyle c(i)}$ позначає довжину найкоротшої лінійної програми, яка містить ${\displaystyle Z(i)={z_{1},...,z_{i}}}$. Нехай ${\displaystyle K(0)={1_{G}}}$ і ${\displaystyle c(0)=0}$. Ми визначаємо множину ${\displaystyle Z}$ рекурсивно:

• Якщо ${\displaystyle K(i)^{-1}K(i)=G}$, оголосимо ${\displaystyle s}$ рівним ${\displaystyle i}$, і зупинимося.
• В іншому випадку виберемо деяке ${\displaystyle z_{i+1}\in G\backslash K(i)^{-1}K(i)}$ (яка непорожня), яке мінімізує «збільшення вартості» ${\displaystyle c(i+1)-c(i)}$.

За допомогою цього процесу ${\displaystyle Z}$ визначається так, що будь-яке ${\displaystyle g\in G}$ можна записати як елемент ${\displaystyle K(i)^{-1}K(i)}$, що фактично полегшує генерування із ${\displaystyle Z}$.

Тепер, щоб переконатися, що процес завершується протягом ${\displaystyle lg(|G|)}$ кроків, потрібно перевірити таке твердження:

Твердження 1. Якщо ${\displaystyle i<s}$, то ${\displaystyle \left\vert K(i+1)\right\vert }$ = ${\displaystyle 2\left\vert K(i)\right\vert }$.

Доведення  

  Очевидно, що ${\displaystyle \left\vert K(i+1)\right\vert \leq 2\left\vert K(i)\right\vert }$. Тепер припустимо, що ${\displaystyle \left\vert K(i+1)\right\vert <2\left\vert K(i)\right\vert }$. За принципом Діріхле ${\displaystyle k_{1},k_{2}\in K(i+1)}$ де ${\displaystyle k_{1}=z_{1}^{\alpha _{1}}\cdot z_{2}^{\alpha _{2}}\cdot ...\cdot z_{i+1}^{\alpha _{i+1}}=z_{1}^{\beta _{1}}\cdot z_{2}^{\beta _{2}}\cdot ...\cdot z_{i+1}^{\beta _{i+1}}=k_{2}}$ для деяких ${\displaystyle \alpha _{j},\beta _{j}\in \{0,1\}}$. Нехай ${\displaystyle r}$ - найбільше ціле число, таке що ${\displaystyle \alpha _{r}\neq \beta _{r}}$. Припустимо, без втрати загальності, що ${\displaystyle \alpha _{r}=1}$. З цього випливає, що ${\displaystyle z_{r}=z_{p}^{-\alpha _{p}}\cdot z_{p-1}^{-\alpha _{p-1}}\cdot ...\cdot z_{1}^{-\alpha _{1}}\cdot z_{1}^{\beta _{1}}\cdot z_{2}^{\beta _{2}}\cdot ...\cdot z_{q}^{\beta _{q}}}$, де ${\displaystyle p,q<r}$. Отже, ${\displaystyle z_{r}\in {K(r-1)^{-1}K(r-1)}}$ - маємо суперечність.■

 

Наступне твердження використовують, щоб показати, що вартість кожного елемента групи міститься в необхідних межах.

Твердження 2. ${\displaystyle c(i)\leq i^{2}-i}$.

Доведення  

Оскільки ${\displaystyle c(0)=0}$, достатньо показати, що ${\displaystyle c(i+1)-c(i)\leq 2i}$. Граф Келі для ${\displaystyle G}$ зв'язний і, якщо ${\displaystyle i<s}$, ${\displaystyle K(i)^{-1}K(i)\neq G}$, то є елемент форми ${\displaystyle g_{1}\cdot g_{2}\in G\backslash K(i)^{-1}K(i)}$ де ${\displaystyle g_{1}\in K(i)^{-1}K(i)}$ і ${\displaystyle g_{2}\in S}$.■

Для створення ${\displaystyle g_{1}\in K(i)^{-1}K(i)}$ потрібно щонайбільше ${\displaystyle 2i}$ кроків. Немає сенсу генерувати елемент максимальної довжини, оскільки це тотожність. Отже, достатньо ${\displaystyle 2i-1}$ кроків. Для створення ${\displaystyle g_{1}\cdot g_{2}\in G\backslash K(i)^{-1}K(i)}$ достатньо ${\displaystyle 2i}$ кроків.

Тепер закінчуємо теорему. Оскільки ${\displaystyle K(s)^{-1}K(s)=G}$, будь-яке ${\displaystyle g\in G}$ можна записати у вигляді ${\displaystyle k_{1}^{-1}\cdot k_{2}}$, де ${\displaystyle k_{1}^{-1},k_{2}\in K(s)}$. Згідно з наслідком 2, нам потрібно щонайбільше ${\displaystyle s^{2}-s}$ кроків, щоб згенерувати ${\displaystyle Z(s)=Z}$, і не більше ${\displaystyle 2s-1}$ кроків, щоб згенерувати ${\displaystyle g}$ із ${\displaystyle Z(s)}$.

Тому ${\displaystyle c(g|S)\leq s^{2}+s-1\leq lg^{2}|G|+lg|G|-1\leq (1+lg|G|)^{2}}$.

Примітки

1. Babai, László, and Endre Szemerédi. «On the complexity of matrix group problems I.» Foundations of Computer Science, 1984. 25th Annual Symposium on Foundations of Computer Science. IEEE, 1984
2. Ákos Seress. (2003). Permutation Group Algorithms. [Online]. Cambridge Tracts in Mathematics. (No. 152). Cambridge: Cambridge University Press.
3. Nies, André; Tent, Katrin (2017). Describing finite groups by short first-order sentences. . 221: 85—115. arXiv:1409.8390. doi:10.1007/s11856-017-1563-2.
4. ATLAS of Finite Group Representations - V3.