Berapa probabilitas bahwa fungsi Boolean acak memiliki kelompok automorfisme sepele?

Iya. Untuk pertanyaan pertama Anda, probabilitasnya menjadi nol dua kali lipat secara eksponensial cepat. Ini dapat dihitung sebagai berikut. Untuk setiap permutasi , kita dapat mengikat probabilitas bahwa , yaitu bahwa untuk semua . Pertimbangkan orbit bekerja pada . Kami memiliki adalah automorfisme dari jika adalah konstan pada aktivitas. Jika adalah non-trivial, ia memiliki setidaknya satu orbit pada yang bukan singleton, dan karenanya setidaknya pada orbit pada $\pi$ $\pi \in Aut(f)$ $f(\pi(x)) = f(x)$ $x \in \{0,1\}^n$ $\pi$ $\{0,1\}^n$ $\pi$ $f$ $f$ $\pi$ $\pi$ $[n]$ $\{0,1\}^n$ itu bukan singleton. Misalkan orbit memiliki elemen di dalamnya. Dengan demikian, probabilitas bahwa adalah konstan pada orbit itu adalah . Misalkan bekerja pada memiliki titik tetap, siklus dengan panjang 2, dll. (Khususnya ). Maka jumlah titik diperbaiki oleh tepatnya . Semua poin tersisa dari berada dalam orbit nontrivial dari . Untuk batas atas probabilitas bahwa $k$ $f$ $2^{-(k-1)}$ $\pi$ $[n]$ $c_1$ $c_2$ $\sum_{i=1}^n i c_i = n$ $\{0,1\}^n$ $\pi$ $2^{\sum_i c_i}$ $\{0,1\}^n$ $\pi$ $\pi \in Aut(f)$ , perhatikan bahwa kemungkinan terbaik adalah jika semua elemen non-tetap dari datang dalam ukuran orbit 2. Jadi kita mendapatkan mana . Sekarang, kami ingin batas bawah pada , yang berarti kami ingin batas atas pada . Sejak , terbesar dapat terjadi ketika dan , yaitu dan , jadi dan . Sekarang terapkan ikatan serikat: $\{0,1\}^n$ $Pr(\pi \in Aut(f)) \leq (1/2)^{M/2}$ $M = 2^n - 2^{\sum_i c_i}$ $M$ $\sum_i c_i$ $\pi \neq 1$ $\sum c_i$ $c_1 = n-2$ $c_2 = 1$ $\sum c_i = n-1$ $M = 2^n - 2^{n-1} = 2^{n-1}$ $M \geq 2^{n-1}$ $Pr(\pi \in Aut(f)) \leq (1/2)^{2^{n-2}}$ $|S_n| = n!$ , jadi , yang pada dasarnya adalah sebagai , cukup cepat. $Pr((\exists \pi \in S_n)[\pi \neq 1 \text{ and } \pi \in Aut(f)]) \leq n! 2^{-2^{n-2}}$ $2^{n \lg n - 2^{n-2}} \to 0$ $n \to \infty$

Untuk setiap Anda dapat menggunakan alasan yang serupa, tetapi probabilitasnya juga akan menjadi nol dengan sangat cepat. $G \leq S_n$

Joshua Grochow
sumber

Bukankah probabilitas f konstan pada orbit adalah $ 2 ^ {- k}?

Samuel Schlesinger

Terima kasih untuk ini, ini mengingatkan saya pada banyak bukti versi grafik.

Samuel Schlesinger

Oh, saya mengerti mengapa ini

2^{- (k - 1)}

$2^{-(k-1)}$

Samuel Schlesinger

@SamuelSchlesinger: Ya, mirip. Saya pikir ini lebih mudah dalam hal ini karena jumlah fungsi boolean adalah eksponensial ganda sedangkan jumlah grafik hanya

\sim 2^{n^{2} - n \lg n}

$\sim 2^{n^2 - n \lg n}$

Joshua Grochow

Berapa probabilitas bahwa fungsi Boolean acak memiliki kelompok automorfisme sepele?

Jawaban: