On quadratic form rank distribution and asymptotic bounds of affinity level.pdf 1. Распределение ранга квадратичных форм Под квадратичной формой здесь понимается двоичная функция, степень нелинейности которой не превосходит двух. Каждую квадратичную форму от n переменных ранга 2r, 1 ^ r ^ |_n/2_|, можно линейным преобразованием аргументов привести к виду Ж1Ж2 е Ж3Ж4 е • • • е x2r-1X2r е /(x1,..., xn), где / - некоторая аффинная функция. Так как вид линейной функции / не влияет на значение ранга, то вероятность того, что квадратичная форма от n переменных имеет ранг 2r, определяемую как относительную долю таких форм, можно записать в виде p2r (n) = Qr (n)/2n(n-1)/2, где Qr (n) - число квадратичных форм от n переменных ранга 2r. Из описания групп автоморфизмов квадратичных форм [1-3] следует, что (2n - 1)... (2n - 22r-1) Qr(n) = |Sp(2r, 2)| , 2 r где Sp(2r, 2) -симплектическая группа, имеющая прядок |Sp(2r, 2)| = 2r П (22i - 1). i=1 При 1 ^ r ^ n/2 - 1 справедливо соотношение Qr (n) _ 4 (х_ 1 Qr+1(n) (2n-2r - 1)(2n-2r-1 - 1) V 22r+2 Поэтому числа Qr(n), 1 ^ r ^ n/2, образуют монотонно возрастающую последовательность. Оценим вероятность максимальности ранга. При n = 2k имеем P2k(2k) = i1 - 7^) i1 - ...(1 - 1 22fc-1 / I 22k-3 / ' ' ' \ 2 Аналогично при n = 2k + 1 имеем P2k(2k + 1) = i1 - ^ I1 - 22^) .. 11 - 23 В частности, p2k-2(2k - 1) = 2р2к(2k) при k ^ 2. Верхнюю оценку вероятности p2k (2k) с наперёд заданной точностью можно получить путём перемножения только части сомножителей в произведении (1): P2k(2k) = П (4 - ^ < .11 (1 - < О,4194224428. Нижнюю оценку вероятности р2к(2k) можно получить, используя подход из работы [4]: к / 1 \ k 1 / 1 ■ -ln P2k (2k) 1 - - = - E E - ^ I 02i-1 / ^ ^ m \ 02i-1 i=1 \ 5 / i=1 m=1 m \2 2m ^ / 1 V _ 2-m 1 - 1/(22m)k ^ _l o2m / _ 1 1 /02m ' m=1 mttrV 22 / m=1 m 1 - 1/2 При k > s можно воспользоваться приближённой формулой 22m s-1 2-m / 1 ln P2k (2k) > --2- ln2 - E 1 22m - 1 m=1 m V22m - 1 22r-1 В частности, полагая s = 8, получаем, что при k > 8 имеет место нижняя оценка р2к(2k) > 0,41942244. Поэтому при больших чётных n = 2k 0,4194224428 > р2к(2k) > 0,41942244. При больших нечетных n = 2k + 1 получаем 0,8388448856 > p2k(2k + 1) = 2p2k+2(2k + 2) > 0,83884488. Теорема 1. Пусть k = [n/2], n = 2k + e и 0 ^ c ^ 1. При n ^ ж доля квадратичных форм от n переменных ранга меньшего, чем 2k - 2 \/(log2 k)/2 + (c + (-1)£)/2 , стремится к нулю. Поэтому для ранга почти всех квадратичных форм q от n переменных при n ^ ж справедлива нижняя оценка: Для математического ожидания ранга случайной квадратичной формы от n переменных можно привести следующую оценку. Теорема 2. Пусть k = [n/2]. При n ^ ж математическое ожидание ранга случайной квадратичной формы q от n переменных оценивается следующим образом: 1) при n = 2k имеем 2k - 0,60196883564 < E r(q) < 2k - 0,6019688356 (1 - 1/2n); 2) при n = 2k + 1 имеем 2k - 0,1625309417 < E r(q) < 2k - 0,1625309415 (1 - 1/2n). 2. Оценка уровня аффинности квадратичной формы Уровень аффинности la(f) двоичной функции f определяется как минимальное число переменных, произвольная фиксация значений которых делает функцию аффинной. Обобщённый уровень аффинности La(f) двоичной функции f определяется как минимальное число линейных комбинаций переменных, некоторая фиксация значений которых делает функцию аффинной. Эти параметры связаны неравенством [5] La(f) ^ la(f). Квадратичную форму от n переменных ранга 2r можно линейным преобразованием аргументов привести к виду q(x1, . . . , xn) = x1x2 Ф x3x4 ф ■ ■ ■ ф x2r-1x2r Ф /(xb . . . ,xn), где 1(x1,... , xn) -некоторая аффинная функция. Поскольку обобщенный уровень аффинности квадратичной формы ранга 2r равен r, то из приведённых выше асимптотических оценок ранга вытекает Следствие 1. Пусть 0 ^ c ^ 1. При n ^ го, n = 2k + е, 0 ^ е ^ 1, доля квадратичных форм от n переменных, имеющих обобщённый уровень аффинности меньший, чем k - \J(log2 k)/2 + (c +(-1)£)/2 , стремится к нулю. Для обобщённого уровня аффинности почти всех квадратичных форм от n переменных при n ^ го справедлива нижняя оценка: Отсюда следует, что оценки уровня аффинности почти всех квадратичных форм из работы [5] не являются точными. Следствие 2. Пусть k = [n/2]. При n ^ го математическое ожидание обобщённого уровня аффинности L«(q) случайной квадратичной формы q от n переменных оценивается следующим образом: 1) при чётных n k - 0,30098441782 < E L«(q) < k - 0,3009844178 (1 - 1/2n); 2) при нечётных n k - 0,8126547085 < E L«(q) < k - 0,8126547075 (1 - 1/2n).

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