Числовая полугруппа
В математике числовая полугруппа — это особый вид полугруппы . Его базовый набор — это набор всех неотрицательных целых чисел, кроме конечного числа, а бинарная операция — это операция сложения целых чисел. Кроме того, целое число 0 должно быть элементом полугруппы. Например, хотя набор {0, 2, 3, 4, 5, 6, ...} является числовой полугруппой, набор {0, 1, 3, 5, 6, ...} таковым не является, потому что 1 в наборе, а 1 + 1 = 2 в наборе нет. Числовые полугруппы являются коммутативными моноидами и также известны как числовые моноиды . [1] [2]
Определение числовой полугруппы тесно связано с проблемой определения целых неотрицательных чисел, которые можно выразить в виде x 1 n 1 + x 2 n 2 + ... + x r n r для заданного множества { n 1 , n 2 , ..., n r } целых положительных чисел и для произвольных целых неотрицательных чисел x 1 , x 2 , ..., x r . Эту проблему рассматривали несколько математиков, таких как Фробениус (1849–1917) и Сильвестр (1814–1897) в конце XIX века. [3] Во второй половине двадцатого века интерес к изучению числовых полугрупп возобновился из-за их приложений в алгебраической геометрии . [4]
Определение и примеры [ править ]
Определение [ править ]
Пусть N — множество неотрицательных целых чисел. Подмножество S группы N называется числовой полугруппой, если выполняются следующие условия.
- 0 — элемент S
- N − S , дополнение S в N , конечно.
- Если x и y находятся в S то x + y также находится в S. ,
Существует простой метод построения числовых полугрупп. Пусть A = { n 1 , n 2 , ..., n r } — непустое множество натуральных чисел. Набор всех целых чисел вида x 1 n 1 + x 2 n 2 + ... + x r n r является подмножеством N, порожденным A , и обозначается ⟨ A ⟩. Следующая теорема полностью характеризует числовые полугруппы.
Теорема [ править ]
Пусть S — подполугруппа группы N порожденная A. , Тогда S является числовой полугруппой тогда и только тогда, когда НОД ( A ) = 1. Более того, каждая числовая полугруппа возникает таким образом. [5]
Примеры [ править ]
Следующие подмножества N являются числовыми полугруппами.
- ⟨ 1 ⟩ = {0, 1, 2, 3, ...}
- ⟨ 1, 2 ⟩ = {0, 1, 2, 3, ...}
- ⟨ 2, 3 ⟩ = {0, 2, 3, 4, 5, 6, ...}
- Пусть а — целое положительное число. ⟨ а , а + 1, а + 2, ..., 2 а – 1 ⟩ = {0, а , а + 1, а + 2, а + 3, ...}.
- Пусть b — нечетное целое число, большее 1. Тогда ⟨ 2, b ⟩ = {0, 2, 4, . . . , б - 3 , б - 1, б , б + 1, б + 2, б + 3 , ...}.
- Хорошо темперированная гармоническая полугруппа H = {0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,...} [6]
Размерность внедрения, кратность [ править ]
Множество A представляет собой множество образующих числовой полугруппы ⟨ A ⟩. Множество образующих числовой полугруппы представляет собой минимальную системуобразующих, если ни одно из ее собственных подмножеств не порождает числовую полугруппу. Известно, чтокаждая числовая полугруппа S имеет единственную минимальную систему образующих, а также то, что эта минимальная система образующих конечна. Мощность минимального набора образующих называется размерностью вложения числовой полугруппы S и обозначается e ( S ). Наименьший член минимальной системы образующих называется кратностью числовой полугруппы S и обозначается m ( S ).
и Фробениуса род Число
связано несколько примечательных чисел С числовой полугруппой S .
- Множество N − S называется множеством пробелов в S и обозначается G ( S ).
- Число элементов в множестве пробелов G ( S ) называется родом S (или степенью особенности S ) и обозначается g ( S ).
- Наибольший элемент в ( S ) называется числом Фробениуса S S и обозначается F ( G ).
- Наименьший элемент S, такой, что все большие целые числа также являются элементами S, называется проводником; это F ( S ) + 1.
Примеры [ править ]
Пусть S = ⟨ 5, 7, 9 ⟩. Тогда у нас есть:
- Набор элементов в S : S = {0, 5, 7, 9, 10, 12, 14, ...}.
- Минимальный набор образующих S : {5, 7, 9}.
- Размерность вложения S : e ( S ) = 3.
- Кратность S : m ( S ) = 5.
- Множество пробелов в S : G ( S ) = {1, 2, 3, 4, 6, 8, 11, 13}.
- Число Фробениуса S равно F ( S ) = 13, а его проводник равен 14.
- Род S : g ( S ) = 8.
Числовые полугруппы с малым числом или родом Фробениуса
| н | Полугруппа S с F ( S ) = n | Полугруппа S с г ( S ) знак равно п |
|---|---|---|
| 1 | ⟨ 2, 3 ⟩ | ⟨ 2, 3 ⟩ |
| 2 | ⟨ 3, 4, 5 ⟩ | ⟨ 3, 4, 5 ⟩ ⟨ 2, 5 ⟩ |
| 3 | ⟨ 4, 5, 6, 7 ⟩ ⟨ 2, 5 ⟩ | ⟨ 4, 5, 6, 7 ⟩ ⟨ 3, 5, 7 ⟩ ⟨ 3, 4 ⟩ ⟨ 2, 7 ⟩ |
| 4 | ⟨ 5, 6, 7, 8, 9 ⟩ ⟨ 3, 5, 7 ⟩ | ⟨ 5, 6, 7, 8, 9 ⟩ ⟨ 4, 6, 7, 9 ⟩ ⟨ 3, 7, 8 ⟩ ⟨ 4, 5, 7 ⟩ ⟨ 4, 5, 6 ⟩ ⟨ 3, 5, ⟩ ⟨ 2, 9 ⟩ |
Вычисление числа Фробениуса [ править ]
Числовые полугруппы с вложенной размерностью два
Сильвестру были известны следующие общие результаты. [7] Пусть a и b — целые положительные числа такие, что НОД ( a , b ) = 1. Тогда
- F (⟨ а , б ⟩) знак равно ( а - 1) ( б - 1) - 1 знак равно ab - ( а + б ).
- г (⟨ а , б ⟩) знак равно ( а - 1) ( б - 1) / 2.
Числовые полугруппы с вложенной размерностью три [ править ]
Не существует известной общей формулы для вычисления числа Фробениуса числовых полугрупп, имеющих размерность вложения три или более. Невозможно найти полиномиальную формулу для вычисления числа или рода Фробениуса числовой полугруппы с размерностью вложения три. [8] Каждое положительное целое число является числом Фробениуса некоторой числовой полугруппы с размерностью вложения три. [9]
Алгоритм Рёдсета [ править ]
Следующий алгоритм, известный как алгоритм Рёдсета, [10] [11] может использоваться для вычисления числа Фробениуса числовой полугруппы S, порожденной { a 1 , a 2 , a 3 }, где a 1 < a 2 < a 3 и НОД ( a 1 , a 2 , a 3 ) = 1. Его сложность в худшем случае не так хороша, как алгоритм Гринберга [12] но это гораздо проще описать.
- Пусть s 0 — единственное целое число такое, что a 2 s 0 ≡ a 3 mod a 1 , 0 ≤ s 0 < a 1 .
- Алгоритм непрерывной дроби применяется к отношению a 1 / s 0 :
- а 1 знак равно q 1 s 0 - s 1 , 0 ≤ s 1 < s 0 ,
- s 0 знак равно q 2 s 1 - s 2 , 0 ≤ s 2 < s 1 ,
- s 1 знак равно q 3 s 2 - s 3 , 0 ≤ s 3 < s 2 ,
- ...
- s м −1 знак равно q м +1 s м ,
- с м +1 = 0,
- где q i ≥ 2, s i ≥ 0 для всех i.
- Пусть p -1 = 0, p 0 = 1, p i +1 = q i +1 p i - p i -1 и r i = ( s i a 2 - p i a 3 )/ a 1 .
- Пусть v — уникальное целое число такое, что r v +1 ≤ 0 < r v , или, что то же самое, уникальное целое число, такое что
- s v +1 / p v +1 ≤ a 3 / a 2 < s v / p v ·
- Тогда F ( S ) = - a 1 + a 2 ( s v - 1) + a 3 ( p v +1 - 1) - min { a 2 s v +1 , a 3 p v }.
числовых классы полугрупп Специальные
Неприводимая числовая полугруппа — это такая числовая полугруппа, которую нельзя записать как пересечение двух числовых полугрупп, собственно содержащих ее. Численная полугруппа S неприводима тогда и только тогда, когда S максимальна по включению множеств в совокупности всех числовых полугрупп с числом Фробениуса F ( S ).
Числовая полугруппа S называется симметричной , если она неприводима и ее число Фробениуса F ( S ) нечетно. Мы говорим, что псевдосимметрична S , если S неприводима и F(S) четна. Такие числовые полугруппы имеют простые характеристики в терминах числа и рода Фробениуса:
- Числовая полугруппа S симметрична тогда и только тогда, когда g ( S ) = ( F ( S ) + 1)/2.
- Числовая полугруппа S псевдосимметрична тогда и только тогда, когда g ( S ) = ( F ( S ) + 2)/2.
См. также [ править ]
Ссылки [ править ]
- ^ Гарсия-Санчес, П.А. «Миникурс числовых полугрупп» . Проверено 6 апреля 2011 г.
- ^ Финч, Стивен. «Моноиды натуральных чисел» (PDF) . Проект алгоритмов INRIA . Проверено 7 апреля 2011 г.
- ^ Х. К. Росалес и П. А. Гарсия-Санчес (2009 г.). Числовые полугруппы . Спрингер. ISBN 978-1-4419-0159-0 .
- ^ В. Баруччи; и др. (1997). «Свойства максимальности в числовых полугруппах и приложения к одномерным аналитически неприводимым локальным областям». Воспоминания амер. Математика. Соц . 598 .
- ^ Гарсиа-Санчес, Х. К. Росалес, Пенсильвания (2009). Числовые полугруппы (Первое изд.). Нью-Йорк: Спрингер. п. 7. ISBN 978-1-4419-0160-6 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ М. Брас-Аморос (2019). «Закаленные моноиды действительных чисел, золотой фрактальный моноид и хорошо закаленная гармоническая полугруппа» . Полугрупповой форум . 99 (2): 496–516. arXiv : 1703.01077 . дои : 10.1007/s00233-019-10059-4 . S2CID 253781462 .
- ^ Джей Джей Сильвестр (1884). «7382» . Математика из Educational Times с дополнительными статьями и решениями. Образовательные времена . 41:21 .
- ^ Ф. Кертис (1990). «О формулах для числа Фробениуса числовой полугруппы» . Математика Скандинавия . 67 (2): 190–192. doi : 10.7146/math.scand.a-12330 . Проверено 18 марта 2019 г.
- ^ Дж. К. Росалес; и др. (2004). «Каждое положительное целое число является числом Фробениуса числовой полугруппы с тремя образующими» . Математика Скандинавия . 94 (1): 5–12. дои : 10.7146/math.scand.a-14427 . Проверено 14 марта 2015 г.
- ^ Х. Л. Рамирес Альфонсин (2005). Диофантова задача Фробениуса . Издательство Оксфордского университета. стр. 4–6 . ISBN 978-0-19-856820-9 .
- ^ О.Дж. Рёдсет (1978). «О линейной диофантовой задаче Фробениуса». Дж. Рейн Анжью. Математика. 301 : 171–178.
- ^ Гарольд Гринберг (1988). «Решение линейного диофантова уравнения для целых неотрицательных чисел». Журнал алгоритмов . 9 (3): 343–353. дои : 10.1016/0196-6774(88)90025-9 .