Uma função booleana que não é constante em subespaços afins de dimensão grande o suficiente

18

Estou interessado em uma função booleana explícita com a seguinte propriedade: se for constante em algum subespaço afim de , então a dimensão deste subespaço é .f:0,1n0,1f0,1no(n)

Não é difícil mostrar que uma função simétrica não satisfaz essa propriedade considerando um subespaço . Qualquer tem exatamente 's e, portanto, é constante o subespaço da dimensão .A=x0,1nx1x2=1,x3x4=1,,xn1xn=1xAn/2 1fAn/2

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

Alexander S. Kulikov
fonte
O intervalo de f deve ser {0,1} em vez de {0,1} ^ n? Caso contrário, acho que a resposta é trivial (f pode ser o mapeamento de identidade).
Tsuyoshi Ito
Ah, desculpe, o intervalo é {0,1}, é claro. Fixo.
Alexander S. Kulikov
Como você pede uma construção explícita, acho que um método probabilístico produz uma prova existencial. Um palpite: O que acontece se identificarmos {0,1} ^ n com o campo finito da ordem 2 ^ n e deixar f (x) = 1 se e somente se x corresponder a um quadrado no campo finito? O conjunto de resíduos quadráticos modudo a primo geralmente parece aleatório, e agora precisamos de um conjunto de vetores que pareça aleatório; portanto, usar o conjunto de quadrados em um campo finito soa como um candidato natural. (Eu não resolvi isso de jeito nenhum, e isso pode estar muito
errado
1
Cruz postada em MO . Adicione um link para sua pergunta quando você estiver postando mensagens cruzadas.
Kaveh
1
Observe também que a interposição cruzada simultânea é desencorajada .
Tsuyoshi Ito

Respostas:

25

Os objetos que você está procurando são chamados de dispersores afins sem sementes com um bit de saída. De maneira mais geral, um dispersor sem sementes com um bit de saída para uma família de subconjuntos de { 0 , 1 } n é uma função f : { 0 , 1 } n{ 0 , 1 } de modo que em qualquer subconjunto S F , o a função f não é constante. Aqui, você está interessado em F ser a família de subespaços afinsF{0,1}nf:{0,1}n{0,1}SFfF

Ben-Sasson e Kopparty em "Affine Dispergadores de Subspace polinómios" construir explicitamente dispersores afins sem sementes para subespaços de dimensão pelo menos . Os detalhes completos do dispersor são um pouco complicados demais para serem descritos aqui. 6n4/5

Um caso mais simples também discutido no artigo é quando queremos um dispersor afim para subespaços da dimensão . Então, sua construção visualiza F n 2 como F 2 n e especifica que o dispersor é f ( x ) = T r ( x 7 ) , onde T r : F 2 nF 2 denota o mapa de traços: T r ( x ) = n2n/5+10F2nF2nf(x)=Tr(x7)Tr:F2nF2. Uma propriedade chave domapa de rastreioé queTr(x+y)=Tr(x)+Tr(y). Tr(x)=i=0n1x2iTr(x+y)=Tr(x)+Tr(y)

arnab
fonte
Muito obrigado, Arnab! Parece que é exatamente disso que preciso, mas obviamente preciso de tempo para ler o jornal. =)
Alexander S. Kulikov
1
A gravação de vídeo de uma palestra de Swastik do papel está aqui: video.ias.edu/csdm/affinedispersers
Arnab
Mais uma vez obrigado, Arnab! Espero que o vídeo me ajude a entender este artigo (depois de ler as primeiras páginas, vejo que é bastante complicado).
Alexander S. Kulikov
9

Uma função que satisfaz algo semelhante ao (mas muito mais fraco que) o que você deseja é o determinante de uma matriz em relação a . Pode ser demonstrado que o determinante de um n × n matriz é não constante em qualquer subespaço afim de dimensão, pelo menos n 2 - n .F2n×nn2n

Ramprasad
fonte
Obrigado, Ramprasad! Isso é realmente muito mais fraco do que eu quero. Mas ainda assim, você poderia dar um link?
Alexander S. Kulikov
1
Não conheço um lugar onde isso esteja escrito, mas a prova não é difícil. Para provar a afirmação acima, é suficiente para mostrar que se você tomar o determinante de um matriz com variáveis em cada entrada, então o polinômio é diferente de zero modulo n - 1 funções lineares. Observe que passar para o módulo uma função linear é apenas substituir uma das entradas por uma função linear dos outros vars. Portanto, queremos mostrar que a substituição de apenas n - 1 entradas não pode matar o determinante. Deve ser fácil ver que, com apenas permutações, podemos mover todas essas entradas n - 1 acima da diagonal. [cntd]n×nn1n1n1
Ramprasad
Uma vez que todas essas entradas são deslocadas acima da diagonal, é claro que o determinante ainda permanece diferente de zero (como todas as entradas abaixo e incluindo a diagonal são independentes, podemos tornar a diagonal inferior completamente zero e a diagonal a ser elementos diferentes de zero para fornecer um determinante diferente de zero). O único truque aqui é que todas as entradas podem ser deslocadas acima da diagonal. n1
Ramprasad
Obrigado, Ramprasad! Isso realmente não é difícil de ver.
Alexander S. Kulikov