Содержание к диссертации
Введение
Глава 1. Мощности конечных критических решеток 19
1.1. Предварительные сведения 19
1.2. Описание конструкций n-элементных критических решеток для n = 7 и натуральных чисел n 9 29
1.3. Доказательство жесткости построенных n-элементных решеток для натуральных чисел n 9 33
1.4. Доказательство критичности построенных n-элементных решеток для натуральных чисел n 9 43
1.5. О существовании критической неразборной решетки 61
Глава 2. Неаксиоматизируемость класса критических решеток 67
2.1. Ультрастепень алгебраической системы по неглавному ультрафильтру 67
2.2. Конструкция счетной критической решетки 70
2.3. Доказательство арифметической незамкнутости класса критических решеток 74
Глава 3. Функция роста конечных жестких решеток 81
3.1. Описание конструкций жестких решеток 81
3.2. Доказательство экспоненциальности роста числа конечных жестких решеток 84
3.3. Описание алгоритма нахождения конечных строго жестких разборных решеток 89
Литература
- Описание конструкций n-элементных критических решеток для n = 7 и натуральных чисел n 9
- Доказательство критичности построенных n-элементных решеток для натуральных чисел n 9
- Конструкция счетной критической решетки
- Доказательство экспоненциальности роста числа конечных жестких решеток
Описание конструкций n-элементных критических решеток для n = 7 и натуральных чисел n 9
Итак, разборной является решетка, полученная из одноэлементной решетки с помощью конечного числа процедур одноэлементного расширения решетки, присоединения к решетке внешнего нуля 0 или единицы 1 [24, предложение 2.1]. Таким образом, понятие разборности имеет алгоритмическую природу, что облегчает описание конечных разборных решеток.
Нами была написана программа для PC, которая порождает из (п — 1)-элементных разборных решеток все попарно неизоморфные п-элементные разборные решетки и анализирует построенные решетки на строгую жесткость. При этом строго жесткой назовем решетку, не имеющую автоморфизмов, кроме тождественного, все интервалы которой проективны [19]. Очевидно, любая строго жесткая решетка является жесткой решеткой. Описание программы дано в параграфе 3.3. Результаты работы этой программы были использованы для нахождения критических n-элементных решеток для п = 9,10,11,12 и конструкции n-элементных критических решеток для п 13, приведенных в параграфе 1.2.
Все приведенные далее в параграфе 1.2 конструкции являются разборными решетками, поскольку их можно построить из одноэлементной решетки, применяя конечное число указанных процедур.
Доказательство критичности построенных n-элементных решеток для натуральных чисел п 9 разбито на три части, а, именно, приводятся доказательство того, что: 1) данные решетки не имеют склеивающих эндоморфизмов, отличных от постоянных, при этом склеивающим эндоморфизмом решетки L будем называть любой ее эндоморфизм (р такой, что ifx = fy для некоторых различных элементов х,у Є L; 2) данные решетки не имеют автоморфизмов, отличных от тождественного; 3) каждая построенная решетка не содержит собственных нетривиальных жестких подрешеток. Из 1) и 2) следует жесткость построенных решеток. Из 3) и из жесткости построенных решеток следует их критичность.
В параграфе 3 излагается доказательство частей 1) и 2). Отметим, что в доказательстве того, что данные решетки не имеют склеивающих эндоморфизмов, отличных от постоянных основную роль играют понятия простой решетки [23] и отношения проективности и слабой проективности интервалов [19]. Для доказательства того, что данные решетки не имеют автоморфизмов, отличных от тождественного, введены типы элементов, основанные на отношении покрытия и длинах максимальных по числу элементов цепей от 0 и от 1 решетки до рассматриваемых элементов. Таким образом, в доказательстве части 2) ведущую роль играет сохранение типов элементов при автоморфизмах.
В параграфе 4 излагается доказательство части 3), которое основано на переборе всех возможных нетривиальных подрешеток и доказательстве их нежесткости. Для упрощения перебора используются несколько вспомогательных решеточных конструкций, описанных в начале параграфа 3. При доказательстве того, что подрешетки не являются жесткими существенно используется достаточное условие нежесткости решетки — лемма 2 из работы [18].
Нами установлено, что существуют конечные критические неразборные решетки и построена минимальная по числу элементов неразборная критическая решетка. Эта решетка содержит десять элементов. Доказательство ее критичности излагается в параграфе 5 главы 1.
В главе 2 излагается решение проблемы 2 (элементарной характериза-ции), а именно, дается отрицательный ответ на вопрос о том, является ли класс критических решеток аксиоматизируемым. Известно [25], что алгебраическая система элементарно эквивалентна своей ультрастепени по любому ультрафильтру. Поэтому для доказательства арифметической незамкнутости класса K критических решеток достаточно показать, что для бесконечной решетки L из K существует некритическая решетка L, являющаяся ее ультрастепенью по некоторому ультрафильтру.
В параграфе 1 главы 2 даются используемые далее понятия фильтра (главного и неглавного), ультрафильтра, ультрапроизведения и ультрастепени алгебраической системы по ультрафильтру, описание которых см. в [25].
В параграфе 2 главы 2 приведены описание бесконечной, а именно счетной, решетки L и доказательство ее критичности. В доказательство того, что решетка L не содержит жестких подрешеток, кроме одно- и двухэлементных, существенно используется решеточная конструкция, описание которой дано в параграфе 1 главы 1 (см. рис. 1.3 и лемму 1.1.3).
В параграфе 3 главы 2 сначала изучается строение ультрастепени L решетки L по некоторому неглавному ультрафильтру над Z и затем доказывается, что ультрастепень L можно разбить в объединение двух подрешеток, удовлетворяющих требованиям леммы 2 из работы [18] о достаточном условии нежесткости. Поэтому L — нежесткая, и, следовательно, — некритическая решетка. Отсюда вытекает Теорема 2. Класс всех критических решеток неаксиоматизируем.
Доказательство критичности построенных n-элементных решеток для натуральных чисел n 9
В данной главе будем придерживаться обозначений и терминологии, принятых в [25]. Фильтром над непустым множеством J называется любая непустая совокупность D подмножеств множества J, удовлетворяющая следующим требованиям. 1. Пересечение любых двух подмножеств из D принадлежит D; 2. Все надмножества любого подмножества, принадлежащего D, принадлежат D. 3. Пустое подмножество не принадлежит D. Из условий 1, 2 непосредственно вытекает, что пересечение любого конечного числа множеств, принадлежащих фильтру, принадлежит этому же фильтру и что базисное множество J принадлежит каждому фильтру над J. Совокупность всех надмножеств какого-либо фиксированного непустого множества М С J, очевидно удовлетворяет требованиям 1, 2, 3 и поэтому является фильтром. Фильтры этого вида называются главными. Остальные фильтры называются неглавными. Ясно, что фильтр D тогда и только тогда является главным, когда D содержит пересечение всех своих множеств. Семейство всех фильтров над J частично упорядочено относительно включения. Максимальные фильтры, т.е. фильтры, не содержащиеся ни в каком другом фильтре, называются ультрафильтрами. С помощью леммы Цорна легко доказывается, что над каждым бесконечным множеством существуют неглавные ультрафильтры. Легко понять, что любое множество, входящее в неглавный ультрафильтр, бесконечно. Фильтр D над множеством J тогда и только тогда является ультрафильтром, когда для любого М С J либо МЄ Д либо J\MeD ([25]).
Замечание 2.1.1. Пусть D - неглавный ультрафильтр над множеством J. Тогда для любого натурального п 1, любого М Є D и любого разбиения М = Uti мг существует единственное і, для которого Мг Є D.
Доказательство. Пусть п = 2. Разобьем М на два произвольных непустых множества Мх и М2. Это возможно, ибо D - неглавный фильтр и, стало быть, М - бесконечно. Допустив, что MuM2 D,и воспользовавшись тем, что D - ультрафильтр, получим J \ Mh J \ М2 Є D, откуда J\M є D, что противоречиво. Отметим, что Мі, М2 не могут принадлежать D одновременно, иначе Mi П М2 = 0 Є D, что противоречиво. Отсюда, либо Мх Є D, либо М2 Є D. Сославшись на очевидную индукцию, можно утверждать справедливость замечания для любого натурального п.
Пусть каждому элементу а множества J поставлена в соответствие некоторая алгебраическая система aа = (Аа, а) фиксированной сигнатуры а. Элементами декартова произведения = Аа (а Є J) носителей Аа указанных систем являются функции /, определенные на J, которые удовлетворяют условию f(a) Є Аа. Наряду с f(a) будем писать fa.
Пусть D какой-нибудь фильтр над J. Вводим на Ф бинарное отношение =), полагая по определению f=Dg {a(E J\fa = ga}eD. В [25] доказано, что =в есть отношение эквивалентности на Ф, и мы можем образовать фактор-множество А = Ф/ , которое называется фильтрованным по D произведением множеств Аа. Символом fD обозначается класс элементов из Ф, эквивалентных / по =в. На множестве А можно определить алгебраическую систему сигнатуры а. Пусть R — какой-то m-арный предикатный символ из а. По определению полагаем Д(/і А , fmD) =И {а\R(f?,..., /«) =И} є D. В [25] доказано, что истинностное значение предиката R(f\D,... , fmD) не зависит от выбора представителей /ь ..., fm в классах /xD,... , /m . Если F есть n-арный функциональный символ из а, то в соответствии с условием (1) полагаем F(/iД ..., /nD) = fD {a\F(f?,..., /na) = Г} Є D.(2) Как и в случае предикатного символа R, можно проверить, что соотношение (2) задает на А всюду определенную функцию F.
Определения (1) и (2) превращают фильтрованное произведение А = Y\Aa/D в алгебраическую систему (Л, а), называемую фильтрованным по фильтру D произведением систем aа(а Є D) и обозначаемую П aa/D.
Произведения систем, фильтрованные по ультрафильтру, называются ультрапроизведениями. Если все сомножители aа в ультрапроизведении сов падают с фиксированной системой Е, то ультрапроизведение называется ультрастепенью системы S по ультрафильтру D.
Известно [25], что алгебраическая система элементарно эквивалентна своей ультрастепени по любому ультрафильтру Поэтому для доказательства арифметической незамкнутости класса К критических решеток достаточно показать, что для бесконечной решетки L из К существует некритическая решетка L , являющаяся ее ультрастепенью по
Легко проверить, что множество L относительно определенного таким образом частичного порядка является решеткой.
Рассмотрим теперь решетку L, изображенную на рис. 2.1. Лемма 2.2.1. Решетка L не имеет склеивающих эндоморфизмов, отличных от постоянных.
Доказательство. Покажем, что все простые интервалы решетки L про-ективны. При этом интервал [а, Ь] называется простым, если а Ь. Поскольку бриллиант является простой решеткой, достаточно проверить, что [ao,d\ « [d,b0]. Указанное отношение следует из цепочки [oo,rf [ai,6i] [a_i,6_i] [d,6o] На основании леммы 1.1.1 решетка L является простой, и поэтому любой еe склеивающий эндоморфизм является постоянным. Лемма доказана. Лемма 2.2.2. Решетка L не имеет автоморфизмов, отличных от тождественного.
Доказательство. Пусть р - нетождественный автоморфизм решетки L и (рао Ф do. Поскольку 2о покрываем тремя элементами d, Со, «а, элемент 2о отображается в элемент, имеющий три покрытия. Следовательно, ра0 = аг (г Є Z). Предположим сначала, что ра0 = ai, где і ф 0. По свойству покрыва-емости р {d} со, ai} С {hn а, аг+1}. Очевидно, из dVcn = Ьх следует рЬх = Ъг+1. Тогда четырехэлементная цепь {a0, d, &о, &i} отображается в трех элементную цепь, что противоречит инъективности р. Следовательно, наше предположение неверно и ра0 = а0. Отсюда вытекает, что ip{d,Co,ai} С {d,c0,ai}. Элементы d,Co покрываемы одним элементом, а\ - тремя. Поэтому ра\ = а\. Отсюда следует, что цепь {a0, d, Ъ0} h} отображается в себя. Поэтому на элементах этой цепи р действует тождественно. Следовательно, рс0 = со и (pd = d. Таким образом, автоморфизм р действует, как тождественный на элементах интервала [ао, Ь\].
Двойной индукцией по множествам N и Z\N нетрудно показать, что р действует тождественно на каждом бриллианте {aJ}bJ}cJ}aJ+hbJ+1} (j Є Z) решетки L. Следовательно, решетка L обладает только тождественным автоморфизмом. Лемма доказана. Ck+i, x = Ck, где fceZ. Пусть теперь хотя бы один элемент из множества элементов {ak,bk,Ck\ к Є Z} не принадлежит подрешетке S и \S\ 3. Тогда найдется ”п-бриллиантная” решетка ВПЛ такая, что подрешетка S не содержит собственное подмножество элементов решетки ВПЛ. Поэтому на основании утверждения (i) леммы 1.1.3 подрешетка S является нежесткой. (2) d Є S. Рассмотрим возникающие здесь подслучаи.
Пусть подрешетка S (\S\ 3) не содержит собственное подмножество множества элементов М: = {ак,Ък,ск\к 1} или собственное подмножество множества элементов М_х = {ah hh сх\\ -1}. Тогда найдется ”п-бриллиант-ная” решетка Впл (q 1) или Вщг (г —1) соответственно такая, что подрешетка S не содержит собственное подмножество элементов решетки Впл или Вщг, соответственно. Следовательно, на основании утверждения (i) леммы 1.1.3 подрешетка S является нежесткой.
Рассмотрим теперь случай 3. Из d V 6_i = b0 и d А сц = а0 следует, что Ь0,а0 Є S. Если c_i S, то S имеет две подрешетки = {х\х 6_і} и52С {у\у а0}, удовлетворяющие условиям леммы 1.1. Следовательно, S обладает нетривиальным эндоморфизмом р таким, что tpSi = {х} С Si и ifS2 = {у} Q 5 2 для некоторых х и у. Случай CQ S рассматривается аналогично. Если с_і,Со Є S, то S = L. Рассмотрим случай 4. Из d Л c_i = a_i S и d V с0 = h ( S следует, что с_1,с0 S. Тогда подрешетка S является либо одноэлементной, либо двухэлементной решеткой, либо трехэлементной цепью {a0,d,b0}. Трехэлементная цепь, очевидно, не является жесткой решеткой. Лемма доказана.
Конструкция счетной критической решетки
Возьмем произвольный элемент uD решетки 77, где и - функция из Z в П. Если uD Є L, то по определению L существует s такое, что {z \uz = s} Є D. Пусть теперь uD L. Будем говорить, что множество всех значений uz функции и ограничено снизу, если существует элемент х Є Q такой, что для любого z Є Z выполняется uz х. Соответственно, множество всех значений uz функции и ограничено сверху, если существует элемент у Є Q такой, что для любого z Є Z выполняется uz у. Из конструкции решетки L ясно, что множество всех значений uz функции и можно представить в виде объединения двух множеств таких, что все элементы первого множества ограничены снизу, а все элементы второго множества ограничены сверху Иными словами, существуют х, у Є Q такие, что для любого z Є Z выполняется uz х или UZ у. В самом деле, на роль х претендует ЬІ, на роль у претендует аі для некоторого і Є Z. В общем случае, одно из множеств может быть пусто. Также данные множества могут иметь непустое пересечение. Нетрудно понять, что множество аргументов М = Z функции и, принадлежащее D, можно представить в и поскольку D - фильтр, M Є D. Как было показано ранее, поскольку множество а (М) конечно, элемент aD принадлежит L, что противоречиво. Третье условие доказывается аналогично первому условию.
Покажем теперь, что выполняется второе условие. Предположим противное. Пусть существуют aD Є L\ и vD Є L2 такие, что aD vD, или, иначе, {z \az vz} Є D. По определению L\ и L2 соответственно
Рассмотрим aD V bD. Определим функцию f : Z П следующим образом: f(z) = a (z) Vb(z). Из определения функции / следует {z\az V bz = f} = Ze D, что равносильно aD V bD = fD.
Покажем сначала, что fD Є Z \Z. Допустим противное, fD Є I. Тогда по определению L существует х Є Q такое, что К = {z\fz = х} Є D. Предположим, что в К мы отыскали бесконечное подмножество Кх Є D такое, что множества а(Кх) = {az\z Є К{\ и Ь(КХ) = {bz\z Є К{\ конечны. Приведем это предположение к противоречию. Пусть имеет место первое. Тогда существует п Є N такое, что а(К{) = {jb...,jn}. Обозначим Mq = {z Є Ki \az = jq}, l q n. Тогда Mu ..., Mn - разбиение множества K\. Согласно замечанию 2.1.1 можно предположить, что М\ Є D. Но тогда {z\az = ji} = Т Э Мі є D и поскольку D - фильтр, Т є D. Отсюда aD Є L по определению множества что противоречиво. Аналогично рассуждая, приводим к противоречию и второе предположение.
Итак, можно считать, что для любого бесконечного подмножества Кх Є D из К множества а{Кі) и b{Ki) бесконечны. Рассматривая теперь на Кх отношение эквивалентности а 1 о а и выбирая в каждом его классе в точности по одному элементу, получаем бесконечное множество К2 Q Кі, на котором а действует взаимно-однозначно. Воспользовавшись тем, что Ь{К2) по-прежнему бесконечно, и выбирая из каждого класса эквивалентности Ь-гоЬнаК2 в точности по одному элементу, получаем бесконечное множество К:І С К2, на котором и Ь действует взаимно-однозначно. Вспомнив определение / и К, заключаем, что в решетке L существуют две последовательности элементов без повторяющихся членов {хг}г2 и {уг}г п такие, что х = хгУуг для любого і Є Z. Без ограничения общности можно считать, что Х{ несравним с І/І для любого і Є Z. Коль скоро элементы а„ с„ d вообще не разложимы в объединение несравнимых элементов, они не могут играть роль элемента х. Значит, нужно рассмотреть лишь элементы ЬІ. Легко, однако, понять, что достаточно рассмотреть только элемент bo. Выпишем все с точностью до симметрии пары несравнимых элементов, дающих в объединении bo:
М можно представить в виде М = Mi U М2, где Mi = {z Є М /z w} и M2 = {z Є М /z = w}. Тогда Mi, М2 - разбиение множества М. Согласно замечанию одно из множеств Mi, М2 принадлежит D. Легко понять, что М2 Є D приводит к противоречию. Следовательно, Мх є D. Но тогда {z\fz w} = Т D М: є D и поскольку D — фильтр, Т Є D. Отсюда по определению множества Li элемент fD принадлежит L\. Итак, L\ — подрешетка решетки L .
Аналогично доказывается, что L2 — подрешетка решетки L . Лемма доказана. Рассмотрим решетку Т?. Обозначим через U объединение подрешеток ТІ и L решетки L . Если множество X7 является подрешеткой решетки L , то к решетке L применима лемма 1.1. Легко понять, что в качестве подрешеток L\ и L2 в лемме 1.1 надо взять подрешетки L и L2, соответственно.
Таким образом, для завершения доказательства основного результата нам осталось доказать следующую лемму.
Частично упорядоченное множество U является подрешеткой решетки L . Доказательство. Достаточно показать, что для любых элементов aD Є IT иfDeL элементы aDAfD,aD\/ fD принадлежат I7. Отметим, что aD Л fD aD Є Lx. Поскольку ни один из элементов решеток L и L i не может быть меньше элемента решетки элемент aDAfD принадлежит решетке Li, и, следовательно, множеству U.
Итак, U - подрешетка 77. Лемма доказана. Глава 3 Функция роста конечных жестких решеток В данной главе доказано, что функция роста конечных жестких решеток экспоненциальна. В параграфе 1 описаны конструкции решеток, используемых в доказательстве теоремы об экспоненциальном росте жестких решеток. В параграфе 2 доказано, что они являются простыми жесткими решетками. В параграфе 3 приведен алгоритм построения разборных решеток и поиска среди них всех строго жестких разборных решеток.
Доказательство экспоненциальности роста числа конечных жестких решеток
Эффективность именно такой пошаговой проверки произвольно взятой решетки на строгую жесткость объясняется тем, что эндоморфизмы вида (8), (9), (10) и автоморфизм ромба являются наиболее часто встречающимися эндоморфизмами в решетках (см. пример ниже), к тому же сложность такой проверки низка. Проверка решетки L на наличие автоморфизмов проводится как частный случай проверки изоморфности двух решеток L1 и L2, только в качестве решеток L1 и L2 выступает решетка L. Таким образом, в про-116 грамме используется указанный выше алгоритм проверки двух решеток на изоморфизм, сложность которого 0{Р). Поскольку сложность проверки на наличие в решетке автоморфизмов в общем случае является факториальной — О(Р), то данная проверка проводится последней. Если после проверки в списке РР_Ъед имеется только один автоморфизм (тождественный), то решетка является строго жесткой.
Пример. Отметим, что из 221 разборной восьмиэлементной решетки эндоморфизмами вида (8), (9) обладают 106 решеток, эндоморфизмами вида (10) обладает 107 решеток, автоморфизмом ромба обладают 116 решеток. Из 221 решетки только 19 решеток необходимо проверить на строгую жесткость. Среди них существует лишь одна решетка, все интервалы которой проектив-ны, - это решетка R8. Проверив решетку R8 на наличие автоморфизмов, получим, что R8 является строго жесткой решеткой.
Опишем соответствующие процедуры проверки. Если в списке покрытий решетки наименьший элемент 0 покрывается единственным атомом, то решетка обладает эндоморфизмом вида (8). Сложность такой проверки 0(1). Пусть в списке покрытий решетки элементы с номерами от 1 до п — 3 покрываются элементами, отличными от наибольшего элемента п - 1 решетки. Тогда решетка имеет единственный коатом п - 2 и обладает эндоморфизмом вида (9). Для такой проверки необходимо просмотреть п — 3 листа в списке покрытий решетки. Следовательно, ее сложность 0(п - 3). Поиск эндоморфизмов вида (8)-(9) функцией Find_only_atom_coatom. a и b последовательно просматриваем список покрытий решетки, начиная с элемента номер 1 и заканчивая на элементе с номером, меньшим или равным n — 3 . Если x y, AT[1][x] = AT[2][x] = 1 и AT[1]y] = 1 или AT[2][x] = 1 и AT[1][y] = AT[2][y] = 1, то поиск прекращается - решетка обладает эндоморфизмом вида (10). Поскольку алгоритм формирования массива AT имеет сложность O(n2), алгоритм проверки решетки на наличие эндоморфизма вида (10) также имеет сложность O(n2). Алгоритм проверки на наличие автоморфизма ромба Сначала приведем краткое описание алгоритма. Шаг 1. Последовательно проверяем q-типы элементов решетки. Если элемент el имеет q-тип (1,1), то запоминаем его высоту lev = Level[el]. Если el n - 2, то СТОП (решетка не обладает автоморфизмом ромба). Шаг 2. Определяем число q элементов q-типa (1,1) высоты lev. Если q 2, то переходим к шагу 3. Иначе, переменной lev присваиваем значение на 1 больше и возвращаемся к шагу 1. Шаг 3. Проверяем, есть ли среди элементов (l,q)-типa (lev, 1,1), элементы, покрывающие и покрываемые одинаковыми элементами. Если такие элементы найдены, то СТОП (решетка обладает автоморфизмом ромба). Иначе, переходим к элементам высоты, большей lev и возвращаемся к шагу 2.
Перейдем к формальному описанию алгоритма. Алгоритм реализован функцией Find_rhomb. Для определения того, что элемент имеет q-тип (1,1) используется массив покрытий AT. Для определения высоты lev элемента используется массив высот Level. Если на каждой высоте lev решетки либо нет элементов (l, q)-типa (lev, 1,1), либо содержится только один элемент указанного (l,q)-типa, то решетка не обладает автоморфизмом ромба.
Шаги 1 и 2 алгоритма реализуются функцией Find_elements_of_ type_11. Опишем более подробно работу функции. Идем по массиву покрытий AT в порядке возрастания номеров элементов. Если элемент el имеет q-тип (1,1), то запоминаем его высоту в переменной lev и проверяем все элементы большего номера, имеющие высоту lev. Число элементов (l,q)-типa (lev, 1,1), запоминаем в переменой q. Если q 1, то переменной q присваиваем значение 0, переменной el присваиваем наименьший номер элемента высоты lev + 1. Далее проверяем элементы с номерами, большими или равными el. Поиск завершается, если q 2 или если новое значение переменной el после просмотра предыдущей высоты l(0, el) - 1 больше или равно n - 2. Если q 2 проверка на наличие автоморфизма ромба продолжается (шаг 3 алгоритма). Если q = 0 и при этом el n - 2, то решетка не обладает автоморфизмом ромба. Шаг 3 алгоритма реализован функцией Aut_pair. Если q 2, то проверяем в списке покрытий решетки PL_beg элементы высоты lev-І. Если элемент x высоты lev-І имеет (l, q)-тип (lev-1,0s, r или более), где s 0, r 2, то проверяем список покрытий данного элемента. Отметим, что при нахождении в листе элемента x элемента (l,q)-типа (lev, 1,1), переменная q каждый раз уменьшается на 1. При нахождении в списке покрытий элемента x двух первых элементов a и b (l, q)-типа (lev, 1,1) проверяем их на условие покрываемости одним элементом y, т. е. a y и b y. Если a и b удовлетворяют указанному условию, то автоморфизм ромба найден. Иначе, из элементов, покрывающих элементы a и b, составляется список PS_beg. При нахождении в списке покрытий элемента x каждого следующего элемента (l,q)-типа (lev,1,1) определяем элемент z его покрывающий. Если в списке покрывающих элементов уже есть элемент z, то автоморфизм ромба найден. Иначе, элемент z добавляется в список. Если в списке покрытий элемента x не найдена пара элементов (l, q)-типа (lev, 1,1), покрываемых одним элементом, то в списке покрытий решетки PL_beg переходим к следующему
