Structural properties of primitive systems of natural numbers.pdf При исследовании перемешивающих свойств композиции преобразований конечно-го множества возникает задача распознавания примитивности квадратной неотрица-тельной матрицы M и определения её экспонента [1, 2], то есть наименьшего нату-рального числа Y, при котором M7 > 0.При изучении указанных свойств матрица M = (m,,) обладает ровно теми же свой-ствами, что и её носитель, то есть матрица v(M) = (vm,,), гдеvm,,1, если m,, > 0,0, если m,, = 0.Вместо матрицы M можно равносильным образом исследовать примитивность иэкспонент орграфа Г, матрица смежности вершин которого совпадает с v(M). За-метим, что множество 0,1-матриц порядка n образует полугруппу Gn относительнооперации *, где A * B = v(AB).Критерий примитивности орграфа определяется длинами его простых конту-ров [1]. Если C1, ..., Ck - все простые контуры орграфа Г длин l1, ..., lk соответ-ственно, то орграф Г примитивный, если и только если наибольший общий делительgcd(l1,... , lk) = 1. Таким образом, один из способов распознавания примитивностиорграфа Г состоит в определении длин /1, . . ., всех его простых циклов и в провер-ке примитивности набора чисел ( / 1 , . . . , ), где набор натуральных чисел примитивен,если и только если эти числа взаимно просты.Распознавание примитивности набора чисел (/1 , . . . ,) можно выполнить, приме-нив k - 1 раз алгоритм Евклида к элементам набора. Альтернативный подход состоитв использовании заранее составленной таблицы примитивных наборов при ограниче-нии на числа /1, . . . , .Работа посвящена исследованию свойств примитивных наборов чисел и задаче по-строения таблицы примитивных наборов при ограничении на числа /1, . . . , .Утверждение 1. Если A - примитивный набор чисел, то примитивен любой на-бор, полученный из A добавлением любого натурального числа или (при |A| > 1) уда-лением числа a, кратного одному из остальных чисел набора.Определение 1. Примитивный набор A размера k ^ 1 называется тупиковым,если A = (1) или при k > 1 удаление из набора любого элемента нарушает его прими-тивность.Определение 2. Примитивный набор A размера k > 1 называется r-примитив-ным, где 0 ^ r ^ k - 1, если после удаления из A любого подмножества порядка rпримитивность получившегося набора сохраняется.Рассмотрим набор натуральных чисел A = ( a 1 , . . . , ), где каждое из чисел наборане превышает m. Пусть 2A - булеан множества { a 1 , . . . , }, P(A,r) -множество всехпримитивных наборов порядка r из 2A, P(A) = (J P(A,r). На множестве P(A) опре-делим отношение частичного порядка: (b1 ,... , bi) ^ (a1 , . . . , ar), если и только если/ ^ r и найдется бесповторная упорядоченная выборка ( i 1 , . . . ,ii) из ( 1 , . . . , r), такая,что i1 < . . . < i и bj делит a^ для всех j = 1 , . . . , /.Определение 3. Тупиковый набор B Е P(A) называется минимальным в P(A),если не существует другого набора B' Е P(A), такого, что B' ^ B, и r-минимальнымв P(A), если не существует другого набора B' Е P(A) длины r, такого, что B' ^ B.Утверждение 2. Если A - примитивный набор, то (P(A), -верхняя полуре-шётка, в которой максимальный элемент есть A и любой минимальный элемент естьтупиковый минимальный набор.Для набора A рассмотрим наибольший общий делитель как функцию, опреде-лённую на 2a. При B = {aix , . . . , a i ; }Е 2a обозначим gcd(B ) = gcd(ai 1 ,... , ai ;), ес-ли B = 0, и gcd(0) = lcm(a1 , . . . , ak), где gcd(ai 1 , . . . , ai ; ) и lcm(ai 1 ,... , ai ; ) -наиболь-ший общий делитель и наименьшее общее кратное чисел ai1, . . . , ai; соответственно;D(A) = {gcd(B) : B Е 2A} . Множество D(A)частично упорядочено по отношению де-лимости: gcd(B) ^ gcd(B') для B , B ' Е 2A, если и только если gcd(B) делит gcd(B').Утверждение 3. Если A - примитивный тупиковый набор, то D(A) -решётка,антиизоморфная решётке 2A.Обозначим через A» коатомы решётки 2A и через ^ - атомы решётки D(A): A» == { a 1 , . . . , afc} \ {a»}, ^ = gcd(Aj), i = 1 , . . . , k.Теорема 1. Набор A - примитивный тупиковый, если и только если ,... , ^) -набор попарно взаимно простых чисел, отличных от 1. При этом a» = (ci^1 ... ^)где (c1,...,cfc) есть 1-примитивный набор натуральных чисел и g c d ^ , ^ ) = 1 дляi = 1 , . . . , k.Следствие 1. Примитивный тупиковый набор A является k-минимальным, еслии только если (^1 , . . . , ) -набор простых чисел и с, = 1 для i = 1 , . . . , k.По утверждению 1 любой примитивный набор A можно получить из соответству-ющего тупикового набора A' добавлением любого числа. По следствию 1 любой ту-пиковый набор A' можно получить из соответствующего k-минимального набора A"умножением элемента набора а, на число, взаимно простое с i G { 1 , . . . , k}.Алгоритм перечисления множества всех k-минимальных примитивных наборов, со-стоящих из чисел, не превышающих m, состоит в следующем. В соответствии с теоре-мой 1 и следствием 1 k-минимальный тупиковый примитивный набор A = ( а 1 , . . . , ад)состоит из чисел а, = . . . ^ г д е ( ^ 1 , . . . , ^ ) -набор различных простых чи-сел. Тогда если < . . . < ^, то достаточно перечислить все наборы (^1 , . . . , ^) сосвойством . . . ^k ^ m.В качестве перебираем все простые числа в пределах, указанных неравенствомm \ k-s+1где Ф, = p3 . . . p,; pn - n-е простое число. При 3 ^ s < k и каждом фиксированномнаборе чисел (^s+1 , . . . ) в качестве перебираем все простые числа в пределах,указанных в (1). При каждом фиксированном наборе чисел ) перебираемiвсе простые числа и где 2 ^ < < mk - 1 .Оценена вычислительная сложность алгоритма, измеренная числом построенныхнаборов различных простых чисел ). Количество таковых не превышает ( ( k-1 \- 1\O I mln k ln2 m Л Ф, I . При k > 2 для оценки величин Фд можно использоватьV V ,=2 ) )k! kоценку [3]: pk > k ln k. Тогда Фд > - П ln j.2 ,=3Значения Фд для k = 3 , . . . , 8 приведены в таблице.1k 3 4 5 6 7 85 35 385 5005 85085 1616615Данная таблица показывает, что при ограничении а1 , . . . , ад ^ m число k-мини-мальных примитивных наборов быстро убывает с ростом k.Рассмотренные свойства и алгоритм составления таблицы примитивных наборовмогут быть использованы для изучения перемешивающих свойств преобразований,в частности для вычисления экспонентов перемешивающих матриц и соответствующихграфов. Алгоритмические вопросы построения простых циклов в графе и вычисленияэкспонента орграфа рассмотрены более детально в [4].

Скачать электронную версию публикации