Une fonction booléenne qui n'est pas constante sur des sous-espaces affines de dimension suffisamment grande

Je suis intéressé par une fonction booléenne explicite avec la propriété suivante: si est constant sur un sous-espace affine de , alors la dimension de ce sous-espace est .$f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$$f$$\\{0,1\\}^n$$o(n)$

Il n'est pas difficile de montrer qu'une fonction symétrique ne satisfait pas cette propriété en considérant un sous-espace . Tout a exactement et donc est constant le sous-espace de dimension .$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$

Cross-post: /mathpro/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

Les objets que vous recherchez sont appelés disperseurs affines sans pépins avec un bit de sortie. Plus généralement, un disperseur sans pépins avec un bit de sortie pour une famille de sous-ensembles de { 0 , 1 } n est une fonction f : { 0 , 1 } n → { 0 , 1 } telle que sur tout sous-ensemble S ∈ F , le la fonction f n'est pas constante. Ici, vous êtes intéressé à ce que F soit la famille des sous-espaces affines$\mathcal{F}$$\{0,1\}^n$$f : \{0,1\}^n \to \{0,1\}$$S \in \mathcal{F}$$f$$\mathcal{F}$

Ben-Sasson et Kopparty dans « affines épandeurs de Subspace polynômes » construire explicitement disperseurs affines sans pépins de sous - espaces de dimension au moins . Les détails complets du disperseur sont un peu trop compliqués à décrire ici. $6n^{4/5}$

Un cas plus simple également discuté dans l'article est celui où nous voulons un disperseur affine pour des sous-espaces de dimension . Ensuite, leur construction considère F n 2 comme F 2 n et spécifie le disperseur f ( x ) = T r ( x 7 ) , où T r : F 2 n → F 2 désigne la carte de trace: 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$. Une propriété clé de lacarte de traceest queTr(x+y)=Tr(x)+Tr(y). $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$$Tr(x+y) = Tr(x) + Tr(y)$

Une fonction qui satisfait quelque chose de similaire (mais beaucoup plus faible que) à ce que vous voulez est le déterminant d'une matrice sur . On peut montrer que le déterminant d'une matrice n × n n'est pas constant sur tout sous-espace affine de dimension au moins n 2 - n .$\mathbb{F}_2$$n\times n$$n^2 - n$