Enumeration of boolean functions with a fixed number of affine products.pdf 1. Случай обычных функций Пусть n ^ 0. Подсчитаем число двоичных функций от n переменных заданного веса, имеющих аффинные сомножители. Функция / : V™(2) ^ {0,1} имеет аффинные сомножители, если найдутся такие функция /(x) = (x,a*) ф b, x Е Vn(2), 0 = а* Е Е Vn(2)* (Vn(2)* - сопряжённое пространство), b Е {0,1} и функция h, что / = / ■ h. Пусть k Е {0,... ,n}. Обозначим через Fn(k) множество всех двоичных функций от n переменных, имеющих ровно k аффинных сомножителей. Функцию / = 0 не включаем ни в одно из множеств Fn(k). Легко видеть, что выполняется равенство n Fn = U Fn(k) U {0}. (1) fc=0 Справедливы следующие свойства: 1. Множества Fn(k) при разных k не пересекаются, k = 0,..., n. 2. Множества Fn(k), k = 0,...,n, инвариантны относительно действия полной аффинной группы AGL (n, 2) (и, следовательно, разбиваются на классы эквивалентности относительно этой группы). 3. Каждую функцию / Е Fn(k) можно привести с помощью некоторого аффинного преобразования к виду h(x) = / (xQ ф b) = xi... xfc g(xfc+i ,...,x™), (2) где g Е Fn-fc(0). 4. Если k Е {0,... , n} и / Е Fn(k), то 1 ^ ||/1| ^ 2n-k, где ||/1| -вес функции /. 5. Множество векторов, входящих в область истинности {а Е Vn(2) : /(а) = 1} функции / вида (2), порождает смежный класс по подпространству размерности n - k. Теорема 1. Пусть 1 ^ k ^ n и функции /, h Е Fn(k) и g Е Fn-k(0) удовлетворяют равенству (2). Тогда порядки групп инерции функций /, h и g в группе аффинных преобразований связаны равенством |AGL (n, 2)f | = |AGL (n, 2)fc| = 2k(n-k)|GL (k, 2)| ■ |AGL (n - k, 2)s|. (3) Доказательство вытекает из инвариантности подпространства, порождённого областью истинности функции. При n ^ 1 числа k-i 2га - 2® П ^-тй, если k е {1,...,n} i=0 2 - 2 1, если k = 0, n k 2 называются коэффициентами Гаусса (индекс 2 для простоты записи далее будем опускать). Теорема 2. При 1 ^ k ^ n справедливо равенство |F(k)| = 2k n k ' |Fn- k (4) Доказательство. Для каждой функции f е Fn(k) число эквивалентных ей функций совпадает с индексом группы инерции |f AGL(n,2)| = (AGL (n, 2) : AGL (n, 2f), который в силу теоремы 1 равен 2 для всех функций f е Fn(k), получаем формулу (4 n k |gAGL (га k,2) |. Применяя данное равенство Наряду с множествами Fn и Fn(k), k = 0,... , n, рассмотрим (2n + 1)-мерные вектор-столбцы Fj4 и F^(k), j -я координата которых равна числу функций из соответствующего множества, имеющих вес j, j = 0,..., 2n. Для этих векторов справедливо аналогичное (1) соотношение п Ft = Е Ft(k) + {4}, k=0 где е0 - вектор, у которого первая координата равна 1, а остальные - нули. В силу свойства 4 у векторов Fjj^k) первая координата и последние 2n - 2n-k координат равны нулю. Заметим, что в (2) веса функций f, h и g совпадают. Поэтому равенства, аналогичные (4), выполняются между первыми 2n-k + 1 координатами вектор-столбцов Fj4 и k (0). Дополним вектор k(0), имеющий длину 2n-k + 1, до вектора длины 2n + 1, полагая координаты с номерами j, 2n-k + 1 ^ j ^ 2n, равными нулю. С учётом этого дополнения можно записать равенство (4) в векторном виде Ft(k) = 2k n k Ft k (0). (5) В силу равенств (4) и (5) для вычисления значений F^(k), k = 0,... , n, достаточно вычислить лишь величины zm = |Fm(0)| и zmj = Fm(0)j, j = 0,... , 2m, m = 0,... , n. Воспользуемся равенством n 22П = E (k)| + 1, k=0 которое непосредственно вытекает из равенства (1) и свойства 1. Обозначая для краткости h(n,k) = 2k с учётом равенства (4) получаем рекуррентное соотношение n Zn = 22n - 1 - E h(n, k)zn-fc. n fc=i Аналогично, с учётом равенства (5) имеем zn0 = 0 и для j = 1,... , 2n 2n n Znj = . - Е h(n, k)zn-fc,j. (7) V j / fc=i 2n При этом при всех n ^ 0 выполнено равенство Е znj = zn. j=0 Рекуррентные соотношения (6) и (7) позволяют вычислять значения величин zn и znj, j = 0,... , 2n, последовательно для n = 0,1, 2,... В табл. 1 приведены соответствующие значения при n = 3. n k Таблица 1 |Fз | {0} |Fз (3) | |Fs(2)| |Fs (1)| |Fз (0) | 0 1 1 0 0 0 0 1 8 0 8 0 0 0 2 28 0 0 28 0 0 3 56 0 0 0 56 0 4 70 0 0 0 14 56 5 56 0 0 0 0 56 6 28 0 0 0 0 28 7 8 0 0 0 0 8 8 1 0 0 0 0 1 Всего 256 1 8 28 70 149 n Un = Е fc=0 Найдём теперь общий вид решений рекуррентных уравнений (6) и (7). Формула обращения Мёбиуса в данном случае принимает следующий вид. Утверждение 1 [1,2]. Если последовательности {un} и {wn} связаны соотношением n Wn-fc, k то n Wn = Е (-1)k2fc(fc+1)/2 n k fc=0 Переписав рекуррентное соотношение (6) в виде n ^ 0, Un-fc, n ^ 0. 22" - 1 n k 2n E fc=0 ^n-fc z" -г, с помо- 2n-fc' щью формулы обращения получаем следующий окончательный результат. Теорема 3. При всех n ^ 0 справедлива формула n k E(-1)fc 2^(k+1)/2 fc=0 (22 - 1)2k Zn Fn Эта формула позволяет, например, оценить вероятность pn того, что у функции f (xi,... , xn) есть аффинные сомножители: _ , zn pn 1 - . Значения вероятности pn при 1 ^ n ^ 10 представлены в табл. 2. Таблица 2 n Pn n Pn 1 0,75 6 2,9 ■ 10 -8 2 0,6875 7 1,3 10- -17 3 0,4218 8 1,4 10- -38 4 0,0809 9 8,8 10- -75 5 8,9 ■ 10-4 10 1,5 10- 151 2. Случай сравнения функций по модулю При -1 ^ s ^ n - 1 обозначим Us подпространство функций, степень нелинейности которых не превышает s (степень нулевой функции полагаем равной -1). Аналогично предыдущему случаю, при k е {0,..., n} обозначим через мно жество всех двоичных функций, имеющих ровно k линейно независимых аффинных сомножителей по модулю Us. Функции f е Us не включаем ни в одно из множеств jis)(k), k = 0,... , n. Легко видеть, что выполняется равенство п Fn = и Fs)(k) и Us. k=0 Заметим, что в работе [4] получена точная формула для числа функций от n переменных с алгебраической иммунностью равной 1, т. е. AIn(f) = 1. Этот класс функций можно записать в виде n Bi = и F0)(k). k=i Справедливы следующие свойства: 1. Множества Fls) (k) при разных k не пересекаются, k = 0,..., n. 2. Множества Fns)(k), k = 0,..., n, инвариантны относительно действия группы AGL (n, 2)Us (и, следовательно, разбиваются на классы эквивалентности относительно этой группы). 3. Каждую функцию f е Fls)(k) можно привести с помощью некоторого аффинного преобразования к виду h(x) = f (xQ 0 b) = xi ■ ■ ■ Xkg(xk+i,... ,Xn) (modUs), (8) где g е ^(0). Аналогично предыдущему случаю (подробнее см. [3]) доказываются: Теорема 4. Пусть s ^ 0, 1 ^ k ^ n и функции f, h е (k) и g е Fn!_"kk)(0) удовлетворяют равенству (8). Тогда порядки групп инерции функций f, h и g по модулю Us связаны равенством |AGL (n, 2)fs)| = |AGL (n, 2) j > s. Воспользуемся соотношением ) - I)|u(n1| = E (Fls)(k)^)j, k=0 которое непосредственно вытекает из свойства 1. С учётом равенства (9) и теоремы 5 при фиксированных j и s получаем соотношение если j = s + 1, |U-k | (n) (s-k) |Us | -^ii zn-k,j-^-(nn-kh, еслиj>s + 1. |Us-k | (n) (s-k) |Us n k Е k=0 n 2k k=0 "n-k,j-k , ,(n-k) (2(n) - 1)|Uj(n1| n k В табл. 3 приведены для примера соответствующие значения при n = 3. Таблица 3 s {Us} |F3s)(3)| Fs)(2)| Fs)(i)| Fs)(0)| -1 1 8 28 70 149 0 2 16 56 126 56 1 16 128 112 0 0 2 128 128 0 0 0 3 256 0 0 0 0

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