Una función booleana que no es constante en subespacios afines de dimensión suficientemente grande

Estoy interesado en una función booleana explícita con la siguiente propiedad: si es constante en algún subespacio afín de , entonces la dimensión de este subespacio es .$f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$$f$$\\{0,1\\}^n$$o(n)$

No es difícil demostrar que una función simétrica no satisface esta propiedad considerando un subespacio . Cualquier tiene exactamente 's y por lo tanto es constante el subespacio de dimensió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\\}$n / 2 1 f A n /$x \in A$$n/2$ $1$$f$$A$$n/2$

Publicación cruzada: /mathpro/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

Los objetos que está buscando se denominan dispersores afines sin semillas con un bit de salida. Más en general, un dispersor sin semillas con un bit de salida para una familia de subconjuntos de { 0 , 1 } n es una función f : { 0 , 1 } n → { 0 , 1 } tal que en cualquier subconjunto S ∈ F , el La función f no es constante. Aquí, le interesa que F sea ​​la familia de subespacios afines$\mathcal{F}$$\{0,1\}^n$$f : \{0,1\}^n \to \{0,1\}$$S \in \mathcal{F}$$f$$\mathcal{F}$

Ben-Sasson y Kopparty en "Dispersantes afines de subespaciales Polinomios" construyen explícitamente dispersores afines sin semillas para subespacios de dimensión al menos . Los detalles completos del dispersor son demasiado complicados para describirlos aquí. $6n^{4/5}$

Un caso más simple también discutido en el documento es cuando queremos un dispersor afín para subespacios de dimensión . Luego, su construcción ve F n 2 como F 2 n y especifica que el dispersador sea f ( x ) = T r ( x 7 ) , donde T r : F 2 n → F 2 denota el mapa de rastreo: T r ( x ) = ∑ $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$. Una propiedad clave delmapa de rastreoes queTr(x+y)=Tr(x)+Tr(y). $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$$Tr(x+y) = Tr(x) + Tr(y)$

Una función que satisface algo similar a (pero mucho más débil que) lo que desea es el determinante de una matriz sobre . Se puede demostrar que el determinante de una matriz n × n no es constante en ningún subespacio afín de dimensión al menos n 2 - n .$\mathbb{F}_2$$n\times n$$n^2 - n$