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

Том 55

2019

Вып. 4

УДК 621.391.1 : 519.1

Д.С. Кротов, В.Н. Потапов

О СПЕКТРЕ МОЩНОСТЕЙ

И ЧИСЛЕ ЛАТИНСКИХ БИТРЕЙДОВ ПОРЯДКА 31,2

Унитрейдом (латинским) порядка k называется подмножество вершин гра-

фа Хэмминга H(n,k), которое либо пересекается по двум вершинам, либо со-

всем не пересекается с любой максимальной кликой. Битрейдом называется

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

Исследуется спектр мощностей битрейдов в графе Хэмминга H(n, k) при k = 3

(троичном гиперкубе) и рост числа таких битрейдов с ростом n. В частности,

определены все возможные малые (до 2,5·2ⁿ) и большие (от 14·3n-3) мощности

битрейдов размерности n и доказано, что мощность битрейда принимает значе-

ния, только сравнимые с 0 или 2ⁿ по модулю 3 (этот результат имеет трактовку

в терминах троичного кода типа Рида - Маллера). Часть результатов примени-

ма для произвольного k. Доказано, что при k = 3 и растущем n число неэквива-

лентных битрейдов не меньше 2(2/3-o(1))n и не больше 2αn , α < 2 (порядок роста

двойного логарифма от этого числа остается неизвестным). Альтернативно ис-

следуемое множество Bn битрейдов порядка 3 можно определить следующим

образом: B0 состоит из трех чисел -1, 0, 1; Bn состоит из всех упорядоченных

троек (a, b, c) элементов из Bn-1, таких что a + b + c = 0.

Ключевые слова: латинские битрейды, унитрейды, коды Рида - Маллера, ком-

бинаторные конфигурации, булевы функции.

DOI: 10.1134/S0555292319040028

§ 1. Введение

Для комбинаторных объектов (конфигураций) различного типа оказывается по-

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

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

разности (например, симметрические) объектов этого типа (см. [1]). Битрейды отра-

жают возможную разницу между двумя комбинаторными конфигурациями одного

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

бинаторных конфигураций. Известны исследования битрейдов (или трейдов) комби-

наторных блок-дизайнов [2-6], латинских квадратов [7], обобщенных дизайнов в ча-

стично упорядоченных множествах [8], совершенных кодов [9, 10], корреляционно-

иммунных булевых функций и бент-функций [11]. В настоящей статье рассматрива-

ются латинские битрейды, соответствующие МДР-кодам с расстоянием 2, или (что

¹ Работа выполнена за счет грантов Российского научного фонда № 14-11-00555 (результаты

§§ 2, 3 и пп. 4.1, 4.5, 5.2) и № 18-11-00136 (результаты пп. 4.2-4.4, 4.6, 5.1).

² Результаты работы были частично представлены на конференциях International Conference and

PhD-Master Summer School “Groups and Graphs, Metrics and Manifolds” G2M2, Yekaterinburg, July

22-30, 2017, International Workshop on Algebraic Combinatorics, Hefei, China, November 22-25, 2018,

и 3rd Hungarian-Russian Combinatorics Workshop, Moscow, May 20-22, 2019.

эквивалентно) латинским гиперкубам, или полиадическим квазигруппам. Исследо-

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

Перейдем к формальным определениям. Пусть Q_k = {0, . . ., k - 1}. Опреде-

лим расстояние Хэмминга d(u, v) как число несовпадающих компонент в наборах

u, v ∈ Q^nk. Метрическое пространство (Q^nk, d), а также граф ΓQ^nk расстояний 1 на

множестве вершин Q^nk, называется k-ичным n-мерным гиперкубом или графом Хэм-

минга. Весом вершины u ∈ Q^nk называется величина wt(u) = d(u, 0), где 0 - набор

из n нулей (далее также используются аналогичные обозначения1, -1). Гранью в Q^nk

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

или нескольких координат. Множество U ⊂ Q^nk называется унитрейдом (размерно-

сти n), если мощности его пересечений с одномерными гранями (максимальными

кликами в ΓQ^nk) принимают только два значения 0 и 2. Обычно битрейдом называ-

ется пара {U₀, U₁}, состоящая из двух независимых долей двудольного унитрейда

U = U₀∪U₁. Но нам будет удобно называть битрейдом такой унитрейд U ⊂ Q^nk, что

подграф ΓU, порожденный множеством вершин U, является двудольным. В двумер-

ном случае (n = 2) любой унитрейд является битрейдом. Действительно, из теоремы

Кёнига следует, что любая квадратная (0, 1)-матрица, содержащая одинаковое число

единиц в каждом столбце и каждой строке, содержит диагональ. Значит, таблица ха-

рактеристической функции двумерного унитрейда, которую можно рассматривать

как (0, 1)-матрицу, после удаления нулевых строк и столбцов содержит две непересе-

кающиеся диагонали из единиц. При n ≥ 3 и k ≥ 3 имеются унитрейды, которые не

являются битрейдами. Минимальный пример приведен ниже, в нем три двумерные

таблицы соответствуют трем параллельным гиперграням трехмерного унитрейда:

(1)

Рассмотрим соответствие между данным выше определением и общим поняти-

ем битрейда. МДР-кодом называется подмножество гиперкуба Q^nk, пересекающееся

с каждой гранью фиксированной размерности r ровно по одному элементу. Нетруд-

но видеть, что МДР-коды - это коды с минимальным расстоянием между вершина-

ми r + 1 и максимальной для этого кодового расстояния мощностью k^n-r, т.е. ко-

ды, достигающие границы Синглтона. В данном контексте нас интересуют только

МДР-коды с кодовым расстоянием 2, т.е. когда r = 1. (Функция, выражающая зна-

чение одной из координат вершин такого кода через значения n - 1 оставшихся,

называется латинским (n - 1)-кубом, в случае n = 3 - латинским квадратом, а ал-

гебраическая система с такой функцией в качестве операции - (n - 1)-арной ква-

зигруппой). Из определений видно, что симметрическая разность двух МДР-кодов

является битрейдом.

Группа изометрий гиперкуба Q^nk порождается группой перестановок координат

и группой изотопий, т.е. перестановок элементов Q_k в каждой координате. В случае

k = 3 группа изометрий Qn3 состоит только из аффинных преобразований гипер-

куба Qn3 как n-мерного векторного пространства над полем GF(3). Подмножества

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

зываются эквивалентными. Ретрактом множества U ⊂ Q^nk будем называть под-

множество гиперкуба Qn-1k, полученное как пересечение множества U с некоторой

гранью размерности n - 1. Направлением ретракта или гиперграни будем называть

номер зафиксированной в этой грани координаты. Из определений следуют

Предложение 1. Любой ретракт унитрейда (битрейда, МДР-кода) являет-

ся унитрейдом (битрейдом, МДР-кодом) в гиперкубе меньшей размерности.

Предложение 2. Образ унитрейда (битрейда, МДР-кода) при изометрии

гиперкуба является унитрейдом (битрейдом, МДР-кодом).

В статье мы почти полностью ограничиваемся рассмотрением битрейдов в Qn3.

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

можно изометрично вложить в гиперкуб большего порядка Q^nk, k ≥ 4, таким обра-

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

случая k = 3. Одним из таких вопросов является проблема асимптотики двойного

логарифма числа объектов при фиксированном k и растущем n, причем именно для

случая k = 3 эта проблема наиболее ярко выражена: имеющаяся нижняя оценка

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

время как верхняя оценка близка к тривиальной 22n (от которой нам все же уда-

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

порядков, k > 3, дважды экспоненциальная нижняя оценка достигается за счет

свитчинговой конструнции, основанной на возможности разместить в рассматри-

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

латинских гиперкубов в [12, 13]). С одной стороны, ограниченное число “степеней

свободы” латинских битрейдов порядка 3 позволяет надеяться на построение строй-

ной комбинаторно-алгебраической теории этих объектов (попытка такого постро-

ения представлена в настоящей статье), с другой стороны, сложность некоторых

вопросов полностью раскрывается уже для этого малого порядка.

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

ры (§ 2 и п. 4.2), теории булевых функций (§ 3) и теории кодирования (§ 3 и п. 4.1).

В частности, показана связь задачи описания троичных битрейдов с задачей нахож-

дения полиномиальной сложности булевой функции [14, 15]. Известна также связь

троичных битрейдов с почти уравновешенными булевыми функциями (предложе-

ние 7).

В §4 исследуется спектр мощностей троичных битрейдов, а также унитрейдов и

битрейдов больших порядков. Показано, что мощность любого троичного битрейда

размерности n сравнима с 0 или 2ⁿ по модулю три. Минимальная мощность непусто-

го битрейда (не только троичного) размерности n равна 2ⁿ. Все возможные мощно-

сти битрейдов, не превышающие 2 · 2ⁿ, были известны ранее (см. [16]). В настоящей

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

го кода Рида - Маллера (предложение 9). Кроме того, определены все возможные

мощности унитрейдов и битрейдов размерности n от минимальной 2ⁿ до 2,5 · 2ⁿ

(теоремы 1, 5, следствие 7). Троичным битрейдом максимальной мощности 2 · 3n-1

является пара непересекающихся МДР-кодов. Как известно (см., например, [17])

имеется единственный (с точностью до эквивалентности) троичный битрейд такой

мощности. Отметим, что уже для порядка 4 имеется дважды экспоненциальное чис-

ло неэквивалентных битрейдов максимальной мощности 2 · 4n-1 (см. [13, 17]).

Одной из основных задач исследования битрейдов является определение их числа

как функции от размерности n и порядка k. Благодаря тому, что битрейды соответ-

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

открывает перспективы исследования разнообразия исходных объектов и оценки их

числа. Для латинских гиперкубов (порядка больше 4) размерности n, с которыми

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

логарифма числа при n → ∞ (см. [13]). В [16] была получена почти экспоненци-

альная (e^Ω(√n)) асимптотическая нижняя оценка числа неэквивалентных битрейдов

в Qn3. В п. 5.1 доказана нижняя оценка 2(2/3-o(1))n числа неэквивалентных битрей-

дов в Qn3 при n → ∞ (теорема 7) и показано, что подобным нашему методом нельзя

получить нижнюю оценку выше экспоненциальной (теорема 6). В п. 5.2 получена

верхняя оценка вида 2αn, α < 2, для числа битрейдов в Qn3 (теорема 8), которая

существенно улучшает тривиальную верхнюю оценку 22n. Однако вопрос о скоро-

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

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

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

в п. 4.5, показывают рост быстрее экспоненциального, но вывод о линейном росте

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

Метод доказательства верхней оценки связан с тем, что в гиперкубе Qn3 при n ≥ 7

удалось указать множество мощности строго больше 3ⁿ - 2ⁿ, которое не включает

в себя ни одного битрейда и даже симметрических разностей двух битрейдов. Для

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

ской прогрессии (что в троичном гиперкубе совпадает с подмножеством, не вклю-

чающем одномерного аффинного подпространства) недавно была получена асимп-

тотическая верхняя оценка вида o(αⁿ), где α < 3 (см. [18]). Нахождение в троичном

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

остается актуальной задачей.

Завершая § 1, опишем рекурсивно класс B_n объектов, который определяется

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

ка 3 (данная формулировка приводится с иллюстративной целью и нигде в тексте

больше не используется):

B₀ = {-1, 0, 1}, B_n = {(a, b, c) ∈ B3n-1 | a + b + c = 0}.

Если представлять элементы класса B_n как n-мерные таблицы, заполненные числа-

ми -1, 0, 1, то множество ячеек с ненулевыми значениями в такой таблице как раз

и образует битрейд.

§ 2. Линейные пространства

Пусть F - некоторое поле. Рассмотрим множество функций {g : Q^nk → F} как век-

торное пространство над полем F. Обозначим через V_n,k(F) подпространство, состо-

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

ной клике в графе ΓQ^nk) равна 0. Рассмотрим битрейд B ⊂ Q^nk. Ему соответствует

функция b[B]: Q^nk → {0, ±1}, которая на одной доле битрейда принимает значе-

ние 1, на другой - значение -1, а в остальных вершинах равна 0. Рассмотрим {0, ±1}

как подмножество поля F (для поля характеристики 2 имеем -1 = 1). Очевидно,

b[B] ∈ V_n,k(F). Характеристическая функция унитрейда содержится в V_n,k(F) в слу-

чае, когда поле F имеет характеристику 2.

Введем следующий частичный порядок ≼ на Q_k: элемент k - 1 будем считать

максимальным, а все остальные элементы из Q_k несравнимыми друг с другом. Рас-

пространим частичный порядок на Q^nk. Пусть (x₁, . . . , x_n), (y₁, . . . , y_n) ∈ Q^nk. Введем

обозначение (x₁, . . ., x_n) ≼ (y₁, . . . , y_n), если для любого i ∈ {1, . . ., n} верно, что

x_i ≼ y_i. Отметим, что множество G_y = {x ∈ Q^nk | x ≼ y} является гранью гиперку-

ба Q^nk размерности, равной числу символов k - 1 в наборе y.

Покажем, что dim V_n,k(F) = (k - 1)ⁿ. Пусть f ∈ V_n,k(F). Сумма значений функ-

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

∑

f (y) = -

f (x) при y ∈ Q^nk \ Qnk-1.

(2)

x∈Qnk-1, x≼y

Следовательно, для определения функции f ∈ V_n,k(F) необходимо и достаточно

определить ее на всех минимальных элементах, т.е. на Qnk-1. Построим семейство

линейно независимых функций той же мощности. Пусть x ∈ Qnk-1. Рассмотрим

множество B_x = {y ∈ Q^nk | x ≼ y}. Нетрудно видеть, что граф ΓB_x изоморфен

булеву гиперкубу ΓQn2, в частности, B_x является битрейдом. Здесь набору z ∈ Qn2

соответствует вершина y ∈ B_x, у которой координаты, соответствующие единицам

в наборе z, равны k - 1, а координаты, соответствующие нулям в наборе z, такие

же, как в наборе x. Определим wt(y) как число координат в наборе y, равных k - 1,

т.е. wt(y) = wt(z). Соответствующую этому битрейду функцию можно задать явной

формулой b_x(y) = (-1)wt(y)χ_B

(y). Поскольку supp(b_x)∩Qnk-1 = {x}, набор функций

{b_x | x ∈ Qnk-1} является базисом в V_n,k(F), и значит, dimV_n,k(F) = (k - 1)ⁿ.

Следующее утверждение нетрудно доказать по индукции (см. [16]).

Предложение 3. Пусть f ∈ V_n,k(F) и supp(f) = ∅. Тогда (a) |supp(f)| ≥ 2ⁿ;

(b) если |supp(f)| = 2ⁿ, то граф Γ(supp(f)) изоморфен булеву гиперкубу ΓQn2.

⁽k

Нетрудно видеть, что имеется всего

вариантов выбрать унитрейд (бит-

рейд) с носителем мощности 2ⁿ. Как показано выше, базис пространства V_n,k(GF(2))

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

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

Поскольку при k > 2 число таких множеств больше размерности пространства,

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

ции над GF(2) булевых гиперкубов. Минимальное число булевых гиперкубов в та-

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

rank(U).

Рассмотрим более подробно троичный гиперкуб. Любой элемент пространства

Vn,3(GF(2)) является унитрейдом, поскольку четное число единиц из трех возмож-

ных в одномерной грани равняется 0 или 2. Размерность пространства Vn,3(GF(2))

равна 2ⁿ, поэтому в гиперкубе Qn3 имеется ровно 22n различных унитрейдов. Мето-

дом индукции по размерности n нетрудно доказать

Предложение 4. (a) Любая пара непустых унитрейдов в Qn3 имеет непу-

стое пересечение.

(b) Если в Qn3 непустой унитрейд является подмножеством другого унитрейда,

то эти унитрейды совпадают.

Из утверждения (c) следует, что если унитрейд U ⊂ Qn3 является битрейдом, то

он разделяется на две доли однозначно.

§ 3. Булевы функции

Пусть f : Qn2 → Q₂ - некоторая булева функция. Определим функцию U[f]: Qn3 →⊕

→ Q₂ равенством U[f](y) =

f (x) (здесь и далее операция ⊕ обозначает

x∈Qn2, x≼y

сложение в двоичном поле GF(2)). Из определения видно, что U[f]|_Qn = f. Из сов-

падения определения функции U[f] и формулы (2) над полем GF(2) следует, что

U [f] - характеристическая функция унитрейда в Qn3. Более того, из вышеизложен-

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

взаимно-однозначное соответствие.

Пусть x ∈ Qn2. Введем следующие обозначения: x1i = x_i, x-1i = x_i ⊕ 1, x0i = 1,

и если x = (x₁, . . . , x_n), то x^v = xv11 . . . xnn , где v ∈ Q³ = {0, ±1}ⁿ.

Полиномиальным предс⊕авлением булевой функции f называется формула вида

f (x) = f^A(x₁, . . . , x_n) =

x^v. Минимальное количество слагаемых в этом пред-

v∈A⊂Qⁿ

ставлении (min |A|) называется полиномиальной сложностью функции f (см. [15]).

Обозначим {0, ±1}₀ = {0, 1}, {0, ±1}₁ = {1, -1}, {0, ±1}-1 = {0, -1} и {0, ±1}_v =

= {0, ±1}v1 ×. . .×{0, ±1}vn. Вложенные в Qn3 булевы гиперкубы исчерпываются ку-

бами вида {0, ±1}_v. Нетрудно видеть, что сужение характеристической функции ги-

перкуба {0, ±1}_v на булев подкуб {0, 1}ⁿ совпадает с мономом x^v, т.е. χ

(x) = x^v

{0,±1}v

⊕

при x ∈ Qⁿ

. Поэтому U[f^A] =

, и rank(U[f]) равен полиномиаль-

{0,±1}v

v∈A⊂Qⁿ

ной сложности функции f. Проблема нахождения представления булевой функ-

ции минимальной полиномиальной сложности (minimization of exclusive-OR-sum-of-

products) рассматривается, например, в [14]. Известно (см. [15]), что для размерно-

сти 5 максимальная сложность булевой функции равна 9, для размерности 6 она

равна 15, и существуют булевы функции от семи аргументов с полиномиальной

сложностью 24.

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

ность булевой функции не больше суммы сложностей двух ее подфункций, полу-

ченных фиксацией 0 и 1 некоторой переменной. Отсюда вытекает

Следствие 1. Ранг унитрейда не превосходит суммы рангов двух его различ-

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

Полиномиальное представление булевой функции неоднозначно. Но если не ис-

пользовать один из операторов x⁰, x¹ или x-1, то представление приобретает од-

нозначность. В § 2 рассматривался базис в пространстве f ∈ Vn,3(GF(2)), соответ-

ствующий операторам x¹ и x-1. Если исключить оператор x-1 (“отрицание”), мы

приходим к базису из сложения и умножения над GF(2). А именно, каждая буле-

ва функция f : Qn2 → Q₂ может быть единственным образом представлена в виде

многочлена Жегалкина (в алгебраической нормальной форме)

⊕

f (x₁, . . . , x_n) =

G[f](y)xy11 . . . xnn ,

y∈Qⁿ

где G[f]: Qn2 → Q₂ - булева функция.

Алгебраической степенью булевой функции f называется максимальная степень

слагаемого в ее многочлене Жегалкина, т.е. deg f = max wt(y).

G[f](y)=1

Справедливо следующее

Предложение 5. Для любой булевой функции f верно равенство G[f](y) =⊕

f (x).

x∈Qn2, x≼y

Таким образом, G[f] являе⊕ся преобразованием Мёбиуса функции f над полем

GF(2). Поскольку f(x) =

G[f](y), имеем равенство G[G[f]] = f для лю-

y∈Qn2, x≼y

бой булевой функции f. Из определений преобразования Мёбиуса и оператора U[ · ]

видно, что U[f]|{0,2}n является преобразованием Мёбиуса булевой функции f.

Из предложения 5 непосредственно следует известное

Предложение 6. Булева функция f : Qn2 → Q₂ имеет четное число единиц во

всех гранях размерности не меньше m тогда и только тогда, когда deg f ≤ m - 1.

Наборы значений булевых функций f : Qn2 → Q₂ можно рассматривать как эле-

менты булева куба размерности 2ⁿ. Множество наборов значений булевых функций

алгебраической степени не выше m называется кодом Рида - Маллера R(m, n) в Q2n2.

Известно, что минимальный вес ненулевого кодового набора R(m, n), совпадающий

с мощностью носителя соответствующей булевой функции, равен 2^n-m.

Замечание 1. Отметим, что аналогичным образом множество элементов про-

странства V_n,k(GF(q)) можно рассматривать как линейный код длины kⁿ и мощ-

ности q(k-1)n с кодовым расстоянием 2ⁿ. В частности, унитрейды в Qn3 образуют

двоичный код длины 3ⁿ и мощности 22n с кодовым расстоянием 2ⁿ.

В случае, когда k = q, пространство V_n,k(GF(q)) имеет достаточно естественное

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

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

менных. Легко понять, что для простого q базисом V_n,q(GF(q)) является множество

всех мономов, у которых степень каждой переменной не превосходит q-2. Таким об-

разом, V_n,q(GF(q)) можно рассматривать как один из вариантов недвоичного обоб-

щения кодов Рида - Маллера. В частности, один из результатов п. 4.2 (следствие 2)

можно трактовать в терминах весового распределения этого кода при q = 3: каждая

третья компонента этого распределения нулевая.

В [19] указана связь между троичными битрейдами и равномерностью распре-

деления единиц булевой функции по граням. Булева функция называется почти

уравновешенной в гранях, если число нулей и единиц функции отличается не более

чем на 2 в любой грани любого размера.

Предложение 7. Пусть булева функция f уравновешена в гранях, а p(x) =

= x₁⊕...⊕x_n - счетчик четности. Тогда унитрейд U[f ⊕p] является битрейдом.

Из предложения 1 следует, что если булева функция f соответствует битрей-

ду U[f], то и ее подфункции, полученные фиксацией некоторых переменных, также

соответствуют битрейдам в гиперкубах меньшей размерности.

§ 4. Мощностной спектр множества битрейдов

В этом параграфе будут доказаны свойства спектра мощностей троичных битрей-

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

4.1. Мощности унитрейдов и весовой спектр кодов Рида - Маллера. Из предло-

жения 3 следует, что минимальная мощность непустого унитрейда размерности n

равна 2ⁿ. В [16] было доказано

Предложение 8. Любой унитрейд U ⊂ Q^nk, мощность которого удовлетво-

ряет неравенствам 2n+1 > |U| ≥ 2ⁿ, является битрейдом, имеет rank(U) = 2

и мощность |U| = 2n+1 - 2s+1, где s ∈ {0, . . ., n - 1}.

Используя результаты исследований весового спектра кодов Рида - Маллера,

можно сильно сузить спектр гипотетических малых (от 2ⁿ до 5 · 2n-1) мощностей

унитрейдов размерности n.

Предложение 9. Пусть U - унитрейд в Q^nk, k = 2^τ. Тогда существует век-

тор u ∈ R((τ - 1)n, τn), такой что |U| = wt(u).

Доказательство. Пусть f = χU : Qnk → {0,1}. Рассмотрим произвольное

взаимно-однозначное отображение ψ: Qτ2 → Q_k. Пусть булева функция F определе-

на равенством

F = f(ψ(x₁,...,x_τ),ψ(xτ+1,...,x2τ),...,ψ(xτ(n-1)+1,...,x_τn)).

Проверим, что deg F ≤ (τ - 1)n. Рассмотрим любую грань Δ булева гиперкуба раз-

мерности (τ -1)n+1. Поскольку Δ получена фиксацией значений n-1 переменных,

найдется i от 0 до n - 1 такое, что значения переменных xτi+1, . . . , xτi+τ не фикси-

рованы в грани Δ. По определению унитрейда при фиксированных значениях всех

остальных переменных, кроме xτi+1, . . . , xτi+τ , функция F принимает значение 1

четное число раз. Значит, она принимает значение 1 четное число раз в грани Δ. Из

предложения 6 следует, что deg F ≤ (τ - 1)n. Поэтому набор значений функции F

содержится в коде R((τ - 1)n, τn). Следовательно, унитрейду U соответствует неко-

торый вектор u ∈ R((τ -1)n, τn). А поскольку функции F и f одинаковое число раз

принимают значение 1, имеем |U| = wt(u). ▴

Замечание 2. [t]-трейд в Q^Nk определяется как пара непересекающихся множеств

вершин из Q^Nk , разность характеристических функций которых имеет сумму 0 по

любой (N -t)-мерной грани. По определению битрейд в Q^Nk является [N -1]-трейдом.

Аналогично предложению 9 доказывается следующий факт: битрейду в Q^nk, k = 2^τ ,

соответствует [t]-трейд в Qτn2, где t = n-1. [t]-трейды естественным образом соответ-

ствуют разностям ортогональных массивов и алгебраических t-дизайнов в графах

Хэмминга. Аналогичное нашему исследование мощностей малых двоичных [t]-трей-

дов было проведено в работе [6]. В частности, построены трейды с мощностями из

серий, рассмотренных нами в п. 4.6.

В [20,21] показано, что ненулевые вершины кода R(m, n) могут иметь вес только

вида α_m2^n-m, где α_m = 2 - 2^-k, k = 0, . . . , n - m - 1, или α_m = 2 + 2^-k, k =

^⌊n-m^⌋

= 2, . . .,

, или α_m = 2

-2^-k, k = 1, . . . , n-m-1, или α_m = 2¹

-2^-k-2-(k+1),

k = 3,...,n - m - 2, или α_m ≥ 2

Теорема 1. Мощность унитрейда в Q^nk может принимать только значения

вида α_n2ⁿ, где

α_n = 2 - 2^-k, k = 0, . . ., n - 1, или

α_n = 2 + 2^-k, k = 2, . . ., ⌊n/2⌋, или

α_n = 2

- 2^-k, k = 1, . . ., n - 1, или

α_n = 2

- 2^-k - 2-(k+1), k = 3,...,n - 2, или α_n ≥ 2¹

Доказательство. Любой унитрейд в Q^nk имеет мощность не меньше 2ⁿ (пред-

ложение 3). Сужение унитрейда на грань (ретракт) есть унитрейд по предложе-

нию 1. Поэтому унитрейд, пересекающийся с пятью параллельными гиперграня-

ми некоторого направления, имеет мощность не менее 5 · 2n-1 (последний случай

в утверждении теоремы). Если же унитрейд пересекается не более чем с четырь-

мя параллельными гипергранями любого направления и является подмножеством

вершин подграфа, изоморфного Qn4, то в этом случае требуемое следует из предло-

жения 9 (τ = 2) и перечисленных выше результатов работ [20, 21]. ▴

4.2. Троичные битрейды как линейные функции над полем GF(3). Вначале вы-

берем подходящий базис в пространстве Vn,3(GF(3)). Здесь нам будет удобно счи-

тать, что Q₃ = {0, ±1} = GF(3) (-1 ≡ 2 mod 3). Пусть s₀(a) = 1 и s₁(a) = a.

Определим функции s_α : Qn3 → Q₃, α ∈ Qn2, равенствами s_α(x) = sα1(x₁) . . . sαn(x_n).

Предложение 10. (a) s_α ∈ Vn,3(GF(3));

(b) {s_α | α ∈ Qn2} - базис в Vn,3(GF(3));∑

s_α(x)s_β(x) = 0 за исключением случая α = β =

1_.

x∈Qⁿ

∑

s₀(a) =

∑оказательство. Утверждение (a) следует из того факта, что

= s₁(a) = 0.

a∈Q3

(b) Заметим, что α ∈ supp(s_α), а α ∈ supp(s_β ), только если β ≼ α, α, β ∈ Qn2. Упо-

рядочим функции s_α в порядке (частичном) убывания от

1 до 0. Носитель каждой

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

щих функций. Поэтому на каждом шаге мы будем получать линейно независимое

семейство функций. Как показано выше, dim(Vn,3(GF(3))) = 2ⁿ, следовательно, се-

мейство линейно независимых функций мощности 2ⁿ является базисом.

считать, что α_n = 0. Тогда справедливы равенства

∑

s_α(x)s_β(x) =

x∈Qn3

∑

sα1 (x₁)sβ1 (x₁). . . sαn-1 (xn-1)sβn-1 (xn-1)

s₀(x_n)sβn (x_n) =

xn∈Q3

∑

sα1 (x₁)sβ1 (x₁). . . sαn-1 (xn-1)sβn-1 (xn-1)

sβn (x_n) = 0.

▴

xn∈Q3

Следствие 2. Для любого f ∈ Vn,3(GF(3)) верно 〈f,f〉₃ ∈ {0,2ⁿ mod 3}.

∑

Доказательство. Из предложения 10 следует, что f =

a_αs_α и

α∈Qⁿ

∑

〈f, f〉₃ =

a_αa_β

s_α(x)s_β(x) = a^¯

s^¯1 = a^¯1|supp(s1)| = a^¯12ⁿ,

α,β∈Qⁿ

x∈Qⁿ

где все операции выполняются в поле GF(3). ▴

Как отмечено в замечании 1, пространство Vn,3(GF(3)) является троичным кодом

типа Рида - Маллера, а следствие 2 означает, что весовой спектр этого кода имеет

нули в каждой третьей компоненте.

Теорема 2. Для любого битрейда B ⊂ Qn3 верно, что |B| ≡ 0,2ⁿ mod 3.

Доказательство. Рассмотрим функцию b: Qn3 → Q₃, принимающую значе-

ния 1 и -1 на двух долях битрейда B и значение 0 в остальных точках. Тогда

b ∈ Vn,3(GF(3)) и |B| mod 3 = 〈b,b〉₃ ∈ {0,2ⁿ mod 3}. ▴

Следствие 3. Не существует битрейда U ⊂ Qn3 мощности 2n+1.

4.3. Некоторые свойства мощностного спектра троичных битрейдов. Рассмотрим

несколько простых свойств битрейдов. Пусть f - булева функция от переменных

x₁, . . ., x_n, а g - булева функция от переменных y₁, . . . , y_m, и наборы переменных

не пересекаются. Обозначим через f(x)g(y) булеву функцию от n + m переменных.

В [16] имеется

Предложение 11. Если U[f] ⊂ Qn3 и U[g] ⊂ Qm3 - битрейды, то U[f(x)g(y)] ⊂

⊂ Qn+m3 - битрейд и |U[f(x)g(y)]| = |U[f]||U[g]|.

В частности, в качестве g можно рассмотреть линейную функцию g(y) =

^⊕y_i

и как следствие получить такое свойство: если в Qn3 имеется битрейд мощности a,

то в Qn+m3 имеется битрейд мощности a2^m. Эту конструкцию можно рассматривать

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

дение двух битрейдов является битрейдом не только в троичном гиперкубе, но и в

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

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

Теорема 3 (о построении разложимых битрейдов). Пусть B ⊂ Q^nk и C ⊂ Q^nk

- битрейды. Тогда в Qn+mk имеются битрейды мощности |B| · |C|, 2^m|B|, k^m|B|.

Доказательство. Битрейды мощности |B| · |C| и 2^m|B| можно построить

с помощью декартова произведения. Возможность построения битрейда мощности

k^m|B| можно доказать по индукции из случая m = 1, который разберем отдель-

но. Пусть функция b: Q^nk → {-1, 0, 1} принимает значения 1 и -1 на двух долях

некоторого битрейда и 0 в остальных точках. Тогда функция b^′ : Qn+1k → {-1, 0, 1},

заданная равенством b^′(x₁, . . . , x_n, xn+1) = b(x₁, . . ., xn-1, (x_n + xn+1) mod k), опре-

деляет битрейд размерности n + 1 и мощности k|B|. ▴

Предложение 12. Если унитрейд U ⊂ Qn3 имеет пустой ретракт по неко-

торому направлению, то он эквивалентен унитрейду U[f], где f - булева функция,

не зависящая от одной из переменных. При этом U является битрейдом тогда и

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

тому же направлению.

Доказательство. Без ограничения общности можно считать, что U ∩ {x_n =

= -1} = ∅. Тогда из определения унитрейда имеем U ∩{x_n = 0} = U ∩{x_n = 1} = U^′

и U = U^′ × {0,1}. Пусть U^′ = U[f] и g(x₁,...,x_n) = f(x₁,...,xn-1). Тогда U =

= U[g]. Из предложений 1 и 11 следует, что унитрейды U и U^′ являются битрейдами

одновременно. ▴

Поскольку каждая одномерная грань гиперкуба пересекается с унитрейдом не

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

более 2 · 3n-1 вершин. При этом в случае равенства |U| = 2 · 3n-1 дополнение Qn3 \ U

является МДР-кодом. Как известно (см., например, [17]), в Qn3 имеется единствен-

ный с точностью до эквивалентности МДР-код, являющийся линейным (т.е. аффин-

ным подпространством над полем GF(3)). Дополнение аффинного подпространства

над GF(3) состоит из двух его смежных классов. Поэтому унитрейд максимальной

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

дующей теоремы.

Теорема 4 (о битрейдах большой мощности). Справедливы следующие утвер-

ждения:

(a) В Qn3 имеется только один с точностью до эквивалентности унитрейд B

максимальной мощности 2 · 3n-1, который является битрейдом и может

быть задан равенством B = {x ∈ Qn3 | x₁ + . . . + x_n ≡ 0 mod 3} = U[ℓ], где ℓ -

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

(b) В Qn3 имеются битрейды мощности 14 · 3n-3.

и 2·3n-1.

Доказательство. Осталось доказать утверждения (b) и (c). В Q³³ имеется

битрейд U[x₁x₂x₃ ⊕(x₁ ⊕1)(x₂ ⊕1)(x₃ ⊕1)] мощности 14. Из теоремы 3 получаем (b).

Докажем (c) по индукции. Базой индукции является случай n = 3, который легко

проверить непосредственно. Пусть теперь Un+1 ⊂ Qn+13 - некоторый битрейд. Ес-

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

2·3n-1, то |Un+1| ≤ 14·3n-2 по предположению индукции. Предположим, что в Un+1

найдется по одному ретракту каждого направления мощности 2·3n-1. Без ограниче-

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

вому значению некоторой переменной (x_i = 0). По утверждению (a) они с точностью

до эквивалентности заданы линейными над GF(3) функциями. Тогда Un+1 = U[f],

где f = ℓ или f = ℓ ⊕ x₁ . . . xn+1. Однако вторая функция имеет недвудольный трех-

мерный ретракт при n ≥ 4. Действительно, рассмотрим трехмерный ретракт, полу-

ченный из U[f], где f = ℓ ⊕ x₁ . . . xn+1, фиксацией координат x₄ = . . . = xn+1 = 1.

Если n-2 = 0, 1 mod 3, то этот ретракт эквивалентен недвудольному унитрейду (1);

если n - 2 = 2 mod 3, то недвудольному унитрейду (1) эквивалентен ретракт, полу-

ченный фиксацией координат x₄ = 2, x₅ = . . . = xn+1 = 1. Поэтому в случае, когда

U [f] ⊂ Qn+13 - битрейд, имеем f = ℓ и |Un+1| = |U[f]| = 2 · 3ⁿ. ▴

4.4. Битрейды и расстояния между мономами. Пусть B ⊂ Q^nk - битрейд. В § 2

была определена функция b[B]: Q^nk → {0, ±1}, которая принимает значение 1 на

одной доле битрейда B, -1 на другой его доле и 0 в остальных вершинах. В этом

пункте мы будем рассматривать b[B] как функцию, действующую в R, т.е. b[B] ∈

∈ Vn,3(R). В случае k = 3 такую функцию можно определить ровно двумя спосо-

бами: b[B] и -b[B], поскольку граф ΓB связен. В дальнейшем мы рассматриваем

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

функции b[B]. Для краткости введем обозначения b_v = b[U[x^v]] и b_V = b[U[f^V ]], где

v∈Qn3,V ⊂Qn3.

Предложение 13. Пусть B,B^′ ⊂ Qn3 - битрейды и b[B](x)b[B^′](x) = 1 для

любого x ∈ Qn3. Тогда S = supp(b[B] + b[B^′]) - битрейд и b[S] = b[B] + b[B^′].

Доказательство. Если b[B],b[B^′] ∈ Vn,3(R), то b[B]+b[B^′] ∈ Vn,3(R). По усло-

вию b[B]b[B^′] = 1, следовательно, (b[B]+b[B^′])(Qn3) ⊆ {0, ±1}. Тогда по определению

S = supp(b[B] + b[B^′]) - битрейд. ▴

Будем говорить, что функции b_v и b_u согласованы, если b_u(x)b_v(x) = 1 для любого

x∈Qn3.

Предложение 14. Пусть v,u ∈ Qn3. Если найдется вершина x ∈ Qn3, такая

что b_v(x)b_u(x) = -1, то пара функций b_u и b_v согласована.

Доказательство. Пересечение битрейдов U[x^u] и U[x^v] является булевым

подкубом в грани, соответствующей совпадающим координатам наборов u и v. Из

связности пересечения U[x^u] ∩ U[x^v] следует, что унитрейд U[x^u ⊕ x^v] является би-

трейдом. Как было замечено выше, любой битрейд разделяется на доли единствен-

ным образом. ▴

Следствие 4. Любой унитрейд ранга 2 является битрейдом.

Предложение 15. Унитрейд U[fV ] является битрейдом, если для каждого∑

v ∈ V можно выбрать функции (знак функции) b_v так, чтобы функция g =

b_v

принимала значения только из множества {0, ±1}.

v∈V

Доказательство. Поскольку b_v ∈ Vn,3(R) для любого v ∈ V , то и g ∈ Vn,3(R).

Тогда из условия следует, что supp(g) - унитрейд. Очевидно, U[f^V ] ⊂ supp(g). Тогда

из предложения 4(b) имеем supp(g) = U[f^V ], т.е. g = ±b_V . ▴

Предложение 16. Пусть V ⊂ Qn3 и |V | = 3 (т.е. rank(U[fV ]) ≤ 3). Если все

вершины множества V различаются только в двух координатах либо две вершины

множества V различаются только в одной координате, то U[f^V ] - битрейд.

Доказательство. Пусть V = {u,v,w} и вершины множества V различаются

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

двумерному случаю, когда все унитрейды являются битрейдами.

Если d(v, u) = 1, то x^v ⊕ x^u = x^o, т.е. rank(U[f^V ]) = 2, и требуемое вытекает из

следствия 4. ▴

Будем говорить, что три вершины {u, v, w} ⊂ Qn3 находятся в общем положе-

нии, если найдется координата, в которой они попарно различаются. В этом случае

найдутся точки a, a^′, a^′′ ∈ Qn3, в которых носители битрейдов b_u, b_v, b_w пересекаются

только попарно, т.е. a ∈ (supp(b_v) ∩ supp(b_u)) \ supp(b_w), a^′ ∈ (supp(b_v) ∩ supp(b_w)) \

\ supp(b_u), a^′′ ∈ (supp(b_w) ∩ supp(b_u)) \ supp(b_v).

Вначале рассмотрим унитрейды U[f^V ] ранга 3, когда три вершины V = {u, v, w}

не находятся в общем положении.

Предложение 17. Пусть V = {u,v,w} ⊂ Qn3.

(a) Если любая координата набора w совпадает с соответствующей координатой

набора u или набора v, то U[f^V ] - битрейд.

(b) Если любая координата на наборах u, v, w принимает не более двух значений и

не выполнено условие (a), то U[f^V ] не является битрейдом.

Доказательство. (a) Рассмотрим случай, когда нет координаты, в которой

все три вершины u, v, w совпадают. Без ограничения общности можно считать, что

u =

0, v = 1, w ∈ {0, 1}ⁿ. По предложению 14 функции b_v и b_u можно выбрать

так, чтобы вещественные суммы b_v + b_w и b_u + b_w принимали значения только из

множества {0, ±1}. Из условия видно, что U[x⁰] ∩ U[x¹] = {1} ⊂ U[x^w]. Поэтому

(b_v + b_w)(1) = 0. Следовательно, функция b_v + b_u + b_w принимает значения только

из множества {0, ±1}. Требуемое следует из предложения 15.

Случай, когда все три вершины u, v, w совпадают в некоторой координате, сво-

дится к рассмотренному с помощью предложения 12.

(b) Если любая тройка координат в наборах u, v, w удовлетворяет условию (a),

то наборы u, v, w также удовлетворяют этому условию. Без ограничения общности

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

ров u, v, w и они равны, соответственно, e₁ = (1, 0, 0), e₂ = (0, 1, 0) и e₃ = (0, 0, 1).

Поскольку в каждой координате наборы u, v, w принимают только два значения, то

найдется трехмерная грань, на которой x^v ⊕ x^u ⊕ x^w = x₁ ⊕ x₂ ⊕ x₃ = f^′. Непосред-

ственная проверка показывает, что U[f^′] эквивалентен унитрейду (1) и не является

битрейдом. Тогда из предложения 1 следует, что и U[f^V ] не является битрейдом. ▴

Теперь рассмотрим унитрейды U[f^V ] ранга 3, когда три вершины V = {u, v, w}

находятся в общем положении.

Предложение 18. Пусть V = {u,v,w} ⊂ Qn3.

(a) Если сумма попарных расстояний между вершинами множества V нечетна,

то они находятся в общем положении.

(b) Если вершины множества V находятся в общем положении, то из согласо-

ванности пары b_v, b_u и пары b_v, b_w следует согласованность пары b_u, b_w тогда

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

ства V нечетна.

Доказательство. Если вершины u,v,w не находятся в общем положении, то

каждая координата дает вклад 0 или 2 в сумму d(u, v) + d(v, w) + d(u, v). Поэтому

в этом случае сумма расстояний четная. Пункт (a) доказан.

Рассмотрим случай, когда V = {⁰, 1, -1}. Нетрудно видеть, что унитрейды U[x⁰]

и U[x¹] пересекаются по одной точке 1. Разделим битрейд U[x⁰ ⊕ x¹] на две доли.

Вершины той же четности, что и

1, в гиперкубах U[x⁰] и U[x¹] должны принадле-

жать разным долям. Следовательно, вершины

0 и -1 оказываются в разных долях.

Рассмотрим гиперкуб U[x-1]. Ясно, что вершины 0 и -1 оказываются в разных до-

лях, если и только если n нечетно. Тогда из согласованности пары b0, b1 и пары

b0, b-1 следует согласованность пары b1, b-1 при нечетном n и несогласованность

пары b1, b-1 при четном n.

Проведем дальнейшее доказательство по индукции. Предположим, что при n - 1

утверждение доказано.

Пусть вершины u, v, w попарно различаются в каждой координате. Тогда утвер-

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

ордината, в которой не все вершины u, v, w попарно различаются. После удаления

этой координаты укороченные наборы v^′, u^′, w^′ также находятся в общем положе-

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

последней. Очевидно, d(u^′, v^′) + d(v^′, w^′) + d(u^′, v^′) = d(u, v) + d(v, w) + d(u, v), если

u_n = v_n = w_n, и d(u^′, v^′)+d(v^′, w^′)+d(u^′, v^′) = d(u, v)+d(v, w)+d(u, v)-2 в против-

ном случае. Тогда утверждение верно для функций b_v′ , b_u′ и b_w′ по предположению

индукции. Поскольку последняя координата не принимает одно из значений {0, ±1}

на наборах u, v, w, то найдется гипергрань x_n = δ по последнему направлению, та-

кая что b_v(xδ) = b_v′ (x), b_u(xδ) = b_u′ (x), b_w(xδ) = b_w′ (x) для всех x ∈ Qn-13. Тогда

для функций b_v, b_u и b_w требуемое следует из предложения 14. ▴

Следствие 5. Если сумма попарных расстояний между вершинами множе-

ства V = {u, v, w} ⊂ Qn3 нечетна, то U[f^V ] - битрейд.

Следствие 6. Если вершины множества V = {u,v,w} ⊂ Qn3 находятся в об-

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

ных расстояний между вершинами множества V четна, то U[f^V ] не является

битрейдом.

Доказательство. Из предложения 18 следует, что набор функций b_u,b_v,b_w

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

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

все три вершины различаются, и сумма попарных расстояний между ними нечетна.

Из условия, что никакие две из вершин u, v, w не находятся на расстоянии 1, сле-

дует, что пересечения supp(b_v) ∩ supp(b_u), supp(b_v) ∩ supp(b_w) и supp(b_u) ∩ supp(b_w)

эквивалентны граням булева гиперкуба размерности как минимум на 2 меньше раз-

мерности гиберкуба, а из условия, что вершины u, v, w различаются не менее чем

в трех координатах, следует, что если ровно на 2, то грани, соответствующие разным

пересечениям, не параллельны. Поэтому множества supp(b_w)\ (supp(b_v)∪supp(b_u)),

supp(b_u) \ (supp(b_v) ∪ supp(b_w)), supp(b_v) \ (supp(b_w) ∪ supp(b_u)) являются связными.

Тогда из несогласованности следует недвудольность унитрейда. ▴

Если вершины множества V = {u, v, w} ⊂ Qn3 находятся в общем положении и

сумма попарных расстояний между вершинами множества V четна, то они не могут

различаться только в одной координате, а если они различаются только в двух

координатах, то ранг унитрейда U[f^V ] равен 2.

Предложение 19. Если все попарные расстояния между различными точ-

ками множества V ⊂ Qn3 нечетны, то U[f^V ] - битрейд.

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

v ∈ V , что все функции b_v будут попарно согласованы. При |V | = 3 требуемое сле-

дует из предложения 18. Пусть для множеств V ⊂ Qn3, |V | = k, утверждение верно.

Рассмотрим u ∈ V , находящуюся на нечетном расстоянии от любой точки из V . Вы-

берем функцию b_u согласовано с b_v для некоторого v ∈ V . Тогда из предложения 18

следует, что b_u согласовано с b_w для любого w ∈ V . Таким образом, функции b_v,

v ∈ V , попа∑но согласованы при |V | = k + 1. Если все функции b_v, v ∈ V , согла-

сованы, то

b_v принимает значения только из множества {0, ±1}. Тогда U[f^V ] -

v∈V

битрейд по предложению 15. ▴

4.5. Вычислительные результаты. В этом пункте мы приведем результаты вы-

числений числа N(n) троичных битрейдов с помощью ЭВМ. Удалось вычислить

число различных битрейдов до размерности n = 7, а число неэквивалентных - до

размерности n = 6. Метод перечисления не сильно отличается от прямого перебо-

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

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

ставителю каждого из N^′(n - 1) классов эквивалентности функций, найденных на

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

перебор значений функции с очевидной проверкой выполнимости условия на сумму

по одномерной грани. Полученное число решений умножалось на число представи-

телей в классе эквивалентности первого ретракта. Вычисление N(7) заняло два года

процессорного времени (в расчете на одно ядро процессора); вычисление проводи-

лось на кластере ИВЦ НГУ. Результаты вычислений до n = 6 проверены с помощью

следующей техники двойного подсчета (см. [22]): мощность каждого класса эквива-

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

совпадает с числом представителей, найденных в процессе полного перебора. В таб-

лице приведены следующие величины: N(n) - число различных (включая тожде-

ственно нулевую) {-1, 0, 1}-функций на Qn3, у которых сумма по каждой одномерной

грани равна 0 (т.е. все три значения в грани либо нулевые, либо попарно различные);

N^′(n) - число неэквивалентных таких функций. Последняя колонка отражает сред-

нюю половинную мощность (число элементов -1) битрейда (в скобках приведено

среднеквадратичное отклонение); из этой статистики исключен пустой битрейд.

Далее мы приведем распределение битрейдов по мощностям. Для каждого n ука-

зано число битрейдов (именно двудольных унитрейдов, т.е. число функций будет

вдвое больше) мощности 2ⁿ, 2ⁿ + 2, 2ⁿ + 4, . . . , 2 · 3n-1.

n = 1: 3.

n = 2: 9, 6.

Таблица

N^′(n)

N(n)

ln N(n)

ln ln N(n)

1,098

0,094

1,945

0,665 (+0,571)

3,433

1,233 (+0,567)

2,4 (±0,490)

403

5,998

1,791 (+0,557)

6,448 = 2,539² (±1,188)

29875

10,304

2,332 (+0,541)

17,960 = 2,619³ (±2,342)

32184151

17,286

2,849 (+0,517)

50,527 = 2,666⁴ (±4,776)

25493

1488159817231

28,028

3,333 (+0,483)

142,25 = 2,695⁵ (±10,07)

> 2187260868

6171914027409468739

43,266

3,767 (+0,434)

398,17 = 2,712⁶ (±22,59)

n = 3: 27, 0, 54, 108, 0, 12.

n = 4: 81, 0, 0, 0, 324, 0, 1296, 648, 0, 3888, 2844, 0, 4536, 1296, 0, 0, 0, 0, 0, 24.

n = 5: 243, 0, 0, 0, 0, 0, 0, 0, 1620, 0, 0, 0, 9720, 0, 9720, 3888, 0, 0, 58320, 0, 41580, 77760,

0, 116640, 301320, 0, 259200, 660960, 0, 480816, 1368576, 0, 1156680, 2468880, 0, 1415232,

2721600, 0, 1148040, 2185056, 0, 583200, 816480, 0, 90720, 104976, 0, 10800, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 48.

n = 6: 729, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7290, 0, 0, 0, 0, 0, 0, 0, 58320,

0, 0, 0, 87480, 0, 69984, 23328, 0, 0, 0, 0, 524880, 0, 0, 0, 370980, 0, 1399680, 0, 0, 699840,

2099520, 0, 4811400, 466560, 0, 2799360, 7290000, 0, 16562880, 2099520, 0, 6998400, 15244848,

0, 49968576, 19012320, 0, 46889280, 48114000, 0, 149999040, 48988800, 0, 173560320, 158793696,

0, 431451360, 203303520, 0, 593464320, 402077520, 0, 1226726208, 655983360, 0, 1759957632,

1275108480, 0, 3455693280, 1610681760, 0, 4922674560, 3332579760, 0, 8667868320, 4840793280,

0, 12263996160, 7124630400, 0, 19261521360, 10458292320, 0, 25982259840, 15546805632,

0, 37437240960, 17859890880, 0, 44159904000, 26492909760, 0, 56014493760, 28054486080,

0, 58200653952, 29447634240, 0, 63563901120, 30536701920, 0, 53914973760, 27520508160,

0, 44905723488, 18151205760, 0, 28971976320, 13573863360, 0, 17778852000, 6267067200, 0,

7903992960, 2932269264, 0, 2917632960, 1190894400, 0, 772623360, 243544320, 0, 299531520,

100077120, 0, 33592320, 41290560, 0, 5598720, 6298560, 0, 0, 1179360, 0, 3079296, 3429216, 0,

0, 0, 0, 0, 77760, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 96.

n = 7: 2187, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 30618, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 306180, 0, 0, 0, 0, 0, 0, 0, 612360, 0,

0, 0, 734832, 0, 489888, 139968, 0, 0, 0, 0, 0, 0, 0, 0, 3674160, 0, 0, 0, 0, 0, 0, 0, 2585520,

0, 0, 0, 14696640, 0, 0, 0, 0, 0, 14696640, 0, 22044960, 5878656, 0, 0, 48376440, 0, 9797760,

0, 0, 0, 58786560, 0, 105325920, 9797760, 0, 29393280, 252292320, 0, 48988800, 19595520, 0,

0, 264539520, 0, 258660864, 39191040, 0, 58786560, 849465792, 0, 417384576, 64665216, 0,

118599552, 1102248000, 0, 1026927720, 440899200, 0, 117573120, 3241833840, 0, 1646023680,

881798400, 0, 411505920, 5472048960, 0, 4595639328, 1293304320, 0, 1175731200, 13190234400,

0, 6642881280, 4967464320,

0, 2792361600,

23992754688,

0, 14767655616,

8897345856, 0,

5232003840, 48779617824, 0, 29422673280, 19428958080, 0, 13418032320, 86712135552, 0,

56942131680, 43070952960, 0, 29628426240, 174586285440, 0, 108140326560, 100338860160, 0,

60767667072, 333349188480, 0, 211194390960, 197052549120, 0, 133406300160, 633974103504,

394756649280,

437915782080,

284879669760,

1184769633600,

732195313920,

918265662720,

553710608640,

2237431905072,

1396486980000,

1839642114240,

1166266563840,

4133841505920,

2463586985664,

3699825232320,

2436508916352,

7740828063360,

4633391621376,

7373480647680,

4422630481920,

14095095607296,

9008038009152,

14256009258624,

8787284896320,

25936010563680,

15056472533760,

27127920314880, 0, 17656455116160, 46489296385728, 0, 28595219380560, 51865158776256, 0,

30807273127680, 84076043325120, 0, 53419783072320, 96717020198400, 0, 59173324616448,

151123241747520, 0, 87927292938240, 177969306401280, 0, 112318130615040, 267008385528864,

160800706809792,

321325302945024,

188053645282560,

466481709832320,

291050421480000,

570238841894400,

343218104712000,

806560729743456,

464604287555520,

996450456984192,

620225396784000,

1373638417522560,

816009087669552,

1708948701149760,

982341376894080,

2305937678879520,

1414154728014336,

2868447898270080,

1691741075976000,

3783164938709184,

2145564791750016,

4708186964144640,

2866434717250944,

6089563693805760,

3543718526510400,

7547844801104640,

4235506218558720,

9574787807964288,

5748041164944960,

11803431065489280,

6789801853310400,

14687203311950400,

8100416661309504,

17888868241614720,

10588066580077056,

21840361606638720,

12363491876450400,

26269417255213440,

14285288100787200,

31462082237108160,

18299032850230272,

37233543050766720,

20709927455180544,

43720111582963200,

23313370728464640,

50763763455713280,

28924064989464960,

58412989843236000,

31813638206316480,

66303578484210816,

34565462372004480,

74583100623265920,

41520901293714528,

82545422286942720,

43826073580183104,

90590698165121280,

45970461276122880,

97356175759100160,

52673395505996160,

103853217900781440,

53561231066238336,

108100043912367360,

53128915099827840,

111570541229580480,

58350442395913920,

112097875912081920,

55765902028032000,

111406452367500864,

52657506351233280,

107575556428968768,

53994455165468160,

102377410528901760,

48778189150406400,

94582347577421760,

42669649619928576,

85745409629443200,

40987358888555520,

75337864538158080,

34117558361470080,

64695169565885376,

27623026142341056,

53722349499008448,

24230050550665344,

43420216983171840,

18493690067425440,

33854862632935680,

13546143606925440,

25584444523483776,

10783563464378880,

18568192776336000,

7350295708661760,

13016846960075520,

4835426179046400,

8727631849641600,

3393591789458304,

5646375105114240,

2053100209063680,

3458776067268480,

1173620938855680,

2041794442509696,

728670130929216,

1138311067888512,

375048142382592,

609672959421120,

191348768439360, 307095833018880, 0, 99253170374400, 152237238241536, 0, 46874958318720,

69750838786176, 0, 19948807630080, 31988971163520, 0, 10729375110720, 13802819748480,

3921475057920,

6002269439040,

1657927958400,

2388145213440,

1007425278720,

1073677731840,

520179426144,

484107321600,

144614937600,

245492674560,

205312060800, 136090886400, 0, 89050752000, 73071694080, 0, 20222576640, 49468890240,

0, 45500797440, 28217548800, 0, 15872371200, 12433357440, 0, 3174474240, 2821754880, 0,

12580323840, 4938071040, 0, 3853785600, 1058158080, 0, 0, 529079040, 0, 1410877440, 0, 0,

1162667520, 0, 0, 0, 0, 0, 235146240, 0, 0, 264539520, 0, 0, 0, 0, 0, 0, 0, 0, 12700800, 0, 0, 0, 0,

0, 129330432, 120932352, 0, 71197056, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 520128, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 192.

4.6. Уточнение мощностного спектра битрейдов.

Предложение 20. Пусть rank(U) ≥ 4 и U ⊂ Qn3 - неразложимый унитрейд

размерности n. Тогда |U| > 2,5 · 2ⁿ.

Доказательство. Рассмотрим ранги ретрактов унитрейда U по некоторой

координате. По следствию 1 суммы рангов двух ретрактов не меньше 4.

1) Если унитрейд U имеет пустой ретракт, то по предложению 12 унитрейд U

разложим.

2) Если унитрейд U имеет два ретракта ранга не меньше 3 и еще один ранга не

меньше 1, то |U| > 2 · 2ⁿ + 2n-1 (см. предложение 8 и следствие 3).

3) Пусть теперь все ретракты унитрейда U по любой координате имеют ранг 2 и

rank(U) = 4. Тогда U = U[f], где f = x^a ⊕x^b ⊕x^c ⊕x^e и попарные расстояния между

наборами a, b, c, e не меньше 2. При этом в любом ретракте расстояния между двумя

непересекающимися парами наборов равны 1, поэтому в каждой координате два

набора из a, b, c, e принимают одно значение, а два другие - другое. Без ограничения

общности можно считать, что a_i = 1 и (b_i, c_i, e_i) ∈ {(0, 0, 1), (0, 1, 0), (1, 0, 0)} для всех

i = 1,...,n.

Если какой-то элемент из E = {(0, 0, 1), (0, 1, 0), (1, 0, 0)} не встречается среди

векторов (b_i, c_i, e_i), то унитрейд U[f] разложим. А именно, f = (x^u ⊕ 1)(x^v ⊕ 1) для

некоторых наборов u и v.

Если все элементы множества E встречаются по одному разу, то унитрейд U

эквивалентен унитрейду (1) и имеет ранг 3. Если все элементы множества E встре-

чаются среди векторов (b_i, c_i, e_i) и какой-то из них встречается в координатах i и i^′,

i = i^′, то ретракт по координате i имеет ранг не менее 3. ▴

Для набора векторов W ⊂ Qn3 определим r(W ) как число позиций, в которых все

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

различных значений. Если же найдется позиция, в которой присутствуют все три

различных символа, то положим r(W ) = -∞, т.е. 2r(W) = 0.

⊕

Предложение 21. Пусть f(x) =

x^v, где V ⊂ Qn3. Тогда

v∈V

∑

|U[f]| =

(-2)t-1

2r(W).

t=1

W⊂V, |W|=t

Доказательство. Известна формула, подобная формуле включения-исклю-

чения:

|supp(χA1 ⊕ . . . ⊕ χAs )| =

∑

|A_i| - 2

|A_i ∩ A_j|+22

|A_i ∩ A_j ∩ A_k| - . . . + (-2)s-1|A₁ ∩ . . . ∩ A_s|.

i=j

i=j=k

Как было отмечено в § 3, справедливы равенства U[xv1 ⊕ xv2 ⊕ . . . ⊕ xvs] = U[xv1] ⊕

⊕... ⊕ U[xvs] и U[x^v] = χ

{0,±1}v

Нетрудно видеть, что |{0, ±1}_v1 ∩ . . . ∩ {0, ±1}_vs| = 2r({v1,...,vs}⁾. Тогда требуемая

формула следует из подстановки этого равенства в первую формулу. ▴

Пусть vⁱ ∈ {0, ±1}ⁿ. Рассмотрим матрицу {v^ij} размера 3 × n, строками которой

являются векторы vⁱ ∈ V , |V | = 3. Пусть матрица содержит k₁(V ) столбцов вида acc,

k₂(V ) - cac, k₃(V ) - cca и k₄(V ) столбцов, состоящих из всех различных символов.

Тогда из предложения 21 вытекает

Предложение 22. Пусть V

⊂ Qn3, rank(U[f^V ]) = 3 и все три монома не

совпадают ни в какой координате. Тогда |U[xv1 ⊕ xv2 ⊕ xv3 ]| = 3 · 2ⁿ - 2(2k1(V) +

+2k2(V) + 2k3(V)) + 4δ(k₄(V )), где δ(k) = 0, если k > 0, и δ(k) = 1, если k = 0.

Рассмотрим все возможные битрейды ранга 3 мощности до 2,5·2ⁿ включительно.

Заметим, что если d(u, v) = 1, то x^u ⊕ xv = xw для некоторого w. Поэтому

достаточно рассматривать случай, когда k_i ≤ n-2, где i = 1, 2, 3 и n = k₁+k₂+k₃+k₄.

1. Пусть k₁ = max

k_i = n - 2. Тогда возможны следующие наборы

i=1,2,3

1.1. (k₁, k₂, k₃, k₄) = (n - 2, 2, 0, 0). Битрейд по предложению 17(a). Мощность

битрейда 3·2ⁿ -2(2n-2 +4+1)+4 = 2,5·2ⁿ -6. При n = 3 ранг битрейда равняется 2.

1.2. (k₁, k₂, k₃, k₄) = (n - 2, 1, 1, 0). Не битрейд по предложению 17(b).

1.3. (k₁, k₂, k₃, k₄) = (n - 2, 0, 0, 2). Не битрейд по следствию 6.

1.4. (k₁, k₂, k₃, k₄) = (n - 2, 1, 0, 1). Битрейд по следствию 5. Мощность битрейда

3 · 2ⁿ - 2(2n-2 + 2 + 1) = 2,5 · 2ⁿ - 6. При n = 3 ранг битрейда равняется 2.

2. Пусть k₁ = max

k_i = n - 3. Тогда возможны следующие наборы.

i=1,2,3

2.1. (k₁, k₂, k₃, k₄) = (n - 3, 3, 0, 0). Битрейд по предложению 17(a). Мощность

битрейда 3 · 2ⁿ - 2(2n-3 + 8 + 1) + 4 = 2,5 · 2ⁿ + 2n-2 - 14. При n = 4 битрейд имеет

ранг 2, при n = 5 совпадает со случаем 1.1, при n > 5 мощность больше 2,5 · 2ⁿ.

2.2. (k₁, k₂, k₃, k₄) = (n - 3, 2, 1, 0). Не битрейд по предложению 17(b).

2.3. (k₁, k₂, k₃, k₄) = (n - 3, 2, 0, 1). Битрейд по следствию 5. Мощность битрейда

3·2n -2(2n-3 +4+1) = 2,5·2n +2n-2 -10. При n = 4 совпадает со случаем 1.4, при

n = 5 имеем мощность 2,5 · 2ⁿ - 2, при n > 5 мощность больше 2,5 · 2ⁿ.

2.4. (k₁, k₂, k₃, k₄) = (n - 3, 1, 1, 1). Битрейд по следствию 5. Мощность битрейда

3 · 2ⁿ - 2(2n-3 + 2 + 2) = 2,5 · 2ⁿ + 2n-2 - 8. При n = 4 имеем мощность 2,5 · 2ⁿ - 4,

при n = 5 имеем мощность 2,5 · 2ⁿ, при n > 5 мощность больше 2,5 · 2ⁿ.

2.5. (k₁, k₂, k₃, k₄) = (n - 3, 0, 1, 2). Не битрейд по следствию 6.

2.6. (k₁, k₂, k₃, k₄) = (n - 3, 0, 0, 3). Битрейд по следствию 5. Мощность битрейда

3 · 2ⁿ - 2(2n-3 + 1 + 1) = 2,5 · 2ⁿ + 2n-2 - 4. При n = 3 имеем мощность 2,5 · 2ⁿ - 2,

при n = 4 имеем мощность 2,5 · 2ⁿ, при n > 4 мощность больше 2,5 · 2ⁿ.

Если max

k_i < n - 3, то мощность унитрейда больше 2,5 · 2ⁿ.

i=1,2,3

Теперь рассмотрим разложимые битрейды (см. предложение 11).

3. Если оба сомножителя в декартовом произведении не являются булевыми ги-

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

2ⁿ,⁷2n

и т.д. Поскольку

, мощность не более 2,5 от минимальной, а именно 2,25 · 2ⁿ,

n ≥ 4, имеют только произведения битрейдов мощности вида

2n1 .

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

жения на булев гиперкуб (см. предложение 8), делаем вывод, что справедлива

Теорема 5 (мощности малых троичных битрейдов). В гиперкубе Qn+m3 при

любом m ≥ 0 имеются только следующие битрейды мощности более 2n+m+1 и

не более 5 · 2n+m-1:

i) 2m(2,5 · 2n - 6) при любых n ≥ 4 (1.1 и 1.4);

ii) 2m(2,5 · 25 - 2) при n = 5 (2.3);

iii) 2m(2,5 · 23 - 2) при n = 3 (2.4, 2.6 и 3);

iv) 2m(2,5 · 24) при n = 4 (2.4 и 2.6).

Рассмотрим унитрейд U мощности не более 2,5 · 2ⁿ в Q^nk, k > 3. Если по одно-

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

пересечение с каждой гиперплоскостью имеет мощность 2n-1 или 3·2n-2 (см. предло-

жение 8). Тогда мощность унитрейда U может равняться 2 · 2ⁿ, 2,25 · 2ⁿ или 2,5 · 2ⁿ.

Как показано выше, битрейды мощностей 2,25 · 2ⁿ и 2,5 · 2ⁿ имеются в троичных

гиперкубах. Помимо них в гиперкубах Q^nk при k > 3 имеются битрейды той же

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

U = U^′×{0,1}n-2, где U^′ ⊂ Q2k - цикл длины 8 или 10. В Q³⁴ нетрудно построить би-

трейд мощности 2,25·2³ = 18. Аналогично доказательству предложения 12 нетрудно

получить, что в гиперкубах Qn4, n ≥ 3, имеются битрейды мощности 9 · 2n-2.

Из сказанного выше имеем

Следствие 7 (мощности малых битрейдов). Возможные малые мощности

(не более 2,5 · 2ⁿ) битрейдов в гиперкубах Q^nk при k > 3 исчерпываются тем же

списком, что в теореме 5, и дополнительной возможной мощностью 2n+1.

§5. Число битрейдов

5.1. Нижняя оценка числа битрейдов. Вначале выясним, какова максимальная

мощность подмножества гиперкуба Q^nk, если все попарные расстояния между его

элементами нечетные. Начнем с рассуждений, касающихся набора вершин в евкли-

довом пространстве.

Пусть {v₁, . . . , v_n} ⊂ R^m и квадраты попарных евклидовых расстояний между

векторами v_i и v_j равны d_ij = ∥v_i -v_j∥²². Определителем Кэли- Менгера называется

⎛

⎞

⎜1

d₁₁

d₁₂

... d1n⎟

⎜

⎟

det⎜1

d₂₁

d₂₂

... d2n⎟

= (-1)n+12ⁿ(n!)²(Voln-1)²,

⎝

⎠

dn1

dn2

... d_nn

где Voln-1 - (n-1)-мерный объем выпуклой оболочки множества {v₁, . . . , v_n}. Дока-

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

нографиях [23, § 40; 24, § 4.7]. Нам важно, что при n - 1 > m определитель равен

нулю, поскольку Voln-1 = 0. Из свойств определителя можно вывести следующую

известную лемму.

Лемма. Пусть A ⊂ R^m, все попарные квадраты евклидовых расстояний между

точками множества A целые нечетные и |A| = m + 2. Тогда (m + 2) ≡ 0 mod 4.

Доказательство. Пусть n = |A| = m + 2. Проведем несколько операций сло-

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

рицы из остальных. Получим равенство

⎛

⎞

⎜

-1

c₁₂

... c1n

⎟

⎜

⎟

det⎜

c₂₁

-1

... c2n

⎟

= 0,

⎝

⎠

cn1

cn2

-1

где числа c_ij = d_ij -1 четные. Теперь прибавим сумму столбцов от второго до (n+1)-

го к первому столбцу, а затем сумму строк от второй до (n + 1)-й к первой строке.

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

⎛

⎞

b a₁

a₂

... a

⎜

-1

c₁₂

... c1n

⎟

⎜

⎟

det⎜

a₂

c₂₁

-1

... c2n

⎟

= 0,

⎝

⎠

a_n cn1 cn2 . . .

-1

∑

где a_i = c_ij = c_ji и b = n+ a_i = n+2 c_ij . Любая диагональ матрицы, кроме

i<j

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

тов диагонали кратно 4. Следовательно, произведение элементов главной диагонали

также должно делиться на 4. Тогда n ≡ b ≡ 0 mod 4. ▴

Следствие 8. Пусть A ⊂ R^m и все попарные квадраты евклидовых расстоя-

ний между точками множества A целые нечетные. Тогда |A| ≤ m + 2.

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

m + 3 точек в R^m. Тогда он также содержится в Rm+1 и удовлетворяет условию

леммы, т.е. m + 3 ≡ 0 mod 4. Кроме того, его поднабор из m + 2 точек в R^m также

удовлетворяет условию леммы и m + 2 ≡ 0 mod 4. ▴

Следствие 9. (a) Пусть A ⊂ Q^mk и все попарные расстояния Хэмминга меж-

ду точками множества A нечетны. Тогда |A| ≤ (q - 1)m + 2.

(b) Пусть A ⊂ Q^mk и для любых трех точек из A сумма попарных расстояний

нечетна. Тогда |A| ≤ (q - 1)m + 3.

Доказательство. (a) Закодируем элементы Q_k наборами действительных чи-

сел длины k - 1 с попарными евклидовыми расстояниями 1 (вершинами симплекса).

При этом словам из Q^mk будут сопоставлены векторы (q - 1)m-мерного евклидова

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

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

(b) Рассмотрим произвольную точку a ∈ A и обозначим через A^′ множество то-

чек из A на нечетном расстоянии от a и через A^′′ множество точек из A \ {a} на

четном расстоянии от a. Легко видеть, что расстояние между b и c нечетно, если

b, c ∈ A^′ или b, c ∈ A^′′, и четно, если b ∈ A^′, c ∈ A^′′ или c ∈ A^′, b ∈ A^′′. Всем наборам

из A^′ ∪{a} припишем в конце 0, а наборам из A^′′ припишем в конце 1. Получим мно-

жество B ⊂ Q^mk × Q₂ с попарно нечетными расстояниями. Применяя далее технику,

аналогичную (a), получаем множество точек в евклидовом пространстве с попарно

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

ней координаты достаточно всего одной евклидовой координаты, оценка получается

на 1 больше, чем в случае (a). ▴

Для случая, когда q - степень простого числа, общеизвестно

Предложение 23. В гиперкубе Q^mq при m = qt - ¹

имеется эквидистантный

q-1

код H_t мощности (q - 1)m + 1 = q^t с кодовым расстоянием qt-1, дуальный к коду

Хэмминга.

3^t - 1

Теорема 6. (a) При n =

найдется множество V ⊂ Qn3, такое что для

любого W ⊆ V унитрейд U[f^W ] является битрейдом и |V | = 2n + 1.

(b) Пусть V

⊂ Qn3, n ≥ 3, и для любого W ⊆ V унитрейд U[f^W] является

битрейдом. Тогда rank(U[f^V ]) ≤ 3n.

Доказательство. Утверждение (a) следует из предложений 19 и 23. Докажем

утверждение (b).

Без ограничения общности полагаем, что |V | = rank(U[f^V ]). Положим π(1) = 3 и

π(2) = 6. Обозначим через π(n), n ≥ 3, максимальную мощность множества V ⊂ Qn3,

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

π(n) ≤ 3n по индукции. При n = 3 неравенство можно проверить непосредственно.

Если любая тройка вершин в множестве V находится в общем положении, то тре-

буемое следует из предложения 18(b) и следствия 9(b). Теперь докажем несколько

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

находятся в общем положении.

По предложению 17 любая тройка вершин из V , не находящаяся в общем положе-

нии, должна удовлетворять условию предложения 17(а), т.е. одна из вершин должна

находится между двумя другими. Это свойство будем называть упорядоченностью

тройки.

Рассмотрим максимальный набор v⁰, . . . , v^m ∈ V , такой что любая тройка вершин

из него упорядочена. Без ограничения общности (применяя, если нужно, изометрии

гиперкуба) можно считать³, что v⁰ =

0, vⁱ = (2 . . . 20 . . . 0) и v⁰ ≺ v¹ ≺ . . . ≺ v^m, где

m > 1. Множество координат j, в которых v^mj = 2, обозначим через M. Множество

координат, в которых вершина vⁱ отличается от vi+1, обозначим через M_i.

В множестве V \ V₀, где V₀ = {v⁰, . . . , v^m}, нет вершин, имеющих только 0 и 2

на позициях из множества M, поскольку это противоречит либо максимальности

набора V₀, либо предложению 17.

Пусть найдется вершина u ∈ V , такая что все три тройки вершин {vi1 , vi2 , u},

{vi1 , vi3 , u} и {vi2 , vi3 , u} находятся в общем положении. Поскольку d(vi1 , vi2 ) +

+ d(vi2 , vi3 ) = d(vi1 , vi3 ), нетрудно убедиться, что сумма длин сторон в одном из трех

треугольников четна. По следствию 6 имеем противоречие. Будем ссылаться на это

замечание как на свойство (∗).

Покажем, что вершина u ∈ V \ V₀ содержит 1 только в одном из блоков M_i,

i = 0,...,m - 1. Если вершина u содержит 1 в двух координатах, из M_i и из M_j,

³ Здесь удобнее использовать алфавит {0, 1, 2} с определенным в начале статьи частичным по-

рядком 0 ≺ 2 и 1 ≺ 2.

i < j, то u находится в общем положении с любыми двумя из трех вершин v⁰,vⁱ,v^m.

Получили противоречие по свойству (∗). Обозначим через U_i множество вершин

из V , имеющих хотя бы одну 1 в блоке M_i.

Покажем, что любая вершина u из U_j имеет в координатах каждого блока M_i,

i < j, одинаковые символы, либо нули, либо двойки. Действительно, в противном

случае тройка вершин v⁰, vj-1, u не в общем положении, но не упорядочена, поэтому

по предложению 17(b) не порождает битрейд. Аналогично, любая вершина u из U_j

имеет в координатах каждого из блоков M_i, i > j, одинаковые символы (достаточно

рассмотреть тройку v^m, v^j , u).

Пусть вершина u⁰ ∈ U₀ содержит 2 в координате из некоторого блока M_i, i > 0.

Тогда тройка вершин v¹, v^m, u⁰ не в общем положении и не упорядочены, поэтому по

предложению 17(b) не порождает битрейд. Значит, u⁰ ∈ U₀ содержит только нули

в координатах из любых блоков M_i, i > 0. Покажем, что никакая вершина u^j ∈ U_j ,

j > 0, не содержит 0 в блоке M₀. Действительно,в этом случае вершина u^j находится

в общем положении с любыми двумя из трех вершин u⁰, v¹, v^m. Получили проти-

воречие по свойству (∗). Аналогично, рассмотрев случай, когда вершина um-1 ∈

∈ Um-1 содержит 0 в координате из некоторого блока M_i, i < m-1, а также случаи

когда вершина u^j ∈ U_j , m - 1 > j > 0 содержит символ 0 в блоках M_i, i < j, или

символ 2 в блоках M_i, i > j, приходим к выводу, что единственной непротиворечи-

вой возможностью является следующая: вершина u^j ∈ U_j, j = 0, . . ., m-1, содержит

только двойки в блоках M_i при i < j и только нули в блоках M_i при i > j.

Покажем от противного, что две вершины uⁱ ∈ U_i, u^j ∈ U_j, i < j, не могут иметь

две разные ненулевые k-е координаты при k > |M|. Пусть uⁱ(k) = 1, u^j (k) = 2.

Рассмотрим тройку вершин v⁰, vⁱ, u^j . Она упорядочена (выполнено условие предло-

жения 17(a)), но любая пара из вершин этой тройки находится в общем положении

с вершиной uⁱ. Получили противоречие по свойству (∗).

Мы показали, что uⁱ(k) = u^j (k) или uⁱ(k) = 0, или u^j(k) = 0 при k > |M|. Теперь

покажем, что и случай uⁱ(k) = u^j(k) = 0 для некоторого k > |M| невозможен. Дей-

ствительно, в этом случае тройка вершин vⁱ, uⁱ, u^j, i < j, не в общем положении и не

упорядочена, поэтому по предложению 17(b) не порождает битрейд. Таким образом,

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

группы N₀, . . . , Nm-1 так, что для любой вершины uⁱ ∈ U_i ненулевыми являются

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

Рассмотрим сужение набора вершин W_i = {v⁰, v^m} ∪ U_i на координаты M_i ∪ N_i.

Нетрудно видеть, что некоторая тройка вершин из W_i находится в общем положении

тогда и только тогда, когда в общем положении находится ее сужение на координа-

ты M_i ∪N_i. При этом четность суммы расстояний между вершинами тройки на всех

координатах и только на множестве M_i ∪ N_i совпадают. Если же сужение тройки

вершин на M_i ∪ N_i находится не в общем положении и не упорядочено, то трой-

ка вершин не упорядочена и на множестве всех координат. Следовательно, тройка

вершин из W_i порождает битрейд, только если она порождает битрейд на сужении.

Отсюда следует, что мощность множества W_i = {v⁰, v^m} ∪ U_i не превышает

π(|M_i| + |N_i|), если |M_i| + |N_i| ≥ 3. При |M_i| + |N_i| = 1 неравенство |W_i| ≤ 3 = π(1)

очевидно. Если |M_i| + |N_i| = 2, то неравенство |W_i| ≤ 6 = π(2) нетрудно доказать,

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

N_i и M_i. Тогда по предположению индукции имеем

∑

|V | = |V₀| +

|U_i| ≤ m + 1 +

(π(|M_i| + |N_i|) - 2) ≤ 3n.

▴

i=0

Далее нам понадобится код H_t при q = 3. Будем оценивать снизу число неэквива-

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

яниями для порождения битрейдов. Теорема 6 показывает, что наша оценка почти

исчерпывает возможности этого способа построения множества битрейдов большой

мощности.

Предложение 24. Пусть D - кодовое расстояние множества V_i ⊂ Qn3 и

|V_i| ≤ 2D-3 при i = 1,2. Тогда из эквивалентности унитрейдов U[fV1] и U[fV2]

следует эквивалентность множеств V₁ и V₂.

Доказательство. Пусть унитрейд U[fV ] эквивалентен унитрейду U^′. Тогда

U^′ = U[fV′ ], где множество V^′ эквивалентно множеству V . Однако соответствие

неоднозначно, т.е. в общем случае имеются другие множества W ⊂ Qn3, для которых

U^′ = U[f^W ].

Достаточно показать, что если 2n-2 > |V |2n-D+1, то множество V с кодовым рас-

стоянием D восстанавливается однозначно по унитрейду U[f^V ]. Рассмотрим произ-

вольный подкуб U[x^v]. Имеем v ∈ V , если и только если |U[f^V ] ∩ U[x^v]| ≥ 2ⁿ - 2n-2.

Действительно, поскольку |U[x^w] ∩ U[x^v]| = 2n-d(v,w) для любого w ∈ Qn3, справед-

ливы неравенства

1) |U[f^V ] ∩ U[x^v]| ≥ 2ⁿ - |V |2^n-D при v ∈ V ;

2) |U[f^V ] ∩ U[x^w]| < 2n-1 + |V |2n-D+1 при w ∈ V .

Имеем 2ⁿ - |V |2^n-D ≥ 2n-1 + |V |2n-D+1 при |V | ≤ 2D-3. ▴

Обозначим через sp(v) состав вектора v, например, sp(0, 1, 1, 0, -1) = (2, 2, 1). Бу-

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

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

Предложение 25. Пусть W ⊂ Q^nk - линейное подпространство над GF(k) и

в W имеется базис B, состоящий из векторов с уникальным составом. Тогда в W

имеется не менее 2|W|-dimW-1/|W| неэквивалентных подмножеств векторов.

Доказательство. Рассмотрим подмножества C ⊂ W, которые содержат ну-

левой вектор и базис, т.е. B ⊂ C и

0∈C.Пустьϕπ,a - изометрия, переводящая одно

такое множество C в другое C^′, т.е. ϕ_π,a(C) = π(C) + a = C^′. Поскольку π(0) = 0,

имеем a ∈ C^′ ⊂ W . Рассмотрим базисный вектор v ∈ C ∩ C^′ с уникальным со-

ставом. Из равенства sp(π(v)) = sp(v) и уникальности состава имеем π(v) = v. Из

линейности автотопии π, т.е. из равенства π(αu + βw) = απ(u) + βπ(w), следует,

что π действует тождественно на W . Тогда ϕ_π,a(u) = u + a, где a ∈ W . Очевидно,

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

но 2|W|-dimW-1, причем любой класс эквивалентности подмножеств содержит не

больше элементов, чем |W|. ▴

Рассмотрим порождающую матрицу A кода H_t размерности t > 1 (см. предло-

жение 23). Матрица A содержит единичную подматрицу. Проведем следующее пре-

образование порождающей матрицы A: добавим к ней столбцы единичной матрицы

в количестве 2k-1 копий k-го столбца при k = 2, . . . , t. Линейный код, порожден-

ный преобразованной таким способом матрицей, обозначим через H^′t. Все векторы

кода H_t (за исключением нулевого) имеют одинаковый нечетный вес, поэтому раз-

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

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

составу у пар коллинеарных векторов из H^′t. Неколлинеарные векторы из H^′t име-

ют разный вес по построению. Поэтому код H^′t имеет базис (строки порождающей

матрицы A) из векторов с уникальным составом. Расстояние между любой парой

векторов из кода H_t нечетно. Поскольку в порождающую матрицу A было добавлено

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

из кода H^′t также нечетно. Длина кода H^′t равна 2^t - 2 +3t -¹

Теорема 7 (нижняя граница). Число неэквивалентных битрейдов размерно-

сти n не меньше 2(2/3-o(1))n при n → ∞.

Доказательство. При 2^t - 2 + 3t - ¹

≤ n < 2t+1 -2+3t+1 -¹

рассмотрим

множество H^′t. По предложению 23 кодовое расстояние множества H^′t равно D = 3^t.

3^t+1

Для достаточно больших t имеем |H^′t|2n-D+1 = 3^t2n-D+1 ≤ 3^t22t-1-

< 2n-2.

Из предложения 24 следует, что эквивалентность двух битрейдов U(f^V ) и U(f^W )

равносильна эквивалентности множеств V, W ⊂ H′t. Из предложения 25 следует

требуемая оценка числа таких подмножеств. ▴

⋃

5.2. Верхняя оценка числа битрейдов. Семейство функций A =

A_n, A_n ⊆

n=1

⊆ {f : Q^nk → S}, n ∈ N, будем называть наследственным, если любое множество

функций A_n замкнуто относительно действия изометрий пространства Q^nk на аргу-

менты функций и любой ретракт любой функции из A_n лежит в An-1. Множество

T ⊂ Q^mk называется тестирующим для множества функций A_m, если для любых

f, g ∈ A_m из f|_T = g|_T следует f = g. Множество T является тестирующим для

множества функций A_m тогда и только тогда, когда supp(f - g) ∩ T = ∅ для любых

f и g из A_m, т.е. его дополнение Q^mk \ T не включает носитель разности никаких

двух функций из A_m. Поскольку разность двух характеристических функций неко-

торых комбинаторных конфигураций является битрейдом (в широком смысле), то

поиск тестирующих множеств эквивалентен нахождению множеств, не включающих

битрейдов.

⋃

Предложение 26. Пусть семейство A =

A_n, n ∈ N, наследственное.

n=1

Пусть T ⊂ Q^mk - тестирующее множество для A_m. Тогда декартово произве-

дение тестирующих множеств T^ℓ ⊂ Q^ℓmk является тестирующим для A_ℓm.

Доказательство. Докажем утверждение по индукции. Пусть f|_Tℓ = g|_Tℓ.

Тогда по предположению индукции для любого v ∈ T из f|_T ℓ-1_×{v} = g|_T ℓ-1_×{v}

следует, что f|_Q(ℓ-1)m

= g|_Q(ℓ-1)m

. Следовательно для любого w ∈ Q(ℓ-1)mk

×{v}

имеем f|_{w}×T = g|_{w}×T . Множество {w}×T является тестирующим для ретрактов

на {w} × Q^mk, поскольку семейство A_n наследственное. Тогда f|_{w}×Qm

= g|_{w}×Qm

для любого w ∈ Q(ℓ-1)mk. ▴

Из определения тестирующего множества и предложения 26 следует

⋃

Предложение 27. Пусть A =

A_n - наследственное семейство функций

n=1

и T ⊂ Q^mk - тестирующее множество для A_m. Тогда |A_ℓm| ≤ |S||T|ℓ.

Ниже мы не будем различать унитрейды и их характеристические функции. Се-

мейства битрейдов и унитрейдов являются наследственными (см. предложения 1

и 2). Как следует из формулы (2), тестирующим множеством для семейства троич-

ных унитрейдов (и битрейдов) является любое подмножество в Qn3, индуцирующее

подграф, изоморфный булеву гиперкубу. Пусть T - тестирующее множество для

семейства унитрейдов в Qn3. Поскольку число унитрейдов в Qn3 равняется 22n, из

предложения 27 следует, что |T | ≥ 2ⁿ. Отметим, что для любого тестирующего

множества T его дополнение Qn3 \ T не включает (непустой) унитрейд, и наобо-

рот, если Qn3 \T включает унитрейд, то множество T не является тестирующим для

унитрейдов. Поэтому максимальная мощность подмножества в Qn3, не включающего

унитрейды, равна 3ⁿ - 2ⁿ. Для семейства битрейдов аналогичный вопрос остается

открытым. Ниже мы по существу доказываем, что найдется подмножество в Qn3

мощности больше 3ⁿ - 2ⁿ, не включающее симметрические разности битрейдов.

Предложение 28. Если найдется унитрейд U ⊂ Qm3, характеристическая

функция которого не является суммой (по модулю 2) двух битрейдов, то для би-

трейдов в Qm3 найдется тестирующее множество мощности 2^m - 1.

Доказательство. Каждой вершине v ∈ Qm3 поставим в соответствиеперемен-

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

унитрейд U:

(i) x_a ⊕ x_b ⊕ x_c = 0 - для любой одномерной грани {a, b, c} в Qm3;

(ii) x_v = 0 - для любой v из Qm3 \ U.

Выберем из уравнений типа (i) независимую подсистему (I), а затем из урав-

нений типа (ii) - максимальную независимую подсистему (II), которая независима

и с уравнениями типа (i). Множество решений подсистемы (I) уравнений типа (i)

имеет размерность 2^m, а совместная система - размерность 1, поскольку (см. пред-

ложение 4) ни один унитрейд не является подмножеством другого, т.е. нули одной

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

унитрейда. Поэтому имеется 2^m - 1 уравнений в подсистеме (II), которые задаются

точками v некоторого множества T ⊂ Qm3, |T| = 2^m - 1.

Покажем, что T есть тестирующее множество для битрейдов в Qm3. Пусть две

характеристические функции χ_A и χ_B различных битрейдов A и B совпадают на

множестве T , тогда χ_U = χ_A ⊕ χ_B, поскольку функция χ_A ⊕ χ_B является решением

системы уравнений, задающей унитрейд U. Это противоречит условию. ▴

Вычислительный эксперимент (см. таблицу из п. 4.5) показывает, что число би-

√

трейдов в Q⁷³ не больше, чем 226 =

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

в Q⁷³. Тогда пар битрейдов в Q⁷³ меньше, чем унитрейдов. Таким образом, при n = 7

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

Следствие 10. Число битрейдов в Q7ℓ3 не выше 2α7ℓ, где α = (2⁷ - 1)1/7 < 2.

Пусть β(n) - число битрейдов в Qn3. Тогда β(n + m) ≤ (β(n))2m , m = 1, . . . , 6.

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

n > 7.

Теорема 8 (верхняя граница). Число битрейдов в Qn3 не выше 2α1, где α₁ < 2.

Авторы выражают благодарность Информационно-вычислительному центру Но-

восибирского государственного университета (ИВЦ НГУ) за предоставленные вы-

числительные ресурсы, участникам семинара “N-арные квазигруппы и смежные

вопросы” ИМ СО РАН за плодотворные обсуждения и рецензенту за полезные за-

мечания.

СПИСОК ЛИТЕРАТУРЫ

1. Кротов Д.С. Трейды в комбинаторных конфигурациях // Материалы XII Междуна-

родного семинара “Дискретная математика и ее приложения” им. академика О.Б. Лу-

панова (Москва, 20-25 июня 2016 г.). М.: Изд-во механико-математического факультета

МГУ, 2016. С. 84-96.

2. Hedayat A.S., Khosrovshahi G.B. Trades // Handbook of Combinatorial Designs. Boca

Raton: Chapman & Hall, 2007. P. 644-648.

3. Khosrovshahi G.B., Maimani H.R., Torabi R. On Trades: An Update // Discrete Appl.

Math. 1999. V. 95. № 1-3. P. 361-376.

4. Krotov D.S. On the Gaps of the Spectrum of Volumes of Trades // J. Combin. Des. 2018.

V. 26. № 3. P. 119-126.

5. Krotov D.S., Mogilnykh I.Yu., Potapov V.N. To the Theory of q-ary Steiner and Other-Type

Trades // Discrete Math. 2016. V. 339. № 3. P. 1150-1157.

6. Ghorbani E., Kamali S., Khosrovshahi G.B., Krotov D.S. On the Volumes and Affine Types

of Trades // Electron. J. Combin. (to appear).

7. Cavenagh N.J. The Theory and Application of Latin Bitrades: A Survey // Math. Slovaca.

2008. V. 58. № 6. P. 691-718.

8. Cho S. On the Support Size of Null Designs of Finite Ranked Posets // Combinatorica.

1999. V. 19. № 4. P. 589-595.

Августинович С.В., Соловьева Ф.И. Построение совершенных двоичных кодов после-

довательными сдвигами α-компонент // Пробл. передачи информ. 1997. Т. 33. № 3.

С. 15-21.

10.

Östergard P.R.J. Switching Codes and Designs // Discrete Math. 2012. V. 312. № 3.

P. 621-632.

11.

Потапов В.Н. Спектр мощностей компонент корреляционно-иммунных функций, бент-

функций, совершенных раскрасок и кодов // Пробл. передачи информ. 2012. Т. 48. № 1.

C. 54-63.

12.

Krotov, D.S., Potapov, V.N., Sokolova, P.V. On Reconstructing Reducible n-ary Quasi-

groups and Switching Subquasigroups // Quasigroups Relat. Syst. 2008. V. 16. № 1.

P. 55-67.

13.

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

кретная математика. 2012. Т. 24. № 1. С. 60-69.

14.

Riener H., Ehlers R., Schmitt B.O., De Micheli G. Exact Synthesis of ESOP Forms //

Advanced Boolean Techniques: Selected Papers from the 13th International Workshop on

Boolean Problems. Cham: Springer, 2020. P. 177-194.

15.

Винокуров С.Ф., Казимиров А.С. О сложности одного класса булевых функций // Изв.

Иркутского гос. ун-та. Сер. Математика. 2010. Т. 3. № 4. С. 2-6.

16.

Потапов В.Н. Многомерные латинские битрейды // Сиб. мат. журн. 2013. Т. 54. № 2.

C. 407-416.

17.

Krotov D.S., Potapov V.N. n-ary Quasigroups of Order 4 // SIAM J. Discrete Math. 2009.

V. 23. № 2. P. 561-570.

18.

Ellenberg J.S., Gijswijt D. On Large Subsets of F^nq with No Three-Term Arithmetic Pro-

gression // Ann. Math. (2). 2017. V. 185. № 1. P. 339-343.

19.

Потапов В.Н. О булевых функциях, почти уравновешенных в гранях // Прикладная

дискретная математика. Приложение. 2012. № 5. C. 23-25.

20.

Kasami T., Tokura N. On the Weight Structure of Reed-Muller Codes // IEEE Trans.

Inform. Theory. 1970. V. 16. № 6. P. 752-759.

21.

Kasami T., Tokura N., Azumi S. On the Weight Enumeration of Weights Less than 2.5d of

Reed-Muller Codes // Inform. Control. 1976. V. 30. № 4. P. 380-395.

22.

Kaski P.,

Östergard, P.R.J. Classification Algorithms for Codes and Designs. Berlin:

Springer, 2006.

23.

Blumenthal L. Theory and Applications of Distance Geometry. Oxford: Clarendon Press,

1953.

24.

Pak I. Lectures on Discrete and Polyhedral Geometry. Book draft, 2010. Available at http:

//www.math.ucla.edu/~pak/book.htm.

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

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

Потапов Владимир Николаевич

24.12.2018

Институт математики им. С.Л. Соболева СО РАН, Новосибирск

После доработки

krotov@math.nsc.ru

19.09.2019

vpotapov@math.nsc.ru

Принята к публикации

12.11.2019