Equivalence of primitive sets.pdf Основные обозначения: N — множество натуральных чисел, k, n Е N, A = {a1,..., ak} С N; (a1,..., ak) —наибольший общий делитель чисел a1,..., ak; (a1,... , ak) — аддитивная полугруппа, порождённая множеством {a1,... , ak}; n{a1,..., ak} = {na1,..., nak}; A(i) = {a1,..., a*}, C(A(i)) = d*No \ (A(i)), d% = (ab ..., a*), i = 2,..., k. Множество A = {a1,...,ak} натуральных чисел, k > 1, называется примитивным, если (a1,..., ak) = 1. Функция Фробениуса g(a1,...,a^) определена на всех примитивных множествах {a1,..., afc} как наибольшее натуральное число t G (a1,..., a^) —число, не представи-мое в виде линейной комбинации чисел a1,... , a^ (рассматриваются линейные комбинации только с целыми неотрицательными коэффициентами): g(a1,..., ak) = max{t G N : t = n1a1 + ... + nkak}. Число Фробениуса g(A) = maxC(A), где C(A) = C(A(k)) —множество всех натуральных чисел, не представимых линейными комбинациями чисел a1,..., a^. Задача определения g(a1,...,a^) известна как диофантова проблема Фробениуса (ПФ). Задача определения множества C(A) называется расширенной проблемой Фробениуса (РПФ). При k = 2 описание множества C(A) и формула числа Фробениуса даны Дж. Сильвестром [1] ещё в 1884 г., формула числа Фробениуса имеет вид g(a1, a2) — a1a2 — a1 — a2. При k > 2 алгоритмы РПФ до недавнего времени не исследовались, в то же время активно изучался порядок множества C(A) и некоторые его свойства [2, гл.5]. В [3] представлен алгоритм РПФ и дана оценка его сложности. Намного активнее исследовалась ПФ. Вместе с тем прогресс в получении формул следует признать умеренным, получены формулы только для множеств частного вида при k = 3,4. Эти трудности в определённой мере объяснимы; показано [4], что уже при k = 3 не существует конечного числа полиномов, позволяющих выразить через них число Фробениуса g(a1, a2, a3) с помощью разбиения области определения. Более продуктивным стал алгоритмический подход к определению g(a1,...,a^). Построен ряд алгоритмов как при k = 3 (O. Rodseth, J. Davison и др. [2]), так и при произвольном k. В работах [5, 6] разработан алгоритм вычисления функции Фробениуса при любом k с помощью экспоненцирования неотрицательной матрицы M порядка a^ и определения её экспонента с использованием соотношения g(a1,..., a^) = exp M - a^. Вычислительная сложность алгоритма в битовых операциях равна O(a|), требуемая память — O(a| log ak) битов. В [7] предложено (без обоснования корректности) улучшение этого алгоритма со сложностью O(a|). В [8] построен теоретико-графовый алгоритм определения g(a1,... , a^) со сложностью O(a1(k+log a1)) арифметических операций. В [9] эта оценка снижена до величины порядка O(ka1) операций. В [3] на основе исследования отношений эквивалентности предложена редукция РПФ и ПФ для множества A к РПФ и ПФ соответственно для собственного подмножества порядка h, где 2 ^ h ^ min(k,a1). Редукция позволила снизить оценку O(ka1) до величины О(/(А) + ha1) арифметических операций, /(A) ^ k — характеристика множества A. Исследования отношений эквивалентности в данной работе получили дальнейшее развитие. 1. Эквивалентность множеств, k > 2 Примитивное множество A = {a1,...,a^} рассмотрим как возрастающую последовательность, где 1 < a1 < ... < afc. Числа ai и aj множества A назовём a1-эквива-лентными, если ai = aj (mod a1). Примитивное множество A = {a1,... , a^} разбивается на h классов a 1-эквивалентности, где 2 ^ h ^ min{k, a1}. Трансверсал множества A по отношению a1 -эквивалентности, состоящий из наименьших чисел классов, назовём a1-трансверсалом множества A и обозначим A/a1. Обозначим W(A/a1) последовательность порядковых номеров i ^ 2 чисел a1-трансверсала. Множество A называется приведённым, если ai Е (A(i-1)), i = 2,..., k. Неприве-дённое примитивное множество A содержит приведённые примитивные подмножества. Построим приведённое подмножество Ba С A, называемое A-базисом: a1 Е Ba; a2 Е Ba, если и только если a2 не кратно a1; пусть из {a1,..., ai-1} в подмножество Ba включены числа b1,..., bj, тогда ai Е Ba, если и только если di-1 > di или (di-1 = di и ai Е C(b1,... , bj)), i = 3,... , k. Обозначим W(Ba) последовательность порядковых номеров i чисел A-базиса. Наименьшее натуральное p(A), такое, что dp(A) — 1, называется индексом примитивности множества A. Положим p(A) = p, тогда p ^ k, dp = ... = dk =1. Последовательность порядковых номеров i Е {2,... ,p}, таких, что di-1 > di, обозначим L(A). Подмножества D и D' множества A эквивалентны (g-эквивалентны), если (D) = (D') (если g(D) = g(D')); будем это отношение обозначать D = D' (соответственно D =g D'). Тогда D = D', если и только если C(D) = C(D'), и если D = D', то g(D) = g(D'). Утверждение 1. BA С A/a1 С A, BA = A/a1 = A, где |BA| ^ |A/a1| ^ min{k,a1}; оценка достижима. Следствие 1. Множество A = {a1,...,ak} содержит эквивалентное подмножество порядка не больше min{k, a1}. Пример 1 (построение A/a1). Для A = {5,13,18, 20, 38} считаем по mod 5: 5 = 20, 13 = 18 = 38, тогда A/5 = {5,13}. Пусть a1 ^ 3 и A = A/a1, т.е. k ^ a1 и числа a1,..., ak несравнимы по модулю a1; L(A) = {n2,..., nr}, 1 < r < k, т. е. dnj-1 > dnj, j = 2,..., r. Тогда A разбивается на r отрезков A1,..., Ar, где Aj = (anj,..., anj+1-1), j = 1,..., r, n1 = 1, nr = p, nr+1 = k + 1. Обозначим J1 = A1 \ {a1}, J (A) —множество чисел ai Е A, таких, что di-1 = di и ai не делит ни одно число из C(A(i-1)) (т. е. J(A) С {n2 + 1,... , k} \ {n2,... , nr}), W(J) — последовательность порядковых номеров чисел из J (A). Далее без ущерба для общности считаем, что n2 = 2. Приведём некоторые известные свойства. Утверждение 2. 1) Если B С A и A \ B С (B), то A = B. 2) Множество A(i)/di={a1/di,..., ai/di} примитивное, (A(i))=di(A(i)/di), i=2,..., k. 3) g(a1,..., ak) ^ (a1 — 1)(ak — 1) — 1 [2, теорема 3.1.1]. Теорема 1. A = A \ J (A); если n2 > 2, то A = A \ (J1 U J (A)). Обозначим Yj = dnj((a1/dnj — 1)(anj/dnj — 1) — 1), /1 = 1, /j —наибольший номер, такой, что nj ^ /j < nj+1 и aj ^ Yj (при a1 ^ 3 условия корректны в силу утверждения 2; S1 = (a1), Sj = (anj,... , a\j), т.е. отрезок Sj составлен из первых (наименьших) /j — nj + 1 чисел отрезка Aj, j = 2,..., r; S(A) есть конкатенация отрезков S1,S2,...,Sr, /(A) = |S(A)|. Следствие 2. A = S(A), /(A) ^ min{k , a1 ap — a1 — 2ap + p}, где p — p(A). Алгоритмы построения A/a1 и A \ S(A) являются полиномиальными. Алгоритм построения A \ J(A) экспоненциальный, по сложности он равносилен решению расширенной проблемы Фробениуса [3]. Пример 2. Пусть A = {5,13,18, 20, 57}. Вычисляем A/5 = {5,13, 57}, J (A/5) : L(A/5) = {13}, r = 2, A1 = {5}, A2 = {13,52}, y2 = 47 < 57. Тогда J (A/5) = {57}, (A/5) \ J (A/5) = {5,13}. Окончательно A = {5,13}. 2. Эквивалентность примитивных пар чисел Обозначим через [A] класс g-эквивалентности, содержащий примитивное множество A; [A]m — класс всех примитивных множеств порядка m, g-эквивалентных A, m =2, 3,... Теорема 2. Пусть (a,b) —примитивная пара чисел. Тогда [(a, b)]2 = (a + 5, b + е) : a - b +1 < e < 0, 5 = (1 - a)e/(b + e - 1) G N; 1 - a < 5 < 0, e = (1 - b)5/(a + 5 - 1) G N. Следствие 3. Если a > 2, то (2, g(a, b) + 2) G [(a, b)]2; если a > 3, то (3, (g(a, b) + 3)/2) G [(a, b)]2. Пример 3. Построим множество [(13,22)]2, g(13,22) = 251. При 5> 0 имеем -8 < e < 0, при e > 0 имеем -12 < 5 < 0. £ -7 -6 -5 -4 -3 -2 -1 6 6 72/15 60/16 48/17 2 24/19 12/20 £ 21/11 42/10 7 84/8 15 21 147/5 42 63 105 231 6 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 Согласно таблице, (5, е) G {(2, -3), (6, -7)}. Паре (13,22) g-эквивалентна примитивная приведённая упорядоченная пара (15,19). Пара (19,15) исключена из класса [(13, 22)]2, так как не упорядочена. Тогда (5,е) G {(-3, 7), (-5,15), (-6, 21), (-8, 42), (-9, 63), (-10,105), (-11, 231)} и (13,22) g-эквивалентна парам (10,29), (8,37), (7,43), (5,64), (4,85), (3,127) и (2,253). Класс g-эквивалентности [(13, 22)]2 содержит (вместе с (13,22)) 9 пар. Вывод: Отношения эквивалентности примитивных множеств позволяют сократить сложность решения РПФ и ПФ с помощью полиномиального алгоритма редукции примитивного множества A к подмножеству B = (A/a1) \ S(A/a1). Сложность экспо-ненцирования неотрицательной матрицы [5, 6] имеет в сочетании с редукцией оценку О (a3), где a = max B. Оценка Боккера — Липтак [9] понижается до величины порядка о(/^) + ha1), где h = |B|.

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