Нижняя оценка мощности наибольшего метрически регулярного подмножества булева куба | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/4

Нижняя оценка мощности наибольшего метрически регулярного подмножества булева куба

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

Lower bound on the size of the largest metrically regular subset of the boolean cube.pdf Рассмотрим Fn - пространство двоичных векторов длины n. Расстояние Хэммин-га d(x,y) между двумя векторами £ Fn равно количеству координат, в которых эти векторы различаются. Пусть X С Fn - произвольное множество, y G Fn - произвольный вектор. Расстояние от y до X определяется как d(y, X) = min d(y, x). Радиусом покрытия множества X x€X называется d(X) = maxd(z,X). zefj Рассмотрим множество Y = {y G Fn : d(y,X) = d(X)} векторов, находящихся на максимальном расстоянии от X. Это множество называется метрическим дополнением [1] множества X и обозначается X. Если X = X, то множество X называется метрически регулярным. Задача исследования максимальных и минимальных (по мощности) метрически регулярных множеств возникает на пути изучения бент-функций, множество которых является метрически регулярным [2]. Бент-функции часто используются в криптографии из-за высокой нелинейности [3], обеспечивающей повышенную устойчивость шифров к криптографическим атакам, однако многие связанные с ними задачи остаются открытыми. Например, неизвестно точное количество бент-функций в общем случае, а существующие верхняя и нижняя оценки значительно разнятся по порядку. В работе изучается особый подкласс метрически регулярных множеств - строго метрически регулярные множества. Множества A,B, такие, что A = B, B = A и d(A) = d(B) = d, называются строго метрически регулярными, если для любого вектора x G Fn выполнено равенство d(x, A) + d(x, B) = d. Получены итеративные конструкции строго метрически регулярных множеств. Теорема 1. Пусть A,B - пара строго метрически регулярных множеств, являющихся метрическими дополнениями друг друга. Тогда C = A U B также является строго метрически регулярным множеством. Обобщение данной конструкции (теорема 2) позволяет получать больше строго метрически регулярных множеств с различными радиусами покрытия из известной пары строго метрически регулярных множеств A, B. Теорема 2. Пусть A, B - пара строго метрически регулярных множеств, являющихся метрическими дополнениями друг друга с радиусом покрытия d. Обозначим Ak = {x G Fn : d(x, A) = k}, k = 0,1,..., d. Пусть i1,... , is - последовательность чиs сел, 0 ^ i1 < i2 < ... < is-1 < is ^ d. Тогда объединение C = (J Aik является строго k=1 метрически регулярным множеством тогда и только тогда, когда существует число r > 0, такое, что выполняются все следующие условия: 1) для любого k G {1,..., s - 1} разница (ik+1 - ik) равна 1, 2r или 2r + 1; 2) для любого k G {2,... , s - 1} как минимум одна из разниц (ik+1 - ik), (ik - ik-1) больше единицы; 3) i1 равно либо r, либо 0, и если i1 = 0 и s > 1, то i2 - i1 = 2r или 2r + 1; 4) is равно либо d - r, либо d, и если is = d и s > 1, то is - is-1 = 2r или 2r + 1. Число r является радиусом покрытия множества C. Получены формулы, позволяющие вычислить количество множеств, получаемых с помощью обобщённой конструкции. Теорема 3. Пусть A, B - пара строго метрически регулярных множеств, являющихся метрическими дополнениями друг друга с радиусом покрытия d. Тогда количество Gr (d) различных строго метрически регулярных множеств с радиусом покрытия r, которые можно получить с помощью теоремы 2 из пары A,B, вычисляется по следующим реккурентным формулам: Gr (d) = Gr (d - r) + Gr (d - r - 1), если d > r, Gr (r) = 2, Gr(d) = 0, если 0 ^ d < r. При помощи конструкции из теоремы 2, применённой к паре граней в пространствах соответствующих размерностей, построено семейство множеств {Y^} (n ^ 2d), имеющих большую (относительно мощности всего пространства) мощность. Индекс n отражает размерность булева куба, в котором лежит соответствующее множество, а d - его радиус покрытия. На основе сферы радиуса d в пространстве F^ построено семейство множеств {Zfy (также для n ^ 2d). Вычислив точные размеры множеств семейств (либо оценив их снизу), получаем нижнюю оценку на мощность наибольших метрически регулярных множеств. Теорема 4. Пусть A - наибольшее метрически регулярное множество с радиусом покрытия d в булевом кубе размерности n (n ^ 2d), r - остаток от деления n +1 на 2d + 1 Тогда |A| s 'Ч'2""^d), 2" (- у=?т)}• Заметим, что при достаточно больших d, n первое число приблизительно равно 1/Vnd от мощности булева куба, второе - 2/(2d + 1) от мощности булева куба.

Ключевые слова

metric complement, metrically regular set, метрическое дополнение, метрически регулярное множество

Авторы

ФИООрганизацияДополнительноE-mail
Облаухов Алексей КонстантиновичНовосибирский государственный университетстудентoblaukhov@gmail.com
Всего: 1

Ссылки

Cusick T. W. and Stanica P. Cryptographic Boolean Functions and Applications. Academic Press, 2017. 288 p.
Tokareva N. Duality between bent functions and affine functions // Discr. Math. 2012. V. 312. No. 3. P. 666-670.
Облаухов А. К. О метрическом дополнении подпространств булева куба // Дискретный анализ и исследование операций. 2016. Т. 23. №3. С. 93-106.
 Нижняя оценка мощности наибольшего метрически регулярного подмножества булева куба | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/4

Нижняя оценка мощности наибольшего метрически регулярного подмножества булева куба | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/4