Qual é a probabilidade de uma função booleana aleatória ter um grupo trivial de automorfismo?

9

Dada uma função booleana , temos o grupo automorfismo .A u t ( f ) = { σ S nx , f ( σ ( x ) ) = f ( x ) }fAut(f)={σSn 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 ) ) GPrf(Aut(f)1)Prf(GAut(f))G

Samuel Schlesinger
fonte

Respostas:

4

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 }{ 0 , 1 } n π { 0 , 1 } n π f f π π [ n ] { 0 , 1 } n k π [ n ] c 1 c 2 nππAut(f)f(π(x))=f(x)x{0,1}nπ{0,1}nπffππ[n]{0,1}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 dekf2(k1)π[n]c1c2{0,1}nπ2Σici{0,1}nππUmut(f){0,1}nPr(πUmut(f))(1/2)M/i=1nici=n{0,1}nπ2ici{0,1}nπ. 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πAut(f){0,1}n 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 PrPr(πAut(f))(1/2)M/2M=2n2iciMiciπ1cic1=n2c2=1ci=n1M=2n2n1=2n1M2n1Pr(πAut(f))(1/2)2n2 . Agora aplique o limite da união:, então , que é basicamente como , rapidamente.|Sn|=n!Pr((πSn)[π1 and πAut(f)])n!22n22nlgn2n20n

Para qualquer você poderia usar um raciocínio semelhante, mas a probabilidade também chegará a zero muito rapidamente.GSn

Joshua Grochow
fonte
A probabilidade de f ser constante na órbita não seria $ 2 ^ {- k}?
Samuel Schlesinger
11
Obrigado por isso, a propósito, isso me lembra muito a prova da versão gráfica.
Samuel Schlesinger
11
Ah, eu entendo por que é 2(k1)
442 Samuel Schlesinger
11
@SamuelSchlesinger: Sim, semelhante. Eu acho que é ainda mais fácil nesse caso, porque o número de funções booleanas é dupla exponencial, enquanto o número de gráficos é apenas . 2n2nlgn
Joshua Grochow