Una función booleana que no es constante en subespacios afines de dimensión suficientemente grande

18

Estoy interesado en una función booleana explícita con la siguiente propiedad: si es constante en algún subespacio afín de , entonces la dimensión de este subespacio es .f:0,1n0,1f0,1no(n)

No es difícil demostrar que una función simétrica no satisface esta propiedad considerando un subespacio . Cualquier tiene exactamente 's y por lo tanto es constante el subespacio de dimensión .A=x0,1nx1x2=1,x3x4=1,,xn1xn=1n / 2 1 f A n / 2xAn/2 1fAn/2

Publicación cruzada: /mathpro/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

Alexander S. Kulikov
fuente
¿El rango de f debe ser {0,1} en lugar de {0,1} ^ n? De lo contrario, creo que la respuesta es trivial (f puede ser el mapeo de identidad).
Tsuyoshi Ito
Oh, lo siento, el rango es {0,1}, por supuesto. Fijo.
Alexander S. Kulikov el
Debido a que solicita una construcción explícita, supongo que un método probabilístico produce una prueba existencial. Una suposición descabellada: ¿qué sucede si identificamos {0,1} ^ n con el campo finito de orden 2 ^ n y dejamos f (x) = 1 si y solo si x corresponde a un cuadrado en el campo finito? El conjunto de residuos cuadráticos modular a primo a menudo parece aleatorio, y ahora necesitamos un conjunto de vectores que se ve aleatorio, por lo que usar el conjunto de cuadrados en un campo finito suena como un candidato natural. (No he resuelto esto en absoluto, y esto puede estar fuera de lugar.)
Tsuyoshi Ito
1
Cross publicado en MO . Agregue un enlace a su pregunta cuando realice una publicación cruzada.
Kaveh
1
También tenga en cuenta que se desaconseja la publicación cruzada simultánea .
Tsuyoshi Ito

Respuestas:

25

Los objetos que está buscando se denominan dispersores afines sin semillas con un bit de salida. Más en general, un dispersor sin semillas con un bit de salida para una familia de subconjuntos de { 0 , 1 } n es una función f : { 0 , 1 } n{ 0 , 1 } tal que en cualquier subconjunto S F , el La función f no es constante. Aquí, le interesa que F sea ​​la familia de subespacios afinesF{0,1}nf:{0,1}n{0,1}SFfF

Ben-Sasson y Kopparty en "Dispersantes afines de subespaciales Polinomios" construyen explícitamente dispersores afines sin semillas para subespacios de dimensión al menos . Los detalles completos del dispersor son demasiado complicados para describirlos aquí. 6n4/5

Un caso más simple también discutido en el documento es cuando queremos un dispersor afín para subespacios de dimensión . Luego, su construcción ve F n 2 como F 2 n y especifica que el dispersador sea f ( x ) = T r ( x 7 ) , donde T r : F 2 nF 2 denota el mapa de rastreo: T r ( x ) = n2n/5+10F2nF2nf(x)=Tr(x7)Tr:F2nF2. Una propiedad clave delmapa de rastreoes queTr(x+y)=Tr(x)+Tr(y). Tr(x)=i=0n1x2iTr(x+y)=Tr(x)+Tr(y)

arnab
fuente
Muchas gracias, Arnab! Parece que esto es exactamente lo que necesito, pero obviamente necesito tiempo para revisar el documento. =)
Alexander S. Kulikov
1
Una grabación de video de una charla de Swastik sobre el papel está aquí: video.ias.edu/csdm/affinedispersers
arnab
Gracias de nuevo, Arnab! Espero que el video me ayude a entender este documento (después de leer las primeras páginas veo que es bastante complicado).
Alexander S. Kulikov
9

Una función que satisface algo similar a (pero mucho más débil que) lo que desea es el determinante de una matriz sobre . Se puede demostrar que el determinante de una matriz n × n no es constante en ningún subespacio afín de dimensión al menos n 2 - n .F2n×nn2n

Ramprasad
fuente
Gracias Ramprasad! De hecho, esto es mucho más débil de lo que quiero. Pero aún así, ¿podría dar un enlace?
Alexander S. Kulikov
1
No sé de un lugar donde esto está escrito, pero la prueba no es difícil. Para probar la afirmación anterior, es suficiente demostrar que si toma el determinante de una matriz con variables en cada entrada, entonces el polinomio es un módulo n - 1 no lineal con funciones lineales. Observe que pasar módulo a una función lineal es simplemente reemplazar una de las entradas por una función lineal de los otros vars. Por lo tanto, queremos mostrar que reemplazar solo n - 1 entradas no puede matar el determinante. Debería ser fácil ver que con solo permutaciones, podemos mover todas estas entradas n - 1 por encima de la diagonal. [cntd]n×nn1n1n1
Ramprasad
Una vez que todas estas entradas se desplazan por encima de la diagonal, por supuesto, el determinante sigue siendo distinto de cero (dado que todas las entradas a continuación, incluida la diagonal, son independientes, podemos hacer que la diagonal inferior sea completamente cero y que la diagonal sea elementos distintos de cero para dar un determinante distinto de cero). El único truco aquí es que todas las entradas se pueden desplazar por encima de la diagonal. n1
Ramprasad
¡Gracias Ramprasad! De hecho, esto no es difícil de ver.
Alexander S. Kulikov