Hypotheses for the number of bent functions.pdf Проблема определения числа всех бент-функций-булевых функций от четногочисла переменных, максимально удаленных от множества аффинных функций, - яв-ляется одной из фундаментальных в этой области. Известно, что разрыв между су-ществующими нижней и верхней оценками этого числа огромен. В работе исследуетсяроль класса итеративных бент-функций в решении этой задачи и формулируется сериягипотез о числе бент-функций.Бент-функция g от n переменных называется итеративной бент-функцией, еслиона получена из четырех бент-функций fo, f 1, f2, f3 от n - 2 переменных с помощьюконструкцииg ( 0 0 , x ) = / О ^ g( 0 1 , x ) = f 1 ( x ) g( 1 0 , x ) = f 2 ( x ) , g( 1 1 , x ) = f 3 ( x ) .При этом необходимым и достаточным условием того, чтобы определенная такимобразом булева функция g была бент-функцией, является выполнение равенстваf0 + /1 + f2 + f3 = 1, где f обозначает дуальную бент-функцию. Этот способ былпредложен А. Канто и П. Шарпин в работе [1], см. также [2].Пусть Bn и BIn обозначают соответственно множество всех бент-функций и мно-жество всех итеративных бент-функций от n переменных. В [2, 3] показано, что|Bn+2| ^ |BIn+21 ^ Y1 Y1 I (Bn + f') п (Bn + f " ) |. Продолжим начатое исследо-/ 'eBn/"eBnвание.Пусть Xn - множество всех булевых функций от n переменных, которые можнопредставить в виде суммы двух бент-функций, т. е.Xn = U (Bn + f )./ eBnКратностью покрытия булевой функции h назовем число бент-функций f от n пере-менных, таких, что h принадлежит множеству Bn + f. Обозначим кратность функциичерез m(f). Несложно заметить, что Y1 m(f) = |Bn|2./ eXnДоказаны следующие утверждения.Теорема 1. Справедливо |BZn+2| = m(f)2./ eXnТеорема 2. Выполняется |BZn+2| ^ |Bn|4/|Xn |.Таким образом, из задачи нахождения числа всех итеративных бент-функций от nпеременных возникают следующие вопросы.Открытые вопросы. Какие булевы функции от n переменных могут быть пред-ставлены в виде суммы двух бент-функций? Сколько различных таких представленийимеет булева функция? Как распределены числа m(f)?Заметим, что поскольку степень каждой бент-функции от n переменных не вы-ше n/2, то множество Xn также содержит только функции степени не выше n/2, т.е.|Xn| ^ 21+n+( n )++( n% ) = 22 n - 1 +К nn2 ). Проверено, что при n = 2, 4,6 множе-ство Xn содержит все булевы функции степени не выше n/2. Сформулируем следую-щую сильную гипотезу.Гипотеза 1. Каждая булева функция от n переменных степени не больше n/2представима в виде суммы двух бент-функций от n переменных.Если гипотеза 1 верна, то из нее практически сразу следует справедливостьследу-ющей гипотезы об асимптотике числа всех бент-функций.Гипотеза 2. Число всех бент-функций от n переменных асимптотически равно22 n/2 ), где c, d - некоторые константы, причем 1 ^ c ^ 2.Гипотеза 2 означает, что число всех бент-функций скорее ближе к тривиаль-ной верхней оценке их числа (в грубом приближении 22n), чем к нижней (около22(n/2) + log(n-2)-1 )С другой стороны, возникают гипотезы, отражающие роль множества итеративныхбент-функций в классе всех бент-функций. Проверено, что при малых n, равных 2, 4, 6,оценка теоремы 2 становится всё более точной.Например, для последнего случая (n = 6) с привлечением методов Монте-Карловычислено с малой погрешностью значение |$I8|, а именно показано, что с вероятно-стью 0,999 выполняется 287'36 < |BI8| < 287'38, тогда как по оценке теоремы 2 имеем|BXs| > 197004 891331091000 000 000 000 « 287'35.Гипотеза 3. Оценка теоремы 2 асимптотически точна, т. е. справедливоlog log |BIn+2| = 1n-mo loglog(|Bn|4/|Xn|) .Сформулируем также следующую гипотезу, смысл которой неформально сводитсяк тому, что «поведение» класса всех бент-функций определяется лишь итеративнымибент-функциями.Гипотеза 4. Класс BIn является базовым классом в множестве Bn, т. е. выполня-етсяl ogl o g |BIn| = 1n loglog |Bn|

Скачать электронную версию публикации