Какова вероятность того, что случайная булева функция имеет тривиальную группу автоморфизмов?

9

Для булевой функции мы имеем группу автоморфизмов .fAut(f)={σSn x,f(σ(x))=f(x)}

Есть ли известные границы для ? Известно ли что-нибудь для величин вида для некоторой группы ?Prf(Aut(f)1)Prf(GAut(f))G

Сэмюэль Шлезингер
источник

Ответы:

4

Да. На ваш первый вопрос вероятность быстро падает до нуля в два раза. Это можно рассчитать следующим образом. Для каждой перестановкиπмы можем ограничить вероятность того, что πAut(f)то есть f(π(x))=f(x) для всех x{0,1}n, Рассмотрим орбитыπ действующий на {0,1}n, У нас есть этоπ это автоморфизм f тогда и только тогда f постоянно на π-орбит. Еслиπ нетривиален, имеет хотя бы одну орбиту на [n] это не одиночка, и поэтому по крайней мере на орбите {0,1}nэто не синглтон. Предположим, что орбита имеетkэлементы в нем. Вероятность того, чтоf постоянна на этой орбите, таким образом, точно 2(k1), Предположим, чтоπ действующий на [n] имеет c1 фиксированные точки, c2 циклы длины 2 и т. д. (в частности i=1nici=n). Тогда количество баллов{0,1}n фиксируется π это точно 2ici, Все остальные точки{0,1}n находятся на нетривиальных орбитах π, Для верхней границы вероятности того, чтоπAut(f)обратите внимание, что лучшая возможность, если все нефиксированные элементы {0,1}n прийти на орбитах размера 2. Таким образом, мы получаем, что Pr(πAut(f))(1/2)M/2 где M=2n2ici, Теперь мы хотим нижнюю границуM, что означает, что мы хотим верхнюю границу Σяся, посколькуπ1, самый большой Σся может быть, когда с1знак равноN-2 а также с2знак равно1т.е. Σсязнак равноN-1 а также Mзнак равно2N-2N-1знак равно2N-1, так M2N-1 а также пр(πAUT(е))(1/2)2N-2, Теперь примените объединенное ограничение:|SN|знак равноN!, так пр((πSN)[π1 а также πAUT(е)])N!2-2N-2что в основном 2NЛ.Г.N-2N-20 в виде Nдовольно быстро

Для любого данного гSN Вы могли бы использовать аналогичные рассуждения, но вероятность также очень быстро упадет до нуля.

Джошуа Грохов
источник
Разве вероятность того, что f будет постоянной на орбите, не будет $ 2 ^ {- k}?
Сэмюэль Шлезингер
1
Спасибо за это, кстати, это напоминает мне много доказательств версии графа.
Сэмюэль Шлезингер
1
О, я понимаю, почему это 2-(К-1)
Сэмюэль Шлезингер
1
@SamuelSchlesinger: Да, похоже. Я думаю, что это даже проще в этом случае, потому что число булевых функций является двойным экспоненциальным, тогда как число графов только~2N2-NЛ.Г.N,
Джошуа Грохов