Quelle est la probabilité qu'une fonction booléenne aléatoire ait un groupe d'automorphisme trivial?

9

Étant donné une fonction booléenne , nous avons le groupe d'automorphisme A u t ( f ) = { σ S nx , f ( σ ( x ) ) = f ( x ) } .fAut(f)={σSn x,f(σ(x))=f(x)}

Existe-t-il des bornes connues sur ? Existe-t-il quelque chose de connu pour les quantités de la forme P r f ( G A u t ( f ) ) pour un groupe G ?Prf(Aut(f)1)Prf(GAut(f))G

Samuel Schlesinger
la source

Réponses:

4

Oui. Pour votre première question, la probabilité va à zéro à double exponentielle rapide. Cela peut être calculé comme suit. Pour chaque permutation , nous pouvons limiter la probabilité que π A u t ( f ) , c'est-à-dire que f ( π ( x ) ) = f ( x ) pour tout x { 0 , 1 } n . Considérons les orbites de π agissant sur { 0 , 1 } n . Nous avons cela πππAut(f)f(π(x))=f(x)x{0,1}nπ{0,1}nπest un automorphisme de si f est constant sur les π -orbites. Si π n'est pas trivial, il a au moins une orbite sur [ n ] qui n'est pas un singleton, et donc au moins sur une orbite sur { 0 , 1 } n qui n'est pas un singleton. Supposons que l'orbite contienne k éléments. La probabilité que f soit constant sur cette orbite est donc précisément 2 - ( k - 1 ) . Supposons que π agissant sur [ n ] affππ[n]{0,1}nkf2(k1)π[n] points fixes, c 2 cycles de longueur 2, etc. (en particuliern i = 1 i c i = n ). Alors le nombre de points de { 0 , 1 } n fixés par π est précisément 2 i c i . Tous les points restants de { 0 , 1 } n sont sur des orbites non triviales de π . À la limite supérieure, la probabilité que π A u t (c1c2je=1njecje=n{0,1}nπ2jecje{0,1}nπ , notons que la meilleure possibilité est que tous les éléments non fixes deπUNEut(F) viennent sur des orbites de taille 2. On obtient donc que P r ( π A u t ( f ) ) ( 1 / 2 ) M / 2 M = 2 n - 2 i c i . Maintenant, nous voulons une borne inférieure sur M , ce qui signifie que nous voulons une borne supérieure suri c{0,1}nPr(πAut(f))(1/2)M/2M=2n2iciM . Puisque π 1 , le plus grandc i peut être lorsque c 1 = n - 2 et c 2 = 1 , c'est-à-direc i = n - 1 et M = 2 n - 2 n - 1 = 2 n - 1 , donc M 2 n - 1 et P r ( π iciπ1cic1=n2c2=1ci=n1M=2n2n1=2n1M2n1 . Appliquez maintenant l'union liée: | S n | = n ! , donc P r ( ( π S n ) [ π 1  et  π A u t ( f ) ] ) n ! 2 - 2 nPr(πAut(f))(1/2)2n2|Sn|=n! , qui est fondamentalement2nlgn- 2 n - 20commen, assez rapidement.Pr((πSn)[π1 and πAut(f)])n!22n22nlgn2n20n

Pour tout vous pourriez utiliser un raisonnement similaire, mais la probabilité ira aussi très rapidement à zéro.GSn

Joshua Grochow
la source
La probabilité que f soit constante sur l'orbite ne serait-elle pas de $ 2 ^ {- k}?
Samuel Schlesinger
1
Merci pour cela d'ailleurs, cela me rappelle beaucoup la preuve de la version graphique.
Samuel Schlesinger
1
Oh, je vois pourquoi c'est 2(k1)
Samuel Schlesinger
1
@SamuelSchlesinger: Oui, similaire. Je pense que c'est encore plus facile dans ce cas car le nombre de fonctions booléennes est double exponentiel alors que le nombre de graphes n'est que . 2n2nlgn
Joshua Grochow