Доказать, что функция, реализуемая полиномом Жегалкина степени k > 0, принимает каждое из значения 0 и 1 не менее чем на 2^(n-k) наборах.

задан 20 Фев '18 22:57

10|600 символов нужно символов осталось
1

Достаточно доказать, что многочлен от n переменных степени <=k, не являющийся константой, обращается в ноль по крайней мере на 2^{n-k} наборах. Тогда применение этого утверждения к многочлену f+1 даёт не менее 2^{n-k} наборов, на которых f равен единице.

Для k=1 утверждение очевидно, так как полином имеет вид a+x+... , где a=0 или 1, а хотя бы одна из переменных присутствует. Меняя значения x, мы получаем поровну, то есть по 2^{n-1}, значений многочлена, равных как 0, так и 1.

Пусть k > 1. Будем проводить индукцию по n. Рассмотрим переменную x, которая входит в запись многочлена. Представим его в виде Ax+B, где A, B -- многочлены от оставшихся n-1 переменной. При этом либо deg B=k, либо deg B < k, и тогда deg A=k-1.

В первом случае можно положить x=0, получая многочлен от n-1 переменной степени k. По предположению, он равен нулю не менее чем на 2^{n-1-k} наборах. Поскольку deg A <=k-1, при x=1 мы получим многочлен A+B, степень которого равна k. Он также равен нулю не менее чем на 2^{n-1-k} наборах. Вместе получается не менее 2^{n-k}. Заметим, что наборы при x=0 и при x=1 учитываются заведомо разные.

Во втором случае, если B не константа, полагаем x=0, получая многочлен B от n-1 переменной степени <=k-1. По предположению, он обращается в ноль как минимум на 2^{(n-1)-(k-1)}=2^{n-k} наборах. Если B -- тождественный ноль, но при x=0 имеем 2^{n-1} набор, где функция равна нулю. Если B -- тождественная единица, то полагаем x=1, получая многочлен A+1 от n-1 переменной степени ровно k-1. Как и выше, это даёт не менее 2^{n-k} нулей многочлена.

ссылка

отвечен 20 Фев '18 23:52

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,481
×160

задан
20 Фев '18 22:57

показан
676 раз

обновлен
20 Фев '18 23:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru