ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 2

УДК 621.391.1 : 519.7

М.Н. Вялый¹, В.К. Леонтьев²

ГЕОМЕТРИЯ СДВИГОВ В БУЛЕВОМ КУБЕ

У операции сложения Минковского геометрических фигур есть дискретный

аналог - сложение подмножеств булева куба как векторного пространства над

полем из двух элементов. Относительно такой операции подмножества булева

куба (или булевы функции от нескольких переменных) образуют моноид. Этот

моноид представляет интерес как в классическом дискретном анализе, так и

в ряде задач, связанных с теорией информации. Рассматриваются различные

аспекты сложности этого моноида: структурный, алгоритмический, алгебраи-

ческий.

Ключевые слова: сложение Минковского, булев куб, моноид, порождающие эле-

менты, примитивные элементы, последовательности кратных.

DOI: 10.1134/S0555292319020049

§ 1. Введение

Пусть B = {0, 1}, а Bⁿ = {0, 1}ⁿ - множество, которое можно понимать по-раз-

ному, в зависимости от той или иной конкретной задачи.

С комбинаторной точки зрения Bⁿ - это булев куб : множество двоичных слов,

т.е. слов в алфавите B, длины n.

Геометрически Bⁿ является множеством вершин единичного куба Eⁿ в n-мерном

пространстве:

Eⁿ = {x ∈ Rⁿ : 0 ≤ x_i ≤ 1, 1 ≤ i ≤ n}.

Если понимать под 0 и 1 элементы поля F₂, то Bⁿ совпадает с n-мерным коорди-

натным векторным пространством Fn2 над этим полем.

Для нас будет важно именно последнее представление. Сложение векторов в век-

торном пространстве определяет естественным образом сложение подмножеств:

A + B = {x : x = y ⊕ z, y ∈ A, z ∈ B}.

В геометрии такая операция называется суммой Минковского, мы сохраним это

название для этой операции с подмножествами Bⁿ.

В дальнейшем мы обозначаем операцию сложения в Fn2 через ⊕, сохраняя обо-

значение + для суммы Минковского.

¹ Работа выполнена частично в рамках государственного задания по теме 0063-2016-0003, а также

при частичной финансовой поддержке Российского фонда фундаментальных исследований (номер

проекта 17-01-00300), исследование также финансировалось в рамках программы государственной

поддержки ведущих университетов Российской Федерации “5-100”.

² Работа выполнена частично в рамках государственного задания по теме 0063-2016-0003, а также

при частичной финансовой поддержке Российского фонда фундаментальных исследований (номер

проекта 17-01-00300).

Пример 1. Приведем несколько простых примеров сложения Минковского под-

множеств булева куба:

1. Bⁿ + A = Bⁿ для любого A ⊆ Bⁿ;

2. A + A = A, если A - подпространство Bⁿ.

Операция сложения Минковского обладает следующими легко проверяемыми

свойствами:

{0ⁿ} + A = A (существование нейтрального элемента);

2. A + (B + C) = (A + B) + C (ассоциативность);

3. A + B = B + A (коммутативность);

4. (A ∪ B) + C = (A + C) ∪ (B + C) (дистрибутивность по объединению);

⋃

(A + B_i) = A + B_i.

i=1

Подмножества Bⁿ находятся во взаимно-однозначном соответствии с булевы-

ми функциями - функции f : Bⁿ → B сопоставляется множество ее единиц N_f =

= {x ∈ Bⁿ : f(x) = 1}. Функцию, соответствующую множеству S, будем называть

характеристической функцией множества и обозначать через χ_S.

Такое соответствие позволяет определить сумму Минковского и для булевых

функций: сумма Минковского функций f₁ и f₂ - это такая функция f₃, что Nf3 =

= Nf1 + Nf2. Таким образом, чтобы сложить две булевы функции по Минковскому,

нужно сложить по Минковскому множества их единиц.

В соответствии с принятым выше соглашением сумму Минковского булевых

функций обозначаем через f₁ +f₂, а поточечную сумму по модулю 2 значений функ-

ций (XOR) - через f₁ ⊕ f₂.

Для суммы Минковского булевых функций имеется формула

⋁

(f + g)(x) =

f (y)g(x ⊕ y),

(1)

y∈Bⁿ

напоминающая свертку.

Пример 2.

1. Если F(x₁, . . . , x_n) ≡ 1, то f + F = F для любой булевой функции f от n аргу-

ментов;

2. Если f(x₁, . . . , x_n) = x₁ ⊕ x₂, f₂(x₁, . . ., x_n) = x₂, то f₁ + f₂ ≡ 1;

3. Будем обозначать 2f(x) = f(x) + f(x). Если 0ⁿ ∈ N_f , то N_f ⊆ N2f ;

4. Сумма по Минковскому симметрических булевых функций является симметри-

ческой булевой функцией.

Напомним, что моноидом называется множество M, снабженное ассоциативной

бинарной операцией +: M × M → M, относительно которой в M существует ней-

тральный элемент e ∈ M. Иными словами, для любого m ∈ M выполняются равен-

ства e + m = m + e = m, и для любой тройки m₁, m₂, m₃ элементов M выполняется

равенство m₁ + (m₂ + m₃) = (m₁ + m₂) + m₃.

Как видно из сформулированных выше свойств 1 и 2 сложения Минковского,

подмножества n-мерного булева куба с операцией сложения Минковского образуют

моноид. Мы будем называть его моноидом Минковского и обозначать через Mⁿ.

Нейтральный элемент в моноиде Минковского будем обозначать через

= {0ⁿ}.

Моноид Минковского представляет определенный интерес как в классическом

дискретном анализе (см. [1, 2]), так и в целом ряде задач, связанных с теорией ин-

формации (см. [3,4]).

Нас интересует сложность операции сложения Минковского. Есть разные спо-

собы описывать сложность операции: структурный, алгоритмический, алгебраиче-

ский. В последующем изложении мы приведем примеры таких способов и уточним

формулировки.

§2. Вычисление суммы Минковского

В этом параграфе мы обсудим вопрос о том, насколько трудно найти сумму Мин-

ковского двух множеств. Такая задача подразумевает алгоритмическую постанов-

ку. Чтобы точно ее сформулировать, нужно зафиксировать способ представления

подмножества булева куба (или булевой функции). Таких способов много, и для

каждого получаем конкретную алгоритмическую задачу, сложность которой можно

оценивать.

Простейший способ - табличный. Подмножество X ⊆ Bⁿ задается таблицей зна-

чений характеристической функции, т.е. для каждого элемента x ∈ Bⁿ указано,

принадлежит ли он множеству X. Описание множества в таком формате имеет би-

товую длину 2ⁿ.

Легко видеть, что для вычисления суммы Минковского двух множеств в таблич-

ном представлении существует полиномиальный алгоритм: вычисление по форму-

ле (1) всей таблицы значений f + g занимает время O(n22n), а длина входа 2 · 2ⁿ.

Более естественный способ “прямого” задания подмножества X булева куба Bⁿ

состоит в том, чтобы записать список элементов этого множества. Битовая длина та-

кого представления равна O(n|X|) (так как элементы задаются битовыми строками

длины n), эта длина может быть много меньше 2ⁿ для некоторых множеств X и не

превосходит O(n2ⁿ). Поэтому алгоритмическая сложность задач при таком способе

представления подмножеств булева куба может оказаться выше, чем при табличном.

Однако прямое применение определения дает и в этом случае полиномиальный

алгоритм вычисления суммы Минковского.

И для табличного способа представлений подмножества, и для задания подмно-

жества списком существуют также алгоритмы вычисления суммы Минковского на

памяти, логарифмической по длине входа.

Напомним модель вычисления на памяти s(n), где s(·) - некоторая числовая

функция. Это машина Тьюринга с тремя лентами. На входной ленте записан вход

задачи, и эту ленту разрешается только читать. На рабочей ленте разрешены и чте-

ние, и запись. Требуется, чтобы размер области, содержащей непустые ячейки на

рабочей ленте, в любой момент вычисления на любом входе длины n не превос-

ходил s(n). Наконец, на выходной ленте разрешена только запись. Состояние этой

ленты в конце вычисления является результатом работы.

Поскольку общее количество конфигураций рабочей ленты не превосходит

s(n)2O(s(n)), время вычисления на логарифмической памяти, когда s(n) = O(log n),

всегда полиномиально по n.

Заметим также, что при вычислениях на логарифмической по длине входа па-

мяти возможна произвольная адресация к входным данным: если на рабочей ленте

записан адрес входного символа, то переместить головку на входной ленте на этот

символ можно, используя на рабочей ленте счетчик, размер которого O(log n).

Легко видеть, что вычисление по формуле (1) возможно на памяти O(n), лога-

рифмической по длине таблиц, задающих слагаемые. Для этого достаточно поддер-

живать два указателя на x и y.

Сумму Минковского подмножеств X и Y , заданных списками элементов, так-

же можно вычислить на памяти, логарифмической по длине входа, т.е. по длине

списков, задающих множества.

Сложение по модулю 2 двух битовых строк длины n возможно на памяти O(log n),

для чего достаточно двух указателей (на i-й бит каждой из строк). Используя еще

два указателя на элементы множеств-слагаемых, можно вычислить все попарные

суммы элементов X и Y и построить на логарифмической памяти список элемен-

тов X +Y . Но этот список может содержать повторения. Избавиться от повторений

возможно ценой некоторого усложнения алгоритма.

Предложение 1. Существует алгоритм, работающий на логарифмической

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

X, Y булева куба порождает список без повторений множества X + Y .

Доказательство. Пусть (x₁,...,x_k), (y₁,...,y_ℓ), где x_i,y_j ∈ Bⁿ, - списки эле-

ментов на входе алгоритма. Алгоритм перебирает все пары (i, j), где 1 ≤ i ≤ k,

1 ≤ j ≤ ℓ, в лексикографическом порядке и для каждой такой пары перебирает

все пары (i^′, j^′), которые меньше (i, j) в лексикографическом порядке. Для каждой

четверки i, j, i^′, k^′ алгоритм проверяет равенство x_i ⊕ y_j = x_i′ ⊕ y_j′ . Это возмож-

но на логарифмической памяти, как описано выше. Если для данной пары (i, j) и

всех меньших в лексикографическом порядке пар (i^′, j^′) равенство не выполняется,

алгоритм включает в результирующий список битовую строку x_i ⊕ y_j .

Корректность алгоритма очевидна: он включает в результирующий список эле-

мент z ∈ X + Y только один раз и не включает в список никаких элементов, не

принадлежащих X + Y . ▴

Замечание 1. Время работы алгоритма, описанного в предложении 1, оценива-

ется как O((k + n)²ℓ²n) = O(N⁵), где N - длина входа. Мы не обсуждаем здесь

вопросы наиболее эффективного вычисления суммы Минковского, ограничиваясь

лишь достаточно грубой классификацией сложности алгоритмических задач, при-

нятой в теории сложности вычислений (полиномиальное время, логарифмическая

память и т.п.).

Подмножества булева куба (или булевы функции, что по существу то же са-

мое) можно задавать многими другими способами. В теории сложности вычислений

довольно часто рассматривается сжатое представление. В этом представлении ис-

пользуются булевы схемы. Напомним, что булева схема C (в стандартном базисе)

с входными переменными x₁, . . ., x_n - это такая последовательность булевых функ-

ций f₁, f₂, . . . , f_s, что каждый ее член либо является входной переменной, либо по-

лучается присваиванием из предыдущих. Более точно, для каждого 1 ≤ k ≤ s

выполняется одно из следующих условий:

• f_k = x_k для всех 1 ≤ k ≤ n;

• f_k = ¬f_i для i < k;

• f_k = f_i ∨ f_j для i,j < k;

• f_k = f_i ∧ f_j для i,j < k.

Последняя функция f_s называется значением схемы и обозначается через C(x).

Число s - n (количество присваиваний в схеме) называется размером схемы. Если

рассматривать схему как программу вычисления функции, то размер схемы про-

порционален длине программы.

Сжатое представление множества X

- это такая булева схема C_X(x), что

C_X(x) = 1 равносильно x ∈ X. Сжатое представление не единственно и может

быть намного короче как табличного представления, так и представления списком

элементов. Поэтому неудивительно, что алгоритмическая сложность задач в сжатом

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

Вычисление суммы Минковского подмножеств в сжатом представлении оказы-

вается трудной задачей в предположении стандартных гипотез теории сложности

вычислений.

Напомним определения сложностных классов P и NP и их основные свойства

(более подробное изложение можно найти в [5] или [6, часть I]).

Сложностные классы состоят из языков - подмножеств слов в некотором ал-

фавите (далее без ограничения общности считаем, что алфавит двоичный). Язык

формализует понятие вычислительной задачи разрешения свойств.

Класс P образуют те языки, для которых проверка принадлежности слова языку

осуществима за полиномиальное от длины слова время. Допуская вольность речи,

говорят также о принадлежности классу P предикатов от двух и более слов. Фор-

мально это означает принадлежность классу P языка описаний тех пар (троек и т.д.)

слов, для которых предикат истинен.

Если L ∈ P, то для каждого n существует булева схема C_L,n от n переменных,

размер которой полиномиально ограничен по n и которая вычисляет характеристи-

ческую функцию языка L, ограниченную на слова длины n: C_L,n(x) = 1 равносильно

тому, что x ∈ L ∩ {0, 1}ⁿ.

Класс NP образуют те языки L, для которых существуют такие полином q(·) и

предикат от двух переменных R(x, y) из класса P, что x ∈ L равносильно существо-

ванию y, для которого |y| = q(|x|) и верно R(x, y).

Класс NP замкнут относительно полиномиальных сводимостей. Говорят, что

язык L₁ полиномиально сводится к языку L₂ (обозначение L₁ ≤_p L₂), если суще-

ствует такая функция f : {0, 1}^∗ → {0, 1}^∗ на двоичных словах, которая вычислима

за полиномиальное от длины входа время и для всех x выполняется следующее

условие: x ∈ L₁ равносильно f(x) ∈ L₂.

Язык L называется NP-полным, если для любого языка L^′ ∈ NP выполняется

L^′ ≤_p L.

Одной из основных гипотез теории сложности вычислений является утверждение

P = NP. Нетрудно проверить, что P = NP равносильно тому, что для какого-нибудь

NP-полного языка L выполняется L ∈ P.

Теорема 1. Если P = NP, то не существует полиномиального алгоритма

вычисления суммы Минковского для подмножеств в сжатом представлении.

Доказательство. Достаточно доказать, что сумма Минковского двух буле-

вых функций схемной сложности s может иметь сверхполиномиальную по s схемную

сложность.

Рассмотрим какой-нибудь NP-полный язык L. По определению это означает, что

существуют такие полином q(·) и предикат R(x, y) ∈ P, что x ∈ L равносильно

существованию такого y, что |y| = q(|x|) и верно R(x, y).

Поскольку R полиномиально вычислим, то для всех достаточно больших n су-

ществуют такие булевы схемы C_R,n от n + q(n) переменных размера poly(n), что

C_R,n(x, y) = R(x, y) для всех x ∈ Bⁿ, y ∈ Bq(n).

Пусть f_n - булева функция от n + q(n) переменных, задаваемая схемой C_R,n,

а g_n - булева функция от n + q(n) переменных, для которой g(x,y) = 1 тогда и

только тогда, когда x = 0ⁿ. Очевидно, что такую функцию можно представить

схемой размера O(n).

Теперь заметим, что (f_n + g_n)(x, 0q(n)) = 1 тогда и только тогда, когда x ∈ L.

Поэтому по схеме вычисления f_n +g_n размера s легко строится алгоритм для задачи

∈ L, время работы которого poly(n, s). Это означает, что в предполо-

жении NP = P размер s сверхполиномиален по n. ▴

§3. О размере суммы Минковского

Размер суммы Минковского может изменяться в значительных пределах.

Лемма 1 [1]. Справедливы следующие оценки:

max{|X|, |Y |} ≤ |X + Y | ≤ |X| · |Y |.

(2)

Оценки (2) являются прямым следствием переформулировки определения суммы

Минковского

⋃

X + Y = (X + {y_i}), где Y = {y₁,...,y_N},

i=1

и равенства |X + {a}| = |X| для любого a ∈ Bⁿ.

Обе границы в (2) достижимы. Нижняя достигается, если X = Y

- подпро-

странство в Bⁿ, а верхняя - если подпространства X и Y пересекаются только по

вектору 0ⁿ. Заметим также, что для любых подпространств X, Y выполняется со-

отношение

|X| · |Y |

|X + Y | =

|X ∩ Y |

Это соотношение можно обобщить. Пусть V - подпространство в Bⁿ, т.е. под-

группа аддитивной группы Fn2. Смежным классом по подгруппе V называется мно-

жество вида {a} + V = {x : x = a ⊕ v, v ∈ V }. Легко видеть, что смежные классы

не пересекаются или совпадают. Для множества X ⊆ Bⁿ обозначим через t_V (X)

количество смежных классов по подгруппе V , пересекающихся с X.

Лемма 2. Если V - подпространство в Bⁿ, то

|V + X| = t_V (X)|V |.

Доказательство. По определению

⋃

V + X = (V + {x_i}), где X = {x₁,...,x_N},

i=1

т.е. V +X является объединением тех смежных классов V +{a}, в которые попадают

элементы из X. Лемма теперь следует из того, что смежные классы по подгруппе

не пересекаются или совпадают. ▴

Эта лемма является некоторым аналогом теоремы Лагранжа из теории групп.

Пример 3. Если V имеет размерность n - 1 (и потому содержит 2n-1 элемен-

тов), то имеется ровно один смежный класс Y , отличный от V . Получаем V +Y = Y

и |V + Y | = |V | = 2n-1.

Действие аддитивной группы Fn2 сдвигами на себе самой и, тем самым, на Bⁿ

→ X + {a}. Обозначим через

Stab X стабилизатор множества X при таком действии:

Stab X = {a : X = X + {a}}.

Заметим, что |X + StabX| = |X|, так что на паре X, StabX достигается нижняя

оценка в (2). Оказывается, что общий случай достижимости нижней оценки в (2)

сводится к данному с незначительными усложнениями.

Предложение 2. Условие |X + Y | = |X| равносильно Y + Y ⊆ StabX.

Доказательство. Пусть |X + Y | = |X|. Тогда для любых y₁,y₂ ∈ Y должно

выполняться равенство X + {y₁} = X + {y₂}. Поэтому для любого x ∈ X вектор

x⊕y₁⊕y₂ ∈ X (напомним, что мы рассматриваем поле характеристики 2, в котором

x⊕x = 0 и вычитание совпадает со сложением). Это и означает, что Y +Y ⊆ StabX.

В обратную сторону: пусть Y + Y

⊆ Stab X. Тогда из z ∈ X + {y₁} следует

z ∈ X+{y₂}, так как из z⊕y₁ ∈ X следует z⊕y₂ = z⊕y₁⊕(y₁⊕y₂) ∈ X+{y₁⊕y₂} =

= X. Аналогично проверяем включение X + {y₂} ⊆ X + {y₁}. ▴

Лемма 3. Нижняя граница в (2) достигается в точности для тех пар X,Y ,

|Y | ≤ |X|, для которых существуют такие вектор a и подмножество S ⊆ Stab X,

что Y + {a} = S.

Доказательство. В силу предложения 2 достаточно проверить, что Y +Y ⊆

⊆ Stab X равносильно существованию такого вектора a, что Y + {a} ⊆ Stab X.

Если множество A лежит в подпространстве V , то A + A также лежит в V .

Заметим также, что (A + {b}) + (A + {b} = A + A для любых A ⊆ Bⁿ, b ∈ Bⁿ.

Поэтому из Y + {a} ⊆ StabX следует (Y + {a}) + (Y + {a}) = Y + Y ⊆ StabX.

В другую сторону: пусть Y +Y ⊆ Stab X. Если Y ⊆ Stab X, то Y +{0ⁿ} ⊆ Stab X.

В противном случае выберем вектор y₀ ∈ Y \ Stab X. Поскольку y₀ ⊕ y ∈ Stab X для

любого y ∈ Y , то Y + {y₀} ⊆ Stab X. ▴

Отсюда получаем простое описание всех случаев достижимости нижней грани-

цы в (2). Каждая такая пара X, Y , |Y | ≤ |X|, задается (неоднозначно) выбором

подпространства V в Fn2, подмножества X₀ в Fn2/V , подмножества Y₀ ⊆ V и вектора

a∈Fn2.

При таком выборе X состоит из объединения смежных классов по V , входящих

в X₀, а Y = {a} + Y₀. Поскольку V ⊆ StabX, условия леммы 3 выполнены, т.е. на

паре X, Y достигается нижняя оценка в (2).

И обратно, если |X + Y | = |X|, |Y | ≤ |X|, то в обозначениях леммы 3 такая па-

ра представляется подпространством V = StabX, подмножеством X₀ тех смежных

классов по V , которые входят в X (из определения стабилизатора ясно, что каж-

дый смежный класс либо целиком содержится в X, либо не пересекается с ним),

и подмножеством стабилизатора Y₀ = S = Y + {a} для вектора a, существование

которого гарантирует лемма 3.

Это показывает “структурную простоту” вопроса о достижимости нижней оцен-

ки.

Для вопроса о достижимости верхней оценки в (2) ситуация иная.

Приведем достаточное условие достижимости верхней оценки на размер суммы

Минковского.

Определим для произвольного множества X ⊆ Bⁿ метрический спектр X как

множество всех возможных попарных расстояний между различными точками мно-

жества:

R(X) = {r : r = ρ(x^′, x^′′), x^′ = x^′′, x^′ ∈ X, x^′′ ∈ X}.

Мы используем стандартные норму и расстояние Хэмминга на булевом кубе: ∥x∥ -

количество единиц в двоичном слове x, а ρ(x, y) = ∥x ⊕ y∥ - количество координат,

в которых различаются двоичные слова x и y.

Предложение 3. Если R(X) ∩ R(Y ) = ∅, то |X + Y | = |X| · |Y |.

Доказательство. Пусть x^′ ⊕ y^′ = x^′′ ⊕ y^′′ для каких-то различных пар эле-

ментов из X и Y . Тогда x^′ ⊕ x^′′ = y^′′ ⊕ y^′, и метрические спектры множеств X и Y

пересекаются. Таким образом, в условиях предложения все попарные суммы эле-

ментов X и Y различны. ▴

Отметим простое следствие этого утверждения. Обозначим

d(X) = min(r : r ∈ R(X)), D(X) = max(r : r ∈ R(X)).

Следствие 1. Если D(Y ) ≤ d и d(X) ≥ d + 1 для некоторого числа d, то

|X + Y | = |X| · |Y |.

Отсюда видим, что верхняя оценка в (2) достигается для любого кода C ⊆ Bⁿ

с кодовым расстоянием d и хэммингова шара радиуса d - 1 с центром в точке 0ⁿ.

Хэмминговым шаром радиуса r с центром a мы называем множество

B^nr(a) = {x ∈ Bⁿ : ∥x - a∥ ≤ r}.

(3)

Учитывая сложность теории корректирующих кодов, можно заключить из это-

го наблюдения “трудность” задачи описания всех случаев достижимости верхней

оценки в (2).

§ 4. Сложение фигур вⁿ

Геометрические фигуры в Bⁿ имеют большой содержательный и практический

смысл. Такими фигурами являются сферы, шары, грани, линейные многообразия.

4.1. Сложение сфер вⁿ. Сферой радиуса r (r-м слоем булева куба) называем

множество

S^nr = {x ∈ Bⁿ : ∥x∥ = r}.

Другими словами, сфера S^nr - это множество точек Bⁿ, находящихся на расстоянии

(Хэмминга) r от нулевой точки (начала координат).

Перестановки координат задают действие симметрической группы S_n на булевом

кубе Bⁿ: если g ∈ S_n, то

g(x) = g(x₁, x₂, . . . , x_n) = (xg(1), xg(2), . . . , xg(n)).

Это действие естественным образом продолжается на подмножества Bⁿ, как и рас-

смотренное ранее действие Fn2 сдвигами. Если M ⊆ Bⁿ и g ∈ S_n, то

⋃

g(M) =

g(x).

x∈M

Отметим следующие простые свойства действия группы S_n и операций сложения

точек и множеств:

1. g(x ⊕ y) = g(x) ⊕ g(y) для x, y ∈ Bⁿ;

2. g(U + V ) = g(U) + g(V ) для U, V ⊆ Bⁿ.

Сферы являются орбитами этого действия. (Напомним, что орбита действия

группы G на множестве X - это множество вида Ox0 = {x ∈ X : x = g(x₀), g ∈ G}.)

Сумма Минковского двух орбит, очевидно, замкнута относительно этого действия:

если x ∈ S^np + S^nq, то x = u ⊕ v, где u ∈ S^np, v ∈ S^nq. Учитывая указанное выше

свойство, имеем g(x) = g(u) ⊕ g(v) для любой g ∈ S_n. Поэтому g(x) ∈ S^np + S^nq.

Поэтому сумма сфер является объединением некоторых сфер.

Лемма 4 [1]. При p ≤ q справедлива формула

⋃

S^np + S^nq =

Snq-p+2s.

(4)

s=0

Замечание 2. Рассмотрим следующую производящую функцию:

∑

Φ_n,p,q(z) =

z^∥x⊕y∥.

x∈S^np

y∈Sⁿ

Аналогично доказательству леммы 4, данному в [1], можно получить разложение

этой функции

)

) min{p,n-q}∑

⁽n

⁽n - q⁾⁽ q

Φ_n,p,q(z) = z^q-p

z2s.

p-s

s=0

Следствие 2. Справедливы соотношения

S^np + S^nq = S^nn-p + S^nn-q,

S^np + S^nn-q = S^nn-p + S^nq.

Доказательство. Первое соотношение получается из второго заменой q на

n -q. Второе следует из равенств |p- (n -q)| = |(n - p)- q| и min{p,n-(n - q)} =

= min{n - (n - p), q} = min{p, q}. ▴

Пример 4. Выпишем таблицу сложения для сфер малого радиуса:

+ Sn0

Sn1

Sn2

Sn0

Sn1

Sn2

Sn1

Sn0 ∪ Sn2

Sn1 ∪ Sn3

Sn2

Sn1 ∪ Sn3 Sn0 ∪ Sn2 ∪ Sn4

Симметрическая булева функция f удовлетворяет условию f(x) = f(g(x)) для

всех x ∈ Bⁿ и g ∈ S_n. Значение симметрической функции одинаково на всех век-

торах булева куба одинакового веса. Поэтому такая функция однозначно задается

множеством “рабочих чисел” W_f = {w₁, . . . , w_k} ⊆ {0, 1, 2, . . . , n}:

^{1, если ∥x∥ ∈ W_f ,

f (x) =

в противном случае.

С помощью формулы (4) можно найти “рабочие числа” для суммы Минковского

двух симметрических функций f, g с заданными множествами рабочих чисел A, B.

Из свойств сложения Минковского имеем равенство

(⋃

)

(⋃

)

⋃

N_f + N_g =

Sⁿ

(S^na + S^nb).

a∈A

b∈B

a∈A

b∈B

Далее, из формулы (4) получаем

⋃

N_f + N_g =

Sn|a-b|+2s.

(5)

a∈A

s=0

b∈B

Пример 5. Пусть множества рабочих чисел для симметрических булевых

функций f, g от n переменных (n ≥ 9) равны {1, 3, 4} и {4, 5} соответственно. Тогда

Sn1 + Sn3 = Sn2 ∪ Sn4,

Sn3 + Sn3 = Sn0 ∪ Sn2 ∪ Sn4 ∪ Sn6,

Sn1 + Sn5 = Sn4 ∪ Sn6,

Sn3 + Sn5 = Sn2 ∪ Sn4 ∪ Sn6 ∪ Sn8,

Sn4 + Sn3 = Sn1 ∪ Sn3 ∪ Sn5 ∪ Sn7,

Sn4 + Sn5 = Sn1 ∪ Sn3 ∪ Sn5 ∪ Sn7 ∪ Sn9.

Из этих соотношений и формулы (5) получаем

⋃

Nf+g = Sn0 ∪ Sn1 ∪ Sn2 ∪ Sn3 ∪ Sn4 ∪ Sn5 ∪ Sn6 ∪ Sn7 ∪ Sn8 ∪ Sn9 = Sⁿⁱ.

i=0

4.2. Сумма шаров вⁿ. Под шаром радиуса r с центром a понимаем, как и выше,

множество, задаваемое формулой (3). Отметим, что по определению B^nr(a) = Bⁿ,

если r ≥ n.

Лемма 5 [1]. Имеет место соотношение

B^np(a) + B^nq(b) = Bnp+q(a ⊕ b).

(6)

Частным случаем этой формулы является следующее утверждение: каждый шар

является сдвигом шара с центром в 0ⁿ. Действительно, Bn0(a) = {a} для a ∈ Bⁿ, и из

формулы (6) получаем B^nr(a) = B^nr(0ⁿ) + {a}.

Обобщение определения шара приводит к понятию r-окрестности множества

A ⊆ Bⁿ (“обобщенного шара”):

⋃

B^nr(A) =

B^nr(a).

a∈A

Для окрестностей множеств справедливо соотношение, аналогичное (6).

Лемма 6 [1]. Имеет место соотношение

B^np(A) + B^nq(B) = Bnp+q(A + B).

Следствие 3. Справедливы формулы

B^np(B^nq(A)) = Bnp+q(A),

B^np(A) = A + B^np(0ⁿ),

B^np(A + B) = B^np(A) + B = A + B^np(B),

B^np(A) + B^np(B) = A + B + Bn2p(0ⁿ).

4.3. Суммы граней вⁿ. Грань (подкуб, интервал) в Bⁿ - это множество точек,

удовлетворяющих условию

J = {x ∈ Bⁿ : a ≤ x ≤ b}.

Здесь ≤ - обычное покоординатное отношение частичного порядка на булевом кубе:

def

x = (x₁,...,x_n) ≤ y = (y₁,...,y_n)

⇐⇒ x_i ≤ y_i для всех 1 ≤ i ≤ n.

По-другому интервал J может быть задан словом λ(J) длины n над алфавитом

A = {0,1,∗}, которое мы будем называть кодом интервала, по следующему правилу:

x ∈ J, если x согласовано с λ(J), т.е. x_i = λ(J)_i для всех i, для которых λ(J)_i = ∗.

Другими словами, если λ(J) = (λ₁λ₂ . . . λ_n) - код интервала J, то точки интервала

получаются всеми возможными заменами символа ∗ на нули или единицы.

Соответствие между этими двумя представлениями устанавливается очень про-

стым способом. Код λ(J) = λ₁λ₂ . . . λ_n непустого интервала

J = {α₁α2 ...α_n ≤ x ≤ β₁β2 ...β_n}

вычисляется по формуле

^{α_i, если α_i = β_i,

λ_i =

∗,

если α_i < β_i.

Пример 6.

1. Если J = {0100 ≤ x ≤ 0111}, то λ(J) = (01 ∗ ∗);

2. Если J = Bⁿ = {00 . . .0 ≤ x ≤ 11 . . .1}, то λ(Bⁿ) = ∗ ∗ . . . ∗.

Количество символов ∗ в коде интервала J - это размерность dimJ интервала.

Количество точек в интервале равно 2dimJ.

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

сумма Минковского двух интервалов.

Введем на множестве A = {0, 1, ∗} операцию ⊛, продолжающую сумму по моду-

лю 2 на множестве {0, 1}:

⊛ 0 1 ∗

∗

К словам в алфавите A операцию ⊛ будем применять покомпонентно.

Лемма 7 [7]. Если J₁,J₂ - интервалы, то J₁+J₂ также является интервалом

и λ(J₁ + J₂) = λ(J₁) ⊛ λ(J₂).

Пример 7.

1. Пусть λ(J₁) = (01∗), λ₂(J₂) = (100). Тогда λ(J₁ + J₂) = (11∗). Поскольку ин-

тервал J₂ состоит из одного вектора, сумма равна сдвигу интервала J₁ на этот

вектор;

2. Пусть λ(J) = (1 ∗ ∗). Тогда λ(J + J) = (0 ∗ ∗), т.е. J + J = J;

3. Однако для любого интервала J выполняется равенство J +J +J = J. Как видно

из таблицы операции ⊛, в коде суммы J + J звездочки стоят на тех же местах,

что и в коде J, а на остальных местах стоят нули. Добавляя к такому интервалу

интервал J еще раз, получаем интервал J;

4. Найдем сумму шара и грани. С точностью до сдвигов достаточно рассмотреть

случай B^nr(0ⁿ) + Γ, где λ(Γ) = (∗ ∗6.7. . 8500...0).

k штук

Ясно, что в этом случае x = (α₁ . . .α_kβ₁ . . . β_n-k) ∈ B^nr(0ⁿ) + Γ, если и только

если ∥β₁ . . . β_n-k∥ ≤ r. Поэтому

(

⁽n - k⁾

⁽n - k⁾⁾

|B^nr(0ⁿ) + Γ| = 2^k

+...+

= 2^k|Bnr (0ⁿ)|.

Из того, что интервалы замкнуты относительно суммы Минковского, следует

продолжение начатого в § 2 анализа сложения Минковского для множеств, задан-

ных сжатым представлением. Если вместо общих булевых схем использовать для

представления множеств только схемы частного вида, а именно дизъюнктивные нор-

мальные формы (ДНФ), то вычисление суммы Минковского двух функций в таком

представлении уже возможно за полиномиальное от длины входа время.

Напомним, что литералом называется переменная или ее отрицание. При запи-

си литералов часто используется показательная запись: x¹ = x, x⁰ = ¬x. Конъюнк-

том называется конъюнкция литералов, среди которых нет одинаковых. ДНФ - это

дизъюнкция конъюнктов, среди которых нет одинаковых.

Интервалы являются множествами единиц конъюнктов. По коду интервала легко

выписывается соответствующий конъюнкт в показательной записи:

⋀

J = N_f, где f =

xλ(J)ii .

i: λ(J)i=∗

Сумма Минковского двух ДНФ

⋁

D₁ = C^′i и D₂ = C^′′i

i=1

в силу дистрибутивности по объединению равна

⋁

(C^′i + C^′′j).

i=1 j=1

В этой дизъюнкции не более чем квадратичное количество членов. Удаляя повто-

рения литералов применением тождества ℓ ∧ ℓ = ℓ и затем повторения конъюнктов

применением тождества C ∨ C = C, получаем эквивалентную ДНФ, размер кото-

рой не более чем квадратичен относительно размеров ДНФ-слагаемых. Такая ДНФ

легко строится полиномиальным алгоритмом (и даже алгоритмом, работающим на

логарифмической памяти).

Заметим также, что из леммы 7 следует, что количество литералов в сумме Мин-

ковского двух конъюнктов не превосходит количества литералов в каждом из них.

4.4. Сумма подпространствⁿ. Сложение Минковского подпространств Bⁿ сов-

падает с обычным определением суммы подпространств, используемым в линейной

алгебре. Если U, V - подпространства Bⁿ, то U +V - тоже подпространство, причем

для размерностей этих подпространств выполняется известное соотношение

dim(U + V ) = dim U + dim V - dim(U ∩ V ),

откуда следует формула для размера суммы

|U| · |V |

|U + V | =

|U ∩ V |

Таким образом, теория “сложения подпространств” является хорошо развитым

разделом линейной алгебры и позволяет давать ответы на многие вопросы, имеющие

отношение к данной проблематике.

§5. Алгебраические свойства сложения Минковского

В этом параграфе мы рассмотрим несколько вопросов, относящихся к алгебраи-

ческим свойствам моноида Минковского.

5.1. Обратимые и идемпотентные элементы. Как нетрудно увидеть из определе-

ния, нейтральным элементом относительно сложения Минковского является одно-

элементое множество {0ⁿ}, будем обозначать его через

A+

= A для всех A ⊆ Bⁿ.

Есть два поглощающих элемента: пустое множество ∅ и весь куб Bⁿ:

A + ∅ = ∅, A + Bⁿ = Bⁿ для всех A ⊆ Bⁿ.

Других поглощающих множеств, как нетрудно проверить, нет. Действительно, если

X = ∅ (скажем, x ∈ X) и y ∈ X, то {x⊕y}+X = X, так как {x⊕y}+X содержит y.

Опишем обратимые элементы M_n. Это в точности одноэлементые множества.

Предложение 4. Элемент A ∈ M_n обратим тогда и только тогда, когда

A = {a}, a ∈ Bⁿ.

Доказательство. Обратимость множеств {a} следует из равенства a⊕a = 0ⁿ

(заметим также, что каждое такое множество совпадает со своим обратным).

Пусть A ∈ M_n обратим, т.е. A + B = для некоторого множества B. Это

означает, что a ⊕ b = 0ⁿ для всех a ∈ A, b ∈ B, т.е. a = b для всех a ∈ A, b ∈ B. Это

и означает, что A состоит из одного элемента и B = A. ▴

Идемпотентный элемент x в моноиде удовлетворяет равенству x + x = x (мы

используем аддитивную запись операции в моноиде). Опишем все идемпотентные

элементы моноида Минковского.

Предложение 5. Если A - идемпотентный элемент моноида Минковского,

то A - либо пустое множество, либо подпространство пространства Bⁿ.

Доказательство. Если для непустого A выполняется равенство A + A = A,

то 0ⁿ ∈ A, так как a⊕a = 0ⁿ для любого a ∈ Bⁿ. Осталось заметить, что для любых

a^′, a^′′ ∈ A сумма a^′ ⊕ a^′′ принадлежит A + A = A. ▴

5.2. Подмоноиды, порожденные одним элементом. Подмоноидом называется под-

множество элементов моноида, которое образует моноид относительно той же опера-

ции. Подмоноидом, порожденным множеством S, называется наименьший по вклю-

чению подмоноид, содержащий S. Нетрудно видеть, что если S состоит из одного

элемента a, то порожденный этим элементом подмоноид содержит нейтральный эле-

мент и все кратные элемента a: a, 2a = a + a, 3a = a + a + a, . . . (Мы используем

знак суммы для обозначения операции в моноиде, поэтому говорим о кратных.)

Последовательность кратных элемента любого конечного моноида является пе-

риодической: как только в этой последовательности элементы повторились, т.е.

kx = ℓx, ℓ - k = p > 0, все остальные кратные периодически повторяются с перио-

дом p: tx = (k + r)x, где r - остаток от деления t на p. Число k - 1 назовем длиной

предпериода (уточним, что мы выбирали первое повторение в последовательности).

Если k = 1, будем говорить, что последовательность чисто периодическая.

Пример 8.

1. Пусть A = {a, b}. Тогда 2A = {0ⁿ, a ⊕ b}, 3A = {a, b} = A. Последовательность

кратных чисто периодическая с периодом 2;

2. Пусть A = {a, b, c}. Тогда 2A = {0ⁿ, a ⊕ b, b ⊕ c, a ⊕ c}, 3A = {a, b, c, a ⊕ b ⊕ c},

4A = {0ⁿ, a ⊕ b, b ⊕ c, a ⊕ c} = 2A. Период 2, длина предпериода 1;

3. Если в предыдущем примере a ⊕ b ⊕ c = 0ⁿ, то уже 3A = {0ⁿ, a, b, c} = 2A.

Приведенные примеры по сути исчерпывают все разнообразие периодов.

Введем обозначение, удобное для дальнейшего анализа. Через G_k(A) обозначим

суммы k попарно различных элементов из множества A. В частности, G₁(A) = A.

Для удобства дальнейших вычислений полагаем также G₀(A) = {0ⁿ} и G_k(A) = ∅,

если k < 0 или k > |A|.

Если занумеровать все элементы A, т.е. A = {a₁, a₂, . . . , a_N }, где N = |A|, то

множества G_k(·) задаются формулой

⋃

G_k(A) =

(ai1 ⊕ ai2 ⊕ . . . ⊕ aik ).

1≤i1<i2<...<ik≤N

Заметим, что для множеств G_k(·) выполняется свойство монотонности: если

A ⊆ B, то G_k(A) ⊆ G_k(B).

Предложение 6. При 0 ≤ p ≤ N имеют место равенства

G_p(A) + A = Gp-1(A) ∪ Gp+1(A).

(7)

Доказательство. Действительно, если добавлять к суммам p различных эле-

ментов A элементы A, то будут получаться суммы p - 1 и суммы p + 1 различных

элементов. (Напомним, что a ⊕ a = 0ⁿ для всех a ∈ Bⁿ.) В граничных случаях p = 0

и p = N равенство выполняется в силу принятых выше соглашений. ▴

Из дистрибутивности сложения Минковского по объединению, равенств (7) и на-

чального условия A = G₁(A) легко проверить индукцией по количеству слагаемых,

что каждое кратное множества A является объединением каких-то множеств ви-

да G_k(A), 0 ≤ k ≤ N. Будем нумеровать такие объединения булевыми векторами

длины N + 1: вектор (γ₀, γ₁, . . . , γ_N ) соответствует множеству

⋃

G_i(A).

i: γi=1

Пусть g(k) - вектор, соответствующий kA. Тогда равенства (7) задают для этих

векторов рекуррентные соотношения

g(k + 1)_p = g(k)p-1 ∨ g(k)p+1

(дизъюнкция берется почленно).

Вычислив несколько первых членов этой рекурренты, легко увидеть правило, по

которому они строятся:

g(1) = (0, 1, 0, 0, 0, 0, 0, . . .),

g(2) = (1, 0, 1, 0, 0, 0, 0, . . .),

g(3) = (0, 1, 0, 1, 0, 0, 0, . . .),

g(4) = (1, 0, 1, 0, 1, 0, 0, . . .),

g(5) = (0, 1, 0, 1, 0, 1, 0, . . .),

g(6) = (1, 0, 1, 0, 1, 0, 1, . . .).

Как видно из этих равенств (и легко доказывается индукцией по p), в слове g(p),

p ≤ |A|, самая правая единица стоит на позиции с номером p (обратите внимание,

что нумерация позиций начинается с 0), а на предыдущих позициях нули и единицы

чередуются.

Пример 9. Рассмотрим еще один пример, обобщающий предыдущие. Пусть

A = {a₁,...,a_d} и все a_i линейно независимы.

Тогда все множества G_k(A) различны при 0 ≤ k ≤ d и

)

⁽d

|G_k(A)| =

Поэтому все кратные вплоть до dA будут различными, а кратное (d+1)A будет равно

(d - 1)A. Далее последовательность (d - 1)A, dA будет периодически повторяться в

последовательности кратных.

Легко также описать множества, лежащие в этом периоде. Обозначим через

F₂〈a₁, . . ., a_d〉 пространство, натянутое на векторы a₁, . . . , a_d, а через E₀ - подпро-

странство векторов четного веса в базисе a₁, . . . , a_d, т.е.

⋃

E₀ = G2i(A).

i=0

Это пространство коразмерности 1, поэтому в нем содержится ровно половина точек

из F₂〈a₁, . . . , a_d〉. Остальные точки образуют линейное многообразие E₁ = E₀ +{a₁}.

Другими словами,

⋃

E₁ = G2i+1(A).

i=0

В периоде кратных A будут как раз E₀ и E₁. Действительно, если d нечетно, то

(d - 1)A = E₀, тогда dA = E₁. Если d четно, то порядок обратный: (d - 1)A = E₁ и

dA = E₀.

Для анализа общей ситуации нам потребуется связать с подмножеством A ⊆ Bⁿ

из N элементов подпространство координатного пространства FN2 (или линейный

код). Пусть A = {a₁, . . . , a_N } - список элементов множества A без повторений. Опре-

делим

{

}

⊕

C(A) = u ∈ FN2 :

u_ia_i

=0ⁿ

i=1

По сути, C(A) состоит из тех линейных комбинаций элементов множества A, ко-

торые равны 0ⁿ. (Напомним, что мы рассматриваем векторные пространства над

полем F₂, поэтому коэффициенты линейных комбинаций равны 0 или 1.)

Заметим, что любой линейный код представляется в виде C(A) для некоторо-

го множества A: достаточно взять проверочную матрицу кода, множество A будет

состоять из ее столбцов.

Через C^⊥(A) обозначим ортогональное дополнение к C(A):

{

}

⊕

C^⊥(A) = v ∈ FN2 :

v_iu_i = 0 для всех u ∈ C(A)

i=1

Определение. Назовем подмножество A ⊆ Bⁿ четным, если

∈ C^⊥(A).

Здесь обозначает вектор из одних единиц. В противном случае будем называть

множество A нечетным.

Например, любой базис B в Bⁿ является четным множеством, так как C(B) =

= {0^N}, а C(B)^⊥ = FN2 . (В данном случае N = n.)

Замечание 3. Конструкция C(A) зависит от упорядочения элементов множест-

ва A. Однако коды, отвечающие разным упорядочениям, эквивалентны: они пере-

водятся друг в друга перестановками координат. Так что свойства кода C(A), инва-

риантные относительно перестановок координат, зависят только от множества A и

не зависят от выбранного на A упорядочения.

В частности, определение четности множества как раз является примером та-

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

построения кода C(A).

Как уже говорилось, векторы кода C(A) задают линейные комбинации элементов

множества A, равные нулю. Далее нам будет удобно использовать характеризацию

четных и нечетных множеств в этих терминах.

⊕

Лемма 8. Подмножество A ⊆ Bⁿ четное, если и только если из

a=0ⁿ

следует, что |S| четное.

a∈S⊆A

Доказательство. Сопоставим каждому подмножеству S ⊆ A его характери-

стический вектор:

^{1, если a_i ∈ S,

u^Si =

в противном случае

(предполагаем, что множество задано упорядоченным списком без повторений A =⊕

= {a₁, . . . , a_N}). Условие

a_i = 0ⁿ равносильно тому, что u^S ∈ C(A). При этом

i∈S

количество единиц в характеристическом векторе u^S равно количеству элементов

в множестве S.

⊕

Равенство

iui = 0 равносильно тому, что в векторе u ∈ F² четное количество

единиц.

i=1

Если множество A четное, то в любом u ∈ C(A) четное количество единиц. Зна-⊕

чит, равенство

a = 0ⁿ возможно лишь при четном |S|.

a∈S⊆A

И наоборот, если множество A нечетное, то существует такой вектор u = u^S ∈

⊕

∈ C(A), что

iuⁱ = 1. Тогда в S нечетное количество элементов, но

a_i = 0ⁿ. ▴

i=1

i∈S

Обозначим через L(A) линейную оболочку множества A, a через d - размер-

ность L(A). В множестве A заведомо содержится хотя бы один базис линейной

оболочки. Для четных и нечетных множеств разложения элементов A по базисам

линейной оболочки, состоящим из элементов A, устроены по-разному.

Предложение 7. Пусть A нечетное. Тогда существуют базис B ⊆ A ли-

нейной оболочки L(A) и элемент a_B ∈ A, такие что разложение a_B по базису B

является суммой четного количества элементов базиса.

Доказательство. Выбе⊕ем наименьшее по включению множество S нечет-

ного размера, для которого

a = 0ⁿ (такие множества существуют, так как A

нечетное).

a∈S⊆A

⊕

Тогда для любого S^′ ⊂ S выполняется неравенство

a = 0ⁿ, так как в про-

a∈S^′⊆A

тивном случае одно из множеств S^′ или S \ S^′ будет собственным подмножеством S

нечетного размера, суммирование по которому дает 0ⁿ.

Значит, если выбрать какой-элемент a_B ∈ S, то остальные элементы из S (обозна-

чим их b₁, . . . , b_k) линейно независимы. Продолжим их до базиса L(A) элементами

bk+1, . . .b_d ∈ A: B = {b₁, . . ., b_k, bk+1, . . . , b_d}. Разложение a_B по этому базису состоит

из четного числа элементов, так как k = |S| - 1 четно. ▴

Заметим, что если A = {a₁, . . ., a_N } и a₁ = 0ⁿ, то построение в доказательстве

дает множество S = {a₁} (1 - наименьшее положительное нечетное число, а список

элементов множества не содержит повторений). Поэтому a_B = a₁ = 0ⁿ (других

элементов в S нет). Базисом B при этом можно выбрать произвольный базис L(A),

состоящий из элементов A.

Второе замечание: из леммы 8 следует, что для четных множеств не существует

базиса L(A), состоящего из элементов A и такого, что какой-то элемент A разлага-

ется в сумму четного числа базисных элементов.

Выбранный в предложении 7 базис важен для анализа кратных в силу следую-

щего утверждения.

Предложение 8. Если A нечетное, то (d + 1)A = L(A), где d = dimL(A).

Доказательство. По предложению 7 существует базис B ⊂ A линейной обо-

лочки множества A, по которому некоторый элемент a_B ∈ A разлагается в сумму

четного количества базисных векторов. Для a_B и вектора x ∈ G_k(A) рассмотрим

разложения по базису B

⊕

a_B = b, S ⊆ B,

|S| ≡ 0 (mod 2),

b∈S

⊕

x = b, X ⊆ B.

(8)

b∈X

Для x есть другое разложение в сумму элементов множества A:

⊕

x=a_B ⊕

(9)

b∈X⊕S

Здесь через X ⊕ S обозначена симметрическая разность множеств, т.е. X ⊕ S =

=X\S∪S\X.

Четность количества слагаемых в этих двух разложениях разная. Действительно,

поскольку в S четное количество элементов, то |S \ X| и |X ∩ S| имеют одинаковую

четность. Поэтому

|X ⊕ S| = |X \ S| + |S \ X| ≡ |X \ S| + |X ∩ S| = |X| (mod 2),

а в разложении (9) есть еще один вектор a_B помимо тех |X ⊕S|, которые стоят под

знаком суммы.

Таким образом, для x есть два разложения, четность количества слагаемых в ко-

торых различна. Количество слагаемых в (8) не превосходит d, а в (9) не превосхо-

дит d + 1. Поэтому x ∈ G_j (A), где j имеет отличную от k четность и j ≤ d + 1.

Отсюда получаем включения

⋃

G_k(A) ⊆

G_j(A).

(10)

j≤d+1

j+k≡1 (mod 2)

Поэтому для четного d из (10), монотонности кратных и вычислений в примере 9

получаем

(d + 1)A ⊇ dA ⊇ dB = E₀,

(11)

(d + 1)A ⊇ (d + 1)B = (d - 1)B = E₁,

т.е. (d + 1)A ⊇ E₀ ∪ E₁ = L(A). (Здесь использованы те же обозначения, что и

в примере 9.)

Для нечетного d рассуждение аналогично: в первой строке (11) будет включе-

ние E₁ в (d + 1)A, а во второй - E₀. ▴

Теперь дадим общее описание множества кратных.

Теорема 2. Если A - нечетное множество, то период последовательности

кратных A равен 1, элемент в периоде - линейная оболочка A, а длина предпериода

не больше d = dimL(A).

Если A - четное множество, то период последовательности кратных A ра-

вен 2, элементы в периоде - подпространство коразмерности 1 в L(A) и его сдвиг,

а длина предпериода не больше max(0, d - 2).

Доказательство. Так как A ⊆ L(A), то L(A) + A = L(A), и первая часть

теоремы прямо следует из предложений 7 и 8.

Далее считаем, что A - четное множество и B ⊆ A - базис в L(A).

Пусть d = dim L(A) четное. Тогда (d-1)A ⊇ (d-1)B = (d+1)B = E₁ (используем

те же обозначения, что и в примере 9).

Предположим, что x ∈ (d - 1)A \ E₁. Это означает, что x ∈ E₀, т.е. x раскладыва-

ется в сумму четного числа базисных векторов. С другой стороны, x ∈ (d-1)A и по-

этому раскладывается в сумму нечетного числа попарно различных векторов из A.

Из этих двух выражений для x получаем сумму нечетного числа векторов из A, рав-

ную 0ⁿ. Это противоречит определению четного множества. Значит, (d - 1)A = E₁.

Теперь заметим, что dA ⊇ dB = E₀. Если x ∈ dA \ E₀, то рассуждением, анало-

гичным предыдущему, опять приходим к противоречию с четностью множества A,

поскольку для такого x есть разложение в сумму как нечетного количества базис-

ных векторов (x ∈ E₁ = L(A)\E₀), так и четного (x ∈ dA и поэтому раскладывается

в сумму четного числа попарно различных векторов из A). Значит, dA = E₀.

Поэтому дальнейшая последовательность кратных повторяется с периодом 2.

Длина предпериода не больше d - 2 при d ≥ 2. Если d = 1, то A - одноэлемен-

тое множество, в этом случае длина предпериода равна 0.

Анализ в случае нечетного d = dim A аналогичен. В этом случае (d - 1)A = E₀,

а dA = E₁. ▴

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

лека от точной. Скажем, для любого подпространства V последовательность крат-

ных чисто периодическая с периодом 1.

Обсудим вычислительную сложность определения периода и предпериода после-

довательности кратных множества A.

Проверка множества на четность возможна за полиномиальное время даже в том

случае, если множество задано списком элементов, а не полной таблицей значений

характеристической функции. Достаточно применить алгоритм Гаусса и найти базис

в пространстве C(A), после чего проверить, что каждый базисный вектор содержит

четное количество единиц.

Дело обстоит иначе с вычислением предпериода последовательности кратных

множества A.

Так как длина предпериода не превосходит n + 1 для любого множества A ⊆ Bⁿ,

то если множество A задано таблицей значений характеристической функции, то

вычисление всей последовательности кратных вплоть до периода занимает время,

полиномиальное от размера этой таблицы (длины входа).

Если же множество задано списком элементов, то задача определения длины

предпериода оказывается NP-трудной, поскольку она связана с оценкой радиуса по-

крытия кода C(A). Радиус покрытия кода - это минимально возможное s, такое что

на расстоянии (Хэмминга) s от любой точки есть точка из кода. Применив это опре-

деление к коду C(A), получаем, что радиус покрытия s равен минимуму по таким t,

что суммами ≤ t элементов A можно представить любой вектор пространства L(A).

Из теоремы 2 следует, что длина предпериода разве что на 1 отличается от радиуса

покрытия кода C(A).

В работе [8] показано, что даже приближенное вычисление радиуса покрытия

кода является NP-трудной задачей. Более точно, в этой работе доказана NP-труд-

ность семейства алгоритмических задач GapCRPcodes_c с априорной информацией

(promise problem). Здесь c > 0 - произвольное положительное число (точность при-

ближения). Входом задачи GapCRPcodes_c является матрица H над полем F₂ (прове-

рочная матрица кода) и число d. Задача состоит в том, чтобы различить два случая:

(i) радиус покрытия кода C_H = {x : Hx = 0} не превосходит d и (ii) радиус покрытия

кода C_H больше cd. Результатом работы алгоритма должен быть ответ “да” в первом

случае и “нет” во втором. На остальных входах результат работы алгоритма может

быть произвольным.

NP-трудность задачи GapCRPcodes_c означает, что если для нее существует алго-

ритм решения за полиномиальное время, то P = NP. Отсюда сразу следует NP-труд-

ность определения длины предпериода последовательности кратных множества A,

если оно задано списком своих элементов: как сказано выше, эта длина отличает-

ся от радиуса покрытия кода C(A) не более чем на 1, и любой код может быть

представлен в виде C(A), если взять в качестве множества A столбцы проверочной

матрицы кода.

5.3. Множества порождающих. Из теоремы 2 следует оценка мощности подмо-

ноида Минковского, порожденного несколькими элементами (т.е. подмножествами

булева куба).

Следствие 4. Рассмотрим подмоноид M = 〈A₁,...,A_s〉, порожденный мно-

жествами A₁, . . ., A_s. Тогда

∏

|M| ≤ (dim L(A_i) + 2),

i=1

где L(A) обозначает линейную оболочку элементов множества A ⊆ Fn2.

Доказательство. Любой элемент из моноида M имеет вид

k₁A₁ + k₂A₂ + . . . + k_sA_s, k_i ≥ 0.

Из теоремы 2 следует, что у множества A ⊆ Bⁿ всего имеется не более dimL(A) + 2

различных кратных (включая кратное с множителем 0). ▴

Отсюда получаем оценку на размер семейства G множеств, порождающих весь

моноид Минковского:

(n + 2)^|G| ≥ 22n ,

т.е. |G| = 2n(1-o(1)).

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

функций, то подмоноиды, порожденные некоторым набором подмножеств (функ-

ций), задают класс функций, выражаемых через порождающие очень простым об-

разом (как сумма кратных). Сама операция, впрочем, достаточно сложна. Тем не

менее представляется интересным вопросом описание классов функций, порождае-

мых как суммы Минковского некоторого выбранного набора “базисных” функций.

Теперь приведем аргументы против существования “простого” набора порожда-

ющих у моноида Минковского. Более точно, мы докажем значительное усиление

оценки количества элементов в порождающем семействе множеств (см. следствие 5

ниже). Оказывается, в любом таком семействе содержится дважды экспоненциаль-

ное количество множеств. Из обычных мощностных соображений отсюда следует,

например, что в таком множестве обязаны присутствовать множества, соответству-

ющие функциям экспоненциальной схемной сложности.

Примитивные элементы моноида Минковского - такие A, что A необратим в мо-

ноиде, а из разложения A = X + Y следует, что X или Y обратим в моноиде.

Разложения в сумму Минковского вида A = B + X, где X обратим в моноиде,

будем называть тривиальными. По предложению 4 все тривиальные разложения

имеют вид A = B+{c}, c ∈ Bⁿ (так как обратимыми являются только одноэлементые

множества).

В силу равенства X + Y = (X + {a})+ (Y + {a}) далее предполагаем без ограни-

чения общности, что для слагаемых разложения A = X + Y выполняются свойства

0ⁿ ∈ X, Y ⊆ A.

Пусть f : B^k → B^s - некоторое отображение k-мерного булева куба в s-мерный.

График этого отображения

Γ_f = {(x, y) ∈ Bk+s : y = f(x)}

является подмножеством Bk+s. Сформулируем достаточное условие примитивности

графика Γ_f как элемента моноида Mk+s.

Предложение 9. Пусть для любого двумерного аффинного подпространства

{a, a + b, a + c, a + b + c} ⊆ Fk2 выполняется неравенство

f (a) ⊕ f(a + b) ⊕ f(a + c) ⊕ f(a + b + c) = 0^s.

Тогда множество Γ_f примитивно.

Доказательство. Если Γ_f = X + Y - нетривиальное разложение графика

отображения f, то |X| > 1, |Y | > 1. Считаем, как сказано выше, что Y ⊆ Γf и

0k+s ∈ X. Выберем два элемента из Y , обозначим их (x₁, f₁) и (x₂, f₂), и какой-то

ненулевой элемент из X, обозначим его (Δ_x, Δ_y).

Тогда (x₁ ⊕ Δ_x, f₁ ⊕ Δ_y) ∈ Γ_f и (x₂ ⊕ Δ_x, f₂ ⊕ Δ_y) ∈ Γ_f , т.е. для двумерного

подпространства

{x₁, x₁ ⊕ (x₁ ⊕ x₂), x₁ ⊕ Δ_x, x₁ ⊕ (x₁ ⊕ x₂) ⊕ Δ_x}

в Fk2 получаем

f (x₁) = f₁,

f (x₁ ⊕ (x₁ ⊕ x₂)) = f₂,

f (x₁ ⊕ Δ_x) = f₁ ⊕ Δ_y,

f (x₁ ⊕ (x₁ ⊕ x₂) ⊕ Δ_x) = f₂ ⊕ Δ_y.

Сумма значений f по этому подпространству равна 0^s, что противоречит условию

предложения. ▴

Это достаточное условие позволяет доказать дважды экспоненциальную ниж-

нюю оценку на количество примитивных элементов в моноиде Минковского.

Теорема 3. Количество примитивных элементов в моноиде Минковского M_n

не меньше 22Ω(n) .

Доказательство. Двумерное аффинное подпространство в B^k задается тре-

мя векторами, так что общее количество таких подпространств не превосходит 23k.

Функция f : B^k → B^s задается s2^k булевыми переменными: ϕ(i, x) = 1 равно-

сильно тому, что f(x)_i = 1. В пространстве Fs2k2 , координатами которого являются

эти переменные, условие равенства нулю суммы значений функции f : B^k → B^s

на некотором двумерном аффинном подпространстве задает систему из s линейно

независимых однородных линейных уравнений. Решения такой системы составляют

долю 2^-s от общего количества функций B^k → B^s.

Поэтому доля функций f : B^k → B^s, удовлетворяющих достаточному условию

примитивности из предложения 9, не меньше 1-23k-s (оценка объединения). Значит,

при 3k < s хотя бы половина функций удовлетворяет этому условию и количество

примитивных элементов в Mk+s не меньше 2s2k-¹. Выберем s = 3k + 1, тогда n =

= k + s = 4k + 1, и в моноиде Минковского M_n не менее чем

2(3k+1)2k-¹ = 22Ω(n)

примитивных элементов. ▴

Следствие 5. Пусть семейство G множеств порождает моноид Минковско-

го. Тогда |G| = 22Ω(n) .

Доказательство. Пусть A - примитивный элемент моноида Минковского.

В любой системе порождающих моноида Минковского должен содержаться ассоци-

ированный c A элемент моноида, т.е. такое множество B, что A = B + X, где X

обратим в моноиде.

Отношение ассоциированности - это отношение эквивалентности, классы экви-

валентности этого отношения называются классами ассоциированных элементов.

В моноиде Минковского обратимыми элементами, как проверено выше (предло-

жение 4), являются одноэлементые множества и только они. Поэтому размер класса

ассоциированных элементов в моноиде Минковского равен 2ⁿ.

Таким образом, в любую систему порождающих должен входить хотя бы один

элемент из каждого класса ассоциированных элементов. Поэтому из теоремы 3 по-

лучаем искомую оценку на размер семейства G. ▴

§ 6. Дубли Минковского

Простейшим уравнением в моноиде Минковского является уравнение вида

X + Y = A.

(12)

Его решения задают возможные факторизации A как элемента моноида Минков-

ского.

У уравнения (12) всегда есть тривиальные решения: X = {x}, Y

= A + {x}.

Напомним, что одноэлементые множества обратимы в моноиде Минковского. Эти

тривиальные решения отвечают как раз таким тривиальным факторизациям A.

Если A таково, что других решений у уравнения (12) нет, то A - примитивный

элемент моноида Минковского (см. п. 5.3).

Пример 10.

1. Если A = Bⁿ, то в качестве X можно взять Bⁿ, а в качестве Y любое подмноже-

ство Bⁿ;

2. Если A - подпространство Bⁿ, то A+A = A, и таким образом, одним из решений

уравнения (12) является X = Y = A.

Родственное уравнение

X+X =A

(13)

уже не всегда имеет решение. Те множества, для которых (13) имеет решение, будем

называть дублями Минковского.

Пример 11. Если A - подпространство Bⁿ, то A+A = A, и поэтому A является

дублем Минковского.

Уравнение (13) представляет интерес по нескольким причинам.

В метрических задачах на булевом кубе оно возникает при характеризации вза-

имных расстояний между точками множества. Приведем краткое изложение этой

связи (подробнее см. в [2]).

Напомним, что мы используем на булевом кубе норму Хэмминга ∥x∥ (количество

единиц в x) и расстояние Хэмминга ρ(x, y) = ∥x⊕y∥ (количество позиций, в которых

различаются слова x и y).

Определим норму множества как

∥A∥ = min{∥x∥ : x ∈ A}.

Тогда ∥A + B∥ совпадает с расстоянием Хаусдорфа между множествами:

ρ(A, B) = minρ(x, y) = min∥x ⊕ y∥ = min

∥z∥ = ∥A + B∥.

x∈A

z∈A+B

y∈B

Множество

R(A, B) = {ρ(a, b) : a ∈ A, b ∈ B}

характеризует “взаимный” спектр расстояний между точками множеств A и B. На-

помним, что R(A, A) = R(A) называется метрическим спектром множества A. Таким

образом, множество A + A однозначно определяет метрический спектр.

Пример 12. Если X + X = A ∪ {0ⁿ} и A ⊆ S^nm, то X - эквидистантный код

с расстоянием m между любыми двумя различными точками.

Таким образом, задачи построения эквидистантных кодов и разрешимости урав-

нения (13) оказываются связанными.

Понятие дубля Минковского тесно связано с изучением эквивалентности адди-

тивных каналов [3], где описание класса эквивалентности связано с нахождением

всех решений уравнения (13). В частности, при описании эквивалентности аддитив-

ных каналов оказывается важным следующее простое наблюдение.

Пусть GL₂(n) - группа обратимых матриц порядка n с элементами из поля F₂.

Эта группа действует на векторах координатного пространства Fn2, и это действие

естественно переносится на подмножества Fn2:

gA = {x : x = ga, a ∈ A}.

Обозначим через G_A стабилизатор этого действия.

Предложение 10. Пусть g ∈ G_A. Тогда равенства X+X = A и gX+gX = A

равносильны.

Доказательство. Если X + X = A, то gX + gX = g(X + X) = gA = A.

Обратное утверждение следует из прямого, если заметить, что g-1 также при-

надлежит G_A. ▴

Дубли Минковского имеют также естественную характеризацию в терминах ана-

лиза Фурье на булевом кубе. Напомним основные обозначения и определения, отно-

сящиеся к такому анализу.

С элементом s ∈ Fd2 свяжем моном

∏

x_i.

x^s = xsii =

i: si=1

Мономы такого вида образуют ортонормированный базис в пространстве функций

{±1}^d → R относительно скалярного произведения

∑

〈f, g〉 =

f (a)g(a).

2^d

a∈{±1}^d

Коэффициенты разложения функции f : {±1}^d → R по этому базису называются

коэффициентами Фурье:

∑

f (x) =

f (s)x^s,

f (s) = 〈f, x_s〉.

s∈F^d

Легко проверяется формула свертки

∑

fg(s) =

f (q)g(s ⊕ q).

(14)

q∈F^d

Обозначим через

spec f = {s :

f (s) = 0} носитель функции

f, который мы будем

называть Фурье-носителем функции. Следствием формулы свертки (14) является

Предложение 11. Пусть g(s) ≥ 0 для всех s ∈ Fd2. Тогда

spec(g2) =

spec g +

spec g.

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

ковского в терминах анализа Фурье на булевом кубе.

Лемма 9. Дубли Минковского - это в точности Фурье-носители квадратов

функций с неотрицательными коэффициентами Фурье.

Доказательство. В одну сторону утверждение леммы совпадает с предло-

жением 11. В другую сторону: пусть A = B + B. Рассмотрим функцию

∑

χ_B = χ_B(s)x^s =

x^s.

s∈B

У нее коэффициенты Фурье неотрицательные, поэтому spec(χB)2 = A. ▴

Множество дублей Минковского образует подмоноид моноида Минковского.

Предложение 12

[1]. Если A и B - дубли, то и A + B - дубль.

Из A = X + X и B = Y + Y с учетом ассоциативности и коммутативности

сложения Минковского получаем

A + B = (X + Y ) + (X + Y ) = (X + X) + (Y + Y ).

Таким образом, отображение τ : X → X + X является эндоморфизмом (морфизмом

в себя) моноида Минковского, а дубли Минковского - это образ моноида Минков-

ского при действии эндоморфизма τ.

Характеризация дублей Минковского и вычислительная сложность проверки то-

го, что множество является дублем Минковского, - трудные открытые вопросы

в этой области.

СПИСОК ЛИТЕРАТУРЫ

1. Leontiev V., Movsisyan G., Margaryan Zh. On Addition of Sets in Boolean Space // J. Inf.

Secur. 2016. V. 7. № 4. P. 232-244.

2. Leontiev V., Movsisyan G., Margaryan Zh. Algebra and Geometry of Sets in Boolean Space //

Open J. Discrete Math. 2016. V. 6. № 2. P. 25-40.

3. Леонтьев В.К., Мовсисян Г.Л., Осипян А.А. Классификация подмножеств Bⁿ и адди-

тивные каналы // Вестн. Моск. ун-та. Сер. 1. Матем., мех. 2014. № 5. С. 23-29.

4. Leontiev V., Movsisyan G., Osipyan A., Margaryan Zh. On the Matrix and Additive Com-

munication Channels // J. Inf. Secur. 2014. V. 5. № 4. P. 178-191.

5. Sipser M. Introduction to the Theory of Computation. Boston: Thomson Course Technology,

2006.

6. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО,

1999.

7. Леонтьев В.К. О гранях единичного n-мерного куба // Ж. вычисл. матем. и матем.

физ. 2008. Т. 48. № 6. С. 1126-1139.

8. Guruswami V., Micciancio D., Regev O. The Complexity of the Covering Radius Problem

on Lattices and Codes // Proc. 19th IEEE Annual Conf. on Computational Complexity

(CCC’04). Amherst, MA, USA. June 21-24, 2004. Washington, DC, USA: IEEE Comput.

Soc., 2004. P. 161-173.