Оглавление
- 1 Числовая полугруппа
- 1.1 Определение числовой полугруппы
- 1.2 Примеры числовых полугрупп
- 1.3 Теорема о числовых полугруппах
- 1.4 Размерность вложения и кратность
- 1.5 Число и род Фробениуса
- 1.6 Примеры числовых полугрупп с малым числом Фробениуса или родом
- 1.7 Алгоритм Редсета
- 1.8 Специальные классы числовых полугрупп
- 1.9 Полный текст статьи:
- 2 Числовая полугруппа
Числовая полугруппа
-
Определение числовой полугруппы
- Числовая полугруппа — это подмножество неотрицательных целых чисел, за исключением конечного числа.
- Двоичная операция — сложение целых чисел.
- 0 должен быть элементом полугруппы.
-
Примеры числовых полугрупп
- Множество {0, 2, 3, 4, 5, 6, …} является числовой полугруппой.
- Множество {0, 1, 3, 5, 6, …} не является числовой полугруппой, так как 1 находится в наборе.
-
Теорема о числовых полугруппах
- Числовая полугруппа порождается набором натуральных чисел, если gcd (A) = 1.
- Каждая числовая полугруппа порождается уникальным набором образующих.
-
Размерность вложения и кратность
- Мощность минимального набора образующих называется размерностью вложения.
- Наименьший элемент в минимальной системе образующих называется кратностью.
-
Число и род Фробениуса
- Множество N − S называется множеством промежутков.
- Количество элементов в наборе пробелов называется родом.
- Наибольший элемент в G(S) называется числом Фробениуса.
-
Примеры числовых полугрупп с малым числом Фробениуса или родом
- Числовые полугруппы с размерностью вложения два имеют известные формулы для числа Фробениуса и рода.
- Числовые полугруппы с размерностью вложения три не имеют известных формул для числа Фробениуса или рода.
-
Алгоритм Редсета
- Алгоритм Редсета используется для вычисления числа Фробениуса числовой полугруппы.
- Сложность алгоритма в худшем случае ниже, чем у алгоритма Гринберга.
-
Специальные классы числовых полугрупп
- Неприводимая числовая полугруппа не может быть записана как пересечение двух числовых полугрупп.
- Симметричная числовая полугруппа имеет нечетное число Фробениуса и род, равный (F(S) + 1)/2.
- Псевдосимметричная числовая полугруппа имеет четное число Фробениуса и род, равный (F(S) + 2)/2.