Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Любая бент-функция имеет четное число переменных и
Доказательство.
По определению бент-функции, . Если нечетно, то не является целым числом и, соответственно, не может быть коэффициентом Уолша.
Докажем теперь утверждение о степени бент-функции.
Воспользуемся формулой для нахождения коэффициентов многочлена Жегалкина булевой функции :
где а все единичные координаты вектора имеют номера .
Тогда эту сумму можно представить как
где – подфункция функции .
Если мы докажем, что при вес этой подфункции четен, то утверждение будет доказано (так как четное число по модулю 2 дает нуль, а значит, коэффициент при -й степени многочлена Жегалкина равен нулю).
Как известно, любую булеву функцию можно разложить в ряд Фурье:
где – коэффициент Фурье.
Возьмем число и рассмотрим векторы следующего вида:
Тогда
Возьмем – подфункцию функции . Имеем:
Очевидно, что Тогда можно выразить коэффициенты Фурье функции через коэффициенты Фурье функции :
Так как коэффициенты Фурье любой булевой функции (в том числе и ) находятся по формуле
то
Итак, чтобы найти вес функции , нам надо вычислить
Ранее мы видели (теорема 3.9 главы 3 в учебнике Фомичева), что
Если – бент-функция, то все ее коэффициенты Уолша равны . Соответственно, в таком случае
Из равенства находим:
Пусть . Рассмотрим два варианта.
1) . Тогда . При подстановке этих значений в формулу мы получаем
То есть вес функции нечетен, а значит, любая бент-функция от двух переменных имеет степень 2.
2) . Видно, что четность формулы зависит только от четности суммы. Если , то каждое слагаемое этой суммы равно . Всего слагаемых штук – а это четное число, так как . Следовательно, вся сумма четна. Пусть теперь . Тогда каждое слагаемое суммы, очевидно, четное число, и вся сумма будет четной. Таким образом, в обоих случаях мы получили четную сумму.
Итак, при любом (разумеется, четном) и любом нулевой коэффициент Фурье функции (являющейся подфункцией бент-функции ) четен. А значит, четен и вес функции . Итак, коэффициент в многочлене Жегалкина нашей бент-функции равен нулю.
Ясно, что все вышеприведенное доказательство не зависит от выбора переменных для подфункции, то есть будет справедливым и для подфункции . Значит, все коэффициенты при -й степени в многочлене Жегалкина равны нулю. Так как это верно для любого , то у бент-функции нет степеней выше , разве что если (тогда степень бент-функции равна 2). Доказательство закончено.
Все бент-функции имеют максимальную нелинейность и, соответственно, минимальную линейность:
Кроме того, утверждается, что другие булевы функции не достигают этих пределов.
Доказательство.
Как уже было доказано, нелинейность любой булевой функции равна:
Видно, что чем больше (по модулю) максимальный коэффициент Уолша булевой функции , тем меньше ее нелинейность. Поэтому максимальную нелинейность имеют только те функции, у которых максимальный коэффициент Уолша — наименьший среди всех булевых функций от переменных. Попробуем выяснить, какое значение может иметь такой коэффициент.
Равенство Парсеваля говорит о том, что сумма квадратов всех коэффициентов Уолша равна . Тогда модуль максимального коэффициента Уолша булевой функции не может быть меньше числа , потому что если предположить, что то, и тогда выполнится — нарушение равенства Парсеваля.
Итак, мы нашли нижнюю границу для модуля максимального коэффициента Уолша любой булевой функции — это число . Таким образом, мы получаем верхнюю границу для нелинейности любой булевой функции :
Очевидно, чтобы функция имела такую нелинейность, модуль ее максимального коэффициента Уолша должен быть равен . В таком случае число должно быть четным. Кроме того, модули всех других коэффициентов Уолша не могут быть меньше , потому что иначе нарушится равенство Парсеваля. В то же время они не могут быть больше , потому что мы выбрали его за максимум. Итак, модули всех коэффициентов Уолша функции равны , а сами коэффициенты, очевидно, равны . Следовательно, — бент-функция.
Обратно, если — бент-функция, то модуль любого ее коэффициента Уолша равен , и, следовательно, ее нелинейность будет равна полученной выше верхней границе.
Используя связь , убеждаемся в справедливости утверждения для линейности.
Класс бент-функций — это единственный класс функций, удовлетворяющий , то есть — сбалансированная функция.
Доказательство.
Пусть функция удовлетворяет , тогда является сбалансированной функцией .
В таком случае
Итак, если функция удовлетворяет , то при любом ненулевом векторе ее автокорреляция равна нулю.
Теперь воспользуемся утверждением 1 из прошлой части доказательств:
В сумме слева равны нулю все слагаемые, кроме .
Из определения автокорреляции следует, что для любой булевой функции . Следовательно, все сумма равна единице, то есть
Итак, всякая функция, удовлетворяющая , является бент-функцией.
Обратно, если — бент-функция, то воспользуемся утверждением 2 из предыдущей части доказательств:
Выносим из-под суммы как константу ( ведь бент-функция!). Тогда сумма будет равна нулю при любом ненулевом векторе . Итак, мы получили, что для любого ненулевого . Воспользуемся утверждением 5 из предыдущей части доказательств и получим то, что нужно.
Бент-функции принимают раз значение 1.
Доказательство.
Как было показано в утверждении 1 этой части доказательств, Используя связь , находим
Модуль коэффициента корреляции любой бент-функции имеет постоянное значение:
Доказательство.
Если , то Доказательство закончено.