Estimates for the number of boolean functions having affine or quadratic approximations with a given accuracy.pdf Пусть Vn = (GF(2))n. Обозначим через FJf" множество всех булевых функций ичерез Ln, An и Qn - множества всех линейных, аффинных и квадратичных функцийот n булевых аргументов соответственно; тогда Ln С An С Qn , |Ln| = 2n, |An | = 2n+1,|Qn| = 2 ( n ) + n + 1 .Пусть p ( f , g) = |{x G v. : f ( x ) = g(x)}| -расстояние Хэмминга между булевымифункциями f, g G F^" и p (f, A) = min p ( f , g) для произвольных f G F^" и A С F^".В [1-3] показано, что если f G F^" -случайная булева функция, имеющая равномер-ное распределение наFV" , то для каждого фиксированного x G Rlim P | p ( f , L n ) - "n < x l = 1 - e-ex, lim P I p ( f , - "n 0lim 2n-Xlim 2n- 2 "2 rn,1- 2 " Vn, An / - . 2 rn,1lim 2n-lim 2n- 2n- 2nF V " ' Q n (r+2F V " ' ( r - 20,1,где r±1 = 2n - 1 - (1 ± .)V2n - 1 n ln 2; r±> = 2n - 1 - (1 ± .)nV2n - 2 ln2.Теорема 1 [4]. Если n ^ 2, то(1 - Qi(n,r))2n + 1 . C2m ^ | FV"' a"(r)| ^ 2 n + 1 . C2 yrny2" ,m=0 m=0где Q1(n, r) = 0 при 0 ^ r < 2 n 2Q1(n,r) < -1 2 - ( c 2 - 3 ) n exp2(c2n)3 /215 I 2n /2при n ^ 8, r = 2 n - 1 - cV2n - 1 n l n 2 ^ 0 и c > 1.Следствие 1. Если rn = 2 n - 1 - c(n^v/2n -T n l n 2 ^ 0, c(n) > \/3/2 и n - то, тоQ1 (n,rn) - 0 .Теорема 2. Если n ^ 3, то(1 - Q2(n,r))2( " ) + n + 1 . C2m ^ | F V " ' ( r ) | ^ 2( " ) + n + 1 . CШy2" ,m=0 m=0где Q2(n, r) = 0 при 0 ^ r < 2 n 32- n 2 ( c 2 - 3 ) / 6 + n + 1 f (cn)3Q 2 ( n , r ) < ^ ex^ n 2при n ^ 15, r = 2 n - 1 - c W 2 n - 2 ln 2 ^ 0 и c > 1.Следствие 2. Если rn = 2 n - 1 - c(n)nV2n - 2 ln 2 ^ 0, c(n) > -\/3 и n - то, тоQ2 (n, rn) - 0 .Таким образом, если выполнены условия следствия 1 (следствия 2), то левые иправые части оценок (1) (оценок (2)) асимптотически эквивалентны.

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