Булева функция, которая не постоянна на аффинных подпространствах достаточно большой размерности

18

Меня интересует явная булева функция со следующим свойством: если постоянна в некотором аффинном подпространстве , то размерность этого подпространства равна .е:0,1N0,1е о ( п )0,1Nо(N)

Нетрудно показать, что симметрическая функция не удовлетворяет этому свойству, рассматривая подпространство Aзнак равноИкс0,1N|Икс1Икс2знак равно1,Икс3Икс4знак равно1,...,ИксN-1ИксNзнак равно1, Любое имеет ровно n / 2 1 , и, следовательно, f является постоянным подпространством A размерности n / 2 .ИксAN/2 1еAN/2

Кросс-пост: /mathpro/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

Александр Сергеевич Куликов
источник
Должен ли диапазон f быть {0,1} вместо {0,1} ^ n? В противном случае я думаю, что ответ тривиален (f может быть отображением тождества).
Цуёси Ито
О, извините, диапазон, конечно, {0,1}. Исправлена.
Александр Сергеевич Куликов
Поскольку вы просите явную конструкцию, я полагаю, что вероятностный метод дает экзистенциальное доказательство. Неожиданное предположение: что произойдет, если мы отождествим {0,1} ^ n с конечным полем порядка 2 ^ n и пусть f (x) = 1 тогда и только тогда, когда x соответствует квадрату в конечном поле? Множество квадратичных вычетов по модулю простого часто выглядит случайным, и теперь нам нужен набор векторов, который выглядит случайным, поэтому использование набора квадратов в конечном поле звучит как естественный кандидат. (Я вообще не работал над этим, и это может быть далеко от цели.)
Tsuyoshi Ito
1
Крест размещен на МО . Пожалуйста, добавьте ссылку на свой вопрос, когда вы кросс-публикации.
Каве
1
Также обратите внимание, что одновременный кросспостинг не рекомендуется .
Цуёси Ито

Ответы:

25

Объекты, которые вы ищете, называются аффинными распределителями без косточек с одним выходным битом. В более общем плане , без косточек диспергатора с одним выходным битом для семьи подмножеств { 0 , 1 } п является функцией F : { 0 , 1 } п{ 0 , 1 } такое , что на любое подмножество S F , то функция f не является постоянной. Здесь вас интересует, что F - это семейство аффинных подпространствF{0,1}nf:{0,1}n{0,1}SFfF

Бен-Сассон и Kopparty в «Аффинные Разбрасывателях из подпространства полиномов» явно построить бессемянные аффинные диспергаторы для подпространств размерности по крайней мере , . Полную информацию о диспергаторе слишком сложно описать здесь. 6n4/5

Более простой случай, который также обсуждается в статье, - это когда нам нужен аффинный диспергатор для подпространств размерности . Затем их конструкция рассматривает F n 2 как F 2 n и определяет диспергатор как f ( x ) = T r ( x 7 ) , где T r : F 2 nF 2 обозначает карту трасс: T r ( x ) = н2n/5+10F2nF2nе(Икс)знак равноTр(Икс7)Tр:F2NF2. Ключевым свойствомкарты трассявляется то, чтоTr(x+y)=Tr(x)+Tr(y). Tр(Икс)знак равноΣязнак равно0N-1Икс2яTр(Икс+Y)знак равноTр(Икс)+Tр(Y)

Арнаб
источник
Большое спасибо, Арнаб! Кажется, это именно то, что мне нужно, но, очевидно, мне нужно время, чтобы просмотреть документ. =)
Александр Сергеевич Куликов
1
Видеозапись выступления Свастика на бумаге находится здесь: video.ias.edu/csdm/affinedispersers
arnab
Еще раз спасибо, Арнаб! Я надеюсь, что видео поможет мне понять эту статью (после прочтения первых нескольких страниц я вижу, что она довольно сложная).
Александр Сергеевич Куликов
9

Функция, которая удовлетворяет чему-то похожему (но гораздо более слабому), чем вы хотите, является определителем матрицы над . Можно показать, что определитель матрицы n × n является непостоянным на любом аффинном подпространстве размерности, по крайней мере, n 2 - n .F2N×NN2-N

Ramprasad
источник
Спасибо, Рампрасад! Это действительно намного слабее, чем я хочу. Но все же, не могли бы вы дать ссылку?
Александр Сергеевич Куликов
1
Я не знаю места, где это написано, но доказательство не сложно. Для доказательства приведенного выше утверждения достаточно показать, что если вы берете определитель матрицы с переменными в каждой записи, то многочлен будет отличен от нуля по модулю n - 1 линейных функций. Обратите внимание, что переход по модулю линейной функции - это просто замена одной из записей на линейную функцию других переменных. Следовательно, мы хотим показать, что замена только n - 1 записей не может уничтожить определитель. Должно быть легко увидеть, что просто перестановками мы можем переместить все эти n - 1 элементов выше диагонали. [cntd]N×NN-1N-1N-1
Рампрасад
Как только все эти элементы смещены выше диагонали, это, конечно, тот случай, когда определитель по-прежнему остается ненулевым (поскольку все элементы, расположенные ниже и включая диагональ, являются независимыми, мы можем сделать нижнюю диагональ полностью нулевой, и диагональ должна быть ненулевые элементы, чтобы дать ненулевой определитель). Единственная хитрость здесь в том, что все элементов могут быть смещены выше диагонали. N-1
Рампрасад
Спасибо, Рампрасад! Это действительно не трудно увидеть.
Александр Сергеевич Куликов