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

18

Ich interessiere mich für eine explizite Boolesche Funktion f:0,1n0,1mit der folgenden Eigenschaft: wenn auf einem affinen Unterraum von konstant istf , dann ist die Dimension dieses Unterraums o ( n ) .0,1no(n)

Es ist nicht schwierig zu zeigen, dass eine symmetrische Funktion diese Eigenschaft nicht erfüllt, indem ein Unterraum A=x0,1nx1x2=1,x3x4=1,,xn1xn=1. Jedes hat genau n / 2 1 und daher ist f konstant der Unterraum A der Dimension n / 2 .xAn/2 1fAn/2

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

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
1
Cross veröffentlicht am MO . Bitte fügen Sie einen Link zu Ihrer Frage hinzu, wenn Sie ein Cross-Posting durchführen.
Kaveh
1
Beachten Sie auch, dass gleichzeitiges Crossposting nicht empfohlen wird .
Tsuyoshi Ito

Antworten:

25

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 { 0 , 1 } n eine Funktion f : { 0 , 1 } n{ 0 , 1 }, so dass auf jeder Teilmenge S F die Funktion f ist nicht konstant. Hier interessieren Sie sich für FF{0,1}nf:{0,1}n{0,1}SFfF 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. 6n4/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 F n 2 als F 2 n und spezifizieren den Dispergierer als f ( x ) = T r ( x 7 ) , wobei T r : F 2 nF 2 die Spurenkarte bezeichnet: T r ( x ) = n2n/5+10F2nF2nf(x)=Tr(x7)Tr:F2nF2Tr(x)=i=0n1x2i . 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
1
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
9

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 n × n- Matrix auf jedem affinen Unterraum der Dimension mindestens n 2 - n nicht konstant ist .F2n×nn2n

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
1
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 n - 1 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 n - 1 Einträgen die Determinante nicht töten kann. Es sollte leicht zu erkennen sein, dass wir durch bloße Permutationen all diese n - 1 Einträge über die Diagonale verschieben können. [cntd]n×nn1n1n1
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. n1
Ramprasad
Vielen Dank, Ramprasad! Das ist in der Tat nicht schwer zu sehen.
Alexander S. Kulikov