Кристаллография, 2022, T. 67, № 4, стр. 561-570

ВВЕДЕНИЕ

Теория информации представляет собой развитую область математики, заложенную в конце 40-х годов Клодом Шэнноном [1]. Наиболее широко используемым в современности способом оценки количества информации, содержащейся в каком-либо символьном сообщении, является расчет так называемой информационной энтропии по Шэннону [2]. Этот функционал имеет вид

где Под p_i понимается вероятность, с которой в сообщении появляется символ i-го сорта.

Расчет количества информации еще с начала 1950-х годов стал применяться к молекулярным графам, чему посвящен большой обзор Бончева [3]. Символами молекулярного графа выступают атомы (вершины графа), а сообщением – сам молекулярный граф. Эквивалентными (i-го сорта), как правило, считаются вершины, на которых группа автоморфизмов графа действует транзитивно.

Более чем десять лет такая оценка количества информации применяется к кристаллам. Согласно [4] количество структурной информации, приходящейся в кристалле на один атом, равно

где m_i – кратность i-й занятой кристаллографической орбиты в расчете на приведенную элементарную ячейку кристалла, ${v}$ – общее число атомов в приведенной элементарной ячейке, k – число занятых атомами орбит. По сути, $I_{G}^{{{\text{str}}}}$ характеризует сложность фактор-графа кристаллической структуры, т.е. конечного графа с ${v}$ вершинами, в котором степень вершины равна валентности атома в кристалле, все ребра отвечают связанным между собой атомам, а ребра, соединяющие трансляционно-эквивалентные атомы, изображаются петлями [5]. Общее количество информации в расчете на приведенную элементарную ячейку составляет

По значению $I_{{G,~{\text{tot}}}}^{{{\text{str}}}}$ кристаллические структуры неорганических веществ условно разделяют на очень простые (<20), простые (20–100), средней сложности (100–500), сложные (500–1000) и очень сложные (>1000) [6]. К очень сложным относятся, в первую очередь, структуры цеолитов и микропористых каркасных материалов. Самым сложным на сегодня среди минералов считается юингит Mg₈Ca₈[(UO₂)₂₄(CO₃)₃₀O₄(OH)₁₂(H₂O)₈](H₂O)₁₃₀ ($I_{{G,~{\text{tot}}}}^{{{\text{str}}}}$ = 23477.5 бит/эл. яч.) [7]. По мере усложнения кристаллической структуры количество информации о ней увеличивается, а конфигурационная энтропия кристалла уменьшается на пропорциональную величину [8]. Недавно было предложено дополнить информационную сложность кристаллической структуры так называемой координационной сложностью, учитывающей число степеней свободы атома в зависимости от симметрии позиции [9].

С помощью функционала по Шэннону также было предложено [10] оценивать количество химической информации, проистекающей из состава минерала: $E_{{c1}}^{{(1)}}E_{{c2}}^{{(2)}}...E_{{ck}}^{{(k)}}$, где E⁽ⁱ⁾ – i-й химический элемент, c_i – индекс в простейшей формуле вещества. Функционал (1) при этом рассчитывается для p_i = с_i/e, где e – общее число атомов в простейшей формуле вещества. В 2020 г. с помощью статистического анализа 5349 минералов, утвержденных Международной минералогической ассоциацией (IMA), был подтвержден эмпирический закон Федорова–Грота, согласно которому более сложному химическому составу обычно отвечает более низкая симметрия кристалла. Химическая сложность продемонстрировала убывающую зависимость от порядка кристаллического класса [11].

Как показано в [12], часть элементарной ячейки, в которой содержится информация о кристалле, рассчитывается как V* = V₀/M, где V₀ – объем элементарной ячейки, M – порядок группы симметрии, а V* представляет собой фундаментальный объем. Заметим, что в данном случае речь идет о приведенной элементарной ячейке, а под группой симметрии понимается кристаллический класс. В пределах фундаментального объема некоторые атомы могут свободно менять свое местоположение (три степени свободы), в то время как другие могут сдвигаться только вдоль поворотной оси или плоскости зеркального отражения (одна и две степени свободы соответственно), а у третьих позиции фиксированы (нонвариантны). Согласно [12] отношение n_s/n_p (где n_s – число “оставшихся” поступательных степеней свободы, n_p – общее число атомов в приведенной элементарной ячейке), а также V* характеризуют стабильность кристаллической структуры. При этом, как правило, далеко не весь фундаментальный объем доступен атомам из-за того, что закрытые элементы симметрии создают вокруг себя запрещенные области (таковых нет только в существенно асимморфных пространственных группах без стационарных орбит) [13, 14]. На взаимосвязь симметрии атомных позиций и стабильности структуры также обращали внимание при анализе редких федоровских групп в структурной минералогии [15, 16].

Помимо сложности, создаваемой расположением атомов в кристалле, каждая пространственная группа характеризуется своей собственной информационной сложностью [17]. Некоторые позиции Уайкова могут трансформироваться друг в друга под действием нормализатора пространственной группы, их относят к одному набору Уайкова. Если под p_i понимать вероятность наугад выбранной позиции Уайкова принадлежать i-му набору Уайкова, то результатом расчета по формулам (1) и (2) становится позиционная сложность пространственной группы. Определенной сложностью обладают и кристаллографические точечные группы (кристаллические классы) [18]. Элементы точечной группы могут быть эквивалентны по действию группы автоморфизмов точечной группы, что хорошо видно на графе циклов группы и позволяет рассчитать p_i. Например, у групп ${{C}_{{3{v}}}}$ и D₃ (рис. 1) есть два элемента третьего порядка ($C_{3}^{1}$ и $С_{3}^{2}$), входящие в один класс эквивалентности, и три элемента второго порядка, тоже друг другу эквивалентные. Тождественное преобразование (черный кружок на рис. 1) всегда составляет отдельный класс эквивалентности. Таким образом, шесть элементов группы разбиваются на классы: {1, 2, 3}. Следовательно, согласно (1) и (2), H = –1/6log₂1/6 – 2/6log₂2/6 – ‒ 3/6log₂3/6 = 1.459 бит/элемент, или 8.755 бит/группа. Результаты аналогичного расчета для других кристаллических классов приведены в табл. 1.

В [19] применялись формулы (1), (2) к распределениям минералов по сингониям и кристаллическим классам. Например, литосфера Земли в целом характеризуется следующей ранговой формулой: М_30.3–Р_21.7–К_14.4–ТРИГ_10.2–ТЕТР_9.4–Г_7.2–ТРИК_6.8 (в процентах от общего числа минералов), где М – минералы моноклинной, Р – ромбической, К – кубической, ТРИГ – тригональной, Г – гексагональной, ТЕТР – тетрагональной, ТРИК – триклинной сингоний. Этой формуле отвечает H = 2.56 бит/минерал. Подобные информационные параметры можно использовать для выяснения глобальных тенденций изменения кристалло-симметрийной структуры сложных минеральных систем [19].

Итак, (1), (2) можно использовать для оценки сложности любого источника информации, если известно отношение эквивалентности на множестве символов, позволяющее рассчитать величины p_i. В данной работе этот подход применяется к оценке сложности порождающих наборов кристаллографических групп. Несмотря на разнообразие таких групп [20], включая группы в пространствах высокой размерности, они все являются конечно-порожденными, а число минимальных комбинаторно-различных подмножеств порождающих элементов у них тоже является конечным.

Некоторый набор элементов (подмножество) U группы G называется порождающим (или образующим), если наименьшей подгруппой G, содержащей U и обозначаемой 〈U〉, является сама G, т.е. 〈U〉 = G. Порождающее множество U называется минимальным, если оно не содержит никакого порождающего множества G, кроме себя самого [21]. Сравнительно недавно программные алгоритмы были применены к кристаллографическим точечным группам [22], для которых выведены все возможные минимальные наборы порождающих. К сожалению, из определения минимального порождающего подмножества U не следует, что мощность |U| одинакова у всех минимальных подмножеств группы G. Некоторые порождающие подмножества кристаллографических групп не обладают наименьшей возможной мощностью min|U|, поскольку в них изначально отсутствует некоторый элемент, включение которого позволило бы еще больше минимизировать U. Например, 〈$C_{6}^{1}$〉 = C₆ ⊃ $C_{6}^{2}$, но 〈$C_{6}^{2}$〉 = С₃ ≠ С₆ и 〈$C_{6}^{3}$〉 = С₂ ≠ С₆. Однако если U = {$C_{6}^{2}$, $C_{6}^{3}$}, то 〈U〉 = = C₆. Такое U называется несущественно минимальным [23]. Далее в тексте под минимальным порождающим подмножеством по умолчанию понимается существенно минимальное.

У трехмерных точечных групп $G_{0}^{3}$ в существенно минимальном порождающем подмножестве два или три элемента [24], у двумерных пространственных (плоских) групп $G_{2}^{2}$ – от двух до четырех [25], у трехмерных пространственных (федоровских) групп $G_{3}^{3}$ – от двух до шести [26]. Часто эту величину называют рангом группы. Существенно минимальный набор порождающих элементов может быть выбран большим числом способов, у конечных групп оно конечно, у плоских и федоровских – бесконечно. Однако даже у последних число комбинаторно-различных вариантов выбора ограничено.

Над вероятностью порождения группы случайно выбранными элементами задумывались еще полвека назад. В [27] исследована вероятность того, что наугад выбранная пара перестановок длины n порождает группу перестановок A_n, и показано, что при n → ∞ эта вероятность стремится к единице. В связи с вероятностным характером порождения любой минимальный набор образующих элементов группы можно трактовать как нечеткий [22, 28–30]. Это имеет прямое отношение к молекулярным кристаллическим структурам, где, как правило, невозможно четко выявить опорные (структурообразующие) межмолекулярные контакты, порождающие конкретную пространственную группу [31–33]. В последнее время наметилась тенденция к анализу порождающих симметрических операций и у ковалентных каркасов [34], поскольку от них зависят возможные искажения каркаса и направления фазовых превращений. Кратко напомним [35]: что если U – множество элементов u_i и ${{{{\mu }}}_{V}}:U \to \left[ {0,1} \right]$, то нечетким подмножеством V в U называется множество вида $\left\{ {(u,{{{{\mu }}}_{{~V}}}(u)):u \in U} \right\}$, а ${{{{\mu }}}_{{~V}}}(u)$ называют степенью принадлежности u к V. Сумму $\sum\nolimits_{i = 1}^n {{{{{\mu }}}_{V}}({{u}_{i}})} $, где n = |U|, называют массой нечеткого подмножества V. Масса нечеткого минимального порождающего подмножества группы совпадает с ее рангом [22]. Для оценки степени нечеткости множества используют функционалы, аналогичные (2), в частности энтропию S (не имеет ничего общего с термодинамической энтропией) [36]:

и другие функционалы с похожими свойствами [37, 38].

Цели настоящей работы – разработка методики, позволяющей рассчитать информационную энтропию порождающих подмножеств всякой конечно-порожденной дискретной группы; разработка программного алгоритма, реализующего данную методику для конечных групп, включая кристаллографические.

МЕТОДИКА РАСЧЕТА

Пусть конечно-порожденная дискретная группа ранга r имеет m минимальных порождающих подмножеств, а число элементов группы, встречающихся хотя бы в одном из этих подмножеств, равно s. Взаимно обратные элементы для порождающего подмножества считаются одинаковыми [22]. Обозначим за N_i число одинаковых элементов i-го сорта среди всех N = rm элементов в m подмножествах, $\sum\nolimits_{i = 1}^k {{{N}_{i}}} = N$. Тогда p_i = N_i/N – вероятность того, что наугад выбранный порождающий элемент из любого минимального порождающего подмножества окажется i-го сорта. При подстановке p_i в (1) и (2) получается величина H, отвечающая информационной сложности минимального порождающего подмножества в расчете на один элемент. А величина H_tot = sH отвечает общей информационной сложности минимального порождающего подмножества в расчете на группу.

Можно сказать, что множеством, на котором вводится отношение эквивалентности для расчета p_i, является множество комбинаторно-различимых графов Кэли для данной группы, а эквивалентность устанавливается по наличию у графов Кэли одинаковых ребер. У периодических групп можно рассматривать фактор-граф периодического графа Кэли [23].

Нетрудно показать взаимосвязь (1), (2) и (6). Так как степень принадлежности μ_i совпадает с вероятностью того, что в наугад выбранном минимальном порождающем наборе содержится элемент i-го сорта, то p_i = μ_i/r. При переходе от двоичного к натуральному логарифму единица измерения количества информации также меняется с бит на нат.

В качестве примера снова рассмотрим кристаллические классы ${{C}_{{3{v}}}}$ и D₃ (абстрактный класс Dih₃ – диэдральная группа шестого порядка и второго ранга) с определяющими соотношениями a³ = b² = (ab)² = e. Порождающими являются элементы a, b, ab и aba^–1 в любом парном сочетании (всего шесть подмножеств). Тогда N = 2 × 6 = = 12, p_i = 3/12 = 1/4 (для всех i). Следовательно, H = 4(–1/4log₂(–1/4)) = 2 бит/элемент, H_tot = 4 × × 2 = 8 бит/элемент.

В качестве еще одного примера рассмотрим федоровскую группу P2₁2₁2₁ второго ранга [39]. Минимальное порождающее подмножество содержит любую пару винтовых поворотов a и b вокруг осей 2₁ (например, вдоль X и Y) на ближайшем друг от друга расстоянии (рис. 2), ba²b^–1a² = = ab²a^–1b² = e. Третий винтовой поворот ab тоже может входить в порождающий набор. В итоге получаем три комбинаторно-различимых набора: {a, b}, {a, ab}, {b, ba}. Следовательно, N = 6, p_i = = 2/6 = 1/3 (для всех i), H = 3(–1/3log₂(–1/3)) = = 1.585 бит/элемент, H_tot = 3 × 1.585 = 4.755 бит/ группа.

АЛГОРИТМ ДЛЯ КОНЕЧНЫХ ГРУПП

Алгоритм реализован в среде Mathematica 11.0 [40]. В нем используется изоморфизм всякой конечной группы некоторой группе перестановок (теорема Кэли [41]). На первом этапе задаются исходные порождающие перестановки, число которых равно r. При помощи перемножения выводятся все остальные перестановки в группе, за исключением e (тождественное преобразование не может входить в минимальный порождающий набор). Затем составляются все парные произведения перестановок. Если среди этих произведений оказался элемент e, одна из перестановок из соответствующей пары выбрасывается. Из списка оставшихся перестановок формируются всевозможные наборы по r в каждом. Из каждого такого набора порождается группа перестановок, и ее порядок сравнивается с порядком исходной группы. Если эти порядки равны, то данный набор является порождающим и при этом минимальным. Затем все порождающие перестановки записываются в виде слов через исходные перестановки и рассчитывается их частотность в уже найденных порождающих наборах. На последнем этапе по формулам (1), (2) рассчитывается информационная сложность. Порождающие перестановки некоторых групп были взяты из баз данных ATLAS [42] и GroupNames [43]. Всем желающим по запросу авторы предоставят программный код.

РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ

В табл. 2 представлены результаты расчета информационной сложности минимального порождающего подмножества у кристаллических классов. С ростом числа элементов, способных быть порождающими, H и H_tot тоже растут.

У циклических групп Z_n один элемент в порождающем подмножестве, но число таких элементов в общем случае не равно одному. В [44] все порождающие элементы группы Z_n названы “атомом”. Если 〈a〉 = Z_n, то порождающими будут все a^k, где 1 ≤ k ≤ n – 1, где k и n – взаимно простые числа. Число таких k в теории групп называют функцией Эйлера φ(k). Например, у некристаллографической группы С₅ из-за того, что числа 2 и 5 взаимно простые, два порождающих подмножества с точностью до обратного элемента – это {$C_{5}^{1}$} и {$C_{5}^{2}$}, следовательно, H = 1 бит/элемент и H_tot = 2 бит/группа. У кристаллографических групп n = 1, 2, 3, 4 и 6, и порождающий элемент единственный, поэтому у восьми классов, изоморфных Z_n, H_tot = H = 0.

Наибольшая сложность у классов D_6h и O_h, не являющихся подгруппами других классов. У первой порождающие подмножества кодируются 74 битами, у второй – 95 битами информации. Увеличение количества информации в порождающих наборах не вполне соответствует увеличению сложности самих классов (табл. 1). В первую очередь обращает на себя внимание группа D_2h, занимающая всего лишь 9 место по первому из значений, но 5 – по второму, а среди других групп подъем еще более значительный – с 26 на 9 место. Ключом к пониманию этого может являться сравнительно большой ранг группы D_2h при небольшом порядке. Также примечательно, что всего у семи классов сложность порождающего подмножества по значению H_tot превышает сложность самой группы: С_2h, ${{C}_{{2{v}}}}$, D₂ (группа диэдра Dih₂), D_4h, D_6h, T и T_h.

Дополнительно проанализированы серии самых известных групп, среди которых есть некристаллографические (рис. 3). По времени расчет на обычном персональном компьютере занял от нескольких секунд до нескольких минут. Группа S₆ порядка 6! = 720 обсчитывалась около 10 мин, она имеет 397 порождающих элементов и 30 420 порождающих подмножеств. Ее сложность наибольшая среди всех рассмотренных групп: H = = 8.426 бит/элемент и H_tot = 3345.2 бит/группа, что по сложности практически сопоставимо с таким сложным минералом, как Ba₁₂(SiO₃)₆(CO₃)₅Cl₂ ($I_{{G,~{\text{tot}}}}^{{{\text{str}}}}$ = 3913.7 бит/эл. яч.) [6]. Сложность порождающих подмножеств симметрических групп S_n и групп перестановок A_n быстро возрастает, начиная с n = 2 и 3 соответственно (S₁ ∼ A₁ ∼ A₂ ∼ Z₁). У диэдральных групп Dih_n рост начинается раньше (Dih₁ ∼ Z₂, Dih₃ ∼ S₃), но он более медленный и, начиная с n = 5, перестает быть монотонным. Такой же немонотонный рост, зависящий от функции Эйлера, характерен для Z_n. При построении зависимости m (числа минимальных порождающих подмножеств) от n в полулогарифмических координатах получается картина, практически идентичная рис. 3.

На рис. 4 представлены результаты расчета сложности диэдральных групп Dih_n с немонотонным ростом. Из-за отсутствия делителей у простых n сложность соответствующих групп довольно большая, что хорошо видно на графике m (n). Точно так же при четных n сложность, как правило, меньше, чем при близких нечетных, и есть всего одно исключение из этого правила при n ≤ 30: H_tot = 80.6 и 86.2 соответственно у Dih₁₅ и Dih₁₆.

Существуют некристаллографические группы, отображающие симметрии прототипных структур в пространствах, отличающихся от трехмерного евклидова. Эти группы определяют симметрийно-возможные кристаллографические и некристаллографические структуры в E³. К таковым, например, можно отнести политоп {240} с группой автоморфизмов порядка 2880, подробно рассматриваемой в [45, 46]. Еще одним примером является строительный тетраблок для широкого круга структур, которые можно аппроксимировать цепями тетраэдров со смежными гранями [47]. Тетраблок представляет собой семивершинное объединение по граням четырех правильных тетраэдров. Линейному и плоскому вариантам тетраблока соответствуют проективная специальная линейная группа PSL(2, 7) и проективная общая линейная группа PGL(2, 7) [48], причем первая для второй является подгруппой индекса 2. У группы PSL(2, 7) порядка 168 (рис. 5a) с порождающими перестановками a = (2, 3)(3, 5), b = = (1, 2, 3)(5, 6, 7) [42] всего 94 порождающих элемента, 2814 порождающих подмножеств, H = = 6.496 бит/элемент, H_tot = 610.6 бит/группа. У группы PGL(2, 7) порядка 336 (рис. 5б) с порождающими перестановками a = (1, 2, 3, 4, 5, 6, 7, 8), b = (1, 8, 2, 7, 4, 6, 5) [43] всего 192 порождающих элемента, 10 626 порождающих подмножеств, H = 7.475 бит/элемент, H_tot = 1435.2 бит/группа. Весьма близкие значения у группы A₆ (H = = 7.559 бит/элемент, H_tot = 1526.9 бит/группа).

Оценка сложности порождающих наборов групп может иметь практический интерес не только в кристаллографии. Известно, что n независимых биполярных психологических признаков (интроверсия–экстраверсия и т.п.) порождают прямое произведение (Z₂)ⁿ [49], например в трехфакторной модели Г. Айзенка n = 3 и соответствующая группа (Z₂)ⁿ ∼ D_2h. При n = 4 порождающих подмножеств 840, т.е. в четырехфакторной модели личности можно сконструировать 840 равноправных базисов из четырех независимых биполярных признаков. Добавление четвертого фактора увеличивает H с 2.807 до 3.907 бит/элемент и H_tot – с 19.7 до 58.6 бит/группа, т.е. почти в 3 раза.

ЗАКЛЮЧЕНИЕ

Предложена методика расчета информационной энтропии порождающих подмножеств всякой конечно-порожденной дискретной группы.

Методика успешно апробирована для конечных групп, включая кристаллографические.

Для рассматриваемых групп установлены значения информационной сложности H и общей информационной сложности минимального порождающего подмножества в расчете на группу H_tot, что позволило выявить соответствующую статистику.

Работа выполнена при поддержке Российского научного фонда (грант № 20-77-10065). Расчеты информационных индексов проведены Д.А. Банару в рамках госбюджетной темы № 0137-2019-0014.