Uma função booleana que não é constante em subespaços afins de dimensão grande o suficiente

Estou interessado em uma função booleana explícita com a seguinte propriedade: se for constante em algum subespaço afim de , então a dimensão deste subespaço é .$f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$$f$$\\{0,1\\}^n$$o(n)$

Não é difícil mostrar que uma função simétrica não satisfaz essa propriedade considerando um subespaço . Qualquer tem exatamente 's e, portanto, é constante o subespaço da dimensão .$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$

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

Os objetos que você está procurando são chamados de dispersores afins sem sementes com um bit de saída. De maneira mais geral, um dispersor sem sementes com um bit de saída para uma família de subconjuntos de { 0 , 1 } n é uma função f : { 0 , 1 } n → { 0 , 1 } de modo que em qualquer subconjunto S ∈ F , o a função f não é constante. Aqui, você está interessado em F ser a família de subespaços afins$\mathcal{F}$$\{0,1\}^n$$f : \{0,1\}^n \to \{0,1\}$$S \in \mathcal{F}$$f$$\mathcal{F}$

Ben-Sasson e Kopparty em "Affine Dispergadores de Subspace polinómios" construir explicitamente dispersores afins sem sementes para subespaços de dimensão pelo menos . Os detalhes completos do dispersor são um pouco complicados demais para serem descritos aqui. $6n^{4/5}$

Um caso mais simples também discutido no artigo é quando queremos um dispersor afim para subespaços da dimensão . Então, sua construção visualiza F n 2 como F 2 n e especifica que o dispersor é f ( x ) = T r ( x 7 ) , onde T r : F 2 n → F 2 denota o mapa de traços: 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$. Uma propriedade chave domapa de rastreioé queTr(x+y)=Tr(x)+Tr(y). $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$$Tr(x+y) = Tr(x) + Tr(y)$

Uma função que satisfaz algo semelhante ao (mas muito mais fraco que) o que você deseja é o determinante de uma matriz em relação a . Pode ser demonstrado que o determinante de um n × n matriz é não constante em qualquer subespaço afim de dimensão, pelo menos n 2 - n .$\mathbb{F}_2$$n\times n$$n^2 - n$