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 . $\\{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 ', a zatem jest stałą podprzestrzenią wymiaru . $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

— Alexander S. Kulikov
źródło

Czy zakres f ma wynosić {0,1} zamiast {0,1} ^ n? W przeciwnym razie myślę, że odpowiedź jest trywialna (f może być odwzorowaniem tożsamości).

— Tsuyoshi Ito,

Przykro mi, zakres wynosi oczywiście {0,1}. Naprawiony.

— Alexander S. Kulikov

Ponieważ pytasz o wyraźną konstrukcję, sądzę, że metoda probabilistyczna daje dowód na istnienie. Dzikie zgadywanie: co się stanie, jeśli zidentyfikujemy {0,1} ^ n skończonym polem rzędu 2 ^ n i pozwolimy f (x) = 1 wtedy i tylko wtedy, gdy x odpowiada kwadratowi w polu skończonym? Zbiór kwadratowych reszt modudo liczba pierwsza często wygląda losowo, a teraz potrzebujemy zestawu wektorów, które wyglądają losowo, więc użycie zestawu kwadratów w polu skończonym brzmi jak naturalny kandydat. (W ogóle tego nie opracowałem i może to być daleko od celu.)

— Tsuyoshi Ito,

Krzyż wysłany na MO . Dodaj link do swojego pytania, gdy piszesz krzyżowo.

— Kaveh

Należy również pamiętać, że odradza się jednoczesne crossspostowanie .

— Tsuyoshi Ito

Odpowiedzi:

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 jest funkcją , tak że w każdej podgrupie The funkcja nie jest stała. Tutaj interesuje Cię, że 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 a i określa dyspergującego być , w którym oznacza mapę śledzenia: $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, że. $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$ $Tr(x+y) = Tr(x) + Tr(y)$

— arnab
źródło

Wielkie dzięki, Arnab! Wydaje się, że tego właśnie potrzebuję, ale oczywiście potrzebuję czasu, aby przejrzeć gazetę. =)

— Alexander S. Kulikov,

Nagranie wideo z przemówienia Swastika na papierze znajduje się tutaj: video.ias.edu/csdm/affinedispersers

— arnab

Jeszcze raz dziękuję, Arnab! Mam nadzieję, że wideo pomoże mi zrozumieć ten artykuł (po przeczytaniu kilku pierwszych stron widzę, że jest to dość skomplikowane).

— Alexander S. Kulikov

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

— Ramprasad
źródło

Dzięki, Ramprasad! To jest rzeczywiście znacznie słabsze, niż chcę. Ale czy możesz podać link?

— Alexander S. Kulikov,

Nie znam miejsca, w którym jest to spisane, ale dowód nie jest trudny. Aby udowodnić powyższe twierdzenie, wystarczy pokazać, że jeśli weźmiesz wyznacznik macierzy

ze zmiennymi w każdym wpisie, to wielomian jest niezerowym modułem

funkcji liniowych. Zauważ, że przejście modulo na funkcję liniową to po prostu zastąpienie jednego z wpisów funkcją liniową pozostałych zmiennych. Dlatego chcemy pokazać, że zastąpienie tylko

pozycji nie może zabić wyznacznika. Powinno być łatwo zauważyć, że za pomocą permutacji możemy przenieść wszystkie te

wpisy powyżej przekątnej. [cntd]

n \times n

$n\times n$

n - 1

$n-1$

n - 1

$n-1$

n - 1

$n-1$

— Ramprasad

n - 1

$n-1$

Dziękuję, Ramprasad! To naprawdę nie jest trudne do zobaczenia.

— Alexander S. Kulikov