Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математике числовая полугруппа - это особый вид полугруппы . Его базовый набор - это набор всех неотрицательных целых чисел, кроме конечного числа, а бинарная операция - это операция сложения целых чисел. Также целое число 0 должно быть элементом полугруппы. Например, в то время как набор {0, 2, 3, 4, 5, 6, ...} является числовой полугруппой, набор {0, 1, 3, 5, 6, ...} не является в наборе и 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) в конце 19 века. [3] Во второй половине двадцатого века интерес к изучению числовых полугрупп вновь проявился в связи с их приложениями в алгебраической геометрии . [4]

Определение и примеры [ править ]

Определение [ править ]

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

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

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

Теорема [ править ]

Пусть S быть подполугруппой N , порожденный A . Тогда S является числовой полугруппой тогда и только тогда, когда gcd ( A ) = 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. Пусть a - натуральное число. ⟨ , + 1 + 2, ..., 2 - 1⟩ = {0, , + 1 + 2, + 3, ...}.
  5. Пусть б нечетное целое число , большее 1. Тогда ⟨2, б ⟩ = {0, 2, 4,. . . , b - 3, b - 1, b , b + 1, b + 2, b + 3, ...}.
  6. Хорошо темперированная гармоническая полугруппа H = {0,12,19,24,31,34,36,38,40,42,43,45,46,47,48, ...} [6]

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

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

Число и род Фробениуса [ править ]

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

  1. Множество N - S называется множеством лаков в S и обозначается G ( S ).
  2. Число элементов в множестве промежутков G ( S ) называется родом S (или степенью сингулярности S ) и обозначается g ( S ).
  3. Наибольший элемент в G ( 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  : 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
   с g ( S ) = n   
   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 - натуральные числа такие, что gcd ( 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 и gcd ( 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 ,
    • ...
    • с м −1 = q м +1 с м ,
    • с м +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.

См. Также [ править ]

  • Число Фробениуса
  • Специальные классы полугрупп
  • Полугруппа
  • Серебряная чеканка

Ссылки [ править ]

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