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

Меня интересует явная булева функция со следующим свойством: если постоянна в некотором аффинном подпространстве , то размерность этого подпространства равна . $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ $f$ $\\{0,1\\}^n$ $o(n)$

Нетрудно показать, что симметрическая функция не удовлетворяет этому свойству, рассматривая подпространство $A=\\{x \in \\{0,1\\}^n \mid x_1 \oplus x_2=1, x_3 \oplus x_4=1, \dots, x_{n-1} \oplus x_n=1\\}$ , Любое имеет ровно , и, следовательно, является постоянным подпространством размерности . $x \in A$ $n/2$ $1$ $f$ $A$ $n/2$

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

cc.complexity-theory circuit-complexity derandomization linear-algebra Александр Сергеевич Куликов
источник

Должен ли диапазон f быть {0,1} вместо {0,1} ^ n? В противном случае я думаю, что ответ тривиален (f может быть отображением тождества).

Цуёси Ито

О, извините, диапазон, конечно, {0,1}. Исправлена.

Александр Сергеевич Куликов

Поскольку вы просите явную конструкцию, я полагаю, что вероятностный метод дает экзистенциальное доказательство. Неожиданное предположение: что произойдет, если мы отождествим {0,1} ^ n с конечным полем порядка 2 ^ n и пусть f (x) = 1 тогда и только тогда, когда x соответствует квадрату в конечном поле? Множество квадратичных вычетов по модулю простого часто выглядит случайным, и теперь нам нужен набор векторов, который выглядит случайным, поэтому использование набора квадратов в конечном поле звучит как естественный кандидат. (Я вообще не работал над этим, и это может быть далеко от цели.)

Tsuyoshi Ito

Крест размещен на МО . Пожалуйста, добавьте ссылку на свой вопрос, когда вы кросс-публикации.

Каве

Также обратите внимание, что одновременный кросспостинг не рекомендуется .

Цуёси Ито

Ответы:

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

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

Более простой случай, который также обсуждается в статье, - это когда нам нужен аффинный диспергатор для подпространств размерности . Затем их конструкция рассматривает как и определяет диспергатор как , где обозначает карту трасс: $2n/5+10$ ${\mathbb{F}}_2^n$ ${\mathbb{F}}_{2^n}$ $f(x) = Tr(x^7)$ $Tr: {\mathbb{F}}_{2^n} \to {\mathbb{F}}_2$ . Ключевым свойствомкарты трассявляется то, что. $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$ $Tr(x+y) = Tr(x) + Tr(y)$

Арнаб
источник

Большое спасибо, Арнаб! Кажется, это именно то, что мне нужно, но, очевидно, мне нужно время, чтобы просмотреть документ. =)

Александр Сергеевич Куликов

Видеозапись выступления Свастика на бумаге находится здесь: video.ias.edu/csdm/affinedispersers

arnab

Еще раз спасибо, Арнаб! Я надеюсь, что видео поможет мне понять эту статью (после прочтения первых нескольких страниц я вижу, что она довольно сложная).

Александр Сергеевич Куликов

Функция, которая удовлетворяет чему-то похожему (но гораздо более слабому), чем вы хотите, является определителем матрицы над . Можно показать, что определитель матрицы является непостоянным на любом аффинном подпространстве размерности, по крайней мере, . $\mathbb{F}_2$ $n\times n$ $n^2 - n$

Ramprasad
источник

Спасибо, Рампрасад! Это действительно намного слабее, чем я хочу. Но все же, не могли бы вы дать ссылку?

Александр Сергеевич Куликов

Я не знаю места, где это написано, но доказательство не сложно. Для доказательства приведенного выше утверждения достаточно показать, что если вы берете определитель матрицы

с переменными в каждой записи, то многочлен будет отличен от нуля по модулю

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

записей не может уничтожить определитель. Должно быть легко увидеть, что просто перестановками мы можем переместить все эти

элементов выше диагонали. [cntd]

n \times n

$n\times n$

n - 1

$n-1$

n - 1

$n-1$

n - 1

$n-1$

Рампрасад

Как только все эти элементы смещены выше диагонали, это, конечно, тот случай, когда определитель по-прежнему остается ненулевым (поскольку все элементы, расположенные ниже и включая диагональ, являются независимыми, мы можем сделать нижнюю диагональ полностью нулевой, и диагональ должна быть ненулевые элементы, чтобы дать ненулевой определитель). Единственная хитрость здесь в том, что все

элементов могут быть смещены выше диагонали.

n - 1

$n-1$

Рампрасад

Спасибо, Рампрасад! Это действительно не трудно увидеть.

Александр Сергеевич Куликов