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

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

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

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

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

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

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

Визначення

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

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

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

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

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

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

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

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

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

Приклади

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

 

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

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

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

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

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

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

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

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

1. α
2. β
3. α²
4. α²β
5. α²βα
6. α²βαβ
7. α²βαβα²βαβ

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. α — твірна
2. β — твірна
3. Друге правило: (1).(1)
4. Друге правило: (3).(2)
5. Друге правило: (4).(1)
6. Друге правило: (5).(2)
7. Друге правило: (6).(6)

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

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

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

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

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

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

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

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

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

Доведення  

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

 

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

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

Доведення  

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

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

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

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