Fungsi Boolean yang tidak konstan pada subruang affine dari dimensi yang cukup besar

Saya tertarik dengan fungsi Boolean eksplisit $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$dengan properti berikut: jika $f$ konstan pada beberapa subruang affine dari$\\{0,1\\}^n$ , maka dimensi dari subruang ini adalah$o(n)$ .

Tidak sulit untuk menunjukkan bahwa fungsi simetris tidak memuaskan properti ini dengan mempertimbangkan subruang $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\\}$. Setiap memiliki tepat n / 2 1 's dan karenanya f adalah konstanta subruang A dari dimensi n / 2 .$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

Objek yang Anda cari disebut disperser affine tanpa biji dengan satu bit keluaran. Lebih umum, disperser tanpa biji dengan satu bit keluaran untuk keluarga dari himpunan bagian dari { 0 , 1 } n adalah fungsi f : { 0 , 1 } n → { 0 , 1 } sedemikian rupa sehingga pada setiap subset S ∈ F , fungsi$\mathcal{F}$$\{0,1\}^n$$f : \{0,1\}^n \to \{0,1\}$$S \in \mathcal{F}$ tidak konstan. Di sini, Anda tertarik F menjadi keluarga ruang bagian affine$f$$\mathcal{F}$

Ben-Sasson dan Kopparty di "Affine penyebar dari Subruang Polinomial" tegas membangun penyebar affine tanpa biji untuk subruang dimensi setidaknya . Detail lengkap dari disperser agak terlalu rumit untuk dijelaskan di sini. $6n^{4/5}$

Kasus yang lebih sederhana yang juga dibahas dalam makalah ini adalah ketika kita menginginkan disperser afin untuk subruang dimensi . Kemudian, konstruksi mereka memandang F n 2 sebagai F 2 n dan menentukan disperser menjadi f ( x ) = T r ( x 7 ) , di mana T r : F 2 n → F 2 menunjukkan peta jejak: 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$ . Properti utama daritrace mapadalah bahwa T r ( x + y ) = T r ( x ) + T r ( y ) . $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$$Tr(x+y) = Tr(x) + Tr(y)$

Fungsi yang memenuhi sesuatu yang mirip dengan (tetapi jauh lebih lemah dari) apa yang Anda inginkan adalah penentu matriks atas . Hal ini dapat menunjukkan bahwa determinan dari suatu n × n matriks adalah non-konstan pada setiap ruang bagian affine dimensi setidaknya n 2 - $\mathbb{F}_2$$n\times n$$n^2 - n$ .