Совершенные коды и n-арные квазигруппы: конструкции и классификация тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

н

485651

Кротов Денис Станиславович

Совершенные коды и п-арные квазигруппы: конструкции и классификация

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

О 3 [.;д? "-г.)

Новосибирск — 2010

4856516

Работа выполнена в Учреждении Российской академии наук Институте математики им. С. Л. Соболева Сибирского отделения РАН

Официальные оппоненты: доктор физико-математических наук

Копытов Валерий Матвеевич

доктор технических наук Федоренко Сергей Валентинович

доктор физико-математических наук Черемугакин Александр Васильевич

Ведущая организация: Московский государственный университет

имени М. В. Ломоносова

Защита состоится 23 марта 2011 г. в 1500 часов на заседании диссертационного совета Д 003.015.01 при Учреяедении Российской академии наук Институте математики им. С. Л. Соболева СО РАН по адресу: 630090, Новосибирск, пр. Академика Коптюга, 4

С диссертацией можно ознакомиться в библиотеке ИМ СО РАН. Автореферат разослан » 01 2011 года.

Ученый секретарь

диссертационного совета Д 003.015.01

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

В диссертации рассматриваются комбинаторные вопросы теории парных квазигрупп и 1-совершенных двоичных кодов. Доказаны признаки разделимости п-арных квазигрупп, получена характеризация класса п-арных квазигрупп порядка 4, Рассмотрены конструкции 1-совершенных двоичных кодов и построение из них кодов в троичном алфавите.

Актуальность темы. Объектами исследования настоящей работы являются 1-совершенные двоичные коды и п-арные квазигруппы, которые также известны как латинские гиперкубы (многомерное обобщение латинских квадратов) и эквивалентны максимально дистанционно разделимым (МДР) кодам с расстоянием 2. Оба класса объектов рассматриваются в метрическом пространстве Хэмминга Я™, носителем которого является множество {0,1,... ,д - 1}" слов длины п алфавита {0,1,..., ц — 1), а расстояние между двумя словами есть число позиций, в которых эти слова различаются. Если д есть степень простого числа, Я™ можно снабдить структурой векторного пространства над конечным полем СР(^), мы будем этим пользоваться в случае д = 2. Пространство Хэмминга удобно также рассматривать как граф, в котором два слова соединены ребром тогда и только тогда, когда они отличаются только в одной позиции. Максимальную клику этого графа будем называть линией (линия состоит из д слов, совпадающих во всех позициях кроме одной), а вершину вместе с ее окрестностью — 1-шаром с центром в этой вершине. Множество слов в называется 1-совершенным кодом, если каждый 1-шар содержит ровно одну кодовую вершину. Множество слов в Я™ называется МДР-кодом с расстоянием 2, если каждая линия содержит ровно одну кодовую вершину. (Напомним, что кодовым расстоянием произвольного подмножества в Я™ из двух или более вершин называется минимальное расстояние между двумя различными вершинами. Так, 1-совершенный код, если у него больше одной вершины, имеет расстояние 3.) Функция из {0,1,..., д — 1}" в {0,1,..., д — 1} называется п-арной квазигруппой порядка (¡, если на каждой линии она принимает все д различных значений, каждое ровно по одному разу.

Если значение n-арной квазигруппы трактовать как дополнительный символ, то получится МДР-код с расстоянием 2.

Определения 1-совершенных кодов и МДР кодов в приведенной выше форме имеют определенную общность, которая в частности подчеркивает, что оба класса относятся к категории «точных» комбинаторных конфигураций. Эти классы кодов молено единообразно определить иначе: если удаление некоторого независимого множества вершин графа Нд приводит к регулярному графу степени (q—1)™ — 1 или (g—2)п, то это множество является 1-совершенным кодом или МДР-кодом с расстоянием 2 соответственно. Такая постановка близка к вопросам, изучаемым в алгебраической теории графов. На самом деле, как 1-совершенные коды, так и МДР-коды с расстоянием 2 являются важнейшими частными случаями так называемых регулярных разбиений, в англоязычной литературе известными также как equitable partitions (термин «equitable» в данном контексте не имеет удобного перевода), а на русском языке больше известными как совершенные раскраски. Наряду с дистанционно регулярными графами и схемами отношений, совершенные раскраски (equitable partitions) являются популярными объектами алгебраической комбинаторики, см. напр. [35], [46].

Отмеченная связь постановок была упомянута, чтобы подчеркнуть общую природу изучаемых объектов, к существу вопросов, рассматриваемых в диссертации, прямого отношения она не имеет. Для нас более важна конструктивная связь: существуют способы построения 1-совершенных кодов из n-арных квазигрупп, впервые предложенные К. Т. Фелпсом [65], [66], см. также [15], [52]. Поэтому результаты, полученные для n-арных квазигрупп, важны и для теории 1-совершенных кодов, к примеру, эта связь использовалась в работах [I], [31], [52], [16], [54].

Прежде чем перейти к рассмотрению классов 1-совершенных кодов и гс-арных квазигрупп отдельно, отметим один общий для них вопрос, вопрос о числе объектов. Известно, что число 1-совершенных кодов в Нд растет дважды экспоненциально при росте п, если q есть степень простого числа, а п~ (qm — l)/(q — 1) (это необходимое для существования 1-совершенных кодов условие на п следует из известных соображений: мощность пространства должна делиться на мощность 1-шара),

то есть нижняя оценка на число кодов имеет вид 2" , где с — некоторая константа. В двоичном случае такая оценка, с с — 1/2, была установлена Ю. Л. Васильевым одновременно с открытием нелинейных 1-совершенных кодов [8], на случай произвольного д, равного степени простого числа, конструкция обобщена Дж. Шонхеймом [70]. Следует отметить, что существование совершенных кодов в Я™ для q, не пред-ставимого в виде степени простого числа, является известной открытой проблемой в данной области; однако, если только существует хотя бы один такой код, известные методы позволяют построить коды для бесконечного числа значений п с тем же д [66], причем число таких кодов будет расти дважды экспоненциально по п. Известная верхняя оценка числа 1-совершенных кодов с точки зрения асимптотики двойного логарифма не отличается от числа всевозможных подмножеств (в двоичном случае 22" '°к , см. [1]). Улучшения нижних оценок в сериях работ [2], [20], [I], [V] (глава 6 диссертации), для двоичного случая, и [42], [17], [27], [18], [52], для кодов над д-значным алфавитом, важны больше с точки зрения понимания возможного строения совершенных кодов, чем в контексте проблемы асимптотики двойного логарифма числа кодов, хотя для <1 > 3 нижняя граница этой асимптотики была реально поднята [18], [52] (в последней работе для этого использовалась связь с п-арными квазигруппами).

Таким образом, основной проблемой является установить константу при п в асимптотике двойного логарифма числа 1-совершенных кодов (мощность алфавита д считается фиксированной). При этом даже существование такой константы не доказано, хотя противное и кажется фантастикой.

Ситуация с п-арными квазигруппами порядка д > 3 аналогична. Дважды экспоненциальное по п число квазигрупп составного порядка следует из известной конструкции сплетения п-арных квазигрупп (термин «сплетение» в данном случае никак не соотносится со сплетением групп), а для простых порядков, начиная с 5, установлено относительно недавно [56]. Для порядка меньше 4 проблема с числом п-арных квазигрупп тривиальна, поскольку существует только одна тг-арная квазигруппа, с точностью до простых преобразований эквивалентности.

Верхнюю оценку числа объектов, с точки зрения асимптотики двойного логарифма, удается несколько улучшить по сравнению с числом всех функций, см. [26]. Однако в случае д > 4 асимптотики двойного логарифма нижней и верхней оценок числа п-арных квазигрупп порядка </, как и для 1-совершенных кодов, расходятся. Единственным классом объектов, для которых проблема асимптотики двойного логарифма числа решена, является класс гг-арных квазигрупп порядка 4. Более того, существует и является одним из основных результатов диссертации характеризация этого класса и, как следствие, известна асимптотика самого числа объектов. (На самом деле, асимптотика получена В.Н.Потаповым ранее и опубликована в совместной статье [25].) Проблема оценки дважды экспоненциального числа комбинаторных объектов известна и в других разделах дискретной математики. Одним из примеров является класс бент-функций, которые определяются как булевы функции {0,1}™ —> {0,1}, на которых определенным образом заданная мера нелинейности достигает теоретической верхней границы. Бент-функции существуют при всех четных п, а нижняя и верхняя оценки их числа, как и для числа 1-совершенных двоичных кодов, имеют вид 22"/2±°(,,) и 22"1"'"' соответственно [36]. Таким образом, проблема оценок подобного рода достаточно широка, и осмысление способов ее решения — это дело будущего. Хочется подчеркнуть, что величины столь большого роста находятся за рамками интуитивного восприятия (по крайней мере автора диссертации), поэтому бывает трудно вообразить природу тех факторов, которые могли бы оказать существенное влияние на верхнюю и, кроме известных конструктивных подходов, нижнюю оценки. Трудность восприятия таких чисел приводит порой к тому, что для некоторых исследователей получение дважды экспоненциальной нижней оценки закрывает вопрос о числе объектов — это число по своей величине в каком-то смысле сравнимо с числом всех подмножеств пространства. На самом же деле нижняя оценка по сравнению с верхней остается почти ничем даже после логарифмирования.

п-Арные квазигруппы. Сам термин алгебраический и, строго говоря, обозначает пару (Е, /), где Е — некоторое множество, а / — п-арная операция такая, что в уравнении хо — /(х\,..., хп) значения любых п переменных из хо, а'1,... ,хп всегда однозначно задают значение оставшейся

переменной. Как видно из названия, понятие п-арной, или многоместной (в англоязычной терминологии используются термины «ро1уас№с» или «тикагу»), квазигруппы является обобщением понятия группы. Действительно, в случае п — 2 добавление аксиомы ассоциативности приводит к определению группы. Некоторое стандартное упрощение терминологии, которое используется в тексте диссертации, — называть п-арной квазигруппой саму операцию, как правило это не приводит к разночтениям. В случае конечного носителя £ такие отображения также известны в комбинаторике как латинские гиперкубы порядка д — |Е| и часто, по аналогии с латинским квадратом (случай п — 2), интуитивно ассоциируются с п-мерной таблицей, д х д х... х заполненной символами алфавита £ правильным образом — так, что в каждом ряду (линии) каждого из п базовых направлений все символы встречаются в точности по одному разу. Однако в некоторых случаях оказывается гораздо удобней работать с графиком {(хо,хь... ,хп) : хо = /(жь • • • ,£«)} п-арной квазигруппы, а не с самой операцией. В теории кодирования такие множества известны как МДР-коды с расстоянием 2. При рассмотрении графика п-арной квазигруппы вместо самой операции оказывается, что зависимая переменная наделена теми же «правами», что и все остальные, что делает многие формулировки более естественными, а доказательства более короткими. Однако в некоторых вопросах, например, при рассмотрении суперпозиции двух или более квазигрупп, функциональная форма все же оказывается необходимой, поэтому порой приходится использовать одновременно обе терминологии.

Фундаментальные результаты в алгебраической теории п-арных квазигрупп, которыми во многом определяется развитие этой теории начиная с 60-х годов прошлого века, принадлежат В. Д. Белоусову (см. напр. [б], [5]), начинавшему свою деятельность в этой области под руководством А. Г. Куроша. Отдельные классы многоместных операций со свойством однозначной обратимости изучались значительно раньше. Одной из первых работ является работа В.Дёрнте [41], положившая начало изучению п-арных групп (ассоциативных п-арных квазигрупп).

В последнее время возрастает интерес к п-арным квазигруппам как к комбинаторному объекту, что отчасти стимулируется возможными приложениями к теории кодирования и криптографии (см. напр. [71]), отча-

сти просто тем, что n-арные квазигруппы (латинские гиперкубы) являются очень естественным обобщением латинских квадратов — классических математических объектов, известных многим со школьной скамьи. В частности, появилось несколько работ с результатами по классификации латинских гиперкубов с малыми параметрами. В последней работе известных австралийских математиков Б. Мак-Кэя и Я. Уонлеса [63] получено число латинских п кубов порядка 4 до п — 5, порядка 5 до п — 4 и порядка 6 до п = 3, причем сосчитано также число классов эквивалентности для различных естественно определенных эквивалент-ностей, представители классов доступны на веб-ресурсе [62]. Продвинуться в большие размерности при помощи переборных алгоритмов не представляется возможным на любых компьютерах, доступных в ближайшем будущем (напомним, что число объектов растет дважды экспоненциально). Число n-арных квазигрупп порядка 3 не было упомянуто не случайно. Существует только одна такая квазигруппа, с точностью до изотопии (перестановки элементов носителя независимо в каждом аргументе), а всего — 3 • 2й. Это факт достаточно простой и, хотя самая ранняя из известных ссылок [44] (см. также [57, Corollary 13.25]) относится к последней декаде прошлого века, был известен намного раньше. Таким образом, порядок 4 — первый нетривиальный порядок с точки зрения n-арных квазигрупп. Именно этому порядку уделяется наибольшее внимание в диссертации и, хотя некоторые утверждения интересны в более общем контексте и применимы также и для других, не обязательно конечных, порядков, изначальной мотивацией и основным применением результатов исследований, описанных в первой части диссертации, в настоящий момент является классификация n-арных квазигрупп порядка 4.

В первой работе [I] автора диссертации 2000 года по n-арным квазигруппам порядка 4 нижняя оценка числа таких объектов устанавливается подсчетом числа изотопов n-арных квазигрупп, полученных сплетением квазигрупп порядка 2 (позже такие квазигруппы порядка 4 были названы полулинейными). После этого В. Н. Потапов сформулировал гипотезу, согласно которой любая n-ариая квазигруппа порядка 4 полулинейна или разделима, то есть представима в виде бесповторной суперпозиции квазигрупп меньшей арности. В частности, из этого

следовало бы, что класс полулинейных тг-арных квазигрупп асимптотически самый мощный, и нижняя оценка в [I] асимптотически точна. Несмотря на простоту формулировки и некоторые интуитивные соображения, на которых строилась гипотеза, найти короткое доказательство, по состоянию на текущий момент, не удалось. Полный текст имеющегося доказательства состоит из четырех статей [VII], [25], [IX], [X], каждая из которых представляет самостоятельное исследование, со своими подходами и терминологией и результатами, актуальность которых не ограничивается контекстом п-арных квазигрупп порядка 4. (Две статьи принадлежат автору диссертации, две написаны в соавторстве в В. Н. Потаповым. В диссертацию не вошла только работа [25], поскольку основная лемма, как и главный результат статьи — асимптотика числа п-арных квазигрупп порядка 4, — принадлежат В. Н. Потапову.) Промежуточным этапом исследования, который позволил ближе ознакомиться с предметом и разработать инструментарий, являлось получение верхних оценок числа квазигрупп порядка 4 [55], [25].

Возможно, утверждение о строении п-арных квазигрупп порядка 4 не прошло достаточную проверку временем и вниманием математической общественности, чтобы говорить о вероятности того, что более короткое решение не будет найдено в ближайшее время. Однако разработанная для текущего доказательства теория обладает достаточной степенью общности, чтобы быть интересной вне контекста парных квазигрупп порядка 4. Кроме того, обнаруживаются некоторые связи, которые косвенно указывают на то, что все действительно не так просто, как может показаться из формулировок теорем. Недавно В. Н. Потапов анонсировал следующее утверждение [68]: (*) любая частичная п-арная квазигруппа порядка 4, значения которой заданы на {0,1,2,3}""1 х {0,1}, может быть дополнена до п-арной квазигруппы {0,1,2,3}" -> {0,1,2,3}. Этот факт имеет следующую эквивалентную формулировку: пусть множество вершин графа Щ разбито на два подмножества, порождающие регулярные подграфы степени п, тогда эти подграфы являются или не являются двудольными одновременно. Оказывается [54], подобным образом (в терминах одновременной двудоль-ности элементов регулярного разбиения множества вершин графа Хэм-минга) можно переформулировать и следующую проблему: (**) каж-

дый ли максимальный по мощности двоичный код длины 2т — 3 с расстоянием 3 можно получить двукратным укорочением некоторого 1 -совершенного кода длины 2т — I? Более того, как отмечено в [54], для некоторого подкласса кодов положительный ответ на вопрос (**) эквивалентен утверждению (*). В то же время в общем случае ответ на вопрос (**) отрицательный [64], контрпример был найден с использованием компьютера. Это говорит о том, что не существует общих аргументов, доказывающих (*), которые могли бы быть обобщены на (**), и для доказательства (*) нужен подход, использующий специфику именно этой задачи. И действительно, имеющееся доказательство [24] использует характеризацию п-арных квазигрупп порядка 4 и даже при этом достаточно трудоемко.

Вернемся к общим вопросам, касающимся п-арных квазигрупп. Важнейшую роль в их исследовании, как комбинаторных объектов, играет понятие разделимости. Разного вида редуцируемость больших объектов к меньшим рассматривается для многих классов математических объектов. Для класса многоместных квазигрупп, который замкнут относительно бесповторной суперпозиции, естественный вопрос представимости в виде такой суперпозиции возник на самом раннем этапе их исследования, как и вопрос существования неразделимых (не представимых в виде бесповторной суперпозиции) п-арных квазигрупп. Этот вопрос известен как одна из проблем В. Д. Велоусова (проблема номер 5 из монографии [5]) и решен для различных порядков в работах В. Д. Велоусова и М. Д. Сандика [6], В. Р. Френкина [28], В. В. Борисенко [7], М. М. Глухова [9], М.А.Акивиса и В. В. Гольдберга [10], [11], [30], Кротова, В.В.Потапова и П.В.Соколовой [56]. Единственным известным в настоящее время способом строить неразделимые п-арные квазигруппы конечных порядков больше 3 является метод свитчинга, состоящий в локальной замене значений квазигруппы на некотором подмножестве области определения. (Следует заметить, что в алгебраической теории п-арных квазигрупп больше известно понятие приводимости, то есть представимости в виде бесповторной суперпозиции с тем же порядком переменных, что и в самой квазигруппе, см. напр. [5]. Это связано с тем, что порядок переменных существенен для выполнимости дополнительных алгебраических аксиом.) Крайне важным для пони-

мания структуры разделимых п-арных квазигрупп фактом является существование и в определенном смысле единственность канонического разложения в древовидную бесповторную суперпозицию неразделимых квазигрупп и групп, установленные А. В. Черемушкиным [29].

Разделимости квазигрупп посвящены три из четырех глав первой части диссертации. Первоначально исследования ориентировались на описание п-арных квазигрупп порядка 4, которое можно считать главным результатом первой части диссертации. Однако результат главы 2 в представленном виде — завершенное утверждение, применимое к угарным квазигруппам произвольного порядка (результаты, дополняющие теорию именно для произвольного порядка, получены в последней совместной работе [XI]) и полезное для исследования классов многоместных квазигрупп, замкнутых относительно взятия ретракта (ре-тракт многоместной квазигруппы получается при фиксации константами значений одного или более аргументов). Примеры использования полученного в главе 2 признака разделимости для характеризации классов п-арных квазигрупп приведены в главе 3.

Совершенные коды. Согласно широко известной теореме В.А.Зиновьева, В.К.Леонтьева и Э.Титвайнена [13], [14], [75], при д равном степени простого числа нетривиальные (т.е. О < г < п/2) /■-совершенные коды существуют только в следующих случаях:

- 1-совершенные коды в Нд* с параметрами кода Хэммин-га, который является единственным с точностью до эквивалентности линейным кодом из этого класса. (Р. У. Хэмминг рассматривал только двоичные коды [49]; общая конструкция, как и коды Голея, предложена М. Дж. Е. Голеем в полустраничной заметке [47].) Однако при непростых г; существуют групповые (то есть замкнутые относительно сложения, но не обязательно относительно умножения на скаляр) 1-совершенные коды, неэквивалентные коду Хэмминга [60]. Число же негрупповых 1-совершенных кодов оценивается снизу дважды экспоненциальным относительно размерности пространства числом, см. последние нижние оценки в [V], [52].

- Коды Голея: построенные М. Дж. Е. Голеем [47] 3-совершенный код в Я|3 и 2-совершенный код в Я3П. Каждый из этих кодов является единственным с точностью до эквивалентности [39].

Вопрос существования g-значных совершенных кодов в случае, когда q не есть степень простого числа, является известной открытой проблемой в общей теории совершенных кодов. Известно, что не существует i-совершенных кодов при t $ {1,2,6,8} [32] и при t > 1 в случае q — 2а3" [4]; известно, что не существует групповых совершенных кодов [58]; известно, что не существует 1-совершенного кода в Щ [48] (последнее следует из несуществования двух ортогональных латинских квадратов размера 6x6 [74]) — наименьших параметрах, удовлетворяющих необходимым условиям: п — 1 = 0 mod q (следствие из теоремы Ллойда для произвольного алфавита [58], [3], [12]) и q(n-i)jq+\ s о mofj _ 2) 4-1) ([51], [69], следствие равномерной распределенности вершин 1-совершенного кода по подкубам размерности (n-l)/g + l).

Существование совершенных кодов исследуется и в отличных от хэм-минговых метрических пространствах и графах. Ввиду применимости мощного аппарата алгебраической теории графов, особый интерес с этой точки зрения уделяется дистанционно-регулярным графам. Так, известная гипотеза Дельсарта [12] о несуществовании нетривиальных совершенных кодов в графах Джонсона на данный момент не решена (см. последнюю работу [43] на эту тему и библиографию в ней), в то время как аналогичный факт для графов Грассмана и графов билинейных форм доказан относительно давно JI. Чихарой [37] (другое доказательство представлено У. Дж. Мартином и З.Дж. Жу [61]).

В главе 7 диссертации рассматриваются совершенные коды с расстоянием 3 в пространстве троичных n-слов веса п — 1 (то есть содержащих ровно один нуль). Такие коды были построены в работах М. Сванстрёма [73], [72], Дж. Ван Линта и Л. Толхьюзена [77] на основе смежных классов по двоичному коду Хэмминга. В работе автора диссертации [53], уже используя технику из теории нелинейных совершенных кодов, построено дважды экспоненциальное число совершенных троичных равновесных кодов. В главе 7 показано, что на основе смежных классов по коду Хэмминга можно строить как неэквивалентные совершенные коды, так и коды с новыми параметрами — оптимальные коды с расстоянием 5, — в пространстве троичных n-слов веса п — 1. Заметим, что хотя рассматриваемое пространство, в отличие от случая равновесных

двоичных кодов, не обладает свойством дистанционной регулярности, равновесные ç-значные коды являются достаточно популярными объектами в теории кодирования.

Как уже было отмечено, над конечными полями непростой мощности возможно существование неэквивалентных 1-совершенных кодов, замкнутых относительно покоординатного сложения. В двоичном случае такой код единственный — код Хэмминга. Однако при помощи отображения Грея 0 —> 00, 1 —»■ 01, 2 —> 11, 3 —> 10, при покоординатном действии являющимся изометрией между n/2-мерным четверичным пространством с метрикой Ли и n-мерньш двоичным пространством Хэмминга, некоторые нелинейные коды представимы в виде образов линейных кодов над кольцом Z4 [50] (такие коды принято считать 2*4 линейными, в смысле [50]) или над смешанным Z2Z4 алфавитом. Возможность представлять хорошие нелинейные двоичные коды как линейные над недвоичными алгебраическими структурами была впервые обнаружена А.А.Нечаевым в работах [21], [22]. В статье А. Р. Хэммонса и др. [50] для подобного представления использованы изометрические свойства отображения Грея. Идея использования масштабных изометрий для построения кодов была развита в работе А.А.Нечаева и Т.Хонольда [23]. 1-Совершенные и расширенные 1-совершенные двоичные коды, представимые при помощи кода Грея как линейные коды над Z4 или смешанным Z2Z4 алфавитом, изучались в работе [И] и в работах Дж. Боргеса, К. Т. Фелпса и Дж. Рифы [34], [67], [33]; оказалось, что число таких неэквивалентных кодов растет примерно как логарифм от длины, и значения параметров, характеризующих «близость» к линейному коду (ранг — размерность линейной оболочки; размерность ядра — множества периодов), для них различные. В диссертации (глава 8) предложен способ построения расширенных 1-совершенных кодов из линейных кодов над кольцом Z^ ■ Использованное обобщение отображения Грея неоднозначно при к > 2, что позволяет сохранить плотность упаковки.

Цель работы: построение новых классов n-арных квазигрупп и кодов — 1-совершенных двоичных кодов, а также бесконечного класса оптимальных троичных равновесных кодов с новыми параметрами; ха-

растеризация классов п-ариых квазигрупп малого порядка и линейных аналогов расширенных 1-совершенных кодов над кольцами обнаружение новых зависимостей внутри исследуемых классов объектов.

Методы исследования. В исследованиях используются традиционные методы и аппарат алгебраической и комбинаторной теории кодирования, теории графов, комбинаторного анализа, метод свитчинга, суть которого состоит в локальном изменении объекта с сохранением его основных параметров, а также разработанные автором методы, в частности анализа разделимости п-арных квазигрупп.

Научная новизна. Основные результаты диссертации являются новыми и состоят в следующем:

1) Доказаны признаки разделимости п-арных квазигрупп: для порядка 4 в терминах связности прообраза двух значений и для произвольного порядка в терминах максимальной арности неразделимого ре-тракта.

2) Получена характеризация п-арных квазигрупп порядка 4: любая п-арная квазигруппа порядка 4 является полулинейной или разделимой. Показано, что все п-арные квазигруппы порядков 5 и 7, бинарные ретракты которых изотопны циклической группе, являются разделимыми при п > 4.

3) Введено понятие свитчинговой разделимости графов, которая эквивалентна разделимости га-арных квазигрупп, построенных по этим графам определенным образом. Показано, что если при удалении любой вершины или любых двух вершин графа получается разделимый подграф, то сам граф является разделимым. С другой стороны, построена бесконечная серия неразделимых графов, у которых удаление любой вершины приводит к разделимому подграфу. Это дает пример неразделимых п-арных квазигрупп, все (п—1)-арные ретракты которых разделимы.

4) Доказано, что любой, в том числе нелинейный, двоичный код с расстоянием 3 всегда можно вложить в 1-совершенный код некоторой большей длины.

5) Предложен метод построения 1-совершенных кодов, дающий самый многочисленный из известных в настоящий момент класс 1-совершенных двоичных кодов.

6) Построен бесконечный класс диаметрально совершенных (как следствие, оптимальных) троичных равновесных кодов с расстоянием 5.

7) Представлено новое обобщение отображения Грея Ф :

связанное с известным обобщенным отображением Грея (р следующим образом: если взять два дуальных линейных -кода и построить из них двоичные коды, используя обобщения и Ф отображения Грея, то весовые нумераторы полученных двоичных кодов будут связаны тождеством Мак-Вильямс. Описаны классы кодов Адамара и расширенных 1-совершенных кодов, полученных из линейных -кодов при помощи старого и нового обобщенного отображения Грея.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные в ней результаты могут быть использованы в различных разделах общей теории п-арных квазигрупп, теории кодирования, криптографии, стеганографии.

Апробация работы. Результаты работы докладывались на научных семинарах «Математические вопросы кибернетики» ММФ НГУ, «Теория информации и теория кодирования» ИППИ РАН, семинаре Кафедры безопасности информационных систем ГУАП, «Теория кодирования» и Общеинститутском семинаре Института математики им. С. Л. Соболева СО РАН, в Похангском государственном университете (г. Поханг, Республика Корея, цикл из б лекций), включены в список важнейших научных результатов ИМ СО РАН за 2006, 2008 и 2009 годы, прошли апробацию на следующих научных конференциях и совещаниях:

• Международные конференции по алгебраической и комбинаторной теории кодирования АССТ (2002 в Царском Селе, 2004 в Болгарии, 2006 в Звенигороде);

• Международная конференция по оптимальным кодам и смежным вопросам ОС 2005 (Болгария);

• Международная конференция по кодированию и криптографии WCC 2001 (Париж);

• Международная конференция по схемам отношений, кодам и дизайнам Сот2МаС 2004 (Ю. Корея);

• Международная конференция «Coding Theory Days in St.-Petersburg» (2008, Санкт-Петербург);

• Конференция «Математика в современном мире» (2007, Новосибирск);

• IX международный семинар «Дискретная математика и ее приложения» (2007, Москва);

• VI сибирская научная школа-семинар «Компьютерная безопасность и криптография» SIBECRYPT (2007, Горно-Алтайск);

• Конференции «Дискретный анализ и исследование операций» DAOR (2000, 2004, Новосибирск).

Публикации. Основные материалы диссертации опубликованы в 12 статьях в журналах, рекомендованных ВАК. Работы [XIJ и [X], результаты которых изложены в главах 2 (кроме раздела 2.2) и 3, написаны в неразделимом соавторстве с Владимиром Николаевичем Потаповым. Работы [IV] и [V] (главы 5 и 6) — в неразделимом соавторстве с Сергеем Владимировичем Августиновичем. По главам, результаты опубликованы: глава 1 — [VII]; глава 2 — [IX], [XI]; глава 3 — [X], раздел 3.5 в [XI]; глава 4 - [XII], [VIII]; глава 5 - [IV]; глава б - [I], [V]; глава 7 -[VI]; глава 8 — [II], [III]. Большинство результатов были предварительно опубликованы в трудах и тезисах конференций [ХШ]-[ХХН].

Структура и объем работы. Диссертация состоит из введения, двух частей, разбитых на восемь глав, и списка литературы (158 наименований, включая 22 работы автора по теме диссертации, приведенные в конце списка). Текст работы изложен на 225 страницах.

СОДЕРЖАНИЕ РАБОТЫ

В первой части диссертации рассматриваются n-арные квазигруппы.

Множество £ с определенной на нем n-арной операцией / : Е™ —> £ называется n-арной квазигруппой порядка |Е|, если в равенстве ! хп) — хп+\ любые п элементов из Х\, ..., хп, хп+\ однозначно задают оставшийся элемент. Саму функцию / при этом будем также называть n-арной квазигруппой.

п-Арная квазигруппа / называется разделимой, если существуют такие т £ {2,... ,п — 1}, (п — т + 1)-арная квазигруппа h, m-арная квазигруппа g и перестановка а : {1,..., п} {1,..., п}, что

f(xi,..., хп) = h(g(x^x),.. .,ха(т)),ха(т+1),..., ха(п))

(т. е. / есть суперпозиция h и д). Если n-арная квазигруппа не является разделимой, то она называется неразделимой.

Если у n-арной квазигруппы / или у функции, обратной ей по некоторому аргументу, зафиксировать один или более аргументов, то мы получим квазигруппу некоторой меньшей арности к, называемую ре-трактом п-арной квазигруппы /.

n-Квазигруппы fug называются изотопными, если для некоторого набора Т — (то, т\,..., тга) перестановок носителя Е выполняется тождество f(xi,...,хп) = тй1д(т1х 1,... ,т„хп).

и-Арная квазигруппа / : £™ Е порядка 4 называется полулинейной, если для некоторых a,b £ Е характеристическая функция Ха,ь прообраза /-1({а, £>}) представима в виде

Xa,b(xi,... ,хп) = Xi(xi) + ••• + Хп(хп) mod 2

для некоторых Хь • • ■ > Хп '■ 2 —> {0,1}. Заметим, что для фиксированных Xi>-- - >Хп существует ровно 2П полулинейных n-арных квазигрупп с данной Ха,ь- Им можно поставить в соответствие n-местные булевы функции, задающие выбор значений а или b (в точках, где \а,ь — 1) и среди двух оставшихся элементов Е (в точках, где Ха,ь — 0) на определенных 2™ наборах из Е™ так, что на оставшихся наборах / определяется однозначно.

В главе 1 доказан признак разделимости гг-арных квазигрупп порядка

4 в терминах связности графа смежности прообраза двух выбранных значений a,b € Е. Пусть Е = {0,1,2,3}. Множество S С Е" назовем 2-МДР-кодом (двукратным МДР-кодом) длины гг, если для любого х е Е и для любой координаты г € {1,..., п} найдется ровно два элемента множества S, совпадающих с х во всех позициях кроме может быть г-й. Для множества S С Е" через G(S) будем обозначать граф на множестве 5, в котором два набора из этого множества соединены ребром тогда и только тогда, когда они различаются ровно в одной позиции.

Теорема 1 (следствие 1.17). Граф G(S) 2-МДР-кода S не связен тогда и только тогда, когда характеристическая функция множества

5 есть бесповторная сумма характеристических функций 2-МДР-кодов меньших длин.

Теорема 2 (следствие 1.24). Пусть / : Еп —> Е — n-арная квазигруппа, a,b € Е, a ф Ь, число компонент связности 2-МДР-кода /-1({а, 6}) равно К и k = 1 + log2 К.

(a) Если 1 < к < п, то n-арная квазигруппа f является разделимой.

(b) Если к — п, то n-арная квазигруппа f является полулинейной.

В главе 2 доказан признак разделимости n-арных квазигрупп произвольного порядка в терминах разделимости ретрактов:

Теорема 3 (теорема 2.1). Пусть f — неразделимая n-арная квазигруппа, п > 4. Тогда f имеет неразделимый (п—1)-арный или (п—2)-арный ретракт. Более того, если порядок n-арной квазигруппы f конечный и простой, то f имеет неразделимый (п—1)-арный ретракт.

Другими словами, если все (n—1)- и (n—ty-ретракты n-арной квазигруппы разделимы, то сама квазигруппа также разделима. Для разделимости n-арной квазигруппы простого конечного порядка достаточно разделимости всех ее (гг—1) -арных ретрактов.

В главе 3 с использованием признаков разделимости из предыдущих глав доказана характеризация п-арных квазигрупп порядка 4:

Теорема 4 (теорема 3.3). Каждая п-арная квазигруппа порядка 4 является разделимой или полулинейной.

В доказательстве использованы признаки разделимости из предыдущих глав. Кроме того, эти признаки использованы для характеризации интересного подкласса класса п-арных квазигрупп порядков 5 и 7. Будем говорить, что п-арная квазигруппа порядка к сублинейная, если все ее бинарные ретракты изотопны циклической группе Z)t.

Теорема 5 (теорема 3.9). Все сублинейные п-арные квазигруппы порядка 5 разделимы при п > 4. Все сублинейные п-арные квазигруппы порядка 7 разделимы при п > 3.

Заметим, что существует пример неразделимой сублинейной тернарной квазигруппы порядка 5.

В главе 4 вводится понятие свитчингой разделимости графа, которое, в рамках описанного способа построения п-арных квазигрупп по графам, соответствует разделимости п-арных квазигрупп. Граф О = {V, Е) назовем свитчингово разделимым, если ¡У| > 4 и для некоторого полного двудольного графа Кцу\и — (V, Еиу\а) граф (V, Е д Ецу\и) (известный как {/-слзитчинг графа С) несвязный, причем каждая компонента связности содержит не более чем п — 2 вершины. Для графов доказывается теорема, аналогичная теореме 3 для квазигрупп:

Теорема 6 (теорема 4.2). Бели все подграфы, порожденные п — 1 или п — 2 вершинами графа (? порядка п свитчингово разделимы, то С — свитчингово разделимый граф.

Формально, этот факт является следствием теоремы 3. Но его доказательство значительно проще, хотя и повторяет общий ход рассуждений разделов 2.2 и 2.5. Кроме того, доказано следующее:

Теорема 7 (теорема 4.3). Для любого нечетного в существует свитчингово неразделимый граф порядка п, у которого все порожденные подграфы порядка п — 1 свитчингово разделимы.

Следствием для п-арных квазигрупп является следующий факт:

Теорема 8 (теорема 4.15). Для любого четного п и любого целого к > 0 существует неразделимая п-арная квазигруппа / порядка 4к, все (п—1)-арные ретракты которой являются разделимыми.

Для п-арной квазигруппы / обозначим через «:(/) наибольшую арность ее неразделимого ретракта. Из теоремы 8 следует, что условия теоремы 3, в которой утверждается, что из к(/) < п — 3 следует разделимость п-арной квазигруппы /, не могут быть в общем случае расширены до к(/) < п - 2.

Во второй части диссертации рассматриваются 1-совершенные двоичные коды или расширенные 1-совершенные двоичные коды, получаемые из 1-совершениых добавлением к каждому кодовому слову еще одного символа, равного сумме по модулю два всех остальных, а также коды с другими параметрами, так или иначе связанные с двоичными совершенными. Напомним, что весом кодового слова называется число ненулевых символов в этом слове, (п, М,сГ) -кодом называется код длины (длины кодовых слов) п, мощности М и попарным расстоянием не меньше <1 между кодовыми словами.

В главе 5 доказана следующая теорема:

Теорема 9 (теорема 5.4). Любой двоичный код С С {0,1}т с расстоянием не меньше 3 является укорочением некоторого 1-совершенного кода Р(С) длины п — 2Ш, т.е.

С = {I £ Гт1(с,0п~т) е Р(С)}.

Другими словами, любой двоичный код с расстоянием не меньше 3 вкладывается в 1-совершенный код некоторой большей длины. Простыми следствиями этого факта являются классические теоремы о вложении так называемых частичных систем троек и четверок Штейнера в полные системы [76], [45] (см. также обзоры в [59], [38]).

В главе 6 приводится конструкция 1-совершенных двоичных кодов, дающая рекордную нижнюю оценку их числа:

Теорема 10 (теорема 6.15). Число В(п — 1) 1-совершенных двоичных кодов длины п — 1 = 2т — 1 удовлетворяет неравенству

20

В(п-1) > KLA(") =

- jrffrrw.....

В частности, KLA{32) « 22363-79.

Предыдущая оценка [I] состояла из двух мультипликативных членов (4 = 1,2) формулы. Заметим, что про асимптотику двойного логарифма числа В(п) эта теорема не говорит ничего нового, со времен пионерской работы Ю. Л. Васильева [8] с этой точки зрения улучшения получено не было (известно, что асимптотика не меньше п/2 и не больше п). Ценность новой оценки не в формуле, а в том, что в рамках современного понимания проблемы 1-совершеиных кодов оценку не удается асимптотически улучшить (даже умножив на константу, что нельзя было сказать про все предыдущие оценки). Можно сформулировать гипотезу, что полученная нижняя оценка асимптотически точна. В пользу этой гипотезы говорит тот факт, что приведенная конструкция накрывает почти все коды, размерность линейной оболочки которых на 1 или 2 превышает размерность линейного 1-совершенного кода, что следует из характеризации таких кодов в терминах п-ар пых квазигрупп порядка 4 [31] и асимптотики числа таких квазигрупп [25].

В главе 7 рассмотрено построение равновесных троичных кодов при помощи смежных классов по линейному 1-совершенному двоичному коду, коду Хемминга. Для удобства вместо слов длины п с весом (числом ненулевых элементов) п — 1 рассматривается множество Хп слов в алфавите {0,1, *}, содержащих ровно один символ * (иногда этот символ удобно трактовать как {0,1}, а слова из Хп — как пару соседних двоичных слов, или ребро двоичного графа Хемминга). Для двух двоичных

кодов P,Q обозначим R(P, Q) = {f G Хп | d(x,P) = d(x,Q) = 1}, где

d{-,-) — расстояние Хемминга. Пусть п = 2т > 4 и ai,a2,...,a„ — все элементы множества {0,1}т. Для любого /3 G {0,1}т определим мно-

п п

{(хих2,...,хп) € {0,1}п | 5> = 0, J2xiai = P}i

¿=1 ¿=1 п n

{(хихъ...,хп) g {о,i}n| Yhxi = 11 YlXiai =

г=1 г=1

которые являются смежными классами по расширенному коду Хемминга. Следующая теорема обобщает результат [72], [77], где для каждого п = 2т был построен только один (п, 2", 3)-код.

Теорема 11 (теорема 7.9, следствие 7.16). Пусть f : {0,1}т -»

{0,1}т — линейный оператор, удовлетворяющий следующим свойствам:

a) f — биекция,

b) f + Id — биекция.

Множество Chj '= U/3g{o iявляется совершенным (n, 2", 3)-кодом в Хп.

Более того, при m > 4 существует два оператора /', /" : {0,1}т —> {0,1}т, удовлетворяющие условиям а) и Ь), такие, что совершенные коды Сн,/' и Chj" неэквивалентны, то есть не получаются друг из друга применением одновременно ко всем кодовым словам перестановки координат и/или инверсиями О о 1 символов в выбранных координатах.

Функция / : {0,1}т {0,1}от называется ПСН функцией (почти совершенно нелинейной), если для любой пары (а; Ь) ф (0т; 0та) элементов {0,1}т система уравнений

Îx + у ~ a

№ + ш = ь

либо не имеет решения, либо имеет ровно два решения {х\ у) (другими словами, образы четырех точек, образующих невырожденный параллелограмм, никогда не образуют параллелограмм). Обозначим

п п

Qf = {(XI, ®2, ...,*„)€ {0,1П1> = 1. Х>/Ы=о™}

¿=1 »=1

жества

ттО lir

Hр -

Н\ 'Ш

Теорема 12 (теорема 7.20). Если / : {0,1}т -> {0,1}т - взаимнооднозначная ПСН функция, то множество R(Hgm, Qj) является (n = 2т, 22"1 ~т-1,5)-кодом в Хп.

Хорошо известно, что взаимнооднозначные ПСН функции, или ПСН перестановки (APN permutations) существуют при всех нечетных m > 3. При m — 4 такой перестановки не существует, а их существование при больших четных m долгое время являлось открытой проблемой. Недавно [40] был найден первый пример ПСН перестановки для m — 6. Таким образом, построена бесконечная серия кодов с расстоянием 5 в Хп, причем нетрудно доказать, что построенные коды оптимальны, то есть имеют максимальную мощность среди кодов с расстоянием 5 в том же пространстве.

В главе 8 рассматриваются двоичные коды, в том числе расширенные 1-совершенные, построенные из линейных кодов над кольцом Z2t. Для того, чтобы сформулировать результаты главы, нам понадобится несколько определений.

Пусть m = 2fc _1. Пусть А С Z™ есть (m, 2m, т/2)-код Адамара и А — {ао, а 1,..., a^m-i}, где ао есть слово из всех нулей и (Ii + Oj+m есть слово из всех единиц для каждого г от 0 до m—1. Определим обобщенное отображение Грея : Z^ —> следующим правилом:

<р(х\,..., х„) = (aXl,...,aXlt).

Известно [23], что является изометричным вложением пространства i?2m со специально определенной метрикой в в mn-мерное двоичное пространство Хемминга.

Далее, пусть {Но,..., H^m-i} — разбиение Z™ на расширенные 1-совершенные (m, 2m/2m, 4)-коды (например, в качестве Hq мы можем взять расширенный код Хемминга, а в качестве остальных частей — смежные классы по нему). Более того, будем полагать, что Hq содержит слово из всех нулей б и четность весов кодовых слов из Hj совпадает с четностью j.

Определим отображение Ф : Z2m —> 2^ ' по правилу

Ф(хь... ,хп) = НХ1 х ... х НХп.

23

Для С С ПОЛОЖИМ Ф(С) = игеС Ф(х).

Линейные коды С, С С ¿Г^т называются дуальными друг другу, если С = {х \ Уу £ С : х ■ у — 0}, где (хь...,хп) ■ (уи...,уп) = жт + • • • + ХпУп- Весовым нумератором двоичного кода С С {0,1}^ называется многочлен

n

где тс,г ~ число слов кода С веса г. Известно [19], что весовые нумераторы дуальных двоичных кодов С и С' связаны тождеством Мак-Вильямс

У) = 1СГ1 + У, X - У).

Любые два кода С, С", для которых это тождество верно, называются формально дуальными.

Теорема 13 (теорема 8.10). Пусть С иС' —дуальные линейные коды. Тоща двоичные коды <р(С) и Ф(С') формально дуальны.

Пусть п — 2Г и / = (¿1,... ,и) —набор неотрицательных целых чисел, удовлетворяющий равенству 1г'1 + 2г2 + ... + кг к = г. Пусть 6Ь...,&„ € — все элементы множества {1} х (2к~1г2к)'11 х

. х (2°^2»:)*,с, упорядоченные лексикографически. Определим линейный -код

п

Н1 = {Й = (/IX, ...,/»„) е ^ I = В/Йг = 0},

дуальный ему код обозначим через Р/.

Теорема 14 (теоремы 8.14, 8.17). Код Ф(%/) является двоичным (пт,2гата/2пт,4)-кодом, т.е. расширенным 1 -совершенным кодом. Код <р(Т>1) является двоичным

-кодом, т. е. кодом Адама-

ра.

Теорема 15 (теорема 8.21). Если Н — линейный 2%к-код такой, что двоичный код Ф(Н) является расширенным 1 -совершенным кодом, то "Н эквивалентен одному из кодов "Н/, т. е. получается из него перестановкой координат и умножением некоторых координат на константы.

Список литературы

[1] Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискрет,, анализ и исслед. операций. Сер. 1. — 1995. — Т. 2, № 1. — С. 4-6. http://rni.rnathnet.ru/da450.

[2| Августинович С. В., Соловьева Ф. И. Построение совершенных двоичных кодов последовательными сдвигами ¿¡-компонент // Проблемы передачи информации.— 1997.— Т. 33, № 3.— С. 15-21. http://mi.mathnet.ru/ppi374.

[3] Бассалыго Л. А. Обобщение теоремы Ллойда на произвольный алфавит // Проблемы управления и теории информации. — 1973. — Т. 2, № 2. - С. 133-137.

[4] Бассалыго Л. А., Зиновьев В. А., Леонтьев В. К., Фельдман Н. И. Несуществование совершенных кодов для некоторых составных алфавитов // Проблемы передачи информации. — 1975-— Т. 11, № 3.— С. 3-13. http://mi.mathnet.ru/ppil590.

[5] Белоусов В. Д. n-Арные квазигруппы. — Кишинев: Штиинца, 1972.

[6] Белоусов В. Д., Санди к М. Д. тг-арные квази-группы и лупы // Сибирский математический журнал. — 1966. — Т. 7, № 1. — С. 31-54.

[7] Борисенко В. В. Неприводимые n-квазигруппы на конечных множествах составного порядка // Квазигруппы и лупы,— Кишинев: Штиинца, 1979. - Т. 51 из Мат. Исслед. - С. 38-42.

[8] Васильев Ю. Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. — М.: Физматгиз, 1962. — Т. 8. — С. 337-339.

[9] Глухое М. М. О многообразиях (г, ^-приводимых 7г-квазигрупп // Сети и квазигруппы. — Кишинев: Штиинца, 1976. — Т. 39 из Мат. Исслед.— С. 67-72.

[10] Гольдберг В. В. Об инвариантной характеристике некоторых условий замыкания в тернарных квазигруппах // Сибирский математический журнал. - 1975. - Т. 16, № 1. - С. 29-43.

[11[ Гольдберг В. В. О приводимых, групповых и (2п + 2)-эдричных (п + 1)-тканях многомерных поверхностей // Сибирский математический журнал. - 1976. - Т. 17, № 1. - С. 44-57.

Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования: Пер. с англ. Библиотека Кибернетического Сборника. — М.: Мир, 1976. - 136 с.

Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Проблемы передачи информации,— 1972.— Т. 8, № 1.— С. 26-35. http://mi.mathnet.ru/ppi772.

Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. — 1973. - Т. 2, № 2. - С. 123-132.

Зиновьев В. А., Лобстейн А. Об обобщенных каскадных конструкциях совершенных двоичных нелинейных кодов // Проблемы передачи информации. — 2000. — Т. 36, № 4. — С. 59-73. http://mi.mathnet.ru/ppi495.

Кротов Д. С., Потапов В. П. О свитчинговой эквивалентности парных квазигрупп порядка 4 и совершенных двоичных кодов // Проблемы передачи информации. — 2010. — Т. 46, № 3. — С. 22-28. http://mi.mathnet.ru/ppi2019.

Лось А. В. Построение совершенных ^-значных кодов последовательными сдвигами а-компонент // Проблемы передачи информации. — 2004. — Т. 40, № 1.-С. 40-47. http://mi.mathnet.ru/ppil22.

Лось А. В. Построение совершенных g-ичных кодов свитчингами простых компонент // Проблемы передачи информации. — 2006. — Т. 42, № 1,— С. 34-42. http://mi.mathnet.ru/ppi35.

Мак-Вильяме Ф. Дж., Слоэн Н. Док. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М.: Связь, 1979. — 744 с.

Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. — 1999. — Т. 6, № 4. — С. 4448. http://mi.mathnet.ru/da327.

Нечаев А. А. Функции «след» в кольце Галуа и помехоустойчивые коды // Тезисы сообщений V Всесоюзн. симп. по теории колец, алгебр и модулей. — Новосибирск, Россия: 1982.— С. 97.

Нечаев А. А. Код кердока в циклической форме // Дискретная математика. — 1989. - Т. 1, № 4. - С. 123-139. http://mi.mathnet.ru/dm948.

Нечаев А. А., Хонольд Т. Полновесные модули и представления кодов // Проблемы передачи информации. — 1999. — Т. 35, Ш 3. — С. 18-39. http://mi.mathnet.ru/ppi450.

Потапов В. Н. О дополняемости частичных n-квазигрупп порядка 4 // Математические труды. — 2010. — Подано в печать.

Потапов В. Н., Кротов Д. С. Асимптотика числа тг-квазигрупп порядка 4 // Сибирский математический журнал. — 2006. — Т. 47, № 4. — С. 873887. http://mi.mathnet.ru/smj902.

Потапов В. Н., Кротов Д. С. О числе n-арных квазигрупп конечного порядка // Дискретная математика.— 2010.— Принято в печать.

Романов А. М. О разбиениях g-ичных кодов хемминга на непересекающиеся компоненты // Дискрет, анализ и исслед. операций. Сер. 1,— 2004. - Т. 11, № 3.- С. 80-87. http://mi.mathnet.ru/dall4.

Фреикин Б. Р. О приводимости и сводимости в некоторых классах п-группоидов. II.— Кишинев: Штиинца, 1972,— Т. 7:1(23) из Мат. Исслед.-С. 150-162.

Черемушкин А. В. Каноническая декомпозиция n-арных квазигрупп // Исследование операций и квазигрупп. — Кишинев: Штиинца, 1988. — Т. 102 из Мат. Исслед. — С. 97-105.

Akivis М. A., Goldberg V. V. Solution of Belousov's problem // Discuss. Math., Gen. Algebra Appl. - 2001. — Vol. 21, no. 1. - Pp. 93-103.

Avgustinovich S. V., Heden O., Solov'eva F. I. The classification of some perfect codes // Des. Codes Cryptography.— 2004.— Vol. 31, no. 3.— Pp. 313-318. - DOI: 10.1023/B:DESI.0000015891.01562.cl.

Best M. R. Perfect codes hardly exist // IEEE Trans. Inf. Theory. - 1983. — Vol. 29, no. 3.— Pp. 349-351.- DOI: 10.1109/TIT.1983.1056677.

Borges J., Phelps К. Т., Rifa, J. The rank and kernel of extended 1-perfect Za-linear and additive non-/^-linear codes // IEEE Trans. Inf. Theory.— 2003. — Vol. 49, no. 8. — Pp. 2028-2034. — DOI: 10.1109/TIT.2003.814490.

Borges J., Rifa J. A characterization of 1-perfect additive codes // IEEE Trans. Inf. Theory.- 1999.- Vol. 45, no. 8.- Pp. 1688-1697.- DOI: 10.1109/18.771247.

Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs.— Berlin: Springer-Verlag, 1989.

Carlet C. Boolean Functions for Cryptography and Error-Correcting Codes // Boolean Models and Methods in Mathematics, Computer Science,

and Engineering / Ed. by Y. Crama, L. Hammer. — Cambridge Univ. Press, 2010. - Vol. 134 of Encycl. Math. Appl. - Pp. 257-397.

[37] Chihara L. On the zeros of the askey-wilson polynomials, with applications to coding theory // SI AM J. Math. Anal. - 1987. - Vol. 18, no. 1. - Pp. 191207. — DOI: 10.1137/0518015.

Colbourn C. J., Rosa A. Triple Systems. — Oxford: Clarendon Press, 1999.

Delsarte P., Goethals J. M. Unrestricted codes with the Golay parameters are unique // Discrete Math.— 1975.— Vol. 12, no. 3.— Pp. 211-224,— DOI: 10.1016/0012-365X(75)90047-3.

Dillon J. F. APN polynomials: An update.— Fq9, International Conference on Finite Fields and their Applications. — 2009. — http://mathsci.ucd.ie/~gmg/Fq9Talks/Dillon.pdf.

Dornte W. Untersuchungen über einen verallgemeinerten Gruppenbegrieff // Mathematische Zeitschrift. — 1928. — Vol. 29. — Pp. 1-19.

Etzion T. Nonequivalent q- ary perfect codes // SI AM J. Discrete Math.— 1996.- Vol. 9, no. 3.- Pp. 413-423.

Etzion T., Schwartz M. Perfect constant-weight codes // IEEE Trans. Inf. Theory.- 2004,- Vol. 50, no. 9.- Pp. 2156-2165.- DOI: 10.1109/TIT.2004.833355.

Finizio N. J., Lewis J. T. Enumeration of maximal codes // Congr. Numer. - 1994. - Vol. 102. - Pp. 139-145.

Ganter B. Finite partial quadruple systems can be finitely embedded // Discrete Math. — 1974. — Vol. 10, no. 2. — Pp. 397-400. — DOI: 10.1016/0012-365X(74)90130-7.

Godsil C. D. Algebraic Combinatorics.— New York: Chapman and Hall, 1993.

Golay M. J. E. Notes on digital coding // Proc. IRE.- 1949.- Vol. 37, no. 6. — P. 657. — DOI: 10.1109/JRPROC. 1949.233620.

Golomb S. W., Posner E. C. Rook domains, latin squares, and error-distributing codes 11 IEEE Trans. Inf. Theory. — 1964.— Vol. 10, no. 3.— Pp. 196-208. — DOI: 10.1109/TIT. 1964.1053680.

Hamming R. W. Error detecting and error correcting codes // Bell Syst. Tech. J. - 1950. - Vol. 29, no. 2. - Pp. 147-160.

[50] Hammons A. R., Jr, Kumar P. V., Calderbank A. It., Sloane N. J. A., Sole P. The Z4-linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inf. Theory. - 1994,- Vol. 40, no. 2,- Pp. 301319. — DOI: 10.1109/18.312154.

[51] Heden O. A Study of Mixed Perfect Codes: Thesis / University of Stockholm. — Stockholm,, 1977.

[52] Heden O., Krotov D. S. On the structure of non-full-rank perfect q-ary codes // Adv. Math. Commun.— 2010.— Accepted. Eprint version: http://arXiv.org/abs/1001.0001.

[53] Krotov D. S. Inductive constructions of perfect ternary constant-weight codes with distance 3 // Probl. Inf. Transm. - 2001. — Vol. 37, no. 1. - Pp. 1-9. -DOI: 10.1023/A: 1010424208992.

[54] Krotov D. S. On the binary codes with parameters of doubly-shortened 1-perfect codes // Des. Codes Cryptography.— 2010.— Vol. 57, no. 2,— Pp. 181-194,— DOI: 10.1007/sl0623-009-9360-5.

[55] Krotov D. S., Potapov V. N. On the reconstruction of rc-quasigroups of order 4 and the upper bounds on their number // Proc. the Conference Devoted to the 90th Anniversary of Alexei A. Lyapunov. — Novosibirsk, Russia: 2001. — October. — Pp. 323-327.- http://www.sbras.ru/ws/Lyap2001/2363.

[56] Krotov D. S., Potapov V. N., Sokolova P. V. On reconstructing reducible nary quasigroups and switching subquasigroups // Quasigroups Relat. Syst. — 2008. - Vol. 16, no. 1. - Pp. 55-67.

[57] Laywine C. F., Mullen G. L. Discrete Mathematics Using Latin Squares. — Wiley, New York, 1998.

[58] Lenstra Jr H. W. Two theorems on perfect codes // Discrete Math. — 1972. — Vol. 3, no. 1-3.- Pp. 125-132. — DOI: 10.1016/0012-365X(72)90028-3.

[59] Lindner G. C. A survey of embedding theorems for Steiner sysrems // Topics on Steiner Systems / Ed. by C. C. Lindner, A. Rosa.— North-Holland, 1980. - Vol. 7 of Ann. Discrete Math. - Pp. 175-202.

[60] Lindstrom B. On group and nongroup perfect codes in q symbols // Math. Scand.— 1969.- Vol. 25.- Pp. 149-158.— http://www.mscand.dk/article.php?id=1942.

[61] Martin W. J., Zhu X. J. Anticodes for the grassman and bilinear forms graphs 11 Des. Codes Cryptography. — 1995. —Vol. 6, no. 1.— Pp. 73-79.— DOI: 10.1007/BF01390772.

[62] McKay B. D., Wanless I. M. Combinatorial data. Latin cubes and hypercubes. — http://cs.anu.edu.au/~bdm/data/latincubes.html.

[63] McKay B. D., Wanless I. M. A census of small Latin hypercubes // SI AM J. Discrete Math. — 2008. — Vol. 22, no. 2. - Pp. 719-736. — DOI: 10.1137/070693874.

[64] Osterg&rd P. R. J.t Pottonen O. Two optimal one-error-correcting codes of length 13 that are not doubly shortened perfect codes // Des. Codes Cryptography. — 2010. — To appair.

[65] Phelps K. T. A general product construction for error correcting codes // SI AM J. Algebraic Discrete Methods. - 1984. - Vol. 5, no. 2. - Pp. 224228.— DOI: 10.1137/0605023.

[66] Phelps K. T. A product construction for perfect codes over arbitrary alphabets // IEEE Trans. Inf. Theory. - 1984. - Vol. 30, no. 5. - Pp. 769771. — DOI: 10.1109/TIT. 1984.1056963.

[67] Phelps K. T., Rifà J. On binary 1-perfect additive codes: Some structural properties // IEEE Trans. Inf. Theory. — 2002. — Vol. 48, no. 9. — Pp. 25872592,— DOI: 10.1109/TIT.2002.801474.

[68] Potapov V. N. On completion of latin hypercuboids of order 4 // Proc. Twelfth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT 2010. — Novosibirsk, Russia: 2010. — September. — Pp. 251-255.

[69] Roos C.: Preprint: Delft, the Netherlands, 1979.

[70] Schônheim J. On linear and nonlinear single-error-correcting ç-ary perfect codes // Inform. Contr.- 1968.- Vol. 12, no. 1.- Pp. 23-26.- DOI: 10.1016/S0019-9958(68)90167-8.

[71] Shcherbacov V. A. Quasigroups in cryptology: E-print 1007.3572: arXiv.org, 2010.— Available at http://arxiv.org/abs/1007.3572.

[72] Svanstrôm M. A class of perfect ternary constant-weight codes // Des. Codes Cryptography.- 1999.- Vol. 18, no. 1-3.- Pp. 223-230.- DOI: 10.1023/A: 1008361925021.

[73] Svanstrôm M. Ternary Codes with Weight Constraints: Dissertation 572 / Linkôping University. — 1999.

[74] Tarry G. Le problème des 36 officers // Comptes Rendu de l'Association Française pour l'Avancement de Science Naturel (National Academy of Sciences). — 1900, 1901.-Vol. 1, 2.-Pp. 122-123, 170-203.

[75] Tietavainen A. On the nonexistence of perfect codes over finite fields // SI AM J. Appl. Math. - 1973. - Vol. 24. - Pp. 88-96.

[76] Treash C. The completion of finite incomplete Steiner triple systems with applications to loop theory // J. Comb. Theory, Ser. A. — 1971.— Vol. 10, no. 3. — Pp. 259-265. — DOI: 10.1016/0097-3165(71)90030-6.

[77] van Lint J., Tolhuizen L. On perfect ternary constant-weight codes // Des. Codes Cryptography.- 1999.— Vol. 18, no. 1-3.- Pp. 231-234.- DOI: 10.1023/A: 1008314009092.

Публикации автора по теме диссертации

[I] Кротов Д. С. Нижние оценки числа m-квазигрупп порядка 4 и числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1,— 2000,— Т. 7, № 2,— С. 47-53. http://mi.mathnet.ru/da261.

[II] Кротов Д. С. Z4-линейные совершенные коды // Дискрет, анализ и исслед. операций. Сер. 1. — 2000. — Т. 7, № 4. — С. 78-90. http://mi.mathnet.ru/da281.

[III] Krotov D. S. Z2k-Dual binary codes // IEEE Trans. Inf. Theory.- 2007.- Vol. 53, no. 4,- Pp. 1532-1537.- DOI: 10.1109/TIT.2007.892787.

[IV] Avyustinovich S. V., Krotov D. S. Embedding in a perfect code // J. Comb. Des.- 2009.- Vol. 17, no. 5.- Pp. 419-423,- DOI: 10.1002/jcd.20207.

[V] Krotov D. S., Avyustinovich S. V. On the number of 1-perfect binary codes: A lower bound // IEEE Trans. Inf. Theory. - 2008. - Vol. 54, no. 4.- Pp. 1760-1765. — DOI: 10.1109/TIT.2008.917692.

[VI] Krotov D. S. On diameter perfect constant-weight ternary codes 11 Discrete Math. - 2008.- Vol. 308, no. 14.- Pp. 3104-3114.- DOI: 10.1016/j.disc.2007.08.037.

[VIII] Krotov D. S. On irreducible n-ary quasigroups with reducible retracts // Eur. J. Comb. - 2008. - Vol. 29, no. 2. - Pp. 507-513. -DOI: 10.1016/j.ejc.2007.01.005.

[VII] Krotov D. S. On decomposability of 4-ary distance 2 MDS

codes, double-codes, and n-quasigroups of order 4 // Discrete

Math.- 2008.- Vol. 308, no. 15.- Pp. 3322-3334.- DOI: 10.1016/j.disc.2007.06.038.

[IX] Krotov D. S. On reducibility of n-ary quasigroups // Discrete Math.- 2008.- Vol. 308, no. 22.- Pp. 5289-5297.- DOI: 10.1016/j.disc.2007.08.099.

[X] Krotov D. S., Potapov V. N. n-Ary quasigroups of order 4 // SIAM J. Discrete Math. - 2009. - Vol. 23, no. 2. - Pp. 561-570. - DOI: 10.1137/070697331.

[XI] Krotov D. S., Potapov V. N. On connection between reducibility of an n-ary quasigroup and that of its retracts // Discrete Math. — 2011. — Vol. 311, no. 1, — Pp. 58-66.- DOI: 10.1016/j.disc.2010.09.023

[XII] Кротов Д. С. О связи свитчинговой разделимости графа и его подграфов // Дискрет, анализ и исслед. операций. — 2010. — Т. 17, № 2. — С. 46-56. http://mi.mathnet.ru/da605.

Труды конференций и тезисы

[XIII] Krotov D. S. Zi-linear Hadamard and extended perfect codes // WCC2001, International Workshop on Coding and Cryptography. — Elsevier B.V., 2001.— Vol. 6 of Electron. Notes Discrete Math.— Pp. 107-112. —DOI: 10.1016/S1571-0653(04)00161-1.

[XIV] Krotov D. S. On decomposition of (n,4n~1,2)4 MDS codes and double-codes // Proc. Eighth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT-VIII. — Tsarskoe Selo, Russia: 2002.-September. - Pp. 168-171.

[XV] Krotov D. S. On decomposability of distance 2 MDS codes // Proc. Ninth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT'2004. - Kranevo, Bulgaria: 2004. - June. - Pp. 247-253.

32

[XVI| Krotov D. S. Z^k-duality, -linear Hadamard codes, and со-¿^it-linear extended perfect codes // Proc. Fourth Int. Workshop on Optimal Codes and Related Topics. — Pamporovo, Bulgaria: 2005. — June. - Pp. 205-213.

[XVII] Krotov D. S. On irreducible n-quasigroups with reducible (n -l)-ary retracts // Proc. Tenth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT-10. — Zvenigorod, Russia: 2006. - September. - Pp. 157-160.

[XVIII] Krotov D., Avgustinovich S. On the number of 1-perfect binary codes: a lower bound // Proc. Tenth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT-10. — Zvenigorod, Russia: 2006.-September. - Pp. 161-164.

[XIX] Avgustinovich S. V., Krotov D. S. Embedding in a perfect code // Coding Theory Days in St.Petersburg. — St.Petersburg: 2008. — September. - Pp. 37-39.

[XX] Krotov D. S., Avgustinovich S. V. On the number of perfect binary codes. A lower bound // Proc. the conference "Discrete Analysis and Operations Research" DAOR'2004. — Novosibirsk, Russia: 2004. - June-July. - P. 95.-http://www.math.nsc.ru/conference/DAOir04/daor04.pdf.

[XXI] Кротов Д. С., Потапов В. Н. Описание n-арных квазигрупп порядка 4 // «Математика в современном мире». Российская конференция, посвященная 50-летаю Института математики им. С. JI. Соболева СО РАН. Тезисы докладов. — Новосибирск: 2007. — Сент.— С. 36.— http://math.nsc.ru/conference/conf50/Abstracts.pdf.

[XXII] Кротов Д. С., Потапов В. Н. О приводимости n-арных квазигрупп и свитчинговой разделимости графов //IX Международный семинар «Дискретная математика и ее приложения», посвященный 75-летию со дня рождения академика О. Б. Лупанова. Тезисы докладов. — Москва: 2007. — Июнь. — С. 432-434,. .

Кротов Денис Станиславович

Совершенные коды и п-арные квазигруппы: конструкции и классификация

Автореферат диссертации на соискание ученой степени доктора физико-математических; наук

Подписано в печать 28.12.2010. Формат 60x84 1/16. Усл. печ. л. 2,0. Уч.-изд. л. 2,0. Тираж 100 экз. Заказ № 169

Отпечатано в ООО "Омега Принт" пр. Лаврентьева, 6, Новосибирск 630090

Введение

Содержание работы.

I Квазигруппы

Основные определения.

Обозначения.

1 О разложимости двукратных МДР-кодов и разделимости п-арных квазигрупп порядка

1.1 Введение.

1.2 Определения и обозначения.

1.3 Вспомогательные результаты.

1.4 Разложение 2-МДР-кодов.

1.5 Разложимость (п, 2)4 МДР-кодов.

1.6 Разделимость п-арных квазигрупп порядка 4.

3.2 Основные определения.107

3.3 Основной результат .109

3.4 Доказательство леммы 3.5.111

3.5 Сублинейные п-квазигруппы.116

4 О свитчинговой разделимости графов 118

4.1 Введение.118

4.2 Доказательство теоремы 4.2.119

4.2.1 Случай к > 3.119

4.2.2 Случай к = 3.122

4.3 Доказательство теоремы 4.3.124

4.4 Графы, булевы функции, квазигруппы .126

4.4.1 Расширенные булевы функции.126

4.4.2 n-Арные квазигруппы.129

II Совершенные коды 133

5 Вложение в совершенный код 134

6 О числе 1-совершенных двоичных кодов: нижняя оценка 141

6.1 Введение.141

6.2 Предварительные сведения.142

6.3 ДА конструкция расширенных 1-совершенных кодов . 145

6.4 Вычисления .148

6.5 Нижняя оценка числа 1-совершенных кодов.154

7 О диаметрально совершенных равновесных троичных кодах 159

7.1 Введение.159

7.2 Пространство Хп и ребра в {0,1}п.161

7.3 Совершенные коды с расстоянием 3.162

7.3.1 Совершенные коды с расстоянием 3 и совершенные па-росочетания в {0,1}га.164

7.3.2 Конструкция совершенных кодов с расстоянием 3. . . 165

7.3.3 Группа автоморфизмов и транзитивность.167

7.3.4 Неэквивалентность.169

7.4 Диаметрально совершенные коды с расстоянием 4.172

7.5 Диаметрально совершенный коды с расстоянием 5.174

7.5.1 Связь с кодами Препарата .177

8 О Z2k-дуальных двоичных кодах 182

8.1 Введение.182

8.2 Определения и основные факты.185

8.2.1 ^2т-Линейные коды.186

8.2.2 Ко-^-линейные коды.188

8.3 ^-Дуальность двоичных кодов.190

8.4 Ко-¿^-линейные расширенные 1-совершенные коды.193

8.4.1 1-Совершенные коды.193

8.4.2 Класс 1-совершенных кодов в .195

8.4.3 Ко-^-линейные расширенные 1-совершенные двоичные коды .197

8.4.4 Замечание об общем случае Z2^m.197

8.5 ¿^-Линейные коды Адамара.198

8.6 Несуществование неизвестных ко-^к-линейных расширенных совершенных кодов и ¿^-линейных кодов Адамара . . . 199

Литература 204

Публикации автора по теме диссертации 222

Введение

В диссертации рассматриваются комбинаторные вопросы теории парных квазигрупп и 1-совершенных двоичных кодов. Доказаны признаки разделимости п-арных квазигрупп, получена характеризация класса парных квазигрупп порядка 4. Рассмотрены конструкции 1-совершенных двоичных кодов и построение из них кодов в троичном алфавите.

Актуальность темы. Объектами исследования настоящей работы являются 1-совершенные двоичные коды и п-арные квазигруппы, которые также известны как латинские гиперкубы (многомерное обобщение латинских квадратов) и эквивалентны максимально дистанционно разделимым (МДР) кодам с расстоянием 2. Оба класса объектов рассматриваются в метрическом пространстве Хэмминга Н™, носителем которого является множество {0,1,., д — 1}" слов длины п алфавита {0,1,., д — 1}, а расстояние между двумя словами есть число позиций, в которых эти слова различаются. Если д есть степень простого числа, Н™ можно снабдить структурой векторного пространства над конечным полем СР(д), мы будем этим пользоваться в случае д = 2. Пространство Хэмминга удобно также рассматривать как граф, в котором два слова соединены ребром тогда и только тогда, когда они отличаются только в одной позиции. Максимальную клику этого графа будем называть линией (линия состоит из д слов, совпадающих во всех позициях кроме одной), а вершину вместе с ее окрестностью — 1-шаром с центром в этой вершине. Множество слов в Н™ называется 1 -совершенным кодом, если каждый 1-шар содержит ровно одну кодовую вершину. Множество слов в Н™ называется МДР-кодом с расстоянием 2, если каждая линия содержит ровно одну кодовую вершину. (Напомним, что кодовым расстоянием произвольного подмножества в Н™ из двух или более вершин называется минимальное расстояние между двумя различными вершинами. Так, 1-совершенный код, если у него больше одной вершины, имеет расстояние 3.) Функция из {0,1,., q — 1}п в {0,1,., q — 1} называется п-арной квазигруппой, порядка д, если на каждой линии она принимает все q различных значений, каждое ровно по одному разу. Если значение n-арной квазигруппы трактовать как дополнительный символ, то получится МДР-код с расстоянием 2.

Определения 1-совершенных кодов и МДР кодов в приведенной выше форме имеют определенную общность, которая в частности подчеркивает, что оба класса относятся к категории «точных» комбинаторных конфигураций. Эти классы кодов можно единообразно определить иначе: если удаление некоторого независимого множества вершин графа Н™ приводит к регулярному графу степени (q — 1)п — 1 или (q — 2)п, то это множество является 1-совершенным кодом или МДР-кодом с расстоянием 2 соответственно. Такая постановка близка к вопросам, изучаемым в алгебраической теории графов. На самом деле, как 1-совершенные коды, так и МДР-коды с расстоянием 2 являются важнейшими частными случаями так называемых регулярных разбиений, в англоязычной литературе известными также как equitable partitions (термин «equitable» в данном контексте не имеет удобного перевода), а на русском языке больше известными как совершенные раскраски. Наряду с дистанционно регулярными графами и схемами отношений, совершенные раскраски (equitable partitions) являются популярными объектами алгебраической комбинаторики, см. напр. [57], [73].

Отмеченная связь постановок была упомянута, чтобы подчеркнуть общую природу изучаемых объектов, к существу вопросов, рассматриваемых в диссертации, прямого отношения она не имеет. Для нас более важна конструктивная связь: существуют способы построения 1-совершенных кодов из n-арных квазигрупп, впервые предложенные К. Т. Фелпсом [110], [111], см. также [22], [83]. Поэтому результаты, полученные для п-арных квазигрупп, важны и для теории 1-совершенных кодов, к примеру, эта связь использовалась в работах [I], [51], [83], [28], [89]. В контексте диссертации эта конструктивная связь имеет также и историческое значение: именно она привлекла мой интерес к n-арным квазигруппам, сформировавшийся в одно из основных направлений исследований.

Прежде чем перейти к рассмотрению классов 1-совершенных кодов и n-арных квазигрупп отдельно, хотелось бы отметить один общий для них вопрос, вопрос о числе объектов. Известно, что число 1-совершенных кодов в Hq растет дважды экспоненциально при росте п, если q есть степень простого числа, а п = (qm — l)/(q — 1) (это необходимое для существования 1-совершенных кодов условие на п следует из известных соображений: мощность пространства должна делиться на мощность 1-шара), то ocTi±o(;i) есть нижняя оценка на число кодов имеет вид , где с — некоторая константа. В двоичном случае такая оценка, с с = 1/2, была установлена Ю.Л.Васильевым одновременно с открытием нелинейных 1-совершенных кодов [10], на случай произвольного д, равного степени простого числа, конструкция обобщена Дж. Шонхеймом [122]. Следует отметить, что существование совершенных кодов в Н™ для q, не представимого в виде степени простого числа, является известной открытой проблемой в данной области; однако, если только существует хотя бы один такой код, известные методы позволяют построить коды для бесконечного числа значений п с тем же q [111], причем число таких кодов будет расти дважды экспоненциально по п. Известная верхняя оценка числа 1-совершенных кодов с точки зрения асимптотики двойного логарифма не отличается от числа всевозможных подмножеств Н* (в двоичном случае 22" const'logn) см> Улучшения нижних оценок в сериях работ [3], [33], [I], [V] (глава 6 диссертации), для двоичного случая, и [67], [30], [44], [31], [83], для кодов над д-значным алфавитом, важны больше с точки зрения понимания возможного строения совершенных кодов, чем в контексте проблемы асимптотики двойного логарифма числа кодов, хотя для q > 3 нижняя граница этой асимптотики была реально поднята [31], [83] (в последней работе для этого использовалась связь с n-арными квазигруппами).

Таким образом, основной проблемой является установить константу при п в асимптотике двойного логарифма числа 1-совершенных кодов (мощность алфавита q считается фиксированной). При этом даже существование такой константы не доказано, хотя противное и кажется фантастикой.

Ситуация с n-арными квазигруппами порядка q > 3 аналогична. Дважды экспоненциальное по п число квазигрупп составного порядка следует из известной конструкции сплетения n-арных квазигрупп (термин «сплетение» в данном случае никак не соотносится со сплетением групп), а для простых порядков, начиная с 5, установлено относительно недавно [92]. Для порядка меньше 4 проблема с числом п-арных квазигрупп тривиальна, поскольку существует только одна п-арная квазигруппа, с точностью до простых преобразований эквивалентности. Верхнюю оценку числа объектов, с точки зрения асимптотики двойного логарифма, удается несколько улучшить по сравнению с числом всех функций, см. [43]. Однако в случае д > 4 асимптотики двойного логарифма нижней и верхней оценок числа п-арных квазигрупп порядка д, как и для 1-совершенных кодов, расходятся. Единственным классом объектов, для которых проблема асимптотики двойного логарифма числа решена, является класс п-арных квазигрупп порядка 4. Более того, существует и является одним из основных результатов данной диссертации характеризация этого класса и, как следствие, известна асимптотика самого числа объектов. (На самом деле, асимптотика получена В. Н. Потаповым ранее и опубликована в нашей совместной статье [42].) Проблема оценки дважды экспоненциального числа комбинаторных объектов известна и в других разделах дискретной математики. Одним из примеров является класс бент-функций, которые определяются как булевы функции {0,1}п —> {0,1}, на которых определенным образом заданная мера нелинейности достигает теоретической верхней границы. Бент-функции существуют при всех четных п, а нижняя и верхняя оценки их числа, как и для числа 1-совершенных двоичных кодов, имеют вид 2^ и 2А соответственно [60]. Таким образом, проблема оценок подобного рода достаточно широка, и осмысление способов ее решения — это дело будущего. Хочется подчеркнуть, что величины столь большого роста находятся за рамками интуитивного восприятия (по крайней мере автора диссертаи ции), поэтому бывает трудно вообразить природу тех факторов, которые могли бы оказать существенное влияние на верхнюю и, кроме известных конструктивных подходов, нижнюю оценки. Трудность восприятия таких чисел приводит порой к тому, что для некоторых исследователей получение дважды экспоненциальной нижней оценки закрывает вопрос о числе объектов — это число по своей величине в каком-то смысле сравнимо с числом всех подмножеств пространства. На самом же деле нижняя оценка по сравнению с верхней остается почти ничем даже после логарифмирования. п-Арные квазигруппы. Сам термин алгебраический и, строго говоря, обозначает пару (2,/), где I] — некоторое множество, а / — п-арная операция такая, что в уравнении х0 = /(а^,., хп) значения любых п переменных из а?о, жь хп всегда однозначно задают значение оставшейся переменной. Как видно из названия, понятие п-арной, или многоместной (в англоязычной терминологии используются термины «ро1уас1ю» или «тиН;агу»), квазигруппы является обобщением понятия группы. Действительно, в случае п = 2 добавление аксиомы ассоциативности приводит к определению группы. Некоторое стандартное упрощение терминологии, которым мы будем в дальнейшем пользоваться, — называть п-арной квазигруппой саму операцию, как правило это не приводит к разночтениям. В случае конечного носителя £ такие отображения также известны в комбинаторике как латинские гиперкубы порядка q— |Е| и часто, по аналогии с латинским квадратом (случай п — 2), интуитивно ассоциируются с п-мерной таблицей, д х д х . х д, заполненной символами алфавита £ правильным образом — так, что в каждом ряду (линии) каждого из п базовых направлений все символы встречаются в точности по одному разу. Однако в некоторых случаях оказывается гораздо удобней работать с графиком {(хо, XI,., хп) ' ^о = /(^ь • ■ •, жга)} п-аРной квазигруппы, а не с самой операцией. В теории кодирования такие множества известны как МДР-коды с расстоянием 2. При рассмотрении графика п-арной квазигруппы вместо самой операции оказывается, что зависимая переменная наделена теми же «правами», что и все остальные, что делает многие формулировки более естественными, а доказательства более короткими. Однако в некоторых вопросах, например, при рассмотрении суперпозиции двух или более квазигрупп, функциональная форма все же оказывается необходимой, поэтому порой приходится использовать одновременно обе терминологии.

Фундаментальные результаты в алгебраической теории п-арных квазигрупп, которыми во многом определяется развитие этой теории начиная с 60-х годов прошлого века, принадлежат В. Д. Белоусову (см. напр. [8], [7]), начинавшему свою деятельность в этой области под руководством А. Г. Куроша. Отдельные классы многоместных операций со свойством однозначной обратимости изучались значительно раньше. Одной из первых работ является работа В.Дёрнте [66], положившая начало изучению угарных групп (ассоциативных п-арных квазигрупп).

В последнее время возрастает интерес к п-арным квазигруппам как к комбинаторному объекту, что отчасти стимулируется возможными приложениями к теории кодирования и криптографии (см. напр. [123]), отчасти просто тем, что п-арные квазигруппы (латинские гиперкубы) являются очень естественным обобщением латинских квадратов — классических математических объектов, известных многим со школьной скамьи. В частности, появилось несколько работ с результатами по классификации латинских гиперкубов с малыми параметрами [104], [85], [18], [84], [124], [100], [103]. В последней работе известных австралийских математиков Б.Мак-Кэя и Я.Уонлеса [103] получено число латинских п кубов порядка 4 до п = 5, порядка 5 до п = 4 и порядка б до п — 3, причем сосчитано также число классов эквивалентности для различных естественно определенных эквивалентностей, представители классов доступны на веб-ресурсе [102]. Продвинуться в бблыние размерности при помощи переборных алгоритмов не представляется возможным па любых компьютерах, доступных в ближайшем будущем (напомним, что число объектов растет дважды экспоненциально). Число n-арных квазигрупп порядка 3 не было упомянуто не случайно. Существует только одна такая квазигруппа, с точностью до изотопии (перестановки элементов носителя независимо в каждом аргументе), а всего — 3 • 2п. Это факт достаточно простой и, хотя самая ранняя из известных ссылок [70] (см. также [94, Corollary 13.25], [80], [124], [136]) относится к последней декаде прошлого века, был известен намного раньше. Таким образом, порядок 4 — первый нетривиальный порядок с точки зрения п-арных квазигрупп. Именно этому порядку уделяется наибольшее внимание в диссертации и, хотя некоторые утверждения интересны в более общем контексте и применимы также и для других, не обязательно конечных, порядков, изначальной мотивацией и основным применением результатов исследований, описанных в первой части диссертации, в настоящий момент является классификация n-арных квазигрупп порядка 4.

В первой моей работе [I] 2000 года по n-арным квазигруппам порядка 4 нижняя оценка числа таких объектов устанавливается подсчетом числа изотопов /?,-арных квазигрупп, полученных сплетением квазигрупп порядка 2 (позже такие квазигруппы порядка 4 были названы полулинейными). После этого В.Н.Потапов сформулировал гипотезу, согласно которой любая п-арная квазигруппа порядка 4 полулинейна или разделима, то есть представима в виде бесповторной суперпозиции квазигрупп меньшей арности. В частности, из этого следовало бы, что класс полулинейных угарных квазигрупп асимптотически самый мощный, и нижняя оценка в [I] асимптотически точна. Несмотря на простоту формулировки и некоторые интуитивные соображения, на которых строилась гипотеза, найти короткое доказательство, по состоянию на текущий момент, не удалось. Полный текст имеющегося доказательства состоит из четырех статей [VII], [42], [IX], [X], каждая из которых представляет самостоятельное исследование, со своими подходами и терминологией и результатами, актуальность которых не ограничивается контекстом тг-арных квазигрупп порядка 4. (Две статьи принадлежат автору диссертации, две написаны в соавторстве в В.Н.Потаповым. В диссертацию не вошла только работа [42], поскольку основная лемма, как и главный результат статьи — асимптотика числа ?г-арных квазигрупп порядка 4, — принадлежат В.Н.Потапову.) Промежуточным этапом исследования, который позволил поближе ознакомиться с предметом и разработать инструментарий, являлось получение верхних оценок числа квазигрупп порядка 4 [91], [42].

Возможно, утверждение о строении п-арных квазигрупп порядка 4 не прошло достаточную проверку временем и вниманием математической общественности, чтобы говорить о вероятности того, что более короткое решение не будет найдено в ближайшее время. Однако разработанная для текущего доказательства теория обладает достаточной степенью общности, чтобы быть интересной вне контекста n-арных квазигрупп порядка 4. Кроме того, обнаруживаются некоторые связи, которые косвенно указывают на то, что все действительно не так просто, как может показаться из формулировок теорем. Мне бы хотелось упомянуть эти связи, не столько как какое-то обоснование, сколько просто потому, что они кажутся интересными. Недавно В.Н.Потапов анонсировал следующее утверждение [118]: (*) любая частичная п-арная квазигруппа порядка 4, значения которой заданы на {0,1,2,3}n1 х {0,1}; может быть дополнена до n-арной квазигруппы {0,1,2,3}п —> {0,1, 2,3}. Этот факт имеет следующую эквивалентную формулировку: пусть множество вершин графа Щ разбито на два подмножества, порождающие регулярные подграфы степени п, тогда эти подграфы являются или не являются двудольными одновременно. Оказывается [89], подобным образом (в терминах одновременной двудольности элементов регулярного разбиения множества вершин графа Хэмминга) можно переформулировать и следующую проблему: (**) каждый ли максимальный по мощности двоичный код длины 2Ш — 3 с расстоянием 3 можно получить двукратным укорочением некоторого 1 -совершенного кода длины 2Ш — 1 ? Более того, как отмечено в [89], для некоторого подкласса кодов положительный ответ на вопрос (**) эквивалентен утверждению (*). В то же время в общем случае ответ на вопрос (**) отрицательный [107], контрпример был найден с использованием компьютера. Это говорит о том, что не существует общих аргументов, доказывающих (*), которые могли бы быть обобщены на (**), и для доказательства (*) нужен подход, использующий специфику именно этой задачи. И действительно, имеющееся доказательство [41] использует характеризацию n-арпых квазигрупп порядка 4 и даже при этом достаточно трудоемко.

Вернемся к общим вопросам, касающимся п-арных квазигрупп. Важнейшую роль в их исследовании, • как комбинаторных объектов, играет понятие разделимости. Разного вида редуцируемость больших объектов к меньшим рассматривается для многих классов математических объектов, в частности, бесповторная суперпозиция исследуется как для дискретных (см. напр. [29]), так и для непрерывных объектов (см. напр. работу [23], связанную с решением тринадцатой проблемы Гилберта). Для класса многоместных квазигрупп, который замкнут относительно бесповторной суперпозиции, естественный вопрос представимости в виде такой суперпозиции возник на самом раннем этапе их исследования, как и вопрос существования неразделимых (не представимых в виде бесповторной суперпозиции) п-арных квазигрупп. Этот вопрос известен как одна из проблем В. Д. Белоусова (проблема номер 5 из монографии [7]) и решен для различных порядков в работах В. Д. Белоусова и М.Д. Сандика [8], Б. Р. Френкина [47], В. В. Борисенко [9], М. М. Глухова [12], М. А. Акивиса и В.В.Гольдберга [13], [14], [50], Кротова, В.В.Потапова и П.В.Соколовой [92]. Единственным известным в настоящее время способом строить неразделимые п-арные квазигруппы конечных порядков больше 3 является метод свитчинга, состоящий в локальной замене значений квазигруппы на некотором подмножестве области определения. (Следует заметить, что в алгебраической теории п-арных квазигрупп больше известно понятие приводимости, то есть представимости в виде бесповторной суперпозиции с тем же порядком переменных, что и в самой квазигруппе, см. напр. [7]. Это связано с тем, что порядок переменных существенен для выполнимости дополнительных алгебраических аксиом.) Крайне важным для понимания структуры разделимых п-арных квазигрупп фактом является существование и в определенном смысле единственность канонического разложения в древовидную бесповторную суперпозицию неразделимых квазигрупп и групп, установленные А. В. Черемушкиным [48]. Интересно, что аналогичное утверждение верно для существенно более широкого класса функций, сильно зависимых от каждой переменной [125].

Разделимости квазигрупп посвящены три из четырех глав первой части диссертации. Первоначально исследования ориентировались на описание п-арных квазигрупп порядка 4, которое можно считать главным результатом первой части диссертации. Однако результат главы 2 в представленном виде — завершенное утверждение, применимое к п-арным квазигруппам произвольного порядка (результаты, дополняющие теорию именно для произвольного порядка, получены в последней совместной работе [XI]) и полезное для исследования классов многоместных квазигрупп, замкнутых относительно взятия ретракта (ретракт многоместной квазигруппы получается при фиксации константами значений одного или более аргументов). Примеры использования полученного в главе 2 признака разделимости для характеризации классов п-арных квазигрупп приведены в главе 3. Интересно было бы, аналогично [125], обобщить результаты главы 2 на более широкий класс функций, сильно зависимых от каждой переменной.

Совершенные коды. Согласно широко известной теореме В.А.Зиновьева, В.К.Леонтьева и Э.Титвайнена [20], [21], [132], при q равном степени простого числа нетривиальные (т.е. 0 < г < п/2) г-совершенные коды существуют только в следующих случаях: пт — \ \ Ип1

- 1-совершенные коды в Щ " с параметрами кода Хэммин-га, который является единственным с точностью до эквивалентности линейным кодом из этого класса. (Р. У. Хэмминг рассматривал только двоичные коды [78]; общая конструкция, как и коды Голея, предложена М. Дж. Е. Голеем в полустраничной заметке [74].) Однако при непростых д существуют групповые (то есть замкнутые относительно сложения, но не обязательно относительно умножения на скаляр) 1-совершенные коды, неэквивалентные коду Хэмминга [97]. Число же негрупповых 1-совершенных кодов оценивается снизу дважды экспоненциальным относительно размерности пространства числом, см. последние нижние оценки в [V], [83].

- Коды Голея: построенные М. Дж. Е. Голеем [74] 3-совершенный код в Я|3 и 2-совершенный код в Я31. Каждый из этих кодов является единственным с точностью до эквивалентности [64].

Вопрос существования д-значных совершенных кодов в случае, когда д не есть степень простого числа, является известной открытой проблемой в общей теории совершенных кодов. Известно, что не существует ¿-совершенных кодов при Ь 0 {1,2,6,8} [54] и при I > 1 в случае д = 2аЗ/3 [6]; известно, что не существует групповых совершенных кодов [95]; известно, ЧТО не существует 1-СОВершеННОГО кода в #6 [75] (последнее следует из несуществования двух ортогональных латинских квадратов размера 6x6 [131]) — наименьших параметрах, удовлетворяющих необходимым условиям: п — 1 = 0 тос! д (следствие из теоремы Ллойда для произвольного алфавита [95], [5], [15]) и ^п"1)/^1 = 0 тос! (п(д-1) + 1) ([81], [121], следствие равномерной распределенности вершин 1-совершенного кода по подкубам размерности (п — 1)/д + 1 ).

Существование совершенных кодов исследуется и в отличных от хэмминговых метрических пространствах и графах. Ввиду применимости мощного аппарата алгебраической теории графов, особый интерес с этой точки зрения уделяется дистанционно-регулярным графам. Так, известная гипотеза Дельсарта [15] о несуществовании нетривиальных совершенных кодов в графах Джонсона на данный момент не решена (см. последнюю V работу [68] на эту тему и библиографию в ней), в то время как аналогичный факт для графов Грассмана и графов билинейных форм доказан относительно давно Л. Чихарой [62] (другое доказательство представлено У. Дж. Мартином и З.Дж. Жу [101]). Среди многообразия работ по совершенным кодам в разных экзотических метрических пространствах отметим работу [87].

В главе 7 рассматриваются совершенные коды с расстоянием 3 в пространстве троичных п-слов веса п — 1 (то есть содержащих ровно один нуль). Такие коды были построены в работах М. Сванстрёма [130], [129], Дж. Ван Линта и Л. Толхьюзена [135] на основе смежных классов по двоичному коду Хэмминга. В моей работе [88], уже используя технику из теории нелинейных совершенных кодов, построено дважды экспоненциальное число совершенных троичных равновесных кодов. В главе 7 показано, что на основе смежных классов по коду Хэмминга можно строить как неэквивалентные совершенные коды, так и коды с новыми параметрами — оптимальные коды с расстоянием 5, — в пространстве троичных п-слов веса п — 1. Заметим, что хотя рассматриваемое пространство, в отличие от случая равновесных двоичных кодов, не обладает свойством дистанционной регулярности, равновесные д-значные коды являются достаточно популярными объектами в теории кодирования.

Как уже было отмечено, над конечными полями непростой мощности возможно существование неэквивалентных 1-совершенных кодов, замкнутых относительно покоординатного сложения. В двоичном случае такой код единственный — код Хэмминга. Однако при помощи отображения Грея 0 —^ 00, 1 —» 01, 2 —» 11, 3 —>■ 10, при покоординатном действии являющимся изометрией между тг/2-мерным четверичным пространством с метрикой Ли и тг-мерным двоичным пространством Хэмминга, некоторые нелинейные коды представимы в виде образов линейных кодов над кольцом Zгí [93] (такие коды принято считать линейными, в смысле [93]) или над смешанным алфавитом. Возможность представлять хорошие нелинейные двоичные коды как линейные над недвоичными алгебраическими структурами была впервые обнаружена А. А. Нечаевым в работах [35], [36]. В статье А. Р. Хэммонса и др. [93] для подобного представления использованы изометрические свойства отображения Грея. Идея использования масштабных изометрий для построения кодов была развита в работе А.А.Нечаева и Т.Хонольда [37]. 1-Совершенные и расширенные 1-совершенные двоичные коды, представимые при помощи кода Грея как линейные коды над ^ или смешанным алфавитом, изучались в работе [II] и в работах Дж. Боргеса, К. Т. Фелпса и Дж. Рифы [56], [114], [55]; оказалось, что число таких неэквивалентных кодов растет примерно как логарифм от длины, и значения параметров, характеризующих «близость» к линейному коду (ранг — размерность линейной оболочки; размерность ядра — множества периодов), для них различные. Более широкое обобщение линейных кодов — транзитивные коды, то есть такие, что стабилизатор кода в группе изометрий пространства действует транзитивно на элементах кода. Классы транзитивных совершенных двоичных кодов строились Ф.И.Соловьевой [45] и В.Н.Потаповым [39], причем в последней работе установлено, что число неэквивалентных кодов растет экспоненциально с ростом длины. В диссертации (глава 8) предложен способ построения расширенных 1-совершенных кодов из линейных кодов над кольцом Использованное обобщение отображения Грея неоднозначно при к > 2, что позволяет сохранить плотность упаковки. Интересно, что в отличие от случая к = 2, в общем случае транзитивность полученных кодов не очевидна, и исследования по этому вопросу еще не проводились.

Цель работы: построение новых классов п-арных квазигрупп и кодов — 1-совершенных двоичных кодов, а также бесконечного класса оптимальных троичных равновесных кодов с новыми параметрами; характеризация классов тг-арных квазигрупп малого порядка и линейных аналогов расширенных 1-совершенных кодов над кольцами ; обнаружение новых зависимостей внутри исследуемых классов объектов.

Методы исследования. В исследованиях используются традиционные методы и аппарат алгебраической и комбинаторной теории кодирования, теории графов, комбинаторного анализа, метод свитчинга, суть которого состоит в локальном изменении объекта с сохранением его основных параметров, а также разработанные автором методы, в частности анализа разделимости п-арных квазигрупп.

Научная новизна. Основные результаты диссертации являются новыми и состоят в следующем:

1) Доказаны признаки разделимости п-арных квазигрупп: для порядка 4 в терминах связности прообраза двух значений и для произвольного порядка в терминах максимальной арности неразделимого ретракта.

2) Получена характеризация п-арных квазигрупп порядка 4: любая п-арная квазигруппа порядка 4 является полулинейной или разделимой. Показано, что все п-арные квазигруппы порядков 5 и 7, бинарные ретракты которых изотопны циклической группе, являются разделимыми при п > 4.

3) Введено понятие свитчинговой разделимости графов, которая эквивалентна разделимости п-арных квазигрупп, построенных по этим графам определенным образом. Показано, что если при удалении любой вершины или любых двух вершин графа получается разделимый подграф, то сам граф является разделимым. С другой стороны, построена бесконечная серия неразделимых графов, у которых удаление любой вершины приводит к разделимому подграфу. Это дает пример неразделимых п-ариых квазигрупп, все (п—1)-арные ретракты которых разделимы.

4) Доказано, что любой, в том числе нелинейный, двоичный код с расстоянием 3 всегда можно вложить в 1-совершенный код некоторой большей длины.

5) Предложен метод построения 1-совершенных кодов, дающий самый многочисленный из известных в настоящий момент класс 1-совершенных двоичных кодов.

6) Построен бесконечный класс диаметрально совершенных (как следствие, оптимальных) троичных равновесных кодов с расстоянием 5.

7) Представлено новое обобщение отображения Грея Ф : Z™k — связанное с известным обобщенным отображением Грея ц) следующим образом: если взять два дуальных линейных Я2*-кода и построить из них двоичные коды, используя обобщения (р и Ф отображения Грея, то весовые нумераторы полученных двоичных кодов будут связаны тождеством Мак-Вильямс. Описаны классы кодов Адамара и расширенных 1-совершенных кодов, полученных из линейных ^2*-КОДОВ при помощи старого и нового обобщенного отображения Грея.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные в ней результаты могут быть использованы в различных разделах общей теории тг-арных квазигрупп, теории кодирования, криптографии, стеганографии.

Апробация работы. Результаты работы докладывались на научных семинарах «Математические вопросы кибернетики» ММФ НГУ, «Теория информации и теория кодирования» ИППИ РАН, семинаре Кафедры безопасности информационных систем ГУАП, «Теория кодирования» и Общеинститутском семинаре Института математики им. С. Л. Соболева СО РАН, в Похангском государственном университете (г. Поханг, Республика Корея, цикл из 6 лекций), включены в список важнейших научных результатов ИМ СО РАН за 2006, 2008 и 2009 годы, прошли апробацию на следующих научных конференциях и совещаниях:

• Международные конференции по алгебраической и комбинаторной теории кодирования АССТ (2002 в Царском Селе, 2004 в Болгарии, 2006 в Звенигороде);

• Международная конференция по оптимальным кодам и смежным вопросам ОС 2005 (Болгария);

• Международная конференция по кодированию и криптографии WCC 2001 (Париж);

• Международная конференция по схемам отношений, кодам и дизайнам Сот2МаС 2004 (Ю. Корея);

• Международная конференция «Coding Theory Days in St.-Petersburg» (2008, Санкт-Петербург);

• Конференция «Математика в современном мире» (2007, Новосибирск) ;

• IX международный семинар «Дискретная математика и ее приложения» (2007, Москва);

• VI сибирская научная школа-семинар «Компьютерная безопасность и криптография» SIBECRYPT (2007, Горно-Алтайск);

• Конференции «Дискретный анализ и исследование операций» DAOR (2000, 2004, Новосибирск). ч

Публикации. Основные материалы диссертации опубликованы в 12 статьях в научных журналах, рекомендованных ВАК. Работы [XI] и [X], результаты которых изложены в главах 2 (кроме раздела 2.2) и 3, написаны в неразделимом соавторстве с Владимиром Николаевичем Потаповым. Работы [IV] и [V] (главы 5 и 6) — в неразделимом соавторстве с Сергеем Владимировичем Августиновичем. По главам, результаты опубликованы:

1. Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискрет. анализ и исслед. операций. Сер. 1.— 1995.— Т. 2, № 1.— С. 4-6. http://mi.mathnet.ru/da450.

2. Августинович С. В., Соловьева Ф. И. О несистематических совершенных двоичных кодах // Проблемы передачи информации. — 1996. — Т. 32, № 3.— С. 47-50. http://mi.mathnet.ru/ppi344.

3. Августинович С. В., Соловьева Ф. И. Построение совершенных двоичных кодов последовательными сдвигами «-компонент // Проблемы передачи информации.— 1997.— Т. 33, № 3.— С. 15-21.http://mi.mathnet.ru/ppi374.

4. Августинович С. В., Соловьева Ф. И., Хеден У. О проблеме рангов и ядер совершенных кодов // Проблемы передачи информации. — 2003. — Т. 39, № 4. — С. 30-34. http://mi.mathnet.ru/ppi313.

5. Бассалыго Л. А. Обобщение теоремы Ллойда на произвольный алфавит // Проблемы управления и теории информации. — 1973. — Т. 2, № 2. С. 133-137.

6. Бассалыго Л. А., Зиновьев В. А., Леонтьев В. К., Фельдман Н. И. Несуществование совершенных кодов для некоторых составных алфавитов // Проблемы передачи информации. — 1975.-— Т. 11, № 3.— С. 3-13. Ы,Ьр://гш. mathnet.ru/ppil590.

7. Белоусов В. Д. п-Арные квазигруппы. — Кишинев: Штиинца, 1972.

8. Белоусов В. Д., Сандик М. Д. п-арные квази-группы и лупы // Сибирский математический журнал. — 1966. — Т. 7, № 1. — С. 31-54.

9. Борисенко В. В. Неприводимые п-квазигруппы на конечных множествах составного порядка // Квазигруппы и лупы. — Кишинев: Штиинца, 1979. Т. 51 из Мат. Исслед. — С. 38-42.

10. Васильев Ю. Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. — М.: Физматгиз, 1962, — Т. 8. — С. 337-339.

11. Васильев Ю. Л., Августинович С. В., Кротов Д. С. О подвижных множествах в двоичном гиперкубе // Дискрет, анализ и исслед. операций.— 2008. — Т. 15, № 3.— С. 11-21. http://mi.mathnet.ru/da530.

12. Глухое М. М. О многообразиях (г, ^-приводимых п-квазигрупп // Сети и квазигруппы. — Кишинев: Штиинца, 1976. — Т. 39 из Мат. Исслед. С. 67-72.

13. Гольдберг В. В. Об инвариантной характеристике некоторых условий замыкания в тернарных квазигруппах // Сибирский математический журнал. — 1975. Т. 16, № 1. — С. 29-43.

14. Гольдберг В. В. О приводимых, групповых и (2п+2)-эдричных (п+1)-тканях многомерных поверхностей // Сибирский математический журнал. 1976. - Т. 17, № 1. - С. 44-57.

15. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования: Пер. с англ. Библиотека Кибернетического Сборника.— М.: Мир, 1976.- 136 с.

16. Думер И. И. Некоторые новые равномерно упакованные коды. — М.: МФТИ, 1976.— Труды МФТИ. Серия «Радиотехника и электроника». Рр. 72-78.

17. Зиновьев В. А. Обобщенные каскадные коды // Проблемы передачи информации. — 1976. —Т. 12, № 1.— С. 5-15. http://mi.mathnet.ru/ppil670.

18. Зиновьев В. А., Зиновьев Д. В. Двоичные расширенные совершенные коды длины 16, построенные обобщенной каскадной конструкцией // Проблемы передачи информации. — 2002. — Т. 38, № 4. — С. 56-84.http: //mi.mathnet.ru/ppil325.

19. Зиновьев В. А., Зиновьев Д. В. Двоичные расширенные совершенные коды длины 16 ранга 14 // Проблемы передачи информации. — 2006. — Т. 42, № 2. — С. 63-80. http://mi.mathnet.ru/ppi45.

20. Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Проблемы передачи информации. — 1972. — Т. 8, № 1. — С. 26-35.http://mi.mathnel.ru/ppi772.

21. Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. — 1973. Т. 2, № 2. — С. 123-132.

22. Зиновьев В. А., Лобстейн А. Об обобщенных каскадных конструкциях совершенных двоичных нелинейных кодов // Проблемы передачи информации. — 2000. — Т. 36, № 4. — С. 59-73. http://mi.mathnet.ru/ppi495.

23. Колмогоров А. Н. О представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одной переменной и сложения // ДАН СССР. — 1957. — Т 114, № 5. — С. 953956.

24. Константинеску И., Хайзе В. Метрика для кодов над кольцами классов вычетов целых чисел // Проблемы передачи информации.— 1997. — Т 33, № 3. — С. 22-28. http://mi.mathnet.ru/ppi375.

25. Кротов Д. С. Комбинированная конструкция совершенных двоичных кодов // Проблемы передачи информации. — 2000. — Т. 36, № 4. — С. 74-79. http://mi.mathnet.ru/ppi496.

26. Кротов Д. С. Индуктивные конструкции совершенных троичных равновесных кодов // Проблемы передачи информации.— 2001.— Т. 37, № 1.—С. 3-11. http://mi.mathnet.ru/ppi505.

27. Кротов Д. С., Потапов В. Н. О кратных МДР- и совершенных кодах, не расщепляемых на однократные // Проблемы передачи информации.— 2004.— Т. 40, № 1.— С. 6-14. http://mi.mathnet.ru/ppill9.

28. Кротов Д. С., Потапов В. Н. О свитчинговой эквивалентности парных квазигрупп порядка 4 и совершенных двоичных кодов // Проблемы передачи информации. — 2010. — Т. 46, № 3. — С. 22-28.http://mi.inathnet.ru/ppi2019.

29. Лось А. В. Построение совершенных g-значных кодов последовательными сдвигами а-компонент // Проблемы передачи информации.— 2004. — Т. 40, № 1. — С. 40-47. http://mi.mathnet.ru/ppil22.

30. Лось А. В. Построение совершенных g-ичных кодов свитчингами простых компонент // Проблемы передачи информации. — 2006. — Т. 42, № 1.— С. 34-42. http://mi.mathnet.ru/ppi35.

31. Мак-Вилъямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М.: Связь, 1979.— 744 с.

32. Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. — 1999. — Т. 6, № 4. — С. 44-48. http://mi.mathnet.ru/da327.

33. Малюгин С. А. Несистематические совершенные двоичные коды // Дискрет, анализ и исслед. операций. Сер. 1.— 2001.— Т. 8, № 1.— С. 55-76. http: / / mi.mathnet.ru/da215.

34. Нечаев А. А. Функции «след» в кольце Галуа и помехоустойчивые коды // Тезисы сообщений V Всесоюзн. симп. по теории колец, алгебр и модулей. — Новосибирск, Россия: 1982,— С. 97.

35. Нечаев А. А. Код кердока в циклической форме // Diskretnaya Matematika.— 1989. — Т. 1, № 4.— С. 123-139. http://mi.mathnet.ru/dm948.

36. Нечаев А. А., Хонолъд Т. Полновесные модули и представления кодов // Проблемы передачи информации. — 1999. — Т. 35, № 3. — С. 1839. http://mi.mathnet.ru/ppi450.

37. Пережогип А. Л. О специальных совершенных паросочетаниях в булевом кубе // Дискрет, анализ и исслед. операций. Сер. 1. — 2005. — Т. 12, № 4. — С. 51-59. http://mi.mathnet.ru/da79.

38. Потапов В. Н. О нижней оценке числа транзитивных совершенных кодов // Дискрет, анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 4. — С. 49-59. http://mi.mathnet.ru/dall.

39. Потапов В. Н. О полностью коммутативно разделимых п-квази-группах // Труды XVI международной школы-семинара «Синтез и сложность управляющих систем». — Санкт-Петербург, Россия: 2006. — Июнь.-С. 88-91.

40. Потапов В. Н. О дополняемости частичных п-квазигрупп порядка 4 // Математические труды. — 2010. — Подано в печать.

41. Потапов В. Н., Кротов Д. С. Асимптотика числа п-квазигрупп порядка 4 // Сибирский математический журнал. — 2006. — Т. 47, № 4.— С. 873-887. http://mi.mathnet.ru/smj902.

42. Потапов В. Н., Кротов Д. С. О числе п-арных квазигрупп конечного порядка // Дискретная математика, — 2010.— Принято в печать.

43. Романов А. М. О разбиениях д-ичных кодов хемминга на непересекающиеся компоненты // Дискрет, анализ и исслед. операций. Сер. 1. — 2004. —Т. 11, № 3. — С. 80-87. http://mi.matimet.ru/dall4.

44. Соловьева Ф. И. О построении транзитивных кодов // Проблемы передачи информации.— 2005.— Т. 41, № 3.— С. 23-31.http://mi.mathnet.ru/ppil04.

45. Токарева Н. Н. Представление ¿^-линейных кодов Препараты с помощью векторных полей // Проблемы передачи информации. — 2005. — Т. 41, № 2. — С. 50-62. http://mi.mathnet.ru/ppi95.

46. Френкин Б. Р. О приводимости и сводимости в некоторых классах n-группоидов. II.— Кишинев: Штиинца, 1972.— Т. 7:1(23) из Мат. Исслед. — С. 150-162.

47. Черемушкин А. В. Каноническая декомпозиция п-арных квазигрупп // Исследование операций и квазигрупп. — Кишинев: Штиинца, 1988.- Т. 102 из Мат. Исслед.-С. 97-105.

48. Ahlswede R.} Aydinian Н. К., Khachatrian L. К. On perfect codes and related concepts // Des. Codes Cryptography. — 2001, —Vol. 22, no. 3.— Pp. 221-237. — DOI: 10.1023/A:1008394205999.

49. Akivis M. A., Goldberg V. V. Solution of Belousov's problem // Discuss. Math., Gen. Algebra Appl. — 2001. — Vol. 21, no. 1, — Pp. 93-103.

50. Avgustinovich S. V., Heden O., Solov'eva F. I. The classification of some perfect codes // Des. Codes Cryptography.— 2004.— Vol. 31, no. 3.— Pp. 313-318.— DOI: 10.1023/B:DESI.0000015891.01562.cl.

51. Avgustinovich S. V., Solov'eva F. I. Perfect binary codes with trivial automorphism group / / Proc. the Information TheoryWorkshop.— Killarney, Ireland: 1998. —June. — Pp. 114-115.—DOI: 10.1109/ITW.1998.706460.

52. Baker R. D., van Lint J. H., Wilson R. M. On the Preparata and Goethals codes // IEEE Trans. Inf. Theory.— 1983. — Vol. 29, no. 3.- Pp. 342345.— DOI: 10.1109/TIT. 1983.105 6675.

53. Best M. R. Perfect codes hardly exist // IEEE Trans. Inf. Theory.— 1983. — Vol. 29, no. 3. — Pp. 349-351. — DOI: 10.1109/TIT.1983.1056677.

54. Borges J., Phelps K. T., R.ifä J. The rank and kernel of extended 1-perfect Zi-linear and additive lion-^-linear codes // IEEE Trans. Inf. Theory.— 2003, — Vol. 49, no. 8. — Pp. 2028-2034. — DOI: 10.1109/TIT.2003.814490.

55. Borges J., Rifä J. A characterization of 1-perfect additive codes // IEEE Trans. Inf. Theory.— 1999.- Vol. 45, no. 8.— Pp. 1688-1697.- DOI:10.1109/18.771247.

56. Brouwer A. E., Cohen A. M.7 Neumaier A. Distance-Regular Graphs.— Berlin: Springer-Verlag, 1989.

57. Bryant D., Horsley D. A proof of Lindner's conjecture on embeddings of partial Steiner triple systems // J. Comb. Des. — 2008. — Vol. 17, no. 1. — Pp. 63-89. — DOI: 10.1002/jcd.20189.

58. Carlet C. Z2fc-linear codes // IEEE Trans. Inf. Theory. — 1998. — Vol. 44, no. 4. — Pp. 1543-1547. — DOI: 10.1109/18.681328.

59. Cadet C., Charpin P., Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems // Des. Codes Cryptography.— 1998,— Vol. 15, no. 2.— Pp. 125-156.— DOI: 10.1023/A:1008344232130.

60. Chihara L. On the zeros of the askey-wilson polynomials, with applications to coding theory // SI AM J. Math. Anal — 1987. — Vol. 18, no. 1.— Pp. 191-207. — DOI: 10.1137/0518015.

61. Colbourn C. J., Rosa A. Triple Systems. — Oxford: Clarendon Press, 1999.

62. Delsarte P., Goethals J. M. Unrestricted codes with the Golay parameters are unique // Discrete Math. — 1975, — Vol. 12, no. 3, — Pp. 211-224.— DOI: 10.1016/0012-365X(75)90047-3.

63. Dillon J. F. APN polynomials: An update.— Fq9, International Conference on Finite Fields and their Applications. — 2009. — Available online: http://mathsci.ucd.ie/ gmg/Fq9Talks/Dillon.pdf.

64. Dornte W. Untersuchungen iiber einen verallgemeinerten Gruppenbegrieff // Mathem.atische Zeitschrift.— 1928.— Vol. 29.— Pp. 1-19.

65. Etzion T. Nonequivalent q- ary perfect codes / / SI AM J. Discrete Math. — 1996. Vol. 9, no. 3. - Pp. 413-423.

66. Etzion T., Schwartz M. Perfect const ant-weight codes // IEEE Trans.1.f. Theory.- 2004.— Vol. 50, no. 9.— Pp. 2156-2165,— dol10.1109/TIT.2004.833355.

67. Etzion T., Vardy A. Perfect binary codes: Constructions, properties and enumeration // IEEE Trans. Inf. Theory.— 1994.— Vol. 40, no. 3.— Pp. 754-763. — DOI: 10.1109/18.335887.

68. Finizio N. J., Lewis J. T. Enumeration of maximal codes // Congr. Numer. 1994. - Vol. 102. - Pp. 139-145.

69. Fon-Der-Flaass D. A bound on correlation immunity // Sib. Ehlektron. Mat. Izv. — 2007.— Vol. 4.— Pp. 133-135.— Avialable online athttp://semr.math.nsc.ru/v4/pl33-135.pdf.

70. Ganter B. Finite partial quadruple systems can be finitely embedded // Discrete Math. — 1974. — Vol. 10, no. 2. — Pp. 397-400. — DOI: 10.1016/0012365X(74) 90130-7.

71. Godsil C. D. Algebraic Combinatorics. — New York: Chapman and Hall, 1993.

72. Golay M. J. E. Notes on digital coding // Proc. IRE. 1949. - Vol. 37, no. 6. — P. 657. — DOI: 10.1109/JRPROC. 1949.233620.

73. Golomb S. W., Posner E. C. Rook domains, latin squares, and error-distributing codes // IEEE Trans. Inf. Theory. — 1964. — Vol. 10, no. 3. — Pp. 196-208. — DOI: 10.1109/TIT. 1964.1053680.

74. Gupta M. K., Bhandari M. C., Lai A. K. On linear codes over » // Des. Codes Cryptography. — 2005. — Vol. 36, no. 3. — Pp. 227-244. — DOI:10.1007/sl0623-004-1717-l.

75. Hamiltonian double latin squares / A. J. W. Hilton, M. Mays, C. A. Rodger, C. St. J. A. Nash-Williams // J. Comb. Theory, Ser. B.— 2003. —Vol. 87, no. 1.— Pp. 81-129. — DOI: 10.1016/S0095-8956(02)00029-1.

76. Hamming R. W. Error detecting and error correcting codes // Bell Syst. Tech. J. 1950. - Vol. 29, no. 2. - Pp. 147-160.

77. Hammons A. R., Kumar P. V., Jr, Calderbank A. R., Sloane N. J. A., Sole P. The ^-linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inf. Theory.— 1994. — Vol. 40, no. 2.- Pp. 301319.— DOI: 10.1109/18.312154.

78. Hartinger T. Cubes with the same number of filled cells in every line of sight.— Web publishing.— 2002-2004.— Available online:http: / / thartmge.de/binaryCube/BinaryCube4.htm.

79. Heden O. A Study of Mixed Perfect Codes: Thesis / University of Stockholm. — Stockholm,, 1977.

80. Heden O. A survey of perfect codes // Adv. Math. Commun. — 2008. — Vol. 2, no. 2,— Pp. 223-247.— DOI: 10.3934/amc.2008.2.223.

81. Heden O., Krotov D. S. On the structure of non-full-rank perfect q-ary codes // Adv. Math. Commun. — 2010. — Accepted. Eprint version:http://arXiv.org/abs/1001.0001.

82. Ito T. Creation method of table, creation apparatus, creation program and program storage medium. — 2004. — http: //ip.com/patapp/US20040243621

83. Jia X. W., Qin Z. P. The number of latin cubes and their isotopy classes // J. Huazhong Univ. Sci. TechnoL— 1999. —Vol. 27, —Pp. 104106. — In Chinese.

84. Kaski P., Ostergard P. R. J., Pottonen O. The Steiner quadruple systems of order 16 // J. Comb. Theory, Ser. A.— 2006.— Vol. 113, no. 8.— Pp. 1764-1770. — DOI: 10.1016/j.jcta.2006.03.017.

85. Kim H. K., Krotov D. S. The poset metrics that allow binary codes of codimension m to be m-, (m — 1)-, or (m — 2)-perfect // IEEE Trans. Inf. Theory.— 2008,— Vol. 54, no. 11.— Pp. 5241-5246.- DOI:10.1109/TIT.2008.929972.

86. Krotov D. S. Inductive constructions of perfect ternary constant-weight codes with distance 3 // Probl. Inf. Transm. — 2001. — Vol. 37, no. 1.— Pp. 1-9. — DOI: 10.1023/A:1010424208992.

87. Krotov D. S. On the binary codes with parameters of doubly-shortened 1-perfect codes // Des. Codes Cryptography. — 2010. — Vol. 57, no. 2. — Pp. 181-194. — DOI: 10.1007/sl0623-009-9360-5.

88. Krotov D. S., Avgustinovieh S. V. On the number of 1-perfect binary codes: A lower bound // IEEE Trans. Inf. Theory.— 2008.- Vol. 54, no. 4. — Pp. 1760-1765. — DOI: 10.1109/TIT.2008.917692.

89. Krotov D. S., Potapov V. N., Sokoloua P. V. On reconstructing reducible n-ary quasigroups and switching subquasigroups // Quasigroups Relat. Syst. 2008. - Vol. 16, no. 1. - Pp. 55-67.

90. Lay wine C. F., Mullen G. L. Discrete Mathematics Using Latin Squares. — Wiley, New York, 1998.

91. Lenstra Jr H. W. Two theorems on perfect codes // Discrete Math.— 1972. — Vol. 3, no. 1-3.— Pp. 125-132. — DOI: 10.1016/0012-365X(72)90028-3.

92. Lindner C. C. A survey of embedding theorems for Steiner sysrems // Topics on Steiner Systems / Ed. by C. C. Lindner, A. Rosa. — North-Holland, 1980. Vol. 7 of Ann. Discrete Math. — Pp. 175-202.

93. Lindstrom B. On group and nongroup perfect codes in q symbols // Math. Scand.- 1969,- Vol. 25.- Pp. 149-158.http: //www.mscand.dk/article.php?id=1942.

94. MacWilliams F. J., Sloane N. J. A. The Theory of Error-Correcting Codes. — Amsterdam, Netherlands: North Holland, 1977.

95. Malyugin S. A. Perfect codes with trivial automorphism group // Proc.the Int. Workshop on Optimal Codes.— Sozopol, Bulgaria: 1998,— June. Pp. 163-167.

96. Markovski S., Dimitrova V., Mileva A. A new method for computing the number of 77-quasigroups // Buletinul Academiei de Stiinte a Republicii Moldova. Matematica. — 2006. — Vol. 52, no. 3. — Pp. 57-64.

97. Martin W. JZhu X. J. Anticodes for the grassman and bilinear forms graphs // Des. Codes Cryptography.— 1995.— Vol. 6, no. 1.— Pp. 7379. — doi: 10.1007/bf01390772.

98. McKay B. D., Wanless I. M. Combinatorial data. Latin cubes and hypercubes. — http://cs.anu.edu.au/ bdm/data/latincubes.html.

99. McKay B. D., Wanless I. M. A census of small Latin hypercubes // SIAM J. Discrete Math. 2008. - Vol. 22, no. 2. - Pp. 719-736. - DOI:10.1137/070693874.

100. Mullen G. L., Weber R. E. Latin cubes of order < 5 // Discrete Math. — 1988. — Vol. 32, no. 3. — Pp. 291-298. — doi: 10.1016/0012-365x(80)90267-s.

101. Ostergard P. R. J., Pottonen O. There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code // J. Comb. Des. — 2007,- Vol. 15, no. 6.- Pp. 465-468.— doi:10.1002/jcd.20122.

102. Ostergard P. R. J., Pottonen O. The perfect binary one-error-correcting codes of length 15: Part I—classification // IEEE Trans. Inf. Theory.— 2009. — Vol. 55, no. 10, — Pp. 4657-4660. — doi: 10.1109/tit.2009.2027525.

103. Ostergard P. R. J., Pottonen O. Two optimal one-error-correcting codes of length 13 that are not doubly shortened perfect codes // Des. Codes Cryptography. — 2010. — To appair.

104. Ostergard P. R. J., Pottonen O., Phelps K. T. The perfect binary one-error-correcting codes of length 15: Part II—properties // IEEE Trans. Inf. Theory.— 2010.— Vol. 56, no. 6,— Pp. 2571-2582.— DOI: 10.1109/TIT.2010.2046197.

105. Ostergard P. R. J., Svanstrom M. Ternary constant weight codes // Electr. J. Comb.— 2002.- Vol. 9, no. 1.- P. R41.http://www.combinatorics.org/Voluine9/Abstracts/v9ilr41.htriil.

106. Phelps K. T. A general product construction for error correcting codes // SI AM J. Algebraic Discrete Methods. — 1984. — Vol. 5, no. 2. — Pp. 224228. — DOI: 10.1137/0605023.

107. Phelps K. T. A product construction for perfect codes over arbitrary alphabets 11 IEEE Trans. Inf. Theory.— 1984.— Vol. 30, no. 5.— Pp. 769-771. — DOI: 10.1109/TIT. 1984.1056963.

108. Phelps K. T., LeVan M. Kernels of nonlinear Hamming codes // Des. Codes Cryptography.— 1995.— Vol. 6, no. 3,— Pp. 247-257,— doi:10.1007/BF01388478.

109. Phelps K. T., LeVan M. Nonsystematic perfect codes // SIAM J. Discrete Math.— 1999.— Vol. 12, no. 1,— Pp. 27-34.— doi:10.1137/S0895480196312206.

110. Phelps K. T., R.ifa J. On binary 1-perfect additive codes: Some structuralproperties // IEEE Trans. Inf. Theory.— 2002.— Vol. 48, 110. 9.— Pp. 2587-2592. — doi: 10.1109/tit.2002.801474.

111. Phelps K. T.} Bifa J., Villanueva M. Rank and kernel of additive (Z4-linear and non-Z4-linear) Hadamard codes // Proc. Ninth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT'2004. — Kranevo, Bulgaria: 2004. June. — Pp. 327-332.

112. Phelps K. T., R.ifa J., Villanueva M. On the additive (^-linear and non-^-linear) Hadamard codes: Rank and kernel // IEEE Trans. Inf. Theory.- 2006,— Vol. 52, no. 1,— Pp. 316-319.— dol10.1109/tit.2005.8c0452.

113. Phelps K. T., Villanueva M. On perfect codes: Rank and kernel // Des. Codes Cryptography.- 2002.- Vol. 27, no. 3,— Pp. 183-194.— doi: 10.1023/a:1019936019517.

114. Potapov V. N. On completion of latin hypercuboids of order 4 // Proc. Twelfth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT 2010. — Novosibirsk, R.ussia: 2010.— September. Pp. 251-255.

115. Preparata F. P. A class of optimum nonlinear double-error correcting codes // Inform. Contr.— 1968.- Vol. 13, no. 4, — Pp. 378-400. doi:10.1016/s0019-9958(68)90874-7.

116. B.ifa JPujol J. Translation-invariant propelinear codes // IEEE Trans. Inf. Theory.— 1997,— Vol. 43, no. 2,— Pp. 590-598.— DOI: 10.1109/18.556115.

117. R.00s C.: Preprint: Delft, the Netherlands, 1979.

118. Schônheim J. On linear and nonlinear single-error-correcting ç-ary perfect codes // Inform. Contr.— 1968.— Vol. 12, no. 1.— Pp. 23-26.— DOI:10.1016/S0019-9958(68)90167-8.

119. Shcherbacov V. A. Quasigroups in cryptology: E-print 1007.3572: arXiv.org, 2010. — Available at http://arxiv.org/abs/1007.3572.

120. Soedarmadji E. Latin hypercubes and MDS codes // Discrete Math. — 2006. — Vol. 306, no. 12. — Pp. 1232-1239. — DOI: io.ioi6/j.disc.2006.02.on.

121. Solov'eva F. I. Switchings and perfect codes // Numbers, Information and Complexity / Ed. by I. Althôfer, N. Cai, G. Dueck et al. — Kluwer Academic Publisher, 2000.- Pp. 311-314.

122. Solov'eva F. I. On perfect binary codes // Discrete Appl. Math. — 2008. — Vol. 156, no. 9. — Pp. 1488-1498. — DOI: 10.1016/j.dam.2005.10.023.

123. Spence E. Two-graphs // CRC Handbook of Combinatorial Designs / Ed. by C. J. Colbourn, J. H. Dinitz.— Boca Raton, FL: CR.C Press, 1996,— Pp. 686-694.

124. Svanstrôm M. A class of perfect ternary constant-weight codes // Des. Codes Cryptography. — 1999,— Vol. 18, no. 1-3.— Pp. 223-230.— DOI: 10.1023/A:1008361925021.

125. Svanstrôm M. Ternary Codes with Weight Constraints: Dissertation 572 / Linkoping University. — 1999.

126. Tarry G. Le problème des 36 officers // Comptes Rendu de l'Association Française pour l'Avancement de Science Naturel (National Academy of Sciences).- 1900, 1901, —Vol. 1, 2.- Pp. 122-123, 170-203.

127. Tietàvàinen A. On the nonexistence of perfect codes over finite fields // SIAM J. Appl. Math. 1973. - Vol. 24. - Pp. 88-96.

128. Zaslavsky T. Associativity in multary quasigroups: the way of biased expansions: eprint math.CO/0411268: arXiv.org, 2004.— Available athttp: / / arxiv. org/abs / math/0411268.Публикации автора по теме диссертации