Вопросы к зачету часть3 (Вопросы к зачету (ответы)), страница 7

Теорема 2. Группа симметрий функции 0 совпадает с аффинной группой. AGL(n).

ДОКАЗАТЕЛЬСТВО содержит два пункта.

а) Покажем, что . Пусть и выбрана произвольная функция . Вычислим алгебраическую нормальную форму для , используя ее связь с . B некоторые нелинейные члены могут исчезать, а некоторые появляться как новые. Однако, члены некоторой степени в не могут в порождать члены степени выше, чем . Отсюда следует, что

.

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

Имеем

.

Из приведенных формул следует, что

.

Следовательно, .

б) Покажем теперь, что .

Пусть . Тогда при действии на имеем нелинейную компоненту и из следует, что . Стало быть , в то время как 0(f)=1. Отсюда вытекает, что .

Из теоремы 2 следует, что другие критерии нелинейности для случая, когда расстояние до функций с порядком нелинейности, не превосходящим k , также остаются инвариантными при действии элементов из AGL(n).

9. Совершенно нелинейные функции.

Булева функция называется совершенно нелинейной функцией, если для каждого ненулевого вектора значения функции f(x+a) и f(x) совпадают точно для половины векторов .

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

Для произвольной функции расстояние до линейных структур можно вычислить следующим образом. Пусть - ненулевой вектор. Тогда пространство можно разбить на неупорядоченных пар вида (x, x+a). Обозначим через число элементов множества пар вида (x, x+a), для которых f(x)=f(x+a), а через - число таких пар множества , что .

Любая булева функция может быть получена из функции f путем изменения соответствующего множества f – значений. Таким способом функцию f можно преобразовать в функцию с линейной структурой a путем изменения f - значений либо для x либо для x+а для пары (x, x+a) , или путем изменения f - значений, либо x, либо x+a для пары (x, x+a) . Таким образом, значений можно изменить так, чтобы получить функцию g с линейной структурой такой, что для всех x, а значений изменить так, что получить функцию g с линейной структурой такой, что для всех x. Для того чтобы получить любую другую функцию с такой же линейной структурой необходимо изменить по крайней мере значений. Следовательно, есть расстояние функции f до ближайшей функции с линейной структурой . Заметим, что n зависит от вектора , то есть .

Отсюда расстояние до линейных структур определяется формулой .

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

Теорема 3. Класс совершенно нелинейных функций совпадает с классом функций, имеющих максимальное расстояние до линейных структур равное 2^n-2 .

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

Рассмотрим преобразование Уолша-Адамара для совершенно нелинейной функции . По определению имеем:

.

Из этого равенства следует, что

.

Пользуясь этими равенствами, с учетом соотношения

находим, что

. ( * )

Теорема 4. Булева функция является совершенно нелинейной тогда и только тогда, когда матрица , строки и столбцы которой помечены векторами пространства и элементы имеют вид

является матрицей Адамара.

Из равенства (*) следует, что . Кроме того, скалярное произведение -й и -й строк удовлетворяет равенствам

в силу соотношения ортогональности для преобразований Уолша-Адамара. Так как ортогональность строк, выраженная предыдущим равенством, является характеристическим свойством для матриц Адамара, то достаточность теоремы 4 доказана.

Обратно, если , то т.е. функция является совершенно нелинейной. Ортогональность строк матрицы Адамара сводится к соотношению ортогональности для преобразований Уолша-Адамара.

Функция , для которой преобразование Уолша-Адамара удовлетворяет условию (*), называется бент-функцией. Таким образом, справедлива следующая

Теорема 5. Класс совершенно нелинейных функций совпадает с классом бент-функций.

Из равенства (*) следует, что бент-функции могут существовать только для четных n . Из свойств совершенно нелинейных функций следует, что порядок нелинейности бент-функции не превосходит n/2.

10. Расстояние до аффинных функций и корреляция.

Пусть - произвольная линейная функция и . Тогда из определения преобразования Уолша-Адамара следует, что

_.

Отсюда следует, что

,

где означает расстояние Хэмминга. Расстояние до соответствующей аффинной функции расстояние вычисляется по формуле

,

так как в этом случае преобразование Уолша-Адамара равно .

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

.

.

Из равенства (*) следует, что для совершенно нелинейных функций расстояние d(f) до ближайшей аффинной функции равно d(f)= .

Если не является совершенно нелинейной функцией, то из равенства Парсеваля следует, что . Следовательно, в этом случае d(f)< и, стало быть, эта функция ближе к множеству аффинных функций, чем совершенно нелинейная функция. Это показывает, что для класса совершенно нелинейных функций достигается оптимум не только по отношению к расстояниям до линейных структур, но по отношению к расстояниям до всех аффинных функций.

Итак, доказана следующая теорема.

Теорема 6. Класс совершению нелинейных функций совпадает с классом функций, для которых достигается максимум расстояния до аффинных функций, равный .

В начале пункта 10 указывалась формула

.

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

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

.

Для в соответствии с равенством

имеем .

Из этого равенства и (*) следует, что абсолютная величина корреляции между совершенно, нелинейной функцией и любой аффинной функцией представляет собой постоянную, равную .

Если же функция не является совершенно нелинейной, то ее корреляция с аффинной функцией больше по абсолютной величине. Отсюда вытекает следующая

Теорема 7. Класс совершенно нелинейных функций совпадает с классом функций, для которых корреляция со всеми аффинными функциями достигает минимума.

Отметим, что корреляция булевой функции с нулевой функцией определяет степень сбалансированности . Ясно, что совершенно нелинейная функция никогда не может быть сбалансированной. Вместе с тем, отметим, что ее отклонение от сбалансированности, равное быстро стремится к нулю, когда n неограниченно возрастает. То же самое имеет место и для корреляции с любой другой аффинной функцией.

11. Булевы функции от нечетного числа аргументов.

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

При нечетном n для булевой функции рассмотрим функции такие, что и . Обозначим через и - преобразования Уолша-Адамара функций и соответственно. Для преобразования Уолша-Адамара функции при положим при и при . Таким образом . Тогда имеют место равенства: , .

Теперь, если и - совершенно нелинейные функции, то

.

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

.

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