Числовая полугруппа - Numerical semigroup

В математике числовая полугруппа особый вид полугруппа. Его основная набор это множество всех неотрицательных целые числа кроме конечный число и бинарная операция это операция добавление целых чисел. Кроме того, целое число 0 должен быть элементом полугруппы. Например, в то время как набор {0, 2, 3, 4, 5, 6, ...} является числовой полугруппой, набор {0, 1, 3, 5, 6, ...} не является в наборе и 1 + 1 = 2 нет в наборе. Числовые полугруппы коммутативный моноиды и также известны как числовые моноиды.[1][2]

Определение числовой полугруппы тесно связано с проблемой определения неотрицательных целых чисел, которые могут быть выражены в виде Икс1п1 + Икс2 п2 + ... + Икср пр для данного набора {п1, п2, ..., пр} натуральных чисел и произвольных неотрицательных целых чисел Икс1, Икс2, ..., Икср. Эту задачу рассматривали несколько математиков, например Фробениус (1849-1917) и Сильвестр (1814 - 1897) в конце 19 века.[3] Во второй половине двадцатого века интерес к изучению числовых полугрупп возродился благодаря их приложениям в алгебраическая геометрия.[4]

Определение и примеры

Определение

Позволять N - множество неотрицательных целых чисел. Подмножество S из N называется числовой полугруппой, если выполняются следующие условия.

  1. 0 является элементом S
  2. N − S, дополнение S в N, конечно.
  3. Если Икс и у находятся в S тогда х + у также в S.

Существует простой метод построения числовых полугрупп. Позволять А = {п1, п2, ..., пр} - непустой набор натуральных чисел. Множество всех целых чисел вида Икс1 п1 + Икс2 п2 + ... + Икср пр это подмножество N создано А и обозначается ⟨ А ⟩. Следующая теорема полностью характеризует числовые полугруппы.

Теорема

Позволять S - подполугруппа N создано А. потом S является числовой полугруппой тогда и только тогда, когда gcd (А) = 1. Более того, так возникает всякая числовая полугруппа.[5]

Примеры

Следующие подмножества N являются числовыми полугруппами.

  1. ⟨ 1 ⟩ = {0, 1, 2, 3, ...}
  2. ⟨ 1, 2 ⟩ = {0, 1, 2, 3, ...}
  3. ⟨ 2, 3 ⟩ = {0, 2, 3, 4, 5, 6, ...}
  4. Позволять а быть положительным целым числом. ⟨ а, а + 1, а + 2, ... , 2а - 1 ⟩ = {0, а, а + 1, а + 2, а + 3, ...}.
  5. Позволять б - нечетное целое число больше 1. Тогда ⟨2, б ⟩ = {0, 2, 4, . . . , б − 3 , б − 1, б, б + 1, б + 2, б + 3 , ...}.
  6. Спокойный гармонический полугруппа ЧАС={0,12,19,24,31,34,36,38,40,42,43,45,46,47,48,...} [6]

Размер вложения, кратность

Набор А является набором образующих числовой полугруппы ⟨ А ⟩. Набор образующих числовой полугруппы является минимальной системой образующих, если ни одно из его собственных подмножеств не порождает числовую полугруппу. Известно, что всякая числовая полугруппа S имеет единственную минимальную систему образующих, а также то, что эта минимальная система образующих конечна. Мощность минимального набора образующих называется мощностью размер встраивания числовой полугруппы S и обозначается е(S). Наименьший член минимальной системы образующих называется множественность числовой полугруппы S и обозначается м(S).

Число и род Фробениуса

Есть несколько примечательных чисел, связанных с числовой полугруппой S.

  1. Набор N − S называется набором промежутков в S и обозначается грамм(S).
  2. Количество элементов в наборе зазоров грамм(S) называется родом S (или степень сингулярности S) и обозначается грамм(S).
  3. Величайший элемент в грамм(S) называется Число Фробениуса из S и обозначается F(S).
  4. Самый маленький элемент S такие, что все большие целые числа также являются элементами S называется дирижером; это F(S) + 1.

Примеры

Позволять S = ⟨5, 7, 9⟩. Тогда у нас есть:

  • Набор элементов в S : S = {0, 5, 7, 9, 10, 12, 14, ...}.
  • Минимальный набор образующих S : {5, 7, 9}.
  • Вложение размерности S : е(S) = 3.
  • Кратность S : м(S) = 5.
  • Набор зазоров в S : грамм(S) = {1, 2, 3, 4, 6, 8, 11, 13}.
  • Число Фробениуса S является F(S) = 13, а его проводник - 14.
  • Род S : грамм(S) = 8.

Числовые полугруппы с малым числом или родом Фробениуса

   п   Полугруппа S
с F(S) = п   		Полугруппа 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][неудачная проверка ] Позволять а и б натуральные числа такие, что gcd (а, б) = 1. Тогда

  • F(⟨ а, б ⟩) = (а − 1) (б − 1) − 1 = ab − (а + б).
  • грамм(⟨ а, б ⟩) = (а − 1)(б − 1) / 2.

Числовые полугруппы с размерностью вложения три

Не существует известной общей формулы для вычисления числа Фробениуса числовых полугрупп, имеющих размерность вложения три или более. Не существует полиномиальной формулы для вычисления числа Фробениуса или рода числовой полугруппы с размерностью вложения три.[8] Каждое натуральное число является числом Фробениуса некоторой числовой полугруппы с размерностью вложения три.[9]

Алгоритм Рёдсета

Следующий алгоритм, известный как алгоритм Рёдсета,[10][11] может использоваться для вычисления числа Фробениуса числовой полугруппы S создано {а1, а2, а3} куда а1 < а2 < а3 и gcd ( а1, а2, а3) = 1. Его сложность в наихудшем случае уступает алгоритму Гринберга.[12]но описать это гораздо проще.

  • Позволять s0 - единственное целое число такое, что а2s0 ≡ а3 мод а1, 0 ≤ s0 < а1.
  • Алгоритм непрерывной дроби применяется к соотношению а1/s0:
    • а1 = q1s0 − s1, 0 ≤ s1 < s0,
    • s0 = q2s1 − s2, 0 ≤ s2 < s1,
    • s1 = q3s2 − s3, 0 ≤ s3 < s2,
    • ...
    • sм−1 = qм+1sм,
    • sм+1 = 0,
куда qя ≥ 2, sя ≥ 0 для всех i.
  • Позволять п−1 = 0, п0 = 1, пя+1 = qя+1пя − пя−1 и ря = (sяа2 − пяа3)/а1.
  • Позволять v - уникальное целое число такое, что рv+1 ≤ 0 < рv, или, что то же самое, единственное целое число, такое
    • sv+1/пv+1 ≤ а3/а2 < sv/пv·
  • Потом, F(S) = −а1 + а2(sv − 1) + а3(пv+1 - 1) - min {а2sv+1, а3пv}.

Специальные классы числовых полугрупп

An неприводимая числовая полугруппа является числовой полугруппой, поэтому ее нельзя записать как пересечение двух числовых полугрупп, содержащих ее должным образом. Числовая полугруппа S неприводимо тогда и только тогда, когда S является максимальным по включению множества в совокупности всех числовых полугрупп с числом Фробениуса F(S).

Числовая полугруппа S является симметричный если оно неприводимо и его число Фробениуса F(S) нечетно. Мы говорим что S является псевдосимметричный при условии, что S неприводимо и F (S) четно. Такие числовые полугруппы имеют простую характеризацию в терминах числа и рода Фробениуса:

  • Числовая полугруппа S симметричен тогда и только тогда, когда грамм(S) = (F(S) + 1)/2.
  • Числовая полугруппа S псевдосимметричен тогда и только тогда, когда грамм(S) = (F(S) + 2)/2.

Смотрите также

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

  1. ^ Гарсия-Санчес, П.А. «Мини-курс числовых полугрупп». Получено 6 апреля 2011.
  2. ^ Финч, Стивен. «Моноиды натуральных чисел» (PDF). Проект алгоритмов INRIA. Получено 7 апреля 2011.
  3. ^ Дж. К. Росалес, П.А. Гарсия-Санчес (2009). Числовые полугруппы. Springer. ISBN  978-1-4419-0159-0.
  4. ^ В. Баруччи; и другие. (1997). «Свойства максимальности в числовых полугруппах и приложения к одномерным аналитически неприводимым локальным областям». Воспоминания амер. Математика. Soc. 598.
  5. ^ Гарсиа-Санчес, Х.С. Росалес, П.А. (2009). Числовые полугруппы (Первое. Изд.). Нью-Йорк: Спрингер. п. 7. ISBN  978-1-4419-0160-6.
  6. ^ М. Бра-Аморос (2019). «Закаленные моноиды действительных чисел, золотой фрактальный моноид и хорошо темперированная гармоническая полугруппа». Полугруппа Форум. 99: 496–516. arXiv:1703.01077. Дои:10.1007 / s00233-019-10059-4.
  7. ^ Дж. Дж. Сильвестр (1884). «Математические вопросы с их решениями». Образовательные времена. 41 (21).
  8. ^ Ф. Кертис (1990). «О формулах для числа Фробениуса числовой полугруппы». Mathematica Scandinavica. 67 (2): 190–192. Дои:10.7146 / math.scand.a-12330. Получено 18 марта 2019.
  9. ^ Дж. К. Росалес; и другие. (2004). «Каждое положительное целое число является числом Фробениуса числовой полугруппы с тремя образующими». Mathematica Scandinavica. 94: 5–12. Дои:10.7146 / math.scand.a-14427. Получено 14 марта 2015.
  10. ^ Х.Л. Рамирес Альфонсин (2005). Диофантова проблема Фробениуса. Издательство Оксфордского университета. стр.4 –6. ISBN  978-0-19-856820-9.
  11. ^ Ö.J. Рёдсет (1978). «О линейной диофантовой проблеме Фробениуса». J. Reine Angew. Математика. 301: 171–178.
  12. ^ Гарольд Гринберг (1988). «Решение линейного диофантова уравнения для целых неотрицательных чисел». Журнал алгоритмов. 9 (3): 343–353. Дои:10.1016/0196-6774(88)90025-9.