Dada uma função booleana , temos o grupo automorfismo .A u t ( f ) = { σ ∈ S n ∣ ∀ x , f ( σ ( x ) ) = f ( x ) }
Existem limites conhecidos no ? Existe algo conhecido por quantidades do formato para algum grupo ?P r f ( G ≤ A u t ( f ) ) G
fonte
Dada uma função booleana , temos o grupo automorfismo .A u t ( f ) = { σ ∈ S n ∣ ∀ x , f ( σ ( x ) ) = f ( x ) }
Existem limites conhecidos no ? Existe algo conhecido por quantidades do formato para algum grupo ?P r f ( G ≤ A u t ( f ) ) G
Sim. Para sua primeira pergunta, a probabilidade chega a zero duas vezes exponencialmente rápido. Isso pode ser calculado da seguinte maneira. Para cada permutação , podemos limitar a probabilidade de que , ou seja, que para todos os . Considere as órbitas de atuando em . Temos que é um automorfismo de se é constante nos -orbits. Se não é trivial, ele tem pelo menos uma órbita em que não é um singleton e, portanto, pelo menos em órbita emπ ∈ A u t ( f ) f ( π ( x ) ) = f ( x ) x ∈ { 0 , 1 } nπ { 0 , 1 } n π { 0 , 1 } n π f f π π [ n ] { 0 , 1 } n k π [ n ] c 1 c 2 ∑ nisso não é um singleton. Suponha que a órbita tenha elementos. A probabilidade de que f seja constante nessa órbita é, portanto, precisamente 2 - ( k - 1 ) . Suponha que agindo em tenha pontos fixos, ciclos de comprimento 2, etc. (em particular ). Então o número de pontos de fixado por é precisamente . Todos os pontos restantes de estão em órbitas não triviais de{0,1}nπ2Σici{0,1}nππ∈Umut(f){0,1}nPr(π∈Umut(f))≤(1/2)M/. Para limitar acima a probabilidade de , observe que a melhor possibilidade é se todos os elementos não fixos de tiverem órbitas de tamanho 2. Portanto, obtemos esse que . Agora, queremos um limite inferior em , o que significa que queremos um limite superior em . Como , a maior pode ser quando e , ou seja, e , então e H= 2 n - 2 Σ i c i H Σ i c i ¸≠1Σ c i c 1 =N-2 c 2 =1Σ c i =n-1M= 2 n - 2 n - 1 = 2 n - 1 M≥ 2 n - 1 Pr . Agora aplique o limite da união:, então , que é basicamente como , rapidamente.
Para qualquer você poderia usar um raciocínio semelhante, mas a probabilidade também chegará a zero muito rapidamente.