Комбинаторные свойства дискретных структур и приложения к криптологии

Ю. В. Таранников

КОМБИНАТОРНЫЕ СВОЙСТВА
ДИСКРЕТНЫХ СТРУКТУР
И ПРИЛОЖЕНИЯ К КРИПТОЛОГИИ

Электронное издание

Москва
Издательство МЦНМО
2014

УДК 519.1
ББК 22.176
Т19

Таранников Ю. В.
Комбинаторные свойства дискретных структур и приложения к криптологии
Электронное издание
М.: МЦНМО, 2014
152 с.
ISBN 978-5-4439-2045-0

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

Подготовлено на основе книги: Ю. В. Таранников. Комбинаторные
свойства дискретных структур и приложения к криптологии. — М.:
МЦНМО, 2011.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11. Тел. (499) 241-74-83
http://www.mccme.ru

ISBN 978-5-4439-2045-0
c⃝ Таранников Ю. В., 2011.
c⃝ МЦНМО, 2014.

ОГЛАВЛЕНИЕ

Введение
6

Глава 1. Теоремы Дилуорса, Кёнига, Холла и Шпернера
8
§ 1.1.
Теорема Дилуорса . . . . . . . . . . . . . . . . . . . . . . .
8
§ 1.2.
Теорема Кёнига . . . . . . . . . . . . . . . . . . . . . . . . .
10
§ 1.3.
Теорема Холла . . . . . . . . . . . . . . . . . . . . . . . . .
11
§ 1.4.
Теорема Шпернера . . . . . . . . . . . . . . . . . . . . . . .
12

Глава 2. Теорема Рамсея
15
§ 2.1.
Теорема Рамсея . . . . . . . . . . . . . . . . . . . . . . . . .
15
§ 2.2.
Следствия из теоремы Рамсея . . . . . . . . . . . . . . . .
16
§ 2.3.
Числа Рамсея . . . . . . . . . . . . . . . . . . . . . . . . . .
21

Глава 3. Теоремы Грэхема–Ротшильда и ван дер Вардена
26
§ 3.1.
Теорема Грэхема–Ротшильда . . . . . . . . . . . . . . . . .
26
§ 3.2.
Теорема ван дер Вардена . . . . . . . . . . . . . . . . . . .
29

Глава 4. Теорема Симона–Вегенера
30
§ 4.1.
Теорема Симона–Вегенера
. . . . . . . . . . . . . . . . . .
30
§ 4.2.
Следствия из теоремы Симона–Вегенера . . . . . . . . . .
34

Глава 5. Матрицы Адамара
37
§ 5.1.
Символы Лежандра . . . . . . . . . . . . . . . . . . . . . .
37
§ 5.2.
Кронекерово произведение матриц
. . . . . . . . . . . . .
39
§ 5.3.
Определение матриц Адамара . . . . . . . . . . . . . . . .
39
§ 5.4.
Методы построения матриц Адамара . . . . . . . . . . . .
40
§ 5.5.
Построение матриц Адамара методом Вильямсона . . . .
43

Глава 6. Кодовые множества с большими кодовыми расстояниями
47
§ 6.1.
Коды, кодовое расстояние и исправление ошибок . . . . .
47
§ 6.2.
Некоторые оценки мощности кода . . . . . . . . . . . . . .
50
§ 6.3.
Построение кодов с большими кодовыми расстояниями
при помощи матриц Адамара
. . . . . . . . . . . . . . . .
52

ОГЛАВЛЕНИЕ

Глава 7. Блок-дизайны
56
§ 7.1.
Блок-дизайны и условия на их параметры . . . . . . . . .
56
§ 7.2.
Симметричные блок-дизайны и условия на их параметры
59

Глава 8. Теорема Брука–Райзера–Човлы
63
§ 8.1.
Теорема Лагранжа о четырех квадратах . . . . . . . . . .
63
§ 8.2.
Теорема Брука–Райзера–Човлы . . . . . . . . . . . . . . .
65

Глава 9. Конечные геометрии
69
§ 9.1.
Аффинная плоскость
. . . . . . . . . . . . . . . . . . . . .
69
§ 9.2.
Проективная плоскость . . . . . . . . . . . . . . . . . . . .
71
§ 9.3.
Проективная геометрия . . . . . . . . . . . . . . . . . . . .
73

Глава 10. Взаимно ортогональные латинские квадраты
76
§ 10.1. Ортогональные латинские квадраты и их простейшие
конструкции
. . . . . . . . . . . . . . . . . . . . . . . . . .
76
§ 10.2. Опровержение гипотезы Эйлера для одного из случаев
.
79
§ 10.3. Взаимно ортогональные латинские квадраты . . . . . . .
81

Глава 11. Ортогональные массивы
85
§ 11.1. Ортогональные массивы
. . . . . . . . . . . . . . . . . . .
85
§ 11.2. Соотношения на параметры ортогональных массивов
. .
88
§ 11.3. Применение ортогональных массивов . . . . . . . . . . . .
89

Глава 12. Линейные коды
92
§ 12.1. Линейные коды . . . . . . . . . . . . . . . . . . . . . . . . .
92
§ 12.2. Линейный код как ортогональный массив
. . . . . . . . .
98

Глава 13. Неравенство Бирбрауэра–Фридмана
99
§ 13.1. Неравенство Бирбрауэра–Фридмана . . . . . . . . . . . . .
99
§ 13.2. Неравенство Рао . . . . . . . . . . . . . . . . . . . . . . . . 103

Глава 14. Трансверсальные дизайны
105
§ 14.1. Трансверсальные дизайны. Эквивалентность трансверсальных дизайнов и ортогональных массивов силы 2
и индекса 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
§ 14.2. Прямая конструкция ортогонального массива силы 2
и индекса 1 с числом элементов, равным степени простого числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
§ 14.3. Усеченные ортогональные дизайны. Конструкция Вильсона
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

ОГЛАВЛЕНИЕ
5

§ 14.4. Завершение опровержения гипотезы Эйлера о несуществовании ортогональных латинских квадратов . . . . . . 112

Глава 15. Комбинаторные t-дизайны
115
§ 15.1. Условия существования t-дизайнов
. . . . . . . . . . . . . 115
§ 15.2. Адамаровы дизайны . . . . . . . . . . . . . . . . . . . . . . 116
§ 15.3. Существование нетривиальных t-дизайнов с возможно
повторяющимися блоками
. . . . . . . . . . . . . . . . . . 117

Глава 16. Код Голея и дизайны Витта
120
§ 16.1. Код Голея . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
§ 16.2. Дизайны Витта . . . . . . . . . . . . . . . . . . . . . . . . . 122

Глава 17. Разностные множества
125
§ 17.1. Разностные множества
. . . . . . . . . . . . . . . . . . . . 125
§ 17.2. Теорема Манна . . . . . . . . . . . . . . . . . . . . . . . . . 127

Глава 18. Булевы функции. Бент-функции
129
§ 18.1. Булевы функции и коэффициенты Уолша . . . . . . . . . 129
§ 18.2. Бент-функции
. . . . . . . . . . . . . . . . . . . . . . . . . 132
§ 18.3. Связь между бент-функциями и разностными множествами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

Глава 19. Корреляционно-иммунные и устойчивые булевы функции140
§ 19.1. Корреляционно-иммунные и устойчивые функции
. . . . 140
§ 19.2. Спектральная характеризация корреляционно-иммунных
функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
§ 19.3. Верхние оценки нелинейности корреляционно-иммунных
и устойчивых булевых функций . . . . . . . . . . . . . . . 146
§ 19.4. Теорема Фон-Дер-Флаасса
. . . . . . . . . . . . . . . . . . 148

Литература
150

ВВЕДЕНИЕ

Книга написана на основе специального курса лекций «Комбинаторные свойства дискретных структур», читавшегося автором на механикоматематическом факультете МГУ в течение ряда лет. Книга посвящена
вопросам существования и построения комбинаторных объектов со специальными свойствами, при этом вопросы перечисления (подсчета количества) таких объектов в случае их существования оставляются в стороне. Среди рассматриваемых в книге комбинаторных объектов — частично упорядоченные множества, графы, булевы функции, матрицы со
специальными свойствами, коды, блок-дизайны, конечные геометрии,
латинские квадраты, ортогональные массивы, разностные множества
и другие. Большое внимание в книге уделяется указанию взаимосвязей между комбинаторными объектами различных типов. Для многих
классов комбинаторных объектов указаны их криптологические приложения. Приводимые в книге доказательства автор старался выдержать
в комбинаторном стиле и сделать их максимально простыми и понятными. Большая часть материала доступна студентам младших курсов.
Аспиранты и научные работники также найдут много полезного, особенно это касается систематического взгляда на предмет.
Первые четыре главы книги посвящены классическим комбинаторным теоремам существования, к которым мы относим теоремы Дилуорса, Кёнига, Холла, Шпернера, Рамсея, Грэхема–Ротшильда, ван дер
Вардена и Симона–Вегенера. Оставшаяся часть книги посвящена объектам, которые в последнее время принято называть комбинаторными
дизайнами. На русском языке данным вопросам в своей значительной
части посвящены переводные книги Г. Дж. Райзера [8] и М. Холла [15],
а также разделы книг К. А. Рыбникова [9], В. Н. Сачкова [10] и В. Е. Тараканова [11]. Все эти книги появились достаточно давно, на заре развития этой области. С тех пор для многих утверждений были найдены
значительно более простые доказательства и были предложены методически более ясные подходы к изложению материала [16, 19, 22, 37],
которые используются в данной книге. Ряд приводимых в книге результатов принадлежит автору. В частности, это результаты о верхних

ВВЕДЕНИЕ
7

оценках нелинейности корреляционно-иммунных и устойчивых булевых
функций, об ограниченности числа нелинейных переменных в устойчивых функциях высокого порядка. Автором также впервые построен
пример функции, заданной на q-значных наборах, q ⩾ 3, не имеющей
симметрических подфункций от двух переменных; приводимое в книге
более простое доказательство для этого примера получено студентом
автора И. В. Гимоном. Аспиранту автора А. В. Халявину принадлежит
приводимое в книге доказательство теоремы Фон-Дер-Флаасса на языке
коэффициентов Уолша.
Криптологические приложения комбинаторных дизайнов в целом
хорошо известны, однако в основном на уровне отдельных статей (некоторые приложения даны в книге [38]), в частности, до сих пор не было
систематического изложения связи комбинаторных дизайнов с криптологическими свойствами булевых функций. Следует отметить, что
криптографическим свойствам булевых функций посвящена недавно
вышедшая книга О. А. Логачева, А. А. Сальникова и В. В. Ященко
«Булевы функции в теории кодирования и криптографии» [7].

Г Л А В А 1

ТЕОРЕМЫ ДИЛУОРСА, КЁНИГА, ХОЛЛА И
ШПЕРНЕРА

§ 1.1. Теорема Дилуорса

Пусть для каждой упорядоченной пары (a, b) элементов множества
P определено, имеет место для этой пары отношение a ≺ b или нет.
Пусть также это отношение удовлетворяет свойствам
1) рефлексивности: a ≺ a ∀ a ∈ P;
2) антисимметричности: a ≺ b, b ≺ a ⇒ a = b;
3) транзитивности: a ≺ b, b ≺ c ⇒ a ≺ c.
Тогда множество P называется частично упорядоченным, а отношение
≺ — отношением частичного порядка. Элементы a и b частично упорядоченного множества называются сравнимыми, если a ≺ b или b ≺ a.
В противном случае элементы a и b называются несравнимыми. Элемент a частично упорядоченного множества P называется максимальным, если в P не существует элемента b, отличного от a, такого что
a ≺ b. Аналогично элемент a из P называется минимальным, если в P
не существует элемента b, отличного от a, такого что b ≺ a.
Цепью в частично упорядоченном множестве называется подмножество элементов, любые два из которых сравнимы. Антицепью называется такое подмножество элементов, что любые два различных элемента
этого подмножества несравнимы.
Теорема 1 (Дилуорс). Пусть P — конечное частично упорядоченное множество. Обозначим через m наименьшее число непересекающихся цепей, которыми может быть покрыто множество P, а через
M — наибольшую мощность антицепи в P. Тогда M = m.
Доказательство. Любые два различных элемента антицепи не могут
принадлежать одной цепи, поэтому M ⩽ m. Доказательство противоположного неравенства осуществляется индукцией по мощности множества P. В случае |P| = 1, очевидно, M = m = 1. Пусть утверждение теоремы выполняется для всех частично упорядоченных множеств,
мощность которых меньше |P|. Возможны два случая:

§ 1.1. ТЕОРЕМА ДИЛУОРСА
9

а) В множестве P существует антицепь U из M элементов, не содержащая ни все максимальные, ни все минимальные элементы. Определим множества P + и P − следующим образом:

P + := {p ∈ P : u ≺ p для некоторого u ∈ U},

P − := {p ∈ P : p ≺ u для некоторого u ∈ U}.

Из этого определения видно, что P + ∪ P − = P и P + ∩ P − = U. Кроме того, в случае a) ни P +, ни P − не совпадает со всем множеством P.
Поэтому к множествам P + и P − применимо предположение индукции.
Оба эти множества содержат антицепь U, поэтому максимальная мощность антицепи в них равна M. Следовательно, каждое из множеств P +

и P − можно разложить на M непересекающихся цепей. Склеивая эти
цепи в точках, принадлежащих U, получаем разложение множества P
на M цепей.
б) Каждая антицепь мощности M содержит либо все минимальные
элементы, либо все максимальные элементы множества P. Следовательно, найдется не более двух антицепей, одна из которых содержит все
максимальные элементы, а другая — все минимальные элементы. Пусть
a1 — минимальный элемент, тогда существует такой максимальный элемент a2, что a1 ≺ a2. (Эти два элемента могут совпадать.) Удаляя из P
элементы a1 и a2, получим множество P ′; легко видеть, что максимальная мощность антицепи в P ′ равна M − 1. Множество P ′ содержит менее |P| элементов, поэтому к нему применимо предположение индукции.
Следовательно, множество P ′ можно покрыть M − 1 непересекающейся цепью. Добавляя к ним цепь, состоящую из двух элементов a1 и a2
(или одного элемента, если a1 = a2), получим покрытие множества P,
состоящее из M непересекающихся цепей.
Рассмотрение совокупности случаев а) и б) показывает, что M ⩾ m.
Теорема доказана.
□
Теорема 2. Пусть P — конечное частично упорядоченное множество. Обозначим через m наименьшее число непересекающихся антицепей, которыми может быть покрыто множество P, а через M —
наибольшую мощность цепи в P. Тогда M = m.
Доказательство. Любые два различных элемента цепи не могут принадлежать одной антицепи, поэтому на покрытие каждого элемента
максимальной цепи нужно затратить антицепь и, следовательно, M ⩽
⩽ m. Докажем противоположное неравенство. Пусть M — длина максимальной цепи. Обозначим через AC1 множество всех минимальных
элементов множества P, которое образует антицепь. Индуктивно будем
определять ACi как множество всех минимальных элементов множе

ГЛ. 1. ТЕОРЕМЫ ДИЛУОРСА, КЁНИГА, ХОЛЛА И ШПЕРНЕРА

ства P \
i−1
j=1
ACj
до тех пор, пока последнее не станет пустым. Постро
енные множества ACi, i = 1, 2, . . . , h, состоят из попарно несравнимых
элементов и поэтому являются антицепями. Заметим, что для любого
элемента a ∈ ACi, i = 2, 3, . . . , h, существует элемент b ∈ ACi−1 такой,
что b ≺ a, иначе элемент a по построению сам бы попал в множество
ACi−1. Отсюда следует, что для любого элемента множества ACh существует цепь, содержащая по одному элементу всех множеств ACi,
i = 1, 2, . . . , h. Поэтому m ⩽ h = M, что и требовалось доказать.
□

§ 1.2. Теорема Кёнига

Пусть G = (V, E) и V ′ ⊆ V . Индуцированным графом G[V ′] или
ограничением графа на подмножество его вершин V ′ называется граф
(V ′, E′), где E′ — подмножество E, состоящее из тех и только тех ребер
графа G, обе концевые вершины которых принадлежат V ′. Паросочетанием в графе называется множество ребер, никакие два из которых
не имеют общих вершин. Вершинное покрытие графа — это такое
множество его вершин, что каждое ребро инцидентно хотя бы одной
вершине данного множества. Граф G = (V, E) называется двудольным,
если множество его вершин V разбивается на два непересекающихся
подмножества V1 и V2, V = V1 ⊔ V2, так, что G[V1] и G[V2] — пустые
графы.
Теорема 3 (Кёниг). Пусть G = (V, E) = (V1 ⊔ V2, E) — двудольный
граф. Обозначим через m′ наименьшую мощность вершинного покрытия графа G, а через M ′ —наибольшую мощность паросочетания графа G. Тогда M ′ = m′.
Доказательство. Определим на множестве V отношение частичного
порядка следующим образом: если a ̸= b, то a ≺ b тогда и только тогда,
когда {a ∈ V1, b ∈ V2, (a, b) ∈ E}.
По теореме Дилуорса наименьшее число m непересекающихся цепей,
которыми может быть покрыто множество V , равно M — наибольшей
мощности антицепи в V . По построению длина любой цепи равна 1
или 2, совокупность непересекающихся цепей длины 2 образует паросочетание. Поэтому M ′ = |V | − m. С другой стороны, все вершины, не
вошедшие в вершинное покрытие, образуют антицепь. Следовательно,
m′ = |V | − M. Отсюда M ′ = m′.
□
(0, 1)-матрица — это прямоугольная матрица, все элементы которой
равны 0 или 1. Строки и столбцы матрицы назовем линиями. Диагональю назовем множество единичных элементов матрицы, никакие два
из которых не стоят в одной линии.

§ 1.3. ТЕОРЕМА ХОЛЛА
11

Теорема 4 (матричный
вариант теоремы Кёнига). Наибольшая
мощность диагонали в (0, 1)-матрице равна наименьшему числу
линий в ней, содержащих все единичные элементы.
Доказательство. Сопоставим (0, 1)-матрице двудольный граф G =
= (V, E) = (V1 ⊔ V2, E), где вершины из множества V1 соответствуют
строкам матрицы, вершины из множества V2 соответствуют столбцам
матрицы и для вершин a ∈ V1 и b ∈ V2 ребро (a, b) существует тогда
и только тогда, когда на пересечении строки и столбца матрицы, соответствующих вершинам a и b, стоит 1. Тогда каждой единице матрицы
соответствует ребро графа, совокупности линий, содержащих все единицы матрицы, соответствует вершинное покрытие, а диагонали соответствует паросочетание.
□

§ 1.3. Теорема Холла

Пусть G = (V, E) = (V1 ⊔ V2, E) — двудольный граф и V ′ ⊆ V1. Обозначим через I(V ′) множество всех таких вершин из V2, которые являются концом какого-либо ребра из E, другой конец которого принадлежит V ′.
Теорема 5 (Холл). В графе G = (V, E) = (V1 ⊔ V2, E) паросочетание
мощности |V1| существует тогда и только тогда, когда |V ′| ⩽ |I(V ′)|
для любого V ′ ⊆ V1.
Доказательство. Пусть V ′
1 ⊔ V ′
2 — вершинное покрытие графа G.
Очевидно, что для любого минимального вершинного покрытия выполнено V ′
2 = I(V1 \ V ′
1). Мощность этого покрытия меньше |V1| тогда
и только тогда, когда |V ′
2| < |V1 \ V ′
1|. Поэтому по теореме Кёнига мощность максимального паросочетания меньше |V1| тогда и только тогда,
когда найдется такое V ′ ⊆ V1, что |V ′| > |I(V ′)|. Это доказывает теорему.
□
Пусть A = {ai} — конечное множество и A = {Aj}, j = 1, 2, . . . , k, —
система его подмножеств. Элементы a1, a2, . . . , ak называются системой
различных представителей (трансверсалью) системы A, если все эти
элементы различны и aj ∈ Aj, j = 1, 2, . . . , k.
Теорема 6 (переформулировка теоремы Холла для системы различных представителей). Система различных представителей системы
A существует тогда и только тогда, когда число множеств в произвольной подсистеме A′ системы A не превосходит числа элементов
в объединении всех множеств из A′.
Доказательство. Построим двудольный граф G(V1 ⊔ V2, E), сопоставляя множествам системы A вершины из V1, элементам множества
A — вершины из V2 и сопоставляя паре вершин a ∈ V1 и b ∈ V2 ребро

ГЛ. 1. ТЕОРЕМЫ ДИЛУОРСА, КЁНИГА, ХОЛЛА И ШПЕРНЕРА

(a, b) тогда и только тогда, когда соответствующий вершине b элемент
принадлежит соответствующему вершине a множеству. В этих терминах наше утверждение в точности соответствует теореме Холла.
□
Булевым кубом V n будем называть множество всех двоичных наборов (наборов из нулей и единиц) длины n. Число таких наборов,
очевидно, равно 2n. С булевым кубом ассоциируется также граф
Bn = (V n, En), в котором ребро соединяет две несовпадающие вершины
a и b тогда и только тогда, когда соответствующие этим вершинам
наборы различаются ровно в одной компоненте. Через V n
k
обозначается множество всех двоичных наборов длины n, содержащих ровно
k единичных компонент. Множество V n
k называется также k-м слоем

булева куба. Несложно видеть, что число наборов в V n
k
равно
n
k

.
Максимальный по мощности слой булева куба называется средним слоем. Легко видеть, что при четном n средний слой один
k = n

2

, а при

нечетном — два
k =
n

2

,
n

2

. Обозначим Bn
k,k+1 = Bn[V n
k ⊔ V n
k+1].
Граф Bn
k,k+1, очевидно, является двудольным.
Теорема 7 (о максимальном паросочетании в соседних слоях булева куба). В графе Bn
k,k+1, k < n

2 , существует паросочетание мощно
сти
n
k

.

Доказательство. Пусть V ′ — произвольное подмножество множества
V n
k . Каждая вершина из V ′ соединена ребром в Bn
k,k+1 с n − k вершинами из V n
k+1, в то же время любая вершина из V n
k+1 соединена ребром не

более чем с k + 1 вершиной из V ′. Поэтому I(V ′) ⩾ n − k

k + 1 |V ′| ⩾ |V ′|. Поэтому по теореме Холла мощность максимального паросочетания равна
|V n
k | =
n
k

.
□

Следствие 1. В графе Bn
k,k+1, k ⩾ n/2, существует паросочетание

мощности
n
k + 1

.

§ 1.4. Теорема Шпернера

На множестве V n введем отношение частичного порядка следующим
образом:
α = (α1, α2, . . . , αn) ≺ β = (β1, β2, . . . , βn)

тогда и только тогда, когда

αi ⩽ βi для всех i, i = 1, . . . , n.

Весом |α| набора α будем называть число единиц в наборе α.