Пусть $%B=\{0,1\}$% - булево множество, $%B^n$% - его $%n$%-я декартова степень, $%F:B^n \to B^n$% - произвольное "булево отображение". Например, $%(y_1,y_2,\ldots,y_n)=F(x_1,x_2,\ldots,x_n)$% можно трактовать как систему булевых функций $%y_i=F_i(x_1,x_2,\ldots,x_n)$%, $%i=\overline{1,n}$%; $%F_i$% - булевы функции $%n$% переменных, их можно отождествить с многочленами Жегалкина, т.е. можно считать, что $%F_i$% - многочлены над полем $%B$%; их еще можно трактовать как $%F_i \mod 2$%, где $%F_i$% - "обычные" многочлены от нескольких переменных, "свободные от степеней", с коэффициентами из поля $%B$%. У меня такой вопрос. Пусть $%k$% - натуральное число, $%k<n$%. Существуют ли необходимые и достаточные условия для того, чтобы множество $$ L=\{x=(x_1,x_2,\ldots,x_n)\in B^n: \, x_1+x_2+\ldots+x_n=k\} $$ переходило в себя при отображении $%F$% ? То есть если $%x\in L$%, то $%y=F(x)\in L$%. Подробно, в развернутом виде: если $%x_1+x_2+\ldots+x_n=k$%, то $%y_1+y_2+\ldots+y_n=k$%. То есть отображение $%F$% как бы сохраняет определенное число единиц в количестве $%k$% штук.

Сложность в том, что в многочленах $%F_i$% сложение рассматривается по модулю 2, а в определении множества $%L$% рассматривается обычная сумма чисел $%x_1+x_2+\ldots+x_n$%, сумма из нулей и единиц, не по модулю 2.

задан 27 Май '17 17:59

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

Какое-то необходимое и достаточное условие всегда имеется -- вопрос в том, насколько простой или сложный вид оно будет иметь. Наборов из $%L$% имеется $%C_n^k$%, и каждому из них мы можем независимо сопоставить какой-то набор из $%L$%. Каждому набору не из $%L$% значение сопоставляется произвольно. Отсюда легко найти количество допустимых отображений. Каждое из них представляется в полиномиальной форме. При этом формально возникает какое-то условие, но интерес, наверное, представляет не это, а возможность лёгкого способа проверки, или какие-то достаточные условия для этого, или что-то ещё.

Можно предложить, например, полиномиальную (уже в терминах полиномов Жегалкина) форму самого условия, когда арифметическая сумма значений булевых переменных принимает значение $%k$%. То есть мы хотим указать полиномы $%g_{nk}(x_1,...,x_n)$% такие, что $%g_{nk}=0$% на наборах из $%L$%, и только на них.

Многочлены здесь все симметрические, поэтому они будут линейными комбинациями элементарных симметрических. Тогда задачу можно решить методом неопределённых коэффициентов, подставляя векторы с данным количеством нулей и единиц, и требуя, чтобы значение 0 получалось только на наборах с $%k$% единицами. Это даст систему линейных уравнений, которая имеет единственное решение. Для конкретных значений задача в принципе решается, но общий вид, боюсь, будет довольно сложным, так как там всё зависит от чётности биномиальных коэффициентов и прочего.

Если такое условие выписать, то для "игреков" можно выписать его же, и упростить. Тогда получится два полинома, и нужно, чтобы нули одного полинома автоматически давали нули другого. Это будет верно, если второй полином делится на первый. Скорее всего, есть и обратная связь, если использовать теорему Гильберта о нулях.

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

ссылка

отвечен 27 Май '17 20:53

Большое спасибо за ответ!

Вы пишете:

"То есть мы хотим указать полиномы $%g_{nk}(x_1,\ldots,x_n)$% такие, что $%g_{nk}=0$% на наборах из $%L$%, и только на них."

А можно пояснить подробнее? Как эти полиномы соотносятся с полиномами $%F_i$%? Мне не очень понятно...

(29 Май '17 16:23) Alsu

@Alsu: мы сначала описываем в виде полиномиального условия само множество L. Это описание от полиномов F_i никак не зависит. Но оно нужно для того, чтобы далее проверять, сохраняют ли L отображения F_i. А именно, мы в то же условие подставляем "игреки", это даёт какой-то полином H от "иксов". Относительно него мы задаём вопрос, верно ли, что если g_{nk}(x)=0, то g_{nk}(y)=H(x)=0. Достаточное условие -- делимость H на g_{nk}.

Если есть какой-то конкретный интересующий пример, можно было бы на нём протестировать изложенную идею.

(29 Май '17 22:51) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,480
×86

задан
27 Май '17 17:59

показан
533 раза

обновлен
29 Май '17 22:51

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

по почте:

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

по RSS:

Ответы

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

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