Полиномы на наборах из нулей и единиц

[DinaG]

Пусть $P(x_1,x_2,\ldots,x_n)$ - полином $n$ вещественных переменных. При каких условиях на коэффициенты этого полинома он принимает значения только 0 или 1 на наборах, состоящих из нулей и единиц? То есть более формально: если $x_k \in \{0,1\}$ $\forall k=\overline{1,n}$, то $P(x_1,x_2,\ldots,x_n)\in \{0,1\}$ (то есть либо $P(x_1,x_2,\ldots,x_n)=0$, либо $P(x_1,x_2,\ldots,x_n)=1$).

Понятно, что можно рассматривать только полиномы, "свободные от степеней" переменных, то есть полиномы, которые являются суммами одночленов вида $a_{i_{1},i_{2},\ldots, i_{m_{i}}} x_{i_{1}} x_{i_{2}} \ldots x_{i_{m_{i}}}$, так как 0 в любой натуральной степени равен 0, а 1 в любой натуральной степени равна 1.

[arseniiv]

Можно попытаться просто перебрать все такие полиномы (свободные от степеней и удовлетворяющие условию), их ведь $2^{2^n}$ штук — конечное число. Например, возьмите ДНФ произвольной булевой функции и преобразуйте её в многочлен, представив отрицание, конъюнкцию и дизъюнкцию в виде многочленов.

(Если никак не получается их подобрать)

Отрицание весьма просто — начинаем искать с линейного многочлена (раз константный явно не подходит) и находим его по двум точкам $(0;1)$ и $(1;0)$.
Конъюнкцию по старой традиции ещё иногда называют логическим умножением. Это может навести на мысль.
Дизъюнкция $a_1\vee\ldots\vee a_m$ представима через предыдущие две с помощью закона де Моргана как $\neg(\neg a_1\wedge\ldots\wedge\neg a_m)$.

После этого можно попытаться усмотреть в значениях получающихся коэффициентов какую-то систему.

[Sender]

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

[Xaositect]

Посмотрите Логачёв, Сальников, Ященко. "Булевы функции в теориикодирования и криптологии". Там во второй главе рассматривается связь между коэффициентами многочлена и коэффициентами Фурье булевой функции, а до этого рассматриваются условия, когда набор чисел является набором коэффициентов Фурье.

[realeugene]

Такие полиномы можно построить рекурсивно. Представьте ваш полином как $P(x_1,x_2,\ldots,x_n)=x_n Q(x_1,x_2,\ldots,x_{n-1})+R(x_1,x_2,\ldots,x_{n-1})$ Полином $R$ сам должен обладать требуемым свойством, но он зависит от меньшего числа переменных. Свободный член такого полинома может быть равен либо 0, либо 1. В первом случае полином $Q$ должен сам обладать требуемым свойством, а во втором случае он должен принимать значения только 0 или -1, т. е. должен быть полиномом с требуемым свойством, умноженным на -1.

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

PS Вывод замкнутой формы для коэффициентов закончите сами.

[realeugene]

Нет, я ошибся. Для $Q$ условие более сложное, выводящее его за пределы класса полиномов, возвращающих нуль или единицу.

В точках, где $R=0$, $Q$ должен обладать требуемым свойством. В точках, где $R=1$, $Q$ должен возвращает 0 или -1. Понятно, что $Q=(1-2R)S$, где $S$ - полином от $n-1$ переменной, возвращающий 0 или 1, является решением. Но как получить все допустимые решения?

[kotenok gav]

Очевидно, что каждый коэфициент равен 1 или 0.
Подставим $x_1=x_2=...=x_n=1$. Тогда сумма всех коэфициентов равна 1 или 0.
Следовательно, у нас не больше одного ненулевого коэфициента. Следовательно, у нас не больше одной переменной.

[Xaositect]

kotenok gav в сообщении #1248238 писал(а):

Очевидно, что каждый коэфициент равен 1 или 0.

Нет, например $x_1 + x_2 - 2x_1x_2$.

[realeugene]

kotenok gav в сообщении #1248238 писал(а):

Очевидно, что каждый коэфициент равен 1 или 0.

Это не так. Полином $-x_1+1$ допустимый, но коэффициенты у него иные.

[kotenok gav]

Я ошибся.

[realeugene]

В общем, для любого допустимого $P=P(x_1,x_2,\ldots,x_n)$ по модулю $x_i^2-x_i$ для всех $i$, в разложении $P=x_{n}Q(x_1,x_2,\ldots,x_{n-1})+R(x_1,x_2,\ldots,x_{n-1})$ полином $R$ - допустимый, а полином $Q$ таков, что полином

$$S=(1-2R)Q \mod x_1^2-x_1 \mod x_2^2-x_2\quad\cdots\mod x_{n-1}^2-x_{n-1}$$

тоже допустимый. Причём, если я не ошибаюсь, то

$$Q=(1-2R)S \mod x_1^2-x_1 \mod x_2^2-x_2\quad\cdots\mod x_{n-1}^2-x_{n-1}$$

Так что, можно строить допустимые полиномы рекурсивно.

[DinaG]

Спасибо за ответы. Да, это понятно, что $\overline{x}=1-x$, $x\wedge y=xy$, $x\vee y=1-(1-x)(1-y)=x+y-xy$.

А что будет, если рассматривать только линейные полиномы $P(x_1,x_2,\ldots, x_n)=a_1 x_1+a_2 x_2+\ldots+a_n x_n+b$ ?

Для $n=2$ их будет 6 штук: $0, 1, x, y, 1-x, 1-y$. А сколько их будет для произвольного $n$? Может, здесь есть какая-то закономерность для коэффициентов $a_1, a_2, \ldots, a_n, b$ ?

[realeugene]

Рассмотрите все произведения вида $x_1\overline{x_2}\overline{x_3}\cdots x_n$, где над некоторыми множителями расставлены черточки, которые означают $\overline{x_i}:=(1-x_i)$. Таких различных произведений всего $2^n$. Каждое такое произведение равно нулю всюду кроме одной своей точки рассматриваемой сетки, в которой оно равно 1. Умножив все эти произведения на коэффициенты, равные 0 или 1, и просуммировав, можно получить нужные значение на точках сетки для любого допустимого полинома, а раскрыв все скобки и сгруппировав одинаковые члены можно получить любой допустимый полином. Если вы найдёте способ обратно преобразовать любой допустимый полином в сумму рассматривавшихся произведений, вы получите и закономерности для коэффициентов.