Une fonction booléenne qui n'est pas constante sur des sous-espaces affines de dimension suffisamment grande

18

Je suis intéressé par une fonction booléenne explicite avec la propriété suivante: si est constant sur un sous-espace affine de , alors la dimension de ce sous-espace est .f:0,1n0,1f0,1no(n)

Il n'est pas difficile de montrer qu'une fonction symétrique ne satisfait pas cette propriété en considérant un sous-espace . Tout a exactement et donc est constant le sous-espace de dimension .A=x0,1nx1x2=1,x3x4=1,,xn1xn=1xAn/2 1fAn/2

Cross-post: /mathpro/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

Alexander S. Kulikov
la source
La plage de f est-elle censée être {0,1} au lieu de {0,1} ^ n? Sinon, je pense que la réponse est triviale (f peut être le mappage d'identité).
Tsuyoshi Ito
Oh, je suis désolé, la plage est {0,1}, bien sûr. Fixé.
Alexander S.Kulikov
Parce que vous demandez une construction explicite, je suppose qu'une méthode probabiliste donne une preuve existentielle. Une supposition sauvage: que se passe-t-il si nous identifions {0,1} ^ n avec le champ fini d'ordre 2 ^ n et laissons f (x) = 1 si et seulement si x correspond à un carré dans le champ fini? L'ensemble des résidus quadratiques modudo a prime semble souvent aléatoire, et maintenant nous avons besoin d'un ensemble de vecteurs qui semble aléatoire, donc l'utilisation de l'ensemble des carrés dans un champ fini ressemble à un candidat naturel. (Je n'ai pas du tout réglé cela, et cela peut être loin de la marque.)
Tsuyoshi Ito
1
Cross posté sur MO . Veuillez ajouter un lien vers votre question lorsque vous effectuez une publication croisée.
Kaveh
1
Notez également que le crossposting simultané est déconseillé .
Tsuyoshi Ito

Réponses:

25

Les objets que vous recherchez sont appelés disperseurs affines sans pépins avec un bit de sortie. Plus généralement, un disperseur sans pépins avec un bit de sortie pour une famille de sous-ensembles de { 0 , 1 } n est une fonction f : { 0 , 1 } n{ 0 , 1 } telle que sur tout sous-ensemble S F , le la fonction f n'est pas constante. Ici, vous êtes intéressé à ce que F soit la famille des sous-espaces affinesF{0,1}nf:{0,1}n{0,1}SFfF

Ben-Sasson et Kopparty dans « affines épandeurs de Subspace polynômes » construire explicitement disperseurs affines sans pépins de sous - espaces de dimension au moins . Les détails complets du disperseur sont un peu trop compliqués à décrire ici. 6n4/5

Un cas plus simple également discuté dans l'article est celui où nous voulons un disperseur affine pour des sous-espaces de dimension . Ensuite, leur construction considère F n 2 comme F 2 n et spécifie le disperseur f ( x ) = T r ( x 7 ) , où T r : F 2 nF 2 désigne la carte de trace: T r ( x ) = n2n/5+10F2nF2nf(x)=Tr(x7)Tr:F2nF2. Une propriété clé de lacarte de traceest queTr(x+y)=Tr(x)+Tr(y). Tr(x)=i=0n1x2iTr(x+y)=Tr(x)+Tr(y)

Arnab
la source
Merci beaucoup, Arnab! Il semble que c'est exactement ce dont j'ai besoin, mais j'ai évidemment besoin de temps pour parcourir le document. =)
Alexander S.Kulikov
1
Un enregistrement vidéo d'un discours de Swastik sur le papier est ici: video.ias.edu/csdm/affinedispersers
arnab
Merci encore, Arnab! J'espère que la vidéo m'aidera à comprendre cet article (après avoir lu les premières pages, je vois que c'est assez compliqué).
Alexander S.Kulikov
9

Une fonction qui satisfait quelque chose de similaire (mais beaucoup plus faible que) à ce que vous voulez est le déterminant d'une matrice sur . On peut montrer que le déterminant d'une matrice n × n n'est pas constant sur tout sous-espace affine de dimension au moins n 2 - n .F2n×nn2n

Ramprasad
la source
Merci, Ramprasad! C'est en effet beaucoup plus faible que je ne le souhaite. Mais encore, pourriez-vous s'il vous plaît donner un lien?
Alexander S.Kulikov
1
Je ne connais pas d'endroit où cela est écrit mais la preuve n'est pas difficile. Pour prouver la revendication ci-dessus, il suffit de montrer que si vous prenez le déterminant d'une matrice avec des variables dans chaque entrée, alors le polynôme est modulo n - 1 fonctions linéaires non nulles . Notez que pour modulo une fonction linéaire, il suffit de remplacer l'une des entrées par une fonction linéaire des autres vars. Par conséquent, nous voulons montrer que le remplacement de seulement n - 1 entrées ne peut pas tuer le déterminant. Il devrait être facile de voir que par de simples permutations, nous pouvons déplacer toutes ces n - 1 entrées au-dessus de la diagonale. [cntd]n×nn1n1n1
Ramprasad
Une fois que toutes ces entrées sont décalées au-dessus de la diagonale, il est bien sûr le cas où le déterminant reste toujours non nul (puisque toutes les entrées ci-dessous et y compris la diagonale sont indépendantes, on peut rendre la diagonale inférieure complètement nulle et la diagonale à être éléments non nuls pour donner un déterminant non nul). La seule astuce ici est que toutes les entrées peuvent être décalées au-dessus de la diagonale. n1
Ramprasad
Merci, Ramprasad! Ce n'est en effet pas difficile à voir.
Alexander S.Kulikov