Прямолинейная программа - Straight-line program

В математика, более конкретно в вычислительная алгебра, а прямолинейная программа (SLP) для конечной группы грамм = ⟨S⟩ - конечная последовательность L элементов грамм так что каждый элемент L либо принадлежит S, является обратным предыдущему элементу или произведению двух предыдущих элементов. SLP L говорят вычислить групповой элемент грамм ∈ грамм если грамм ∈ L, куда грамм закодировано словом в S и его обратные.

Интуитивно понятно, что SLP, вычисляющий некоторые грамм ∈ грамм является эффективный способ хранения грамм как групповое слово над S; заметьте, что если грамм построен в я шагов, длина слова грамм может быть экспоненциальным в я, но длина соответствующего SLP линейна поя. Это имеет важные приложения в вычислительная теория групп, используя SLP для эффективного кодирования элементов группы в виде слов в заданной генерирующей установке.

Прямолинейные программы были введены Бабаем и Семереди в 1984 году.^[1] как инструмент для изучения вычислительной сложности некоторых свойств групп матриц. Бабай и Семереди доказывают, что каждый элемент конечной группы грамм имеет SLP длины О(бревно²|грамм|) в каждой генераторной установке.

Эффективное решение проблема конструктивного членства имеет решающее значение для многих теоретико-групповых алгоритмов. В терминах SLP это можно сформулировать следующим образом. Для конечной группы грамм = ⟨S⟩ и грамм ∈ грамм, найдите прямолинейную программу вычисления грамм надS. Проблема конструктивного членства часто изучается в контексте группы черного ящика. Элементы кодируются битовыми строками фиксированной длины. Три оракулы предусмотрены для теоретико-групповых функций умножения, обращения и проверки на равенство с тождеством. А алгоритм черного ящика тот, который использует только эти оракулы. Следовательно, прямые программы для групп черного ящика являются алгоритмами черного ящика.

Явные прямые программы даны для множества конечных простых групп в онлайн Атлас конечных групп.

Определение

Неформальное определение

Позволять грамм конечная группа и пусть S быть подмножеством грамм. Последовательность L = (грамм₁,…,грамм_м) элементов грамм это прямолинейная программа над S если каждый грамм_я можно получить по одному из следующих трех правил:

1. грамм_я ∈ S
2. грамм_я = грамм_j ${\displaystyle \cdot }$ грамм_k для некоторых j,k < я
3. грамм_я = грамм⁻¹
   _j для некоторых j < я.

Прямая Стоимость c(грамм|S) элемента грамм ∈ грамм длина кратчайшей прямой программы по S вычисление грамм. Стоимость бесконечна, если грамм не входит в подгруппу, порожденную S.

Прямолинейная программа похожа на вывод в логике предикатов. Элементы S соответствуют аксиомам, а групповые операции соответствуют правилам вывода.

Формальное определение

Позволять грамм конечная группа и пусть S быть подмножеством грамм. А прямолинейная программа длины м над S вычисляя некоторые грамм ∈ грамм представляет собой последовательность выражений (ш₁,…,ш_м) такой, что для каждого я, ш_я является символом некоторого элемента S, или же ш_я = (ш_j, -1) для некоторых j < я, или же ш_я = (ш_j,ш_k) для некоторых j,k < я, так что ш_м принимает значение грамм при оценке в грамм очевидным образом.

Исходное определение, появляющееся в ^[2] требует, чтобы грамм =⟨S⟩. Приведенное выше определение является общим обобщением этого.

С вычислительной точки зрения формальное определение прямой программы имеет некоторые преимущества. Во-первых, последовательность абстрактных выражений требует меньше памяти, чем термы в генерирующем наборе. Во-вторых, он позволяет строить прямолинейные программы в одном представлении грамм и оценивается в другом. Это важная особенность некоторых алгоритмов.^[2]

Примеры

В группа диэдра D₁₂ группа симметрий шестиугольника. Оно может быть создано поворотом ρ на 60 градусов и одним отражением λ. В крайнем левом столбце ниже приводится прямая программа для λρ³:

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

λ - генератор. ρ - образующая. Второе правило: (2). (2) Второе правило: (3). (2) Второе правило: (1). (4)

В S₆, группу перестановок из шести букв, мы можем взять α = (1 2 3 4 5 6) и β = (1 2) в качестве образующих. В крайнем левом столбце приведен пример прямой программы для вычисления (1 2 3) (4 5 6):

α β α^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)

Приложения

Краткие описания конечных групп. Прямые программы могут быть использованы для изучения сжатия конечных групп с помощью логика первого порядка. Они предоставляют инструмент для построения "коротких" предложений, описывающих грамм (т.е. намного короче, чем |грамм|). Более подробно, SLP используются для доказательства того, что каждая конечная простая группа имеет описание первого порядка длины О(журнал |грамм|), и каждая конечная группа грамм имеет описание длины первого порядка О(бревно³|грамм|).^[3]

Прямолинейные программы, вычисляющие порождающие для максимальных подгрупп конечных простых групп. Онлайн-атлас представлений конечных групп^[4] предоставляет абстрактные линейные программы для вычисления производящих наборов максимальных подгрупп для многих конечных простых групп.

Пример: Группа Sz (32), принадлежащая бесконечному семейству Группы Suzuki, имеет ранг 2 по образующим а и б, куда а имеет порядок 2, б имеет порядок 4, ab имеет порядок 5, ab² имеет порядок 25 и Abab²ab³ имеет порядок 25. Ниже приводится прямолинейная программа, которая вычисляет набор порождающих для максимальной подгруппы E₃₂${\displaystyle \cdot }$E₃₂${\displaystyle \rtimes }$C₃₁. Эту прямолинейную программу можно найти в онлайн-АТЛАСЕ представительств конечных групп.

а б ab abb Ababb ababbb (abb)^18 (abb)^−18 (abb)^−18б (abb)^−18б(abb)^18 (Ababb)^14 (Ababb)^−14 (Ababb)^−14ababbb (Ababb)^−14ababbb(Ababb)^14

а генератор. б генератор. Второе правило: (1). (2) Второе правило: (3). (2) Второе правило: (3). (4) Второе правило: (5). (2) Повторяется второе правило: (4) умножить 18 раз Третье правило: (7) обратное Второе правило: (8). (2) Второе правило: (9). (7) Повторяется второе правило: (5) умножается в 14 раз Третье правило: (11) обратное Второе правило: (12). (6) Второе правило: (13). (11)

Теорема о достижимости

Теорема о достижимости утверждает, что для конечной группы грамм создано S, каждый грамм ∈ грамм имеет максимальную стоимость (1 + LG |грамм|)². Это можно понимать как ограничение сложности создания группового элемента из генераторов.

Здесь функция lg (Икс) является целочисленной версией функции логарифмирования: для k≥1 пусть lg (k) = max {р : 2^р ≤ k}.

Идея доказательства состоит в построении множества Z = {z₁,…,z_s} который будет работать как новая генераторная установка (s будут определены в процессе). Обычно он больше, чем S, но любой элемент грамм можно выразить как слово длиной не более 2|Z| над Z. Набор Z строится путем индуктивного определения возрастающей последовательности множеств K(я).

Позволять K(я) = {z₁^α₁·z₂^α₂·…·z_я^α_я : α_j ∈ {0,1}}, где z_я добавлен ли элемент группы в Z на я-й шаг. Позволять c(я) обозначают длину кратчайшей прямой программы, содержащей Z(я) = {z₁,…,z_я}. Позволять K(0) = {1_грамм} и c(0) = 0. Определим множество Z рекурсивно:

• Если K(я)⁻¹K(я) = граммобъявить s принять ценность я и остановись.
• В противном случае выберите несколько z_я+1 ∈ грамм\K(я)⁻¹K(я) (который не является пустым), что минимизирует «увеличение стоимости» c(я+1) − c(я).

Таким образом, Z определен таким образом, что любой грамм ∈ грамм можно записать как элемент K(я)⁻¹K(я), что существенно упрощает создание из Z.

Теперь нам нужно проверить следующее утверждение, чтобы гарантировать, что процесс завершится в пределах lg (|грамм|) много шагов:

Утверждение 1 — Если я < s тогда |K(я+1)| = 2|K(я)|.

Доказательство —

Немедленно, что |K(я+1)| ≤ 2|K(я)|. Теперь предположим от противоречия, что |K(я+1)| < 2|K(я)|. По принципу ячейки есть k₁,k₂ ∈ K(я+1) с k₁ = z₁^α₁·z₂^α₂·…·z_я+1^α_я+1 = z₁^β₁·z₂^β₂·…·z_я+1^β_я+1 = k₂ для некоторых α_j,β_j ∈ {0,1}. Позволять р - наибольшее целое число такое, что α_р ≠ β_р. Предположим, что WLOG α_р = 1. Отсюда следует, что z_р = z_п^−α_п·z_п-1^−α_п-1·…·z₁^−α₁·z₁^β₁·z₂^β₂·…·z_q^β_q, с п,q < р. Следовательно z_р ∈ K(р−1)⁻¹K(р - 1); противоречие.

Следующее утверждение используется, чтобы показать, что стоимость каждого элемента группы находится в пределах требуемой границы.

Утверждение 2 —  c(я) ≤ я ² − я.

Доказательство —

С c(0) = 0 достаточно показать, что c(я+1) - c(я) ≤ 2я. В Граф Кэли из грамм связано и если я < s, K(я)⁻¹K(я) ≠ грамм, то есть элемент вида грамм₁·грамм₂ ∈ грамм \ K(я)⁻¹K(я) с грамм₁ ∈ K(я)⁻¹K(я) и грамм₂ ∈ S.

Требуется не более 2я шаги для создания грамм₁ ∈ K(я)⁻¹K(я). Нет смысла генерировать элемент максимальной длины, так как он тождественный. Следовательно 2я −1 шагов хватит. Чтобы генерировать грамм₁·грамм₂ ∈ грамм\K(я)⁻¹K(я), 2я шагов достаточно.

Завершим теорему. С K(s)⁻¹K(s) = грамм, любой грамм ∈ грамм можно записать в виде k⁻¹
₁·k₂ с k⁻¹
₁,k₂ ∈ K(s). По следствию 2 нам понадобится не более s² − s шаги для создания Z(s) = Z, и не более 2s − 1 шаги для создания грамм из Z(s).

Следовательно c(грамм|S) ≤ s² +  s - 1 ≤ lg²|грамм| + LG |грамм| - 1 ≤ (1 + lg |грамм|)².

Рекомендации

1. Бабай, Ласло и Эндре Семереди. «О сложности матричных групповых задач I.» Основы компьютерных наук, 1984. 25-й ежегодный симпозиум по основам компьютерных наук. IEEE, 1984 г.
2. Ákos Seress. (2003). Алгоритмы группы перестановок. [В сети]. Кембриджские трактаты по математике. (№ 152). Кембридж: Издательство Кембриджского университета.
3. Nies, A., & Tent, K. (2016). Описание конечных групп короткими предложениями первого порядка. Исраэль Дж. Математика, чтобы появиться. https://arxiv.org/abs/1409.8390
4. http://brauer.maths.qmul.ac.uk/Atlas/v3/