Eine Boolesche Funktion, die bei affinen Unterbereichen mit ausreichend großer Dimension nicht konstant ist

Ich interessiere mich für eine explizite Boolesche Funktion $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ mit der folgenden Eigenschaft: wenn auf einem affinen Unterraum von konstant ist $f$ , dann ist die Dimension dieses Unterraums . $\\{0,1\\}^n$ $o(n)$

Es ist nicht schwierig zu zeigen, dass eine symmetrische Funktion diese Eigenschaft nicht erfüllt, indem ein Unterraum $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\\}$ . Jedes hat genau und daher ist konstant der Unterraum der Dimension . $x \in A$ $n/2$ $1$ $f$ $A$ $n/2$

Cross-Post: /mathpro/41129/a-boolean-function-that-ist-nicht-konstant-auf-affine-subspaces-of-large-enough-dimen

cc.complexity-theory circuit-complexity derandomization linear-algebra Alexander S. Kulikov
quelle

Soll der Bereich von f {0,1} anstelle von {0,1} ^ n sein? Ansonsten halte ich die Antwort für trivial (f kann die Identitätszuordnung sein).

Tsuyoshi Ito

Oh, es tut mir leid, der Bereich ist natürlich {0,1}. Fest.

Alexander S. Kulikov

Da Sie nach einer expliziten Konstruktion fragen, denke ich, dass eine probabilistische Methode einen existenziellen Beweis liefert. Eine wilde Vermutung: Was passiert, wenn wir {0,1} ^ n mit dem endlichen Feld der Ordnung 2 ^ n identifizieren und f (x) = 1 lassen, wenn und nur wenn x einem Quadrat im endlichen Feld entspricht? Die Menge der quadratischen Reste, die mit einem Primzahlwert erzeugt werden, sieht oft zufällig aus, und jetzt benötigen wir eine Menge von Vektoren, die zufällig aussehen. Die Verwendung der Menge der Quadrate in einem endlichen Feld klingt also wie ein natürlicher Kandidat. (Ich habe das überhaupt nicht geklärt, und dies könnte weit vom Ziel entfernt sein.)

Tsuyoshi Ito

Cross veröffentlicht am MO . Bitte fügen Sie einen Link zu Ihrer Frage hinzu, wenn Sie ein Cross-Posting durchführen.

Kaveh

Beachten Sie auch, dass gleichzeitiges Crossposting nicht empfohlen wird .

Tsuyoshi Ito

Antworten:

Die Objekte, nach denen Sie suchen, werden als kernlose affine Disperser mit einem Ausgangsbit bezeichnet. Allgemeiner ist ein kernloser Dispergierer mit einem Ausgangsbit für eine Familie von Teilmengen von eine Funktion so dass auf jeder Teilmenge die Funktion ist nicht konstant. Hier interessieren Sie sich für $\mathcal{F}$ $\{0,1\}^n$ $f : \{0,1\}^n \to \{0,1\}$ $S \in \mathcal{F}$ $f$ $\mathcal{F}$ die Familie der affinen Subräume ist

Ben-Sasson und Kopparty konstruieren in "Affin-Disperser aus Subraum-Polynomen" explizit kernlose Affin-Disperser für Subräume mit mindestens einer Dimension . Die vollständigen Details des Dispergierers sind etwas zu kompliziert, um sie hier zu beschreiben. $6n^{4/5}$

Ein einfacherer Fall, der ebenfalls in diesem Artikel diskutiert wird, ist, wenn wir einen affinen Disperser für Teilräume der Dimension . Dann sehen ihre Konstruktionen als und spezifizieren den Dispergierer als , wobei die Spurenkarte bezeichnet: $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$ $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$ . Eine Schlüsseleigenschaft der Spur der Karte ist , dass . $Tr(x+y) = Tr(x) + Tr(y)$

Arnab
quelle

Vielen Dank, Arnab! Es scheint, dass dies genau das ist, was ich brauche, aber offensichtlich brauche ich Zeit, um die Zeitung durchzugehen. =)

Alexander S. Kulikov

Eine Videoaufzeichnung einer Rede von Swastik auf dem Papier ist hier: video.ias.edu/csdm/affinedispersers

arnab

Nochmals vielen Dank, Arnab! Ich hoffe, das Video wird mir helfen, dieses Papier zu verstehen (nachdem ich die ersten Seiten gelesen habe, sehe ich, dass es ziemlich kompliziert ist).

Alexander S. Kulikov

Eine Funktion, die etwas Ähnliches erfüllt (aber viel schwächer ist als das, was Sie wollen), ist die Determinante einer Matrix über . Es kann gezeigt werden, dass die Determinante einer Matrix auf jedem affinen Unterraum der Dimension mindestens nicht konstant ist . $\mathbb{F}_2$ $n\times n$ $n^2 - n$

Ramprasad
quelle

Danke, Ramprasad! Das ist in der Tat viel schwächer als ich will. Aber bitte geben Sie einen Link an.

Alexander S. Kulikov

Ich kenne keinen Ort, an dem dies geschrieben steht, aber der Beweis ist nicht schwer. Um die obige Behauptung zu beweisen, ist es ausreichend zu zeigen, dass das Polynom von Null verschiedene modulo

lineare Funktionen ist, wenn Sie die Determinante einer

Matrix mit Variablen in jedem Eintrag nehmen . Beachten Sie, dass beim Modulo einer linearen Funktion nur einer der Einträge durch eine lineare Funktion der anderen Variablen ersetzt wird. Daher möchten wir zeigen, dass das Ersetzen von nur

Einträgen die Determinante nicht töten kann. Es sollte leicht zu erkennen sein, dass wir durch bloße Permutationen all diese

Einträge über die Diagonale verschieben können. [cntd]

n \times n

$n\times n$

n - 1

$n-1$

n - 1

$n-1$

n - 1

$n-1$

Ramprasad

Sobald alle diese Einträge über die Diagonale verschoben sind, bleibt die Determinante natürlich immer noch ungleich Null (da alle Einträge unter und einschließlich der Diagonale unabhängig sind, können wir die untere Diagonale vollständig zu Null und die Diagonale zu Null machen Nicht-Null-Elemente, um eine Nicht-Null-Determinante zu erhalten). Der einzige Trick dabei ist, dass alle

Einträge über die Diagonale verschoben werden können.

n - 1

$n-1$

Ramprasad

Vielen Dank, Ramprasad! Das ist in der Tat nicht schwer zu sehen.

Alexander S. Kulikov