Изометричные отображения множества всех булевых функций в себя, сохраняющие самодуальность и отношение Рэлея | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/16

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

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

Isometric mappings of the set of all boolean functions into itself which preserve self-duality and the rayleigh quotient.pdf Булевой функцией от n переменных называется любое отображение f : Fn^F2. Скалярным произведением (x,y) двух векторов x = (x1, x2,..., xn) Е Fn, y = n = (y1, y2,..., yn) Е Fn называется значение ф x^. Весом Хэмминга wt(x) вектора i=1 x Е Fn называется количество единиц в нём. Расстояние Хэмминга dist(f, g) между булевыми функциями f, g от n переменных - число двоичных векторов длины n, на которых эти функции принимают различные значения. Через On обознается ортогональная группа On = {L Е GL(n, 2) : LLT = /nj , где LT - операция транспонирования L; In - единичная матрица порядка n над полем F2 [1]. Преобразованием Уолша - Адамара булевой функции f от n переменных называется целочисленная функция Wf : Fn ^ Z, заданная равенством Wf (y) = Е (-1)f(x)®, y Е Fn. ^gfj Булева функция f от чётного числа переменных n называется бент-функцией, если |Wf (y)| = 2n/2 для каждого y Е Fn [2]. Для множества бент-функций от n переменных используется обозначение Bn. Для каждой f Е Bn однозначным образом определяется дуальная к ней бент-функция f Е Bn, значения которой находятся из соответствия Wf (y) = (-1)/(y)2n/2 для каждого y Е Fn. Бент-функция f называется самодуальной Исследование выполнено при финансовой поддержке РФФИ (проекты №18-07-01394 и 18-3100374). (антисамодуальной), если / = / (соответственно / = /ф 1). Множества самодуальных и антисамодуальных бент-функций от n переменных обозначаются через SB+ (n) и SB-(n) соответственно [3]. Открытой проблемой является полная характеризация и описание класса самодуальных бент-функций. Этому и другим вопросам, связанным с самодуальными бент-функциями, посвящён ряд работ (C. Carlet, L. E. Danielson, M. G. Parker, P. Sole, X. Hou, T. Feulner, L. Sok, A. Wassermann и др.). В частности, в работе [4] приведена аффинная классификация самодуальных бент-функций от 2, 4,6 переменных и всех квадратичных самодуальных бент-функций от 8 переменных относительно преобразования, сохраняющего самодуальность. В [3] приведена классификация всех квадратичных самодуальных бент-функций. Аффинную классификацию квадратичных и кубических самодуальных бент-функций от 8 переменных относительно преобразования, сохраняющего самодуальность, можно найти в [5]. В [6] найден полный спектр расстояний Хэмминга между самодуальными бент-функциями из класса Мэйорана - МакФарланда. Согласно [4, 7], отношением Рэлея (the Rayleigh quotient) S/ булевой функции / от n переменных называется число Sf = Е (-1)/(ж)ф/= Y, (-1)/(y)W/(y). Из соотношения dist (// = Г-1 - 2n1TTS/ следует, что отношение Рэлея полностью характеризует расстояние Хэмминга между бент-функцией / S Bn и дуальной к ней функцией / 6 Bn. Известно [4], что абсолютное значение S/ не превосходит 23n/2, при этом данная оценка достигается только на самодуальных бент-функциях (+23га/2) и антисамодуальных бент-функциях (-23га/2). Отображение всех булевых функций от n переменных в себя называется изомет-ричным, если оно сохраняет расстояние Хэмминга для каждой пары функций. Известно, что каждое такое отображение однозначно представляется в виде /(x) /(n(x)) ф g(x), где п - перестановка на множестве F^; g - булева функция от n переменных [8]. Единственным изометричным отображением множества всех булевых функций от n переменных в себя, оставляющим множество на месте, является композиция аффинного преобразования координат и прибавления аффинной функции от n переменных [9]. Всюду далее предполагается, что n - чётное натуральное число. В работе [5] (см. также [4]) доказано, что отображение всех булевых функций от n переменных в себя, имеющее вид /(x) -> / (L (x ф c)) ф (c, x) ф d, где L 6 On; c 6 F^; wt(c) -чётное число; d 6 F2, сохраняет самодуальность бент-функции. Нетрудно видеть, что все отображения данного вида являются изометрич-ными. В [7] приведены примеры отображений всех булевых функций от n переменных в себя, сохраняющих максимальную нелинейность и отношение Рэлея. Показано, что для каждой бент-функции / 6 Bn и любых L 6 On,c 6 F^,d 6 F2 для бент-функций g, h Е Bn, определённых как g(x) = f (Lx) ф d и h(x) = f (x ф c) ф (c, x), справедливо Sg = Sf и Sh =(-1)Sf. В [3] отмечено, что отображение всех булевых функций от n переменных в себя, имеющее вид f (x) -> f (x ф c) ф (c,x) , где c Е Fn, wt(c) -нечётное число, определяет биекцию между множествами SB+(n) и SB-(n). Очевидно, что такое отображение сохраняет расстояние Хэмминга. Частный случай отображения данного вида - при c = (1,0, 0,..., 0) Е Fn - ранее был рассмотрен в работе [4], на основании чего был сделан вывод о том, что между множествами SB+(n) и SB-(n) существует взаимно-однозначное соответствие. В настоящей работе получено обобщение известных результатов в рамках класса изометричных отображений. Пусть ^ - изометричное отображение всех булевых функций от n переменных в себя, то есть f (x) f (n(x)) ф g(x), где п - перестановка на множестве Fn; g - булева функция от n переменных. Теорема 1. Следующие условия эквивалентны: - ^ сохраняет самодуальность; - ^ сохраняет антисамодуальность; - ^ сохраняет отношение Рэлея каждой булевой функции от n переменных; - n(x) = L (x ф c) и g(x) = (c, x) ф d, где L Е On; c Е Fn; wt(c) - чётное число; d Е F2. Следствие 1. Отображение ^ сохраняет максимальную нелинейность и расстояние Хэмминга между каждой бент-функцией и дуальной к ней тогда и только тогда, когда n(x) = L (x ф c) и g(x) = (c, x) ф d, где L Е On; c Е Fn; wt(c) - чётное число; d Е F2. Теорема 2. Следующие условия эквивалентны: - ^ определяет взаимно-однозначное соответствие между множествами SB+(n) и SB-(n); - ^ меняет знак отношения Рэлея каждой булевой функции от n переменных; - n(x) = L (x ф c) и g(x) = (c, x) ф d, где L Е On; c Е Fn; wt(c) -нечётное число; d Е F2. Из полученных результатов следует, что более общего подхода к эквивалентности самодуальных бент-функций на основе изометричных отображений, чем предложенный в работах [4, 5], не существует.

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

булева функция, изометричное отображение, самодуальная бент-функция, отношение Рэлея, Boolean function, isometric mapping, self-dual bent function, Rayleigh quotient

Авторы

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

Ссылки

Janusz G. J. Parametrization of self-dual codes by orthogonal matrices // Finite Fields Appl. 2007. No. 13(3). P. 450-491.
Rothaus O. On bent functions // J. Combin. Theory. Ser. A. 1976. No. 20(3). P. 300-305).
Hou X.-D. Classification of self dual quadratic bent functions // Des. Codes Cryptogr. 2012. No. 63 (2). P. 183-198.
Carlet C., Danielson L. E., Parker M. G., and Sole P. Self dual bent functions // Int. J. Inform. Coding Theory. 2010. No. 1. P. 384-399.
Feulner T., SokL., Sole P., and Wassermann A. Towards the classification of self-dual bent functions in eight variables // Des. Codes Cryptogr. 2013. No. 68(1). P. 395-406.
Куценко А. В. Спектр расстояний Хэмминга между самодуальными бент-функциями из класса Мэйорана - МакФарланда // Дискретный анализ и исследование операций. 2018. Т. 25. №1. C. 98-119.
Danielsen L. E., Parker M. G., and Sole P. The Rayleigh quotient of bent functions // LNCS. 2009. V. 5921. P. 418-432.
Марков А. А. О преобразованиях, не распространяющих искажения // Избранные труды. Т. II. Теория алгорифмов и конструктивная математика, математическая логика, информатика и смежные вопросы. М.: МЦНМО, 2003. С. 70-93.
Tokareva N. N. The group of automorphisms of the set of bent functions // Discr. Math. Appl. 2010. No. 20 (5). P. 655-664.
 Изометричные отображения множества всех булевых функций в себя, сохраняющие самодуальность и отношение Рэлея | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/16

Изометричные отображения множества всех булевых функций в себя, сохраняющие самодуальность и отношение Рэлея | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/16