Funkcja boolowska, która nie jest stała w podprzestrzeniach afinicznych o wystarczająco dużym wymiarze

Interesuje mnie wyraźna funkcja boolowska $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$z następującą właściwością: jeśli jest stałe w jakiejś podprzestrzeni afinicznej$f$ , wówczas wymiar tej podprzestrzeni wynosi o ( n ) .$\\{0,1\\}^n$$o(n)$

Nie jest trudno wykazać, że funkcja symetryczna nie spełnia tej właściwości, biorąc pod uwagę podprzestrzeń $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\\}$. Dowolne ma dokładnie n / 2 1 ', a zatem f jest stałą podprzestrzenią A wymiaru 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

Szukane obiekty nazywane są beznasiennymi rozpraszaczami afinicznymi z jednym bitem wyjściowym. Bardziej ogólnie, dyspergator pestek o jeden bit wyjściowy dla rodziny podzbioru { 0 , 1 } n jest funkcją f : { 0 , 1 } n → { 0 , 1 } , tak że w każdej podgrupie S ∈ F The funkcja f nie jest stała. Tutaj interesuje Cię, że F jest rodziną podprzestrzeni afinicznych$\mathcal{F}$$\{0,1\}^n$$f : \{0,1\}^n \to \{0,1\}$$S \in \mathcal{F}$$f$$\mathcal{F}$

Ben-Sasson i Kopparty w „afinicznej rozprowadzenia z podprzestrzeni wielomianów” wyraźnie skonstruować niezaziarniony rozprowadzających afiniczne do podprzestrzeni o wymiarze co najmniej . Pełne szczegóły dyspergatora są nieco zbyt skomplikowane, aby je tutaj opisać. $6n^{4/5}$

Prostszy przypadek omówiony również w artykule dotyczy sytuacji, gdy chcemy afinicznego dyspergatora dla podprzestrzeni o wymiarze . Następnie postrzega ich budowa M n 2 a F 2 n i określa dyspergującego być F ( x ) = t R ( x 7 ) , w którym T r : F 2 n → F 2 oznacza mapę śledzenia: 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$. Kluczową właściwościąmapy śledzeniajest to, żeTr(x+y)=Tr(x)+Tr(y). $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$$Tr(x+y) = Tr(x) + Tr(y)$

Funkcja, która spełnia coś podobnego (ale znacznie słabszego), niż chcesz, jest wyznacznikiem macierzy nad . Można wykazać, że wyznacznik macierzy n × n nie jest stały w dowolnej afinicznej podprzestrzeni wymiaru co najmniej n 2 - n .$\mathbb{F}_2$$n\times n$$n^2 - n$